VC dimension is a worst-case combinatorial quantity. It measures the largest set of points a hypothesis class can shatter, full stop — without reference to the data distribution. This makes VC bounds distribution-free, which is a virtue, but also makes them vacuous on classes that are expressive but constrained in practice by the data. Rademacher complexity was introduced to repair this. It is the same basic move as VC — measure how much a class can fit noise — but measured on the actual sample, with the actual data distribution implicit in the empirical average.
For a sample S = {x_1, …, x_n} and a function class F, the empirical Rademacher complexity is
R̂S(F) = E_σ [ sup{f ∈ F} (1/n) Σ_i σ_i f(x_i) ],
where σ_i are independent ±1 Rademacher random variables. Intuitively, it asks: how well can the best function in F correlate with random sign labels on this specific sample? The expected version, taking E over samples of size n, is R_n(F).
For shallow nets, SVMs, boosting, and kernel methods, Rademacher bounds produce non-vacuous generalization bounds — often within a factor of 2-5 of the observed test error. This was a real victory in the 2000s and remains the foundation of modern statistical learning theory courses.
For overparameterized deep networks, the bound is still vacuous — sometimes by orders of magnitude. The issue is that for a network with W parameters, the Rademacher complexity of “all functions representable by this architecture” scales roughly as √(W/n). Once W ≫ n, the bound is ≥ 1, which says nothing.
The bound is not wrong; it is tight over the hypothesis class as declared. The hypothesis class is wrong. SGD does not actually search the full set of representable functions. It explores a small norm-constrained, geometry-constrained subset. Rademacher bounds restricted to that effective subset are sometimes non-vacuous, but characterizing the subset is exactly the unsolved problem of implicit-bias theory.