Paper: Rademacher complexity (Bartlett & Mendelson, 2003)

 

1. Original Paper (Bartlett & Mendelson, 2002)

Title: "Rademacher and Gaussian Complexities: Risk Bounds and Structural Results"
Authors: Peter Bartlett and Shahar Mendelson
Journal: Journal of Machine Learning Research (JMLR), 2002.
PDF: Download from JMLR

Key Contributions:

• Introduces Rademacher complexity as a measure of hypothesis class complexity.

• Provides data-dependent generalization bounds (tighter than VC bounds).

• Connects Rademacher complexity to Gaussian complexity and covering numbers.

---

2. Why Rademacher Complexity?

Rademacher complexity measures the ability of a hypothesis class to fit random noise, defined as:

$${\mathcal{R}}_n(\mathcal{H})={\mathbb{E}}_{\sigma ,{\mathcal{D}}_n}[\underset{h\in \mathcal{H}}{\sup }\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}h(x_i)]$$

where ${\sigma }_i$ are random Rademacher variables ($\pm 1$ with equal probability).

Interpretation:

• A high Rademacher complexity implies the model can overfit noise (poor generalization).

• Used to derive bounds like:

  $$\text{Test Error}\le \text{Train Error}+2{\mathcal{R}}_n(\mathcal{H})+\mathcal{O}\left(\sqrt{\frac{\log (1\mathrm{/}\delta )}{n}}\right)$$

---

3. Key Results from the Paper

1. Bounds for Classification/Regression:

   • Sharper than VC bounds because they adapt to the data distribution.

2. Structural Results:

   • Decomposes complexity for composite function classes (e.g., neural networks).

3. Connection to Gaussian Complexity:

   • Shows equivalence under mild conditions.

---

4. Follow-Up Work & Tutorials

1. Modern Tutorial (MIT):

   • PDF

2. Lecture Notes (CMU):

   • PDF

3. Book Chapter (Understanding ML, Shalev-Shwartz & Ben-David):

   • Chapter 26

---

5. Practical Implications

• Model Selection: Prefer models with lower Rademacher complexity.

• Deep Learning: Explains why SGD finds models that generalize despite overparameterization.

• Adversarial Robustness: Used to prove robustness guarantees.

---

6. Example Calculation

For a linear classifier class $\mathcal{H}=\{x\mapsto w^{T}x:\mathrm{\parallel }w{\mathrm{\parallel }}_2\le 1\}$:

$${\mathcal{R}}_n(\mathcal{H})\le \frac{\underset{i}{\max }\mathrm{\parallel }{x}_i{\mathrm{\parallel }}_2}{\sqrt{n}}$$

(Derived using Dudley’s entropy integral in the paper.)

---

7. How to Cite

bibtex

Copy

@article{bartlett2002rademacher,
  title={Rademacher and Gaussian complexities: Risk bounds and structural results},
  author={Bartlett, Peter L and Mendelson, Shahar},
  journal={Journal of Machine Learning Research},
  volume={3},
  pages={463--482},
  year={2002}
}

---

Summary

Bartlett & Mendelson’s work provides data-dependent complexity measures that refine classical VC theory. Rademacher complexity is now a cornerstone of modern statistical learning theory.

For code implementations, see:

• Rademacher complexity in scikit-learn (used in margin-based classifiers).

• TensorFlow L2 regularization (connects to Rademacher bounds).

Link: https://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf