0
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! I'm also reading Ng's notes, but the ones from the Stanford Education Everywhere program, and this wasn't discussed in the notes (might be in the lecture, didn't check yet though). Great stuff! Thanks again! $\endgroup$ – lte__ Sep 21 '16 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.