A0512
Title: Large-scale entropy regularized optimal transport independence criterion
Authors: Lang Liu - University of Washington (United States) [presenting]
Soumik Pal - University of Washington (United States)
Zaid Harchaoui - University of Washington (United States)
Abstract: An independence criterion is introduced based on entropy regularized optimal transport (EOT). Its empirical estimator involves solving an EOT problem between two discrete distributions whose support size scales quadratically in the sample size $n$. This is computationally challenging since a na\"ive application of the popular Sinkhorn algorithm requires $O(n^4)$ time and space. For large-scale problems, we design a Tensor Sinkhorn algorithm equipped with a random feature type approximation, reducing the time complexity and space complexity to $O(n^2)$. We also offer a differentiable program implementation for deep learning applications, which allows one to run the reverse mode automatic differentiation through statistical quantities based on our criterion. We present experimental results on existing benchmarks for independence testing, illustrating the interest of the proposed criterion to capture both linear and nonlinear dependencies in synthetic data and real data.
