Online Learning: Sufficient Statistics and the Burkholder Method
This work provides a general principle for designing memory-efficient online learning algorithms, which is incremental but offers practical improvements for applications like matrix prediction and supervised learning.
The paper tackles the problem of online learning by showing that if regret can be expressed via sufficient statistics, a Burkholder function enables algorithmic regret bounds with memory efficiency. It demonstrates this with a matrix prediction strategy achieving a regret bound tied to matrix concentration variance and a linear-time/space strategy for parameter-free supervised learning.
We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function that 1) can be used algorithmically to achieve the regret bound and 2) only depends on these sufficient statistics, not the entire data sequence, so that the online strategy is only required to keep the sufficient statistics in memory. This characterization is achieved by bringing the full power of the Burkholder Method --- originally developed for certifying probabilistic martingale inequalities --- to bear on the online learning setting. To demonstrate the scope and effectiveness of the Burkholder method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We also present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms.