研究人员为稀疏最小二乘优化确立了一个下界，证实了Axiotis和Sviridenko的猜想。这一发现以随机精确体积小集展开（Small-Set Expansion）的一个特定假设为条件，表明多项式时间算法无法改进对受限条件数的线性依赖性。值得注意的是，该证明最初由Google开发的基于Gemini的代理系统生成，作者随后验证并完善了该结果。 AI
影响 展示了AI在协助复杂数学证明方面的能力，有望加速优化及相关领域的研究。
排序理由 该集群描述了在arXiv上发表的一项数学证明，详细说明了稀疏最小二乘优化的下界。
在 Hugging Face Daily Papers 阅读 →
AI 生成摘要 · Google Gemini · 来自 2 个来源。 我们如何撰写摘要 →
arXiv:2608.02588v1 Announce Type: cross Abstract: 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 boun…
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…