Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms
This work addresses optimization challenges in machine learning and related fields where data lies on manifolds, offering a practical improvement over existing methods but is incremental in nature.
The paper tackles stochastic optimization on Riemannian manifolds by proposing Zeroth-order Riemannian Averaging Stochastic Approximation (Zo-RASA) algorithms, achieving optimal sample complexities for generating ε-approximation first-order stationary solutions with one-sample or constant-order batches per iteration.
We present Zeroth-order Riemannian Averaging Stochastic Approximation (\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities for generating $ε$-approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. We improve the algorithm's practicality by using retractions and vector transport, instead of exponential mappings and parallel transports, thereby reducing per-iteration complexity. Additionally, we introduce a novel geometric condition, satisfied by manifolds with bounded second fundamental form, which enables new error bounds for approximating parallel transport with vector transport.