📊 statistics

How abundant are good interpolators?

Diese Arbeit stellt fest, dass in überparametrisierten Regimen mit kleinen Stichproben-zu-Dimension-Verhältnissen die überwiegende Mehrheit der Einheitsnorm-Linearen Interpolatoren einen gemeinsamen Generalisierungsfehler teilt, der durch ein Large-Deviation-Prinzip bestimmt wird, während effiziente Optimierungsmethoden wie der Gradientenabstieg und die lineare Programmierung diese typische Performance signifikant übertreffen und damit benignes Overfitting nachweisen.

Ursprüngliche Autoren: August Y. Chen, Ahmed El Alaoui

Veröffentlicht 2026-06-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: August Y. Chen, Ahmed El Alaoui

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Die Suche nach der Nadel im Heuhaufen (die keine Nadel ist)

Stellen Sie sich vor, Sie versuchen, ein riesiges Puzzle zu lösen. Sie haben einen Satz an Hinweisen (Datenpunkte) und eine riesige Kiste voller Puzzleteile (Parameter). Im modernen maschinellen Lernen haben wir oft viel mehr Teile als Hinweise. Das nennt man „überparametrisiert“.

Da es so viele Teile gibt, gibt es tausende verschiedene Möglichkeiten, sie anzuordnen, sodass sie perfekt zu den Hinweisen passen. Tatsächlich können Sie sie so anordnen, dass jeder einzelne Hinweis mit null Fehlern erfüllt wird. In der Sprache der Arbeit werden diese perfekten Anordnungen als „Interpolatoren“ bezeichnet.

Die große Frage, die die Autoren stellen, ist: Wenn Sie einfach blind eine dieser perfekten Anordnungen zufällig auswählen, wird sie auch bei neuen Puzzles funktionieren, die Sie noch nicht gesehen haben?

Die Analogie: Das „Perfekte“ vs. das „Typische“

Betrachten Sie die Menge aller möglichen perfekten Anordnungen als eine riesige, weitläufige Stadt.

Der „typische“ Bewohner: Wenn Sie ein zufälliges Haus in dieser Stadt auswählen, wie sieht es aus?
Der „schlaue“ Bewohner: Wenn Sie einen intelligenten Algorithmus verwenden (wie Gradient Descent oder Lineare Programmierung), um ein Haus zu finden, wie sieht es aus?

Die Haupterkenntnis der Arbeit ist etwas überraschend: Der „typische“ Bewohner ist meistens schrecklich darin, zu generalisieren.

Wenn Sie eine zufällige Lösung wählen, die Ihre Trainingsdaten perfekt abbildet, ist es fast garantiert, dass sie bei neuen Daten kläglich versagt. Es ist, als fände man einen Schlüssel, der perfekt in die eigene Haustür passt, aber aus Schokolade besteht – er schmilzt (versagt), sobald man versucht, ihn im Regen (neue Daten) zu benutzen.

Die „schlauen“ Algorithmen (diejenigen, die wir tatsächlich verwenden) wählen jedoch keine zufälligen Häuser aus. Sie finden gezielt die wenigen, seltenen Häuser in dieser Stadt, die tatsächlich stabil sind und gut funktionieren.

Die Kernentdeckung: Gute Interpolatoren sind selten

Die Autoren verwendeten fortgeschrittene Mathematik (speziell etwas namens „Large Deviation Principles“), um diese Stadt der Lösungen abzubilden. Sie berechneten das „Volumen“ des Raums, in dem gute Lösungen leben, im Vergleich zu den schlechten.

Dies fanden sie heraus:

