論文の概要: 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$ の最適選択の場合、サンプル複雑性境界は同じ順序であることがわかった。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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) - 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 [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。