# Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks](https://mlsanity.com/paper/2007.04462/) (2020)
- [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [Debiased Sinkhorn barycenters](https://mlsanity.com/paper/2006.02575/) (2020)
- [Continuous Regularized Wasserstein Barycenters](https://mlsanity.com/paper/2008.12534/) (2020)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [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)
- [Tree-Based Diffusion Schr"odinger Bridge with Applications to Wasserstein Barycenters](https://mlsanity.com/paper/2305.16557/) (2023)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Estimating Barycenters of Distributions with Neural Optimal Transport](https://mlsanity.com/paper/2402.03828/) (2024)
- [Energy-Guided Continuous Entropic Barycenter Estimation for General Costs](https://mlsanity.com/paper/2310.01105/) (2023)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem](https://mlsanity.com/paper/1905.12895/) (2019)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [Wasserstein Proximal Coordinate Gradient Algorithms](https://mlsanity.com/paper/2405.04628/) (2024)
- [Introducing a new high-resolution handwritten digits data set with writer characteristics](https://mlsanity.com/paper/2011.07946/) (2020)
- [Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs](https://mlsanity.com/paper/2208.03025/) (2022)
- [Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2501.14635/) (2025)

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

- [Functional Gradient Descent with Adaptive Representations](https://mlsanity.com/paper/2606.16926/) (2026)
- [Another Look at Log-PCA for Probability Measures: A Dynamical Formulation and Statistical Convergence](https://mlsanity.com/paper/2606.17196/) (2026)

## Abstract (arXiv)

This paper introduces a new constraint-free concave dual formulation for the Wasserstein barycenter. Tailoring the vanilla dual gradient ascent algorithm to the Sobolev geometry, we derive a scalable Sobolev gradient ascent (SGA) algorithm to compute the barycenter for input distributions discretized over a regular grid. Despite the algorithmic simplicity, we provide a global convergence analysis that achieves the same rate as the classical subgradient descent methods for minimizing nonsmooth convex functions in the Euclidean space. A central feature of our SGA algorithm is that the computationally expensive c-concavity projection operator enforced on the Kantorovich dual potentials is unnecessary to guarantee convergence, leading to significant algorithmic and theoretical simplifications over all existing primal and dual methods for computing the exact barycenter. Our numerical experiments demonstrate the superior empirical performance of SGA over the existing optimal transport barycenter solvers.