Identifying Phase Transition Thresholds of Permuted Linear Regression via Message Passing
Authors: Hang Zhang
Ping Li
Venue: Submitted to ICLR 2023 (2023)

Abstract: This paper considers the permuted linear regression, i.e., ${\mathbf{Y}} = {\mathbf{\Pi}}^{\natural}{\mathbf{X}}{\mathbf{B}}^{\natural} + {\mathbf{W}}$, where ${\mathbf{Y}} \in \mathbb{R}^{n\times m}, {\mathbf{\Pi}}^{\natural}\in\mathbb{R}^{n\times n}, {\mathbf{X}} \in \mathbb{R}^{n\times p}, {\mathbf{B}}^{\natural}\in \mathbb{R}^{p\times m}$, and ${\mathbf{W}}\in \mathbb{R}^{n\times m}$ represent the observations, missing (or incomplete) information about ordering, sensing matrix, signal of interests, and additive sensing noise, respectively. As is shown in the previous work, there exists phase transition phenomena in terms of the \emph{signal-to-noise ratio} ($\mathsf{snr}$), number of permuted rows, etc. While all existing works only concern the convergence rates without specifying the associate constants in front of them, we give a precise identification of the phase transition thresholds via the message passing algorithm. Depending on whether the signal ${\mathbf{B}}^{\natural}$ is known or not, we separately identify the corresponding critical points around the phase transition regimes. Moreover, we provide numerical experiments and show the empirical phase transition points are well aligned with theoretical predictions.

