🤖 machine learning

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

Dieses Paper schlägt ein analytisches Framework vor, das auf der Rademacher-Komplexität mit einer L1-Norm basiert, um die optimale Zeit für das Early Stopping von linearen Regressionsmodellen ohne die Notwendigkeit von Trainingsdaten oder probabilistischen Annahmen zu schätzen, wobei dessen Anwendbarkeit auf nichtlineare neuronale Netze durch Linear Probing demonstriert wird.

Ursprüngliche Autoren: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Veröffentlicht 2026-08-26

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

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 Training eines Computers zur Erkennung von Mustern – sei es die Identifizierung einer Katze in einem Foto oder die Vorhersage eines Aktienkurses – erfordert eine feine Balance. Die Maschine lernt durch das Betrachten von Beispielen und passt ihre internen Einstellungen an, um die gesehenen Daten abzubilden. Wenn sie jedoch zu perfekt lernt, beginnt sie, die spezifischen Eigenheiten dieser Beispiele auswendig zu lernen, anstatt die zugrunde liegenden Regeln zu verstehen. Dies ist ein wenig wie ein Schüler, der die Antworten auf eine Übungsprüfung auswendig lernt, aber bei der echten Prüfung scheitert, weil er die Logik nicht auf neue Fragen anwenden kann. In der Welt der künstlichen Intelligenz ist dieses Unvermögen zur Generalisierung eine große Hürde. Um dies zu verhindern, nutzen Forscher oft eine Strategie namens „Early Stopping“ (vorzeitiger Abbruch), bei der sie den Lernprozess zum genau richtigen Zeitpunkt stoppen – nachdem das Modell die Regeln gelernt hat, aber bevor es beginnt, das Rauschen auswendig zu lernen. Die Herausforderung bestand schon immer darin, genau zu wissen, wann dieser Moment eintritt. Traditionell erfordert das Finden dieses optimalen Punktes, den Trainingsprozess mehrmals auf separaten Datensätzen durchzuführen, eine Methode, die langsam, rechenintensiv und oft auf Vermutungen basierend ist.

Ein Team von Forschern der Université Paris-Saclay hat einen neuen Weg vorgeschlagen, um dieses Timing-Problem ohne die Notwendigkeit wiederholter Versuche zu lösen. Anstatt zu raten oder zusätzliche Simulationen durchzuführen, entwickelten sie eine mathematische Methode, die den idealen Stopppunkt direkt aus den Daten selbst vorhersagen kann. Ihr Ansatz stützt sich auf ein Konzept, das als Rademacher-Komplexität bekannt ist, welches im Wesentlichen misst, wie gut ein Modell zwischen echten Mustern und zufälligem Rauschen unterscheiden kann. Durch die Verwendung dieses Maßstabs entwickelten die Forscher eine Regel, die einem Computer genau sagt, wann er mit dem Lernen aufhören soll. Was ihre Arbeit auszeichnet, ist, dass sie keine Annahmen über die Form oder Verteilung der Daten erfordert, was eine häufige Voraussetzung früherer Methoden war. Darüber hinaus fanden sie heraus, dass die Verwendung einer spezifischen Art der Fehlermessung, bekannt als L1-Norm, signifikant genauere Vorhersagen lieferte als die in der Fachwelt üblichen Standardmethoden.

Die Forscher konzentrierten sich in ihrer ersten Arbeit auf lineare Modelle, die einfachste Art von Algorithmen des maschinellen Lernens, zeigten jedoch auf, dass sich ihre Erkenntnisse auf komplexe, nicht-lineare neuronale Netze erweitern lassen. Um ihre Theorie zu testen, wandten sie ihre Methode auf ein klassisches Problem an: die Unterscheidung zwischen handgeschriebenen Ziffern. In einem Experiment trainierten sie ein neuronales Netz, um zwischen den Zahlen drei und fünf aus einem Datensatz von über zehntausend Bildern zu unterscheiden. Mit ihrer neuen Regel berechnete das System eine Stoppzeit von 342 Schritten. Als sie dies mit der tatsächlichen optimalen Stoppzeit verglichen, die durch das Durchlaufen des vollständigen Trainingsprozesses und die Überprüfung eines separaten Testdatensatzes ermittelt wurde, lag das reale Optimum bei 357 Schritten. Der Unterschied war vernachlässigbar, und die Leistung des Modells zum vorhergesagten Zeitpunkt war nahezu identisch mit der Leistung des Modells zum wahren Optimum. In einem anderen Test mit den Zahlen Null und Eins betrug die vorhergesagte Stoppzeit 415 Schritte, während das tatsächliche Optimum bei 418 Schritten lag. In beiden Fällen vermied das mit ihrer Regel trainierte Modell die Falle des Overfittings und erreichte die bestmögliche Genauigkeit für ungesehene Daten.

