An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters

Summary · qwen2.5:32b

The study introduces an accelerated stochastic variance-reduced primal-dual algorithm for computing entropically regularized Wasserstein barycenters, which improves upon deterministic accelerated gradient methods by reducing dependency on support size by a square-root factor while maintaining efficiency with respect to target accuracy. Experiments across various datasets demonstrate the method's lower arithmetic costs compared to first-order baseline algorithms.

Suggested post angle

Discovering new optimization algorithms for entropic Wasserstein barycenters in probability distribution averaging.

Excerpt

arXiv:2203.00813v4 Announce Type: replace-cross Abstract: 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.