统计博士后驯服数十年之久的旧几何问题

在1980年代中期，数学家让·布尔加因（Jean Bourgain）提出了一个有关高维形状的简单问题。然后他一生都坚持不懈。

布尔根（Bourgain）于2018年去世，是近代杰出的数学家之一。他是数学领域的最高荣誉菲尔兹奖章的获得者，被誉为“解决问题的杰出人物”，您可能会和您谈论一个已经解决了几个月的问题，只是让他解决问题的人。点。然而，布尔根（Bourgain）无法回答自己有关高尺寸形状的问题。

特拉维夫大学的维塔利·米尔曼（Vitali Milman）写道：“让让曾经告诉我，他在这个问题上花费了更多的时间，并且比他曾经研究过的任何其他问题花费了更多的精力。”

自从布尔加因提出问题以来的几年里，这已成为以色列魏茨曼科学研究所的米尔曼和博阿兹·克拉塔格所称的“门户”，以理解有关高维凸形的各种问题，这些问题总是包含连接其任意两个点的整个线段。高维凸形不仅是纯粹的数学家的研究重点，也是统计学家，机器学习研究人员和其他处理高维数据集的计算机科学家的主要研究对象。

布尔加因的问题归结为以下简单问题：假设凸形在您最喜欢的单位选择中具有体积1。如果您考虑使用低一维平面切割形状的所有方法，那么这些切片是否都具有极小的面积，或者至少必须相当大？

布尔甘猜测，这些低维切片中的某些切片必须具有足够的面积。特别是，他推测存在一个与尺寸无关的通用常数，从而每个形状都包含至少一个面积大于该常数的切片。

乍看之下，布尔加因的猜想似乎显然是正确的。毕竟，如果形状在每个方向上都非常瘦，那么它怎么有足够的物质来形成一个单位体积？

“来吧，这有多难？”魏茨曼研究所的高维几何学家罗恩·埃尔丹（Ronen Eldan）记得他第一次听说这个问题时的想法。 “然后，您对它的思考越多，您就越了解它的真正精致之处。”

困难在于高维形状经常以违背我们人类低维直觉的方式表现。例如，在尺寸10或更大的尺寸中，可以构建一个立方体和一个球，以使立方体的体积比球大，但是穿过立方体中心的每个切片的面积都小于穿过立方体中心的相应切片的面积。球。

华盛顿州雷德蒙市Microsoft Research的塞巴斯蒂安·布贝克（SébastienBubeck）说：“高维几何的美妙之处在于，它看上去根本不像二维。

布尔加因的切片猜想是对高维驯服的投票-猜测高维形状至少在某些方面符合我们的直觉。

现在，布尔加因的猜想已经得到了证明：11月在线发表的一篇论文已经证明，不是布尔加因的全部猜想，而是一个如此接近的版本，以至于出于所有实际目的严格限制了高维怪异性。

陈元思-即将加入杜克大学统计科学系的苏黎世瑞士联邦技术学院的博士后研究员-袁四思（Yuansi Chen）通过一个甚至更深远的关于凸几何的问题解决了布尔加因切片问题。 KLS猜想。这个25岁的猜想询问将形状切成相等的两部分的最佳方法，这暗示了布尔加因的猜想。此外，KLS猜想是统计和计算机科学中许多问题的核心，例如热量通过凸形扩散需要多长时间，或者随机步行者必须从起点开始走几步才能到达一个真正随机的位置。

Eldan说，随机游走几乎是唯一有效的随机点采样方法。对于各种不同的计算机科学问题，他说：“算法中最重要的子例程是，您想对随机点进行采样。”

Chen的新结果立即改进了已知算法的运行时间，这些算法可用于执行任务，例如计算凸形的体积或从各种机器学习模型中采样。 Chen的工作并不能完全证明KLS的全部猜测。但是谈到计算机科学应用程序时，巴贝克说：“您不需要完全的猜想就能获得全部的影响。”

Chen并不是经过培训的凸几何仪-相反，他是统计学家，他对KLS猜想感兴趣，因为他想获得随机抽样的处理方法。 “在我们的社区中没有人认识元四辰，”埃尔丹说。 “很高兴你让这个家伙无所事事，解决了（我们）最重要的问题之一。”

像布尔加因切片问题一样，KLS猜想（以其创建者Ravi Kannan，LászlóLovász和MiklósSimonovits的名字命名）提出了一个简单的问题：假设您想将凸出的形状（可能是一个没有酒窝的苹果）切成两个相等大小的部分，并且您打算将其放在一旁以备以后使用。裸露的表面将变成棕色且不开胃，因此您要使其尽可能小。在所有可能的切口中，哪一个会最大程度地减少裸露的表面？

如果您仅限于直截了当，那么回答这个问题并不难，至少可以回答一下。但是，如果允许您进行曲线切割，则所有投注均无效。在第二维中，数学家知道，最佳切割将始终是直线或圆弧。但是在三维空间中，只有某些简单形状才能理解最佳切割，而对于高维形状，数学家通常甚至都不希望找到最佳切割。

由于很难确定最佳的弯曲切口，因此Kannan，Lovász和Simonovits怀疑如果仅允许直线切割会导致更糟的情况。在1995年，他们猜想这种限制永远不会使事情变得更糟：存在一个普遍常数，使得最佳平切的表面积最多等于恒定值，即最佳整体切例的表面积。

佐治亚理工学院的Santosh Vempala说：“这是一个绝妙的见解，尽管Kannan，Lovász和Simonovits无法证明他们的猜想。他们没有要做的是建立一个通用常数，而是建立一个可以近似计算形状所处尺寸的平方根的因数。因此，例如对于100维凸形，他们知道最佳直线切口的表面积最多是最佳切口的10倍。

暴露10倍的表面积听起来可能并不好。但是，由于高维形状的许多属性都随维数的增长而呈指数增长，因此，相比之下，平方根的增长值是适度的。 Bubeck说：“这已经表明高尺寸方面存在很好的现象。” “事情并没有像他们想象的那样疯狂。”

但是研究人员渴望改善这一结果，而不仅是出于学术兴趣：他们知道KLS因子封装了一个有关随机过程在凸形内的行为方式的信息。这是因为最佳切割越小，随机过程越难以在形状周围快速散布。

想一想一个哑铃，有两个巨大的球通过一个狭窄的桥相连。您可以将其划分为两个相等的部分，而这只是一个小切口，这恰恰体现了桥梁是瓶颈的观念。两个球之一中的热源或随机助行器通常需要很长的时间才能到达另一个球，因为它必须找到通过瓶颈的方式。

当然，哑铃不是凸的。凸形不能像哑铃中的那样具有不成比例的小平面切口，但是也许可以有不成比例的小弯曲切口。 KLS猜想本质上是在询问高维凸形是否可以包含隐藏的，扭曲的哑铃，从而减慢随机混合的速度。

坎南（Kannan），洛瓦兹（Lovász）和西蒙诺维茨（Simonovits）的平方根界限限制了这些隐藏的哑铃的极限程度。 2012年，艾丹（Eldan）通过引入一种称为随机定位的技术来降低其与维度的立方根的界限，该技术大致上是设想将凸形倾斜并沿一个方向一个接另一个地滑动其点，直到它们堆积在一个特定的位置上为止。地区。可以很容易地证明KLS猜想是一个高度集中的质量，它与哑铃几乎一样。通过显示倾斜过程并没有太大改变，Eldan能够计算出原始形状的KLS边界。 “这是一个非常非常美丽的过程，”巴贝克说。

几年后，华盛顿大学的范佩拉（Vempala）和李印达（Yin-Tat Lee）完善了艾尔丹（Eldan）的随机本地化方法，以进一步将KLS因子降低到维度的第四根。在短暂而光荣的时刻，他们认为自己做的事情要强大得多。如果将尺寸称为d，则平方根为d 1/2，立方根为d 1/3，而第四根为d 1/4。通过引入一种称为自举的新技术，Lee和Vempala认为他们可以将KLS边界一直降低到d，使其升至0的幂加上一点软糖因子。由于d 0始终等于1，因此Lee和Vempala的界线或多或少是一个常数。

“这太神奇了，”巴贝克回忆起李在告诉他结果时的讲话。他说：“就我而言，这很重要，值得高度赞扬。”

Lee和Vempala在网上发布了他们的论文。但是几天后，克拉拉塔格发现了一个缺口，破坏了他们对d 0界的证明。 Lee和Vempala迅速发布了修订后的草稿，该草稿仅要求d 1/4的范围。几年来，研究人员一直认为这也许就是KLS故事的终结。

这是因为Eldan和Klartag先前已经证明，任何KLS边界都会立即转换为Bourgain切片边界-例如，Lee和Vempala的d 1/4边界意味着在Bourgain切片问题中，始终存在一个切片，其表面积至少为约1 / d 1/4。但是，数学家们已经知道了几种方法来证明Bourgain切片的1 d 1/4界。因此，也许他们以为Lee和Vempala已经达到了KLS问题的自然终点。

“我开始感到，‘是的，也许这是事实。’”埃尔丹说。

克拉尔塔格说：“感觉到有能力的人正在努力采用这种方法，任何可以利用的东西都被利用了。”但这是在陈远思到来之前。

当Lee和Vempala发布修订后的论文时，他们保留了关于大约d 0界的证明如何起作用的想法。他们解释说，他们的证明中只有一个失败了。

他们的论文引起了Chen的注意，Chen当时是加州大学伯克利分校的统计研究生，他正在研究随机抽样方法的混合速率。随机抽样是许多类型的统计推断中的关键要素，例如贝叶斯统计，贝叶斯统计是一种基于新证据更新信念的框架。 Chen说：“如果要进行贝叶斯统计，则每天都要处理[随机]抽样。”

Lee和Vempala的论文向Chen介绍了随机本地化的概念。 “我认为这是我一段时间以来见过的最漂亮的证明技术之一，” Chen说。

Chen深入研究文学，花了数周的时间试图填补Lee和Vempala的证明中的空白，但无济于事。在接下来的几年中，关于如何修改随机本地化的想法会定期出现在他的脑海中，他会思考几个小时然后放弃。最后，他的一个想法结出了硕果：他意识到，有一种方法，不是证明Lee和Vempala的证词中缺少的陈述，而是解决所有如此强烈的陈述的必要性。

通过Chen所说的“一些小技巧”，而Vempala则称其为“优雅而重要的新见解”，Chen指出了如何使Lee和Vempala的引导方法起作用。该方法采用递归方法来降低KLS边界，方法是显示可以将边界减小得很小，那么有一种方法可以减小它。反复应用，这种自举方法为KLS猜想以及Bourgain切片问题实现了近似恒定的边界。

当Chen在网上发布他的作品时，“我立即基本上停止了我所做的一切，并检查了这篇论文，” Klartag说。考虑到以前的错误证明，以及大多数人从未听说过Chen的事实，研究人员对此保持警惕。但事实证明，他的贡献很容易验证。 “这篇论文是100％正确的，” Klartag说。 “毫无疑问。”

Chen的结果意味着，最佳的50-50凸形切口并没有比最佳的平切口小很多；换句话说，高维凸形不包含带有非常窄桥的隐藏哑铃。从纯粹的数学角度来看，“这很重要，因为在我们的理解中这是一个巨大的漏洞，”巴贝克说。

从实际的角度来看，这意味着可以保证随机游走混合凸出形状的速度比研究人员先前证明的要快得多。除其他事项外，这种理解将有助于计算机科学家在不同的随机采样技术之间进行优先级排序-找出最基本的随机游走何时最佳，以及哪种更复杂但计算成本更高的算法何时会表现更好。

最后，考虑到有多少人尝试并未能证明d 0界，该证明非常简单，Vempala说。他推测，布尔加因可能会想到：“我怎么想念它？”

数学家们一致认为，布尔加因会因这种发展而激动不已。在2018年去世前几个月，他联系米尔曼，询问是否有任何进展。 “他想在离开之前就知道答案，”米尔曼写道。

本文经过修改，以澄清陈元思在杜克大学的主要任命是在统计科学系。