# A Second-Order Method for Stochastic Bandit Convex Optimisation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 10 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [(Bandit) Convex Optimization with Biased Noisy Gradient Oracles](https://mlsanity.com/paper/1609.07087/) (2016)
- [Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions](https://mlsanity.com/paper/1501.07242/) (2015)
- [Adaptive Bandit Convex Optimization with Heterogeneous Curvature](https://mlsanity.com/paper/2202.06150/) (2022)

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

- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [Second Order Methods for Bandit Optimization and Control](https://mlsanity.com/paper/2402.08929/) (2024)
- [Online Decision Deferral under Budget Constraints](https://mlsanity.com/paper/2409.20489/) (2024)
- [Tight Rates for Bandit Control Beyond Quadratics](https://mlsanity.com/paper/2410.00993/) (2024)
- [Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity](https://mlsanity.com/paper/2406.19617/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization](https://mlsanity.com/paper/2607.18652/) (2026)
- [CONGO: Compressive Online Gradient Optimization](https://mlsanity.com/paper/2407.06325/) (2024)
- [A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise](https://mlsanity.com/paper/2501.11127/) (2025)
- [Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension](https://mlsanity.com/paper/2607.12938/) (2026)

## Abstract (arXiv)

We introduce a simple and efficient algorithm for unconstrained zeroth-order stochastic convex bandits and prove its regret is at most (1 + r/d)[d1.5 √n + d3] polylog(n, d, r) where n is the horizon, d the dimension and r is the radius of a known ball containing the minimiser of the loss.