Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

1. Probleemstelling

Het paper behandelt het probleem van Gaussian Process (GP) Bandit Optimization, specifiek in een niet-Bayese setting (waarbij de functie vast maar onbekend is en ligt in een Reproducing Kernel Hilbert Space, of RKHS). Het doel is om sequentieel punten $x_t$ te selecteren om een dure black-box functie $f(x)$ te maximaliseren op basis van ruisbeïnvloede waarnemingen $y_t = f(x_t) + \epsilon_t$.

De prestaties worden gemeten aan de hand van cumulatieve regret $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$, waarbij $x^*$ het globale optimum is en $x_t^+$ het beste punt dat door het algoritme tot iteratie $t$ is gerapporteerd.

De Kernuitdaging:
Hoewel het Expected Improvement (EI) algoritme een populaire heuristiek is voor Bayesiaanse Optimalisatie vanwege zijn eenvoud, zijn de theoretische convergentie-eigenschappen ervan in de ruisbeïnvloede setting een open vraag gebleven.

• In ruisvrije settings is de "incumbent" (de huidige beste waarde) simpelweg de maximale waargenomen waarde, wat monotoon is.
• In ruisbeïnvloede settings wordt de incumbent doorgaans gedefinieerd als het maximum van het GP voorspellende gemiddelde ($\mu_t^+$) of het maximum van de ruisbeïnvloede waarneming ($y_t^+$).
• In tegenstelling tot het ruisvrije geval, is het GP voorspellende gemiddelde $\mu_t^+$ niet monotoon in de tijd. Dit gebrek aan monotonie maakt standaard theoretische analyse (die berust op het begrenzen van de regret via de monotonie van de incumbent) extreem moeilijk. Vorige werken vereisten óf het kennen van onbekende parameters (zoals de RKHS-normgrens $B$ en ruis sub-Gaussianiteit $R$) óf gebruikten niet-standaard incumbents die dure globale optimalisatiestappen vereisten.

2. Methodologie

De auteurs stellen twee hoofdalgoritmen voor om deze theoretische en praktische hiaten aan te pakken.

A. GP-EI met Standaard Incumbent

De eerste bijdrage is een rigoureuze analyse van een standaard GP-EI algoritme waarbij de incumbent wordt gedefinieerd als het maximum van het GP voorspellende gemiddelde over waargenomen punten:
$$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$$

• Acquisitiefunctie: Het algoritme selecteert het volgende punt $x_t$ door het Expected Improvement te maximaliseren:
  $$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$$
  Dit wordt in gesloten vorm berekend met de functie $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$.
• Tijdsvariërende Schaal: Om ruis te hanteren en convergentie te garanderen zonder kennis van de RKHS-norm ($B$) of ruisparameter ($R$), gebruikt het algoritme een tijdsvariërende schaalparameter $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$, waarbij $\gamma_t$ de maximale informatiewinst is.
• Kern Theoretische Innovatie: De auteurs overwinnen de niet-monotonie van $\mu_t^+$ door gebruik te maken van de monotonie van de variantiefunctie ($\sigma_t(x)$ neemt af naarmate $t$ toeneemt). Ze decomponeren de instantane regret en begrenzen de som van "verbetertermen" met behulp van deze variantie-eigenschap, een techniek die eerder niet op deze manier is toegepast op GP bandit optimalisatie.

B. Improved-GP-EI

Om beperkingen in de standaard GP-EI aan te pakken (specifiek, dat de regretgrens niet altijd sublineair is voor Matérn-kernen en dat de schaalparameter $\omega_t$ te snel groeit, wat onnodige exploratie veroorzaakt), stellen de auteurs Improved-GP-EI voor.

• Inspiratie: Aanpassing van het $\pi$-GP-UCB algoritme (Janz et al., 2020).
• Partitioneringsstrategie: De zoekruimte wordt opgedeeld in hyperkubussen (een dekking). Een onafhankelijke GP wordt op elke hyperkubus gefit met uitsluitend lokale data.
• Globale Schaal: In plaats van een tijdsvariërende $\omega_t$, gebruikt het een vaste globale schaal $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ die slechts poly-logaritmisch groeit.
• Mechanisme: In elke stap selecteert het algoritme een punt door EI te maximaliseren binnen de specifieke hyperkubus die de huidige beste kandidaat bevat, waardoor de optimalisatie effectief wordt gelokaliseerd.

3. Belangrijkste Bijdragen

