# Majorizing Measures, Sequential Complexities, and Online Learning

arXiv: https://arxiv.org/abs/2102.01729 · HTML: https://mlsanity.com/paper/2102.01729/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 36 references that are in the map.
- First posted on arXiv 2 Feb 2021.

## Builds on (most cited first, 9 of 9)

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [On the Equivalence between Online and Private Learnability beyond Binary Classification](https://mlsanity.com/paper/2006.01980/) (2020)
- [Inference of High-dimensional Autoregressive Generalized Linear Models](https://mlsanity.com/paper/1605.02693/) (2016)

## Built on by (most cited first, 17 of 17)

- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learning](https://mlsanity.com/paper/2510.10981/) (2025)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation](https://mlsanity.com/paper/2606.07931/) (2026)
- [Why Agentic Theorem Prover Works: A Statistical Provability Theory of Mathematical Reasoning Models](https://mlsanity.com/paper/2602.10538/) (2026)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers](https://mlsanity.com/paper/2602.10512/) (2026)

## Abstract (arXiv)

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.