Query Complexity of Derivative-Free Optimization

By Kevin G. Jamieson, Robert D. Nowak, B. Recht. 2012

175 citations recorded by the source corpus.

This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions. A distinctive feature of the algorithm is that it uses only Boolean-valued function comparisons, rather than function evaluations. This makes the algorithm useful in an even wider range of applications, such as optimization based on paired comparisons from human subjects, for example. We also show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training

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 Theory and Mathematics

In Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “In fact, this may seem to contradict the result in [13], which shows an Ω( √ d/T ) lower bound on quadratic functions.”
Simple random search provides a competitive approach to reinforcement learning (2018, methodology): “Jamieson et al. [14] oﬀer an information theoretic lower bound for derivative free convex optimization and show that a coordinate based random search method achieves the lower bound with nearly optimal dependence on the dimension.”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “[16] shows a lower bound O(1/ √ K) for any zeroth-order method with inaccurate evaluation.”
Simple random search of static linear policies is competitive for reinforcement learning (2018, methodology): “[13] offer an information theoretic lower bound for derivative free convex optimization and show that a coordinate based random search method achieves the lower bound with nearly optimal dependence on the dimension.”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, methodology): “Direct search methods that use the log-likelihood trick are necessarily derivative free optimization methods, and, in turn, are necessarily less eﬀective than methods that compute actual gradients, especially when the function evaluations are noisy [37].”
Risk minimization by median-of-means tournaments (2016, background): “Techniques of “derivative-free optimization” with “function comparison oracle” may be useful, see, for example, [20].”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, background): “Lower Bounds for Stochastic Optimization: Lower bounds have also been established in the stochastic convex optimization [2, 17] where each gradient- or function-value oracle query is corrupted with i.”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, methodology): “[13] present simpler comparisonbased algorithms for solving a subclass of such problems, and Shamir [14] gives optimal algorithms for quadratic objectives, as well as providing some lower bounds on optimization error when only single function values are available.”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, unknown): “…of UCB to the continuous bandit setting (Srinivas et al., 2010; Bubeck et al., 2011; Munos, 2011; de Freitas et al., 2012; Valko et al., 2013), we aim to extend RUCB to the continuous dueling bandit setting, without a convexity assumption as in (Yue & Joachims, 2009; Jamieson et al., 2012).”
Fine-Tuning Language Models with Just Forward Passes (2023, background): “[45] Kevin G Jamieson, Robert Nowak, and Ben Recht.”
Learning Structured Predictors from Bandit Feedback for Interactive NLP (2016, methodology): “Sokolov et al. (2015) showed in a simulation experiment that partial information in form of translation quality judgements on predicted translations is sufficient for model adaptation in SMT.”