1. Eerste Theoretische Garanties voor Standaard GP-EI:
   Het paper levert het eerste bewijs dat GP-EI met een standaard incumbent ($\xi = \mu_t^+$) convergeert in de ruisbeïnvloede setting.

   • Regretgrens: De cumulatieve regret is begrensd door $O(\gamma_T \sqrt{T})$.
   • Parameteronafhankelijkheid: Cruciaal is dat het algoritme geen kennis vereist van de RKHS-normgrens ($B$) of de sub-Gaussianiteitsparameter ($R$) van de ruis, die typisch onbekend zijn in real-world toepassingen.

2. Improved-GP-EI Algoritme:
   Een nieuwe variant die snellere convergentiesnelheden bereikt voor Matérn-kernen.

   • Regretgrens: Voor Matérn-kernen met gladheid $\nu > 1$ is de regret $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$. Dit is sublineair voor alle $\nu > 1$ en $d \geq 1$, wat een verbetering is ten opzichte van de beperkingen van de standaard GP-EI.
   • Efficiëntie: Door gebruik te maken van een partitioneringsstrategie en een poly-logaritmische schaalparameter, vermijdt het de snelle groei van de variantieschaal die bij eerdere methoden werd waargenomen, waardoor onnodige exploratie wordt verminderd.

3. Nieuwe Bewijstechnieken:
   De auteurs introduceren een bewijsstrategie die de niet-monotonie van de GP voorspellende gemiddelde incumbent afhandelt door gebruik te maken van de afnemende monotonie van de GP variantiefunctie om de som van verbetertermen te begrenzen.

4. Resultaten

Theoretische Resultaten

• Standaard GP-EI: Bereikt een regret van $O(\gamma_T \sqrt{T})$. Voor Squared Exponential (SE) kernen is dit sublineair. Voor Matérn-kernen vereist het $2\nu > d$ om sublineair te zijn.
• Improved-GP-EI: Bereikt een strakkere regretgrens die sublineair is voor alle $\nu > 1$. Het komt overeen met de regret-snelheid van $\pi$-GP-UCB, maar verwijdert de vereiste om $B$ en $R$ te kennen.

Empirische Resultaten

De auteurs testten hun algoritmen op synthetische functies (Hartmann3, Shekel, Hartmann6, Ackley) en functies gegenereerd vanuit RKHS-ruimten.

• Prestaties: Improved-GP-EI presteerde consequent beter dan de standaard GP-EI, Modified-GP-EI en de state-of-the-art $\pi$-GP-UCB.
• Robuustheid: In tegenstelling tot $\pi$-GP-UCB, dat heuristische afstemming van onbekende parameters ($B$ en $R$) vereist en slecht presteerde wanneer deze verkeerd werden geraamd, is Improved-GP-EI parameter-vrij wat betreft deze grenzen en toonde superieure stabiliteit.
• Efficiëntie: De partitioneringsstrategie in Improved-GP-EI verlaagde de computationele complexiteit. Bijvoorbeeld, op Hartmann3 was de gemiddelde runtime per iteratie 1,21 minuten voor Improved-GP-EI tegenover 1,37 minuten voor standaard GP-EI, waarbij het gat verder opende voor grotere horizons door de verkleinde omvang van kernelmatrix-inversies (het inverteren van kleinere lokale matrices in plaats van één globale matrix).

5. Betekenis

Dit paper lost een langdurig open probleem op in de theoretische analyse van Expected Improvement voor Gaussian Process bandits.

• Brug tussen Theorie en Praktijk: Het bewijst dat de populairste heuristiek (EI) theoretisch sound is in ruisbeïnvloede omgevingen zonder "orakel"-kennis van functiegladheid of ruisniveaus te vereisen.
• Praktische Toepasbaarheid: Door de afhankelijkheid van onbekende parameters ($B$ en $R$) te verwijderen, zijn de voorgestelde algoritmen direct toepasbaar op real-world scenario's (bijv. robotica, hyperparameter-tuning) waar deze waarden moeilijk of onmogelijk a priori te schatten zijn.
• Algoritmische Vooruitgang: De Improved-GP-EI biedt een robuust, parameter-vrij alternatief voor op UCB gebaseerde methoden, en demonstreert dat EI-gebaseerde strategieën optimale regretsnelheden kunnen bereiken terwijl ze robuuster zijn ten opzichte van kernelkeuze en parameteronzekerheid.