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

Jason M. Altschuler, Sinho Chewi, Patrik Gerber, Austin J. Stromme

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 GD empirically converges rapidly, in fact faster than off-the-shelf methods such as Euclidean GD and SDP solvers. This stands in stark contrast to the best-known theoretical results for Riemannian GD, 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 Riemannian GD for these problems.

Introduction: The Dimension Gap in Optimal Transport

In machine learning and computer vision, finding the "average" of several probability distributions—the Wasserstein barycenter—is a fundamental task. For Gaussian distributions, this problem is framed on the Bures–Wasserstein manifold, the space of positive semidefinite matrices.

Historically, a significant discrepancy existed between theory and practice. While Riemannian Gradient Descent (GD) performed exceptionally well in high-dimensional settings, existing theoretical proofs suggested convergence rates that scaled exponentially with the dimension ($d$). This paper resolves this gap by proving that convergence speed is actually independent of dimension, aligning mathematical theory with empirical observations.

Methodology

The authors analyze Riemannian Gradient Descent (GD) and Stochastic Gradient Descent (SGD) through several novel theoretical lenses:

  • Polyak–Łojasiewicz (PL) Inequalities: Because the Bures-Wasserstein space has non-negative curvature, the objective function is geodesically non-convex. The authors prove the objective satisfies a PL inequality, which serves as a proxy for strong convexity and ensures the gradient remains sufficient to drive the algorithm toward the optimum.
  • Iterate Conditioning: A critical risk in manifold optimization is that iterates may become ill-conditioned. The authors demonstrate that if initial data is well-conditioned, the iterates remain so throughout the optimization process.
  • Smoothing for Medians: To handle the non-smooth nature of the Wasserstein geometric median, the authors introduce a smoothed objective, enabling the application of first-order methods.

Key Results and Empirical Validation

The core contribution is the proof of dimension-independent convergence. The rate depends on the condition number of the input distributions rather than the dimension $d$.

Empirical validation of dimension-free convergence for GD and SGD.

As shown in the figure above, the number of passes required for convergence remains constant as the dimension increases from 100 to 1000. Furthermore, Riemannian GD demonstrates significant performance advantages over Euclidean alternatives.

Comparison of Riemannian GD vs. Euclidean GD (EGD) for high-precision barycenter computation.

Summary of Findings:

  • Linear Convergence: Riemannian GD achieves a linear convergence rate for the Wasserstein barycenter.
  • Efficiency: The algorithm reaches high precision ($10^{-12}$ error) in seconds, significantly outperforming SDP solvers.
  • Robustness: The geometric median proved resilient to outliers; even with 45% heavily perturbed data, the median remained stable.

Limitations and Future Directions

While this work provides a major breakthrough, some challenges remain. The convergence guarantee for the smoothed geometric median currently only ensures reaching an approximately stationary point. Additionally, the current analysis assumes non-degenerate covariance matrices; extending these results to low-rank or degenerate cases is a promising area 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 GD empirically converges rapidly, in fact faster than off-the-shelf methods such as Euclidean GD and SDP solvers. This stands in stark contrast to the best-known theoretical results for Riemannian GD, 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 Riemannian GD for these problems.
BibTeX
@inproceedings{altschuler2021averaging,
  author = {Jason M. Altschuler and Sinho Chewi and Patrik 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