Unlinked monotone regression

We consider so-called univariate unlinked (sometimes \decoupled,"or \shuffled") regression when the unknown regression curve is monotone. In standard monotone regression, one observes a pair (X; Y ) where a response Y is linked to a covariate X through the model Y = m0(X) + ϵ, with m0 the (unknown) monotone regression function and ϵ the unobserved error (assumed to be independent of X). In the unlinked regression setting one gets only to observe a vector of realizations from both the response Y and from the covariate X where now Y d= m0(X) + ϵ. There is no (observed) pairing of X and Y . Despite this, it is actually still possible to derive a consistent non-parametric estimator of m0 under the assumption of monotonicity of m0 and knowledge of the distribution of the noise ϵ. In this paper, we establish an upper bound on the rate of convergence of such an estimator under minimal assumption on the distribution of the covariate X. We discuss extensions to the case in which the distribution of the noise is unknown. We develop a second order algorithm for its computation, and we demonstrate its use on synthetic data. Finally, we apply our method (in a fully data driven way, without knowledge of the error distribution) on longitudinal data from the US Consumer Expenditure Survey.