Gradient descent avoids strict saddles with a simple line-search method too

2025/07/18 by Andreea-Alexandra Muşat, Nicolas Boumal, Muşat, Andreea-Alexandra +1
Computer Science · Mathematics · #37C75 #58K05 (Secondary) #90C30 (Primary) 65K05 #Dynamical Systems (math.DS) #FOS: Mathematics #Geometric Analysis and Curvature Flows #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2507.13804

openalex publication_date 2025/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is known that gradient descent (GD) on a C² cost function generically avoids strict saddle points when using a small, constant step size. However, no such guarantee existed for GD with a line-search method. We provide one for a modified version of the standard Armijo backtracking method with generic, arbitrarily large initial step size. The proof underlines the double role of the Luzin N^-1 property for the iteration maps, and allows to forgo the habitual Lipschitz gradient assumption. We extend this to the Riemannian setting (RGD), assuming the retraction is real analytic (though the cost function still only needs to be C²). In closing, we also improve guarantees for RGD with a constant step size in some scenarios.

Citations

• Some iterative algorithms on Riemannian manifolds and Banach spaces with good global convergence guarantee
• Bounds on the geodesic distances on the Stiefel manifold for a family of Riemannian metrics
• The injectivity radius of the compact Stiefel manifold under the Euclidean metric
• High curvature means low-rank: On the sectional curvature of Grassmann and Stiefel manifolds and the underlying matrix trace inequalities
• A mathematical perspective on Transformers
• Riemannian stochastic optimization methods avoid strict saddle points
• Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
• Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Extending the step-size restriction for gradient descent to avoid strict saddle points
• Escaping from saddle points on Riemannian manifolds
• Efficiently escaping saddle points on manifolds
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• How to Escape Saddle Points Efficiently
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Related

• Glocal Smoothness: Line search and adaptive step sizes can help in theory too!
• CGD: Modifying the Loss Landscape by Gradient Regularization
• Convergence to minima for the continuous version of Backtracking Gradient Descent
• Extending the step-size restriction for gradient descent to avoid strict saddle points
• Gradient Descent Can Take Exponential Time to Escape Saddle Points