How abundant are good interpolators?

Technische Samenvatting: "Hoe overvloedig zijn goede interpolatoren?"

Probleemstelling
Het artikel onderzoekt de generalisatie-eigenschappen van de verzameling interpolerende lineaire classificaties in overgeparametriseerde regimes. Specifiek wordt een gelabelde dataset $(X_i, y_i)_{i=1}^n$ in $\mathbb{R}^d$ beschouwd waarbij $n/d \to \alpha$ met $\alpha$ klein (hoge overparametrisatie). De auteurs definiëren de verzameling $S$ van eenheidsnorm lineaire classificatoren $\theta$ die alle trainingspunten correct classificeren met een vaste marge $\kappa$. De centrale vraag is: Wat is de typische generalisatieprestatie van een classificator die willekeurig wordt gekozen uit $S$?

Deze vraagstelling behandelt het fenomeen van "benigne overfitting", waarbij modellen met een trainingsfout van nul goed generaliseren. Hoewel impliciete regularisatie (bijv. via gradiëntafdaling) bekend staat om het selecteren van specifieke interpolatoren met goede prestaties, vraagt dit artikel zich af of de meeste interpolatoren deze eigenschap delen of dat "goede" interpolatoren zeldzame uitzonderingen zijn binnen de oplossingsruimte.

Methodologie
De auteurs maken gebruik van instrumenten uit de statistische fysica, specifweg de theorie van grote afwijkingen (large deviations) en de replica-methode (aangepast naar rigoureuze probabilistische bewijzen), om de geometrie van de oplossingsruimte $S$ te analyseren.

1. Datamodellen: De analyse wordt uitgevoerd onder twee verschillende datagenererende distributies met een constante signaal-ruisverhouding (SNR) $\lambda$:
   • Een Gaussian Mixture Model (GMM).
   • Een logistisch model met Gaussische kenmerken.
2. Large Deviation Principle (LDP): De kern van de technische aanpak is het vaststellen van een "quenched" large deviation principle voor de overlap $\langle \theta, \theta^* \rangle / d$ tussen een willekeurige interpolator $\theta$ en de ware signaalrichting $\theta^*$. Het doel is om de exponentiële snelheid van het volume van de verzameling interpolatoren met een specifieke overlap $x$ te karakteriseren.
3. Variationele Formulering: De auteurs leiden een snelheidsfunctie $\Phi(x, q)$ af die gedefinieerd is op de overlap $x$ en een parameter $q$ (die de overlap vertegenwoordigt tussen twee onafhankelijke willekeurige interpolatoren). Het volume van de oplossingsruimte wordt gekarakteriseerd door een saddle-point probleem met betrekking tot $\sup_x \inf_q \Phi(x, q)$.
4. Bewijstechnieken:
   • Gaussische Referentiemaat: De bewijzen versoepelen de sferische beperking naar een volledige Gaussische maat om concentratie van maat en Gaussische interpolatietechnieken te kunnen gebruiken (volgens de aanpak van Talagrand voor de sferische perceptron).
   • Cavity-methode: De auteurs gebruiken een "cavity"-argument om beperkingen (datapunten) één voor één toe te voegen, waarbij de vrije energie van $n$ punten wordt gerelateerd aan $n-1$ punten.
   • Hard Constraints: Een cruciale stap is het omzetten van de gladde mollificatie-functies die gebruikt worden in de Gaussische analyse terug naar de harde stapfunctie-beperkingen die de interpolatoren definiëren ($y_i \langle X_i, \theta \rangle \ge \kappa$). Dit vereist het behandelen van niet-Gaussische signaalcomponenten en het vaststellen van concentratie-grenzen voor Gibbs-maten met harde beperkingen.
   • Bayesiaanse Vergelijking: Het artikel analyseert ook de posterior distributie (Bayes-optimale estimator) om een baseline te verkrijgen voor optimale prestaties, waarbij wordt opgemerkt dat de posterior een specifieke relatie (Nishimori-lijn) tussen overlappingen voldoet die de uniforme maat op de interpolatoren niet heeft.

Belangrijkste Bijdragen en Resultaten

1. Concentratie van Typische Prestaties: Het artikel stelt vast dat de generalisatiefout van een willekeurig gekozen interpolator, met een hoge waarschijnlijkheid over de data heen, exponentieel concentreert rond een unieke "typische" waarde $x^*$. Dit bevestigt een conjectuur van Theisen, Klusowski en Mahoney [TKM21] over het bestaan van een typische fout, hoewel het artikel de voorwaarden waaronder dit geldt verfijnt.
2. Zeldzaamheid van Goede Interpolatoren: De belangrijkste bevinding is dat in het overgeparametriseerde regime met een constante SNR, de typische prestatie $x^*$ aanzienlijk slechter is dan de prestatie die wordt bereikt door efficiënte algoritmen.
   • De auteurs vergelijken $x^*$ met de prestaties van een Lineair Programmeren (LP) estimator en Gradiëntafdaling (GD) op de logistische loss.
   • Numerieke simulaties en theoretische grenzen tonen aan dat $x^* < x_{LP}$ en $x^* < x_{GD}$ voor een breed scala aan parameters.
   • Concluderend: "goede" interpolatoren (die net zo goed presteren als LP of GD) vormen een exponentieel klein deel van de totale verzameling interpolatoren.
3. Afhankelijkheid van SNR: Het artikel verduidelijkt dat de overvloed aan goede interpolatoren sterk afhankelijk is van de SNR. Hoewel eerdere heuristische analyses suggereerden dat goede classificatoren overvloedig zijn, gingen die analyses impliciet uit van een hoge SNR (waarbij de klassenseparatie meegroeit met de dimensie). In het geanalyseerde regime met constante SNR zijn goede classificatoren uiterst zeldzaam, waardoor het succes van impliciete regularisatie een niet-trivial fenomeen is.
4. Bayes-Optimale Karakterisering: De auteurs bieden een asymptotische karakterisering van de Bayes-optimale prestatie ($x_{Bayes}$) onder beide datamodellen, waarbij zij aantonen dat efficiënte algoritmen (LP en GD) de typische interpolator aanzienlijk overtreffen en de Bayes-optimale limiet dichter benaderen dan een willekeurige trekking uit de oplossingsverzameling.

Betekenis en Claims
Het artikel claimt de vraag over de "overvloed van goede interpolatoren" in het regime van constante SNR en overparametrisatie te hebben opgelost. De betekenis ligt in het aantonen dat:

• Impliciete Regularisatie Essentieel is: Het feit dat efficiënte algoritmen (GD, LP) een willekeurige interpolator veel overtreffen, suggereert dat het succes van generalisatie in overgeparametriseerde modellen niet een inherente eigenschap is van de oplossingsverzameling $S$, maar een gevolg van het specifieke pad dat optimalisatie-algoritmen volgen (impliciete regularisatie).
• Weerlegging van Heuristische Overvloed: De resultaten spreken heuristieken tegen die suggereren dat "goede classificatoren overvloedig zijn" in het interpolatieregime; ze laten zien dat dergelijke overvloed alleen voorkomt in de limieten van een hoge SNR.
• Rigoureuze LDP voor Interpolatoren: Het werk levert een rigoureus large deviation principle voor de generalisatiefout van uniforme interpolatoren, een resultaat dat voorheen heuristisch was of beperkt was tot specifieke aannames van een hoge SNR.

De auteurs stellen expliciet dat hun bevindingen de niet-triviale aard van benigne overfitting in deze setting benadrukken, waarbij de overgrote meerderheid van de oplossingen voor het interpolatieprobleem slechte generalisaties oplevert, en slechts een minuscule, algoritmisch geselecteerde subset goed presteert.