Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

技術要約：非拡大型二段階タイムスケール・ストカスティック近似

問題設定
本論文は、高速マップが縮小写像であるが、簡約化された低速マップが非拡大（non-expansive）である領域における、二段階タイムスケール（two-time-scale, TTSA）ストカスティック近似の収束率を調査している。この設定は、ミニマックス最適化、変分不等式、および制約付きストカスティック近似において発生する。縮小的なTTSAでは、低速変数が一意の平衡点に収束するが、非拡大なケースでは、固定点集合が単一の点になるとは限らない。したがって、自然な性能指標は、特定の点への距離ではなく、固定点残差 $p(y) = h(y) - y$ となる。

先行研究では、この領域における最終イテレートの平均二乗残差率として $O(k^{-1/4+\epsilon})$ が確立されている。本論文は、この $1/4$ という指数の理論的起源を解明し、アルゴリズムの修正によってこれを改善できるかどうかを決定することを目的としている。

手法および理論的枠組み
著者らは、誤差ダイナミクスを、非拡大な低速再帰の固有の収束と、高速追従誤差が低速オラクルへ漏出（leakage）する成分の2つの異なる成分に分解している。

1. 固定スケジュールKM障壁の鋭さ（Sharpness of the Fixed-Schedule KM Barrier）:
   本論文はまず、任意の固定された低速ステップサイズ・スケジュール $(\beta_k)$ に対して、古典的なクラスンスキ・マン（Krasnoselskii–Mann, KM）残差スケール（$\sum \beta_i(1-\beta_i)$ の逆数で定義される）が鋭いことを確立する。平面回転の例を用いることで、著者らは有限ホライゾンの下界を証明し、与えられたスケジュールに対して、いかなる未修正のKM更新も、このスケールよりも速い最悪ケースの残差減衰を達成できないことを示している。これは、標準的なKM更新の解析を精緻化するだけでは不十分であり、アルゴリズムのレジームまたはオラクルの構造自体を変更する必要があることを示唆している。

2. $1/4$ 指数の診断:
   著者らは、「一次の高速多様体漏出（first-order fast-manifold leakage）」を主要な障害として特定した。生のTTSAでは、低速オラクルは真の平衡点 $x^*(Y_k)$ ではなく、現在の高速イテレート $X_k$ における写像を評価する。低速マップの高速座標におけるリプシッツ連続性により、誤差 $g(X_k, Y_k) - h(Y_k)$ は、高速追従誤差 $\|X_k - x^*(Y_k)\|$ に関して一次のオーダーとなる。追従誤差自体は、高速の統計的分散（$\alpha_k$）と、動的なターゲットに対する決定論的なラグ（$(\beta_k/\alpha_k)^2$）のバランスによって支配される。標準的な分離条件 $\beta_k^2/\alpha_k^3 \lesssim 1$ の下でも、鋭いKMスケールとこの一次の漏出が組み合わさることで、合計のサンプル複雑度は $T^{-1/4+o(1)}$ となる。分離条件を破ってもレートは改善されず、単にボトルネックが統計的分散から動的ターゲットのラグへとシフトするだけであり、そのラグも依然として一次の摂動として作用する。

3. 残差による前処理を用いたバイアス補正:
   この一次の漏出を克服するために、著者らは残差前処理付きの低速オラクルを導入する。高速および低速マップの微分を利用することで、高速追従誤差への線形依存性を打ち消す補正項を構成する。
   具体的には、$A(y) = I - \nabla_x f(x^*(y), y)$ および $C(y) = \nabla_x g(x^*(y), y)$ とすると、前処理行列は $P^*(y) = C(y)A(y)^{-1}$ となる。補正されたオラクルは以下のように定義される：
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   テイラー展開により、この補正は低速オラクルのバイアスを、一次（$O(\|e\|)$）から二次（$O(\|e\|^2)$）へと減少させることが示される。ここで $e$ は高速追従誤差である。

主な貢献および結果

本論文は、未修正の手法から構造化されたオラクル仮定の下での最適化アルゴリズムへと進展する、3つの主要な理論的結果を提示している。

1. 固定スケジュール下界:
   著者らは、任意の固定された低速ステップサイズ・スケジュールに対して、未修正のKMイテレーションの平均二乗残差が、一様に $(\sum \beta_i(1-\beta_i))^{-1}$ のスケールを上回ることはできないことを証明した。これにより、先行研究における $1/4$ の指数は緩い解析によるアーティファクトではなく、鋭いKMスケールと一次の漏出が組み合わさった結果であることを確認した。

2. 入れ子状のバイアス補正アルゴリズム ($T^{-1/3}$):
   入れ子状のティコノフ・KMフレームワークにおいて、著者らは残差前処理を適用する。

• 未修正: 生のオラクルを用いた入れ子状の手法は、合計サンプルレート $T^{-1/4+o(1)}$ を達成する。
• 補正済み: 前処理付きオラクルを使用することで、低速オラクルの二乗バイアスは $O(n^{-1})$ ではなく $O(n^{-2})$ （ここで $n$ は内部サンプル数）となる。この構造的変化により、合計サンプル複雑度は $T^{-1/3+o(1)}$ に改善される。
• 注記: この結果は、正確な前処理行列 $P^*(y)$ へのアクセス、または特定の積精度条件を満たす推定器へのアクセスを前提としている。

3. シングルループ学習型前処理器 ($T^{-1/2}$):
   入れ子状の手法における内部ソルの反復コストを避けるため、著者らは、高速平衡、低速変数、および前処理行列をオンラインで追跡するシングルループ・アルゴリズムを提案する。

• この手法は、確率的な微分観測を用いて、$X_k, Y_k, P_k$ の実行時推定値を維持する。
• 滑らかさの仮定（写像の微分可能性および微分オラクルへのアクセス）の下で、このアプローチは、イテレーションあたり $O(1)$ の基本サンプルを用いて、合計サンプルレート $T^{-1/2+o(1)}$ を達成する。
• この改善は、漏出の前処理行列をオンラインで学習する能力に依存しており、これにより内部ソルのコストを効果的に償却（amortize）している。

意義および主張
本論文は、非拡大型TTSAにおける $1/4$ 指数の完全な理論的説明を提供しており、それを鋭いKM残差スケールと一次の高速多様体漏出の相互作用に帰していると主張している。主要な貢献は、この障壁が問題クラスそのものに固有のものではなく、「生の」オラクル構造に特有のものであることを示したことにある。

残差前処理付きオラクルを導入することで、漏出を二次オーダーまで減少できることを示し、これにより収束レートを改善できることを示している。$T^{-1/3}$ の結果はバイアス補正が有効であることの証明として機能し、$T^{-1/2}$ の結果は、微分情報が利用可能であれば、シングルループの設定においてもこれらの利得が実現できることを示している。著者らは、これらの結果を「構造化オラクル（structured-oracle）」の成果として明確に位置づけており、これらがブラックボックスな非拡大固定点法とは異なり、微分可能性およびヤコビアン関連の情報へのアクセスに依存していることを述べている。本研究は、一般的なブラックボックス・オラクルに対して問題を解決すると主張するものではなく、滑らかさが存在する場合に収束を加速させるために必要な具体的な構造的修正（バイアス除去）を特定するものである。