Robust Online Learning

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

De Onzichtbare Vervorming: Een Verhaal over Slimme Voorspellers

Stel je voor dat je een supersterke voorspeller bent. Je bent een voetbaltrainer die elke week precies weet wie er gaat winnen. Maar er is een probleem: je tegenstander is een listige bedrieger.

In het normale leven (wat wetenschappers "PAC-leren" noemen) krijg je de feiten zoals ze zijn, en de bedrieger mag ze een beetje verdraaien voordat jij ze ziet. In dit nieuwe onderzoek kijken we echter naar een online spelletje waarbij de bedrieger nog listiger is.

Het Spel: De Vervormde Bal

Hier is hoe het spel werkt, rondje voor rondje:

De Bedrieger gooit een vervormde bal naar je toe. Dit is een input die net iets anders is dan het origineel (bijvoorbeeld een foto van een panda die er voor een computer uitziet als een gibbon, maar voor een mens nog steeds een panda is).
Jij (de Leraar) moet direct een voorspelling doen: "Is het een panda of een gibbon?"
De Bedrieger toont nu pas het echte origineel en het ware antwoord.
Het Doel: Jij wilt zo min mogelijk fouten maken, zelfs als de bal er vervormd uitziet.

Het probleem? Soms is de vervorming zo klein dat zelfs jij het niet ziet, maar de computer maakt er een complete fout van. De vraag is: Hoe slim moet je zijn om dit spel te winnen, ongeacht hoe listig de bedrieger is?

De Nieuwe Maatstaf: De "Vervormings-Boom"

In de wiskunde gebruiken ze vaak ingewikkelde kaarten om te meten hoe moeilijk een probleem is. De auteurs van dit paper hebben een nieuwe, veel simpelere maatstaf bedacht. Ze noemen het de $LU$-dimensie (een soort "Vervormings-Boom").

De Analogie: Stel je een boom voor. Elke tak van de boom is een keuze die de bedrieger kan maken.
- Als de boom heel hoog is (veel lagen), betekent dit dat de bedrieger heel veel verschillende trucs kan uithalen om je in de war te brengen. Het spel is dan heel moeilijk.
- Als de boom kort is, zijn er maar weinig trucs mogelijk. Het spel is makkelijker.

De auteurs bewijzen dat de hoogte van deze boom precies bepaalt hoeveel fouten je maximaal kunt maken. Is de boom 10 lagen hoog? Dan kun je in het beste geval niet minder dan 10 fouten maken. Is hij oneindig hoog? Dan kun je het spel nooit winnen.

Twee Manieren om te Spelen

Het paper behandelt twee situaties:

1. De Realistische Situatie (Het "Perfecte" Spel)
Stel, er bestaat een perfecte trainer in de wereld die nooit fouten maakt, zelfs niet bij vervormde ballen.

De uitkomst: Als je slim genoeg bent om te leren van je fouten, kun je het spel winnen met precies zoveel fouten als de hoogte van de boom. Geen meer, geen minder.
De strategie: Je houdt een lijst bij van alle trainers die nog steeds "mogelijk" zijn. Elke keer als je een fout maakt, haal je de trainers van die lijst die dat niet hadden kunnen doen. Je lijst wordt kleiner en kleiner, tot je de enige juiste trainer overhoudt.

2. De Onzekere Situatie (Het "Agnostische" Spel)
Stel, er is geen perfecte trainer. Misschien is de data gewoon erg rommelig of is de bedrieger zo slim dat zelfs de beste trainer soms faalt.

De uitkomst: Hier kijken we niet naar het aantal fouten, maar naar het regret (spijt). Hoeveel slechter heb je gepresteerd vergeleken met de beste trainer die er had kunnen zijn?
De formule: De auteurs laten zien dat je spijt niet te groot wordt. Het hangt af van de hoogte van de boom en het aantal rondes dat je speelt. Het is alsof je een spoorboekje gebruikt: hoe langer je reist, hoe meer kans je hebt om een fout te maken, maar je blijft binnen een berekenbare grens.

Wat als je niet weet welke vervorming er komt?

In de laatste sectie van het paper stellen ze een nog lastigere vraag: Wat als je niet eens weet welke vervormingen de bedrieger mag gebruiken?
Stel, de bedrieger kan kiezen uit 100 verschillende soorten vervormingen, maar jij weet niet welke hij vandaag kiest. Je weet alleen dat het er één van die 100 is.

