A Hypergradient Approach to Robust Regression without Correspondence

Abstract

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.

References in corpus (17)

• Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks
• Simple Online and Realtime Tracking
• MOT16: A Benchmark for Multi-Object Tracking
• MOT20: A benchmark for multi object tracking in crowded scenes
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance
• Linear regression without correspondence
• Linear Regression with Shuffled Labels
• Signal Recovery from Unlabeled Samples
• A new optimal transport distance on the space of finite Radon measures
• Linear Regression without Correspondences via Concave Minimization
• How To Train Your Deep Multi-Object Tracker
• Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints
• Differentiable Top-k Operator with Optimal Transport
• Homomorphic Sensing
• A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data
• Robust approximate linear regression without correspondence