Majorizing Measures, Sequential Complexities, and Online Learning

Adam Block, Yuval Dagan, Alexander Rakhlin
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:587-590, 2021.

Abstract

We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-block21a, title = {Majorizing Measures, Sequential Complexities, and Online Learning}, author = {Block, Adam and Dagan, Yuval and Rakhlin, Alexander}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {587--590}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/block21a/block21a.pdf}, url = {https://proceedings.mlr.press/v134/block21a.html}, abstract = {We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.} }
Endnote
%0 Conference Paper %T Majorizing Measures, Sequential Complexities, and Online Learning %A Adam Block %A Yuval Dagan %A Alexander Rakhlin %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-block21a %I PMLR %P 587--590 %U https://proceedings.mlr.press/v134/block21a.html %V 134 %X We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.
APA
Block, A., Dagan, Y. & Rakhlin, A.. (2021). Majorizing Measures, Sequential Complexities, and Online Learning. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:587-590 Available from https://proceedings.mlr.press/v134/block21a.html.

Related Material