Bayesian Optimistic Optimisation with Exponentially Decaying Regret

1. Probleemstelling

Het artikel behandelt het probleem van globale optimalisatie voor dure, ruisvrije, black-box functies $f(x)$ waarbij $x \in \mathcal{X} \subset \mathbb{R}^D$. Het doel is om het globale maximum $x^*$ te vinden met een beperkt budget aan functiewaarde-bepalingen $N$.

De prestaties worden gemeten aan de hand van simple regret:
$$r_N = \sup_{x \in \mathcal{X}} f(x) - \max_{1 \le i \le N} f(x_i)$$

Bestaande Beperkingen:

• Bayesian Optimization (BO): Standaard BO-algoritmen (zoals GP-UCB, GP-EI) bereiken doorgaans sub-lineaire regret-grenzen (bijvoorbeeld $O(\sqrt{\frac{\log N}{N}})$ of $O(1/\sqrt{N})$). Een grote knelpunt is dat BO bij elke iteratie een hulpoptimalisatieprobleem moet oplossen (het maximaliseren van de acquisitiefunctie), wat rekenkundig duur en moeilijk is in hoge dimensies.
• Optimistic Optimization (Boomgebaseerd): Algoritmen zoals SOO en BaMSOO partitioneren de zoekruimte hiërarchisch. Hoewel ze hulpoptimalisatie vermijden, lijden ze onder een streng negatieve correlatie tussen de vertakkingsfactor $m$ (granulariteit van partitionering) en het aantal boomuitbreidingen. Om fijne partities te bereiken (grote $m$), moeten ze veel kindknopen evalueren, waardoor het evaluatiebudget $N$ snel wordt opgebruikt. Bijgevolg zijn hun worst-case regret-grenzen vaak beperkt tot $O(e^{-\sqrt{N}})$ of sub-lineaire snelheden.

De auteurs vragen zich af: Kunnen we een praktisch algoritme ontwerpen dat de model-efficiëntie van BO combineert met de structurele voordelen van boomgebaseerde optimistische optimalisatie om een strakkere regret-grens te bereiken (specifiek $O(N^{-\sqrt{N}})$), zonder de rekenkosten van hulpoptimalisatie?

2. Methodologie: Het BOO-algoritme

De auteurs stellen Bayesian Optimistic Optimisation (BOO) voor, een nieuw algoritme dat Gaussische Processen (GP) integreert met een gemodificeerde hiërarchische boomzoektocht.

Belangrijkste Innovaties

1. Ontkoppeling van Vertakkingsfactor en Evaluaties:

   • Traditionele Aanpak: In SOO/BaMSOO vereist het uitbreiden van een knoop het evalueren van $m$ kinderen. Het aantal uitbreidingen is dus beperkt tot $N/m$.
   • BOO-Aanpak: Het algoritme selecteert een knoop om uit te breiden op basis van de GP-Upper Confidence Bound (GP-UCB). Cruciaal is dat het alleen de objectieve functie evalueert bij de geselecteerde ouderknoop, niet bij zijn $m$ kinderen. De kinderen worden structureel aan de boom toegevoegd maar blijven ongeëvalueerd totdat ze later worden geselecteerd.
   • Resultaat: Dit "ontkoppelt" de vertakkingsfactor $m$ van het evaluatiebudget. Het algoritme kan een zeer grote $m$ gebruiken om extreem fijne partities te creëren zonder de kosten van $m$ evaluaties per stap te betalen.

2. Nieuwe Partitioneringsprocedure $P(m; a, b)$:

   • In plaats van alleen de langste zijde van een cel te verdelen (standaard in SOO), decomposeert BOO de vertakkingsfactor als $m = a^b$.
   • Het verdeelt de cel langs zijn $b$ langste dimensies in elk $a$ gelijke delen.
   • Door $b = D$ (de dimensionaliteit) te stellen, partitioneert het algoritme alle dimensies gelijktijdig. Dit staat toe dat de zoekruimte in alle richtingen veel sneller wordt verfijnd in vergelijking met sequentiële dimensie-splitsing.

3. Samplingstrategie:

   • Het algoritme onderhoudt een GP-model.
   • Bij elke stap selecteert het het blad met de hoogste GP-UCB-waarde.
   • Het evalueert $f$ alleen in het centrum van deze geselecteerde knoop.
   • Het update het GP en de boomstructuur, waarbij $m$ kinderen aan de geselecteerde knoop worden toegevoegd.

Algoritme Flow (Vereenvoudigd)

