The Phase Transition Phenomenon of Shuffled Regression

Then, let us address your concerns.

(1) First, we would like to clarify that conducting our analysis within the message-passing (MP) framework does not diminish the technical novelty of our work.

MP serves as an analytical tool, much like concentration inequalities. Conducting analysis within the framework of MP is like giving analysis with concentration inequalities, which we hardly think downgrade the technical novelty. Determining the phase transition point of a specific group of message passing equations requires careful and intricate analysis.

Furthermore, numerous papers adopting similar methodologies, or inherently related approaches (such as the replica method), have been published in leading machine learning conferences/journals. A few examples are listed in below.

Construction of optimal spectral methods in phase retrieval

Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem

Spectral redemption in clustering sparse networks

Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

Optimal errors and phase transitions in high-dimensional generalized linear models

Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

Short-term memory in neuronal networks through dynamical compressed sensing

(2) Second, we would like to confirm you that Proposition 1 is derived rigorously under the Assumption 1.

(3) As for your concern regarding to the presentation clarity, we really appreciate it if you could provide more details. For your convenience, we would like to give a brief roadmap of our results.

Section 3 is about the oracle case, Section 3.1 derives the phase transition by directly analyzing the RV $\Xi$, and Section 3.2 proposes to approximate $\Xi$ with Gaussian approximation, which is easier to compute and more general.

Section 4 concerns the non-oracle case, which calculates the phase transition point based on the Gaussian approximation. Proposition 3 concerns the position of the phase transition while Theorem 3 calculates the associated quantities.

In the end, please feel free to let us know if you have any questions.

First, we would like to thank you for your feedback. Before we answer your concern, we would like to first discuss the advancement of our approach.

1. Our work shows noticeable advantage over the work in the same field. One example is [Lufkin et al. 2024], which was released this Feburary from several renowned statistists. It considers a similar but simpler setting of our paper $(m=1)$. A conjectured (c.f. the phase transition happens at $snr = n^{4/m}$ on the oracle case) that they mention as an open problem can be easily derived by us, c.f. Line 372-374. In fact, we treat them as a warm-up example. Other advantages include 1) our work can predict the precise phase transition point; 2) our applicability to a wider class of cases; and 3) our consolidation into a cohesive framework to predict the phase transition point. More details can be found in Remark 4.

2. Our work can predict the phase transition in a rather accurate way. The numerical experiments show that differences between the predicted value and our predictions are under 0.001 in some cases. Meanwhile, previous works in the permuted linear regression only consider the logarithmic value (c.f.  Pananjady et al., 2018; Slawski & Ben-David, 2019; Pananjady et al., 2017; Slawski et al., 2020; Zhang & Li, 2020), that is, only checks the order of magnitude.

Dear Reviewer,

We are reaching out to check if you have any additional concerns, as the deadline for the discussion period is approaching. We would be happy to address any other questions you may have.

Thank you.

Dear Reviewer,

As the deadline is approaching, we would like to ask whether you're satisfied with our responses. We will be happy to address the additional issues.

Thank you.

Dear Reviewer, first we would like to thank you for your feedback. Let us address your questions.

1. Questions regarding Eq. (3), the underlying motivation, whether it is necessary and the prediction error.

Eq. (3) is to frame the permuted linear regression under the message passing framework, which requires a probability distribution to build the probabilistic graphical model. Eq. (3) is to associate the optimization Eq (2) with a probability distribution, that allows us to study its property. It is an equivalent transformation and thus won't bring any prediction errors.

2. Reasoning behind Eq (10).

It comes from the definition of random variable $\Xi$, whose definition can be found in Eq. (8).

3. Motivation behind Assumption 1.

This assumption is a common practice in analyzing the message passing algorithm such that the correlations are weak enough to be ignored. It's required by default except for some simple cases. And all previous study suggests that such assumption can be safely placed without any noticeable impact on the final prediction.

A reference example can be found in Section 16.2.5 "Non-zero temperature and stability analysis" (start reading from the third paragraph) in Information, Physics, and Computation by Andrea Montanari and Marc Mézard [also cited in our paper].

4. What are the predicted points for the non-oracle case in Table 2? Are they similar with Table 2?

First, the non-oracle will be drastically different from the oracle case, whose phase transition point is with a smaller number. In addition, a direct comparison between the non-oracle case and oracle case is difficult. In the non-oracle case, we can predict and observe the appearance of another phase transition associated with the number of permuted rows (to be more specific, $\tau_h$). Predicting the phase transition induced by the SNR is more complex, as $\tau_h$ tends to trigger a phase transition earlier, complicating direct comparisons.

5. Interpreting the upper panel in Fig 2.

Yes. The fluctuated point is the predicted phase transition point. As you note, the SNR should be positive value. The sudden change to a negative value suggests a phase transition point happens here.

In the end, we would like to thank you again for your feedback and please feel free to let us know if you have any other questions. Thank you.

Dear Reviewer, we would like to first thank you for your encouragement and high rating. Let us address your question, i.e., the motivation under Eq. (3).

This is to frame the permuted linear regression under the message-passing framework. It requires constructing a probabilistic graphical model based on the joint probability distribution. Eq (3) transforms the optimization in Eq (2) to a probability distribution, thus enabling us to study the property of Eq (2) with the maximum prior estimate of $\mu(\Pi)$.

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

Let's only focus on the issues with assumption 1. I never said that you should not justify assumptions by experiments. I said that assumptions should be mathematically correct and they should be true for some non-trivial classes of inputs, and some examples of such classes should be provided. Can you name some classes of $B$ that satisfy this assumption? (e.g. low rank, or sparse, or some other properties that can be fully described in terms of $B$, preferably with an easy description). When you do it, we can say that you proof works for these classes, but we cannot formally say anything about other $B$. You can say then that experiments suggest that for many other $B$ the result should also be true, that is fine and good for future works. The strength of you result then would mainly depend on the specific classes of $B$ for which assumption 1 is satisfied, and for some other classes of $B$ you can formulate a relevant conjecture based on the experiments.

