mlsanityData to 7 Oct 2026

Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization

arXiv 1910.12166 ↗First posted 27 Oct 2019cs.LG math.OC stat.MLcited by 47

Not on the map. Why?

Abstract (arXiv)

Two types of zeroth-order stochastic algorithms have recently been designed for nonconvex optimization respectively based on the first-order techniques SVRG and SARAH/SPIDER. This paper addresses several important issues that are still open in these methods. First, all existing SVRG-type zeroth-order algorithms suffer from worse function query complexities than either zeroth-order gradient descent (ZO-GD) or stochastic gradient descent (ZO-SGD). In this paper, we propose a new algorithm ZO-SVRG-Coord-Rand and develop a new analysis for an existing ZO-SVRG-Coord algorithm proposed in Liu et al. 2018b, and show that both ZO-SVRG-Coord-Rand and ZO-SVRG-Coord (under our new analysis) outperform other exiting SVRG-type zeroth-order methods as well as ZO-GD and ZO-SGD. Second, the existing SPIDER-type algorithm SPIDER-SZO (Fang et al. 2018) has superior theoretical performance, but suffers from the generation of a large number of Gaussian random variables as well as a √ε-level stepsize in practice. In this paper, we develop a new algorithm ZO-SPIDER-Coord, which is free from Gaussian variable generation and allows a large constant stepsize while maintaining the same convergence rate and query complexity, and we further show that ZO-SPIDER-Coord automatically achieves a linear convergence rate as the iterate enters into a local PL region without restart and algorithmic modification.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 4; 2024: 9; 2025: 12; 2026: 7.

47 papers.

Sort:

By area:

  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  2. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  3. 2024Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Modelscited by 50
  4. 2024Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structurescited by 48
  5. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  6. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 33
  7. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  8. 2024Zeroth-Order Fine-Tuning of LLMs in Random Subspacescited by 23
  9. 2021Distributed Learning Systems with First-order Methodscited by 17
  10. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  11. 2025ComPO: Preference Alignment via Comparison Oraclescited by 11
  12. 2026Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalizationcited by 11
35 more
  1. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  2. 2025Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbationscited by 9
  3. 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
  4. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  5. 2021Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimizationcited by 6
  6. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  7. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  8. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  9. 2024Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approachcited by 5
  10. 2025ElasticZO: A Memory-Efficient On-Device Learning with Combined Zeroth- and First-Order Optimizationcited by 4
  11. 2022Lazy Queries Can Reduce Variance in Zeroth-order Optimizationcited by 2
  12. 2025Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scalecited by 2
  13. 2025Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbationscited by 2
  14. 2025On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimizationcited by 2
  15. 2021Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Methodcited by 1
  16. 2021An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimizationcited by 1
  17. 2022Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectivescited by 1
  18. 2023Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approachcited by 1
  19. 2024Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradientcited by 1
  20. 2024Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimizationcited by 1
  21. 2024Gradient-Free Method for Heavily Constrained Nonconvex Optimizationcited by 1
  22. 2026Optimal low-rank stochastic gradient estimation for LLM trainingcited by 1
  23. 2022Adaptive Stochastic Optimisation of Nonconvex Composite Objectivescited by 0
  24. 2024Gradient Testing and Estimation by Comparisonscited by 0
  25. 2024Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithmscited by 0
  26. 2025Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimizationcited by 0
  27. 2025VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergencecited by 0
  28. 2025A Structured Tour of Optimization with Finite Differencescited by 0
  29. 2025A Unified Perspective on Optimization in Machine Learning and Neuroscience: From Gradient Descent to Neural Adaptationcited by 0
  30. 2025ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Modelscited by 0
  31. 2026Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotioncited by 0
  32. 2026Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulationcited by 0
  33. 2026Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNscited by 0
  34. 2026Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuningcited by 0
  35. 2026A Zeroth-Order Paradigm for LLM Preference Alignmentcited by 0