Localized complexities and fast rates

Assume iid examples, a finite nonempty fixed class with losses in[0,1], and a class member h_star minimizing population risk. For each h, define excess loss g_h as its loss minus that of h_star, and let r_h be its nonnegative expectation. The excess loss can be negative on particular examples even though its mean is nonnegative. A Bernstein condition requires its second moment to be at most B times that mean, uniformly over the class, for some fixed B. This is stronger than boundedness alone.

The condition says that candidates with tiny excess risk also have tiny fluctuations relative to the comparator. In a realizable zero-one problem, the zero-risk comparator has zero loss almost surely, so g is itself a zero-one error and its second moment equals its mean. General agnostic problems need not satisfy such a condition with a uniform constant. Noise or curvature assumptions can provide it in specific models, but the relationship must be proved rather than inferred from the word localization.

For a candidate with positive r, Bernstein’s lower-tail inequality bounds the probability that its empirical excess is nonpositive. The centered summands have absolute value at most two and variance at most Br. Consequently the exponent can be bounded by minus nr divided by 2B+4/3. If exact ERM selects a candidate, that candidate’s empirical excess relative to h_star is nonpositive. A union bound over M candidates then rules out all selected candidates above the displayed excess threshold with confidence one minus delta.

This is a complete finite-class statement under its listed hypotheses, with a conservative constant reflecting a general bounded-centered-variable inequality. It gives an inverse-n bound when M, B and delta are fixed. It does not imply that every noisy classification problem has an inverse-n rate, or that a local-complexity theorem always has the same numerical constant. If there is no class minimizer, the comparator and approximation errors need different handling; if losses are unbounded, the bounded-increment Bernstein step must be replaced.

For an infinite class, one may measure Rademacher complexity only among excess-loss functions whose variance or mean is below a radius r. A schematic local envelope proportional to the square root of vr/n intersects the line r at a scale proportional to v/n. This fixed point explains the appearance of faster rates: smaller neighborhoods fluctuate less, allowing a self-consistent error radius. Constants, confidence penalties, star-shaped enlargements and a precise definition of the neighborhood belong to the actual theorem being applied.

An algebraic intersection is not a statistical guarantee until a valid localized empirical-process argument connects it to the estimator. For example, formally solving r=c times the square root of vr/n gives r=c squared times v/n for the positive solution; zero is also a solution and cannot simply be announced as zero estimation error. The worked example instead uses the proved finite-class certificate, while the fixed-point calculation is used only to interpret the balance behind more general localized results.