Resumen Técnico: Enfoques de Relajación Convexa para el Transporte Óptimo de Alta Dimensión

1. Planteamiento del Problema

El artículo aborda los desafíos computacionales y estadísticos inherentes a la resolución de problemas de Transporte Óptimo (OT, por sus siglas en inglés) en altas dimensiones. Si bien el OT es un marco poderoso para comparar distribuciones de probabilidad con fidelidad geométrica, su aplicación se ve obstaculizada por la "maldición de la dimensionalidad". Específicamente, el costo computacional de los resolvedores de OT estándar crece rápidamente con el tamaño de la muestra, y la complejidad de muestreo requerida para estimar la distancia de Wasserstein escala exponencialmente con la dimensión $d$. Las estrategias de reducción de dimensión existentes, como las parametrizaciones mediante redes neuronales (que carecen de garantías teóricas sólidas debido a la optimización no convexa) o las distancias de Wasserstein segmentadas (que aproximan pero no recuperan la distancia real), a menudo fallan al intentar proporcionar una solución escalable y teóricamente fundamentada para distribuciones continuas de alta dimensión.

2. Metodología

Los autores proponen una familia de enfoques de relajación convexa que aprovechan la localidad y la dispersión (sparsity) de las correlaciones dentro de las distribuciones de alta dimensión. En lugar de optimizar sobre el plan de transporte conjunto completo $\pi \in \mathcal{P}(X \times Y)$, los métodos aproximan el problema utilizando marginales de bajo orden y estadísticas de momentos dispersos.

2.1 Supuestos Estructurales

El enfoque se basa en la partición de las coordenadas de $d$ dimensiones en $K$ clústeres y en la definición de un grafo de referencia $G$ que codifica la estructura de correlación.

• Partición de Clústeres: Las coordenadas se agrupan en clústeres $z_k = (x_k, y_k)$.
• Grafo de Referencia: Un grafo $G$ con vértices que representan clústeres y aristas que representan interacciones de pares. El método asume que las dependencias decrecen con la distancia del grafo, lo que permite aproximaciones dispersas.

2.2 Marcos de Relajación

El artículo introduce dos niveles primarios de relajación:

1. Relajación de Marginales:

   • El problema de OT original se relaja imponiendo restricciones solo en los marginales del plan de transporte $\pi$ correspondientes a clústeres individuales ($\pi_k$) y pares de clústeres conectados ($\pi_{ij}$) en el grafo $G$.
   • Positividad: La no negatividad de la medida global se relaja mediante restricciones de Semidefinitud Positiva (PSD) sobre la matriz de bloques de estos marginales.
   • Formulaciones: Los autores definen tres variantes:
     • $(OT_{mar})$: Incluye restricciones PSD y de no negatividad (programación Doblemente No Negativa).
     • $(OT^1_{mar})$: Elimina la restricción PSD global, resultando en un problema de Programación Lineal (LP).
     • $(OT^2_{mar})$: Elimina la restricción de no negatividad, resultando en un Programa Semidefinido (SDP) que puede reducirse adicionalmente mediante conversión cordal.

2. Relajación de Momentos de Clúster:

   • Para manejar distribuciones continuas sin discretización espacial, las relajaciones de marginales se aproximan mediante relajaciones de momentos de Suma de Cuadrados (SOS).
   • En lugar de optimizar sobre medidas, las variables son matrices de momentos de dimensión finita ($M_k, M_{ij}$) derivadas de una base polinómica de grado $n$.
   • Innovación Clave: A diferencia de las jerarquías SOS estándar (por ejemplo, Mula y Nouy [44]) que requieren momentos de todos los monomios hasta el grado $n$ (lo que conlleva una complejidad de $O(d^{2n})$), este método restringe la base a clústeres locales y aristas del grafo de referencia.
   • Complejidad: El SDP resultante involucra colecciones dispersas de momentos. Si el tamaño del clúster y el grado de relajación son fijos, el tamaño del problema escala linealmente con $d$ (específicamente $O(d)$) cuando el grafo $G$ tiene un ancho de árbol (tree-width) acotado, resolviéndose mediante descomposición cordal.

2.3 Extracción del Mapa de Transporte

Las variables duales del SDP relajado proporcionan potenciales de Kantorovich aproximados. Al restringir estos potenciales al subespacio de la base polinómica elegida, los autores construyen un mapa de transporte explícito $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$, ofreciendo una alternativa interpretable a los modelos generativos basados en redes neuronales.

3. Contribuciones Clave y Resultados Teóricos

3.1 Modelos Gaussianos con Precisión Dispersa

Para medidas gaussianas $\mu = \mathcal{N}(m_1, \Sigma_1)$ y $\nu = \mathcal{N}(m_2, \Sigma_2)$ donde las matrices de precisión son dispersas con respecto a un grafo $G$:

• Convergencia Exponencial: Los autores demuestran que la relajación de momentos de clúster (específicamente de grado 1) logra una tasa de convergencia exponencial en el error de aproximación a medida que aumenta el radio de conectividad $h$ del grafo de referencia $G_h$. El límite de error es de la forma $C d \rho^{-h}$.
• Mejora en la Complejidad de Muestreo: El límite de error estadístico para la relajación dispersa es $O(\sqrt{d/N} + |E(G)|/N)$. Para grafos dispersos donde $|E(G)| = O(d)$, esto mejora el límite de la relajación densa de $O(\sqrt{d/N} + d^2/N)$, demostrando que el aprovechamiento de la dispersión reduce significativamente el número de muestras requeridas.

3.2 Perturbaciones Locales de Medidas de Campo Medio

Para distribuciones que son perturbaciones locales de medidas de producto de campo medio:

• Límites de Aproximación: Se demuestra que la relajación de marginales captura la geometría de orden principal de la distancia de Wasserstein, la cual corresponde a la norma de Sobolev homogénea negativa ponderada.
• Error Estadístico: Bajo un grado de relajación fijo y un tamaño de clúster acotado, el error estadístico escala como $O(d N^{-1/2})$, lo que implica una complejidad de muestreo de $O(d^2 \epsilon^{-2})$. Esta es una mejora significativa respecto a la dependencia exponencial de $d$ encontrada en la estimación de OT estándar.

3.3 Límites Estadísticos Generales

Para distribuciones generales que satisfacen condiciones de cola gaussiana uniforme, el artículo establece que el error estadístico del SDP de momentos de clúster está gobernado por el número de bloques locales y aristas del grafo ($K + |E(G)|$) en lugar de la dimensión ambiente $d$. En el régimen de grado fijo y disperso, el error escala linealmente con $d$.

4. Resultados Numéricos

Experimentos extensos validan las afirmaciones teóricas en diversos entornos:

• Distribuciones Gaussianas: La relajación de momentos de clúster exhibe una convergencia exponencial con respecto al radio de conectividad $h$. Supera a los resolvedores de OT vainilla (Sinkhorn) y a las bases ICNN tanto en precisión como en eficiencia computacional, manteniendo un error relativo y un tiempo de ejecución bajos incluso cuando la dimensión $d$ aumenta a 1000.
• Medidas de Producto No Gaussianas (Beta): El método mantiene una alta precisión (error relativo $\approx 10^{-3}$) para medidas de producto no gaussianas, mientras que los resolvedores de OT vainilla se degradan rápidamente con la dimensión.
• Modelos de Ising: Para modelos de Ising discretos, la relajación de marginales proporciona límites inferiores ajustados al costo de OT con tiempos de ejecución órdenes de magnitud más rápidos que las soluciones exactas de LP.
• Modelado Generativo (Ginzburg-Landau y MNIST): Los mapas de transporte extraídos generan con éxito muestras que coinciden con los marginales objetivo. En modelos de Ginzburg-Landau, el método supera a los flujos normalizantes, ICNNs y mapas basados en Sinkhorn en la distancia de Wasserstein segmentada. En MNIST (en un espacio PCA de 6D), el método produce muestras de dígitos reconocibles.

5. Significación y Reivindicaciones

El artículo sostiene que las relajaciones convexas basadas en marginales y momentos de clúster ofrecen un camino prometedor para la reducción de la dimensión en el transporte óptimo de alta dimensión.

• Escalabilidad: Al aprovechar las estructuras locales y la dispersión, el método evita la complejidad exponencial del OT estándar y de las jerarquías de momentos completas, logrando un escalamiento lineal en la dimensión tanto para el error como para el tiempo de ejecución bajo supuestos estructurales específicos.
• Garantías Teóricas: A diferencia de los enfoques de redes neuronales, el método propuesto proporciona límites rigurosos de aproximación y de error estadístico, particularmente para modelos gaussianos dispersos y de perturbación de campo medio.
• Interpretabilidad: El enfoque produce mapas de transporte explícitos derivados de potenciales polinómicos, sirviendo como una alternativa más simple e interpretable a los modelos generativos profundos.
• Robustez: Los resultados empíricos sugieren que el método es robusto incluso en entornos no gaussianos donde las garantías teóricas son menos explícitas, manteniendo el rendimiento donde los métodos tradicionales basados en discretización fallan.

Los autores concluyen que estas relajaciones mitigan eficazmente la maldición de la dimensionalidad, haciendo que el transporte óptimo de alta dimensión sea computacional y estadísticamente tratable para una amplia clase de distribuciones estructuradas.