Sample complexity of unbalanced entropic OT

Resumo Técnico: Complexidade de Amostragem de OT Entrópico Desbalanceado

Enunciado do Problema
O Transporte Ótimo (OT) fornece um arcabouço geométrico para comparar medidas de probabilidade, mas o OT entrópico balanceado clássico enfrenta duas limitações significativas em aplicações de aprendizado de máquina: (1) a rigidez das restrições de conservação de massa rígidas, que é inadequada para dados com massa ausente ou criada, e (2) uma desfavorável complexidade de amostragem de alta dimensão (a "maldição da dimensionalidade"), onde as taxas de convergência empírica se deterioram com a dimensão ambiente.

Embora a regularização entrópica e as relaxações desbalanceadas (usando $\phi$-divergências) tenham sido desenvolvidas para abordar esses problemas individualmente, as garantias estatísticas existentes para o OT entrópico desbalanceado limitam-se principalmente ao valor de transporte escalar (a função objetivo). Há uma carência de limites de amostra finita de alta probabilidade diretamente sobre o acoplamento ótimo (plano de transporte). Essa lacuna é crítica porque, em aplicações como modelagem generativa ou inferência de trajetória, o próprio acoplamento é o objeto de interesse para predição e interpolação, não apenas o valor do custo.

Metodologia
O artigo desenvolve uma análise estatística do OT entrópico desbalanceado focando nas propriedades geométricas do problema dual. A inovação metodológica central é a introdução de uma formulação de envelope invariante à translação para lidar com a perda de invariância de gauge inerente aos cenários desbalanceados.

1. Formulação Dual e Construção do Envelope:
   Ao contrário do OT balanceado, onde o objetivo dual é invariante sob translações aditivas dos potenciais de Kantorovich ($f \to f+\lambda, g \to g-\lambda$), o OT desbalanceado quebra essa simetria devido às penalidades de divergência marginal que dependem dos níveis absolutos de potencial. Os autores definem um envelope invariante à translação $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$. Esta construção separa explicitamente os graus de liberdade intrínsecos do dual da direção de translação espúria.

2. Análise Geométrica (Compacidade e Convexidade Forte):
   Os autores provam que, sob suposições brandas (espaços compactos, custo Lipschitz), este funcional de envelope admite um domínio de minimização ancorado compacto ($P_{\alpha, \beta}^0$) onde os potenciais são fixados para ter média zero em relação à medida de origem. Crucialmente, neste domínio, o envelope é uniformemente fortemente convexo em relação a uma norma $L^2$ ponderada. Isso recupera a estrutura geométrica favorável perdida no dual desbalanceado padrão.

3. Controle do Parâmetro de Translação:
   Embora o envelope elimine a necessidade de fixação de gauge arbitrária, ele introduz uma otimização sobre um parâmetro de translação $\lambda$. O artigo estabelece que, sob uma condição de domínio suave nos geradores de divergência (Suposição A2), o $\lambda$ ótimo é confinado a um intervalo uniformemente limitado $[-R, R]$. Isso permite limites $L^\infty$ uniformes sobre os potenciais duais.

4. Estabilidade Estatística:
   Aproveitando a convexidade forte do envelope ancorado e a limitação do parâmetro de translação, os autores derivam estimativas de estabilidade. Eles mostam que os potenciais duais empíricos convergem uniformemente para os potenciais populacionais. Essas taxas de convergência dual são então transferidas para o plano de transporte primal via a relação de escala exponencial ($d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$).

Principais Contribuições

• Formulação Dual Invariante à Translação: O artigo introduz uma formulação dual rigorosa que restaura a convexidade forte para o OT entrópico desbalanceado ao quotientar a direção de translação, uma propriedade anteriormente utilizada apenas para estabilidade algorítmica em iterações de Sinkhorn.
• Complexidade de Amostragem ao Nível do Plano: A principal contribuição é a derivação de limites de alta probabilidade de amostra finita para o acoplamento ótimo (plano de transporte) no cenário desbalanceado, em vez de apenas o valor da função objetivo.
• Aplicabilidade a Divergências Gerais: Os resultados aplicam-se a uma ampla classe de $\phi$-divergências (incluindo KL, $\chi^2$, Hellinger, Jensen–Shannon e $\alpha$-divergências) sem exigir provas específicas para cada divergência, baseando-se em argumentos gerais de convexidade e compacidade.
• Constantes Explícitas: O artigo fornece constantes explícitas para os limites no parâmetro de translação e na consequente complexidade de amostragem, esclarecendo a dependência do parâmetro de entropia $\eta$, da função de custo e das propriedades da divergência.

Principais Resultados
O artigo estabelece que, para medidas empíricas $\alpha_n, \beta_n$ derivadas de $n$ amostras, o desvio entre o plano ótimo empírico $\pi_n$ e o plano populacional $\pi^\star$ satisfaz um limite de alta probabilidade da forma:
$$|\langle h, \pi^\star - \pi_n \rangle| \lesssim C \cdot e^{C(M + \|c\|_\infty)/\eta} \|h\|_\infty \sqrt{\frac{m_\alpha m_\beta (\log n + t)}{n}}$$
onde $M$ é um limite uniforme nos potenciais duais, $h$ é uma função de teste, e as constantes dependem da geometria do problema e dos parâmetros de divergência. Notavelmente, se a distribuição de amostragem coincidir com o produto das marginais, o fator $\log n$ pode ser removido.

Significância e Alegações
O artigo afirma que estes resultados esclarecem a necessidade prática de regularização em aplicações de OT em aprendizado de máquina. Especificamente:

• Mitigação da Dimensionalidade: A regularização suaviza a maldição da dimensionalidade, reduzindo o número de amostras necessárias para uma estimativa de transporte estável.
• Compatibilidade Algorítmica: Os estimadores resultantes permanecem compatíveis com solvers do tipo Sinkhorn escaláveis, unindo a teoria estatística à prática computacional.
• Estabilidade para Problemas Inversos: As estimativas de estabilidade direta fornecidas são essenciais para análises complementares de problemas inversos (ex: recuperar custos a partir de amostras), conforme observado em trabalhos relacionados [1].

Os autores enfatizam que sua análise se baseia em "suposições muito brandas e amplamente agnósticas à divergência", tornando o arcabouço teórico robusto e aplicável aos modelos padrão usados na prática. Eles não alegam resolver inteiramente a maldição da dimensionalidade, mas demonstram como o OT desbalanceado entrópico fornece uma alternativa estatisticamente tratável às distâncias de Wasserstein não regularizadas em cenários de alta dimensão.