論文の概要: Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach
- arxiv url: http://arxiv.org/abs/2607.17595v1
- Date: Mon, 20 Jul 2026 06:27:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-21 18:48:37.512595
- Title: Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach
- Title（参考訳）: 拘縮確率近似における濃度と平均二乗境界:統一初等的アプローチ
- Abstract要約: 任意のノルム縮約写像を持つモロー近似(SA)の平均二乗および濃度境界を確立する。
これらの設定は強化学習で発生し、演算子は $ell_infty$ norm で収縮することが多い。
提案手法は, 乗法雑音下でのSAに対する最初の準ガウス尾化最大濃度を導出する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish mean-square and concentration bounds for stochastic approximation (SA) with arbitrary norm contractive mappings, under a multiplicative noise model where the noise may scale affinely with the norm of the iterates, and the iterates are potentially unbounded. These settings arise in reinforcement learning, where operators are often contractive in the $\ell_\infty$ norm and the noise scales with the iterates. To address the arbitrary norm, earlier works replace the non-smooth squared norm with a smooth Lyapunov function constructed via the generalized Moreau envelope. For concentration analysis, these works handle multiplicative noise and unbounded iterates through a multi-stage bootstrapping argument that starts from a time-varying worst-case bound and iteratively refines it. We instead present a unified and elementary analysis that yields both bounds. Using an averaged noise sequence and corresponding auxiliary iterates, we obtain a one-step Lyapunov drift inequality for the normed error directly, without smoothing the norm or constructing an envelope. For the mean-square bound, we combine this drift inequality with an induction argument showing that the iterates remain bounded in expectation. For the concentration bound, we develop a probabilistic induction over a sequence of "good" events on which the iterates are controlled, allowing the standard Azuma-Hoeffding bound to be applied. Our approach yields the first sub-Gaussian tailed maximal (all-time) concentration bound for SA under multiplicative noise, by allowing the stepsize to depend logarithmically on the confidence level. Beyond the specific setting considered here, we discuss the generalizability of these proof techniques to other noise models and iterative algorithms.
- Abstract（参考訳）: 我々は、任意のノルムの縮約写像を持つ確率近似(SA)の平均二乗および濃度境界を、雑音が反復のノルムと親和的にスケールし、反復が非有界であるような乗法的雑音モデルの下で確立する。
これらの設定は強化学習で発生し、演算子はしばしば$\ell_\infty$ノルムとイテレートによるノイズスケールで収縮する。
任意のノルムに対処するために、初期の研究は、非滑らかな平方ノルムを一般化されたモローエンベロープを通して構成された滑らかなリャプノフ函数に置き換えた。
濃度分析では、これらの研究は乗法ノイズを処理し、時間的に変化する最悪のケース境界から始まり、それを反復的に洗練する多段ブートストラッピングの議論を通じて、無制限に反復する。
代わりに、両方の境界をもたらす統一的かつ初等的な解析を提示する。
平均的なノイズシーケンスとそれに対応する補助的イテレートを用いて、1ステップのリアプノフドリフト不等式をノルムを滑らかにしたりエンベロープを構成することなく直接求める。
平均二乗境界に対しては、このドリフト不等式と帰納的議論を組み合わせることで、反復が期待通りに有界であることを示す。
濃度境界では, 反復が制御される一連の「良い」事象に対して確率的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的帰納的(probabilistic)が成立する。
提案手法は, 乗法雑音下でのSAの最小(全時間)濃度を推定し, ステップサイズを信頼度に対数的に依存させることにより, 準ガウス級の極大(全時間)濃度を導出する。
ここでは、これらの証明技術の他のノイズモデルや反復アルゴリズムへの一般化可能性について論じる。
関連論文リスト
- Universality of General Spiked Tensor Models [9.454986540713655]
高次元状態におけるランクワンスパイクテンソルモデルについて検討する。
本研究では,その高次元スペクトル挙動と統計的限界が非ガウス雑音に対して頑健であることを示す。
論文 参考訳（メタデータ） (2026-02-04T11:59:30Z) - Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation [6.800624963330628]
ワッサーシュタイン-$p$距離における非線形近似アルゴリズムの非漸近誤差境界を導出する。
正規化された最後の繰り返しは、$p$-ワッサーシュタイン距離のガウス分布に階数$_n1/6$で収束することを示し、$_n$はステップサイズである。
これらの分布保証は、モーメント境界やマルコフの不等式から得られるものより改善される高確率濃度の不等式を暗示する。
論文 参考訳（メタデータ） (2026-02-02T18:41:06Z) - Regularized least squares learning with heavy-tailed noise is minimax optimal [22.406170258823803]
本稿では,高次モーメントの再生回数が有限である雑音の存在下で,カーネルヒルベルト空間におけるリッジ回帰の性能について検討する。
我々は、よく知られた積分作用素の枠組みに基づいて、部分ガウス項と余剰項からなるリスク境界を確立する。
論文 参考訳（メタデータ） (2025-05-20T11:17:54Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳（メタデータ） (2023-06-27T08:15:28Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
我々は,契約演算子の下で近似(SA)によって生成される反復体に対して最大濃度境界を確立する。
本稿では,有界乗法雑音を持つ SA と準ガウス加法雑音を持つ SA の2つの条件について考察する。
論文 参考訳（メタデータ） (2023-03-28T05:32:30Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳（メタデータ） (2020-04-08T03:59:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。