# An optimal algorithm for bandit convex optimization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2016.

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

- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Online Decision Deferral under Budget Constraints](https://mlsanity.com/paper/2409.20489/) (2024)
- [Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization](https://mlsanity.com/paper/2102.07387/) (2021)
- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Adaptive Bandit Convex Optimization with Heterogeneous Curvature](https://mlsanity.com/paper/2202.06150/) (2022)
- [Online Ad Procurement in Non-stationary Autobidding Worlds](https://mlsanity.com/paper/2307.05698/) (2023)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Stochastic Direct Search Method for Blind Resource Allocation](https://mlsanity.com/paper/2210.05222/) (2022)
- [Online Convex Optimization with Memory and Limited Predictions](https://mlsanity.com/paper/2410.23574/) (2024)
- [Online Episodic Convex Reinforcement Learning](https://mlsanity.com/paper/2505.07303/) (2025)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)
- [Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization](https://mlsanity.com/paper/2608.16216/) (2026)

## Abstract (arXiv)

We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback, known as bandit convex optimization. We give the first tildeO(√T)-regret algorithm for this setting based on a novel application of the ellipsoid method to online learning. This bound is known to be tight up to logarithmic factors. Our analysis introduces new tools in discrete convex geometry.