## Fast convergence of empirical barycenters in Alexandrov spaces and the Wasserstein space

Thibaut Le Gouic, Quentin Paris, Philippe Rigollet and Austin J. Stromme

Abstract. This work establishes fast, i.e., parametric, rates of convergence for empirical barycenters over a large class of geodesic spaces with curvature bounds in the sense of Alexandrov. More specifically, we show that parametric rates of convergence are achievable under natural conditions that characterize the bi-extendibility of geodesics emanating from a barycenter. These results largely advance the state-of-the-art on the subject both in terms of rates of convergence and the variety of spaces covered. In particular, our results apply to infinite-dimensional spaces such as the 2-Wasserstein space, where bi-extendibility of geodesics translates into regularity of Kantorovich potentials.

## 1. INTRODUCTION

The notion of average is paramount across all of statistics. It is fundamental not only in theory but also in practice as it arises in nearly every known estimation method: the method of moments, empirical risk minimization, and more. The law of large numbers, sometimes dubbed the fundamental law of statistics, ensures that the average of independent and identically distributed random variables converges to their common expected value. While such results guarantee asymptotic validity of the average, modern statistics and machine learning focuses on non-asymptotic performance guarantees that hold for every sample size. The goal of this paper is to provide such non-asymptotic guarantees for a generalized notion of average over metric spaces with the Wasserstein space as a prime example.

To illustrate our goal more precisely, consider the following example. Let X,X ,... , X 1 n be i.i.d. (independent and identically distributed) copies of X in a vector space equipped with a distance d . Denote by E [ X ] and ¯ X the expectation of X and the average of the X i 's respectively. In many instances, ¯ X converges to E [ X ] at a dimension-independent and parametric rate . Such convergence is characterized by the following inequality:

$$\mathbb { E } [ d ^ { 2 } ( \bar { X }, \mathbb { E } [ X ] ) ] \leq \frac { c \sigma ^ { 2 } } { n } \,,$$

where c &gt; 0 and σ 2 = E [ d 2 ( X, E [ X ])] denotes the variance of X . When the underlying space is a Hilbert space, and d is the natural Hilbert metric, this inequality is in fact an equality with c = 1. More generally, the bound (1.1) holds in a Banach space if and only if it is of type 2 [LT91], which is a property linked to the geometry of the Banach space [Kwa72].

Using a predominantly geometric approach, we tackle the question of extending these statistical guarantees to metric spaces that are devoid of a linear structure. In recent years, this problem has gone from a theoretical curiosity to a practical necessity. Indeed, data such as images, shapes, networks, point clouds and even distributions are now routinely collected and come with the need for new statistical methods with strong performance guarantees.

## 1.1 Barycenters

The barycenter is a natural extension of the notion of expectation on an abstract metric space which we recall next. Let ( S, d ) be a metric space and P 2 ( S ) be the set of (Borel) probability measures P on S such that, the variance functional defined by

↦

$$b \mapsto \int d ^ { 2 } ( b, x ) d P ( x )$$

is finite on S . For P ∈ P 2 ( S ), a barycenter of P is any b /star ∈ S such that

$$b ^ { * } \in \underset { b \in S } { \arg \min } \int d ^ { 2 } ( b, x ) \mathrm d P ( x ).$$

Throughout, we always implicitly assume the existence of at least one barycenter. The question of existence has been largely addressed in the literature and shown to hold in most reasonable scenarios [Afs11,LGL17].

Letting X ,. . . , X 1 n be n random variables drawn independently from P , an empirical barycenter , is defined as a barycenter of the empirical distribution P n = (1 /n ) ∑ n i =1 δ X i , i.e.,

$$b _ { n } \in \underset { b \in S } { \arg \min } \, \frac { 1 } { n } \sum _ { i = 1 } ^ { n } d ^ { 2 } ( b, X _ { i } ) \,.$$

The main motivation for this work is to study the statistical behavior of empirical barycenters in the context where ( S, d ) is the 2-Wasserstein space of probability measures over R D that is defined by S = P 2 ( R D ) equipped with the 2-Wasserstein metric.

The Wasserstein space has recently played a central role in many applications including machine learning [ACB17, GPC18], computer graphics [SdGP + 15, FCVP17], statistics [RW18, PZ19] and computational biology [SST + 19].

Barycenters in this setting are called Wasserstein barycenters and were first studied in [AC11] who derive a dual formulation of the associated optimization problem and establish regularity properties of the solution. Despite computational advances [CD14,SCSJ17] and asymptotic consistency results [AC17,LGL17,ZP19], little is known about the rates of convergence of barycenters on Wasserstein spaces, let alone general metric spaces. Initial contributions have focused on the Wasserstein space over the real line which is isometric to a convex subset of a Hilbert space [AC17] or finite dimensional subspaces of the Wasserstein space [KSS19,CMRS20]. The study of rates of convergence of Wasserstein barycenters in the general case was triggered in [ALP18], where the truly geometric nature of the question was first brought forward. However, the rates obtained in that paper suffer from the curse of dimensionality: the rate n -1 in (1.1) is replaced with n -1 /D , whenever the probability distributions are defined on R D , D ≥ 3 and their techniques yield the suboptimal rate n -2 3 / in the flat case D = 1.

In this work, we aim to improve these results to optimality. To that end, we adopt a general framework and establish dimension-independent and parametric rates for empirical barycenters, of the form (1.1), for a large family of geodesic metric spaces with curvature bounds in the sense of Alexandrov. In particular these spaces need not be finite-dimensional. More specifically, our results apply to geodesic spaces with positive curvature under a compelling synthetic geometric condition: the bi-extendibility of all geodesics emanating from a barycenter.

The 2-Wasserstein space over R D is itself a geodesic space with positive curvature [AGS05] and parametric rates for this case follow as a simple consequence of our general result. In addition, we show that the bi-extendibility condition translates into simple regularity conditions on the Kantorovich potentials.

We end by mentioning references related to our work. General properties of barycenters in metric spaces with bounded curvature are studied in [Stu03,Oht12,Yok16] and [Yok17]. Specific examples of spaces with negative curvature are studied in [HHL + 13]. The asymptotic properties of empirical barycenters, in the case where S is a Riemannian manifold, are addressed in [BP03, BP05] and [KL11]. The statistical properties of empirical barycenters in abstract metric spaces have only been considered in [Sch18] (for the case of negatively curved spaces) and [ALP18].

## 1.2 Overview of main results

Our results rely on the notion of extendible geodesics . For λ in , λ out &gt; 0 we say that a constantspeed geodesic γ : [0 , 1] → S is ( λ in , λ out )-extendible if there exists a constant-speed geodesic γ + : [ -λ in , 1 + λ out ] → S such that γ is the restriction of γ + to [0 , 1]. We now state our main result and refer the reader to Section 3 for omitted definitions. The variance σ 2 of a distribution P ∈ P 2 ( S ) is given by

$$\sigma ^ { 2 } = \inf _ { b \in S } \int d ^ { 2 } ( b, x ) \mathrm d P ( x ) = \int d ^ { 2 } ( b ^ { * }, x ) \mathrm d P ( x ) \,,$$

where b /star is a barycenter of P .

Our main theorem is stated below informally and follows directly from Theorems 10 and 14.

Theorem 1 (Main theorem, informal) . Let ( S, d ) be a geodesic space of nonnegative curvature. Let P ∈ P 2 ( S ) be such that, for any x in the support of P , there exist a geodesic from b /star to x that is ( λ in , λ out ) -extendible. Define

$$k \coloneqq \frac { \lambda _ { \text{out} } } { 1 + \lambda _ { \text{out} } } - \frac { 1 } { \lambda _ { \text{in} } } \,.$$

Then if k &gt; 0 , b /star is unique and for any empirical barycenter b n , we have

$$\mathbb { E } [ d ^ { 2 } ( b _ { n }, b ^ { * } ) ] \leq \frac { 4 \sigma ^ { 2 } } { k n } \,.$$

Note that the constant k is a geometric characteristic of the metric measure space ( S, d, P ). Since the seminal work of Cheeger and Colding [CC96,CC97,CC00a,CC00b], and culminating with the Lott-Sturm-Villani theory of Ricci curvature lower bounds for geodesic spaces [Stu06a,Stu06b,LV09], such triples are central to modern geometry.

To illustrate the meaning of the condition k &gt; 0, consider the canonical example of the Euclidean unit sphere (in any dimension). In this setup, the ( λ in , λ out )-extendibility imposes that, for all x in the support of P ,

$$d ( b ^ { * }, x ) ( 1 + \lambda _ { \text{in} } + \lambda _ { \text{out} } ) \leq \pi$$

In addition, condition k &gt; 0 requires that

$$1 + \lambda _ { \text{in} } + \lambda _ { \text{out} } \geq 2 + \lambda _ { \text{out} } + \frac { 1 } { \lambda _ { \text{out} } } \geq 4,$$

so that the support of P is necessarily contained in the spherical ball of center b ∗ and radius π/ 4. This bound aligns with known results, on the sphere, stating that we cannot hope for 1 /n rates when mass is allowed to accumulate around a point antipodal to b /star [EH19]. The above theorem thus requires stringent conditions on the support of P that can be largely relaxed using a local notion of extendibility where λ in and λ out may depend on x and k is only required to be positive on average (see Theorem 12).

It is known that extendibility of geodesics in the 2-Wasserstein space is related to the regularity of Kantorovich potentials [ALP18]. In this case, we get the following corollary.

Corollary 2 . Let P ∈ P 2 ( P 2 ( R D )) be a probability measure on the 2-Wasserstein space and let µ /star ∈ P 2 ( R D ) be a barycenter of P . Let α, β &gt; 0 and suppose that every µ ∈ supp( P ) is the pushforward of µ /star by the gradient of an α -strongly convex and β -smooth function ϕ µ /star → µ , i.e., µ = ( ∇ ϕ µ /star → µ ) # µ /star . Then, if β -α &lt; 1 , µ /star is unique and any empirical barycenter µ n of P satisfies

