An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters

Fixed-support Wasserstein barycenters average probability distributions while accounting for the geometry of the support.

We study the entropically regularized Wasserstein barycenter problem with a fixed regularization parameter and propose an accelerated stochastic variance-reduced primal-dual algorithm.

The proposed algorithm uses a semi-dual finite-sum structure in which each stochastic gradient requires only one softmax over the barycenter support.

The resulting finite-sum components have dimension-free smoothness bounds, which lead to a complexity result showing that the method improves the support-size dependence of deterministic accelerated gradient by a square-root factor while preserving accelerated dependence on the target accuracy.

Experiments on synthetic data, DOTmark images, shape aggregation, and digit-averaging instances are consistent with the theoretical dependence on support size and accuracy and show lower arithmetic costs than the tested first-order baselines.