論文の概要: Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling
- arxiv url: http://arxiv.org/abs/2502.14648v1
- Date: Thu, 20 Feb 2025 15:37:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-21 14:26:46.418916
- Title: Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling
- Title(参考訳): 完全勾配計算不要なばらつき低減法:シャッフルによる効率改善
- Authors: Daniil Medyakov, Gleb Molodtsov, Savelii Chezhegov, Alexey Rebrikov, Aleksandr Beznosikov,
- Abstract要約: 大規模機械学習問題に対するメモリ効率のアルゴリズムを開発した。
メモリ効率を向上し、完全な計算を避けるために、2つの重要な手法を用いる。
- 参考スコア(独自算出の注目度): 44.31966204357333
- License:
- Abstract: In today's world, machine learning is hard to imagine without large training datasets and models. This has led to the use of stochastic methods for training, such as stochastic gradient descent (SGD). SGD provides weak theoretical guarantees of convergence, but there are modifications, such as Stochastic Variance Reduced Gradient (SVRG) and StochAstic Recursive grAdient algoritHm (SARAH), that can reduce the variance. These methods require the computation of the full gradient occasionally, which can be time consuming. In this paper, we explore variants of variance reduction algorithms that eliminate the need for full gradient computations. To make our approach memory-efficient and avoid full gradient computations, we use two key techniques: the shuffling heuristic and idea of SAG/SAGA methods. As a result, we improve existing estimates for variance reduction algorithms without the full gradient computations. Additionally, for the non-convex objective function, our estimate matches that of classic shuffling methods, while for the strongly convex one, it is an improvement. We conduct comprehensive theoretical analysis and provide extensive experimental results to validate the efficiency and practicality of our methods for large-scale machine learning problems.
- Abstract(参考訳): 今日の世界では、大規模なトレーニングデータセットやモデルなしでは、機械学習は想像できない。
これにより、確率勾配降下(SGD)のような確率的訓練法が用いられるようになった。
SGDは収束の弱い理論的保証を提供するが、SVRG (Stochastic Variance Reduced Gradient) やStochAstic Recursive grAdient algoritHm (SARAH) のような変化があり、分散を減少させる。
これらの手法は時折完全な勾配の計算を必要とするが、時間を要することがある。
本稿では,全勾配計算を不要とする分散削減アルゴリズムの変種について検討する。
メモリ効率を向上し、完全な勾配計算を避けるために、シャッフルヒューリスティック法とSAG/SAGA法という2つの重要な手法を用いる。
その結果,全勾配計算を使わずに,分散削減アルゴリズムの既存の推定値を改善することができた。
さらに,非凸目的関数では従来のシャッフル法と一致し,強い凸関数では改善される。
本研究では,大規模機械学習問題に対する手法の有効性と実用性を検証するため,包括的理論的解析を行い,広範な実験結果を提供する。
関連論文リスト
- Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data [9.913418444556486]
本稿では, FSAを用いた確率, 勾配, 予測分布の計算コストの削減に, 反復法をどのように利用できるかを示す。
また,推定法や反復法に依存する予測分散を計算する新しい,正確かつ高速な手法を提案する。
すべてのメソッドは、ハイレベルなPythonとRパッケージを備えたフリーのC++ソフトウェアライブラリで実装されている。
論文 参考訳(メタデータ) (2024-05-23T12:25:22Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Stochastic Gradient Descent with Preconditioned Polyak Step-size [1.3300175008796402]
Gradient Descent with Polyak Step-size (SPS)は、データセットの学習率を微調整する必要性を軽減する更新ルールを提供する方法である。
本稿では,Hutchinson'sやAda'sなどのプレコンディショニング技術を用いたSPSの拡張を提案する。
論文 参考訳(メタデータ) (2023-10-03T14:36:05Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
StochAstic Recursive grAdientritHm (SARAH)アルゴリズムは、Gradient Descent (SGD)アルゴリズムのばらつき低減版である。
本稿では,完全勾配の必要性を除去する。
集約された勾配は、SARAHアルゴリズムの完全な勾配の見積もりとなる。
論文 参考訳(メタデータ) (2021-11-26T06:00:44Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Stochastic Reweighted Gradient Descent [4.355567556995855]
SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
論文 参考訳(メタデータ) (2021-03-23T04:09:43Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳(メタデータ) (2020-01-27T08:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。