Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

技術要約：オンライン凸最適化におけるノイズ適応型高確率リグレット境界

問題提起
本研究は、以下の3つの明確かつ相互に関連する課題の下でのオンライン凸最適化（OCO）の問題に取り組むものである。(1) フル情報設定における強凸損失に対するノイズ適応型の高確率リグレット境界の達成、(2) フル情報からバンディットフィードバックへ移行する際の、根本的な信頼コスト（失敗確率 $\delta$ への依存性）の決定、(3) 確率的制約を満たす制約付きOCOにおける、累積リグレットと長期的な制約違反に関する同時高確率保証の確立である。

古典的な結果では、$\alpha$-強凸な損失に対して、オンライン勾配降下法（OGD）が $O(\frac{G^2}{\alpha} \log T)$ の期待リグレット（ここで $G$ は勾配ノルムの上界）を達成することを確立しているが、高確率保証は安全性が重視されるアプリケーションにおいては不十分な場合が多い。標準的な手法はアズマ・ホフディンクの不等式に依存しており、これはマルチンゲール偏差項が最悪の勾配境界 $G$ とドメインの直径 $D$（具体的には $GD\sqrt{2T \log(1/\delta)}$）に依存することになる。この境界は、実際の確率的ノイズレベル $\sigma$ が $G$ よりも大幅に小さい場合（正則化された経験リスク最小化において一般的なレジーム）、緩すぎる。さらに、既存の文献には、ノイズ適応性、フィードバック構造の違い、および高確率な制約充足に関する統一的な扱いが欠けている。

手法および主要な貢献

本論文は、新しい集中不等式の議論と下界構成を通じて、3つの未解決問題を解決する。

1. ノイズ適応型高確率境界（フル情報）:
   著者らは、ステップサイズ $\eta_t = 1/(\alpha t)$ を用いた射影OGDが、マルチンゲール偏差が $G$ ではなくノイズレベル $\sigma$ にスケールする高確率リグレット境界を達成することを証明する。

   • 手法: 解析では、条件付き劣ガウス系列に特化した指数型超マルチンゲール引数を導入する。この手法は、通常、非有界な劣ガウスノイズの切り捨てを必要とするフリードマンの不等式に固有の、有界差分要件を回避する。切り捨てを避けることで、著者らはマルチンゲール性を保持し、偏差項が $O(\sigma D \sqrt{T \log(1/\delta)})$ となる境界を導出する。
   • 結果: リグレット境界は $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$ となる。これにより、$\sigma \ll G$ の場合、古典的なアズマ・ホフディンクのベースラインに対して $G/\sigma$ の乗法的改善が得られる。証明では、勾配ノルムの切り捨てとマルチンゲールのテール集中を分離するために、独立した確率予算を利用している。

2. 信頼コストの分離（バンディット vs. フル情報）:
   本論文は、強凸OCOにおけるフル情報フィードバックとバンディットフィードバックの設定間における、信頼コストのミニマックス下界を示す。

   • 手法: 加法的なガウスノイズを用いたエポックベースのテスト構成を用い、著者らはブレット・アグノー・フーバーの補題と条件付き結合の議論を適用して、困難なインスタンスを構成する。
   • 結果: フル情報設定では、高確率リグレットは $\sqrt{\log(1/\delta)}$ にスケールする。対照的に、バンディットフィードバック（スカラー値の損失のみが観測される設定）の下では、リグレットは $\log(1/\delta)$ として線形にスケールする。これは、強凸問題において、信頼の情報の理論的コストがバンディット設定の方が厳密に高いことを示す最初の形式的な証明である。

3. 同時高確率保証（制約付きOCO）:
   著者らは、スラタ条件を満たす確率的制約の下で、累積リグレットと長期的な制約違反を同時に高確率で制御できる最初のアルゴリズムを提供する。

   • 手法: 解析では、主・双対OGDフレームワークを採用する。リグレット境界は、制約ノイズのほとんど確実な有界性に適用可能なフリードマンの不等式を利用する。制約違反の解析は、累積違反を期待成分と確率的マルチンゲール成分に分解する。期待成分は、サドルポイント引数とマルコフの不等式を通じて境界付けられる。一方、確率的成分はフリードマンの不等式によって制御される。
   • 結果: アルゴリズムは $O(\sqrt{T \log(m/\delta)})$ のリグレットと、$O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$ の長期制約違反を達成する。注目すべきは、違反境界が期待成分に対してマルコフの不等式を介した $1/\delta$ 因子の保持を行う一方で、確率的偏差は $\sqrt{\log(1/\delta)}$ でスケールすることである。

実験による検証
合成実験は、理論的予測を裏付けている：

• ノイズ適応性: 実験的なテール統計量は、リグレットの分位数がノイズ適応的な境界（$\sigma$ 依存）を追跡し、$\sigma \ll G$ の場合にアズマ・ホフディンクのベースライン（$G$ 依存）を大幅に下回ることを確認している。
• 信頼コスト: 1次元の強凸問題を用いた実験により、フル情報の高確率リグレットは $\sqrt{\log(1/\delta)}$ として成長する一方、バンディットのリグレットは $\log(1/\delta)$ として線形に成長することが示され、情報の理論的な分離が検証された。
• 制約付きOCO: リグレットと違反の同時分布は、独立した確率予算付けと、スラタ・ギャップ $\zeta$ に対する逆線形スケーリングを確認している。

意義および主張
本論文は、強凸OCOにおけるノイズ適応性、フィードバック構造、および制約充足の交差点における3つの具体的な未解決問題を解決したと主張している。

• 「信頼の代償」を最悪の勾配の大きさから切り離し、実際のノイズレベルに結びつけることで、ノイズ適応的な洗練を提供している。
• バンディットフィードバックは、フル情報の $\sqrt{\log(1/\delta)}$ ペナルティと比較して、線形な $\log(1/\delta)$ ペナルティを課すという、形式的な分離を確立している。
• 確率的制約設定におけるリグレットと制約違反の両方に対する初の同時高確率保証を提供し、それぞれの成分を支配する統計的メカニズム（マルコフ vs. フリードマン）を明らかにしている。

著者らは、制約違反の境界における $1/\delta$ 依存性は（期待成分に対するマルコフの不等式に依存しているため）現在の証明手法においてタイトであるが、これを $\log(1/\delta)$ に改善することは、主・双対サドルポイント不等式のパスワイズ制御を必要とする未解決の問題であると述べている。同様に、バイアス・超マルチンゲール相互作用を伴うバンディット設定へのノイズ適応性の拡張は、今後の研究方向として特定されている。