2020/06/12 by Meyer Scetbon, Marco Cuturi, Scetbon, Meyer +1 · 1 voice
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques #Statistical Mechanics and Entropy #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2006.07057
openalex publication_date 2020/06/12 · arxiv created 2020/10/26 · arxiv updated 2020/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although Sinkhorn divergences are now routinely used in data sciences to compare probability distributions, the computational effort required to compute them remains expensive, growing in general quadratically in the size n of the support of these distributions. Indeed, solving optimal transport (OT) with an entropic regularization requires computing a n× n kernel matrix (the neg-exponential of a n× n pairwise ground cost matrix) that is repeatedly applied to a vector. We propose to use instead ground costs of the form c(x,y)=-log\dotpφ(x)φ(y) where φ is a map from the ground space onto the positive orthant \RRr+, with r≪ n. This choice yields, equivalently, a kernel k(x,y)=\dotpφ(x)φ(y), and ensures that the cost of Sinkhorn iterations scales as O(nr). We show that usual cost functions can be approximated using this form. Additionaly, we take advantage of the fact that our approach yields approximation that remain fully differentiable with respect to input distributions, as opposed to previously proposed adaptive low-rank approximations of the kernel matrix, to train a faster variant of OT-GAN \citesalimans2018improving.