The Phase Transition Phenomenon of Shuffled Regression

Authors: Hang Zhang, Ping Li
Primary area: learning theory
Keywords: Message Passing, Permuted Linear Regression, Phase Transition

Abstract:
We study the phase transition 
phenomenon inherent in the shuffled (permuted) regression problem, which has found numerous applications in databases, privacy, data analysis, etc. For the permuted regression task: $\mathbf{Y} = \mathbf{\Pi}\mathbf{X}\mathbf{B}$, the goal is to recover the permutation matrix $\mathbf{\Pi}$ as well as the coefficient matrix $\mathbf{B}$. It has been empirically observed in prior studies that when recovering $\mathbf{\Pi}$, there exists a phase transition phenomenon: the error rate drops to zero rapidly once the parameters reach certain thresholds. In this study, we aim to precisely identify the locations of the phase transition points by leveraging techniques from {\em message passing} (MP). 

In our analysis, we first transform the permutation recovery problem into a probabilistic graphical model. Then, we leverage the analytical tools rooted in the message passing (MP) algorithm and derive an equation to track the convergence of the MP algorithm. By linking this equation to the branching random walk process, we are able to characterize the impact of the \emph{signal-to-noise-ratio} ($\mathsf{snr}$) on the permutation recovery.  Depending on whether the signal is given or not, we separately investigate the oracle case and the non-oracle case. The bottleneck in identifying the phase transition regimes lies in deriving closed-form formulas for the corresponding critical points, but only in rare scenarios can one obtain such precise expressions. To tackle this challenge, we propose the Gaussian approximation method, which allows us to obtain the closed-form formulas in almost all scenarios. In the oracle case, our method can fairly accurately predict the phase transition $\mathsf{snr}$. In the non-oracle case, our proposed algorithm can predict the maximum allowed number of permuted rows and uncover its dependency on the sample number.

Decision: reject
Reviewer scores: 3, 8, 6, 3

Reviews and discussion:
<thread>
creation date:
1730078373074

thread_type:
official_review

<thread_object>
creator: reviewer_ytgr

<content>
summary:
This paper studies high-dimensional shuffled linear regression, which is the following problem.
We are given a design matrix $X$ and a set of observations $Y$, drawn according to the following model:

$Y = Pi \cdot X \cdot B + \sigma W$

Here, $B$ is a "signal" matrix and $Pi$ is an unknown permutation matrix.
$\sigma > 0$ is a parameter and $W$ is a noise matrix with iid Gaussian entries.
In some variants of the problem, we may also be given $B$.
The goal is to recover $Pi$, and, if it is not given to us, $B$.

The paper offers a method to predict the signal-to-noise ratio above which a certain "message passing" algorithm, derived from statistical physics, can recover $Pi$ or $Pi,B$.
(The message passing algorithm is also derived in the paper.)
From what I can tell, the method is heuristic, making "physics-style" approximations along the way.
The authors corroborate their findings with some numerical experiments to show that the predictions they make are not too far numerically from the observed signal-to-noise threshold at which message passing stops working.

The problem of shuffled linear regression is a natural one, and well within the scope of ICLR.
However, I do not feel that the paper clears the bar for acceptance.

The main (major) issue is that the presentation of results is not at all clear.
The results are scattered throughout the 10 page, there is inadequate context for all of them.
For instance, I think proposition 1 is supposed to be one of the main results.
But I cannot tell how to interpret it as a mathematical proposition -- is it meant to be a rigorously-proven equation?

There are lots of heuristic physics-style "derivations" of phase transitions for message passing algorithms for high-dimensional learning problems now in the literature.
What is novel about this derivation?
If it is just a matter of turning the crank on existing technology, then even with clarified presentation I think it should go to a more specialized conference.
If there is something really novel about the way the derivation works here that I am missing, then perhaps it could be of interest to a broad ICLR audience.

strengths:
see above

weaknesses:
see above

questions:
see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730690388228

thread_type:
official_review

<thread_object>
creator: reviewer_5ffe

<content>
summary:
This paper studies the shuffled regression problem, in which unknown permutation matrix is multiplied to a linear model, with a focus on predicting phase transition. The authors leverage the message passing algorithm to find phase transition point in the limit of some parameters. In the analysis of phase transition, they categorize oracle and non-oracle cases, where the signal matrix is known and unknown respectively.

strengths:
The derivation of the phase transition point using message passing and LAP is clearly presented and technically sound. This work distinguishes the difference from the recent papers having similar problem and settings, which in fact shows technical contribution over the  recent papers.

weaknesses:
Some motivations and intuition in the derivation part are missing. For instance, eq(3), eq (10) and assumption 1 are given without motivation. Analysis of the approximation error (such as Gaussian approximation in eq (10) or the use of the lower bound for $\theta^*$) is not provided. As oracle case is rare in practice, I think comparison of non-oracle case with oracle case is needed at least in empirically, but it is missing in the paper.