Under review as a conference paper at ICLR 2023
IDENTIFYING PHASE TRANSITION THRESHOLDS OF PERMUTED LINEAR REGRESSION VIA MESSAGE PASS- ING
Anonymous authors Paper under double-bling review
ABSTRACT
This paper considers the permuted linear regression, i.e. Y - IIXB + W, where Y Raxm ITf E R=xx X E RTxp, B IR and W E Raxm represent the observations, missing (or incomplete) information about ordering, sensing matrix, signal of interests, and additive sensing noise, respectively. As shown in the previous work, there exists phase transition phenomena in terms of the signal-to-noise ratio (snr), number of permuted rows, etc. While all existing works only concern the convergence rates without specifying the associate constants front of them, we give a precise identification the phase transition thresholds via the message passing algorithm. Depending on whether the signal B is known or not, we separately identify the corresponding critical points around the phase transition regimes. Moreover, provide numerical experiments and show the empirical phase transition points are well aligned with theoretical predictions.
INTRODUCTION
This paper considers the permuted linear regression
where Y E R= denotes the sensing result, IT E R represents the permutation matrix, X E Raxp is the sensing matrix, B is the signal of interests, W denotes the additive noise, and is the noise variance. The research on this problem dates back at least to 1970s under the name 'broken sample problem' (Goel 1975 Bai & Hsing 2005 DeGroot et al. 1971: DeGroot Goel 1976 1980). In recent years, have witnessed revival of this problem due to its board spectrum of
applications in privacy protection, data integration, etc (Pananjady et al., 2018
Unnikrishnan cf al.
2015 Slawski et al. 2020 Slawski & Ben-David 2019 Pananjady al. 2017 Zhang al. 2022
Zhang & 2020).
Associated with this problem comes phase transition phenomenon: the error rate for the permutation recovery suddenly drops to zero once some parameters reach certain thresholds. Despite previous work such as Slawski al. (200)) (Slawski & Ben-David (2019); Pananjady al. (2017); Zhang et al. 2022); Zhang & Li (020) can all cxplain this phenomenon, the precise positions of the phase transition thresholds are never studied but rather their statistical order. In this work, we would like to leverage message passing (MP) algorithm to identify their precise location. As byproduct, we also come up with an algorithm to partially recover the permutation matrix.
Related work. The line of research starts with the literature in permuted linear regression. Among all the works mentioned above, the most related works include Sllaski et al. (2020); Slawski &
Ben-David (2019); PPananjady et al. (017); Zhang et al.] (2022): Zhang & Li (2020). in which almost the same settings as ours are used. Pananjady et al. (2018); Sllaski
Ben-David (2119)
consider the single observation model (m 1) and proved the snr for the correct permutation
recovery will be Op (n where c > is some positive constant. Later, Slawski et al. 2020):
Zhang et al. (2022); Zhang & Li (2020) investigate the multiple observations model (m suggest the snr requirement can be signficcntty decreased, to put it more specifically, from Op (n²)
and
to Op (n²/m) In particular, Zhang Li (020) develop an estimator which we will analyze as part of contributions. Although they obtained the correct convergence rate to restore the correspondence,

---

Under review as a conference paper at ICLR 2023
which are mannimaxx-ptiiiie in certain regimes, their results fail to specify the leading coefficients, or equivalently, the precise location of the phase transition threshold. Moreover, their analysis does not consider the intertwined influence among the parameters n, p. m, etc. One example would be the impact of the p/n ratio on the maximum allowed number of permuted rows, which has not been studied before this work.
Another line of research comes from the field of statistical physics, which begins with Mézard & p.85.. Using the replica method, they study the linear assignment problem (LAP), i.e. minn Lt Li Big where II denotes permutation matrix and Eij is i.idd random variable uniformly distributed within the regime [0, 1]. Martin et al. (2005) then generalize the LAP to multi-index matching and presented investigation based on MP algorithm. And Caracciolo et al. (017); Malatesta al. (2019) extend the distribution of E;; to a broader class. However, all the above works exhibit no phase transition. In Cherttovv et al. (2010), this method is extended to the particle tracking problem, where phase transition phenomenon is first observed. Later, [Semerjian al. (2200) modify it to fit the graph matching problem, which paves way for our work in studying the permuted linear regression.
Parisi 1986
Our technical contributions are summarized as follows
We propose the first framework that can identify the precise location phase transition thresholds associated with permuted linear regression. In the oracle case where B is known, scheme is able to determine the phase transition snr. In the non-oracle case where B is not given, our scheme can further predict the maximum allowed permuted rows and uncover its dependence the ratio '/p-
We generalize the full permutation estimator and first obtain a partial permutation estimator. Consider the example where the correspondence for single index is desired. By removing all function nodes except that corresponds to that index, we exploit the MP algorithm and design algorithm that converge in one step. Moreover, show its performance almost match the estimator for the full permutation recovery.
In addition, we would like to briefly mention the technical challenges. Compared with the previous
works (Mezard & Montanari 2009 Talagrand| 2010 Linusson & Wästlund 2004 Mézard & Parisi 1987: 1986]] Parist & Ratiéville 2002 Semerjian et al., 2020). where the edge weights are relatively
simple, our edge weights usually involve high-order interactions across Gaussian random variables and are densely correlated. To tackle this issue, our proposed approximation method to compute the
phase transition thresholds consists of three parts: (i) perform Taylor expansion; (ii) modify the leave-one-out technique; and (iit) size correction scheme. A detailed explanation can be found in Section 5 Hopefully, it will serve independent technical interests for researchers in the machine learning community.
Notations. We use a.. b to suggest converges almost surely to b. We denote f(n) s g(n) when limp-+00 f(m)/(()) = 1. We denote fn) = Op (g(n) if the sequence f(m)/(()) is bounded in probability; while denote ['n op (g(n)) if the sequence f(n)/a(m) converges to zero in probability. The inner product between two vectors (resp. matrices) are denoted as (s))). In addition, for two distributions d, and d2, we write dj _ d2 if they are the equal up to some normalization. Moreover, we define Pn, as the set of all possible permutation matrices, i.e., P,, A (II E (0, 10 >. D1, =, E, Hij mapping æ of (1,2.....n) n), where (i) denotes the correspondence of index i permuted by II, 1 < i S n. The signal-to-noiee-ree
1]: and associate each permutation matrix II E Pn with
(snr) written as || Ill (m (2), where I-||p the Frobenius norm and σ² denotes the variance of the sensing noise.
2 PROBLEM SETTING
In this paper, we consider the linear regression with permuted labels reading as
Y xB + +oW,
where Y E xm represents the sensing result, I E Pr, denotes a permutation matrix awaiting to be reconstructed, X RRxp is the sensing matrix with each entry Xiş following the i.i.d standard
2

---

Under review as a conference paper at ICLR 2023
normal distribution, B E R is the signal of interests, and W E R= represents the additive sensing noise and its entries Wi are i.d standard normal random variables. In addition, we denote h as the Hamming distance between the identity matrix and the permutation matrix IIs, i.e., h Σ 11 (1) + i).
The goal is to reconstruct the permutation matrix II' from the pair (Y, X). As is well known in the previous works (Zhagg & Li. 2020; Pananjady al. 2018 Zhang et al. 2022). there exists phase transition phenomenon inherent in this problem. However, all these work only present the statistical order without specifying the constants. In this work, we would like to identify the precise position of the phase transition points in the large-system limit, i... n, m, p. and h all approach infinity with m/n- - Tm. p/n - Tp and h/n > Th-
Inspired by the Mezard & Montanari 2009); [Semerjian al. (2020) Chertkov et al. (2010),
borrow the tools from the statistical physics to identify the precise location of the phase transition threshold. In the following context, we separately study the phase transition phenomenon in (i) the oracle case where B is given as a prior and (ix) the non-oracle case where B is unknown.
3 BACKGROUND KNOWLEDGE ON GRAPHICAL MODELS
To begin with, we briefly review the linear assignment problem (LAP), which is defined as
π argminneP..
III, -)),
where E g2xn is a fixed matrix and Pn. denotes the set of all possible permutation matrices. The following context investigates the behavior of fl with the message-pussing (MP) algorithm, First,
follow the approach in (Semerjaan et al. (2020); [ezard & Montanari (2009) and introduce probability measure over the permutation matrix II, which reads as
a IIII= = Z II (11 - Eu,) II
(1 (II1--u E11)) J
E.,, R,
(2)
where 11()) is the indicator function, Z is the normalization constant of the probability measure (III). and B > 0 is an auxiliary parameter. We can verify that the solution to the ML estimator maximizes the probability measure (III,, which means we can study the properties of II via the configuration argmax In addition, we notice the probability measure (IIII concentrates IT when letting 3 + 0o. Then we identify the phase transition thresholds by studying the marginals of (II)..
3.1 CONSTRUCTION OF GR GRAPHICAL MODEI.
To start with, we construct the factor graph associated with the probability measure in 2 Adopting the same strategy in Chapter 16 in Mezard & Montanari 2009). we (i) associate each variable IIj variable node way: (ii) connect the variable node Vij function node representing the term -am, Fas; and (dii) associate each one function node and similarly for the constraint Σ, M1 1. A graphical representa- tion is put in Figure !
E gm
Σ ja =
Figure 1: Illustration of the constructed graphical model. The circle icons represents the variable node; while the square icons represent the function node: the blue square icon repre- sents the constraints for the rows of II, the green square icon represents the constraints for the columns of II, and the red square icon denotes the function e Fa,
constraint Σ; TTy
Then we briefly review the MP algo- rithm. Informally speaking, MP local algorithm to compute the marginal probabilities over the graphical model. In each iteration, the variable node e transmits the message to its incident function node f by multiplying all incoming messages except that along the edge (v, f). And the function
Althogg our analysis concerns the large-system limit, numerical results matches our predicted results to good extent even when n, m, p, and are few hundreds.
3

---

Under review as a conference paper at ICLR 2023
node transmits the message to its incident variable node by computing the weighted summary of all incoming messages except that along the edge (f. For a detailed introduction to MP, we refer readers to Kschischang et al. (200T); Mezard & Montanari (2009).
MP is able to obtain the exact marginals (Mezard & Montanari 2009) for the tree-like graphical models. While for graphs with lot of short loops, which happens be case, this claim may become invalid. However, past works all suggest that MP can still obtain meaningful results when applying to LAP (Mezard & Montanari
2009
Semerjian et al. 20200.
3.2 MESSAGE PASSING (MP) ALGORITHM
Next, we turn to the permutation recovery via MP. The following derivation follows the standard
procedure, which can found in the previous works (Seeejiaan et. al. 2020 Mezard Montanari
2009). Denote the message flow from the node it to the variable node (7*,)%) as Ma (R) (+)
and that from the edge (it.,%) node iL as mG)))))> (-). Similarly, we define man-(aa-)R)
and ma (8) - (-) as the message flow transmitted between the functional node j and the variable node (i",jR). Here the superscripts L and R are used to indicate the positions of the node (left and right). Roughly speaking, these transmitted messages can be viewed as (unnormalized) conditional probability P( {0, (0,1)(()) with the joint pdf being defined in 2 And the message transmission process is to iteratively compute these conditional probabilities. For more detailed introduction of
the MP algorithm, we refer to Mezard & Montanari (2009): MacKay et al. 2003).
First, we consider the message flows transmitted between the functional node j and the variable node (it,jR), which are written as
()))))= (T) mife (ay)) A (a-(a
Σ
II (p (Ta BTa en Bn 111(1 + Σ Ta = 1), (3)
LR RR
where π E 10, 1} is binary data. Similarly, we can write the message flows between the functional node 18 and the variable node, which are denoted as (R),))) mia (T) and ( respectively. With the parametrization method, we define
1 A
log ()-))))9(1)
log myr-11 (1)
hp -0 (n))
hyp= Jay
B
m. (==(0-99)0))
B ma (e)
Define ( as h,- (8) + hys ( Ex jR, we select the edge (it, (R) according to the probability
(+) A exp(Bnt,,,,R)
F E {0, 13. Provided ma le) (1) > (m).)n((0) or equivalently, (C,
Ga 0,
we pick 7(th)= = R otherwise, we have 7((l) * jR. Due to the fact that (III concentrates on fi when 3 is sufficiently large, we can thus simply the MP update equation
=R;
ha
min Ex R h48 (PL,)))))); 13 = min Ext hat (() $2
(5)
which is obtained by letting 3 -
00. 00.
4 ANALYSIS OF ORACLE CASE
As warm-up example, we first consider the oracle scenario, where Bà is given prior. To reconstruct the permutation matrix II. we adopt the maximum maximan-likelihone (ML) estimator reading as
oracle argmax (II, T s.t. In 1 E
1 n. = 1III E {0, 1
(6)
Denote the variable Eoracle as -X (1) B + B. X, S n), we can transform
the objective function in 6 as the canonical form of LAP, i.e., - Ex, m,y Egrade,
4

---

Under review as a conference paper at ICLR 2023
4.1 IDENTIFYING THE PHASE TRANSITION THRESHOLD
This subsection studies the phase transition phenomenon inherent in the MP update equation ( Following the same strategy in Semerjian et al. (2020), we divide all edges ( into two categories based on whether the edge (7* corresponds to the ground-truth permutation matrix II or not. Within each category. we assumne the edges's 's weights and the message flows along them are independent identically distributed. For the edge (i', Tt (++)) corresponding to the ground-truth correspondence, we represent its weight as random variable called fi and the associated message flow as a random variable called H (both hp- s") and (V"->("))))>> Similarly, we define random
variables st and H for other edges. Then
rewrite
5 as
(++1) = min ( - (0) (())
((++1)
min Ω - - 15i5n-1
where ())() denotes the update in the 4th iteration, H' is an independent copy of H, and (H(()) hisign- and (Ri)isisn- denote the i.i.d. copies of random variables H(] and Q2))-
Then turn to computing the critical point where the permutation matrix can be perfectly recon- structed. According H this means the event H + H Q holds with probability one. Conditional on this event, we can simplify 7 to be
H(++1)
min 15i5n-1
11, (9 + +
(8)
where the random variable E is defined as the difference between 52 and Q i.e. E - 2 Ω. and {H. hisign- and { JEgisnn denote the i.i.d. copies of random variables and E()-
This equation can be viewed as the analogous version of the density evolution and state evolution, which are used to analyze the convergence of the message passing and approximate message passing algorithm, respectively (Chung) 2000, Richardson & Urbanke 2001 2008 Maleki] 2010 Donoho
cct al.
2009;
Bayati & Montanari 2011 Rangan 2011). Adopting the same viewpoint of Semerjian
al.
2020 treat
branching random walk (BRW) process, which satisfies
Theorem (Biggins 1977 Hammersley 1974 Kingman 1975 Semerjian al.
2020 Consider and E, are i.i.d E Ee 08:]] 0.:j.
the recursive distributional equation ((+++) minjsisn K-(") + E, where K
copies of random variables k(O) and Eg), we have ((--1)
a.. infozo 8 log
conditional the event lim, K(O # cc.
With Theorem can be computed by letting infe>o 1 log [_= EE [3.] S O, since otherwise the condition in will be violated. the oracle case where B is known, we have random variable E written as
we conclude the critical point for the correct permutation recovery, i.c., H+H > Ω.
== T (æ y) + TwB (x -ey- y))
where æ and follow the distribution N(O, Ipxp). and follows the distribution N(O, Imxm).
For the convenience of computation, we consider the simple case where B is XI pxp (m p)- Proposition 1. Consider the case where Ba is a re-sealed version of the identity matrix, i.e., AIpxp we can write the expectation Ie -0E, which is defined in
1 as
Ee _ = (1 20 0² x2 (X² + (
(10)
provided that
x² 1, and x2 (x² + 20
< 11+20 28X
(11)
Provided the conditions in |I] is violated, we have the expectation -6- -0 to diverge to infinity, which suggests the optimal 0, for infeso log(nBe (n)Be-B))) 3//8 cannot be achieved. Using 100 we can
compute the optimal 0, as 0, s BBE
2logn
The corresponding snroracl is written as
4
snforacle
(12)
m - 2 2og
The comparison between the theoretical values of the phase transition threshold and the numerical values are put in Table from which conclude the phase transition threshold snr can be predicted to a good extent. As m increases, we believe the gap between the theoretical values and the numerical values will keep shrinking.
5

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison between the predicted value of the phase transition threshold snroorae and its numerical value when = 500. P denotes the predicted value while N denotes the numerical value. value corresponds to the snforacle when the eπror rate drops below 0.05.)
20
30
40
50
60
70
P
3.283
1.415
0.902
0.662
0.523
0.432
N
2.466
1,290
0.862
0.644
0.513
0.426
4.2 APPROXIMATED COMPUTATION PHASE TRANSITION THRESHOLDS
The computation of phase transition threshold is by setting infa log(E2- /// be zero. However, in certain scenarios, can be extremely difficult impossible obtain closed-formula of Ee Ee-02 00 let alone the optimal solution 6. To handle such difficulties, we propose to approximate Ee -0-60__ with Taylor expansion, which proceeds as
Ee == = Ee ((3-EE)
! --8E
+ 2
0 R3)² Op (('E(E-E3)))
E
R
where ① is due to the fact IE (3 IE3) = 0. To simplify the computation, we adopt one widely-used assumption, stating
Assumption 1. We assume 8t E
E=
to negligible.
Then we obtain
(1
02 2
0 2 Varz
Ee Ee- 63 28 e
FEE
Var
exp -OBE
(13)
where in @ we use the approximation + x 2 e" when x is near zero. In this way, the rather complicated computation of E& - is replaced by the computation of mean TE and variance VarE, which is still complex but manageable. With this approximation, the optimal 0. for log(nEe *²)/o is computed as / 2 v//ar and hence the critical point corresponding to the phase transition as
2(log n) Var (EE)²
(14)
To verify that this approximation can yield meaningful results, revisit the oracle case and have
EE
| Var= = 3 B
20 B
(15)
Plugging
15 into
14
then yields the relation
log ri|
B'B I|:
4o (logn) B² I1
||
from which we can determine the critical point of snr.
Discussion, As a comparison, we first revisit the simple case where B is AIxxp (p m)) We can compute the phase transition snr as 1l0m This solution is almost identical to 12 in the large-system limit snForacle Snroracle ~ n 1. Moreover, we should stress that (i) our approximation method applies to other types of matrices as well, rather than limited to the identity matrix; and (ii) our approximation method can predict the phase transition thresholds even when the entries X.3 are sub- gaussian. An illustration is given in Table 2 in (Case D), half of eigenvalues are with Ener while the other half are with Ener/2; in (Case II), half of the eigenvalues are with Ener while the other half are with 3Eoer/4.
ANALYSIS OF NON-ORACES CASE
Having presented the oracle case as warm-up example, we now extend the analysis to the non-oracle case, where the value of Ba is not given prior. To begin with, we need to recast the permutation recovery problem as LAP. As shown in Zhang et al. (2022), the ML estimator yields a quadratic assignment problem (QAP), which is NP-hard solve and fails meet this requirement. Fortunately,

---

Under review as a conference paper at ICLR 2023
Table 2: Comparison between the predicted value of the phase transition threshold anraracl and its numerical value when 800. Gauss refers to Xij iid 1, I]. We averaged over experiments.
N(0, 1) while Unif refers to Xij iid
m
100
110
120
130
(Case
0.63
0.52
0.43
0.38
(Gauss) N
0.6 0.65
0.55
0.6
0.55 ~ 0.6
0.5 ~ 0.55
(Unif) N
0.6 0.65
0.6 ~ 0.65
0.55 ~ 0.6
0.55 0.6
(Case II) P
0.47
0.40
0.35
0.31
(Gauss) N
0.5 ~ 0.55
0.5 rv 0.55
0.45 ~ 0.5
0.45 ~ 0..
(Unif) N
0.5 ~ 0.55
0.5
0.45 ~ 0.5
0.45 ~ 0.5
the proposed estimator in Zhang & Li 2020) is able to fill the gap. Define the edge weight bj
Eran- as Enen-orace oracle & YY,Y Xxx; we can reconstruct the permutation matrix II2 as TT. Before proceeding. Eig
would like justify using the estimator in Zhang & Li (020)) analyze the permuted linear regression in the non-oracle case: first, this estimator is proved to achieve both the computational and statistical optimality; second, this estimator also exhibits a phase transition phenomenon, which behaves similarly to that in the oracle case. Naturally, we should expect this estimator will incorporate some inherent properties of the permutation recovery problem (with unknown B3), from which we can gain meaningful insights.
5.1 ANALYSIS OF NON-ORACLE CASE
Having illustrated soundness of the approximation method where the random variable is written
we apply the non- non-oracle case,
= E +o ( o'
(16)
where E; (1 S i < 4) are defined as
E X (i)
B x
x
X xb(())
X,);
E a X B X (X - -X,);
Eg W B IT
x
(()
X,);
E A W. W
X (()) -x,)
respectively. Then we conclude
Theorem 2. The mean IE of = in
39 and its variance Var are computed
E n Tm) (1 Tp)
B TT
Var ~ n2 (1 Tm) Tタ
B mo²]
+ n²
2Tp + 31
mh)²
|| Bill
+ GTD (1 - Th) + (3 Th)
B |
respectively, where the definitions of Tp. Tm and Th can be found in Section
For the clarity of presentation, we only present the proof outlines.
Computation of mean EE For the computation of the mean IE, easily we can verify that EE₂ and EEg are both zero, which due to the independence between X and W. Regarding the computation of EE, and EE4, we adopt Wick's 's theorem and obtain
EE = n (1 Th) (1 Tp) ) 1 (1)) |I EE, = ni Tm (1 Th) (1+ (1)).
Computation of variance VarE. With the relation Var(E) E=² (EE)) our goal becomes computing EEE2, which consists the calculation of the following six terms
E BE + O' "'E のf EE 20 + 20 EE,Ea
The computation of above terms turns to be quite complex due to the high order Gaussian chaos. For example, term EE$ involves the eighth-order Gaussian chaos; terms EE3, EE3 EE, and EE,E, all involves the sixth-order Gaussian variables. To alleviate the computational burden, we compute the expectation E= in the following three phases.
7

---

Under review as a conference paper at ICLR 2023
Table 3:
Comparison between the predicted value of the phase transition threshold and its numerical value when n = 500. denotes the predicted value while N denotes the numerical value. (The numerical value of is the minimum when the correct permutation rate drops blow 0.05.)
75
100
125
150
175
200
P
0.82
0.73
0.68
0.62
0.56
0.52
0.77
0.74
0.7
0.66
0.61
0.57
Phase I. The solution in this phase comes from a modification of the so-called leave-one-out technique (Sur et al., 2019 El Karoui 2013 2018 Bai & Silverstein 2010). Notice that the major technical difficulty comes from the correlation between the product X "I'X and the difference ( Xj. We decompose this correlation by first rewriting the matrix X II
as the sum XXX,X (1)- Then we collect all terms X,X (3(()) independent of x and X, in the matrix E
and leave the rest terms to matrix A, which means X Σ. This decomposition is in the same spirit of the leave-one-out technique.
With this method, we divide all terms involved in the computation E=² into three categories: (i) those only containing matrix Σ; (ii) those containing both E and A; and (iit) those only containing Easily we can see the first two categories contain most vectors' outer products while the last category only contains finite number of such terms.
Phase II. Concerning the terms in the first two categories, which contains majority of terms, we can exploit the independence among rows in the sensing matrix X and reduce the order of Gaussian random variables by separately taking expectation w.r.t Σ and w.r.t vectors X (1)) and X,.
Phase III. For the few terms in the third category which contains high-order Gaussian chaos, we compute their expectations by iterative applying of Wick's Theorem and Stein's 's Lemma, which filters out the zero terms to reduce higher-order interactions between Gaussian random variables to lower-order interactions.
For more technical details, we refer the interested readers to the supplementary material.
5.2 IDENTIFYING THE PHASE TRANSITION THRESHOLD
Having explained the computation of EE and VarE, we turn to identifying the phase transition threshold. Different from the oracle case, notice the edge weight Fij are strongly correlated in this case especially when (z), which corresponds the non-permuted rows. To factor out these independence, we only take the permuted rows into account and correct the sample size from n TR... Thus, have
Proposition 2. The critical point for the phuse transition phenomenon transforms from 2 (log n. Var = (RE)).
14 to
Example 1. We consider the case where B = =XIxxp as an illustration. With Theorem and
Proposition we obtain the solution
Shr non-oracle -1/m.
(17)
where in and up are defined as
Th 2 2T T log (nTh) - (T + (1 Th) + V2 Th)Th (log (nTr)):
1/2 Tn log(nns) (1 (1-Th) Th) (Tp +
Notice that the negative solution has been abandoned due to the non-negativin requirement snr.
Discussion. For the accuracy of the predicted phase transition nonnon-orle.. notice a increasing gap between the theoretical value and the numerical value when compared with that in the oracle case. Possible reasons include strong correlation across the edge weights (Figh Jiijsn and the error within the approximation relation Ee -6- E Exx (+EZ 8 VaEE2).
In addition, we observe a singularity point, i.e., Tn is approximately 0.73 in Figure 2 which suggests phase transition phenomenon. To validate the predicted phenomenon, we consider the noiseless
8

---

Under review as a conference paper at ICLR 2023
case, i.e., snr and reconstruct the permutation matrix II with ①. Numerical experiments confirm our prediction by showing that the correct rate of the permutation recovery exceeds 0.2 when h/n I 0.73 and drops below 0.05 when h/n 0.74. Additional experiments from which we conclude the solution
put in Table F 17 can predict the critical points w.r.. Th to a good extent.
Remark 1. Compared with the prior work Zhang & Li 2020 which only yields the statistical order, Le. 8/2 S e fe is positive constant), our framework can (i) specify the positive constant e, and (ti) uncover the dependence of Th on the ratio Tp- In addition, Zhang & Li (200)) requires >> p while our work allows n to be the same order of p. i.e, p/n To as P.P P + Oo. Notice that this is consistent with numerical experiments such that Op (p) is sufficient for the permutation recovery.
6 PARTIAL PERMUTATION RECOVERY
Apart from the phase transition thresholds, we would like to exploit MP to design algorithms for a partial permuta- tion recovery. As an illustration, we consider recovering the correspondence T (1) for single index i. In ef- fortless way, we can generalize to recovering the corre- spondences for multiple indices by iterative applying the following procedure.
100
29
0.5
0.6
0.7
0.8
0.9
To start with, we modify the graphical model in Figure by removing the unnecessary function nodes and their in- cident edge. Then we can rewrite the MP update equation
Figure 2: nonnoroee when 500 and
p = 100.
(P)(()))(T)))
EI exp AR 1 + Σ
TH = 1).
k
Compared with the MP for the full permutation recovery, MP for the par- tial permutation recovery can reach convergence in one iteration. Letting + 0o, we obtain the edge selection criteria as
Duiid Donnny
P0 (1)
Purta Hermery
4.6
0.8
14
Orsck
0.4
Non-Orade
7( = argmin, Eaj,
02
02
which turns out to be a greedy selec- tion scheme.
8.25
0.50
0.75
0.90
5.5
3.5
692
Figure 3: Comparison between the full permutation recovery and partial permutation recovery. We set n = 500, p = 100, and m 75. The partial permutation recovery estimator also exhibits a phase transition, similar to the full permutation recovery estimator. However, their phase transition points are larger when compared with the corresponding points for the full permutation recovery.
Following the same procedure as in Sections 4 and [ we can analyze its statistical properties, which are simi- lar (although degraded) to the estima- tor for the full permutation recovery thereof (both the oracle case and non- oracle case). This claim is also confirmed by numerical experiments in Figure 3
7 CONCLUSION
This is the first work that can identify the precise location of phase transition thresholds of permuted linear regressions. For the oracle case where the signal 8 is given a prior, our analysis can predict the phase transition threshold snroradl to good extent. For the non-oracle case where Ba is not given, we modified the leave-one-out technique to approximately compute the phase critical snr oracle value for the phase transition, as the precise computation becomes significantly complicated as the high-order interaction between Gaussian random variables is involved. Moreover, we associated the singularity point snr prnncce with phase transition point w.r.t the maximum allowed number of permuted rows. In the end, we generalized the full permutation recovery and obtained partial permutation recovery algorithm. Following the same analytical procedure, we argued it would have similar although degraded performance compared with the full permutation recovery algorithm, which is later confirmed by our numerical experiments. In the future, we will incorporate the replica symmetry breaking scheme into our framework and extend this framework to broad areas.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zhidong Bai and Tailen Hsing. The broken sample problem. Probab, Theory Relat. Fields, 131(4): 528-552, 2005.
Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
Mohsen Bayati and Andrea Montanari. The dynamics message passing on dense graphs, with applications compressed sensing. IEEE Transactions on Information Theory, 57(2):764-785, 2011.
JD464415 Biggins. Chernoff's theorem in the branching random walk. Journal of Applied Probability, 14(3):630-636, 1977.
Sergio Caracciolo, Matteo P D) Achille, Enrico M Malatesta, and Gabriele Sicuro. Finite-size corrections in the random assignment problem. Physical Review E, 95(5):052129, 2017.
Michael Chertkov, Lukas Kroc, F Krzakala, M Vergassola, and L Zdeborová. Inference in particle tracking experiments by passing messages between images. P Proceedings of the National Academy of Sciences, 107(17):7663-766) 2010.
Sae- Young Chung. On the construction of some capacity-approaching coding schemes. PhD thesis, Massachusetts Institute of Technology, 2000.
Morris H. DeGroot and Prem K. Goel. The matching problem for multivariate normal data. Sankhyā: The Indian Journal of Statistics, Series B (1960-2002), 38(1):14-29, 1976.
Morris H. DeGroot and Prem K. Goel. Estimation of the correlation coefficient from a broken random sample. The Annals Statistics, 8(2):264-278, 03 1980.
Morris H. DeGroot, Paul I. Feder, and Prem K. Goel. Matchmaking. Annals of Mathernatical Statistics, 42(2):578-593, 04 1971.
David I. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciiences 106(45):18914-155) 2009.
Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results. arXiv preprini urXiv:1311.22. 2013.
Noureddine Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. Probab. Theory Relat. Fields, 170(1-2): 95-175, 2018.
Prem K. Goel. On re-pairing observations in broken random sample. The Annals of Statistics, 3(6): 1364-1369, 11 1975.
John M Hammersley. Postulates for subadditive processes. The Annals of Probability, 244)622-660 1974.
Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge university press, 1990.
Svante Janson. Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics. Cambridge University Press, 1997. doi: 00.1017/C8097805115526
John Frank Charles Kingman. The first birth problem for age-dependent branching process. The Annals of Probability, pp. 790-801, 1975.
Frank Kschischang, Brendan Frey, and H-A Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on information theory, 47(2):498-519, 2001.
Svante Linusson and Johan Wästlund. A proof of parisi's 's conjecture the random assignment problem. Probability theory and related fields, 128(3):419 440, 2004.
David JC MacKay, David JC Mac Kay, et al. Information theory, inference and learning algorithms. Cambridge university press, 2003.
10

