14
$\begingroup$

I am currently a bit puzzled by how mini-batch gradient descent can be trapped in a saddle point.

The solution might be too trivial that I don't get it.

You get an new sample every epoch, and it computes a new error based on a new batch, so the cost function is only static for each batch, which means that the gradient also should change for each mini batch.. but according to this should a vanilla implementation have issues with saddle points?

Another key challenge of minimizing highly non-convex error functions common for neural networks is avoiding getting trapped in their numerous suboptimal local minima. Dauphin et al. [19] argue that the difficulty arises in fact not from local minima but from saddle points, i.e. points where one dimension slopes up and another slopes down. These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.

I would mean that especially SGD would have clear advantage against saddle points, as it fluctuates towards its convergence... The fluctuations and the random sampling , and cost function being different for each epoch should be enough reasons for not becoming trapped in one.

For full batch gradient decent does it make sense that it can be trapped in saddle point, as the error function is constant.

I am a bit confused on the two other parts.

$\endgroup$
  • 1
    $\begingroup$ Moti gets it. The saddle point with very high slopes and surrounded by zero slope launches a gradient descent with large-steps into "the badlands" from which it cannot recover. Think about looking for a well on an essentially flat plain. Now think about the well as dry, and with an ant-hill in the center. A gradient-descent that lands on the ant-hill, but not at the exact top, is going to shoot the search out radially. Now imagine that the step-size for the search is a thousand times larger than the diameter of the well. If the search ever finds the well, the anthill shoots it to montana $\endgroup$ – EngrStudent - Reinstate Monica May 11 '17 at 13:26
  • $\begingroup$ I'm confused what your asking. Are you confused why SGD is not able to get trapped in saddle point because of the inherit noise SGD has, so according to you it should be able to escape? (unlike if it was full batch GD then if the gradient is zero and no noise then it can't escape, is that what your asking?) $\endgroup$ – Pinocchio Jun 9 '17 at 2:12
16
+50
$\begingroup$

Take a look at the image below from Off Convex. In a convex function (leftmost image), there is only one local minimum, which is also the global minimum. But in a non-convex function (rightmost image), there may be multiple local minima and often joining two local minima is a saddle point. If you are approaching from a higher point, the gradient is comparatively flatter, and you risk getting stuck there, especially if you are moving only in one direction.

Diagrammatic representation of a saddle point

Now the thing is, whether you are optimizing using mini-batch or stochastic gradient descent, the underlying non-convex function is the same, and the gradient is a property of the this function. When doing mini-batch, you consider many samples at a time and take the gradient step averaged over all of them. This reduces variance. But if the average gradient direction is still pointing in the same direction as the saddle point, then you still risk getting stuck there. The analogy is, if you're taking 2 steps forward and 1 step back, averaging over those, you ultimately end up taking 1 step forward. If you perform SGD instead, you take all the steps one after the other, but if you're still moving in a single direction, you can reach the saddle point and find that the gradient on all sides is fairly flat and the step size is too small to go over this flat part. This doesn't have anything to do with whether you considered a bunch of points at once, or one by one in random order.

Take a look at the visualization here. Even with SGD, if the fluctuations occur only along one dimension, with the steps getting smaller and smaller, it would converge at the saddle point. In this case, the mini-batch method would just reduce the amount of fluctuation but would not be able to change the gradient's direction.

SGD can sometimes break out of simple saddle points, if the fluctuations are along other directions, and if the step size is large enough for it to go over the flatness. But sometimes the saddle regions can be fairly complex, such as in the image below.

Complex saddle regions

The way methods like momentum, ADAGRAD, Adam etc are able to break out of this, is by considering the past gradients. Consider momentum,

$$ v_t = \gamma v_{t-1} + \eta \nabla_{theta} J(\theta) $$

which adds a portion of the last gradient, $v_{t-1}$. In case you've just been going back and forth in one direction, essentially changing signs, it ends up dampening your progress. While if there has consistently been positive progress in one direction, it ends up building up and going down that way.

$\endgroup$
  • $\begingroup$ Well, not exactly! For an answer in practice see: stats.stackexchange.com/a/284399/117305 $\endgroup$ – alifornia Jun 9 '17 at 1:53
  • $\begingroup$ @AliAbbasinasab I think Antimony explains well. Of course, getting stuck in a ordinary saddle point is hardly as you mention in your answer, but he just showed the possibility that the SGD might be caught. And to me, he just showed some unusual saddle points that SGD can't escape. $\endgroup$ – Kazuya Tomita Oct 20 '17 at 0:28
