Chaining

This chapter presents some foundational methods for bounding random processes. We begin with the chaining technique and prove the Dudley inequality, which bounds a random process using covering numbers. Applications include Monte Carlo integration and uniform bounds for empirical processes. We then develop VC (Vapnik– Chervonenkis) theory, offering combinatorial insights into random processes and applying it to statistical learning. Building on chaining, we introduce generic chaining to obtain optimal two-sided bounds using Talagrand’s g2 functional. A key consequence is the Talagrand comparison inequality, a generalization of the Sudakov–Fernique inequality for sub-Gaussian processes. This is used to derive the Chevet inequality, a powerful tool for analyzing random bilinear forms over general sets. Exercises explore the Lipschitz law of large numbers in higher dimensions, one-bit quantization, and the small ball method for heavy-tailed random matrices.