一名 Microsoft 的研究员和 Zhao Song 证明了 KLS 猜想
十月的证明在一次由人类指导的人工智能搜索帮助识别出关键数学准则之后，消除了1995年界限中的维度依赖。
By Ryan Merket · Published · Updated
Primary source: Microsoft Research
为何重要
该证明将一个关于高维采样的广泛使用的假设变成了一个定理。其人工智能的贡献也很具体：有指导的探索帮助研究人员找到一个有用的判据，而人类的数学判断则塑造并完成了证明。
一份于10月4日发布的证明解决了 Kannan-Lovász-Simonovits 猜想，这是一个关于随机游走如何高效探索高维概率分布的1995年问题。Microsoft Research 于10月21日宣布了该结果，并归功于 Microsoft 研究员 Xinzhi Zhang 和合作者 Zhao Song。他们的论文建立了一个不随维度增长的界限，这正是该猜想的核心主张。
该结果涉及各向同性对数凹概率测度，这是一个用于建模具有良好凸结构的分布的广泛数学类别。用几何上的简略说法，KLS 问的是在这样的空间中最窄的瓶颈是否可以通过一个平面割在一个普适常数因子内被捕获。这个因子在31年里一直抵抗着一个与维数无关的证明。瓶颈的几何结构决定了随机游走混合的速度，从而将 KLS 与采样理论联系起来。该猜想还与概率论和理论计算机科学中使用的集中不等式和 Poincaré 不等式相关联。…
When you purchase through links in our articles, we may earn a small commission. This doesn’t affect our editorial independence.