Elad Hazan: Is Optimization Computationally Equivalent to Online Learning?

Abstract: 

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.

Joint work with Tomer Koren