# Bandit Convex Optimization with Gradient Prediction Adaptivity

arXiv: https://arxiv.org/abs/2605.22191 · HTML: https://mlsanity.com/paper/2605.22191/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 20 of 20)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Taking a hint: How to leverage loss predictors in contextual bandits?](https://mlsanity.com/paper/2003.01922/) (2020)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [(Bandit) Convex Optimization with Biased Noisy Gradient Oracles](https://mlsanity.com/paper/1609.07087/) (2016)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Non-Stationary Bandit Convex Optimization: An Optimal Algorithm with Two-Point Feedback](https://mlsanity.com/paper/2508.04654/) (2025)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)

## Built on by (most cited first, 1 of 1)

- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)

## Abstract (arXiv)

Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions mt, we seek regret bounds that scale with the cumulative prediction error ST=sumt=1T |nabla ft(xt)-mt|2. We first establish a negative result: under the single-point feedback protocol, an unavoidable Omega(√T) regret lower bound persists even when ST=o(T), showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose Two-Point Variance-Reduced Optimistic Gradient Descent (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of Obig(√d,mathbbE[ST]big), where d is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as Omega(√mathbbE[ST]), providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of √ d. We further develop adaptive variants that eliminate the need for prior knowledge of mathbbE[ST] or the horizon T, and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.