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

arXiv:2607.18652v2 Announce Type: replace-cross Abstract: We establish a widetildeOmega(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 dsqrt{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^star a^1 - frac{r}{8arepsilon} a^2 |_2 (hyperparameterized by arepsilon,r), and a squared distance function, frac12 | a^1 - u^star |_2^2 - frac12 | u^star |_2^2. Here, W^star in R^{d imes d} is an unknown linear transformation, and u^star in 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{8arepsilon}{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 widetilde{Omega}(d^{5/2}/arepsilon^2) to find an arepsilon-optimal action, which translates to an widetilde{Omega} (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.

Source: arXiv cs.LG | 2026-07-24