De oplossing: Je neemt 100 verschillende "experts" mee naar het veld. Elke expert is gespecialiseerd in één specifieke vervorming.
De strategie: Je luistert naar de menigte. Als een expert een fout maakt, stuur je hem naar huis. Omdat je weet dat er minstens één expert is die de juiste vervorming heeft gekozen, zul je uiteindelijk alleen nog maar de slimme experts overhouden.
Het resultaat: Je maakt maar een paar extra fouten (afhankelijk van het logaritme van het aantal experts), zelfs als je niet precies wist wat er ging gebeuren.

Waarom is dit belangrijk?

Vandaag de dag gebruiken we AI voor van alles: zelfrijdende auto's, medische diagnoses en beveiliging. Maar deze systemen zijn vaak kwetsbaar. Een heel klein beetje ruis op een foto (zoals een sticker op een stopbord) kan een auto laten denken dat het een snelweg is.

Dit paper geeft ons een wiskundige blauwdruk om te begrijpen:

Hoe moeilijk het is om een systeem te bouwen dat bestand is tegen deze trucs.
Hoe we algoritmes kunnen bouwen die leren om deze trucs te doorzien, zonder dat ze in de war raken.

Het is als het bouwen van een schip dat niet alleen tegen golven kan, maar ook tegen de listige kapitein die de golven zelf probeert te sturen. De auteurs zeggen: "Met de juiste maatstaf (de boom) weten we precies hoe sterk het schip moet zijn om te overleven."

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

Titel: Robust Online Learning

Auteur: Sajad Ashkezari
Datum: 2 maart 2026

1. Probleemdefinitie en Context

Dit paper onderzoekt het probleem van het leren van robuste classifiers binnen het kader van online learning. Het centrale doel is het ontwikkelen van voorspellers die correct blijven, zelfs wanneer de invoer (input) door een tegenstander (adversary) wordt verstoord.

Het onderscheid met eerdere werken: In tegenstelling tot eerdere studies over Robust PAC Learning (waarbij de schone data uit een verdeling komt en vervolgens wordt gemanipuleerd), stelt dit paper dat zowel de schone data als het bijbehorende label adversariaal gekozen kunnen zijn.
Het spel: Het probleem wordt gemodelleerd als een interactief spel tussen een tegenstander en een leerder:
1. De tegenstander kiest een verstoord punt $Z_t$ en onthult dit aan de leerder.
2. De leerder voorspelt een label $\hat{Y}_t$ .
3. De tegenstander onthult vervolgens het oorspronkelijke schone punt $X_t$ (waarvoor $Z_t \in U(X_t)$ ) en het ware label $Y_t$ .
4. De leerder incasseert een fout als $\hat{Y}_t \neq Y_t$ .
Doel: Het minimaliseren van het aantal fouten (in de realizable setting) of het minimaliseren van de regret (in de agnostische setting).

2. Methodologie en Kernconcepten

De $U$ -adversarial Littlestone-dimensie

De auteur introduceert een nieuwe combinatorische maatstaf voor de complexiteit van een hypothese-klasse $\mathcal{H}$ , genaamd de $U$ -adversarial Littlestone-dimensie, genoteerd als $LU(\mathcal{H})$ .

Definitie: Deze dimensie is gebaseerd op de diepte van een "shattered" $U$ -adversarial Littlestone-boom. In zo'n boom vertegenwoordigen de interne knopen paren van punten $(x^0, x^1)$ waarvan de toelaatbare verstoringen overlappen ( $U(x^0) \cap U(x^1) \neq \emptyset$ ). Een boom is "shattered" als er voor elk pad van de wortel naar een blad een hypothese in $\mathcal{H}$ bestaat die consistent is met de labels langs dat pad, zelfs rekening houdend met de verstoringen.
Vergelijking: In het geval van geen verstoringen ( $U(x)=\{x\}$ ), reduceert deze dimensie tot de klassieke Littlestone-dimensie. Dit is eenvoudiger dan de dimensie die nodig is voor Robust PAC learning (die afhankelijk is van een globale one-inclusion graaf).

De Oriëntatie-spel (Orientation Game)

Om de foutgrenzen af te leiden, introduceert de auteur een vereenvoudigd sub-probleem: het Orientation Game.

Hierbij kiest de tegenstander twee punten $x^0_t$ en $x^1_t$ met overlappende verstoringen. De leerder moet kiezen welk label bij welk punt hoort.
Het paper bewijst dat de optimale foutgrens voor dit spel exact gelijk is aan $LU(\mathcal{H})$ .
Algoritme: Het Standard Optimal Algorithm for Orientation Game (SOAOG) voorspelt het label dat de grootste $LU$-dimensie overlaat in de versie-ruimte (version space) na de voorspelling. Elke fout vermindert de dimensie van de versie-ruimte met minstens één.

