Scalable Batch Bayesian Optimization Via Subspace Acquisition Functions

Sintesi Tecnica: Ottimizzazione Bayesiana Batch Scalabile tramite Funzioni di Acquisizione in Sottospazi

Definizione del Problema

L'Ottimizzazione Bayesiana (BO) è un framework potente per risolvere problemi di ottimizzazione black-box costosi. Mentre la BO standard opera in modo sequenziale, selezionando un punto di campionamento alla volta, questo approccio è inefficiente quando sono disponibili risorse di calcolo parallelo. Per sfruttare il parallelismo, sono necessari algoritmi di Ottimizzazione Bayesiana Batch per valutare più campioni simultaneamente.

Tuttavia, gli approoli batch esistenti affrontano significativi problemi di scalabilità all'aumentare della dimensione del batch ($q$):

• Expected Improvement Multi-punto (qEI): Sebbene teoricamente solido, l'ottimizzazione di qEI comporta uno spazio di ricerca di dimensione $d \times q$ (dove $d$ è la dimensione del problema). Man mano che $q$ cresce, il costo computazionale della valutazione della funzione di distribuzione cumulativa multivariata e la difficoltà di ottimizzare la funzione di acquisizione aumentano esponenzialmente, rendendo qEI e le sue varianti (es. FqEI, qLogEI) impraticabili per grandi dimensioni di batch (tipicamente $q > 10$).
• Approcci Euristici (es. Kriging Believer, Constant Liar, Local Penalization): Questi metodi spesso si affidano a "punti finti" o funzioni di penalità artificiali per simulare gli effetti del batch. All'aumentare della dimensione del batch, l'accumulo di questi punti artificiali degrada l'accuratezza del modello a Processo Gaussiano (GP), potenzialmente confondendo la direzione di ricerca e riducendo l'efficienza dell'ottimizzazione.
• Approcci Multi-obiettivo e Multi-modello: I metodi che addestrano molteplici modelli surrogati o risolvono problemi di ottimizzazione multi-obiettivo spesso comportano elevati costi computazionali che non scalano bene con grandi dimensioni di batch.

La sfida centrale affrontata in questo lavoro è la progettazione di una strategia di acquisizione batch che rimanga computazionalmente trattabile ed efficace per valutazioni batch su larga scala senza soffrire della maledizione della dimensionalità o del degrado del modello.

Metodologia

