Resumo Técnico: Busca de Vizinhança Grande Regularizada (RLNS)

Definição do Problema

A integração de camadas de otimização combinatória em redes neurais emergiu como um paradigma poderoso para a predição estruturada, permitindo que modelos gerem decisões discretas que satisfaçam restrições complexas. A formulação padrão envolve uma camada definida por $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$, onde $\mathcal{Y}$ é um conjunto finito, porém combinatorialmente grande, de saídas viáveis.

O desafio fundamental neste cenário é a diferenciabilidade. Como o operador $\arg \max$ fornece gradientes nulos em quase todos os pontos, as abordagens existentes tipicamente dependem de regularização para gerar uma relaxação contínua e diferenciável. No entanto, a maioria dos métodos atuais (por exemplo, perdas Fenchel-Young, otimizadores perturbados) assume fundamentalmente o acesso a um solver global exato (um oráculo MAP global) ou a um oráculo marginal para computar expectativas da distribuição de Gibbs. Para problemas de otimização NP-difíceis comuns em pesquisa operacional, chamar um oráculo global em cada etapa de treinamento é computacionalmente intratável. Consequentemente, os praticantes recorrem a heurísticas escaláveis como a Busca de Vizinhança Grande (LNS), que refina iterativamente as soluções congelando subconjuntos de variáveis e reotimizando o restante. A falta de um framework principiado para utilizar a LNS como uma camada combinatória diferenciável permanece um gargalo crítico.

Metodologia: LNS Regularizada (RLNS)

Os autores introduzem a Busca de Vizinhança Grande Regularizada (RLNS), uma versão estocástica da LNS que preenche a lacuna entre heurísticas escaláveis e camadas de otimização diferenciáveis. A ideia central é regularizar ou perturbar os subproblemas locais dentro do framework de LNS, transformando a heurística em um amostrador de Cadeia de Markov Monte Carlo (MCMC) eficiente sobre o conjunto combinatório de soluções viáveis.

1. Framework e Regularização Local

A RLNS define uma família de funções de regularização local derivadas de um regularizador global $\Omega$. Para um subconjunto de soluções $\mathcal{Z} \subseteq \mathcal{Y}$, um regularizador local $\Omega_{\mathcal{Z}}$ é definido via uma aplicação de inclusão. Em vez de resolver o problema regularizado global, a RLNS amostra iterativamente de distribuições localmente regularizadas $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$, onde $\mathcal{Y}(k)$ é a vizinhança local definida pelo congelamento de um subconjunto de coordenadas $S^{(k)}$.

2. Regularização Entrópica e Amostragem de Gibbs em Blocos

