Stability of the Monge Map in Semi-Dual Optimal Transport

Résumé Technique : Stabilité de la Carte de Monge en Transport Optimal Semi-Dual

Énoncé du Problème
Le Transport Optimal (OT) est devenu un outil fondamental en apprentissage automatique, sous-tendant des modèles génératifs tels que les GAN, les VAE et les modèles de diffusion. Une classe significative d'algorithmes, incluant le Transport Optimal Neuronal (NOT), repose sur la formulation semi-duale du problème OT combinée à une optimisation amortie. Bien que ces méthodes exploitent l'existence et l'unicité des cartes de transport optimal (cartes de Monge) sous des conditions spécifiques, elles manquent souvent de garanties de convergence rigoureuses pour les cartes apprises. La littérature existante suppose fréquemment l'existence d'une carte optimale et le caractère bien posé du problème d'optimisation, pourtant ces hypothèses peuvent échouer en pratique. De plus, des observations empiriques suggèrent que les algorithmes numériques nécessitent souvent beaucoup plus d'itérations pour mettre à jour la carte de transport ($t$) que le potentiel dual ($\psi$), un phénomène précédemment dépourvu d'explication théorique.

Méthodologie et Cadre Théorique
Les auteurs analysent la formulation semi-duale du problème OT, en se concentrant spécifiquement sur la structure de point selle du fonctionnel objectif. L'étude suppose que $X$ et $Y$ sont des sous-ensembles compacts de $\mathbb{R}^n$ avec des mesures de probabilité $\mu$ et $\nu$ absolument continues par rapport à la mesure de Lebesgue.

1. Analyse du Point Selle : Le papier reformule le problème semi-dual comme un problème minimax impliquant une carte de transport $t$ et un potentiel $\psi$. Le fonctionnel objectif est défini par :
   $$F(\psi, t) = \int_X c(x, t(x)) d\mu + \int_Y \psi(y) d(\nu - t_\sharp \mu)$$
   Les auteurs démontrent que cette formulation possède une structure de point selle dégénérée. Plus précisément, à la carte de transport optimale $T^\star$, la valeur du fonctionnel $F(\psi, T^\star)$ devient indépendante du potentiel $\psi$. Cette « platitude » implique que, une fois la carte de transport proche de l'optimum, le potentiel $\psi$ n'est plus uniquement déterminé par l'objectif, même si la carte n'est pas encore parfaitement optimale.

2. Conditions de Convergence : Contrairement aux travaux antérieurs qui s'appuient sur l'optimalité du potentiel dual pour prouver la convergence de la carte, ce papier dérive des conditions nécessaires et suffisantes pour la convergence des cartes de Monge qui ne requièrent pas que $\psi$ soit optimal. Les auteurs établissent une borne d'erreur pour la carte de transport $t$ dans la norme $L^2$ :
   $$\|t - T^\star\|_{L^2}^2 \lesssim |F(t, \psi) - W_2(\mu, \nu)^2| + d_{KR}(t_\sharp \mu, \nu)$$
   Cette estimation montre que la distance à la carte optimale dépend de l'écart dans la valeur de l'objectif et de la distance de Kantorovich-Rubinstein entre la mesure image par l'application et la cible, plutôt que de la proximité de $\psi$ par rapport au potentiel optimal.

3. Interprétation par les Systèmes Dynamiques : Le papier interprète la dynamique d'entraînement des algorithmes NOT comme un système dynamique continu à deux échelles de temps. L'analyse révèle que la contrainte $t_\sharp \mu = \nu$ n'est pas satisfaite lors des étapes intermédiaires d'entraînement, ce qui provoque une maximisation non bornée sur $\psi$ sans force de rappel. Pour stabiliser le système, la variable primale $t$ doit évoluer sur une échelle de temps plus rapide que la variable duale $\psi$. Cela fournit une justification théorique à la pratique empirique consistant à effectuer plusieurs étapes de descente de gradient sur la carte de transport pour chaque unique étape de montée de gradient sur le potentiel.

Contributions et Résultats Clés

• Identification de la Dégénérescence : Le papier identifie explicitement la structure de point selle dégénérée dans la formulation OT semi-duale, où l'objectif devient indépendant du potentiel à la carte optimale. Cela explique pourquoi le potentiel peut diverger ou échouer à converger même lorsque la carte de transport converge.
• Estimation de Convergence Indépendante du Potentiel : Les auteurs fournissent une estimation de convergence (Équation 17) qui borne l'erreur de la carte de transport sans supposer l'optimalité du potentiel dual. Cela remet en question les hypothèses antérieures dans la littérature qui lient directement la convergence de la carte à la convergence du potentiel.
• Explication des Mises à Jour à Deux Échelles de Temps : Le papier valide théoriquement la règle de mise à jour « à deux échelles de temps » utilisée dans NOT et les formulations WGAN connexes. Il démontre que mettre à jour la carte $t$ plusieurs fois par mise à jour du potentiel ($K \eta_t / \eta_\psi$) est nécessaire pour stabiliser le système et réduire les violations de contraintes avant que le potentiel ne soit mis à jour.
• Validation Expérimentale : Des expériences numériques sur des distributions gaussiennes confirment que la carte de transport peut converger vers la solution optimale tandis que le potentiel reste loin de l'optimalité. Les résultats montrent que le ratio des étapes de mise à jour ($K$) et des taux d'apprentissage ($\eta_t/\eta_\psi$) affecte de manière critique si la carte ou le potentiel est appris avec plus de précision.

Signification et Revendications
Le papier revendique fournir une explication théorique du comportement pratique des algorithmes de transport optimal neuronal, spécifiquement pourquoi ils nécessitent souvent plus d'itérations pour la carte que pour le potentiel. En caractérisant le problème semi-dual comme une tâche d'optimisation contrainte avec un point selle dégénéré, les auteurs clarifient pourquoi les garanties de convergence standard basées sur l'optimalité du potentiel sont insuffisantes.

Les auteurs soulignent que l'existence d'un infimum dans le problème semi-dual ne garantit pas l'existence d'un minimiseur pour le potentiel, une distinction qui a conduit à des revendications incorrectes dans la littérature antérieure. Ils soutiennent que les « solutions parasites » et les déviations de gradient observées en pratique découlent de cette dégénérescence, où différents potentiels produisent des gradients distincts près de la carte optimale. Par conséquent, le papier suggère que l'imposition de contraintes structurelles (comme la convexité) sur le potentiel peut réduire la dégénérescence mais introduit un biais d'approximation, tandis que les paramétrisations non contraintes peuvent mieux performer malgré l'absence de propriétés de point selle strictes.

L'ouvrage conclut que la stabilité de la carte de Monge en OT semi-dual dépend des échelles de temps relatives des mises à jour de la carte et du potentiel, et que la convergence de la carte n'implique pas la convergence du potentiel.