$$\mathbb { E } W _ { 2 } ^ { 2 } ( \mu _ { n }, \mu ^ { * } ) & \leq \frac { 4 \sigma ^ { 2 } } { ( 1 - \beta + \alpha ) n }. \\ \cdots \cdots \cdots.$$

While our results are resolutely focused on spaces with nonnegative curvature, we obtain the following strong result about spaces of nonpositive curvature as a byproduct of the techniques developed in this paper.

Theorem 3 . Suppose ( S, d ) is a geodesic space satisfying κ ≤ curv( S ) ≤ 0 for some κ ≤ 0 . Then, any distribution P ∈ P 2 ( S ) has a unique barycenter b /star and any empirical barycenter b n satisfies

$$\mathbb { E } d ^ { 2 } ( b _ { n }, b ^ { * } ) \leq \frac { \sigma ^ { 2 } } { n }.$$

The above parametric rate should be contrasted with the slower rates obtained in [ALP18] and [Sch18] but that hold without curvature lower bounds.

## 2. GEOMETRY AND BARYCENTERS

## 2.1 Preliminaries

We gather important notation and standard facts from metric geometry for reference. We refer the reader to [BBI01] and [AKP19] for an introduction.

Throughout, let ( S, d ) be a (Polish) geodesic metric space (see Remark 6). For all x, y ∈ S , we call (constant-speed) geodesic connecting x to y any continuous path γ : [ a, b ] → S such that γ a ( ) = x , γ b ( ) = y and such that, for all a ≤ s ≤ t ≤ b ,

$$d ( \gamma ( s ), \gamma ( t ) ) = \frac { t - s } { b - a } d ( x, y ). \\ 2 \cdots \cdots = \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots - \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots+ \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots += \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots + \cdots$$

Given κ ∈ R , we denote by ( M ,d 2 κ κ ) the complete and simply connected 2-dimensional Riemannian manifold with constant sectional curvature κ . The diameter D κ of M 2 κ is D κ = + ∞ if κ ≤ 0 and

D κ = π/ √ κ if κ &gt; 0. We define a triangle in S as any set of three points { p, x, y } ⊂ S . For κ ∈ R , a comparison triangle for { p, x, y } ⊂ S in M 2 κ is an isometric embedding { ¯ ¯ p, x, y ¯ } ⊂ M 2 κ of { p, x, y } in M 2 κ . Such a comparison triangle always exists and is unique (up to an isometry) provided peri { p, x, y } = d p, x ( ) + d p, y ( ) + d x, y ( ) &lt; 2 D κ . We recall the definition of curvature bounds for reference.

Definition 4 . Let κ ∈ R . We say that curv( S ) ≥ κ if for any triangle { p, x, y } ⊂ S with peri { p, x, y } &lt; 2 D κ , any comparison triangle { ¯ ¯ p, x, y ¯ } ⊂ M 2 κ and any geodesic γ : [0 , 1] → S connecting x to y in S , we have

$$d ( p, \gamma ( t ) ) & \geq d _ { \kappa } ( \bar { p }, \bar { \gamma } ( t ) ), & \quad \quad \quad ( 2. 1 ) \\ \sim \pi ^ { 1 } \cdots \epsilon ^ { 2 } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon$$

for all t ∈ [0 , 1] , where ¯ : [0 γ , 1] → M 2 κ is the unique geodesic connecting ¯ x to ¯ y in M 2 κ . We say that curv( S ) ≤ κ if the same holds with converse inequality in (2.1) .

Comparison angles allow to provide useful characterisations of curvature bounds. Given p, x, y ∈ S with p / ∈ { x, y } and peri { p, x, y } &lt; D 2 κ , we define the comparison angle /sphericalangle κ p ( x, y ) ∈ [0 , π ] at p by

/negationslash where, for r ≥ 0,

