稀疏最小二乘中的条件数障碍
The Condition-Number Barrier in Sparse Least Squares
Google用Gemini自动化系统先跑通了证明，人工再验证。你要是做稀疏优化或条件数相关算法，看看这个下界怎么证的。
arXiv:2608.02588 的论文证明了稀疏最小二乘问题的一个条件数下界：在随机化精确体积小集扩张假设（Small-Set Expansion Hypothesis）下，对任意固定的 γ∈(0,1]，不存在多项式时间随机算法能以至少 2/3 概率返回满足误差不超过最优值加 ε、且稀疏度 s=O(k·κ_{s+k}^{1-γ}) 的解。
该结果甚至对有理数实例、A 为列满秩时也成立。作者表示，证明最初由 Google 内部开发的基于 Gemini 的自动化智能体系统完成，随后由人工验证并整理。
The Condition-Number Barrier in Sparse Least Squares
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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include 稀疏最小二乘, 条件数, Small-Set Expansion, Gemini.
Source attribution: curated from arXiv cs.LG (@Honghao Lin, Vahab Mirrokni, David P. Woodruff).
