高维思考练习（困扰陶哲轩启蒙者的高维几何难题被这个90后华人博后解决了）

【新智元导读】困扰菲尔兹奖得主让·布尔甘20余年的几何难题竟然被一个90后华人统计学博后解决了！这个90后不简单！

菲尔兹奖得主、比利时数学家让·布尔甘（Jean Bourgain）被认为是这个时代最具独创性、最敏锐、最多才多艺的分析学大师之一。

数学家陶哲轩早期受其影响颇多，他曾经这样概括自己的早期工作：「读他的论文，学会他的技巧，尝试做些改进。」

但是，20世纪80年代中期，布尔甘提出了一个高维图形的问题，这个看似简单的问题竟然伴随了他的余生，一直悬而未决。

布尔甘提出的问题可以简单总结为：假设一个凸形的体积为1，单位不重要。如果你尝试用低一维的平面切开凸形，尝试所有方法后得到的切片是否都有极小的面积，或者至少有一个面积必须是相当大的？

布尔甘猜测，其中一些低维切片一定有相当大的面积，尤其是存在一个与维度无关的「通用常数」，这样每个形状都至少包含一个面积大于这个常数的切片。

乍一看，布尔甘的猜想显然是正确的。毕竟，如果这个形状在各个方向上都非常细小，它怎么可能有足够的物质形成一个体积单位呢？

「得了吧，这能有多难?」魏茨曼科学研究所的高维几何学家Ronen Eldan第一次听说这个问题时这样想。「然后，你越想它，你就越明白它有多微妙。」

难点就在于，高维图形的行为常常违背我们人类的低维直觉。例如，在尺寸为10及以上的情况下，可以建立一个立方体和一个球，使得立方体的体积大于球，但是每一个穿过立方体中心的切片的面积小于穿过球中心的相应切片的面积。

布尔甘的切片猜想是对解决高维问题的一种想法——高维形状至少在某些方面符合我们的直觉。

90后华人统计学博后跨界解决难题

现在，布尔甘的猜测得到了证实: 去年11月发表在网上的一篇论文提供了一个非常接近的版本，虽然并没有证明布尔甘的全部猜想，但从所有实际目的来看，它严格限制了高维奇异性。

这篇论文作者是Yuansi Chen，瑞士苏黎世联邦理工学院的博士后研究生，今年年初，他开始在杜克大学统计科学系担任助理教授的职位。

主要研究方向是统计机器学习、优化以及在神经科学中的应用，尤其对其中域适应性、稳定性、MCMC采样算法、卷积神经网络和计算神经科学中出现的统计问题感兴趣。

2019年，他在加州大学伯克利分校统计系获得博士学位。

其博士生导师是著名华裔统计学家、UC伯克利统计系和电子工程与计算机科学系终身教授郁彬。

在攻读博士之前，他还在法国Ecole Polytechnique获得了应用数学专业的工程师文凭。

随后，前往在苏黎世联邦理工学院ETH Foundations of Data Science（ETH-FDS）做博士后研究。

这个有25年历史的猜想，要求将一个形状切成两等分的最佳方法，暗示了布尔甘猜想。

更重要的是，KLS猜想是许多统计学和计算机科学问题的核心，例如热量需要多长时间才能通过凸形扩散，或者一个随机行走者必须从一个起点走多少步才能到达一个真正随机的位置。

高维几何学家Ronen Eldan表示，随机漫步是对随机点进行抽样的唯一有效方法。对于各种各样的计算机科学问题，「算法中最重要的子程序是，你要对一个随机点进行采样。」

Chen的论文结果对已知的任务算法运行时间提供了及时的改进，这些任务包括计算凸形体的体积或者从一组机器学习模型中抽取样本。他的工作并不能完全证明 KLS 猜想。

但是当涉及到计算机科学的应用时，微软研究院的Sébastien Bubeck说，「你不需要完整的猜想来得到完整的影响。」

Chen并不是几何学专家，而是一个统计学家，他只是对KLS猜想产生了兴趣，因为他想掌握随机抽样的方法。

高维几何领域甚至都没有人认识他，但他却解决了困扰很多人数年的难题。

如何把苹果平均一分为二，还要尽可能保持新鲜？

1995年Kannan、Lovász和Simonovits三人提出的KLS猜想关心的问题：用来平分的最小曲面面积是多少？

假设你想把一个凸形体，也许是一个两头没有凹陷的苹果——切成一样大小的两部分，你打算把切开的一半先放在一边之后再切，但是裸露的表面会氧化变色，让人倒胃口，所以你要尽可能地让先切掉的这一块面积小一些。那么，在所有可能的切割方式中，哪种方式暴露的表面最小？

如果只能直线切割，这个问题并不难。但是如果曲线切割，所有情况都会打折扣。在二维空间中，数学家们知道最好的切法永远是一条直线或一个圆弧。但是在三维空间中，最好的切法只能理解为几个简单的形状，而对于更高维度的形状，数学家们通常找不到任何最佳切法。

既然最佳切法这么难确定，Kannan, Lovász和Simonovits就换了一个角度思考，如果只允许直线切割，情况会糟糕到什么程度。

1995年，他们推测这种限制不会使事情变得更糟，也就是说存在一个通用常数，即最好的平面切割的表面积最多是最好的整体切割表面积的常数倍。

尽管Kannan, Lovász和Simonovits无法证明他们的猜想。他们能做的最好的事情不是建立一个普遍常数，而是建立一个因子，大致计算出形状存在的维度的平方根。

