🤖 machine learning

On Regularization via Early Stopping for Least Squares Regression

Cet article caractérise la dynamique de la descente de gradient à lot complet (full-batch) discrète pour la régression linéaire afin de démontrer que l'arrêt précoce produit une solution équivalente à la régression de Ridge généralisée à norme minimale, prouvant ainsi ses bénéfices de généralisation à travers des spectres de données et des programmes de taux d'apprentissage arbitraires, tout en fournissant une estimation du temps d'arrêt optimal.

Auteurs originaux : Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

Publié 2026-07-07

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous enseignez à un étudiant (le modèle de machine learning) comment résoudre un problème de mathématiques (prédire des résultats à partir de données). Vous avez un manuel avec des exemples (les données d'entraînement), et vous voulez que l'étudiant apprenne les règles sous-jacentes afin qu'il puisse résoudre de nouveaux problèmes qu'il n'a jamais vus auparavant (la généralisation).

Vous utilisez la stratégie d'Arrêt Précoce (Early Stopping). Habituellement, les enseignants laissent les étudiants étudier jusqu'à ce qu'ils réussissent parfaitement chaque exercice du manuel. Mais parfois, si un étudiant étudie trop longtemps, il commence à mémoriser les particularités spécifiques du manuel (comme la police de caractères ou la texture du papier) plutôt que les véritables règles mathématiques. C'est ce qu'on appelle le "surapprentissage" (overfitting), et cela fait échouer l'étudiant lors de nouveaux examens.

L'Arrêt Précoce est la stratégie qui consiste à dire : « D'accord, arrête d'étudier maintenant, avant de commencer à mémoriser le bruit. »

Voici ce que les auteurs ont découvert, expliqué simplement :

1. La « Main Invisible » de l'arrêt précoce

Les auteurs voulaient savoir : Que se passe-t-il exactement dans le cerveau de l'étudiant lorsque nous l'arrêtons prématurément ?

Ils ont découvert que l'arrêt précoce est mathématiquement identique à un type spécifique de « discipline » appelée Régression Ridge.

L'analogie : Imaginez que la Régression Ridge soit comme donner un sac à dos lourd à l'étudiant. Le sac à dos le force à garder ses réponses simples et proches de zéro (le point de départ).
La découverte : Le papier prouve que si vous arrêtez l'étudiant au bon moment, son état cérébral est exactement le même que s'il avait porté ce sac à dos lourd pendant tout le temps. Vous n'avez pas besoin d'ajouter physiquement le sac à dos (la pénalité mathématique) ; il vous suffit d'arrêter la leçon au moment parfait, et le résultat est le même.

2. Le « Bouton de Volume » pour différentes fréquences

Les auteurs ont observé comment l'étudiant apprend différentes parties du problème. Ils ont réalisé que les données ne sont pas un seul gros bloc, mais sont composées de nombreuses « fréquences » ou directions différentes (certaines faciles, d'autres difficiles).

L'analogie : Pensez aux données comme à une symphonie. Certains instruments jouent des notes fortes et évidentes (motifs faciles), tandis que d'autres jouent des notes faibles et complexes (motifs difficiles).
La découverte : Lorsque vous utilisez la Descente de Gradient (la méthode standard d'enseignement), l'étudiant apprend très vite les notes fortes. Si vous continuez, l'étudiant commence à essayer d'apprendre les notes faibles, mais ce faisant, il commence à entendre du « statique » (du bruit) dans les notes faibles et à mémoriser ce statique comme s'il s'agissait de musique.
Le résultat : L'arrêt précoce agit comme un bouton de volume. Il baisse le volume sur les notes complexes et faibles juste assez pour que l'étudiant entende la musique mais ignore le statique. Le papier donne une formule pour déterminer exactement comment tourner le bouton de volume.

3. Le « Taux d'Apprentissage » est crucial

Une partie cruciale du papier concerne les Taux d'Apprentissage (Learning Rates). C'est la vitesse à laquelle l'étudiant fait un pas lorsqu'il apprend.

Rythme constant : Si l'étudiant marche à un rythme régulier et lent, il apprend les notes fortes, puis les notes faibles, et finit par entendre du statique. Ici, l'arrêt préci fonctionne très bien.
Rythme dégressif : Si l'étudiant commence vite et ralentit ensuite trop rapidement (comme une décroissance exponentielle), il pourrait arrêter d'apprendre les notes faibles avant même d'atteindre le statique. Dans ce cas, l'arrêt précoce n'aide pas beaucoup car il ralentissait déjà de lui-même.
La thèse du papier : Les auteurs fournissent un manuel de règles. Ils disent : « Si votre programme de taux d'apprentissage ressemble à X, alors l'arrêt précoce est un super-pouvoir. S'il ressemble à Y, l'arrêt précoce est inutile. »

4. La « Formule Magique » pour savoir quand s'arrêter

La partie la plus pratique du papier est une formule qu'ils ont dérivée pour vous dire exactement quand vous arrêter.

Les entrées : Vous devez connaître trois choses :
1. Combien de « bruit » se trouve dans votre manuel (à quel point les données sont désordonnées).
2. Quelle est la force du « signal » (à quel point les règles réelles sont claires).
3. À quelle vitesse l'étudiant marche (le taux d'apprentissage).
La sortie : La formule recrache un nombre spécifique d'étapes (itérations).
Le test : Les auteurs ont testé cela sur des données réelles (comme des chiffres manuscrits et des images). Ils ont constaté que leur formule prédisait le « point idéal » presque parfaitement. Si on s'arrêtait au moment suggéré par leur formule, l'étudiant était plus performant que s'il avait étudié plus longtemps ou moins longtemps.

5. Quand NE PAS s'arrêter prématurément

Le papier prévient également que l'arrêt précoce n'est pas toujours la solution.

L'analogie : Si vous portez déjà un sac à dos très lourd (une forte pénalité mathématique appelée « Régularisation Ridge »), vous n'avez pas besoin de vous arrêter prématurément. Le sac à dos fait déjà le travail de maintenir l'étudiant dans la simplicité.
La thèse : Si le « sac à dos » est trop lourd, l'arrêt précoce nuit en réalité à la performance. L'étudiant doit continuer pour terminer le travail. Les auteurs prouvent mathématiquement que si la pénalité est suffisamment forte, vous devez simplement laisser l'étudiant étudier jusqu'à ce qu'il ait terminé.

Résumé

Ce papier est un « manuel d'utilisation » pour la stratégie de l'Arrêt Précoce.

Il explique pourquoi cela fonctionne (c'est la même chose qu'ajouter une pénalité mathématique).
Il explique quand cela fonctionne (cela dépend de la vitesse à laquelle vous apprenez et de la désorganisation des données).
Il vous donne un calculateur pour trouver le moment exact de l'arrêt, ce qu'ils ont prouvé fonctionner sur des données réelles.

Ils n'ont pas inventé une nouvelle façon d'enseigner ; ils ont simplement compris la physique précise de quand débrancher la prise pour obtenir les meilleurs résultats.

Résumé technique : Régularisation par arrêt précoce pour la régression des moindres carrés

Énoncé du problème

L'article traite du défi fondamental consistant à comprendre les effets de l'arrêt précoce (early stopping) sur les paramètres et les capacités de généralisation des modèles d'apprentissage automatique, spécifiquement dans le contexte de la régression linéaire. Bien que l'arrêt précoce soit une technique de régularisation largement utilisée, ses propriétés théoriques restent incomplètement comprises, particulièrement pour la descente de gradient en mode full-batch discrète avec des programmes de taux d'apprentissage arbitraires et des distributions de données variées.

La littérature existante repose souvent sur des hypothèses fortes, telles que la dynamique de flux de gradient en temps continu ou des hypothèses gaussiennes sur la matrice de caractéristiques, pour dériver des règles d'arrêt. Ces approches ne parviennent pas à quantifier le temps d'arrêt optimal sous des programmes de taux d'apprentissage non constants et pratiques, ni à expliquer des phénomènes comme le « grokking » (où les modèles surajustent initialement avant de généraliser) dans des contextes discrets. De plus, la relation précise entre l'arrêt précoce et la régularisation $L_2$ explicite (ridge), ainsi que les conditions sous lesquelles l'arrêt précoce est bénéfique ou préjudiciable, nécessitent une caractérisation plus rigoureuse sans hypothèses distributionnelles restrictives.

