Source-linked AI summary
Online convex optimization in the bandit setting: gradient descent without a gradient
Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan
TL;DR
The paper asks whether online convex optimization can achieve low regret when each changing function is observed only at the chosen point. It uses a single randomized function evaluation to estimate the gradient and extends online gradient-descent analysis, obtaining vanishing regret with bounded-function assumptions and improved rates under Lipschitz continuity.
Problem
Bandit online optimization provides only black-box access to changing convex functions, revealing the value at the chosen point but not the gradient or values elsewhere.
Method
The method estimates a gradient from one randomized evaluation and interprets the estimator as unbiased for the gradient of a smoothed function.
Results
The analysis obtains expected regret O(n^5/6) under bounded-function assumptions and O(n^3/4) when the functions are additionally L-Lipschitz.
Takeaways & Limitations
A single-point gradient estimate is sufficient to extend Zinkevich’s online gradient-descent analysis to the bandit setting against an oblivious adversary.
Takeaways & Limitations
The model assumes a fixed sequence of bounded convex functions and handles only an oblivious adversary; unconstrained analysis remains an open direction because boundedness may fail.
Abstract
from arXiv · showhide
We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a signle point (from some feasible set) and pay a cost equal to the value of the next function on our chosen point. Zinkevich shows that, if the each function is revealed after the choice is made, then one can achieve vanishingly small regret relative the best single decision chosen in hindsight. We extend this to the bandit setting where we do not find out the entire functions but rather just their value at our chosen point. We show how to get vanishingly small regret in this setting. Our approach uses a simple approximation of the gradient that is computed from evaluating a function at a single (random) point. We show that this estimate is sufficient to mimic Zinkevich's gradient descent online analysis, with access to the gradient (only being able to evaluate the function at a single point).
1 Introduction
The paper extends online gradient descent to bandit convex optimization, where only the chosen point’s function value is observed and gradients are unavailable. It uses a single randomized evaluation to approximate the gradient and obtains regret guarantees under bounded-function assumptions, improved by Lipschitz continuity.
- Problem: Bandit online optimization reveals only c_t(x_t), so the decision-maker cannot directly access gradients while functions may change adversarially over time.The model restricts each next decision to prior decisions, observed costs, and private randomness.
- Method: The algorithm uses a one-point gradient estimate from evaluating the function at x + δu, with u uniformly random, instead of explicit multi-point finite differences.Its expectation is tied to the gradient of a smoothed function, allowing gradient-descent analysis despite one evaluation per function.
- Novelty: The estimate is sufficient for gradient descent even against an oblivious adversary, extending prior one-point approaches beyond their stochastic settings.The paper contrasts its adversarial model with related work by Granichin and Spall.
- Guarantees: The analysis replaces differentiability and bounded-gradient assumptions with bounded-function assumptions, while obtaining expected regret O(n^5/6) instead of full-information O(n^1/2).With an additional L-Lipschitz assumption, expected regret improves to O(n^3/4).
- Analysis: The analysis handles perturbations outside the feasible set by restricting iterates to an interior subset and relating guarantees to the feasible set’s inner and outer radii.Reshaping the feasible body can reduce the radius ratio to at most d.
2 Approximating the gradient with a single sample
The paper constructs a one-point gradient estimator by sampling a random unit direction and scaling it by a single function evaluation. Its expectation equals the gradient of a ball-smoothed version of the function, even when the original function is nondifferentiable.
- Estimator: A random unit vector u and the evaluation f(x + δu) produce a one-point estimate whose expectation is proportional to the gradient of a smoothed function.The construction follows from applying the fundamental theorem of calculus in one dimension and Stokes’ theorem in higher dimensions.
- Smoothing: The smoothed function averages f over a ball of radius δ around x, making the estimator’s target differentiable even when f is not.The paper explicitly notes that the smoothed function is differentiable without requiring differentiability of f.
3 Expected Gradient Descent
The analysis extends projected online gradient descent to bandit feedback by using a single-sample gradient estimator and controlling smoothing, feasibility, and geometry. It derives expected-regret guarantees, improves the Lipschitz case through reshaping, and identifies extensions and boundaries of the approach.
- Expected Gradient Descent: Expected projected descent preserves Zinkevich’s analysis when random updates are unbiased for the current gradients and uniformly bounded.The update starts at the center of a containing ball and projects each step back onto the feasible set; the proof uses squared distance to the comparator as a potential.
- 3.2 Reshaping: Near-isotropic preprocessing removes the explicit dependence on the feasible body’s inner radius and yields a corollary for diameter-D, L-Lipschitz domains.The transformation gives an inner radius of 1, an outer radius of about 1.01d, and preserves Lipschitz control with parameter LR.
- Expected Gradient Descent: The bandit algorithm replaces unavailable gradients with a one-point estimator whose expectation equals the gradient of a smoothed cost function.This lets the method apply expected-gradient descent to smoothed functions while accounting separately for smoothing and exploration errors.
- 3.3 Conclusions: The analysis requires an oblivious adversary and leaves adaptive step sizes, non-stationary comparators, and unconstrained domains as possible extensions or open difficulties.The unconstrained case is difficult because boundedness of the convex functions cannot be assumed; slowly changing functions might permit previous evaluations to control estimator magnitude.