Resumo Técnico: Abordagens de Relaxação Convexa para Transporte Ótimo de Alta Dimensão

1. Enunciado do Problema

O artigo aborda os desafios computacionais e estatísticos inerentes à resolução de problemas de Transporte Ótimo (OT) em altas dimensões. Embora o OT seja um arcabouço poderoso para comparar distribuições de probabilidade com fidelidade geométrica, sua aplicação é dificultada pela "maldição da dimensionalidade". Especificamente, o custo computacional dos resolvedores de OT padrão cresce rapidamente com o tamanho da amostra, e a complexidade de amostragem necessária para estimar a distância de Wasserstein escala exponencialmente com a dimensão $d$. Estratégias de redução de dimensão existentes, como parametrizações por redes neurais (que carecem de garantias teóricas fortes devido à otimização não convexa) ou distâncias de Wasserstein fatiadas (que aproximam, mas não recuperam a distância real), frequentemente falham em fornecer uma solução escalável e teoricamente fundamentada para distribuições contínuas de alta dimensão.

2. Metodologia

Os autores propõem uma família de abordagens de relaxação convexa que exploram a localidade e a esparsidade das correlações em distribuições de alta dimensão. Em vez de otimizar sobre o plano de transporte conjunto completo $\pi \in \mathcal{P}(X \times Y)$, os métodos aproximam o problema utilizando marginais de baixa ordem e estatísticas de momentos esparsos.

2.1 Suposições Estruturais

A abordagem baseia-se na partição das coordenadas de $d$ dimensões em $K$ clusters e na definição de um grafo de referência $G$ que codifica a estrutura de correlação.

• Partição de Clusters: As coordenadas são agrupadas em clusters $z_k = (x_k, y_k)$.
• Grafo de Referência: Um grafo $G$ com vértices representando clusters e arestas representando interações de pares. O método assume que as dependências decaem com a distância do grafo, permitindo aproximações esparsas.

2.2 Estruturas de Relaxação

O artigo introduz dois níveis primários de relaxação:

1. Relaxação de Marginais:

   • O problema de OT original é relaxado impondo restrições apenas nas marginais do plano de transporte $\pi$ correspondentes a clusters individuais ($\pi_k$) e pares de clusters conectados ($\pi_{ij}$) no grafo $G$.
   • Positividade: A não-negatividade da medida global é relaxada para restrições de Semidefinitude Positiva (PSD) na matriz em blocos dessas marginais.
   • Formulações: Os autores definem três variantes:
     • $(OT_{mar})$: Inclui restrições PSD e não-negatividade (programação Doubly Non-Negative).
     • $(OT^1_{mar})$: Descarta a restrição PSD global, resultando em um problema de Programação Linear (LP).
     • $(OT^2_{mar})$: Descarta a restrição de não-negatividade, resultando em um Programa Semidefinido (SDP) que pode ser adicionalmente reduzido via conversão chordal.

2. Relaxação de Momentos de Cluster:

   • Para lidar com distribuições contínuas sem discretização espacial, as relaxações de marginais são adicionalmente aproximadas usando relaxações de momentos de Soma de Quadrados (SOS).
   • Em vez de otimizar sobre medidas, as variáveis são matrizes de momentos de dimensão finita ($M_k, M_{ij}$) derivadas de uma base polinomial de grau $n$.
   • Inovação Chave: Ao contrário das hierarquias SOS padrão (ex: Mula e Nouy [44]) que exigem momentos de todos os monômios até o grau $n$ (levando a uma complexidade de $O(d^{2n})$), este método restringe a base aos clusters locais e arestas do grafo de referência.
   • Complexidade: O SDP resultante envolve apenas coleções esparsas de momentos. Se o tamanho do cluster e o grau de relaxação forem fixos, o tamanho do problema escala linearmente com $d$ (especificamente $O(d)$) quando o grafo $G$ possui largura de árvore (tree-width) limitada, sendo solúvel via decomposição chordal.

2.3 Extração do Mapa de Transporte

As variáveis duais do SDP relaxado fornecem potenciais de Kantorovich aproximados. Ao restringir esses potenciais ao subespaço da base polinomial escolhida, os autores constroem um mapa de transporte explícito $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$, oferecendo uma alternativa interpretável aos modelos generativos baseados em redes neurais.

3. Contribuições Principentes e Resultados Teóricos

3.1 Modelos Gaussianos com Precisão Esparsa

Para medidas Gaussianas $\mu = \mathcal{N}(m_1, \Sigma_1)$ e $\nu = \mathcal{N}(m_2, \Sigma_2)$ onde as matrizes de precisão são esparsas em relação a um grafo $G$:

