🤖 machine learning

On Regularization via Early Stopping for Least Squares Regression

Diese Arbeit charakterisiert die Dynamik des diskreten Full-Batch-Gradientenabstiegs für die lineare Regression, um zu demonstrieren, dass das vorzeitige Abbrechen (Early Stopping) eine Lösung liefert, die einer Minimum-Norm-Generalisierten Ridge-Regression entspricht, wodurch deren Generalisierungsvorteile über beliebige Datenspektren und Lernraten-Zeitpläne hinweg bewiesen und eine Schätzung für die optimale Stoppzeit bereitgestellt wird.

Ursprüngliche Autoren: Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

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

Stellen Sie sich vor, Sie bringen einem Schüler (dem Machine-Learning-Modell) bei, ein mathematisches Problem zu lösen (Vorhersagen von Ergebnissen aus Daten). Sie haben ein Lehrbuch mit Beispielen (die Trainingsdaten) und Sie möchten, dass der Schüler die zugrunde liegenden Regeln lernt, damit er auch neue Probleme lösen kann, die er noch nie gesehen hat (Generalisierung).

Dieses Papier handelt von einer speziellen Lehrmethode namens Early Stopping (vorzeitiger Abbruch). Normalerweise lassen Lehrer Schüler so lange lernen, bis sie jede einzelne Übungsaufgabe perfekt beherrschen. Aber manchmal, wenn ein Schüler zu lange lernt, beginnt er, die spezifischen Eigenheiten des Übungsbuches auswendig zu lernen (wie die Schriftart oder die Papierbeschaffenheit), anstatt die eigentlichen mathematischen Regeln zu verstehen. Dies wird als „Overfitting“ (Überanpassung) bezeichnet, und es führt dazu, dass er bei neuen Tests scheitert.

Early Stopping ist die Strategie, zu sagen: „Okay, hör jetzt auf zu lernen, bevor du anfängst, das Rauschen auswendig zu lernen.“

Hier ist das, was die Autoren herausgefunden haben, einfach erklärt:

1. Die „unsichtbare Hand“ des vorzeitigen Abbruchs

Die Autoren wollten wissen: Was genau passiert im Gehirn des Schülers, wenn wir ihn vorzeitig stoppen?

Sie fanden heraus, dass das vorzeitige Stoppen mathematisch identisch mit einer bestimmten Art von „Disziplin“ ist, die man Ridge-Regression nennt.

Die Analogie: Stellen Sie sich vor, die Ridge-Regression ist wie ein schwerer Rucksack, den man dem Schüler gibt. Der Rucksack zwingt ihn dazu, seine Antworten einfach zu halten und nahe bei Null (dem Ausgangspunkt) zu bleiben.
Die Entdeckung: Das Papier beweist, dass das Gehirn des Schülers exakt denselben Zustand einnimmt, wenn man ihn zum richtigen Zeitpunkt stoppt, als hätte er die ganze Zeit diesen schweren Rucksack getragen. Man muss den Rucksack nicht physisch hinzufügen (die mathematische Strafe); man muss nur die Lektion zum perfekten Zeitpunkt beenden, und das Ergebnis ist dasselbe.

2. Der „Lautstärkeregler“ für verschiedene Frequenzen

Die Autoren untersuchten, wie der Schüler verschiedene Teile des Problems lernt. Sie erkannten, dass die Daten nicht nur ein einziger großer Block sind, sondern aus vielen verschiedenen „Frequenzen“ oder Richtungen bestehen (einige sind einfach, andere sind schwer).

Die Analogie: Stellen Sie sich die Daten wie eine Symphonie vor. Einige Instrumente spielen laute, offensichtliche Noten (einfache Muster), während andere leise, komplexe Noten spielen (schwierige Muster).
Die Entdeckung: Wenn Sie Gradient Descent (die Standardmethode des Lehrens) verwenden, lernt der Schüler die lauten Noten sehr schnell. Wenn Sie weitermachen, versucht er, auch die leisen Noten zu lernen, aber dabei beginnt er, das „Rauschen“ (Statik) in den leisen Noten zu hören und dieses Rauschen als wäre es Musik auswendig zu lernen.
Das Ergebnis: Early Stopping wirkt wie ein Lautstärkeregler. Es dreht die Lautstärke der komplexen, leisen Noten gerade so weit herunter, dass der Schüler die Musik hört, aber das Rauschen ignoriert. Das Papier liefert eine Formel, um genau zu berechnen, wie lange man den Lautstärkeregler heruntergedreht lassen muss.

3. Die „Lernrate“ ist entscheidend

Ein entscheidender Teil des Papiers handelt von den Lernraten (Learning Rates). Dies ist das Tempo, in dem der Schüler einen Schritt macht, während er lernt.

