The Price of Hidden Curvature: An (d 5/4 sqrt T) Lower Bound for Bandit Convex Optimization

We establish a (d 5/4 sqrt T) lower bound on the minimax expected regret of stochastic bandit convex optimization of 1-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than d sqrt T for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension 2d: for an action a = (a 1,a 2) in B 2d 2, each function is the scaled soft maximum of a "tube", r-1 W a 1 - r over 8 epsilon a squared 2 (hyperparameterized by epsilon,r), and a squared distance function, 12 a 1 - u 2 squared - 12 u 2 squared. Here, W in R d times d is an unknown linear transformation, and u in R d is an unknown vector which must be learned to minimize the function. Observations are informative about u only when the learner's action lies near the tube determined by W, satisfying a squared about 8 epsilon over r W a 1: thus the learner must either find this tube without knowing W, or spend observations learning useful directions of W. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of (d 5/2/epsilon 2) to find an epsilon-optimal action, which translates to an (d 5/4 sqrt T) regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is R d.