mlsanityData to 7 Oct 2026

A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials

arXiv 2504.03097 ↗First posted 4 Apr 2025stat.ML cs.LG math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

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(Pi_* X Q_* + σ Z), where X is an n*d standard Gaussian design matrix, Z is an n*m Gaussian noise matrix, Pi_* 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=obig( tfracdm big). (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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 69 references that are in the map. First posted on arXiv 4 Apr 2025.

Builds on

34 of 69 references.

References · 34

  1. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  2. 2018Unsupervised Alignment of Embeddings with Wasserstein Procrustescited by 96
  3. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  6. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  7. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  8. 2020Continuous LWEcited by 37
  9. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  10. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  11. 2014Testing for high-dimensional geometry in random graphscited by 25
  12. 2018High-dimensional estimation via sum-of-squares proofscited by 25
22 more
  1. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  2. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  3. 2017Linear Regression with Sparsely Permuted Datacited by 18
  4. 2017Linear regression without correspondencecited by 16
  5. 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
  6. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  7. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  8. 2019A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Datacited by 12
  9. 2020Counterexamples to the Low-Degree Conjecturecited by 12
  10. 2021Strong recovery of geometric planted matchingscited by 12
  11. 2017Linear Regression with Shuffled Labelscited by 11
  12. 2023Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphscited by 11
  13. 2016Exact Recovery with Symmetries for Procrustes Matchingcited by 10
  14. 2024Tensor cumulants for statistical inference on invariant distributionscited by 8
  15. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  16. 2019The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectorscited by 6
  17. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  18. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  19. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 4
  20. 2021Linear regression with partially mismatched data: local search with theoretical guaranteescited by 3
  21. 2024Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testingcited by 3
  22. 2024Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problemcited by 3

Built on by

Not cited yet.