证明了稀疏最小二乘问题中条件数的下界，揭示算法极限。
The Condition-Number Barrier in Sparse Least Squares
- 基于小集展开假设，构建反例证明算法无法突破条件数依赖。
- 在概率2/3下，解的稀疏度受限于κ^{1-γ}形式，无法改进。
- 适用于理解稀疏优化算法理论边界的研究者。
Axiotis和Sviridenko在[AS21]中猜想，稀疏凸优化中的线性条件数依赖无法被多项式时间算法改进。本文在加权正则图形式下的随机精确体积小集展开假设（RST12）下，建立了该猜想对最小二乘目标的下界。具体而言，对任意固定γ∈(0,1]，不存在随机多项式时间算法能在至少2/3的概率下，输出向量x，使得其稀疏度s满足：‖Ax−b‖₂² ≤ min_{‖z‖₀≤k}‖Az−b‖₂² + ε，且s = O(k κ_{s+k}^{1−γ})，其中κ_r为稀疏度r处的受限条件数。该结果即使在A满列秩的有理实例上也成立。证明最初由谷歌内部开发的全自动化Gemini代理系统完成，作者已验证并润色以提升可读性。
原文摘要 · Abstract (English)
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed $γ\in(0,1]$, there is no randomized polynomial-time algorithm that, with probability at least $2/3$, returns a vector $x$ such that, writing $s=\lVert x\rVert_0$, \[ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\!\left(k\,κ_{s+k}^{\,1-γ}\right), \] where $κ_r$ is the restricted condition number at sparsity level $r$. The result holds even on rational instances with $A$ of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。