Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
Hayden Schaeffer, Scott G. McCalla · SIAM Journal on Mathematics of Data Science · 2020
We provide larger step-size restrictions for which gradient descent-based algorithms (almost surely) avoid strict saddle points. In particular, consider a twice differentiable (nonconvex) objective function whose gradient has Lipschitz constant $L$ and that the set of points that obtain the maximum value of the spectral norm of the Hessian is measure zero. We prove that given one uniformly random initialization, the probability that gradient descent with a step-size up to $2/L$ will converge to a strict saddle point is zero. This extends previous results up to the sharp limit imposed by the convex quadratic case (provably converging to local minimizers). In addition, the arguments hold in the case when a learning rate schedule is given, with either a continuous decaying rate or a piecewise constant schedule. We show that the assumptions are robust in the sense that functions which do not satisfy the assumptions are meager with respect to analytic functions.