論文の概要: Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

• arxiv url: http://arxiv.org/abs/2605.31309v1
• Date: Fri, 29 May 2026 13:41:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-01 20:56:50.642339
• Title: Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
• Title（参考訳）: 確率的反復アルゴリズムの漸近収束:リアプノフフレームワーク
• Abstract要約: 反復アルゴリズムの有限時間解析のためのリアプノフに基づく手法を探索する。 一般化エンベロープが、基礎となるノルムによらず、普遍リプノフ函数としてどのように機能するかを示す。 マルコフ雑音、半収縮作用素、散逸的および高確率境界の拡張について論じ、開問題で結論付ける。
• 参考スコア（独自算出の注目度）: 9.210053545945886
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations $\bar{F}(x)=x$, where the operator $\bar{F}(\cdot)$ can only be accessed through a noisy oracle. We first focus on the standard setting in which $\bar{F}(\cdot)$ is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.
• Abstract（参考訳）: 確率的反復アルゴリズムの有限時間解析のためのリャプノフに基づく手法を探索し、確率的近似(英語版)(SA)アルゴリズム(英語版)(Stochastic Approximation:SA)アルゴリズム(英語版)とも呼ばれる)を用いて、不動点方程式の解法として$\bar{F}(x)=x$(英語版)を探索する。 まず、あるノルムに対して$\bar{F}(\cdot)$ が収縮的であり、ノイズは i.d. であり、基礎ノルムによらず、一般化されたモローエンベロープが普遍リプノフ函数としてどのように機能するかを説明する。 次に,この枠組みが平均二乗収束を保証する方法を示し,確率勾配降下,線形SA,Q-ラーニングや時間差学習などの値に基づく強化学習アルゴリズムに適用する。 最後に、マルコフ雑音、半ノルム収縮作用素、散逸作用素、高確率境界の拡張について議論し、開問題で結論付ける。 目標は、SAとその応用、特に強化学習における有限時間解析のための統一的で自己完結したロードマップを提供することである。

関連論文リスト

• Stochastic simultaneous optimistic optimization [70.50540950403109]
  雑音による摂動数が有限である関数 f の評価問題について検討する。 我々のアルゴリズムであるStoSOOは、関数領域の階層的分割上の上位信頼境界を構築し、次にどの点をサンプリングするかを決定する楽観的な戦略に従う。 StoSOO の有限時間解析は、関数の局所的滑らかさが分かっていないにもかかわらず、最も高度に最適化されたアルゴリズムと同等に機能することを示している。
  論文  参考訳（メタデータ） (2026-04-27T14:34:24Z)
• A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging [2.378735224874938]
  Polyak-Rt平均化は近似アルゴリズムの最適分散を実現するために広く用いられている手法である。 平均的なSA反復の誤差に対する非漸近濃度境界を確立するための一般的な枠組みを提案する。
  論文  参考訳（メタデータ） (2025-05-27T21:58:35Z)
• Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise [5.7071219882414885]
  2時間スケール近似(英: Two-time-scale Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 強化学習の応用により、非線型2時間スケール SA 上の最初の平均正方形を与える。
  論文  参考訳（メタデータ） (2025-03-24T07:03:23Z)
• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [4.769747792846004]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning [40.636276521022474]
  近似(英: Approximation、SA)は、初期から信号処理に大きな影響を与えてきた古典的なアルゴリズムである。 本稿では,SAの非確率的・漸進的な視点を信号処理と機械学習のオーディエンスに紹介する。 我々は、様々な穏やかな条件を満たすリャプノフ関数のクラスに基づいて分析フレームワークを構築した。
  論文  参考訳（メタデータ） (2023-02-22T05:00:51Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants [39.28675942566465]
  本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。 副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
  論文  参考訳（メタデータ） (2021-02-02T15:48:19Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes [40.31139355952393]
  一般化エンベロープを用いて滑らかなリャプノフ函数を構築し、そのリャプノフ函数に対してSAの反復体が負のドリフトを持つことを示す。 特に、政治以外のTD学習において、Vトレースアルゴリズムの最初の既知収束率を確立するためにこれを用いる。 また、TD学習を現場で研究し、既存の最先端の成果を$Q$ラーニングで回収する。
  論文  参考訳（メタデータ） (2020-02-03T16:42:01Z)

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

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