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

arXiv: https://arxiv.org/abs/2510.21468 · HTML: https://mlsanity.com/paper/2510.21468/

## 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 (most cited first, 30 of 38)

- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Orthogonal Convolutional Neural Networks](https://mlsanity.com/paper/1911.12207/) (2019)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifold](https://mlsanity.com/paper/2302.08210/) (2023)
- [An accelerated first-order method for non-convex optimization on manifolds](https://mlsanity.com/paper/2008.02252/) (2020)
- [Geometry-aware Domain Adaptation for Unsupervised Alignment of Word Embeddings](https://mlsanity.com/paper/2004.08243/) (2020)
- [MADMM: a generic algorithm for non-smooth optimization on manifolds](https://mlsanity.com/paper/1505.07676/) (2015)
- [Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisation](https://mlsanity.com/paper/2010.00211/) (2020)
- [Global Riemannian Acceleration in Hyperbolic and Spherical Spaces](https://mlsanity.com/paper/2012.03618/) (2020)
- [O-ViT: Orthogonal Vision Transformer](https://mlsanity.com/paper/2201.12133/) (2022)
- [Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysis](https://mlsanity.com/paper/2202.02036/) (2022)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [A Riemannian trust-region method for low-rank tensor completion](https://mlsanity.com/paper/1703.10019/) (2017)
- [Rapid Mixing of Geodesic Walks on Manifolds with Positive Curvature](https://mlsanity.com/paper/1609.02901/) (2016)
- [Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms](https://mlsanity.com/paper/2309.14506/) (2023)
- [Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis](https://mlsanity.com/paper/1710.02236/) (2017)
- [Retraction-Free Decentralized Non-convex Optimization with Orthogonal Constraints](https://mlsanity.com/paper/2405.11590/) (2024)
- [Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold](https://mlsanity.com/paper/2005.01209/) (2020)
- [Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity](https://mlsanity.com/paper/2405.05713/) (2024)
- [Decentralized Online Riemannian Optimization with Dynamic Environments](https://mlsanity.com/paper/2410.05128/) (2024)

## Built on by (most cited first, 2 of 2)

- [Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions](https://mlsanity.com/paper/2607.20316/) (2026)
- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## 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.