generic chaining and majorizing measures

Generic chaining is the technology for bounding the supremum of a random process — the largest fluctuation over a whole continuum of correlated random variables. This is the central difficulty of empirical-process theory: a single random variable concentrates easily, but the supremum over an infinite index set can be much larger, and how much larger is governed by the geometry of the index set as seen through the process's own metric. Generic chaining, and Talagrand's majorizing-measure theorem, give the SHARP answer where the classical Dudley entropy integral gives only an upper bound.

Let (X_t) for t in a set T be a process with sub-Gaussian increments: ||X_s - X_t||_psi2 <= d(s, t) for a metric d on T. We want to bound E[sup_t X_t]. The chaining idea is to approximate each t by a sequence of successively finer nets, t_0, t_1, t_2, ..., where the n-th net has at most 2^(2^n) points, and write X_t - X_{t_0} as a telescoping sum sum_n (X_{t_n} - X_{t_{n-1}}) of increments between consecutive approximations. Each increment is sub-Gaussian with scale d(t_n, t_{n-1}), and there are few enough points at each level that a union bound over the increments at level n costs only sqrt(2^n) in the exponent. Summing the contributions gives Talagrand's gamma_2 functional: E[sup_t X_t] <= C gamma_2(T, d), where gamma_2(T, d) = inf over admissible sequences of nets of sup_t sum_n 2^(n/2) d(t, A_n) — the cheapest way to cover T by nested nets, weighting each level by sqrt(2^n). The classical Dudley integral, integral of sqrt(log N(T, d, eps)) deps over the covering numbers N, is a convenient upper bound on gamma_2 but is not always tight. Talagrand's majorizing-measure theorem is the deep converse: for GAUSSIAN processes, gamma_2(T, d) is equivalent (up to absolute constants) to E[sup_t X_t], so chaining is not merely sufficient but captures the truth exactly — the supremum of a Gaussian process is, two-sidedly, a purely geometric quantity of (T, d).

The theory is the backbone of modern high-dimensional probability: it controls suprema of empirical processes (hence uniform laws of large numbers and Rademacher complexity), the operator norm of random matrices, and the behaviour of Gaussian and sub-Gaussian fields on continuous index sets. The honest caveats are real. The majorizing-measure equivalence (gamma_2 = E[sup]) is a theorem for Gaussian processes; for general sub-Gaussian processes chaining gives only the upper bound E[sup] <= C gamma_2, and the lower bound can fail. Dudley's integral is strictly weaker than gamma_2 (it can overestimate by a log factor on irregular index sets, the classic example being the ellipsoid). And the whole machinery measures distance in the PROCESS's intrinsic metric d (the psi_2 increment metric), not the ambient one; using the wrong metric gives a wrong, usually loose, bound.