Bayesian Optimistic Optimisation with Exponentially Decaying Regret

1. Enunciato del Problema

Il documento affronta il problema dell'ottimizzazione globale per funzioni costose, prive di rumore e a scatola nera $f(x)$ dove $x \in \mathcal{X} \subset \mathbb{R}^D$. L'obiettivo è trovare il massimo globale $x^*$ con un budget limitato di valutazioni della funzione $N$.

La prestazione è misurata dal rimpianto semplice (simple regret):
$$r_N = \sup_{x \in \mathcal{X}} f(x) - \max_{1 \le i \le N} f(x_i)$$

Limitazioni Esistenti:

• Ottimizzazione Bayesiana (BO): Gli algoritmi BO standard (es. GP-UCB, GP-EI) raggiungono tipicamente limiti di rimpianto sub-lineari (es. $O(\sqrt{\frac{\log N}{N}})$ o $O(1/\sqrt{N})$). Un collo di bottiglia maggiore è che la BO richiede la risoluzione di un problema di ottimizzazione non convesso ausiliario (massimizzazione della funzione di acquisizione) ad ogni iterazione, il che è computazionalmente costoso e difficile in dimensioni elevate.
• Ottimizzazione Ottimista (basata su alberi): Algoritmi come SOO e BaMSOO partizionano gerarchicamente lo spazio di ricerca. Sebbene evitino l'ottimizzazione ausiliaria, soffrono di una correlazione negativa rigorosa tra il fattore di diramazione $m$ (granularità del partizionamento) e il numero di espansioni dell'albero. Per ottenere partizioni fini (grande $m$), devono valutare molti nodi figli, consumando rapidamente il budget di valutazione $N$. Di conseguenza, i loro limiti di rimpianto nel caso peggiore sono spesso limitati a $O(e^{-\sqrt{N}})$ o a tassi sub-lineari.

Gli autori chiedono: Possiamo progettare un algoritmo pratico che combini l'efficienza del modello della BO con i benefici strutturali dell'ottimizzazione ottimista basata su alberi per ottenere un limite di rimpianto più stretto (specificamente $O(N^{-\sqrt{N}})$) senza il costo computazionale dell'ottimizzazione ausiliaria?

2. Metodologia: L'Algoritmo BOO

Gli autori propongono l'Ottimizzazione Ottimista Bayesiana (BOO), un nuovo algoritmo che integra i Processi Gaussiani (GP) con una ricerca gerarchica su albero modificata.

Innovazioni Chiave

1. Disaccoppiamento del Fattore di Diramazione dalle Valutazioni:

   • Approccio Tradizionale: In SOO/BaMSOO, espandere un nodo richiede di valutare $m$ figli. Pertanto, il numero di espansioni è limitato a $N/m$.
   • Approccio BOO: L'algoritmo seleziona un nodo da espandere basandosi sul GP-Upper Confidence Bound (GP-UCB). Crucialmente, valuta la funzione obiettivo solo sul nodo genitore selezionato, non sui suoi $m$ figli. I figli vengono aggiunti all'albero strutturalmente ma rimangono non valutati fino a quando non vengono selezionati successivamente.
   • Risultato: Questo "svincola" il fattore di diramazione $m$ dal budget di valutazione. L'algoritmo può utilizzare un $m$ molto grande per creare partizioni estremamente fini senza pagare il costo di $m$ valutazioni per passo.

2. Procedura di Partizionamento Innovativa $P(m; a, b)$:

   • Invece di dividere solo il lato più lungo di una cella (standard in SOO), BOO scompone il fattore di diramazione $m = a^b$.
   • Divide la cella lungo le sue $b$ dimensioni più lunghe in $a$ parti uguali ciascuna.
   • Impostando $b = D$ (la dimensionalità), l'algoritmo partiziona tutte le dimensioni simultaneamente. Ciò consente di affinare lo spazio di ricerca molto più velocemente in tutte le direzioni rispetto alla divisione sequenziale delle dimensioni.

3. Strategia di Campionamento:

   • L'algoritmo mantiene un modello GP.
   • Ad ogni passo, seleziona il nodo foglia con il valore GP-UCB più alto.
   • Valuta $f$ solo al centro di questo nodo selezionato.
   • Aggiorna il GP e la struttura dell'albero, aggiungendo $m$ figli al nodo selezionato.

Flusso dell'Algoritmo (Semplificato)

