Bandit Convex Optimization with Gradient Prediction Adaptivity

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.