Research map / Learning theory and algorithms / Optimal transport

Finding Wasserstein Ball Center: Efficient Algorithm and The Applications in Fairness

ICML 2025 · Learning theory and algorithms › Optimal transport · approach: Wasserstein barycenters and GW

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 Wasserstein Ball Center (minmax Wasserstein radius objective) as a fairer alternative to Wasserstein barycenter, reformulates it as an LP and accelerates predictor-corrector interior point method via a block-diagonal normal-equation solver.

Problem

Wasserstein barycenter minimizes the sum of distances and can be unfair to minority distributions that lie far from the barycenter; computing a minmax Wasserstein ball center efficiently is also hard at scale due to large LP instances.

Approach

Replace the sum-of-distances barycenter objective with a minmax objective (minimize the maximum Wasserstein distance to inputs), cast it as an LP, and speed up the IPM normal equation by transforming its coefficient matrix into a block-diagonal form, reducing per-iteration cost from O(N^3 m^4) to O(Nm^3 + N^2m^2 + N^3) (plus sum m_i terms).

Key results

• The algorithm accelerates each IPM inner iteration by O(min{N^2 m, N m^2, m^4}) times over vanilla IPM and runs faster than Gurobi, which cannot solve instances with m > 500 due to memory limits.
• On FairFace, the WB object value for Middle Eastern is 78.30 versus 45.37 for WBC, indicating a more balanced distance across racial groups.
• Across 2,700 synthetic experiments, WBC reportedly achieves lower var(WD) than WB, though one reported L1 example shows the opposite (58.35 for WB vs 418.61 for WBC).

Measured effects reported in the paper

Surprising findings

• In one reported L1 example, WBC has higher variance of Wasserstein distances (418.61) than WB (58.35), contradicting the broader claim that WBC consistently lowers var(WD).

Limitations

• Experiments run on a modest workstation (Intel i5, 8GB RAM) with synthetic data and a single real dataset.
• Fairness is evaluated mainly through max Wasserstein distance and variance proxies rather than downstream fairness outcomes.
• The LP formulation applies to discrete distributions with fixed support points.

Experimental setup

Datasets: FairFace ShapeNet Core-55

Benchmarks: FairFace ShapeNet Core-55

Metrics: computational time (s) objective value maximum Wasserstein distance variance of Wasserstein distances (var(WD)) convergence iterations

Baselines: Gurobi Wasserstein barycenter (WB)

Builds on: Mehrotra predictor-corrector IPM Wasserstein barycenter LP formulation (Ge et al., 2019) Sinkhorn distance

Closest papers by meaning

• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm (NeurIPS 2020 · similarity 0.90)
• Dimensionality Reduction for Wasserstein Barycenter (NeurIPS 2021 · similarity 0.89)
• Towards Marginal Fairness Sliced Wasserstein Barycenter (ICLR 2025 · similarity 0.88)
• A Unified Approach for Computing Wasserstein Barycenters of Discrete and Continuous Measures (NeurIPS 2026 · similarity 0.87)
• Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization (ICML 2025 · similarity 0.87)
• Towards Understanding Gradient Dynamics of the Sliced-Wasserstein Distance via Critical Point Analysis (ICML 2025 · similarity 0.86)