I wonder when to use linear regression with stochastic or batch gradient descent to minimize the cost function vs when to use normal equations? The algorithms using gradient descent are iterative, so they might take more time to run, as opposed to the normal equation solution, which is a closed form equation. But it does use matrices to store the training data. Does this mean gradient solutions require more processing power, but using the normal equation method requires more memory because of the matrices? Which method is optimal in what scenario?
Andrew Ng answers this question succinctly in his Coursera lecture about the normal equation. I will summarize.
You have m training examples and n features.
Disadvantages of gradient descent:
- you need to choose the learning rate, so you may need to run the algorithm at least a few times to figure that out.
- it needs many more iterations, so, that could make it slower
Compared to the normal equation:
- you don't need to choose any learning rate
- you don't need to iterate
Disadvantages of the normal equation:
- Normal Equation is computationally expensive when you have a very large number of features ( n features ), because you will ultimately need to take the inverse of a n x n matrix in order to solve for the parameters data.
Compared to gradient descent:
- it will be reasonably efficient and will do something acceptable when you have a very large number ( millions ) of features.
So if n is large then use gradient descent.
If n is relatively small ( on the order of a hundred ~ ten thousand ), then the normal equation