Isotonic regression

Function (biology)

Algorithm

Deconvolution

Biology

Discrete mathematics

Statistics

Minimax

Applied mathematics

Mathematical optimization

Classical mechanics

Evolutionary biology

Physics

Isotonic

Regression

Mathematics

Estimator

Leverage (statistics)

Internal medicine

Moment (physics)

Combinatorics

Matching (statistics)

Medicine

Information and Inference A Journal of the IMA

Isotonic regression is a standard problem in shape-constrained estimation where the goal is to estimate an unknown non-decreasing 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.

Uncoupled isotonic regression via minimum Wasserstein deconvolution