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

Nived Rajaraman, Yanjun Han

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 ti…