The Phase Transition Phenomenon of Shuffled Regression

Thanks for your positive comments and support of our work. We are glad that you like our paper and find our paper well-written and accessible to audiences not familiar with this area. We really like your comment that our paper makes significant technical contributions and our theory's accurate capture of the phase transition phenomenon.

In addition, we would like to highlight that our main results obtained with complex derivations, especially those concerning the higher moments of Gaussian random variables, can be reused and serve as independent technical interests.

Moreover, let us answer your question concerning the connections to phase transitions studied in other problems. The most related work are (Montanari & Mezard, 2009) and (Semerjian et al, 2020). In (Montanari & Mezard, 2009), all edge weights are i.i.d. samples and there is no phase transition behavior. Whereas, (Semerjian et al, 2020) observe the phase transition behavior when switching the independent identical distribution (i.i.d.) assumption to independent non-identical distributions. Hence, we conjecture the phase transition is caused by the distribution discrepancy among different edges.

Again, thanks for your review of our work.

Next, let us address your other questions.

1. Justifications of weak correlations of matrix $E$ for the oracle case.

First, we can calculate the correlations between entries in $E$. We can find most of these correlations are zero. There are only two scenarios with non-zero correlations, (i) $E_{\pi(i), \pi(i)}$ $E_{\pi(j)\pi(j)}$ and (ii) $E_{i \pi(j)}$ $E_{j \pi(i)}$, which is with $O(n)$ number while the total edge number is $O(n^2)$. In this sense, we can say $E$ is only weakly correlated. In addition, the numerical evidence in Table 1 and Table 2 also suggests that we can safely ignore these weak correlations and predict the phase transition points to a good extent.

2. Meaning of phase transition.

We use the term phase transition to denote the phenomenon such that a small change in the parameter will lead to a sudden change in the reconstruction performance. That is, the error rate drops from one to zero drastically when SNR exceeds the threshold. The meaning of phase transition can be observed in Table 1, Table 2, and Figure 2, where we specifically study the change in error rates.

Dear Reviewer, we would like to first thank you for recognizing our method to be original and promising. Please allow us to clarify the statistical optimality of LAP/QAP in the non-oracle case, where there seems to be a misunderstanding.

First, whether the QAP will reach the statistical optimality still remains an open problem. To the best of our knowledge, the only related work is (Zhang, Slawski & Li, 2022) but they only prove the optimality holds for a restricted region. More specifically, they require the $\textup{rank}(B) \leq c\log n/n$.

Second, the optimality of LAP over a wide range is answered by the cited work (Zhang & Li, 2020) (c.f. one line above Equation (19)). Work (Zhang & Li, 2020) show that the mini-max lower bound of SNR requirement, i.e., no estimator can obtain the correct permutation matrix provided that $\log SNR \leq c_0 \log n/\textup{stable-rank}(B)$; and the LAP in Equation (19) can obtain the correct permutation matrix when $\log SNR \geq c_1 \log n/\textup{stable-rank}(B)$ ($\textup{stable-rank}(B)=|B|_F^2/|B|^2$ is the stable rank).

Interestingly, based on the current literature, the LAP estimator in Equation (19) can actually reach statistical optimality in a wider range than the QAP estimator.

Your detailed comments are answered in the following.

1. Explanation of the reasoning in Section 2.3.

First, we explain the reasoning in Section 2.3 and the role of Theorem 1. Section 2.3 basically is to analyze the impact of SNR on the convergence behaviors of the message passing (c.f. Equation (6)). As it is very difficult to track all message flows, we view the message flows to be i.i.d. samples. Here, we regard the message flow $h_{i\rightarrow (i, \pi^{\natural}(i))}$ and $h_{j\rightarrow (i, \pi^{\natural}(i))}$ along the correct correspondence edge to be i.i.d. samples (represented by the random variable $H$). Similarly, we regard the message flows along the rest edges as i.i.d. samples from a distribution denoted by $\hat{H}$. In this way, we only need to track two scalars ($H$ and $\hat{H}$) instead of all message flows. The iterative equation is Equation (6), which can be further simplified to Equation (8) and can be analyzed by Theorem 1. When $\inf_{\theta} 1/\theta \log\left(\sum_{i=1}^n \mathbb{E} e^{-\theta \Xi_i}\right) > 0$, we have $H^{t}$ converge to a large positive value; whereas $\inf_{\theta} 1/\theta \log\left(\sum_{i=1}^n \mathbb{E} e^{-\theta \Xi_i}\right) < 0$ leads to a large negative value. Hence, we conclude there is a sudden behavior change, namely, phase transition happens when $\inf_{\theta} 1/\theta \log\left(\sum_{i=1}^n \mathbb{E} e^{-\theta \Xi_i}\right) = 0$.

