KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Sintesi Tecnica: KSOS-BO: Miglioramento del Campionamento nell'Ottimizzazione Bayesiana tramite Somma di Nuclei al Quadrato

Enunciato del Problema
L'Ottimizzazione Bayesiana (BO) è un framework standard per l'ottimizzazione globale di funzioni black-box costose, ampiamente utilizzato nel tuning degli iperparametri, nella robotica e nella progettazione scientifica. La procedura BO coinvolge due passaggi: adattare un modello surrogato (tipicamente un Processo Gaussiano) e ottimizzare una funzione di acquisizione per selezionare il prossimo punto di interrogazione. Sebbene ricerche significative si siano concentrate sul miglioramento dei modelli surrogati e sulla progettazione della funzione di acquisizione, l'ottimizzazione della funzione di acquisizione stessa rimane un collo di bottiglia critico. Nella pratica, questo problema di ottimizzazione interna è spesso non convesso, multimodale e ad alta dimensionalità. Gli ottimizzatori privi di derivata esistenti (ad esempio, Evoluzione Differenziale, CMA-ES, Ricerca Sobol) spesso trattano questo come un problema black-box generico, fallendo nello sfruttare esplicitamente la natura strutturata dei paesaggi di acquisizione. Di conseguenza, questi metodi possono rimanere intrappolati in ottimi locali o richiedere valutazioni eccessive per trovare candidati di alta qualità, limitando l'efficienza complessiva del processo BO.

Metodologia: KSOS-BO
Gli autori propongono KSOS-BO, un framework basato su nuclei e privo di derivata progettato specificamente per ottimizzare le funzioni di acquisizione. Il metodo adatta l'approccio Kernel Sum-of-Squares (KernelSOS) al contesto BO.

1. Formulazione: L'idea centrale è riformulare la minimizzazione della funzione di acquisizione $\alpha(x)$ come un problema di ottimizzazione globale che cerca il più grande limite inferiore $c$ tale che $\alpha(x) - c \geq 0$ per ogni $x$ nel dominio.
2. Rilassamento tramite Nuclei: A differenza dei metodi classici Sum-of-Squares (SOS) limitati a obiettivi polinomiali, KSOS-BO utilizza Spazi di Hilbert a Nucleo Riproducente (RKHS). Sostituisce le basi polinomiali a dimensione finita con funzioni di nucleo. Il vincolo di non negatività è rilassato in un programma semidefinito (SDP) che coinvolge una matrice di nucleo $K$ derivata da un insieme finito di punti campionati.
3. Ottimizzazione e Recupero: L'algoritmo risolve un SDP per trovare una rappresentazione surrogata basata su nuclei della funzione di acquisizione spostata. Invece di ottimizzare direttamente nello spazio degli input, recupera un punto candidato continuo $x^*$ come combinazione ponderata dei punti campionati. Questo permette al metodo di eseguire una ricerca globale strutturata utilizzando solo valutazioni della funzione.
4. Integrazione: In ogni iterazione BO, KSOS-BO campiona punti per valutare la funzione di acquisizione corrente, costruisce il surrogato KernelSOS, risolve l'SDP per trovare il prossimo candidato e aggiorna il modello BO.

Contributi Chiave

• Ricerca Globale Strutturata: Il documento introduce una nuova applicazione di KernelSOS all'ottimizzazione dell'acquisizione, andando oltre la ricerca black-box generica per sfruttare la natura liscia e strutturata dei paesaggi di acquisizione indotta dai surrogati del Processo Gaussiano.
• Framework Privo di Derivate: Il metodo opera senza richiedere gradienti, rendendolo compatibile con impostazioni standard prive di derivate, pur fornendo un'alternativa principiale alle ricerche euristica basate su popolazione.
• Guadagni di Prestazione: Gli autori dimostrano che, nonostante un costo computazionale per iterazione più elevato dovuto al passaggio SDP, KSOS-BO raggiunge una convergenza più rapida in termini di tempo reale, ottenendo soluzioni di alta qualità con meno valutazioni di acquisizione.

Risultati Sperimentali
Gli autori hanno valutato KSOS-BO contro tre baseline prive di derivate (Ricerca Sobol, Evoluzione Differenziale e CMA-ES) su 15 funzioni di riferimento con proprietà di paesaggio variabili (multimodali, a forma di ciotola, a forma di valle, a forma di altopiano e con ripide discese) in 10 dimensioni.

• Miglioramento del Rimpianto: KSOS-BO ha ottenuto le prestazioni migliori su 10 su 15 benchmark. Su queste funzioni ad alte prestazioni, ha mostrato un miglioramento medio del rimpianto dell'81,16% rispetto al secondo miglior ottimizzatore.
• Efficienza Temporale: Sebbene KSOS-BO comporti un sovraccarico computazionale più elevato per iterazione, ha convergito più rapidamente nel tempo reale. Sui 10 benchmark in cui si è classificato primo, ha ottenuto un miglioramento medio del tempo reale del 93,55%, riducendo efficacemente della metà il tempo necessario per raggiungere la stessa accuratezza delle baseline.
• Sensibilità al Paesaggio: Il metodo ha eccelluto su funzioni altamente multimodali (ad esempio, Ackley, Rastrigin, Griewank) e funzioni unimodali lisce (ad esempio, Rosenbrock, Dixon Price). Tuttavia, le prestazioni sono peggiorate su funzioni con curvatura estrema, ripide discese o regioni a forma di altopiano (ad esempio, Michalewicz, Zakharov, Styblinski Tang), dove la rappresentazione basata su nuclei è risultata meno adeguata.
• Robustezza: Studi di ablazione hanno indicato che KSOS-BO è robusto alle variazioni nella dimensione del disegno iniziale, nei budget di valutazione e nelle scelte di nucleo (Gaussiano vs Laplace), sebbene abbia costantemente superato le baseline nella maggior parte dei casi di test.

Significato e Affermazioni
Il documento afferma che migliorare esclusivamente il passaggio di ottimizzazione dell'acquisizione produce miglioramenti misurabili nelle prestazioni complessive dell'Ottimizzazione Bayesiana. Il significato principale risiede nel dimostrare che trattare l'ottimizzazione dell'acquisizione come un problema strutturato risolvibile tramite rilassamenti KernelSOS è superiore al trattarlo come un problema black-box generico.

Gli autori notano con modestia che, sebbene KSOS-BO sia efficace per diverse strutture di paesaggio, non è una soluzione universale; incontra difficoltà con specifiche caratteristiche geometriche come ripide discese o altopiani piatti. Inoltre, il metodo introduce un compromesso computazionale: il passaggio SDP è più costoso delle strategie evolutive standard, ma questo costo è giustificato dalla riduzione del numero di valutazioni di funzioni costose necessarie per trovare soluzioni ottimali. Il lavoro suggerisce che le direzioni future dovrebbero concentrarsi sul miglioramento della scalabilità di KSOS-BO, sull'esplorazione di strategie ibride con raffinamento locale e sui test in contesti a dimensionalità più elevata o vincolati.