Technische Samenvatting: De GP uit de lus halen

Probleemstelling

Bayse Optimalisatie (BO) wordt traditioneel ingezet voor black-box problemen waarbij functiewaarden duur zijn om te evalueren, wat resulteert in weinig observaties ($N$). Echter, een groeiende klasse van problemen, aangeduid als Bayse Optimalisatie met Veel Observaties (BOMO), omvat snelle, paralleliseerbare evaluaties (bijvoorbeeld grootschalige simulaties) waarbij $N$ tienduizenden kan bereiken.

In het BOMO-regime ondervinden standaard BO-methoden een schaalbaarheidsknelpunt. Traditionele benaderingen vertrouwen op Gaussian Process (GP) surrogaten. Hoewel moderne implementaties de complexiteit van de acquisitietijd hebben gereduceerd van $O(N^3)$ tot ongeveer $O(N^2)$, blijft de vereiste om bij elke iteratie GP-hyperparameters te schatten een aanzienlijke computereis. Dit schattingsproces, dat vaak de reconstructie van de kernelmatrix omvat, schaalt slecht met $N$, wat de toepassing van BO op problemen met enorme aantallen observaties belemmert.

Methodologie

De auteurs stellen TuRBO-ENN voor, een methode die de GP-surrogaat in het Trust Region Bayse Optimalisatie (TuRBO)-kader vervangt door een lichtgewicht alternatief genaamd Epistemic Nearest Neighbors (ENN).

1. Epistemic Nearest Neighbors (ENN)

ENN is een op K-nearest-neighbor (KNN) gebaseerde surrogaat die is ontworpen om zowel functiewaarden als onzekerheid (epistemisch en aleatorisch) te schatten met lineaire schaling.

• Surrogaatconstructie: Voor een vraagpunt $x$ identificeert ENN de $K$ dichtstbijzijnde buren in de observatiestel $D$. Het behandelt elke buur als een onafhankelijke schatting van de functiewaarde.
• Kwantificering van onzekerheid:
  • Aleatorische variantie ($\sigma_a^2$): Gemodelleerd als de som van een basisruisniveau ($s_0^2$) en de specifieke ruisgrootte van de observatie ($s_m^2$).
  • Epistemische variantie ($\sigma_e^2$): Gemodelleerd als evenredig met het kwadraat van de Euclidische afstand tussen het vraagpunt en de buur ($c_e d^2(x, x_m)$).
• Aggregatie: De uiteindelijke gemiddelde schatting $\mu(x)$ en variantieschattingen worden berekend met behulp van een precisie-gewogen gemiddelde (inverse variantiegewichting) van de $K$ buren. Dit vermijdt de $O(N^2)$ paarsgewijze covariantieberekeningen die door GPs worden vereist.
• Complexiteit: Het vinden van $K$ dichtstbijzijnde buren met behulp van een max-heap of Faiss-bibliotheek kost $O(N \ln K)$ per vraag. Het schatten van hyperparameters ($s_0, c_e$) wordt uitgevoerd via Type-II Maximum Likelihood Estimation (MLE) op een Leave-One-Out Cross-Validation (LOOCV) pseudolikelihood, benaderd met een subsample van vaste grootte om $O(N)$ schaling te behouden.

2. Integratie van TuRBO-ENN

De methode integreert ENN in het TuRBO-algoritme, dat een vertrouwensgebied gebruikt om de zoekinspanningen te focussen.

• Ruizige doelen: Voor problemen met ruis past de methode ENN-hyperparameters aan en gebruikt de Upper Confidence Bound (UCB) acquisitiefunctie: $UCB(x) = \mu(x) + \sigma(x)$.
• Ruisvrije doelen: Voor deterministische problemen stellen de auteurs een variant zonder schatting voor. Aangezien het schatten van hyperparameters onnodig is wanneer ruis bekend is als nul, selecteert de methode kandidaten via Non-Dominated Sorting (NDS) over het paar $(\mu(x), \sigma(x))$. Dit elimineert de schattingsstap volledig, wat de voorsteltijd verder verlaagt.
• Pseudo-Bayse Optimalisatie (PBO): De auteurs verifiëren dat TuRBO-ENN voldoet aan de voorwaarden voor Pseudo-Bayse Optimalisatie (Chen & Lam, 2025), waardoor theoretische convergentiegaranties worden gewaarborgd.

Belangrijkste Bijdragen

1. ENN-surrogaat: Introductie van een lichtgewicht KNN-surrogaat dat functiewaarden en onzekerheid schat met $O(N)$ schattings- en vraagtijd, in tegenstelling tot de $O(N^2)$ of $O(N^3)$ schaling van GPs.
2. TuRBO-ENN-algoritme: Ontwikkeling van een BO-methode die de GP en Thompson Sampling van TuRBO vervangt door ENN en UCB (of NDS voor ruisvrije gevallen).
3. Empirische validatie: Aantonen dat TuRBO-ENN de voorsteltijd (schatting + acquisitie) met één tot twee ordes van grootte reduceert ten opzichte van TuRBO-GP op problemen met tot 50.000 observaties, zonder in te leveren op de oplossingskwaliteit.
4. Theoretische garantie: Verificatie dat TuRBO-ENN kwalificeert als een PBO-methode, waarbij convergentiegaranties worden geërfd.
5. Open source: Uitgifte van het ennbo Python-pakket.

Experimentele Resultaten

De auteurs hebben TuRBO-ENN getoetst aan state-of-the-art methoden (TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP) op vijf simulatietaken (LunarLander, Hopper, BipedalWalker, Push) en een hyperparameteroptimalisatietaken (LASSO-DNA) met dimensies variërend van 12 tot 180.

• Schaalbaarheid: Waar GP-gebaseerde methoden (bijvoorbeeld turbo-one, ucb) ongeveer $O(N^2)$ schaling vertoonden in de voorsteltijd, schaalde TuRBO-ENN lineair ($O(N)$).
• Snelheidswinst: TuRBO-ENN behaalde snelheidswinsten variërend van 8,5x tot 151x ten opzichte van TuRBO-GP, met grotere winsten waargenomen bij hogere aantallen observaties ($N$) en in settings met vaste ruis (ruisvrij) waar het schatten van hyperparameters werd overgeslagen.
• Oplossingskwaliteit: TuRBO-ENN kwam overeen met de optimalisatieprestaties (oplossingskwaliteit) van TuRBO-GP over alle geteste taken.
• Schattingstaken: In pure regressietaken (synthetische data) was ENN ordes van grootte sneller om te schatten dan Exacte GPs, SVGP en neurale netwerk-surrogaten, terwijl het concurrerende log-likelihoods op de testset behield.

Betekenis en Beweringen

Het artikel betoogt dat naarmate simulatiecapaciteiten groeien, het knelpunt in Bayse Optimalisatie verschuift van de kosten van functiewaarde-evaluatie naar de computerkosten van het optimalisatiealgoritme zelf (voorsteltijd). Door de Gaussian Process uit de lus te halen, stelt TuRBO-ENN BO in staat om te schalen naar regimes met tienduizenden observaties, waar traditionele methoden computationeel onbetaalbaar worden.

De auteurs maken bescheiden de bewering dat hun methode een praktische, schaalbare alternatief biedt voor BOMO-problemen, met een "schatting-vrije" optie voor deterministische simulaties en een lineair-schalende optie voor ruizige, terwijl ze tegelijkertijd de theoretische convergentie-eigenschappen van Bayse optimalisatie behouden. Zij merken op dat hoewel ze convergentiegaranties bereiken via PBO-axioma's, ze geen specifieke regretgrenzen bieden. Toekomstige werkrichtingen die worden voorgesteld, omvatten het aanpassen van ENN aan benaderende naaste-buur-algoritmen voor $O(\ln N)$ schaling en het verkennen van dimensiespecifieke weging in de afstandsmetriek.