mlsanityData to 14 Oct 2026

Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds

arXiv 2510.21468 ↗First posted 24 Oct 2025math.OC cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

This work addresses the finite-time analysis of nonsmooth nonconvex stochastic optimization under Riemannian manifold constraints. We adapt the notion of Goldstein stationarity to the Riemannian setting as a performance metric for nonsmooth optimization on manifolds. We then propose a Riemannian Online to NonConvex (RO2NC) algorithm, for which we establish the sample complexity of O(ε-3δ-1) in finding (δ,ε)-stationary points. This result is the first-ever finite-time guarantee for fully nonsmooth, nonconvex optimization on manifolds and matches the optimal complexity in the Euclidean setting. When gradient information is unavailable, we develop a zeroth order version of RO2NC algorithm (ZO-RO2NC), for which we establish the same sample complexity. The numerical results support the theory and demonstrate the practical effectiveness of the algorithms.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 38 of its 68 references that are in the map. First posted on arXiv 24 Oct 2025.

Builds on

38 of 68 references.

References · 38

  1. 2015Unitary Evolution Recurrent Neural Networkscited by 294
  2. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  3. 2019Orthogonal Convolutional Neural Networkscited by 123
  4. 2016First-order Methods for Geodesically Convex Optimizationcited by 93
  5. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  6. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  7. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  8. 2021Decentralized Riemannian Gradient Descent on the Stiefel Manifoldcited by 33
  9. 2015Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matricescited by 24
  10. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  11. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  12. 2017Riemannian Optimization via Frank-Wolfe Methodscited by 21
26 more
  1. 2023A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifoldcited by 21
  2. 2020An accelerated first-order method for non-convex optimization on manifoldscited by 15
  3. 2020Geometry-aware Domain Adaptation for Unsupervised Alignment of Word Embeddingscited by 14
  4. 2015MADMM: a generic algorithm for non-smooth optimization on manifoldscited by 12
  5. 2020Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisationcited by 12
  6. 2020Global Riemannian Acceleration in Hyperbolic and Spherical Spacescited by 10
  7. 2022O-ViT: Orthogonal Vision Transformercited by 10
  8. 2022Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysiscited by 10
  9. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  10. 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9
  11. 2017A Riemannian trust-region method for low-rank tensor completioncited by 8
  12. 2016Rapid Mixing of Geodesic Walks on Manifolds with Positive Curvaturecited by 7
  13. 2023Zeroth-order Riemannian Averaging Stochastic Approximation Algorithmscited by 7
  14. 2017Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysiscited by 6
  15. 2024Retraction-Free Decentralized Non-convex Optimization with Orthogonal Constraintscited by 6
  16. 2020Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifoldcited by 5
  17. 2024Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexitycited by 5
  18. 2024Decentralized Online Riemannian Optimization with Dynamic Environmentscited by 5
  19. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  20. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 4
  21. 2025Decentralized Online Riemannian Optimization Beyond Hadamard Manifoldscited by 4
  22. 2022A Riemannian ADMMcited by 3
  23. 2025Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectivescited by 3
  24. 2022Riemannian Smoothing Gradient Type Algorithms]{Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean Spacecited by 2
  25. 2024Oracle complexities of augmented Lagrangian methods for nonsmooth manifold optimizationcited by 1
  26. 2025Federated Learning on Riemannian Manifolds: A Gradient-Free Projection-Based Approachcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functionscited by 1
  2. 2026Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraintscited by 0