Sample complexity of unbalanced entropic OT

Résumé Technique : Complexité d'Échantillonnage de l'OT Entropique Déséquilibré

Énoncé du Problème
Le transport optimal (OT) fournit un cadre géométrique pour comparer des mesures de probabilité, mais l'OT équilibré classique fait face à deux limitations significatives dans les applications d'apprentissage automatique : (1) la rigidité des contraintes de conservation de masse strictes, qui est inadaptée aux données présentant des masses manquantes ou créées, et (2) une complexité d'échantillonnage en haute dimension défavorable (le « fléau de la dimension ») où les taux de convergence empiriques se détériorent avec la dimension ambiante.

Bien que la régularisation entropique et les relaxations déséquilibrées (utilisant des $\phi$-divergences) aient été développées pour traiter ces problèmes individuellement, les garanties statistiques existantes pour l'OT entropique déséquilibré se limitent principalement à la valeur de transport scalaire (la fonction objectif). Il existe un manque de bornes de convergence sur échantillon fini à haute probabilité directement sur le couplage optimal (plan de transport). Cette lacune est critique car, dans des applications comme la modélisation générative ou l'inférence de trajectoire, le couplage lui-même est l'objet d'intérêt pour la prédiction et l'interpolation, et non seulement la valeur du coût.

Méthodologie
L'article développe une analyse statistique de l'OT entropique déséquilibré en se concentrant sur les propriétés géométriques du problème dual. L'innovation méthodologique centrale est l'introduction d'une formulation d'enveloppe invariante par translation pour gérer la perte d'invariance de jauge inhérente aux contextes déséquilibrés.

1. Formulation Duale et Construction de l'Enveloppe :
   Contrairement à l'OT équilibré, où l'objectif dual est invariant sous les translations additives des potentiels de Kantorovich ($f \to f+\lambda, g \to g-\lambda$), l'OT déséquilibré brise cette symétrie en raison des pénalités de divergence marginale dépendant des niveaux absolus des potentiels. Les auteurs définissent une enveloppe invariante par translation $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$. Cette construction sépare explicitement les degrés de liberté intrinsèques du dual de la direction de translation parasite.

2. Analyse Géométrique (Compacité et Convexité Forte) :
   Les auteurs prouvent que, sous des hypothèses légères (espaces compacts, coût Lipschitzien), cette fonctionnelle d'enveloppe admet un domaine de minimisation ancré compact ($P_{\alpha, \beta}^0$) où les potentiels sont fixés pour avoir une moyenne nulle par rapport à la mesure source. Crucialement, sur ce domaine, l'enveloppe est uniformément fortement convexe par rapport à une norme $L^2$ pondérée. Cela permet de récupérer la structure géométrique favorable perdue dans le dual déséquilibré standard.

3. Contrôle du Paramètre de Translation :
   Bien que l'enveloppe élimine la nécessité d'un ancrage de jauge arbitraire, elle introduit une optimisation sur un paramètre de translation $\lambda$. L'article établit que, sous une condition de domaine légère sur les générateurs de divergence (Hypothèse A2), le $\lambda$ optimal est confiné dans un intervalle uniformément borné $[-R, R]$. Cela permet d'obtenir des bornes $L^\infty$ uniformes sur les potentiels duaux.

4. Stabilité Statistique :
   En s'appuyant sur la forte convexité de l'enveloppe ancrée et sur le caractère borné du paramètre de translation, les auteurs dérivent des estimations de stabilité. Ils montrent que les potentiels duaux empiriques convergent uniformément vers les potentiels de la population. Ces taux de convergence duaux sont ensuite transférés au plan de transport primal via la relation d'échelle exponentielle ($d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$).

Principales Contributions

• Formulation Duale Invariante par Translation : L'article introduit une formulation duale rigoureuse qui restaure la forte convexité pour l'OT entropique déséquilibré en quotientant la direction de translation, une propriété précédemment utilisée uniquement pour la stabilité algorithmique des itérations de Sinkhorn.
• Complexité d'Échantillonnage au Niveau du Plan : La contribution principale est la dérivation de bornes de haute probabilité sur échantillon fini pour le couplage optimal (plan de transport) dans le cadre déséquilibré, plutôt que pour la seule valeur de l'objectif.
• Applicabilité à une Large Classe de Divergences : Les résultats s'appliquent à une large classe de $\phi$-divergences (incluant KL, $\chi^2$, Hellinger, Jensen–Shannon, et les $\alpha$-divergences) sans nécessiter de preuves spécifiques à chaque divergence, en s'appuyant sur des arguments généraux de convexité et de compacité.
• Constantes Explicites : L'article fournit des constantes explicites pour les bornes sur le paramètre de translation et la complexité d'échantillonnage résultante, clarifiant la dépendance vis-à-vis du paramètre d'entropie $\eta$, de la fonction de coût et des propriétés de la divergence.

Résultats Principaux
L'article établit que pour des mesures empiriques $\alpha_n, \beta_n$ dérivées de $n$ échantillons, l'écart entre le plan optimal empirique $\pi_n$ et le plan de la population $\pi^\star$ satisfait une borne de haute probabilité de la forme :
$$|\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}}$$
où $M$ est une borne uniforme sur les potentiels duaux, $h$ est une fonction test, et les constantes dépendent de la géométrie du problème et des paramètres de divergence. Notamment, si la distribution d'échantillonnage correspond au produit des marginales, le facteur $\log n$ peut être supprimé.

Signification et Revendications
L'article affirme que ces résultats clarifient la nécessité pratique de la régularisation dans les applications d'OT en apprentissage automatique. Spécifiquement :

• Atténuation de la Dimensionnalité : La régularisation adoucit le fléau de la dimension, réduisant le nombre d'échantillons requis pour une estimation de transport stable.
• Compatibilité Algorithmique : Les estimateurs résultants restent compatibles avec les solveurs de type Sinkhorn hautement scalables, comblant le fossé entre la théorie statistique et la pratique computationnelle.
• Stabilité pour les Problèmes Inverses : Les estimations de stabilité directe fournies sont essentielles pour les analyses de problèmes inverses compagnons (par exemple, la récupération des coûts à partir d'échantillons), comme noté dans les travaux connexes [1].

Les auteurs soulignent que leur analyse repose sur des « hypothèses très légères et largement agnostiques vis-à-vis de la divergence », rendant le cadre théorique robuste et applicable aux modèles standards utilisés en pratique. Ils ne prétendent pas résoudre entièrement le fléau de la dimension, mais démontrent comment l'OT entropique déséquilibré fournit une alternative statistiquement traitable aux distances de Wasserstein non régularisées dans des contextes de haute dimension.