Die Studie zeigte auch, dass die Methode am besten funktioniert, wenn eine große Menge an Daten im Verhältnis zur Komplexität des Modells vorhanden ist. Als die Forscher Szenarien mit weniger Datenpunkten testeten, wurde die Methode weniger präzise und schlug teilweise eine Stoppzeit von Null vor, was bedeutet, dass das Modell gar nicht erst trainiert werden sollte. Dies deckt sich mit dem Verständnis, dass komplexe Modelle ausreichend Daten benötigen, um allgemeine Regeln zu lernen. Die Forscher verglichen ihren neuen Ansatz auch mit älteren Techniken, die auf anderen mathematischen Annahmen über die Daten beruhen. Sie fanden heraus, dass ihr Ansatz, der die L1-Norm für die Berechnung verwendet, konsistent viel näher am wahren Optimum liefernde Stoppzeiten produzierte als die älteren Methoden. Dies deutet darauf hin, dass die Art und Weise, wie der Fehler gemessen wird, genauso wichtig ist wie die Stoppregel selbst.

Vielleicht am wichtigsten ist, dass die Forscher zeigten, dass vorzeitiger Abbruch nicht nur ein theoretisches Konzept, sondern in vielen Fällen eine praktische Notwendigkeit ist. Sie berechneten, was passieren würde, wenn das Training unbegrenzt fortgesetzt würde. In den von ihnen untersuchten Beispielen verschlechterte sich die Leistung des Modells bei neuen Daten tatsächlich, wenn das Training über den optimalen Punkt hinaus fortgesetzt wurde, was bestätigt, dass Early Stopping verhindert, dass das Modell degradiert. Sie stellten jedoch auch fest, dass in einigen spezifischen, hochkomplexen Szenarien, in denen das Modell weit mehr Parameter als Datenpunkte besitzt, ein Fortsetzen des Trainings letztendlich zu besseren Ergebnissen führen könnte – ein Phänomen, das als „benign overfitting“ (gutartiges Overfitting) bekannt ist. Ihre Methode hilft dabei, zu identifizieren, in welcher Situation sich ein Nutzer befindet, sodass er entscheiden kann, ob er vorzeitig stoppt oder weitermacht.

Indem sie einen Weg aufzeigen, die optimale Stoppzeit zu berechnen, ohne den vollständigen Trainingsprozess durchlaufen zu müssen, bietet diese Arbeit einen effizienteren Pfad für die Entwicklung zuverlässiger künstlicher Intelligenz. Sie macht das Bedürfnis nach Versuch und Irrtum überflüssig und spart Zeit sowie Rechenressourcen. Die Methode ist besonders nützlich für Situationen, in denen Daten reichlich vorhanden, aber die Rechenleistung begrenzt ist oder die Kosten für das Training hoch sind. Während sich die aktuelle Studie auf lineare Modelle und spezifische Arten von Daten konzentriert, glauben die Forscher, dass ihr Rahmenwerk für komplexere Systeme und unterschiedliche Arten von Ausgaben angepasst werden kann. Ihre Arbeit liefert eine klare, datengestützte Antwort auf eine Frage, die lange Zeit nur durch Raten beantwortet werden konnte, und bietet ein präziseres Werkzeug, um den Kompromiss zwischen Lernen und Auswendiglernen zu navigieren.

Technische Zusammenfassung: Eine datenabhängige Early-Stopping-Regel unter Verwendung der Rademacher-Komplexität mit der L1-Norm

