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

arXiv: https://arxiv.org/abs/1312.2139 · HTML: https://mlsanity.com/paper/1312.2139/

## Key facts

- Cited by 198 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2013.

## Built on by (most cited first, 30 of 198)

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [Do Differentiable Simulators Give Better Policy Gradients?](https://mlsanity.com/paper/2202.00817/) (2022)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Test-Time Model Adaptation with Only Forward Passes](https://mlsanity.com/paper/2404.01650/) (2024)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models](https://mlsanity.com/paper/2404.08080/) (2024)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Random Noise Defense Against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2104.11470/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Query-Efficient Black-box Adversarial Attacks Guided by a Transfer-based Prior](https://mlsanity.com/paper/2203.06560/) (2022)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Zeroth-Order Fine-Tuning of LLMs in Random Subspaces](https://mlsanity.com/paper/2410.08989/) (2024)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Corruption Robust Offline Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2402.06734/) (2024)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [On the Convergence of Zeroth-Order Federated Tuning for Large Language Models](https://mlsanity.com/paper/2402.05926/) (2024)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy](https://mlsanity.com/paper/2410.09591/) (2024)
- [Zero-th Order Algorithm for Softmax Attention Optimization](https://mlsanity.com/paper/2307.08352/) (2023)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)

## 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.