mlsanityData to 7 Oct 2026

Online Newton Method for Bandit Convex Optimisation

arXiv 2406.06506 ↗First posted 10 Jun 2024math.OC cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most d3.5 √n polylog(n, d) with high probability where d is the dimension and n is the time horizon. In the stochastic setting the bound improves to M d2 √n polylog(n, d) where M ∈ [d-1/2, d-1 / 4] is a constant that depends on the geometry of the constraint set and the desired computational properties.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 7 of its 30 references that are in the map. First posted on arXiv 10 Jun 2024.

Builds on

7 of 30 references.

References · 7

  1. 2016Kernel-based methods for bandit convex optimizationcited by 63
  2. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  3. 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
  4. 2021Efficient Projection-Free Online Convex Optimization with Membership Oraclecited by 29
  5. 2016An optimal algorithm for bandit convex optimizationcited by 20
  6. 2024Bandit Convex Optimisationcited by 18
  7. 2023A Second-Order Method for Stochastic Bandit Convex Optimisationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 5.

11 papers.

  1. 2024Online Convex Optimization with a Separation Oraclecited by 7
  2. 2026Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variationscited by 5
  3. 2024A simple and improved algorithm for noisy, convex, zeroth-order optimisationcited by 1
  4. 2025Non-stationary Bandit Convex Optimization: A Comprehensive Studycited by 1
  5. 2026The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimizationcited by 1
  6. 2026Online Convex Optimization with Dueling Feedbackcited by 1
  7. 2025A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noisecited by 0
  8. 2025Gradient-free stochastic optimization for additive modelscited by 0
  9. 2025Online Episodic Convex Reinforcement Learningcited by 0
  10. 2026Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimensioncited by 0
  11. 2026Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimizationcited by 0