Problemstellung
Das Training neuronaler Netze erfordert ein Abwägen zwischen dem Anpassen an Trainingsdaten und dem Erreichen einer robusten Leistung bei ungesehenen Eingaben, einer Eigenschaft, die als Generalisierbarkeit bekannt ist. Diese wird durch die Differenz zwischen dem empirischen Risiko ( $L_S$ ) und dem erwarteten Populationsrisiko ( $L_D$ ) bestimmt. Der Generalisierungsverlust ( $L_G$ ) ist als die Differenz zwischen diesen beiden definiert. Während des Gradientenabstiegs (GD) sinkt $L_S$ typischerweise, während $L_G$ steigt, was einen „Bias-Varianz-Trade-off“ erzeugt. Das Ziel des Early Stopping besteht darin, den optimalen Zeitpunkt $t^*$ zu finden, der die Summe $L_S + L_G$ minimiert.

Klassischerweise wird $t^*$ numerisch durch die Überwachung eines separaten Testdatensatzes ( $S_{test}$ ) geschätzt. Alternativ existieren analytische Ansätze mittels Random Matrix Theory (RMT), diese beruhen jedoch oft auf starken probabilistischen Annahmen, wie etwa Gauß-verteilten Daten oder spezifischen Eigenwertverteilungen (z. B. Marchenko–Pastur) der Kovarianzmatrix der Daten. Diese Arbeit adresset das Bedürfnis nach einer analytischen Early-Stopping-Regel, die keine separaten Testsets oder restriktiven Verteilungsannahmen erfordert.

Methodik
Die Autoren schlagen einen analytischen Rahmen vor, der auf der Rademacher-Komplexität (RC) basiert, um den optimalen Stoppzeitpunkt ohne Durchführung von Gradientenabstieg zu schätzen. Die Methodik konzentriert sich auf lineare Modelle und lineare Regression, mit Erweiterungen auf nichtlineare Netzwerke via „Linear Probing“.

L1-Norm-Formulierung: Im Gegensatz zu vielen bestehenden RC-Bounds, die die L2-Norm verwenden, drückt diese Arbeit die Rademacher-Komplexität unter Verwendung der L1-Norm aus. Diese Wahl ist motiviert durch das Bestreben, eine datenabhängige Konstante $M$ (eine Schranke für den Verlust) aus der Generalisierungsfehler-Schranke zu eliminieren. Durch das Setzen von $p=1$ in der allgemeinen $L_p$ -Norm-Schranke leiten die Autoren eine obere Schranke für den Populationsverlust ( $L_D$ ) her, die nur vom empirischen Fehlervektor und der Modellnorm abhängt und somit die explizite Abhängigkeit von $M$ vermeidet.
Gradientenfluss-Dynamik: Das Problem wird in kontinuierlicher Zeit mittels Gradient Flow (GF) modelliert. Die Autoren analysieren die Dynamik des Trainingsfehlervektors $v(t)$ und der Modellparameter $a(t)$ . Die obere Schranke des Populationsverlusts, bezeichnet als $L^*_D(t)$ , zeigt sich als „U-förmig“: Sie sinkt zunächst, während der empirische Verlust abnimmt, und steigt später an, wenn die Modellnorm wächst.
Analytisches Stoppkriterium ( $t^+$ ): Der Kernbeitrag ist die Ableitung eines datenabhängigen Kriteriums $C(s)$ $C (s)$ , das sicherstellt, dass $L^*_D(t)$ $L_{D}^{*} (t)$ für alle $t \leq s$ $t \leq s$ fallend ist.
- Die Autoren zerlegen die Eigenwerte der Datenkovarianzmatrix in „informative“ (große) und „Störungs“-Sets (kleine).
- Sie definieren eine Funktion $\Phi(t)$ , die diese Eigenwerte und die Fehlerdynamik beinhaltet.
- Die Stoppzeit $t^+$ ist definiert als das Supremum der Zeit $s$ , für die $\Phi(t) > 0$ für alle $t \in [0, s)$ gilt.
- Mathematisch gesehen ist $t^+$ der erste Zeitpunkt, an dem $\Phi(t)$ die Null kreuzt. Es wird bewiesen, dass $t^+$ eine untere Schranke für die Schätzung der wahren optimalen Zeit $t^*$ ist (d. h. $t^+ \leq t^*$ ). Unter spezifischen Bedingungen (z. B. wenn das wahre Minimum innerhalb des ersten sign-invarianten Intervalls liegt) gilt $t^+ = t^*$ .
Approximation: Die Arbeit liefert eine einfache Approximation $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ , welche einer Signal-Rausch-Verhältnis (SNR)-Formulierung ähnelt, die in der RMT-Literatur zu finden ist, hier jedoch ohne probabilistische Annahmen hergeleitet wurde.