Die „schlechte“ Zone ist massiv: Der Großteil der Stadt ist gefüllt mit Lösungen, die die Trainingsdaten perfekt abbilden, aber für alles andere nutzlos sind. Wenn Sie eine Lösung zufällig auswählen, werden Sie fast sicher hier landen.
Die „gute“ Zone ist winzig: Die Lösungen, die tatsächlich gut generalisieren (also bei neuen Daten funktionieren), existieren zwar, nehmen aber einen exponentiell kleinen Bruchteil des gesamten Raums ein.
Algorithmen sind glücklich: Die effizienten Algorithmen, die wir verwenden (wie Gradient Descent), sind im Wesentlichen „glücklich“ oder „geführt“ genug, um die massive schlechte Zone zu vermeiden und die winzige gute Zone zu finden. Sie stoßen nicht einfach nur auf eine gute Lösung; sie suchen sie aktiv auf.

Der „Signal-zu-Rauschen“-Twist

Die Arbeit untersuchte auch, wie „klar“ die Daten sind (Signal-to-Noise Ratio).

In einer verrauschten Welt (niedriges Signal): Gute Lösungen sind unglaublich selten. Es ist, als versuche man, eine Nadel in einem Heuhaufen zu finden, der aus anderen Nadeln besteht, die fast identisch aussehen. Die „schlauen“ Algorithmen leisten etwas ganz Besonderes, um die richtige zu finden.
In einer klaren Welt (hohes Signal): Wenn die Daten sehr sauber und leicht zu verstehen sind, werden gute Lösungen häufiger. Dies erklärt, warum einige vorangegangene Studien (die sehr saubere Daten betrachteten) dachten, gute Lösungen seien im Überfluss vorhanden. Die Autoren klären hiermit auf, dass in den unordentlichen, realistischen Szenarien, mit denen wir es normalerweise zu tun haben, gute Lösungen tatsächlich sehr selten sind.

Das Rätsel des „Benign Overfitting“

In den letzten Jahren waren Wissenschaftler über „Benign Overfitting“ rätselhaft. Dies ist das Phänomen, bei dem ein Modell die Trainingsdaten zu perfekt anpasst (sogar Rauschen auswendig lernt), aber dennoch hervorragend bei neuen Daten funktioniert.

Diese Arbeit erklärt, warum das passiert:

Es liegt nicht daran, dass „die meisten“ perfekten Anpassungen gut sind.
Es liegt daran, dass die Algorithmen, die wir verwenden, voreingenommen sind. Sie haben eine verborgene Präferenz (implizite Regularisierung), die sie von den Milliarden der „schlechten“ perfekten Anpassungen weg und hin zu der winzigen Insel der „guten“ perfekten Anpassungen steuert.

Zusammenfassung in einem Satz

Während es Millionen von Wegen gibt, Ihre Trainingsdaten perfekt auswendig zu lernen, sind fast alle davon für die reale Welt unbrauchbar, und der einzige Grund, warum unsere KI-Modelle funktionieren, ist, dass unsere Trainingsalgorithmen klug genug sind, die schlechten zu vermeiden und die seltenen, guten zu finden.

Was die Arbeit nicht behauptet

Sie sagt nicht, dass zufälliges Raten jemals funktionieren wird.
Sie behauptet nicht, dass dies für jede Art von neuronalem Netzwerk gilt (sie konzentriert sich auf lineare Klassifikatoren und spezifische Datenmodelle).
Sie bietet keine neue medizinische oder klinische Anwendung; es ist eine theoretische Studie darüber, warum aktuelle Methoden funktionieren.

Technische Zusammenfassung: „Wie abundant sind gute Interpolatoren?“

Problemstellung
Die Arbeit untersucht die Generalisierungseigenschaften der Menge interpolierender linearer Klassifikatoren in überparametrisierten Regimen. Konkret wird ein gelabelter Datensatz $(X_i, y_i)_{i=1}^n$ in $\mathbb{R}^d$ betrachtet, wobei $n/d \to \alpha$ mit $\alpha$ klein (hohe Überparametrisierung) gilt. Die Autoren definieren die Menge $S$ der unit-norm linearen Klassifikatoren $\theta$ , die alle Trainingspunkte mit einer festen Margin $\kappa$ korrekt klassifizieren. Die zentrale Frage lautet: Was ist die typische Generalisierungsleistung eines Klassifikators, der gleichmäßig zufällig aus $S$ gewählt wird?

