Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan
Proceedings of the 31st Conference On Learning Theory, PMLR 75:3028-3064, 2018.

Abstract

We uncover a fairly general principle in online learning: If a regret inequality 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-foster18b, title = {Online Learning: Sufficient Statistics and the Burkholder Method}, author = {Foster, Dylan J. and Rakhlin, Alexander and Sridharan, Karthik}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {3028--3064}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/foster18b/foster18b.pdf}, url = {https://proceedings.mlr.press/v75/foster18b.html}, abstract = {We uncover a fairly general principle in online learning: If a regret inequality 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.} }
Endnote
%0 Conference Paper %T Online Learning: Sufficient Statistics and the Burkholder Method %A Dylan J. Foster %A Alexander Rakhlin %A Karthik Sridharan %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-foster18b %I PMLR %P 3028--3064 %U https://proceedings.mlr.press/v75/foster18b.html %V 75 %X We uncover a fairly general principle in online learning: If a regret inequality 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.
APA
Foster, D.J., Rakhlin, A. & Sridharan, K.. (2018). Online Learning: Sufficient Statistics and the Burkholder Method. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:3028-3064 Available from https://proceedings.mlr.press/v75/foster18b.html.

Related Material