論文の概要: A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms

• arxiv url: http://arxiv.org/abs/2502.14208v1
• Date: Thu, 20 Feb 2025 02:39:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:28:48.643706
• Title: A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms
• Title（参考訳）: 半ノルムリアプノフ安定性の非漸近理論:決定論的から確率的反復アルゴリズムへ
• Authors: Zaiwei Chen, Sheng Zhang, Zhe Zhang, Shaan Ul Haque, Siva Theja Maguluri,
• Abstract要約: 半ノルム制約作用素に対する不動点方程式の解法について検討する。 決定論的および基礎的設定の両方において反復アルゴリズムの漸近的動作を確立する。
• 参考スコア（独自算出の注目度）: 15.764613607477887
• License:
• Abstract: We study the problem of solving fixed-point equations for seminorm-contractive operators and establish foundational results on the non-asymptotic behavior of iterative algorithms in both deterministic and stochastic settings. Specifically, in the deterministic setting, we prove a fixed-point theorem for seminorm-contractive operators, showing that iterates converge geometrically to the kernel of the seminorm. In the stochastic setting, we analyze the corresponding stochastic approximation (SA) algorithm under seminorm-contractive operators and Markovian noise, providing a finite-sample analysis for various stepsize choices. A benchmark for equation solving is linear systems of equations, where the convergence behavior of fixed-point iteration is closely tied to the stability of linear dynamical systems. In this special case, our results provide a complete characterization of system stability with respect to a seminorm, linking it to the solution of a Lyapunov equation in terms of positive semi-definite matrices. In the stochastic setting, we establish a finite-sample analysis for linear Markovian SA without requiring the Hurwitzness assumption. Our theoretical results offer a unified framework for deriving finite-sample bounds for various reinforcement learning algorithms in the average reward setting, including TD($\lambda$) for policy evaluation (which is a special case of solving a Poisson equation) and Q-learning for control.
• Abstract（参考訳）: 本研究では,半ノルム制約演算子に対する不動点方程式の解法について検討し,決定論的および確率的条件下での反復アルゴリズムの漸近的動作に関する基礎的結果を確立する。 具体的には、決定論的設定において、半ノルム-収縮作用素に対する不動点定理を証明し、反復が半ノルムの核に幾何学的に収束することを示す。 確率的設定では、半ノルム収縮作用素とマルコフ雑音の下で対応する確率近似 (SA) アルゴリズムを解析し、様々な段階選択に対して有限サンプル解析を行う。 方程式解のベンチマークは方程式の線形系であり、固定点反復の収束挙動は線形力学系の安定性と密接に結びついている。 この特別な場合、この結果は半ノルムに関する系の安定性の完全な特徴づけを提供し、正の半定値行列の観点でリアプノフ方程式の解にリンクする。 確率的設定では、Hurwitzness の仮定を必要とせず、線型マルコヴィアン SA に対する有限サンプル解析を確立する。 理論的な結果は、ポリシー評価のためのTD($\lambda$)や制御のためのQ学習など、様々な強化学習アルゴリズムの有限サンプル境界を平均的な報酬設定で導出するための統一的なフレームワークを提供する。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
  本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。 本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
  論文  参考訳（メタデータ） (2024-01-31T11:42:46Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。 提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
  論文  参考訳（メタデータ） (2022-10-23T23:23:23Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming [17.9230793188835]
  客観的・決定論的等式と不等式制約を用いた非線形最適化問題について検討する。 本稿では,有理関数として微分可能な拡張ラグランジアンを用いて,能動型逐次適応型プログラミングアルゴリズムを提案する。 アルゴリズムは、拡張ラグランジアンのパラメータを適応的に選択し、行探索を行い、ステップサイズを決定する。
  論文  参考訳（メタデータ） (2021-09-23T17:12:17Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Neural Stochastic Contraction Metrics for Learning-based Control and Estimation [13.751135823626493]
  NSCMフレームワークにより、自律エージェントは最適な安定制御と推定ポリシーをリアルタイムで近似することができる。 これは、状態依存リカティ方程式、反復LQR、EKF、神経収縮など、既存の非線形制御と推定技術より優れている。
  論文  参考訳（メタデータ） (2020-11-06T03:04:42Z)

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

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