🤖 machine learning

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

Dit artikel stelt een analytisch kader voor gebaseerd op de Rademacher-complexiteit met een L1-norm om de optimale vroege stop-tijd voor lineaire regressiemodellen te schatten zonder dat daarvoor training of probabilistische aannames vereist zijn, waarbij de toepasbaarheid op niet-lineaire neurale netwerken wordt aangetoond via lineaire probing.

Oorspronkelijke auteurs: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Gepubliceerd 2026-08-26

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het trainen van een computer om patronen te herkennen, of het nu gaat om het identificeren van een kat op een foto of het voorspellen van een aandelenkoers, houdt een delicaat evenwicht in. De machine leert door naar voorbeelden te kijken en past haar interne instellingen aan om bij de geziene data te passen. Echter, als de machine te perfect leert, begint zij de specifieke eigenaardigheden van die voorbeelden te memoriseren in plaats van de onderliggende regels te begrijpen. Dit is een beetje zoals een student die de antwoorden op een oefentoets uit het hoofd leert, maar de echte toets niet kan maken omdat hij de logica niet kan toepassen op nieuwe vragen. In de wereld van kunstmatige intelligentie is dit onvermogen om te generaliseren een grote hindernis. Om dit te voorkomen, gebruiken onderzoekers vaak een strategie genaamd "early stopping" (vroegtijdige stopzetting), waarbij zij het leerproces op precies het juiste moment stoppen—nadat het model de regels heeft geleerd, maar voordat het begint met het memoriseren van de ruis. De uitdaging is altijd geweest om precies te weten wanneer dat moment aanbreekt. Traditioneel vereist het vinden van dit ideale punt het meerdere keren draaien van het trainingsproces op afzonderlijke datasets, een methode die traag, rekenintensief is en vaak op gokwerk berust.

Een team van onderzoekers aan de Université Paris-Saclay heeft een nieuwe manier voorgesteld om dit timingprobleem op te lossen zonder de noodzaak van herhaalde proeven. In plaats van te gokken of extra simulaties uit te voeren, hebben zij een wiskundige methode ontwikkeld die het ideale stoppunt direct uit de data zelf kan voorspellen. Hun aanpak rust op een concept dat bekend staat als Rademacher-complexiteit, wat in essentie meet hoe goed een model het onderscheid kan maken tussen echte patronen en willekeurige ruis. Door deze maatstaf te gebruiken, creëerden de onderzoekers een regel die een computer precies vertelt wanneer zij moet stoppen met leren. Wat hun werk onderscheidt, is dat het geen aannames vereist over de vorm of distributie van de data, een veelvoorkomende vereiste bij eerdere methoden. Bovendien ontdekten zij dat het gebruik van een specifieke manier om fouten te meten, de zogenaamde L1-norm, aanzienlijk nauwkeurigere voorspellingen opleverde dan de standaardmethoden die in het vakgebied worden gebruikt.

De onderzoekers richtten hun initiële werk op lineaire modellen, de eenvoudigste soort machine learning-algoritmen, maar zij toonden aan dat hun bevindingen kunnen worden uitgebreid naar complexe, niet-lineaire neurale netwerken. Om hun theorie te testen, pasten zij hun methode toe op een klassiek probleem: het onderscheiden van handgeschreven cijfers. In één experiment trainden zij een neuraal netwerk om het verschil te zien tussen de cijfers drie en vijf met behulp van een dataset van meer dan tienduizend afbeeldingen. Met behulp van hun nieuwe regel berekende het systeem een stoppertijd van 342 stappen. Toen zij dit vergeleken met de werkelijke beste stoppertijd die werd gevonden door het volledige trainingsproces te draaien en een aparte testset te controleren, bleek het werkelijke optimum 357 stappen te zijn. Het verschil was verwaarloosbaar, en de prestaties van het model dat op de voorspelde tijd stopte, waren vrijwel identiek aan de prestaties van het model dat op het werkelijke optimum stopte. In een andere test met de cijfers nul en één was de voorspelde stoppertijd 415 stappen, terwijl het werkelijke optimum 418 stappen was. In beide gevallen vermeed het met hun regel getrainde model de valstrik van overfitting en bereikte het de best mogelijke nauwkeurigheid voor ongeziene data.

De studie onthulde ook dat de methode het beste werkt wanneer er een grote hoeveelheid data is in verhouding tot de complexiteit van het model. Wanneer de onderzoekers scenario's testten met minder datapunten, werd de methode minder precies en suggereerde zij soms een stoppertijd van nul, wat aangeeft dat het model helemaal niet getraind zou moeten worden. Dit komt overeen met het begrip dat complexe modellen voldoende data nodig hebben om algemene regels te leren. De onderzoekers vergeleken hun nieuwe methode ook met oudere technieken die steunen op andere wiskundige aannames over de data. Zij vonden dat hun aanpak, die de L1-norm gebruikt voor de berekening, consequent stoppertijden produceerde die veel dichter bij het werkelijke optimum lagen dan de oudere methoden. Dit suggereert dat de manier waarop fouten worden gemeten even belangrijk is als de stopregel zelf.

