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

あなたは、複雑なシステムにおけるあらゆる選択の組み合わせを表現する、巨大で多次元的なキャンバスに絵を描こうとしているところだと想像してください。コンピュータサイエンスや数学の世界では、この「キャンバス」はしばしばハイパーキューブ（超立方体）と呼ばれます。これは、温度、速度、価格といった異なる変数を各辺が表す箱のようなものです。このシステムがどのように振る舞うかを理解するために、数学者は**準モンテカルロ積分（Quasi-Monte Carlo integration）**という手法を用います。これは、キャンバス全体に「点（ドット）」を有限数散布して、全体像をサンプリングすることだと考えてください。目標は、すべての領域を均等にカバーするようにこれらの点を完璧に選び、すべての箇所を一つひとつ確認することなく、正確な平均値を出すことです。

問題は、変数を増やしていく（＝箱の次元を上げていく）につれて、空間が爆発的に増大することです。これは**次元の呪い（curse of dimensionality）として知られています。それは、新しい次元が加わるたびにサイズが倍増するビーチで、特定の砂粒を見つけようとするようなものです。突然、ビーチは宇宙よりも大きくなってしまいます。点がどれだけ空間をうまくカバーしているかを測定するために、数学者はディスクレパンシー（不一致性）**と呼ばれる指標を用います。ディスクレパンシーが低ければ、あなたの点は完璧なグリッドのように広がっています。高ければ、こぼれた袋の中のビー玉のように固まっています。時には、単に点を配置するだけでなく、それらに「重み」を付ける（例えば、いくつかの点に他の点よりも重要性を与えるなど）ことで、不均衡を修正しようとすることもあります。大きな疑問はこうでした。私たちはこれらの巧妙な重みを使って、次元の呪いを打ち破り、高次元空間を効率的にカバーできるのでしょうか？

ヨセフ・ディック（Josef Dick）によるこの論文は、この特定の重要な種類の重み付けに関しては、その問いに対して決定的な「ノー」を突きつけています。著者は、たとえ非負の重み（ある点を強化することはできるが、他の点を打ち消すために負の数を使うことはできないという意味）の使用が許されていたとしても、次元の呪いから逃れることはできないことを証明しています。この論文は、次元が増えるにつれて、良い結果を得るために必要な点の数が指数関数的に増加することを示す数学的証明を提示しています。これは単なる示唆やシミュレーションではありません。厳密な数学的定理なのです。この結果は、これらの特定のルールにおいては、問題の複雑さが非常に速く増大するため、どれほど巧妙に重みを割り当てたとしても、高次元での解決は実質的に不可能であることを意味しています。

負けられない箱の物語

なぜこれがこれほど大きな意味を持つのかを理解するために、この数学者が用いた道具を見てみましょう。想像してみてください。あなたの手元に、点がどれほど「塊（かたまり）」になっているかを測る魔法のスケールがあるとします。この論文の世界では、そのスケールは$L_1$-ディスクレパンシーと呼ばれます。点が完璧に広がっていれば、スケールはゼロを示します。点が乱れていれば、数値は高くなります。目標はこの数値を極めて小さく保つことです。

長い間、数学者たちは、もし等しい重み（すべての点が正確に1としてカウントされる）の使用を強制された場合、次元の呪いは避けられないことを知っていました。100次元の箱をカバーするには、天文学的な数の点が必要になります。しかし、そこにはかすかな希望がありました。もし非負の重み（ある点に2や3といった「スーパーパワー」を与え、他の点を0.5にするなど）を許容すれば、システムを欺けるのではないか？ いくつかの点をより重要に扱うことで、より少ない点で済ませられるのではないか？ という希望です。

ヨセフ・ディックの論文は、この扉をきっぱりと閉ざします。その証明は、視点の変化を伴う探偵小説のようなものです。著者は、点を通常の方法で見るのではなく、視点を変えることで、別のレンズを通して問題を見るように「確率測度」を変更します。彼は「ボリューム・バイアス（体積バイアス）」の視点を導入しますが、これは本質的に、点がターゲットを外してしまう可能性が最も高い箱の角の部分にズームインすることを意味します。

以下が、簡略化された議論の核心です：

1. 設定： 著者は、議論のために、誰かが高次元でも完璧に機能する魔法の点と重みのセットを見つけ出したと仮定します。
2. 罠： 次に、彼は「分数モーメント（小さな値に対して敏感な平均化の方法）」を用いた数学的なトリックを用い、もしそのような完璧なセットが存在するならば、それは数学の根本的なルールに違反することになることを示します。
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次元へと進むなら、この小さな倍率は、宇宙の原子の数を超えるほどの巨大な数字へと変わります。

この論文は、それが「扱わない」範囲についても非常に慎重に記述しています。これは、負の重みの使用を明確に除外しています。もし負の数を使用することが許されていたら（つまり、ある点に「反質量」を与えて他の塊を打ち消すことができれば）、物語は変わっていたかもしれません。しかし、多くの物理的あるいは金融的なモデルという現実世界において、負の重みを持つことはできません。それらはゼロまたは正である必要があります。この論文が、すべての非負の重みに対してこの呪いが適用されることを証明しているため、これらの現実世界のシナリオにおいては、難易度の指数関数的な爆発は避けられないことが確定したのです。

したがって、好奇心旺盛なティーンエイジャーへの教訓はこうです：高次元の世界では、単に「重み付け」をして問題を回避することはできません。どのように点を分布させようと、あるいはそれらの重要性をどれほど高めようと（ただし正の範囲内に留まる限り）、純粋な空間の大きさが常に勝利します。「次元の呪い」は単なる噂ではなく、これらの種の問題における数学的な法則なのです。この論文は単に示唆しているのではなく、疑いの余地を残さない、鉄壁の論理をもってそれを証明しているのです。単純な重み付きの点を用いて、これらの巨大で多次元的なパズルを解くための近道を見つけるという夢は、公式に終わったのです。