# Online Newton Method for Bandit Convex Optimisation

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

## Key facts

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

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

- [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)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)

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

- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Online Convex Optimization with Dueling Feedback](https://mlsanity.com/paper/2608.15050/) (2026)
- [A simple and improved algorithm for noisy, convex, zeroth-order optimisation](https://mlsanity.com/paper/2406.18672/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Harnessing Unimodality in Semiparametric Contextual Pricing via Oracle Price Map Learning](https://mlsanity.com/paper/2605.15411/) (2026)
- [The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization](https://mlsanity.com/paper/2607.18652/) (2026)
- [A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise](https://mlsanity.com/paper/2501.11127/) (2025)
- [Gradient-free stochastic optimization for additive models](https://mlsanity.com/paper/2503.02131/) (2025)
- [Online Episodic Convex Reinforcement Learning](https://mlsanity.com/paper/2505.07303/) (2025)
- [Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension](https://mlsanity.com/paper/2607.12938/) (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 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.