Méthodologie

Les auteurs analysent la dynamique discrète de la descente de gradient full-batch pour la régression linéaire, évitant l'approximation par flux de gradient en temps continu. La principale contribution méthodologique est la dérivation d'expressions exactes et en forme close pour la trajectoire des paramètres $\beta_k$ après $k$ étapes.

Les composantes méthodologiques clés incluent :

Décomposition spectrale : L'analyse est menée dans la base propre de la matrice de covariance des échantillons $X^T X$ . Les auteurs définissent une fonction $\phi(k; \zeta, \{\eta_i\})$ qui capture l'effet cumulatif d'un programme de taux d'apprentissage $\{\eta_i\}$ sur une valeur propre $\zeta$ spécifique.
Formulation de la trajectoire exacte : En utilisant cette fonction, les auteurs dérivent une formule explicite pour $\beta_k$ qui est valable pour toute matrice de données $X$ , tout programme de taux d'apprentissage et toute initialisation. Cette formule décompose l'erreur en une composante de signal (dépendante de l'initialisation et des paramètres réels) et une composante de bruit (dépendante des résidus).
Analyse du risque : L'espérance du risque excédentaire est analysée en prenant les espérances sur le bruit et, sous une hypothèse de priorité sphérique, sur le signal. Les auteurs différencient le risque par rapport au nombre d'itérations (en le traitant comme une variable continue via l'Hypothèse 2) pour identifier les points critiques.
Preuves d'équivalence : L'article établit des équivalences mathématiques entre les solutions d'arrêt précoce et les solutions de problèmes de régression ridge généralisée, permettant une comparaison directe des effets de régularisation.

Contributions clés

1. Trajectoires exactes pour les dynamiques discrètes

L'article fournit la Proposition 1, qui donne des formules exactes pour les dynamiques discrètes de $\beta_k$ pour le problème de régression ridge à noyau. Contrairement aux travaux antérieurs, ces formules ne font aucune hypothèse sur la distribution des données, le programme de taux d'apprentissage ou la distribution du bruit. Les auteurs fournissent des expressions en forme close pour $\phi$ sous divers programmes courants, incluant le taux constant, la décroissance polynomiale, la décroissance additive constante et la décroissance exponentielle (en utilisant les fonctions Gamma et les symboles $q$ -Pochhammer).

2. Équivalence avec la régression ridge généralisée

Les auteurs prouvent le Théorème 5, démontrant que pour des données génériques et des programmes de taux d'apprentissage arbitraires, la solution obtenue après $T$ itérations d'arrêt précoce (avec $\mu=0$ ) est équivalente à la solution de norme minimale d'un problème de régression ridge généralisée. La matrice de régularisation $D$ dans ce problème généralisé est explicitement déterminée par le programme de taux d'apprentissage et le temps d'arrêt.
Inversement, le Théorème 6 montre que toute solution de norme minimale d'un problème de régression ridge standard peut être obtenue via l'arrêt précoce si l'on peut assigner un taux d'apprentissage distinct à chaque espace propre de la matrice de covariance des échantillons.

3. Conditions de bénéfice et de préjudice

L'article établit des conditions suffisantes pour déterminer quand l'arrêt précoce améliore la performance de généralisation :

Théorème 8 (Bénéfique) : L'arrêt précoce est bénéfique si le programme de taux d'apprentissage permet au facteur de rétrécissement (shrinkage factor) $\phi(k)$ de décroître suffisamment rapidement pour que la limite du rapport $\phi(k)/\phi(0)$ soit inférieure à un seuil déterminé par le rapport signal sur bruit. Cela est vrai pour les programmes constants, à décroissance linéaire et autres programmes où la taille de l'étape cumulée diverge.
Théorème 9 (Non bénéfique) : L'arrêt précoce n'est pas bénéfique si le taux d'apprentissage décroît trop rapidement (par exemple, une décroissance polynomiale ou exponentielle rapide) de sorte que le facteur de rétrécissement n'atteigne pas le seuil nécessaire. Dans ces cas, le risque continue de diminuer avec la poursuite de l'entraînement.
Théorème 10 (Régularisation Ridge) : Ces conditions sont étendues au cas où la régularisation ridge explicite ( $\mu > 0$ ) est présente. Une conclusion clé est que si le paramètre de régularisation explicite $\mu$ dépasse une valeur critique ( $\mu \ge \tau^2 / (n\sigma^2)$ ), l'arrêt précoce n'apporte aucun bénéfice supplémentaire.

4. Estimation du temps d'arrêt optimal

Les auteurs proposent une estimation du temps d'arrêt optimal (Équation 31) basée sur le budget cumulé du taux d'apprentissage $\sum \eta_i$ . L'estimation est dérivée en égalisant le facteur de rétrécissement au équilibre optimal entre le signal et le bruit pour une valeur propre représentative. Cette estimation généralise les résultats antérieurs du régime de flux de gradient aux dynamiques discrètes avec des spectres arbitraires et des taux d'apprentissage non constants.

Résultats et validation empirique

Les conclusions théoriques sont validées par des expériences sur des données synthétiques et des jeux de données réels (MNIST et CIFAR10).

Précision de l'estimation : L'estimation du temps d'arrêt proposé (Équation 31) correspond étroitement aux temps d'arrêt optimaux observés empiriquement à travers divers programmes de taux d'apprentissage (constant, polynomial, linéaire, exponentiel, cosine annealing et aléatoire).
Dépendance au régime : Les expériences confirment la prédiction théorique selon laquelle l'arrêt précoce est bénéfique lorsque le paramètre ridge explicite $\mu$ est inférieur au paramètre ridge optimal $\mu^*$ , mais devient préjudiciable (ou inutile) lorsque $\mu \ge \mu^*$ .
Sensibilité au programme : Les résultats démontrent que l'itération à laquelle l'optimum se produit varie considérablement selon le programme de taux d'apprentissage, mais que le budget cumulé des taux d'apprentissage sert de prédicteur robuste pour le point d'arrêt optimal.
Grokking : L'analyse suggère que pour de nombreux programmes de taux d'apprentissage courants (où la taille de l'étape cumulée diverge), les modèles linéaires ne présentent pas de « grokking » (généralisation tardive après surapprentissage) ; ils présentent plutôt le compromis biais-variance classique où l'arrêt précoce est optimal.

Signification et revendications

L'article prétend fournir une caractérisation non asymptotique et indépendante de la distribution de l'arrêt précoce dans la régression linéaire. Sa signification réside dans :

Pont entre théorie et pratique : En s'éloignant du flux de gradient en temps continu et des hypothèses gaussiennes, les résultats s'appliquent à des scénarios d'entraînement discrets et pratiques avec des programmes de taux d'apprentissage arbitraires.
Perspective unificatrice : Il unifie formellement l'arrêt précoce avec la régularisation ridge généralisée, montrant que la régularisation « implicite » de l'arrêt précoce est mathématiquement équivalente à une pénalité $L_2$ explicite dépendante des données.
Orientation pratique : Il offre une estimation concrète, théoriquement fondée, du temps d'arrêt optimal qui dépend uniquement de quantités observables (rapport signal sur bruit, spectre des valeurs propres et programme de taux d'apprentissage), plutôt que de la connaissance du signal sous-jacent réel.
Clarification des limites : Le travail délimite explicitement quand l'arrêt précoce est bénéfique par rapport à quand il ne l'est pas, soulignant particulièrement l'interaction entre la régularisation ridge explicite et l'arrêt précoce, et identifiant les programmes de taux d'apprentissage spécifiques qui rendent l'arrêt précoce inefficace.

Les auteurs concluent que bien que l'analyse actuelle soit limitée aux modèles linéaires, le cadre fournit une base pour comprendre des modèles plus complexes, tels que les réseaux de neurones à deux couches, et suggère des directions futures pour étendre ces résultats à la descente de gradient stochastique et aux méthodes d'optimisation adaptatives.