---

Under review as a conference paper at ICLR 2023
Enrico M Malatesta, Giorgio Parisi, and Gabriele Sicuro. Fluctuations in the random-lint matching problem. Physical Review E, 100(3)003202, 2019.
Mohammad Ali Maleki. Approximate message passing algorithms for compressed sensing. Stanford University, 2010.
OC Martin, M Mézard, and Olivier Rivoire. Random multi-index matching problems. Journal of Statistical Mechanics: Theory and Experiment, P009(09) 2005.
Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Marc Mézard and Giorgio Parisi. Replicas and optimization. Journal de Physique Lettres, 46(17); 771-778, 1985.
Mare Mézard and Giorgio Parisi. Mcan-field equations for the matching and the travelling salesman problems. EPL (Europhysics Letters), 2(12):913, 1986.
Mare Mézard and Giorgio Parisi. On the solution of the random link matching problems. Journal de Physique, 48(9):1451-1455 1987.
Heinz Neudecker and Tom Wansbeek. Fourth-orde properties of normally distributed random matrices. Linear Algebra and Its Applications, 97:13-21, 1987.
Ashwin Pananjady, Martin J Wainwright, and Thomas Courtade. Denoising linear models with permuted data. In Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), pp. 446-450, Aachen, Germany, 2017.
Ashwin Pananjady, Martin J. Wainwright, and Thomas A. Courtade. Linear regression with shuffled data: Statistical and computational limits of permutation recovery. IEEE Trans. Inf. Theory, 64(5); 3286-3300, 2018
Giorgio Parisi and Matthieu Ratiéville. On the finite size corrections to some random matching problems. The European Physical Journal 8-Condensed Matter and Complex Systems, 29(3): 457-468, 2002.
Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. In Information Theory Proceedings (ISIT), 2011 IEFE International Symposium on, pp. 2168-2172. IEEE, 2011.
Thomas J Richardson and Rüdiger L Urbanke. The capacity of low-density parity-check codes under message-passingg decoding. IEEE Transactions on information theory, 47(2):599-613 2001.
Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008
Guilhem Semerjian, Gabriele Sicuro, and Lenka Zdeborová. Recovery thresholds in the sparse planted matching problem. Physical Review E, 102(2):022304, 2020.
Martin Slawski and Emanuel Ben-David. Linear regression with sparsely permuted data. Electron. J. Statist., 13(1):1-36, 2019.
Martin Slawski, Emanuel Ben-David, and Ping Li. Two-stage approach multivariate linear regression with sparsely mismatched data. J. Mach. Learn. Res., 21(204): 2020.
Pragya Sur, Yuxin Chen, and Emmanuel J Candès. The likelihood ratio test in high-dimensional logistic regression asymptotically a rescaled chi-square. Probab. Theory Relat. Fields, 175(1-2): 487-558, 2019.
Michel Talagrand. Mean field models for spin glasses: Volume I: Basic examples, volume 54. Springer Science & Business Media, 2010.
Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, and Martin Vetterli. Unlabeled sensing: Solving linear system with unordered measurements. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 786-793, Monticello, IL, 2015.
11

