論文の概要: 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ベースのメソッドを大幅に上回ることを示している。

関連論文リスト

• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
  オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。 我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-19T19:53:58Z)
• Learning High-Dimensional Nonparametric Differential Equations via Multivariate Occupation Kernel Functions [0.31317409221921133]
  通常の微分方程式の非パラメトリック系を学ぶには、$d$変数の$d$関数を学ぶ必要がある。 明示的な定式化は、スパーシティや対称性といったシステム特性に関する追加の知識が得られない限り、$d$で2次的にスケールする。 本稿では,ベクトル値の再現Kernel Hilbert Spacesによる暗黙の定式化を用いた線形学習手法を提案する。
  論文  参考訳（メタデータ） (2023-06-16T21:49:36Z)
• 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)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• 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)
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
  本研究では,1つの有限軌跡から得られた標本からシステム力学を学習するための勾配に基づくアルゴリズムについて検討する。 既存の作業とは異なり、我々の限界はノイズに敏感で、精度が高く、サンプルの複雑さも小さい。
  論文  参考訳（メタデータ） (2020-02-20T02:36:44Z)

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

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