論文の概要: Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2301.00944v3
- Date: Tue, 4 Jun 2024 15:40:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 14:46:08.047751
- Title: Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning
- Title(参考訳): 圧縮更新による時間差学習:Error-Feedbackによる強化学習
- Authors: Aritra Mitra, George J. Pappas, Hamed Hassani,
- Abstract要約: 本稿では,従来の時間差学習アルゴリズムの変種について検討する。
我々は、圧縮されたTDアルゴリズムと、最適化に広く用いられているエラーフィードバック機構が組み合わさって、漸近的でない近似を保証することを証明した。
特に、これらは一般圧縮演算子と線形関数近似とマルコフサンプリングを併用したタンデムの誤差フィードバックを考慮に入れたRLにおける最初の有限時間結果である。
- 参考スコア(独自算出の注目度): 47.904127007515925
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In large-scale distributed machine learning, recent works have studied the effects of compressing gradients in stochastic optimization to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? We investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our work makes three important technical contributions. First, we prove that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. Second, we show that our analysis framework extends seamlessly to nonlinear stochastic approximation schemes that subsume Q-learning. Third, we prove that for multi-agent TD learning, one can achieve linear convergence speedups with respect to the number of agents while communicating just $\tilde{O}(1)$ bits per iteration. Notably, these are the first finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our proofs hinge on the construction of novel Lyapunov functions that capture the dynamics of a memory variable introduced by error-feedback.
- Abstract(参考訳): 大規模分散機械学習において、近年の研究は、通信ボトルネックを軽減するための確率的最適化における勾配の圧縮の効果について研究している。
これらの研究により、確率勾配降下(SGD)は量子化、スパーシフィケーション、遅延などの構造的摂動に対して頑健であることが判明した。
おそらく意外なことに、マルチエージェント強化学習への関心が高まっているにもかかわらず、類似した質問についてはほとんど何も知られていない。
本稿では,従来の時間差(TD)学習アルゴリズムの変種を摂動更新方向で解析し,一般的な圧縮演算子を用いて摂動をモデル化する手法を提案する。
私たちの仕事は3つの重要な技術貢献をする。
まず、圧縮されたTDアルゴリズムと、最適化に広く用いられているエラーフィードバック機構が組み合わさって、SGDアルゴリズムと同じ非漸近的理論的保証を示すことを示す。
第2に、我々の分析フレームワークは、Q-ラーニングを仮定する非線形確率近似スキームにシームレスに拡張することを示す。
第三に、マルチエージェントのTD学習では、反復毎に$\tilde{O}(1)$ bitsと通信しながら、エージェント数に関して線形収束速度を達成できることが証明される。
特に、これらは一般圧縮演算子と線形関数近似とマルコフサンプリングを併用したタンデムの誤差フィードバックを考慮に入れたRLにおける最初の有限時間結果である。
我々の証明は、エラーフィードバックによって導入されたメモリ変数のダイナミクスを捉える新しいリアプノフ関数の構築に関するものである。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Understanding Augmentation-based Self-Supervised Representation Learning
via RKHS Approximation and Regression [53.15502562048627]
最近の研究は、自己教師付き学習とグラフラプラシアン作用素のトップ固有空間の近似との関係を構築している。
この研究は、増強に基づく事前訓練の統計的分析に発展する。
論文 参考訳(メタデータ) (2023-06-01T15:18:55Z) - Koopman Kernel Regression [6.116741319526748]
クープマン作用素理論は線形時間不変(LTI)ODEによる予測のキャラクタリゼーションに有効なパラダイムであることを示す。
我々は、LTI力学系への変換のみにまたがる、普遍的なクープマン不変核再生ヒルベルト空間(RKHS)を導出する。
実験では、Koopman演算子やシーケンシャルデータ予測器と比較して予測性能が優れていることを示した。
論文 参考訳(メタデータ) (2023-05-25T16:22:22Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳(メタデータ) (2022-06-01T23:26:51Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - Compressing gradients by exploiting temporal correlation in momentum-SGD [17.995905582226463]
エラーフィードバックのないシステムにおける時間相関を利用した圧縮手法を解析する。
ImageNetデータセットを用いた実験により,提案手法は通信速度を著しく低減することを示した。
我々は、最小勾配ノルムの有界性を確立することにより、予測誤差仮定の下でSGDの収束を証明した。
論文 参考訳(メタデータ) (2021-08-17T18:04:06Z) - A Stable High-order Tuner for General Convex Functions [0.0]
線形回帰問題に対して高次チューナー (HT) を開発した。
本稿では、一般凸損失関数に対する同じHTの結果を拡張し、議論する。
本稿では,HTアルゴリズムの満足な動作を支援する数値シミュレーションと,高速化学習特性について述べる。
論文 参考訳(メタデータ) (2020-11-19T17:50:53Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2020-05-05T18:08:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。