A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Rademacher complexity measures the ability of a hypothesis class to fit random noise. Given a sample of n points, the empirical Rademacher complexity is the expected maximum correlation between functions in the class and random +/-1 labels (Rademacher variables). A class that can correlate highly with random labels is overly expressive and will need more data to generalize. Unlike VC dimension, Rademacher complexity is data-dependent — it adapts to the actual distribution, often yielding tighter generalization bounds.
VC dimension tells you the worst-case capacity of a hypothesis class, but it ignores the actual data distribution. A class might have high VC dimension yet behave simply on the data you actually encounter. Rademacher complexity addresses this limitation by measuring capacity relative to the data, providing tighter and more informative generalization bounds.
The definition is elegant. Given a sample S = {x_1, ..., x_n}, generate random Rademacher variables sigma_1, ..., sigma_n, each independently +1 or -1 with equal probability. The empirical Rademacher complexity is R_S(H) = E_sigma[sup_{h in H} (1/n) sum_i sigma_i * h(x_i)]. In words: assign random labels to the data points, then find the hypothesis in H that best correlates with those random labels, and average over all possible random labelings. A flexible class will find high correlation even with random noise; a restricted class will not.
The generalization bound that follows is clean and powerful: with probability at least 1 - delta, for all h in H, the true risk R(h) is at most the empirical risk R_hat(h) + 2 * R_S(H) + sqrt(log(1/delta)/(2n)). The Rademacher complexity term directly controls the generalization gap. For a class with VC dimension d, the Rademacher complexity is at most O(sqrt(d/n)), recovering the VC-based bound. But for structured problems — data on low-dimensional manifolds, sparse representations, smooth functions — Rademacher complexity can be much smaller than the VC bound would suggest, because it measures capacity with respect to the actual data geometry.
The practical significance extends beyond tighter bounds. Rademacher complexity provides a principled way to compare hypothesis classes on specific problems: compute the empirical Rademacher complexity for each class on your data, and the one with lower complexity will have a tighter generalization guarantee for the same training error. This connects directly to model selection and regularization — techniques that reduce Rademacher complexity (such as norm constraints on weights) provably improve generalization. The data-dependent nature of Rademacher complexity also explains why deep networks with millions of parameters can generalize well: their effective Rademacher complexity on structured real-world data is much smaller than their VC dimension would suggest.