Massively scalable Sinkhorn distances via the Nyström method
Authors: Jason Altschuler, Francis Bach, Alessandro Rudi, Jonathan Niles-Weed
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. In this section we empirically validate our theoretical results. Details about the setup for each experiment appear in the supplement. We first compare to the standard Sinkhorn algorithm. Fig. 1 plots the time-accuracy tradeoff for NYSSINK, compared to the standard SINKHORN algorithm. |
| Researcher Affiliation | Academia | Jason Altschuler MIT jasonalt@mit.edu Francis Bach INRIA ENS PSL francis.bach@inria.fr Alessandro Rudi INRIA ENS PSL alessandro.rudi@inria.fr Jonathan Niles-Weed NYU jnw@cims.nyu.edu |
| Pseudocode | Yes | Pseudocode for our proposed algorithm is given in Algorithm 1. NYS-SINK (pronounced nice sink ) computes a low-rank Nyström approximation of the kernel matrix via a column sampling procedure. ... Algorithm 1 NYS-SINK |
| Open Source Code | No | The paper mentions comparing with optimized implementations in the Geom Loss library (http://www.kernel-operations.io/geomloss/), but it does not provide an explicit statement or link for the open-source code of the NYS-SINK algorithm developed in this paper. |
| Open Datasets | Yes | We measured Wasserstein distance between two 3D cloud points from the Stanford 3D Scanning Repository.2 (2http://graphics.stanford.edu/data/3Dscanrep/) |
| Dataset Splits | No | The paper mentions using |
| Hardware Specification | No | The paper states, 'We ran T = 20 iterations of our algorithm (Nys-Sink) with approximation rank r = 2000 on a GPU'. While it mentions 'a GPU', it does not provide specific details such as the model, CPU, memory, or other hardware components used. |
| Software Dependencies | No | The paper mentions comparing with optimized implementations in the 'Geom Loss' library, but it does not provide version numbers for this or any other software dependencies used for their own algorithm's implementation. |
| Experiment Setup | Yes | We ran T = 20 iterations of our algorithm (Nys-Sink) with approximation rank r = 2000 on a GPU... Each Nys-Sink experiment was repeated 50 times... Exp. 1 n = 3 10^5, d = 3, η = 15 W2 time (s) Nys-Sink r = 2000, T = 20... We ran two experiments, with n = 3 10^5 and n = 3.8 10^6 points, respectively. |