Technische Samenvatting: Subsampling voor Supervised Learning in Reproducing Kernel Hilbert Spaces

Probleemstelling

In het tijdperk van big data zijn de computationele kosten en het energieverbruik die gepaard gaan met het trainen van statistische leermodellen op massale datasets kritieke knelpunten geworden. Hoewel er diverse technieken voor datareductie bestaan (bijv. sketching, coresets, stochastische optimalisatie), zijn veel hiervan ofwel taak-agnostisch, ofwel afhankelijk van intratabele waarschijnlijkheden voor optimale selectie. Specifiek in de niet-parametrische supervised learning waar hypothesen liggen in een Reproducing Kernel Hilbert Space (RKHS), schieten bestaande methoden vaak tekort in het bieden van een optimaal, datarijke subsampling-schema dat de asymptotische variantie van de estimator minimaliseert. Kernel-methoden schalen doorgaans slecht ($O(n^2)$ of $O(nm)$) met de oorspronkelijke datasetgrootte $n$, en hoewel subsampling dit reduceert naar $O(s^2)$ (waarbij $s \ll n$), negeert standaard uniforme subsampling de informatieve waarde van individuele datapunten, wat leidt tot suboptimale schattingsprecisie.

Methodologie

De auteurs stellen een framework voor Subsampled Risk Minimization (SRM) in RKHS's voor, gebruikmakend van een Horvitz-Thompson herwegtingsschema om een onbevooroordeelde schatting van de empirische risico te garanderen. De kernmethodologie omvat:

1. Theoretisch Kader:

   • Setting: Niet-parametrische supervised learning (classificatie en regressie) met een convexe, tweemaal differentieerbare verliesfunctie $\ell$ en een ridge-penalty. De estimator minimaliseert een geregulariseerd empirisch risico.
   • Subsampling Strategieën: Het artikel analyseert twee strategieën:
     • Multinomiale Subsampling (met vervanging): Punten worden onafhankelijk getrokken met inclusiewaarschijnlijkheden $\pi_{n,i}$.
     • Poisson Subsampling (zonder vervanging): Punten worden onafhankelijk opgenomen met waarschijnlijkheid $s_n \pi_{n,i}$.
   • Asymptotische Analyse: Met behulp van instrumenten uit functionele probabiliteitsruimtes en martingaaltheorie, vestigen de auteurs de asymptotische normaliteit van de SRM-estimator. Ze leiden de asymptotische covariantie-operator $\Sigma^*$ af, die afhankelijk is van de inclusiewaarschijnlijkheden $\pi_{n,i}$.

