I always read that gradient descent terminates at a local minima. Isn't it possible that it will terminate at a saddle point? I know it cant terminate at a maxima unless iteration begins there. However, I fail to see why it would fail to terminate at a saddle point if it approaches such a point before it reaches the minima.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ @Media The referenced thread does not appear to have contradictory answers. It's just that those answers embody at least three different conceptions of the question! A recent answer adopts an overly general definition of "saddle point," using a quartic as an example. Another one answers from the perspective of numerical algorithms, which do more than a simple gradient descent: they work hard to determine how far to move in the direction of the gradient and if that's not well-tuned, a poor algorithm very well could converge to a true saddle point. I recommend a careful re-reading. $\endgroup$– whuber ♦Commented Sep 24, 2020 at 18:16
-
1$\begingroup$ I would, therefore, nominate Antimony's answer in that thread as the "answer from a reputable source" that you are seeking with your bounty. $\endgroup$– whuber ♦Commented Sep 24, 2020 at 18:18
-
$\begingroup$ @whuber But I am sure that answer is no longer valid. On the other hand, I completely disagree with that. mini batch methods approximate the cost function. We are not really moving over the real cost function. $\endgroup$– Green FalconCommented Sep 24, 2020 at 18:40
-
$\begingroup$ @Media You seem to be concerned about a problem that is rather different than the one articulated here! $\endgroup$– whuber ♦Commented Sep 24, 2020 at 18:41
-
$\begingroup$ @whuber Well, let's say not really. The point is that I believe GD will be stuck in saddle points, while stochastic methods do not. Just compare the answer there with the one here. They are contradictory. $\endgroup$– Green FalconCommented Sep 24, 2020 at 18:43
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
11
This answer will only consider asymptotic outcomes, that is, whether we get stuck after infinite number of iterations. We will also only consider the classical gradient descent with zero noise. Noisy variants of GD such as SGD always have a non-zero probability of randomly making several consecutive steps away from the equilibrium, so they never really get asymptotically stuck. While asymptotic convergence of classical GD definitely is related to the performance / convergence rate of SGD, I think that optimization of SGD vastly exceeds the scope of the original question.
We will consider the probability of getting stuck in an unstable equilibrium, that is a saddle point or a maximum. We will define unstable equilibria by having zero gradients and a Hessian matrix that is not positive definite.
It is effectively impossible to get stuck in the unstable equillibrium point itself. It is easy to see that a point or a line in 2D have zero area, so the probability of landing on those is zero unless the starting point is fine-tuned.
To finish the analysis of classical GD, it remains to see if one can construct an unstable equillibrium whose basin of attraction has non-zero area/hypervolume of the same dimension as the domain, which would make the probability of landing there from a random init point non-zero. Consider a weird saddle point with the following gradient
$$ f'_x = x\cdot \mathrm{sign}(xy) $$ $$ f'_y = y\cdot \mathrm{sign}(xy) $$
While the sign function may be a bit unrealistic, the same argument holds if we replace it with a sigmoid. If we consider the plot of this gradient (arrows are normalized, because in asymptotic analysis we only care about direction, not magnitude)
we find that its basin of attraction (yellow) has nonzero area. With this particular arrangement, it is possible and likely to get stuck forever with classical GD
-
1$\begingroup$ (3) seems to contradict (2) and (2) is incomplete. (2) rests on the claim "And if you are not on this line, you will move away from saddle point towards minimum eventually." Why is this so? I believe that a rigorous demonstration will require you to explain what you mean by "saddle point" and to be clearer about the specific gradient descent algorithm you have in mind. $\endgroup$– whuber ♦Commented Sep 28, 2020 at 13:33
-
1$\begingroup$ Yes, you do, because the correctness of your answer depends on it! Some people, for instance, would take a a generalized monkey saddle, $f(x,y)=x^4-6x^2y^2+y^4,$ to be a "saddle point"--but your argument fails for a monkey saddle (or at least requires more care). Another fun situation to consider is $f(x,y)=(x^2-y^2)\sin(1/\sqrt{x^2+y^2}).$ $\endgroup$– whuber ♦Commented Sep 28, 2020 at 14:24
-
1$\begingroup$ Ups, I guess I have learned something today. I was completely convinced that a saddle point is defined by having a Hessian with eigenvalues of mismatching signs. I have never encountered the situation where Hessian is zero. That does indeed invalidate my answer. I am sorry, I will reconsider it $\endgroup$ Commented Sep 28, 2020 at 14:49
-
2$\begingroup$ @SextusEmpiricus My intuition screwed me up as well initially. But good guy whuber does not sleep when evil is committed :D $\endgroup$ Commented Sep 28, 2020 at 17:10
-
1$\begingroup$ @Media No, as I said, a saddle point is just 1 point. One can never realistically reach it unless one does infinite steps, because the volume of a point is zero, and so the probability of landing there in finite steps is zero. One can however get stuck in the basin of attraction of the saddle point after a few epochs. $\endgroup$ Commented Oct 1, 2020 at 7:29
$\begingroup$
$\endgroup$
2
Old gradient descent will terminate once it touch a point with derivative zero. And so also will terminate in a saddle if the derivative is zero. But in the everyday gradient descent (stochastic) it's pretty hard or almost impossible to terminate in maximum or saddle, because those aren't points with stable equilibrium, in the sense that the Hessian matrix of the function isn't definite positive.
-
$\begingroup$ Can you please clarify on the intuition behind "unstable equilibrium"? If the small steps are driving me towards a saddle point, what would prevent the algorithm from settling there. $\endgroup$– MinajCommented Nov 20, 2015 at 12:23
-
3$\begingroup$ In plain gradient descent nothing, you will be caught in that saddle. In stochastic gradient descent you don't follow a geodetic curve towards the saddle. By unstable equilibrium, intuitively it's like the top of a mountain: once you move even a little from that point you will get far away of that equilibrium. It could be that a neighborhood of that point has also gradient zero, so you stay in the saddle, but not in the same point. That's why stochastic gradient descent prevents to be caught in critical point other than minima. $\endgroup$– user59747Commented Nov 20, 2015 at 12:31
$\begingroup$
$\endgroup$
1
Gradient descent can indeed converge to a saddle point, given a worst case initialization (Nesterov 2013, section 1.2.3).
Random initialization can prevent convergence to saddle points
Things are different when gradient descent is initialized randomly (given certain assumptions). Lee et al. (2016) prove that:
If $f: \mathbb{R}^d \to \mathbb{R}$ is twice continuously differentiable and satisfies the strict saddle property, then gradient descent with a random initialization and sufficiently small constant step size almost surely converges to a local minimizer.
A 'sufficently small' step size means less than the inverse of the Lipschitz constant of the gradient, which they say is standard in practice. The 'strict saddle property' means that all critical points (where the gradient is zero) are either local minima or strict saddles (i.e. the Hessian has at least one strictly negative eigenvalue). This property doesn't apply universally, but they claim that it applies to many objective functions of practical interest.
The proof proceeds by treating gradient descent as a dynamical system. Each critical point has a surrounding basin of attraction. If gradient descent enters this basin, then it will converge to the corresponding critical point. Given the assumptions above, the basin of attraction around saddle points has zero measure. This implies that, with random initialization, there's zero probability of landing in such a basin (and therefore converging to a saddle point).
Escaping saddle points may require exponential time
The above result concerns asymptotic convergence. It says that gradient descent with random initialization will eventually converge to a local minimum, but it provides no guarantees about how long convergence will take. Unfortunately, Du et al. (2017) show that gradient descent may require exponential time to escape saddle points, even with random initialization and non-pathological objective functions. That is, there exist 'natural' objective functions where the required number of steps scales exponentially with the number of saddle points to escape. Although gradient descent will eventually converge in these cases, it may take an infeasibly long time. Note that this result describes the worst case scenario; it doesn't imply exponential time for all objective functions.
Speeding up convergence
There are various ways to speed up convergence in the presence of saddle points (see references in Du et al. 2017). One approach involves clever initialization schemes, but this is problem-specific. Another strategy exploits curvature information in the Hessian, yielding polynomial-time convergence to a local minimum (this is no longer gradient descent). This requires access to the Hessian (or the computation of Hessian-vector products) and may not scale to extremely large problems.
Pure gradient-based methods can escape saddle points in polynomial time if augmented with random perturbations. Intuitively, this works because, saddle points are unstable fixed points; if the optimization algorithm is randomly pushed away, there's a high probability it will move elsewhere. Random perturbations can be implemented by explicitly adding noise. Alternatively, standard stochastic gradient descent (SGD) might provide a similar effect, provided the noise in the gradient is sufficiently large in all directions (Ge et al. 2015; however Du et al. speculate that SGD will require exponential time in general).
References
Du, S. S., Jin, C., Lee, J. D., Jordan, M. I., Singh, A., & Poczos, B. (2017). Gradient descent can take exponential time to escape saddle points. In Advances in neural information processing systems (pp. 1067-1077).
Ge, R., Huang, F., Jin, C., & Yuan, Y. (2015, June). Escaping from saddle points—online stochastic gradient for tensor decomposition. In Conference on Learning Theory (pp. 797-842).
Lee, J. D., Simchowitz, M., Jordan, M. I., & Recht, B. (2016, June). Gradient descent only converges to minimizers. In Conference on learning theory (pp. 1246-1257).
Nesterov, Y. (2013). Introductory lectures on convex optimization: A basic course (Vol. 87). Springer Science & Business Media.
answered Sep 28, 2020 at 19:04
-
$\begingroup$ Cool, very broad answer. I would request 2 small clarifications: (1) How do Du et al define pathological objective functions? I believe I have constructed above an objective function where a saddle point can never be escaped by classical GD. Is it pathological? (2) "GD can escape saddle points in polynomial time if augmented with random perturbations" - how is convergence time defined for stochastic processes? You were mostly discussing worst-case performance up to now, but for stochastic processes worst case-scenario is that they never converge, right? $\endgroup$ Commented Sep 29, 2020 at 7:41