Stochastic Saddle-Point Optimization for Wasserstein Barycenters
arXiv:2006.06763
Abstract
We consider the population Wasserstein barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. This leads to a complicated stochastic optimization problem where the objective is given as an expectation of a function given as a solution to a random optimization problem. We employ the structure of the problem and obtain a convex-concave stochastic saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose a stochastic optimization algorithm and estimate its complexity. The second result, based on kernel methods, extends the previous one to the arbitrary distribution of random probability measures. Moreover, this new algorithm has a total complexity better than the Stochastic Approximation approach combined with the Sinkhorn algorithm in many cases. We also illustrate our developments by a series of numerical experiments.
References in corpus (18)
- Fast Computation of Wasserstein Barycenters
- Stochastic Optimization for Large-scale Optimal Transport
- Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
- On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
- Stochastic Wasserstein Barycenters
- Gradient descent algorithms for Bures-Wasserstein barycenters
- A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
- On the Complexity of Approximating Wasserstein Barycenter
- Recent theoretical advances in decentralized distributed convex optimization
- Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
- Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
- Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
- Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
- A Study of Performance of Optimal Transport
- Stochastic Optimization for Regularized Wasserstein Estimators
- On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
- Improved Complexity Bounds in Wasserstein Barycenter Problem
- Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees