mlsanityData to 7 Oct 2026

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

arXiv 2106.08502 ↗First posted 16 Jun 2021math.OC cs.LGcited by 32

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 33 of its 116 references that are in the map. First posted on arXiv 16 Jun 2021.

Builds on

33 of 116 references.

References · 33

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2013A survey of the Schr"odinger problem and some of its connections with optimal transportcited by 286
  5. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  6. 2013Fast Computation of Wasserstein Barycenterscited by 216
  7. 2018Statistical Aspects of Wasserstein Distancescited by 202
  8. 2016First-order Methods for Geodesically Convex Optimizationcited by 92
  9. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  10. 2021Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimizationcited by 50
  11. 2020Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networkscited by 49
  12. 2017Multilevel Clustering via Wasserstein Meanscited by 48
21 more
  1. 2015Scalable Bayes via Barycenter in Wasserstein Spacecited by 44
  2. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
  3. 2020Entropy-Regularized 2-Wasserstein Distance between Gaussian Measurescited by 32
  4. 2020Continuous Regularized Wasserstein Barycenterscited by 32
  5. 2020Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithmcited by 29
  6. 2021Wasserstein barycenters are NP-hard to computecited by 28
  7. 2019On the Complexity of Approximating Multimarginal Optimal Transportcited by 27
  8. 2015Fast Optimal Transport Averaging of Neuroimaging Datacited by 26
  9. 2020Wasserstein barycenters can be computed in polynomial time in fixed dimensioncited by 23
  10. 2017Riemannian Optimization via Frank-Wolfe Methodscited by 21
  11. 2017Fr'echet Means and Procrustes Analysis in Wasserstein Spacecited by 18
  12. 2019On a Combination of Alternating Minimization and Nesterov's Momentumcited by 18
  13. 2020Estimating Barycenters of Measures in High Dimensionscited by 18
  14. 2019Concentration bounds for linear Monge mapping estimation and optimal transport domain adaptationcited by 17
  15. 2020The statistical effect of entropic regularization in optimal transportationcited by 14
  16. 2018Bayesian Learning with Wasserstein Barycenterscited by 12
  17. 2019Wasserstein Barycenter Model Ensemblingcited by 10
  18. 2019A proof of the Caffarelli contraction theorem via entropic regularizationcited by 8
  19. 2015Convex Color Image Segmentation with Optimal Transport Distancescited by 6
  20. 2017An LP-based, Strongly-Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenterscited by 4
  21. 2020Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenterscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 9; 2023: 10; 2024: 3; 2025: 6; 2026: 4.

32 papers.

Sort:

  1. 2022Variational inference via Wasserstein gradient flowscited by 84
  2. 2022The Schr"odinger Bridge between Gaussian Measures has a Closed Formcited by 63
  3. 2023Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Spacecited by 36
  4. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27
  5. 2023Learning Gaussian Mixtures Using the Wasserstein-Fisher-Rao Gradient Flowcited by 25
  6. 2022Wasserstein Iterative Networks for Barycenter Estimationcited by 23
  7. 2023Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein spacecited by 20
  8. 2022Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metricscited by 18
  9. 2022Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Outcited by 11
  10. 2023Scalable Unbalanced Sobolev Transport for Measures on a Graphcited by 10
  11. 2022Measure Estimation in the Barycentric Coding Modelcited by 9
  12. 2024Generalized Sobolev Transport for Probability Measures on a Graphcited by 9
20 more
  1. 2023Bridging the Gap Between Variational Inference and Wasserstein Gradient Flowscited by 8
  2. 2023Optimal Transport for Measures with Noisy Tree Metriccited by 7
  3. 2023Personalised Federated Learning On Heterogeneous Feature Spacescited by 5
  4. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  5. 2023Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisationcited by 3
  6. 2022An Optimal Transport-driven Approach for Cultivating Latent Space in Online Incremental Learningcited by 2
  7. 2024Stochastic variance-reduced Gaussian variational inference on the Bures-Wasserstein manifoldcited by 2
  8. 2025Variational Online Mirror Descent for Robust Learning in Schr"odinger Bridgecited by 2
  9. 2026Convergence Rates for Distribution Matching with Sliced Optimal Transportcited by 2
  10. 2022Rieoptax: Riemannian Optimization in JAXcited by 1
  11. 2025Finite sample bounds for barycenter estimation in geodesic spacescited by 1
  12. 2025Metric Graph Kernels via the Tropical Torelli Mapcited by 1
  13. 2025Busemann Functions in the Wasserstein Space: Existence, Closed-Forms, and Applications to Slicingcited by 1
  14. 2022Meta-learning Pathologies from Radiology Reports using Variance Aware Prototypical Networkscited by 0
  15. 2024On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussianscited by 0
  16. 2025Gaussian mixture layers for neural networkscited by 0
  17. 2025Exact Solutions to the Quantum Schr"odinger Bridge Problemcited by 0
  18. 2026Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Spacecited by 0
  19. 2026Fr'echet Regression on the Bures-Wasserstein Manifoldcited by 0
  20. 2026Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Sizecited by 0