🔢 mathematics

Bandit Convex Optimization with Gradient Prediction Adaptivity

This paper demonstrates that while optimistic gradient predictions cannot improve worst-case regret in single-point feedback bandit convex optimization due to inherent variance, a novel Two-Point Variance-Reduced Optimistic Gradient Descent algorithm achieves optimal prediction-adaptive regret bounds of $O(\sqrt{d\,\mathbb{E}[S_T]})$ in the two-point feedback setting, matching a fundamental information-theoretic lower bound.

Original authors: Shuche Wang, Adarsh Barik, Vincent Y. F. Tan

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shuche Wang, Adarsh Barik, Vincent Y. F. Tan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game where you have to guess the best move in a maze, but you can only see the score of the move you just made, not the map or the rules. This is the world of Bandit Convex Optimization (BCO). You are the "learner," and your goal is to make as few mistakes as possible over time compared to the best possible player who knew the whole map from the start.

In the past, researchers found that if you only get to see the score of one move per round (Single-Point Feedback), you are stuck with a certain amount of "regret" (mistakes) no matter how smart you are. It's like trying to find the exit in a dark room by bumping into one wall at a time; the randomness of your bumps makes it impossible to learn the layout quickly, even if you have a hunch about where the door is.

This paper asks a big question: What if we could give the player a "hint" or a "prediction" before they make a move? For example, "I think the gradient (the slope of the hill) will be pointing this way." Can we use these hints to get much better results, especially if the hints are usually right?

Here is the breakdown of their findings, using simple analogies:

1. The "One-Eye" Problem (Single-Point Feedback)

The authors first tested a scenario where the player gets a hint but can only check the score of one spot per turn.

The Result: They proved a "negative result." Even with perfect hints, if you can only peek at one spot, you are still stuck with a high level of mistakes.
The Analogy: Imagine trying to guess the temperature of a room by sticking your hand in one spot. Even if someone whispers, "It's getting hotter," your single hand measurement is so noisy (due to random air currents) that you can't tell if the room is actually changing or if you just moved your hand slightly. The "noise" drowns out the "hint."

2. The "Two-Eye" Solution (Two-Point Feedback)

To fix the noise problem, the authors looked at a scenario where the player can check two spots at once: one slightly to the left and one slightly to the right of their current position.

The Innovation: They created a new algorithm called TP-VR-OPT (Two-Point Variance-Reduced Optimistic Gradient Descent).
How it works: Instead of trying to guess the entire temperature of the room from scratch, the algorithm uses the "hint" as a baseline. It only tries to measure the difference between the hint and the actual two-point reading.
The Analogy: Think of the hint as a "zero point" on a scale. If the hint says "it's 20 degrees," and you measure two points, you don't need to measure the whole 20 degrees. You just measure how much the actual temperature deviates from 20. Because the deviation is usually small (if the hint is good), the "noise" in your measurement becomes tiny.
The Result: When the hints are accurate, the number of mistakes drops dramatically. The algorithm adapts: if the hints are great, it learns fast; if the hints are terrible, it falls back to a safe, standard performance.

3. The "Magic Mirror" (Lower Bounds)

The authors didn't just build a better car; they checked the speed limit of the road. They proved mathematically that their new algorithm is nearly the best possible thing you can do.

The Finding: You cannot do better than their algorithm by more than a tiny factor related to the size of the maze (the number of dimensions). They showed that the "noise" in the two-point measurement is the fundamental limit, and their algorithm squeezes out every drop of performance possible.

4. No "Crystal Ball" Needed (Adaptive Variants)

Usually, to make these algorithms work perfectly, you need to know the future: "How good will the hints be?" and "How long will the game last?"

The Fix: They built "Adaptive" versions (TP-VR-OPT+ and TP-VR-OPT++) that don't need to know the future.
The Analogy: Instead of setting a fixed speed limit for a race, these algorithms act like a smart cruise control. They start slow, and if they see the car is handling well (low error), they speed up. If they see the car wobbling (high error), they slow down. They figure out the right settings on the fly without needing a crystal ball.

5. The Moving Target (Dynamic Regret)

Finally, they looked at a harder version of the game where the "best move" keeps changing over time (like a moving target).

The Result: Their algorithm can track a moving target efficiently. It adapts not just to how good the hints are, but also to how fast the target is moving. If the target moves slowly, the algorithm is very efficient. If the target zips around wildly, it adjusts to keep up, balancing the cost of the hints against the cost of the target's movement.

Summary

In short, this paper says:

Hints alone aren't enough if your measurement tool is too noisy (Single-Point).
But if you measure two points at once, you can use the hints to cancel out the noise.
Their new algorithm does this perfectly, adapting to how good the hints are and how fast the environment changes, without needing to know the future.
They proved that you can't really do much better than this; they hit the theoretical speed limit for this type of problem.

Technical Summary: Bandit Convex Optimization with Gradient Prediction Adaptivity

1. Problem Statement

This work investigates Bandit Convex Optimization (BCO), a framework for sequential decision-making where the learner selects a decision point $x_t$ from a convex set $\mathcal{X} \subseteq \mathbb{R}^d$ and observes only the scalar loss $f_t(x_t)$ incurred at that point, rather than the full loss function or its gradient. The performance is measured by regret, defined as the cumulative difference between the learner's losses and the losses of the best fixed decision in hindsight (static regret) or a time-varying comparator sequence (dynamic regret).

The central question addressed is whether optimistic gradient predictions ( $m_t$ ), available before each round, can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, the authors seek regret bounds that scale with the cumulative prediction error $S_T = \sum_{t=1}^T \|\nabla f_t(x_t) - m_t\|^2$ (or its expectation $\bar{S}_T$ ) rather than solely with the time horizon $T$ . The work assumes the loss functions are convex, Lipschitz continuous, and smooth ( $\beta$ -smooth), a necessary condition for the proposed adaptivity.

2. Methodology and Key Findings

A. The Single-Point Feedback Barrier

The authors first establish a fundamental limitation under the single-point feedback protocol (where only $f_t(x_t)$ is observed).

Negative Result: They prove an information-theoretic lower bound of $\Omega(\sqrt{T})$ for the expected regret, even when the cumulative prediction error is negligible ( $\bar{S}_T = o(T)$ ).
Mechanism: The proof constructs a hard instance using linear losses with additive Gaussian noise. In single-point feedback, the learner observes absolute function values, which mix the local first-order signal (gradient) with zero-order offsets. This noise prevents the learner from distinguishing between different gradient directions, rendering accurate predictions ineffective for reducing variance. Consequently, the variance of the gradient estimator fundamentally obscures the benefit of predictions in this setting.

B. Two-Point Feedback and Variance Reduction

To overcome the single-point barrier, the paper focuses on the two-point feedback protocol, where the learner observes $f_t(y_t + \delta v_t)$ and $f_t(y_t - \delta v_t)$ for a center point $y_t$ and random direction $v_t$ .

Algorithm (TP-VR-OPT): The authors propose Two-Point Variance-Reduced Optimistic Gradient Descent.
- Core Innovation: Instead of estimating the full gradient $\nabla f_t(x_t)$ directly, the algorithm uses the prediction $m_t$ as a baseline. It constructs an estimator for the residual $\nabla f_t(x_t) - m_t$ .
- Estimator: $\hat{g}_t = m_t + \frac{d}{2\delta} \Delta_t v_t$ , where $\Delta_t = f_t(y_t + \delta v_t) - f_t(y_t - \delta v_t) - 2\delta \langle m_t, v_t \rangle$ .
- Variance Control: By centering the estimator on the prediction, the variance of the estimator scales with the prediction error $\|\nabla f_t(x_t) - m_t\|^2$ rather than the full gradient norm. This allows the algorithm to exploit accurate predictions to reduce regret.
Regret Bound: With oracle-tuned parameters, TP-VR-OPT achieves an expected static regret of $O(D\sqrt{d \bar{S}_T})$ , where $D$ is the diameter of $\mathcal{X}$ . This improves upon the standard $O(\sqrt{T})$ bound when predictions are accurate.

C. Information-Theoretic Optimality

The authors establish a lower bound showing that no algorithm (even with full-information feedback) can achieve a regret scaling better than $\Omega(D\sqrt{\bar{S}_T})$ in terms of the prediction error. This confirms that the $O(\sqrt{d \bar{S}_T})$ upper bound of TP-VR-OPT is optimal up to a factor of $\sqrt{d}$ .

D. Adaptive Implementation (TP-VR-OPT+)

Since the optimal parameters for TP-VR-OPT depend on the unknown $\bar{S}_T$ and horizon $T$ , the authors propose TP-VR-OPT+.

Mechanism: This variant uses a nested doubling-trick approach. It maintains a time budget and a "sensitivity budget" (a guess for the prediction error). The algorithm doubles these budgets whenever the observable residual $\sum \|\hat{g}_t - m_t\|^2$ exceeds a threshold.
Result: TP-VR-OPT+ achieves a regret bound of $\tilde{O}(D\sqrt{d \bar{S}_T})$ without requiring prior knowledge of $\bar{S}_T$ or $T$ .

E. Dynamic Regret in Non-Stationary Environments

The framework is extended to dynamic regret, where the comparator is a sequence $\{u_t\}$ with path length $P_T = \sum \|u_t - u_{t-1}\|$ .

Algorithm (TP-VR-OPT++): This variant combines the adaptive doubling strategy with a Meta-Expert framework. It maintains a grid of experts with different step sizes to adapt to the unknown path length $P_T$ .
Result: TP-VR-OPT++ achieves a dynamic regret bound of $\tilde{O}(\sqrt{d \bar{S}_T (D^2 + D P_T)})$ , adapting simultaneously to the cumulative prediction error and the comparator's path length.

3. Key Contributions

Single-Point Barrier: Proved that prediction adaptivity is impossible under single-point feedback due to an inherent $\Omega(\sqrt{T})$ lower bound caused by observational noise, regardless of prediction accuracy.
Variance-Reduced Estimator: Designed a novel gradient estimator for two-point feedback that leverages predictions to reduce variance, scaling with the prediction error rather than the gradient norm.
Optimal Adaptive Bounds: Established $O(\sqrt{d \bar{S}_T})$ static regret and $\tilde{O}(\sqrt{d \bar{S}_T (D^2 + D P_T)})$ dynamic regret, matching information-theoretic lower bounds up to dimension factors.
Parameter-Free Algorithms: Developed fully adaptive variants (TP-VR-OPT+ and TP-VR-OPT++) that do not require knowledge of the prediction error or time horizon.
Generalization: Showed that the proposed framework generalizes previous results on "gradually evolving worlds" (gradient variation bounds) as a special case.

4. Significance and Claims

The paper claims to resolve the fundamental question of whether prediction-based adaptivity can be extended from full-information to bandit convex optimization.

Fundamental Insight: The work demonstrates that the feasibility of prediction adaptivity in BCO is not merely an algorithmic challenge but depends critically on the feedback protocol. The single-point protocol inherently masks the benefits of predictions due to variance, while the two-point protocol allows for variance reduction.
Optimality: The results provide a fundamental characterization of the best achievable regret in prediction-adaptive BCO, showing that the dependence on the prediction error is unavoidable and that the proposed algorithms are optimal up to a dimension factor.
Practicality: By removing the need for prior knowledge of the environment's complexity (prediction error or path length), the proposed algorithms are presented as practically applicable solutions for non-stationary environments.

The authors note that future work could explore whether predictions can interpolate between the $O(T^{2/3})$ rate for smooth losses and the $\Omega(\sqrt{T})$ floor in single-point feedback, or extend these results to strongly convex settings.