An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters
For practitioners computing Wasserstein barycenters, this method reduces computational cost when the support size is large, offering a practical speedup over existing first-order methods.
The paper proposes an accelerated stochastic variance-reduced algorithm for entropic Wasserstein barycenters that improves the support-size dependence of deterministic accelerated gradient by a square-root factor while preserving accelerated convergence, with experiments showing lower arithmetic costs than baselines.
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.