Stochastic Convex Optimization with Bandit Feedback

By Alekh Agarwal, Dean Phillips Foster, Daniel J. Hsu, Sham M. Kakade, Alexander Rakhlin. 2011

250 citations recorded by the source corpus.

This paper addresses the problem of minimizing a convex, Lipschitz function f over a convex, compact set χ under a stochastic bandit feedback model. In this model, the algorithm is allowed to observe noisy realizations of the function value f(x) at any query point x ∈ χ. We demonstrate a generalization of the ellipsoid algorithm that incurs O(poly (d) √T) regret. Since any algorithm has regret at least Ω(√T) on this problem, our algorithm is optimal in terms of the scaling with T.

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

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “In contrast, the current best-known upper bounds areO( 4 √ d2/T ),O( 3 √ d2/T ),O( √ d2/T ) for convex, strongly-convex, and strongly-convex-and-smooth functions respectively [11, 2]; And aO( √ d32/T ) bound for convex functions [3], which is better in terms of dependence on T but very bad in terms ”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Another direction for nonlinear stochastic bandits was recently investigated in [Agarwal et al., 2011b].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “[2] proved a regret of O(poly(N ) √ K) for zeroth-order bandit algorithm on convex objectives.”
Query Complexity of Derivative-Free Optimization (2012, methodology): “While there are known theoretical results for DFO in the noiseless setting [15, 5, 10], to the best of our knowledge we are the first to characterize lower bounds for DFO in the stochastic setting.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “Another popular setting is when the mean-reward function x 7→ μ(x) is convex [56, 5] in which case regret bounds of order O(poly(d) √ n) can be achieved3.”
Bandits with Knapsacks (2013, background): “3: Over the next | X | rounds, for each x ∈ X : choose an arm as an independent sample from D .”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, background): “Therefore, many researchers have extensively studied and applied various SGD methods [3,4,5].”
Bandit Algorithms (2020, methodology): “As we mentioned in Note 5, there exist efficient algorithms for stochastic contextual bandit problems when a suitable optimisation oracle is available [Agarwal et al., 2014]. An earlier attempt to address the problem of reducing contextual bandits to cost-sensitive ERM is by Dud́ık et al. [2011]. Th”
Non-Stationary Stochastic Optimization (2013, unknown): “Considering a convex (and diﬀerentiable) cost function, Agarwal et al. (2013) showed that the minimax regret is of the same order, building on estimation methods presented in Nemirovski and Yudin (1983).”
HopSkipJumpAttack: A Query-Efficient Decision-Based Attack (2019, background): “Agarwal et al. [19] and Nesterov and Spokoiny [20] demonstrated that faster convergence can be achieved by using two function evaluations for estimating the gradient.”
Boundary Attack++: Query-Efficient Decision-Based Adversarial Attack (2019, background): “Agarwal et al. [1] and Nesterov and Spokoiny [23] observed a faster convergence rate by using two function evaluations for estimating gradient.”
Random Gradient-Free Minimization of Convex Functions (2015, background): “In [2], themodel of the oracle admits even more noise.”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, background): “[7] provide algorithms that achieve convergence rates after k iterations of O(d16/√k); however, as the authors themselves note, the algorithms are quite complicated.”