# Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization

arXiv: https://arxiv.org/abs/2501.14635 · HTML: https://mlsanity.com/paper/2501.14635/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 24 Jan 2025.

## Builds on (most cited first, 23 of 23)

- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization](https://mlsanity.com/paper/2102.01752/) (2021)
- [Wasserstein Regression](https://mlsanity.com/paper/2006.09660/) (2020)
- [Debiased Sinkhorn barycenters](https://mlsanity.com/paper/2006.02575/) (2020)
- [Continuous Regularized Wasserstein Barycenters](https://mlsanity.com/paper/2008.12534/) (2020)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [Wasserstein Iterative Networks for Barycenter Estimation](https://mlsanity.com/paper/2201.12245/) (2022)
- [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019)
- [Fr'echet Means and Procrustes Analysis in Wasserstein Space](https://mlsanity.com/paper/1701.06876/) (2017)
- [A fast approach to optimal transport: The back-and-forth method](https://mlsanity.com/paper/1905.12154/) (2019)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Wasserstein Autoregressive Models for Density Time Series](https://mlsanity.com/paper/2006.12640/) (2020)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Fr'echet Change Point Detection](https://mlsanity.com/paper/1911.11864/) (2019)
- [Autoregressive Optimal Transport Models](https://mlsanity.com/paper/2105.05439/) (2021)
- [Introducing a new high-resolution handwritten digits data set with writer characteristics](https://mlsanity.com/paper/2011.07946/) (2020)
- [Convergence rate of entropy-regularized multi-marginal optimal transport costs](https://mlsanity.com/paper/2307.03023/) (2023)
- [Geodesic Optimal Transport Regression](https://mlsanity.com/paper/2312.15376/) (2023)
- [Smooth Strongly Convex Regression](https://mlsanity.com/paper/2003.00771/) (2020)
- [Two-Sample and Change-Point Inference for Non-Euclidean Valued Time Series](https://mlsanity.com/paper/2307.04318/) (2023)

## Built on by (most cited first, 2 of 2)

- [Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis](https://mlsanity.com/paper/2505.13660/) (2025)
- [Another Look at Log-PCA for Probability Measures: A Dynamical Formulation and Statistical Convergence](https://mlsanity.com/paper/2606.17196/) (2026)

## Abstract (arXiv)

The optimal transport barycenter (a.k.a. Wasserstein barycenter) is a fundamental notion of averaging that extends from the Euclidean space to the Wasserstein space of probability distributions. Computation of the unregularized barycenter for discretized probability distributions on point clouds is a challenging task when the domain dimension d > 1. Most practical algorithms for approximating the barycenter problem are based on entropic regularization. In this paper, we introduce a nearly linear time O(m logm) and linear space complexity O(m) primal-dual algorithm, the Wasserstein-Descent dotmathbbH1-Ascent (WDHA) algorithm, for computing the exact barycenter when the input probability density functions are discretized on an m-point grid. The key success of the WDHA algorithm hinges on alternating between two different yet closely related Wasserstein and Sobolev optimization geometries for the primal barycenter and dual Kantorovich potential subproblems. Under reasonable assumptions, we establish the convergence rate and iteration complexity of WDHA to its stationary point when the step size is appropriately chosen. Superior computational efficacy, scalability, and accuracy over the existing Sinkhorn-type algorithms are demonstrated on high-resolution (e.g., 1024 × 1024 images) 2D synthetic and real data.