論文の概要: Streaming Linear System Identification with Reverse Experience Replay

• arxiv url: http://arxiv.org/abs/2103.05896v1
• Date: Wed, 10 Mar 2021 06:51:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-11 15:00:59.296997
• Title: Streaming Linear System Identification with Reverse Experience Replay
• Title（参考訳）: リバースエクスペリエンスリプレイを用いたストリーミング線形システム同定
• Authors: Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, Praneeth Netrapalli
• Abstract要約: 本稿では,線形時間不変(LTI)力学系を,ストリーミングアルゴリズムによる単一軌道から推定する問題を考察する。 強化学習(RL)で遭遇する多くの問題において、勾配オラクルを用いて囲碁上のパラメータを推定することが重要である。 本稿では,RL文学で人気のある経験リプレイ(ER)技術に触発された小説SGD with Reverse Experience Replay (SGD-RER)を提案する。
• 参考スコア（独自算出の注目度）: 45.17023170054112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of estimating a stochastic linear time-invariant (LTI) dynamical system from a single trajectory via streaming algorithms. The problem is equivalent to estimating the parameters of vector auto-regressive (VAR) models encountered in time series analysis (Hamilton (2020)). A recent sequence of papers (Faradonbeh et al., 2018; Simchowitz et al., 2018; Sarkar and Rakhlin, 2019) show that ordinary least squares (OLS) regression can be used to provide optimal finite time estimator for the problem. However, such techniques apply for offline setting where the optimal solution of OLS is available apriori. But, in many problems of interest as encountered in reinforcement learning (RL), it is important to estimate the parameters on the go using gradient oracle. This task is challenging since standard methods like SGD might not perform well when using stochastic gradients from correlated data points (Gy\"orfi and Walk, 1996; Nagaraj et al., 2020). In this work, we propose a novel algorithm, SGD with Reverse Experience Replay (SGD-RER), that is inspired by the experience replay (ER) technique popular in the RL literature (Lin, 1992). SGD-RER divides data into small buffers and runs SGD backwards on the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error for standard problem settings. Thus, we provide the first - to the best of our knowledge - optimal SGD-style algorithm for the classical problem of linear system identification aka VAR model estimation. Our work demonstrates that knowledge of dependency structure can aid us in designing algorithms which can deconstruct the dependencies between samples optimally in an online fashion.
• Abstract（参考訳）: ストリームアルゴリズムによる1つの軌道から確率的線形時間不変量(lti)力学系を推定する問題を考える。 この問題は、時系列解析で遭遇するベクトル自己回帰(VAR)モデルのパラメータを推定することと同等である(Hamilton (2020))。 最近の論文(Faradonbeh et al., 2018; Simchowitz et al., 2018; Sarkar and Rakhlin, 2019)では、通常の最小正方形(OLS)回帰を使用して、問題の最適な有限時間推定値を提供することができる。 しかし、このような手法はolsの最適なソリューションが利用可能なオフライン設定に適用できる。 しかし、強化学習(RL)で遭遇する多くの問題において、勾配オラクルを用いて囲碁上のパラメータを推定することが重要である。 Gy\orfi and Walk, 1996, Nagaraj et al., 2020) の相関データ点から確率勾配を用いる場合, SGD のような標準的な手法ではうまく機能しないため, この課題は困難である。 本研究では、RL文学(Lin, 1992)で普及した経験再生(ER)技術にインスパイアされた新しいアルゴリズムであるSGD with Reverse Experience Replay(SGD-RER)を提案する。 SGD-RERはデータを小さなバッファに分割し、個々のバッファに格納されたデータに対してSGDを後方に実行する。 このアルゴリズムは依存構造を正確に分解し、標準問題設定におけるパラメータ誤差と予測誤差の両方について理論的に最適な保証を得る。 したがって、線形システム同定の古典的問題であるVARモデル推定に対して、私たちの知る限り、最適なSGDスタイルのアルゴリズムを初めて提供する。 我々の研究は、オンライン手法でサンプル間の依存関係を最適に分解できるアルゴリズムの設計に、依存関係構造に関する知識が役立つことを示す。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  モンテカルロシミュレーションによる政策評価は多くのMC強化学習(RL)アルゴリズムの中核にある。 本研究では,異なる長さの軌跡を用いた回帰推定器の平均二乗誤差のサロゲートとして品質指標を提案する。 本稿では,Robust and Iterative Data Collection Strategy Optimization (RIDO) という適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-17T11:47:56Z)
• Statistical Learning and Inverse Problems: An Stochastic Gradient Approach [0.0]
  逆問題は科学と工学において最重要である。 本稿では,統計的逆問題 (SIP) のセットアップについて考察し,線形SIP設定においてグラディエント・ディフレッシュ (SGD) アルゴリズムをどのように利用できるかを示す。
  論文  参考訳（メタデータ） (2022-09-29T17:42:01Z)
• One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares [8.443742714362521]
  我々は,従来のデータポイントの予測にほとんど変化しない方向にパラメータを変更しながら,すべての新しいデータポイントに完全に適合するワンパス学習アルゴリズムを開発した。 我々のアルゴリズムは、インクリメンタル・プリンシパル・コンポーネント分析(IPCA)を用いてストリーミングデータの構造を利用して、メモリを効率的に利用する。 本実験では,提案手法の有効性をベースラインと比較した。
  論文  参考訳（メタデータ） (2022-07-28T02:01:31Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Robust Regression Revisited: Acceleration and Improved Estimation Rates [25.54653340884806]
  強い汚染モデルの下で, 統計的回帰問題に対する高速アルゴリズムについて検討する。 目的は、逆向きに破損したサンプルを与えられた一般化線形モデル(GLM)を概ね最適化することである。 実行時や推定保証が改善された頑健な回帰問題に対して,ほぼ直線的な時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T17:21:56Z)
• A spectral algorithm for robust regression with subgaussian rates [0.0]
  本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。 目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
  論文  参考訳（メタデータ） (2020-07-12T19:33:50Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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