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.
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:
- 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.
- 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.
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