Uncoupled isotonic regression via minimum Wasserstein deconvolution
Preprint
Abstract
Isotonic regression is a standard problem in shape-constrained estimation where the goal is to estimate an unknown nondecreasing regression function $f$ from independent pairs $(x_i, y_i)$ where $\mathbb{E}[y_i]=f(x_i), i=1, \ldots n$. While this problem is well understood both statistically and computationally, much less is known about its uncoupled counterpart where one is given only the unordered sets $\{x_1, \ldots, x_n\}$ and $\{y_1, \ldots, y_n\}$. In this work, we leverage tools from optimal transport theory to derive minimax rates under weak moments conditions on $y_i$ and to give an efficient algorithm achieving optimal rates. Both upper and lower bounds employ moment-matching arguments that are also pertinent to learning mixtures of distributions and deconvolution.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- One-dimensional empirical measures, order statistics, and Kantorovich transport distancesMemoirs of the American Mathematical Society, 2019
- Entropic optimal transport is maximum-likelihood deconvolutionComptes Rendus Mathematique, 2018
- Unlabeled Sensing With Random Linear MeasurementsIEEE Transactions on Information Theory, 2018
- Optimal Transport for Applied Mathematicians2015
- Improved rates for Wasserstein deconvolution with ordinary smooth error in dimension oneElectronic Journal of Statistics, 2015
- Minimax rates of convergence for Wasserstein deconvolution with supersmooth errors in any dimensionJournal of Multivariate Analysis, 2013
- Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functionalThe Annals of Statistics, 2011
- Deconvolution for the Wasserstein metric and geometric inferenceElectronic Journal of Statistics, 2011
- On minimum Kantorovich distance estimatorsStatistics & Probability Letters, 2006
- On estimation of the L r norm of a regression functionProbability Theory and Related Fields, 1999