Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference

Technische Samenvatting: Warm-starting van Iteratieve Gaussische Processen voor Snellere Sequentiële Inferentie

Probleemstelling
Gaussische Processen (GP's) zijn krachtige niet-parametrische modellen voor regressie, classificatie en Bayesiaanse optimalisatie, maar hun schaalbaarheid wordt beperkt door de $O(n^3)$ kosten van het inverteren van de covariantie-matrix om de posterieur te berekenen. Hoewel iteratieve oplosmethoden (bijv. Conjugate Gradients, Stochastic Gradient Descent, Alternating Projections) een manier bieden om de kubische kosten te vermijden door de oplossing te benaderen, vereisen ze doorgaans veel iteraties om te convergeren. In sequentiële omgevingen—zoals actieve leerprocessen, online voorspelling en Bayesiaanse optimalisatie—waar gegevens incrementeel binnenkomen en de posterieur frequent moet worden bijgewerkt, vormt de standaard "cold-start" aanpak (waarbij alle gewichten op nul worden geïnitialiseerd en de vorige berekening wordt weggegooid) een bottleneck. Deze inefficiëntie beperkt de effectiviteit van iteratieve GP's in dynamische omgevingen.

Methodologie
Het artikel stelt drie "warm-start" strategieën voor om de initiële waarden van iteratieve lineaire oplosmethoden te bepalen wanneer een GP-posterieur wordt bijgewerkt met nieuwe datapunten. In plaats van de uitgebreide lineaire systeem vanaf nul op te lossen, maken deze methoden gebruik van de oplossing ($u_1$) van het vorige, kleinere lineaire systeem om de gewichten ($v$) van het nieuwe, grotere systeem te initialiseren.

Het probleem wordt geformuleerd als het oplossen van een uitgebreid lineair systeem $Hv = b$, waarbij de matrix $H$ en vector $b$ zijn gepartitioneerd om bestaande data (blok 1) en nieuwe data (blok 2) te bevatten. De drie voorgestelde initialisatiemethoden zijn:

1. Naïeve Warm-Start: De gewichten die overeenkomen met de oorspronkelijke data ($v_1$) worden geïnitialiseerd met de vorige oplossing ($u_1$), terwijl de gewichten voor de nieuwe data ($v_2$) op nul worden geïnitialiseerd.
   $$v \leftarrow \begin{bmatrix} u_1 \\ 0 \end{bmatrix}$$
2. Residual Line Search: Deze methode verbetert de naïeve aanpak door een lineaire zoekopdracht (line search) uit te voeren om de optimale scalaire $\alpha$ voor de nieuwe gewichten ($v_2$) te bepalen in de richting van de residu. Dit minimaliseert de kwadratische doelfunctie gegeven de vaste $v_1 = u_1$.
   $$v_2 = \alpha^* r, \quad \text{waarbij } r = b_2 - H_{12}^\top u_1 \text{ en } \alpha^* = \frac{r^\top r}{r^\top H_{22} r}$$
3. Marginal System Solve: De meest complexe methode lost een kleiner marginaal lineair systeem ($H_{22}v_2 = r$) op om de optimale $v_2$ te vinden die de doelfunctie minimaliseert gegeven $v_1 = u_1$.
   $$v_2 = H_{22}^{-1} r$$

Theoretische Analyse
De auteurs bieden theoretische ondersteuning via de Reproducing Kernel Hilbert Space (RKHS) afstand, gedefinieerd als $d^2 = (v - v^*)^\top H (v - v^*)$, waarbij $v^*$ de exacte oplossing is. Zij demonstreren dat:

• De naïeve warm-start de initiële RKHS-afstand strikt vermindert vergeleken met een cold-start ($d^2_{cold} - d^2_{naïve} \geq 0$).
• Zowel de residual line search als de marginal system solve deze afstand verder verkleinen ($d^2_{naïve} > d^2_{line-search} > d^2_{marginal-solve}$).
• Het verminderen van de RKHS-afstand gelijkstaat aan het verminderen van het initiële residu van het lineaire systeem, wat direct correleert met het aantal benodigde iteraties voor convergentie.

Belangrijkste Bijdragen en Resultaten
Het artikel introduceert deze drie initialisatiestrategieën en valideert deze via theoretische analyse en empirische experimenten op regressie-benchmarks en Bayesiaanse optimalisatie-taken.

• Regressie-experimenten: Gebruikmakend van datasets uit de UCI repository (bijv. 3droad, protein, buzz), vergeleken de auteurs het aantal iteraties dat nodig is voor convergentie met een cold-start baseline.

  • Versnellingen: Bij het oplossen tot een specifieke tolerantie, bereikte warm-starting versnellingen van respectievelijk tot 1.4× voor Conjugate Gradients (CG), 1.5× voor Stochastic Gradient Descent (SGD) en 4.0× voor Alternating Projections (AP).
  • Extreme gevallen: Voor AP bereikten de versnellingen tot wel 19× op bepaalde datasets, met name wanneer de ratio van nieuwe data ten opzichte van bestaande data klein is.
  • Nauwkeurigheid: Onder een vastgesteld rekenbudget (beperkte iteraties) produceerde warm-starting nauwkeurigere posterieur-schattingen, wat de uiteindelijke residu-norm verminderde.

• Bayesiaanse Optimalisatie (Parallel Thompson Sampling): In een experiment met parallel Thompson sampling met een vast rekenbudget, werden de methoden geëvalueerd op hun vermogen om een doelfunctie te maximaliseren.

  • Prestatiewinsten: De warm-start methoden verbeterden de uiteindelijke gevonden maximumwaarde van de doelfunctie met respectievelijk tot 13% voor CG, 46% voor SGD en 10% voor AP vergeleken met cold-starting.
  • Geaccumuleerde progressie: De resultaten gaven aan dat de progressie van de solver accumuleert over meerdere sequentiële oplossingen bij warm-starting, in plaats van te resetten, wat leidt tot nauwkeurigere posterieur-steekproeven en betere optimalisatieprestaties.

Betekenis
Dit artikel vestigt warm-starting als een eenvoudige, effectieve en breed toepasbare tool om de schaalbaarheid van Gaussische processen in sequentiële settings te vergroten. Door gebruik te maken van oplossingen van kleinere lineaire systemen, versnellen deze methoden de convergentie aanzienlijk zonder dat er sparse benaderingen nodig zijn die de nauwkeurigheid opofferen. De auteurs stellen dat deze aanpak direct de schaalbaarheids-bottleneck in sequentiële besluitvormingstaken aanpakt, waardoor frequentere en nauwkeurigere posterieur-updates mogelijk zijn binnen dezelfde computationele beperkingen. De methoden worden gepresenteerd als praktische verbeteringen die kunnen worden geïntegreerd met bestaande iteratieve oplosmethoden (CG, SGD, AP) om de efficiëntie van GP-gebaseerde toepassingen te verbeteren.