Misschien wel het belangrijkste is dat de onderzoekers lieten zien dat vroegtijdig stoppen niet alleen een theoretisch concept is, maar in veel gevallen een praktische noodzaak. Zij berekenden wat er zou gebeuren als de training onbeperkt zou doorgaan. In de voorbeelden die zij bestudeerden, verslechterde de prestatie van het model op nieuwe data daadwerkelijk als de training verder ging dan het optimale punt, wat bevestigt dat vroegtijdige stopzetting voorkomt dat het model degradeert. Zij merkten echter ook op dat in sommige specifieke, zeer complexe scenario's waar het model veel meer parameters heeft dan dat er datapunten zijn, het voortzetten van de training uiteindelijk toch tot betere resultaten kan leiden, een fenomeen dat bekend staat als "benign overfitting" (welwillende overfitting). Hun methode helpt te identificeren in welke situatie een gebruiker zich bevindt, zodat men kan beslissen of men vroegtijdig stopt of doorgaat.

Door een manier te bieden om de optimale stoppertijd te berekenen zonder het volledige trainingsproces te hoeven doorlopen, biedt dit werk een efficiënter pad voor de ontwikkeling van betrouwbare kunstmatige intelligentie. Het elimineert de noodzaak van trial-and-error, waardoor tijd en computationele middelen worden bespaard. De methode is bijzonder nuttig voor situaties waarin data overvloedig is maar de rekenkracht beperkt is, of waar de kosten van training hoog zijn. Hoewel de huidige studie zich richt op lineaire modellen en specifieke soorten data, geloven de onderzoekers dat hun raamwerk kan worden aangepast voor complexere systemen en verschillende soorten outputs. Hun werk biedt een duidelijk, op data gebaseerd antwoord op een vraag die lang op gokwerk heeft geleid, en biedt een nauwkeuriger instrument om de afweging tussen leren en memoriseren te navigeren.

Technische Samenvatting: Een datagebonden vroege stopregel met behulp van Rademacher-complexiteit met de L1-norm

Probleemstelling
Het trainen van neurale netwerken vereist een balans tussen het fitten van trainingsdata en het bereiken van robuuste prestaties op ongeziene inputs, een eigenschap die bekend staat als generaliseerbaarheid. Dit wordt bepaald door de kloof tussen het empirische risico ( $L_S$ ) en het verwachte populatierisico ( $L_D$ ). Het generalisatieverlies ( $L_G$ ) wordt gedefinieerd als het verschil tussen deze twee. Tijdens gradiëntafdaling (GD) neemt $L_S$ doorgaans af terwijl $L_G$ toeneemt, wat een "bias-variantie"-trade-off creëert. Het doel van vroege stoptechnieken (early stopping) is om de training te stoppen op een optimaal tijdstip $t^*$ dat de som $L_S + L_G$ minimaliseert.

Klassiek wordt $t^*$ numeriek geschat door een aparte testset ( $S_{test}$ ) te monitoren. Alternatief bestaan er analytische benaderingen met behulp van Random Matrix Theory (RMT), maar deze leunen vaak op sterke probabilistische aannames, zoals Gaussische datadistributies of specifieke eigenwaarde-distributies (bijv. Marchenko–Pastur) van de covariantie-matrix van de data. Dit artikel adresseert de behoefte aan een analytische vroege stopregel die geen aparte testsets of restrictieve distributieve aannames vereist.

Methodologie
De auteurs stellen een analytisch kader voor op basis van Rademacher-complexiteit (RC) om de optimale stoppertijd te schatten zonder gradiëntafdaling uit te voeren. De methodologie richt zich op lineaire modellen en lineaire regressie, met uitbreidingen naar niet-lineaire netwerken via "linear probing".

L1-norm Formulering: In tegen tegenstelling tot veel bestaande RC-bounds die de L2-norm gebruiken, drukt dit werk de Rademacher-complexiteit uit met behulp van de L1-norm. Deze keuze is gemotiveerd door de wens om een datagebonden constante $M$ (een bovengrens op de loss) uit de generalisatiefout-bound te elimineren. Door $p=1$ in de algemene $L_p$ -norm bound in te stellen, leiden de auteurs een bovengrens af op de populatie-loss ( $L_D$ ) die alleen afhankelijk is van de empirische foutvector en de modelnorm, waardoor de expliciete afhankelijkheid van $M$ wordt vermeden.
Gradient Flow Dynamica: Het probleem wordt in continue tijd gemodelleerd met behulp van Gradient Flow (GF). De auteurs analyseren de dynamica van de trainingsfoutvector $v(t)$ en de modelparameters $a(t)$ . De bovengrens van de populatie-loss, aangeduid als $L^*_D(t)$ , wordt getoond als "U-vormig": aanvankelijk dalend naarmate de empirische loss afneemt en later toenemend naarmate de modelnorm groeit.
Analytisch Stopcriterium ( $t^+$ ): De kernbijdrage is de afleiding van een datagebonden criterium $C(s)$ $C (s)$ dat ervoor zorgt dat $L^*_D(t)$ $L_{D}^{*} (t)$ dalend is voor alle $t \leq s$ $t \leq s$ .
- De auteurs deconstrueren de eigenwaarden van de datacovariantie-matrix in "informatieve" (grote) en "ruis"-sets (kleine eigenwaarden).
- Ze definiëren een functie $\Phi(t)$ die deze eigenwaarden en de foutdynamica bevat.
- De stoppertijd $t^+$ wordt gedefinieerd als het supremum van de tijd $s$ waarvoor $\Phi(t) > 0$ voor alle $t \in [0, s)$ .
- Wiskundig gezien is $t^+$ het eerste moment waarop $\Phi(t)$ nul kruist. Er wordt bewezen dat $t^+$ een ondergrens-schatting is van de werkelijke optimale tijd $t^*$ (d.w.z. $t^+ \leq t^*$ ). Onder specifieke condities (bijv. wanneer het werkelijke minimum binnen het eerste teken-invariante interval ligt), geldt $t^+ = t^*$ .
Approximatie: Het artikel biedt een eenvoudige approximatie $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ , die lijkt op een signaal-ruisverhouding (SNR) formulering uit de RMT-literatuur, maar hier zonder probabilistische aannames is afgeleid.

Belangrijkste Bijdragen

Distributievrije Analytische Estimatie: Het artikel introduceert een methode om de optimale vroege stop-tijd analytisch te schatten zonder een aparte validatieset of restrictieve probabilistische aannames over de datadistributie nodig te hebben.
L1-norm Voordeel: De auteurs tonen theoretisch en numeriek aan dat het gebruik van de L1-norm voor Rademacher-complexiteit een stoppertijd-schatting ( $t^+$ ) oplevert die significant dichter bij de numerieke optimum ( $t_{test}$ ) ligt dan de L2-norm benadering.
Focus op Onderparameterisatie: De methode is specifiek ontworpen voor het ondergeparameteriseerde regime ( $m \leq n$ ), waar "benign overfitting" en "epoch-wise double descent" minder prominent aanwezig zijn, wat het gebruik van vroege stoptechnieken een zinvolle strategie maakt.
Toepassing van Linear Probing: Hoewel de theorie is afgeleid voor lineaire modellen, passen de auteurs de resultaten succesvol toe op niet-lineaire neurale netwerken (specifiek op MNIST classificatie) door de verborgen lagen te bevriezen en alleen de outputlaag te trainen (linear probing).

Resultaten
De auteurs valideren hun methode via verschillende voorbeelden:

Synthetische Gaussische Data: In binaire classificatietaken met variërende steekproefgroottes ( $n=512$ en $n=16384$ ) kwam de analytische schatting $t^+$ exact overeen met de werkelijke optimale tijd $t^*$ in het eerste geval en bood het een nauwe ondergrens in het tweede geval. De L1-gebaseerde schatting was consistent dichter bij de testset-optimum dan de L2-gebaseerde schatting.
MNIST Classificatie (3-5 en 0-1): Bij het gebruik van een 4-laagse ReLU-netwerk met linear probing, voorspelde de methode accuraat de stoppertijd. Voor de 3-5 classificatie was $t^+ = 342$ vergeleken met de numerieke optimum $t^* = 357$ en de testset-optimum $t_{test} = 356$ . Voor de 0-1 classificatie kwam $t^+ = 415$ overeen met $t^* = 415$ en lag het dicht bij $t_{test} = 418$ .
Voordeligheid van Vroeg Stoppen: In alle geteste gevallen was de loss bij de geschatte stoppertijd lager dan de loss bij een oneindige trainingstijd ( $L^*_D(t^+) < L^*_D(\infty)$ ), wat bevestigt dat vroege stoptechnieken zinvol zijn en de "benign overfitting" fase vermijden.
Robuustheid: De methode presteerde goed over verschillende datadistributies (Gaussisch, Uniform, Pareto), waarbij de prestaties verbeterden naarmate de ratio van samples tot parameters ( $n/m$ ) toenam.

Betekenis en Claims
Het artikel claimt dat de primaire betekenis ervan ligt in het bieden van een datagebonden, analytische vroege stopregel die opereert zonder de noodzaak van een aparte validatieset of restrictieve probabilistische aannames over de datadistributie. Door gebruik te maken van Rademacher-complexiteit met de L1-norm, bieden de auteurs een praktisch instrument voor het bepalen van het moment waarop de training van lineaire modellen (en via linear probing, bepaalde niet-lineaire netwerken) gestopt moet worden om de generalisatiefout te minimaliseren. De auteurs merken bescheiden op dat hoewel de methode goed werkt voor ondergeparameteriseerde modellen, deze niet bedoeld is voor het overgeparameteriseerde regime waar "benign overfitting" optreedt. Ze identificeren ook richtingen voor toekomstig werk, waaronder directe toepassing op volledig niet-lineaire modellen, vectoriële outputs en het afhandelen van willekeurige ruis in inputdata.

Meer zoals dit