2021-07-21-block21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Majorizing Measures, Sequential Complexities, and Online Learning	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	block21a	0	Majorizing Measures, Sequential Complexities, and Online Learning	587	590	587-590	587	false	Block, Adam and Dagan, Yuval and Rakhlin, Alexander	given family Adam Block given family Yuval Dagan given family Alexander Rakhlin	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/block21a/block21a.pdf