Online Komlós converges to mean curvature flow

技术摘要：在线 Komlós 问题向平均曲率流的收敛性

问题陈述
本文研究了“在线 Komlós 博弈”（online Komlós game）的渐近行为。这是一个在 $\mathbb{R}^m$ 空间中进行的零和博弈，由两名玩家组成：Paul（自适应对手）和 Carol（极小化者），博弈进行 $T$ 轮。

• 设定： 在每一轮 $t$，Paul 选择一组位于欧几里得单位球内的 $n$ 个向量 $\{a_{1,t}, \dots, a_{n,t}\}$。Carol 则不可撤销地选择符号序列 $\bar{\varepsilon}_t \in \{-1, 1\}^n$。状态向量 $y_t$ 的更新方式为 $y_t = y_{t-1} + \sum_{i=1}^n \varepsilon_{i,t} a_{i,t}$，初始状态为 $y_0 = 0$。
• 目标： Paul 旨在最大化最终的 $\ell_\infty$ 范数 $\|y_T\|_\infty$，而 Carol 旨在最小化该范数。博弈的价值记为 $K_T(m, n)$。
• 背景： 当 $T=1$ 时，这可以简化为经典的 Komlós 问题（与 Komlós 猜想相关），其目标是限制单批次向量的偏差（discrepancy）。本文关注的是 $T \to \infty$ 的情形，将该博弈视为经典问题的局部化版本，即当状态向量变得很大时，单位球的几何形状在局部变得平滑。

方法论
作者采用了一种连续极限方法，将组合偏差理论与非线性偏微分方程（PDE）及粘性解（viscosity solutions）理论联系起来。

1. 价值函数与重缩放： 他们定义了一个价值函数 $v(y, s)$，代表剩余 $s$ 轮时的博弈结果。通过引入抛物型重缩放 $w_\delta(x, t) = \delta v(x/\delta, t/\delta^2)$，其中 $\delta = 1/\sqrt{T}$，他们将离散的动态规划方程转化为有限差分格式。
2. 极限 PDE 的识别： 当 $\delta \to 0$ 时，该有限差分格式收敛于一个非线性抛物型 PDE。关键步骤在于分析 Bellman 算子的极限：
   $$\max_A \min_{\bar{\varepsilon}} \delta^{-2} (w(x + \delta A\bar{\varepsilon}, t) - w(x, t))$$
   利用 Banaszczyk 定理（Beck-Fiala 定理的 $\ell_2$ 类比），作者刻画了该 max-min 项的极限。他们证明了对于 $n \ge m-1$，该项收敛于一个涉及解的水平集最大主曲率之和的算子。
3. 粘性解： 极限方程被识别为曲率流的水平集表述。具体而言，对于 $n \ge m-1$，方程为：
   $$\partial_t w + \frac{1}{2} |\nabla w| \text{div}\left(\frac{\nabla w}{|\nabla w|}\right) = 0$$
   这是 平均曲率流（Mean Curvature Flow, MCF） 的水平集方程。作者利用粘性解理论（特别是比较原理和稳定性性质）来证明离散价值函数收敛于该 PDE 的唯一粘性解。
4. 消亡时间分析： 博弈的渐近值与初始凸体（单位立方体 $[-1, 1]^m$）在相应的曲率流下的消亡时间 $\tau$ 相关联。作者利用热方程构造了显式的次解（subsolutions）和超解（supersolutions）来界定这一消亡时间。

核心贡献与结果

1. 连续极限定理（定理 2.1）：
   对于任何中心对称凸体 $E$ 且批次大小 $n \ge m-1$，在线 Komlós 博弈的价值满足：
   $$\lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} = \frac{1}{\sqrt{2\tau_n(E)}}$$
   其中 $\tau_n(E)$ 是 $E$ 在由前 $\min(n, m-1)$ 个最大主曲率驱动的流下的消亡时间。对于 $n \ge m-1$，这就是标准的平均曲率流。

2. 维度渐近性（定理 2.2）：
   本文刻画了博弈价值随维度 $m$ 的增长情况。当 $m, n \to \infty$ 且 $n \ge m-1$ 时：
   $$(1-o(1))\sqrt{\log m} \le \lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} \le (\sqrt{2} + o(1))\sqrt{\log m}$$
   这意味着在 MCF 下，单位立方体的消亡时间 $\tau$ 随 $\Theta(1/\log m)$ 缩放。这些界限是通过将 MCF 解与具有特定终端数据的线性热方程解进行比较而得出的。

3. 推广：
   结果推广到了 $\mathbb{R}^m$ 中任意范数 $\|\cdot\|_E$（不仅限于 $\ell_\infty$ 范数）。极限 PDE 取决于所选范数对应的单位球 $E$ 的几何性质。

意义与主张
本文声称建立了在线向量平衡问题与几何流（特别是平均曲速流）之间的严谨联系。

• 局部化： 作者将结果描述为经典 Komlós 猜想的“局部化”。虽然经典问题（$T=1$）是一个全局几何问题，但大 $T$ 极限（$T \to \infty$）实际上是在对单位球的局部几何进行缩放，使得问题受控于局部几何（曲率）而非全局组合结构。
• 方法论桥梁： 这项工作建立在 Kohn 和 Serfaty 建立的框架之上，后者将确定性博弈与 MCF 联系起来，但本文将其扩展到了在线 Komlós 设定中，因为在该设定下，对手拥有更大的自由度（可以选择单位球内的向量，而非仅限于正交框架）。这种扩展关键在于依赖于 Banaszczyk 的偏差界限。
• 潜在洞察： 作者表达了希望通过这种 PDE 视角以及使用热方程势函数进行下界分析，能为离线 Komlós 猜想和其他向量平衡问题提供启发，尽管他们明确表示尚未发现大 $T$ 极限与 $T=1$ 猜想之间的直接联系。他们注意到，虽然在偏差理论中使用平滑势函数（如 cosh）是标准做法，但在该特定设定中使用热方程解进行下界分析则较不常见。

本文并未提出新的向量平衡算法，也未声称解决了 Komlós 猜想本身；相反，它为研究此类问题的在线博弈价值提供了渐近特征描述以及一套新的分析工具（粘性解与曲率流）。