Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds

Abstract

Nonconvex optimization on Stiefel manifolds underlies many problems in machine learning and deep learning. However, existing stochastic Riemannian retraction methods often rely on stepsizes that require prior knowledge of the gradient Lipschitz constant, a prescribed iteration horizon, or restrictive batch-size choices. We develop {\sf RGR}, a recursive gradient retraction method for stochastic nonconvex optimization on Stiefel manifolds. Instead of recursively updating gradient estimators in changing tangent spaces, {\sf RGR} constructs them in the Euclidean space and subsequently maps them to tangent space, thereby avoiding vector transport. The method comprises three variants: {\sf RGR-SPIDER} for finite-sum optimization and {\sf RGR-SRM} and {\sf RGR-EMA} for online stochastic optimization. {\sf RGR-SPIDER} is Lipschitz-free and horizon-free, as its adaptive stepsize requires neither prior knowledge of the gradient Lipschitz constant nor a prescribed iteration horizon. {\sf RGR-SRM} and {\sf RGR-EMA} are mini-batch and horizon-free methods whose convergence guarantees do not rely on prescribed large batch sizes and whose parameters can be chosen without prior knowledge of the total iteration budget. We show that {\sf RGR-SPIDER} reaches an ε-critical point using 𝒪(ε⁻²) iterations and 𝒪(N+√Nε⁻²) component-gradient evaluations, where N denotes the number of component functions. For the online setting, {\sf RGR-SRM} and {\sf RGR-EMA} achieve iteration complexities of 𝒪̃(ε⁻³) and 𝒪̃(ε⁻⁴), respectively. Experiments on principal component analysis, low-rank matrix completion, and orthogonal convolutional neural networks demonstrate faster empirical convergence than methods that construct recursive gradient estimators directly in Riemannian tangent spaces.

Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
Daniel Cortild, Mathias Staudigl, Juan Peypouquet +1
arXiv6 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
Tianzhu Liu, Michael J. O'Neill
arXiv27 Aug 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
On the Complexity of Finding Stationary Points in Stochastic (L₀, L₁)-Smooth Nonconvex Optimization
Yanpeng Liang, Luo Luo
arXiv15 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
Raghu Bollapragada, Yash Kumar
arXiv23 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
Qihao Zhou
arXiv25 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{yuan2026recursive,
  title = {{Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds}},
  author = {Zhijie Yuan and Lei Sun and Ganzhao Yuan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.19944},
  eprint = {2610.19944},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.19944},
}

RIS

TY  - UNPB
TI  - Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds
AU  - Zhijie Yuan
AU  - Lei Sun
AU  - Ganzhao Yuan
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.19944
UR  - https://arxiv.org/abs/2610.19944
AB  - Nonconvex optimization on Stiefel manifolds underlies many problems in machine learning and deep learning. However, existing stochastic Riemannian retraction methods often rely on stepsizes that require prior knowledge of the gradient Lipschitz constant, a prescribed iteration horizon, or restrictive batch-size choices. We develop {\sf RGR}, a recursive gradient retraction method for stochastic nonconvex optimization on Stiefel manifolds. Instead of recursively updating gradient estimators in changing tangent spaces, {\sf RGR} constructs them in the Euclidean space and subsequently maps them to tangent space, thereby avoiding vector transport. The method comprises three variants: {\sf RGR-SPIDER} for finite-sum optimization and {\sf RGR-SRM} and {\sf RGR-EMA} for online stochastic optimization. {\sf RGR-SPIDER} is Lipschitz-free and horizon-free, as its adaptive stepsize requires neither prior knowledge of the gradient Lipschitz constant nor a prescribed iteration horizon. {\sf RGR-SRM} and {\sf RGR-EMA} are mini-batch and horizon-free methods whose convergence guarantees do not rely on prescribed large batch sizes and whose parameters can be chosen without prior knowledge of the total iteration budget. We show that {\sf RGR-SPIDER} reaches an ε-critical point using 𝒪(ε^−2) iterations and 𝒪(N+√Nε^−2) component-gradient evaluations, where N denotes the number of component functions. For the online setting, {\sf RGR-SRM} and {\sf RGR-EMA} achieve iteration complexities of 𝒪̃(ε^−3) and 𝒪̃(ε^−4), respectively. Experiments on principal component analysis, low-rank matrix completion, and orthogonal convolutional neural networks demonstrate faster empirical convergence than methods that construct recursive gradient estimators directly in Riemannian tangent spaces.
ER  -

Abstract

Related

Cite