mlsanityData to 14 Oct 2026

An optimal algorithm for bandit convex optimization

arXiv 1603.04350 ↗First posted 14 Mar 2016cs.LG cs.DScited by 20

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 4; 2023: 3; 2024: 4; 2025: 1; 2026: 4.

20 papers.

Sort:

By area:

  1. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  2. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  3. 2024Online Newton Method for Bandit Convex Optimisationcited by 12
  4. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  5. 2023A Second-Order Method for Stochastic Bandit Convex Optimisationcited by 10
  6. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  7. 2022Online Convex Optimization with Unbounded Memorycited by 6
  8. 2023A Certified Radius-Guided Attack Framework to Image Segmentation Modelscited by 5
  9. 2024Online Decision Deferral under Budget Constraintscited by 5
  10. 2021Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimizationcited by 3
  11. 2021Minimax Regret for Bandit Convex Optimisation of Ridge Functionscited by 3
  12. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
8 more
  1. 2022Adaptive Bandit Convex Optimization with Heterogeneous Curvaturecited by 2
  2. 2023Online Ad Procurement in Non-stationary Autobidding Worldscited by 1
  3. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1
  4. 2022Stochastic Direct Search Method for Blind Resource Allocationcited by 0
  5. 2024Online Convex Optimization with Memory and Limited Predictionscited by 0
  6. 2025Online Episodic Convex Reinforcement Learningcited by 0
  7. 2026SCaLE: Switching Cost aware Learning and Explorationcited by 0
  8. 2026Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimizationcited by 0