Konstantes Tempo: Wenn der Schüler in einem stetigen, langsamen Tempo geht, lernt er die lauten Noten, dann die leisen Noten und fängt schließlich an, das Rauschen zu hören. Hier funktioniert das vorzeitige Stoppen sehr gut.
Abnehmendes Tempo: Wenn der Schüler schnell beginnt und dann zu schnell langsamer wird (wie bei einem exponentiellen Zerfall), könnte er bereits vor dem Erreichen des Rauschens aufhören zu lernen. In diesem Fall hilft das vorzeitige Stoppen nicht viel, da er ohnehin schon von selbst langsamer wurde.
Die Behauptung des Papiers: Die Autoren stellen ein Regelwerk bereit. Sie sagen: „Wenn dein Lernraten-Schema wie X aussieht, dann ist das vorzeitige Stoppen eine Superkraft. Wenn es wie Y aussieht, ist das vorzeitige Stoppen nutzlos.“

4. Die „magische Formel“ für den Zeitpunkt des Abbruchs

Der praktischste Teil des Papiers ist eine Formel, die ihnen sagt, wann genau man stoppen muss.

Die Eingaben: Sie müssen drei Dinge wissen:
1. Wie viel „Rauschen“ in Ihrem Lehrbuch ist (wie unordentlich die Daten sind).
2. Wie stark das „Signal“ ist (wie klar die tatsächlichen Regeln sind).
3. Wie schnell der Schüler geht (die Lernrate).
Die Ausgabe: Die Formel spuckt eine spezifische Anzahl von Schritten (Iterationen) aus.
Der Test: Die Autoren haben dies mit realen Daten getestet (wie handgeschriebenen Ziffern und Bildern). Sie fanden heraus, dass ihre Formel den „Sweet Spot“ (den idealen Punkt) fast perfekt vorhersagt. Wenn sie zum Zeitpunkt stoppten, den ihre Formel vorschlug, schnitt der Schüler besser ab, als wenn er länger oder kürzer gelernt hätte.

5. Wann man NICHT vorzeitig stoppen sollte

Das Papier warnt auch davor, dass Early Stopping nicht immer die Lösung ist.

Die Analogie: Wenn Sie bereits einen sehr schweren Rucksack tragen (eine starke mathematische Strafe namens „Ridge-Regularisierung“), brauchen Sie nicht vorzeitig zu stoppen. Der Rucksack erledigt bereits die Arbeit, den Schüler einfach zu halten.
Die Behauptung: Wenn die „Strafe“ zu schwer ist, schadet das vorzeitige Stoppen der Leistung. Der Schüler muss weitermachen, um die Aufgabe zu vollenden. Die Autoren beweisen mathematisch, dass, wenn die Strafe stark genug ist, man den Schüler einfach fertig lernen lassen sollte.

Zusammenfassung

Dieses Papier ist ein „Benutzerhandbuch“ für die Strategie des Early Stopping.

Es erklärt, warum es funktioniert (es ist dasselbe wie das Hinzufügen einer mathematischen Strafe).
Es erklärt, wann es funktioniert (es hängt davon ab, wie schnell man lernt und wie unordentlich die Daten sind).
Es gibt Ihnen einen Rechner, um den exakten Moment zu finden, an dem man stoppen muss – etwas, das sie mit realen Daten bewiesen haben.

Sie haben keinen neuen Weg erfunden, zu lehren; sie haben lediglich die präzise Physik entschlüsselt, wann man den Stecker ziehen muss, um die besten Ergebnisse zu erzielen.

Technisches Resümee: Regularisierung durch Early Stopping bei der Least-Squares-Regression

Problemstellung

Die Arbeit befasst sich mit der grundlegenden Herausforderung, die Auswirkungen von Early Stopping auf die Parameter und die Generalisierungsfähigkeit von Machine-Learning-Modellen zu verstehen, speziell im Kontext der linearen Regression. Während Early Stopping eine weit verbreitete Regularisierungstechnik ist, bleibt ihre theoretische Natur unvollständig verstanden, insbesondere für diskretes Full-Batch-Gradientenabstieg mit beliebigen Lernraten-Schedules und Datenverteilungen.

Die bestehende Literatur stützt sich oft auf starke Annahmen, wie etwa die Kontinuumslimit-Gradientenfluss-Dynamik oder Gauß-Annahmen auf die Feature-Matrix, um Stopp-Regeln abzuleiten. Diese Ansätze versäumen es, die optimale Stopp-Zeit unter praktischen, nicht-konstanten Lernraten-Schedules oder zu erklären, Phänomene wie „Grokking“ (bei denen Modelle erst überfitten und dann generalisieren) in diskreten Settings zu erläutern. Darüber hinaus erfordern die präzise Beziehung zwischen Early Stopping und expliziter $L_2$ - (Ridge-) Regularisierung sowie die Bedingungen, unter denen Early Stopping vorteilhaft oder nachteilig ist, eine rigorosere Charakterisierung ohne restriktive Verteilungsannahmen.

