論文の概要: Learning nonlinear dynamical systems from a single trajectory
- arxiv url: http://arxiv.org/abs/2004.14681v1
- Date: Thu, 30 Apr 2020 10:42:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 03:47:31.265322
- Title: Learning nonlinear dynamical systems from a single trajectory
- Title(参考訳): 単一軌道から非線形力学系の学習
- Authors: Dylan J. Foster, Alexander Rakhlin, Tuhin Sarkar
- Abstract要約: 我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 102.60042167341956
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce algorithms for learning nonlinear dynamical systems of the form
$x_{t+1}=\sigma(\Theta^{\star}x_t)+\varepsilon_t$, where $\Theta^{\star}$ is a
weight matrix, $\sigma$ is a nonlinear link function, and $\varepsilon_t$ is a
mean-zero noise process. We give an algorithm that recovers the weight matrix
$\Theta^{\star}$ from a single trajectory with optimal sample complexity and
linear running time. The algorithm succeeds under weaker statistical
assumptions than in previous work, and in particular i) does not require a
bound on the spectral norm of the weight matrix $\Theta^{\star}$ (rather, it
depends on a generalization of the spectral radius) and ii) enjoys guarantees
for non-strictly-increasing link functions such as the ReLU. Our analysis has
two key components: i) we give a general recipe whereby global stability for
nonlinear dynamical systems can be used to certify that the state-vector
covariance is well-conditioned, and ii) using these tools, we extend well-known
algorithms for efficiently learning generalized linear models to the dependent
setting.
- Abstract(参考訳): x_{t+1}=\sigma(\theta^{\star}x_t)+\varepsilon_t$, ここで$\theta^{\star}$は重み行列、$\sigma$は非線形リンク関数、$\varepsilon_t$は平均ゼロノイズ処理である。
最適なサンプル複雑性と線形実行時間を持つ単一軌道から重み行列$\Theta^{\star}$を復元するアルゴリズムを提案する。
このアルゴリズムは、以前の研究、特に、より弱い統計的仮定の下で成功する
i) 重み行列 $\Theta^{\star}$(あるいはスペクトル半径の一般化に依存する)のスペクトルノルムの束縛を必要とせず、
二 ReLU のような非制限増加リンク関数の保証を楽しむこと。
分析には2つの重要な要素があります
一 非線形力学系に対する大域的安定性を利用して、状態ベクトル共分散が十分に条件づけられていることを証明し、また、
二 このツールを用いて、一般化線形モデルを依存した設定に効率的に学習するためのよく知られたアルゴリズムを拡張する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳(メタデータ) (2023-07-13T08:46:19Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Near-optimal Offline and Streaming Algorithms for Learning Non-Linear
Dynamical Systems [45.17023170054112]
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。
論文 参考訳(メタデータ) (2021-05-24T22:14:26Z) - 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) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳(メタデータ) (2020-07-29T00:31:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
本研究では,1つの有限軌跡から得られた標本からシステム力学を学習するための勾配に基づくアルゴリズムについて検討する。
既存の作業とは異なり、我々の限界はノイズに敏感で、精度が高く、サンプルの複雑さも小さい。
論文 参考訳(メタデータ) (2020-02-20T02:36:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。