mlsanityData to 7 Oct 2026

Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation

arXiv 2006.00475 ↗First posted 31 May 2020math.OC cs.LG stat.MLcited by 33

Not on the map. Why?

Abstract (arXiv)

We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most O(d2.5 √n log(n)), where d is the dimension and n is the number of interactions. This improves on O(d9.5 √n log(n)7.5 by Bubeck et al. (2017). The proof is based on identifying an improved exploratory distribution for convex functions.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 6; 2023: 7; 2024: 5; 2025: 3; 2026: 7.

33 papers.

Sort:

  1. 2021How to Learn when Data Reacts to Your Model: Performative Gradient Descentcited by 70
  2. 2022On the Complexity of Adversarial Decision Makingcited by 32
  3. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  4. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  5. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  6. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  7. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 11
  8. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  9. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11
  10. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  11. 2024Online Newton Method for Bandit Convex Optimisationcited by 11
  12. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
21 more
  1. 2023A Second-Order Method for Stochastic Bandit Convex Optimisationcited by 10
  2. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  3. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  4. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5
  5. 2021Minimax Regret for Bandit Convex Optimisation of Ridge Functionscited by 3
  6. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  7. 2022Adaptive Bandit Convex Optimization with Heterogeneous Curvaturecited by 2
  8. 2022A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimizationcited by 2
  9. 2023Infinite Action Contextual Bandits with Reusable Data Exhaustcited by 2
  10. 2025Adversarial bandit optimization for approximately linear functionscited by 2
  11. 2024A simple and improved algorithm for noisy, convex, zeroth-order optimisationcited by 1
  12. 2025Non-stationary Bandit Convex Optimization: A Comprehensive Studycited by 1
  13. 2026Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Lossescited by 1
  14. 2026Bandit Convex Optimization with Gradient Prediction Adaptivitycited by 1
  15. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1
  16. 2026The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimizationcited by 1
  17. 2023Bandit Convex Optimisation Revisited: FTRL Achieves tildeO(t1/2) Regretcited by 0
  18. 2024CONGO: Compressive Online Gradient Optimizationcited by 0
  19. 2025A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noisecited by 0
  20. 2026Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimizationcited by 0
  21. 2026Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regretcited by 0