$$\tilde { \lambda } _ { p } ( x, y ) \coloneqq & \begin{cases} \frac { d ^ { 2 } ( p, x ) + d ^ { 2 } ( p, y ) - d ^ { 2 } ( x, y ) } { 2 d ( p, x ) d ( p, y ) } & \text{if $\kappa=0$}, \\ \frac { c _ { \kappa } ( d ( x, y ) ) - c _ { \kappa } ( d ( p, x ) ) \cdot c _ { \kappa } ( d ( p, y ) ) } { \kappa \cdot s _ { \kappa } ( d ( p, x ) ) s _ { \kappa } ( d ( p, y ) ) } & \text{if $\kappa\neq 0$}, \\ \intertext { r e, for } r \geq 0, & \int \sin ( r \sqrt { \kappa } \, / \sqrt { \kappa } \quad \text{if $\kappa>0$}. \end{cases}$$

$$& \mathcal { \Lambda }, & s _ { \kappa } ( r ) \coloneqq \begin{cases} \sin ( r \sqrt { \kappa } ) / \sqrt { \kappa } & \text{if $\kappa>0$,} \\ \sinh ( r \sqrt { - \kappa } ) / \sqrt { - \kappa } & \text{if $\kappa<0$,} \end{cases} \\ & r \mathcal { \Lambda }$$

and c κ ( r ) = s ′ κ ( r ).

The next result can be found in [BGP92].

Theorem 5 . Let ( S, d ) be a geodesic space and κ ∈ R . Then the following statements are equivalent.

- (1) curv( S ) ≥ κ in the sense of Definition 4.
- (2) For all p, x, y, z ∈ S such that p / ∈ { x, y, z } ,

$$\lhd _ { p } ^ { \kappa } ( x, y ) + \lhd _ { p } ^ { \kappa } ( x, z ) + \lhd _ { p } ^ { \kappa } ( y, z ) \leq 2 \pi.$$

- (3) For any p, x, y ∈ S with p / ∈ { x, y } any geodesics γ , γ x y : [0 , 1] → S from p to x and from p to y respectively, the function

$$( s, t ) \mapsto \lhd _ { p } ^ { \kappa } ( \gamma _ { x } ( s ), \gamma _ { y } ( t ) ), \\ \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \eta \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \p \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \nu \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \nolimits$$

↦

is non-increasing in each variable when the other is fixed.

Tangent cones are fundamental objects around which revolve many ideas of the paper. While they reduce to more familiar tangent spaces when S is a smooth manifold, tangent cones provide a natural proxy for tangent spaces in the context of abstract metric structures. Given p ∈ S , let Γ p be the set of all geodesics γ : [0 , 1] → S with γ (0) = p . For γ, σ ∈ Γ , the p Alexandrov angle /sphericalangle p ( γ, σ ) is given by

$$\lhd _ { p } ( \gamma, \sigma ) = \lim _ { s, t \rightarrow 0 } \lhd _ { p } ^ { 0 } ( \gamma ( s ), \sigma ( t ) ).$$

Whenever curv( S ) ≥ κ or curv( S ) ≤ κ , for κ ∈ R , the angle /sphericalangle p : Γ 2 p → [0 , π ] exists and is a pseudometric on Γ . Hence, it induces a metric, still denoted p /sphericalangle p , on the quotient space Γ p / ∼ where γ ∼ σ if and only if /sphericalangle p ( γ, σ ) = 0. The completion (Σ p , /sphericalangle p ) of (Γ p / ∼ , /sphericalangle p ) is called the space of directions at p . The tangent cone T S p of ( S, d ) at p is the Euclidean cone over the space of directions Σ p , i.e., the quotient space Σ p × R + / ≈ where ( γ, s ) ≈ ( σ, t ) if and only if s = t = 0 or ( γ, s ) = ( σ, t ). For ( γ, s ) ∈ Σ p × R + , we denote [ γ, s ] the corresponding element in T S p and we call o p = [ γ, 0] the tip of the cone. For all u = [ γ, s , v ] = [ σ, t ] ∈ T S p , we set 1

$$\| u - v \| _ { p } ^ { 2 } = s ^ { 2 } + t ^ { 2 } - 2 s t \cos \lhd _ { p } ( \gamma, \sigma ).$$

We also use notation ‖ u ‖ p = ‖ u -o p ‖ p and 〈 u, v 〉 p = st cos /sphericalangle p ( γ, σ ) so that

$$\| u - v \| _ { p } ^ { 2 } = \| u \| _ { p } ^ { 2 } + \| v \| _ { p } ^ { 2 } - 2 \langle u, v \rangle _ { p } \,.$$

↦

Let C p ⊂ S denote the cut-locus of p and for all x ∈ S \ C p , let ↑ ∈ x p Σ p denote the direction of the unique geodesic connecting p to x . Then, the log map at p is the map from S \ C p to T S p that is defined by

The map ( u, v ) →‖ - ‖ u v p is a metric on T S p called the cone metric . The cone structure of T S p is defined, for u = [ γ, s ] and λ ≥ 0, by λ · u = [ γ, λs ].

$$\log _ { p } & ( x ) = [ \uparrow _ { p } ^ { x }, d ( p, x ) ] \,. \\ \cdot \,. \quad \sim \,. \quad \cdot \,. \quad.$$

This definition can be extended to x ∈ C p by selecting an arbitrary direction from p to x .

Remark 6 . In the rest of this paper, we integrate functionals of the log map and now comment on its measurability. Note first that the map log p : S → T S p can be chosen to be measurable whenever the tangent cone T S p is equipped with the σ -algebra S B generated by the closed balls. This observation follows from a straightforward adaptation of Lemmas 3.3 and 4.2 in [Oht12] and implies Borel-measurability of the log map if the tangent cone T S p is separable, since, in that case, S B coincides with the Borel σ -algebra.

In particular, when S = P 2 ( X ) is the 2 -Wasserstein space over a separable space X , this condition follows from the characterization of T p P 2 ( X ) in [AGS05, Section 12.4]. It is unclear whether general conditions on S imply separability of the tangent cone-in fact, this question was raised in [Oht12] in the case where S is proper-or even Borel-measurability of the log map. Fortunately, it can be checked that our arguments require Borel measurability not of log p itself, but only of maps of the form 〈 log p ( ) · , b 〉 p for some b ∈ T S p , which, in turn, follows from the S B -measurability of log p .

A useful consequence of the monotonicity property, Theorem 5 point (3), is the following. If curv( S ) ≥ 0 (resp ≤ 0), then for any x, y, p ∈ S the metric d and cone metric ‖ · - · ‖ p satisfy

$$d ( x, y ) \leq \| \log _ { p } ( x ) - \log _ { p } ( y ) \| _ { p }, \quad ( \text{resp.} \, \geq ),$$

with equality if x = p or y = p .

1 Observe that we often denote paths and directions by the same letters. For any two directions γ, σ ∈ Σ , the angle p /sphericalangle p ( γ, σ ) is defined without ambiguity as the Alexandrov angle between any two representatives of these directions.

## 2.2 Tangent cone at a barycenter

The notation ‖ · ‖ p and 〈· , ·〉 p suggests that the cone T S p possesses a Hilbert-like structure. However, the tangent cone may fail to be even geodesic whenever S has only lower bounded curvature (see [Hal00]). To overcome this limitation, we gather facts on the structure of T S p , that are used in the sequel, in particular when p is a barycenter.

Theorem 7 . Let κ ∈ R and let ( S, d ) be a geodesic space with curv( S ) ≥ κ . Then the following holds:

- (1) For any p ∈ S , the tangent cone T S p can be isometrically embedded in a geodesic space T p S , such that curv( T p S ) ≥ 0 .
- (2) For any P ∈ P 2 ( S ) and any barycenter b /star ∈ S of P ,

$$\iint \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( y ) \rangle _ { b ^ { * } } \mathrm d P ( x ) \mathrm d P ( y ) = 0.$$

- (3) For any P ∈ P 2 ( S ) and any barycenter b /star of P , there exists a subset L b /star S ⊂ T b /star S , which is a Hilbert space when equipped with the restricted cone metric, and such that log b /star (supp( P )) ⊂ L b /star S .

$$\omega \omega _ { \omega } \\ \int \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( b ) \rangle _ { b ^ { * } } \mathrm d Q ( x ) = \langle u, \log _ { b ^ { * } } ( b ) \rangle _ { b ^ { * } },$$

- (4) For any P ∈ P 2 ( S ) , any barycenter b /star of P , any Q ∈ P 2 ( S ) with log b /star (supp( Q )) ⊂ L b /star S and any b ∈ S , we have

where u is the (Pettis) integral ∫ v d ¯ ( Q v , Q ) ¯ = (log b /star ) # Q .

Proof. (1) This statement follows directly by combining Claim 3.3.2, Theorem 3.4.1 and Theorem 11.3.1 in [AKP19]. Note that T p S is formally described as the ultralimit of blowups of S at point p and called the ultratangent cone.

- (2) Let X ,. . . , X 1 n be i.i.d. with distribution P and let P n = n -1 ∑ n i =1 δ X i . Let f : S 2 → R be defined by f ( x, y ) = 〈 log b /star ( x , ) log b /star ( y ) 〉 b /star and observe that f ∈ L 2 ( P ⊗ P ). Moreover, explicit computations show that

$$\mathbb { E } | ( P \otimes P ) f - ( P _ { n } \otimes P _ { n } ) f | ^ { 2 } \underset { n \rightarrow + \infty } { \longrightarrow } 0,$$

so that there exists a subsequence ( P n k ) such that ( P n k ⊗ P n k ) f converges almost surely to ( P ⊗ P f ) . Since P n k is finitely supported, it follows from [LS97, Proposition 3.2] that ( P n k ⊗ P n k ) f ≥ 0. Therefore, ( P ⊗ P f ) ≥ 0. Note that this first inequality holds even when b /star is not a barycenter.

To complete the proof, we prove the reverse inequality.

Without loss of generality, suppose that κ &lt; 0. Then, combining claim 1.1.1.d and Lemma 5.3.1 in [AKP19], we deduce there exists a constant c &gt; 0 (depending only on κ ) such that, for all x, y ∈ S ,

$$\lhd _ { b ^ { * } } ^ { \kappa } ( x, y ) \leq \lhd _ { b ^ { * } } ^ { 0 } ( x, y ) \leq \lhd _ { b ^ { * } } ^ { \kappa } ( x, y ) + c d ( b ^ { * }, x ) d ( b ^ { * }, y ).$$

Now for all x, y ∈ S , let γ x and γ y be two geodesics connecting b /star to x and y respectively and with

respective directions ↑ x b /star and ↑ y b /star . Then, letting 〈 x, y 〉 0 b /star = d b , x d b ( /star ) ( /star , y ) cos /sphericalangle 0 b /star ( x, y ), we get

$$\text{ive directions } \uparrow _ { b } ^ { * } \text{ and } \uparrow _ { b } ^ { * } \text{$\Psi$}, \text{$\text{in}$, letting } \langle x, y \rangle _ { b } ^ { * } = d ( b ^ { * }, x ) d ( b ^ { * }, y ) \cos < _ { b } ^ { * } ( x, y ), \text{ we get} \\ \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( y ) \rangle _ { b ^ { * } } & = d ( b ^ { * }, x ) d ( b ^ { * }, y ) \cos < _ { b ^ { * } } ( \uparrow _ { b ^ { * } } ^ { x }, \uparrow _ { b ^ { * } } ^ { y } ) \\ & = \lim _ { s, t \rightarrow 0 } d ( b ^ { * }, x ) d ( b ^ { * }, y ) \cos < _ { b ^ { * } } ^ { * } ( \gamma _ { x } ( s ), \gamma _ { y } ( t ) ) \\ & \leq \lim _ { s, t \rightarrow 0 } d ( b ^ { * }, x ) d ( b ^ { * }, y ) \cos < _ { b ^ { * } } ^ { * } ( \gamma _ { x } ( s ), \gamma _ { y } ( t ) ) \\ & \leq d ( b ^ { * }, x ) d ( b ^ { * }, y ) \cos < _ { b ^ { * } } ^ { * } ( x, y ) \\ & \leq \langle x, y \rangle _ { b ^ { * } } ^ { 0 } + c d ^ { 2 } ( b ^ { * }, x ) d ^ { 2 } ( b ^ { * }, y ), \\ \text{ing to Theorem $5-(3)$, inequality $(2.5)$ and the Lipschitz continuity of $cos(.*).$ Now $c$}.$$

according to Theorem 5-(3), inequality (2.5) and the Lipschitz continuity of cos( ). Now observe · that, for all x ∈ S and all t ∈ (0 1), ,

$$\varphi _ { \lambda } \cdots & \cdots \cdots - \cdots \cdots - \cdots \cdots \cdots \cdots \\ & d ^ { 2 } ( x, \gamma _ { y } ( t ) ) - d ^ { 2 } ( b ^ { * }, x ) \\ & = d ^ { 2 } ( b ^ { * }, \gamma _ { y } ( t ) ) - 2 \langle x, y \rangle _ { b ^ { * } } ^ { 0 } \\ & \leq d ^ { 2 } ( b ^ { * }, \gamma _ { y } ( t ) ) - 2 \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( \gamma _ { y } ( t ) ) \rangle _ { b ^ { * } } + c d ^ { 2 } ( b ^ { * }, x ) d ^ { 2 } ( b ^ { * }, \gamma _ { y } ( t ) ) \\ & = t ^ { 2 } d ^ { 2 } ( b ^ { * }, y ) - 2 t \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( y ) \rangle _ { b ^ { * } } + c t ^ { 2 } d ^ { 2 } ( b ^ { * }, x ) d ^ { 2 } ( b ^ { * }, y ). \\ \text{rating with respect to } d P ( x ). \, \text{using the definition of a barvcenter and letting } t \, \text{go to } 0$$

Integrating with respect to d P x ( ), using the definition of a barycenter and letting t go to 0, we deduce that

$$\int \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( y ) \rangle _ { b ^ { * } } \mathrm d P ( x ) \leq 0 \,.$$

Since this holds for all y ∈ S , integrating with respect to d P y ( ) gives the result.

(3) Given p ∈ S and two elements u = [ γ, s , v ] = [ σ, t ] ∈ T S p , we write u + v = 0 and say that u and v are opposite to each other if ( s = t = 0) or ( s = t and /sphericalangle p ( γ, σ ) = π ). Then, we set

$$\mathcal { L } _ { p } S = \{ u \in T _ { p } S \, \colon \exists \, v \in T _ { p } S, u + v = 0 \} \,.$$

Given u ∈ L p S , there is a unique vector opposite to u denoted -u . The fact that L p S is a Hilbert space for the restricted cone metric follows from Theorem 11.6.4 in [AKP19]. The inclusion log b /star (supp( P )) ⊂ L b /star S follows from statement (2) and [Le 19].

(4) Fix a barycenter b /star of P and some b ∈ S . Note that if b is in the support of P , it follows readily from (3) that (4) holds. The main purpose of this proof is to show that the same holds for any b ∈ S , not necessarily in supp( P ). For brevity we use the following notation:

$$| x - y | = \| \log _ { b ^ { * } } ( x ) - \log _ { b ^ { * } } ( y ) \| _ { b ^ { * } } \,, \ \ | x | = \| \log _ { b ^ { * } } ( x ) \| _ { b ^ { * } }$$

and

$$\langle x, y \rangle & = \langle \log _ { b ^ { * } } ( x ), \log _ { b ^ { * } } ( y ) \rangle _ { b ^ { * } } \quad \forall \, x, y \in S \,. \\ _ { - \, \sigma \, \sigma } \quad \dots \quad _ { - \, \sigma \, \dots \, \dots \, \dots \, \dots \, } \quad \dots$$

In addition, whenever u ∈ T b /star S and y ∈ S , the notation | u - | y , | u | and 〈 u, y 〉 should be understood as ‖ u -log b /star ( y ) ‖ b /star , ‖ u ‖ b /star and 〈 u, log b /star ( y ) 〉 b /star respectively.

↦

↦

$$| u _ { t } - y | ^ { 2 } \geq ( 1 - t ) | u _ { 0 } - y | ^ { 2 } + t | u _ { 1 } - y | ^ { 2 } - t ( 1 - t ) | u _ { 0 } - u _ { 1 } | ^ { 2 },$$

We first prove that u ∈ L b /star S → 〈 u, b 〉 is a convex function. To that end, fix t ∈ (0 1), , u , u 0 1 ∈ L b /star S , and set u t = (1 -t ) u 0 + tu 1 ∈ L b /star S . The path t ∈ [0 , 1] → u t defines a geodesic in T b /star S according to (1) and (3). Since curv( T b /star S ) ≥ 0 we get from Definition 4 that, for all y ∈ S and t ∈ [0 , 1],

with equality if y = b /star since u , u t 0 and u 1 belong to L b /star S . Hence, by (2.3), we have

$$2 \langle u _ { t }, b \rangle & = | u _ { t } | ^ { 2 } + | b | ^ { 2 } - | u _ { t } - b | ^ { 2 } \\ & \leq ( 1 - t ) ( | u _ { 0 } | ^ { 2 } + | b | ^ { 2 } - | u _ { 0 } - b | ^ { 2 } ) + t ( | u _ { 1 } | ^ { 2 } + | b | ^ { 2 } - | u _ { 1 } - b | ^ { 2 } ) \\ & = ( 1 - t ) 2 \langle u _ { 0 }, b \rangle + t 2 \langle u _ { 1 }, b \rangle, \\ \text{hat $u\mapsto /u$ $h\is a convv function on the Hilbert encase $e$...$} \,.. \, S \text{ Therefore for all $u\in\mathcal{ }E$...$}$$

↦

so that u →〈 u, b 〉 is a convex function on the Hilbert space L b /star S . Therefore, for all u ∈ L b /star S , there exists g = g u ( ) such that for all v ∈ supp Q ,

$$\langle \log _ { b ^ { * } } ( v ), b \rangle \geq \langle u, b \rangle + \langle \log _ { b ^ { * } } ( v ) - u, g \rangle.$$

Choosing u to be the Pettis integral ∫ log b /star ( v )d Q v ( ) and integrating v with respect to Q yields

$$\int \langle \log _ { b ^ { * } } ( v ), b \rangle \text{d} Q ( v ) \geq \langle u, b \rangle,$$

The same arguments apply to the map u →〈-u, b 〉 , so that

↦

$$\int \langle - \log _ { b ^ { * } } ( v ), b \rangle \mathrm d Q ( v ) \geq \langle - u, b \rangle.$$

To conclude the proof, it remains to show that 〈-v, b 〉 = -〈 v, b 〉 for all v ∈ L b /star S (in particular, for u ∈ L b /star S ). To that end, select v = [ γ, s ] ∈ L b /star S and let -v = [ σ, s ]. Then on the one hand, using the definition of opposite points and the triangle inequality on the space of directions Σ p , it follows that π = /sphericalangle b /star ( γ, σ ) ≤ /sphericalangle b /star ( γ, ↑ b b /star ) + /sphericalangle b /star ( ↑ b b /star , σ ). On the other hand, the fact that curv( T p S ) ≥ 0 implies that

$$\lhd _ { b ^ { * } } ( \gamma, \sigma ) + \lhd _ { b ^ { * } } ( \gamma, \uparrow _ { b ^ { * } } ^ { b } ) + \lhd _ { b ^ { * } } ( \uparrow _ { b ^ { * } } ^ { b }, \sigma ) \leq 2 \pi, \\ \ker \nolimits _ { \nu } \varepsilon \nolimits _ { \nu } \nolimits _ { \nu } \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot$$

according to Theorem 5-(2). Combining these inequalities we get that /sphericalangle b /star ( γ, ↑ b b /star ) + /sphericalangle b /star ( ↑ b b /star , σ ) = π so that, by definition of the bracket 〈 ., . 〉 and using elementary trigonometry, we get 〈-v, b 〉 = -〈 v, b 〉 .

## 3. MAIN RESULTS

We now turn to the proof of our main result: parametric and dimension-free rates for empirical barycenters on Alexandrov spaces with curvature bounded below. We study the case of positively curved spaces in more detail and, in particular, the 2-Wasserstein space.

## 3.1 Hugging

We begin with a useful identity that controls the average curvature of the square distance around its minimum.

Given P ∈ P 2 ( S ) and a barycenter b /star of P , define for all x, b ∈ S the hugging function at b /star by

$$k _ { b ^ { * } } ^ { b } ( x ) = 1 - \frac { \| \log _ { b ^ { * } } ( x ) - \log _ { b ^ { * } } ( b ) \| _ { b ^ { * } } ^ { 2 } - d ^ { 2 } ( x, b ) } { d ^ { 2 } ( b, b ^ { * } ) }.$$

Note that if S is a Hilbert space, then k b b /star ( x ) = 1 for all x, b ∈ S . The hugging function k b b /star measures the proximity of S to its tangent cone T b /star S . The next result is a generalization of Theorem 3.2 in [ALP18] and demonstrates the central role of the hugging coefficient in the context of barycenters: it precisely controls the quadratic growth of the variance functional around its minimum.

Theorem 8 (Variance equality) . Let κ ∈ R and ( S, d ) be a geodesic space with curv( S ) ≥ κ . Let P ∈ P 2 ( S ) and b /star be a barycenter of P . Then, for all b ∈ S ,

$$d ^ { 2 } ( b, b ^ { * } ) \int k _ { b ^ { * } } ^ { b } ( x ) \, \mathrm d P ( x ) = \int ( d ^ { 2 } ( x, b ) - d ^ { 2 } ( x, b ^ { * } ) ) \, \mathrm d P ( x ),$$

where k b b /star ( x ) is as in (3.1) .

Proof. We adopt the same notation as in the proof of Theorem 7-(4). By definition of the cone metric | · - · | and bracket 〈· , ·〉 in T b /star S , we get

$$k _ { b ^ { * } } ^ { b } ( x ) d ^ { 2 } ( b, b ^ { * } ) & = d ^ { 2 } ( b, b ^ { * } ) + d ^ { 2 } ( x, b ) - | b - x | ^ { 2 } \\ & = d ^ { 2 } ( x, b ) - d ^ { 2 } ( x, b ^ { * } ) + 2 \langle x, b \rangle. \\ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot$$

The result follows by integrating both sides with respect to d P x ( ), in Theorem 7-(4) with Q = P and noticing that b /star is the Pettis integral of (log b /star ) # P in the Hilbert space L b /star S .

Remark 9 . By definition of a barycenter, the right hand side of identity (3.2) is non-negative. It follows that

$$\int k _ { b ^ { * } } ^ { b } ( x ) \, \mathrm d P ( x ) \geq 0 \,,$$

for all b = b /star ∈ S .

/negationslash

Note also that for any triple x, b, b /star , the curvature properties of S are directly reflected in k b b /star ( x ) . Indeed, k b b /star ( x ) ≥ 1 if S is non-positively curved and k b b /star ( x ) ≤ 1 if S is positively curved according to (2.4) .

## 3.2 A master theorem for spaces with curvature lower bound

This section presents general statistical guarantees for empirical barycenters, in connection to lower bounds on the function k b b /star .

Throughout, we fix a probability measure P with barycenter b /star on a geodesic space ( S, d ). Moreover, we denote by σ 2 the variance of P , which is defined by

$$\sigma ^ { 2 } = \int d ^ { 2 } ( b ^ { * }, x ) \, \mathrm d P ( x ).$$

Theorem 10 . Suppose that curv( S ) ≥ κ , for some κ ∈ R . If there exists a constant k min &gt; 0 such that k b b /star ( x ) ≥ k min , for all x, b ∈ S , then b /star is unique and any empirical barycenter b n satisfies

$$\mathbb { E } d ^ { 2 } ( b _ { n }, b ^ { * } ) \leq \frac { 4 \sigma ^ { 2 } } { n k _ { \min } ^ { 2 } }.$$

Proof. Let k x ( ) := k b n b /star ( x ) and recall the convention introduced in the proof of Theorem 7 concerning the use of the cone metric ‖ · - · ‖ b /star = | · - · | and associated bracket 〈· , ·〉 b /star = 〈· , ·〉 . We also use the following standard notation:

$$P f ( \cdot ) = \int f \text{d} P \text{ \ and \ } P _ { n } f ( \cdot ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } f ( X _ { i } ) \,.$$

On the one hand, we have from the variance equality that

$$P d ^ { 2 } ( b _ { n }, \cdot ) - P d ^ { 2 } ( b ^ { * }, \cdot ) & = d ^ { 2 } ( b _ { n }, b ^ { * } ) P k ( \cdot ) \\ P _ { n } d ^ { 2 } ( b ^ { * }, \cdot ) - P _ { n } d ^ { 2 } ( b _ { n }, \cdot ) & = d ^ { 2 } ( b _ { n }, b ^ { * } ) P _ { n } k _ { b _ { n } } ^ { b ^ { * } } ( \cdot ).$$

$$b ^ { * }, \cdot ) - P _ { n } d ^ { 2 } ( b _ { n }, \cdot ) = d ^ { 2 } ( b _ { n }, b ^ { * } ) P _ { n } k _ { b _ { n } } ^ { b ^ { * } } ( \cdot ).$$

Adding these two identities yields

$$( P - P _ { n } ) ( d ^ { 2 } ( b _ { n }, \cdot ) - d ^ { 2 } ( b ^ { * }, \cdot ) ) = d ^ { 2 } ( b _ { n }, b ^ { * } ) \left ( P k ( \cdot ) + P _ { n } k _ { b _ { n } } ^ { b ^ { * } } ( \cdot ) \right ) \,. \quad \, \\ \omega \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \. \, \$$

On the other hand, by the definition of k , we have

$$d ^ { 2 } ( b _ { n }, \cdot ) - d ^ { 2 } ( b ^ { * }, \cdot ) & = ( | b _ { n } - \cdot | ^ { 2 } - | b ^ { * } - \cdot | ^ { 2 } ) + ( d ^ { 2 } ( b _ { n }, \cdot ) - | b _ { n } - \cdot | ^ { 2 } ) \\ & = ( | b _ { n } - \cdot | ^ { 2 } - | b ^ { * } - \cdot | ^ { 2 } ) + ( k ( \cdot ) - 1 ) d ^ { 2 } ( b _ { n }, b ^ { * } ). \\.. \ e. \. \.$$

Hence, it follows that

$$( P - P _ { n } ) ( d ^ { 2 } ( b _ { n }, \cdot ) - d ^ { 2 } ( b ^ { * }, \cdot ) ) = ( P - P _ { n } ) ( | b _ { n } - \cdot | ^ { 2 } - | b ^ { * } - \cdot | ^ { 2 } ) + d ^ { 2 } ( b _ { n }, b ^ { * } ) ( P - P _ { n } ) k ( \cdot ). \ \ ( 3. 5 )$$

Combining (3.4) and (3.5) together yields

$$d ^ { 2 } ( b _ { n }, b ^ { * } ) P _ { n } [ k ( \bullet ) + k _ { b _ { n } } ^ { b ^ { * } } ( \bullet ) ] = ( P - P _ { n } ) ( | b _ { n } - \bullet | ^ { 2 } - |$$

We now focus on the right-hand side of (3.6). By definition of 〈· , ·〉 , it holds

$$| b _ { n } - \cdot | ^ { 2 } - | b ^ { * } - \cdot | ^ { 2 } = | b _ { n } | ^ { 2 } - 2 \langle \cdot, b _ { n } \rangle.$$

Hence, by Theorem 7-(4) applied to Q = P and Q = P n , we get

$$( P - P _ { n } ) ( | b _ { n } - \cdot | ^ { 2 } - | b ^ { * } - \cdot | ^ { 2 } ) & = 2 P _ { n } \langle \cdot, b _ { n } \rangle = 2 \langle b ^ { * } _ { n }, b _$$

where b /star n stands for the barycenter of (log b /star ) # ( P n ) in the Hilbert space L b /star S ⊂ T b /star S . Combining (3.6) and (3.7), yields

Hence, since P k n b /star b n ( /a113 ) ≥ 0, if k x ( ) ≥ k min &gt; 0 for all x ∈ S , we get by assumption that

$$\omega _ { \quad d ( b _ { n }, b ^ { * } ) P _ { n } [ k ( \cdot ) + k _ { b _ { n } } ^ { b ^ { * } } ( \cdot ) ] \leq 2 | b _ { n } ^ { * } |. } \quad \quad \quad$$

$$k _ { \min } ^ { 2 } d ^ { 2 } ( b _ { n }, b ^ { * } ) \leq 4 | b _ { n } ^ { * } | ^ { 2 }.$$

Since (log b /star ) # ( P n ) is the empirical distribution associated to (log b /star ) # ( P ), we get by properties of averages in Hilbert spaces that

$$\mathbb { E } | b _ { n } ^ { * } | ^ { 2 } = \frac { \sigma ^ { 2 } } { n } \,, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \$$

where we also used the fact that the variance of (log b /star ) # ( P ) is given by

$$\int \| \log _ { b ^ { * } } ( x ) \| _ { b ^ { * } } ^ { 2 } \text{d} P ( x ) = \int d ^ { 2 } ( x, b ^ { * } ) \text{d} P ( x ) = \sigma ^ { 2 } \,.$$

This completes the proof of the Theorem.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00828v4-figure-a468f609-b7d7-446e-b870-6e392f44cd69.jpg)

As pointed out in Remark 9, the condition curv( S ) ≤ 0 implies that k b n b /star ( x ) ≥ 1 and k b /star b n ( x ) ≥ 1 for all x ∈ S . The next result therefore follows readily from (3.8) and (3.9) above.

Corollary 11 . Suppose ( S, d ) is a geodesic space satisfying κ ≤ curv( S ) ≤ 0 for some κ ≤ 0 . Then, any distribution P ∈ P 2 ( S ) has a unique barycenter b /star and any empirical barycenter b n satisfies

$$\mathbb { E } d ^ { 2 } ( b _ { n }, b ^ { * } ) \leq \frac { \sigma ^ { 2 } } { n }.$$

A careful inspection of our proof techniques reveals that the previous result extends as well to complete and simply connected Riemannian manifolds with nonpositive sectional curvature, also known as Hadamard manifolds. Indeed, the use of curvature lower bounds in our results is twofold. First, it guarantees a Hilbert-like structure of the tangent cone at a barycenter. Second, we concluded by using the fact that the pushforward of P under log b ∗ has the tip of the cone as its barycenter (i.e., the fact that any barycenter is a so-called exponential barycenter ; [EM91]). The former is satisfied by the manifold assumption, and the latter is the content of Theorem 2.1(b,c) in [BP03], at least when M is Hadamard.

Our proof technique does not extend, however, to the case of general geodesic spaces with nonpositive curvature and no curvature lower bound. Indeed, it can be easily checked that claim (2) in Theorem 7 is typically not satisfied by distributions supported on the tripod (gluing of three line segments) for example.

## 3.3 Tail bound

We now provide an extension of Theorem 10 to the case of more general bounds on k b b /star . The next result shows in particular that the requirement, made in Theorem 10, that k b b /star ( x ) ≥ k min &gt; 0, for all x, b ∈ S , can be relaxed to k b b /star ( x ) ≥ k min , for all x, b ∈ S and k min possibly negative, provided that Pk b /star ( /a113 ) &gt; 0 where

$$k _ { b ^ { * } } ( x ) = \min _ { b } k _ { b ^ { * } } ^ { b } ( x ).$$

For simplicity, we prove this extension under an additional integrability assumption on P . We say that P (with barycenter b /star ) is subgaussian with variance proxy ς 2 &gt; 0 if

$$\int \exp \left ( \frac { d ^ { 2 } ( b ^ { * }, x ) } { 2 \varsigma ^ { 2 } } \right ) \mathrm d P ( x ) \leq 2.$$

Such conditions are commonly used in high-dimensional probability and statistics [Ver18,RH17].

Theorem 12 . Suppose that curv( S ) ≥ κ , for some κ ∈ R . Fix a subgaussian probability distribution P on S with variance proxy ς 2 &gt; 0 and barycenter b /star . Suppose that there exists k min &lt; 0 such that k b b /star ( x ) ≥ k min for all x, b ∈ S and that Pk b /star ( /a113 ) &gt; 0 . Then b /star is unique and, for any empirical barycenter b n and any δ ∈ (0 1) , , we get

$$d ^ { 2 } ( b _ { n }, b ^ { * } ) \leq \frac { c _ { 1 } } { n } \log \left ( \frac { 2 } { \delta } \right ),$$

with probability at least 1 -δ -e -c 2 n where c 1 , c 2 &gt; 0 are independent of n .

Proof. Denote k x ( ) = k b /star ( x ) for brevity. For all c ∈ (0 1) and , t &gt; 0,

$$\mathbb { P } ( d ( b _ { n }, b ^ { * } ) > t ) & \leq \mathbb { P } ( d ( b _ { n }, b ^ { * } ) > t, P _ { n } k \geq c P k ) + \mathbb { P } ( P _ { n } k < c P k ) \\ & \leq \mathbb { P } ( d ( b _ { n }, b ^ { * } ) P _ { n } k > t c P k ) + \mathbb { P } ( ( P - P _ { n } ) k > ( 1 - c ) P k ) \\ & \leq \mathbb { P } ( 2 | b _ { n } ^ { * } | > t c P k ) + \mathbb { P } ( ( P - P _ { n } ) k > ( 1 - c ) P k ), \\ \text{there the last inmatrix follow from inmatrix} \, ( 3 8 ) \text{ in} a \text{ odd variant of Rometain}$$

where the last inequality follows from inequality (3.8). Using a one-sided variant of Bernstein's inequality [BLM13, eq. 2.10], we get

$$\mathbb { P } ( ( P - P _ { n } ) k > ( 1 - c ) P k ) & \leq \exp \left ( - \frac { n } { 2 } \frac { ( 1 - c ) P k } { | k _ { \min } | } \left ( \frac { ( 1 - c ) | k _ { \min } | P k } { P k ^ { 2 } } \wedge \frac { 3 } { 2 } \right ) \right ). \\ \mathbb { m } { t } \dots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots.$$

Using (3.10), and the classical properties of subgaussian variables, we get

$$\mathbb { P } ( 2 | b _ { n } ^ { * } | > t c P k ) \leq 2 \exp \left ( - \frac { n t ^ { 2 } c ^ { 2 } ( P k ) ^ { 2 } } { 8 \leq ^ { 2 } } \right ).$$

The result then follows by considering, for any c ∈ (0 1), ,

$$c _ { 1 } = \frac { c ^ { 2 } ( P k ) ^ { 2 } } { 8 \varsigma ^ { 2 } } \ \text{ and } \ c _ { 2 } = \frac { ( 1 - c ) P k } { 2 | k _ { \min } | } \left ( \frac { ( 1 - c ) | k _ { \min } | P k } { P k ^ { 2 } } \wedge \frac { 3 } { 2 } \right ).$$

To better appreciate the extent of this relaxation, recall the illustrative example of the sphere used in Section 1.2. Theorem 12 covers distributions whose support may be almost the entire sphere. However, note that the existence of a finite k min precludes a support that includes the cut-locus of the barycenter, even if P puts arbitrarily small probability on small neighborhoods of the cut-locus. While such cases are out of the scope of the present paper, we anticipate that careful truncation arguments should suffice to derive parametric rates of convergence in such favorable cases.

## 4. POSITIVELY CURVED SPACES

↦

Theorem 10 guarantees a dimension-free parametric rate of convergence of b n under a uniform positive lower bound on the function ( x, b ) → k b b /star ( x ). Such a condition is closely linked to the better know notion of k -convexity which is connected to positive curvature upper bounds [Oht07]. In fact, it is not hard to check that assuming that k b b /star ( x ) ≥ k min uniformly not only in b, x but also in b /star ∈ supp( P ) is equivalent to k min -convexity of the support of P . As a result, the condition of Theorem 10 is weaker than k min -convexity of the support of P since it imposes only a control on geodesics emanating from b /star . The rest of this section is devoted to developing a suitable relaxation via the notion of geodesic extendibility.

## 4.1 Extendible geodesics

We present a compelling synthetic geometric condition that implies this lower bound in the context of positively curved spaces: the extendibility, by a given factor, of all geodesics (emanating from and arriving at) the barycenter b /star . To formalize the notion of extendible geodesics, consider a (constant-speed) geodesic γ : [0 , 1] → S . For ( λ in , λ out ) ∈ R 2 + , we say that γ is ( λ in , λ out )-extendible if there exists a (constant-speed) geodesic γ + : [ -λ in , 1 + λ out ] → S such that γ is the restriction of γ + to [0 , 1]. Before we state our sufficient condition we shall first need a fact given in [ALP18].

Theorem 13 . Suppose that curv( S ) ≥ 0 . Let P ∈ P 2 ( S ) with barycenter b /star . Suppose that, for each x ∈ supp( P ) , there exists a geodesic γ x : [0 , 1] → S connecting b /star to x which is (0 , λ ) -extendible. Suppose in addition that b /star remains a barycenter of distribution P λ = ( e λ ) # P where e λ ( x ) = γ + x (1 + λ ) . Then for all b ∈ S ,

$$\frac { \lambda } { 1 + \lambda } d ^ { 2 } ( b, b ^ { * } ) \leq \int ( d ^ { 2 } ( x, b ) - d ^ { 2 } ( x, b ^ { * } ) ) \text{d} P ( x ).$$

According to the variance equality of Theorem 8, inequality (4.1) is equivalent to the statement that, for all b ∈ S ,

$$\int k _ { b ^ { * } } ^ { b } ( x ) \mathrm d P ( x ) \geq \frac { \lambda } { 1 + \lambda }.$$

We will use this observation next.

Theorem 14 . Suppose that curv( S ) ≥ 0 and let x, b, b /star ∈ S . Suppose that, for some λ in , λ out &gt; 0 , there is a geodesic connecting b /star to x which is ( λ in , λ out ) -extendible. Then

$$k _ { b ^ { * } } ^ { b } ( x ) \geq \frac { \lambda _ { \text{out} } } { 1 + \lambda _ { \text{out} } } - \frac { 1 } { \lambda _ { \text{in} } }.$$

Proof. Let γ : [0 , 1] → S be a ( λ in , λ out )-extendible geodesic connecting b /star to x and Let γ + : [ -λ in , 1 + λ out ] → S be its extension. Let z = γ + ( -ξ ) where ξ = λ in / (1 + λ out ). Then, it may be easily checked that b /star is a barycenter of the probability measure

$$P \coloneqq \frac { \xi } { 1 + \xi } \delta _ { x } + \frac { 1 } { 1 + \xi } \delta _ { z }.$$

Now, we wish to apply Theorem 13 to P . To this aim, note that the geodesic γ from b /star to x is (0 1 + , λ out )-extendible by assumption with e λ out ( x ) = γ + (1 + λ out ). Similarly, we check that the geodesic σ : [0 , 1] → S connecting b /star to z and defined by σ t ( ) = γ + ( -tξ ) is (0 , 1 + λ out )-extendible by construction with e λ out ( z ) = γ + ( -λ in ). Finally, one checks that b /star remains a barycenter of the probability measure P λ out = ( e λ out ) # P . As a result, Theorem 13 implies that

$$\frac { \lambda _ { o u t } } { 1 + \lambda _ { o u t } } \leq P k _ { b ^ { * } } ^ { b } ( \cdot ) = \frac { \xi } { 1 + \xi } k _ { b ^ { * } } ^ { b } ( x ) + \frac { 1 } { 1 + \xi } k _ { b ^ { * } } ^ { b } ( z ).$$

Finally, the fact that curv( S ) ≥ 0 implies that d x, y ( ) ≤ ‖ log b /star ( x ) -log b /star ( y ) ‖ b /star , for all x, y ∈ S which imposes that k b b /star ( z ) ≤ 1 for all b, z ∈ S . Hence, we obtain

$$k _ { b ^ { * } } ^ { b } ( x ) \geq \frac { 1 + \xi } { \xi } \left ( \frac { \lambda _ { \text{out} } } { 1 + \lambda _ { \text{out} } } - \frac { 1 } { 1 + \xi } \right ) = \frac { \lambda _ { \text{out} } } { 1 + \lambda _ { \text{out} } } - \frac { 1 } { \lambda _ { \text{in} } },$$

which completes the proof.

## 4.2 The Wasserstein space

The case of geodesic spaces with lower curvature bound contains several spaces of interest such as the space of metric measure spaces equipped with the Gromov-Wasserstein distance [Stu12] or the Wasserstein space over a postively curved space. In this subsection, we explore the extendible

geodesics condition, described in the previous subsection, in the context of the Wasserstein space over a separable Hilbert space. This space exhibits a very particular structure that allows for a simple and transparent formulation of the extendibility of geodesics in terms of the regularity of Kantorovich potentials. Given a separable Hilbert space H , with inner product 〈· , ·〉 and norm | · | , recall that the subdifferential ∂ϕ ⊂ H 2 of a function ϕ : H → R is defined by ∂ϕ = { ( x, g ) : ∀ y ∈ H,ϕ y ( ) ≥ ϕ x ( ) + 〈 g, y -x 〉} . We denote ∂ϕ x ( ) = { g ∈ H : ( x, g ) ∈ ∂ϕ } . The function ϕ is called α -strongly convex if, for all x ∈ H ∂ϕ x , ( ) = ∅ and

/negationslash

$$\langle g, x - y \rangle \geq \varphi ( x ) - \varphi ( y ) + \frac { \alpha } { 2 } | x - y | ^ { 2 },$$

for all g ∈ ∂ϕ x ( ) and all y ∈ H . We recall the following result.

Theorem 15 (Theorem 3.5 in [ALP18]) . Let ( S, d ) = ( P 2 ( H ,W ) 2 ) be the Wasserstein space over a separable Hilbert space H . Let µ and ν be two elements of S and let γ : [0 , 1] → S be a geodesic connecting µ to ν . Then, γ is (0 , λ ) -extendible if, and only if, the support of the optimal transport plan of µ to ν lies in the subdifferential ∂ϕ µ → ν of a λ 1+ λ -strongly convex map ϕ µ → ν : H → R .

In the above theorem, ϕ µ → ν is defined as follows. Let f µ → ν , g ν → µ be optimal Kantorovich potentials, i.e., solutions of the dual Kantorovich problem

$$W _ { 2 } ^ { 2 } ( \mu, \nu ) = \sup \left \{ \int f \mathrm d \mu + \int g \mathrm d \nu \, \colon f, g \in C _ { b } ( H ), f ( x ) + g ( y ) \leq | x - y | ^ { 2 } \right \} \,,$$

where C b ( H ) denotes the set of real-valued bounded continuous functions on H . Then, for all x ∈ H ,

$$f _ { \mu \to \nu } ( x ) = 2 | x | ^ { 2 } - \varphi _ { \mu \to \nu } ( x ), \quad \ g _ { \nu \to \mu } ( x ) = 2 | x | ^ { 2 } - \varphi _ { \nu \to \mu } ( x ), \\ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot$$

and one checks that ϕ ν → µ = ϕ ∗ µ → ν is the Fenchel-Legendre conjuguate of ϕ µ → ν [Vil09, Theorem 5.10]. Our next result is in the same spirit as Theorem 15 and characterises the ( λ in , 1 + λ out )-extendibility of geodesics in the Wasserstein space in a specific scenario. Recall that a convex function ϕ : H → R is called β -smooth if

$$\langle g _ { x }, x - y \rangle \leq \varphi ( x ) - \varphi ( y ) + \frac { \beta } { 2 } | x - y | ^ { 2 }, \quad \forall \, g _ { x } \in \partial \varphi ( x ) \\ \Delta _ { \ } \nu \ \nu \ \nu \ \nu \ \nu \cdots \ \nu \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \end{matrix}$$

for all x, y ∈ H . In fact, for β &gt; 0, it is easy to check that convex β -smooth functions are differentiable. Therefore, a convex function ϕ : H → R is β -smooth if and only if it is differentiable and

$$\langle \nabla \varphi ( x ), x - y \rangle \leq \varphi ( x ) - \varphi ( y ) + \frac { \beta } { 2 } | x - y | ^ { 2 } \,. \\ \ell \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdots$$

It is known that a convex function is β -smooth if and only if its Fenchel-Legendre transform is 1 /β -strongly convex [BC17, Theorem 18.15]. Since ϕ ν → µ = ϕ ∗ µ → ν , the next result follows readily from Theorems 10, 14 and 15.

Corollary 16 . Let ( S, d ) = ( P 2 ( H ,W ) 2 ) be the Wasserstein space over a separable Hilbert space H . Let P ∈ P 2 ( S ) with barycenter µ /star ∈ S . Let α, β &gt; 0 and suppose that every µ ∈ supp( P ) is the pushforward of µ /star by the gradient of an α -strongly convex and β -smooth function ϕ µ /star → µ , i.e., µ = ( ∇ ϕ µ /star → µ ) # µ /star . Then, if β -α &lt; 1 , any empirical barycenter µ n of P satisfies

$$\mathbb { E } W _ { 2 } ^ { 2 } ( \mu _ { n }, \mu ^ { * } ) \leq \frac { 4 \sigma ^ { 2 } } { ( 1 - \beta + \alpha ) ^ { 2 } n }.$$

## 4.3 Examples

