論文の概要: Stochastic Reweighted Gradient Descent
- arxiv url: http://arxiv.org/abs/2103.12293v1
- Date: Tue, 23 Mar 2021 04:09:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-24 14:02:28.172292
- Title: Stochastic Reweighted Gradient Descent
- Title（参考訳）: 確率的再重み付け勾配降下
- Authors: Ayoub El Hanchi, David A. Stephens
- Abstract要約: SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
- 参考スコア（独自算出の注目度）: 4.355567556995855
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the strong theoretical guarantees that variance-reduced finite-sum
optimization algorithms enjoy, their applicability remains limited to cases
where the memory overhead they introduce (SAG/SAGA), or the periodic full
gradient computation they require (SVRG/SARAH) are manageable. A promising
approach to achieving variance reduction while avoiding these drawbacks is the
use of importance sampling instead of control variates. While many such methods
have been proposed in the literature, directly proving that they improve the
convergence of the resulting optimization algorithm has remained elusive. In
this work, we propose an importance-sampling-based algorithm we call SRG
(stochastic reweighted gradient). We analyze the convergence of SRG in the
strongly-convex case and show that, while it does not recover the linear rate
of control variates methods, it provably outperforms SGD. We pay particular
attention to the time and memory overhead of our proposed method, and design a
specialized red-black tree allowing its efficient implementation. Finally, we
present empirical results to support our findings.
- Abstract（参考訳）: 分散削減された有限サム最適化アルゴリズムが楽しめるという強い理論的保証にもかかわらず、その適用性は、導入するメモリオーバーヘッド(sag/saga)や必要な周期フルグラデーション計算(svrg/sarah)に制限されている。
これらの欠点を避けながら分散削減を実現するための有望なアプローチは、制御変数の代わりに重要サンプリングを使用することである。
このような手法は文献に多く提案されているが、結果の最適化アルゴリズムの収束性を改善することが直接証明されている。
本研究では,srg(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
強凸の場合におけるsrgの収束を解析し, 制御変数の線形率を回復しないが, sgdよりも優れていることを示す。
我々は,提案手法の時間とメモリオーバーヘッドに特に注意を払い,その効率的な実装を可能にする特別な赤黒木を設計する。
最後に,本研究の成果を裏付ける実証的結果を示す。
関連論文リスト
- Sample-efficient Bayesian Optimisation Using Known Invariances [56.34916328814857]
バニラと制約付きBOアルゴリズムは、不変目的を最適化する際の非効率性を示す。
我々はこれらの不変カーネルの最大情報ゲインを導出する。
核融合炉用電流駆動システムの設計に本手法を用い, 高性能溶液の探索を行った。
論文 参考訳（メタデータ） (2024-10-22T12:51:46Z) - Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。
通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。
本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文 参考訳（メタデータ） (2023-09-29T15:24:48Z) - Efficiency Ordering of Stochastic Gradient Descent [9.634481296779057]
我々は、任意のグラフ上のノイズやランダムウォークを含む一般的なサンプリングシーケンスによって駆動される勾配降下(SGD)アルゴリズムについて検討する。
我々は、マルコフ・チェイン・モンテカルロサンプリング器の性能を比較するためのよく分析されたツールである「効率順序付け」の概念を採用している。
論文 参考訳（メタデータ） (2022-09-15T16:50:55Z) - An Accelerated Doubly Stochastic Gradient Method with Faster Explicit
Model Identification [97.28167655721766]
本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。
まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
論文 参考訳（メタデータ） (2022-08-11T22:27:22Z) - On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
論文 参考訳（メタデータ） (2022-01-26T22:02:21Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes [4.355567556995855]
ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
論文 参考訳（メタデータ） (2021-03-23T00:28:15Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
政治政策の最適化は強化学習において難しい問題である。
オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
論文 参考訳（メタデータ） (2020-09-14T16:22:46Z) - Stochastic Approximate Gradient Descent via the Langevin Algorithm [11.36635610546803]
本研究では,不偏勾配が自明に得られない場合の勾配勾配の代替として,近似勾配勾配(SAGD)を導入する。
SAGDは,予測最大化アルゴリズムや変分オートエンコーダといった,一般的な統計的および機械学習問題において,実験的によく機能することを示す。
論文 参考訳（メタデータ） (2020-02-13T14:29:21Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳（メタデータ） (2020-01-27T08:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。