論文の概要: Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

• arxiv url: http://arxiv.org/abs/2609.34791v1
• Date: Mon, 28 Sep 2026 10:00:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 02:52:04.933499
• Title: Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
• Title（参考訳）: マルコフ雑音による2時間スケール確率近似の有限時間濃度と収束速度
• Abstract要約: 制御マルコフ連鎖によって駆動される投影された2時間1/2スケール近似の有限時間濃度と収束率について検討した。 スコロホッド写像を用いて、運動する高速平衡と予測されるスローダイナミクスを追跡するために、明示的な高確率境界を確立する。
• 参考スコア（独自算出の注目度）: 23.031381267928904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contractive, while the slow iterate is projected onto a compact convex polyhedron. The associated projected ordinary differential equation may have a discontinuous vector field at the boundary, preventing a direct application of standard analyses based on Lipschitz vector fields. Using the Skorokhod map, we establish explicit high-probability bounds for tracking the moving fast equilibrium and the projected slow dynamics. These bounds separate martingale fluctuations, Markov-noise residuals, and the bias due to time-scale separation. A Lipschitz Lyapunov function satisfying a uniform decrease condition over fixed time intervals yields almost-sure convergence, with explicit last-iterate rates when the decrease admits a power lower bound. Under uniform Lyapunov contraction, polynomial step sizes yield joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to $1/3$. Under the additional assumption that the reduced slow update map is a Euclidean contraction, logarithmically separated step sizes improve the joint rate to $O(n^{-1/2}\log n)$ almost surely, including for boundary equilibria. The same rate holds under a distinct geometric condition involving a strictly attracting face of a box and a fast equilibrium that is constant on that face. An actor-critic application achieves an almost-sure value-gap rate of $O(n^{-1}\log n)$ relative to the optimum within the constrained policy class. Further applications include projected TD(0) and projected stochastic gradient descent. We also extend the analysis to projection of the fast recursion under Euclidean contractivity.
• Abstract（参考訳）: 制御マルコフ連鎖によって駆動される2時間スケール確率近似の有限時間濃度と収束率について検討した。 平均化された高速写像は収縮的であり、遅いイテレートはコンパクト凸多面体に投影される。 関連する射影常微分方程式は境界における不連続ベクトル場を持ち、リプシッツベクトル場に基づく標準解析の直接的な適用を妨げている。 スコロホッド写像を用いて、運動する高速平衡と予測されるスローダイナミクスを追跡するために、明示的な高確率境界を確立する。 これらの境界は、マーチンゲール変動、マルコフノイズ残差、時間スケールの分離によるバイアスを分離する。 リプシッツ・リャプノフ函数は、一定時間間隔で一様還元条件を満たすことができ、下降が下限の電力を許容するときに、ほぼ全周収束する。 均一なリャプノフ縮約の下では、多項式ステップサイズはジョイント・ファストトラックと遅いリャプノフ・エラー指数を任意に1/3$に近くする。 縮小された遅い更新写像がユークリッドの縮約であるという仮定の下で、対数的に分離されたステップサイズは、境界平衡を含むほぼ確実に$O(n^{-1/2}\log n)$に改善する。 同じ速度は、箱の厳密に引き寄せる面と、その面に一定である速い平衡を含む、明確な幾何学的条件の下で保持される。 アクター批判的なアプリケーションは、制約されたポリシークラス内の最適値に対して、ほぼ確実に$O(n^{-1}\log n)$の値ギャップ率を達成する。 さらに、射影されたTD(0) や射影された確率勾配降下を含む。 また、この解析をユークリッドの収縮率の下での高速再帰の予測にまで拡張する。

関連論文リスト

• Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds [1.6582968942719265]
  一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。 直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。 局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
  論文  参考訳（メタデータ） (2026-09-24T19:37:07Z)
• Provable Non-Acceleration of Standard Strang Splittings of Kinetic Langevin Dynamics [0.0]
  OBABO や BAOAB のスキームや、ランゲヴィン力学の標準的なストラング分割は、マルコフ連鎖モンテカルロアルゴリズムとして広く使われている。 我々は、曲率境界と次元のみに基づくステップサイズと摩擦の固定的な選択が、この加速度を達成することを証明した。
  論文  参考訳（メタデータ） (2026-08-26T01:27:39Z)
• Strong Averaging Principle and Long-Time Dynamics for Fast-Slow SDEs with Increasing Time-Scale Separation and Degenerate Noise [1.0026496861838448]
  時間依存スケール分離パラメータを持つ高速スロー微分方程式の平均化原理を確立する。 ノイズ誘起の平滑化や規則性に基づくアプローチとは対照的に,本手法は凍結高速力学の解離性に依存する。
  論文  参考訳（メタデータ） (2026-08-24T16:30:59Z)
• A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space [0.0]
  ワッサーシュタイン空間において、曲線 $tmapsto_t$ の将来の値 $t_n+h$ を推定するミニマックス速度について検討する。 我々の中心的な結果は、時間空間的ミニマックスの下位境界であり、正規で局所的な輸送に富むサブクラスである。
  論文  参考訳（メタデータ） (2026-06-05T14:43:10Z)
• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis [0.0]
  2時間スケール近似アルゴリズムは、最適化、強化学習、制御などのアプリケーションで使用される。 我々は、より高速な時間スケールが、より遅い時間スケールで非拡張性をもたらすプロジェクションステップを持つ変種について研究する。
  論文  参考訳（メタデータ） (2025-01-18T16:00:14Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)

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

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