Online Learning, Probabilistic Inequalities, and the Burkholder Method

Speaker: Dylan Foster , Cornell University

Date: Wednesday, October 17, 2018

Time: 3:00 PM to 4:00 PM

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description:

Host: Akshay Degwekar, Pritish Kamath and Govind Ramnarayan, MIT CSAIL

Contact: Rebecca Yadegar,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: 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.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms & Complexity Seminars 2018-2019.

Created by Rebecca Yadegar Email at Thursday, September 27, 2018 at 1:37 PM.