Stochastic Optimization for Large-scale Optimal Transport

By Aude Genevay, Marco Cuturi, G. Peyr'e, Francis R. Bach. 2016

530 citations recorded by the source corpus.

Optimal transport (OT) defines a powerful framework to compare probability distributions in a geometrically faithful way. However, the practical impact of OT is still limited because of its computational burden. We propose a new class of stochastic optimization algorithms to cope with large-scale problems routinely encountered in machine learning applications. These methods are able to manipulate arbitrary distributions (either discrete or continuous) by simply requiring to be able to draw samples from them, which is the typical setup in high-dimensional learning problems. This alleviates the need to discretize these densities, while giving access to provably convergent methods that output the correct distance without discretization error. These algorithms rely on two main ideas: (a) the dual OT problem can be re-cast as the maximization of an expectation ; (b) entropic regularization of the primal OT problem results in a smooth dual optimization optimization which can be addressed with algorithms that have a provably faster convergence. We instantiate these ideas in three different setups: (i) when comparing a discrete distribution to another, we show that incremental stochastic optimization schemes can beat Sinkhorn's algorithm, the current state-of-the-art finite dimensional OT solver; (ii) when comparing a discrete distribution to a continuous density, a semi-discrete reformulation of the dual program is amenable to averaged stochastic gradient descent, leading to better performance than approximately solving the problem by discretization ; (iii) when dealing with two continuous densities, we propose a stochastic gradient descent over a reproducing kernel Hilbert space (RKHS). This is currently the only known method to solve this problem, apart from computing OT on finite samples. We backup these claims on a set of discrete, semi-discrete and continuous benchmark problems.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Wasserstein GAN (2017, methodology): “Finally, the work of [3] shows new algorithms for calculating Wasserstein distances between diﬀerent distributions.”
Wasserstein Auto-Encoders (2017, background): “Literature on OT [13] address computing the OT cost in large scale using SGD and sampling.”
From optimal transport to generative modeling: the VEGAN cookbook (2017, background): “The authors of [7] address computing the OT cost in large scale using stochastic gradient descent (SGD) and sampling.”
Computational Optimal Transport (2018, methodology): “Indeed, as shown in [Genevay et al., 2016], the Hessian of Eε is upper bounded by 1/ε, so that ∇Eε is (1)ε -Lipschitz continuous.”
Approximation and Convergence Properties of Generative Adversarial Learning (2017, methodology): “(f) (Regularized) Optimal Transport [6].”
Learning to Score Behaviors for Guided Policy Optimization (2019, background): “Algorithm 1 is the random features equivalent of Algorithm 3 in (Genevay et al., 2016).”
Sample Complexity of Sinkhorn Divergences (2018, methodology): “(1) Choosing the relative entropy as a regularizer allows to express the dual formulation of regularized OT as the maximization of an expectation problem, as shown in (Genevay et al., 2016) .”
Orthogonal Estimation of Wasserstein Distances (2019, background): “*Equal contribution. mations (see for example (Cuturi, 2013; Genevay et al., 2016)).”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, background): “For any ↵, 2 M1 (X ), the Optimal Transport problem with entropic regularization is defined as follow [13, 24, 38]”
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters (2018, methodology): “Working with continuous distributions requires the application of stochastic procedures like stochastic gradient method as in [22], where it is applied for regularized Wasserstein distance, but not for Wasserstein barycenter.”
Learning single-cell perturbation responses using neural optimal transport (2021, methodology): “Despite existing numerical approximations of the optimal transport distance and the corresponding optimal coupling (Cuturi, 2013; Aude et al., 2016) (2), recent eﬀorts have investigated neural network-based approaches as fast and scalable approximations to (1).”
Multivariate goodness-of-fit tests based on Wasserstein distance (2020, methodology): “• In all other cases (p = 1 or d = 5), we relied on our own C implementation of the SAG method as employed in Genevay et al. (2016). A package making our implementation available is in preparation.”
Fast geometric learning with symbolic matrices (2020, unknown): “This implementation is straightforward to generalize to stochastic settings [2, 3, 47] and non-Euclidean cost functions [9, 28, 30]: we believe that it will open new ranges of applications to the OT community [37, 39].”
Wasserstein Generative Adversarial Networks (2017, unknown): “Finally, the work of (Genevay et al., 2016) shows new algorithms for calculating Wasserstein distances between different distributions.”
Adversarial Variational Optimization of Non-Differentiable Simulators (2017, background): “[26] Aude Genevay, Marco Cuturi, Gabriel Peyré, and Fran-”
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm (2018, methodology): “In (Genevay et al., 2016), stochastic gradient descent is applied to solve the entropy-regularized OT problem, but the complexity for approximating OT distance Table 1.”