論文の概要: Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling

• arxiv url: http://arxiv.org/abs/2402.11800v3
• Date: Wed, 27 Mar 2024 15:48:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-28 22:03:50.948076
• Title: Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling
• Title（参考訳）: 遅延更新による確率近似:マルコフサンプリングにおける有限時間率
• Authors: Arman Adibi, Nicolo Dal Fabbro, Luca Schenato, Sanjeev Kulkarni, H. Vincent Poor, George J. Pappas, Hamed Hassani, Aritra Mitra,
• Abstract要約: マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
• 参考スコア（独自算出の注目度）: 73.5602474095954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by applications in large-scale and multi-agent reinforcement learning, we study the non-asymptotic performance of stochastic approximation (SA) schemes with delayed updates under Markovian sampling. While the effect of delays has been extensively studied for optimization, the manner in which they interact with the underlying Markov process to shape the finite-time performance of SA remains poorly understood. In this context, our first main contribution is to show that under time-varying bounded delays, the delayed SA update rule guarantees exponentially fast convergence of the \emph{last iterate} to a ball around the SA operator's fixed point. Notably, our bound is \emph{tight} in its dependence on both the maximum delay $\tau_{max}$, and the mixing time $\tau_{mix}$. To achieve this tight bound, we develop a novel inductive proof technique that, unlike various existing delayed-optimization analyses, relies on establishing uniform boundedness of the iterates. As such, our proof may be of independent interest. Next, to mitigate the impact of the maximum delay on the convergence rate, we provide the first finite-time analysis of a delay-adaptive SA scheme under Markovian sampling. In particular, we show that the exponent of convergence of this scheme gets scaled down by $\tau_{avg}$, as opposed to $\tau_{max}$ for the vanilla delayed SA rule; here, $\tau_{avg}$ denotes the average delay across all iterations. Moreover, the adaptive scheme requires no prior knowledge of the delay sequence for step-size tuning. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms, including TD learning, Q-learning, and stochastic gradient descent under Markovian sampling.
• Abstract（参考訳）: 大規模・マルチエージェント強化学習の応用により,マルコフサンプリング下での遅延更新を伴う確率近似(SA)スキームの漸近的性能について検討した。 遅延の影響は最適化のために広く研究されているが、それらが基礎となるマルコフ過程と相互作用し、SAの有限時間性能を形成する方法はまだよく分かっていない。 この文脈において、我々の最初の主な貢献は、時間変化した有界遅延の下で、遅延SA更新規則は、SA演算子の固定点の周囲の球に \emph{last iterate} が指数関数的に高速収束することを保証していることを示すことである。 特に、我々の境界は最大遅延$\tau_{max}$と混合時間$\tau_{mix}$の両方に依存して \emph{tight} となる。 この厳密な境界を達成するために、既存の様々な遅延最適化解析とは異なり、イテレートの均一な有界性を確立することに依存する新しい帰納的証明手法を開発した。 したがって、我々の証明は独立した関心を持つかもしれない。 次に、最大遅延が収束率に与える影響を軽減するために、マルコフサンプリングの下での遅延適応型SAスキームの最初の有限時間解析を行う。 特に、このスキームの収束指数は、バニラ遅延SA則に対する$\tau_{max}$とは対照的に、$\tau_{avg}$でスケールダウンする。 さらに、適応型スキームはステップサイズチューニングのための遅延シーケンスの事前知識を必要としない。 理論的には, マルコフサンプリング下でのTD学習, Q-ラーニング, 確率勾配降下を含む, 幅広いアルゴリズムの遅延の有限時間効果に光を当てた。

関連論文リスト

• Tree Search-Based Policy Optimization under Stochastic Execution Delay [46.849634120584646]
  遅延実行 MDP は、状態拡張に頼ることなく、ランダムな遅延に対処する新しい形式である。 観測された遅延値から、マルコフポリシーのクラスでポリシー探索を行うのに十分であることを示す。 我々はマルコフポリシーのクラスを最適化するモデルベースのアルゴリズムであるDEZを考案した。
  論文  参考訳（メタデータ） (2024-04-08T12:19:04Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
  論文  参考訳（メタデータ） (2024-03-25T22:49:56Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。 我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。 遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
  論文  参考訳（メタデータ） (2023-10-29T06:12:43Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。 既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。 我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
  論文  参考訳（メタデータ） (2023-08-18T10:00:27Z)
• Min-Max Optimization under Delays [26.830212508878162]
  大規模な機械学習問題では遅延と非同期は避けられない。 min-max最適化に類似した理論は存在しない。 たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
  論文  参考訳（メタデータ） (2023-07-13T16:39:01Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)

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

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