Riepilogo Tecnico: Ottimizzazione Black-Box Mixed-Categorical tramite Decomposizione Bilevel Information-Geometric

Definizione del Problema

Il documento affronta l'Ottimizzazione Black-Box Mixed-Categorical (MC-BBO), una classe di problemi in cui la funzione obiettivo $f(c, x)$ deve essere minimizzata su un dominio eterogeneo composto da variabili categoriche $c$ e variabili continue $x$. Nello specifico, lo studio si concentra sul caso in cui $c$ consiste in variabili categoriche discrete (modellate come vettori one-hot o bit binari) e $x \in \mathbb{R}^{d_x}$.

La sfida principale identificata è la presenza di forti interazioni tra variabili categoriche e continue. Gli approcci esistenti di stato dell'arte basati su Strategie Evolutive (ES), come CatCMA e ICatCMA, modellano la distribuzione di ricerca come il prodotto di una Gaussiana multivariata (per $x$) e di una distribuzione categorica (per $c$). Questa assunzione di distribuzione di prodotto impone implicitamente l'indipendenza tra $c$ e $x$, impedendo a questi metodi di apprendere dipendenze complesse in cui la configurazione continua ottimale dipende fortemente dalla scelta categorica effettuata. Sebbene esistano metodi bayesiani, essi soffrono spesso di problemi di scalabilità in spazi ad alta dimensionalità.

Metodologia: IGBD

Gli autori propongono l'Information-Geometric Bilevel Decomposition (IGBD), un framework che modella esplicitamente la dipendenza tra variabili categoriche e continue riformulando il problema come un compito di ottimizzazione bilevel:

$$\min_{c} f(c, x^\star) \quad \text{soggetto a} \quad x^\star = \arg\min_{x} f(c, x)$$

Il metodo impiega l'Information-Geometric Optimization (IGO) per formulare rilassamenti stocastici per entrambi i livelli della gerarchia:

1. Livello Superiore (Ottimizzazione Categorica):

   • Ottimizza il vettore di probabilità $q$ che governa la distribuzione categorica.
   • Utilizza il metodo Adaptive Stochastic Natural Gradient (ASNG).
   • Aggiorna $q$ lungo il gradiente naturale utilizzando una modellazione della fitness basata sul ranking (rank-based fitness shaping) per garantire l'invarianza rispetto alle trasformazioni monotone.
   • Adatta la dimensione del passo (raggio di fiducia) utilizzando un meccanismo di adattamento cumulativo della dimensione del passo (CSA) analogo a CMA-ES.

2. Livello Inferiore (Ottimizzazione Continua):

   • Ottimizza le variabili continue $x$ condizionate a una configurazione categorica fissa $c$.
   • Utilizza dd-CMA-ES (una variante diagonale con aggiornamento attivo) per minimizzare l'obiettivo $f(c, x)$.
   • Il solver del livello inferiore è trattato come un processo stateful che fornisce una stima della $x^\star(c)$ ottimale al livello superiore.

3. Strategia di Warm-Starting (Meccanismo di Cache):

   • Per mitigare il costo computazionale proibitivo del risolvere il problema del livello inferiore fino alla convergenza per ogni candidato del livello superiore, IGBD introduce una strategia di warm-starting.
   • Viene mantenuta una cache di $N_\omega$ configurazioni del livello inferiore $\{(x_k, \omega_k, p_k)\}$, dove $\omega_k$ rappresenta i parametri di CMA-ES e $p_k$ è un punteggio di qualità.
   • Selezione: Per ogni candidato del livello superiore $c_i$, l'algoritmo seleziona la migliore configurazione in cache $k^\star_i$ basata sull'attuale valore dell'obiettivo.
   • Inizializzazione: Il solver del livello inferiore per $c_i$ viene inizializzato con i parametri provenienti dalla configurazione selezionata dalla cache.
   • Aggiornamento: Dopo la ricerca del livello inferiore, la cache viene aggiornata. Le voci selezionate vengono rinfrescate con il nuovo stato del solver e i loro punteggi vengono incrementati; le voci non selezionate vedono il proprio punteggio decrementato. Le voci che scendono sotto una certa soglia vengono ri-inizializzate casualmente per promuovere l'esplorazione.

