证明了非高斯成分分析在低阶平方和框架下存在超多项式计算瓶颈。
Sum-of-squares lower bounds for Non-Gaussian Component Analysis
- 采用平方和（SoS）框架研究非高斯成分分析的计算复杂性
- 在样本数少于 $n^{(1-\varepsilon)k/2}$ 时，低度 SoS 无法识别隐藏方向
- 揭示了统计-计算权衡，适用于鲁棒统计与混合模型学习问题
非高斯成分分析（NGCA）是在高维数据中寻找非高斯方向的统计任务。给定独立同分布样本来自分布 $P^A_v$，其在隐藏方向 $v$ 上服从已知分布 $A$，在正交补空间上服从标准高斯分布，目标是近似该隐藏方向。标准设定要求 $A$ 的前 $k-1$ 阶矩与标准高斯分布一致，第 $k$ 阶矩不同。在温和假设下，该问题具有 $O(n)$ 的样本复杂度，但所有已知高效算法需 $Ω(n^{k/2})$ 样本。已有工作通过统计查询和低度测试建立下界，暗示统计-计算权衡。本文在平方和（SoS）框架下研究该问题，首次给出超常数度的 SoS 下界：若 $A$ 与 $ ext{N}(0,1)$ 前 $k-1$ 阶矩匹配且满足其他弱条件，则当样本数少于 $n^{(1-eta)k/2}$ 时，以高概率，度为 $( ext{log} hinspace n)^{1/2 - o_n(1)}$ 的 SoS 无法反驳存在此类方向 $v$。该结果显著强化了此前工作，建立了对更广泛算法类别的超多项式统计-计算权衡。作为推论，我们得到了鲁棒统计和混合模型学习中若干问题的 SoS 下界。证明引入了一种新颖技术，可能具更广意义，并对现有方法进行了多项改进。
原文摘要 · Abstract (English)
Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distribution $P^A_{v}$ on $\mathbb{R}^n$ that behaves like a known distribution $A$ in a hidden direction $v$ and like a standard Gaussian in the orthogonal complement, the goal is to approximate the hidden direction. The standard formulation posits that the first $k-1$ moments of $A$ match those of the standard Gaussian and the $k$-th moment differs. Under mild assumptions, this problem has sample complexity $O(n)$. On the other hand, all known efficient algorithms require $Ω(n^{k/2})$ samples. Prior work developed sharp Statistical Query and low-degree testing lower bounds suggesting an information-computation tradeoff for this problem. Here we study the complexity of NGCA in the Sum-of-Squares (SoS) framework. Our main contribution is the first super-constant degree SoS lower bound for NGCA. Specifically, we show that if the non-Gaussian distribution $A$ matches the first $(k-1)$ moments of $\mathcal{N}(0, 1)$ and satisfies other mild conditions, then with fewer than $n^{(1 - \varepsilon)k/2}$ many samples from the normal distribution, with high probability, degree $(\log n)^{{1\over 2}-o_n(1)}$ SoS fails to refute the existence of such a direction $v$. Our result significantly strengthens prior work by establishing a super-polynomial information-computation tradeoff against a broader family of algorithms. As corollaries, we obtain SoS lower bounds for several problems in robust statistics and the learning of mixture models. Our SoS lower bound proof introduces a novel technique, that we believe may be of broader interest, and a number of refinements over existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。