Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
It provides foundational theoretical guarantees for optimization on manifolds, addressing a key bottleneck in machine learning and data science applications.
This paper tackles the problem of nonsmooth nonconvex stochastic optimization on Riemannian manifolds by proposing the RO2NC algorithm, achieving a sample complexity of O(ε^{-3}δ^{-1}) to find (δ,ε)-stationary points, which matches optimal Euclidean complexity and is the first finite-time guarantee for this setting.
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.