Stochastic Optimization for Large-scale Optimal Transport

Abstract

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.

References in corpus (2)

• Learning with a Wasserstein Loss
• Wasserstein Training of Boltzmann Machines

Cited by in corpus (52)

• DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation
• Estimating individual treatment effect: generalization bounds and algorithms
• Large-Scale Optimal Transport and Mapping Estimation
• An Entropic Optimal Transport Loss for Learning Deep Neural Networks under Label Noise in Remote Sensing Images
• GAN and VAE from an Optimal Transport Point of View
• Optimal transport mapping via input convex neural networks
• Semi-dual Regularized Optimal Transport
• Generalization Bounds and Representation Learning for Estimation of Potential Outcomes and Causal Effects
• On the Complexity of Approximating Wasserstein Barycenter
• Sliced Gromov-Wasserstein
• Statistical and Topological Properties of Sliced Probability Divergences
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Wasserstein Patch Prior for Image Superresolution
• A Generative Model for Texture Synthesis based on Optimal Transport between Feature Distributions
• Continuous Regularized Wasserstein Barycenters
• Greedy stochastic algorithms for entropy-regularized optimal transport problems
• Computational Methods for Martingale Optimal Transport problems
• Approximate inference with Wasserstein gradient flows
• (Martingale) Optimal Transport And Anomaly Detection With Neural Networks: A Primal-dual Algorithm
• Scalable Unbalanced Optimal Transport using Generative Adversarial Networks
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• Outlier-Robust Optimal Transport
• Vector quantile regression and optimal transport, from theory to numerics
• Re-evaluating Word Mover's Distance
• The statistical effect of entropic regularization in optimal transportation
• Entropic regularization of Wasserstein distance between infinite-dimensional Gaussian measures and Gaussian processes
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark
• Large-Scale Wasserstein Gradient Flows
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Asymptotic Guarantees for Generative Modeling Based on the Smooth Wasserstein Distance
• Learning Cost Functions for Optimal Transport
• Statistical Optimal Transport posed as Learning Kernel Embedding
• Gaussian-Smooth Optimal Transport: Metric Structure and Statistical Efficiency
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• A gradual, semi-discrete approach to generative network training via explicit Wasserstein minimization
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• SGD with Coordinate Sampling: Theory and Practice
• On the Existence of Optimal Transport Gradient for Learning Generative Models
• The Wasserstein Proximal Gradient Algorithm
• Optimal Transport Relaxations with Application to Wasserstein GANs
• Entropic Optimal Transport in Random Graphs
• Convergence and finite sample approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings
• Efficient Wasserstein Natural Gradients for Reinforcement Learning
• Numerical Solution of the $L^1$-Optimal Transport Problem on Surfaces
• Learning Generalized Gumbel-max Causal Mechanisms
• Randomized Stochastic Gradient Descent Ascent
• Efficient Discretizations of Optimal Transport
• Sequential Ensemble Transform for Bayesian Inverse Problems
• Coupling Matrix Manifolds and Their Applications in Optimal Transport
• Entropy-regularized optimal transport on multivariate normal and q-normal distributions
• Learning to Transport with Neural Networks
• Distributionally-Constrained Policy Optimization via Unbalanced Optimal Transport