Overdracht naar Robust Online Learning

De auteur toont aan dat een leerder voor het Oriëntatie-spel kan worden omgezet in een leerder voor het volledige Robust Online Learning-probleem. Als de leerder een fout maakt in het oorspronkelijke spel, impliceert dit dat er een fout is gemaakt in de onderliggende oriëntatie tussen een kandidaat-punt en een punt met het tegenovergestelde label. Hierdoor wordt de totale foutgrens begrensd door de foutgrens van het Oriëntatie-spel.

3. Belangrijkste Resultaten

A. Realizable Setting (Waar de data consistent is met een hypothese)

Hoofdstelling: Een hypothese-klasse $\mathcal{H}$ is realizable robust online learnable dan en slechts dan als $LU(\mathcal{H}) < \infty$ .
Foutgrens: De optimale foutgrens $M^*$ is exact gelijk aan de dimensie:
$M^* = LU(\mathcal{H})$
Multiclass Uitbreiding: De resultaten worden gegeneraliseerd naar multiclass klassen (met een mogelijke oneindige labelruimte). De definitie van de boom en de dimensie wordt aangepast, maar de karakterisering van de leerbaarheid en de foutgrens blijven gelijk.

B. Agnostische Setting (Waar de data niet noodzakelijk realizable is)

In deze setting wordt de regret geminimaliseerd in plaats van het absolute aantal fouten.
Regretgrens: De optimale verwachte regret wordt begrensd door:
$R^*_T = \tilde{O}\left(\sqrt{T \cdot LU(\mathcal{H}) \log(T)}\right)$
Methode: De auteur gebruikt een techniek gebaseerd op het comprimeren van de inputsequentie naar een maximaal realizable sub-sequentie en past "prediction with expert advice" toe op deze sub-sequenties.

C. Onzekere Verstoringen (Uncertain Perturbation Sets)

Scenario: De leerder kent de exacte verstoringsfunctie $U$ niet, maar weet dat deze behoort tot een eindige familie $\mathcal{G}$ van mogelijke functies.
Resultaat: Zelfs als $LU(\mathcal{H})$ oneindig kan zijn voor sommige functies in $\mathcal{G}$ , is het aantal fouten begrensd door:
$O\left((LU^*(\mathcal{H}) + 1) \log(|\mathcal{G}|)\right)$
waarbij $LU^*(\mathcal{H})$ de dimensie is voor de ware verstoringsfunctie $U^*$ . Dit wordt bereikt door een "phased" strategie waarbij experts die fouten maken worden verwijderd.

4. Bijdragen en Significatie

Formulering: Dit is het eerste werk dat Robust Learning systematisch bestudeert binnen het theoretische kader van Online Learning (Littlestone-framework), in plaats van alleen PAC-learning.
Nieuwe Complexiteitsmaat: De introductie van de $U$ -adversarial Littlestone-dimensie ( $LU(\mathcal{H})$ ). Deze dimensie is conceptueel eenvoudiger dan de bestaande dimensies voor Robust PAC learning en gedraagt zich analoog aan de klassieke Littlestone-dimensie.
Optimaliteit: Het paper levert strakke boven- en ondergrenzen voor zowel het aantal fouten (realizable) als de regret (agnostisch), die direct worden gedicteerd door deze nieuwe dimensie.
Robustheid tegen onzekerheid: Het biedt oplossingen voor situaties waarin de leerder niet precies weet welke verstoringen mogelijk zijn, wat een praktische versterking is van het theoretische model.

5. Conclusie en Toekomstgericht Onderzoek

Het paper legt een solide theoretische basis voor robust online learning. De auteur identificeert echter nog open vragen voor toekomstig onderzoek:

Wat gebeurt er als de familie van verstoringen oneindig is maar gestructureerd?
Kan leren nog mogelijk zijn als de leerder het schone punt $X_t$ niet ziet?
Hoe ziet leerbaarheid eruit bij gedeeltelijke feedback (bandit setting)?
Kan de kloof tussen de boven- en ondergrenzen voor de regret (factor $\sqrt{\log T}$ ) worden gesloten?
Uitbreiding naar regressie-taken in plaats van alleen classificatie.

Samenvattend biedt dit paper een fundamentele doorbraak in het begrijpen van de learnability van robuste modellen onder agressieve omstandigheden, met een nieuwe, elegante dimensionele maatstaf die de leerbaarheid volledig karakteriseert.