# Minimax Regret for Bandit Convex Optimisation of Ridge Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 1 Jun 2021.

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

- [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)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [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)
- [Bandit Convex Optimization: sqrt{T} Regret in One Dimension](https://mlsanity.com/paper/1502.06398/) (2015)
- [Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization](https://mlsanity.com/paper/2102.07387/) (2021)

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

- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret](https://mlsanity.com/paper/2609.10981/) (2026)

## Abstract (arXiv)

We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form ft(x) = gt(langle x, θrangle) for convex gt : mathbb R → mathbb R and unknown θ ∈ mathbb Rd that is homogeneous over time. We provide a short information-theoretic proof that the minimax regret is at most O(d √n log(n operatornamediam(mathcal K))) where n is the number of interactions, d the dimension and operatornamediam(mathcal K) is the diameter of the constraint set.