2. Meaning of negative SNR. The negative SNR denotes the place of the potential phase transition points. As SNR is non-negative by nature, we can conclude there is no phase transition in this region, which means the permutation reconstruction cannot be ever reconstructed.

3. Lower Approximation of Page 6. We use the standard inequality $\log(1+x)\leq x$.

In the end, we would like to thank you again for your detailed comments. Please feel free to let us know if you have any other questions. We will be happy to answer them. Thank you.

4. Presentation of Algorithm 1 and detailed explanation of Lines 5 and 6

Thanks for the suggestion in presenting Algorithm 1 that we may need to give more focus on Lines 5 and 6 rather than the binary search. It is interesting that some other reviewers suggested that the binary search method needs more clarification since many readers might be unfamiliar with it. We will try to balance these suggestions.

Regarding Line 5, it corresponds to the estimators to solve the permutation matrix, that is equation (9) for the oracle case and equation (19) for the non-oracle estimator.

As for Line 6, the error rate refers to the fraction of samples on which the inferred permutation fails to coincide with the planted one, as we state in the second paragraph in Appendix C "we calculate the error rate of the permutation matrix (full recovery)". Its mathematical definition is $L^{-1}\sum_{i=1}^L 1(\Pi \neq \hat{\Pi})$, where $1(\cdot)$ is the indicator function, $L$ is the number of experiments and is set as $100$. We explained this in the main text. Perhaps we can make it more explicit. Thanks for the suggestion.

Again, thanks for your review of our work. Please kindly let us know if there are further questions. Thank you.

Dear Reviewer, thanks for your appreciation of our derivation of the phase transition SNR. It's very encouraging to see your positive comments such as our ideas are shining.

We feel your major concern is on whether our results can be reused or not.

First, we can assure you that all theorems/propositions are rigorously derivated and can be confidently reused. Regarding the approximations, they mainly exist in establishing the connections between the phase transition point and the SNR. To be more specific, it primarily involves two aspects (i) the process of linking the phase transition point and Equation (11) and (ii) approximating the solution of (11). The conclusions in Theorem 1, Proposition 1, and Theorem 2, are rock solid.

Next, we address your detailed questions as follow.

1. Approximation of $\log \mathbb{E}e^{-\theta \Xi}$.

This is due to the relation $\log(1+x)\leq x$.

2. Justification of Gaussian approximation.

The technique of Gaussian approximation is widely applied in analyzing the message-passing algorithm. One of the most successful its applications is in designing the LDPC code (c.f. 'Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation' by Sae-Young Chung, T.J. Richard, and R.L. Urbanke). Its success is mostly verified by empirical experiments and the theoretical justifications are still awaiting to be given.

Again, we would like to mention that all theorems/propositions (Theorem 1, Proposition 1, and Theorem 2) are rigorously derived. The non-rigorous part is mostly about the dependence between the phase transition points and the expectation $\mathbb{E} \exp(-\theta\Xi)$ and its calculations.

3. Position of the Proof of Proposition 1.

It can be found in Appendix B.

Again, thanks for your review of our work. Please kindly let us know if there are further questions. Thank you.

Dear Reviewer, thanks for recognizing our work to be novel, of high quality, and with great significance.

First, there seems to be a misunderstanding on Equation (3), please allow us to clarify. Our notations with (Montanari & Mezard, 2009) are in fact equivalent, so Equation (3) is correct. In both our work and (Montanari & Mezard, 2009), the terms with the indicator function are one when $\sum_{j}\Pi_{ij} = 1$ (and $\sum_i \Pi_{ij} = 1$), and zero otherwise. They are both to enforce the constraint such that $\Pi$ is a permutation matrix.

Next, we answer your other questions.

1. Difference with Mezard & Montanari (2009).

