Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations

By John C. Duchi, Michael I. Jordan, Martin J. Wainwright, Andre Wibisono. 2013

595 citations recorded by the source corpus.

We consider derivative-free algorithms for stochastic and nonstochastic convex optimization problems that use only function values rather than gradients. Focusing on nonasymptotic 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 nonsmooth 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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Episodic Exploration for Deep Deterministic Policies: An Application to StarCraft Micromanagement Tasks (2016, background): “In addition to implementing a local random search in the policy space, the motivation for this randomization comes from stochastic gradient-free optimization [14, 21, 30, 9, 11], where”
Evolution Strategies as a Scalable Alternative to Reinforcement Learning (2017, methodology): “Derivative free optimization methods have also been analyzed in the convex setting Duchi et al. [2015], Nesterov [2012].”
Fine-Tuning Language Models with Just Forward Passes (2023, methodology): “Thus, in principle, the method can update neural networks with just forward passes, though naive implementation still doubles the memory overhead and classical lower bounds [69, 32] suggest that convergence slows linearly with model size.”
Communication-Efficient Edge AI: Algorithms and Systems (2020, background): “Communication-EfﬁcientAlgorithmsforEdgeAI Zeroth-Order Methods • Optimal rates for zeroth-order convex optimization [42] • Distributed zeroth-order algorithms over time-varying networks [43], [44] First-Order Methods • Variance reduction for minimizing communication rounds [36], [37] • Gradient…”
Square Attack: a query-efficient black-box adversarial attack via random search (2019, result): “We obtain the following result, similar to existing convergence rates for zeroth-order methods [42,43,24]:”
Boundary Attack++: Query-Efficient Decision-Based Adversarial Attack (2019, background): “Duchi et al. [8] established optimal rates of convex zeroth-order optimization via mirror descent with two-point gradient estimates.”
Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates. (2018, methodology): “This paper and our prior works [19], [20] distinguish further from other works on distributed zeroth order optimization, e.g., [14], [21], in that, not only the gradient is approximated through function values due to the absence of ﬁrst order information, but also the function values themselves are…”
Improving Black-box Adversarial Attacks with a Transfer-based Prior (2019, methodology): “It is noted that ĝi → ui ∇xf(x, y) · ui when σ → 0, which is nearly an unbiased estimator of the gradient [10] when E[uiui ] = I.”
AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks (2018, background): “Note that with b = 1, the gradient estimator in (3) becomes the one used in (Duchi et al. 2015).”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, methodology): “Although the optimal rate for ZO unconstrained convex optimization was studied in [21], there remain many open questions on seeking the optimal rates, or associated tight lower bounds, for general cases of ZO constrained nonconvex optimization.”
Stochastic Structured Prediction under Bandit Feedback (2016, methodology): “Work on stochasti p irwise learning has been formalized as derivative-free stochastic zeroth-order optimization [1, 9, 6].”
HopSkipJumpAttack: A Query-Efficient Decision-Based Attack (2019, background): “Duchi et al. [21] established optimal rates of convex zeroth-order optimization via mirror descent with two-point gradient estimates.”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, result): “Note that these assumptions are similar to the assumptions made in other zeroth-order analysis works, (Flaxman et al., 2005; Agarwal et al., 2010; Duchi et al., 2015; Shamir, 2013; Ghadimi and Lan, 2013; Nesterov and Spokoiny, 2017).”
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (2017, methodology): “We consider a smooth approximation of it following the idea of Duchi et al. [13]: where σ > 0 is a smoothing parameter.”