I read about regression in machine learning and came across this gradient descent algorithm to find the minimum value of a cost function. Then I read wikipedia to know more and it says the following

enter image description here

But then I started thinking of what I learnt in my high school math like the one described here in these Khan Academy lectures. The way to take derivative and second derivative test to find maximum and minimum. Then I started wondering why we need iterative gradient descent algorithm when we have the above mentioned high school math method.

I am not sure if I have understood things wrongly.

Can you help me understand why we need gradient descent here ?

  • $\begingroup$ What if the objective function is polynomial? To find the critical points, one needs to solve a system of polynomial equations, which is in the realm of algebraic geometry. One can then use Groebner bases, but that is not exactly taught in high school, is it? $\endgroup$ – Rodrigo de Azevedo Jun 11 '17 at 10:16
  • $\begingroup$ Actually the simplest problem in my head is logistic regression: try to write down its objective and derivative and set the derivative to 0. You'll find that you can't get the solution in closed form, because there isn't. The solution must be find using some iterative method like gradient descent $\endgroup$ – Yining Wang Jun 21 '17 at 15:04

A couple reasons:

  1. Sometimes we cannot solve the minimization problem by hand. This includes situations where we have an explicit form for the function but the equations for the local minima are not able to be solved in closed form and also situations where we don't have an explicit form for the function (but of course we can still compute it).

  2. Sometimes even in situations where we have a nice formula for the minimum, it can be computationally more efficient to use gradient descent than to compute the formula. This includes very high-dimensional linear regressions. The formula for the least squares estimator is well-known but it involves inverting a potentially large matrix. At a certain point gradient descent starts to be faster, cause it contains less expensive operations even though you must iterate them many times to find the minimum.

  • $\begingroup$ Good answer. My followup: gradient descent is not the only numerical optimization algorithm. $\endgroup$ – Ian Jun 11 '17 at 2:45
  • $\begingroup$ We are not going to do it by hand. Why can't we write one time code for that ? But whichever resource I take to study machine learning only talks more about gradient descent algo when it comes to minimizing cost function. $\endgroup$ – Harish Kayarohanam Jun 11 '17 at 2:46
  • $\begingroup$ Can you give examples to support your answer ? $\endgroup$ – Harish Kayarohanam Jun 11 '17 at 2:47
  • $\begingroup$ @HarishKayarohanam 1) First, never write one-time code if you don't need to (except as a learning experience, of course). Second, what do you imagine this code doing? $\endgroup$ – spaceisdarkgreen Jun 11 '17 at 3:35
  • $\begingroup$ @HarishKayarohanam 2) For my second point I already gave an example of large regression problems. It's similar in spirit, to, say, finding the roots of a cubic equation. Sure, there's a closed form solution, but it's horrible and why bother when you can just use a root solver (or code up newton's method in shorter time than it would take you to enter the cubic formula right)? It might even be computationally more efficient at the end of the day. $\endgroup$ – spaceisdarkgreen Jun 11 '17 at 3:42

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.