Rademacher Complexity: Scaling and Shift Invariance

MediumClassical ML

Reported in interviews at Citadel Renaissance Technologies

Problem statement

Rademacher complexity is a fundamental tool in statistical learning theory for measuring the richness of a function class.

  1. Define the (empirical) Rademacher complexity $R_n(F)$ for a function class $F$ evaluated on a sample $x_1, \dots, x_n$.
  1. Suppose $F_2 = aF_1 + b$, meaning $F_2 = \{x \mapsto a f(x) + b : f \in F_1\}$ for constants $a, b \in \mathbb{R}$. Show that $R_n(F_2) = |a|\, R_n(F_1)$. In particular, explain why the Rademacher complexity is completely independent of the shift $b$.
Show hint

What quantity would capture how well a class of functions can line up with purely random labels on a fixed sample?

Relevant roles: Research Scientist, Applied Scientist and Data Scientist.

Related free problems