Résumé technique : Optimisation du temps d'exécution computationnel-statistique pour l'estimation de la distance de Wasserstein

Énoncé du problème

La distance de Wasserstein au carré, $W_2^2(P, Q)$, est une métrique standard pour mesurer l'écart entre les distributions de probabilité $P$ et $Q$ dans $\mathbb{R}^d$. Dans les tâches pratiques d'analyse de données et d'apprentissage automatique (par exemple, l'estimation de paramètres, les tests d'hypothèses), ces distributions sont inconnues et doivent être estimées à partir d'échantillons empiriques $\hat{P}_n$ et $\hat{Q}_n$ de taille $n$.

Les approches existantes se heurtent à un goulot d'étranglement fondamental : le calcul exact de $W_2^2(\hat{P}_n, \hat{Q}_n)$ ou avec une erreur additive $\epsilon$ nécessite généralement un temps d'exécution qui évolue défavorablement avec $n$ et $\epsilon$ (par exemple, $O(n^2/\epsilon^2)$ ou pire). À l'inverse, les approches purement statistiques qui reposent sur le taux de convergence des mesures empiriques ignorent souvent le coût computationnel de la résolution du problème de transport optimal sur les grands ensembles de données résultants.

Ce papier aborde le Temps d'Exécution Computationnel-Statistique (CSR). L'objectif est de concevoir un algorithme randomisé qui estime $W_2^2(P, Q)$ avec une erreur additive $\epsilon$ en espérance, où le temps d'exécution $O(f(\epsilon))$ prend en compte à la fois le coût de la collecte des échantillons (supposé $O(1)$ par échantillon) et le coût du calcul. Les auteurs soutiennent que la précision cible devrait s'aligner sur l'erreur statistique induite par la taille de l'échantillon, plutôt que de traiter les mesures empiriques comme la vérité terrain.

Méthodologie : Paradigme Échantillon-Brouillon-Résoudre

Les auteurs proposent un paradigme en trois phases pour atteindre des CSR rapides, en particulier pour les distributions possédant des densités lisses au sens de Hölder sur le domaine $(0, 1)^d$ :

1. Échantillonner : Collecter $n$ échantillons aléatoires de $P$ et $Q$ pour former les mesures empiriques $\hat{P}_n$ et $\hat{Q}_n$.
2. Brouillonner (Sketch) : Projeter ces échantillons sur une grille cartésienne régulière $G_h$ avec une largeur de cellule $h = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$. Toute la masse contenue dans une cellule de grille est effondrée vers le centre de la cellule. Cela crée des mesures discrètes compressées $G_h\#\hat{P}_n$ et $G_h\#\hat{Q}_n$.
3. Résoudre : Calculer la distance de Wasserstein au carré exacte entre les mesures brouillonisées en utilisant un algorithme spécialisé qui exploite la structure de la grille régulière.

Composants techniques clés

1. Bornes d'erreur de discrétisation basées sur la grille (Section 2)

Le papier établit une nouvelle borne supérieure sur l'erreur d'approximation introduite par l'effondrement de la masse vers les centres de grille.

