Technische Samenvatting: Bagging leert robuust VC-klassen met lineaire steekproefcomplexiteit

Probleemstelling

Het artikel behandelt de fundamentele uitdaging van het leren van voorspellers die robuust zijn tegen adversariële voorbeelden op testtijd. Gegeven een instantieruimte $\mathcal{X}$, een labelruimte $\mathcal{Y} = \{-1, 1\}$, en een tegenstander gedefinieerd door een perturbatiekaart $U: \mathcal{X} \to 2^\mathcal{X}$, is het doel om een voorspeller $\hat{f}$ te leren die de populatierobuste risico minimaliseert:
$$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$$
waarbij $P$ een onbekende distributie is over $\mathcal{X} \times \mathcal{Y}$.

Het artikel richt zich op de leerbaarheid van functieklassen $\mathcal{F}$ met een eindige Vapnik-Chervonenkis (VC) dimensie $d$. Eerdere studies toonden aan dat hoewel VC-klassen leerbaar zijn in de standaard PAC-setting, adversarieel robuust leren aanzienlijke hindernissen kent. Specifiek toonden Montasser, Hanneke en Srebro [2019] aan dat:

1. Proper learning (het beperken van de output tot binnen $\mathcal{F}$) zelfs kan falen voor klassen met een VC-dimensie 1.
2. Improper learning mogelijk is, maar de best bekende bovengrens op de steekproefcomplexiteit exponentieel was in $d$.
3. Bestaande improper algoritmen zijn computationeel inefficiënt en vereisen $O(nd)$ oproepen aan een Robust Empirical Risk Minimization (RERM) oracle met een evenredig grote overhead.

De centrale vraag is of men algoritmen kan ontwerpen die zowel steekproefefficiënt (lineair in $d$) als oracle-efficiënt (weinig oproepen aan RERM) zijn voor adversarieel robuust leren.

Methodologie

De auteur stelt een eenvoudig improper learning algoritme voor dat Bagging (Bootstrap Aggregatie) combineert met Robust Empirical Risk Minimization (RERM).

Het Algoritme (Bagging Robust ERMs)

Gegeven een trainingsset $S$ van grootte $n$, een betrouwbaarheidsparameter $\delta$, en een RERM oracle $\hat{f}$:

1. Stel het aantal bootstrap-stalen in op $N = O(d^\star + \log(1/\delta))$, waarbij $d^\star$ de duale VC-dimensie is van de klasse $\mathcal{F}$.
2. Voor elke $i \in \{1, \dots, N\}$:
   • Kies een willekeurige grootte $t$ uit een specifieke reeks $J_n = \{n/4, \dots, n-1\}$.
   • Neem een bootstrap-dataset $S'_i$ van grootte $t$ door middel van uniforme trekking met teruglegging uit het prefix van $S$ van lengte $t$.
   • Voer de RERM oracle uit op $S'_i$ om een voorspeller $\hat{f}_{S'_i} \in \mathcal{F}$ te verkrijgen.
3. Output de meerderheidsstem van de $N$ voorspellers: $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$.

Theoretische Benadering

De analyse wijkt af van eerdere steekproefcompressie-argumenten. In plaats daarvan wordt een leave-one-out analyse toegepast die is afgestemd op het robuuste risico:

1. Distributie over RERMs: De auteur analyseert de distributie van fouten gemaakt door RERMs getraind op willekeurige deelverzamelingen. Zij bewijzen dat voor een willekeurig testvoorbeeld $(X, Y)$ en elke perturbatie $Z \in U(X)$, het fractie van de RERMs die $Z$ foutief classificeren, klein is in verwachting ($\tilde{O}(d/n)$).
2. Leave-One-Out Bound: Door deze verwachting toe te passen op een empirische distributie, stellen zij een grens vast voor het robuuste risico van de "volledige bagging" voorspeller (een geïdealiseerde gemiddelde over alle mogelijke bootstraps).
3. Sparsificatie: Omdat de volledige bagging-voorspeller onhandelbaar is, gebruikt de auteur een sparsificatietechniek (Moran en Yehudayoff [2016]) om de geaggregeerde stem te benaderen met slechts $N = O(d^\star)$ onafhankelijke bootstrap-stalen. Deze stap koppelt de oracle-complexiteit direct aan de duale VC-dimensie $d^\star$.

