skip to main content

Keller Colloquium in Computing and Mathematical Sciences

Monday, April 9, 2018
4:00pm to 5:00pm
Add to Cal
Annenberg 105
Sufficient Statistics for Online Prediction via the Burkholder Method
Associate Professor Alexander (Sasha) Rakhlin, Center for Statistics, IDSS Department of Brain & Cognitive Sciences Laboratory for Information & Decision Systems Center for Brains, Minds, and Machines., Massachusetts Institute of Technology,

Martingale inequalities and bounds for online prediction methods have one thing in common: they are often proved using a "dynamic programming" approach. In this talk, we discuss a surprising equivalence between existence of online prediction algorithms, validity of certain martingale inequalities, and existence of special Burkholder functions. Building on these connections, we define a notion of a sufficient statistic for online methods and exhibit algorithms that only keep these sufficient statistics in memory. We demonstrate the power of the approach by deriving a new algorithm for matrix completion, as well as several other problems. In particular, concentration inequalities for matrix-valued martingales suggest a sufficient statistic that an online procedure should keep track of; we then find the corresponding Burkholder function and exhibit an efficient algorithm that significantly improves upon the standard adaptive-gradient-descent approach.

Joint work with Dylan Foster and Karthik Sridharan

For more information, please contact Carmen Nemer-Sirois by phone at (626) 395-4561 or by email at [email protected].