12:08
官方账号arXiv cs.LG@Honghao Lin, Vahab Mirrokni, David P. Woodruff
精选
推荐理由：Google用Gemini自动化系统先跑通了证明，人工再验证。你要是做稀疏优化或条件数相关算法，看看这个下界怎么证的。
稀疏最小二乘
共 1 条相关 AI 资讯
8月4日
12:08
arXiv:2608.02588 的论文证明了稀疏最小二乘问题的一个条件数下界：在随机化精确体积小集扩张假设（Small-Set Expansion Hypothesis）下，对任意固定的 γ∈(0,1]，不存在多项式时间随机算法能以至少 2/3 概率返回满足误差不超过最优值加 ε、且稀疏度 s=O(k·κ_{s+k}^{1-γ}) 的解。该结果甚至对有理数实例、A 为列满秩时也成立。作者表示，证明最初由 Google 内部开发的基于 Gemini 的自动化智能体系统完成，随后由人工验证并整理。