TY - JOUR
T1 - Massively scalable sinkhorn distances via the nyström method
AU - Altschuler, Jason
AU - Bach, Francis
AU - Rudi, Alessandro
AU - Niles-Weed, Jonathan
N1 - Funding Information:
We thank the reviewers for their helpful comments. We also thank Piotr Indyk, Pablo Parrilo, and Philippe Rigollet for helpful discussions. JA was supported in part by NSF Graduate Research Fellowship 1122374. FB and AR were supported in part by the European Research Council (grant SEQUOIA 724063). JNW was supported in part by the Josephine de Kármán Fellowship.
Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85090171417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090171417&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85090171417
SN - 1049-5258
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -