Cost-aware Stopping for Bayesian Optimization

Technische Samenvatting: Kostenbewust Stoppen voor Bayesiaanse Optimalisatie

Probleemstelling
In automatische machine learning, wetenschappelijke ontdekking en andere toepassingen van Bayesiaanse optimalisatie (BO), worden beoefenaars geconfronteerd met de uitdaging om te beslissen wanneer de evaluatie van dure black-box functies moet worden beëindigd. Hoewel er bestaande stopregels zijn, houden deze vaak geen rekening met variërende evaluatiekosten op een principiële wijze.

• Heuristische regels (bijv. vaste iteratieaantallen of stoppen wanneer de beste waarde ongewijzigd blijft) missen theoretische garanties en kunnen te vroeg stoppen of onnodige evaluaties veroorzaken.
• Regret-gebaseerde regels (bijv. UCB-LCB, Knowledge Gradient) zijn theoretisch onderbouwd voor het minimaliseren van eenvoudige regret, maar zijn doorgaans ontworpen voor situaties met uniforme kosten. Ze houden geen expliciet rekening met evaluatiekosten, wat vaak leidt tot excessieve cumulatieve kosten en een hoge kosten-gecorrigeerde regret wanneer de kosten hoog zijn.
• Kostenbewuste acquisitiefuncties (bijv. Pandora's Box Gittins Index (PBGI) en log expected improvement per cost (LogEIPC)) zijn ontwikkeld om de afweging tussen de kwaliteit van de oplossing en de kosten te optimaliseren, maar hun integratie met adaptieve stopregels is nog niet systematisch bestudeerd.

Het kerndoel is het ontwerpen van een stopregel die de verwachte kosten-gecorrigeerde eenvoudige regret optimaliseert, gedefinieerd als de som van de eenvoudige regret (het verschil tussen de beste gevonden oplossing en het wereldwijde optimum) en de cumulatieve kosten van gegevensverzameling.

Methodologie
De auteurs stellen een nieuwe, principiële kostenbewuste stopregel voor, afgeleid van het Pandora's Box beslissingskader. De methodologie legt een theoretische verbinding tussen twee state-of-the-art kostenbewuste acquisitiefuncties:

1. Pandora's Box Gittins Index (PBGI): Afgeleid van de dynamische programmeringsoplossing voor het Pandora's Box-probleem, aangepast voor gecorreleerde Bayesiaanse optimalisatie.
2. Log Expected Improvement per Cost (LogEIPC): Een eenstapsbenadering van het Bayesiaanse optimale beleid.

De voorgestelde stopregel, de PBGI/LogEIPC stopregel genoemd, wordt gedefinieerd door de voorwaarde dat de optimalisatie moet stoppen wanneer geen ongeobserveerd punt een verwachte verbetering biedt die zijn evaluatiekosten waard is. Wiskundig gezien stopt de regel op tijdstip $\tau$ wanneer:
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
of equivalent aan:
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
waar $y^*_{1:\tau}$ de tot nu toe beste geobserveerde waarde is.

Belangrijke implementatiedetails omvatten:

• Timing van de Posterior Update: De regel maakt gebruik van de acquisitiefunctiewaarden die berekend zijn na de posterior update van de huidige iteratie (vooruitkijkend), wat de auteurs naar verluidt beter reflecteert met de "fair value" intuïtie en empirische winst oplevert ten opzichte van achteruitkijkende benaderingen.
• Omgaan met onbekende kosten: Wanneer kosten onbekend zijn, worden ze stochastisch gemodelleerd (bijv. als een Gaussian Process op de log-kosten), en wordt de verwachte kosten $E[c(x)]$ gebruikt in de stopvoorwaarde.
• Stabilisatie: Om spookachtige stops te voorkomen die worden veroorzaakt door modelfluctuaties of imperfecte optimalisatie van de acquisitiefunctie (vooral in hoge dimensies), dwingen de auteurs een stabilisatieperiode af en passen ze een voortschrijdend gemiddelde toe voor het opschonen van het stop signaal.

Belangrijkste Bijdragen

1. Een Nieuwe Kostenbewuste Stopregel: Het artikel presenteert een adaptieve stopregel afgeleid van de Pandora's Box-theorie die zich natuurlijk uitbreidt naar het principe van verwachte verbetering. Het biedt een verenigd kader dat toepasbaar is op zowel klassieke als kostenbewuste BO.
2. Theoretische Garanties: De auteurs bewijzen dat wanneer de voorgestelde stopregel wordt gekoppeld aan ofwel PBGI of LogEIPC acquisitiefuncties, deze voldoet aan een theoretische bovengrens op de verwachte kosten-gecorrigeerde eenvoudige regret. Specifiek is het beleid gegarandeerd niet slechter te presteren dan de "onmiddellijke stopping" baseline (stoppen direct na de eerste evaluatie). Dit vormt de eerste theoretische garantie van dit type voor elke adaptieve stopregel in Bayesiaanse optimalisatie.
3. Empirische Validatie: De studie biedt een systematische evaluatie over synthetische taken en empirische benchmarks (LCBench voor hyperparameteroptimalisatie en NATS-Bench voor neurale architectuurzoektoestanden).

Resultaten

• Synthetische Taken: In 1D en 8D Bayesiaanse regret-settings met uniforme, lineaire en periodieke kostenfuncties, presteert de PBGI/LogEIPC stopregel samen met de bijbehorende acquisitiefunctie consistent gelijk aan of beter dan andere paren (inclusief UCB-LCB, LogEIPC-med, en PRB). Het is bijzonder robuust in scenario's met hoge kosten.
• Empirische Benchmarks:
  • Op LCBench (35 datasets) staat de voorgestelde regel gekoppeld aan PBGI of LogEIPC in de top 3 voor ongeveer 75% van de taken.
  • Op NATS-Bench presteert de regel competitief en nadert het de hindsight-optimale prestaties.
  • De regel stopt betrouwbaar vóór de iteratiegrens (200 iteraties), terwijl baseline regret-gebaseerde regels (zoals SRGap-med en UCB-LCB) vaak niet vroegtijdig stoppen, wat excessieve kosten met zich meebrengt.
  • De auteurs merken op dat onderprestatie op specifieke kleine datasets waarschijnlijk te wijten is aan benchmark-intrinsieke validatie/test mismatch in plaats van aan de stopregel zelf.

Betekenis en Claims
De auteurs claimen een kritische maar onderbelichte praktische overweging in Bayesiaanse optimalisatie aan te pakken: de kostenbewuste bepaling van wanneer men moet stoppen.

• Theoretische Vooruitgang: Het werk overbrugt de kloof tussen kostenbewuste acquisitiefuncties en adaptief stoppen, en biedt de eerste formele garantie dat een adaptief beleid niet een slechtere kosten-gecorrigeerde regret zal veroorzaken dan onmiddellijk stoppen.
• Praktisch Nut: De voorgestelde regel elimineert de noodzaak voor heuristische afstemming van stopdrempels (bijv. vaste constanten of mediaan-gebaseerde drempels) door de drempel direct af te leiden van de evaluatiekosten.
• Robuustheid: Het framework demonstreert robuustheid over variërende kostenstructuren en modelmisspecificaties, en biedt een principieel alternatief voor heuristische stopcriteria in dure optimalisatietaken.

De auteurs concluderen dat hun framework kan worden uitgebreid naar settings die ruisende, multi-fidelity of gebundelde (batched) evaluaties bevatten, evenals naar alternatieve objectieve formuleringen, hoewel dit als toekomstige richtingen worden genoteerd en niet als huidige bijdragen.