arXiv cs.LG
· Papers
The Price of Hidden Curvature: An $widetilde{Omega} (d^{5/4} sqrt{T})$ Lower Bound for Bandit Convex Optimization
arXiv:2607.18652v1 Announce Type: 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