Online Beck--Fiala Down to Logarithmic Sparsity

技術要約：オンライン・ベック–フィアラ問題における対数的な疎性への到達

問題提起
本論文は、組合せ不一致理論（combinatorial discrepancy theory）における中心的な問題である**ベック–フィアラ予想（Beck–Fiala conjecture）**を扱う。この予想は、各列の非ゼロ要素が最大 $d$ 個である任意のバイナリ行列 $A \in \{0, 1\}^{n \times T}$ に対して、$\|A\varepsilon\|_\infty$ の不一致（discrepancy）が $O(\sqrt{d})$ に抑えられるような符号化 $\varepsilon \in \{-1, 1\}^T$ が存在することを主張している。極めて重要な点は、この境界が次元 $n$ および $T$ に依存しないことである。

オフライン版の問題については、Bansal と Jiang が $d \ge \log(T)^2$ の場合に境界を確立するなど、大きな進展が見られた。しかし、オンライン版の変種は依然としてより困難な課題として残っている。オンライン設定では、ベクトル $a_1, \dots, a_T$ が逐次的に公開され、アルゴリズムはプレフィックス不一致 $\max_{t \le T} \|\sum_{s=1}^t \varepsilon_s a_s\|_\infty$ を最小化するために、符号 $\varepsilon_t$ を不可逆的に選択しなければならない。本研究以前の、オンライン・ベック–フィアラ問題に対する最良の既知のアルゴリズム的境界は、一般的なコムロス（Komlós）の結果から導かれる $O(\sqrt{d \log T})$ であった。

手法
著者らは、**コンパクトに支持されたメトロポリス・固定点ウォーク（compactly supported Metropolis fixed-point walk）**に基づく効率的なランダム化オンラインアルゴリズムを開発している。その中核となる手法は、以下の3つの構成要素からなる：

1. トリプレット・カップリング（Triplet Coupling）： アルゴリズムは、有界な領域 $(-L, L)^n$ 内で進化する3つの結合されたランダムウォーク $(X_{t,1}, X_{t,2}, X_{t,3})$ を維持する。各ステップにおいて、アルゴリズムは、各ウォークに対して増分 $\delta_{t,j} \in \{-1, 0, 1\}$ をサンプリングするための三方向カップリング補題（Aden-Ali によるものから適応）を用い、それらの和 $\varepsilon_t = \sum \delta_{t,j}$ が真の符号 $\{-1, 1\}$ となるようにする。
2. 定常測度とバランス： ウォークは、特定の積測度 $\mu = \rho^{\otimes n}$ に関して定常であるように設計されている。アルゴリズムは、現在の状態 $X_{t-1}$ が、入力ベクトル $v_t$ に対して「バランス」が取れていることを保証する。ある状態が $v$-balanced であるとは、$v$ または $-v$ の方向に移動する確率が十分に高い（具体的には $p^+_v + p^-_v \ge 1/3$）ことを指す。状態がバランスされている場合、カップリングは増分がドリフトを打ち消すことを保証し、プレフィックス和を有界に保つ。
3. スケール感受的な曲率とバンプ密度（Scale-Sensitive Curvature and Bump Densities）： 疎なベクトル（$d$ が小さい場合）を扱うために、著者らは $(-1, 1)$ 上に支持された特定の不変密度 $\rho$（「バンプ則」）を構築する。この密度は、ポテンシャル関数 $\Phi_\beta(y) = e^{(1-y^2)^{-\beta}}$ を通じて定義される。証明は、このポテンシャルの**曲率（curvature）**を分析することに依拠している。彼らは、疎なベクトルに対して、「曲率の裾（curvature tail）」（ポテンシャルが劇的に変化する確率）が指数関数的に小さいことを確立した。これにより、ウォークがアンバランスになる確率を抑えることが可能となる。

主要な貢献と結果

• 定理 1.1 (オンライン・ベック–フィアラ)： 著者らは、疎性パラメータ $d$ が $d \ge C (\log T)(\log \log T)^{2+\eta}$ を満たす場合に、プレフィックス不一致 $O(\sqrt{d})$ を達成するランダム化オンラインアルゴリズムを提示している。

  • 失敗確率は $C_\eta T \exp\left(-\frac{c_\eta d}{\log^{2+\eta}(ed)}\right)$ によって抑えられる。
  • これは、ベック–フィアラ予想の妥当性を、オフラインの結果である $d \ge \log(T)^2$ という閾値よりも大幅に改善された、ほぼ対数的な疎性領域へと拡張するものである。

• 系 1.2 (オフライン・ベック–フィアラ)： 本結果の直接的な帰結として、同一の対数的な領域における列疎性 $d$ を持つ行列に対するオフライン・ベック–フィアラ予想が確立される。

• 系 1.3 (オンライン・スペンサー)： 本結果は、オンライン・ベクトル・バランシングのスペンサー設定（ベクトルが $[-1, 1]^n$ 内にある場合）における未解決問題を解決する。著者らは、$T \le \exp\left(\frac{c_\eta n}{\log^{2+\eta}(en)}\right)$ であるとき、プレフィックス不一致 $O(\sqrt{n})$ を達成するオンラインアルゴリズムが存在することを証明した。これは、Kulkarni, Reis, and Rothvoss による予想1に対し、終端の不一致だけでなく、すべての プレフィックスに対して境界を保証するという強い形で肯定的に答えるものである。

• 最適性： 論文では、検討されている $d$ の範囲が本質的に最適であることに触れている。Kulkarni, Reis, and Rothvoss を引用し、$d = o(\log T)$ の場合、無知な敵対者（oblivious adversary）が $\Omega(\sqrt{\log T})$ の不一致を強制できるため、オンラインアルゴリズムが $O(\sqrt{d})$ の不一致を保証することはできないと指摘している。

意義
本論文は、対数的な疎性まで $O(\sqrt{d})$ という最適な境界にプレフィックス不一致を最小化する、最初の効率的なオンラインアルゴリズムを提供すると主張している。これは、理論的なオフラインの予想と、アルゴリズム的なオンラインの性能との間の溝を埋めるものである。その意義は以下の点にある：

1. アルゴリズムの効率性： コムロス問題の従来の最適境界が指数関数的な時間を必要としたのに対し、このアルゴリズムは効率的である（カップリング構成の文脈において線形時間）。
2. 予想の拡張： ベック–フィアラ予想の妥当性を、以前に証明されていたものよりもはるかに低い疎性領域へと押し広げ、オンラインアルゴリズムが可能とされる理論的限界に接近させている。
3. 未解決問題の解決： プレフィックス不一致に関するオンライン・スペンサー予想の強い形式に対して、肯定的な回答を与えている。

注記：証明の生成について
著者らは、証明が ChatGPT 5.6 Pro との対話によって生成されたことを明記している。著者らは、有界なランダムウォークにトリプレット・カップリングを適用することでオンライン・スペンサー問題を解くための、高レベルのガイダンスとプロンプティングを提供した。AIは、$O(\sqrt{n})$ のケースに関する完全な証明と、特定の「バンプ密度」の構成を生成した。その後、著者らはこれらの結果を手動で検証、書き換え、最終的な原稿へと整理した。