Abstract
自己正規化マルチンゲール不等式は、オンライン最小二乗法に対する信頼楕円体、そしてより広く多くのバンディットおよび強化学習の結果の核心にあります。にもかかわらず、既存のベクトル版およびスカラー版の結果は典型的には、共変量が有界であることと、明示的な正則化行列に依存しており、そのため得られる境界は \\emph{スケール不変ではない} ものになっています。自己正規化量自体は定義によりスケール不変ですが、その標準的な上界はそうではないのです。
本論文では、自己正規化マルチンゲールに対してスケール不変な上界が可能となる条件を特徴づけます。追加の仮定なしに、非自明なスケール不変上界が存在し得るのは次元 d=1 のみであることを証明します。さらに d=1 においては、共変量に関する何らの仮定も置かずに、O(\log T) のスケール不変な自己正規化境界を得ます。対照的に、d>1 では、全ての場合において成り立つ非自明なスケール不変上界は存在し得ないことを示します。
次に、この二分法をオンライン線形回帰における \\emph{二重一様} regret（すなわち、共変量のスケールと比較対象のノルムの双方に独立な regret 境界）に結びつけ、Gaillard, Gerchinovitz, Huard, Stoltz による未解決問題、
\\emph{``二乗損失を用いる逐次線形回帰問題に対する \mathbb{R}^d 上での一様 regret 境界''}（ALT 2019）を解決します。すなわち d=1 では、O(\log T) の二重一様 regret を達成する明示的なアルゴリズムを提示します。一方 d>1 では、従属次元が正である二重一様 regret を準線形にはできず不可能です。
最後に、自然な \\emph{滑らかさ} 条件（固定された基準測度に関する条件付き共変量分布の Radon--Nikodym 微分が有界）を仮定すると、共変量が有界でない場合でも d>1 に対して準線形 regret を回復し、通常の正則化ペナルティを伴わない自己正規化集中不等式を導きます。これは、おそらく適応的で非 i.i.d. なベクトル・マルチンゲールに対する初めての自然なスケール不変な境界であると言えます。
