Title: Uncoupled isotonic regression via minimum Wasserstein deconvolution,
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.