Source-linked AI summary
Kernel-based methods for bandit convex optimization
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee
TL;DR
The paper addresses unresolved information-theoretic limits and estimation difficulties in derivative-free and convex bandit optimization. It develops a polynomial-time robust method using kernel-based estimation, achieving polynomial-in-dimension regret, while leaving open the necessity of focus regions and restart mechanisms.
Problem
Information-theoretic limits for derivative-free optimization remain unknown even for bounded convex functions, and convex bandits lack an obvious unbiased loss estimator from one-point observations.
Method
The approach uses kernel methods to construct unbiased estimates and relates smoothed-play regret to the original loss through the kernel adjoint.
Results
The method provides a polynomial-time algorithm with polynomial-in-dimension regret, including a variant running in poly(n log(T)) time with regret at most nO(1)T^1/2+1/log log T.
Takeaways & Limitations
The paper conjectures that a modification could require only O(n^3/ε^2) queries, potentially optimal even without adversarial noise.
Takeaways & Limitations
Open questions remain about whether focus regions and restart mechanisms are necessary, especially in the stochastic case.
Abstract
from arXiv · showhide
We consider the adversarial convex bandit problem and we build the first $\mathrm{poly}(T)$-time algorithm with $\mathrm{poly}(n) \sqrt{T}$-regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves $\tilde{O}(n^{9.5} \sqrt{T})$-regret, and we show that a simple variant of this algorithm can be run in $\mathrm{poly}(n \log(T))$-time per step at the cost of an additional $\mathrm{poly}(n) T^{o(1)}$ factor in the regret. These results improve upon the $\tilde{O}(n^{11} \sqrt{T})$-regret and $\exp(\mathrm{poly}(T))$-time result of the first two authors, and the $\log(T)^{\mathrm{poly}(n)} \sqrt{T}$-regret and $\log(T)^{\mathrm{poly}(n)}$-time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve $\tilde{O}(n^{1.5} \sqrt{T})$-regret, and moreover that this regret is unimprovable (the current best lower bound being $Ω(n \sqrt{T})$ and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order $n^3 / ε^2$.
1 Introduction
Derivative-free optimization has longstanding applications, but its information-theoretic limits remain unknown even for bounded convex functions. This paper contributes a polynomial-time method for the robust setting and conjectures an optimal query complexity of O(n^3/ε^2).
- Information-theoretic limits remain unknown for derivative-free optimization, even for bounded convex functions.
- O(n^7.5/ε^2) queries are sufficient for noisy function evaluation, while Ω(n^2/ε^2) are necessary even for linear functions.
- The robust setting allows an adversary to arbitrarily corrupt an ε-fraction of queries, making it substantially less understood.
- The paper gives a polynomial-time method for the robust setting and conjectures O(n^3/ε^2) queries may be optimal without adversarial noise.
1.1 Bandit convex optimization
Bandit convex optimization gives feedback only through the loss at the played action, and the paper targets polynomial-time algorithms with polynomial dimension dependence and √T-regret. It also proposes faster variants and conjectures a near-optimal regret bound.
- At each round, the player selects an action, observes only its suffered convex loss, and is evaluated by cumulative regret.
- The main contribution is a first eO(poly(n)√T)-regret algorithm with polynomial(T)-time computation.
- The algorithm has a high-probability guarantee, while variants trade additional regret factors for per-step computation in poly(n log(T))-time.
- The conjectured target is eO(n^1.5√T)-regret, with no better regret bound achievable for large n and T.
1.2 Contributions
The paper develops kernelized continuous exponential weights for bandit convex optimization, using adaptive kernels, generalized Bernoulli convolutions, and a focus-region restart mechanism. It also outlines a simpler one-dimensional kernel and a polynomial-time implementation.
- Kernel methods: Kernel methods turn bandit feedback into an unbiased estimator for the adjoint-transformed loss.Sampling x from q and using f(x)K(x, ·)/q(x) yields an unbiased estimator of K*f; the adjoint identity connects this to the relevant regret expression.
- Generalized Bernoulli convolutions: Generalized Bernoulli convolutions define the kernel core through a distributional fixed-point identity.The core exists uniquely and can be represented as an infinite weighted sum of independent copies, generalizing the classical random-sign construction.
- Kernel methods: Adaptive kernels balance estimator smoothness against faithful approximation of losses near the exponential-weights distribution.As the distribution concentrates, the kernel can trade smoothness far from that region for greater local accuracy; fixed Gaussian convolution cannot provide this tradeoff.
- Dimension-specific variant: The one-dimensional variant replaces the core with the mean of p and samples λ uniformly from [0, 1].For n = 1, this simpler kernel yields a pseudo-regret upper bound of order log(T).
- High-dimensional algorithm: In higher dimensions, a focus-region test and restart mechanism handle variance control that is available only within a distribution-dependent region.If the test succeeds, the optimum lies in the focus region; if it fails, negative regret permits a safe restart.
- Polynomial-time implementation: The algorithm can be modified into a polynomial-time method using approximate log-concave sampling and optimization, with parameter and kernel adjustments.The modification also changes the focus-region construction and preserves polynomial-time performance under the stated geometric assumptions.
1.3 Related work
Prior work established important special cases and information-theoretic guarantees, but general explicit algorithms faced unfavorable dimension or time dependence. The paper situates its approach among bandit convex optimization and zeroth-order stochastic optimization results.
- General bandit convex optimization: Early bandit convex optimization methods achieved eO(poly(n)T^3/4)-regret using one-point gradient estimates.This bound remained the general state of the art for roughly a decade before later information-theoretic and explicit-algorithm advances.
- General bandit convex optimization: Bubeck and Eldan established that poly(n) guarantees are achievable, while Hazan and Li’s explicit result had regret and time complexity exponential in n.The comparison highlights the gap between information-theoretic existence and dimension-efficient explicit computation.
- Special cases: The linear bandit problem has a known minimax regret of eTheta(n sqrt(T)), making it an especially important special case.Its practical relevance is linked to contextual bandit applications.
- Special cases: Several subclasses already admitted square-root regret, including stochastic losses, strongly convex and smooth losses, and the one-dimensional case.These results covered restricted settings rather than the fully general adversarial convex bandit problem.
- Zeroth-order stochastic optimization: Zeroth-order stochastic convex optimization studies simple regret under i.i.d. losses and is closely related to cumulative bandit regret.A cumulative-regret bound implies a simple-regret bound by taking the center of mass of played points.
- Zeroth-order stochastic optimization: Prior zeroth-order results included eO(n^3.25/...) guarantees, while the paper conjectures stronger bounds for bounded convex functions and adversarially noisy settings.The cited prior result is described as the state of the art without adversarial noise; the paper’s stronger statements are conjectural.
1.4 Open problems
The paper identifies unresolved questions about the optimal dimension dependence of bandit convex optimization and several technical routes for improving it. It also asks whether focus regions, restarts, and exponential weights are essential components of the approach.
- Dimension dependence: The main open problem is proving the conjectured optimal dimension dependence or finding the correct alternative.The paper presents the proposed n^1.5 dependence as unresolved and notes that the conjecture may be wrong.
- Lower bounds: The conjectured lower bound would require quantifying the relation between information gain and loss non-linearity.This relation would expose the adversary’s trade-off between loss and information.
- Dimension dependence: Three sources of dimension loss are identified: Gaussian rather than real cores, Hoeffding rather than Bernstein bounds, and oversized focus regions for restart guarantees.The paper states that improving any of these points appears difficult.
- Algorithmic design: It remains unclear whether focus regions and restarts are necessary, particularly because restarts may be irrelevant in the stochastic setting.The paper specifically asks whether the restart condition is ever satisfied with high probability for i.i.d. losses.
- Algorithmic design: The authors also ask whether gradient descent could replace exponential weights in the kernelized framework.Their intuition is that the estimated loss is close to linear when the distribution is concentrated near its centroid.
2 Kernelized exponential weights
The kernelized strategy combines adaptive kernel smoothing with continuous exponential weights to obtain unbiased loss estimates from bandit feedback. Its regret is reduced to the regret of exponential weights on smoothed losses, with a factor depending on the kernel properties.
- Kernel framework: A kernel K is a linear map on measures with adjoint K* on functions, defined by ⟨Kp,f⟩ = ⟨p,K*f⟩.The adjoint lets the method construct estimators for smoothed losses from one bandit observation.
- Strategy: The strategy samples from an adaptive kernel applied to the exponential-weights distribution and updates using an estimated loss function.The kernel K_t depends on p_t, and the sampled action is drawn from K_t p_t.
- Regret analysis: The theorem requires kernel conditions including approximation, boundedness, and smoothness of K[p]*f.For convex 1-Lipschitz f, the smoothed function must be L-Lipschitz.
- Estimator: The estimated loss is unbiased for K*ℓ_t, allowing bandit feedback to drive continuous exponential weights.The estimator uses the observed loss multiplied by a kernel value and divided by the sampling density.
- Regret analysis: The strategy’s pseudo-regret is controlled, up to a factor 1/λ, by exponential weights’ pseudo-regret on the estimated losses.This reduction is the central analytical role of inequality (9).
3 Construction of a kernel in dimension 1
In one dimension, the paper constructs a simple kernel centered at the distribution mean that satisfies the required approximation and smoothness properties. With selected parameters, this yields an explicit pseudo-regret bound.
- Kernel construction: The one-dimensional kernel is centered at the mean μ of p and maps points to uniform distributions on segments toward μ.Near μ it uses the interval [μ−ε, μ], while farther points use the segment connecting the point to μ.
- Kernel properties: The adjoint of this kernel preserves 1-Lipschitzness on the relevant intervals, allowing L = 1 in the theorem’s smoothness condition.The construction has a small discontinuity that requires a minor proof adjustment.
- Kernel properties: Convexity and Jensen’s inequality establish the kernel approximation condition with λ = 1/2.The argument treats points near and far from the mean separately.
- Regret bound: With ε = 1/T^2, L = 1, λ = 1/2, and C = 2 log(eT^2), the construction gives the stated pseudo-regret upper bound.These parameters are substituted into the general kernel-based analysis.
4 The high-dimensional case
The high-dimensional construction uses a distribution-dependent kernel built from a Gaussian core, then controls estimation only inside a high-probability focus region. Truncation, restarts, and an increasing learning rate address the resulting localization problem.
- Kernel construction: The high-dimensional algorithm uses a kernel map K[p] based on the mean, covariance, approximate log-concavity, and Gaussian core of p.The construction mixes the Gaussian core with a draw from q using parameters ε and λ.
- Kernel construction: The kernel is not necessarily supported on K, creating a technical issue that the algorithm handles when sampling actions.Samples outside K are replaced by an arbitrary point in K.
- Kernel properties: For approximately log-concave distributions, the kernel approximately convexly dominates the Gaussian core and has useful smoothness properties after truncation.These are the key structural properties established for the high-dimensional kernel.
- Focus region: The loss estimator cannot be controlled over all of K, so the algorithm truncates it to a focus region containing most of the exponential-weights mass.Within the focus region, the estimator’s magnitude and variance are controlled; outside it, estimates are unreliable.
- Restarts and annealing: Restarts address the possibility that the optimum moves outside the focus region, while a multiplicatively increasing learning rate supports the negative-regret argument.When the focus-region test indicates a scale change, the learning rate is increased by a factor 1 + γ.
- Parameter choices: The parameter choices use α approximately n^2 log^2(T), γ approximately 1/(n log(T)), constant-order β, and a small kernel parameter λ.These choices keep most distributional mass in the focus ellipsoid and control the estimator magnitude.
5 Analysis of the high-dimensional algorithm
The analysis establishes approximate log-concavity, geometric control, concentration, and restart properties needed to prove the high-dimensional algorithm’s regret guarantee.
- Distributional invariant: The exponential-weights distributions p_t remain (1/e)-approximately log-concave throughout the algorithm.This invariant follows from the update structure and supports the subsequent geometric and concentration arguments.
- Restarts and regret: The restart analysis bounds the probability of restarting before time T by 2/T^2.Together with the restart decomposition and Proposition 1, this establishes the final high-probability regret analysis.
- Geometric control: The analysis bounds the focus region F_t inside an ellipsoid and lower-bounds its volume, yielding control of covariance and restart complexity.The volume bound also implies N ≤ Cn log T for the number of relevant scales.
- Loss regularity: The estimated losses are regular on F_t: they are bounded there and have controlled gradients under the algorithm’s parameter choices.These properties enable uniform concentration over the focus region.
- Concentration: The proof uses martingale differences and Azuma-Hoeffding concentration to control deviations of the loss estimates and related quantities.The concentration argument is combined with Lipschitz estimates to make the bounds hold over all relevant points in F_t.
6 Implementation
The implementation replaces expensive sampling, kernel, and restart computations with approximate procedures, obtaining polynomial-time variants with explicit regret–runtime trade-offs.
- Implementation challenges: The main implementation obstacles are sampling from p_t, computing the kernel, and testing the restart condition.The polynomial-time construction assumes K is a polytope with polynomially many constraints.
- Sampling p_t: Theorem 5 generates samples from p_t within total variation distance 1/T^κ in poly(n log(T))T time.The sampler relies on approximate log-concavity and an oracle for density ratios and membership testing.
- Modified kernel: A modified kernel avoids requiring the unknown centroid μ[p_t] by using a mixture of translated Gaussians whose centroid is exactly μ[p_t].This modification preserves the relevant convex-domination structure while enabling efficient sampling.
- Kernel sampling: Theorem 6 samples from K[p_t]p_t within total variation distance 1/T^κ in poly(n log(T))T time.The construction uses a single-sample modification of the loss estimator and an unbiased treatment of the normalization constant.
7 Technical lemmas
The technical lemmas provide concentration, tail, covariance, and convex-domination properties for approximately log-concave measures used throughout the algorithm’s analysis.
- Foundations: The technical development establishes foundational facts about approximately log-concave measures and Gaussian vectors.These results support later bounds on concentration, support, covariance, and tails.
- Density and covariance bounds: The lemmas compare approximately log-concave densities with log-concave references to derive bounds involving normalization constants and covariance determinants.These comparisons provide geometric control after normalization or affine transformation.
- Gaussian tails: Gaussian concentration controls the contribution of vectors outside the region ⟨x, Θ^-1x⟩ ≤ 20n log T.The corresponding tail estimates are used to bound truncated or smoothed quantities.
- One-dimensional consequences: One-dimensional marginal and tail arguments yield bounded-density and variance properties for isotropic approximately log-concave measures.The results apply to projections and support later control of translated or convolved kernels.
- Convex domination: A centered measure supported in a sufficiently small Euclidean ball is convexly dominated by an isotropic approximately log-concave measure.This is the technical relation used to compare the modified kernel with the target distribution.