9
$\begingroup$

When we can differentiate the cost function and find parameters by solving equations obtained through partial differentiation with respect to every parameter and find out where the cost function is minimum. Also I think its possible to find multiple places where the derivatives are zero, thereby we can check for all such places and can find global minima

why is gradient descent performed instead?

$\endgroup$
  • 2
    $\begingroup$ How does one generically set the derivatives to 0 for a function? With algorithms, such as gradient descent. $\endgroup$ – Cliff AB May 15 '16 at 3:12
  • 3
    $\begingroup$ You can think of gradient descent as the method used to solve the equations you are referring to. If you are under the belief that you can generically solve such equations with clever algebraic manipulation, I invite you to try to do so for logistic regression. $\endgroup$ – Matthew Drury May 15 '16 at 3:29
  • 3
    $\begingroup$ Probable duplicate Solving for regression parameters in closed-form vs gradient descent $\endgroup$ – Glen_b -Reinstate Monica May 15 '16 at 9:19
  • 1
    $\begingroup$ Also see stackoverflow.com/questions/26804656/… $\endgroup$ – Glen_b -Reinstate Monica May 16 '16 at 0:53
  • $\begingroup$ you can't solve everything analytically. Even if you could, if there were say, uncountable number of zeros, then you'd take a long time to check all critical points. $\endgroup$ – Pinocchio Jun 7 '16 at 17:55
7
$\begingroup$

Even in the case of, say, linear models, where you have an analytical solution, it may still be best to use such an iterative solver.

As an example, if we consider linear regression, the explicit solution requires inverting a matrix which has complexity $O(N^3)$. This becomes prohibitive in the context of big data.

Also, a lot of problems in machine learning are convex, so using gradients ensure that we will get to the extrema.

As already pointed out, there are still relevant non-convex problems, like neural networks, where gradient methods (backpropagation) provide an efficient solver. Again this is specially relevant for the case of deep learning.

$\endgroup$
  • 2
    $\begingroup$ Inverting a matrix is a bit of a strawman here as QR decomposition with partial pivoting is more accurate and faster, but yeah, QR is still $O(n^3)$. I agree that for sufficiently large systems (eg. > 10,000 variables) that can start becoming a problem. The modern, high tech approach is then to approximate the solution with iterative Krylov subspace methods (eg. conjugate gradient, GMRES). $\endgroup$ – Matthew Gunn May 20 '16 at 7:43
  • 1
    $\begingroup$ A point some people may find confusing is how is solving a linear system an optimization problem? The answer of course is that solving a linear system can be reframed as minimizing a quadratic objective. Some iterative methods for solving linear systems are easier to understand from the perspective that they're minimizing a quadratic objective in an iterative fashion. (Eg. the Krylov subspace method conjugate gradient's step direction is based on the gradient... it's loosely related to gradient descent.) $\endgroup$ – Matthew Gunn May 20 '16 at 7:48
12
$\begingroup$

Gradient descent is not required. It turns out gradient descent is often a horribly inefficient optimization algorithm! For iterative methods, it is often possible to find a better direction to move in than where the gradient is steepest.

That's a bit of a flip answer though. Your question really should be, "why do we need iterative methods?" Eg. why not go straight to the solution if the problem is convex, Slater's condition holds, and the first order conditions are necessary and sufficient conditions for an optimum? That is, when the solution can be described as the solution to a system of equations, why not simply solve the system? The answer is that:

  • For a quadratic optimization problem, the first order condition is a system of linear equations, and we can go almost directly to the solution because linear systems can be efficiently solved! We do use the first order conditions and solve the system (eg. with QR decomposition, caveat below).
  • More generally though, the first order conditions define a non-linear system of equations and a non-linear system may be quite difficult to solve! In fact, the way you often solve a system of non-linear equations numerically is you reformulate it as an optimization problem...
  • For extremely large linear systems, solving the system directly with QR decomposition and partial pivoting becomes infeasible. What do people do?! Iterative methods! (eg. iterative Krylov subspace methods...)
$\endgroup$
7
$\begingroup$

In calculus 101 we learned about how to optimize a function using "analytical method": we just need to get the derivative of cost function and set the derivative to 0 then solve the equation. This is really a toy problem and will almost never happen in real world.

In real world, many cost functions are not have derivative everywhere (Further, the cost function may be discrete and do not have any derivative at all). In addition, even you can calculate the derivative, you cannot just solve the equation analytically (for example, think about how to solve $x^7+x^3-5^2+e^x+log(x+x^2)+1/x=0$ analytically? I can tell you the numerical answer is $x=1.4786$, but do not know analytical solution). We must use some numerical methods (check why here on polynomial cases Abel Ruffin Theorem).

Iterative methods are great to use, and very intuitive to understand. Suppose you want to optimize one function, instead of solving an equation and get the answer, you try to improve your answer by number of iterations /steps after enough iteration, you will get the answer close to "true answer". Say if you use calculus to minimize $f(x)=x^2$, you directly get $x=0$, but using numerical methods, you may get $x=1.1234\times10^{-20}$.

Now, it is important to understand how these iterative methods work. The key concept is knowing how to update your input parameters to get a better solution. Suppose you want to minimize $f(x_1,x_2)=x_1^2+x_2^2+|x_1+x_2|$ (note this cost function is not differentiable everywhere, but differentiable have at "most places", this is good enough for us, since we know how to update at "most places".), currently you are at $(1,1)$, and the cost is $4.0$, now you want to update $(x_1,x_2)$ to make objective function smaller. How would you do that? You may say I want to decrease both $x_1$ $x_2$, but why? In fact you are implicit using the concept of gradient "changing small amount of $x$, what will happen on $y$".. In $(1,1)$, the derivative is $(3,3)$, so negative gradient times a learning rate say $\alpha=0.001$, is $(-0.003,-0.003)$, so we updated our solution from $1, 1$ to $(0.997, 0.997)$ which have better cost.

$\endgroup$
  • $\begingroup$ more information can be found in this related post $\endgroup$ – Haitao Du May 16 '16 at 17:44
4
$\begingroup$

The approach you mentioned can only be used to solve a set of linear equations for example in the case of linear regression, but say for solving a set of non linear equations, in cases such as neural networks with sigmoid activations, gradient descent is the approach to go for. Thus Gradient Descent is a more generic approach.

Even for linear equations, the size of the matrices given by the set of linear equations i huge, and can be hard to constrain the memory requirement.

$\endgroup$

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.