Research map / Optimization / Nonconvex and smooth optimization
Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coordinate-wise outer-loop estimation and independent random smoothing directions for paired inner-loop estimates (ZO-SVRG-Coord-Rand) | SVRG-based zeroth-order optimization · Nonconvex optimization | function query complexity: \mathcal{O}\left(\min\left\{\frac{dn^{2/3}}{\epsilon},\,\frac{d}{\epsilon^{5/3}}\right\}\right) | Helped |
| Apply the refined variance analysis to ZO-SVRG-Coord | ZO-SVRG-Coord · Nonconvex optimization | function query complexity: \mathcal{O}\left(\min\left\{\frac{dn^{2/3}}{\epsilon},\,\frac{d}{\epsilon^{5/3}}\right\}\right) | Helped |
| Replace Gaussian random gradient estimation with coordinate-wise estimation in SPIDER | SPIDER-SZO · Nonconvex optimization | function query complexity: same complexity performance | No clear effect |
| Use coordinate-wise estimation in SPIDER | SPIDER-SZO · Nonconvex optimization | Gaussian sample complexity: None | Helped |
| Use a constant-level stepsize instead of SPIDER-SZO's small stepsize | SPIDER-SZO · Nonconvex optimization | stepsize: \mathcal{O}( 1) vs. \mathcal{O}(\sqrt{\epsilon}) | Helped |
| Use mini-batch ZO-SPIDER-Coord rather than ZO-SVRG-Coord-Rand | Nonconvex zeroth-order optimization · Nonconvex optimization | function query complexity: factor of \min\{\epsilon^{-1/6}, n^{1/6}\} | Helped |
| Use coordinate-wise recursive estimates under the PL condition without restart | ZO-SPIDER-Coord · Nonconvex optimization under PL condition | convergence rate: \left(1-\frac{1}{16L\gamma}\right)^K | Helped |
| Add a proximal gradient step for the nonsmooth term | ZO-SPIDER-Coord · Nonconvex nonsmooth composite optimization | function query complexity: \mathcal{O}\left(\min\left\{n^{1/2}d\epsilon^{-1}, d\epsilon^{-3/2} \right\}\right) | Helped |
| Use ZO-SVRG-Coord-Rand-C instead of ZO-SGD | Convex zeroth-order optimization · Convex optimization | function query complexity: \mathcal{O}(d\min\{n,1/\epsilon\}\log(1/\epsilon)) vs. \mathcal{O}(d/\epsilon^{2}) | Helped |
| Use ZO-SPIDER-Coord-C instead of ZO-SGD | Convex zeroth-order optimization · Convex optimization | function query complexity: \mathcal{O}(d\min\{n,1/\epsilon\}\log(1/\epsilon)) vs. \mathcal{O}(d/\epsilon^{2}) | Helped |
| Use SVRG-based algorithms rather than SPIDER-based algorithms in the reported experiments | ZO-SVRG-Coord-Rand and ZO-SPIDER-Coord · Black-box adversarial examples and nonconvex logistic regression | empirical convergence and function-query performance | Mixed |
| Use ZO-SVRG-Coord-Rand rather than ZO-SGD or ZO-SVRG-Ave | Black-box adversarial example generation · MNIST digit 4 image distortion | image distortion: 13.85 -> 11.21 | Helped |
Closest papers by meaning
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.91)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.89)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.89)
- Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications (NeurIPS 2024 · similarity 0.88)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.88)
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.