論文の概要: Does Momentum Help? A Sample Complexity Analysis
- arxiv url: http://arxiv.org/abs/2110.15547v1
- Date: Fri, 29 Oct 2021 05:26:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-01 14:44:31.711984
- Title: Does Momentum Help? A Sample Complexity Analysis
- Title(参考訳): Momentumは役に立つか?
サンプル複雑度解析
- Authors: Gugan Thoppe, Rohan Deb, Swetha Ganesh, Amarjit Budhiraja
- Abstract要約: まず,運動量を用いた場合,最適なステップサイズでの収束速度は向上しないことを示す。
次に、運動量と無運動量で反復するサンプルの複雑さを分析する。
SA が運動量を持つ場合のサンプル複雑性は、$alpha$ の小さな場合の方がよいが、2つの場合の$alpha$ の最適選択の場合、サンプル複雑性境界は同じ順序であることがわかった。
- 参考スコア(独自算出の注目度): 5.0468312081378475
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Momentum methods are popularly used in accelerating stochastic iterative
methods. Although a fair amount of literature is dedicated to momentum in
stochastic optimisation, there are limited results that quantify the benefits
of using heavy ball momentum in the specific case of stochastic approximation
algorithms. We first show that the convergence rate with optimal step size does
not improve when momentum is used (under some assumptions). Secondly, to
quantify the behaviour in the initial phase we analyse the sample complexity of
iterates with and without momentum. We show that the sample complexity bound
for SA without momentum is
$\tilde{\mathcal{O}}(\frac{1}{\alpha\lambda_{min}(A)})$ while for SA with
momentum is $\tilde{\mathcal{O}}(\frac{1}{\sqrt{\alpha\lambda_{min}(A)}})$,
where $\alpha$ is the step size and $\lambda_{min}(A)$ is the smallest
eigenvalue of the driving matrix $A$. Although the sample complexity bound for
SA with momentum is better for small enough $\alpha$, it turns out that for
optimal choice of $\alpha$ in the two cases, the sample complexity bounds are
of the same order.
- Abstract(参考訳): モメンタム法は確率的反復法の加速に広く用いられている。
かなりの量の文献が確率的最適化の運動量に費やされているが、確率的近似アルゴリズムの特定の場合において、重い球の運動量を使うことの利点を定量化する限定的な結果がある。
まず, 最適ステップサイズの収束率は, 運動量を用いた場合(いくつかの仮定により)は改善しないことを示した。
第二に,初期段階での挙動を定量化するために,運動量と無運動量で反復のサンプル複雑性を分析した。
運動量のないSAのサンプル複雑性は$\tilde{\mathcal{O}}(\frac{1}{\alpha\lambda_{min}(A)})$であるのに対し、運動量を持つSAのサンプル複雑性は$\tilde{\mathcal{O}}(\frac{1}{\sqrt{\alpha\lambda_{min}(A)}})$であり、$\alpha$はステップサイズであり、$\lambda_{min}(A)$は運転行列の最小固有値である。
SA が運動量を持つ場合のサンプル複雑性は小さければ$\alpha$ の方がよいが、2つの場合において$\alpha$ の最適選択の場合、サンプル複雑性境界は同じ順序であることがわかった。
関連論文リスト
- Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳(メタデータ) (2023-10-13T03:08:59Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳(メタデータ) (2023-02-13T00:22:28Z) - Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic
Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。
学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文 参考訳(メタデータ) (2022-10-10T18:34:32Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳(メタデータ) (2021-05-28T17:49:39Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。