Riepilogo Tecnico: BAXUS – Ottimizzazione Bayesiana Adattiva in Sottospazi Annidati

Enunciato del Problema

L'ottimizzazione bayesiana ad alta dimensionalità (HDBO) mira a ottimizzare funzioni black-box costose da valutare con decine o centinaia di dimensioni di input. Sebbene recenti progressi abbiano esteso la portata dell'ottimizzazione bayesiana (BO) a campi come le scienze della vita, la ricerca di architetture neurali e la robotica, i metodi all'avanguardia incontrano limitazioni significative all'aumentare della dimensionalità.

Gli approcci esistenti rientrano generalmente in due categorie, entrambe con svantaggi critici:

1. Metodi a Regione di Fiducia (es. TURBO): Questi ottimizzano su regioni limitate locali (regioni di fiducia) all'interno dello spazio di input completo. Sebbene efficaci per dimensioni moderate, le loro prestazioni si degradano in dimensioni molto elevate perché le regioni di fiducia mantengono l'intera dimensionalità del problema, subendo la maledizione della dimensionalità.
2. Metodi di Incorporamento Lineare (es. REMBO, HESBO, ALEBO): Questi presuppongono l'esistenza di un "sottospazio attivo" a bassa dimensionalità e proiettano lo spazio di input ad alta dimensionalità in uno spazio target a dimensionalità inferiore. Tuttavia, questi metodi richiedono all'utente di "indovinare" la dimensionalità effettiva ($d_e$) del sottospazio attivo. Se la dimensionalità target scelta ($d$) è troppo piccola, il sottospazio non può rappresentare l'ottimo globale; se $d$ è troppo grande, l'ottimizzazione rallenta a causa della maledizione della dimensionalità. Inoltre, metodi come HESBO si basano su hashing casuale che offre garanzie peggiori nel caso peggiore per contenere un ottimo rispetto ad altri incorporamenti.

La sfida principale è sviluppare un metodo HDBO che trovi in modo affidabile ottimi globali senza richiedere conoscenze preliminari sulla dimensionalità del sottospazio attivo, evitando al contempo il degrado delle prestazioni associato agli spazi di ricerca ad alta dimensionalità.

Metodologia: BAXUS

Gli autori propongono BAXUS (Ottimizzazione bayesiana con sottospazi in espansione adattiva), un approccio fondato teoricamente che regola dinamicamente la dimensionalità dello spazio di ottimizzazione.

1. Sottospazi Annidati Adattivi

Invece di fissare la dimensionalità target, BAXUS opera su una famiglia di sottospazi casuali annidati. L'algoritmo inizia con uno spazio target a bassa dimensionalità ($d_{init}$) e aumenta progressivamente la dimensionalità man mano che raccoglie più dati.

• Inizializzazione: BAXUS inizia con una piccola dimensionalità target $d_0$.
• Espansione: Man mano che l'ottimizzazione procede, la dimensionalità target viene aumentata "dividendo" le dimensioni target esistenti. Questo processo continua fino a quando la dimensionalità target raggiunge approssimativamente la dimensionalità di input $D$ o il budget di valutazione si esaurisce.
• Conservazione delle Osservazioni: Una caratteristica critica di BAXUS è la sua capacità di conservare le osservazioni dagli spazi a bassa dimensionalità quando si espande verso dimensioni superiori. Quando una dimensione target viene divisa, le dimensioni di input contribuenti vengono riassegnate alla dimensione originale e a nuovi contenitori. I valori della funzione (osservazioni) vengono copiati nelle nuove dimensioni, garantendo che i dati raccolti nella fase a bassa dimensionalità rimangano validi nella fase a dimensionalità superiore.

2. L'Incorporamento Sparse BAXUS

BAXUS utilizza un nuovo incorporamento lineare sparso per mappare lo spazio target $Y \in \mathbb{R}^d$ nello spazio di input $X \in \mathbb{R}^D$.

• Struttura: La matrice di incorporamento $S^\top \in \{0, \pm 1\}^{d \times D}$ è sparsa, il che significa che ogni colonna (dimensione di input) ha esattamente una voce non nulla.
• Bilanciamento dei Contenitori: A differenza di HESBO, che assegna le dimensioni di input alle dimensioni target in modo uniforme e casuale (portando a dimensioni di contenitori variabili), BAXUS impone che il numero di dimensioni di input contribuenti per dimensione target (dimensione del contenitore) differisca al massimo di uno. Questa assegnazione "bilanciata" è ottenuta permutando le dimensioni di input e dividendole in $d$ contenitori.
• Vantaggio Teorico: Gli autori dimostrano che questo incorporamento sparso bilanciato fornisce una probabilità di successo nel caso peggiore strettamente superiore (la probabilità che lo spazio target contenga un ottimo globale) rispetto all'incorporamento HESBO per dimensioni di input finite. Man mano che $D \to \infty$, la probabilità di successo di BAXUS converge a quella di HESBO.

3. Strategia di Regione di Fiducia e Divisione

BAXUS integra l'espansione dell'incorporamento con un approccio a Regione di Fiducia (TR) simile a TURBO:

• Regioni di Fiducia: L'ottimizzazione avviene all'interno di regioni di fiducia iperrettangolari nello spazio target, scalate dalle scale di lunghezza del GP.
• Attivatore di Espansione: La dimensionalità target viene aumentata quando la lunghezza del lato di base della regione di fiducia scende sotto una soglia minima (indicando che la regione corrente è troppo piccola o che l'algoritmo è bloccato).
• Controllo dei Fallimenti: Il numero di "fallimenti" consentiti (iterazioni consecutive senza miglioramento) prima che avvenga una divisione viene ridotto in base alla dimensionalità target corrente. Questo garantisce che l'algoritmo possa raggiungere dimensionalità elevate entro un budget di valutazione fisso.
• Convergenza: È dimostrato che l'algoritmo raggiunge la convergenza globale. Una volta che la dimensionalità target raggiunge la dimensionalità di input $D$, BAXUS si comporta come TURBO, che è noto per convergere globalmente.

Contributi Chiave

1. Sviluppo dell'Algoritmo: Gli autori introducono BAXUS, che raggiunge in modo affidabile soluzioni eccellenti su un ampio set di task ad alta dimensionalità, superando i metodi attuali all'avanguardia.
2. Nuova Teoria di Incorporamento: Presentano una nuova famiglia di incorporamenti casuali annidati con tre proprietà chiave:
   • Fornisce una garanzia peggiore più ampia per contenere un ottimo globale rispetto all'incorporamento HESBO.
   • È un incorporamento sparso ottimale, il che significa che nessun altro incorporamento sparso ha una probabilità di successo nel caso peggiore più alta per le stesse dimensioni di input, target ed effettive.
   • La sua probabilità di contenere un ottimo converge alla probabilità di HESBO man mano che la dimensionalità di input $D \to \infty$.
3. Valutazione Completa: Il documento fornisce prove empiriche estese che dimostrano la superiorità di BAXUS rispetto a TURBO, SAASBO, ALEBO, HESBO, CMA-ES e ricerca casuale su benchmark diversificati.

Risultati Sperimentali

Gli autori hanno valutato BAXUS su una raccolta di task di ottimizzazione degli iperparametri a 388 dimensioni, problemi di progettazione a 124 dimensioni e benchmark con sottospazi attivi noti (LASSO, MOPTA08, BRANIN, HARTMANN).

• Prestazioni: BAXUS ha costantemente superato i metodi all'avanguardia. Sul benchmark SVM a 388D, BAXUS si è adattato alla dimensionalità target appropriata e ha trovato soluzioni migliori più velocemente di TURBO e CMA-ES. Sul benchmark LASSO-HARD a 1000D, BAXUS ha ottenuto soluzioni considerevolmente migliori di tutti i concorrenti, inclusi i metodi che si basano su assunzioni di sottospazio attivo (SAASBO, ALEBO, HESBO), i quali non sono riusciti a beneficiare della struttura del sottospazio attivo.
• Robustezza: BAXUS ha dimostrato robustezza al rumore osservazionale, mantenendo prestazioni forti su varianti rumorose dei benchmark dove concorrenti come SAASBO e CMA-ES si sono degradati significativamente.
• Studi di Ablazione: Sostituire l'incorporamento BAXUS con un incorporamento HESBO annidato ha portato a prestazioni significativamente peggiori, confermando che la strategia di binning bilanciato è un motore chiave del successo.
• Confronto con Incorporamenti Fissi: BAXUS ha superato l'esecuzione di TURBO con una dimensionalità target fissa, dimostrando che la strategia di espansione adattiva è superiore alle scelte statiche di $d$.

Significato e Affermazioni

Il documento afferma che BAXUS affronta le limitazioni critiche dei metodi HDBO attuali rimuovendo la necessità per i praticanti di "indovinare" la dimensionalità effettiva del problema. Espandendo adattivamente lo spazio di ricerca, BAXUS sfrutta l'efficienza dell'ottimizzazione a bassa dimensionalità garantendo al contempo che lo spazio di ricerca copra infine l'intero spazio di input, assicurando così che l'ottimo globale sia raggiungibile.

Gli autori affermano che BAXUS è un ottimizzatore "pronto all'uso" (out-of-the-box) che raggiunge prestazioni robuste su un'ampia varietà di task ad alta dimensionalità senza richiedere assunzioni specifiche sulla struttura del problema (come sottospazi attivi allineati agli assi). Il lavoro mira a rendere l'ottimizzazione bayesiana ad alta dimensionalità più accessibile e affidabile per applicazioni nella scienza e nell'industria dove il numero di parametri regolabili è elevato e la loro dimensionalità effettiva è sconosciuta.