The Price of Hidden Curvature: An $\tilde{\Omega }(d^5/4\text{sqrtT})$ Lower Bound for Bandit Convex Optimization

Abstract

We establish a $\tilde{\Omega }(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 {\mathbb{B}}_2^{2d}$, each function is the scaled soft maximum of a "tube", $r^{-1}\Vert W^{\star }{a}^1-\frac{r}{8\epsilon }{a}^2{\Vert }_2$ (hyperparameterized by $\epsilon ,r$), and a squared distance function, $\frac{1}{2}\Vert a^1-u^{\star }{\Vert }_2^2-\frac{1}{2}\Vert u^{\star }{\Vert }_2^2$. Here, $W^{\star }\in {\mathbb{R}}^{d\times d}$ is an unknown linear transformation, and $u^{\star }\in {\mathbb{R}}^d$ is an unknown vector which must be learned to minimize the function. Observations are informative about $u^{\star }$ only when the learner's action lies near the tube determined by $W^{\star }$, satisfying $a^2\approx \frac{8\epsilon }{r}{W}^{\star }{a}^1$: thus the learner must either find this tube without knowing $W^{\star }$, or spend observations learning useful directions of $W^{\star }$. 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 $\tilde{\Omega }(d^{5/2}/{\epsilon }^2)$ to find an $\epsilon$-optimal action, which translates to an $\tilde{\Omega }(d^{5/4}\sqrt{T})$ regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is ${\mathbb{R}}^d$.