An optimal algorithm for bandit convex optimization
arXiv:1603.04350v254 citations
Originality Highly original
AI Analysis
This solves a fundamental online learning problem with bandit feedback, providing optimal regret bounds for convex optimization.
The paper tackles the bandit convex optimization problem against arbitrary adversaries and presents the first algorithm achieving $ ilde{O}(\sqrt{T})$-regret, which is tight up to logarithmic factors.
We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback, known as bandit convex optimization. We give the first $\tilde{O}(\sqrt{T})$-regret algorithm for this setting based on a novel application of the ellipsoid method to online learning. This bound is known to be tight up to logarithmic factors. Our analysis introduces new tools in discrete convex geometry.