22
$\begingroup$
  1. When training a neural network using the back-propagation algorithm, the gradient descent method is used to determine the weight updates. My question is: Rather than using gradient descent method to slowly locate the minimum point with respect to a certain weight, why don't we just set the derivative $\frac{d(\text{Error})}{dw}=0$, and find the value of weight $w$ which minimizes the error?

  2. Also, why are we sure that the error function in back-propagation will be a minimum? Can't it turn out the error function is a maximum instead? Is there a specific property of the squashing functions that guarantees that a network with any number of hidden nodes with arbitrary weights and input vectors will always give an error function that has some minima?

$\endgroup$
  • 2
    $\begingroup$ All caps titles are not standard here (please look around you) and here and elsewhere widely deprecated as unwelcome SHOUTING. $\endgroup$ – Nick Cox Nov 13 '15 at 14:56
  • $\begingroup$ @Nick Cox my apologies $\endgroup$ – Minaj Nov 13 '15 at 15:01
  • $\begingroup$ It is interesting to see whenever hidden or latent variables are used in Machine Learning models, optimization (almost?) always gets non-linear, non-convex and just harder to optimize. $\endgroup$ – Vladislavs Dovgalecs Nov 13 '15 at 16:42
  • 1
    $\begingroup$ FYI why is Newton's method not widely used in machine learning? $\endgroup$ – Franck Dernoncourt Dec 30 '16 at 1:57
30
$\begingroup$
  1. Because we can't. The optimization surface $S(\mathbf{w})$ as a function of the weights $\mathbf{w}$ is nonlinear and no closed form solution exists for $\frac{d S(\mathbf{w})}{d\mathbf{w}}=0$.

  2. Gradient descent, by definition, descends. If you reach a stationary point after descending, it has to be a (local) minimum or a saddle point, but never a local maximum.

$\endgroup$
  • $\begingroup$ If the function was concave, gradient decent would descend forever since the only way to go is downwards. Are you saying that the error surface is guaranteed to not be concave? Also, its not clear to me why the derivative of the error function would have no closed form solution. Isnt the error of the form $K-\frac{1}{1+e^{\Sigma wx}}$ where K is a constant? That function looks fairly differentiable and the resulting expression analytically solvable. Please help me clarify as there is something I clearly fail to see. $\endgroup$ – Minaj Nov 13 '15 at 15:05
  • 8
    $\begingroup$ This cannot happen, because all commonly used error functions have a strict theoretical minimum of 0. Errors can never become negative. $\endgroup$ – Marc Claesen Nov 13 '15 at 15:06
  • 2
    $\begingroup$ One other possible interpretation of 1. is "That's exactly what we do, the equation is solved using gradient descent." $\endgroup$ – Matthew Drury Nov 13 '15 at 16:55
  • 1
    $\begingroup$ there clearly is a closed form for the gradient(that's how we do gradient descent efficiently) . The problem is no closed form root of gradient =0 $\endgroup$ – seanv507 Nov 13 '15 at 20:30
  • $\begingroup$ @seanv507 that's what I intended to say, sorry for the confusion. Edited my post. $\endgroup$ – Marc Claesen Nov 13 '15 at 20:31
10
$\begingroup$

Regarding Marc Claesen's answer, I believe that gradient descent could stop at a local maximum in situations where you initialize to a local maximum or you just happen to end up there due to bad luck or a mistuned rate parameter. The local maximum would have zero gradient and the algorithm would think it had converged. This is why I often run multiple iterations from different starting points and keep track of the values along the way.

$\endgroup$
  • 1
    $\begingroup$ I edited out your preamble comment, as it seems you are already attracting some upvotes! Welcome to the site! $\endgroup$ – Matthew Drury Nov 13 '15 at 17:25
  • $\begingroup$ Thanks! I was not sure if it should be a comment or an answer and did not want my first answer to be downvoted to oblivion based on that alone. $\endgroup$ – Jared Becksfort Nov 13 '15 at 17:35
6
$\begingroup$

In Newton-type methods, at each step one solves $\frac{d(\text{error})}{dw}=0$ for a linearized or approximate version of the problem. Then the problem is linearized about the new point, and the process repeats until convergence. Some people have done it for neural nets, but it has the following drawbacks,

  • One needs to deal with second derivatives (the Hessian, specifically Hessian-vector products).
  • The "solve step" is very computationally expensive: in the time it takes to do a solve one could have done many gradient descent iterations.

If one uses a Krylov method for the Hessian solve, and one does not use a good preconditioner for the Hessian, then the costs roughly balance out - Newton iterations take much longer but make more progress, in such a way that the total time is roughly the same or slower than gradient descent. On the other hand, if one has a good Hessian preconditioner then Newton's method wins big-time.

That said, trust-region Newton-Krylov methods are the gold-standard in modern large-scale optimization, and I would only expect their use to increase in neural nets in the upcoming years as people want to solve larger and larger problems. (and also as more people in numerical optimization get interested in machine learning)

$\endgroup$
  • $\begingroup$ I think you are mistaken. People have been using nnets since the 90s, and they are well aware of second order methods. the problem is precisely that nnets are successful when there is a lot of data, which then support a lot of parameters in which case the time and memory constraints of second order methods are ineffective. see eg leon.bottou.org/publications/pdf/compstat-2010.pdf $\endgroup$ – seanv507 Nov 13 '15 at 22:02
  • $\begingroup$ @seanv507 Not really. The discussion of second order methods in that paper has a lot of flaws, in that they assume one must construct and invert the entire dense Hessian in order to use second order methods. This is simply not how it is done in modern large-scale numerical optimization. In modern second order methods one computes the action of the Hessian on vectors by solving adjoint problems, and uses them within an iterative (Krylov) solver. Generally the first inner iteration returns the gradient direction, and subsequent iterations improve it. $\endgroup$ – Nick Alger Nov 14 '15 at 10:25
  • $\begingroup$ Although I am not a particular fan of that paper, I don't think that is true. He has previously discussed/implemented diagonal and reduced rank approximations of hessian. And what about pearlmutter's 1994 paper fast exact multiplication by hessian? $\endgroup$ – seanv507 Nov 14 '15 at 21:09
  • $\begingroup$ Right. Once you have fast Hessian applications (whether through Pearlmutter or what have you), you can do inexact Hessian solves with Krylov methods like conjugate gradient. By doing this, one effectively transfers the ill-conditioning difficulties away from the nonlinear iterative optimizer, onto the linear algebra iterative solver where one has a lot of machinery and preconditioning techniques available to deal with the problem. A good reference is the section on trust region CG-Steihaug in the classic "Numerical Optimization" by Nocedal and Wright. $\endgroup$ – Nick Alger Nov 15 '15 at 1:29
  • $\begingroup$ My point is that this multiplication by hessian and conjugate gradients was known in nnets community since say 1994. So I believe there is definitely a reason why SGD is used rather than second order methods (and I would certainly like a clear resolution of why this is) $\endgroup$ – seanv507 Nov 15 '15 at 10:14

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.