Rademacher Complexity

Rademacher complexity is a data-dependent measure of the richness of a function class F on a sample x_1,...,x_n, defined as the expected supremum over F of the average correlation with random Rademacher signs σ_i∈{±1}: R_n(F)=E_σ[ sup_{f∈F} (1/n)∑_{i=1}^n σ_i f(x_i) ]. It quantifies how well functions in F can fit random ±1 noise on the sample.