Technische Samenvatting: Schaalbare Batch Bayesiaanse Optimalisatie via Subruimte-acquisitiefuncties

Probleemstelling

Bayesiaanse Optimalisatie (BO) is een krachtig raamwerk voor het oplossen van dure, black-box optimalisatieproblemen. Hoewel standaard BO sequentieel werkt—waarbij telkens één steekproefpunt wordt geselecteerd—is deze aanpak inefficiënt wanneer parallel rekenkracht beschikbaar is. Om parallellisme te benutten, zijn Batch Bayesiaanse Optimalisatie-algoritmen vereist om meerdere steekproeven gelijktijdig te evalueren.

Bestaande batch-benaderingen kampen echter met aanzienlijke schaalbaarheidsproblemen naarmate de batchgrootte ($q$) toeneemt:

• Multi-point Expected Improvement (qEI): Hoewel theoretisch solide, brengt het optimaliseren van qEI een zoekruimte met zich mee van dimensie $d \times q$ (waarbij $d$ de dimensie van het probleem is). Naarmate $q$ groeit, nemen de computationele kosten van het evalueren van de multivariate cumulatieve distributiefunctie en de moeilijkheid van het optimaliseren van de acquisitiefunctie exponentieel toe, wat qEI en varianten (zoals FqEI, qLogEI) onpraktisch maakt voor grote batchgroottes (doorgaans $q > 10$).
• Heuristische Benaderingen (bijv. Kriging Believer, Constant Liar, Local Penalization): Deze methoden vertrouwen vaak op "nep"-punten of kunstmatige straffuncties om batch-effecten te simuleren. Naarmate de batchgrootte toeneemt, verslechtert de accumulatie van deze kunstmatige punten de nauwkeurigheid van het Gaussian Process (GP) model, wat de zoekrichting kan misleiden en de optimalisatie-efficiëntie kan verminderen.
• Multi-objective en Multi-model Benaderingen: Methoden die meerdere surrogaatmodellen trainen of multi-objective optimalisatieproblemen oplossen, brengen vaak hoge computationele kosten met zich mee die niet goed schalen met grote batchgroottes.

De kernuitdaging die in dit werk wordt aangepakt, is het ontwerpen van een batch-acquisitiestrategie die computationeel hanteerbaar en effectief blijft voor grootschalige batch-evaluaties zonder te lijden onder de vloek van dimensionaliteit of modeldegradatie.

Methodologie

De auteurs stellen een nieuwe aanpak voor genaamd Subspace Acquisition Functions, die bestaande acquisitiefuncties (specifiek Expected Improvement, maar ook aanpasbaar naar PI en UCB) uitbreidt om te opereren binnen willekeurig gekozen, as-gerichte subruimten.

Kernconcept: Subspace Expected Improvement (SSEI)

In plaats van te zoeken naar $q$ punten in de volledige $d$-dimensionale ontwerpruimte tegelijkertijd, doet de methode het volgende:

1. Selecteert Subruimten: Selecteert willekeurig een reeks as-gerichte subruimten. Een $k$-dimensionale as-gerichte subruimte wordt gedefinieerd door $k$ coördinaten te kiezen uit de oorspronkelijke $d$ dimensies, terwijl de resterende $d-k$ coördinaten worden vastgezet op de waarden van de huidige beste oplossing ($x_{min}$).
2. Optimaliseert Lokaal: Voor elke geselecteerde subruimte wordt de standaard acquisitiefunctie (bijv. EI) geoptimaliseerd alleen over de $k$ actieve variabelen. De niet-geselecteerde variabelen blijven vastgezet op $x_{min}$.
3. Genereert Batch: Eén querypunt wordt geselecteerd uit elke unieke subruimte. Als de vereiste batchgrootte $q$ de grootte van het aantal beschikbare subruimten ($N = 2^d - 1$) overstijgt, gebruikt de methode Subspace Multi-Point Expected Improvement (SSqEI), die meerdere punten binnen een enkele subruimte optimaliseert.

Computationeel Raamwerk

Het voorgestelde algoritme (Algoritme 1) werkt als volgt:

• Initialisatie: Genereer initiële steekproeven en train een GP-model.
• Subruimte Selectie: Trek willekeurig een geheel tal $k \in [1, d]$ en vervolgens een willekeurige combinatie van $k$ coördinaten om een subruimte te vormen. Dit voorkomt de computationele kosten van het enumereren van alle mogelijke subruimten.
• Acquisitie Optimalisatie:
  • Als $q \le N$: Selecteer $q$ verschillende subruimten en optimaliseer de standaard SSEI in elke subruimte om één punt per subruimte te vinden.
  • Als $q > N$: Verdeel de $q$ punten over de beschikbare $N$ subruimten (waarbij meerdere punten per subruimte worden geoptimaliseerd met SSqEI).
• Evaluatie: Evalueer de resulterende batch van $q$ punten parallel.
• Update: Update het GP-model met de nieuwe observaties en herhaal.

De dimensionaliteit van de optimalisatie van de acquisitiefunctie wordt gereduceerd van $d \times q$ naar ongeveer $k \times 1$ (of $k \times q_i$ voor SSqEI), waarbij de verwachte dimensie $E[k] \approx d/2$. Dit vermindert de complexiteit van de acquisitie-optimalisatie aanzienlijk.

Belangrijkste Bijdragen

1. Schaalbare Batch-strategie: Het artikel introduceert een methode om Bayesiaanse optimalisatie uit te breiden naar grote batchgroottes door de batchselectie te ontkoppelen in onafhankelijke of laag-dimensionale subruimte-optimalisaties, waardoor de exponentiële complexiteit van qEI wordt vermeden.
2. Eenvoud en Generaliseerbaarheid: De aanpak vereist geen extra hyperparameters en is toepasbaar op een breed scala aan acquisitiefuncties (gedemonstreerd op EI, PI en UCB). Het is conceptueel eenvoudig: "teken subruimten, optimaliseer lokaal, aggregeer."
3. Robuustheid tegen Dimensionaliteit: Door de zoektocht te beperken tot as-gerichte subruimten verankerd aan de huidige beste oplossing, balanceert de methode van nature exploratie (via willekeurige subruimte selectie) en exploitatie (via lokale zoektocht rond $x_{min}$), wat het bijzonder effectief maakt in hoog-dimensionale ruimten.

Experimentele Resultaten

De auteurs evalueerden de voorgestelde methode (SSEI) tegen tien state-of-the-art batch-algoritmen (inclusief qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB en Random Search) op 60 synthetische benchmark-problemen (GPMean, SumSquares, Rosenbrock, etc.) over dimensies $d \in \{2, 4, 8, 10, 20, 30\}$ en batchgroottes $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Prestaties vs. Sequentiële BO: Wanneer $q=1$, presteert SSEI vergelijkbaar met standaard EI op laag-dimensionale problemen, maar presteert het aanzienlijk beter dan EI op hoog-dimensionale problemen ($d \ge 8$). De auteurs schrijven dit toe aan het feit dat sequentiële EI moeite heeft met het optimaliseren van de acquisitiefunctie in hoge dimensies, terwijl de lokale subruimte-zoektocht van SSEI betere lokale optima voor de acquisitiefunctie vindt.
• Schaalbaarheid met Batchgrootte:
  • Kleine tot Middelgrote Batches ($q \le 32$): SSEI bereikt bijna een lineaire versnelling in termen van wandkloktijd (iteraties) terwijl het prestaties behoudt die vergelijkbaar met of beter zijn dan andere batch-methoden wanneer gemeten in functie-evaluaties.
  • Grote Batches ($q = 128$): SSEI presteert aanzienlijk beter dan alle vergeleken batch-algoritmen, inclus_ qEI-varianten die falen of aanzienlijk degraderen op deze schaal. De voorgestelde methode convergeert sneller en vindt betere uiteindelijke oplossingen.
• Vergelijking met Specifieke Algoritmen:
  • vs. qEI/qLogEI/FqEI: SSEI is superieur, vooral naarmate $d$ en $q$ toenemen, omdat het de $d \times q$ dimensionaliteitsvloek vermijdt.
  • vs. TuRBO: SSEI presteert competitief, presteert vaak beter dan TuRBO op laag- tot middelhoge dimensies en is vergelijkbaar op hoge dimensies.
  • vs. Strafgebaseerde methoden (PEI, EIMI, KB): SSEI presteert consequent beter dan deze methoden, die lijden onder modeldegradatie naarmate de batchgrootte groter wordt.
• Generaliseerbaarheid: De subruimte-aanpak werd succesvol toegepast op Probability of Improvement (SSPI) en Upper Confidence Bound (SSUCB), waarbij vergelijkbare prestatiewinsten werden getoond ten opzichte van hun multi-point tegenhangers (qPI, qUCB).

Betekenis en Claims

Het artikel claimt dat de voorgestelde Subspace Acquisition Functions een eenvoudige, efficiënte en schaalbare oplossing bieden voor batch Bayesiaanse optimalisatie. De primaire betekenis ligt in het mogelijk maken van het gebruik van grootschalige parallelle rekenbronnen (grote $q$) zonder de computationele knelpunten of de nauwkeurigheidsdegradatie die gepaard gaan met bestaande methoden.

De auteurs benadrukken dat:

• De methode de vloek van dimensionaliteit bij de optimalisatie van de acquisitiefunctie effectief verzacht.
• Het een praktische afweging biedt tussen globale exploratie (via willekeurige subruimte selectie) en lokale exploitatie (via het vastzetten van niet-geselecteerde variabelen).
• Het een "plug-and-play" uitbreiding is die op diverse acquisitiefuncties kan worden toegepast en bijzonder waardevol is voor dure optimalisatieproblemen waar parallelle evaluatie haalbaar is.

Het werk concludeert dat het selecteren van querypunten uit meerdere verschillende subruimten een veelbelovende strategie is voor grootschalige batch Bayesiaanse optimalisatie, die significante verbeteringen biedt in convergentiesnelheid en oplossingskwaliteit vergeleken met de huidige state-of-the-art benaderingen.