Methodik

Die Autoren analysieren die diskreten Dynamiken des Full-Batch-Gradientenabstiegs für die lineare Regression und vermeiden dabei die Näherung durch den kontinuierlichen Gradientenfluss. Der kerndoktorale methodische Beitrag ist die Ableitung von exakten, geschlossenen Ausdrücken für die Parameter-Trajektorie $\beta_k$ nach $k$ Schritten.

Zentrale methodische Komponenten sind:

Spektrale Zerlegung: Die Analyse wird in der Eigenbasis der Stichproben-Kovarianzmatrix $X^T X$ durchgeführt. Die Autoren definieren eine Funktion $\phi(k; \zeta, \{\eta_i\})$ , welche den kumulativen Effekt eines Lernraten-Schedules $\{\eta_i\}$ auf einen spezifischen Eigenwert $\zeta$ erfasst.
Formulierung der exakten Trajektorie: Unter Verwendung dieser Funktion leiten die Autoren eine explizite Formel für $\beta_k$ ab, die für jede Datenmatrix $X$ , jeden Lernraten-Schedule und jede Initialisierung gilt. Diese Formel zerlegt den Fehler in eine Signal-Komponente (abhängig von der Initialisierung und den wahren Parametern) und eine Rausch-Komponente (abhängig von den Residuen).
Risiko-Analyse: Das erwartete exzessive Risiko wird durch Erwartungswerte über das Rauschen und – unter einer sphärischen Prior-Annahme – über das Signal analysiert. Die Autoren differenzieren das Risiko bezüglich der Iterationszahl (indem sie diese via Annahme 2 als kontinuierliche Variable behandeln), um kritische Punkte zu identifizieren.
Äquivalenzbeweise: Die Arbeit etabliert mathematische Äquivalenzen zwischen Early-Stopping-Lösungen und Lösungen zu verallgemeinerten Ridge-Regression-Problemen, was einen direkten Vergleich der Regularisierungseffekte ermöglicht.

Zentrale Beiträge

1. Exakte Trajektorien für diskrete Dynamiken

Die Arbeit liefert Proposition 1, die exakte Formeln für die diskreten Dynamiken von $\beta_k$ für das Kernel-Ridge-Regression-Problem bereitstellt. Im Gegensatz zu früheren Arbeiten treffen diese Formeln keine Annahmen über die Datenverteilung, den Lernraten-Schedule oder die Rauschverteilung. Die Autoren liefern geschlossene Ausdrücke für $\phi$ unter verschiedenen gängigen Schedules, einschließlich konstantem, polynomiellem Zerfall, konstantem additives Zerfall und exponentiellem Zerfall (unter Verwendung von Gamma-Funktionen und $q$ -Pochhammer-Symbolen).

2. Äquivalenz zur verallgemeinerten Ridge-Regression

Die Autoren beweisen Theorem 5 und zeigen damit, dass die nach $T$ Iterationen von Early Stopping (mit $\mu=0$ ) erzielte Lösung für generische Daten und beliebige Lernraten-Schedules äquivalent zur Minimum-Norm-Lösung eines verallgemeinerten Ridge-Regression-Problems ist. Die Regularisierungsmatrix $D$ in diesem verallgemeinerten Problem wird explizit durch den Lernraten-Schedule und die Stopp-Zeit bestimmt.
Umgekehrt zeigt Theorem 6, dass jede Minimum-Norm-Lösung einer Standard-Ridge-Regression mittels Early Stopping erreicht werden kann, sofern man jedem Eigenraum der Stichproben-Kovarianzmatrix eine distinkte Lernrate zuweisen kann.

3. Bedingungen für Nutzen und Nachteil

Das Paper etabliert hinreichende Bedingungen dafür, wann Early Stopping die Generalisierungsleistung verbessert:

Theorem 8 (Vorteilhaft): Early Stopping ist vorteilhaft, wenn der Lernraten-Schedule es dem „Shrinkage-Faktor“ $\phi(k)$ ermöglicht, ausreichend schnell zu zerfallen, sodass der Grenzwert des Verhältnisses $\phi(k)/\phi(0)$ unter einem durch das Signal-Rausch-Verhältnis bestimmten Schwellenwert liegt. Dies gilt für konstante, linear fallende und andere Schedules, bei denen das kumulative Schrittmaß divergiert.
Theorem 9 (Nicht vorteilhaft): Early Stopping ist nicht vorteilhaft, wenn die Lernrate zu schnell zerfällt (z. B. schneller polynomialer oder exponentieller Zerfall), sodass der Shrinkage-Faktor den notwendigen Schwellenwert nicht erreicht. In diesen Fällen sinkt das Risiko mit weiterer Trainingsdauer weiter.
Theorem 10 (Ridge-Regularisierung): Diese Bedingungen werden auf den Fall erweitert, in dem explizite Ridge-Regularisierung ( $\mu > 0$ ) vorliegt. Eine zentrale Erkenntnis ist, dass, falls der explizite Regularisierungsparameter $\mu$ einen kritischen Wert überschreitet ( $\mu \ge \tau^2 / (n\sigma^2)$ ), Early Stopping keinen zusätzlichen Nutzen bietet.

4. Schätzung der optimalen Stopp-Zeit

Die Autoren schlagen eine Schätzung für die optimale Stopp-Zeit (Gleichung 31) vor, die auf dem kumulativen Lernraten-Budget $\sum \eta_i$ basiert. Die Schätzung wird abgeleitet, indem der Shrinkage-Faktor mit dem optimalen Gleichgewicht zwischen Signal und Rauschen für einen repräsentativen Eigenwert gleichgesetzt wird. Diese Schätzung generalisiert vorangegangene Ergebnisse aus dem Gradientenfluss-Regime auf diskrete Dynamiken mit beliebigen Spektren und nicht-konstanten Lernraten.

Ergebnisse und empirische Validierung

Die theoretischen Befunde werden durch Experimente an synthetischen Daten und realen Datensätzen (MNIST und CIFAR10) validiert.

Genauigkeit der Schätzung: Die vorgeschlagene Stopp-Zeit-Schätzung (Gleichung 31) stimmt eng mit den empirisch beobachteten optimalen Stopp-Zeiten über verschiedene Lernraten-Schedules (konstant, polynomiel, linear, exponentiell, Cosine Annealing und zufällig) überein.
Regime-Abhängigkeit: Die Experimente bestätigen die theoretische Vorhersage, dass Early Stopping vorteilhaft ist, wenn der explizite Ridge-Parameter $\mu$ unter dem optimalen Ridge-Parameter $\mu^*$ liegt, aber nachteilig (oder unnötig) wird, wenn $\mu \ge \mu^*$ .
Schedule-Sensitivität: Die Ergebnisse zeigen, dass die Iteration, bei der das Optimum auftritt, je nach Lernraten-Schedule signifikant variiert, aber das kumulative Budget der Lernraten als robuster Prädiktor für den optimalen Stopp-Punkt dient.
Grokking: Die Analyse legt nahe, dass für viele gängige Lernraten-Schedules (bei denen das kumulative Schrittmaß divergiert) lineare Modelle kein „Grokking“ (späte Generalisierung nach Overfitting) zeigen; stattdessen zeigen sie den klassischen Bias-Variance-Tradeoff, bei dem Early Stopping optimal ist.

Bedeutung und Ansprüche

Das Paper beansprucht, eine nicht-asymptotische, distributionsfreie Charakterisierung von Early Stopping in der linearen Regression zu liefern. Seine Bedeutung liegt in:

Überbrückung von Theorie und Praxis: Durch die Abkehr von kontinuierlicher Gradientenfluss-Dynamik und Gauß-Annahmen sind die Ergebnisse auf praktische, diskrete Trainings-Szenarien mit beliebigen Lernraten-Schedules anwendbar.
Vereinheitlichende Perspektive: Es vereint formal Early Stopping mit verallgemeinerter Ridge-Regularisierung und zeigt, dass die „implizite“ Regularisierung durch Early Stopping mathematisch äquivalent zu einem expliziten, datenabhängigen $L_2$ -Penalty ist.
Praktische Orientierungshilfe: Es bietet eine konkrete, theoretisch fundierte Schätzung der optimalen Stopp-Zeit, die nur von beobachtbaren Größen abhängt (Signal-Rausch-Verhältnis, Eigenwert-Spektrum und Lernraten-Schedule) und kein Wissen über das wahre zugrunde liegende Signal erfordert.
Klärung von Limitationen: Die Arbeit grenzt explizit ab, wann Early Stopping vorteilhaft ist bzw. wann nicht, hebt insbesondere die Interaktion zwischen expliziter Ridge-Regularisierung und Early Stopping hervor und identifiziert spezifische Lernraten-Schedules, die Early Stopping unwirksam machen.

Die Autoren kommen zu dem Schluss, dass die aktuelle Analyse auf lineare Modelle beschränkt ist, der Rahmen jedoch eine Grundlage für das Verständnis komplexerer Modelle, wie etwa zweischichtiger neuronaler Netze, bietet und Wege aufzeigt, diese Ergebnisse auf stochastischen Gradientenabstieg und adaptive Optimierungsmethoden zu erweitern.