論文の概要: Concentration of Contractive Stochastic Approximation: Additive and
Multiplicative Noise
- arxiv url: http://arxiv.org/abs/2303.15740v1
- Date: Tue, 28 Mar 2023 05:32:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 16:21:44.801342
- Title: Concentration of Contractive Stochastic Approximation: Additive and
Multiplicative Noise
- Title（参考訳）: 収縮確率近似の濃度:加算音と乗算音
- Authors: Zaiwei Chen, Siva Theja Maguluri, and Martin Zubeldia
- Abstract要約: 本研究では, 任意のノルムに対して, 契約演算子の下でのモロー近似アルゴリズムの濃度挙動について検討する。
我々は収束誤差の最大濃度不等式を求め、これらの誤差が加法雑音設定における準ガウス尾を持つことを示す。
乗法雑音によるSAの準指数尾の達成は一般に不可能であることを示す。
- 参考スコア（独自算出の注目度）: 7.532013242448151
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study the concentration behavior of a stochastic
approximation (SA) algorithm under a contractive operator with respect to an
arbitrary norm. We consider two settings where the iterates are potentially
unbounded: (1) bounded multiplicative noise, and (2) additive sub-Gaussian
noise. We obtain maximal concentration inequalities on the convergence errors,
and show that these errors have sub-Gaussian tails in the additive noise
setting, and super-polynomial tails (faster than polynomial decay) in the
multiplicative noise setting. In addition, we provide an impossibility result
showing that it is in general not possible to achieve sub-exponential tails for
SA with multiplicative noise. To establish these results, we develop a novel
bootstrapping argument that involves bounding the moment generating function of
the generalized Moreau envelope of the error and the construction of an
exponential supermartingale to enable using Ville's maximal inequality.
To demonstrate the applicability of our theoretical results, we use them to
provide maximal concentration bounds for a large class of reinforcement
learning algorithms, including but not limited to on-policy TD-learning with
linear function approximation, off-policy TD-learning with generalized
importance sampling factors, and $Q$-learning. To the best of our knowledge,
super-polynomial concentration bounds for off-policy TD-learning have not been
established in the literature due to the challenge of handling the combination
of unbounded iterates and multiplicative noise.
- Abstract（参考訳）: 本研究では,任意のノルムに対する契約演算子の下での確率近似(SA)アルゴリズムの濃度挙動について検討する。
本稿では,(1)有界乗法雑音,(2)加法的部分ガウス雑音の2つの条件について考察する。
我々は収束誤差の最大濃度不等式を求め,これらの誤差が加法雑音設定における準ガウス尾と乗法雑音設定における超多項式テール(多項式減衰よりも速い)を有することを示す。
さらに,乗法雑音を伴うsaのサブ指数尾部を実現することは一般に不可能であることを示す。
これらの結果を確立するために,誤りの一般化モロー包絡のモーメント生成関数と,ville の極大不等式を有効活用するための指数関数スーパーマーチンゲールの構成を境界とする新しいブートストラップ法を考案する。
理論的な結果の適用性を実証するために,線形関数近似を用いたオンラインTD学習,一般化された重要サンプリング因子を用いたオフポリティクスTD学習,および$Q$ラーニングを含む,大規模な強化学習アルゴリズムに対して,最大濃度境界を提供する。
最善の知識として,非拘束イテレートと乗法雑音の組み合わせを扱うという課題から,オフポリティカルtd学習のための超多項濃度境界は文献に確立されていない。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。