論文の概要: A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using $L$-$\lambda$ Smoothness

• arxiv url: http://arxiv.org/abs/2307.15892v2
• Date: Sat, 2 Sep 2023 16:54:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 03:55:18.967161
• Title: A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using $L$-$\lambda$ Smoothness
• Title（参考訳）: 1ステップサイズしか持たない新しい勾配TDアルゴリズム:$L$-$\lambda$Smoothnessを用いた収束速度解析
• Authors: Hengshuai Yao
• Abstract要約: 本稿では,期待されたtd更新のノーム(NEU)目標を最小化する,真のシングルタイムスケールのGTDアルゴリズムを提案する。 我々は、Impression GTDと呼ばれる新しいアルゴリズムが少なくとも$O(1/t)$として収束していることを証明する。 実証的な結果から、Impression GTDは既存のGTDアルゴリズムよりもはるかに高速に収束し、オン・ポリティカとオフ・ポリティカの両方の学習課題が解決された。
• 参考スコア（独自算出の注目度）: 6.429314569034207
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gradient Temporal Difference (GTD) algorithms (Sutton et al., 2008, 2009) are the first $O(d)$ ($d$ is the number features) algorithms that have convergence guarantees for off-policy learning with linear function approximation. Liu et al. (2015) and Dalal et. al. (2018) proved the convergence rates of GTD, GTD2 and TDC are $O(t^{-\alpha/2})$ for some $\alpha \in (0,1)$. This bound is tight (Dalal et al., 2020), and slower than $O(1/\sqrt{t})$. GTD algorithms also have two step-size parameters, which are difficult to tune. In literature, there is a "single-time-scale" formulation of GTD. However, this formulation still has two step-size parameters. This paper presents a truly single-time-scale GTD algorithm for minimizing the Norm of Expected td Update (NEU) objective, and it has only one step-size parameter. We prove that the new algorithm, called Impression GTD, converges at least as fast as $O(1/t)$. Furthermore, based on a generalization of the expected smoothness (Gower et al. 2019), called $L$-$\lambda$ smoothness, we are able to prove that the new GTD converges even faster, in fact, with a linear rate. Our rate actually also improves Gower et al.'s result with a tighter bound under a weaker assumption. Besides Impression GTD, we also prove the rates of three other GTD algorithms, one by Yao and Liu (2008), another called A-transpose-TD (Sutton et al., 2008), and a counterpart of A-transpose-TD. The convergence rates of all the four GTD algorithms are proved in a single generic GTD framework to which $L$-$\lambda$ smoothness applies. Empirical results on Random walks, Boyan chain, and Baird counterexample show that Impression GTD converges much faster than existing GTD algorithms for both on-policy and off-policy learning problems, with well-performing step-sizes in a big range.
• Abstract（参考訳）: gtd(gradient temporal difference)アルゴリズム(sutton et al., 2008, 2009)は、線形関数近似によるオフポリシー学習のための収束保証を持つ最初の$o(d)$(d$ is the number features)アルゴリズムである。 Liu et al. (2015) and Dalal et. al. (2018) は、GTD, GTD2 および TDC の収束率は、ある$\alpha \in (0,1)$に対して$O(t^{-\alpha/2})$であることを示した。 この境界はタイト(dalal et al., 2020)であり、$o(1/\sqrt{t})$よりも遅い。 GTDアルゴリズムには2つのステップサイズパラメータがあり、チューニングが難しい。 文献では、gtdの「シングルタイムスケール」な定式化がある。 しかし、この定式化はまだ2つのステップサイズパラメータを持つ。 本稿では,期待されたtd更新(NEU)目標のノルムを最小化するための,真に単一時間スケールのGTDアルゴリズムを提案する。 我々は、Impression GTDと呼ばれる新しいアルゴリズムが少なくとも$O(1/t)$の速さで収束していることを証明する。 さらに、期待される滑らかさの一般化(Gower et al. 2019)により、$L$-$\lambda$ smoothness と呼ばれる新しい GTD が線型速度でさらに速く収束することを証明することができる。 私たちのレートは、より弱い仮定の下でより厳密な境界で、Gowerらの結果も改善します。 印象 gtd の他に,yao と liu (2008) による他の 3 つの gtd アルゴリズム,a-transpose-td (sutton et al., 2008) と呼ばれるアルゴリズム,および a-transpose-td の対数も証明した。 4つのGTDアルゴリズムの収束速度は、1つのGTDフレームワークで証明され、そこでは$L$-$\lambda$滑らかさが適用される。 Random walk, Boyan chain, and Baird counterexample の実証結果は、Impression GTD が既存の GTD アルゴリズムよりもはるかに早く、オン・ポリティクスとオフ・ポリティクスの両方の学習問題に収束し、大きな範囲で優れたステップサイズを達成していることを示している。

関連論文リスト

• A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies [34.7582575446942]
  多次元スケーリング(MDS)は、低次元ユークリッド空間に$n$ポイントの計量を埋め込む方法のファミリーである。 準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
  論文  参考訳（メタデータ） (2023-11-29T17:42:05Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity [30.97847679999505]
  GDA(Gradient descent Ascent)は、GAN(Generative Adversarial Network)やGAN(Adversarial Network)といった実用用途で広く利用されている。 最近の研究は、一方のトレーニング結果に対する反復の理論において、GDAの収束率が劣っていることを示している。 本稿では, 1変数のpolyak-Lojasiewicz(PL)条件を満たすという軽微な仮定の下で, GDAと滑らかなGDAの交互化という2つの代替シングルループアルゴリズムを確立する。
  論文  参考訳（メタデータ） (2021-12-10T15:35:42Z)
• On the Last Iterate Convergence of Momentum Methods [32.60494006038902]
  我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。 凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
  論文  参考訳（メタデータ） (2021-02-13T21:16:16Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• 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)

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

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