Timezone: »

 
Oral
Relax and Randomize : From Value to Algorithms
Sasha Rakhlin · Ohad Shamir · Karthik Sridharan

Tue Dec 04 11:20 AM -- 11:40 AM (PST) @ Harveys Convention Center Floor, CC
in Oral Session 2 »

We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones, also capturing such ''unorthodox'' methods as Follow the Perturbed Leader and the R^2 forecaster. Understanding the inherent complexity of the learning problem thus leads to the development of algorithms. To illustrate our approach, we present several new algorithms, including a family of randomized methods that use the idea of a ''random play out''. 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.

Author Information

Sasha Rakhlin (University of Pennsylvania)
Ohad Shamir (Weizmann Institute of Science)
Karthik Sridharan (University of Pennsylvania)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors