Source-linked AI summary
Stochastic convex optimization with bandit feedback
Alekh Agarwal, Dean P. Foster, Daniel Hsu, Sham M. Kakade, Alexander Rakhlin
TL;DR
The paper studies how to minimize convex Lipschitz functions over compact convex domains using noisy function-value queries while controlling cumulative regret. It combines a zeroth-order method with a center-point device and a modified ellipsoid algorithm. The resulting guarantee has near-square-root dependence on T, with dimension-polynomial and logarithmic factors, while dimension dependence remains large.
Problem
The problem is minimizing a convex Lipschitz function over a compact convex set under stochastic bandit feedback, where queries return noisy function values and regret is cumulative excess cost.
Method
The method combines a zeroth-order convex optimization procedure with a center-point device and a modification of the classical ellipsoid algorithm.
Results
˜O(poly(d)√T) regret is achieved with high probability for convex Lipschitz mean cost functions, with optimal T-scaling up to dimension-polynomial and logarithmic factors.
Takeaways & Limitations
The center-point device helps control regret by detecting costly or non-flat regions during the sequence of queries.
Takeaways & Limitations
The guarantee has a rather large dependence on dimension, and improving this dependence in the noisy setting remains an open research question.
Abstract
from arXiv · showhide
This paper addresses the problem of minimizing a convex, Lipschitz function $f$ over a convex, compact set $\xset$ 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 \in \xset$. The quantity of interest is the regret of the algorithm, which is the sum of the function values at algorithm's query points minus the optimal function value. We demonstrate a generalization of the ellipsoid algorithm that incurs $\otil(\poly(d)\sqrt{T})$ regret. Since any algorithm has regret at least $Ω(\sqrt{T})$ on this problem, our algorithm is optimal in terms of the scaling with $T$.
1 Introduction
The paper studies stochastic bandit optimization of convex Lipschitz functions and asks how convexity can improve regret guarantees. It proposes an algorithm achieving near-square-root regret, optimal in T up to dimension-polynomial and logarithmic factors.
- Motivation: The central question is how to leverage convexity of the mean cost function as a structural assumption in bandit optimization.
- Main result: The algorithm achieves ˜O(poly(d)√T) regret with high probability for all convex Lipschitz mean cost functions.
- Main result: The regret rate is optimal in T up to factors polynomial in d and logarithmic in T, matching the Ω(√T) lower-bound scaling.
- Scope: The stochastic setting assumes independently sampled noisy costs, unlike the adversarial setting where costs may change arbitrarily across rounds.Adversarial bandit optimization is outside this paper’s goal.
- Problem setup: The problem minimizes a convex Lipschitz mean cost function over a compact convex set using noisy function-value queries.Each query incurs the function cost, and regret compares cumulative queried costs with the optimum.
2 Related work
Prior work spans stochastic derivative-free optimization, unimodal and non-convex bandits, adversarial convex bandits, and oracle-based convex optimization. The paper emphasizes that optimization guarantees do not automatically provide low regret, which requires controlling costs throughout the sequence of queries.
- Stochastic bandits: Earlier ˜O(√T) regret results for unimodal functions required smoothness, strong convexity, and an interior unconstrained optimum.
- Stochastic bandits: Other bandit results address one-dimensional non-convex or graph-structured unimodal settings and may not exploit convexity.
- Stochastic bandits: Lipschitz X-armed bandit methods can achieve dimension-dependent rates in special near-optimality settings, but their constants may grow exponentially with dimension.
- Adversarial bandits: For adversarial convex bandits, one-point gradient estimators have best-known regret O(T^3/4), while two evaluations per round do not directly transfer to stochastic noise.
- Optimization versus regret: In noisy zeroth-order convex optimization, producing an ε-minimizer does not necessarily bound regret because exploratory queries may remain far from the minimum.Small regret implies an optimization guarantee by averaging, but the converse need not hold.
3 Outline of our approach
The approach combines zeroth-order convex optimization with a center-point device and a modified ellipsoid method. The center point detects costly or non-flat regions while supporting decisions about which parts of the domain to discard.
- Design choice: The paper chooses a zeroth-order approach that avoids estimating first-order information from noisy function values.
- Center-point device: A center-point device detects when the optimization method may be incurring high regret and triggers an appropriate response.
- Algorithm: The construction is first developed for one-dimensional convex optimization and then extended to higher dimensions.
- Algorithm: The device is fused with a modification of the classical ellipsoid algorithm to obtain an anytime regret-controlled method.
- Center-point device: Sampling the center between two points distinguishes a flat or linear region from a quadratic dip and enables discarding regions based on observed relative values.
4 One-dimensional case
The one-dimensional algorithm maintains a feasible interval, queries three equally spaced points with shrinking confidence intervals, and either discards a provably suboptimal quartile or certifies low regret. Its analysis preserves near-optimal points and yields a high-probability regret bound, with adaptive-to-T implementation available by doubling.
- Algorithm structure: The algorithm runs in epochs over a working interval and queries its left, center, and right quartiles.Each epoch begins with xl, xc, and xr equally spaced within the current feasible region.
- Case 1: Case 1 uses separated endpoint confidence intervals to discard a quarter of the working region containing no near-optimal points.The discarded portion lies either left of xl or right of xr, depending on which endpoint has the larger lower confidence bound.
- Case 2: Case 2 compares the center confidence interval with an endpoint and discards a quartile when that interval is sufficiently lower.Convexity then identifies a quartile containing no near-optimal points.
- Case 3: Case 3 treats the function as sufficiently flat when earlier separations fail, continuing with more queries and smaller confidence intervals.The confidence width γi is halved each round, allowing the algorithm to resolve function-value differences while controlling regret.
- Guarantee: With probability at least 1 − 1/T, Algorithm 1 satisfies the theorem’s regret bound for convex, 1-Lipschitz functions with i.i.d. σ-subgaussian noise.The algorithm can be made adaptive to an unknown T by a standard doubling argument.
- Analysis: Every epoch reduction retains all points within γi of the optimum, while a continuing round incurs at most 72σ log T γi regret.The analysis conditions on simultaneous confidence-interval coverage and combines per-epoch regret with a bound on the number of epochs.
5 Algorithm for optimization in higher dimensions
The higher-dimensional algorithm combines a pyramid-based geometric construction with confidence intervals and center-point reasoning to discard regions while retaining an approximate optimum. It operates in epochs and rounds, progressively refining estimates and updating enclosing ellipsoids.
- Algorithmic idea: The algorithm combines Nemirovski–Yudin’s pyramid construction with a center-point device to explore directions using polynomially many pyramids while targeting low regret.The pyramid sequence captures variation in multiple directions, while the center-point device supports the low-regret analysis.
- Epoch structure: Each epoch maintains a feasible region containing an approximate optimum, then discards part of that region while preserving at least one approximate optimum.The region is rounded between inner and outer balls before the epoch’s geometric and sampling steps begin.
- Initialization and sampling: At each round, the algorithm samples the vertices of a regular simplex inside the inner ball until their confidence intervals shrink to γi, then selects the vertex with the largest lower confidence bound.The round precision is γi = 2^-i, so successive rounds use progressively smaller confidence targets.
- Pyramid updates: For each pyramid, the algorithm repeatedly queries the apex, center, and base vertices, using confidence-interval comparisons among top, bottom, apex, and center to choose its next operation.The possible operations include advancing to a new pyramid, halving the confidence width, cone-cutting, or hat-raising.
- Geometric reduction: Cone-cutting replaces the current enclosing ball with a minimum-volume ellipsoid containing the ball after removing a cone, then intersects the feasible region with that ellipsoid.Hat-raising first moves the apex away from the pyramid center while preserving the base, after which cone-cutting is applied.
- Decision cases: When confidence intervals indicate that the function is sufficiently flat, the algorithm halves bγ or advances to the next round; other orderings terminate the epoch through cone-cutting or hat-raising.The case structure uses separations between top and bottom, top and apex, or center and bottom confidence intervals.
6 Analysis
The analysis establishes correctness of the pyramid-based elimination steps and combines per-round, per-epoch, and epoch-count bounds into a high-probability regret guarantee. The guarantee is optimal in T, while its polynomial dependence on d remains large.
- Correctness and confidence: Under event E, all sampled function values lie within their confidence intervals, enabling the subsequent correctness and regret analysis.The failure probability is bounded by P(E^c) ≤ 1/T.
- Correctness and confidence: Lemma 5 shows that every point discarded through Case (1b) has regret at least γ_i relative to the lowest confidence interval of the final pyramid.The proof uses convexity and the geometric relation between the pyramid apex, base, and discarded cone.
- Correctness and confidence: Hat-raising preserves approximate optima while ensuring points in the newly discarded cone have regret at least γ_i.This conclusion relies on the apex-distance assumption and the convexity-based comparison among the old apex, new apex, center, and cone points.
- Final guarantee: Theorem 2 gives a high-probability regret bound with optimal dependence on T, but the dependence on dimension d is polynomial and remains an open improvement target.A doubling argument removes the need for prior knowledge of T; improving the d dependence is identified as future work.
- Regret decomposition: Lemma 7 bounds regret from sampling a pyramid by poly(d)/bγ, while round-level analysis yields a C/γ bound when confidence widths shrink geometrically.The center-point evaluation is critical for controlling pyramid regret; the geometric schedule then bounds cumulative epoch regret.
- Regret decomposition: The enclosing-ball volume contracts by ρ = exp(−1/(4(d+1))), yielding a bound on the number of epochs and supporting the final high-probability regret theorem.The theorem analysis combines the epoch regret bound, epoch-count bound, and P(E^c) ≤ 1/T.
7 Discussion
The paper extends noisy zeroth-order convex optimization to guarantee low regret for queried points. Its regret has optimal T-scaling up to logarithmic factors, but retains substantial dimension dependence.
- 7 Discussion: The algorithm extends Nemirovski and Yudin’s zeroth-order method to noisy function evaluations while guaranteeing low regret on queried points.It relies on a center-point device that distinguishes regret minimization from an optimization guarantee.
- 7 Discussion: O(√T) regret scaling up to logarithmic factors is optimal in T.The paper states that the guarantee is optimal with respect to T-scaling.
- 7 Discussion: The regret guarantee has a rather large dimension dependence, inherited from the underlying method’s dimension dependence.The paper notes this dependence is unsurprising because the Nemirovski–Yudin algorithm already has large dimension dependence in the noiseless case.
A Properties of pyramid constructions
The appendix characterizes the geometry of recursively constructed pyramids inside an epoch ball. It gives explicit distances, heights, and an interior-ball relation used in the construction’s analysis.
- A Properties of pyramid constructions: At epoch τ, the initial simplex lies inside B(rτ), where rτ = Rτ/(c1d).The pyramid construction is therefore parameterized by the epoch-specific enclosing-ball radius.
- A Properties of pyramid constructions: Lemma 15 gives the apex distance, apex-to-base-vertex distance, and pyramid height for the k-th pyramid in epoch τ.The three quantities are rτ sin^(k−1)(ϕ), rτ sin^(k−1)(ϕ) cos(ϕ), and rτ sin^(k−1)(ϕ) cos^2(ϕ), respectively.
- A Properties of pyramid constructions: These geometric identities are proved by induction because each new apex is a vertex on the preceding pyramid’s base.The base case follows from similar triangles, and the inductive step rescales the distances.
- A Properties of pyramid constructions: For a pyramid with apex distance at least rτ/d, the largest ball centered at its center of mass supports an interior geometric bound.The appendix introduces this ball as BΠ and studies its radius through distances to the pyramid’s faces.