Uncoupled isotonic regression

The classical regression problem seeks to estimate a function f on the basis of independent pairs $(x_i,y_i)$ where $\mathbb E[y_i]=f(x_i)$, $i=1,\dotsc,n$. In this talk, we consider statistical and computational aspects of the "uncoupled" version of this problem, where one observes only the unordered sets $\{x_1,…,x_n\}$ and $\{y_1,…,y_n\}$ and still hopes to recover information about $f$. Under the assumption that $f$ is nondecreasing, we give minimax statistical rates under weak moment conditions on $y_i$ and provide an efficient algorithm achieving the optimal rates. Both upper and lower bounds employ moment-matching arguments based on optimal transport theory. Joint work with Philippe Rigollet.