level: research
researchers have found a new lower bound for stochastic bandit convex optimization. the bound is roughly d^{5/4} times the square root of t, where d is the dimension and t is the number of rounds. this is the first lower bound that grows faster than d sqrt(t) for this problem. it shows that optimizing convex functions with bandit feedback is harder than linear bandits, where the regret scales as d sqrt(t).
the proof uses a hard class of convex functions in 2d dimensions. each function combines a scaled soft maximum of a tube and a squared distance. the tube depends on an unknown linear transformation w and an unknown vector u. the construction forces any algorithm to suffer high regret because it must learn both w and u from only function value feedback.
this result settles a long-standing question about the true difficulty of bandit convex optimization. previous upper bounds suggested regret around d^{2.5} sqrt(t), but the best known lower bound was d sqrt(t). the new lower bound of d^{1.25} sqrt(t) narrows the gap. it implies that algorithms must account for hidden curvature in the loss functions, which makes the problem intrinsically harder than linear bandits.
why it matters: this lower bound guides algorithm design by showing that bandit convex optimization cannot match the efficiency of linear bandits, so practitioners should not expect simple methods to work well.