論文の概要: Dimension-free Regret for Learning Asymmetric Linear Dynamical Systems
- arxiv url: http://arxiv.org/abs/2502.06545v1
- Date: Mon, 10 Feb 2025 15:10:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:35:02.734478
- Title: Dimension-free Regret for Learning Asymmetric Linear Dynamical Systems
- Title(参考訳): 非対称線形力学系学習のための次元自由回帰法
- Authors: Annie Marsden, Elad Hazan,
- Abstract要約: 本稿では,行列の存在にもかかわらず,トレードオフのない非次元的後悔を克服する新しい手法を提案する。
本手法では,スペクトルフィルタリングと線形予測器を併用し,複素平面にチェビシェフを用いて新しいスペクトルフィルタリング基盤を構築する。
遷移行列が1/mathrmpoly log$で有界な複素成分を持つ固有値を持つ限り、我々の手法は後見の最良の線形予測子と比較して、後悔の$tildeO(9/10)$を達成できる。
- 参考スコア(独自算出の注目度): 19.415741153449265
- License:
- Abstract: Previously, methods for learning marginally stable linear dynamical systems either required the transition matrix to be symmetric or incurred regret bounds that scale polynomially with the system's hidden dimension. In this work, we introduce a novel method that overcomes this trade-off, achieving dimension-free regret despite the presence of asymmetric matrices and marginal stability. Our method combines spectral filtering with linear predictors and employs Chebyshev polynomials in the complex plane to construct a novel spectral filtering basis. This construction guarantees sublinear regret in an online learning framework, without relying on any statistical or generative assumptions. Specifically, we prove that as long as the transition matrix has eigenvalues with complex component bounded by $1/\mathrm{poly} \log T$, then our method achieves regret $\tilde{O}(T^{9/10})$ when compared to the best linear dynamical predictor in hindsight.
- Abstract(参考訳): それまでは、境界的に安定な線形力学系を学習するためには、遷移行列が対称的であるか、システムの隠れ次元と多項式的にスケールする帰納的後悔境界が必要である。
本研究では,非対称行列の存在と限界安定性にもかかわらず,このトレードオフを克服し,無次元後悔を実現する新しい手法を提案する。
スペクトルフィルタリングを線形予測器と組み合わせ、複素平面にチェビシェフ多項式を用いて新しいスペクトルフィルタリング基盤を構築する。
この構成は、統計的または生成的仮定に頼ることなく、オンライン学習フレームワークにおけるサブリニアな後悔を保証する。
具体的には、遷移行列が複素成分が 1/\mathrm{poly} \log T$ で有界な固有値を持つ限り、我々の手法は、後向きの最良の線形動的予測子と比較して、後悔の$\tilde{O}(T^{9/10})$を達成する。
関連論文リスト
- The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
連続状態と行動空間を持つ非線形力学系に対するオンライン強化学習のサンプル複雑性について検討した。
我々のアルゴリズムは、その単純さ、事前知識を組み込む能力、そして良心的な過渡的行動のために、実際に有用である可能性が高い。
論文 参考訳(メタデータ) (2025-01-27T10:01:28Z) - Asymmetric matrix sensing by gradient descent with small random
initialization [0.8611782340880084]
いくつかの線形測定値から低ランク行列を再構成する問題について検討する。
私たちの重要な貢献は、$texted gradient flow$と呼ぶ連続的な勾配流方程式の導入です。
論文 参考訳(メタデータ) (2023-09-04T20:23:35Z) - Implicit Balancing and Regularization: Generalization and Convergence
Guarantees for Overparameterized Asymmetric Matrix Sensing [28.77440901439686]
最近の一連の論文は、非ランダムな正準決定(PSD)行列センシング問題に対して、この役割を一般化し始めている。
本稿では,小さなランダムな測定から得られる勾配降下の軌跡が,どちらも地球規模で良好である解へと移動することを示す。
論文 参考訳(メタデータ) (2023-03-24T19:05:52Z) - Oracle-Preserving Latent Flows [58.720142291102135]
我々はラベル付きデータセット全体にわたって複数の非自明な連続対称性を同時に発見するための方法論を開発する。
対称性変換と対応するジェネレータは、特別に構築された損失関数で訓練された完全連結ニューラルネットワークでモデル化される。
この研究における2つの新しい要素は、縮小次元の潜在空間の使用と、高次元のオラクルに関して不変な変換への一般化である。
論文 参考訳(メタデータ) (2023-02-02T00:13:32Z) - Online Stochastic Gradient Descent Learns Linear Dynamical Systems from
A Single Trajectory [1.52292571922932]
本研究では,システムを記述する未知の重み行列がブルノフスキー正則形式であれば,システムの未知の基底真理を効率的に推定できることを示した。
具体的には、具体的な境界を導出することにより、SGDは基底真理重みから任意の小さなフロベニウスノルム距離に期待して線型収束することを示す。
論文 参考訳(メタデータ) (2021-02-23T17:48:39Z) - Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric
Low-Rank Matrix Sensing [36.96922859748537]
低ランク行列推定は、科学と工学のさまざまなアプリケーションで中心的な役割を果たします。
既存のアプローチは、2つの行列因子のスケールのバランスをとるために計量正規化項を加えることに頼っている。
本論文では,低ランク行列の線形測定値の少ない値から回復する性能の理論的正当化について述べる。
論文 参考訳(メタデータ) (2021-01-13T15:03:52Z) - Sparse Quantized Spectral Clustering [85.77233010209368]
このような非線形変換の下で行列の固有スペクトルがどのように変化するのかを、ランダム行列理論のツールを用いて正確に述べる。
急激なスペーシング/量子化の下でも,情報的固有構造にはほとんど変化は見られなかった。
論文 参考訳(メタデータ) (2020-10-03T15:58:07Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z) - Eigendecomposition-Free Training of Deep Networks for Linear
Least-Square Problems [107.3868459697569]
我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。
この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。
我々の手法は収束特性が良く、最先端の結果が得られます。
論文 参考訳(メタデータ) (2020-04-15T04:29:34Z) - No-Regret Prediction in Marginally Stable Systems [37.178095559618654]
本稿では,線形力学系におけるオンライン予測の問題点について考察する。
本手法を自己回帰フィルタの学習に適用することにより,部分的に観察された条件下での対数的後悔も達成できる。
論文 参考訳(メタデータ) (2020-02-06T01:53:34Z) - Regret Minimization in Partially Observable Linear Quadratic Control [91.43582419264763]
モデル力学が未知の先行性を持つ場合、部分的に観測可能な線形二次制御系における後悔の問題を考察する。
本稿では, 部分的に観測可能な線形二次制御のために, 後悔を分解し, 終端から終端までの後悔の上限を与える新しい方法を提案する。
論文 参考訳(メタデータ) (2020-01-31T22:35:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。