How to Predict When Estimation is Hard: Algorithms for Learning on Graphs

Tuesday, February 16, 2016 - 4:00pm to Wednesday, February 17, 2016 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Sasha Rakhlin


University of Pennsylvania

Building and Room number

32-G449 (please note special location!)


We consider the problem of predicting a binary label for an individual given the information about the person and her position within a network. Such a fusion of the two sources of information naturally arises in a variety of applications, including recommendation systems, ad placement, and personalized medical care.

When formalizing this problem, one faces a computationally intractable combinatorial objective. We present an unexpected phenomenon: it is possible to develop poly-time (and statistically near-optimal) online prediction methods even when the offline problem is provably hard. These prediction methods arise in a systematic way from a new relaxation framework that has roots in the work of Cover and Blackwell. The new applications to learning on graphs are based in part on multiplicative approximation algorithms developed by the theoretical computer science community. Our approach naturally extends to the contextual multi-armed bandit setting with large sets of policies -- a notoriously difficult problem, which is often encountered in real-world applications.

Joint work with K. Sridharan.


Alexander (Sasha) Rakhlin is an Associate Professor at the Department  of Statistics at the University of Pennsylvania. He received his bachelors degrees in Mathematics and Computer Science from Cornell
University, and a doctoral degree from MIT. He was a postdoc at UC Berkeley before joining UPenn. His research is in machine learning, with an emphasis on statistics and computation. Alexander is a recipient of the NSF CAREER award, IBM Research Best Paper award, Machine Learning Journal award, and COLT Best Paper Award.


This talk is jointly hosted with Theory of Computation.