論文の概要: Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic
Approximation under Markovian Noise
- arxiv url: http://arxiv.org/abs/2104.01627v1
- Date: Sun, 4 Apr 2021 15:19:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-06 14:19:30.398462
- Title: Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic
Approximation under Markovian Noise
- Title（参考訳）: マルコフ雑音下における非線形2時間スケール確率近似の有限時間収束率
- Authors: Thinh T. Doan
- Abstract要約: 2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。
特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。
演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
- 参考スコア（独自算出の注目度）: 2.0305676256390934
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the so-called two-time-scale stochastic approximation, a
simulation-based approach for finding the roots of two coupled nonlinear
operators. Our focus is to characterize its finite-time performance in a Markov
setting, which often arises in stochastic control and reinforcement learning
problems. In particular, we consider the scenario where the data in the method
are generated by Markov processes, therefore, they are dependent. Such
dependent data result to biased observations of the underlying operators. Under
some fairly standard assumptions on the operators and the Markov processes, we
provide a formula that characterizes the convergence rate of the mean square
errors generated by the method to zero. Our result shows that the method
achieves a convergence in expectation at a rate $\mathcal{O}(1/k^{2/3})$, where
$k$ is the number of iterations. Our analysis is mainly motivated by the
classic singular perturbation theory for studying the asymptotic convergence of
two-time-scale systems, that is, we consider a Lyapunov function that carefully
characterizes the coupling between the two iterates. In addition, we utilize
the geometric mixing time of the underlying Markov process to handle the bias
and dependence in the data. Our theoretical result complements for the existing
literature, where the rate of nonlinear two-time-scale stochastic approximation
under Markovian noise is unknown.
- Abstract（参考訳）: 本研究では,2つの連結非線形作用素の根元を求めるシミュレーションに基づく手法である,いわゆる2時間スケール確率近似について検討する。
我々の焦点は、確率的制御や強化学習問題でしばしば発生するマルコフ設定における有限時間性能を特徴付けることである。
特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。
このような従属データは、基礎となる演算子のバイアス付き観測結果をもたらす。
演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を0に特徴づける公式を提供する。
この結果は,本手法が期待値の収束を$\mathcal{O}(1/k^{2/3})$で達成していることを示す。
我々の分析は主に、2時間スケール系の漸近収束を研究する古典的な特異摂動理論、すなわち2つのイテレーション間のカップリングを慎重に特徴づけるリャプノフ関数によって動機付けられている。
さらに,マルコフ過程の幾何学的混合時間を利用して,データのバイアスと依存を扱う。
この理論結果はマルコフ雑音下での非線形2時間スケール確率近似の速度が不明な既存の文献を補完するものである。
関連論文リスト
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。
本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。
我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
論文 参考訳（メタデータ） (2024-10-03T09:07:13Z) - Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。
ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。
我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
論文 参考訳（メタデータ） (2023-12-07T14:09:27Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence [65.63201894457404]
非線形微分方程式のドリフトと拡散係数の同定のための新しい非パラメトリック学習パラダイムを提案する。
鍵となる考え方は、基本的には、対応するフォッカー・プランク方程式のRKHSに基づく近似をそのような観測に適合させることである。
論文 参考訳（メタデータ） (2023-05-24T20:43:47Z) - Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
連続時間マルコフ連鎖を介して逆過程が認知されるマルコフジャンププロセスを導入することにより、拡散モデルを離散変数に拡張する。
条件境界分布の単純なマッチングにより、偏りのない推定器が得られることを示す。
提案手法の有効性を,合成および実世界の音楽と画像のベンチマークで示す。
論文 参考訳（メタデータ） (2022-11-30T05:33:29Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。
この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
論文 参考訳（メタデータ） (2021-01-16T17:11:02Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
非線形2時間スケール近似の収束と有限時間解析について検討する。
特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
論文 参考訳（メタデータ） (2020-11-03T17:43:39Z) - Finite-Time Convergence Rates of Decentralized Stochastic Approximation
with Applications in Multi-Agent and Multi-Task Learning [16.09467599829253]
本研究では, 雑音測定により, 演算子の根元を求めるためのデータ駆動手法について検討する。
エージェントのネットワークは、それぞれ独自の演算子とデータ観測を持ち、分散化された通信グラフ上で集約演算子の固定点を協調的に見つける。
我々の主な貢献は、各エージェントで観測されたデータがマルコフ過程からサンプリングされるとき、この分散近似法を有限時間で解析することである。
論文 参考訳（メタデータ） (2020-10-28T17:01:54Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳（メタデータ） (2020-04-08T03:59:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。