The $L_1$-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality

想象一下，你正试图在一块巨大的、多维的画布上绘画，这块画布代表了复杂系统中所有可能的选择组合。在计算机科学和数学的世界里，这个“画布”通常是一个超立方体（hypercube）——一个每一条边都代表一个不同变量的盒子，比如温度、速度或价格。为了理解这个系统的行为，数学家们使用了一种名为**拟蒙特卡罗积分（Quasi-Monte Carlo integration）**的技术。你可以把它想象成在画布上撒下有限数量的“点”（或样本点）来采样整个画面。其目标是完美地挑选这些点，使它们均匀地覆盖整个空间，从而在不需要检查每一寸空间的情况下，获得一个准确的平均值。

问题在于，随着你增加变量的数量（即增加盒子的维度），空间会呈爆炸式增长。这被称为维度之咒（curse of dimensionality）。这就像是在试图寻找一片海滩上的特定一粒沙子，而每当你增加一个维度，海滩的大小就会翻倍；突然之间，这片海滩比整个宇宙还要大。为了衡量一组点对空间的覆盖程度，数学家使用了一个名为**差异性（discrepancy）**的指标。如果差异性很低，说明你的点分布得像完美的网格一样均匀；如果差异性很高，则说明它们像撒了一袋弹珠一样堆积在一起。有时，我们不仅仅是放置点，还会给它们分配“权重”（比如赋予某些点更高的重要性），试图以此来修复这种不均匀性。而核心的问题在于：我们能否利用这些聪明的权重来战胜维度之咒，从而高效地覆盖高维空间？

约瑟夫·迪克（Josef Dick）撰写的这篇论文，针对一种特定且重要的权重类型，给出了一个明确的“不”字。作者证明了，即使允许使用非负权重（这意味着你可以提升某些点的权重，但不能使用负数来抵消其他点），你仍然无法逃脱维度之咒。该论文建立了一个数学证明，表明随着维度的增加，获得理想结果所需的点数呈指数级增长。这不仅仅是一个建议或模拟；它是一个严谨的数学定理。其结果意味着，对于这些特定的规则，问题的复杂度爆炸得如此之快，以至于在处理高维空间时，无论你如何巧妙地分配权重，在实践中都是不可能实现的。

不可战胜的盒子之谜

为了理解为什么这件作品如此重要，让我们来看看数学家使用的工具。想象你有一个神奇的天平，可以测量你的点有多“堆积”。在这个论文所讨论的世界里，这个天平被称为 $L_1$-差异性（$L_1$-discrepancy）。如果你的点分布得非常完美，天平读数为零；如果点分布得很乱，天平读数就会变高。目标是保持这个数值极小。

长期以来，数学家们已知，如果你被迫使用等权重（每个点都计为恰好 1），维度之咒是不可避免的。要在 100 维的盒子中覆盖空间，你需要天文数字般的点数。但一直存在着一种希望：也许如果我们允许使用非负权重——即给予某些点“超级力量”，让它们的权重变成 2 或 3，而另一些点则是 0.5——我们就能欺骗系统？也许我们可以通过让正确的点发挥更大的作用，从而使用更少的点？

约瑟夫·迪克的论文彻底封死了这条路。其证明过程有点像一个关于视角转变的侦探故事。作者并没有用通常的方式观察这些点，而是改变了“概率测度（probability measure）”，这是一种高级说法，意指他改变了游戏规则，通过不同的视角来看待这个问题。他引入了一个“体积偏置（volume-biased）”的视角，这本质上是放大了观察范围，聚焦于那些点最容易错过目标的盒子角落。

以下是核心论证的简化版：

1. 设定： 作者假设，为了论证起见，有人已经找到了一组能在高维空间完美运作的神奇点集和权重。
2. 陷阱： 随后，他使用了一个涉及“分数矩（fractional moments）”（一种对微小数值非常敏感的平均方式）的数学技巧，来证明如果这样完美的集合确实存在，它将违反一项基本的数学规则。
3. 结果： 数学表明，为了获得一个好的结果，所需的点数 $N$ 必须至少是某个特定数字的 $d$ 次幂。具体来说，论文证明了对于任何微小的误差容限 $\varepsilon$，所需的点数至少为：
   $$N \ge (1 - \varepsilon)^{\frac{2}{1 + \varepsilon}} \left( \frac{3 + 2\sqrt{3}}{6} \right)^d$$
   其中 $\frac{3 + 2\sqrt{3}}{6}$ 大约等于 1.077。

用通俗易懂的话来说，这意味着每增加一个维度，你需要的点数大约会比之前多出 1.077 倍。虽然 1.077 听起来并不多，但在指数增长的世界里，这是一个灾难。如果你从 10 维增加到 100 维，这个微小的乘数会变成一个巨大的数字，甚至超过宇宙中的原子总数。

这篇论文非常谨慎地界定了它的适用范围。它特别排除了使用负权重的情况。如果你被允许使用负数（即给予某些点“反质量”来抵消堆积的部分），故事可能会有所不同。但在现实世界的许多物理和金融模型中，你不能使用负权重；权重必须是零或正数。既然这篇论文证明了对于所有非负权重，维度之咒都成立，那么它便证实了对于这些现实场景，这种难度的指数级爆炸是不可避免的。

因此，对于我们这些好奇的青少年来说，结论是：在高维世界里，你不能仅仅靠“加权”来摆脱困境。无论你如何分布你的点，或者无论你如何提升它们的重要性（只要保持为正值），空间的巨大规模永远会占据上风。所谓的“维度之咒”不仅仅是一个传闻，它是这类问题的一个数学定律。这篇论文不仅提出了这一观点，还用那种不留任何余地的铁律逻辑进行了证明。通过简单的加权点来寻找解决这些庞大、多维谜题的捷径，这个梦想正式破灭了。