A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

Sintesi Tecnica: Un Metodo Monte-Carlo ispirato al Compressive Sensing per l'Ottimizzazione Combinatoria

Definizione del Problema
Il documento affronta la sfida di risolvere problemi di ottimizzazione combinatoria, specificamente quelli definiti su uno spazio binario discreto $\{0,1\}^N$. Gli autori si concentrano su scenari in cui la funzione obiettivo (costo o ricompensa) è complessa, potenzialmente non convessa, non differenziabile o una "Black-Box" priva di una forma analitica esplicita. Questi problemi, che includono gli Hamiltoniani di Ising generalizzati, il problema dello zaino (knapsack problem) e il problema del commesso viaggiatore, soffrono tipicamente di una complessità temporale esponenziale quando affrontati tramite ricerca brute-force o ricerca ingenua. Sebbene le meta-euristiche come il simulated annealing e gli algoritmi genetici siano lo standard, gli autori sostengono che i metodi efficienti per funzioni binarie generali rimangano limitati.

Metodologia: Monte-Carlo Compressive Optimization (MCCO)
La soluzione proposta è l'algoritmo Monte-Carlo Compressive Optimization (MCCO). Esso integra i principi del compressive sensing, dell'apprendimento compressivo statistico e dei metodi Monte-Carlo per trovare l'ottimo globale di una funzione basandosi su un campione dei suoi valori, anche se l'ottimo stesso non viene mai direttamente osservato durante il campionamento.

L'algoritmo procede attraverso i seguenti passaggi:

1. Campionamento Casuale (Random Sampling): Viene generato un campione $S_f$ della funzione obiettivo $f$ estraendo $n$ indici da una distribuzione uniforme ed valutando $f$ in questi punti.
2. Sogliatura (Thresholding): Viene applicato un operatore di sogliatura rigida $T_t$ al campione, azzerando i valori al di sotto di una specifica soglia $t$. Questo passaggio è crucialo per le prestazioni, poiché introduce una non-linearità che supera le semplici mappe lineari casuali.
3. Sketching (Misurazione): Viene applicata una mappa di sketching $\Phi$ al campione sogliato per produrre un vettore di sketch $y$. Questo vettore contiene stime empiriche dei momenti generalizzati della distribuzione. Il documento utilizza tre tipi di funzioni di sketch:
   • Interazioni di Quadrupletti/Quintupletti: Mappe deterministiche strutturate basate su interazioni locali di stringhe di bit (ad esempio, 4 o 5 bit consecutivi).
   • Random Sketch: Una matrice con coefficienti estratti da una distribuzione Gaussiana.
4. Decodifica (Recovery): Una procedura di decodifica greedy $\Delta$ (specificamente l'Orthogonal Matching Pursuit negli esperimenti numerici) viene applicata a $y$ per ricostruire una stima $\tilde{f}$. Gli autori scelgono esplicitamente metodi greedy rispetto alla minimizzazione $\ell_1$ (Basis Pursuit) per evitare l'overfitting rispetto al campione specifico e per catturare invece le caratteristiche globali della distribuzione.
5. Ottimizzazione: Il valore massimo della funzione ricostruita $\tilde{f}$ viene preso come stima dell'ottimo globale.

Il metodo è progettato per problemi "compressibili", definiti come quelli in cui la funzione di costo può essere determinata o ben approssimata da un breve insieme di regole (una rappresentazione sparsa in una base nota), anche se tale rappresentazione non è esplicitamente nota all'utente.

Contributi Chiave

• Novità Algoritmica: L'introduzione di MCCO, che riutilizza le tecniche di recupero del compressive sensing per l'ottimizzazione combinatoria, sfruttando specificamente algoritmi greedy per prevenire l'overfitting in un contesto Monte-Carlo.
• Giustificazione Teorica: Il documento fornisce un'analisi teorica (Teorema 1) dimostrando che la probabilità che il vero massimo sopravviva al processo di campionamento e sketching dipende dalla media e dalla varianza del gap tra il valore più grande e il secondo valore più grande della funzione obiettivo. Dimostra che, con un campionamento sufficiente, il massimo può essere preservato con alta probabilità.
• Implementazione Pratica: Lo sviluppo di TrOMA (Tractable Optimization Modeling Approach), una libreria Python open-source che implementa MCCO. Questa libreria è hardware-agnostic (supporta backend classici e quantistici, inclusi i computer quantistici IBM) e permette agli utenti di ottimizzare qualsiasi problema semplicemente fornendo una funzione di costo.
• Ambito Definito: Gli autori definiscono una classe di problemi "compressibili" e sostengono che MCCO sia particolarmente efficace per questa classe, che include molti problemi NP-completi.

Risultati Numerici
Gli autori hanno condotto simulazioni numeriche su un problema di dimensione $N=12$ (uno spazio di $2^{12}$), estratto casualmente dalla classe dei problemi compressibili. Hanno confrontato MCCO con Dual Annealing (una combinazione di simulated annealing e fast annealing).

• Prestazioni: MCCO utilizzando funzioni di sketch strutturate (Quadruplets e Quintuplets) ha superato il Dual Annealing.
  • Success Rate: MCCO con sketch di tipo Quadruplet ha recuperato il massimo globale in circa il 58% dei casi, e Quintuplets in circa il 49%, rispetto al 46% del Dual Annealing.
  • Prossimità: Quando il massimo globale non veniva trovato, le stime di MCCO erano significativamente più vicine all'ottimo. Per i Quadruplet, il 91% delle stime era entro una distanza di Hamming di 1 dall'ottimo reale, rispetto all'81% del Dual Annealing.
  • Efficienza di Campionamento: MCCO ha mostrato prestazioni competitive o superiori anche con piccoli campioni (da 50 a 400 campioni).
• Random Sketches: MCCO utilizzando un random Gaussian sketch ha performato peggio degli sketch strutturati ed è stato comparabile al Dual Annealing in termini di recupero dell'ottimo globale (6%), sebbene abbia comunque superato un puro tentativo casuale in termini di distanza di Hamming.

Significato e Rivendicazioni
Il documento sostiene che MCCO offra un'alternativa competitiva alle meta-euristiche consolidate come il Dual Annealing per una vasta classe di problemi combinatori, in particolare per quelli che sono "compressibili". La significatività risiede nella capacità del metodo di:

1. Gestire funzioni obiettivo Black-Box e complesse senza richiedere informazioni sul gradiente.
2. Sfruttare la sparsità della struttura sottostante del problema (anche se ignota) per trovare soluzioni ottimali con meno valutazioni della funzione.
3. Essere calibrato sulle risorse computazionali disponibili, regolando i parametri euristici e le funzioni di sketch.
4. Fornire un ponte tra l'ottimizzazione classica e il calcolo quantistico, poiché la decodifica di matrici strutturate può essere facilitata da algoritmi quantistici.

Gli autori rimangono modesti riguardo ai confini esatti di applicabilità del metodo, osservando che, sebbene la classe di problemi compressibili sia ampia, i limiti precisi in cui MCCO supera tutti gli altri metodi rimangono un'area aperta per ulteriori indagini. Invitano la comunità a testare il metodo tramite la libreria TrOMA.