Resumo Técnico: Uma Abordagem Riemanniana para o Transporte Ótimo de Baixo Posto

Declaração do Problema

O Transporte Ótimo (OT) clássico fornece uma métrica rigorosa para comparar distribuições de probabilidade, mas sofre de um gargalo computacional quadrático ($O(mn)$) devido à necessidade de computar matrizes de acoplamento densas. Embora a regularização entrópica permita o uso do algoritmo de Sinkhorn, ela mantém essa escala e introduz viés. Para mitigar isso, o Transporte Ótimo de Baixo Posto (LOT) restringe o plano de transporte a uma estrutura de baixa dimensão, fatorando a matriz de acoplamento $\Gamma$ em subacoplamentos $(U, V)$ que compartilham uma marginal latente $g$.

Apesar da eficiência estrutural das formulações de baixo posto, os solvers existentes (ex: LOT, LR-GW, UB-LOT) dependem fortemente de atualizações de descenso de espelho de primeira ordem acopladas a loops internos iterativos (Dykstra ou projeções de Bregman). Essas abordagens enfrentam diversas limitações:

1. Sensibilidade a Hiperparâmetros: Exigem ajuste cuidadoso de tamanhos de passo e parâmetros de regularização entrópica.
2. Curvatura Ignorada: Falham em explorar a curvatura local do panorama de otimização, levando a uma convergência mais lenta.
3. Sobrecarga Computacional: Os loops internos iterativos para projeção e retração aumentam a complexidade por iteração, particularmente em configurações não balanceadas.

Metodologia

Os autores propõem um arcabouço geométrico riemanniano unificado que modela o conjunto de acoplamentos fatorados positivos de posto-$r$ como subvariedades suaves imersas dentro do ortante positivo. Ao equipar essas variedades com a métrica de produto Fisher-Rao, os autores derivam formulações tratáveis para todos os ingredientes geométricos necessários, permitindo otimização robusta de primeira e segunda ordem.

1. Formulação de Variedade (Manifold)

O arcabouço define duas variedades distintas baseadas em restrições marginais:

• Variedade Balanceada ($\mathcal{M}_{bal}$): Impõe a reconstrução estrita das marginais de origem e alvo ($U\mathbf{1}=a, V\mathbf{1}=b$) e consistência latente ($U^\top\mathbf{1}=V^\top\mathbf{1}$).
• Variedade Não Balanceada ($\mathcal{M}_{ub}$): Relaxa as restrições de marginais externas, exigindo apenas consistência latente ($U^\top\mathbf{1}=V^\top\mathbf{1}$), com desvios marginais penalizados via divergência KL no objetivo.

2. Ingredientes Geométricos

Sob a métrica Fisher-Rao, os autores derivam expressões explícitas para:

• Projetores Ortogonais:
  • Para $\mathcal{M}_{bal}$, a projeção envolve resolver um sistema KKT (reduzido a um complemento de Schur) via Gradiente Conjugado (CG).
  • Para $\mathcal{M}_{ub}$, a projeção simplifica-se para uma expressão em forma fechada, eliminando a necessidade de solvers iterativos.
• Retrações:
  • A retração mapeia vetores tangentes de volta para a variedade via um passo de espelho exponencial Fisher-consistente seguido por uma projeção KL.
  • Para $\mathcal{M}_{bal}$, isso requer projeções Bregman cíclicas (iterativas).
  • Para $\mathcal{M}_{ub}$, a projeção KL colapsa em um escalonamento de coluna em forma fechada, removendo totalmente os loops internos.
• Gradiente e Hessiano Riemanniano:
  • O arcabouço fornece uma formulação agnóstica ao custo, onde o gradiente riemanniano e os produtos vetor-Hessiano dependem apenas das derivadas euclidianas da função de custo específica (OT Linear, Gromov-Wasserstein, etc.) e da geometria da variedade.
  • Isso permite o uso de solvers de segunda ordem (Região de Confiança, Gradiente Conjugado) que utilizam informações de curvatura.

3. Certificado de Suficiência de Posto

O artigo introduz um certificado para verificação de otimalidade global. Ao computar um "gradiente reduzido" (matriz de folga dual) em um ponto crítico de posto-$r$, o método pode verificar se a solução é globalmente ótima para o problema de posto total. Se o posto for insuficiente, o certificado identifica uma direção para o aumento do posto.

Principais Contribuições

1. Formulação Riemanniana Unificada: Formaliza o OT de baixo posto balanceado e não balanceado como variedades suaves sob a métrica Fisher-Rao, fornecendo um único arcabouço geométrico para OT linear, Gromov-Wasserstein (GW) e suas variantes não balanceadas.
2. Operações Não Balanceadas em Forma Fechada: Demonstra que, para OT não balanceado, os projetores do espaço tangente e as retrações reduzem-se a expressões de forma fechada. Isso elimina os loops internos de Dykstra/Bregman exigidos pelos métodos de estado da arte (ex: UB-LOT), reduzindo a complexidade por iteração para $O(rN)$.
3. Solvers de Segunda Ordem: Permite o uso de solvers conscientes de curvatura (CG, Região de Confiança) que alcançam convergência mais rápida do que o descenso de espelho de primeira ordem, sem exigir regularização entrópica ou ajuste de tamanho de passo.
4. Verificação de Otimalidade Global: Fornece um certificado computável para verificar se uma solução de baixo posto é globalmente ótima ou para guiar estratégias de aumento de posto.

Resultados Experimentais

Experimentos extensos em configurações balanceadas e não balanceadas (OT Linear, GW, Fused GW) com tamanhos de conjunto de dados de até $N=50.000$ demonstram:

• Velocidade de Convergência: Solvers riemannianos convergem em um número de ordens de magnitude menor de iterações externas comparado às linhas de base de descenso de espelho.
• Tempo de Execução (Wall-Clock Time): A eliminação dos loops internos na configuração não balanceada leva a acelerações significativas. Por exemplo, no OT não balanceado com outliers, os solvers riemannianos convergem em segundos, enquanto o UB-LOT esgota o tempo ou diverge.
• Desempenho: Os métodos alcançam valores de objetivo superiores ou comparáveis sem o viés entrópico inerente às linhas de base regularizadas.
• Vantagem de Segunda Ordem: Em problemas não convexos (GW, Fused GW), os métodos de Região de Confiança aproveitam a informação do Hessiano para escapar de mínimos locais rasos, superando os métodos de primeira ordem.

Significância

O artigo afirma que, ao mudar de um paradigma de descenso de espelho de primeira ordem para uma perspectiva geométrica riemanniana, os solvers de OT de baixo posto podem superar as limitações de má condição e sensibilidade de hiperparâmetros. A principal significância reside na simplificação estrutural das operações não balanceadas, que transforma um processo iterativo computacionalmente caro em uma avaliação de forma fechada. Isso permite uma otimização livre de regularização e de ajustes, que escala linearmente com o tamanho do conjunto de dados, ao mesmo tempo em que fornece garantias rigorosas de convergência de segunda ordem e verificação de otimalidade global. O arcabouço é apresentado como uma abordagem geral e agnóstica ao custo, aplicável a um amplo espectro de problemas de transporte ótimo.