論文の概要: MSTGD:A Memory Stochastic sTratified Gradient Descent Method with an
Exponential Convergence Rate
- arxiv url: http://arxiv.org/abs/2202.10923v1
- Date: Mon, 21 Feb 2022 01:36:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 14:55:52.696168
- Title: MSTGD:A Memory Stochastic sTratified Gradient Descent Method with an
Exponential Convergence Rate
- Title（参考訳）: MSTGD:指数収束率を持つ記憶確率sTratified Gradient Descent法
- Authors: Aixiang (Andy) Chen, Jinting Zhang, Zanbo Zhang, Zhihong Li
- Abstract要約: 本稿では,指数収束率を持つ新しいアンダーラインメモリStochastic sunderlineTratified Gradient Descend(underlineMSTGD)アルゴリズムを設計する。
特に、MSTGDは2つの分散還元戦略を用いており、第1の戦略は、使用履歴勾配の比例pに応じて分散還元を行うことである。
指数収束率を達成すると主張する他のほとんどのアルゴリズムとは異なり、収束率はデータセットサイズN、バッチサイズnなどのパラメータとは独立である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The fluctuation effect of gradient expectation and variance caused by
parameter update between consecutive iterations is neglected or confusing by
current mainstream gradient optimization algorithms.Using this fluctuation
effect, combined with the stratified sampling strategy, this paper designs a
novel \underline{M}emory \underline{S}tochastic s\underline{T}ratified Gradient
Descend(\underline{MST}GD) algorithm with an exponential convergence rate.
Specifically, MSTGD uses two strategies for variance reduction: the first
strategy is to perform variance reduction according to the proportion p of used
historical gradient, which is estimated from the mean and variance of sample
gradients before and after iteration, and the other strategy is stratified
sampling by category. The statistic \ $\bar{G}_{mst}$\ designed under these two
strategies can be adaptively unbiased, and its variance decays at a geometric
rate. This enables MSTGD based on $\bar{G}_{mst}$ to obtain an exponential
convergence rate of the form $\lambda^{2(k-k_0)}$($\lambda\in (0,1)$,k is the
number of iteration steps,$\lambda$ is a variable related to proportion
p).Unlike most other algorithms that claim to achieve an exponential
convergence rate, the convergence rate is independent of parameters such as
dataset size N, batch size n, etc., and can be achieved at a constant step
size.Theoretical and experimental results show the effectiveness of MSTGD
- Abstract（参考訳）: 逐次繰り返しのパラメータ更新による勾配予測と分散の変動効果は、現在の主流勾配最適化アルゴリズムによって無視または混乱されるが、この揺らぎ効果と成層化サンプリング戦略を組み合わせることで、指数収束率を持つ新しい勾配デセンド(\underline{MST}GD)アルゴリズムを設計する。
特に、mstgdは分散低減のための2つの戦略を用いる:第1の戦略は、反復前後のサンプル勾配の平均および分散から推定される使用済み履歴勾配の比率pに応じて分散低減を行うことであり、他の戦略はカテゴリごとに階層化サンプリングされる。
この2つの戦略の下で設計された統計量 \$\bar{g}_{mst}$\ は適応的に偏りがなく、その分散は幾何学的速度で減衰する。
これにより、$\bar{G}_{mst}$ に基づいた MSTGD は $\lambda^{2(k-k_0)}$($\lambda\in (0,1)$,k という形の指数収束率を得ることができ、$\lambda$ は比例 p に関連する変数である。
指数収束率を達成したと主張する他のほとんどのアルゴリズムとは異なり、収束速度はデータセットサイズN、バッチサイズnなどのパラメータとは独立であり、一定のステップサイズで達成できる。
関連論文リスト
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳（メタデータ） (2023-09-03T19:21:59Z) - $\bar{G}_{mst}$:An Unbiased Stratified Statistic and a Fast Gradient
Optimization Algorithm Based on It [0.0]
barG_mst$をベースとしたMSSGという新しいアルゴリズムは、他のsgdライクなアルゴリズムより優れている。
論文 参考訳（メタデータ） (2021-10-07T11:48:55Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Fast Margin Maximization via Dual Acceleration [52.62944011696364]
指数関数的尾の損失を持つ線形分類器を訓練するための運動量に基づく手法を提案し,解析する。
この運動量に基づく法は、最大マルジン問題の凸双対、特にこの双対にネステロフ加速度を適用することによって導出される。
論文 参考訳（メタデータ） (2021-07-01T16:36:39Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文 参考訳（メタデータ） (2020-02-15T00:26:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。