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

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.