Stochastic EM for Shuffled Linear Regression
  We consider the problem of inference in a linear regression model in which
the relative ordering of the input features and output labels is not known.
Such datasets naturally arise from experiments in which the samples are
shuffled or permuted during the protocol. In this work, we propose a framework
that treats the unknown permutation as a latent variable. We maximize the
likelihood of observations using a stochastic expectation-maximization (EM)
approach. We compare this to the dominant approach in the literature, which
corresponds to hard EM in our framework. We show on synthetic data that the
stochastic EM algorithm we develop has several advantages, including lower
parameter error, less sensitivity to the choice of initialization, and
significantly better performance on datasets that are only partially shuffled.
We conclude by performing two experiments on real datasets that have been
partially shuffled, in which we show that the stochastic EM algorithm can
recover the weights with modest error.
