High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

技術要約：マルコフノイズを伴う高確率なPL-SGD

問題設定
本論文は、勾配サンプルが独立ではなく外生的なマルコフ連鎖によって生成される、ポリヤク・ロジャシッチ（PL）条件を満たす滑らかな目的関数に対する一次確率的最適化手法を調査している。設定は、再帰式 $x_{k+1} = x_k - \alpha_k G_k$ であり、ここで $G_k = g(x_k, Z_k) + M_{k+1}$ である。ここで $(Z_k)$ は不変分布 $\pi$ を持つマルコフ連鎖であり、$g(x, \cdot)$ は $\int g(x, z)\pi(dz) = \nabla f(x)$ を満たすオラクルである。また、$M_{k+1}$ はマルチンゲール差分摂動である。勾配オラクルは、有界な「ABC」成長エンベロープ $\|G_k\|^2 \leq A\|\nabla f(x_k)\|^2 + B(f(x_k) - f^\star) + C$ を満たす。これは、勾配の分散が目的関数のギャップや勾配ノルムに応じてスケールすることを可能にするものであり、過学習モデルや最小二乗問題において一般的な特徴である。

対処すべき主要な課題は、ノイズの時間的依存性である。独立またはマルチンゲールノイズとは異なり、マルコフノイズは連鎖が混合するにつれて減少するバイアスを導入する。先行研究では $\tilde{O}(t_{\text{mix}}/k)$ とスケールする期待値の境界が確立されていたが、高確率境界については $\tilde{O}(t_{\text{mix}}^2/k)$ となっており、二次的な $t_{\text{mix}}$ への依存性が本質的なものか、あるいは（特にポアソン方程式の分解といった）証明手法によるアーティファクトであるかという点に関するギャップが存在していた。

手法
本論文では、ライトテイル（軽裾）およびヘビーテイル（重裾）のレジームに対して、2つの異なる手法的枠組みを採用している。

1. ライトテイル・レジーム（有界なABCエンベロープ）:

   • ラグ・ブロッキング（遅延ブロック）引数: ポアソン方程式の分解（これはノイズの大きさを $t_{\text{mix}}$ 倍に増幅させる）を用いる代わりに、著者らは「ラグ・ブロッキング」技術を導入している。ターゲットとなる時刻 $k$ に対して、解析的な遅延 $m_k$ を導入する。マルコフ的な降下項は、遅延部分、混合バイアス部分、置換誤差、および初期ウィンドウへと分解される。
   • 剰余類マルチンゲール: $m_k$ ステップ前の $\sigma$-代数で条件付けることにより、遅延された観測量はダウンサンプリングされたフィルタリングに対するマルチンゲール差分となる。この和は $m_k$ 個の剰余類に分割される。各クラス内で集中不等式（Azuma-Hoeffding）を適用し、クラス間の独立性は必要としない。
   • バイアスと誤差の制御: 混合バイアスは全変動混合プロファイルを通じて制御され、置換誤差（遅延中にイテレートが移動することによる誤差）は、オラクルのリプシッツ連続性とABCエンベロープを用いて抑えられる。

2. ヘビーテイル・レジーム（有限の $p$ 次モーメント、$p \in (1, 2]$）:

   • 全サンプル・クリッピング・ブロック法: 分散が無限になる可能性がある、有限の $p$ 次モーメントのみを持つ勾配を扱うために、著者らはブロックベースのアルゴリズムを提案している。イテレートは、$b$ 個の連続するマルコフ遷移にわたって固定される。ブロック内の各勾配は座標ごとにクリッピングされ、これらのクリップされたサンプルの平均を用いて更新が行われる。
   • サンプルの破棄なし: 独立性を確保するためにサンプルを破棄する他のロバストな手法とは異なり、本手法はブロック内のすべてのマルコフ遷移を利用する。混合ウィンドウは、分析（ラグ・ブロッキング）とクリッピング閾値の選択を通じてのみ寄与する。
   • 集中: 解析では、定常的なクリッピング・バイアス/分散の推定と、連続するブロックに対する剰余類マルチンゲール集中論を組み合わせる。これはライトテイルの場合と同様であるが、Freedmanの不等式を用いてヘビーテイルに適応されている。

主な貢献と結果

1. ライトテイルPL-SGDに対する最適な高確率境界:

   • 本論文は、幾何学的混合の下での通常の1サンプルSGDに対する一様時間高確率境界を確立している。主要な確率的項は $\tilde{O}\left(\frac{t_{\text{mix}}}{k + K_0}\right)$ とスケールする。
   • この結果は、$\tilde{O}(t_{\text{mix}}/k)$ の期待値境界と、既知の $\tilde{O}(t_{\text{mix}}^2/k)$ の高確率境界との間のギャップを埋め、標準的なSGDアルゴリズムを変更することなく、線形な $t_{\text{mix}}$ への依存性が達成可能であることを証明した。

2. 一致する下限:

   • 持続的な2状態マルコフ連鎖によって駆動される1次元二次目的関数に対して、下限が証明されている。その結果、$\mathbb{E}[f(x_k) - f^\star] = \Omega(\sigma^2 t_{\text{mix}}/k)$ であり、一定の確率で成立することが示された。
   • これにより、定数信頼度における高確率保証において、線形な多項式依存性は（対数因子を除いて）回避不可能であることが確認された。

3. ヘビーテイル・ロバスト最適化:

   • 勾配が有限の定常 $p$ 次モーメントを持つ場合、提案されたクリップド・ブロック法は、高確率の確率的誤差 $\tilde{O}\left(\sigma_p^2 \left(\frac{t_{\text{mix}}}{T}\right)^{2(p-1)/p}\right)$ を達成する（ここで $T$ は総遷移予算である）。
   • 指数 $2(p-1)/p$ および有効サンプルサイズ（$T/t_{\text{mix}}$）への依存性は、「粘着性（sticky）」のあるマルコフ連鎖を用いて構築された一致する下限によって、最適であることが示されている。

意義と主張
本論文は、PL確率的最適化におけるマルコフ依存性の統計的コストを厳密に特徴付けていると主張している。

• ライトテイル・ノイズに対して: 以前の高確率境界における二次的な混合時間依存性が本質的であったかという未解決の問いを解決した。線形な下限と一致する上界を証明することで、通常のSGDが $t_{\text{mix}}$ に対する最適な多項式依存性を達成することを確立した。
• ヘビーテイル・ノイズに対して: ヘビーテイルの設定へのロバスト最適化の保証を拡張し、有効サンプルサイズが混合時間によって減少すること、および有限モーメントの指数が回避不可能であることを示した。
• 手法の新規性: ラグ・ブロッキング引数は、ノイズの大きさを人工的に増幅させることなく、標準的なSGDアルゴリズムの単純さを維持しながら、高確率分析のためのポアソン方程式分解に代わる優れた代替案として提示されている。

本研究は、ヘビーテイルの上界における次元依存性に関する最適性については主張しておらず、下限の構築が1次元であることを注記している。また、分析は外生的なマルコフ連鎖を想定しており、パラメータ依存のカーネル（例：アクター・クリティック法）については今後の課題として残している。