We consider a much harder problem than that in Mezard & Montanari (2009). In our work, the distributions of edge weights are neither identical nor independent. Moreover, we discover and analyze a phase transition phenomenon, which is the main contribution of our paper. Mezard & Montanari assume each edge weight is i.i.d. distributed and there is no phase transition phenomenon present.

2. Constraints on the simulations.

There is hardly any constraint on the numerical experiments. In our experiments, we only assume the entries in the sensing matrix $X$ to be i.i.d. sub-gaussian with zero mean. For example, we consider Gaussian distributed $X$ in Table 1 and Figure 2, and uniformly $[-1, 1]$ distributed $X$ in Table 2. The sensing noise matrix $W$ is a Gaussian random matrix with each entry being a standard normal random variable. As for the signal matrix $B$, it can be an arbitrarily fixed matrix in the oracle case; and is required to have all eigenvalues reside within approximately the same region in the non-oracle case.

3. Practical applications of permuted linear regression.

For the permuted linear regression, its application widely ranges from database merging, to privacy, to communications, to computer vision, to robotics, to sensor networks, etc. Two of the most important practical applications of the permuted linear regression include (i) linkage record, where we would like to align data from different sources and merge them into one comprehensive database; (ii) data de-anonymization, where we want to use public information to infer and uncover hidden identities or connections within private datasets.

Since our work is a theoretical paper, our focus is on the theoretical analysis and prefer to leave the applications to the references, which are (Unnikrishnan et al., 2015; Pananjady et al., 2018; Slawski & Ben-David, 2019; Pananjady et al., 2017; Slawski et al., 2020; Zhang & Li, 2020). We can include more content on the practical applications of permuted linear regression if the readers feel helpful. Thanks for the suggestion.

Again, we appreciate your valuable feedback. Please kindly let us know if there are further questions. Thank you.

Dear Reviewer, thanks for your feedback and recognizing that our work is the first work that leverages the framework of message-passing algorithms to derive phase transition thresholds. In addition, we are pleased that you find our literature review comprehensive and informative.

Let us address your questions.

1. Lower bound on Equation (6). The lower bound is obtained with the relation $\log(1 + x) \leq x$.

2. Intuition of Gaussian approximation. The choice of Gaussian approximation in the message passing (MP) is mainly due to its past success in analyzing the MP algorithm. One of the most successful examples is (c.f. 'Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation' by Sae-Young Chung, T.J. Richard, and R.L. Urbanke), a famous paper in coding theory with more than 1600+ citations.

3. Role of the assumption such that all singular values of the matrix $B$ are of the same range in computing $snr_{\textup{non-oracle}}$.

First, this assumption can greatly simplify the expression of $snr_{\textup{non-oracle}}$. Otherwise, $\textup{snr}_{\textup{non-oracle}}$ will be the solution of a quartic equation (fourth order) rather than a quadratic equation (second order). Second, this assumption can preserve the generality of our theorem since this assumption can cover a wide family of matrices, say sub-Gaussian random matrices. It is well known that all their eigenvalues are within the region $[1-c_0\sqrt{m/p},~1 + c_0 \sqrt{m/p}]$ (after column normalization), and satisfy our assumption that all eigenvalues are of the same range.

In addition, we appreciate your suggestions on the paper organization such as adding more discussion on the practical applications. As our work a theoretical paper focusing on bridging the message passing with the analysis of permuted linear regression, we limit the content to avoid distraction. The problem of permuted regression has many useful applications, for example:

(A) Record linkage.
Given multiple databases containing information about the same entities, the objective is to merge them into one comprehensive database. However, these data may not be well-aligned due to the data formatting or data quality issues. Modeling the mismatches as a permutation is investigated as a mitigation strategy.

(B) Data de-anonymization. This task can be regarded as the opposite side of privacy protection. The intruders aim to infer the hidden identities/labels in certain private networks with public information. One commonly used method is to compare the correlation between this information and to find matching pairs with maximum correlation sum. Here, the permuted linear regression arises as a natural generalization.

For more applications, we recommend (Unnikrishnan et al., 2015; Pananjady et al., 2018; Slawski & Ben-David, 2019; Pananjady et al., 2017; Slawski et al., 2020; Zhang & Li, 2020), which are a good starting point. We are happy to add more references on the applications if the reviewer suggests.

Thanks again for your review of our work. We will carefully revise our paper according to these suggestions. Please feel free to let us know if you have more questions. Thank you.