Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient

2020/10/23 by Andi Han, Han, Andi, Junbin Gao +1 · 1 citation
Computer Science · Engineering · #3D Shape Modeling and Analysis #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2010.12191

openalex publication_date 2020/10/23 · openalex created_date 2020/10/29 · openalex updated_date 2026/07/28

Abstract

In this paper, we propose a variant of Riemannian stochastic recursive gradient method that can achieve second-order convergence guarantee and escape saddle points using simple perturbation. The idea is to perturb the iterates when gradient is small and carry out stochastic recursive gradient updates over tangent space. This avoids the complication of exploiting Riemannian geometry. We show that under finite-sum setting, our algorithm requires \widetildeO( ( √(n))/(ε²) + (√(n) )/(δ⁴) + (n)/(δ³)) stochastic gradient queries to find a (ε, δ)-second-order critical point. This strictly improves the complexity of perturbed Riemannian gradient descent and is superior to perturbed Riemannian accelerated gradient descent under large-sample settings. We also provide a complexity of \widetildeO ( (1)/(ε³) + (1)/(δ³ ε²) + (1)/(δ⁴ ε) ) for online optimization, which is novel on Riemannian manifold in terms of second-order convergence using only first-order information.

Citations

• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Finding Local Minima via Stochastic Nested Variance Reduction
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Cited by

• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method

Related

• Efficiently escaping saddle points on manifolds
• Riemannian stochastic optimization methods avoid strict saddle points
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• Escaping from saddle points on Riemannian manifolds
• Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds