Large Deviations Principle for Bures-Wasserstein Barycenters

arXiv:2409.11384 · math.PR, math.OC, math.ST, stat.TH · Submitted 2024-09-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Large Deviations Principle for Bures-Wasserstein Barycenters".

Emmy: Here's the gist of the paper. The paper proves that empirical Bures-Wasserstein barycenters satisfy a large deviations principle with a good rate function, revealing a novel notion of exponential tilting in the Bures-Wasserstein space that solves the relative entropy projection problem under a constraint on the barycenter.

Ada: The main result shows that for any Borel set E ⊆ K, there is a relationship between its interior and closure concerning the rate function IP (M).

Emmy: Specifically, if E is equal to the closure of its interior, then P(M∗ n ∈ E) ≈ exp(−IP (E) n) for large n, ignoring sub-exponential factors.

Ada: This result is the first known large deviations principle for barycenters in any non-linear metric space.

Paper summary: Ada: So, thinking about the title and the authors again. "Large Deviations Principle for Bures-Wasserstein Barycenters." The work by Quinn, Jaffe, and Santoro is really about extending large deviations theory to this specific type of space.

Emmy: It's an important extension because it moves the whole framework into more general geometries where you can have things like Riemannian manifolds involved > It shows how a concept developed in Euclidean space can be adapted to these non-linear metric spaces >

Kolya: For me, the implication is that we get tools to analyze rare events in areas like quantum information or statistical shape analysis, because we now know how fast those empirical averages will converge when you're looking at them under certain constraints >

Ada: Exactly. It’s not just about the math itself; it’s about providing a way to rigorously quantify the concentration of measure for these kinds of averages > The results show that this convergence rate is dimension-free, which is a big deal when dealing with high dimensions.

Emmy: And they've shown that the rate function IP E gives us the exact exponential rate of decay for those rare events related to the convergence M star n to M star > It links the geometry directly to probability in a way that seems very deep >

Kolya: I think what stands out is how they manage to get these results in both univariate and multivariate cases, even if they have to settle for an upper bound in the latter case > And the suggestion about entropic regularization is telling us where we need more structure to make those multivariate results full large deviations principles >

Ada: So, it’s a solid piece of work that gives us a rigorous way to study empirical averages in complex spaces and tells us what limits are possible for their convergence rates > It provides the machinery for understanding how quickly things concentrate around their average.

Conclusion: Ada: So, we're wrapping up this look at Quinn, Jaffe, and Santoro’s paper on the Large Deviations Principle for Bures-Wasserstein Barycenters.

Emmy: It basically shows that even in these complex metric spaces with non-linear structures, you can still use large deviations theory to figure out how these empirical averages behave when they get really rare.

Kolya: What I’m picking up is that they manage to define this rate function, which we call IP M, and it links directly into a relative entropy projection problem with a barycenter constraint.

Ada: That's the core mechanism, right? It takes something usually seen in Euclidean geometry—exponential tilting—and adapts it for the Bures-Wasserstein space.

Emmy: Exactly. They show that this new notion of exponential tilting solves the relative entropy projection problem when you have a fixed point constraint on where the barycenter ends up.

Kolya: But they still have those heavy assumptions, right? Condition E and condition R, which say things like the population distribution has to have some specific integrability properties for this whole framework to hold together.

Ada: Right. And the real payoff is in what it means for concentration of measure. They prove that the empirical barycenters asymptotically follow a dimension-free Hoeffding-type inequality.

Emmy: That’s significant because it tells us how fast those empirical averages concentrate around the true barycenter, and this rate doesn't depend on the number of dimensions involved in the space.

Kolya: It also gives us a way to characterize exactly *how* large distances between these empirical points can occur, showing they are roughly supported on the boundary of a ball around where we expect them.

Ada: So, looking at the title and what we’ve seen, this paper gives us a rigorous mathematical language for understanding rare events in these non-linear setups.

Emmy: It sets up a framework that could be adapted to other geometric settings like Riemannian manifolds and univariate Wasserstein spaces.

Kolya: And since they've done the multivariate case, it opens the door for more complex applications in areas where we have many different variables interacting.

Adam Quinn, Jaffe, Leonardo V. Santoro

Columbia University · Ecole Polytechnique Férale de Lausanne

math.PR, math.OC, math.ST, stat.TH

Submitted: 2024-09-17

Updated: 2026-11-10

