論文の概要: Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach

• arxiv url: http://arxiv.org/abs/2603.14481v1
• Date: Sun, 15 Mar 2026 17:00:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:35.83308
• Title: Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach
• Title（参考訳）: 2つの時間スケール確率近似の収束性: Martingale アプローチ
• Authors: Mathukumalli Vidyasagar,
• Abstract要約: ボルカール (1997) で導入された2つの時間スケール近似 (TTSSA) アルゴリズムを, マーチンゲール法を用いて解析した。 我々の理論は非線形方程式に適用できるが、TSSAの文献では方程式が線型であると仮定する多くの論文とは対照的である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we analyze the two time-scale stochastic approximation (TTSSA) algorithm introduced in Borkar (1997) using a martingale approach. This approach leads to simple sufficient conditions for the iterations to be bounded almost surely, as well as estimates on the rate of convergence of the mean-squared error of the TTSSA algorithm to zero. Our theory is applicable to nonlinear equations, in contrast to many papers in the TTSSA literature which assume that the equations are linear. The convergence of TTSSA is proved in the "almost sure" sense, in contrast to earlier papers on TTSSA that establish convergence in distribution, convergence in the mean, and the like. Moreover, in this paper we establish different rates of convergence for the fast and the slow subsystems, perhaps for the first time. Finally, all of the above results to continue to hold in the case where the two measurement errors have nonzero conditional mean, and/or have conditional variances that grow without bound as the iterations proceed. This is in contrast to previous papers which assumed that the errors form a martingale difference sequence with uniformly bounded conditional variance. It is shown that when the measurement errors have zero conditional mean and the conditional variance remains bounded, the mean-squared error of the iterations converges to zero at a rate of $o(t^{-η})$ for all $η\in (0,1)$. This improves upon the rate of $O(t^{-2/3})$ proved in Doan (2023) (which is the best bound available to date). Our bound is virtually the same as the rate of $O(t^{-1})$ proved in Doan (2024), but for a Polyak-Ruppert averaged version of TTSSA, and not directly. Rates of convergence are also established for the case where the errors have nonzero conditional mean and/or unbounded conditional variance.
• Abstract（参考訳）: 本論文では,1997年にボルカールで導入された2つの時間スケール確率近似(TTSSA)アルゴリズムをマーチンゲール法を用いて解析する。 このアプローチは、イテレーションがほぼ確実に有界となるための単純な条件と、TSSAアルゴリズムの平均二乗誤差の収束率を0に見積もる。 我々の理論は非線形方程式に適用できるが、TSSAの文献では方程式が線型であると仮定する多くの論文とは対照的である。 TTSSAの収束は、分布の収束、平均の収束などを確立するTSSAに関する以前の論文とは対照的に、ほぼ確実な意味で証明されている。 さらに、本論文では、おそらく初めて、高速かつ遅いサブシステムに対して異なる収束率を確立する。 最後に、上記の結果の全ては、2つの測定誤差が非ゼロ条件平均を持つ場合、および/または繰り返しが進むにつれて束縛されずに成長する条件分散を持つ場合において持続する。 これは、誤差が一様有界な条件分散を持つマーチンゲール差分列を形成すると仮定した以前の論文とは対照的である。 測定誤差が条件平均をゼロとし、条件分散が有界であるとき、全ての$η\in (0,1)$に対して、反復の平均二乗誤差は$o(t^{-η})$の速度でゼロに収束する。 これにより、Doan (2023) で証明された$O(t^{-2/3})$のレートが向上する。 我々の境界は、Doan (2024)で証明された$O(t^{-1})$のレートとほぼ同じであるが、Polyak-Ruppert平均バージョンのTSSAは直接ではない。 誤差が非ゼロ条件平均および/または非有界条件分散を持つ場合にも収束率が確立される。

関連論文リスト

• Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds [9.739744677824286]
  定段近似(SA)は計算効率の学習に広く用いられている。 以前の研究は、段数 $downarrow 0$ のとき中心とスケールの定常状態がガウス確率ベクトルに弱収束することを示していた。 この論文は、固定された$に対して明示的で漸近的でないエラー境界を提供する。
  論文  参考訳（メタデータ） (2026-02-15T02:34:50Z)
• Online Covariance Estimation in Nonsmooth Stochastic Approximation [14.818683408659764]
  非滑らかな変分包含問題を解くために近似法(SA)を適用することを検討する。 我々の収束構造は、統計的推定法で最もよく知られているものを確立する。
  論文  参考訳（メタデータ） (2025-02-07T20:16:51Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  我々は、一般的な非データ生成プロセスの下で、最初のタイプIエラーと予測リジェクション時間保証を提供する。 本研究では, 平均処理効果など, 方程式を推定することによって定義されるパラメータの推測に, 結果を適用する方法を示す。
  論文  参考訳（メタデータ） (2022-12-29T18:37:08Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean [9.289846887298854]
  信頼シーケンスは、時間パラメトリックカバレッジ保証付き予測可能なパラメータシーケンスに対する適応されたセット列を生成する。 この研究は、スラックが0に収束するランニング平均条件付き期待値に対して、漸近的でない低CSを構成する。
  論文  参考訳（メタデータ） (2022-10-20T09:50:05Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。