At first glance, online learning and martingale inequalities do not appear to be related. 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 online learning algorithms, including an algorithm for matrix prediction that attains a regret bound corresponding to the variance term found in matrix concentration inequalities. We also discuss the prospect of automatically discovering Burkholder functions, thereby automating the design of online learning algorithms altogether.
.