論文の概要: Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction
- arxiv url: http://arxiv.org/abs/2511.12467v1
- Date: Sun, 16 Nov 2025 05:49:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-18 14:36:24.185027
- Title: Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction
- Title（参考訳）: オンライン多段階予測における対数回帰と多項式スケーリング
- Authors: Jiachen Qian, Yang Zheng,
- Abstract要約: 未知の線形システムに対するオンラインマルチステップ予測の問題について検討する。
条件分布理論を用いて、予測ポリシーの最適パラメータ化を将来の入力、過去の入力、過去の出力の線形関数として導出する。
多段階設定における最適カルマンフィルタに対して,オンラインアルゴリズムが対数後悔を実現することを示す。
- 参考スコア（独自算出の注目度）: 4.42171635795004
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This letter studies the problem of online multi-step-ahead prediction for unknown linear stochastic systems. Using conditional distribution theory, we derive an optimal parameterization of the prediction policy as a linear function of future inputs, past inputs, and past outputs. Based on this characterization, we propose an online least-squares algorithm to learn the policy and analyze its regret relative to the optimal model-based predictor. We show that the online algorithm achieves logarithmic regret with respect to the optimal Kalman filter in the multi-step setting. Furthermore, with new proof techniques, we establish an almost-sure regret bound that does not rely on fixed failure probabilities for sufficiently large horizons $N$. Finally, our analysis also reveals that, while the regret remains logarithmic in $N$, its constant factor grows polynomially with the prediction horizon $H$, with the polynomial order set by the largest Jordan block of eigenvalue 1 in the system matrix.
- Abstract（参考訳）: 本稿では,未知の線形確率系のオンラインマルチステップ予測問題について検討する。
条件分布理論を用いて、予測ポリシーの最適パラメータ化を将来の入力、過去の入力、過去の出力の線形関数として導出する。
この特徴から, 最適モデルベース予測器に対して, ポリシーを学習し, その後悔を解析するオンライン最小二乗アルゴリズムを提案する。
多段階設定における最適カルマンフィルタに対して,オンラインアルゴリズムが対数後悔を実現することを示す。
さらに、新しい証明手法により、十分に大きな地平線に対して固定された失敗確率に依存しないほぼ確実に後悔する境界を樹立する。
最後に、我々の分析は、後悔は$N$で対数的であるが、その定数係数は予測水平線$H$で多項式的に増大し、多項式次数は系行列の中で最大の固有値 1 のジョーダンブロックによって設定されることを示した。
関連論文リスト
- A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。
提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-31T05:02:33Z) - Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。
GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。
本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-16T02:24:21Z) - Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation [0.46040036610482665]
我々は, 与えられた測定行列の列の線形結合の観点から, 測定列の最良のスパース近似を予測できるような, テキストトンラインスパース線形近似の問題を考察する。
本稿では、このオンライン問題に対処するための効率的なオンラインメタ政治であるFollow-The-Approximate-Sparse-Leaderを提案する。
論文 参考訳（メタデータ） (2025-01-01T10:50:35Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳（メタデータ） (2021-10-24T22:43:15Z) - Online Learning of the Kalman Filter with Logarithmic Regret [2.0305676256390934]
高い確率で$mathrmpolylog(N)$の順序を後悔することは可能であり、$N$は収集された観測数である。
これは、将来の観測と過去の観測との概ね線形関係を利用するオンラインの最小二乗アルゴリズムを用いて達成される。
論文 参考訳（メタデータ） (2020-02-12T18:31:31Z) - No-Regret Prediction in Marginally Stable Systems [37.178095559618654]
本稿では,線形力学系におけるオンライン予測の問題点について考察する。
本手法を自己回帰フィルタの学習に適用することにより,部分的に観察された条件下での対数的後悔も達成できる。
論文 参考訳（メタデータ） (2020-02-06T01:53:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。