Hauptbeiträge

Distributionsfreie analytische Schätzung: Die Arbeit führt eine Methode zur analytischen Schätzung der optimalen Early-Stopping-Zeit ein, die ohne die Annahme von Gauß-Daten oder spezifischen Eigenwertverteilungen der Daten funktioniert.
Vorteil der L1-Norm: Die Autoren zeigen theoretisch und numerisch, dass die Verwendung der L1-Norm für die Rademacher-Komplexität eine Schätzung der Stoppzeit ( $t^+$ ) liefert, die der numerischen Optimierung ( $t_{test}$ ) signifikant näher kommt als der L2-Norm-Ansatz.
Fokus auf Unterparametrisierung: Die Methode ist speziell für das unterparametrisierte Regime ( $m \leq n$ ) konzipiert, in dem „Benign Overfitting“ und „Epoch-wise Double Descent“ weniger präsent sind, was Early Stopping zu einer vorteilhaften Strategie macht.
Anwendung von Linear Probing: Obwohl die Theorie für lineare Modelle hergeleitet wurde, wenden die Autoren die Ergebnisse erfolgreich auf nichtlineare neuronale Netze an (speziell auf MNIST-Klassifizierung), indem sie die verborgenen Schichten einfrieren und nur die Ausgabeschicht trainieren (Linear Probing).

Ergebnisse
Die Autoren validieren ihre Methode durch mehrere Beispiele:

Synthetische Gauß-Daten: In binären Klassifikationsaufgaben mit variierenden Stichprobengrößen ( $n=512$ und $n=16384$ ) entsprach die analytische Schätzung $t^+$ exakt der wahren optimalen Zeit $t^*$ im ersten Fall und lieferte im zweiten Fall eine enge untere Schranke. Die auf der L1-Norm basierende Schätzung war konsistent näher am Testset-Optimum als die L2-basierte Schätzung.
MNIST-Klassifikation (3-5 und 0-1): Unter Verwendung eines 4-Schicht-ReLU-Netzwerks mit Linear Probing sagte die Methode die Stoppzeit präzise voraus. Für die 3-5 Klassifikation ergab sich $t^+ = 342$ im Vergleich zum numerischen Optimum $t^* = 357$ und dem Testset-Optimum $t_{test} = 356$ . Für die 0-1 Klassifikation entsprach $t^+ = 415$ dem Wert $t^* = 415$ und lag nahe bei $t_{test} = 418$ .
Vorteilhaftes Stoppen: In allen getesteten Fällen war der Verlust zum geschätzten Stoppzeitpunkt niedriger als der Verlust zum Zeitpunkt unendlichen Trainings ( $L^*_D(t^+) < L^*_D(\infty)$ ), was bestätigt, dass Early Stopping vorteilhaft ist und das „Benign Overfitting“-Regime vermeidet.
Robustheit: Die Methode funktionierte gut über verschiedene Datenverteilungen hinweg (Gauß, Uniform, Pareto), wobei die Leistung mit zunehmendem Verhältnis von Stichproben zu Parametern ( $n/m$ ) besser wurde.

Bedeutung und Ansprüche
Die Arbeit behauptet, dass ihre primäre Bedeutung darin liegt, eine datenabhängige, analytische Early-Stopping-Regel bereitzustellen, die ohne die Notwendigkeit eines separaten Validierungssets oder restriktiver probabilistischer Annahmen über die Datenverteilung operiert. Durch die Nutzung der Rademacher-Komplexität mit der L1-Norm bieten die Autoren ein praktisches Werkzeug zur Bestimmung des Zeitpunkts, an dem das Training linearer Modelle (und via Linear Probing auch bestimmter nichtlinearer Netzwerke) gestoppt werden sollte, um den Generalisierungsfehler zu minimieren. Die Autoren merken bescheiden an, dass die Methode zwar gut für unterparametrisierte Modelle funktioniert, aber nicht für das überparametrisierte Regime intendiert ist, in dem „Benign Overfitting“ auftritt. Sie identifizieren zudem zukünftige Forschungsrichtungen, einschließlich der direkten Anwendung auf voll nichtlineare Modelle, vektorielle Ausgaben und den Umgang mit zufälligem Rauschen in den Eingangsdaten.

Mehr davon