2
$\begingroup$

It should not.

[1] has shown that gradient descent with random initialization and appropriate constant step size does not converge to a saddle point. It is a long discussion but to give you an idea of why see the following example:

$$f(x,y)=\frac12 x^2+ \frac14y^4 - \frac12y^2$$

enter image description here

The critical points are $$z_1=\begin{bmatrix}0\\0\end{bmatrix}, z_2=\begin{bmatrix}0\\1\end{bmatrix}, z_3=\begin{bmatrix}0\\-1\end{bmatrix}$$.

The points $z_2$ and $z_3$ are isolated local minima, and $z_1$ is a saddle point.

Gradient descent initialized from any point of the form $z_0=\begin{bmatrix}x\\0\end{bmatrix}$ converges to the saddle point $z_1$. Any other initial point either diverges or converges to a local minimum, so the stable set of $z_1$ is the $x$-axis, which is a zero measure set in $\mathbb{R}^2$. By computing the Hessian, $$\nabla^2f(x,y)=\begin{bmatrix}1&&0\\0&&3y^2-1\end{bmatrix}$$

we find that $\nabla^2f(z_1)$ has one positive eigenvalue with eigenvector that spans the $x$-axis, thus agreeing with our above characterization of the stable set. If the initial point is chosen randomly, there is zero probability of initializing on the $x$-axis and thus zero probability of converging to the saddle point $z_1$.

$\endgroup$
  • $\begingroup$ You could just as easily pick a counter-example function where you will get stuck in a saddle point every time... $\endgroup$ – Jan Kukacka Aug 14 '18 at 11:01
  • 1
    $\begingroup$ I have been unable to reach your link [1]--could you provide a full citation? In the meantime, it is possible to construct counterexamples to your claim, indicating it must be based on additional unstated assumptions. $\endgroup$ – whuber Jun 6 at 16:55
  • $\begingroup$ @whuber you can easily cook up counterexamples. For example if you have only a line as your space. I just tried to add a point which may not be obvious to many (It was initially not too obvious to me why). About the reference, I have no idea why you cannot reach it. I double checked, the link is valid and get updated as well. You may search "Gradient Descent Converges to Minimizers, Jason D. Lee , Max Simchowitz , Michael I. Jordan †, and Benjamin Recht † ♯Department of Electrical Engineering and Computer Sciences †Department of Statistcs University of California, Berkeley, April 19, 2019" $\endgroup$ – alifornia Jun 7 at 18:17
  • $\begingroup$ Thank you for the reference. A quick glance at it (the link now works) shows the analysis is limited to "strict saddles" (where there are both positive and negative eigenvalues of the Hessian), which precludes many possibilities. The final statements of the paper include "we note that there are very difficult unconstrained optimization problems where the strict saddle condition fails" and they offer quartic minimization as an example. $\endgroup$ – whuber Jun 7 at 18:26
0
$\begingroup$

If you go to the referenced paper (they also emperically show how their saddle-free approach does indeed improve upon mini-batch SGD) they state:

A step of the gradient descent method always points in the right direction close to a saddle point...and so small steps are taken in directions corresponding to eigenvalues of small absolute value.

They also note the presence of "plateaus" near saddle points (in other words, the saddle is not steep) - in these cases, taking too small steps would indeed result in premature convergence before having escaped the saddle region. Since this is a non-convex optimization, the convergence of the learning rate would make this worse.

It does seem possible that one could try an iterative approach, where one restarts the mini-batch SGD once it completes (i.e., resetting the learning rate) to see if one can escape the problematic region.

$\endgroup$
0
$\begingroup$

I think the problem is that while approaching a saddle point you enter a plateau, i.e. an area with low (in absolute value) gradients. Especially when you're approaching from the ridge. So your algorithm decreases the step size. With a decreased step size now all gradients (in all directions) are small in absolute value. So the algorithm stops, thinking it's at the minimum.

If you don't decrease the steps then you'll be jumping over the minimum, and missing them a lot. You must decrease the step size somehow.

$\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.