論文の概要: Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

• arxiv url: http://arxiv.org/abs/2605.20999v1
• Date: Wed, 20 May 2026 10:38:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.62598
• Title: Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise
• Title（参考訳）: 重み付きマルコフ雑音下での一般確率近似の濃度
• Authors: Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia,
• Abstract要約: 我々は、一般的なステップサイズを持つ近似アルゴリズムによって生成される反復集合に対して、最大濃度境界を確立する。 Martingale-Difference ノイズが有界であるとき、誤差のテールが準ガウス的であることを示す。 ランダム作用素がほぼ確実に拡張可能でない場合、誤差テールはノイズテールの3倍の重みを持つことを示す。
• 参考スコア（独自算出の注目度）: 6.780086370528622
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian, sub-Weibull, or something lighter than any Pareto but heavier than any Weibull, depending on the step size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. Our analysis relies on a novel Lyapunov function involving the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. We complement the upper bounds with worst-case examples showing that qualitatively sharper bounds are impossible. We further study the case of unbounded Martingale-difference noise when the average operator is contractive, and the step sizes are of order $1/k$. In this setting, we show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail, whereas if the random operator is expansive with positive probability, then the error may have substantially heavier tails. These results are obtained through a novel black-box truncation argument that reduces the unbounded-noise setting to the bounded-noise case.
• Abstract（参考訳）: 我々は,確率近似アルゴリズムによって生成されるイテレートに対して,雑音が有限状態マルコフ成分とMartingale-Difference成分を持つような一般的なステップサイズで最大濃度境界を確立する。 Martingale-Differenceノイズが有界であるとき、この誤差の尾は、どのパレートよりも軽く、どのワイブルよりも重く、またランダム作用素がほぼ確実に収縮的か、ほぼ確実に非膨張的か、あるいは正の確率で拡張可能であることを示す。 我々の解析は、ポアソン方程式に対する解のモーメント生成関数と補助射影アルゴリズムを含む新しいリャプノフ関数に依存している。 上界は、定性的にシャープな境界が不可能であることを示す最悪の例で補う。 さらに、平均作用素が縮約されたときの非有界マルティンゲール差音の場合について検討し、ステップサイズは1/k$である。 この設定では、ランダム作用素がほぼ確実に拡張可能でない場合、エラーテールはノイズテールの3倍の重みを持つ一方、ランダム作用素が正の確率で拡張可能であれば、エラーは著しく重みを持つ可能性があることを示す。 これらの結果は、非有界ノイズ設定を有界ノイズケースに還元する、新しいブラックボックス・トランケーション引数によって得られる。

関連論文リスト

• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。 また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
  論文  参考訳（メタデータ） (2026-02-15T23:19:07Z)
• Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation [6.800624963330628]
  ワッサーシュタイン-$p$距離における非線形近似アルゴリズムの非漸近誤差境界を導出する。 正規化された最後の繰り返しは、$p$-ワッサーシュタイン距離のガウス分布に階数$_n1/6$で収束することを示し、$_n$はステップサイズである。 これらの分布保証は、モーメント境界やマルコフの不等式から得られるものより改善される高確率濃度の不等式を暗示する。
  論文  参考訳（メタデータ） (2026-02-02T18:41:06Z)
• Towards Sharp Minimax Risk Bounds for Operator Learning [8.781886844319231]
  我々は、一様有界リプシッツ作用素に対して、情報理論の下界とマッチングあるいは近接マッチングの上界を共に証明する。 重要な意味はサンプル複雑性の呪いであり、これは一般リプシッツ作用素のミニマックスリスクがサンプルサイズにおける任意の代数的速度で崩壊できないことを示している。
  論文  参考訳（メタデータ） (2025-12-19T17:07:43Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
  我々は,契約演算子の下で近似(SA)によって生成される反復体に対して最大濃度境界を確立する。 本稿では,有界乗法雑音を持つ SA と準ガウス加法雑音を持つ SA の2つの条件について考察する。
  論文  参考訳（メタデータ） (2023-03-28T05:32:30Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• 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)

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

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