Diese Untersuchung adresset das Phänomen des „benign overfitting“ (gutartigen Overfittings), bei dem Modelle mit einem Trainingsfehler von Null gut generalisieren. Während bekannt ist, dass implizite Regularisierung (z. B. durch Gradientenabstieg) spezifische Interpolatoren mit guter Leistung auswählt, fragt die Arbeit, ob die meisten Interpolatoren diese Eigenschaft teilen oder ob „gute“ Interpolatoren seltene Ausnahmen innerhalb des Lösungsraums sind.

Methodik
Die Autoren nutzen Werkzeuge der statistischen Physik, insbesondere die Theorie der großen Abweichungen (Large Deviations) und die Replica-Methode (angepasst an rigorose probabilistische Beweise), um die Geometrie des Lösungsraums $S$ zu analysieren.

Datenmodelle: Die Analyse wird unter zwei unterschiedlichen datengenerierenden Verteilungen mit einer konstanten Signal-Rausch-Verhältnis (SNR) $\lambda$ $λ$ durchgeführt:
- Einem Gaußschen Mischmodell (GMM).
- Einem logistischen Modell mit Gaußschen Merkmalen.
Große Abweichungstheorie (LDP): Der zentrale technische Ansatz besteht darin, ein „quenched“ Large Deviation Principle für den Überlapp $\langle \theta, \theta^* \rangle / d$ zwischen einem zufälligen Interpolator $\theta$ und der wahren Signalrichtung $\theta^*$ zu etablieren. Ziel ist es, die exponentielle Rate des Volumens der Menge der Interpolatoren mit einem spezifischen Überlapp $x$ zu charakterisieren.
Variationsformulierung: Die Autoren leiten eine Ratendfunktion $\Phi(x, q)$ her, die auf dem Überlapp $x$ und einem Parameter $q$ (der den Überlapp zwischen zwei unabhängigen zufälligen Interpolatoren darstellt) basiert. Das Volumen des Lösungsraums wird durch ein Sattelpunktproblem der Form $\sup_x \inf_q \Phi(x, q)$ charakterisiert.
Beweistechniken:
- Gaußsches Referenzmaß: Die Beweise lockern die sphärische Beschränkung zu einem vollen Gaußschen Maß auf, um die Konzentration von Maßen und Gaußsche Interpolationstechniken nutzen zu können (folgend dem Talagrand-Ansatz für den sphärischen Perzeptron).
- Cavity-Methode: Die Autoren verwenden ein „Cavity“-Argument, um Constraints (Datenpunkte) nacheinander hinzuzufügen, wobei sie den Free Energy von $n$ Punkten zu $n-1$ Punkten in Beziehung setzen.
- Harte Constraints: Ein entscheidender Schritt besteht darin, die zur Gaußschen Analyse verwendeten glatten Mollifizierungfunktionen zurück in die harten Sprungfunktions-Constraints zu transformieren, welche die Interpolatoren definieren ( $y_i \langle X_i, \theta \rangle \ge \kappa$ ). Dies erfordert die Handhabung nicht-gaußscher Signalanteile und die Etablierung von Konzentrationsgrenzen für Gibbs-Maße mit harten Constraints.
- Bayesianischer Vergleich: Die Arbeit analysiert auch die Posterior-Verteilung (Bayes-optimaler Schätzer), um eine Baseline für die optimale Leistung abzuleiten, wobei angemerkt wird, dass die Posterior eine spezifische Relation (Nishimori-Linie) zwischen Überlappen erfüllt, die das Gleichverteilungsmaß auf den Interpolatoren nicht besitzt.

Wesentliche Beiträge und Ergebnisse

