2018

Minimax Distribution Estimation in Wasserstein Distance

Singh, Shashank, Póczos, Barnabás

Understand

The Wasserstein metric is an important measure of distance between probability distributions, with applications in machine learning, statistics, probability theory, and data analysis.

This paper provides upper and lower bounds on statistical minimax rates for the problem of estimating a probability distribution under Wasserstein loss, using only metric properties, such as covering and packing numbers, of the sample space, and weak moment assumptions on the probability distributions.

Built on

On the translocation of masses
Leonid Vitalievich Kantorovich · 1942
Earlier work this paper cites.
Markov processes and the H-theorem
Tetsuzo Morimoto · 1963
Earlier work this paper cites.
Eine informationstheoretische ungleichung und ihre anwendung auf beweis der ergodizitaet von markoffschen ketten
Imre Csiszár · 1964
Earlier work this paper cites.
A general class of coefficients of divergence of one distribution from another
Syed Mumtaz Ali and Samuel D Silvey · 1966
Earlier work this paper cites.
The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
Richard M Dudley · 1967
Earlier work this paper cites.
The speed of mean Glivenko-Cantelli convergence
RM Dudley · 1969
Earlier work this paper cites.
Quantization and the method of k k -means
David Pollard · 1982
Earlier work this paper cites.
On optimal matchings
Miklós Ajtai, János Komlós, and Gábor Tusnády · 1984
Earlier work this paper cites.
The Wasserstein distance and approximation theorems
Ludger Rüschendorf · 1985
Earlier work this paper cites.
Bayesian inference in econometric models using monte carlo integration
John Geweke · 1989
Earlier work this paper cites.
Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
Tom Leighton and Peter Shor · 1989
Earlier work this paper cites.
Empirical processes: theory and applications
David Pollard · 1990
Earlier work this paper cites.
Minimax grid matching and empirical measures
Peter W Shor, Joseph E Yukich, et al · 1991
Earlier work this paper cites.
Constructive approximation , volume 303
Ronald A DeVore and George G Lorentz · 1993
Earlier work this paper cites.
Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension
David Haussler · 1995
Earlier work this paper cites.
Central limit theorems for the Wasserstein distance between the empirical and the true distributions
Eustasio del Barrio, Evarist Giné, and Carlos Matrán · 1999
Earlier work this paper cites.
A wavelet tour of signal processing
Stéphane Mallat · 1999
Earlier work this paper cites.
Nearest q q -flat to m m points
Paul Tseng · 2000
Earlier work this paper cites.
Covering number bounds of certain regularized linear function classes
Tong Zhang · 2002
Earlier work this paper cites.
The covering number in learning theory
Ding-Xuan Zhou · 2002
Earlier work this paper cites.
Correction: Central limit theorems for the Wasserstein distance between the empirical and the true distributions
Eustasio del Barrio, Evarist Giné, Carlos Matrán, et al · 2003
Earlier work this paper cites.
Central limit theorem and convergence to stable laws in Mallows distance
Oliver Johnson, Richard Samworth, et al · 2005
Earlier work this paper cites.
On minimum Kantorovich distance estimators
Federico Bassetti, Antonella Bodini, and Eugenio Regazzini · 2006
Earlier work this paper cites.

Similar

