A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

Resumo Técnico: Um Método de Monte Carlo Inspirado em Sensoriamento Comprimido para Otimização Combinatória

Enunciado do Problema
O artigo aborda o desafio de resolver problemas de otimização combinatória, especificamente aqueles definidos sobre um espaço binário discreto $\{0,1\}^N$. Os autores focam em cenários onde a função objetivo (custo ou recompensa) é complexa, potencialmente não convexa, não diferenciável ou uma "Caixa-Preta" sem uma forma analítica explícita. Esses problemas, que incluem Hamiltonianos de Ising generalizados, o problema da mochila e o problema do caixeiro viajante, tipicamente sofrem de complexidade de tempo exponencial quando abordados via busca por força bruta ou busca ingênua. Embora meta-heurísticas como o simulated annealing (recozimento simulado) e algoritmos genéticos sejam padrões, os autores argumentam que métodos eficientes para funções binárias gerais permanecem limitados.

Metodologia: Otimização de Monte-Carlo Comprimida (MCCO)
A solução proposta é o algoritmo de Otimização de Monte-Carlo Comprimida (MCCO). Ele integra princípios de sensoriamento comprimido, aprendizado compressivo estatístico e métodos de Monte-Carlo para encontrar o ótimo global de uma função com base em uma amostra de seus valores, mesmo que o próprio ótimo nunca seja observado diretamente durante a amostragem.

O algoritmo procede através das seguintes etapas:

1. Amostragem Aleatória: Uma amostra $S_f$ da função objetivo $f$ é gerada ao desenhar $n$ índices de uma distribuição uniforme e avaliar $f$ nesses pontos.
2. Limiarização (Thresholding): Um operador de limiarização rígida $T_t$ é aplicado à amostra, zerando valores abaixo de um limiar específico $t$. Esta etapa é crucial para o desempenho, pois introduz não-linearidade que supera mapas lineares aleatórios simples.
3. Esboço (Sketching/Measurement): Um mapa de esboço $\Phi$ é aplicado à amostra limiarizada para produzir um vetor de esboço $y$. Este vetor contém estimativas empíricas de momentos generalizados da distribuição. O artigo utiliza três tipos de funções de esboço:
   • Interações de Quadrupletos/Quíntupletos: Mapas determinísticos estruturados baseados em interações locais de cadeias de bits (ex: 4 ou 5 bits consecutivos).
   • Esboço Aleatório: Uma matriz com coeficientes extraídos de uma distribuição Gaussiana.
4. Decodificação (Recuperação): Um procedimento de decodificação guloso $\Delta$ (especificamente Orthogonal Matching Pursuit nos experimentos numéricos) é aplicado a $y$ para reconstruir uma estimativa $\tilde{f}$. Os autores escolhem explicitamente métodos gulosos em vez de minimização $\ell_1$ (Basis Pursuit) para evitar o overfitting (sobreajuste) ao exemplo específico e, em vez disso, capturar as características globais da distribuição.
5. Otimização: O valor máximo da função reconstruída $\tilde{f}$ é tomado como a estimativa para o ótimo global.

O método é projetado para problemas "compressíveis", definidos como aqueles onde a função de custo pode ser determinada ou bem aproximada por um conjunto curto de regras (uma representação esparsa em uma base conhecida), mesmo que essa representação não seja explicitamente conhecida pelo usuário.

Principais Contribuições

• Novidade Algorítmica: A introdução do MCCO, que reaproveita técnicas de recuperação de sensoriamento comprimido para otimização combinatória, aproveitando especificamente algoritmos gulosos para prevenir o overfitting em um cenário de Monte-Carlo.
• Justificativa Teórica: O artigo fornece uma análise teórica (Teorema 1) demonstrando que a probabilidade de o máximo real sobreviver ao processo de amostragem e esboço depende da média e da variância do intervalo entre os maiores e os segundos maiores valores da função objetivo. Prova-se que, sob amostragem suficiente, o máximo pode ser preservado com alta probabilidade.
• Implementação Prática: O desenvolvimento do TrOMA (Tractable Optimization Modeling Approach), uma biblioteca Python de código aberto que implementa o MCCO. Esta biblioteca é agnóstica ao hardware (suportando backends clássicos e quânticos, incluindo computadores quânticos da IBM) e permite que usuários otimizem qualquer problema simplesmente fornecendo uma função de custo.
• Escopo Definido: Os autores definem uma classe de problemas "compressíveis" e argumentam que o MCCO é particularmente eficaz para esta classe, que inclui muitos problemas NP-completos.

Resultados Numéricos
Os autores conduziram simulações numéricas em um problema de tamanho $N=12$ (um espaço de $2^{12}$), extraído aleatoriamente da classe de problemas compressíveis. Eles compararam o MCCO contra o Dual Annealing (uma combinação de simulated annealing e fast annealing).

• Desempenho: O MCCO usando funções de esboço estruturadas (Quadruplets e Quintuplets) superou o Dual Annealing.
  • Taxa de Sucesso: O MCCO com esboços de Quadruplets recuperou o máximo global em ~58% dos casos, e Quintuplets em ~49%, comparado a ~46% para o Dual Annealing.
  • Proximidade: Quando o máximo global não era encontrado, as estimativas do MCCO estavam significativamente mais próximas do ótimo. Para Quadruplets, 91% das estimativas estavam a uma distância de Hamming de 1 do ótimo real, comparado a 81% para o Dual Annealing.
  • Eficiência de Amostragem: O MCCO mostrou desempenho competitivo ou superior mesmo com pequenos tamanhos de amostra (50 a 400 amostras).
• Esboços Aleatórios: O MCCO usando um esboço Gaussiano aleatório teve desempenho inferior aos esboços estruturados e foi comparável ao Dual Annealing em termos de recuperação do ótimo global (6%), embora ainda tenha superado um palpite puramente aleatório em termos de distância de Hamming.

Significância e Alegações
O artigo afirma que o MCCO oferece uma alternativa competitiva às meta-heurísticas estabelecidas, como o Dual Annealing, para uma ampla classe de problemas combinatórios, particularmente aqueles que são "compressíveis". A significância reside na capacidade do método de:

1. Lidar com funções objetivo de Caixa-Preta e complexas sem exigir informações de gradiente.
2. Aproveitar a esparsidade da estrutura subjacente do problema (mesmo que desconhecida) para encontrar soluções ótimas com menos avaliações de função.
3. Ser ajustado aos recursos computacionais disponíveis, ajustando parâmetros heurísticos e funções de esboço.
4. Fornecer uma ponte entre a otimização clássica e a computação quântica, uma vez que a decodificação de matrizes estruturadas pode ser facilitada por algoritmos quânticos.

Os autores mantêm-se modestos quanto aos limites exatos de aplicabilidade do método, observando que, embora a classe de problemas compressíveis seja grande, os limites precisos de onde o MCCO supera todos os outros métodos permanecem uma área aberta para investigação adicional. Eles convidam a comunidade a testar o método através da biblioteca TrOMA.