Online Convex Optimization
A Game-Theoretic Approach to Learning

ICML 2016 Tutorial
Elad Hazan & Satyen Kale

June 2016


In recent years convex optimization and the notion of regret minimization in games have been combined and applied to machine learning in a general framework called online convex optimization. We will survey the basics of this framework, its applications, main algorithmic techniques and future research directions.


Slides for Part 1
Slides for Part 2

Bibliography: Books, Surveys and Research Papers

Textbooks and surveys:

Introduction to Online Convex Optimization E. Hazan
Online Learning and Online Convex Optimization S. Shalev-Shwartz
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems S. Bubeck and N. Cesa-Bianchi
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications S. Arora, E. Hazan and S. Kale
Statistical Learning and Sequential Prediction A. Rakhlin and K. Sridharan
The convex optimization approach to regret minimization E. Hazan

Research articles:

Online gradient descent, logarithmic regret and applications to soft-margin SVM:



Adaptive regularization and AdaGrad

Bandit Convex Optimization

Projection-free algorithms

Lower bounds

Relevant courses