# The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 21 references that are in the map.
- First posted on arXiv 21 Jul 2026.

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

- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)

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

- [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 establish improved lower bounds on the minimax expected regret of stochastic bandit convex optimization for 1-Lipschitz functions on the d-dimensional Euclidean ball. For time horizons n≥ d10/3, we prove a lower bound of Omega(d4/3√n), the first nontrivial bound that exceeds the d√n dependence of linear bandits, showing that stochastic bandit convex optimization is fundamentally harder than linear bandits. For d2≤ n≤ d10/3, we obtain a lower bound of Omega(√dn3/4), matching the regret of the algorithm of Flaxman et al. (2005), establishing its optimality in this regime. The hard class of convex functions we construct takes the following form in dimension 2d: for an action a=(a1,a2)∈ mathbbB2d, each function is the scaled soft maximum of a "tube", r-1|W^star a1-fracr8varepsilona2 | (hyperparameterized by varepsilon,r), and a squared distance function, frac12|a1-u^star|2-frac12|u^star|2. Here u^star∈ℝd is the unknown target determining the minimizer, while W^star∈ℝd× d hides the region in which the quadratic curvature is observable. Indeed, observations reveal substantial information about u^star only when the learner acts near the hidden tube a2≈ frac8varepsilonrW^star a1; away from it, the tube branch masks the quadratic branch. Thus the learner must pay to uncover the geometry encoded by W^star before it can effectively exploit the curvature that identifies u^star. Formalizing this tradeoff yields a sample complexity lower bound of Omega(fracd5/2varepsilon2wedgefracd2varepsilon4) for finding an varepsilon-optimal action, and ultimately the Omega(d4/3√nwedge√dn3/4) regret lower bound. The proof was developed by GPT-5.5 Pro and GPT-5.6 Sol Pro under the authors' guidance.