2. Optimaal Subsampling Schema:

   • De auteurs definiëren L-optimaliteit als het minimaliseren van de trace van de asymptotische covariantie-operator (preconditionerd door de inverse Hessian van het ware risico).
   • Ze leiden een gesloten vorm af voor de L-optimale absolute interesse-functie $\psi^*$, die de optimale inclusiewaarschijnlijkheden dicteert:
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     waarbij $h_0$ de ware geregulariseerde risico-minimalisator is, $\ell'$ de afgeleide van de loss is, en $k$ de kernel is.
   • Dit impliceert dat datapunten met een hoge voorspellingsfout (grote $|\ell'|$) of een hoge kernel zelf-gelijkenis (high kernel self-similarity) met een hogere waarschijnlijkheid gesampled moeten worden.

3. Praktische Implementatie (Piloted Estimator):

   • Omdat $h_0$ onbekend is, stellen de auteurs een plug-in benadering voor:
     1. Bereken een pilot estimator $\hat{h}_{k_n}$ op een kleine subset van de data ($k_n \ll s_n$).
     2. Schat de optimale waarschijnlijkheden met behulp van $\hat{h}_{k_n}$.
     3. Smooth de geschatte waarschijnlijkheden om te voldoen aan technische assumpties (specifiek dat ze niet te snel naar nul convergeren) met behulp van een hyperparameter $\alpha \in (0, 1]$:
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. Voor Poisson subsampling, pas een post-hoc truncatie toe om de waarschijnlijkheden geldig te houden ($\leq 1/s_n$).
   • Theoretische garanties (consistentie en asymptotische normaliteit) worden geboden voor deze $\alpha$-piloted estimator.

Belangrijkste Bijdragen

• Asymptotische Normaliteit in RKHS: Het artikel vestigt de asymptotische normaliteit van gesubsamplede estimators in oneindig-dimensionale RKHS's, waarbij het zich onderscheidt van parametrische resultaten door gebruik te maken van functionele random probabiliteitsruimte-technieken en martingaaltheorie.
• Afleiding van Optimaal Schema: Het biedt de eerste afleiding van een optimaal subsampling-schema specifiek voor niet-parametrische kernel-methoden, waarbij wordt aangetoond dat de optimale inclusiewaarschijnlijkheid evenredig is aan de magnitude van de loss-gradiënt gewogen door de kernel-diagonaal.
• Vergelijking van Strategieën: De auteurs analyseren de trade-offs tussen Multinomiale en Poisson subsampling, en tonen aan dat de optimale keuze afhangt van de limietratio $c = \lim s_n/n$. Opmerkelijk genoeg, door de aanwezigheid van ridge-regularisatie, hebben de twee strategieën niet identieke asymptotische efficiënties wanneer $c=0$, wat afwijkt van bevindingen in parametrische settings.
• Robuust Praktisch Algoritme: Het voorstel van een twee-staps "piloted" algoritme dat een pilot estimator combineert met smoothing en truncatie maakt het theoretisch optimale schema implementeerbaar in de praktijk terwijl statistische garanties behouden blijven.

Resultaten

Numerieke experimenten werden uitgevoerd op synthetische datasets (classificatie en regressie) en een real-world dataset (UCI Covertype), waarbij de voorgestelde $\alpha$-piloted SRM werd vergeleken met:

• Uniforme subsampling (baseline).
• Nyström methode.
• Random Fourier Features (RFF).
• Kernel sketching.

Bevindingen:

• Smoothing Parameter: Een smoothing parameter $\alpha$ tussen 0.1 en 0.4 levert de beste generalisatiefout op, waarbij een balans wordt gevonden tussen de voordelen van optimale subsampling en de stabiliteit van uniforme sampling.
• Grote Data Regime: Voor grote datasets presteert de voorgestelde SRM aanzienlijk beter dan uniforme subsampling in termen van de trade-off tussen generalisatiefout en computationele tijd (CPU).
• Vergelijking met Approximaties: Op de real-world Covertype dataset was de SRM-methode efficiënter dan Nyström, RFF en sketching. Op synthetische laag-dimensionale taken waren kernel-approximaties (Nyström, RFF) sneller, wat suggereert dat subsampling en kernel-approximatie complementaire technieken zijn.
• Hybride Benadering: Het combineren van subsampling met de Nyström-methode verbeterde de prestaties verder, wat wijst op de compatibiliteit van de methode met bestaande kernel-approximatietechnieken.

Betekenis en Claims

Het artikel claimt een theoretisch gefundeerde en praktisch levensvatbare methode te bieden voor het verminderen van de computationele last van kernel-gebaseerd leren zonder statistische efficiëntie op te offeren. Door een optimaal subsampling-schema af te leiden op basis van de trace van de asymptotische covariantie, bieden de auteurs een manier om "informatieve" individuen uit grote datasets te extraheren.

De auteurs kaderen hun werk bescheiden als een stap naar meer energie-efficiënt leren, waarbij zij opmerken dat hoewel de methode de omvang van het optimalisatieprobleem reduceert van $O(n^2)$ naar $O(s^2)$, het vertrouwt op een pilot estimator. Zij erkennen dat de theorie momenteel gebaseerd is op geregulariseerde risico's en dat het uitbreiden naar niet-geregulariseerde settings of het ontwikkelen van multi-stage online procedures potentiële richtingen zijn voor toekomstig onderzoek. Het werk onderscheidt zich door de specifieke uitdagingen van de niet-parametrische RKHS-setting aan te pakken, waar bestaande parametrische subsampling-theorieën niet volledig op ingaan.