Article

PDF
Access to the PDF text
Advertising


Free Article !

Comptes Rendus Mathématique
Volume 355, n° 7
pages 812-818 (juillet 2017)
Doi : 10.1016/j.crma.2017.05.010
Received : 19 February 2017 ;  accepted : 29 May 2017
Vers un théorème de la limite centrale dans l'espace de Wasserstein ?
Towards a central limit theorem in the Wasserstein space?
 

Martial Agueh a , Guillaume Carlier b, c
a University of Victoria, Victoria, BC, PO Box 3060 STN CSC Victoria, BC, V8W 3R4, Canada 
b Université Paris-Dauphine, PSL Research University, CNRS, CEREMADE, 75016 Paris, France 
c INRIA, Centre de Paris, équipe MOKAPLAN, France 

Résumé

Les barycentres dans l'espace de Wasserstein constituent une manière naturelle d'interpoler entre plusieurs mesures de probabillité, utile dans différents domaines appliqués comme le traitement d'images ou l'apprentissage statistique. Nous conjecturons que ces barycentres obéissent à un théorème de la limite centrale que nous démontrons dans quelques cas (très) particuliers.

The full text of this article is available in PDF format.
Abstract

The notion of Wasserstein barycenters is a natural way to interpolate between several probability measures, useful in various applied settings like image processing or machine learning. We conjecture that such barycenters obey a central limit theorem which we prove in some (very) particular cases.

The full text of this article is available in PDF format.
Abridged English version

The 2-Wasserstein space (on  ),   is by definition the space of Borel probability measures on   having finite second moments and endowed with the distance  
(1)W22(μ,ν):=inf⁡{∫Rd×Rd|x−y|2dγ(x,y),γ∈Π(μ,ν)},∀(μ,ν)∈P2(Rd)2 where   denotes the set of transport plans between μ and ν i.e. the set of probability measures on   having μ and ν as marginals. Given an integer N ,   elements of   and positive weights   with  , a Wasserstein barycenter of the measures   with weights   is a minimizer of(2)Jλ(μ):=∑i=1NλiW22(νi,μ). Wasserstein barycenters were introduced in a previous work [[1]], where it was observed that:

the minimizer is unique (its existence is obvious) as soon as one of the measures ν does not give mass to small sets (i.e. Borel sets of Hausdorff dimension at most  ), in this case, we may call this minimizer the Wasserstein barycenter of the measures   with weights  ,
if for some  , all the measures   are   (with respect to the Lebesgue measure) then so is their barycenter (this follows from a displacement convexity type argument in the spirit of McCann's seminal work [[11]]), this also holds for the limit case   and for  , it is enough that one of the measures   is  .
Wasserstein barycenters found various applications in statistics, image processing and machine learning, and there are fast solvers to compute them, see Cuturi [[5]] and Benamou et al. [[2]]. The concept of Wasserstein barycenter has been significantly extended by Bigot and Klein [[3]], Le Gouic and Loubes [[10]] to the case of a quite general Borel probability measure m on   and by Kim and Pass [[9]] to the Riemannian setting. A Wasserstein barycenter is then a minimizer of the Wasserstein variance functional:(3)Jm(μ):=∫P2(Rd)W22(ν,μ)dm(ν). The existence of a barycenter can easily be established by the direct method of the calculus of variations (see [[10]]) as soon as(4)∫P2(Rd)∫Rd|x|2dν(x)dm(ν)<+∞. Uniqueness also holds provided that m gives a strictly positive mass to the set of measures that vanish on small sets. We shall always make these assumptions and then define unambiguously:(5)bar(m):=argminP2(Rd)Jm. If, in addition, for some  , m is supported by   and(6)∫P2(Rd)‖ν‖Lp(Rd)pdm(ν)<+∞ the same convexity argument as in [[1]] gives that  . Of course, ((2)) is a special case of ((3)) corresponding to a discrete m :  , and if one of the measures   vanishes on small sets, the barycenter of this discrete measure will be denoted as:(7)bar(ν1,λ1…,νN,λN)=bar(∑i=1Nλiδνi):=argminP2(Rd)∑i=1NλiW22(νi,.).

Following Bigot and Klein [[3]], we are interested in the asymptotic behavior of empirical Wasserstein barycenters. More precisely, let us consider m a Borel probability measure m on   such that for some   and some  
(8)∫Rd|x|2dν(x)+∫Rdν(x)pdx≤C for m-a.e. ν. Considering an i.i.d. sample of (random) probability measures   drawn according to the probability measure m on  , the empirical Wasserstein barycenter of this sample is the random (a.s. well-defined since m gives full mass to measures that vanish on small sets) measure(9)μˆn:=bar(νˆ1,1n…,νˆn,1n). In the compactly supported case, Bigot and Klein [[3]] proved a law of large number, extended to a general setting by Le Gouic and Loubes [[10]], for the empirical barycenter:(10)limn→∞⁡W22(μˆn,μ¯)→0 a.s., where μ¯:=bar(m). Since, thanks to ((8)) both   and   have   densities, there exists a unique optimal transport map for   between the true barycenter   and the empirical barycenter  , we denote by   this map, which may be viewed as an  -valued random variable. Since  , thanks to ((8)) and to a simple convexity argument (see [[1]]), one has  . Thanks to ((10)) and Lebesgue's dominated convergence theorem, we thus have(11)‖Tˆn−id‖L2(μ¯)2→0 a.s. and E(‖Tˆn−id‖L2(μ¯)2)→0.

It is natural then to investigate whether one can go one step further in the convergence of empirical Wasserstein barycenters through some central limit theorem. The law of large numbers of Bigot and Klein gives that   converges a.s. to the identity map, we believe that an   estimate in   and asymptotic normality seem reasonable to conjecture for a wide class of measures m . Proving such a CLT even in the case of a discrete m seems a delicate issue, actually related to the regularity of solutions of an obstacle problem for a system of Monge–Ampère equations. Let us mention that a related question concerning the asymptotic distribution of the scalar quantity   and its use for statistical tests purposes has been considered in the recent works [[6]] and [[7]].

By definition, we will say that the Wasserstein CLT holds whenever   converges in distribution (in the separable Hilbert space  ) to a centered Gaussian   for a certain positive self-adjoint operator Σ of trace class on  . The following gives a positive answer in a few (very) particular cases.

Theorem 1

The Wasserstein CLT holds in the following cases:

(i)
  with  ,  ,   in   and   vanishing on small sets,
(ii)
 , m satisfies ((19)) and gives full mass to the set of non-atomic measures,
(iii)
  with each   a non-degenerate Gaussian on  .

Introduction

L'espace de Wasserstein (sur  ),   est par définition l'ensemble des mesures de probabilité sur  , de second moment fini, muni de la métrique   définie par le problème de transport optimal quadratique :
(12)W22(μ,ν):=inf⁡{∫Rd×Rd|x−y|2dγ(x,y),γ∈Π(μ,ν)},∀(μ,ν)∈P2(Rd)2 où   est l'ensemble des plans de transport entre μ et ν c'est-à-dire l'ensemble des mesures de probabilité sur   ayant μ et ν comme marginales (nous renvoyons aux livres de Villani [[13]] et Santambrogio [[12]] pour une présentation de la théorie du transport optimal). Soit N un entier plus grand que 1,   des éléments   et   des poids positifs normalisés par  , un barycentre dans l'espace de Wasserstein des mesures   avec les poids   est un minimiseur de(13)Jλ(μ):=∑i=1NλiW22(νi,μ). Cette notion a été introduite dans notre travail précédent [[1]], dans lequel nous avions observé que :

le minimiseur est unique (l'existence est quant à elle évidente) dès lors que l'une des mesures   ne charge pas les ensembles petits (i.e. les Boréliens de dimension de Hausdorff au plus  ) ; dans ce cas, on appelle ce minimiseur le barycentre dans l'espace de Wasserstein des mesures   avec les poids   ;
si toutes les mesures   sont dans   (par rapport à la mesure de Lebesgue) pour un certain  , alors il en est de même de leur barycentre (ceci découle d'un argument de type convexité par déplacement dans l'esprit du travail pionnier de McCann [[11]]), c'est encore valable pour le cas limite   et pour  , il suffit que l'une des mesures   (pour laquelle le poids   évidemment) soit dans  .

Indiquons quelques questions naturelles de régularité/stabilité dont la réponse n'est pas connue (même dans le cas un peu plus simple du tore plat) : 1) le barycentre dépend-il de manière lipschitzienne (pour  ) des poids   ? 2) le barycentre a-t-il une densité régulière (par exemple  ) si c'est le cas des mesures de départ  ... Les barycentres dans l'espace de Wasserstein sont relativement populaires dans différents contextes applicatifs comme le traitement d'images ou l'apprentissage statistique et peuvent se calculer numériquement efficacement – voir Cuturi [[5]] et Benamou et al. [[2]].

Dans cette note, nous conjecturons que, lorsque les mesures   sont des mesures tirées aléatoirement et de manière i.i.d. selon une certain loi de probabilité m sur   vérifiant des conditions adéquates, alors l'écart entre le vrai barycentre de la mesure m (voir paragraphe suivant) et le barycentre empirique obéit à un théorème de la limite centrale. Cela est un raffinement qui nous semble naturel d'un résultat de type loi des grands nombres de Bigot et Klein [[3]]. Nous précisons un peu les définitions dans le paragraphe suivant et établirons le théorème de la limite centrale au paragraphe 3 dans quelques cas très particuliers.

Barycentre empirique et vrai barycentre

La notion de barycentre dans l'espace de Wasserstein a été étendue de manière significative au cas d'une mesure borélienne m sur   assez générale par Bigot and Klein [[3]], Le Gouic et Loubes [[10]] dans le cas de   et par Kim et Pass [[9]] dans le cas de l'espace de Wasserstein sur une variété riemannienne. Un barycentre Wasserstein de m est alors un miniseur de la fonctionnelle de variance :
(14)Jm(μ):=∫P2(Rd)W22(ν,μ)dm(ν). L'existence d'un tel barycentre s'obtient aisément par la méthode directe du calcul des variations (voir notamment [[10]]) lorsque(15)∫P2(Rd)∫Rd|x|2dν(x)dm(ν)<+∞. L'unicité est quant à elle assurée dès que m donne une mesure positive aux mesures qui ne chargent pas les ensembles petits. Sous ces hypothèses, on peut donc définir sans ambiguité(16)bar(m):=argminP2(Rd)Jm. Si en plus, pour un  , m est portée par   et(17)∫P2(Rd)‖ν‖Lp(Rd)pdm(ν)<+∞ le même argument de convexité que dans [[1]] permet de déduire que  . Évidemment, ((13)) est un cas particulier de ((14)) correspondant à la mesure discrète  , et si l'une des mesures   (avec un poids strictement positif) ne charge pas les ensembles petits, on note alors :(18)bar(ν1,λ1…,νN,λN)=bar(∑i=1Nλiδνi):=argminP2(Rd)∑i=1NλiW22(νi,.).

Suivant Bigot et Klein [[3]], nous nous intéressons au comportement asymptotique des barycentres de Wasserstein empiriques . Plus précisément, considérons m une mesure de probabilité borélienne sur   telle qu'il existe   tel que
(19)∫Rd|x|2dν(x)≤C pour m-presque tout ν, et   tel que(20)∫Rdν(x)pdx≤C pour m-presque tout ν.

Considérons maintenant un échantillon i.i.d. de mesures aléatoires de probabilité   tirées selon m sur  . Le barycentre de Wasserstein empirique de cet échantillon est la mesure aléatoire (p.s. bien définie puisque m est portée par les mesures qui ne chargent pas les ensembles petits)
(21)μˆn:=bar(νˆ1,1n…,νˆn,1n). Bigot et Klein [[3]] ont établi, dans un cadre à support compact, une loi des grands nombres, étendue par Le Gouic et Loubes [[10]] à des cas beaucoup plus généraux, pour le barycentre Wasserstein empirique :(22)limn→∞⁡W22(μˆn,μ¯)→0 p.s., avec μ¯:=bar(m). Comme, grâce à ((20)) à la fois   et   sont  , il existe un unique transport optimal (voir [[4], [12], [13]]) pour   entre le vrai barycentre   et le barycentre empirique  , notons   ce transport optimal que l'on doit comprendre comme une variable aléatoire prenant ses valeurs dans l'espace de Hilbert séparable  . On a  , avec ((19)) et un argument simple de convexité (voir [[1]]), on a  , de sorte qu'avec ((22)) et le théorème de convergence dominée de Lebesgue, on a(23)‖Tˆn−id‖L2(μ¯)2→0 p.s. et E(‖Tˆn−id‖L2(μ¯)2)→0. Il est alors naturel de chercher à aller un ordre plus lointain dans la convergence au travers d'un théorème de la limite centrale. La loi des grands nombres de Bigot et Klein énonçant que   converge p.s. et en moyenne quadratique vers l'identié dans  , il semble raisonnable de conjecturer une vitesse de convergence en   et une normalité aymptotique de  , au moins pour certaines classes de mesures m . Une stratégie naturelle consiste à essayer de dériver les conditions d'optimalité par rapport à la mesure pour appliquer un théorème d'inversion locale. Cela semble néanmoins délicat, même dans le cas d'une mesure m discrète, car la condition d'optimalité caractérisant le barycentre prend la forme d'un problème d'obstacle pour un système d'équations de Monge–Ampère, l'aspect frontière libre du problème compliquant significativement l'analyse... Mentionnons une question reliée qui a fait l'objet de travaux récents en statistiques [[6], [7]] et qui concerne l'identification de la distribution asymptotique de la quantité scalaire   afin de construire des test d'hypothèse ou d'adéquation.

Par définition, nous dirons que le TLC dans l'espace de Wasserstein est satisfait si   converge en loi (dans le Hilbert séparable  ) vers une mesure gaussienne centrée   pour un certain opérateur auto-adjoint positif de trace finie Σ sur  . On donne au paragraphe suivant quelques exemples très particuliers de validité de ce TLC au sens Wasserstein.

Quelques cas de validité du TLC Wasserstein

Théorème 3.1

Le TLC dans l'espace de Wasserstein est satisfait dans les cas suivants :

(i)
lorsque m est une loi de Bernoulli,   avec  ,  ,   dans   et   ne chargeant pas les ensembles petits,
(ii)
lorsque   et que m est portée par les mesures non atomiques et vérifie ((19)),
(iii)
lorsque   où chaque   est une gaussienne non dégénérée.

Proof

(i) Pour deux mesures,   et   comme dans l'énoncé, la notion de barycentre est étroitement liée à celle de géodésique ou interpolante de McCann entre   et  , le transport optimal de Brenier   entre   et   dérive d'un potentiel convexe ϕ (dont le gradient est défini de manière unique  -presque partout),  , pour  , le barycentre de   coïncide avec l'interpolation de McCann (voir [[1], [11]]) :
ν(t):=bar((1−t)δν0+tδν1)=∇ϕt#ν0 avec ϕt:=(1−t)12|x|2+tϕ (observer que   a pour inverse   qui est Lipschitz dès que  ). Par ailleurs, il est facile de voir que le transport optimal entre deux points   et   de la géodésique, avec s , t dans   et   est donné parTν(s)→ν(t)=id+t−s1−s(∇ϕ∘∇ϕs⁎−id). En particulier, le transport optimal   entre   et le barycentre emprique   (ici   désigne la fréquence empirique d'apparition de   dans l'échantillon  ) satisfaitn(Tˆn−id)=n(λˆn−λ)(1−λ)(∇ϕ∘∇ϕλ⁎−id) et on conclut avec le TLC standard pour  .

(ii) En dimension 1, le barycentre d'une mesure m portée par les mesures non atomiques est non atomique et donné par la formule explicite (voir par exemple [[1]])
(24)bar(m):=(∫P2(R)Tρ→νdm(ν))#ρ, où ρ est n'importe quelle mesure non atomique et   l'unique transport croissant de ρ vers ν . En prenant   et en appliquant la formule précédente au barycentre empirique  , il vient que le transport optimal (i.e. croissant) de   vers   est(25)Tˆn:=1n∑i=1nTbar(m)→νˆi et comme les variables aléatoires à valeurs dans  ,   sont i.i.d. et de carré intégrable par ((19)), le TLC usuel dans les espaces de Hilbert séparables (voir [[8]]) permet de conclure.

(iii) Sans perte de généralité, nous supposerons que les   sont des gaussiennes centrées et notons   leur matrice de variance covariance (  et   appartiennent à   le cône des matrices   symétriques, définies positives, on note par ailleurs   l'espace des matrices symétriques et   le cône des matrices   symétriques, semi-définies positives). Le point important ici est que si   alors   est elle-même une gaussienne centrée dont la matrice de variance-covariance   est l'unique racine dans   de l'équation matricielle (cf. [[1]]) :
(26)I=∑i=1NαiΦi(S) où Φi(S):=Ki(KiSKi)−12Ki. En vertu du Lemme 3.2 ci-dessous, l'application   est  . Le vrai barycentre   est la mesure gaussienne centrée de variance-covariance   tandis que le barycentre empirique   est la mesure gaussienne centrée de variance-covariance   où   est le vecteur des fréquences empiriques :(27)(λˆn)i=1n#{j=1…,n:νˆj=νi},i=1,…,N. Le TLC implique que   converge en loi vers   ( ). Il est bien connu que le transport optimal entre les gaussiennes centrées de variance covariance   et   est linéaire et explicitement donné en fonction de   parT(λˆ)=S(λˆ)12(S(λˆ)12S(λ)S(λˆ)12)−12S(λˆ)12 c'est encore une application   de   dans   et évidemment  . Avec une inégalité d'accroissements finis, il vientTˆn=T(λˆn)=id+T′(λ)(λˆn−λ)+εn,|εn|≤|λˆn−λ|supθ∈[λ,λˆn]⁡|T′(θ)−T′(λ)|, de sorte quen(Tˆn−id)=T′(λ)n(λˆn−λ)+nεn ce qui par des arguments classiques (la méthode delta ) permet aisément de conclure que   converge en loi vers une distribution gaussienne centrée et de variance–covariance  .  □

Nous avons utilisé ci-dessus le résultat suivant

Lemme 3.2

L'application   définie implicitement par l'équation ((26)) est de classe  .

Proof

Grâce au théorème des fonctions implicites, il suffit de montrer que pour  ,   est inversible. Pour  ,   est la solution unique de
(28)−Ki−1S−1θS−1Ki−1=(KiSKi)−12Ki−1LiKi−1+Ki−1LiKi−1(KiSKi)−12. DéfinissantL˜i:=Ki−1LiKi−1,S˜i:=KiSKi,θ˜i:=KiθKi, il est commode de réécrire ((28)) sous la forme plus concise(29)−S˜i−1θ˜iS˜i−1=S˜i−12L˜i+L˜iS˜i−12. Supposons que   soit dans le noyau de   i.e.  , il vient donc avec ((29)) et quelques manipulations élémentaires(30)0=∑i=1NαiTr(Liθ)=∑i=1NαiTr(L˜iθ˜i)=−2∑i=1NαiTr(S˜i12L˜iS˜i12L˜iS˜i12) et comme  , chaque terme de cette somme est nul, de sorte que, pour  , comme  , on a   et donc  , si bien que  , ce qui montre l'inversibilité cherchée.  □

Note :

Cette note a été rédigée après la disparition soudaine du premier auteur, Martial Agueh ; le second auteur tient à la dédier à sa mémoire.

Références

Agueh M., Carlier G. Barycenters in the Wasserstein space SIAM J. Math. Anal. 2011 ;  43 (2) : 904-924 [cross-ref]
Benamou J.-D., Carlier G., Cuturi M., Nenna L., Peyré G. Iterative Bregman projections for regularized transportation problems SIAM J. Sci. Comput. 2015 ;  37 (2) : 1111-1138
Bigot J., Klein T. Characterization of barycenters in the Wasserstein space by averaging optimal transport mapspreprint. 1212.25622012
Brenier Y. Polar factorization and monotone. Rearrangement of vector-valued functions Commun. Pure Appl. Anal. 1991 ;  44 (4) : 375-417 [cross-ref]
M. Cuturi, A. Doucet, Fast computation of Wasserstein barycenters, in: Proceedings of the 31st International Conference on Machine Learning (ICML-14), Beijing, China, 21–26 June 2014, pp. 685–693.
Del Barrio E., Lescornel H., Loubes J.-M. A statistical analysis of a deformation model with Wasserstein barycenters: estimation procedure and goodness of fit testpreprint. 1508.064652015
Ebert J., Spokoiny V., Suvorikova A. Construction of non-asymptotic confidence sets in 2-Wasserstein spacepreprint. 1703.036582017
Giné E., Leòn J.-R. On the central limit theorem in Hilbert space Stochastica 1980 ;  4 (1) : 43-71
Kim Y.-H., Pass B. Wasserstein Barycenters over Riemannian manifolds Adv. Math. 2017 ;  307 : 640-683 [cross-ref]
Le Gouic T., Loubes J.-M. Existence and consistency of Wasserstein barycenters Probab. Theory Relat. Fields 2016 ; 1-17
McCann R.-J. A convexity principle for interacting gases Adv. Math. 1997 ;  128 : 153-179 [cross-ref]
Santambrogio F. Optimal Transport for Applied Mathematicians  : Birkhäuser (2015). 
Villani C. Topics in Optimal Transportation  : American Mathematical Society (2003). 



© 2017  Académie des sciences@@#104156@@
EM-CONSULTE.COM is registrered at the CNIL, déclaration n° 1286925.
As per the Law relating to information storage and personal integrity, you have the right to oppose (art 26 of that law), access (art 34 of that law) and rectify (art 36 of that law) your personal data. You may thus request that your data, should it be inaccurate, incomplete, unclear, outdated, not be used or stored, be corrected, clarified, updated or deleted.
Personal information regarding our website's visitors, including their identity, is confidential.
The owners of this website hereby guarantee to respect the legal confidentiality conditions, applicable in France, and not to disclose this data to third parties.
Close
Article Outline