## Is optimization computationally equivalent to online learning?

Elad Hazan

Princeton University

October 5, 2015

Vapnik's fundamental theorem of statistical learning establishes a computational equivalence between optimization (empirical risk minimization) and learning in the statistical setting. Is the same true for learning in games? We give a precise answer to this question.