1. Initialiseer een boom met een wortelknoop.
2. Selecteer het blad $(h, i)$ met de maximale GP-UCB-waarde $U_p(c_{h,i})$.
3. Als $U_p(c_{h,i}) \ge v_{max}$ (huidige beste waargenomen waarde):
   • Evalueer $f$ in het centrum van de knoop.
   • Update de dataset en pas het GP opnieuw aan.
   • Breid de knoop uit door $m$ kinderen toe te voegen met de partitioneringsregel $P(m; a, b)$.
4. Herhaal totdat het budget $N$ is uitgeput.

3. Theoretische Bijdragen & Regret-analyse

Het artikel biedt een rigoureuze theoretische analyse onder de aanname dat $f$ is bemonsterd uit een Gaussisch Proces met een Matérn-kern met gladheidsparameter $\nu > 4 + \frac{D}{2}$.

• Regret-grens: De auteurs bewijzen dat BOO een simple regret-grens bereikt van:
  $$r_N = O(N^{-\sqrt{N}})$$
  Dit is een exponentieel afnemende regret die strikt strakker is dan de $O(e^{-\sqrt{N}})$-grens van eerdere state-of-the-art optimistische algoritmen (zoals IMGPO) en aanzienlijk beter dan standaard BO-grenzen.

• Belangrijkste Theoretisch Mechanisme:

  • Het bewijs berust op het begrenzen van de grootte van de "uitbreidingsset" (knopen die potentieel het optimum kunnen bevatten).
  • Door gebruik te maken van de nieuwe partitionering ($b=D$) en de grote vertakkingsfactor $m$, wordt aangetoond dat de "near-optimality dimension" effectief 0 is.
  • De ontkoppeling van $m$ van evaluaties stelt het algoritme in staat om de ruimte met hoge granulariteit ($m$ groot) te verkennen terwijl het lage evaluatiekosten behoudt, wat leidt tot de verbeterde convergentiesnelheid.

4. Experimentele Resultaten

De auteurs hebben BOO gevalideerd op synthetische benchmarks en real-world machine learning hyperparameter-tuning taken.

• Baselines: Vergelijken met GP-EI, GP-UCB, SOO, BaMSOO en IMGPO.
• Synthetische Functies: Getest op Hartmann3, Schwefel en Shekel functies.
  • Resultaat: BOO presteerde consequent beter dan alle baselines op het gebied van convergentiesnelheid (log-afstand tot optimum). Het bereikte de beste prestaties op Hartmann en Schwefel, en concurrerende prestaties op Shekel.
• Hyperparameter Tuning:
  • Taken: Tunen van ElasticNet, MLP en XGBoost op MNIST en Skin Segmentation datasets.
  • Resultaat: BOO bereikte lagere voorspellingsfouten in vergelijking met alle baselines. Voor XGBoost presteerde het met een grote marge beter dan de anderen.
• Rekenkundige Efficiëntie:
  • BOO is aanzienlijk sneller dan GP-EI en GP-UCB omdat het de dure maximalisatie van acquisitiefuncties over continue ruimtes vermijdt.
  • Het is iets trager dan IMGPO vanwege de overhead van het beheren van een grotere boom (grote $m$), maar de afweging levert superieure optimalisatieprestaties op.

5. Betekenis en Conclusie

• Doorbreken van de Regret-barrière: Dit is het eerste praktische algoritme dat een regret-grens van $O(N^{-\sqrt{N}})$ bereikt voor Bayesian optimization, waarmee de theoretische limieten van eerdere optimistische en Bayesiaanse methoden worden overtroffen.
• Praktijktoepasbaarheid: In tegenstelling tot eerdere theoretische benaderingen die onpraktische sampling vereisten (zoals $\delta$-cover sampling), is BOO implementeerbaar en efficiënt.
• Synergie: Het werk slaagt erin de kloof te overbruggen tussen Model-Based Optimization (BO) en Model-Free Optimistic Optimization, en demonstreert dat het integreren van een GP-model in een boomgebaseerde structuur met een specifieke samplingstrategie exponentiële verbeteringen in convergentie kan opleveren.
• Toekomstig Werk: De auteurs merken plannen op om de methode uit te breiden naar ruisige settings en hogere dimensionale ruimtes.

Kortom, het artikel presenteert een significante vooruitgang in de theorie en praktijk van globale optimalisatie door een mechanisme te introduceren om zoekgranulariteit te ontkoppelen van evaluatiekosten, wat resulteert in een state-of-the-art regret-grens en superieure empirische prestaties.