Research map / Learning theory and algorithms / Optimal transport
Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes WDHA, a primal-dual Wasserstein-descent / H1-ascent algorithm that computes the exact (unregularized) OT barycenter on m-point grids in O(m log m) per iteration, with a stationary-point convergence analysis, and shows gains over entropic Sinkhorn-type barycenter solvers on 1024x1024 images.
Problem
Computing the unregularized Wasserstein barycenter of discretized densities on point clouds/grids in dimension d>1 is expensive; existing practical solvers use entropic regularization that blurs results.
Approach
Recast the barycenter as a nonconvex-concave minimax problem over the barycenter measure nu and strongly convex, smooth Kantorovich potentials; alternate a Wasserstein gradient step for nu with a homogeneous H1 gradient ascent step on the potentials, using second convex conjugates for the projection in practice.
Key results
- On 1024x1024 synthetic shapes, WDHA reaches barycenter functional value 74.5791 in 676 s, versus CWB 75.0689 (3731 s) and DSB 74.5804 (7249 s).
- On 500x500 handwritten 8s (100 images, T=300), WDHA takes 3,299 s versus 10,808 s for CWB and 11,186 s for DSB, with sharper textures.
- Theory: the min squared L2 norm of the Wasserstein gradient over T iterations decays at rate O(1/T) under bounded-density and step-size assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use WDHA instead of CWB | Synthetic uniform distributions, 1024 × 1024 · Synthetic uniform distributions, 1024 × 1024 | barycenter functional value × 10^3: 75.0689 -> 74.5791 | Helped |
| use WDHA instead of DSB | Synthetic uniform distributions, 1024 × 1024 · Synthetic uniform distributions, 1024 × 1024 | barycenter functional value × 10^3: 74.5804 -> 74.5791 | Helped |
| use WDHA instead of CWB | Synthetic uniform distributions, 1024 × 1024 · Synthetic uniform distributions, 1024 × 1024 | runtime (seconds): 3731 -> 676 seconds | Helped |
| use WDHA instead of DSB | Synthetic uniform distributions, 1024 × 1024 · Synthetic uniform distributions, 1024 × 1024 | runtime (seconds): 7249 -> 676 seconds | Helped |
| use WDHA instead of CWB | Handwritten digit 8 barycenter · Handwritten digit 8, 500 × 500 | runtime (seconds): 10,808 -> 3,299 seconds | Helped |
| use WDHA instead of DSB | Handwritten digit 8 barycenter · Handwritten digit 8, 500 × 500 | runtime (seconds): 11,186 -> 3,299 seconds | Helped |
| use the Wasserstein gradient rather than the L2 gradient to update the barycenter (ablation) | WDHA · simulation studies | performance | Helped |
| replace projection onto strongly convex and smooth potentials with the second convex conjugate (ablation) | WDHA · empirical simulations | empirical performance | No clear effect |
| threshold CWB barycenter intensities, removing 10% of total mass (ablation) | CWB · Synthetic uniform distributions, 1024 × 1024 | barycenter functional value × 10^3: 75.0689 -> 74.7346 | Hurt |
| threshold DSB barycenter intensities, removing 10% of total mass (ablation) | DSB · Synthetic uniform distributions, 1024 × 1024 | barycenter functional value × 10^3: 74.5804 -> 74.5921 | Hurt |
Surprising findings
- The second-convex-conjugate replacement for the strongly convex projection, which lacks the theoretical guarantee, is what makes the practical algorithm run in O(m log m) and works empirically with diminishing step sizes.
- CWB and DSB with entropic regularization produce blurry barycenters and DSB fails with division by zero at reg=0.001.
Limitations
- Theory requires bounded density iterates (max_t ||nu^t||_inf <= V), which is assumed not proven.
- Practical algorithm uses second convex conjugate instead of strongly convex projection, so the convergence guarantee does not directly apply.
- Method is mainly limited to 2D or 3D distributions on compact domains.
Experimental setup
Datasets: synthetic uniform densities (square, circle, heart, cross) on 1024x1024 grid high-resolution handwritten digits (100 images of digit 8, 500x500)
Benchmarks: synthetic uniform shapes barycenter high-resolution handwritten digit 8 barycenter
Metrics: 2-Wasserstein barycenter functional value run time (seconds)
Baselines: Convolutional Wasserstein Barycenter (CWB) Debiased Sinkhorn Barycenter (DSB)
Builds on: Wasserstein gradient descent for barycenters H1 gradient ascent for Kantorovich potentials Danskin's theorem / GDA convergence analysis
Closest papers by meaning
- Continuous Regularized Wasserstein Barycenters (NeurIPS 2020 · similarity 0.94)
- A Grid Efficient Transport Optimization Model for the Wasserstein Barycenter Problem (NeurIPS 2026 · similarity 0.93)
- Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.91)
- A Unified Approach for Computing Wasserstein Barycenters of Discrete and Continuous Measures (NeurIPS 2026 · similarity 0.90)
- Energy-Guided Continuous Entropic Barycenter Estimation for General Costs (NeurIPS 2024 · similarity 0.90)
- Estimating Barycenters of Distributions with Neural Optimal Transport (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.