questions:
1) Is eq (3) necessary for the problem of shuffled regression? How much does prediction error arise if the prior distribution on the permutation matrix is not following eq(3)?
2) As I wrote in the weaknesses part, what are the motivation or reasoning behind using eq(3), eq(10), and assumption 1?
3) With the similar setting of Table 2, what are the predicted phase transition points by the algorithm for non-oracle case? Are they similar with the prediction of oracle case? 
4) How to read the upper panel in figure 2? Is the fluctuated point of $\tau_h$ the phase transition point w.r.t. $\tau_h$? If yes, why it is?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694496278

thread_type:
official_review

<thread_object>
creator: reviewer_vemt

<content>
summary:
The paper studies the phase transition phenomenon in the shuffled regression problem. The authors transform the permutation recovery problem into a probabilistic graphical model and use message passing (MP) algorithms to derive equations tracking convergence. To address the challenge of deriving closed-form formulas for critical points, they propose a Gaussian approximation method, which provides accurate predictions of phase transition thresholds in multiple scenarios. Experiments are provided and suggest that the proposed algorithm is able to recover the structure.

strengths:
- The problem being studied seems novel. I'm more familiar with phase transitions in the context of network models, and in the context of permuted LR the problem seems new.
- The authors propose a new method which leverages the MP algorithms by relating the combinatorial structure in the shuffled regression problem to a graphical model. This seems novel. 
- Detailed proofs for the phase transition points are included. Specifically the Gaussian approximation analysis can be interesting when tackling more general scenarios.
- Synthetic experiments are provided, and the phase transition points from the results match the prediction from the theorem.

weaknesses:
I am not familiar with this line of literature and I wouldn't be the best to provide an assessment. That being said, I think the organization of the paper can be improved. While I understand the paper is highly theoretical and statistical, it would be easier for readers to follow if the authors can provide more high level motivations or concrete examples.

questions:
- Can the authors provide some motivation behind eq. (3)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731250460637

thread_type:
official_review

<thread_object>
creator: reviewer_sf1x

<content>
summary:
The paper studies the shuffled multi-observation linear regression in two regimes: when the signal matrix is known and when it is unknown. The authors investigate the SNR at the phase transition.

strengths:
The paper studies the general version of the problem that was studied in several prior works. The authors claim that they solve an open problem from a prior work [Lufkin et al., 2024]. While I'm not sure about this statement (see below), I think their result might be anyway helpful to investigate the regime that [Lufkin et al., 2024] were interested in.

weaknesses:
Your assumption 1 seems to be unrealistic. You justify it by some numerical experiments, but it is not the usual way how assumptions in learning theory work. You have to assume some nice properties of B (or other paramerers of the problem), and then rigorously derive some result. Currently it is unclear to me whether there is any non-trivial matrix B that satisfies this assumption. Is it the case that you used this assumption in your formal proofs? Also, is it correct that your result formally answers the question from [Lufkin et al., 2024] only under this assumption?

In addition, your proofs seem to contain only equalities (or approximate equalities up to $o(1)$ terms). While this complaint might sound weird, it indicates that the approach may not be very sophisticated. You basically just do equivalent transformations of formulas. While potentially sometimes it might be non-trivial, practically almost always it is not the case. So far it seems to me that your assumption 1 is needed exactly for these equivalent transformations to work, and with any mathematically correct assumption the analysis has to become significantly more challenging.

Given these two observations, I recommend rejecting the paper.

questions:
(see Weaknesses above)
</content>
</thread_object>

</thread>


Metareview:
metareview:
The views on this paper are fairly mixed, and some positive points are certainly there on giving new thresholds for message passing in shuffled regression.  However, there are still some strong doubts about (i) the underlying assumptions and level of rigor, and (ii) the writing clarity and presentation.

Regarding (i), since Assumption 1 was a focus of much of the discussion, I will give a summary of the latest thoughts:
- The statement in Assumption 1 is not mathematically formal, particularly the phrasing “We ignore … and view…”.  If you were to make it formal (e.g., by assuming exactly 0 correlation), then the assumption would probably be strictly false.  This raises the delicate question of whether any formal statements in the entire paper are fully justified. 
- Assumption 1 is not cross-referenced after it is introduced, so it is hard to pinpoint where it is used.
- Formal theorem statements (e.g., Proposition 1) are stated as being true without mentioning Assumption 1, which is misleading.
- The derived thresholds are shown to have fairly good prediction accuracy in several scenarios (Tables 1 and 2), which is useful, but is by no means a complete justification.
- The reference to Montanari/Mezard is appreciated but it remains quite difficult to pinpoint exactly what they assumed, how it compares, and whether or not they similarly gave formal statements that rely on similar assumptions.
- I personally don't agree with the (implicit) defense that the reviewer(s) can’t specifically identify a case where the assumption fails.  That at most points to the assumption's validity being "inconclusive" rather than "justified".

Regarding (ii), perhaps this could be more dependent on the reader.  It is probably fair to say that the paper is not so accessible to outsiders, but on the other hand, that is often the case for these kinds of papers.