Optimal training-conditional regret for online conformal prediction

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een waarzegger bent die elke dag een voorspelling doet: "Zal het morgen regenen?" of "Wat wordt de prijs van deze aandeel?". In de wereld van machine learning noemen we dit conformal prediction. Het doel is niet alleen om een antwoord te geven, maar ook om een veiligheidsnet te spannen: een bereik van antwoorden waar we 90% zeker van zijn dat het juiste antwoord erin zit.

Het probleem? De wereld verandert. De data die je gisteren kreeg, is niet hetzelfde als die van vandaag. De weersvoorspellingen veranderen als de seizoenen wisselen, en aandelen gedragen zich anders tijdens een crisis. Dit noemen we distributie-drift (de onderliggende regels veranderen).

De meeste oude methoden voor online voorspellingen waren als een stugge leraar die zegt: "Op de lange termijn, gemiddeld over een heel jaar, zullen we 90% goed zitten." Maar dat zegt niets over vandaag. Misschien heb je gisteren 100% fouten gemaakt en morgen 80%, zolang het gemiddelde maar klopt. Dat is gevaarlijk als je echt betrouwbare voorspellingen nodig hebt.

Dit paper (geschreven door Liang, Ren en Chen) introduceert een slimme nieuwe manier om dit op te lossen. Ze noemen hun methode DriftOCP. Hier is de uitleg in simpele taal:

1. Het Probleem: De Verkeersborden Veranderen

Stel je voor dat je auto rijdt op een weg met verkeersborden.

Oude methode: Je kijkt alleen naar het gemiddelde aantal verkeersborden dat je de hele dag hebt gezien. Als je gemiddeld 90% van de borden hebt gehaald, denk je: "Goed gedaan!" Maar wat als je gisteren 50 borden hebt genegeerd en vandaag 100% goed hebt? Je gemiddelde klopt, maar je was gisteren levensgevaarlijk.
Het nieuwe doel: De auteurs willen dat je elke dag (of bij elke voorspelling) precies 90% veilig rijdt, zelfs als de weg plotseling verandert (bijvoorbeeld van asfalt naar modder).

2. De Oplossing: Twee Slimme Strategieën

De auteurs bieden twee oplossingen, afhankelijk van hoe "slim" je voorspellingsmodel is.

Strategie A: De Vaste Kaart (Pretrained Scores)

Stel, je hebt een vaste kaart (een model) die je al hebt getraind op oude data. Je gebruikt deze kaart om de voorspellingen te maken, maar je moet wel weten of de weg nog wel op de kaart staat.

De Analogie: Je hebt een GPS die je niet kunt updaten, maar je hebt wel een slimme passagier die naar buiten kijkt.
Hoe het werkt: De passagier (het algoritme) kijkt continu naar de "foutmarge". Als de auto plotseling begint te slippen (de data verandert), schreeuwt de passagier: "Stop! De weg is veranderd!"
De actie: De GPS wordt dan direct gereset met nieuwe informatie van de laatste paar minuten. Dit heet drift detection.
Het resultaat: Je bent altijd scherp ingesteld op de huidige situatie. Je maakt geen fouten omdat je vastzit aan oude regels.

Strategie B: De Leerling die Opgroeit (Adaptively Trained Scores)

Stel, je auto leert terwijl je rijdt. Het model past zich elke seconde aan aan de nieuwe weg. Dit is lastiger, want het model zelf verandert ook.

De Analogie: Je rijdt met een leerling die elke dag een beetje beter wordt, maar soms ook een beetje "verkeerd" leert als de weg verandert.
Het probleem: Als je de leerling te vaak laat oefenen op de verkeerde weg, wordt hij onbetrouwbaar.
De oplossing: De auteurs gebruiken een techniek genaamd stabiliteit. Ze zeggen: "Als je één steentje uit de weg haalt, mag de leerling niet volledig gek worden." Als het model stabiel genoeg is (een klein steentje verandert het gedrag maar een beetje), dan kunnen we het toch vertrouwen, zelfs als het online leert.
De actie: Ze bouwen een "veiligheidszone" rondom de leerling. Als de leerling te veel afwijkt van de norm, weten ze dat de weg te snel verandert en passen ze de regels aan.

