The Phase Transition Phenomenon of Shuffled Regression
Message Passing;Permuted Linear Regression;Phase Transition
Yes
No ethics review needed.
(see Weaknesses above)
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.
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.
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.
Yes
No ethics review needed.
- Can the authors provide some motivation behind eq. (3)?
- 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.
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.
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.
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
see above
see above
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.
see above
@inproceedings{
anonymous2024the,
title={The Phase Transition Phenomenon of Shuffled Regression},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=gVVoZtiQlt},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Message Passing Permuted Linear Regression Phase Transition
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/808fe3f9ca9f306674d282b52bd2477f0703382b.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/799ed36ad8074bccbb5a3cea7bd503caef9a95b8.pdf
The Phase Transition Phenomenon of Shuffled Regression
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission