論文の概要: Characterizing & Finding Good Data Orderings for Fast Convergence of
Sequential Gradient Methods
- arxiv url: http://arxiv.org/abs/2202.01838v1
- Date: Thu, 3 Feb 2022 20:38:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-07 15:01:53.740504
- Title: Characterizing & Finding Good Data Orderings for Fast Convergence of
Sequential Gradient Methods
- Title（参考訳）: 逐次勾配法の高速収束のための良いデータ順序付けのキャラクタリゼーションと探索
- Authors: Amirkeivan Mohtashami Sebastian Stich Martin Jaggi
- Abstract要約: 我々は、順序が収束速度に及ぼす影響を定量化し、選択された置換列に基づいて収束境界を求める。
我々は、訓練中に優れた順序を選択するための欲求アルゴリズムを開発し、RRよりも優れた性能(精度が14%以上)を達成した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While SGD, which samples from the data with replacement is widely studied in
theory, a variant called Random Reshuffling (RR) is more common in practice. RR
iterates through random permutations of the dataset and has been shown to
converge faster than SGD. When the order is chosen deterministically, a variant
called incremental gradient descent (IG), the existing convergence bounds show
improvement over SGD but are worse than RR. However, these bounds do not
differentiate between a good and a bad ordering and hold for the worst choice
of order. Meanwhile, in some cases, choosing the right order when using IG can
lead to convergence faster than RR. In this work, we quantify the effect of
order on convergence speed, obtaining convergence bounds based on the chosen
sequence of permutations while also recovering previous results for RR. In
addition, we show benefits of using structured shuffling when various levels of
abstractions (e.g. tasks, classes, augmentations, etc.) exists in the dataset
in theory and in practice. Finally, relying on our measure, we develop a greedy
algorithm for choosing good orders during training, achieving superior
performance (by more than 14 percent in accuracy) over RR.
- Abstract（参考訳）: SGDは理論上はデータからサンプルを抽出するが、実際にはRandom Reshuffling (RR)と呼ばれる変種の方が一般的である。
RRはデータセットのランダムな置換を通して反復し、SGDよりも早く収束することが示されている。
順序が決定論的に選択されるとき、インクリメンタル勾配降下(IG)と呼ばれる変種は、既存の収束境界はSGDよりも改善されているが、RRよりも悪い。
しかし、これらの境界は良い順序と悪い順序を区別せず、最悪の順序の選択を保っている。
一方、IGを使用するときの正しい順序を選択すると、RRよりも早く収束することがある。
本研究では, 順序が収束速度に及ぼす影響を定量化し, 選択した順列に基づく収束境界を得るとともに, rr の先行結果を回収する。
さらに、様々なレベルの抽象化(タスク、クラス、拡張など)が理論や実践においてデータセットに存在する場合、構造化シャッフルを使用することの利点を示す。
最後に,本尺度に依拠して,トレーニング中に適切な注文を選択し,rrよりも優れた性能(精度で14%以上)を達成するための欲深いアルゴリズムを開発した。
関連論文リスト
- MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
並列作業者の助けを借りてスムーズな非関数の期待を最小化する問題について検討する。
本稿では,ノイズの重み付けを行う新しい非同期SGD手法であるMindlayer SGDを提案する。
我々の理論は、ノイズが重く尾行されている場合に、Mindlayer SGDの優位性を実証するものである。
論文 参考訳（メタデータ） (2024-10-05T21:11:32Z) - Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities [40.1331539540764]
本稿では,3種類のVIPに対してランダムリシャッフル(SEG-RR)を用いたSEGの収束解析を行う。
我々は,SEG-RRが均一な置換サンプリングSEGよりも高速に収束する条件を導出する。
単調な設定では,SEG-RRの解析により,大きなバッチサイズを伴わずに任意の精度で収束が保証される。
論文 参考訳（メタデータ） (2024-03-11T20:35:52Z) - Fast Convergence of Random Reshuffling under Over-Parameterization and
the Polyak-\L ojasiewicz Condition [41.58274719943315]
ランダムリシャッフル法(RR)として知られるサンプリング無勾配勾配勾配勾配(SGD)の収束特性について検討する。
RRは各エポックの開始時にデータのランダムな置換を選択し、各サンプルは置換から次のサンプルを選択する。
論文 参考訳（メタデータ） (2023-04-02T06:00:29Z) - Coordinating Distributed Example Orders for Provably Accelerated
Training [39.05759866984658]
本稿では,分散環境に順応する置換型例の利点を変換するために,CD-GraB(Coordinated Distributed GraB)を提案する。
無視可能なオーバーヘッドでは、CD-GraBは集中型GraBよりも収束速度が線形に向上し、様々なベンチマークタスクにおいて分散RRより優れる。
論文 参考訳（メタデータ） (2023-02-02T03:15:29Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Stochastic Reweighted Gradient Descent [4.355567556995855]
SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
論文 参考訳（メタデータ） (2021-03-23T04:09:43Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳（メタデータ） (2020-06-10T17:57:21Z) - Top-k Training of GANs: Improving GAN Performance by Throwing Away Bad
Samples [67.11669996924671]
GAN(Generative Adversarial Network)トレーニングアルゴリズムに,簡単な修正(一行のコード)を導入する。
ジェネレータパラメータを更新するとき、批判者が最も現実的に評価するバッチの要素から勾配のコントリビューションをゼロにします。
このトップk更新の手順が一般的に適用可能な改善であることを示す。
論文 参考訳（メタデータ） (2020-02-14T19:27:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。