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

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}{\delta }^{-1})$ in finding ($\delta ,ϵ$)-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.