いずれLILの後悔：有界でないデータに対するサブガウス混合でのほぼ確実な $\ln\ln T$ 回帰（regret）

arXiv stat.ML / 2026/4/23

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、Robbinsが提案した古典的なサブガウス混合が、「Ville event」と呼ばれる集合 $\mathcal E_\alpha$ 上でパスごとの（決定論的な）回帰（regret）上界を満たすことを示す。
任意のパスが $\mathcal E_\alpha$ に属する場合、時刻 $T$ までの regret は、非負かつ非減少の累積分散過程 $V_T$ に関する項（$\ln^2(1/\alpha)/V_T$、$\ln(1/\alpha)$、および $\ln \ln V_T$）で上から抑えられる（定数は普遍定数として扱う）。
特に $V_T\ge \ln(1/\alpha)$ なら上界は $\ln(1/\alpha)+\ln \ln V_T$ に簡略化され、確率1のイベント $\mathcal E_0$ 上では regret が最終的に $\ln\ln V_T$（定数倍）で抑えられる。
さらに著者らは、通常は有界データを扱うことが多い逆説的（アドバーサリアル）オンライン学習と、確率的仮定の下で有界でないデータを扱えるゲーム理論的統計を、条件付き regret が橋渡しになるという観点で結び付ける。

要旨: ロビンズが確率的な状況で提案した古典的な劣ガウス混合（sub-Gaussian mixture）が、実際には経路ごとの（決定論的な）後悔（regret）に対する上界を満たすことを証明します。自然な「ヴィル（Ville）事象」 $mathcal E_alpha$ に属するあらゆる経路について、時刻 $T$ までのこの後悔は、普遍定数の範囲で、 $\ln^2(1/\alpha)/V_T + \ln (1/\alpha) + \ln \ln V_T$ で抑えられます。ここで $V_T$ は非負で非減少な累積分散（cumulative variance）過程です。（もし $V_T \geq \ln(1/\alpha)$ であれば、この上界は $\ln(1/\alpha) + \ln \ln V_T$ に減少します。）データが確率的であったなら、広いクラスの分布（例：劣ガウス、対称、分散が有界、など）にわたって、 $mathcal E_alpha$ が確率少なくとも $1-\alpha$ を持つことを示せます。実際、確率1のヴィル事象 $mathcal E_0$ 上で、 $mathcal E_0$ に属するすべての経路における後悔は、（定数の範囲で）最終的に $\ln \ln V_T$ で抑えられることを示します。この研究が、（通常は有界データに対する）後悔上界を扱う、敵対的オンライン学習の世界と、（確率的仮定を用いるものの）非有界データを扱えるゲーム論的統計の世界をどのように橋渡しするかを説明します。要するに、条件付きの後悔上界は、確率的な賭けと敵対的な賭けの間の架け橋として機能します。