---

Under review as a conference paper at ICLR 2023
Hang Zhang and Ping Li. Optimal estimator for unlabeled linear regression. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 11153-11162, Virtual Event, 2020.
Hang Zhang, Martin Slawski, and Ping Li. The benefits of diversity: Permutation recovery in unlabeled sensing from multiple measurement vectors. IEEE Trans. Inf. Theory, 68(4):2509-2529, 2022.
12


Reviews:
[{"review_id": "bi-I6kikvlj", "reviewer": "Reviewer_PjJn", "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": "This work explores the high dimensional limit of a permuted linear regression problem with Gaussian sensing matrix and additive Gaussian noise.  Thanks to the introduction of a tailored graphical model, the authors build a Message Passing (MP) algorithm to reconstruct the permutation matrix $\\Pi$. The theoretical analysis is focused on the precise characterization of the phase transition for perfect recovery of $\\Pi$. The authors first study the oracle case, in which the signal of interest is known, and secondly the non-oracle scenario. The snr threshold is predicted analytically by writing recursive distributional equations and exploiting a mapping to a branching random walk process; an approximation framework is proposed to deal with untractable cases. Numerical experiments which highlight the phase transitions are presented, and the theoretical predictions are close to the algorithmic ones. ", "summary_of_the_review": "My score is due to the nice findings presented in this submission. My main concerns are about the lack of clarity in the presentation and the reproducibility of the results in this submission. The present grade is dependent on the future release of the code.", "strength_and_weaknesses": "The paper is generally pleasant to read and the introduction offers an interesting broad picture of the field. The precise characterization of the snr threshold for the full recovery of $\\Pi$ is a novel contribution. The details of the technical discussion are properly explained, indeed both the construction of the MP algorithm and the approximation method are discussed thoroughly. The analysis of the distributional equations via the connection with a BRW process is correctly reported. \n\n\nThe comparison of theoretical and algorithmic prediction is done in different scenarios and accompanied with numerical simulations, however the clarity in the presentation of the results could be improved.\nThe proposed approximation framework to pinpoint the threshold is interesting, although the mapping to a BRW process has been already presented in *Semerjan et al. 2020*, which marginally limts the originality of the work. There is almost no discussion about the limitations of this work, e.g. the restricting assumption about additive Gaussian noise, and the motivations for future directions of research are briefly reported.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ND0Fzms5Kh", "reviewer": "Reviewer_K1xv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper considers the problem of permuted linear regression. Here, you are given $Y \\in \\mathbb R^{n \\times m}, X \\in \\mathbb R^{n \\times p}$ such that $Y = \\Pi X B + W$ where $\\Pi$ is an unknown permutation matrix, $B \\in \\mathbb R^{p \\times m}$ is the signal matrix, $X \\in \\mathbb R^{n \\times p}$ is the set of Gaussian measurements and $W$ is additive Gaussian noise.  From these, the goal is to reconstruct the unknown permutation matrix. \n\nThis paper focuses on identifying the phase transitions that occur for this problem, in terms of recoverability, as the parameters tend to infinity with ratios of the relevant parameters tending to some bound. They attempt to predict the phase transition in the limit by investigating the behaviour of a message passing algorithm. \n\n", "summary_of_the_review": "Overall, I think this is an interesting paper that attempts to predict the relationships between various parameters in the large-system regime, at the points of phase transition (specifically, they predict the snr at which the phase transition occurs). Unfortunately I am not extremely familiar with the literature surrounding message passing algorithms, and so my confidence is low. ", "strength_and_weaknesses": "Strengths: \n1. I think the paper proves an interesting result, demonstrating the phase transitions that occur for this problem.\n\nWeaknesses:\n1. The paper has a several typos, it might help to put the prose through a grammar and spell checker. \n2. The techniques used in the paper seem standard. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LZ3Ddmt_bA", "reviewer": "Reviewer_eTFJ", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "In this paper, the authors studied the permuted linear regression problem using the message-passing framework.\n\nThe authors argue that they identify the **precise locations** of the phase transition phenomenon in this problem.\n\nThe analysis is divided into two cases, the case where the ground-truth B is given (the oracle case), and the case where it is not.\n\nFinally, the authors propose an estimator for partial permutation recovery.", "summary_of_the_review": "I am not an expert in the field. Thus I did not evaluate the technical contributions.\n\nHowever, my judgment is that the paper makes a lot of claims that are not well supported by theory or experiments, and the writing is highly sub-optimal. This renders the paper inaccessible to an ordinary ICLR reader and inappropriate for ICLR publications. \n\nI recommend the authors make a significant revision and consider resubmission to other avenues (e.g., for statisticians or physicians). Actually, the paper might have a better fate if submitted to AISTATS.", "strength_and_weaknesses": "# Weaknesses\n\n1. Proposition 1 relies on an unrealistic assumption where $B$ is a rescaled identity matrix.\n2. The paper contradicts itself by arguing two converse points. On the one hand, the authors congratulate on their identifying the **precise locations** of the phase transition phenomenon for the problem of interest. On the other, the title of Section 4.2 indicates that the phase transition threshold is computed **approximately**.\n3. The authors argue that they propose **the first framework** for something. The word **framework** is so vague that it does not make sense to me. If it means the message-passing framework, it has already been known. \n4. The authors argue that the proposed partial permutation estimator is a **generalization** of the full permutation estimator. This claim is not supported by any explanations.\n5. The authors argue that **the empirical phase transition points are well aligned with theoretical predictions**. However, the theoretical results are asymptotic, and the empirical results are for finite samples. There is a huge gap between practice and theory, and this claim amounts to aligning apples with oranges.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "J2LZK1MqBc1", "reviewer": "Reviewer_tsTr", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors study phase transitions in linear regression with permuted labels for both the oracle setting (in which the regression coefficients are assumed to be known) and the non oracle setting (in which both the permutation and the regression vector are considered as unknown). The main result of the paper is an estimator for the signal to noise ratio above which recovery of the permutation matrix is possible in the absence of any estimate for the regression coefficients. The result relies on an estimator for the permutation matrix derived in a previous paper (Hang Zhang, Ping Li, Optimal estimator for unlabeled linear regression) and applies the machinery of Semerjian et al 2020 (cavity method) to derive the phase transition.\n\n\n", "summary_of_the_review": "I don't think the paper can be accepted in its current state. Although the result is interesting, the paper should either be seriously reorganized or submitted to a journal which would allow for a longer and clearer exposition.  Detailed comments can be found below.\n\n\npage 2\n- The second item when you expose your technical contributions is not very clear \n\npage 3\n\n- In figure 1, it is difficult to read the expression in the red square\n\npage 4\n\nI’m in favor of removing the whole section as it appears exactly in this form in Mezard and Montanari Chapter 16. (A couple of comments can be found below)\n\n- Section 3.2. When you say “here L and R are used to denote the positions of the nodes” do you mean the row vs column indexing ? This is unclear\n- Your introduction of the messages in (3) is not clear. Honestly the \\cong notation is misleading, why not use the traditional \\leftarrow. What you are introducing here are the messages updates. Also you should really get rid of the \\hat{m} e^{-\\beta \\pi_{i,k} E}… that appears in the second line and replace it with the RHS from the first update. Expanding the expression only makes things more confusing than they are\n- Do you really need to keep the L and R indices, that makes the notations so much heavier\n- I feel like the second equation between (3) and (4) in which you introduce the log ratio is redundant. \n- Is \\zeta (above (4)) the same as \\zeta_{i,j} ? if so you should keep the same notation.\n- The whole section on MP has to be rewritten. You introduce variables from nowhere. Below equation (4), what is \\hat{\\pi} ? We can somewhat guess  that it corresponds to the (estimated) permutation operator but for that same operator you used ‘\\pi’ on page 2 and ‘pi^\\sharp’ on page 3. Why not just keep pi for the entries in the matrix \\Pi?\n- It is very difficult to follow on your definition of the cavity fields in Equation (5). In fact you should rewrite the transition. At least add a reference to (5) in the paper of Semerjian. For someone who has not read the paper, it is absolutely unclear where the updated BP equations on the cavity fields come from (in particular the min which appears out of nowhere)\n- Honestly, you should provide a clear reference to section (16) in Mezard and Montanari or (15) in Semerjian\npage 5\n- When you introduce the random variables H and \\hat{H}, you skip a number of steps and that makes the reading of the paper quite painful. E.g. you again need to zero temperature limit for (7) to hold if I’m not wrong\n- What you call the message flows are the cavity fields?\n- You can introduce the independent copies because you have equality in the distributional sense (again I think you should specify this, otherwise you lose the reader who is not familiar with the cavity method)\n- The equations in (7) are the same as (48a) and (48b) in Semerjian but if you look at (48b) the first update is carried only with probability (1-q). Also look at (29a) (29b)\n- The transition from (4) to the condition H+H’>\\Omega is unclear. Either provide a reference or expand\n- The definitions of the random variables Omega and K are unclear. If I’m not wrong, you never introduce the K that appears in the statement of Theorem 1. If I’m not wrong the K has a precise definition as a lower bound for H following from a simplification of the Recursive Distributional Equations for H. This should be properly introduced.\n- Also your notion of phase transition is unclear. What is meant by phase transition here? Once again, there is too much content and the essentials are missing. If you look at the Semerjian paper, those notion are carefully introduced. E.g. the authors take the time to explain that in the large n (or in your case t) limit, a value of K (and hence H since K lower bounds H) going to infinity implies that the only solution to the BP equations is the solution H = +infty. we are thus interested in the transition from the setting where there are possibly other solution (i.e. K\\neq \\infty) to this last setting. This explanation should appear in your paper\n- In (12) you introduce an SNR but there is no explanation on where that SNR comes from or even what it encodes. We can sort of guess it is related to the sigma in (6) and on page 2 but the connection is unclear \n- When you introduce the SNR, is that the SNR between Pi*X*B and W at which the transition occurs ? You should elaborate on this. Is the SNR related to sigma?\n\npage 6\n- Why is assumption 1 a good assumption ? You say “widely used assumption” but you don’t provide any reference\n\n- Section 4.2. is particularly unclear.  \n\n- In the discussion before section 5, when you discuss subGaussian matrices What is ENER ?\n\n- Honestly, your introduction of the two different approaches to derive the threshold SNR is unclear. From what I understand, you first use the solution of inf 1/\\theta * \\log(\\sum_i \\mathbb{E} e^{-\\theta \\Xi_i}) for which you have to compute the average  E{e^{-\\theta \\Xi}} exactly and then you use the taylor expansion approach (which you want to use in the non oracle case). You motivate the second approach by saying that it is not always possible to compute the expectation. Yet in this case (since you restrict to the identity) you just computed this expectation so why use the simplification? You should clearly explain why you discuss both approaches (i.e. add a short sentence such as “Solving the non oracle case requires an approximation on the expectation \\mathbb{E} e^{\\theta \\Xi}. We first motivate such an approximation by showing that it can be related to the exact solution for the SNR, in the particular case of the identity”). \n\n- From what I understand the conditions  inf_\\theta (1/\\theta) \\log\\left(\\mathbb{E} Z * \\mathbb{E}e^{-\\theta\\Xi}\\right) and inf_\\theta (1/\\theta) \\log(n \\mathbb{E} e^{-\\theta \\Xi}) are the same. what you do is, in the first approach, you compute the exact expectation, in the other, you use an approximation. But this is very poorly explained\n- Can you claim that your approximation is sound just because it works for the identity ?\n\npage 7/8\n\n- The connection between the oracle and the non oracle case is not very clear. In particular, why can you apply the same machinery in the non oracle case as the one you use in the oracle case? I.e. from the paper it seems straightforward that the phase transition in the non oracle setting occurs when -inf_theta \\frac{1}{\\theta} \\log\\left[\\sum_i \\mathbb{E} e^{-\\theta\\Xi_i}\\right] or inf_\\theta \\log(\\mathbb{E}Z \\mathbb{E}e^{-\\theta\\Xi}). Yet this does not seem straightfoward to me. I.e. when you say “second, this estimator also exhibits a phase transition phenomenon, which behaves similarly to that in the oracle case”, can you expand a little more ?\n\n- You should give a more detailed reference (indicate Algorithm 1?) to your 2020 paper (i.e. Zhang et Li) in which you introduce the estimator for Pi.\n\n- How do you go from your estimator (i.e the 2020 one to the matrix Xi? further explanation is needed here). If I understand well, because your estimator does not rely on the regression coefficients, you dcan apply the BP equations to this estimator to study the phase transition. if so you should add that somewhere. \n\n- In the statement of Theorem 2, you reference an equation (39) in appendix\n\n- I would remove the proof details for Theorem 2 as it is just the computation of an expectation (i.e. everything can be done by means of Isserlis' theorem) and your explanation of the three phases is unclear. I think no one will blame you for not providing the details of the computation of an expectation. But if what you provide is unclear, then a the reader will start to question the whole paper.\n\n- In the very last paragraph of page 8 you mention a gap between the theoretical value and the numerical value. What gap are you talking about? Where are the numerical experiments ? Are you talking about The result from table 3, then you should add a reference to that table.\n\npage 9\n\n- At the beginning of page 9 (first paragraph), you again indicate that numerical experiments confirm your results while not adding any reference to those experiments. Are you talking about Figure 2/Table 3 because the captions of those do not seem to relate to what you say on page 9\n- I would consider removing section 6. The section should be expanded and is unclear in its current state. Why would you want to do partial recovery if you can apply the full recovery algorithm. You need to better motivate this (for example in terms of computation) or remove it.\n- The discussion is not clear. From what I understand the SNR already represent the SNR at which the phase transition occurs. Then you indicate that there is a possible phase transition w.r.t tau ? what do you mean? there is a regime in which you can’t predict anything ? i.e. no SNR will enable the recovery? This also appears surprising to me that this regime corresponds to a very narrow subset of tau values (as your plot in Figure 2 seems to indicate). How do you explain this? \n\nAs a side note, I find it surprising that the Hamming distance of the permutation matrix to the identity seem to matter for the phase transition but maybe this is a well known fact. \n\n================================================================\n\nTypos/syntax errors \n\n================================================================\n\npage 1\n- fisrt paragraph: “we have witnessed a revival of this problem due to its board spectrum” —> I guess you mean “broad”  \n- The result introduced in Zhang et Li 2020 is indeed very similar to the work of the paper\npage 2\n- When you say “the maximum allowed permuted rows”, do you mean the “maximum allowed number of permutations”?\n- When you introduce your technical contributions, “By removing all function nodes except that corresponds to that index” —> “except the one that corresponds”\n- Again, when you introduce your technical contributions : “an algorithm that converge in one step “ —> “that convergeS”\n- “its performance almost match” —> “its performance almost matchES”\n\npage 4\n\n- Before Equation 5: “we can thus simply the MP update equation as” —> “we can thus simply write”?\n- Before Equation 6: “where B^ sharp is given a prior” —> “B^\\sharp is given as a prior” ?\n\npage 6\n- section 4.2. “to obtain a closed-formula” —> “A closed form expression”?\n- First paragraph of section 4.2. “The computation of phase transition threshold is by setting”  —> “The phase transition can be estimated from“ ?\n- In the title of section 4.2. : “APPROXIMATED COMPUTATION ” —> “Approximate computation”\n\npage 7\n- Computation of the mean: “easily we can verify” —> “we can easily verify”\n\npage 8\n- Phase 1 of the computation of the variance : “This decomposition is in the same spirit of the leave-one-out technique” —> “in the same spirit as …”\n- Right before the subsection “Computation of Var \\Xi”: “which consists the calculation of the following six terms” —> “which consists OF the calculation of…”\n- Phase 2 of the computation of the variance : “we can exploit the independence among rows” —> “among the rows”\n- Phase 2 of the computation of the variance: “which contains majority of terms” —> “which contains THE majority of THE terms”\n- Same phase: “reduce the order of Gaussian random variables” —> “of THE Gaussian variables”\n- Same phase: “by separately taking expectation’ —> “by taking THE expectation”\n- When you explain phase 1 for the computation of the variance, “and leave the rest terms to matrix” —> “the rest OF the terms” or even better “the remaining terms”\n- In the discussion paragraph at the end of the page: “we notice a increasing gap” —> “AN increasing gap“\n- In the caption of table 3, “rate drops blow 0.05 ” —> “drops below”?\n\nPage 9\n- At the beginning of the first paragraph you say “Numerical experiments confirm our prediction ”. Which numerical experiments are you talking about ?\n- In the conclusion: “For the oracle case where the signal B is given a prior ” —> “is given AS a prior”\n\n\n\n", "strength_and_weaknesses": "The paper is interesting although poorly written. I have some concern with (1) the incremental nature of the result; Although there is a clear mathematical venture/achievement and the necessary associated hard work, the novelty lies in part in an approximation (based on a Taylor expansion) used to compute the phase transition when considering the non oracle setting; and perhaps more importantly (2) the organization/intelligibility of the paper.  The first part of the paper is very similar to Semerjian et al 2020 and the second part is an analysis based on the estimator provided in Zhang et al 2020. A reader unfamiliar with the former paper will have a very difficult time going through the notations. See below for more details\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6AzNEoadUx", "reviewer": "Reviewer_vjWT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper studies the phase transition thresholds of permuted linear regression in terms of the signal-to-noise ratio (snr). The authors first consider the oracle case where the signal of interest is known and predict the phase transition threshold $\\mathrm{snr}_{\\mathrm{oracle}}$. \n\nThen, they study the non-oracle case where the signal of interest is not given and approximately identify the phase transition threshold $\\mathrm{snr}_{\\mathrm{non-oracle}}$ based on a modification of the leave-one-out technique. In addition, the full permutation estimator is generalized to a partial permutation estimator in Section 6. ", "summary_of_the_review": "Based on all the above comments, my impression is that this submission is not ready for publication in the current version.", "strength_and_weaknesses": "Strength:\n\nA precise identification of the phase transition thresholds for permuted linear regression would be of interest.\n\nWeaknesses:\n\nAs far as I can tell, the major contribution is the derived phase transition threshold $\\mathrm{snr}_{\\mathrm{non-oracle}}$ for the non-oracle case.  In particular, the assumption about a known signal matrix seems to be not practically meaningful (and it is mentioned at the beginning of Section 4 that it is a \"warm-up\" example), and the analysis seems to be simply a corollary of the well-established Theorem 1 in prior works. In addition, from this submission, I cannot see the practical motivation for considering partial permutation recovery instead of full permutation recovery. (The authors claimed on page 2 for the partial permutation estimator that \"we show its performance almost match the estimator for the full permutation recovery\". But this claim is clearly overstated according to Figure 3 which shows that partial recovery clearly requires significantly larger snr). \n\n\nMoreover, the writing of the paper is somewhat messy or non-rigorous:\n\n- The authors mentioned on page 2 that \"In the non-oracle case where $\\mathbf{B}^♮$ is not given, our scheme can further predict the maximum allowed permuted rows and uncover its dependence on the ratio $n/p$\". Such a sentence is a bit strange. If the authors want to include the results for the simpler oracle case in the main document, it is better to also include the prediction for the maximum allowed permuted rows and the uncovering of its dependence on the ratio $n/p$ for the oracle case.\n\n- Assumption 1 is weird. The authors should provide justifications for it (and provide a rigorous characterization of \"to be negligible\"), instead of saying that it is a widely-used assumption.\n\n- It is difficult for me to follow how the authors go from Theorem 2 to Proposition 2. In addition, in Example 1, the case that $\\mathbf{B}^♮$ seems to be not practical. I hope that there are more discussions on Proposition 2 and the corresponding examples.\n\n- In Table 2, for the numerical values, $0.6 \\sim 0.65$ is a strange form of representation. It should be $\\mathrm{mean} \\pm \\mathrm{std}$. Similar modifications should also apply to the numerical values in Table 1.\n\n- $\\mathbb{O}_P(\\cdot)$ is used on page 1 before its definition in the Notations section. The authors should mention that $\\mathbf{W}_i$ represents the $i$th row of $\\mathbf{W}$. In Eq. (6), the constraints can be simplified as $\\mathbf{\\Pi} \\in \\mathcal{P}_n$, which has been defined in the Notations section.   \n\n- In the Discussion on page 6, $\\tilde{snr}_{\\mathrm{oracle}}$ appears suddenly (it seems to be a redundant notation) and what does $\\mathrm{Ener}$ refer to? In the statement of Theorem 2, the referred Eq. (39) is in the supplementary material (and in fact, it should be Eq. (40)). It is better to write down Eq. (40) explicitly in the main document.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject