A Hypergradient Approach to Robust Regression without Correspondence
Authors: Yujia Xie
Yixiu Mao
Simiao Zuo
Hongteng Xu
Xiaojing Ye
Tuo Zhao
Hongyuan Zha
Venue: ICLR 2021 Poster (2021)
Keywords: Regression without correspondence
differentiable programming
first-order optimization
Sinkhorn algorithm

Abstract: We consider a regression problem, where the correspondence between the input and output data is not available. Such shuffled data are commonly observed in many real world problems. Take flow cytometry as an example: the measuring instruments are unable to preserve the correspondence between the samples and the measurements. Due to the combinatorial nature of the problem, most of the existing methods are only applicable when the sample size is small, and are 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 models. Specifically, we propose to formulate regression without correspondence as a continuous optimization problem. Then by exploiting the interaction between the regression model and the data correspondence, we propose to develop a hypergradient approach based on differentiable programming techniques. Such a hypergradient approach essentially views the data correspondence as an operator of the regression model, and therefore it allows us to find a better descent direction for the model parameters by differentiating through the data correspondence. ROBOT is quite general, and can be further extended to an inexact correspondence setting, where the input and output data are not necessarily exactly aligned. 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.  

particular target (Abid & Zou| 2018). Through this process, cells are suspended in fluid and injected into the flow cytometer, where measurements are taken using the scattering of a laser. However, the instruments are unable differentiate the cells passing through the laser, such that the correspondence between the cell proprieties (i.e., the measurements) and the cells is unknown. This prevents us from analyzing the relationship between the instruments and the mea- surements using classical regression analysis, due to the missing correspondence. Another example is multi-object tracking, where we need to infer the motion of objects given consecutive frames in Published as a conference paper at ICLR 2021
A HYPERGRADIENT APPROACH TO ROBUST REGRESSION WITHOUT CORRESPONDENCE
Yujia Xie; Yixiu Mao; Simiao Zuo, Hongteng Xu, Xiaojing Ye,
Tuo Zhao, Hongyuan Zha
ABSTRACT
We consider a 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 in- struments unable preserve the correspondence between the samples and the measurements. Due to the combinatorial nature, most of existing methods are only applicable when the sample size is small, and limited models. To overcome such bottlenecks, we propose a new computational frame- work ROBOT- for the shuffled regression problem, which is applicable to large data and complex models. Specifically, we propose to formulate the regression without correspondence as a continuous optimization problem. Then by exploit- ing the interaction between the regression model and the data correspondence, we propose to develop a hypergradient approach based on differentiable program- ming techniques. Such a hypergradient approach essentially views the data cor- respondence 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 is quite general, and can be further extended to the inexact correspondence setting, where the input and output data are not necessar- ily exactly aligned. 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 eytometry and multi-object tracking.
linear regression
INTRODUCTION
Regression analysis has been widely used in various machine learning applications to infer the the relationship between explanatory random variable (i.e., the input) X E RRd and response random variable (i.e., the output) Y E Ro (Stanton] 200T). In the classical setting, regression is used on labeled datasets that contain paired samples (: where Vi, Yi are realizations of X, Y, respectively.
Unfortunately, such onput-output correspondence is not always available in some applications. One example is flow cytometry, which is a physical experiment for measuring properties of cells, e.g., affinity
'Equal Contributions.
Yujia Xie, Simiao Zuo, Tuo Zhao are affiliated with Georgia Institute of Technology. Emails: [xieyujia, simiaozuo, courzhao]@gatenn Tong University. Email: 056985044myx8@mmn
edu. Yixiu Mao is affiliated with Shanghai Jiao com. Hongteng Xu is affiliated with Gaoling School of Artificial Intelligence, Renmin University of China, and Beijing Key Laboratory of Big Data Manage- ment and Analysis Methods. Email: hongtengxu@rus ruc. edu. en. Xiaojing Ye is affiliated with Georgia State University. Email: xyeêgsu. edu. Hongyuan Zha is affiliated with School of Data Science Shenzhen Institute of Artificial Intelligence and Robotics for Society, the Chinese University of Hong Kong, Shenzhen. Email: zhahyEcuht edu.en.

---

Published as a conference paper at ICLR 2021
video. This requires us to find the correspondence between the objects in the current frame and those in the next frame.
The two examples above can be formulated as shuffled regression problem. Specifically, we sider a multivariate regression model
= Zx +
where X E R. Z E R are two input vectors, Y E R is output vector, f Réte - R is the unknown regression model with parameters w and E is the random noise independent on X and Z. When we sample realizations from such regression model, the correspondence between (X, Y) and Z is not available. Accordingly, we collect two datasets D = {z,, 9i J==1 and D2 = {zy j= and there exists a permutation x² such that (Ii *=(i)) corresponds to yi in the regression model. Our goal recover the unknown model parameter w. Existing literature also refer to the shuffled regression problem as unlabeled sensing, homomorphic sensing, and regression with an unknown permutation Unnikrishnan et al. 2018). Throughout the rest of the paper, we refer to as Regression WithOut Correspondence (RWOC).
natural choice of the objective for RWOC is to minimize the sum of squared residuals with respect to the regression model parameter w up to the permutation TT-) over the training data, i.e.,
min Lww, π Σm 11y - f (I., (x); w) 13.
Existing works RWOC mostly focus on theoretical properties of the global optima to equation
for estimating w and x (Pananjady et al. 2016; 2017b] Abid et al. 2017, Elhami et al.] 2017
Hsu al. 2017 Unnikrishnan al. 20118 Tsakiris & Peng 2019). The development of practical
algorithms, however, falls far behind from the following three aspects:
Most of the works are only applicable to linear regression models.
Some of the existing algorithms are of very high computational complexity, and can only handle small number of data points in low dimensions (Elhami al.) 2017 Pananjady et al. 2017aa Tsakiris iet al. 2018 Peng & Tsakiris 2020). For example, Abid & Zou (2018) adopt an Expectation Maxi- mization (EM) method where Metropolis-Hastten
sampling is needed, which is not scalable. Other algorithms choose to optimize with respect to w and ı in an alternating manner, e.g., alternating minimization in Abid et al. (2017). However, as there exists strong interaction between and æ, the optimization landscape of equation is ill-conditioned. Therefore, these algorithms are not effective and often get stuck in local optima.
Most of the works only consider the case where there exists an exact one-to-one correspondence between D1 and D2. For many more scenarios, however, these two datasets are not necessarily well aligned. For example, consider Dj and D2 collected from two separate databases, where the users overlap, but are not identical. As a result, there exists only partial one-to-one correspondence. A similar situation also happens to multiple-object tracking: Some objects may leave the scene in one frame, and new objects may enter the scene in subsequent frames. Therefore, not all objects in different frames can be perfectly matched. The RWOC problem with partial correspondence is known as robust-RWOC, or rRWOC (Varol & Nejatbakhsh 2019), and is much less studied in existing literature.
To address these concerns, we propose a new computational framework - ROBOT (Regression withOut correspondence using Bilevel OptimizaTion). Specifically, we propose formulate the regression without correspondence as a continuous optimization problem. Then by exploiting the interaction between the regression model and the data correspondence, we propose develop a hypergradient approach based on differentiable programming techniques (Duchi et al. [0088] Luise ett al. 2018). Our hypergradient approach views the data correspondence as an operator of the regression, i.c., for a given w, the optimal correspondence is
f(w) = arg min, L(w, .T.
(2)
Accordingly, when applying gradient descent to (I). we need to find the gradient with respect to w by differentiating through both the objective function L and the data correspondence ((w). For simplicity, we refer such a gradient to "hypergradient" Note that due to its discrete nature, (w) is actually not continuous in w. Therefore, such hypergradient does not exist. To address this issue, we further propose construct smooth approximation of ((w) ) by adding additional regularizer to equation 2 and then we replace ((w with our proposed smooth replacement when computing the hyper gradient of w. Moreover, we also propose an efficient and scalable implementation of
2

---

Published as a conference paper at ICLR 2021
hypergradient computation based simple first order algorithms and implicit differentiation, which outperforms conventional automatic differentiation in terms time and memory cost.
ROBOT can also be extended to the robust RWOC problem, where D1 and D2 are not necessarily exactly aligned, i.c., some data points in D1 may not correspond to any data point in D2. Specifically, relax the constraints the permutation (.) (Liero et al. 2018) automatically match related data points and ignore the unrelated ones.
At last, we conduct thorough numerical experiments to demonstrate the effectiveness of ROBOT. For RWOC (i.e., exact correspondence), we use several synthetic regression datasets and a real gated flow cytometry dataset, and show that ROBOT outperforms baseline methods by significant margins. For robust RWOC (i.e., inexact correspondence), in addition to synthetic datasets, we consider a rision-based multiple-object tracking task, and then we show that ROBOT also achieves significant improvement over baseline methods.
Notations. Let 11- denote the l norm of vectors, (.-)) the inner product of matrices, i.e., (A, B) Σ,g Ai Bi, for matrices A and B. Os:j are the entries from index i to index j of vector a. Let 1,
denote an n-dimensional vector of all ones. Denote
d()) the gradient of scalars, and (-)(.) the d(-)
Jacobian of tensors. We denote [vi, [2] the concatenation of two vectors ia and U2. (N, o²) ) the Gaussian distribution with mean f and variance o².
ROBOT: A HYPERGRADIENT APPROACH FOR RWOC
We develop our hypergradient approach for RWOC. Specifically, we first introduce continuous formulation equivalent to [ and then propose a smooth bi-level relaxation with an efficient hyper- gradient descent algorithm.
2.1 EQUIVALENT CONTINUOUS FORMULATION
We propose a continuous optimization problem equivalent to Specifically, we rewrite an equiv- alent form of [ as follows,
min, minSEROK> C(w, S) = (C(w), S) subject to SeP,
(3)
where P denotes the set of all permutation matrices, C(w) [R"x" is the loss matrix with Ci)(w)= = Ia - f (zi, zy: w) 112.
Note that we can relax E P, which is the discrete feasible set of the inner minimization problem of 3). to convex set, without affecting the optimality, suggested by the next theorem. Proposition 1. Given any a E IR" and b E RT, we define
Ia b) {A Raxm Al a, A = b, A.j 2 0).
The optimal solution the inner discrete minimization problem of B is also the optimal solution to the following continuous optimization problem.
min (C((w) S), s.t. S [I,,,, 1.).
(4)
This is direct corollary of the Birkhoff-von Neumann theorem (Birkhoff 1946 Von Neumann 1953), and please refer to Appendix A for more details. Theorem I allows to replace P in (3) with II(,,, In), which is also known as the Birkhoff polytope Ziegler 2012). Accordingly, we obtain the following continuous formulation,
min,, minSeR SC subject to S E [T(1,, 1,).
Remark 1. In gquaton, 3 can be solved by linear programming algorithms (Dantzig 1998
2.2 CONVENTIONAL WISDOM: ALTERNATING MINIMIZATION
Conventional wisdom for solving
5 suggests to use alternating minimization (AM, Abid et al.
2017 Specifically, at the k-th iteration, we first update S by solving
S(k) arg min (( 1), 1)S).
and then given 5(k), we update w using gradient descent or exact minimization, i.e.,
(R) (k-1) V/ (( g(k)).
However, AM works poorly for solving (5) practice. This is because w and S have strong
interaction throughout the iterations: A slight change to may lead to significant change to S. Therefore, the optimization landscape ill- ill-conditioned, and AM can easily get stuck at local optima.
This common practice in integer programming Marcus & Ree 1959
3

---

Published as a conference paper at ICLR 2021
2.3 SMOOTH BI-LEVEL RELAXATION
To tackle the aforementioned computational challenge, we propose hypergradient approach, which can better handle the interaction between w and S. Specifically, we first relax ( to smooth bi- level optimization problem, and then we solve the relaxed bi-level optimization problem using the hypergradient descent algorithm.
We rewrite ( as a smoothed bi-level optimization problem,
min F.( (C(w), (w)), subject S Su(w) arg mnn (S)) (6)
where H(S) = (log S, S) is the entropy of S. The regularizer H(S) in equation alleviates the sensitivity of 5 (w) w. Note that if without such regularizer, we solve
(w) = arg minsennt,....
(7)
The resulting S (w) can be discontinuous in w. This is because 5*(w) is the optimal solution of linear optimization problem, and usually lies on vertex of [I, 1,). This means that if we change w, S*(w) either stays the same or jumps to another vertex of II 1p). The jump makes S (www) highly sensitive to w. To alleviate this issue, we propose smooth S (w) by adding an entropy regularizer to the lower level problem. The entropy regularizer enforces (www) to stay in the interior of [I In), and (w) changes smoothly with respect to w, as suggested by the following theorem.
Theorem 1. For any 6 > 0, (w) is differentiable, the cost C(w) is differentiable with respect to w. Consequently, the objective (w) = 55 (w)) is also differentiable.
The proof is deferred to Appendix C Note that (6) provides us a new perspective to interpret the relationship between wo and S. As can be seen from 6). w and S have different priorities: the parameter of the leader problem, which is of the higher priority; S is the parameter of the follower problem, which is of the lower priority, and can also be viewed as an operator of w denoted by S. (w). Accordingly, when we minimize (6) with respect to w using gradient descent, we should also differentiate through S We refer to such a gradient as "hypergradient" defined as follows.
V.F((w)= (w)) aC(w) (w)) (S)(w) aC(w) dw + (w) Dw VwL(w, S) + (F.(w) 05, (w)
as; (w) dw
We further examine the alternating minimization algorithm from the bi-level optimization perspec- tive: Since (w ((() not differentiable through 5((), AM is essentially using an inexact gradient. From a game-theoretic perspective (6) defines a competition between the leader and the follower 5. When using AM, S only reacts what w has responded. In contrast, when using the hypergradient approach, the leader essentially recognizes the follower's 's strategy and reacts to
aF. 0.57 (1) what the follower is anticipated to response through 85; (wr) descent direction for w.
In this way, we can find better 8
Remark 2. We use a simple example of quadratic minimization to illustrative why we expect the bilevel optimization formulation in (6) to enjoy a benign optimization landscape. We consider a quadratic function
(8) where a Rd, 02 Rd:, a = (u1,u2], P E Rdd++ds)x(( E Rdi+ds Let P = pla,+d, +do + (1 +dd, where Iditd, is the identity matrix, and p is a constant. We solve the following bilevel optimization problem.
L(a1, 02) T
Pa +Taa
ming, F(az)= L(a),a)(a;)) subject a5(a1) arg mig, L(a a2) Al|az112 (9)
where À is regularization coefficient. The next proposition shows that V F²F((a) enjoys smaller condition number than V2 L(a1, 02), which corresponds to the problem that AM solves.
Proposition 2. Given F defined (9), we have
p Amax. V ((2((a)) 1 d2p - p -+ Amin (22((a))
dip T-p and
Amaax (V2 Vay I(ai, 02)) 1 dip
Xmin (V2, [(ai,u2))
The proof is deferred to Appendix B.1
As suggested by Proposition 2 F(a1) much better- conditioned than L(a,, a²) in terms of a for high dimensional settings.
The bilevel formulation can he viewed Stackelberg game.
4

---

Published as a conference paper at ICLR 2021
2.4 SOLVING RWOC BY HYPERGRADIENT DESCENT
We present how solve o using our hypergradient approach. Specifically, we compute the "hy- pergradient" of Fe F(()) based on the following theorem.
Theorem 2. The gradient of Fc with respect to w is
7,
VwFF(W)
(1 (1-Ci))
Σ
CheS
+
CheSaneees A,E=1
VoCis. (10)
é i,j=
A.E=1
The definition of P and Q and the proof is deferred to Appendix solve the lower level problem (6)
Theorem suggests that first
S arg min (elt (C(w), +
(11)
and then substitute S: into to obtain (w.).
Note that the optimization problem in 11 can be efficiently solved by variant of Sinkhorn al- 2015). Specifically, (TT) I can formulated as an entropic optimal transport (EOT) problem (Monge] [781] [ Kantorovich] 1960), which aims to find the optimal
gorithm (Cuturi 2013 Benamou al.,
way to transport the mass from a categorical distribution with weight μ = [ui...., Pn] to another categorical distribution with weight v = [M,,..., pm]].
| = arg minrem (M,1) + +L)
(12)
with I1, v) {T Rexm Ilm μr, I T 1, v, Fij 2 0),
where M Re is the matrix with Maj the transport cost. When we the two categorical distributions as the empirical distribution of DD and D2, respectively.
M C and ja = v = 1n/n,
one can verify that (12) is scaled lower problem of (6), and their optimal solutions satisfies S nI" Therefore, we can apply Sinkhorn algorithm to solve the EOT problem in equation 12 At the L-th iteration, take
p ((et1)=
1 and g(++1) GT p((2)) where (0)) 1,, and G.ş cxp Gyle)
V
(-Cu(u)) e
n
GE IRnn, and the division here is entrywise. Let px and gº denote the stationary points. Then we obtain S²,,0 =np,Geyg Gejaj.
Remark 3. The Sinkhorn algorithm is iterative and cannot exactly solve [1] within finite steps. As the Sinkhorn algorithm is very efficient and attains linear convergence, it suffices to well approxi- mate the gradient V (ww) using the output inexact solution.
3 ROBOT FOR ROBUST CORRESPONDENCE.
We next propose a robust version of ROBOT to solve rRWOC (Varol Nejatbakhsh 2019). Note that in (6). the constraint S E 11(1,, 1n) enforces one-to-one matching between 2, and D2. For rRWOC, however, such an exact matching may not exist. For example, we have n < m, where [Di], = [Dzl_ Therefore, need to relax the constraint on S.
Motivated by the connection between 6 and 12), we propose to solve the lower problem
(S) ,", -arg miggmimsemp..r (C(w), S) + +HH(S),
(13)
subject to ju 1, = n, 1m = m, |1 - 1 S Pr, || 1 1m p2, where (w) E Raxm denotes an inexact correspondence between D and D22- As can be seen 13). we relax the marginal constraint II(1, 1) (6) to 11(z, 7). where μ,, 8 are required to not deviate much from 1. Problem (13 relaxes the marginal constraints 1I(1, 1) in the original problem [ 7), where μ,, D are picked such that they do not deviate too much from Illustrative examples of the exact and robust alignments are provided in Figure
'The idea inspired by the marginal relaxation of optimal transport. first independently proposed by Kon- dratyev al. (2016) and Chizat al. (2018)), and later developed by Chizat al. (011c)) Licro al. (018))
Chizat et al. (018b)) share same formulation as ours.
Heere we measure the deviation using the Fuclidean distance, and more detailed discussions can be found
Appendix
5

---

Published as a conference paper at ICLR 2021
Computationally, 13 can be solved by taking the Sinkhorn iteration and the projected gradient iteration an alternating manner (See more details in Appendix D Given S, (w), we solve the upper level optimization in (6) to obtain w² i.c.,
e arg min (C(w), (C(w),
Similar to the previous section, we use first-order algorithm to solve this problem, and we derive explicit expressions for the update rules. See Appendix B for details.
0.21 0.22
0.49 9.61
0.77
10.87 10.82
0.21 0.22
0.49 061
D.77
10.87 10.92
0.08 0.19 0.30 0.64 0.52
0.76
0.08 0.19 0.30 0.44 0.52
0.74
(a) Original
(b) Robust
Figure 1: Illustrative example of exact (L. and robust (R) alignments. The robust alignment can drop potential outliers and only match data points close to each other.
EXPERIMENT
0.020
0.04
We evaluate ROBOT and ROBOT- robust on both synthetic and real- world datasets, including flow cy- tometry and multi-object tracking. We first present numerical results and then we provide insights in the discussion section. Experiment de- tails and auxiliary results can be found in Appendix
1.5
0.015
0.03
Rel. Error
RS
0.010
0.02
ROBUTT
0.01
0.00
e=5 c= 10 20
SWR
100
SNR
1000
(a) Puolse = 0.1
(b) c
10
Figure 2: Unlabeled sensing. Results are the mean over 10
runs. SNR= ||0||// Phoise is the signal-to-nois to-soise ratio.
4.1 UNLABELED SENSING
Data Generation. We follow the unlabeled sensing setting Tsakiris & Peng 2019) and generate n 1000 data points {[yi, 2)) where 2 E R. Note here we take = 0. We first generate 2, w ~ (O,.. Ie), and E ~ (hoiee)) Then we compute y = 2, w+ We randomly permute the order of 50% of that lose the Z-to-y correspondence. We generate the test set in the same way, only without permutation.
Baselines and Training. We consider the following scalable methods:
1. Oracle: Standard linear regression where no data are permuted.
2. Least Squares (LS): Standard linear regression, i.e., treating the data as if they are not permuted.
3. Alternating Minimization (AM, Abid et al. (2017)): We iteratively solve the correspondenec given w, and update w using gradient descent with the correspondence.
4. Stochastic EM (Abid & Zou 2018): stochastic EM approach to recover the permutation.
5. Robust Regression (RR, Slawski & Ben-David (2019); Slawski et al. (2019)).. A two-stage block coordinate descent approach to discard outliers and fit regression models.
6. Random Sample (RS, Varol & Nejatbakhsh (2019)) random sample consensus (RANSAC) approach estimate W.
We initialize AM, EM and ROBOT using the output of RS with multi-start. We adopt linear model f(Z: w) = Z w. Models are evaluated by the relative error on the test set, i.c., error = (. y;)3 Σ, (v= ?) where is the predicted label, and is the mean of (us).
Results. We visualize the results in Figure all the experiments, ROBOT achieves better results than the baselines. Note that the relative error is larger for all methods except Oracle the dimen- sion and the noise increase. For low dimensional data, e.g., = 5, our model achieves even better performance than Oracle. We have more discussions using RS as initializations Appendix G.5
4.2 NONLINEAR REGRESSION
Data Generation. We mimic the scenario where the dataset is collected from different platforms. Specifically, we generate n data points {1,, [x,, 2x]) 2 where 2; E Rd and 2 E R We first generate F; N (Oa, Ia), 2; No Ie), N Ia=e), and e NO, phoise) Then

---

Published as a conference paper at ICLR 2021
0.0
RRtalRRl Emor
0.0
-0.5
-0.5
0.3
-10
-10
1.0
Oracle
-1.5
-15
-1.5
LS
-2.0
-2.0
-2.0
ROBOT
-25
-2.
ROBOT-robust
10
100
500 1000 2000
0.1
0.2
0.5
Phane
Figure 3: Nonlinear regression. We use n. 1000, d = 2, e = 3, Puoise 0.1 as defaults.
compute y/ = f([2;, w) + E Next, we randomly permute the order of {2+} so that lose the data correspondence. Here, D1 = { yi}} and D.2 = {2₃} mimic two parts of data collected from two separate platforms. Since data from platform two, i.e., D2, as well as 80% of data in D, as the training data. The remaining data from D the test data. Notice that have different number of data on Dj and D2, i.e., the correspondence is not exactly one-to-one.
interested in the response on platform one, treat all
Baselines and Training. We consider a nonlinear function f(X, w) - =
k== sin ([X, w)aw)).
In this case, we consider only two baselines Oracle and LS, since the other baselines in the previous section are designed for linear models. We evaluate the regression models by the transport cost divided by (y+ 7)² on the test set.
Results. As shown in Figure 3 ROBOT-robust consistently outperforms ROBOT and LS, demon- strating the effectiveness of our robust formulation. Moreover, ROBOT-robust achieves better per- formance than Oracle when the number of training data is large when the noise level is high.
4.3 FLOW CYTOMETRY
2.00
0.080
1.75
0.075
Hard EM
In flow cytometry (FC), a sample containing particles is suspended in a fluid and injected into the flow cy- tometer, but the measuring instruments are unable pre- serve the correspondence between the particles and the measurements. Different from FC, gated flow eytometry (GFC) uses "gates" to sort the particles into one of many bins, which provides partial ordering information since the measurements are provided individually for each bin. In practice, there are usually 3 or 4 bins.
1.50
0.070
Stochastic EM
0.065
ROBOT
1.00
0.060-
Oracie
0.75
0.055
0.50
0.050
0.045
0.25
0.040
#group-3 3 #group-4
(a) FC
(b) GFC
Figure 4: methods.
Relative error of different
Settings. We adopt the dataset from Knight et al. (2009) Following Abid et al. (2017). 7). the outputs y/ 's are normal-
ized, and we select the top 20 significant features by a linear regression the top 1400 items in the dataset. We use 90% of the data as the training data, and the remaining as test data. For ordinary FC, we randomly shuffle all the labels in the training the labels, and then divided into equal-sized groups, mimicking the sorting by gates process. The labels in each group are then randomly shuffled. To simulate gating error, 1% of the data are shuf- fled across the groups We compare ROBOT with Oracle, LS, Hard EM (a variant of Stochastic EM proposed in Abid & Zou (018)), Stochastic EM, and AM. We use relative error on the test set as the evaluation metric.
For GFC, the training set is first sorted by
Results. As shown in Figure 4 while AM achieves good performance on GFC when the number of groups is 3, it behaves poorly on the FC task. ROBOT, on the other hand, is efficient on both tasks.
4.4 MULTI-OBJECT TRACKING
In this section we extend our method to vision-based Multi-Object Tracking (MOT), task with broad applications in mobile robotics and autonomous driving, to show the potential of applying RWOC to more real-world tasks. Given video and the current frame, the goal of MOT is to predict the locations of the objects in the next frame. Specifically, object detectors (Felzenszwalb eet al. 2009 Ren al., 2015) first provide us the potential locations of the objects by their bounding boxes. Then, MOT aims to assign the bounding boxes to trajectories that describe the path of individual objects over time. Here, we formulate the current frame and the objects' locations in the current frame as D2 = {2z}. while we treat the next frame and the locations in the next frame as
D2 {(x,, 9:)).
7

---

Published as a conference paper at ICLR 2021
Table 1: Experiment results on MOT.
Data
Method
MOTA
MОTP*
IDFI
MT
MLJ
FP4
FNL
IDS1
ROBOT
48.3
82.6
55.3
407
553
22,443
149,988
1,811
MOT17 (train)
w/o ROBOT
44.0
81.3
49.9
404
550
36,187
149,131
3,204
ROBOT
48.2
76.6
43.4
455
904
29,419
259,714
3,228
MOT17 (dev)
w/o ROBOT
42.1
75.0
36.8
414
890
61,210
259,318
6.138
SORT
43.1
77.8
39.8
295
997
28,398
287,582
4,852
ROBOT
56.2
84.9
47.6
805
288
113,752
377,247
5,888
MOT20 (train)
w/o ROBOT
48.8
81.5
40.2
769
290
186,245
384,562
10,153
ROBOT
45.0
76.9
34.0
394
257
70,416
210,425
3,683
MOT20 (dev)
w/o ROBOT
38.5
75.1
27.0
383
233
104,958
207.627
5,696
SORT
42.7
78.5
45.1
208
326
27,521
264,694
4,470
Existing deep learning based MOT algorithms require large amounts of annotated data, i.e., the ground truth of the correspondence, during training. Different from them, our algorithm does not require the correspon- dence between D1 and D2, and all we need is the video. This task referred as unsupervised MOT (He et al., 2019).
Related Works. To the best of our knowledge, the only method that accomplishes unsupervised end-to- end learning of MOT is He et al. (2019). How-
Figure 5: One frame in MOT20 with de- tected bounding boxes in yellow.
ever, it targets tracking with low densities, e.g.. Sprites -MOT which is different from our focus.
Settings. We adopt the MOT17 (Milan et al. 2016) and the MOT20 Dendorfer et al. 2020) datasets. Scene densities of the two datasets are 31.8 and 170.9, respectively, which means the scenes are pretty crowded
illustrated in Figure 5 We adopt the DPM detector (Felzenszwalb et al. 2009) on MOT17 7 and the Master-RCNN detector (Ren et al., 2015) on MOT20 to provide us the bounding boxes. Inspired by Xuu et al. (2019b), the cost matrix is computed as the average of the Euclidean center-point distance and the Jaccard distance between the bounding boxes,
Cis(w) = (Ilc([(z;;))) w))
VH² ((1())) W W
c(vi))l2 + (()
where c(-) is the location the box center, H and W are the height and the width of the video frame, and -)--) is the Jaccard distance defined as 1-IoU (Intersection-over-Uuue Union). We utilize the single-object tracking model SiamRPN (Li et al. 2018) as our regression model f. We apply ROBOT-robust with P1 P2 = 10-3. See Appendix for more detailed settings.
Results. We demonstrate the experiment results in Table I where the evaluation metrics follow Ristani al. (2016). In the table, 1 represents the higher the better, and J. represents the lower the better. ROBOT signifies the model trained by ROBOT-robust, and w/o ROBOT means the pretrained model [i al. (2018). The scores are improved significantly after training with ROBOT-robust.
We also include the scores of the SORT model (Bewley et al. 2016) obtained from the dataset platform. Different from SiamRPN and SiamRPN-ROBOT, SORT is a supervised learning model. As shown, our unsupervised training framework achieves comparable even better performance.
5 DISCUSSION
Sensitivity to initialization. As stated in Pananjady et al. (2017b), obtaining the global optima of (1) is general an NP-hard problem. Some "global" methods use global optimization techniques and have exponential complexity, e.g., Elhami The other "local" methods only guarantee converge to local optima, and the convergence is very sensitive initialization. Compared with existing "local" methods, our method computationally efficient and greatly reduces the sensitivity to initialization.
e.g.,Elhami et al. (017), which is not applicable large data.
'The initial weights of f obtained from https: Cestta://githhie http:///gttttbbcco com/ foo/ fool wood/ DaSi amRPN.
8

---

Published as a conference paper at ICLR 2021
To demonstrate such advantage, run AM and ROBOT with 10 different initial solutions, and then we sort the results based on (a) the averaged residual the training set, and (b) the relative prediction error on the test set. We plot the percentiles in Figure [ Here we use fully shuffled data under the unlabeled sensing setting, and we n 1000, e 5, Puoise 0.1, and 10-2 We can see that ROBOT can find "good" solutions in 30% of the cases (The relative prediction error is smaller than 1), but AM is more sensitive to the initialization and cannot find " "good" solutions.
Avg. Resduul
Rel.
AM
25
50
73
25
Peromnile
Percentile
(a) Training residual
(b) Test error
Figure 6: Results of different initialization
of AM and ROBOT.
ROBOT v.s. Automatic Differ- entiation (AD). Our algorithm computes the Jacobian matrix di- rectly based on the KKT condi-
0.12
6/
Sabtbe lanaze.
1500
10 Santioee ieniie: ICC beathern koniicm
Tame por spech
AD
Maneyy (XG
AD
1000
0.200
0.000
500
tion of the lower problem {II). An alternative approach to ap- proximate the Jacobian is the automatic differentiation through the Sinkhorn iterations for updat- ing S when solving IT.. As sug- gested by Figure 7 (a), running Sinkhorn iterations until conver- gence (200 Sinkhorn iterations) can lead to better solutior In order to apply AD, we need to store all the intermediate updates of all the Sinkhorn iterations. This require the memory usage to be proportional to the number of iterations, which is not necessarily affordable. In contrast, applying explicit expression for the backward pass is memory--fficient. Morcover, also observe that AD is much more consumingg than our method. The timing performance and memory usage shown in Figure (b)(c), where we
0.000
50
160
150
350
100
500
1000
100
550
1000
(a)
(b)
(c)
Figure 7: The comparisons AD. (a) Convergence under differ- ent number of Sinkhorn iterations of AD. (b) Time comparison. (c) Memory comparison.
1000.
Connection to EM. Abid & Zou (2018) adopt an Expectation Maxi- mization (EM) method for RWOC, where S is modeled as latent dom variable. Then in the M-step, one maximizes the expected likeli- hood of the data over S. This method shares the same spirit ours: We avoid updating w using one single permutation matrix like AM. How- ever, this method is very dependent on a good initialization. Specifically, if we randomly initialize w, the posterior distribution of S in this itera- tion would be close to its prior, which is a uniform distribution. In this way, the follow-up update for is not informative. Therefore, the solution of EM would quickly converge to an undesired stationary point. Figure
Figure 8: Expected respondence EM.
8 illlstraates an example of converged correspon- 1, 0. For this reason, we initialize EM with good
dence, where we adopt initial points, either by RS or AM throughout all experiments.
30, o
Related works with additional constraints. There is another line of research which improves the computational efficiency by solving variants of RWOC with additional constraints. Specifically, Haghighatshoar & Caire (2017): Rigollet & Weed (018)) assume isotonic function (note that such an assumption may not hold in practice), and Shi et (2018); Slawskk & Ben- BeviDa (019) [llaski eet al. (2019a b): Varol & Nejatbakhshi (2019) assume only small fraction of the correspondence is missing. Our method is also applicable to these problems, as long as the additional constraints can be adapted the implicit differentiation.
More applications of RWOC. RWOC problems generally appear for two reasons. First, the mea- suring instruments are unable preserve the correspondence. In addition GFC and MOT, we list a few more examples: SLAM tracking (Thrun) 2007), archaeological measurements (Robinson, 1951, large sensor networks (Keller et al., 2209)) pose and correspondence estimation (David al. 2004. and the genome assembly problem from shotgun reads (Huang & Madan 1999). Second, the data correspondence is masked for privacy reasons. For example, we want to build a recommender system for new platform, borrowing user data from a mature platform.
We remark that running one iteration sometimes cannot converge.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENT
This works is partially supported by NSF I1S-20033334 Hongteng Xu is supported in part by Beijing Outstanding Young Scientist Program (NO. BUWZYJH012019100002000
and National Natural Science Foundation of China (No. 61832017). Xiaojing Ye is partially supported by NSF DMS- 1925263. Hongyuan Zha is supported part by grant from Shenzhen Institute of Artificial Intel- ligence and Robotics for Society. We also appreciate the fruitful discussions with Bo Dai and Yan Li.
REFERENCES
Abubakar Abid and James Zou. A stochastic regression. In 2018 56th Annual Allerton Conference Communication, Control, and Comput- ing (Allerion), pp. 470-477. IEEE, 2018.
approach to shuffled linear
Abubakar Abid, Ada Poon, and James Zou. Linear regression with shuffled labels. arXiv preprint arXiv:1705.01 2017.
Dean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Com- puting, 37())A1111-A113 2015.
Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Uperoft. Simple online and realtime tracking. In 2016 IEEE International Conference on Image Processing (ICIP), pp. 3464-3468 IEEE, 2016.
Garrett Birkhoff. Three observations linear algebra. Univ. Nac. Tacuman, Rev. Ser. A, 5:147-151, 1946.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xaviee Vialard. An interpolating distance between optimal transport and fisher-rao metrics. Foundations of Computational Math- ematics, 18(1):1-44 2018a
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-2609 2018b.
Lénaïc Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Unbalanced opti- mal transport: Dynamic and kantorovich formulations. Journal of Functional Analysis, 274(11): 3090-3123, 2018c.
Marco Cuturi. Sinkhorn distances: Lightspeed computation optimal transport. In Advances in neural information processing systems, pp. 2292-2300, 2013,
George Bernard Dantzig. Linear programming and extensions, volume 48. Princeton university press, 1998.
Philip David, Daniel Dementhon, Ramani Duraiswami, and Hanan Samet. Softposit: Simultaneous pose and correspondence determination. International Journal of Computer Vision, 59(3):259- 284, 2004.
Dendorfer, H. Rezatofighi, A. Milan, J. Shi, D. Cremers, Reid, S. Roth, K. Schindler, and L. Leal-Taise Mot20: A benchmark for multi object tracking in crowded scenes. arXiv:2003. 09000//s,,, March 2020. URLhatp: htttp::///axi.... http//aaivv.gaaaaaaaaaaa org/ /aw.a/906.... 04567 arXiv: 2003.09003.
John Duchi. Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the b-ball for learning in high dimensions. In Proceedings of the 25th international conference Machine learning, pp. 272-279, 2008
10

---

Published as a conference paper at ICLR 2021
Golnooshsadat Elhami, Adam James Benjamin, Bejar Haro, and Martin Vetterli. Unlabeled sensing: Reconstruction algorithm and theoretical guarantees. In 2017 42nd IEEE International Confer- ence on Acoustics, Speech and Signal Processing. 2017.
Pedro F Felzenszwalb, Ross Girshick, David McAllester, and Deva Ramanan. Object detection with discriminatively trained part-based models. IEEE transactions pallern analysis and ma- chine intelligence, 32(9):1627-1645, 2009.
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in stack- elberg games. arXiv preprint arXiv:1906.0122) 2019.
Saeid Haghighatshoar and Giuseppe Caire. Signal recovery from unlabeled samples. IEEE Trans- actions on Signal Processing, 66(5):1242-1257, 2017.
Zhen He, Jian Li. Daxue Liu, Hangen He, and David Barber. Tracking by animation: Unsupervised learning of multi-object attentive trackers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1318-1327, 2019.
Daniel Hsu, Kevin Shi, and Xiaorui Sun. Linear regression without correspondence. In Advances in Neural Information Processing Systems, pp. 1531-1540, 2017.
Xiaoqiu Huang and Anup Madan. Cap3: A dna sequence assembly program. Genome research, (9):868-877, 1999.
Leonid Vitaliyevich Kantorovich. Mathematical methods of organizing and planning production. Management science, 6(4):366-422, 1960.
Lorenzo Keller, M Jafari Siavoshani, Christina Fragouli, Katerina Argyraki, and Suhas Diggavi. Identity aware sensor networks. In JEEE INFOCOM 2009, pp. 2177-2185. IEEE, 2009.
Christopher G Knight, Mark Platt, William Rowe, David C Wedge, Farid Khan, Philip JR Day, Andy McShea, Joshua Knowles, and Douglas B Kell. Array-based evolution of dna aptamers allows modelling of explicit sequence-fitnes, landscape. Nucleic acids research, 37(1):e6--6, 2009.
Stanislav Kondratyev, Léonard Monsaingcon, Dmitry Vorotnikov, et al. new optimal transport distance the space of finite radon measures. Advances in Differential Equations, 21(11/12): 1117-1164, 2016.
Bo Li, Junjie Yan, Wei Wu, Zheng 7hu, and Xiaolin Hu. High performance visual tracking with siamese region proposal network. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8971-8980, 2018.
Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy problems and new bellinger-kantrrovie distance between positive measures. Inventiones mathematicae, 211 (3):669-1117, 2018.
Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential properties of sinkhor approximation for learning with wasserstein distance. In Advances in Neural Informa- tion Processing Systems, pp. 5859-5870, 2018.
Marvin Marcus and Rimhak Rec. Diagonals of doubly stochastic matrices. The Quarterly Journal of Mathematics, 10(1):296-300 -022, 1959.
A. Milan, L. Laxx-T I. Reid, S. Roth, and K. Schindler. MOT16: A benchmark for multi-object tracking. 16003vv6000.00 [cs], March 2016. URL. htta:://arriiv.rr/abbbs. 603. 00831 arXiv: 1603.00831.
Gaspard Monge. Mémoire la théorie des déblais et des remblais. Histoire de I' l'Académie Royale des Sciences de Paris, 1781
Ashwin Pananjady, Martin J Wainwright, and Thomas A Courtade. Linear regression with known permutation: Statistical and computational limits. 2016 54th Annual Allerton Confer- on Communication, Control, and Computing, pp. 417 424, 2016.

---

Published as a conference paper at ICLR 2021
Ashwin Pananjady, Martin J Wainwright, and Thomas A Courtade. Denoising linear models with permuted data. In 2017 IEEE International Symposium on Information Theory (ISIT), pp. 446- 450. IEEE, 2017a.
Ashwin Pananjady, Martin J Wainwright, and Thomas A Courtade. Linear regression with shuf- fled data: Statistical and computational limits of permutation recovery. IEEE Transactions on Information Theory, 64(5):3286-333 -3000, 2017b.
Liangzu Peng and Manolis C Tsakiris. Linear regression without correspondences via concave minimization. arXiv preprint arXiv:2003.07706 2020.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91-99, 2015.
Rigollet and J. Weed. Uncoupled isotonic regression via minimum wasserstein deconvolution. arXiv preprini arXiv: 10648, 2018.
Ergys Ristani, Francesco Solera, Roger Zou, Rita Cucchiara, and Carlo Tomasi. Performance mea- sures and a data set for multi-target, multi-camera tracking. In European Conference on Computer Vision, pp. 17-35. Springer, 2016.
William S Robinson. A method for chronologically ordering archaeological deposits. American antiquity, 16(4):293-301, 1951.
X. Shi, X. Lu, and T. Cai. Spherical regresion under mismatch corruption with application to auto- mated knowledge translation. arXiv preprint arXiv: 1xX1:////000669, 2018.
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matri- ces. Pacific Journal of Mathematics, 21(2):343-33 348,, 1967.
M. Slawski and E. Ben- Ben-David. Linear regression with sparsely permuted data. Electronic Journal of Statistics, 2019.
M. Slawski, E. Ben- Nen-David, and P. Li. A two-stage approach multivariate linear regression with sparsely mismatched data, arXiv preprint 1rXiv:1907.077 2019a.
Martin Slawski, Mostafa Rahmani, and Ping Li. A sparse representation-basee approach to linear regression with partially shuffled labels. In 35th Conference on Uncertainty in Artificial Intelli- gence, UAI 2019, 2019b.
Jeffrey Stanton. Galton, pearson, and the peas: A brief history of linear regression for statistics instructors. Journal of Statistics Education, 9(3), 2001.
Sebastian Thrun Simultancous localization and mapping. In Robotics and cognitive approaches to spatial mapping, pp. 13-41. Springer, 2007.
Manolis Tsakiris and Liangzu Peng. Homomorphic sensing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6335 6344, Long Beach, Cali- fornia, USA, 09-15 Jun 2019. PMLR. URL htt.:::pppppceeeeeeeeete ngs ml www.mmrr...ss/ee tsaki Mikkirss 1 .a..tttt.. htmm
Manolis C Tsakiris, Liangzu Peng, Aldo Conca, Laurent Kneip, Yuanming Shi, Hayoung Choi, et al. An algebraic-geometric approach shuffled linear regression. arXiv preprint 1810.05440, 2018.
Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, and Martin Vetterli. Unlabeled sensing with random linear measurements. IEEE Transactions Information Theory, 6455)33277 2018.
Erdem Varol and Amin Nejatbakhsh. Robust approximate linear regression without correspondence. arXiv preprint arXiv: D0X.vv999000027... 2019.
Titouan Vayer, Rémi Flamary, Romain Tavenard, Lactitia Chapel, and Nicolas Courty. Sliced gromov-wasserstein. arXiv preprint arXiv: 1905. 10124, 2019.
12

---

Published as a conference paper at ICLR 2021
John Von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, 2(0))5-12, 1953.
Mengdi Wang, Yichen Chen, Jialin Liu, and Yuantao Gu. Random multi-constraint projection: Stochastic gradient methods for convex optimization with many constraints. arXiv preprint ar1iv: 2015.
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k operator with optimal transport. arXiv preprint arXiv:000.006004, 2020.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov-wassersee learning for graph matching and node embedding. arXiv preprint
2019a.
Yihong Xu, Yutong Ban, Xavier Alameda- Pineda,, and Radu Horaud. Deepmot: A differentiable framework for training multiple object trackers. arXiv preprint arXiv: 06618, 2019b.
Günter Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
13

---

Published as a conference paper at ICLR 2021
A CONNECTION BETWEEN OT AND RWOC
Theorem 1. Denote aT, b) = (S E Rexm 51 = a, S 1, = b, Sig 2 0} for any a E IR" and b E m Then at least one of the optimal solutions of the following problem lies in P. minsesr*x (C(w), S) s.t. S E (1,1,, I.).
(14)
Proof. Denote the optimal solution of corollary of Birkhoff-von Neumann theorem Birk 1946 Von Neumann 1953). Specifically, Birkhoff-von Neumann theorem claims that the polytope I[(1,; In.) the convex hull of the set of n x n permutation matrices, and furthermore that the vertices of [[ 1,) are precisely the permutation matrices.
Z As mentioned earlier, this is direct
On the other hand, (14) is a linear optimization problem. There would be at least one optimal solutions lies the vertices given the problem is feasible. As result, there would be least one Z" being permutation matrix.
B TWO PERSPECTIVES OF THE MOTIVATIONS OF BILEVEL OPTIMIZATION
B.I FASTER CONVERGENCE
The bilevel optimization formulation has better gradient descent iteration complexity than alter- nating minimization. To see this, consider a quadratic function F(e1, a2) = a Pa + b a, where a1 E Rd 42 E _2, ja IT E R (d +d2) P E I (dd) b E (d +d2), To further simplify the discussion, we assume = (1 (di-da)) (d, +da) (1 p) where Id,tda the identity matrix. Then we have the following proposition.
Proposition 1. Given F defined in we have
Amax 2 ((a)( = 1
1 p p+
dip
Amax V2,a, Laa,, = + dip
1 1 d2p + and
Amin 2 (22(()))
Amiu ( ores I(a1, (2))
Proof. For alternating minimization, the Hessian for a1 is a submatrix of P, i.e.,
HAM pld, 17, + P)
whose condition number is
dip I-p P
CAM = =1
We now compute the condition number for ROBOT. Denote
Pu
Pie
b1
P
b
Pn
Pza
b2
where Pn E dddid,, P12 E Rd1 ROBOT first minimize over 02
xd2 Pai E Rdd2xd, Prz E I d2dd, and b, E Rd, b2 E R2
az((1) arg min ((a1, 02) = (P22 + ( + b2/2).
02 Substituting ()))) into F(a,, HROBOT Pı1 Piz(Pe2 + Al ) P21.
obtain the Hessian for a is
Using Sherman-Morrison formula, we can explicitly express P as
P
Tao
1 1 TT:
(1- p+ +1-p+A)(1- P + pdg)
Substituting it into HROBOT, HROBOT = Pu PieP P2i = (1 p) + (p d2p p x
dzp²
1a, 17,
Therefore, the condition number is
1 p +
dip
CσOBOT = 1+
1 1-p
p
dep p x11
14

---

Published as a conference paper at ICLR 2021
Note that CAM increases linearly with respect to d1. Therefore, the optimization problem inevitably becomes ill-conditioned as dimension increase. In contrast, CROBOT can stay in the same order of magnitude when dj and d2 increase simultancously.
Since the iteration complexity of gradient descent is proportional the condition number (Bottou al. 2018), ROBOT needs fewer iterations converge than AM.
C
DIFFERENTIABIITY
Theorem 2. For any 6 > 0, (w) is differentiable, as long as the cost C(w) differentiable with respect w. As a result, the objective [.(w) (C(w), St (w)) is also differentiable.
Proof. The proof is analogous to Xie et al. 2020).
We first prove the differentiability of (w). This part of proof mirrors the proof in Luise et al. 2018). By Sinkhorn's 's scaling theorem (Sinkhorn & Knopp 1967
S. (wc = diag(e (w)) C(w)
)e diag(e
Therefore, since Ciz is differentiable, I is differentiable if (f"(w,, (w))) is differentiable as a function of w.
Let us set
C( = = -
Σ 4,==1
Cu 52
and recall that (5", arg max L(C, C). The differentiability of (*" ) is proved using the Implicit Function theorem and follows from the differentiability and strict convexity in (E*, ((* of the function L.
Theorem 3. Denoting Le = (C(w), The gradient of Le with respect to w is
V VwC. = 1
n. Σ
(1 - Cit) +
Σ
nnn
CheS
dE dCis
Σ
CheSt dOis
dçp
VuCig. (15)
:1=1
h.8=1
where VoE* Vos
H-1D
with HH -H (2 (2n-11)xx E R Rlxxx
BeiStasy == 1.. ; S1
Daş
{ = n 1,... 2n 1,
(diag(()) -1 (diag(u)) -1 -S:K- 1:5k-15p00 -K- (diag(w))
S5a (diag(a)) (1)) 5:K-
H-1
K-
and K = diag(D) 55 (diag(n))~ == U1m-1
= = 1mm,
Proof. This result is straightforward combining the Sinkhorn's 's scaling theorem and Theorem 3 in Xie et (2020).
D ALGORITHM OF THE FORWARD PASS FOR ROBOT-ROBUST
For better numerical stability, in practice we add two more regularization terms, S7 (w), Ht, 8 arg min A.FEA, (C(w), eH + e1h(p)+ + E2h(D),
(16)
s.t. (z) S pl, F(D,V) S P2; where (a)) E; t4 log 14 is the entropy function for vectors. This can avoid the entries of and D shrink to zeros when updated by gradient descent. We remark that since we have entropy term H (S), the entries of S would not be exactly zeros. Furthermore, we have j 51 and j S1. Therefore. theoretically the entries of ā and 7 will not be zeros. We only add the two more entropy terms for numerical consideration. The detailed algorithm is in Algorithm I Although the algorithm is not guaranteed to converge to feasible solution, in practice it usually converges to good solution (Wag et al. 2015).
15

---

Published as a conference paper at ICLR 2021
Algorithm Solving S; for robust matching
Require:
Ce Rmxx s,.V ,,V, K, 1
S2 1, 1=v=
Gúj
Ln
for | = 1,... Lo
p/(Gb), b D/(G"a))
á = P - n(e² + +1 * log p), カ= nne + 62 * log
1 max ma, 03.
max 0]
1 = p1/ 1). 1= D/
if 1r 1112 > P1 then
p = 1ut + vPI 2
R-
end if
if 1 - v > then
= V/ + P2 サ-ル v 2
end if end for
S = diag () 3 G @ diag(b)
ALGORITHM OF THE BACKWARD PASS FOR ROBOT-ROBUST
Since the derivation is tedious, we first summarize the outline of the derivation, then provide the detailed derivation.
E.1 SUMMARY
Given ;0' D², (w), we compute the Jacobian matrix dS; (w)/dw using implicit differentiation and differentiable programming techinques. Specifically, the Lagrangian function of Problem (16) is
C=(C,S) ((()) + + c2 - E (T1m -1) -
+ 1, - A2 1m - 1) + >s(1 - 1112 -1) + -011p-v112--1111 P2).
where & and ( are dual variables. The KKT conditions (Stationarity condition) imply that the optimal solution n can be formulated using the optimal dual variables ç and (* as,
St diag(e )e diagle 5).
(17)
By the chain rule, we have
dS; dS; dC
is;
Os, de De
0S: ds* dC
+
dw
dC du ac
dC
O dC dw
Therefore, we can compute ds; (S)(w)/d (w)/dw if we obtain and
de dc
Substituting 17 into the Lagrangian function, the optimal solutions we obtain
== C=E(E S ai, D" Xi No Ag. Xis C": Denote y" (CET),(("")) (z) (D) Ai Xū Ag, Ti and o(r"; C) aL(r";C)/rr' At the optimal dual variable r", the KKT condition immediately yields "(r":C) = 0. By the chain rule, we have
d Oø(r":C) +
0ø(r": C) dr*
dr dC = 0.
(18)
dC
d0
Rerranging terms, we obtain
dr*
(bb(+;CC)
"bb(r;;) C)
(19)
dC
dr
80
Combining 17). 18 and 19) we can then obtain dS; (w)
16

---

Published as a conference paper at ICLR 2021
E.2 DETAILS
Now we provide the detailed derivation for computing /dw.
Since S is the optimal solution of optimization problem, we can follow the implicit function theorem to solve for the closed-form expression of the gradient. Specifically, we adopt F(u,, v) =
E.(, pa)2, and rewrite the optimization problem as
min (C, + p,0,8
Σ
Sty (log Siz 1) + a Σ (log Ps 1) + c2 E By (log Vn 1),
DSa Sig -iss
Σ = DB} Dj,
s.t.,
En sb 11, Σ0==14
E(e: - ( sp. Pl.
(eg-vr)) S p2.
The Language of the above problem is
S, D, S. A1, A2, Ao, Xaa)
(C,S) + Σ Siy (log Sig 1) + 6 Σ Ji(goog - 1) + c2 Ee (log -1)
ij
(S1m [1) (S 1, -)
+ X1 >i(Cim
1) 11 X2
Σ Djj 1) + Ao e (N: -mi) - p1) + de > (ig - -uz²² - p2).
Easy to see that the Slater's condition holds. Denote
L' L(C, F","",""" D'. . Xi, ,,, 17. A1).
Following the KKT conditions,
dC
Cij + clog Siaj - -G- = 0.
dS
6i <1+5--00 Then we have
Therefore, S7,5 =
dS;
as;
as de g dC Oc dC dw
+ as; ds* dC
dw
a
So all we need to do is to compute
de' and de de dc
Denote Fi -
Denote
dc
ū Flms
df
dc
- - 1'nm
dc
dc
p
dp
{ + 11 + 2>a(ū - 11) + log
Jp
q = da
( + 1 + 20 v) - c2 lo
Jp
XI Vyp
p 1, 1,
dC
X2 =
7 1m - 1,
dAg
X3 = As(I 1112- P1),
X4 = >1 212 p2)-
Denote X = Xx, X2, X2, x4), and \ = A2, As. >4). Following the KKT conditions, we have
-= Φ 0.p 0, 0, x 0,
17

---

Published as a conference paper at ICLR 2021
at the optimal solutions. Therefore, for the optimal solutions we have
dø 06 dΦ de*
de ds*
dō dă
dΦ dø*
dĀ dx*
dC aC
ō5* dC
ō dC
0p dC
d dC
Ox dC
du 0
Oy dg
d dç*
0b dār
dub do
Ob dx*
0,
dC ac
0 dc
Oç* dc
Opt dc
Oi dc
Ox* dc
Op
Öp de
0p dc*
Op dp
Öp do
Öp dx*
0,
dC AC
05* dc
oç* dc
0pe" dc
0 dc
0x* dc
dq 0q
0q de"
0q dç
ôq du
0q db
ōq dx*
0
dC OC
05* dc
0p dC
07 dC
-Y dc'
dx =
0x
0x de
0x dc*
0x dp=
0x do*
0x dx*
+
+
dC ac
0 dC
20* dC
dC
07
dC
-YD dc'
Therefore, we have
06
06
00
06
86
DE
00
dC
0
10
dC
0E 0
ac
dp
Öp
0p
dp
dp
Öp
00
dC
05
11
-Y
ac
dv
0q
0q
dq
0g
Oq
04
dx.
0c*
0x
0x
0x
8x
xx
dC
aç*
-X
Lac
After some derivation, we have
de'
disg(a)
In
(87)T
I.
gG
In
2Ag
didgg
2(F2
2A + diag
2(P
T
2)a (A
|| 1
2Ag u)
||P
and
a SnySty Vh 1.... n, i 1,... n, j -,......
aCi;
Ovh StzSej, AE 1....
i 1, n, j 1, m.
aCg
To efficiently solve for the inverse in the above equations, we denote
diag(ı)
St
I,
0
G
(SP)T
diag(E)
Im
In
0
2AaIn + diag (
0
0
Im
2A + diag( $2)
In
0
2(
n1)
Bi
0
1
2(D
v)
T
0
n
T
C
2)a(
n1) T
0
2 (v D)
18

---

Published as a conference paper at ICLR 2021
0
0
0
0 0
0
0
D
0
|1
14
P1
0 0
0
|
1112
P2
We first A-1 using the rules for inverting a block matrix,
K
- KL
A1
A2
A =
- LK
L+ LKL
=
Aa
A1
where
L 2A n + diag(")
0
K= (
diag(()
S
+
0
2 + diag(
(St
diag(E)
Then using the rules of inverting block matrix again, we have
de
06
d
A A
πc
Ou
dC
Lac_
Therefore, the bottleneck of computation is the inverting step in computing K. Note is diagonal matrix, we can further lower the computation cost by applying the rules for inverting block matrix again. The value of A3 and X can be estimated from the fact p 0, q 0. We detail the algorithm
in Algorithm
Algorithm Computing the gradient for w
dC' Require: C mmxn 14, V. C, dnc Run forward pass to get S S P. D. E.S
21
[n/2] ( 14), Σ i= |//
(it 14),
E(m/21 Ei, -E=[n/21 E
[n/21
-EE
[Ai Aa] = [n/2], x1; [n/2] 02
[61, 62)
21 Σ [m/2]
=1 (V) 12),
-;=[m/21
(D) V2) b,
E}m/?1 Sj. by -==
[m/2]] Si
[A2, Aa] = [[m/2]
21;
[m/2]
[b1 82
ş + =22 -)-1
6 622 )
)--1
1' xl: -1). S S -1]
X diag(r") " (diag(n)
(1)(
H1 + (diag(ā)) ) (diag(n) S' S' (dnn))))))))))((((((((()
H₂ (diag(n) S'K
H3 t (H2)*
H4 K-
Pad H2 to be [n, ml with value 0
Pad H3 be (m, n] with value 0
Pad H2 to be
(m, m. with value 0
L diag((e() ((eAg(e + = c22241m -)-11)
A1 = H H2; H3, Ha)
A2 A
Ag A.
A1 L + L. L-A1-L
E A1 + A2 B.-BIDD A4 -)- C-A
As. where B1, C₁, D defined above
J2; Js] =E. where J1 E Raxx J2 gaxm Jg Rmxa J4 xm
dde"
4C mnj + [JinnsStt (1
de
2C mmjj + [JalmiSij [JaJmj
Pad do
de to be [m, m] with value 0
lij 1-
Enm Com Smm da
dC nij + Σn.m Cum Sum db" dc
mis) + Sig
dL dC
return dC dw
19

---

Published as a conference paper at ICLR 2021
L1
0.02
0.02
0.07
0.07
0.09
0.09
0.53
0.53
0.57
0.57
0.78
0.78
0.79
0.79
0.83
0.83
0.87
0.87
0.93
0.93
(a) & distance
(b) divergeenc
Figure 9: Illustration with different choice of F.
F DIFFERENT FORMS OF MARGINAL RELAXATION
In this paper adopt F to be the Euclidean distance. This is because this choice provides an OT plan that fits our intuition the data points with significantly larger transportation cost should not be considered. Figure (9 shows an illustration. Here, the input distributions are the empirical distributions of the scalars on the left and the bottom. Notice that there are three support points in y that far away from others, i.e., 10.72, 10.89, 10.96. In Figure | (a). the optimal solution r automatically ignores them, matching only the rest of the scalars. One alternative choice of the Kullback-Leible (KL) divergence (Chizat al.) 2018b), whose resulted formulation possesses an efficient algorithm for the forward pass, and the differentiability for the backward pass. We do not adopt because the OT plan generated by this choice does not fit intuition: As shown in Figure (b), the OT plan tends to ignore the points that are away from the mean, even with very small and p2. For both figures, we adopt
10-5,
G MORE ON EXPERIMENTS
G.1 UNLABELED SENSING
We provide trained with batch size 500 and learning rate 10-4 for
training details for experiments in Section 4.1 Here. AM and ROBOT is 2, 000 iterations. For the Sinkhorn algorithm 10-1 We run RS for 2 105 iterations with inlier threshold 10 Other settings for the hyper-parameters in the baselines follows the default settings of their corresponding papers.
in ROBOT
G.2 NONLINEAR REGRESSION
For the nonlinear regression experiment in Section with learning rate 10-4 for 80 iterations. For n 100, 200, 500, 1000, 2000, we set batch size 10, 30, 50, 100, 300, respectively. We set 10-4 for the Sinkhorn algorithm in ROBOT. For Oracle and LS, we perform ordinary regression model and ensure convergence, i.e., learning rate 5 x 10-2 for 100 iterations.
ROBOT and ROBOT-robust is trained
G.3 FLOW CYTOMETRY
We provide more details for the Flow Cytometry experiment in Section 4.3 In the FC seting, ROBOT is trained with batch size 1260 and learning rate 10 for 80 iterations. In the GFC seting, ROBOT is trained with batch size 1260 and learning rate 6 x 10 4 for 60 iterations. We set 10 for the Sinkhorn algorithm in ROBOT. Other settings for the hyper-parameter in the basclines follows the default settings of their corresponding papers. EM is initialized by AM.
20

---

Published as a conference paper at ICLR 2021
G.4 MULTI-OBJECT TRACKING
For the MOT experiments in Section the reported results of MOT17 (train) and MOT17 (dev) trained on MOT17 (train), and the reported results of MOT20 (train) and MOT20 (dev) trained on MOT2C (train). Each model is trained for epoch. We adopt Adam optimizer with learning rate= 10-5, 10-1, and y = 10-3 To track the birth and death of the tracks, we adapt the inference code of Xu et al. (209hh).
G.5 COMBINATION
RS
As suggested in Figure al- though RS cannot perform well itself, retraining the output of RS using our algorithms increases the performance by large mar- gin. To show that combining RS and ROBOT
Table 2: Pairwise comparisons between RS alone and the com- bination of RS and ROBOT. The relative error ratio is the ra- tio of the relative errors of RS alone and RS+ ROBOT combina- tion. Ratios larger than suggest that RS performs worse than RS+ROBOT combination.
achieve better results than RS alone. we com- pare the following two cases: i). Subsample 2 x 10 times using RS; ii). Subsample 10 times us- ing RS followed by ROBOT for 50 training steps. The result is shown in Table 2 For a larger permutation proportion, RS alone cannot perform as well as RS+ROBOT combination. Here, we have 10 runs for each proportion. We adopt SNR= 100, d = 5 for data, and e 100- learning rate 10 for ROBOT training.
Proportion
25%
50%
75%
Rel. error ratio
1.04 + 0.20 1.29 + 0.32
1.27 + 0.34
G.6 THE EFFECT OF AND
We visualize ST computed from the robust optimal transport problem in Figure 10 The two input distributions are Unif(0, and Unif(O, 1). We that with large enough fr and p2, Unif(O, 1) would be aligned with the first half of Unif(0, 2).
612
63
634
61
68
681
048
6/6
646
035
655
055
664
606
696
678
675
(a) #1 0, =0
(b) pi = 0.1, 0.1
(c) pt = 0.2, P2 = 0.2
Figure 10: Computed S* for robust optimal transport problem.
G.7 COMPARISON OF RESIDUALS IN LINEAR REGRESSION
Settings. We generate n data points {(y,, [x,, 21))] where x; E Rdd and 2; E R We first generate I; (0,, Ia), 2, ~ NNO,,, I.), ~ NOO Iama), and E; NN(0, Protse) Then compute = [( = w) + e.. Next, we randomly permute the order of {zi] } so that we lose the data correspondence. Here, D, (II,y:)) and D2 (2,) mimic two parts of data collected from two separate platforms.
We adopt a linear model fa; w) = T To evaluate model performance, we use error- Σ. 3:)3//2 1,, g) where 0: is the predicted label, and ÿ is the mean of {3s}
Baselines. We use Oracle, LS, Stochastic-FE as the baselines. Notice that without a proper ini- tialization, Stochastic-FM performs well in partially permuted cases, but not in fully shuffled cases.
21

---

Published as a conference paper at ICLR 2021
For better visualization, only include this baseline in one experiment. Furthermore, adopt two new baselines: Sliced-GW (Vayer et al. 2019) and Sinkhorn-GV (Xu et al. 2019a), which can be used to align distributions and points sets.
Results. We visualize the fitting error of regression models in Figure II outperforms all the baselines except Oracle. Also, model can beat the Oracle model when the dimension is low or when the noise is large.
We can see that ROBOT
10-
Discle
Sicca
GA
-10-
-22
-35
-35-
-45-
Sices-O
Orade
Sicao SM
-30
0.51
0.1
05
1.
130
202
506
30.0
5009
Figure 11: Linear regression. We use = 1000, d = 2, e = 3, P = 0.1 as defaults.
22


Reviews:
[{"review_id": "xA9iKu08bQ2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThe paper presents a method for robust regression with no correspondences. The association matrix is replaced by a matrix with continuous positive values. Two practical and relevant problems are investigated.\n\nThis seems to be a very interesting investigation, and the authors have done many commendable things such as studiyng relevant problems with real data, comparing to multiple alternatives, and appear to bring an interesting perspective to the problems.\n\nThe exposition of the method seems to lack a few details that might perhaps have escaped the attention of the authors. The recommendation unfortunately should tend towards not accepting. The authors should be urged to consider their work inside a wider perspective.\n\nThe main method that is repeatedly compared to the proposal was only AM. The proposal is in many ways actually more similar to Expectation-Maximization. The Birkhoff polytope here basically appears to represent likelihoods of data assignment according to Gaussian likelihoods.\n\nIt does not seem clear if the authors are exploring some further constraint in their proposal. It would be paramount to contrast the method with EM, though. The paper, as it is, looks like it could be basically proposing a form of EM without recognizing this. And for sure EM must bring many of the advantages over AM as the paper promises.\n\nSome further smaller points:\n\nIn section one, on the second point, ending with \"...they get stuck in local optima easily.\" What exactly is the argument here? If we are talking about a local, hill-climbing style of algorithm, there is no hope to escape local optima unless the initialization is improved, or the landscape is improved, or the algorithm is modified in such a way that it is not hill-climbing anymore, becoming some form of global optimization. In what way does the proposal differ?\n\nEM, compared to AM, would imply in an enhanced landscape, as also seems to be the case with the proposal. Another benefit is merely to utilize slower although more robust first-order optimization methods.\n\nIt's important to make explicit what exactly are the proposed benefits. The way this sentence is written may give an impression the algorithm is proposing something that goes above a local search style of algoritm.\n\nAnother important point is about initialization which is certainly crytical to all such algoritms. In the experiments the authors suggest there's an improvement there, although the improvement must be more related only to a better landscape. Although what was the initialization afterall? This must be evaluated in the context of how good the available initializations are.\n\nStill on section one: \"Efficient first-order optimization algorithms\" - Efficient relative to what? How would second-order algorithms be classified?\n\nRegarding the experiments, RANSAC, by virtue of being a global optimization algoritm unlike the proposal and other alternatives, would be expected to be able to reach very high levels of accuracy, even if associated with a great computational cost. When comparing such a method with RANSAC one would expect to see a discussion about time/accuracy compromises. The paper is only presenting RANSAC as a method that could not reach a satisfactory accuracy. It should present at least an accuracy at a setting that was deemed to be equiparable computationally.\n\nOne final remark about AD. It is in general expected that AD techniques can match explicit derivative formulas, unless the problem is not well suited to the specific AD technique used. Or sometimes the user is required to make some extra tuning or configuration. It would be nice to review exactly how AD was not suitable, and whether there isn't an AD based solution for that (e.g. forward mode versus backwards mode). \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VQO9qHjuarF", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a novel method for regression problems with outliers. The main idea is to first propose a mixed-integer optimization problem for the regression problem and then and the optimization procedure of finding the solutiuon of the problem differentiable, and the objective function of the problem are also be rephrased as a differentiable function. Based on this, an end-to-end learning approach can be established.\n\nPros:\n\n1. The motivation of the paper is very clearly stated in the text, and the sketch of the theorems make the paper easy to understand. \n2. The experimental part is good and it proved the efficiency of the proposed method.\n3. The idea of converting a mixed-integer programming to a differentiable function is elegent. \n\nCons:\n1. The authors says that they are going to somehow relax the one-to-one matching constraints, however, in the main text we can see that the model is still based on strict one-to-one matching constraints. In the experiments, for synthetic data, every generated data is in fact an one-to-one matching. For other datasets, through they are not strictly one-to-one, but they are close to one-to-one.\n\n2. Theorem 1 is a trival result due to total uni-modular, and it is proved many years ago, maybe it would be better to simple give a citation there. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "QGZXrpXtYn", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this submission, the authors propose a bilevel optimization based solution to the problem of Regression Without Correspondence (RWOC). \n\nStrong points:\n1. The paper writing is very clear. I didn't know the RWOC problem before reading this submission; but after reading the introduction, I can clearly understand the problem setting, its applications (the two provided examples are great!), its challenges and what is the high-level idea of the proposed solution. Also, the organization and presentation of experiment part are very clear and easy to follow.\n\n2. Besides the normal case of RWOC, the authors also consider and solve the case of \"partial one-to-one correspondence\". They also demonstrate its application using multiple-object tracking.\n\n\nThere are some issues that can be addressed to further make the submission strong:\n1. For the experiments about multi-object tracking, could the authors include some (at least one) strong baseline? The current experiment setting for this part is not so convincing and it is a bit difficult to justify the improvement.\n\n2. Besides the application of multi-object tracking, could the authors discuss more potential applications of RWOC? This can enlarge the application scope and make the studied problem more important and practical.\n\n\nMinor places:\n1. Page 2, the paragraph above \"Related Works\": rRWOC -> RWOC\n\n2. Fig 2 and Fig 3: For the printed paper version (black-white), these figures are hard to read. The authors can use different markers or textual to differentiate methods.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GW7_OEMOeXr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strengths:\n- the problem formulation is clean and clearly explained\n- the method presentation is well written\n- the techniques in used in the optimization steps, after  the relaxation step, are well motivated\n\nWeaknesses:\n- it is not clear whether the significance of  Regression without Correspondence, is high. The Multi-object tracking experiment seems contrived, at least a very good approximation of the permutation matrix can be obtained using descriptors and motion continuity\n- the issue of initialization, is not fully resolved. In the reported experiment in the discussion section, ROBOT succeed 30% of the time. The percentage may vary and it is not clear how a user of the method should find a good initialization regime.\n- in the experimental set-up that most resemble realistic applications (GFC for the cytometry), the improvement over AM, say a \"trivial baseline\" is not significant.\n\nNote: calling a method ROBOT will make it very difficult to google ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to solve regression without correspondence.  The problem is well-motivated, and the proposed method is technically sound. The motivation, organization, and presentation of the paper are very clear.  Reviewers’ suggestions to further improve the paper (e.g., clarifications on initialization, comparison and discussion with with EM, AD, etc) were adequately incorporated to the revised manuscript. 
Decision: Accept (Poster)