低阶方法失效：新算法突破计算瓶颈，挑战经典预测范式。
Low-Degree Method Fails to Predict Robust Subspace Recovery
- 设计基于反集中性的多项式时间算法解决鲁棒子空间恢复问题。
- 在n^{Ω(1)}阶低阶多项式下，该方法仍无法预测可解性。
- 适合研究计算复杂性与算法设计的理论学者阅读。
低阶多项式框架在高维统计问题的平均情况分析中表现卓越，常被用于预测计算与统计之间的差距。然而，我们发现一个在ℝⁿ中的基本假设检验问题，虽可在多项式时间内求解，但低阶多项式方法却无法预测其可解性，即使在阶数k=n^{Ω(1)}时亦然。此外，低阶矩在k=O(√(log n / log log n))以内完全匹配。该问题为广受研究的鲁棒子空间恢复问题的特例。尽管已有下界表明此类问题无多项式时间算法，但我们提出一个简单且鲁棒的多项式时间算法，利用分布的反集中性质解决了该问题及其噪声变体。结果表明，低阶方法与低阶矩无法捕捉基于反集中性的算法，挑战了其作为通用计算障碍预测工具的普适性。
原文摘要 · Abstract (English)
The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in $\mathbb{R}^n$ which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree $k=n^{Ω(1)}$. Moreover, the low-degree moments match exactly up to degree $k=O(\sqrt{\log n/\log\log n})$. Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。