mlsanityData to 14 Oct 2026

Global rates of convergence for nonconvex optimization on manifolds

arXiv 1605.08101 ↗First posted 25 May 2016math.OC cs.NA math.NAcited by 62

Not on the map. Why?

Abstract (arXiv)

We consider the minimization of a cost function f on a manifold M using Riemannian gradient descent and Riemannian trust regions (RTR). We focus on satisfying necessary optimality conditions within a tolerance varepsilon. Specifically, we show that, under Lipschitz-type assumptions on the pullbacks of f to the tangent spaces of M, both of these algorithms produce points with Riemannian gradient smaller than varepsilon in O(1/varepsilon2) iterations. Furthermore, RTR returns a point where also the Riemannian Hessian's least eigenvalue is larger than -varepsilon in O(1/varepsilon3) iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy varepsilon (up to constants) and hence are sharp in that sense. These are the first deterministic results for global rates of convergence to approximate first- and second-order Karush-Kuhn-Tucker points on manifolds. They apply in particular for optimization constrained to compact submanifolds of ℝn, under simpler assumptions.

Key facts. Cited by 62 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 12; 2023: 12; 2024: 11; 2025: 7; 2026: 8.

62 papers.

Sort:

By area:

  1. 2021Decentralized Riemannian Gradient Descent on the Stiefel Manifoldcited by 33
  2. 2023Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraintscited by 18
  3. 2023Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifoldcited by 14
  4. 2022Federated Learning on Riemannian Manifoldscited by 13
  5. 2021Interactive Dimensionality Reduction for Comparative Analysiscited by 12
  6. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
  7. 2022Differentially private Riemannian optimizationcited by 12
  8. 2022Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transportcited by 11
  9. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  10. 2021On the Local Linear Rate of Consensus on the Stiefel Manifoldcited by 8
  11. 2021Projection Robust Wasserstein Barycenterscited by 8
  12. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
38 more
  1. 2025Landing with the Score: Riemannian Optimization through Denoisingcited by 8
  2. 2023Decentralized Riemannian Algorithm for Nonconvex Minimax Problemscited by 7
  3. 2023Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifoldcited by 7
  4. 2024Optimization without Retraction on the Random Generalized Stiefel Manifoldcited by 7
  5. 2021Coordinate descent on the orthogonal group for recurrent neural network trainingcited by 5
  6. 2022Riemannian Natural Gradient Methodscited by 5
  7. 2022Riemannian accelerated gradient methods via extrapolationcited by 5
  8. 2021Accelerating Training of Batch Normalization: A Manifold Perspectivecited by 4
  9. 2021New Riemannian preconditioned algorithms for tensor completion via polyadic decompositioncited by 4
  10. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 4
  11. 2022Manifold Free Riemannian Optimizationcited by 4
  12. 2024Riemannian Federated Learning via Averaging Gradient Streamscited by 4
  13. 2025A Human-AI Collaborative Workflow for Mathematical Discovery: A Case Study in Grover-Compatible Riemannian Optimizationcited by 4
  14. 2021BN-invariant sharpness regularizes the training model to better generalizationcited by 3
  15. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  16. 2022A Riemannian ADMMcited by 3
  17. 2023Gradient-Based Spectral Embeddings of Random Dot Product Graphscited by 3
  18. 2023Fair Canonical Correlation Analysiscited by 3
  19. 2025Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Methodcited by 3
  20. 2021Nonlinear matrix recovery using optimization on the Grassmann manifoldcited by 2
  21. 2022Riemannian stochastic approximation algorithmscited by 2
  22. 2023Contrastive inverse regression for dimension reductioncited by 2
  23. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  24. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  25. 2024Optimal Matrix-Mimetic Tensor Algebras via Variable Projectioncited by 2
  26. 2025Scalable Second-order Riemannian Optimization for K-means Clusteringcited by 2
  27. 2022On a class of geodesically convex optimization problems solved via Euclidean MM methodscited by 1
  28. 2022Riemannian Stochastic Gradient Method for Nested Composition Optimizationcited by 1
  29. 2023Decentralized Riemannian natural gradient methods with Kronecker-product approximationscited by 1
  30. 2023Decentralized Weakly Convex Optimization Over the Stiefel Manifoldcited by 1
  31. 2024Registration of algebraic varieties using Riemannian optimizationcited by 1
  32. 2024Learning-Rate-Free Stochastic Optimization over Riemannian Manifoldscited by 1
  33. 2024Disciplined Geodesically Convex Programmingcited by 1
  34. 2024Structured Regularization for Constrained Optimization on the SPD Manifoldcited by 1
  35. 2025Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Treecited by 1
  36. 2023Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularizationcited by 0
  37. 2023Sharpness-Aware Teleportation on Riemannian Manifoldscited by 0
  38. 2024Continuous-time Riemannian SGD and SVRG Flows on Wasserstein Probabilistic Spacecited by 0

50 most cited of 62 All 62 (JSON)