Comments: 27 pages, 4 figures. Comments welcome

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: The paper proves that empirical Bures-Wasserstein barycenters satisfy a large deviations principle with a good rate function…

Key concepts

Bures-Wasserstein Barycenter
This is a central point representing the optimal average or center of a set of distributions within the Bures-Wasserstein metric. The paper focuses on how this center behaves when observed empirically (as an empirical barycenter) and how it concentrates around its true limit under rare events.
Large Deviations Principle (LDP)
An LDP describes the exponential decay rate at which the probability of observing a rare event decreases as the number of samples increases. The paper proves this holds for these specific barycenters, providing a mathematical framework to quantify how unlikely extreme empirical results are.
Rate Function IP(M)
This function quantifies the exponential rate of decay in an LDP. It is crucial because it tells us the 'cost' of deviating from the expected behavior. The paper shows this function can be related to a relative entropy projection problem, offering a way to calculate these costs numerically.
Exponential Tilting
This is a novel notion introduced in the Bures-Wasserstein space that mirrors standard exponential tilting seen in Euclidean spaces. It is used as the solution to the relative entropy projection problem, guiding how one should shift probability distributions when constrained by a barycenter.

Terminology

Summary

The paper proves that empirical Bures-Wasserstein barycenters satisfy a large deviations principle with a good rate function, revealing a novel notion of exponential tilting in the Bures-Wasserstein space that solves the relative entropy projection problem under a constraint on the barycenter. p. 0

Main Results and Theory

The main result shows that for any Borel set E ⊆ K, there is a relationship between its interior and closure concerning the rate function IP (M). Specifically, if E is equal to the closure of its interior, then P(M∗ n ∈ E) ≈ exp(−IP (E) n) for large n, ignoring sub-exponential factors. p. 2 This result is the first known large deviations principle for barycenters in any non-linear metric space. p. 2 The rate function IP (M) can be equivalently formulated in terms of a relative entropy projection problem with a barycenter constraint, which is solved by a suitable transformation of P mirroring the usual Euclidean notion of exponential tilting. p. 2

Key Assumptions and Duality

The main results rely on several assumptions for the population distribution P, including condition (E), which states that for some λ > 0 we have ´K exp(λΠ 2(Σ, 0)) dP(Σ) < ∞. Another crucial assumption is condition (R), which states that Σ is almost surely equivalent to R, in the sense that they generate the same reproducing kernel Hilbert space, and roughly speaking that the ratio of their corresponding eigenvalues is integrable. p. 6 Under these conditions, the unique Bures-Wasserstein barycenter M is characterized by a fixed-point equation (13). p. 6 Proposition 2. p. 22 shows that the optimization problems (14) and (15) have the same value and admit at most one optimizer, and feasible points A ∈ SM and Q ∈ P2(K+) are optimal if and only if they satisfy Q = P M→A. p. 7

Consequences for Concentration of Measure

The theory has consequences for the study of rare events related to the convergence of empirical Bures-Wasserstein barycenters, focusing on concentration of measure. Corollary 2. p. 21 shows that the empirical barycenters asymptotically satisfy a dimension-free Hoeffding-type inequality. p. 2 Furthermore, Corollary 2. p. 22 characterizes the exact mechanism by which large distances Π(M∗ n, M∗) may occur. p. 2 This result shows that the conditional distribution of M∗ n given Er is roughly supported on the boundary of the ball of radius r around M∗ n.

Extensions to Other Geometries

The method of proof can be adapted to other geometric settings, yielding large deviations principles for barycenters in Riemannian manifolds and for barycenters in the univariate Wasserstein space. Specifically, sufficient conditions are provided for establishing the full large deviations theory on Riemannian manifolds (ME) and a partial large deviations principle (upper bound) for barycenters in the general multivariate Wasserstein space. p. 0 These extensions rely on key ingredients such as a fixed-point characterization of barycenters and sufficient integrability of the population distribution. p. 7 The analysis is cast in purely geometric terms, where the rate function IP (M) can be written as IP (M) = sup A∈SM − log ˆK expphA, lM (Σ)iM dP(Σ). p. 9

Numerical Optimization and Rate Function Properties