We complete this section by two concrete examples in which we instantiate sufficient conditions for the application of Corollary 16.

4.3.1 Gaussians. Consider first the metric space of Gaussians distributions over H = R D equipped with the 2-Wasserstein distance.

Assume that P is supported on non-degenerate Gaussians N ( m, Σ) ∼ P .

It is a well-known fact that the optimal transport map between N ( m , 0 Σ ) and 0 N ( m , 1 Σ ) is 1 given by [PC19]:

$$\Phi _ { 0 } ^ { \Phi _ { 1 } } \Phi _ { 0 } ^ { \Phi _ { 2 } } x \mapsto \Sigma _ { 0 } ^ { - 1 / 2 } ( \Sigma _ { 0 } ^ { 1 / 2 } \Sigma _ { 1 } \Sigma _ { 0 } ^ { 1 / 2 } ) ^ { 1 / 2 } \Sigma _ { 0 } ^ { - 1 / 2 } ( x - m _ { 0 } ) + m _ { 1 }. \quad \Phi _ { 0 } ^ { \Phi _ { 2 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Phi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } } \Phi _ { 0 } ^ { \Psi _ { 3 } }$$

↦

Using Equation (4.2), the condition of geodesic extendibility translates, by Theorem 15, to control on the maximum and minimum eigenvalues of the matrix acting on ( x -m 0 ). A natural means of establishing this control uniformly for the distribution P is to assume that each element of its support N ( m, Σ) has covariance matrix Σ with eigenvalues in [ κ , κ 0 1 ]. In terms of the space of positive definite matrices, this can be interpreted as ensuring that the support of P lies away from the boundary while remaining bounded, respectively.

Under this assumption on the support of P , it can be shown [CMRS20, Prop. 15] that the barycenter of P exists, and is the unique Gaussian N ( m , /star Σ ) where /star m /star := ∫ m P m d ( ) and Σ /star solves the first-order optimality equation

$$I _ { D } = \int \Sigma _ { * } ^ { - 1 / 2 } ( \Sigma _ { * } ^ { 1 / 2 } \Sigma \Sigma _ { * } ^ { 1 / 2 } ) ^ { 1 / 2 } \Sigma _ { * } ^ { - 1 / 2 } \mathrm d P ( \Sigma ).$$

Using this equation one can directly calculate that Σ /star must also have eigenvalues in [ κ , κ 0 1 ]. By inspecting the formula (4.2), it follows that the optimal transport maps between N ( m , /star Σ ) and each /star element of the support of P are κ -1 -strongly convex and κ -smooth, where κ := κ /κ 1 0 . Together, this yields the following application of our main result.

Corollary 17 . Let ( S, d ) denote the space of Gaussians metrized by the 2 -Wasserstein distance. Fix κ 1 &gt; κ 0 &gt; 0 and let P ∈ P 2 ( S, d ) be any distribution supported solely on Gaussians N ( m, Σ) with eigenvalues in [ κ , κ 0 1 ] . Denote κ := κ /κ 1 0 , and assume κ -κ -1 &lt; 1 . Then P has a unique barycenter µ /star = N ( m , /star Σ ) /star , and the empirical barycenter µ n = N ( m , n Σ ) n satisfies

$$\mathbb { E } W _ { 2 } ^ { 2 } ( \mu _ { n }, \mu ^ { * } ) & \leq \frac { 4 \sigma ^ { 2 } } { ( 1 - \kappa + \kappa ^ { - 1 } ) ^ { 2 } n }. \\.. \quad \dots \quad.. \quad.. \quad..$$

4.3.2 Template deformation model. Throughout this paper we have made minimal assumptions on P , apart from those that ensure convergence of its barycenter. It is customary to define models where the mean, and more generally the barycenter of P is a parameter of interest. Template deformation models were introduced as convenient models where the Wasserstein barycenter is the parameter of interest. As we will see below, this model gives an equivalent but complementary perspective on Corollary 16.

Recall that since ( P 2 ( R D ) , W 2 ) is positively curved, the barycenter µ /star of a measure P ∈ P 2 ( P 2 ( R D )) is also a barycenter of the measure P pushed forward to the tangent space at µ /star ; in other words, the barycenter is also an exponential barycenter [Le 19, Corollary 2]. Moreover, the tangent space at a measure µ /star can be identified with the closure in L 2 ( µ /star ) of the set of maps T that can be

written as the gradient of a function - this follows from identifying a tangent vector log µ /star ( µ ) with ∇ ϕ µ /star → µ -id where ∇ ϕ µ /star → µ is the optimal transport map from µ /star to µ ; see [AGS05, § 8.4]. In particular, µ /star is an exponential barycenter for P if and only if

$$\int \nabla \varphi _ { \mu ^ { * } \to \mu } ( x ) \mathrm d P ( \mu ) = x, \text{ for } \mu ^ { * } \text{-almost all } x.$$

Exponential barycenters correspond to critical points that are not necessarily global minima of the variance functional. Hence, (4.3) does not imply that µ /star is a barycenter of P . However, one can easily check that the variance equality (Theorem 8) holds also when µ /star is an exponential barycenter. It implies that if (4.3) holds and k ν µ /star ( µ ) ≥ 0 for all ν ∈ P 2 ( R D ) and P -almost all µ , then µ /star is also a barycenter of P .

Wasserstein exponential barycenters as in (4.3) arise naturally as the parameter of interest in the following template deformation model [BLGL + 15,ZP19]. Let T ∈ L 2 ( R D , R D , µ /star ) be a random function, often call warping function . In a template deformation model, one observes independent copies of

