A Stochastic Riemannian Alternating Descent Ascent Method for Nonsmooth Composite Expectation Optimization on Riemannian Manifolds
Abstract
In this paper, we consider a class of Riemannian nonsmooth composite expectation optimization problems, which arises in various machine learning, signal processing, and statistics applications. Noting that these problems admit structured minimax reformulations, we propose an efficient algorithm, named stochastic Riemannian alternating descent ascent method with recursive momentum (StoRADA-RM), to tackle them. StoRADA-RM performs one or multiple Riemannian stochastic gradient descent steps and then a proximal gradient ascent step at each iteration. To compute the Riemannian stochastic gradient, we propose a vector transport-free recursive momentum estimator that requires only O(1) stochastic gradient evaluations per iteration. We prove that StoRADA-RM returns an ε-Riemannian-stochastic-stationary point of a given problem in the said class in O(ε−3) iterations while making O(ε−3) calls to a stochastic first-order oracle (SFO). Both the iteration complexity and SFO complexity bounds are the best known in the literature for the said class of problems. The latter even matches the optimal lower bound for smooth nonconvex optimization with stochastic first-order algorithms. We then present numerical results on sparse principal component analysis and coordinate-independent sparse estimation to demonstrate the superior performance of our proposed method.
Related
- Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
- A Unified Efficient Gradient-Based Heuristic For Box-Constrained Expectation-Related and Risk-Averse Stochastic Optimization Problems
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Locally Private Inference for Riemannian Stochastic Optimization
BibTeX
@misc{xu2026stochastic,
title = {{A Stochastic Riemannian Alternating Descent Ascent Method for Nonsmooth Composite Expectation Optimization on Riemannian Manifolds}},
author = {Meng Xu and Bo Jiang and Ya-Feng Liu and Anthony Man-Cho So},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04116},
eprint = {2609.04116},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04116},
}
RIS
TY - UNPB
TI - A Stochastic Riemannian Alternating Descent Ascent Method for Nonsmooth Composite Expectation Optimization on Riemannian Manifolds
AU - Meng Xu
AU - Bo Jiang
AU - Ya-Feng Liu
AU - Anthony Man-Cho So
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04116
UR - https://arxiv.org/abs/2609.04116
AB - In this paper, we consider a class of Riemannian nonsmooth composite expectation optimization problems, which arises in various machine learning, signal processing, and statistics applications. Noting that these problems admit structured minimax reformulations, we propose an efficient algorithm, named stochastic Riemannian alternating descent ascent method with recursive momentum (StoRADA-RM), to tackle them. StoRADA-RM performs one or multiple Riemannian stochastic gradient descent steps and then a proximal gradient ascent step at each iteration. To compute the Riemannian stochastic gradient, we propose a vector transport-free recursive momentum estimator that requires only O(1) stochastic gradient evaluations per iteration. We prove that StoRADA-RM returns an ε-Riemannian-stochastic-stationary point of a given problem in the said class in O(ε^−3) iterations while making O(ε^−3) calls to a stochastic first-order oracle (SFO). Both the iteration complexity and SFO complexity bounds are the best known in the literature for the said class of problems. The latter even matches the optimal lower bound for smooth nonconvex optimization with stochastic first-order algorithms. We then present numerical results on sparse principal component analysis and coordinate-independent sparse estimation to demonstrate the superior performance of our proposed method.
ER -