論文の概要: 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 Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。
この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文 参考訳(メタデータ) (2023-03-17T13:32:33Z) - Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal
Leakage [24.40306100502023]
我々は,雑音学習アルゴリズムのクラスにおける一般化挙動を解析するために,情報理論の枠組みを採用する。
更新関数の仮定が雑音の最適選択にどのように影響するかを示す。
論文 参考訳(メタデータ) (2023-02-28T12:13:57Z) - Model-Based Uncertainty in Value Functions [89.31922008981735]
MDP上の分布によって引き起こされる値の分散を特徴付けることに重点を置いている。
従来の作業は、いわゆる不確実性ベルマン方程式を解くことで、値よりも後方の分散を境界にしている。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式を提案する。
論文 参考訳(メタデータ) (2023-02-24T09:18:27Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Concentration analysis of multivariate elliptic diffusion processes [0.0]
連続時間および離散時間付加関数に対する濃度不等式と関連するPAC境界を証明した。
我々の分析はポアソン方程式によるアプローチに依存しており、非常に幅広い指数的エルゴード過程のクラスを考えることができる。
論文 参考訳(メタデータ) (2022-06-07T14:15: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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Uncertainty quantification for nonconvex tensor completion: Confidence
intervals, heteroscedasticity and optimality [92.35257908210316]
本研究では,不完全かつ破損した観測によって与えられる低ランクテンソルを推定する問題について検討する。
改善不可能なレートをell-2$の精度で達成できることが分かりました。
論文 参考訳(メタデータ) (2020-06-15T17:47:13Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。