2025/04/04 by Li, Zhangsong
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2504.03097
In this paper, we study the problem of multivariate shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a latent permutation. Specifically, we investigate the model Y=\tfrac1√(1+σ2)(Π_* X Q_* + σZ), where X is an n*d standard Gaussian design matrix, Z is an n*m Gaussian noise matrix, Π_* is an unknown n*n permutation matrix, and Q_* is an unknown d*m on the Grassmanian manifold satisfying Q_*\top Q_* = \mathbb Im. Consider the hypothesis testing problem of distinguishing this model from the case where X and Y are independent Gaussian random matrices of sizes n*d and n*m, respectively. Our results reveal a phase transition phenomenon in the performance of low-degree polynomial algorithms for this task. (1) When m=o(d), we show that all degree-D polynomials fail to distinguish these two models even when σ=0, provided with D4=o( \tfracdm ). (2) When m=d and σ=ω(1), we show that all degree-D polynomials fail to distinguish these two models provided with D=o(σ). (3) When m=d and σ=o(1), we show that there exists a constant-degree polynomial that strongly distinguish these two models. These results establish a smooth transition in the effectiveness of low-degree polynomial algorithms for this problem, highlighting the interplay between the dimensions m and d, the noise level σ, and the computational complexity of the testing task.