Relax and Randomize: A recipe for online learning algorithms

Опубликовано 28 июля 2016, 23:03

We show a principled way of deriving online learning algorithms from a minimax analysis. The framework yields algorithms for various upper bounds on the minimax value, that were previously only obtained in a non-constructive fashion. The framework allows us to seamlessly recover most of the known methods and to derive new and efficient online learning algorithms. We present a number of new algorithms, including a family of randomized methods that use the idea of a "random play out". Several new versions of the Follow-the-Perturbed-Leader algorithms are presented, as well as methods based on the Littlestone's dimension, efficient methods for matrix completion with trace norm and algorithms for the problems of transductive learning and prediction with static experts. Along with localized analysis the framework can also be used to provide adaptive online learning algorithms that can attain faster rates against more benign adversaries. Overall through the framework we emphasize that understanding the inherent complexity of the learning problem leads to the development of algorithms. Joint work with Alexander Rakhlin and Ohad Shamir