論文の概要: Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2109.03445v6
- Date: Tue, 6 Aug 2024 06:19:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-07 20:01:27.692878
- Title: Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning
- Title（参考訳）: バッチ非同期確率近似の強化学習への応用
- Authors: Rajeeva L. Karandikar, M. Vidyasagar,
- Abstract要約: Reinforcement Learning (RL)のいくつかのアプリケーションでは、textitonlyの$theta_t$の1つのコンポーネントは、各$t$で更新される。
本稿では、 textbfBlock Asynchronous SA (BASA) について検討し、各ステップ $t$, textitsome で $theta_t$ のすべてのコンポーネントが更新される必要はない。
BASA の収束に十分な条件を提供し、$theta_t$ to の収束のテキスト化を証明します。
- 参考スコア（独自算出の注目度）: 2.0584253077707477
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We begin by briefly surveying some results on the convergence of the Stochastic Gradient Descent (SGD) Method, proved in a companion paper by the present authors. These results are based on viewing SGD as a version of Stochastic Approximation (SA). Ever since its introduction in the classic paper of Robbins and Monro in 1951, SA has become a standard tool for finding a solution of an equation of the form $f(\theta) = 0$, when only noisy measurements of $f(\cdot)$ are available. In most situations, \textit{every component} of the putative solution $\theta_t$ is updated at each step $t$. In some applications in Reinforcement Learning (RL), \textit{only one component} of $\theta_t$ is updated at each $t$. This is known as \textbf{asynchronous} SA. In this paper, we study \textbf{Block Asynchronous SA (BASA)}, in which, at each step $t$, \textit{some but not necessarily all} components of $\theta_t$ are updated. The theory presented here embraces both conventional (synchronous) SA as well as asynchronous SA, and all in-between possibilities. We provide sufficient conditions for the convergence of BASA, and also prove bounds on the \textit{rate} of convergence of $\theta_t$ to the solution. For the case of conventional SGD, these results reduce to those proved in our companion paper. Then we apply these results to the problem of finding a fixed point of a map with only noisy measurements. This problem arises frequently in RL. We prove sufficient conditions for convergence as well as estimates for the rate of convergence.
- Abstract（参考訳）: 本稿では,SGD法(Stochastic Gradient Descent, SGD)の収束に関するいくつかの結果を,筆者らによる共用論文で簡単に調査することから始める。
これらの結果は、SGDを確率近似(Stochastic Approximation, SA)のバージョンと見なすことに基づいている。
1951年にRobins and Monroの古典的な論文で紹介されて以来、SAは$f(\theta) = 0$という形の方程式の解を見つけるための標準ツールとなっている。
ほとんどの場合、配置ソリューション $\theta_t$ の \textit{every component} は各ステップ $t$ で更新される。
Reinforcement Learning (RL) のいくつかのアプリケーションでは、$\theta_t$ の \textit{only one component} が各 $t$ で更新される。
これは \textbf{asynchronous} SA として知られている。
本稿では,各ステップ$t$, \textit{some, but not always all} component of $\theta_t$を更新した \textbf{Block Asynchronous SA (BASA)} について検討する。
ここで提示される理論は、従来の(同期) SA だけでなく、非同期 SA も含んでいる。
BASA の収束に十分な条件を提供し、また、解に対する$\theta_t$ の収束の \textit{rate} 上の有界性を証明する。
従来のSGDの場合,これらの結果は共用紙で証明された結果に還元される。
そして、これらの結果を、雑音測定のみによる写像の定点を求める問題に適用する。
この問題はRLで頻繁に発生する。
我々は収束率と収束率の推定に十分な条件を証明している。
関連論文リスト
- Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - Convergence Analysis of Decentralized ASGD [1.8710230264817358]
本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。
我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
論文 参考訳（メタデータ） (2023-09-07T14:50:31Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Topology-aware Generalization of Decentralized SGD [89.25765221779288]
本稿では,分散型Valpha-10安定降下(D-SGD)の一般化可能性について検討する。
D-SGDの一般化性は、初期訓練段階における接続性と正の相関があることを証明した。
論文 参考訳（メタデータ） (2022-06-25T16:03:48Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
この論文は$d$-dimensional recursion approximation, $$theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1)に関するものである。
主な結果は、ドスカー・バラダン・リャプノフドリフト条件(DV3)の平均流とバージョンに関する追加条件の下で確立される。
a example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometryal.
論文 参考訳（メタデータ） (2021-10-27T13:38:25Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。