Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent

Jason Altschuler, Sinho Chewi, Patrik Robert Gerber, Austin J Stromme

Introduction

Averaging data is a fundamental task in machine learning and statistics. However, when the data consists of probability distributions—such as images, sensor heatmaps, or natural language embeddings—standard Euclidean averaging often fails to capture the underlying geometric structure. The Wasserstein barycenter has emerged as the preferred tool for this task, as it respects the natural geometry of the space using optimal transport.

For the common case of Gaussian distributions, computing this barycenter becomes an optimization problem over the Bures-Wasserstein manifold (the space of positive semidefinite matrices). While practitioners have long observed that Riemannian Gradient Descent (GD) efficiently computes these averages, existing optimization theory suggested a grim reality: the complexity should explode exponentially with the dimension of the data. This paper bridges this major gap between theory and practice, proving that these algorithms actually enjoy dimension-free convergence rates.

Passes required for convergence remain constant as dimension increases, demonstrating dimension-free convergence.

The Optimization Challenge

The core theoretical hurdle is that the objective function for the Wasserstein barycenter is geodesically non-convex. Standard optimization theory typically fails in this regime, leading prior bounds on convergence speed to be "cursed" by the dimension $d$, scaling as $\exp(d)$. The authors sought to explain why, in reality, algorithms like Riemannian GD work perfectly fine even in very high dimensions.

Overcoming Non-Convexity

To overcome the non-convexity of the problem, the authors analyze Riemannian GD and Stochastic Gradient Descent (SGD), which move along the natural curves (geodesics) of the Bures-Wasserstein manifold rather than in straight Euclidean lines. They employ two clever theoretical strategies:

  1. Polyak-Łojasiewicz (PL) Inequalities: They prove that while the objective isn't convex, it satisfies a "gradient domination" condition. This ensures that as long as the algorithm hasn't reached the optimum, the gradient remains large enough to guarantee significant progress in every step.
  2. Geodesic Convexity of Eigenvalues: A major technical challenge is ensuring that the covariance matrices don't become "ill-conditioned" (too close to singular) during optimization. The authors prove a new theorem showing that the minimum and maximum eigenvalues of the iterates behave convexly along geodesics. This allows them to keep the optimization well-behaved without relying on dimension-dependent bounds.

Key Insights and Empirical Superiority

The authors' analysis reveals that the "dimension curse" found in previous studies was an artifact of mathematical limitations, not a property of the algorithm itself. The true bottleneck for convergence isn't the number of dimensions ($d$), but the condition number ($\kappa$)—how "stretched" the distributions are.

By respecting the natural Riemannian geometry, the algorithm becomes significantly more robust. The authors demonstrate that Euclidean GD (EGD) is highly sensitive to step-size tuning and is often slower. In contrast, Riemannian GD requires zero parameter tuning for the step size and achieves linear convergence.

Riemannian GD (solid line) reaches high precision rapidly without the step-size tuning required by Euclidean GD (dashed lines).

In synthetic experiments, Riemannian GD reached high precision ($10^{-12}$ error) in less than 0.5 seconds, while standard off-the-shelf Semidefinite Programming (SDP) solvers took over 15 seconds for the same problem. Furthermore, the authors extended their unified framework to the Wasserstein geometric median (a more robust version of an average), providing the first-ever convergence guarantees for Riemannian GD on this problem and showing it remains stable even when a large fraction of the data is corrupted.

Future Directions

While the convergence rates are proven to be dimension-free, it remains an open question whether the specific dependencies on the condition number ($\kappa$) are mathematically optimal. The authors suggest that "acceleration" techniques, such as Nesterov's momentum, might be applicable to the Bures-Wasserstein manifold to speed up convergence even further. Finally, extending these dimension-free results beyond Gaussian covariance matrices to more general, non-parametric probability distributions remains a compelling challenge for future research.

Summary updated

Abstract

We study first-order optimization algorithms for computing the barycenter of Gaussian distributions with respect to the optimal transport metric. Although the objective is geodesically non-convex, Riemannian gradient descent empirically converges rapidly, in fact faster than off-the-shelf methods such as Euclidean gradient descent and SDP solvers. This stands in stark contrast to the best-known theoretical results, which depend exponentially on the dimension. In this work, we prove new geodesic convexity results which provide stronger control of the iterates, yielding a dimension-free convergence rate. Our techniques also enable the analysis of two related notions of averaging, the entropically-regularized barycenter and the geometric median, providing the first convergence guarantees for these problems.
BibTeX
@inproceedings{altschuler2021averaging,
  author = {Jason Altschuler and Sinho Chewi and Patrik Robert Gerber and Austin J Stromme},
  title = {{Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=YV3uoawS5KK},
}
Figure