Optimistic Bandit Convex Optimization Scott Yang Courant Institute and Google Courant Institute 251 Mercer Street 251 Mercer Street New York, NY10012

We introduce the general and powerful scheme of predicting information re-use in optimization algorithms. This allows us to devise a computationally efficient algorithm for bandit convex optimization with new state-of-the-art guarantees for both Lipschitz loss functions and loss functions with Lipschitz gradients.