Why doesn't gradient descent terminate on saddle point? 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.
 A: 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
A: 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.
A: 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.
