Uncoupled isotonic regression via minimum Wasserstein deconvolution

Authors:

Abstract
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.
Funding Information
  • National Science Foundation (DGE-1122374, DMS-1712596, TRIPODS-1740751, IIS-183807)
  • Office of Naval Research (N00014-17-1-2147)
  • Silicon Valley Community Foundation (2018-182642)
  • Massachusetts Institute of Technology
  • Josephine De Karman Fellowship Trust

This publication has 27 references indexed in Scilit: