Publications (7)
Massively scalable Sinkhorn distances via the Nyström method
Jason Altschuler, Francis Bach, Alessandro Rudi +1
The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However,…
Approximating the Quadratic Transportation Metric in Near-Linear Time
Jason Altschuler, Francis Bach, Alessandro Rudi +1
Computing the quadratic transportation metric (also called the -Wasserstein distance or root mean square distance) between two point clouds, or, more generally, two discrete dis…
Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Jason Altschuler, Aditya Bhaskara, Gang Fu +3
The problem of column subset selection has recently attracted a large body of research, with feature selection serving as one obvious and important application. Among the technique…
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Jason Altschuler, Jonathan Weed, Philippe Rigollet
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduct…
Best Arm Identification for Contaminated Bandits
Jason Altschuler, Victor-Emmanuel Brunel, Alan Malek
This paper studies active learning in the context of robust statistics. Specifically, we propose a variant of the Best Arm Identification problem for \emph{contaminated bandits}, w…
Inclusion of Forbidden Minors in Random Representable Matroids
Jason Altschuler, Elizabeth Yang
In 1984, Kelly and Oxley introduced the model of a random representable matroid corresponding to a random matrix , whose entries are…