Introduction
Bandit Convex Optimization (BCO) is a fundamental framework for decision-making under uncertainty, generalizing many problems in online and statistical learning. In the standard Online Convex Optimization (OCO) setting, a learner repeatedly chooses a point in a decision set and suffers a loss, subsequently observing the entire loss function. However, in the more challenging Bandit setting, the learner only observes the loss value at the specific point they chose. This creates a classic exploration-exploitation dilemma: should the learner stick to points that performed well in the past, or explore new areas to find better options?
While optimal results for linear functions have been established, non-linear functions have historically been trickier. Previous algorithms for general convex functions hit a regret wall of $O(T^{3/4})$, and even for smooth or strongly-convex functions, the best bounds hovered around $\tilde{O}(T^{2/3})$. This paper closes a significant gap in BCO by introducing an efficient algorithm that achieves a near-optimal regret bound of $\tilde{O}(\sqrt{T})$ for strongly-convex and smooth loss functions.
Methodology: Shrinking Exploration and Dikin Ellipsoids
The authors introduce a novel algorithm specifically tailored for strongly-convex and smooth loss functions. The "secret sauce" of their approach is a "shrinking exploration" strategy, which leverages the geometry of self-concordant barriers to reduce the amount of random probing as the learner gains more information over time.
The approach combines several sophisticated tools:
- Self-Concordant Barriers: Used traditionally in interior-point methods to manage the boundaries of a decision set, these barriers act as regularization terms to ensure the learner stays within the "safe" interior of the set. By using these barriers, the algorithm "feels" the shape of the decision set, preventing illegal moves while maintaining high-quality gradient estimates.
- Dikin Ellipsoids: Instead of exploring by picking points from a simple sphere (which might push the learner outside the allowed set), the algorithm samples from an ellipsoid defined by the local geometry (the Hessian) of the barrier function.
- Shrinking Exploration: This is the core innovation. Previous BCO algorithms used a fixed exploration radius, which caused the $T^{2/3}$ bottleneck. Because the loss functions are strongly convex, the learner can afford to decrease the exploration magnitude over time. As $t$ increases, the "search area" around the current best guess shrinks at a rate of $1/\sqrt{t}$, balancing the error from gradient estimation with the cost of moving away from the optimal point.
- FTARL-$\sigma$: The algorithm feeds noisy gradient estimates into Follow The Approximately Regret Leader (FTARL), a variant of the FTRL meta-algorithm tuned to handle the curvature of strongly convex functions.
Key Results
The paper's theoretical guarantees are robust. The proposed algorithm achieves an expected regret of $\tilde{O}(\sqrt{T})$ over $T$ rounds. Crucially, a concurrent work (Shamir, 2013) proved a lower bound of $\Omega(\sqrt{T})$ for this exact setting. This demonstrates that the authors' algorithm is essentially tight and as good as any algorithm can possibly be, up to logarithmic factors. Furthermore, the algorithm is computationally efficient, relying on standard convex optimization primitives like gradient descent and Hessian calculations.
Limitations and Open Questions
As a theoretical work, the paper focuses on mathematical guarantees rather than empirical benchmarking. While the results are groundbreaking, they come with specific constraints:
- Specific Function Class: The $\sqrt{T}$ result strictly requires the functions to be both strongly convex and smooth. If the functions are only smooth or only strongly convex, the best known efficient bound remains $\tilde{O}(T^{2/3})$.
- The General Case: For general Lipschitz-continuous convex functions, the gap between the $O(T^{3/4})$ upper bound and the $\Omega(\sqrt{T})$ lower bound remains one of the biggest open questions in the field.
- High Dimensionality: While the rate is optimal in terms of time ($T$), the dependence on the dimension ($n$) and other parameters like the smoothness constant ($\beta$) could potentially be further optimized.
Summary updated