Data to 7 Oct 2026

Optimal rates for zero-order convex optimization: the power of two function evaluations

arXiv 1312.2139 ↗First posted 7 Dec 2013math.OC cs.IT math.ITcited by 190

Not on the map. Why?

Abstract (arXiv)

We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for d-dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most √d in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and non-smooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple (m ≥ 2) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.

Key facts. Cited by 190 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Dec 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 21; 2023: 28; 2024: 40; 2025: 40; 2026: 46.

190 papers.

Sort:

By area:

2023Fine-Tuning Language Models with Just Forward Passescited by 337
2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 113
2022Do Differentiable Simulators Give Better Policy Gradients?cited by 83
2023DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Trainingcited by 76
2024Test-Time Model Adaptation with Only Forward Passescited by 74
2021How to Learn when Data Reacts to Your Model: Performative Gradient Descentcited by 70
2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
2024Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuningcited by 53
2024Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Modelscited by 50
2024Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structurescited by 48
2022Private Convex Optimization via Exponential Mechanismcited by 47
2021Random Noise Defense Against Query-Based Black-Box Attackscited by 46

38 more

2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
2022Query-Efficient Black-box Adversarial Attacks Guided by a Transfer-based Priorcited by 38
2023Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oraclescited by 34
2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
2024Zeroth-Order Fine-Tuning of LLMs in Random Subspacescited by 23
2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
2024On the Convergence of Zeroth-Order Federated Tuning for Large Language Modelscited by 18
2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 18
2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
2023Zero-th Order Algorithm for Softmax Attention Optimizationcited by 16
2021Derivative-Free Reinforcement Learning: A Reviewcited by 15
2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
2023Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approachcited by 14
2024Synergizing Foundation Models and Federated Learning: A Surveycited by 14
2021Projection-free Distributed Online Learning with Sublinear Communication Complexitycited by 13
2023Gradient-free optimization of highly smooth functions: improved analysis and a new algorithmcited by 12
2023Continuation Path Learning for Homotopy Optimizationcited by 12
2023Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networkscited by 12
2024Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimizationcited by 12
2024Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimizationcited by 12
2022Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learningcited by 11
2024Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimizationcited by 11
2025ComPO: Preference Alignment via Comparison Oraclescited by 11
2026Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalizationcited by 11
2024Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Priorcited by 10
2021Preference learning along multiple criteria: A game-theoretic perspectivecited by 9
2023Learning the Kalman Filter with Fine-Grained Sample Complexitycited by 9
2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
2023Revisiting LQR Control from the Perspective of Receding-Horizon Policy Gradientcited by 9
2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
2025Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbationscited by 9
2026The Blessing of Dimensionality in LLM Fine-tuning: A Variance-Curvature Perspectivecited by 9
2022Stochastic Zeroth order Descent with Structured Directionscited by 8

50 most cited of 190 All 190 (JSON)