Online convex optimization in the bandit setting: gradient descent without a gradient

By Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan. 2004

1,009 citations recorded by the source corpus.

We study a general online convex optimization problem. We have a convex set S and an unknown sequence of cost functions c<inf>1</inf>, c<inf>2</inf>,..., and in each period, we choose a feasible point x<inf>t</inf> in S, and learn the cost c<inf>t</inf>(x<inf>t</inf>). If the function c<inf>t</inf> is also revealed after each period then, as Zinkevich shows in [25], gradient descent can be used on these functions to get regret bounds of O(√n). That is, after n rounds, the total cost incurred will be O(√n) more than the cost of the best single feasible decision chosen with the benefit of hindsight, min<inf>x</inf> Σ ct(x).We extend this to the "bandit" setting, where, in each period, only the cost c<inf>t</inf>(x<inf>t</inf>) is revealed, and bound the expected regret as O(n3/4).Our approach uses a simple approximation of the gradient that is computed from evaluating c<inf>t</inf> at a single (random) point. We show that this biased estimate is sufficient to approximate gradient descent on the sequence of functions. In other words, it is possible to use gradient descent without seeing anything more than the value of the functions at a single point. The guarantees hold even in the most general case: online against an adaptive adversary.For the online linear optimization problem [15], algorithms with low regrets in the bandit setting have recently been given against oblivious [1] and adaptive adversaries [19]. In contrast to these algorithms, which distinguish between explicit explore and exploit periods, our algorithm can be interpreted as doing a small amount of exploration in each period.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

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 ”
Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies (2015, background): “An important insight is that the gradient of an unknown function at a specific point can be estimated by perturbing its input (Flaxman et al., 2005).”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “This step takes time polynomial in p with additional polylog factor in 1r where r > 0 is the diameter of the largest ball we can fit inside C (See [35] and [23]).”
Introduction to Online Convex Optimization (2016, methodology): “The full generality BCO setting was introduced by Flaxman, Kalai and McMahan in (42), who gave the first efficient and low-regret algorithm for BCO.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The approach presented in this chapter for online convex optimization with bandit feedback was pioneered by [Flaxman et al., 2005] and [Kleinberg, 2004].”
Simple random search provides a competitive approach to reinforcement learning (2018, methodology): “BRS is called Bandit Gradient Descent by Flaxman et al. [7].”
Fair Algorithms for Infinite and Contextual Bandits (2016, methodology): “This may be undesirable for large k , thus motivating the investigation of fair algorithms for the inﬁnite bandit setting (the online linear optimization with bandit feedback problem Flaxman et al. [2005]).”
Online Learning and Online Convex Optimization (2012, methodology): “The proof for d > 1 follows similarly using Stoke’s theorem and can be found in [16].”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, background): “in [Flaxman et al., 2005]) to show that the gradient of Cr(K) can be estimated just with an oracle for function value.”
Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization (2008, methodology): “Flaxman et al [9] developed a bandit optimization algorithm that used OGD as the full-information subroutine A.”
Multi-armed bandits in metric spaces (2008, background): “While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with exponentially or infinitely large strategy sets are still a topic of very active investigation [1, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 16, 17].”
Fine-Tuning Language Models with Just Forward Passes (2023, methodology): “Many one-point gradient estimators have been proposed in past works [34, 87, 95], and using such estimators in place of SPSA would halve the training time.”
Contextual Bandits with Similarity Information (2009, background): “The bandit problems with large arm sets have been studied in [7, 2, 4, 6, 20, 28, 21, 15, 12, 13, 14, 5, 19, 24].”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, background): “with radius 1 [20], μ > 0 is a perturbation radius (also called a smoothing parameter), and φ(d) denotes a certain dimension-”
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient (2016, methodology): “For any wt ∈ (1− ξ)Ω and any unit vector u, wt + δu ∈ Ω (Flaxman et al., 2005).”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, neutral): “…research areas such as stochastic optimization [Rakhlin et al., 2011, Liu et al., 2018], image retrieval [Gao et al., 2017], multiple kernel learning [Lu et al., 2016, Shen et al., 2018], and bandit problems [Flaxman et al., 2005, Arora et al., 2012, Kwon and Perchet, 2017, Kock et al., 2016], etc.”