Question

Show the per-iteration computational cost of Gradient Descent for Linear Regression is O(nd); n is the sample size, d is the dimension.

Answer 1

in order to answer the question we need to have basic understanding of following terms :

1. Linear_regression : LA is another technique in machine learning which can be used to predict output given some input and attributes. The attributes here are trainable and are used later for prediction once the training phase is completed. the Dimension of a linear regression problem is defined by how many attributes it has and said to have n dimension for n attributes.
2. Gradient Descent : Its just an algorithm and rather a powerful one to minimize the error we get from the regression model and the target output during training phase. This error is then propagated back to the network to adjust the trainable parameters like attributes in this case. The very basic equation used to update the weights or attributes is : new_weights = old_weights - (learning_rate * error)

So now we can see one probable dependency when we run gradient descent on linear regression model . that is , the update is required for each and every attribute and hence is to the worst o(d)

and also now to mention , GD is done on each and every instance of the training dataset and so this whole above mentioned process is repeated n no of times where n is the number of sample in the dataset. So clearly there is one more dependency on the sample size.

Both combined , we can get the total computational cost or time complexity which O(nd).