Massively scalable Sinkhorn distances via the Nyström method
arXiv:1812.05189
Abstract
The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However, the time and memory requirements of standard algorithms for computing this distance grow quadratically with the size of the data, making them prohibitively expensive on massive data sets. In this work, we show that this challenge is surprisingly easy to circumvent: combining two simple techniques---the Nyström method and Sinkhorn scaling---provably yields an accurate approximation of the Sinkhorn distance with significantly lower time and memory requirements than other approaches. We prove our results via new, explicit analyses of the Nyström method and of the stability properties of Sinkhorn scaling. We validate our claims experimentally by showing that our approach easily computes Sinkhorn distances on data sets hundreds of times larger than can be handled by other techniques.
arXiv commentto appear in NeurIPS 2019
References in corpus (10)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Computational Optimal Transport
- From optimal transport to generative modeling: the VEGAN cookbook
- Recursive Sampling for the Nyström Method
- Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
- Kernel Approximation on Manifolds I: Bounding the Lebesgue Constant
- The spectral norm error of the naive Nystrom extension
- Statistical Optimal Transport via Factored Couplings
- On Fast Leverage Score Sampling and Optimal Learning
- Approximating the Quadratic Transportation Metric in Near-Linear Time
Cited by in corpus (13)
- CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding
- Sinkhorn Divergences for Unbalanced Optimal Transport
- The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
- On parameter estimation with the Wasserstein distance
- Screening Sinkhorn Algorithm for Regularized Optimal Transport
- Linear Time Sinkhorn Divergences using Positive Features
- Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
- Efficient online learning with kernels for adversarial large scale problems
- Importance Sampling via Local Sensitivity
- Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
- Approximating Optimal Transport via Low-rank and Sparse Factorization
- Deep Networks Provably Classify Data on Curves
- Low-Rank Sinkhorn Factorization