Gli autori propongono un approccio innovativo chiamato Funzioni di Acquisizione in Sottospazio, che estende le funzioni di acquisizione esistenti (specificamente l'Expected Improvement, ma anche adattabile a PI e UCB) per operare all'interno di sottospazi scelti casualmente e allineati agli assi.

Concetto Core: Subspace Expected Improvement (SSEI)

Invece di cercare $q$ punti in un intero spazio di progettazione $d$-dimensionale simultaneamente, il metodo:

1. Seleziona i Sottospazi: Seleziona casualmente un insieme di sottospazi allineati agli assi. Un sottospazio $k$-dimensionale allineato agli assi è definito scegliendo $k$ coordinate dalle $d$ dimensioni originali, fissando le restanti $d-k$ coordinate ai valori della soluzione migliore attuale ($x_{min}$).
2. Ottimizza Localmente: Per ogni sottospazio selezionato, la funzione di acquisizione standard (es. EI) viene ottimizzata solo sulle $k$ variabili attive. Le variabili non selezionate rimangono fisse a $x_{min}$.
3. Genera il Batch: Un punto di query viene selezionato da ciascun sottospazio unico. Se la dimensione del batch richiesta $q$ supera il numero di sottospazi disponibili ($N = 2^d - 1$), il metodo impiega la Subspace Multi-Point Expected Improvement (SSqEI), che ottimizza più punti all'interno di un singolo sottospazio.

Framework Computazionale

L'algoritmo proposto (Algoritmo 1) opera come segue:

• Inizializzazione: Genera campioni iniziali e addestra un modello GP.
• Selezione del Sottospazio: Estrae casualmente un intero $k \in [1, d]$ e poi una combinazione casuale di $k$ coordinate per formare un sottospazio. Questo evita il costo computazionale di enumerare tutti i possibili sottospazi.
• Ottimizzazione dell'Acquisizione:
  • Se $q \le N$: Seleziona $q$ sottospazi distinti e ottimizza la SSEI standard in ciascuno per trovare un punto per sottospazio.
  • Se $q > N$: Distribuisce i $q$ punti tra i $N$ sottospazi disponibili (ottimizzando più punti per sottospazio usando SSqEI).
• Valutazione: Valuta il batch risultante di $q$ punti in parallelo.
• Aggiornamento: Aggiorna il modello GP con le nuove osservazioni e ripete.

La dimensionalità del problema di ottimizzazione per la funzione di acquisizione è ridotta da $d \times q$ a circa $k \times 1$ (o $k \times q_i$ per SSqEI), dove la dimensione attesa $E[k] \approx d/2$. Ciò riduce significativamente la complessità dell'ottimizzazione dell'acquisizione.

Contributi Chiave

1. Strategia Batch Scalabile: Il paper introduce un metodo per estendere l'ottimizzazione bayesiana a grandi dimensioni di batch scomponendo la selezione del batch in ottimizzazioni di sottospazio indipendenti o a bassa dimensionalità, evitando la complessità esponenziale di qEI.
2. Semplicità e Generalità: L'approccio non richiede iperparametri aggiuntivi ed è applicabile a una vasta gamma di funzioni di acquisizione (dimostrato su EI, PI e UCB). È concettualmente semplice: "disegna sottospazi, ottimizza localmente, aggrega".
3. Robustezza alla Dimensionalità: Limitando la ricerca ai sottospazi allineati agli assi ancorati alla soluzione migliore attuale, il metodo bilancia naturalmente l'esplorazione (tramite la selezione casuale dei sottospazi) e lo sfruttamento (tramite la ricerca locale attorno a $x_{min}$), rendendolo particolarmente efficace in spazi ad alta dimensionalità.

Risultati Sperimentali

Gli autori hanno valutato il metodo proposto (SSEI) contro dieci algoritmi batch allo stato dell'arte (inclusi qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB e Random Search) su 60 problemi benchmark sintetici (GPMean, SumSquares, Rosenbrock, ecc.) attraverso dimensioni $d \in \{2, 4, 8, 10, 20, 30\}$ e dimensioni di batch $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Performance vs. BO Sequenziale: Quando $q=1$, SSEI performa in modo simile alla EI standard su problemi a bassa dimensione, ma supera significativamente quest'ultima su problemi ad alta dimensione ($d \ge 8$). Gli autori attribuiscono ciò al fatto che la EI sequenziale fatica a ottimizzare la funzione di acquisizione in alta dimensione, mentre la ricerca locale nei sottospazi di SSEI trova migliori ottimi locali per la funzione di acquisizione.
• Scalabilità con la Dimensione del Batch:
  • Batch Piccoli o Medi ($q \le 32$): SSEI raggiunge un'accelerazione quasi lineare in termini di tempo di esecuzione (iterazioni) pur mantenendo prestazioni comparabili o superiori ad altri metodi batch quando misurate in termini di valutazioni della funzione.
  • Batch Grandi ($q = 128$): SSEI supera significativamente tutti gli algoritmi batch confrontati, inclusi i varianti di qEI che falliscono o degradano sensibilmente a questa scala. Il metodo proposto converge più velocemente e trova soluzioni finali migliori.
• Confronto con Algoritmi Specifici:
  • vs. qEI/qLogEI/FqEI: SSEI è superiore, specialmente all'aumentare di $d$ e $q$, perché evita la maledizione della dimensionalità di $d \times q$.
  • vs. TuRBO: SSEI è competitivo, spesso superando TuRBO su dimensioni medio-basse e pareggiando in dimensioni elevate.
  • vs. Metodi basati su Penalità (PEI, EIMI, KB): SSEI supera costantemente questi metodi, che soffrono di degrado del modello all'aumentare della dimensione del batch.
• Generalizzabilità: L'approccio in sottospazio è stato applicato con successo alla Probability of Improvement (SSPI) e all'Upper Confidence Bound (SSUCB), mostrando guadagni di performance simili rispetto ai loro corrispettivi multi-punto (qPI, qUCB).

Significato e Rivendicazioni

Il paper sostiene che le proposte Funzioni di Acquisizione in Sottospazio forniscono una soluzione semplice, efficiente e scalabile per l'ottimizzazione bayesiana batch. Il significato primario risiede nel rendere possibile l'uso di risorse di calcolo parallelo su larga scala (grandi $q$) senza i colli di bottiglia computazionali o il degrado dell'accuratezza associati ai metodi esistenti.

Gli autori sottolineano che:

• Il metodo mitiga efficacementamente la maledizione della dimensionalità nell'ottimizzazione della funzione di acquisizione.
• Offre un compromesso pratico tra esplorazione globale (tramite la selezione casuale dei sottospazi) e sfruttamento locale (tramite il fissaggio delle variabili non selezionate).
• È un'estensione "plug-and-play" che può essere applicata a varie funzioni di acquisizione ed è particolarmente preziosa per problemi di ottimizzazione costosi dove la valutazione parallela è fattibile.

Il lavoro conclude che la selezione dei punti di query da molteplici sottospazi differenti è una strategia promettente per l'ottimizzazione bayesiana batch su larga scala, offrendo miglioramenti significativi nella velocità di convergenza e nella qualità della soluzione rispetto agli approcci attuali allo stato dell'arte.