揭示了高维乱序线性回归中低度多项式算法的计算相变现象。
A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials
- 通过分析低度多项式在乱序回归中的检测能力，发现其性能随参数变化存在临界点。
- 当噪声小、维度匹配时，常数度多项式可有效区分；噪声大或维数不匹配时则失效。
- 适用于研究统计推断与计算复杂性关系的理论研究者，尤其关注高维数据建模者。
本文研究多变量乱序线性回归问题，其中线性模型中预测变量与响应变量的对应关系被未知排列隐藏。模型形式为 $Y=\tfrac{1}{\sqrt{1+σ^2}}(Π_* X Q_* + σZ)$，其中 $X$ 是 $n×d$ 标准高斯设计矩阵，$Z$ 是 $n×m$ 高斯噪声矩阵，$Π_*$ 是未知 $n×n$ 排列矩阵，$Q_*$ 是满足 $Q_*^\top Q_* = \mathbb I_m$ 的 $d×m$ 矩阵（位于格拉斯曼流形上）。我们研究在该模型与 $X$、$Y$ 独立同分布的高斯矩阵之间进行假设检验的问题。结果揭示了低度多项式算法在此任务上的相变现象：(1) 当 $m=o(d)$ 时，只要 $D^4=o\big( \tfrac{d}{m} \big)$，所有度为 $D$ 的多项式均无法区分两个模型，即使 $σ=0$；(2) 当 $m=d$ 且 $σ=ω(1)$ 时，只要 $D=o(σ)$，所有度为 $D$ 的多项式仍无法区分；(3) 当 $m=d$ 且 $σ=o(1)$ 时，存在常数度多项式能强区分。这些结果建立了低度多项式算法在此问题上的平滑计算相变，凸显了 $m$、$d$、$σ$ 与计算复杂性的相互作用。
原文摘要 · Abstract (English)
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=\tfrac{1}{\sqrt{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 I_m$. 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 $D^4=o\big( \tfrac{d}{m} \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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。