Research map / Optimization / Nonconvex and smooth optimization
Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity
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 RAZGD, a Riemannian accelerated zeroth-order gradient descent using coordinate-wise finite-difference estimators in tangent spaces, achieving O(d ε^{-7/4}) query complexity for first-order stationary points and larger smoothing parameters for robustness.
Problem
Nonconvex optimization on Riemannian manifolds using only function value (zeroth-order) queries, aiming to find first- and second-order stationary points with low query complexity and robust (larger) smoothing parameters.
Approach
Extends coordinate-wise finite-difference zeroth-order gradient estimates to Riemannian manifolds via pullback functions and tangent-space bases, and embeds an accelerated (Nesterov-style) tangent-space step alternating with Riemannian zeroth-order gradient descent steps; a perturbation yields second-order guarantees and a stable-manifold argument gives almost sure convergence.
Key results
- RAZGD with Option I achieves O(d ε^{-7/4}) function query complexity for ε-approximate first-order stationary points, improving on the prior O(d ε^{-2}) by a factor of ε^{-1/4} (ZO-RGD-style rate).
- Perturbed RAZGD reaches second-order stationary points with high probability at Õ(d ε^{-7/4}) queries using smoothing parameter Õ(ε^{7/8} d^{-1/2}), versus Õ(ε^{13/8} d^{-1/2}) in prior accelerated zeroth-order work.
- On the sphere hypervolume experiment, RAZGD reaches target accuracy within 30 seconds while PZGD needs more than 300 seconds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RAZGD with Option I instead of ZO-RGD | Riemannian zeroth-order optimization · Riemannian first-order stationary point | function query complexity: \mathcal{O}\left(\frac{d}{\epsilon^{2}}\right) -> \mathcal{O}\left(\frac{d}{\epsilon^{7/4}}\right) | Helped |
| Use Perturbed RAZGD with Option I instead of ZO-PAGD | Riemannian zeroth-order optimization · Second-order stationary point | smoothing parameter: \tilde{\mathcal{O}}\left(\frac{\epsilon^{13/8}}{\sqrt{d}}\right) -> \tilde{\mathcal{O}}\left(\frac{\epsilon^{7/8}}{\sqrt | Helped |
| Use Perturbed RAZGD with Option I at the same smoothing parameter | Quartic function optimization · Quartic function on Euclidean space | variance across runs | Helped |
| Increase the smoothing parameter to 0.3 | Perturbed RAZGD · Quartic function on Euclidean space | convergence: μ=0.01 -> μ=0.3 | Helped |
| Use non-perturbed RAZGD with Option I instead of RZGD and PZGD | Simplex constrained least-squares · Linear least-squares over the unit simplex | function queries | Helped |
| Use RAZGD instead of PZGD | Optimal linear combination of continuous predictors · Empirical hypervolume under the unit sphere | time to target accuracy: 30 seconds; more than 300 seconds | Helped |
Limitations
- Assumptions (local Lipschitz gradient and Hessian of pullback, bounded retraction singular values) are strong and only hold locally.
- Asymptotic convergence uses a slower-decaying smoothing schedule only in theory; exponential decay makes the method nearly first-order.
- Experiments are small-scale (quartic function, simplex and sphere problems) without comparison on large-scale problems.
Experimental setup
Benchmarks: quartic function simplex-constrained least squares empirical hypervolume under sphere manifold
Metrics: function value versus number of function queries running time to target accuracy variance across runs
Baselines: ZO-RGD ZO-PAGD ZO-Perturbed-AGD ZO-Perturbed-AGD-ANCF PZGD ZO-GD PAGD ZO-GD-NCF ZOPGD
Builds on: Riemannian gradient descent Nesterov accelerated gradient ZO-PAGD pullback function
Closest papers by meaning
- Acceleration via silver step-size on Riemannian manifolds with applications to Wasserstein space (NeurIPS 2025 · similarity 0.89)
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.87)
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.87)
- Implicit Riemannian Optimism with Applications to Min-Max Problems (ICML 2025 · similarity 0.87)
- Riemannian coordinate descent algorithms on matrix manifolds (ICML 2024 · similarity 0.87)
- An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.86)
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.