Rademacher-Komplexität ist ein datenabhängiges Maß für die Reichweite einer Funktionsklasse F auf einer Stichprobe x_1,...,x_n, definiert als der Erwartungswert des Supremums über F der durchschnittlichen Korrelation mit zufälligen Rademacher-Zeichen σ_i∈{±1}: R_n(F)=E_σ[ sup_{f∈F} (1/n)∑_{i=1}^n σ_i f(x_i) ]. Sie quantifiziert, wie gut Funktionen in F zufälliges ±1-Rauschen auf der Stichprobe anpassen können.

Prinzip

Bewerte die Kapazität einer Funktionsklasse durch ihre Fähigkeit, sich an zufällige Vorzeichen auf einer gegebenen Stichprobe anzupassen: große Rademacher-Komplexität bedeutet, dass viele Funktionen beliebig mit Rauschen korrelieren können, was auf mögliche Überanpassung hinweist.

Demonstration

Für lineare Prädiktoren mit beschränkter Norm in R^d und einer festen Stichprobe skaliert die empirische Rademacher-Komplexität wie die Normbeschränkung mal die durchschnittliche Merkmalnorm geteilt durch √n; dies führt zu expliziten Generalisierungsabschätzungen für regulierte lineare Modelle.

Fehlanwendung

Die empirische Rademacher-Komplexität, die auf dem Trainingssatz berechnet wurde, so zu behandeln, als entspreche sie der Populationskomplexität ohne Konzentrationsargumente; oder sie auf unbeschränkte Funktionsklassen anzuwenden ohne Trunkierung oder Varianzkontrolle.

Konsequenz

Rademacher-Komplexität liefert scharfe, datenabhängige Generalisierungsabschätzungen via Symmetrisierung: erwartete Generalisierungslücke ≤ 2·R_n(F)+kleinere Terme, wodurch modellbezogene Auswahl und Kapazitätskontrolle auf beobachteten Daten basieren können.

Umkehrung

Im Gegensatz zu kombinatorischen Maßen (VC-Dimension) oder metrischen Maßen (Überdeckung/Entropie): Rademacher-Komplexität ist stichprobenabhängig und zufällig, während VC-Dimension distributionsfrei und kombinatorisch ist; die Umkehrung betont empirische vs. uniforme Beschreibungen der Komplexität.

Abgrenzung

Hängt von Stichprobe, Funktionsklasse und Schranken für Funktionswerte ab; ist nur sinnvoll, wenn Funktionen messbar und angemessen beschränkt (oder subgaussian) sind; misst nicht direkt Approximationsfehler oder Worst-Case-Populationsleistung.

Semantische Spannung

Spannung zu Überdeckungszahl- und VC-basierten Schranken: Rademacher-Komplexität liefert oft schärfere, datenabhängige Schranken, erfordert jedoch Stichprobenberechnung und Konzentrationsbetrachtungen, während andere Maße distributionsfrei oder leichter mit metrischen Annahmen zu verbinden sind.

Synthese

Rademacher-Komplexität fasst zusammen, wie gut eine Funktionsklasse zufällige ±1-Labels auf einer konkreten Stichprobe anpassen kann: der erwartete maximale Korrelationswert mit Rademacher-Zeichen und eine zentrale Größe in modernen Generalisierungsbeweisen.