Contributi Chiave

1. Framework IGBD: La proposta di un framework di ottimizzazione bilevel per MC-BBO in cui ogni livello è un rilassamento stocastico sotto IGO. Questo cattura esplicitamente le interazioni tra categoriche e continue che i metodi a distribuzione di prodotto trascurano.
2. Nuovo Tipo di Interazione: L'introduzione di un quarto tipo di interazione (Tipo-IV) in cui le variabili categoriche governano le interazioni all'interno del dominio continuo stesso (ad esempio, cambiando la struttura di covarianza o la rotazione del paesaggio continuo), oltre a determinare la posizione ottimale.
3. Benchmarking: Valutazione completa rispetto a CatCMA e ICatCMA su domini binari-continui, inclusi i tipi di interazione esistenti (I, II, III) e il nuovo tipo proposto (IV), attraverso diverse dimensionalità ($d_c=d_x=5$ e $10$) e intensità di interazione.

Risultati Sperimentali

Gli esperimenti dimostrano che IGBD supera i metodi esistenti nel gestire le forti interazioni pur mantenendo l'efficienza computazionale:

• Gestione delle Interazioni: IGBD raggiunge un tasso di successo del 100% in quasi tutti i tipi e le intensità di interazione testati, inclusi i problematici tipi di interazione IV, dove CatCMA e ICatCMA falliscono significativamente.
  • CatCMA: Funziona bene solo quando le interazioni sono deboli o assenti (l'assunzione di indipendenza è rispettata). Fallisce sulle interazioni di Tipo-III e Tipo-IV all'aumentare della forza di interazione.
  • ICatCMA: Migliora rispetto a CatCMA nelle interazioni di Tipo-II (mappatura affine) grazie alla sua iper-rappresentazione, ma fallisce nelle interazioni di Tipo-III (mascheramento non lineare) e Tipo-IV. Le sue prestazioni degradano bruscamente all'aumentare della complessità dell'interazione.
• Efficienza Computazionale:
  • IGBD è generalmente più efficiente di ICatCMA, che incorre in costi elevati a causa dei parametri della sua iper-rappresentazione affine.
  • Sebbene CatCMA sia più veloce su problemi semplici (interazioni deboli), IGBD diventa più robusto ed efficiente all'aumentare della forza di interazione ($a$), evitando i massicci cicli di restart e i tassi di fallimento osservati nei baseline.
• Scalabilità: Il metodo proposto mantiene alti tassi di successo ad altissime dimensioni ($d=10$), mentre i baseline faticano significativamente, particolarmente con le interazioni di Tipo-IV.

Significato e Rivendicazioni

L'articolo sostiene che IGBD rappresenti un passo avanti significativo nell'ottimizzazione black-box a variabili miste affrontando il limite fondamentale delle assunzioni di indipendenza nelle attuali Strategie Evolutive. Sfruttando una struttura bilevel con principi di geometria dell'informazione e una cache di warm-starting, il metodo modella efficacemente le dipendenze complesse tra variabili discrete e continue.

Gli autori osservano che, sebbene l'implementazione attuale sia limitata al dominio binario-continuo, l'approccio si estende naturalmente all'ottimizzazione mixed-categorical generale. Riconoscono che l'alto costo computazionale del metodo in regimi di interazione estremi è dovuto principalmente al budget di valutazione della funzione piuttosto che a un difetto algoritmico fondamentale. Si suggerisce come lavoro futuro l'estensione a categorie non-binarie, la gestione di sottospazi a bassa dimensione effettiva e l'integrazione di euristiche a minor costo per alleviare ulteriormente l'onere dell'ottimizzazione bilevel.