論文の概要: Sampling and Update Frequencies in Proximal Variance-Reduced Stochastic
Gradient Methods
- arxiv url: http://arxiv.org/abs/2002.05545v3
- Date: Tue, 18 Oct 2022 11:10:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 13:48:09.066085
- Title: Sampling and Update Frequencies in Proximal Variance-Reduced Stochastic
Gradient Methods
- Title(参考訳): 確率的勾配法による確率変数のサンプリングと更新頻度
- Authors: Martin Morin and Pontus Giselsson
- Abstract要約: 本稿では, 一般近似分散還元勾配法を提案し, 強い凸性仮定の下で解析する。
このアルゴリズムの特別な例は、SAGA、L-SVRGとその近位変種である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variance-reduced stochastic gradient methods have gained popularity in recent
times. Several variants exist with different strategies for the storing and
sampling of gradients and this work concerns the interactions between these two
aspects. We present a general proximal variance-reduced gradient method and
analyze it under strong convexity assumptions. Special cases of the algorithm
include SAGA, L-SVRG and their proximal variants. Our analysis sheds light on
epoch-length selection and the need to balance the convergence of the iterates
with how often gradients are stored. The analysis improves on other convergence
rates found in the literature and produces a new and faster converging sampling
strategy for SAGA. Problem instances for which the predicted rates are the same
as the practical rates are presented together with problems based on real world
data.
- Abstract(参考訳): 分散還元確率勾配法は近年普及している。
いくつかの変種は勾配の保存とサンプリングのための異なる戦略を持ち、この研究はこれらの2つの側面間の相互作用に関するものである。
本稿では, 一般近似分散還元勾配法を提案し, 強い凸性仮定の下で解析する。
このアルゴリズムの特別な例は、SAGA、L-SVRGとその近位変種である。
我々の分析は、エポック長の選択に光を当て、繰り返しの収束とどれだけの頻度で勾配が保存されるかのバランスを取る必要がある。
この分析は文献中の他の収束率を改善し、SAGAの新しいより高速な収束サンプリング戦略を生成する。
実世界データに基づく問題とともに、予測率と実用率とが同一である問題事例を提示する。
関連論文リスト
- On the Stochastic (Variance-Reduced) Proximal Gradient Method for
Regularized Expected Reward Optimization [12.244251361123396]
我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。
特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon-stationaryポイントに含めることが示されている。
追加条件下では,サンプルの複雑さが$epsilon-4)$から$O(epsilon-3)$に改善できることが示されている。
論文 参考訳(メタデータ) (2024-01-23T06:01:29Z) - Accelerated stochastic approximation with state-dependent noise [7.623467689146604]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳(メタデータ) (2023-07-04T06:06:10Z) - Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient
Methods [73.35353358543507]
SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。
本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。
本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
論文 参考訳(メタデータ) (2022-02-15T09:17:39Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - A Unified Analysis of Stochastic Gradient Methods for Nonconvex
Federated Optimization [16.714109768541785]
非非状態におけるSGD不変量を満たすすべての方法について単一の解析を行う。
また、PL条件下での非非状態におけるより高速な線形収束を得るための統一解析も提供する。
論文 参考訳(メタデータ) (2020-06-12T08:58:03Z) - A Unified Convergence Analysis for Shuffling-Type Gradient Methods [32.8097849940763]
有限項問題を解くための一般化勾配シャッフル型法に対する統一収束解析を提案する。
以上の結果から,特定の神経シャッフル変種でのトレーニングに適する選択が示唆された。
論文 参考訳(メタデータ) (2020-02-19T15:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。