The paper discusses numerical optimization for solving the problem of minimizing IP (M) over M ∈ E. Heuristic arguments suggest using zeroth-order methods to compute the rate function IP (M) for each M ∈ DP, as the maximization over A appearing in (23) is a convex optimization problem. For first-order methods, a projected Riemannian gradient descent (PRGD) scheme is suggested, where the gradient of the rate function can be computed using equation (29). p. 7 The paper also proves fundamental properties of the rate function IP (M), including that IP (M) = 0 if and only if M = M∗. p. 9 It further establishes that IP is lower semi-continuous, coercive, and strictly convex along certain interpolating paths in K+. The paper also shows that the rate of decay in Corollary 2. p. 11 cannot be improved because any geodesic segment in (K, Π) is isometric to the unit interval [0, 1] under its usual metric. p. 1 p. 1 The relationship between IP and the Fenchel-Legendre transform of the cumulant generating function is also established. p. 9

Univariate and Multivariate Cases

For the univariate Wasserstein space, a full large deviations principle is established with a rate function IP (µ) given by IP (µ) = sup α∈L2([0,1]) hα, idiL2([0,1]) − log ˆWac(R) exphα, F−1ν iL2([0,1]) dP(ν). For the multivariate case, a partial result in the form of a large deviations upper bound is established with the rate function IP (µ) = sup α∈L2(µ) hα, idiL2(µ) − log ˆWac(Rd) exphα, tν µ iL2([0,1]) dP(ν). p. 2 The partial result is obtained by following the method of proof of Section 2 and relies on the fact that the fixed-point equation ˆWac(Rd) (tν µ − id) dP(ν) = 0 is a necessary but not sufficient condition in general. p. 7 The paper suggests that entropic regularization might be useful to gain the necessary regularity for a full large deviations principle in the multivariate case. p. 0 p. 0

Conclusion on Rate Function Properties

The function IP: K+ → [0, ∞] enjoys several fundamental properties, including IP (M) = 0 if and only if M = M∗. It is lower semi-continuous, coercive and satisfies the growth condition IP (M)/Π(M, 0) → ∞ as Π(M, 0) → ∞. The convexity of IP along certain interpolating paths is shown to be analogous to the properties of the rate function appearing in Cr´amer’s theorem. p. 2 The paper concludes by proving that for sufficiently small t > 0, we must have both Π(γ(t), M∗) > r+ε 2 ≥ r and IP (γ(t)) ≤ (1-t)IP (M)+t·0 < ir. p. 6 This result is further evidence of concentration of measure, showing that the conditional distribution of M∗ n given Er is roughly supported on the boundary of the ball of radius r around M∗ n. The rate of decay in Corollary 2. p. 11 cannot be improved because any geodesic segment in (K, Π) is isometric to the unit interval [0, 1] under its usual metric. The conditional distribution of M∗ n under a rare event E is approximately supported on arg minM∈E IP (M).

Numerical Optimization and Convergence Guarantees

The paper outlines the use of a projected Riemannian gradient descent (PRGD) scheme for numerical optimization of the rate function IP (M) over a closed set E. The convergence guarantees require some form of geodesic convexity, although only convexity along paths of the form given in part (d) of Proposition 2. p. 53 is currently known. p. 0 The paper also notes that understanding the eigenvalues of ∇2 IP is needed to choose the stepsize η appropriately. p. 6 The convergence analysis faces obstructions regarding rigorous theory for PRGD due to the lack of geodesic convexity guarantees. p. 1 The paper suggests that entropic regularization might be useful to gain the necessary regularity for a full large deviations principle in the multivariate case.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Large deviations theory for Bures-Wasserstein barycenters allows AI systems to analyze atypical behaviors of empirical barycenters by determining exponential decay rates, as shown by Theorem 2.1 and Corollary 2.1: the function PhiP: [0, infinity) → [0, infinity] satisfies (26) lim inf r→infinity PhiP (r)/r squared ≥ 1/2 sigma squared.

  2. The theory provides a dimension-free concentration of measure result for Bures-Wasserstein barycenters, meaning AI systems can characterize the exact mechanism by which large distances Pi(M∗n, M∗) may occur as described in Corollary 2.2: the empirical barycenters asymptotically satisfy a dimension-free Hoeffding-type inequality.

  3. The framework enables the use of exponential tilting to solve relative entropy projection problems under barycenter constraints, suggesting AI systems can perform optimization by solving maximization problems like (14) or minimization problems like (15) using duality: the value of (19) is equal to the value IP (M) of (14).

  4. The system can numerically solve optimization problems related to rare events by employing projected Riemannian gradient descent, which uses the gradient expression derived from the rate function: (29) (nabla M IP)(H) = tr AM / ˆK nabla M TΣ(H) dP M (Σ).

Sources

Related papers