所以对于一个100维的凸面形状，他们知道最好的直线切割得到的面积最多是最佳切割的表面积的10倍。

露出10倍的表面积可能听起来不是很大。但是，由于高维形状的许多属性随着维度的增长呈指数增长，相比之下，一个平方根的增长并不算太多。

但是研究人员急于改进这个结果，而不仅仅是出于学术兴趣: 他们知道 KLS 因子包含了很多关于随机过程在凸形状中表现如何的信息。这是因为最好的切口越小，随机过程就越难以迅速在形状周围扩散。

就像哑铃，两个巨大的球被一个狭窄的部分连接。你可以用一个很小的切口把它分成两个相等的部分，这个切口就是一个瓶颈。两个球中任意一个球的漫步者或者热源通常需要很长时间才能到达另一个球，因为它必须找到通过瓶颈的路。

当然，哑铃不是凸的。一个凸起的形状不可能有一个不成比例的小而平的切口，就像哑铃上的那个，但是也许它可以有一个不成比例的小的弯曲切口。KLS 猜想实质上是要问一个高维的凸形是否可以包含一个隐藏的、扭曲的哑铃，它可以减缓随机混合。

Kannan, Lovász和Simonovits的平方根限制了这些隐藏的哑铃的极限。在2012年，Eldan 通过引入一种叫做随机定位的技术降低了他们对维度的立方根的限制，粗略地说，这种技术设想倾斜凸面形状，使其点向一个方向滑动，直到它们堆积在一个特定的区域。

对于一个高密度的物体，很容易证明 KLS 猜想，这个质量和哑铃差不多。通过表明倾斜过程并没有改变太多东西，Eldan能够计算出一个 KLS 的界限为原始形状。

几年后，华盛顿大学的Yin-Tat Lee和Vempala改进了Eldan的随机局部化，进一步降低KLS因子，到维度的四次方根。

他们一度认为自己解决了更大的问题。如果维度称为d，那么平方根是d1/2，立方根是d1/3，四次方根是d1/4. 通过引入一种叫做 bootstrapping 的新技术，Lee（下图左）和 Vempala（下图右）认为他们可以将 KLS 的边界降低到d，升高到0的幂加上一点容差系数。

由于d0总是等于1，Lee和Vempala似乎证明了KLS因子是一个与维度无关的常数。

他们在arXiv上发布了他们的论文。但是几天后，这篇文章就被人发现了一个缺陷，他们关于d0的证明是错的。

之后，二人修改了文章，把界限重新调整到d1/4. 几年来，研究人员认为KLS猜想的探索已经到此终结了。

边界切片

Lee和Vempala的论文引起了Chen的注意，当时他还是UC伯克利的统计学研究生，正在研究随机抽样方法的混合率。随机抽样在许多类型的推论统计学中都是一个关键因素，比如基于新证据更新信念的框架——贝叶斯统计。

「如果你想做贝叶斯统计的话，你每天都要处理这样的随机抽样。」

Lee 和 Vempala 的论文将Chen引入了随机局部化的概念。他表示：「这是我一段时间以来见过的最漂亮的验证技术之一。」

Chen研究了很多文献，花了几个星期的时间试图填补Lee和Vempala的证据空白，但是没有用。在接下来的几年里，每隔一段时间，他就会想到一些如何修正随机定位的想法。

最后，他想到了一种方法，不是去证明 Lee和Vempala的证明中缺失的陈述，而是绕过需要这样一个强有力的陈述。

基于Lee和Vempala的bootstrapping方法，Chen提出使用递归方法来降低 KLS 边界。他的想法是：如果你可以让边界非常小，那么就有方法让边界更小。

在反复的应用中，他所使用的bootstrapping方法实现了 KLS 猜想与布尔甘截面问题的近似恒定边界。

当Chen把他的研究结果发表在网上后，很多研究员看到后都持谨慎态度，因为之前错误的证明也出现过，而且Chen根本不是几何学家，数学界的研究人员听都没听过他。

但是，在魏茨曼科学研究学院的数学家Bo’az Klartag看过Chen的论文后，说：我基本上立即停止了我正在做的一切事情，并检查了这篇论文。这篇论文是100%正确的！

Chen的研究结果显示，凸形的最佳对半切口并没有比最佳的平切口要小很多；也就是说，高维凸形不包含带有非常窄的桥梁的隐藏哑铃。

从实际的角度来看，这意味着：随机游走混合凸形的速度一定比研究人员之前证明的速度要快得多。

Chen的研究成果明显减少了已知算法在执行任务方面的运行时间，这些任务包括计算凸形体积，或从各种机器学习模型中采样等。

这将有助于计算机科学家在不同的随机采样技术之间进行优先级排序：找出最基础的随机游走在何时表现最佳，以及更复杂但计算成本更高的算法在何时会表现更好。

Chen的工作并不能完全证明 KLS猜想，但在计算机科学应用领域，即使没有完全证明该猜想，Chen的研究也有潜力产生巨大的影响力。

布尔甘曾经告诉特拉维夫大学数学教授Vitali Milman，他在这个问题上花费的时间和精力远超过其他任何问题。

甚至在他去世的前几个月，还曾经询问Milman，这一猜想是否有进展，他想在离开之前知道答案。

但是直到2018年年底布尔甘去世，他都没能等到一个解决方案。

不过，Chen的成果出来后，大家都觉得，如果布尔甘还在世，他一定会为Chen的成果激动不已，甚至可能会想「我怎么会没注意到呢?」

参考资料：

https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/

,