1. Inizializzare un albero con un nodo radice.
2. Selezionare il nodo foglia $(h, i)$ con il valore GP-UCB massimo $U_p(c_{h,i})$.
3. Se $U_p(c_{h,i}) \ge v_{max}$ (valore osservato migliore corrente):
   • Valutare $f$ al centro del nodo.
   • Aggiornare il dataset e rifittare il GP.
   • Espandere il nodo aggiungendo $m$ figli utilizzando la regola di partizionamento $P(m; a, b)$.
4. Ripetere fino a esaurimento del budget $N$.

3. Contributi Teorici e Analisi del Rimpianto

Il documento fornisce un'analisi teorica rigorosa sotto l'assunzione che $f$ sia campionata da un Processo Gaussiano con un kernel Matérn con parametro di regolarità $\nu > 4 + \frac{D}{2}$.

• Limite di Rimpianto: Gli autori dimostrano che BOO raggiunge un limite di rimpianto semplice di:
  $$r_N = O(N^{-\sqrt{N}})$$
  Questo è un rimpianto a decadimento esponenziale che è rigorosamente più stretto del limite $O(e^{-\sqrt{N}})$ dei precedenti algoritmi ottimisti all'avanguardia (come IMGPO) e significativamente migliore dei limiti standard della BO.

• Meccanismo Teorico Chiave:

  • La dimostrazione si basa sulla limitazione della dimensione dell'"insieme di espansione" (nodi che potrebbero potenzialmente contenere l'ottimo).
  • Utilizzando il partizionamento innovativo ($b=D$) e il grande fattore di diramazione $m$, si dimostra che la "dimensione di quasi-ottimalità" è efficacemente 0.
  • Il disaccoppiamento di $m$ dalle valutazioni permette all'algoritmo di esplorare lo spazio con alta granularità ($m$ grande) mantenendo un basso costo di valutazione, portando al tasso di converzione migliorato.

4. Risultati Sperimentali

Gli autori hanno validato BOO su benchmark sintetici e compiti reali di ottimizzazione degli iperparametri nel machine learning.

• Baseline: Confronto contro GP-EI, GP-UCB, SOO, BaMSOO e IMGPO.
• Funzioni Sintetiche: Testate su funzioni Hartmann3, Schwefel e Shekel.
  • Risultato: BOO ha superato costantemente tutte le baseline in termini di velocità di convergenza (distanza logaritmica dall'ottimo). Ha ottenuto le migliori prestazioni su Hartmann e Schwefel, e prestazioni competitive su Shekel.
• Ottimizzazione degli Iperparametri:
  • Compiti: Ottimizzazione di ElasticNet, MLP e XGBoost sui dataset MNIST e Skin Segmentation.
  • Risultato: BOO ha ottenuto errori di predizione inferiori rispetto a tutte le baseline. Per XGBoost, ha superato le altre con un ampio margine.
• Efficienza Computazionale:
  • BOO è significativamente più veloce di GP-EI e GP-UCB perché evita la massimizzazione costosa delle funzioni di acquisizione su spazi continui.
  • È leggermente più lento di IMGPO a causa dell'overhead di gestione di un albero più grande (grande $m$), ma il compromesso produce prestazioni di ottimizzazione superiori.

5. Significato e Conclusione

• Superamento della Barriera del Rimpianto: Questo è il primo algoritmo pratico a raggiungere un limite di rimpianto di $O(N^{-\sqrt{N}})$ per l'ottimizzazione bayesiana, superando i limiti teorici dei precedenti metodi ottimisti e bayesiani.
• Praticità: A differenza di approcci teorici precedenti che richiedevano campionamenti impraticabili (come il campionamento $\delta$-cover), BOO è implementabile ed efficiente.
• Sinergia: Il lavoro colma con successo il divario tra Ottimizzazione Basata su Modelli (BO) e Ottimizzazione Ottimista Senza Modelli, dimostrando che l'integrazione di un modello GP in una struttura basata su alberi con una specifica strategia di campionamento può produrre miglioramenti esponenziali nella convergenza.
• Lavori Futuri: Gli autori notano i piani per estendere il metodo a contesti rumorosi e spazi a dimensionalità più elevate.

In sintesi, il documento presenta un avanzamento significativo nella teoria e nella pratica dell'ottimizzazione globale introducendo un meccanismo per disaccoppiare la granularità della ricerca dal costo di valutazione, risultando in un limite di rimpianto all'avanguardia e prestazioni empiriche superiori.