How abundant are good interpolators?

Résumé technique : « Quelle est l'abondance des bons interpolateurs ? »

Énoncé du problème
Le papier étudie les propriétés de généralisation de l'ensemble des classifieurs linéaires interpolants dans des régimes surparamétrés. Plus précisément, il considère un ensemble de données étiquetées $(X_i, y_i)_{i=1}^n$ dans $\mathbb{R}^d$ où $n/d \to \alpha$ avec $\alpha$ petit (surparamétrage élevé). Les auteurs définissent l'ensemble $S$ des classifieurs linéaires de norme unitaire $\theta$ qui classent correctement tous les points d'entraînement avec une marge fixe $\kappa$. La question centrale est la suivante : quelle est la performance de généralisation typique d'un classifieur choisi uniformément au hasard dans $S$ ?

Cette enquête aborde le phénomène du « surapprentissage bénin » (benign overfitting), où des modèles présentant une erreur d'entraînement nulle généralisent bien. Bien qu'il soit connu que la régularisation implicite (par exemple, via la descente de gradient) sélectionne des interpolateurs spécifiques dotés de bonnes performances, l'article demande si la plupart des interpolateurs partagent cette propriété ou si les « bons » interpolateurs sont des exceptions rares au sein de l'espace de solution.

Méthodologie
Les auteurs emploient des outils de la physique statistique, plus précisément la théorie des grandes déviations et la méthode de la réplique (adaptée à des preuves probabilistes rigoureuses), pour analyser la géométrie de l'espace de solution $S$.

1. Modèles de données : L'analyse est menée sous deux distributions de génération de données distinctes avec un rapport signal sur bruit (SNR) constant $\lambda$ :
   • Un modèle de mélange gaussien (GMM).
   • Un modèle logistique avec des caractéristiques gaussiennes.
2. Principe des grandes déviations (LDP) : L'approche technique centrale consiste à établir un principe de grandes déviations « quenched » pour le chevauchement (overlap) $\langle \theta, \theta^* \rangle / d$ entre un interpolateur aléatoire $\theta$ et la direction du signal réel $\theta^*$. L'objectif est de caractériser le taux exponentiel du volume de l'ensemble des interpolateurs ayant un chevauchement $x$ spécifique.
3. Formulation variationnelle : Les auteurs dérivent une fonction de taux $\Phi(x, q)$ définie sur le chevauchement $x$ et un paramètre $q$ (représentant le chevauchement entre deux interpolateurs aléatoires indépendants). Le volume de l'espace de solution est caractérisé par un problème de point selle impliquant $\sup_x \inf_q \Phi(x, q)$.
4. Techniques de preuve :
   • Mesure de référence gaussienne : Les preuves relaxent la contrainte sphérique pour une mesure gaussienne complète afin d'utiliser la concentration de la mesure et les techniques d'interpolation gaussienne (suivant l'approche de Talagrand pour le perceptron sphérique).
   • Méthode de la cavité (Cavity Method) : Les auteurs utilisent un argument de « cavité » pour ajouter des contraintes (points de données) un par un, reliant la liberté de l'énergie de $n$ points à celle de $n-1$ points.
   • Contraintes strictes : Une étape critique consiste à convertir les fonctions de mollification lissées utilisées dans l'analyse gaussienne vers les contraintes de fonctions échelons strictes définissant les interpolateurs ($y_i \langle X_i, \theta \rangle \ge \kappa$). Cela nécessite de gérer les composantes de signal non gaussiennes et d'établir des bornes de concentration pour les mesures de Gibbs avec des contraintes strictes.
   • Comparaison bayésienne : Le papier analyse également la distribution a posteriori (estimateur bayésien optimal) pour dériver une base de référence pour la performance optimale, notant que le postérieur satisfait une relation spécifique (ligne de Nishimori) entre les chevauchements que la mesure uniforme sur les interpolateurs ne satisfait pas.

Contributions clés et résultats

1. Concentration de la performance typique : Le papier établit que, avec une haute probabilité sur les données, l'erreur de généralisation d'un interpolateur uniformément aléatoire se concentre exponentiellement autour d'une valeur « typique » unique $x^*$. Cela confirme une conjecture de Theisen, Klusowski et Mahoney [TKM21] concernant l'existence d'une erreur typique, bien que l'article affine les conditions sous lesquelles cela est vrai.
2. Rareté des bons interpolateurs : La principale conclusion est que, dans le régime surparamétré avec un SNR constant, la performance typique $x^*$ est nettement moins bonne que la performance atteinte par les algorithmes efficaces.
   • Les auteurs comparent $x^*$ à la performance d'un estimateur de programmation linéaire (LP) et de la descente de gradient (GD) sur la perte logistique.
   • Les simulations numériques et les bornes théoriques montrent que $x^* < x_{LP}$ et $x^* < x_{GD}$ pour une large gamme de paramètres.
   • Par conséquent, les « bons » interpolateurs (ceux qui performent aussi bien que LP ou GD) constituent une fraction exponentiellement petite de l'ensemble total des interpolateurs.
3. Dépendance au SNR : Le papier clarifie que l'abondance de bons interpolateurs dépend fortement du SNR. Alors que des analyses heuristiques antérieures suggéraient que les bons classifieurs sont abondants, ces analyses supposaient implicitement un SNR élevé (où la séparation des classes croît avec la dimension). Dans le régime à SNR constant analysé ici, les bons interpolateurs sont extrêmement rares, faisant du succès de la régularisation implicite un phénomène non trivial.
4. Caractérisation de l'optimalité bayésienne : Les auteurs fournissent une caractérisation asymptotique de la performance bayésienne optimale ($x_{Bayes}$) sous les deux modèles de données, montrant que les algorithmes efficaces (LP et GD) surpassent significativement l'interpolateur typique et se rapprochent davantage de la limite bayésienne optimale que l'échantillonnage aléatoire du ensemble de solutions.

Signification et affirmations
Le papier prétend résoudre la question de l'« abondance des bons interpolateurs » dans le régime à SNR constant et surparamétré. Sa signification réside dans la démonstration que :

• La régularisation implicite est essentielle : Le fait que les algorithmes efficaces (GD, LP) surpassent largement un interpolateur aléatoire suggère que le succès de généralisation des modèles surparamétrés n'est pas une propriété inhérente de l'ensemble de solutions $S$, mais plutôt une conséquence du chemin spécifique emprunté par les algorithmes d'optimisation (régularisation implicite).
• Réfutation de l'abondance heuristique : Les résultats contredisent les heuristiques suggérant que « les bons classifieurs sont abondants » dans le régime d'interpolation, montrant au contraire que cette abondance n'apparaît que dans les limites de SNR élevé.
• LDP rigoureux pour les interpolateurs : Le travail fournit un principe de grandes déviations rigoureux pour l'erreur de généralisation des interpolateurs uniformes, un résultat qui était auparavant heuristique ou limité à des hypothèses spécifiques de SNR élevé.

Les auteurs déclarent explicitement que leurs conclusions soulignent la nature non triviale du surapprentissage bénin dans ce contexte, où la vaste majorité des solutions au problème d'interpolation sont de piètres généralisateurs, et seule une infime sous-partie sélectionnée algorithmiquement performe de manière satisfaisante.