Online Learning, Probabilistic Inequalities, and the Burkholder Method
, Cornell University
Date: Wednesday, October 17, 2018
Time: 3:00 PM to 4:00 PM
Event Type: Seminar
Host: Akshay Degwekar, Pritish Kamath and Govind Ramnarayan, MIT CSAIL
Contact: Rebecca Yadegar, email@example.com
Speaker URL: None
TALK: Dylan Foster: Online Learning, Probabilistic Inequalities, and the Burkholder Method
Abstract: At first glance, online learning and martingale inequalities may not appear to be intrinically linked. We will showcase a recently discovered equivalence between existence of algorithms for online learning, martingale inequalities, and special "Burkholder" functions. Using this equivalence as a starting point, we define a notion of a sufficient statistic for online learning and use the Burkholder method---originally used to certify probabilistic martingale inequalities---to develop algorithms that only keep these sufficient statistics in memory. To demonstrate the power of the Burkholder method we introduce new efficient and adaptive algorithms for online learning, including an algorithm for matrix prediction that attains a regret bound corresponding to the variance term found in matrix concentration inequalities.
Algorithms & Theory
Created by Rebecca Yadegar at Thursday, September 27, 2018 at 1:37 PM.