Relax and Randomize: A recipe for online learning algorithms

  • Karthik Sridharan | University of Pennsylvania

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

Speaker Details

Karthik Sridharan is currently a Post-Doctoral researcher at The Wharton School, Statistics Department, University of Pennsylvania. He received his PhD degree in computer science from Toyota Technological Institute at Chicago. His research interests include theoretical machine learning, convex optimization, empirical process theory and game theory

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks