論文の概要: A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging

• arxiv url: http://arxiv.org/abs/2505.21796v1
• Date: Tue, 27 May 2025 21:58:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 17:35:50.312991
• Title: A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
• Title（参考訳）: ポリーク平均化による確率近似の高確率境界に対する汎用理論
• Authors: Sajad Khodadadian, Martin Zubeldia,
• Abstract要約: Polyak-Rt平均化は近似アルゴリズムの最適分散を実現するために広く用いられている手法である。 平均的なSA反復の誤差に対する非漸近濃度境界を確立するための一般的な枠組みを提案する。
• 参考スコア（独自算出の注目度）: 2.378735224874938
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.
• Abstract（参考訳）: Polyak-Ruppert averagingは確率近似(SA)アルゴリズムの漸近的最適分散を実現するために広く使われている手法であるが、その高確率性能保証は一般には未探索のままである。 本稿では,平均的なSA反復の誤差に対する非漸近濃度境界を確立するための一般的な枠組みを提案する。 提案手法では, 平均化されていないイテレーションに対して, 個々の濃度境界へのアクセスを仮定し, 平均化イテレーションに鋭い境界を与える。 また、結果の厳密さを一定乗算因子まで示す例も作成する。 直接的応用として、契約型SAアルゴリズムと、時間差分学習や平均化によるQ-ラーニングなどのアルゴリズムの厳密な濃度境界を導出し、従来の分析が困難な環境での新しい境界を求める。

関連論文リスト

• Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms [10.022615790746466]
  アルゴリズムのサンプルパスとOrnstein-Uhlenbeck近似の非漸近関数近似誤差を導出する。 我々は、L'evy-Prokhorov と有界ワッサーシュタイン距離という2つの一般的な測度で誤差境界を構築するために、主要な結果を使用する。
  論文  参考訳（メタデータ） (2025-01-21T15:29:11Z)
• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP [1.0923877073891446]
  政策評価のために線形関数近似(LFA)を用いた時間差分学習アルゴリズムを解析する。 我々は、(i) を平均二乗の意味で保持し、(ii) を尾の反復平均化の下で高い確率で導く有限サンプル境界を導出する。 これらの結果は、強化学習におけるリスクに敏感なアクター批判法に対する有限サンプル理論的保証を確立する。
  論文  参考訳（メタデータ） (2024-06-12T05:49:53Z)
• Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
  一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。 本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
  論文  参考訳（メタデータ） (2023-10-22T12:37:25Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound [15.557653926558638]
  分類器の有限アンサンブルに対する多数票の対について検討し、その一般化特性について検討する。 ディリクレ分布でインスタンス化し、予測されるリスクに対して閉じた形式と微分可能な表現を可能にする。 結果の多数決学習アルゴリズムは、最先端の精度と(非空きな)厳密な境界から恩恵を得る。
  論文  参考訳（メタデータ） (2021-06-23T16:57:23Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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