2021/02/02 by Adam Block, Block, Adam, Yuval Dagan +3 · 2 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Numerical Methods and Algorithms #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2102.01729
arxiv created 2021/02/02 · openalex publication_date 2021/02/02 · arxiv updated 2021/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.