Konzentration der typischen Leistung: Die Arbeit stellt fest, dass die Generalisierungsfehlerrate eines gleichmäßig zufälligen Interpolators mit hoher Wahrscheinlichkeit über die Daten um einen eindeutigen „typischen“ Wert $x^*$ konvergiert. Dies bestätigt eine Vermutung von Theisen, Klusowski und Mahoney [TKM21] bezüglich der Existenz eines typischen Fehlers, wobei die Arbeit die Bedingungen, unter denen dies gilt, präzisiert.
Seltenheit guter Interpolatoren: Das primäre Ergebnis ist, dass im überparametrisierten Regime mit konstanter SNR die typische Leistung $x^*$ $x^{*}$ signifikant schlechter ist als die Leistung, die durch effiziente Algorithmen erreicht wird.
- Die Autoren vergleichen $x^*$ mit der Leistung eines Linear Programming (LP) Schätzers und des Gradientenabstiegs (GD) auf der logistischen Loss-Funktion.
- Numerische Simulationen und theoretische Schranken zeigen, dass $x^* < x_{LP}$ und $x^* < x_{GD}$ für einen weiten Parameterbereich gilt.
- Folglich bilden „gute“ Interpolatoren (jene, die so gut performen wie LP oder GD) einen exponentiell kleinen Bruchteil der gesamten Menge der Interpolatoren.
Abhängigkeit von der SNR: Die Arbeit klärt, dass die Abundanz guter Interpolatoren hochgradig von der SNR abhängt. Während frühere heuristische Analysen suggerierten, dass gute Klassifikatoren abundant seien, nahmen diese Analysen implizit eine hohe SNR an (wo die Klassentrennung mit der Dimension wächst). In dem hier untersuchten Regime mit konstanter SNR sind gute Interpolatoren extrem selten, was den Erfolg der impliziten Regularisierung zu einem nicht-trivialen Phänomen macht.
Charakterisierung des Bayes-Optimalen: Die Autoren liefern eine asymptotische Charakterisierung der Bayes-optimalen Leistung ( $x_{Bayes}$ ) unter beiden Datenmodellen und zeigen, dass effiziente Algorithmen (LP und GD) den typischen Interpolator deutlich übertreffen und sich dem Bayes-optimalen Limit näher annähern als eine Zufallsziehung aus dem Lösungsset.

Bedeutung und Behauptungen
Die Arbeit behauptet, die Frage der „Abundanz guter Interpolatoren“ im Regime der konstanten SNR und der Überparametrisierung gelöst zu haben. Ihre Bedeutung liegt in der Demonstration, dass:

Implizite Regularisierung essenziell ist: Die Tatsache, dass effiziente Algorithmen (GD, LP) einen zufälligen Interpolator weit übertreffen, legt nahe, dass der Generalisierungserfolg überparametrisierter Modelle nicht eine inhärente Eigenschaft der Lösungsmenge $S$ ist, sondern eine Folge des spezifischen Pfades, den Optimierungsalgorithmen nehmen (implizite Regularisierung).
Heuristische Abundanz widerlegt wird: Die Ergebnisse widersprechen Heuristiken, die suggerieren, dass „gute Klassifikatoren abundant sind“, und zeigen stattdessen, dass eine solche Abundanz nur in High-SNR-Limits auftritt.
Rigoroses LDP für Interpolatoren: Die Arbeit liefert ein rigoroses Large Deviation Principle für den Generalisierungsfehler von Uniform-Interpolatoren, ein Ergebnis, das zuvor heuristisch war oder auf spezifische High-SNR-Annahmen beschränkt war.

Die Autoren stellen explizit fest, dass ihre Ergebnisse die nicht-triviale Natur des benign overfitting in diesem Setting hervorheben, in dem die überwältigende Mehrheit der Lösungen des Interpolationsproblems schlecht generalisiert und nur eine winzige, algorithmisch selektierte Teilmenge gut performt.