290 citations · 467 across the 9 of their papers we have counts for
13 papers
Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem
Gonzalo Mena, Jonathan Weed
We prove several fundamental statistical bounds for entropic OT with the squared Euclidean cost between subgaussian probability measures in arbitrary dimension. First, through a ne…
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…
Entropic optimal transport is maximum-likelihood deconvolution
Philippe Rigollet, Jonathan Weed
We give a statistical interpretation of entropic optimal transport by showing that performing maximum-likelihood estimation for Gaussian deconvolution corresponds to calculating a…
An explicit analysis of the entropic penalty in linear programming
Jonathan Weed
Solving linear programs by using entropic penalization has recently attracted new interest in the optimization community, since this strategy forms the basis for the fastest-known…
Uncoupled isotonic regression via minimum Wasserstein deconvolution
Philippe Rigollet, Jonathan Weed
Isotonic regression is a standard problem in shape-constrained estimation where the goal is to estimate an unknown nondecreasing regression function from independent pairs $(x_…
Statistical Optimal Transport via Factored Couplings
Aden Forrow, Jan-Christian Hütter, Mor Nitzan +3
We propose a new method to estimate Wasserstein distances and optimal transport plans between two probability distributions from samples in high dimension. Unlike plug-in rules tha…
Minimax Rates and Efficient Algorithms for Noisy Sorting
Cheng Mao, Jonathan Weed, Philippe Rigollet
There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than par…
The sample complexity of multi-reference alignment
Amelia Perry, Jonathan Weed, Afonso S. Bandeira +2
The growing role of data-driven approaches to scientific discovery has unveiled a large class of models that involve latent transformations with a rigid algebraic constraint. Three…
Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
Jonathan Weed, Francis Bach
The Wasserstein distance between two probability measures on a metric space is a measure of closeness with applications in statistics, probability, and machine learning. In this wo…
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…
Approximately certifying the restricted isometry property is hard
Jonathan Weed
A matrix is said to possess the Restricted Isometry Property (RIP) if it acts as an approximate isometry when restricted to sparse vectors. Previous work has shown it to be NP-hard…
Further results on arc and bar k-visibility graphs
Mehtaab Sawhney, Jonathan Weed
We consider visibility graphs involving bars and arcs in which lines of sight can pass through up to k objects. We prove a new edge bound for arc k-visibility graphs, provide maxim…
Online learning in repeated auctions
Jonathan Weed, Vianney Perchet, Philippe Rigollet
Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) inform…