$$\mu = T _ { \# } \mu ^ { * } \,, \quad T \sim Q \, \quad \dots \quad \dots \quad \dots \quad \dots \quad \sim \, \quad \dots \quad \dots \,.$$

and the goal is to estimate µ /star . Under some conditions on the distribution Q of T , µ /star is an exponential barycenter of the distribution of µ . For example if T is linear and identified to a positive semidefinite D × D matrix, it is sufficient to assume the E Q [ T ] = I D . More generally, we can assume that T is a gradient of a convex function. Since T # µ /star = µ , we have by Brenier's theorem that T = ∇ ϕ µ /star → µ . In that case, E Q [ T ] = I D is replaced with (4.3). Additional regularity conditions on the warping functions ensures that µ /star is, in fact, a barycenter.

The following result follows readily from Corollary 16.

Corollary 18 . Fix α, β &gt; 0 such that β -α &lt; 1 and consider the template deformation model (4.4) where Q is supported on gradients of α -strongly convex and β -smooth function ϕ µ /star → µ . Moreover, assume that

$$\int T ( x ) \mathrm d Q ( T ) = x, \text{ for } \mu ^ { * } \text{-} a l m o s t \text{ all } x.$$

Let µ n denote the empirical barycenter of n independent copies of µ from the template deformation model (4.4) . Then, for all n ≥ 1 , it holds

$$\mathbb { E } W _ { 2 } ^ { 2 } ( \mu _ { n }, \mu ^ { * } ) \leq \frac { 4 \sigma ^ { 2 } } { ( 1 - \beta + \alpha ) ^ { 2 } n } \,,$$

where

$$\sigma ^ { 2 } = \mathbb { E } W _ { 2 } ^ { 2 } ( \mu, \mu ^ { * } ) = \int \| T ( x ) - x \| ^ { 2 } \mathrm d \mu ^ { * } ( x ) \mathrm d Q ( T ).$$

## ACKNOWLEDGMENTS

TLG, PR and QP acknowledge the hospitality of the Institute for Advanced Study where most of this work was carried out. TLG and QP were supported by the Russian Academic Excellence Project 5-100. PR was supported by NSF awards IIS-1838071, DMS-1712596 and DMS-TRIPODS1740751; grant 2018-182642 from the Chan-Zuckerberg Initiative DAF and the Schmidt Foundation. The authors thank Sinho Chewi and anonymous reviewers for helpful remarks.

| REFERENCES   | REFERENCES                                                                                                                                                                                     |
|--------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [Afs11]      | B. Afsari , Riemannian L p center of mass: Existence, uniqueness, and convexity, Pro- ceedings of the American Mathematical Society 139 (2011), 655-655.                                       |
| [AC11]       | M. Agueh and G. Carlier , Barycenters in the Wasserstein space, SIAM Journal on Mathematical Analysis 43 (2011), 904-924.                                                                      |
| [AC17]       | M. Agueh and G. Carlier , Vers un th´or`me e e de la limite centrale dans l'espace de Wasserstein?, Comptes Rendus Mathematique 355 (2017), 812 - 818.                                         |
| [ALP18]      | A. Ahidar-Coutrix , T. Le Gouic , and Q. Paris , On the rate of convergence of empirical barycentres in metric spaces: curvature, convexity and extendible geodesics, arXiv:1806.02740 (2018). |
| [AKP19]      | S. Alexander , V. Kapovitch , and A. Petrunin , Alexandrov geometry: preliminary version no. 1 , Book in preparation, March 2019 (en), arXiv:1903.08539.                                       |
| [AGS05]      | L. Ambrosio , N. Gigli , and G. Savare , Gradient Flows: In Metric Spaces and in the Space of Probability Measures , Lectures in Mathematics. ETH Z¨rich u , Birkh¨user a Basel, 2005.         |
| [ACB17]      | M. Arjovsky , S. Chintala , and L. Bottou , Wasserstein generative adversarial networks, in International Conference on Machine Learning , 2017, pp. 214-223.                                  |
| [BC17]       | H. H. Bauschke and P. L. Combettes , Convex analysis and monotone operator theory in Hilbert spaces , second ed., CMS Books in Mathematics , Springer, Cham, 2017.                             |
| [BP03]       | R. Bhattacharya and V. Patrangenaru , Large sample theory of intrinsic and extrinsic sample means on manifold - I, The Annals of Statistics 31 (2003), 1-29.                                   |
| [BP05]       | R. Bhattacharya and V. Patrangenaru , Large sample theory of intrinsic and extrinsic sample means on manifold - II, The Annals of Statistics 33 (2005), 1225- 1259.                            |
| [BLGL + 15]  | E. Boissard , T. Le Gouic , J.-M. Loubes , and others , Distribution's template estimate with Wasserstein metrics, Bernoulli 21 (2015), 740-759.                                               |
| [BLM13]      | S. Boucheron , G. Lugosi , and P. Massart , Concentration inequalities , Oxford University Press, Oxford, 2013.                                                                                |
| [BBI01]      | D. Burago , Y. Burago , and S. Ivanov , A course in metric geometry , 33 , American Mathematical Society Providence, 2001.                                                                     |
| [BGP92]      | Y. Burago , M. Gromov , and G. Perelman , A.D. Alexandrov spaces with curvature bounded below, Russian Mathematical Surveys 47 (1992), 1-58.                                                   |
| [CC96]       | J. Cheeger and T. H. Colding , Lower bounds on Ricci curvature and the almost rigidity of warped products, Ann. of Math. (2) 144 (1996), 189-237.                                              |
| [CC97]       | J. Cheeger and T. H. Colding , On the structure of spaces with Ricci curvature bounded below. I, J. Differential Geom. 46 (1997), 406-480.                                                     |
| [CC00a]      | J. Cheeger and T. H. Colding , On the structure of spaces with Ricci curvature bounded below. II, J. Differential Geom. 54 (2000), 13-35.                                                      |
| [CC00b]      | J. Cheeger and T. H. Colding , On the structure of spaces with Ricci curvature bounded below. III, J. Differential Geom. 54 (2000), 37-74.                                                     |
| [CMRS20]     | S. Chewi , T. Maunu , P. Rigollet , and A. J. Stromme , Gradient descent algo- rithms for bures-Wasserstein barycenters, in Conference on Learning Theory , PMLR, 2020, pp. 1276-1304.         |

[CD14] M. Cuturi and A. Doucet , Fast computation of Wasserstein barycenters, in Inter-

national Conference on Machine Learning , 2014, pp. 685-693.

| [EH19]     | B. Eltzner and S. F. Huckemann , A smeary central limit theorem for manifolds                                                                                                                                                          |
|------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [EM91]     | 3381. M. ´ Emery and G. Mokobodzki , Sur le barycentre d'une probabilit´ e dans une vari´t´, e e in S´minaire e de Probabilit´s, e XXV , Lecture Notes in Math. 1485 , Springer, Berlin, 1991, pp. 220-233.                            |
| [FCVP17]   | J. Feydy , B. Charlier , F. Vialard , and G. Peyr´ e , Optimal transport for diffeo- morphic registration, in MICCAI 2017 , Proceedings, Part I , 2017, pp. 291-299.                                                                   |
| [GPC18]    | A. Genevay , G. Peyr´ e , and M. Cuturi , Learning generative models with Sinkhorn divergences, in International Conference on Artificial Intelligence and Statistics , 2018, pp. 1608-1617.                                           |
| [Hal00]    | S. Halbeisen , On tangent cones of Alexandrov spaces with curvature bounded below, manuscripta mathematica 103 (2000), 169-182.                                                                                                        |
| [HHL + 13] | T. Hotz , S. Huckemann , H. Le , J. S. Marron , J. C. Mattingly , E. Miller , J. Nolen , M. Owen , V. Patrangenaru , and S. Skwerer , Sticky central limit theorems on open books, Annals of Applied Probability 23 (2013), 2238-2258. |
| [KL11]     | W. Kendall and H. Le , Limit theorems for empirical Fr´chet e means of independent and non-identically distributed manifold-valued random variables, Brazilian Journal of Probability and Statistics 25 (2011), 323-352.               |
| [KSS19]    | A. Kroshnin , V. Spokoiny , and A. Suvorikova , Statistical inference for Bures- Wasserstein barycenters, arXiv:1901.00226 (2019).                                                                                                     |
| [Kwa72]    | S. Kwapie´ n , Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients, Studia Mathematica 44 (1972), 583-595.                                                                       |
| [LS97]     | U. Lang and V. Schroeder , Kirszbraun's Theorem and Metric Spaces of Bounded Curvature, Geometric And Functional Analysis 7 (1997), 535-560.                                                                                           |
| [Le 19]    | T. Le Gouic , A note on flatness of non separable tangent cone, arXiv:1906.11536 (2019).                                                                                                                                               |
| [LGL17]    | T. Le Gouic and J.-M. Loubes , Existence and consistency of Wasserstein barycen- ters, Probability Theory and Related Fields 168 (2017), 901-917.                                                                                      |
| [LT91]     | M. Ledoux and M. Talagrand , Probability in Banach spaces , Ergebnisse der Math- ematik und ihrer Grenzgebiete 23 , Springer-Verlag, Berlin, 1991.                                                                                     |
| [LV09]     | J. Lott and C. Villani , Ricci curvature for metric-measure spaces via optimal trans- port, Ann. of Math. (2) 169 (2009), 903-991.                                                                                                     |
| [Oht07]    | S.-I. Ohta , Convexities of metric spaces, Geometriae Dedicata 125 (2007), 225-250.                                                                                                                                                    |
| [Oht12]    | S.-I. Ohta , Barycenters in Alexandrov spaces of curvature bounded below, Advances in geometry 14 (2012), 571-587.                                                                                                                     |
| [PZ19]     | V. M. Panaretos and Y. Zemel , Statistical aspects of Wasserstein distances, Annual Review of Statistics and Its Application 6 (2019), 405-431.                                                                                        |
| [PC19]     | G. Peyr´ e and M. Cuturi , Computational optimal transport, Foundations and Trends in Machine Learning 11 (2019), 355-607.                                                                                                             |
| [RH17]     | P. Rigollet and J.-C. H¨tter u , High-dimensional statistics, Lecture notes, 2017.                                                                                                                                                     |
| [RW18]     | P. Rigollet and J. Weed , Entropic optimal transport is maximum-likelihood decon- volution, Comptes Rendus Mathematique 356 (2018), 1228 - 1235.                                                                                       |
| [SST + 19] | G. Schiebinger , J. Shu , M. Tabaka , B. Cleary , V. Subramanian , A. Solomon ,                                                                                                                                                        |

[Sch18]

[SdGP + 15]

[SCSJ17]

[Stu03]

[Stu06a]

[Stu06b]

[Stu12]

[Ver18]

[Vil09]

[Yok16]

[Yok17]

- J. Gould S. Liu , , S. Lin , P. Berube L. Lee , , J. Chen , J. Brumbaugh P. Rigol-, let , K. Hochedlinger , R. Jaenisch , A. Regev , and E. S. Lander , Optimaltransport analysis of single-cell gene expression identifies developmental trajectories in reprogramming, Cell 176 (2019), 928 - 943.e22.
- C. Sch¨tz o , Convergence rates for the generalized Fr´ echet mean via the quadruple inequality, arXiv:1812.08037 (2018).
- J. Solomon , F. de Goes , G. Peyr´ e , M. Cuturi , A. Butscher , A. Nguyen , T. Du , and L. Guibas , Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Trans. Graph. 34 (2015), 66:1-66:11.
- M. Staib , S. Claici , J. M. Solomon , and S. Jegelka , Parallel streaming Wasserstein barycenters, in Advances in Neural Information Processing Systems , 2017, pp. 2644-2655.

K.-T. Sturm , Probability measures on metric spaces of nonpositive curvature, Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces: Lecture Notes from a Quarter Program on Heat Kernels, Random Walks, and Analysis on Manifolds and Graphs 338 (2003), 357.

K.-T. Sturm , On the geometry of metric measure spaces. I, Acta Math. 196 (2006), 65-131.

K.-T. Sturm , On the geometry of metric measure spaces. II, Acta Math. 196 (2006), 133-177.

K.-T. Sturm , The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces, arXiv:1208.0434 (2012).

- R. Vershynin , High-Dimensional Probability: An Introduction with Applications in Data Science , Cambridge Series in Statistical and Probabilistic Mathematics , Cambridge University Press, 2018.

C. Villani , Optimal transport , Grundlehren der Mathematischen Wissenschaften 338 , Springer-Verlag, Berlin, 2009.

T. Yokota , Convex functions and barycenter on CAT(1)-spaces of small radii, Journal of the Mathematical Society of Japan 68 (2016), 1297-1323.

- T. Yokota , Convex functions and p -barycenter on CAT(1)-spaces of small radii, Tsukuba Journal of Mathematics 41 (2017), 43-80.

[ZP19]

- Y. Zemel and V. M. Panaretos , Fr´chet means and procrustes analysis in Wassere stein space, Bernoulli 25 (2019), 932-976.

Thibaut Le Gouic National Research University Higher School of Economics (HSE) Faculty of Computer Science Moscow, Russia Aix Marseille Univ, CNRS, Centrale Marseille, I2M Marseille, France ( thibaut.le gouic@math.cnrs.fr )

Quentin Paris National Research University Higher School of Economics (HSE) Faculty of Computer Science Moscow, Russia ( qparis@hse.ru )

Philippe Rigollet Department of Mathematics Massachusetts Institute of Technology 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA ( rigollet@math.mit.edu )

Austin Stromme Department of EECS Massachusetts Institute of Technology 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA ( astromme@mit.edu )
Thibaut Le Gouic Quentin Paris Philippe Rigollet Austin J. Stromme
Fast convergence of empirical barycenters in Alexandrov spaces and the Wasserstein space
This work establishes fast rates of convergence for empirical barycenters
over a large class of geodesic spaces with curvature bounds in the sense of
Alexandrov. More specifically, we show that parametric rates of convergence are
achievable under natural conditions that characterize the bi-extendibility of
geodesics emanating from a barycenter. These results largely advance the
state-of-the-art on the subject both in terms of rates of convergence and the
variety of spaces covered. In particular, our results apply to
infinite-dimensional spaces such as the 2-Wasserstein space, where
bi-extendibility of geodesics translates into regularity of Kantorovich
potentials.