• Convergência Exponencial: Os autores provam que a relaxação de momento de cluster (especificamente de grau-1) alcança uma taxa de convergência exponencial no erro de aproximação conforme o raio de conectividade $h$ do grafo de referência $G_h$ aumenta. O limite de erro é da forma $C d \rho^{-h}$.
• Complexidade de Amostragem Melhorada: O limite de erro estatístico para a relaxação esparsa é $O(\sqrt{d/N} + |E(G)|/N)$. Para grafos esparsos onde $|E(G)| = O(d)$, isso melhora o limite da relaxação densa de $O(\sqrt{d/N} + d^2/N)$, demonstrando que explorar a esparsidade reduz significativamente o número de amostras necessárias.

3.2 Perturbações Locais de Medidas de Campo Médio

Para distribuições que são perturbações locais de medidas de produto de campo médio:

• Limites de Aproximação: A relaxação de marginais mostra-se capaz de capturar a geometria de ordem principal da distância de Wasserstein, que corresponde à norma de Sobolev homogênea negativa ponderada.
• Erro Estatístico: Sob grau de relaxação fixo e tamanho de cluster limitado, o erro estatístico escala como $O(d N^{-1/2})$, implicando uma complexidade de amostragem de $O(d^2 \epsilon^{-2})$. Este é um avanço significativo em relação à dependência exponencial de $d$ encontrada na estimativa de OT padrão.

3.3 Limites Estatísticos Gerais

Para distribuições gerais que satisfazem condições de cauda Gaussiana uniforme, o artigo estabelece que o erro estatístico do SDP de momento de cluster é governado pelo número de blocos locais e arestas do grafo ($K + |E(G)|$) em vez da dimensão ambiente $d$. No regime de grau fixo e esparso, o erro escala linearmente com $d$.

4. Resultados Numéricos

Experimentos extensivos validam as afirmações teóricas em diversos cenários:

• Distribuições Gaussianas: A relaxação de momento de cluster exibe convergência exponencial em relação ao raio de conectividade $h$. Ela supera os resolvedores de OT tradicionais (Sinkhorn) e bases ICNN tanto em precisão quanto em eficiência computacional, mantendo baixo erro relativo e tempo de execução mesmo quando a dimensão $d$ aumenta para 1000.
• Medidas de Produto Não-Gaussianas (Beta): O método mantém alta precisão (erro relativo $\approx 10^{-3}$) para medidas de produto não-gaussianas, enquanto os resolvedores de OT tradicionais degradam rapidamente com a dimensão.
• Modelos de Ising: Para modelos de Ising discretos, a relaxação de marginais fornece limites inferiores apertados no custo de OT com tempos de execução ordens de magnitude mais rápidos que as soluções exatas de LP.
• Modelagem Generativa (Ginzburg-Landau & MNIST): Os mapas de transporte extraídos geram amostras que correspondem às marginais alvo com sucesso. No modelo Ginzburg-Landau, o método supera fluxos de normalização, ICNNs e mapas baseados em Sinkhorn na distância de Wasserstein fatiada. No MNIST (em um espaço PCA de 6D), o método produz amostras de dígitos reconhecíveis.

5. Significância e Alegações

O artigo afirma que as relaxações convexas baseadas em marginais e momentos de cluster oferecem um caminho promissor para a redução de dimensão em transporte ótimo de alta dimensão.

• Escalabilidade: Ao alavancar estruturas locais e esparsidade, o método evita a complexidade exponencial do OT padrão e das hierarquias de momentos completos, alcançando escalonamento linear na dimensão tanto para erro quanto para tempo de execução sob suposições estruturais específicas.
• Garantias Teóricas: Diferente das abordagens de redes neurais, o método proposto oferece limites rigorosos de aproximação e erro estatístico, particularmente para modelos Gaussianos esparsos e de perturbação de campo médio.
• Interpretabilidade: A abordagem gera mapas de transporte explícitos derivados de potenciais polinomiais, servindo como uma alternativa mais simples e interpretável aos modelos generativos profundos.
• Robustez: Os resultados empíricos sugerem que o método é robusto mesmo em configurações não-gaussianas onde as garantias teóricas são menos explícitas, mantendo o desempenho onde métodos tradicionais baseados em discretização falham.

Os autores concluem que essas relaxações mitigam efetivamente a maldição da dimensionalidade, tornando o transporte ótimo de alta dimensão computacional e estatisticamente tratável para uma ampla classe de distribuições estruturadas.