Another fact we feel helpful for the discussion is that all the previous findings (c.f. Pananjady et al., 2018; Slawski & Ben-David, 2019; Pananjady et al., 2017; Slawski et al., 2020; Zhang & Li, 2020) suggests that the structure of the B matrix barely has any impact on the phase transition point, including the [Lufkin et al., 2024] that also targets on the precise location of the phase transition point.

In fact, the SNR and the stable rank of $B$ play the dominant role. This is also suggested in our result.

In summary, we have already verified Assumption 1 with the following three ways:

1. Our numerical experiments on multiple matrices show good alignment between the numerical values and the predicted values.
2. Our prediction results agree with the previous rigorously derived result, that is, the SNR and the stable rank determines the phase transition point.
3. Our prediction results agrees with the conjecture in [Lufkin et al., 2024], which consider the same problem but under a much simpler setting,

We hope this can address your concern over our assumption 1 and please feel free to let us know if you have questions on other issues.

Dear reviewer,

We thank you for your response.

Directly checking Assumption 1 is difficult however wet do not think that Assumption 1 is affected by the B matrix structure, as the correlation is brought by the sensing matrix and the noise.

Numerical experiments also confirm this. We conduct experiments on almost all the typical matrices, including both deterministic (c.f. Table 1 and 2) and Gaussian random matrices and other matrices. We do not find any matrices will lead to significant divergence between our predicted results and the numerical results. A detailed description of the B matrix can be found in our paper.

We will be happy to add new experiments on the matrices you would like to try.

Thank you for the timely feedback.

First, we agree with you that assuming the correlation is zero is inappropriate. But we should respectfully mention that we do not make such assumption but only assume the correlation can be ignored. In fact, our words is ignore the weak correlation but we will make this more clear.

Second, we would like to mention that ignoring these correlations is quite common in analyzing the message-passing algorithm. The most related example can be found in Section 16.2.5 "Non-zero temperature and stability analysis" (starting from the third paragraph) in Information, Physics, and Computation by Andrea Montanari and Marc Mézard [cited in our paper].

They consider the linear assignment problem and give some heuristic explanations why the correlation may be ignored (because the correlation decays very fast). Although their explanation may not fully apply to our case (ours is more complex), we expect a justification of Assumption 1 can be provided following a similar argument.

In the end, we would like to thank you again for your comments & please let us know if you have any other questions.

In addition, we respectfully disagree with some of your suggestions. A few points raised appear somewhat confusing and might even suggest some degree of bias. We hope to clarify these aspects further.

First, you suggest that in learning theory community, you have to assume some nice properties of B (or other parameters of the problem), and then rigorously derive some result. In particular, we are very confused about your suggestion such that we should not justify our assumptions by numerical experiments.

We regard the theory needs to be aligned with the numerical experiments but not vice versa. A theory that appears elegant but fails to align with experiments lacks any practical value.

As you can see, our numerical experiments (Table 1 and 2) align with the numerical experiments to a very good extent, with differences under 0.001 in some cases. Meanwhile, notice that all the previous works in the permuted linear regression only considers the logarithmic value (c.f.  Pananjady et al., 2018; Slawski & Ben-David, 2019; Pananjady et al., 2017; Slawski et al., 2020; Zhang & Li, 2020), that is, the order of magnitude.

Second, we are confused by your comment our result only contain equalities (approximate equalities up to o(1) terms) suggest the approach are not very sophisticated. As you noted, the goal of asymptotic analysis is to identify expressions that approximate complex behavior in the limit. Almost all the asymptotic analysis are of a similar look.

While we do not view sophistication as a primary objective, we hope our analysis, which spans over 40 pages, demonstrates a thorough approach that goes beyond simple equivalence transformations.

In the end, we are happy to assist you in understanding our paper and address your questions regarding the technical or whatever questions you have.

We thank you for your feedback. Let us answer some of your questions.

First, we would like to confirm that we only need Assumptin 1 to derive the conjecture of [Lufkin et al. 2024]. We appreciate your suggestion regarding assumptions on some nice properties of B (or other parameters of the problem). However, our approach does not require us to impose such assumptions, allowing us to work under more general conditions.

Second, Assumption 1 is to meet the i.i.d conditions in Theorem 1. Our work is not performing equivalent transformations, as you commented. This can be easily seen from the depth and detail of our analysis, which spans 46 pages.

Again we would like to thank you for your comments.

We would like to be more specific here, that is, all matrices $B$ should satisfy the Assumption 1, at least our current findings do not find any $B$ that violates this assumption (c.f. the correlation is weak and can be ignored). This has already been verified by our numerical experiments.

By the way, we do not assume the structure of B will have any impact on Assumption 1, as the correlation is brought by the sensing matrix $X$ and noise $W$. The sensing matrix $B$ has no role here.

In the end, we really appreciate it if you can kindly list any examples or potential examples you feel Assumption 1 is violated. We are happy to conduct experiments and report the discrepancy between the numerical values and predicted values.

Regarding your comment that only $B= 0$ will satisfy the assumption, we would like to kindly mention that our paper contains several matrices (c.f. Table 1 and 2) that is not zero such that Assumption 1 can be safely taken, as the associated prediction accuracies are pretty high.

Dear Reviewer,

We are writing to ask if you're satisfied with our responses, since the discussion period is about to end and you do not give any feedback since Nov 15, 2024.

We will be happy to address any of your concerns. Thank you.