論文の概要: Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning

• arxiv url: http://arxiv.org/abs/2008.10103v1
• Date: Sun, 23 Aug 2020 20:36:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-26 02:53:48.555583
• Title: Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Title（参考訳）: 平滑な非線形TD学習のための単一時間確率非凸凹最適化
• Authors: Shuang Qiu, Zhuoran Yang, Xiaohan Wei, Jieping Ye, Zhaoran Wang
• Abstract要約: 本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
• 参考スコア（独自算出の注目度）: 145.54544979467872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Temporal-Difference (TD) learning with nonlinear smooth function approximation for policy evaluation has achieved great success in modern reinforcement learning. It is shown that such a problem can be reformulated as a stochastic nonconvex-strongly-concave optimization problem, which is challenging as naive stochastic gradient descent-ascent algorithm suffers from slow convergence. Existing approaches for this problem are based on two-timescale or double-loop stochastic gradient algorithms, which may also require sampling large-batch data. However, in practice, a single-timescale single-loop stochastic algorithm is preferred due to its simplicity and also because its step-size is easier to tune. In this paper, we propose two single-timescale single-loop algorithms which require only one data point each step. Our first algorithm implements momentum updates on both primal and dual variables achieving an $O(\varepsilon^{-4})$ sample complexity, which shows the important role of momentum in obtaining a single-timescale algorithm. Our second algorithm improves upon the first one by applying variance reduction on top of momentum, which matches the best known $O(\varepsilon^{-3})$ sample complexity in existing works. Furthermore, our variance-reduction algorithm does not require a large-batch checkpoint. Moreover, our theoretical results for both algorithms are expressed in a tighter form of simultaneous primal and dual side convergence.
• Abstract（参考訳）: 非線形滑らか関数近似を用いたtd学習は,近年の強化学習において大きな成功を収めている。 このような問題を確率的非凸・強凹最適化問題として再定式化できることが示されているが、これはナイーブな確率的勾配降下・上昇アルゴリズムが収束の遅い問題である。 この問題に対する既存のアプローチは、2時間スケールまたはダブルループの確率的勾配アルゴリズムに基づいている。 しかし、実際には、その単純さとステップサイズが調整しやすいため、シングルタイムスケールのシングルループ確率アルゴリズムが好まれる。 本稿では,各ステップごとに1つのデータポイントしか必要としない2つのシングルタイムスケールシングルループアルゴリズムを提案する。 我々の最初のアルゴリズムは、プリマル変数と双対変数の両方の運動量更新を実装し、O(\varepsilon^{-4})$サンプル複雑性を実現し、単一時間スケールのアルゴリズムを得る上での運動量の役割を示す。 第2のアルゴリズムは,既存の作業における最もよく知られた$o(\varepsilon^{-3})$サンプル複雑性と一致する運動量上に分散還元を適用することで,第1のアルゴリズムを改善する。 さらに,本アルゴリズムでは大きなバッチチェックポイントを必要としない。 さらに, 両アルゴリズムの理論的結果は, 同時一次および二重側収束のより厳密な形式で表される。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。 我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。 さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
  論文  参考訳（メタデータ） (2023-06-28T00:46:58Z)
• Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression [15.389011827844572]
  重み付き雑音や客観的腐敗の下での高テール線形回帰は、どちらも統計的に困難である。 本稿では,ノイズガウスあるいは重度1+エプシロン回帰問題に対するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T14:31:03Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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