Belangrijkste Bijdragen en Resultaten

1. Bovengrens: Lineaire Steekproefcomplexiteit

Het primaire resultaat (Theorema 1) stelt vast dat VC-klassen adversarieel robuust leerbaar zijn met een steekproefcomplexiteit die lineair is in de VC-dimensie $d$.

• Steekproefcomplexiteit: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$. Dit biedt een exponentiële verbetering ten opzichte van de vorige $O(\exp(d))$ grens.
• Oracle-complexiteit: Het algoritme maakt $N = O(d^\star)$ oproepen aan de RERM oracle.
• Computationele Efficiëntie: Het algoritme is paralleliseerbaar (in tegen tegenstelling tot eerdere boosting-gebaseerde benaderingen) en brengt slechts $O(d^\star n)$ computationele overhead met zich mee.
• Agnostische Setting: Door dit realizatie-resultaat te combineren met een reductie vanuit de agnostische setting (Montasser et al. [2019]), leidt de auteur een agnostische leerder af met een steekproefcomplexiteit van $\tilde{O}(\sqrt{d/n})$ en een oracle-complexiteit van $O(d^\star \log n)$.

2. Ondergrens: Noodzakelijkheid van de Duale VC-dimensie

Het artikel bewijst dat de afhankelijkheid van de duale VC-dimensie $d^\star$ in de oracle-complexiteit onvermijdelijk is (Theorema 2).

• Resultaat: Er bestaan klassen met VC-dimensie $d$ en duale VC-dimensie $d^\star = 2^{d+1}-1$ waarvoor elk algoritme dat minder dan $d^\star - 1$ oproepen doet aan een RERM oracle faalt om robuust te leren, ongeacht het aantal verstrekte trainingsvoorbeelden.
• Implicatie: In tegen tegenstelling tot klassieke PAC-leren waar $O(\log n)$ of constante ERM-oproepen volstaan, vereist adversarieel robuust leren inherent $\Omega(d^\star)$ oracle-queries. Dit benadrukt een fundamentele scheiding tussen standaard en robuust leercomplexiteit.

3. Technische Karakterisering

De resultaten impliceren dat de verfijnde complexiteitsmaat $\dim(\mathcal{F}, U)$ voorgesteld door Montasser, Hanneke en Srebro [2022] begrensd wordt door de VC-dimensie $d$, wat de conjectuur oplost dat deze maat aanzienlijk groter zou kunnen zijn.

Betekenis en Claims

Het artikel beweert een "recept" te bieden voor computationeel efficiënt robuust PAC-leren. Door aan te tonen dat een eenvoudige bagging-heuristiek gecombineerd met RERM een optimale steekproefcomplexiteit bereikt, overbrugt het werk de kloof tussen theoretische robuustheid en praktische algoritmische efficiëntie.

Belangrijke claims met betrekking tot de bijdrage van het artikel zijn onder meer:

• Exponentiële Verbetering: Van een exponentiële naar een lineaire steekproefcomplexiteit in $d$.
• Oracle-efficiëntie: Het verminderen van oracle-oproepen van $O(nd)$ naar $O(d^\star)$, wat de aanpak haalbaar maakt voor klassen waar RERM computationeel hanteerbaar is.
• Fundamentele Limiet: Het vaststellen dat de duale VC-dimensie de juiste barrière is voor oracle-efficiëntie in robuust leren, in contrast met de rol van de VC-dimensie in standaard leren.
• Praktische Relevantie: De paralleliseerbaarheid van het algoritme en de afhankelijkheid van standaard RERM-oracles (die overeenkomen met de in de praktijk gebruikte adversariële training-heuristieken) suggereren dat deze theoretische verbeteringen direct toepasbaar zijn in moderne deep learning-contexten.

De auteur merkt op dat hoewel het algoritme improper is (het geeft een meerderheidsstem uit in plaats van een enkele functie in $\mathcal{F}$), dit noodzakelijk is om deze grenzen te bereiken, wat de distinctie tussen proper en improper leren in de robuuste setting weerspiegelt. Het werk verenigt algoritmische efficiëntie met bewijsbare robuustheid, en suggereert dat efficiënt robuust leren mogelijk is als men accepteert dat men werkt met improper learners en gebruikmaakt van de duale VC-dimensie.