• Hypothèse : $P$ et $Q$ possèdent des densités $\alpha$-Höldériennes ($0 < \alpha < 1$) et sont bornées loin de zéro et de l'infini.
• Résultat : Les auteurs prouvent que $|W_2^2(G_h\#P, G_h\#Q) - W_2^2(P, Q)| \leq K h^{1+\alpha}$.
• Mécanisme : Contrairement aux arguments standards d'inégalité triangulaire qui donnent $O(h)$, ce résultat utilise un argument de couplage novateur basé sur la régularité de la carte de Brenier (la carte de transport optimal). En tirant parti des résultats récents de Collins et Tong [2025] concernant la continuité Höldérienne globale de la carte de Brenier, les auteurs montrent que les termes d'erreur du premier ordre s'annulent (similaire à une règle du point milieu), aboutissant à une borne plus serrée de $O(h^{1+\alpha})$.
• Cas non lisse : Pour les distributions sans hypothèses de régularité, la borne revient à $O(h)$, cohérente avec les arguments standards d'inégalité triangulaire.

2. Calcul exact efficace sur grilles régulières (Section 3)

Une fois les données brouillonisées sur une grille régulière, la structure du problème permet un calcul exact significativement plus rapide.

• Structure : Les mesures brouillonisées sont supportées sur une grille avec $L$ divisions par axe, où chaque atome a un poids qui est un multiple de $1/n$. Le coût de base (distance euclidienne au carré) est séparable selon les dimensions.
• Réduction : Les auteurs utilisent une réduction par Auricchio et al. [2018] pour transformer le problème de transport optimal entre des histogrammes $d$-dimensionnels avec des coûts séparables en un problème de flot à coût minimum sur un graphe $(d+1)$-partite.
• Algorithme : En mettant à l'échelle le problème pour garantir des demandes, des capacités et des coûts entiers, ils appliquent l'algorithme déterministe exact de flot à coût minimum de van den Brand et al. [2023].
• Complexité : Le calcul exact sur le brouillon s'exécute en temps $\tilde{O}(L^{d+1+o(1)})$.

3. Synthèse : L'algorithme CSR (Section 4)

L'algorithme final combine l'échantillonnage statistique, le brouillage sur grille et le solveur rapide.

• Taille de l'échantillon : Le nombre d'échantillons $n$ est choisi pour équilibrer l'erreur statistique et l'erreur de discrétisation, typiquement $n = \tilde{O}(\epsilon^{-\max(2, d/2)})$.
• Résolution de la grille : La taille de la grille est fixée à $L = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$.
• Temps d'exécution total : Le temps d'exécution combiné est dominé par l'étape du solveur, produisant un Temps d'Exécution Computationnel-Statistique de :
  $$\tilde{O}\left(\epsilon^{-\max\left(2, \frac{d+1+o(1)}{1+\alpha}\right)}\right)$$

Résultats clés et contributions

1. Temps d'exécution amélioré pour les distributions lisses

Le papier démontre que pour les distributions $\alpha$-Höldériennes lisses, le CSR peut être presque optimal, correspondant à la borne inférieure statistique de $\Omega(\epsilon^{-2})$ dans des régimes spécifiques :

• Dimension $d=2$ : Pour $\alpha > 1/2$, l'algorithme atteint $\tilde{O}(\epsilon^{-2})$. Cela correspond au taux statistique optimal, ce qui signifie que le coût computationnel ne dépasse pas le coût de la collecte d'échantillons suffisants.
• Dimension $d=3$ : Lorsque $\alpha \to 1$ (régularité Lipschitzienne), le temps d'exécution approche $\tilde{O}(\epsilon^{-2})$. Pour $0 < \alpha < 1$ général, le temps d'exécution est $\tilde{O}(\epsilon^{-\frac{4}{1+\alpha}})$.
• Dimension générale $d$ : Le temps d'exécution est $\tilde{O}(\epsilon^{-\max(2, \frac{d+1}{1+\alpha})})$.

2. Comparaison avec les travaux antérieurs

Les auteurs comparent leurs résultats aux méthodes existantes dans le Tableau 2 :

• Plug-in empirique + Lahn et al. [2019] : Atteint $\tilde{O}(\epsilon^{-4})$ en $d=2$ et $\tilde{O}(\epsilon^{-5})$ en $d=3$.
• OT entropique / Sinkhorn (Chizat et al. [2020]) : Atteint $\tilde{O}(\epsilon^{-6})$ en $d=2$ et $d=3$.
• Ce travail : Atteint $\tilde{O}(\epsilon^{-2})$ en $d=2$ (pour $\alpha > 1/2$) et $\tilde{O}(\epsilon^{-2})$ en $d=3$ (lorsque $\alpha \to 1$).

3. Cas non lisse

En l'absence d'hypothèses de régularité ($\alpha \to 0$), la méthode produit un CSR de $\tilde{O}(\epsilon^{-\max(2, d+1)})$. Pour $d=2$, cela donne $\tilde{O}(\epsilon^{-3})$, et pour $d=3$, c'est $\tilde{O}(\epsilon^{-4})$.

Importance et affirmations

Le papier affirme que sa contribution principale est le paradigme Échantillon-Brouillon-Résoudre, qui découple avec succès l'erreur d'estimation statistique de la complexité computationnelle du problème de transport.

• Compression sans erreur : Les auteurs montrent que la projection des échantillons sur une grille régulière compresse les données sans augmenter l'erreur asymptotique, à condition que les distributions sous-jacentes soient lisses.
• Régularisation pour la vitesse : La structure de la grille régularise le problème, permettant l'utilisation d'algorithmes de flot exacts rapides qui sont intraitables pour des ensembles de points discrets généraux.
• Optimalité : Le travail soutient que pour des distributions suffisamment lisses dans de faibles dimensions ($d=2, 3$), il est possible d'atteindre computationnellement le taux statistique optimal de $\epsilon^{-2}$. Cela remet en question l'idée que le calcul des distances de Wasserstein nécessite intrinsèquement un temps d'exécution super-linéaire ou super-quadratique par rapport à la précision souhaitée.

Les auteurs déclarent explicitement que leurs résultats reposent sur l'hypothèse que $P$ et $Q$ sont supportées sur un domaine borné (spécifiquement $(0, 1)^d$) et possèdent des densités Höldériennes lisses. Ils ne prétendent pas que ces résultats s'étendent aux distributions non lisses ou aux domaines non bornés sans modification. L'importance réside dans le fait de combler le fossé entre la théorie de l'estimation statistique et le transport optimal computationnel, démontrant que, sous des hypothèses de régularité réalistes, le « goulot d'étranglement computationnel » peut être efficacement éliminé.