Uncoupled isotonic regression via minimum Wasserstein deconvolution

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 (xi, yi) where mathbbE[yi]=f(xi), 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 x1, ldots, xn and y1, ldots, yn. In this work, we leverage tools from optimal transport theory to derive minimax rates under weak moments conditions on yi 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.