Single-loop O(ε^-3) stochastic smoothing algorithms for nonsmooth Riemannian optimization

2025/05/14 by Kangkang Deng, Deng, Kangkang, Peng, Zheng +2
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #FOS: Mathematics #Insurance, Mortality, Demography, Risk Management #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2505.09485

openalex publication_date 2025/05/14 · openalex created_date 2025/10/08 · openalex updated_date 2026/07/28

Abstract

In this paper, we develop two Riemannian stochastic smoothing algorithms for nonsmooth optimization problems on Riemannian manifolds, addressing distinct forms of the nonsmooth term \( h \). Both methods combine dynamic smoothing with a momentum-based variance reduction scheme in a fully online manner. When \( h \) is Lipschitz continuous, we propose an stochastic algorithm under adaptive parameter that achieves the optimal iteration complexity of \( O(ε^-3) \), improving upon the best-known rates for exist algorithms. When \( h \) is the indicator function of a convex set, we design a new algorithm using truncated momentum, and under a mild error bound condition with parameter \( θ≥ 1 \), we establish a complexity of \( O(ε^-max\θ+2, 2θ\) \), in line with the best-known results in the Euclidean setting. Both algorithms feature a single-loop design with low per-iteration cost and require only \( O(1) \) samples per iteration, ensuring that sample and iteration complexities coincide. Our framework encompasses a broad class of problems and recovers or matches optimal complexity guarantees in several important settings, including smooth stochastic Riemannian optimization, composite problems in Euclidean space, and constrained optimization via indicator functions.

Citations

• Stochastic momentum ADMM for nonconvex and nonsmooth optimization with application to PnP algorithm
• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees
• Oracle complexities of augmented Lagrangian methods for nonsmooth manifold optimization
• Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction
• Non-convex Stochastic Composite Optimization with Polyak Momentum
• Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization
• Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization
• Inexact Sequential Quadratic Optimization for Minimizing a Stochastic Objective Function Subject to Deterministic Nonlinear Equality Constraints
• Riemannian stochastic recursive momentum method for non-convex optimization
• Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• A Brief Introduction to Manifold Optimization
• Momentum-Based Variance Reduction in Non-Convex SGD
• Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming
• Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming

Related

• A Single-loop Stochastic Riemannian ADMM for Nonsmooth Optimization
• Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
• Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction
• Riemannian stochastic recursive momentum method for non-convex optimization
• Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds