論文の概要: Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2109.03445v1
• Date: Wed, 8 Sep 2021 06:06:28 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-10 02:02:20.959876
• Title: Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning
• Title（参考訳）: バッチ非同期確率近似の収束と強化学習への応用
• Authors: Rajeeva L. Karandikar and M. Vidyasagar
• Abstract要約: 凸近似(英: convex approximation、SA)アルゴリズムは、 $mathbff(boldsymboltheta) = mathbf0$ ここで mathbff mathbbRdarrow mathbbRdarrow mathbbRd という形の方程式の解を求めるために広く用いられる確率的手法である。
• 参考スコア（独自算出の注目度）: 1.2640278589409006
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The stochastic approximation (SA) algorithm is a widely used probabilistic method for finding a solution to an equation of the form $\mathbf{f}(\boldsymbol{\theta}) = \mathbf{0}$ where $\mathbf{f} : \mathbb{R}^d \rightarrow \mathbb{R}^d$, when only noisy measurements of $\mathbf{f}(\cdot)$ are available. In the literature to date, one can make a distinction between "synchronous" updating, whereby the entire vector of the current guess $\boldsymbol{\theta}_t$ is updated at each time, and "asynchronous" updating, whereby ony one component of $\boldsymbol{\theta}_t$ is updated. In convex and nonconvex optimization, there is also the notion of "batch" updating, whereby some but not all components of $\boldsymbol{\theta}_t$ are updated at each time $t$. In addition, there is also a distinction between using a "local" clock versus a "global" clock. In the literature to date, convergence proofs when a local clock is used make the assumption that the measurement noise is an i.i.d\ sequence, an assumption that does not hold in Reinforcement Learning (RL). In this note, we provide a general theory of convergence for batch asymchronous stochastic approximation (BASA), that works whether the updates use a local clock or a global clock, for the case where the measurement noises form a martingale difference sequence. This is the most general result to date and encompasses all others.
• Abstract（参考訳）: 確率近似(英: stochastic approximation, sa)アルゴリズムは、大雑把な測定値である$\mathbf{f}(\boldsymbol{\theta}) = \mathbf{0}$ where $\mathbf{f} : \mathbb{r}^d \rightarrow \mathbb{r}^d$ の方程式に対する解を見つけるために広く用いられる確率的手法である。 これまでの文献では、現在の推定値$\boldsymbol{\theta}_t$の全ベクトルが更新される「同期」更新と、$\boldsymbol{\theta}_t$の1つのコンポーネントが更新される「同期」更新とを区別することができる。 convex と nonconvex の最適化では、"batch" の更新の概念もあり、$\boldsymbol{\theta}_t$ のすべてのコンポーネントが $t$ のたびに更新されるわけではない。 さらに、"ローカル"クロックと"グローバル"クロックの区別もある。 これまでの文献では、局所クロックを使用する場合の収束証明は、測定ノイズがi.i.d\シーケンスであると仮定しており、これは強化学習(rl)では持たない仮定である。 本稿では,観測ノイズがマルティンゲール差分列を形成する場合において,更新が局所クロックか大域クロックかに関わらず動作するバッチ漸近確率近似 (basa) の収束の一般理論を提案する。 これは今まででもっとも一般的な結果であり、他の全てを包含している。

関連論文リスト

• 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)

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

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