On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization

By Ohad Shamir. 2012

210 citations recorded by the source corpus.

The problem of stochastic convex optimization with bandit feedback (in the learning community) or without knowledge of gradients (in the optimization community) has received much attention in recent years, in the form of algorithms and performance upper bounds. However, much less is known about the inherent complexity of these problems, and there are few lower bounds in the literature, especially for nonlinear functions. In this paper, we investigate the attainable error/regret in the bandit and derivative-free settings, as a function of the dimension d and the available number of queries T. We provide a precise characterization of the attainable performance for strongly-convex and smooth functions, which also imply a non-trivial lower bound for more general problems. Moreover, we prove that in both the bandit and derivative-free setting, the required number of queries must scale at least quadratically with the dimension. Finally, we show that on the natural class of quadratic functions, it is possible to obtain a "fast" O(1/T) error rate in terms of T, under mild assumptions, even without having access to gradients. To the best of our knowledge, this is the first such rate in a derivative-free stochastic setting, and holds despite previous results which seem to imply the contrary.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Trust Region Policy Optimization (2015, background): “However, the complexity scales as d(2) if we are given single noisy function evaluations [8] and d if we are given pairs of evaluations with the same noise sample [9].”
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.”
Minimax Bounds on Stochastic Batched Convex Optimization (2018, background): “The gold-standard in such cases is for fully sequential algorithms that receive n queries, in which case the minimax rates for the two settings scale (ignoring polynomials in dimension d) as n− 1 2 and n−1, respectively (Agarwal et al., 2012; Shamir, 2013); achieving these comparatively good rates r”
Online Learning with Switching Costs and Other Adaptive Adversaries (2013, background): “…learning with full-information, even on a small finite action set and even in terms of the dependence onT (previous gaps we are aware of were either in terms of the number of actions Auer et al. [2002], or required large or continuous action spaces —see, e.g., Bubeck et al. [2011], Shamir [2012]).”
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).”