Efficient Discretizations of Optimal Transport
Obtaining solutions to Optimal Transportation (OT) problems is typically intractable when the marginal spaces are continuous. Recent research has focused on approximating continuous solutions with discretization methods based on i.i.d. sampling, and has proven convergence as the sample size increases. However, obtaining OT solutions with large sample sizes requires intensive computation effort, that can be prohibitive in practice. In this paper, we propose an algorithm for calculating discretizations with a given number of points for marginal distributions, by minimizing the (entropy-regularized) Wasserstein distance, and result in plans that are comparable to those obtained with much larger numbers of i.i.d. samples. Moreover, a local version of such discretizations which is parallelizable for large scale applications is proposed. We prove bounds for our approximation and demonstrate performance on a wide range of problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
How to train your neural ODE: the world of Jacobian and kinetic regularization
Training neural ODEs on large datasets has not been tractable due to the necessity of allowing the adaptive numerical ODE solver to refine its step size to very small values. In practice this leads to dynamics equivalent…
Density EstimationImage GenerationMomentum Particle Maximum Likelihood
Maximum likelihood estimation (MLE) of latent variable models is often recast as the minimization of a free energy functional over an extended space of parameters and probability distributions. This perspective was recen…
Transport map unadjusted Langevin algorithms: learning and discretizing perturbed samplers
Langevin dynamics are widely used in sampling high-dimensional, non-Gaussian distributions whose densities are known up to a normalizing constant. In particular, there is strong interest in unadjusted Langevin algorithms…
Transported Memory Networks accelerating Computational Fluid Dynamics
In recent years, augmentation of differentiable PDE solvers with neural networks has shown promising results, particularly in fluid simulations. However, most approaches rely on convolutional neural networks and custom s…
Computational EfficiencyFaster Wasserstein Distance Estimation with the Sinkhorn Divergence
The squared Wasserstein distance is a natural quantity to compare probability distributions in a non-parametric setting. This quantity is usually estimated with the plug-in estimator, defined via a discrete optimal trans…
Computational Efficiency