Quando o regularizador global é a entropia negativa de Shannon ($\Omega = -\gamma H_s$), os autores provam que a RLNS realiza uma amostragem de Gibbs em blocos exata. Especificamente, a distribuição localmente regularizada coincide com a distribuição de Gibbs globalmente regularizada condicionada às variáveis fixas:
$$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])(y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$$
Sob um esquema de seleção de variáveis irredutível, a distribuição estacionária das iterações da RLNS converge exatamente para a distribuição de Gibbs globalmente regularizada. Este resultado é exclusivo à regularização entrópica; a Proposição 2 caracteriza a entropia de Shannon como o único regularizador separável que garante essa exatidão.

3. Regularização Baseada em Perturbação

Em cenários onde oráculos marginais locais (necessários para amostragem entrópica) são intratáveis, mas oráculos MAP locais estão disponíveis, os autores propõem o uso de regularização baseada em perturbação. Ao adicionar ruído $\epsilon Z$ aos scores locais e resolver o problema de maximização local perturbado, a RLNS pode amostrar da distribuição local regularizada. Esta abordagem aproveita oráculos LNS padrão (por exemplo, programação dinâmica para subproblemas de mochila/knapsack) sem exigir mecanismos de rejeição de amostras, ao contrário da busca local baseada em Metropolis-Hastings.

4. Aprendizado e Interpolação

O artigo estabelece uma conexão entre o número de iterações da RLNS ($K$) e o objetivo de aprendizado:

• $K=1$ (Perda Fenchel-Young Local): Um único passo de RLNS fornece um estimador não viesado para uma perda Fenchel-Young local. No cenário entrópico, isso recupera o objetivo de pseudoverossimilhança (verossimilhança composta), que maximiza a verossimilhança de subconjuntos de variáveis condicionadas ao restante.
• $K \to \infty$ (Perda Fenchel-Young Global): À medida que as iterações aumentam, o estimador converge para o gradiente da perda Fenchel-Young global, aproximando a estimativa de máxima verossimilhança exata.
  Isso permite que os praticantes interpole entre a pseudoverossimilhança e a estimativa de máxima verossimilhança exata ajustando $K$, possibilitando o aprendizado de ponta a ponta sem solvers globais.

Principais Contribuições

1. Framework RLNS: Introdução de uma versão estocástica e regularizada da LNS que integra a regularização local nos subproblemas de LNS, criando uma camada combinatória diferenciável.
2. Equivalência Teórica: Prova de que, sob regularização entrópica, a RLNS implementa um amostrador de Gibbs em blocos exato cuja distribuição estacionária coincide com a distribuição de Gibbs globalmente regularizada.
3. Tratabilidade via Perturbação: Demonstração de que a regularização baseada em perturbação permite que a RLNS utilize oráculos MAP locais padrão, garantindo a tratabilidade sempre que a LNS padrão for tratável.
4. Interpolação de Paradigmas de Aprendizado: Demonstração teórica e empírica de que o número de iterações da RLNS permite a interpolação entre a pseudoverossimilhança e a estimativa de máxima verossimilhança exata.
5. Validação Empírica: Avaliação em três problemas distintos:
   • Vetores $\kappa$-hot: Tarefa de estimativa controlada validando a convergência contra o ground truth.
   • Problema de Atribuição Generalizada (GAP): Aprendizado de predição de atribuições onde os subproblemas locais são problemas de Mochila (Knapsack) 0/1.
   • Escalonamento de Veículos Estocástico: Um benchmark do mundo real onde a RLNS-1 supera as bases de diferenciação blackbox e de entropia cruzânea binária (BCE).

Resultados

• Convergência: No experimento de vetores $\kappa$-hot, a RLNS converge mais rápido que o MCMC de Busca Local e atinge um Erro Médio Absoluto (MAE) menor do que a estimativa de Monte Carlo para o mesmo número de amostras, particularmente quando uma alta proporção de variáveis é mantida livre.
• Escalabilidade: Nos experimentos de GAP, os oráculos MAP locais usados pela RLNS são ordens de magnitude mais rápidos que os solvers de Programação Linear Inteira Mista (MILP) globais, especialmente conforme a escala do problema aumenta.
• Desempenho: No escalonamento de veículos estocásticos, a RLNS-1 (usando uma única iteração) aproxima-se do desempenho do aprendizado Fenchel-Young perturbado (PFY) global em termos de custo de atraso, enquanto exige significativamente menos computação do que os solvers globais. Ela supera significativamente as bases de Diferenciação Blackbox (DBB) e Entropia Cruzada Binária (BCE).
• Análise de Viés: Limites teóricos mostram que o erro de aproximação escala com o número de restrições compartilhadas (restrições de corte) entre as variáveis congeladas e livres, motivando esquemas de seleção de variáveis que minimizam essas dependências cruzadas (ex: seleção de corte mínimo/min-cut).

Significância e Alegações

O artigo afirma preencher uma lacuna crítica na literatura ao permitir o uso de heurísticas altamente escaláveis (LNS) como camadas diferenciáveis em redes neurais, removendo a dependência de solvers globais computacionalmente intratáveis. Ao estabelecer uma conexão rigorosa entre LNS e amostragem de Gibbs, o trabalho fornece um framework principiado para diferenciar através de camadas de otimização combinatória usando apenas oráculos locais. Os autores posicionam a RLNS como uma solução prática para o aprendizado de ponta a ponta em tarefas de predição estruturada envolvendo restrições NP-difíceis, oferecendo um compromisso ajustável entre custo computacional e precisão estatística através do número de iterações $K$.