Online Komlós converges to mean curvature flow

Resumo Técnico: Convergência do Komlós Online para o Fluxo de Curvatura Média

Enunciado do Problema
Este artigo investiga o comportamento assintótico do "jogo de Komlós online", um jogo de soma zero entre dois jogadores, Paul (um adversário adaptativo) e Carol (uma minimizadora), jogado ao longo de $T$ rodadas em $\mathbb{R}^m$.

• Configuração: Em cada rodada $t$, Paul seleciona um conjunto de $n$ vetores $\{a_{1,t}, \dots, a_{n,t}\}$ dentro da bola unitária euclidiana. Carol escolhe, de forma irrevogável, os sinais $\bar{\varepsilon}_t \in \{-1, 1\}^n$. O vetor de estado $y_t$ é atualizado como $y_t = y_{t-1} + \sum_{i=1}^n \varepsilon_{i,t} a_{i,t}$, partindo de $y_0 = 0$.
• Objetivo: Paul visa maximizar a norma $\ell_\infty$ final $\|y_T\|_\infty$, enquanto Carol visa minimizá-la. O valor do jogo é denotado por $K_T(m, n)$.
• Contexto: Quando $T=1$, isso reduz-se ao clássico problema de Komlós (relacionado à conjectura de Komlós), onde o objetivo é limitar a discrepância de um único lote de vetores. O artigo foca no regime onde $T \to \infty$, tratando o jogo como uma localização do problema clássico, onde o vetor de estado torna-se grande e a geometria da bola unitária torna-se localmente suave.

Metodologia
Os autores empregam uma abordagem de limite contínuo, estabelecendo uma ponte entre a teoria da discrepância combinatória e a teoria de equações diferenciais parciais (EDPs) não lineares e soluções viscosas.

1. Função Valor e Escalonamento: Eles definem uma função valor $v(y, s)$ que representa o resultado do jogo com $s$ rodadas restantes. Ao introduzir um escalonamento parabólico $w_\delta(x, t) = \delta v(x/\delta, t/\delta^2)$ com $\delta = 1/\sqrt{T}$, eles transformam a equação de programação dinâmica discreta em um esquema de diferença finita.
2. Identificação da EDP Limite: À medida que $\delta \to 0$, o esquema de diferença finita converge para uma EDP parabólica não linear. O passo fundamental envolve analisar o limite do operador Bellman:
   $$\max_A \min_{\bar{\varepsilon}} \delta^{-2} (w(x + \delta A\bar{\varepsilon}, t) - w(x, t))$$
   Utilizando o teorema de Banaszczyk (um análogo $\ell_2$ do teorema de Beck-Fiala), os autores caracterizam o limite do termo max-min. Eles mostram que, para $n \ge m-1$, este termo converge para um operador que envolve a soma das maiores curvaturas principais das superfícies de nível da solução.
3. Soluções Viscosas: A equação limite é identificada como a formulação de nível de um fluxo de curvatura. Especificamente, para $n \ge m-1$, a equação é:
   $$\partial_t w + \frac{1}{2} |\nabla w| \text{div}\left(\frac{\nabla w}{|\nabla w|}\right) = 0$$
   Esta é a equação de nível para o Fluxo de Curvatura Média (MCF). Os autores utilizam a teoria de soluções viscosas (especificamente o princípio de comparação e propriedades de estabilidade) para provar a convergência das funções valor discretas para a solução viscosa única desta EDP.
4. Análise do Tempo de Extinção: O valor assintótico do jogo está ligado ao tempo de extinção $\tau$ do corpo convexo inicial (o cubo unitário $[-1, 1]^m$) sob o correspondente fluxo de curvatura. Os autores constroem subsoluções e supersoluções explícitas usando a equação do calor para limitar este tempo de extinção.

Contribuições Principais e Resultados

1. Teorema do Limite Contínuo (Teorema 2.1):
   Para qualquer corpo convexo centralmente simétrico $E$ e tamanho de lote $n \ge m-1$, o valor do jogo de Komlós online satisfaz:
   $$\lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} = \frac{1}{\sqrt{2\tau_n(E)}}$$
   onde $\tau_n(E)$ é o tempo de extinção de $E$ sob o fluxo pela soma das maiores $\min(n, m-1)$ curvaturas principais. Para $n \ge m-1$, este é o fluxo de curvatura média padrão.

2. Assintótica Dimensional (Teorema 2.2):
   O artigo caracteriza o crescimento do valor do jogo em relação à dimensão $m$. Enquanto $m, n \to \infty$ com $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}$$
   Isso implica que o tempo de extinção $\tau$ do cubo unitário sob MCF escala como $\Theta(1/\log m)$. Os limites são derivados comparando a solução de MCF com soluções da equação do calor linear com dados terminais específicos.

3. Generalização:
   Os resultados generalizam para normas arbitrárias $\|\cdot\|_E$ em $\mathbb{R}^m$, não apenas para a norma $\ell_\infty$. A EDP limite depende da geometria da bola unitária $E$ da norma escolhida.

Significado e Alegações
O artigo afirma estabelecer uma conexão rigorosa entre o problema de balanceamento de vetores online e fluxos geométricos, especificamente o Fluxo de Curvatura Média.

• Localização: Os autores enquadram seu resultado como uma "localização" da clássica conjectura de Komlós. Enquanto o problema clássico ($T=1$) é um problema geométrico global, o limite de grande $T$ ($T \to \infty$) efetivamente dá um zoom na curvatura local da bola unitária, tornando o problema governado pela geometria local (curvatura) em vez da estrutura combinatória global.
• Ponte Metodológica: O trabalho baseia-se no framework estabelecido por Kohn e Serfaty, que conectou jogos determinísticos ao MCF, mas estende-o ao cenário de Komlós online, onde o adversário tem mais liberdade (escolhendo vetores na bola unitária em vez de frames ortonormais). Esta extensão depende crucialmente dos limites de discrepância de Banaszczyk.
• Potenciais Insights: Os autores expressam esperança de que esta perspectiva de EDP e o uso de potenciais da equação do calor para limites inferiores possam lançar luz sobre a conjectura de Komlós offline e outros problemas de balanceamento de vetores, embora afirmem explicitamente não ter encontrado uma conexão direta entre o limite de grande $T$ e a conjectura de $T=1$. Eles observam que, embora potenciais suaves (como cosh) sejam padrão para limites superiores em discrepância, o uso da solução da equação do calor para limites inferiores é menos comum neste contexto específico.

O artigo não propõe novos algoritmos para balanceamento de vetores nem afirma resolver a própria conjectura de Komlós; em vez disso, fornece uma caracterização assintótica do valor do jogo online e um novo conjunto de ferramentas analíticas (soluções viscosas e fluxos de curvatura) para estudar tais problemas.