A new method of normal approximation
Sourav Chatterjee et al · 2008
Cited alongside, same era.
An elementary proof of the triangle inequality for the Wasserstein metric
Philippe Clement and Wolfgang Desch · 2008
Cited alongside, same era.
Optimal transport: old and new , volume 338
Cédric Villani · 2008
Cited alongside, same era.
Stochastic processes with applications , volume 61
Rabi N Bhattacharya and Edward C Waymire · 2009
Cited alongside, same era.
Upper bounds for minimal distances in the central limit theorem
Emmanuel Rio et al · 2009
Cited alongside, same era.
Introduction to nonparametric estimation
Alexandre B Tsybakov · 2009
Cited alongside, same era.
Normal approximation by Stein’s method
Louis HY Chen, Larry Goldstein, and Qi-Man Shao · 2010
Cited alongside, same era.
Non-parametric estimation of integral probability metrics
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet · 2010
Cited alongside, same era.
Sublinear time algorithms for earth mover’s distance
Khanh Do Ba, Huy L Nguyen, Huy N Nguyen, and Ronitt Rubinfeld · 2011
Cited alongside, same era.
The numerical tours of signal processing
Gabriel Peyré · 2011
Cited alongside, same era.
Asymptotic constants for minimal distance in the central limit theorem
Emmanuel Rio et al · 2011
Cited alongside, same era.
Learning probability measures with respect to optimal transport metrics
Guillermo Canas and Lorenzo Rosasco · 2012
Cited alongside, same era.

Then

k k -means algorithms for functional data
María Luz López García, Ricardo García-Ródenas, and Antonia González Gómez · 2015
Later among the works it cites.
Minimax estimation of discrete distributions under ℓ 1 \ell_{1} loss
Yanjun Han, Jiantao Jiao, and Tsachy Weissman · 2015
Later among the works it cites.
On the rate of convergence of empirical measures in ∞ \infty -transportation distance
Nicolás Garcia Trillos and Dejan Slepčev · 2015
Later among the works it cites.
The estimation of Wasserstein and Zolotarev distances to the class of exponential variables
Original
Amparo Baíllo, Javier Cárcamo, and Konstantin V Getman · 2016
Later among the works it cites.
Distributionally robust stochastic optimization with Wasserstein distance
Original
Rui Gao and Anton J Kleywegt · 2016
Later among the works it cites.
Wasserstein training of restricted Boltzmann machines
Grégoire Montavon, Klaus-Robert Müller, and Marco Cuturi · 2016
Later among the works it cites.
Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers
Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan J Tibshirani · 2016
Later among the works it cites.
Wasserstein generative adversarial networks
Martin Arjovsky, Soumith Chintala, and Léon Bottou · 2017
Later among the works it cites.
Generalization and equilibrium in generative adversarial nets (gans)
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang · 2017
Later among the works it cites.
Inference in generative models using the Wasserstein distance
Original
Espen Bernton, Pierre E Jacob, Mathieu Gerber, and Christian P Robert · 2017
Later among the works it cites.
What happens to a manifold under a bi-lipschitz map?
Armin Eftekhari and Michael B Wakin · 2017
Later among the works it cites.
Improved training of Wasserstein GANs
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville · 2017
Later among the works it cites.
Multilevel clustering via Wasserstein means
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung · 2017
Later among the works it cites.
Minimax estimation of the l 1 l_{1} distance
Original
Jiantao Jiao, Yanjun Han, and Tsachy Weissman · 2017
Later among the works it cites.
How well can generative adversarial networks (GAN) learn densities: A nonparametric view
Original
Tengyuan Liang · 2017
Later among the works it cites.
Gradient descent GAN optimization is locally stable
Original
Vaishnavh Nagarajan and J Zico Kolter · 2017
Later among the works it cites.
Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
Original
Jonathan Weed and Francis Bach · 2017
Later among the works it cites.
Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces
Original
Jing Lei · 2018
Closest in time.
Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks
Original
Tengyuan Liang and James Stokes · 2018
Closest in time.
On the rate of convergence of empirical measure in ∞ \infty -Wasserstein distance for unbounded density function
Original
Anning Liu, Jian-Guo Liu, and Yulong Lu · 2018
Closest in time.
Nonparametric density estimation under adversarial losses
Shashank Singh, Ananya Uppal, Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnabás Póczos · 2018
Closest in time.
A variational approach to the consistency of spectral clustering
Nicolas Garcia Trillos and Dejan Slepčev · 2018
Closest in time.
Nonparametric density estimation under besov ipm losses
Original
Ananya Uppal, Shashank Singh, and Barnaás Póczos · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…