Online Komlós converges to mean curvature flow

Technical Summary: Online Komlós Convergence to Mean Curvature Flow

Problem Statement
This paper investigates the asymptotic behavior of the "online Komlós game," a zero-sum game between two players, Paul (an adaptive adversary) and Carol (a minimizer), played over $T$ rounds in $\mathbb{R}^m$.

• Setup: At each round $t$, Paul selects a set of $n$ vectors $\{a_{1,t}, \dots, a_{n,t}\}$ within the Euclidean unit ball. Carol then irrevocably chooses signs $\bar{\varepsilon}_t \in \{-1, 1\}^n$. The state vector $y_t$ is updated as $y_t = y_{t-1} + \sum_{i=1}^n \varepsilon_{i,t} a_{i,t}$, starting from $y_0 = 0$.
• Objective: Paul aims to maximize the final $\ell_\infty$ norm $\|y_T\|_\infty$, while Carol aims to minimize it. The value of the game is denoted $K_T(m, n)$.
• Context: When $T=1$, this reduces to the classic Komlós problem (related to the Komlós conjecture), where the goal is to bound the discrepancy of a single batch of vectors. The paper focuses on the regime where $T \to \infty$, treating the game as a localization of the classic problem where the state vector becomes large, and the geometry of the unit ball becomes locally smooth.

Methodology
The authors employ a continuum limit approach, bridging combinatorial discrepancy theory with the theory of nonlinear partial differential equations (PDEs) and viscosity solutions.

1. Value Function and Rescaling: They define a value function $v(y, s)$ representing the game outcome with $s$ remaining rounds. By introducing a parabolic scaling $w_\delta(x, t) = \delta v(x/\delta, t/\delta^2)$ with $\delta = 1/\sqrt{T}$, they transform the discrete dynamic programming equation into a finite difference scheme.
2. Limiting PDE Identification: As $\delta \to 0$, the finite difference scheme converges to a nonlinear parabolic PDE. The key step involves analyzing the limit of the Bellman operator:
   $$\max_A \min_{\bar{\varepsilon}} \delta^{-2} (w(x + \delta A\bar{\varepsilon}, t) - w(x, t))$$
   Using Banaszczyk's theorem (an $\ell_2$ analogue of the Beck-Fiala theorem), the authors characterize the limit of the max-min term. They show that for $n \ge m-1$, this term converges to an operator involving the sum of the largest principal curvatures of the level sets of the solution.
3. Viscosity Solutions: The limiting equation is identified as the level set formulation of a curvature flow. Specifically, for $n \ge m-1$, the equation is:
   $$\partial_t w + \frac{1}{2} |\nabla w| \text{div}\left(\frac{\nabla w}{|\nabla w|}\right) = 0$$
   This is the level set equation for Mean Curvature Flow (MCF). The authors utilize the theory of viscosity solutions (specifically the comparison principle and stability properties) to prove the convergence of the discrete value functions to the unique viscosity solution of this PDE.
4. Extinction Time Analysis: The asymptotic value of the game is linked to the extinction time $\tau$ of the initial convex body (the unit cube $[-1, 1]^m$) under the corresponding curvature flow. The authors construct explicit subsolutions and supersolutions using the heat equation to bound this extinction time.

Key Contributions and Results

1. Continuum Limit Theorem (Theorem 2.1):
   For any centrally symmetric convex body $E$ and batch size $n \ge m-1$, the value of the online Komlós game satisfies:
   $$\lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} = \frac{1}{\sqrt{2\tau_n(E)}}$$
   where $\tau_n(E)$ is the extinction time of $E$ under the flow by the sum of the largest $\min(n, m-1)$ principal curvatures. For $n \ge m-1$, this is the standard mean curvature flow.

2. Dimensional Asymptotics (Theorem 2.2):
   The paper characterizes the growth of the game value with respect to the dimension $m$. As $m, n \to \infty$ with $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}$$
   This implies that the extinction time $\tau$ of the unit cube under MCF scales as $\Theta(1/\log m)$. The bounds are derived by comparing the MCF solution to solutions of the linear heat equation with specific terminal data.

3. Generalization:
   The results generalize to arbitrary norms $\|\cdot\|_E$ in $\mathbb{R}^m$, not just the $\ell_\infty$ norm. The limiting PDE depends on the geometry of the unit ball $E$ of the chosen norm.

Significance and Claims
The paper claims to establish a rigorous connection between the online vector balancing problem and geometric flows, specifically Mean Curvature Flow.

• Localization: The authors frame their result as a "localization" of the classic Komlós conjecture. While the classic problem ($T=1$) is a global geometric problem, the large $T$ limit ($T \to \infty$) effectively zooms in on the local curvature of the unit ball, making the problem governed by the local geometry (curvature) rather than global combinatorial structure.
• Methodological Bridge: The work builds upon the framework established by Kohn and Serfaty, who connected deterministic games to MCF, but extends it to the online Komlós setting where the adversary has more freedom (choosing vectors in the unit ball rather than orthonormal frames). This extension relies crucially on Banaszczyk's discrepancy bounds.
• Potential Insights: The authors express hope that this PDE perspective and the use of heat equation potentials for lower bounds may shed light on the offline Komlós conjecture and other vector balancing problems, though they explicitly state they have not yet found a direct connection between the large $T$ limit and the $T=1$ conjecture. They note that while smooth potentials (like cosh) are standard for upper bounds in discrepancy, their use of the heat equation solution for lower bounds is less common in this specific setting.

The paper does not propose new algorithms for vector balancing nor does it claim to resolve the Komlós conjecture itself; rather, it provides an asymptotic characterization of the online game's value and a new analytical toolset (viscosity solutions and curvature flows) for studying such problems.