論文の概要: The Power of Second Order Methods for Sequence Preconditioning

• arxiv url: http://arxiv.org/abs/2605.08390v1
• Date: Fri, 08 May 2026 18:56:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:49.609134
• Title: The Power of Second Order Methods for Sequence Preconditioning
• Title（参考訳）: シーケンスプレコンディショニングにおける第2次手法のパワー
• Authors: Annie Marsden, Elad Hazan,
• Abstract要約: 本稿では,Vovk-Azoury-Warmuth (VAW) アルゴリズムが,Universal Sequence Preconditioning (USP) 方式と自然に一致することを示す。 VAWとUSPを組み合わせることで、非対称な非対称な遷移行列が存在する場合でも、ポリ対数的後悔$O left( log3 Tright)$を達成できることを示す。 我々は、チェビシェフに新しい複素解析的境界を提供することにより、有界スペクトルシステムを超えてUSPの適用性を拡張する。
• 参考スコア（独自算出の注目度）: 15.021303911702121
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sequence prediction methods for dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows polynomially with the hidden dimension of the underlying generative model. Universal Sequence Preconditioning (USP) is a method that compresses any sequence which comes from a linear dynamical system into a "preconditioned" sequence which requires exponentially shorter memory for accurate prediction. However, the preconditioned sequence yields exponentially larger diameters and gradients, hindering USP from unlocking optimal regret bounds. Inspired by the minimum description length principle, we show that the Vovk-Azoury-Warmuth (VAW) algorithm is naturally matched to the USP regime. Indeed, it takes advantage of the memory compression while remaining robust to the exponential explosion of the diameter. We prove that combining USP with VAW achieves astoundingly strong results: for any marginally-stable linear dynamical system, this algorithm achieves polylogarithmic regret $O \left( \log^3 T \right)$ even in the presence of asymmetric hidden transition matrices. Finally, we extend the applicability of USP beyond bounded-spectrum systems by providing new complex-analytic bounds on Chebyshev polynomials, allowing for systems with constant complex arguments.
• Abstract（参考訳）: 長い記憶を持つ力学系の系列予測法、すなわち、極端に安定な系は、一般に、基礎となる生成モデルの隠れ次元と多項式的に成長する後悔を達成する。 ユニバーサルシーケンスプレコンディショニング(Universal Sequence Preconditioning、USP)とは、線形力学系から生じる任意のシーケンスを「プリコンディショニング」シーケンスに圧縮する手法である。 しかし、プレコンディショニングされたシーケンスは指数関数的に大きな直径と勾配をもたらし、USPが最適な後悔境界を解き放つのを妨げている。 最小記述長原理に着想を得て, Vovk-Azoury-Warmuth (VAW) アルゴリズムがUSP方式と自然に一致することを示す。 実際、直径の指数的爆発に対して頑健でありながら、メモリ圧縮を利用する。 我々は、USP と VAW を組み合わせることで驚くべきほど強い結果が得られることを証明した:任意の辺りが安定な線形力学系に対して、このアルゴリズムは非対称な非対称な遷移行列が存在する場合でも、多対数的後悔$O \left( \log^3 T \right)$を達成する。 最後に、チェビシェフ多項式上の新しい複素解析的境界を提供することにより、有界スペクトル系を超えてUSPの適用性を拡張し、一定の複素引数を持つ系が可能である。

関連論文リスト

• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  我々はこの緊張を解決するためにPRISM(Parallel Residual Iterative Sequence Model)を提案する。 PRISMは、パラレル化可能な形で多段階精製の重要な構造特性を捉える、ソルバに着想を得た帰納バイアスを導入している。 この定式化が Rank-$L$ の蓄積を達成することを証明し、更新多様体を単一ステップの Rank-$1$ ボトルネックを超えて構造的に拡張する。
  論文  参考訳（メタデータ） (2026-02-11T12:39:41Z)
• Universal Sequence Preconditioning [15.021303911702121]
  逐次予測におけるプレコンディショニングの問題について検討する。 対象シーケンスを畳むと、隠れた遷移行列のレンズを適用することが示される。 我々は,この手法が予測アルゴリズムの後悔を軽減することを証明した。
  論文  参考訳（メタデータ） (2025-02-10T15:10:06Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  連続状態と行動空間を持つ非線形力学系の一般設定におけるオンライン強化学習のサンプル複雑性について検討した。 我々のアルゴリズムは、$mathcalO(N epsilon2 + Mathrmln(m(epsilon)/epsilon2)$のポリシーを後悔する。 力学がコンパクトで実数値のパラメータ集合によってパラメータ化される特別な場合、$mathcalO(sqrt)のポリシー後悔を証明する。
  論文  参考訳（メタデータ） (2025-01-27T10:01:28Z)
• Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
  本稿では,STT-MPC (Self-Tuning tube-based Model Predictive Control) について述べる。 システム力学を最初に認識したアルゴリズムと比較して,アルゴリズムの後悔を解析する。
  論文  参考訳（メタデータ） (2023-10-07T15:07:10Z)
• A relaxed proximal gradient descent algorithm for convergent plug-and-play with proximal denoiser [6.2484576862659065]
  本稿では,新しいコンバーゼントなPlug-and-fidelity Descent (Play)アルゴリズムを提案する。 このアルゴリズムは、より広い範囲の通常の凸化パラメータに収束し、画像のより正確な復元を可能にする。
  論文  参考訳（メタデータ） (2023-01-31T16:11:47Z)
• DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention [53.02648818164273]
  動的双線形低ランク注意(DBA)という,効率的かつ効果的な注意機構を提案する。 DBAは入力感度の動的射影行列によってシーケンス長を圧縮し、線形時間と空間の複雑さを実現する。 様々なシーケンス長条件のタスクに対する実験は、DBAが最先端のパフォーマンスを達成することを示す。
  論文  参考訳（メタデータ） (2022-11-24T03:06:36Z)
• No-Regret Prediction in Marginally Stable Systems [37.178095559618654]
  本稿では,線形力学系におけるオンライン予測の問題点について考察する。 本手法を自己回帰フィルタの学習に適用することにより,部分的に観察された条件下での対数的後悔も達成できる。
  論文  参考訳（メタデータ） (2020-02-06T01:53:34Z)

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

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