Résumé Technique : Approches de Relaxation Convexe pour le Transport Optimal de Haute Dimension

1. Énoncé du Problème

L'article traite des défis computationnels et statistiques inhérents à la résolution des problèmes de Transport Optimal (OT) en haute dimension. Bien que l'OT soit un cadre puissant pour comparer des distributions de probabilité avec une fidélité géométrique, son application est entravée par la « malédiction de la dimensionnalité ». Plus précisément, le coût computationnel des solveurs d'OT standards croît rapidement avec la taille de l'échantillon, et la complexité statistique requise pour estimer la distance de Wasserstein croît exponentiellement avec la dimension $d$. Les stratégies de réduction de dimension existantes, telles que les paramétrisations par réseaux de neurones (qui manquent de garanties théoriques fortes en raison de l'optimisation non convexe) ou les distances de Wasserstein découpées (qui approchent mais ne récupèrent pas la distance réelle), échouent souvent à fournir une solution scalable et théoriquement fondée pour les distributions continues de haute dimension.

2. Méthodologie

Les auteurs proposent une famille d'approches de relaxation convexe qui exploitent la localité et la parcimonie des corrélations au sein des distributions de haute dimension. Au lieu d'optimiser sur le plan de transport conjoint complet $\pi \in \mathcal{P}(X \times Y)$, les méthodes approchent le problème en utilisant des marginales d'ordre inférieur et des statistiques de moments parcimonieuses.

2.1 Hypothèses Structurelles

L'approche repose sur la partition des coordonnées de dimension $d$ en $K$ clusters et la définition d'un graphe de référence $G$ qui encode la structure de corrélation.

• Partition de Clusters : Les coordonnées sont regroupées en clusters $z_k = (x_k, y_k)$.
• Graphe de Référence : Un graphe $G$ dont les sommets représentent les clusters et les arêtes représentent les interactions par paires. La méthode suppose que les dépendances décroissent avec la distance du graphe, permettant des approximations parcimonieuses.

2.2 Cadres de Relaxation

L'article introduit deux niveaux principaux de relaxation :

1. Relaxation Marginale :

   • Le problème d'OT original est relaxé en imposant des contraintes uniquement sur les marginales du plan de transport $\pi$ correspondant aux clusters individuels ($\pi_k$) et aux paires de clusters connectés ($\pi_{ij}$) dans le graphe $G$.
   • Positivité : La non-négativité de la mesure globale est relaxée en contraintes de semi-positivité (PSD) sur la matrice par blocs de ces marginales.
   • Formulations : Les auteurs définissent trois variantes :
     • $(OT_{mar})$ : Inclut les contraintes PSD et la non-négativité (programmation Doubly Non-Negative).
     • $(OT^1_{mar})$ : Supprime la contrainte PSD globale, résultant en un problème de Programmation Linéaire (LP).
     • $(OT^2_{mar})$ : Supprime la contrainte de non-négativité, résultant en un Programme Semi-Déterminé (SDP) qui peut être davantage réduit via une conversion chordale.

2. Relaxation de Moment de Cluster :

   • Pour traiter les distributions continues sans discrétisation spatiale, les relaxations marginales sont davantage approximées par des relaxations de moments de Somme de Carrés (SOS).
   • Au lieu d'optimiser sur des mesures, les variables sont des matrices de moments de dimension finie ($M_k, M_{ij}$) dérivées d'une base polynomiale de degré $n$.
   • Innovation Clé : Contrairement aux hiérarchies SOS standard (par exemple, Mula et Nouy [44]) qui nécessitent les moments de tous les monômes jusqu'au degré $n$ (entraînant une complexité de $O(d^{2n})$), cette méthode restreint la base aux clusters locaux et aux arêtes du graphe de référence.
   • Complexité : Le SDP résultant n'implique que des collections de moments parcimonieuses. Si la taille du cluster et le degré de relaxation sont fixés, la taille du problème croît linéairement avec $d$ (spécifiquement $O(d)$) lorsque le graphe $G$ possède une largeur de parcours (tree-width) bornée, résoluble via la décomposition chordale.

2.3 Extraction de la Carte de Transport

Les variables duales du SDP relaxé fournissent des potentiels de Kantorovich approximatifs. En restreignant ces potentiels à l'espace engendré par la base polynomiale choisie, les auteurs construisent une carte de transport explicite $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$, offrant une alternative interprétable aux modèles génératifs basés sur les réseaux de neurones.

3. Contributions Clés et Résultats Théoriques

3.1 Modèles Gaussiens avec Précision Parcimonieuse

Pour les mesures gaussiennes $\mu = \mathcal{N}(m_1, \Sigma_1)$ et $\nu = \mathcal{N}(m_2, \Sigma_2)$ où les matrices de précision sont parcimonieuses par rapport à un graphe $G$ :

• Convergence Exponentielle : Les auteurs prouvent que la relaxation de moment de cluster (spécifiquement de degré 1) atteint un taux de convergence exponentiel dans l'erreur d'approximation à mesure que le rayon de connectivité $h$ du graphe de référence $G_h$ augmente. La borne d'erreur est de la forme $C d \rho^{-h}$.
• Complexité Statistique Améliorée : La borne d'erreur statistique pour la relaxation parcimonieuse est de $O(\sqrt{d/N} + |E(G)|/N)$. Pour les graphes parcimonieux où $|E(G)| = O(d)$, cela améliore la borne de la relaxation dense de $O(\sqrt{d/N} + d^2/N)$, démontant que l'exploitation de la parcimonie réduit significativement le nombre d'échantillons requis.

3.2 Perturbations Locales de Mesures de Champ Moyen

Pour les distributions qui sont des perturbations locales de mesures de produit de champ moyen :

• Bornes d'Approximation : La relaxation marginale est montrée comme capturant la géométrie de premier ordre de la distance de Wasserstein, ce qui correspond à la norme de Sobolev homogène négative pondérée.
• Erreur Statistique : Sous un degré de relaxation fixe et une taille de cluster bornée, l'erreur statistique scale comme $O(d N^{-1/2})$, impliquant une complexité statistique de $O(d^2 \epsilon^{-2})$. C'est une amélioration significative par rapport à la dépendance exponentielle en $d$ trouvée dans l'estimation de l'OT standard.

3.3 Bornes Statistiques Générales

Pour les distributions générales satisfaisant des conditions de queue gaussienne uniforme, l'article établit que l'erreur statistique du SDP de moment de cluster est gouvernée par le nombre de blocs locaux et d'arêtes du graphe ($K + |E(G)|$) plutôt que par la dimension ambiante $d$. Dans le régime de degré fixe et parcimonieux, l'erreur scale linéairement avec $d$.

4. Résultats Numériques

Des expériences approfondies valident les affirmations théoriques à travers divers contextes :

• Distributions Gaussiennes : La relaxation de moment de cluster présente une convergence exponentielle par rapport au rayon de connectivité $h$. Elle surpasse les solveurs d'OT classiques (Sinkhorn) et les bases ICNN en termes de précision et d'efficacité computationnelle, maintenant une erreur relative et un temps d'exécution faibles même lorsque la dimension $d$ atteint 1000.
• Mesures de Produit Non-Gaussiennes (Beta) : La méthode maintient une haute précision (erreur relative $\approx 10^{-3}$) pour les mesures de produit non-gaussiennes, alors que les solveurs d'OT classiques se dégradent rapidement avec la dimension.
• Modèles d'Ising : Pour les modèles d'Ising discrets, la relaxation marginale fournit des bornes inférieures serrées sur le coût d'OT avec des temps d'exécution ordres de grandeur plus rapides que les solutions LP exactes.
• Modélisation Générative (Ginzburg-Landau & MNIST) : Les cartes de transport extraites génèrent avec succès des échantillons qui correspondent aux marginales cibles. Dans les modèles de Ginzburg-Landau, la méthode surpasse les flux de normalisation, les ICNN et les cartes basées sur Sinkhorn en distance de Wasserstein découpée. Sur MNIST (dans un espace PCA de 6D), la méthode produit des échantillons de chiffres reconnaissables.

5. Signification et Revendications

L'article affirme que les relaxations convexes basées sur les moments de cluster et les marginales offrent une voie prometteuse pour la réduction de dimension dans le transport optimal de haute dimension.

• Scalabilité : En exploitant les structures locales et la parcimonie, la méthode évite la complexité exponentielle de l'OT standard et des hiérarchies de moments complètes, atteignant une mise à l'échelle linéaire en dimension pour l'erreur et le temps d'exécution sous des hypothèses structurelles spécifiques.
• Garanties Théoriques : Contrairement aux approches par réseaux de neurones, la méthode proposée fournit des bornes rigoureuses d'approximation et d'erreur statistique, particulièrement pour les modèles gausiens parcimonieux et les perturbations de champ moyen.
• Interprétabilité : L'approche produit des cartes de transport explicites dérivées de potentiels polynomiaux, servant d'alternative plus simple et interprétable aux modèles génératifs profonds.
• Robustesse : Les résultats empiriques suggèrent que la méthode est robuste même dans des contextes non-gausiens où les garanties théoriques sont moins explicites, maintenant des performances là où les méthodes traditionnelles basées sur la discrétisation échouent.

Les auteurs concluent que ces relaxations atténuent efficacement la malédiction de la dimensionnalité, rendant le transport optimal de haute dimension computationnellement et statistiquement traitable pour une large classe de distributions structurées.