論文の概要: Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems

• arxiv url: http://arxiv.org/abs/2105.11558v1
• Date: Mon, 24 May 2021 22:14:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-26 14:21:54.773137
• Title: Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Title（参考訳）: 非線形力学系学習のための近最適オフライン・ストリーミングアルゴリズム
• Authors: Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, Praneeth Netrapalli
• Abstract要約: X_t+1 = phi(A* X_t) + eta_t$, where $eta_t$ is unbiased noise and $phi : mathbbR to mathbbR$ is a known link function that certain em expansivity properties。
• 参考スコア（独自算出の注目度）: 45.17023170054112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the setting of vector valued non-linear dynamical systems $X_{t+1} = \phi(A^* X_t) + \eta_t$, where $\eta_t$ is unbiased noise and $\phi : \mathbb{R} \to \mathbb{R}$ is a known link function that satisfies certain {\em expansivity property}. The goal is to learn $A^*$ from a single trajectory $X_1,\cdots,X_T$ of {\em dependent or correlated} samples. While the problem is well-studied in the linear case, where $\phi$ is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay ($\mathsf{SGD-RER}$) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU link function -- a non-expansive but easy to learn link function with i.i.d. samples -- any method would require exponentially many samples (with respect to dimension of $X_t$) from the dynamical system. We validate our results via. simulations and demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized methods designed for the dependency structure in data can significantly outperform standard SGD based methods.
• Abstract（参考訳）: ベクトル値の非線形力学系 $x_{t+1} = \phi(a^* x_t) + \eta_t$, ここで、$\eta_t$ は偏りのないノイズであり、$\phi : \mathbb{r} \to \mathbb{r}$ はある拡張性を満たす既知のリンク関数である。 目標は、1つの軌道から$A^*$を学習することであり、$X_1,\cdots,X_T$ of {\em dependent or correlation} sampleである。 この問題は、$\phi$ が同一であり、非混合系においても最適な誤差率を持つ線形の場合においてよく研究されているが、非線形の場合の既存の結果は混合系でのみ成り立つ。 In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay ($\mathsf{SGD-RER}$) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU link function -- a non-expansive but easy to learn link function with i.i.d. サンプル -- どのメソッドも動的システムから指数関数的に多くのサンプル(x_t$の次元で)を必要とします。 私たちは結果を検証します。 シミュレーションと、SGDの単純適用が極めて準最適であることを示す。 実際、我々の研究は相関データの場合、データ内の依存構造のために設計された特殊なメソッドが標準のsgdベースのメソッドを大幅に上回ることを示している。

関連論文リスト

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  連続状態と行動空間を持つ非線形力学系に対するオンライン強化学習のサンプル複雑性について検討した。 我々のアルゴリズムは、その単純さ、事前知識を組み込む能力、そして良心的な過渡的行動のために、実際に有用である可能性が高い。
  論文  参考訳（メタデータ） (2025-01-27T10:01:28Z)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
  オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。 我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-19T19:53:58Z)
• Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks [22.20726152012564]
  本稿では,2種類の状態を持つシステムに関わる強化学習問題のクラスについて考察する。 拡張データサンプルを生成することで学習を高速化するサンプル効率のよい手法を提案する。
  論文  参考訳（メタデータ） (2023-05-25T21:29:11Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  我々は、既存のアルゴリズムが適用できないXリスクのファミリーを最適化するために、新しい連邦学習(FL)問題に取り組む。 Xリスクに対するFLアルゴリズムを設計する際の課題は、複数のマシンに対する目的の非可逆性と、異なるマシン間の相互依存にある。
  論文  参考訳（メタデータ） (2022-10-26T00:23:36Z)
• Learning Mixtures of Linear Dynamical Systems [94.49754087817931]
  そこで我々は,2段階のメタアルゴリズムを開発し,各基底構造LPSモデルを誤り$tildeO(sqrtd/T)$.sqrtd/T)まで効率的に復元する。 提案手法の有効性を検証し,数値実験による理論的研究を検証する。
  論文  参考訳（メタデータ） (2022-01-26T22:26:01Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。 最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-30T10:42:48Z)
• Using Deep Learning to Improve Ensemble Smoother: Applications to Subsurface Characterization [2.4373900721120285]
  エンサンブルスムース(ES)は様々な研究分野で広く使われている。 ES$_text(DL)$は、複雑なデータ同化アプリケーションにおけるESの更新スキームである。 DLに基づくES法,すなわちES$_text(DL)$はより汎用的で柔軟であることを示す。
  論文  参考訳（メタデータ） (2020-02-21T02:46:53Z)
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
  本研究では,1つの有限軌跡から得られた標本からシステム力学を学習するための勾配に基づくアルゴリズムについて検討する。 既存の作業とは異なり、我々の限界はノイズに敏感で、精度が高く、サンプルの複雑さも小さい。
  論文  参考訳（メタデータ） (2020-02-20T02:36:44Z)

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

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