  We consider a variant of regression problem, where the correspondence between
input and output data is not available. Such shuffled data is commonly observed
in many real world problems. Taking flow cytometry as an example, the measuring
instruments may not be able to maintain the correspondence between the samples
and the measurements. Due to the combinatorial nature of the problem, most
existing methods are only applicable when the sample size is small, and limited
to linear regression models. To overcome such bottlenecks, we propose a new
computational framework -- ROBOT -- for the shuffled regression problem, which
is applicable to large data and complex nonlinear models. Specifically, we
reformulate the regression without correspondence as a continuous optimization
problem. Then by exploiting the interaction between the regression model and
the data correspondence, we develop a hypergradient approach based on
differentiable programming techniques. Such a hypergradient approach
essentially views the data correspondence as an operator of the regression, and
therefore allows us to find a better descent direction for the model parameter
by differentiating through the data correspondence. ROBOT can be further
extended to the inexact correspondence setting, where there may not be an exact
alignment between the input and output data. Thorough numerical experiments
show that ROBOT achieves better performance than existing methods in both
linear and nonlinear regression tasks, including real-world applications such
as flow cytometry and multi-object tracking.
