localized Rademacher complexity

Global Rademacher complexity measures how well your whole class can fit noise — but the hypotheses an algorithm actually selects are near-optimal, low-risk ones, not the wild high-risk corners of the class. Why pay for capacity you never use? Localization restricts the complexity to the small neighborhood of low-variance, low-risk functions where the solution genuinely lives, and that restriction can upgrade slow one-over-root-n rates to fast one-over-n rates.

Instead of the Rademacher complexity of the full class, compute it over the subset of functions whose variance is at most r, giving a function of the radius r. The key device is the sub-root fixed point: find the value of r where this localized complexity equals r itself. Under a variance-risk relation — a Bernstein condition, where the variance of the excess loss is controlled by its mean, as holds for strongly convex or low-noise problems — the excess risk is governed by that fixed point, yielding rates as fast as one-over-n rather than one-over-root-n. The analysis pairs Talagrand's concentration inequality with peeling arguments over shells of increasing variance.

Localization is the technical key to fast rates and the sharp tool behind modern analyses of kernel methods, empirical risk minimization under low noise, and oracle inequalities. It explains why, in benign regimes, learning is far faster than worst-case global bounds suggest. The requirements are real: a Bernstein or low-noise condition and curvature of the loss; without them — heavy noise, flat losses — the gain collapses back to the slow global rate.