Rademacher complexity and contraction

Fix a sample of inputs and attach independent signs taking values plus and minus one with equal probabilities. The empirical Rademacher complexity averages, over those signs, the largest normalized signed sum obtainable by a function in the class. The sample is held fixed in this definition. Its population counterpart then averages over the random training inputs. We use the supremum without an absolute value; introducing an absolute value instead corresponds to symmetrizing the class and can change constants or finite-class counts.

For finite or countable classes, assume measurable evaluations; for more general classes explicitly assume the relevant suprema are measurable. Bounded losses make the expectations needed for elementary symmetrization finite. A ghost-sample argument bounds the expected one-sided uniform population-to-empirical deviation of a bounded loss class by twice its population Rademacher complexity. This is an expectation statement. A high-probability certificate needs an additional concentration step and its confidence penalty, rather than reinterpreting an average as an event that always occurs.

For linear scores with a Euclidean weight norm at most B, the supremum becomes B times the norm of the signed sum of inputs, divided by n. Jensen and cancellation of cross terms bound its expectation by B times the square root of the sum of squared input norms, divided by n. If each input norm is at most R, this is at most BR divided by the square root of n. The bound does not explicitly depend on ambient dimension, but the norm constraints are substantive assumptions.

A larger dimension can still worsen these radius quantities, or permit a different class if the norm budget changes. Thus a dimension-free-looking expression is not a universal promise that more features are harmless. The two-point calculation below keeps the feature vectors and the weight interval explicit. Its exact value can be smaller than the Jensen upper bound because the norm of the random sum fluctuates. That gap is a cost of the inequality, not an inconsistency in the complexity definition.

For coordinatewise L-Lipschitz maps that vanish at zero, the scalar contraction principle bounds the Rademacher complexity of the transformed vectors by L times that of the original class, in the no-absolute-value convention used here. For a nonlinear loss, verify the Lipschitz constant on every score value the class can attain; a local derivative estimate at one fitted point is insufficient. Squared loss is not globally Lipschitz on unrestricted scores, though it is Lipschitz on a specified bounded score-and-label range.

Contraction controls fluctuation size, but it does not say a surrogate loss targets the desired decision problem. A constant loss has zero complexity and teaches no classifier. Calibration, approximation error and optimization error require separate arguments. When the loss also depends on fixed sample labels, one may apply coordinate maps to the margin scores with those labels held fixed, provided their Lipschitz requirements hold. This is how a useful score-class bound can become a loss-class bound without pretending that all losses have the same geometry.