論文の概要: Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise

• arxiv url: http://arxiv.org/abs/2303.15740v2
• Date: Tue, 17 Sep 2024 01:23:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-18 23:00:28.821171
• Title: Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise
• Title（参考訳）: 収縮確率近似の濃度:加算音と乗算音
• Authors: Zaiwei Chen, Siva Theja Maguluri, Martin Zubeldia,
• Abstract要約: 我々は,契約演算子の下で近似(SA)によって生成される反復体に対して最大濃度境界を確立する。 本稿では,有界乗法雑音を持つ SA と準ガウス加法雑音を持つ SA の2つの条件について考察する。
• 参考スコア（独自算出の注目度）: 9.76321513479048
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we establish maximal concentration bounds for the iterates generated by a stochastic approximation (SA) algorithm under a contractive operator with respect to some arbitrary norm (for example, the $\ell_\infty$-norm). We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise. Our maximal concentration inequalities state that the convergence error has a sub-Gaussian tail in the additive noise setting and a Weibull tail (which is faster than polynomial decay but could be slower than exponential decay) in the multiplicative noise setting. In addition, we provide an impossibility result showing that it is generally impossible to have sub-exponential tails under multiplicative noise. To establish the maximal concentration bounds, we develop a novel bootstrapping argument that involves bounding the moment-generating function of a modified version of the generalized Moreau envelope of the convergence error and constructing an exponential supermartingale to enable using Ville's maximal inequality. We demonstrate the applicability of our theoretical results in the context of linear SA and reinforcement learning.
• Abstract（参考訳）: 本稿では,任意のノルム(例えば$\ell_\infty$-norm)に関して,確率近似(SA)アルゴリズムによって生成される反復集合に対する最大濃度境界を確立する。 本稿では,有界乗法雑音を持つ SA と準ガウス加法雑音を持つ SA の2つの条件について考察する。 我々の最大濃度不等式は、収束誤差が加法雑音設定における準ガウス尾と乗法雑音設定におけるワイブルテール(多項式減衰よりも速いが指数減衰より遅い)を有することを示している。 さらに,乗法雑音下でのサブ指数尾を持つことは一般的に不可能であることを示す。 最大濃度境界を確立するために、収束誤差の一般化モローエンベロープの修正版におけるモーモローのモーメント生成関数の有界化と、ヴィルの最大不等式を有効活用するための指数スーパーマーチンゲールの構築を含む、新しいブートストラップ引数を開発する。 線形SAと強化学習の文脈における理論的結果の適用性を示す。

関連論文リスト

• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
  本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。 我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
  論文  参考訳（メタデータ） (2024-08-25T10:28:31Z)
• Revisiting Convergence of AdaGrad with Relaxed Assumptions [4.189643331553922]
  問題に対する AdaGrad の収束と運動量(特別の場合として AdaGrad をカバー)を再考する。 このモデルは、多くの実用的な応用において、サブソースを含む広い範囲のノイズを含む。
  論文  参考訳（メタデータ） (2024-02-21T13:24:14Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage [24.40306100502023]
  我々は,雑音学習アルゴリズムのクラスにおける一般化挙動を解析するために,情報理論の枠組みを採用する。 更新関数の仮定が雑音の最適選択にどのように影響するかを示す。
  論文  参考訳（メタデータ） (2023-02-28T12:13:57Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean [9.289846887298854]
  信頼シーケンスは、時間パラメトリックカバレッジ保証付き予測可能なパラメータシーケンスに対する適応されたセット列を生成する。 この研究は、スラックが0に収束するランニング平均条件付き期待値に対して、漸近的でない低CSを構成する。
  論文  参考訳（メタデータ） (2022-10-20T09:50:05Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Heavy-tailed denoising score matching [5.371337604556311]
  ランゲヴィン力学における複数のノイズレベルを連続的に初期化する反復的雑音スケーリングアルゴリズムを開発した。 実用面では、重み付きDSMを用いることで、スコア推定、制御可能なサンプリング収束、不均衡データセットに対するよりバランスのない非条件生成性能が改善される。
  論文  参考訳（メタデータ） (2021-12-17T22:04:55Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。 低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
  論文  参考訳（メタデータ） (2021-10-26T15:02:27Z)

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

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