Research map / Optimization / Nonconvex and smooth optimization
Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RO2NC, a Riemannian online-to-nonconvex conversion for fully nonsmooth stochastic optimization on manifolds, with a zeroth-order variant (ZO-RO2NC), achieving O(δ^{-1}ε^{-3}) sample complexity for Goldstein-type stationarity.
Problem
Finite-time guarantees for finding (δ,ε)-Goldstein stationary points of fully nonsmooth, nonconvex stochastic objectives defined on Riemannian manifolds, with first-order and zeroth-order oracles.
Approach
Adapts the Euclidean O2NC online-to-nonconvex conversion to manifolds using retractions, with parallel transport or projection to relate tangent spaces; defines a Riemannian Goldstein δ-subdifferential and a zeroth-order estimator sampled in the tangent space whose expectation approximates it.
Key results
- RO2NC with parallel transport and with projection achieves O(δ^{-1}ε^{-3}) sample complexity for (δ,ε)-stationary points on manifolds, the first finite-time result for fully nonsmooth nonconvex Riemannian optimization.
- ZO-RO2NC attains the same sample complexity using a tangent-space-sampled zeroth-order gradient estimator.
- Numerical experiments on sparse PCA on the sphere show gradient-norm decay for both parallel transport and projection variants, with the projection variant comparable to parallel transport.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use projections instead of parallel transport (ablation) | RO2NC · Riemannian nonsmooth nonconvex optimization | sample complexity: O(\delta^{-1}\epsilon^{-3}) | No clear effect |
| Use zeroth-order function-value queries instead of gradient information | RO2NC · Riemannian nonsmooth nonconvex optimization | sample complexity: O(\delta^{-1}\epsilon^{-3}) | No clear effect |
| Use zeroth-order function-value queries instead of gradient information | RO2NC · Sparse principal component optimization on the unit sphere | convergence speed | Hurt |
| Use projection operations instead of parallel transport operations (ablation) | RO2NC · Sparse principal component optimization on the unit sphere | gradient norm | No clear effect |
Limitations
- Assumes bounded second fundamental form and retraction curve derivative bounds, which are stronger than bounded sectional curvature.
- Zeroth-order variant is more sensitive to parameter choice and converges more slowly in experiments.
- Experiments are limited to a single synthetic sparse PCA problem and only evaluate an upper bound on the stationarity measure.
Experimental setup
Datasets: synthetic Gaussian samples for sparse PCA on the sphere
Benchmarks: sparse PCA on the unit sphere (synthetic)
Metrics: upper bound on Goldstein gradient norm
Builds on: O2NC (online-to-nonconvex conversion) Goldstein stationarity Riemannian Clarke subdifferential
Closest papers by meaning
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.91)
- Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization (AAAI 2025 · similarity 0.89)
- Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (ICML 2024 · similarity 0.89)
- SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.89)
- Implicit Riemannian Optimism with Applications to Min-Max Problems (ICML 2025 · similarity 0.88)
- Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.