3. Waarom is dit zo belangrijk? (De "Regret"-metriek)

In de wiskunde gebruiken ze een term die Regret (spijt) heet.

Oude manier: "We hebben gemiddeld 90% goed gezegd." (Dit kan betekenen dat je soms 0% goed zegt, maar later 100%, en het gemiddelde redt het).
Nieuwe manier (Training-conditional Regret): "Hoe ver zitten we nu van de 90%?"
- Als je vandaag 95% goed zit, is je spijt laag.
- Als je vandaag 50% goed zit, is je spijt hoog.
- Het paper bewijst dat hun methode minimaal spijt veroorzaakt. Ze zijn zo goed mogelijk, theoretisch gezien, voor elke mogelijke manier waarop de wereld kan veranderen.

4. De Experimenten: De Proef op de Som

Ze hebben hun methode getest in simulations:

Scenario 1: Plotselinge veranderingen (een brug is ingestort, je moet ineens omrijden).
Scenario 2: Langzame veranderingen (de weg wordt langzaam modderig door regen).

Het resultaat:
Hun methode (DriftOCP) reageerde veel sneller en nauwkeuriger dan de bestaande methoden.

De oude methoden (zoals ACI) waren als een trage auto: ze reageerden te traag op plotselinge veranderingen of waren te onstabiel bij rustige veranderingen.
DriftOCP was als een sportauto met een slimme bestuurder: hij bleef stabiel op de rechte weg, maar remde en stuurde direct bij als de weg veranderde.

Samenvatting in één zin

Dit paper leert computers hoe ze onmiddellijk moeten reageren op veranderingen in de wereld, zodat ze elke dag een betrouwbare voorspelling kunnen doen, in plaats van alleen te hopen dat het op de lange termijn wel goed komt.

Het is alsof je een kompas hebt dat niet alleen naar het noorden wijst, maar ook direct merkt als de magnetische pool verschuift en zichzelf daarop aanpast, zodat je nooit verdwaalt.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Optimal training-conditional regret for online conformal prediction" in het Nederlands.

Titel: Optimal training-conditional regret voor online conformale voorspelling

Auteurs: Jiadong Liang, Zhimei Ren, Yuxin Chen
Datum: 6 maart 2026

1. Probleemstelling

Conformale voorspelling is een krachtig raamwerk voor het kwantificeren van onzekerheid in machine learning, dat strikte dekkingsgaranties biedt zonder sterke distributie-aannames. Traditionele methoden gaan echter uit van uitwisselbare (vaak i.i.d.) data. In de praktijk komen we echter vaak te maken met niet-stationaire datastromen waarbij de onderliggende verdeling in de loop van de tijd verandert (distributiedrift).

Bestaande werk op het gebied van online conformale voorspelling richt zich voornamelijk op:

Adversariële settings: Waar data willekeurig door een tegenstander wordt gegenereerd.
Metingen op basis van tijdgemiddelde dekking: Waarbij wordt gekeken naar de empirische dekking over een lange periode.

De beperkingen van bestaande aanpakken:

Een tijdgemiddelde dekking van $1-\alpha$ garandeert niet dat de voorspellingsintervallen op elk individueel tijdstip betrouwbaar zijn. Een algoritme kan een perfecte lange-termijn dekking hebben door simpelweg grote, nutteloze intervallen te kiezen of door fouten te compenseren die later optreden.
Er is een gebrek aan optimaliteitsgaranties voor methoden die specifiek zijn ontworpen voor niet-adversariële drift (zoals abrupte veranderingen of gladde drift) met onafhankelijke data.

Doel van dit paper:
Het paper introduceert en analyseert training-conditional cumulatieve regret als de primaire prestatie-maatstaf. Deze maatstaf meet de afwijking van de conditionele dekking (gegeven de historische data en interne randomisatie) ten opzichte van het doelniveau $1-\alpha$, geaggregeerd over de tijd. Het doel is om algoritmen te ontwikkelen die minimax-optimaal zijn voor deze regret-maatstaf onder twee soorten drift:

Abrupte veranderingen (Change-points): De verdeling blijft stationair tussen sprongen.
Gladde drift: De verdeling evolueert continu en soepel.

2. Methodologie

De auteurs onderscheiden twee scenario's gebaseerd op hoe de niet-conformiteitscores (de maatstaf voor hoe "vreemd" een datapunt is) worden gegenereerd.

Scenario A: Vooraf getrainde scores (Pretrained Scores)

In dit scenario zijn de scorefuncties getraind op een onafhankelijk dataset en zijn onafhankelijk van de online datastroom (vergelijkbaar met split conformal prediction).

Algoritme: DriftOCP (Online Conformal Prediction with Drift Detection).
Werking:
- Het algoritme verdeelt de tijdshorizon in "stages" en "rondes" met een verdubbelingstruc (round lengths groeien exponentieel).
- Het gebruikt een drift-detectie subroutine (DriftDetect) die de empirische blok-dekkingsfout monitort. Als de afwijking van de verwachte dekking een drempelwaarde overschrijdt, wordt een drift gedetecteerd.
- Bij detectie wordt de kalibratieset gereset en begint een nieuwe stage.
- De drempelwaarde voor de voorspellingsset wordt dynamisch aangepast op basis van de huidige ronde.
Theoretische basis: Het algoritme leunt op de onafhankelijkheid van de scores en gebruikt driftdetectie om de kalibratie bij te werken zonder de horizonlengte $T$ vooraf te kennen.

Scenario B: Adaptief getrainde scores (Adaptively Trained Scores)

In dit scenario worden zowel de voorspellingsmodellen als de scores online bijgewerkt op basis van de waargenomen data. Dit introduceert complexe statistische afhankelijkheden en schendt de uitwisselbaarheid.

Algoritme: DriftOCP-full (Online Full Conformal Prediction with Drift Detection).
Werking:
- Gebruikt het full conformal paradigma (alle beschikbare data wordt gebruikt voor zowel training als kalibratie, zonder splitsing) voor betere data-efficiëntie.
- Integreert driftdetectie (DriftDetect+) die werkt op de voorspellingssets in plaats van alleen op scores.
- Stabiliteitsveronderstelling: In plaats van de gebruikelijke permutatie-symmetrie (die vaak schendt bij online learning), maakt het algoritme gebruik van stabiliteit van het leeralgoritme. Dit betekent dat het veranderen van één trainingspunt slechts een kleine verandering in het voorspellingsmodel veroorzaakt (bijv. $O(1/m)$ ).
Theoretische basis: De analyse leunt op veronderstellingen over de Lipschitz-continuïteit van de conditionele responsverdeling en de stabiliteit van het leeralgoritme (zoals gestochastische convex optimalisatie).

3. Belangrijkste Bijdragen

Nieuwe Prestatiemaatstaf: Het paper introduceert training-conditional cumulative regret als een robuustere maatstaf dan tijdgemiddelde dekking of adversariële regret. Dit garandeert dat de voorspellingssets op elk moment informatief en betrouwbaar zijn, niet alleen in het gemiddelde.
Minimax-Optimaliteit:
- Voor pretrained scores wordt bewezen dat DriftOCP een regret bereikt van $\tilde{O}(\sqrt{N_{cp} T})$ bij change-points en $\tilde{O}(\sqrt{T} + K_{ST}^{1/3}T^{2/3})$ bij gladde drift (waarbij $N_{cp}$ het aantal veranderingen is en $K_{ST}$ de cumulatieve variatie).
- Voor adaptief getrainde scores wordt DriftOCP-full geanalyseerd, met vergelijkbare regret-garanties onder stabiliteitsveronderstellingen.
- De auteurs bewijzen minimax ondergrenzen die aantonen dat hun algoritmen (op logaritmische factoren na) optimaal zijn. Dit is een van de eerste keer dat dergelijke ondergrenzen worden bewezen voor online full conformal prediction.
Nieuwe Theoretische Resultaten voor Full Conformal:
- Het paper levert een nieuwe training-conditional dekkingstheorie voor batch full conformal methoden onder stabiliteitsveronderstellingen, zonder de noodzaak van permutatie-symmetrie.
- Het toont aan dat zelfs bij niet-symmetrische leeralgoritmen (zoals online SGD), geldige dekking kan worden gegarandeerd als het algoritme stabiel is.
Horizon-vrij en Rekenefficiënt: De voorgestelde algoritmen vereisen geen kennis van de totale tijdsduur $T$ en hebben een lage rekentijd per tijdstap, wat ze praktisch toepasbaar maakt.

4. Resultaten

Theoretische Bewijzen:
- De regret-grenzen van DriftOCP en DriftOCP-full komen overeen met de bewezen minimax ondergrenzen. Dit betekent dat er geen algoritme bestaat dat fundamenteel beter presteert voor deze klassen van problemen.
- De analyse toont aan dat de regret voornamelijk wordt gedreven door de snelheid van de drift en het aantal veranderingen, en niet door de lengte van de tijdreeks alleen.
Numerieke Experimenten:
- Pretrained Scores: DriftOCP wordt vergeleken met Adaptive Conformal Inference (ACI). DriftOCP toont superieure prestaties: het past zich snel aan bij veranderingen (zoals plotselinge variatieverschuivingen) zonder de stabiliteit te verliezen in stationaire periodes, terwijl ACI last heeft van een afweging tussen stapgrootte en aanpassingsvermogen.
- Adaptieve Scores: Experimenten tonen aan dat het gebruik van een online bijgewerkt model (via SGD) in combinatie met DriftOCP-full leidt tot smaller voorspellingsintervallen en stabielere dekking dan methoden met vooraf getrainde modellen of model-vrije baselines, zelfs onder model-misspecificatie en covariaat-drift.

5. Betekenis en Impact

Dit paper is significant voor het veld van onzekerheidskwantificatie en online learning om de volgende redenen:

Overbrugging van Theorie en Praktijk: Het biedt een oplossing voor het veelvoorkomende probleem van distributiedrift in real-time systemen, waarbij bestaande methoden vaak falen of inefficiënt zijn.
Verschuiving in Validatie: Door de focus te verleggen van "gemiddelde dekking" naar "training-conditional regret", stelt het paper een hogere standaard voor de betrouwbaarheid van voorspellingen. Dit is cruciaal voor veiligheidskritische toepassingen (zoals autonoom rijden of medische diagnose) waar een enkele fout op een specifiek moment fataal kan zijn, zelfs als de lange-termijn statistiek goed lijkt.
Generalisatie van Conformale Theorie: Het bewijst dat full conformal prediction, vaak gezien als te rekenintensief of beperkt tot i.i.d. data, kan worden uitgebreid naar dynamische omgevingen mits men gebruikmaakt van stabiliteit in plaats van symmetrie. Dit opent de deur voor het gebruik van complexe, adaptieve machine learning modellen in conformale voorspelling.
Optimaliteit: Het leveren van zowel boven- als ondergrenzen (minimax optimaliteit) plaatst deze werk als een fundamenteel referentiepunt voor toekomstig onderzoek in niet-stationaire conformale voorspelling.

Kortom, dit paper levert een theoretisch onderbouwde, optimale en praktische oplossing voor het probleem van onzekerheidskwantificatie in een veranderende wereld.