論文の概要: GraB: Finding Provably Better Data Permutations than Random Reshuffling
- arxiv url: http://arxiv.org/abs/2205.10733v1
- Date: Sun, 22 May 2022 04:17:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-24 19:27:15.218898
- Title: GraB: Finding Provably Better Data Permutations than Random Reshuffling
- Title(参考訳): GraB: ランダムリシャッフルよりもおそらく優れたデータ置換を見つける
- Authors: Yucheng Lu, Wentao Guo, Christopher De Sa
- Abstract要約: ランダムリシャッフルはデータセットを各エポックにランダムに置換するが、非置換サンプリングよりも高速な収束をもたらすため、モデルトレーニングでは広く採用されている。
最近の研究では、厳密に選択されたデータ順序付けは、より多くの計算とメモリを使用するコストで、経験的に収束をさらにスピードアップさせることができることが示されている。
グラディエント・バランシング・アルゴリズム(GraB)は、トレーニングと検証の両方のパフォーマンスにおいて、ランダムなリシャッフルよりも優れていることを示す。
- 参考スコア(独自算出の注目度): 39.067886932979874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random reshuffling, which randomly permutes the dataset each epoch, is widely
adopted in model training because it yields faster convergence than
with-replacement sampling. Recent studies indicate greedily chosen data
orderings can further speed up convergence empirically, at the cost of using
more computation and memory. However, greedy ordering lacks theoretical
justification and has limited utility due to its non-trivial memory and
computation overhead. In this paper, we first formulate an example-ordering
framework named herding and answer affirmatively that SGD with herding
converges at the rate $O(T^{-2/3})$ on smooth, non-convex objectives, faster
than the $O(n^{1/3}T^{-2/3})$ obtained by random reshuffling, where $n$ denotes
the number of data points and $T$ denotes the total number of iterations. To
reduce the memory overhead, we leverage discrepancy minimization theory to
propose an online Gradient Balancing algorithm (GraB) that enjoys the same rate
as herding, while reducing the memory usage from $O(nd)$ to just $O(d)$ and
computation from $O(n^2)$ to $O(n)$, where $d$ denotes the model dimension. We
show empirically on applications including MNIST, CIFAR10, WikiText and GLUE
that GraB can outperform random reshuffling in terms of both training and
validation performance, and even outperform state-of-the-art greedy ordering
while reducing memory usage over $100\times$.
- Abstract(参考訳): 各エポックごとにデータセットをランダムに置換するランダムなリシャッフルは、リプレースメントサンプリングよりも収束が速いため、モデルトレーニングで広く採用されている。
最近の研究では、厳格に選択されたデータ順序付けは、計算とメモリをより多く使用するコストで、経験的な収束をさらにスピードアップできることを示している。
しかし、欲望の順序付けは理論的正当性に欠けており、その非自明なメモリと計算オーバーヘッドのために有用性は限られている。
本稿では,まずherding という例順付けフレームワークを定式化し,sgd と herding の和は,ランダムな再帰によって得られる $o(n^{1/3}t^{-2/3})$ よりも高速で,滑らかな非凸目的に対して $o(t^{-2/3})$ で収束することを示す。
メモリオーバヘッドを低減するために、差分最小化理論を利用して、共有型グラディエント・バランシングアルゴリズム(GraB)を提案する。また、メモリ使用量を$O(nd)$から$O(d)$に、計算を$O(n^2)$から$O(n)$に減らし、$d$はモデル次元を表す。
我々は,MNIST, CIFAR10, WikiText, GLUEなどのアプリケーションにおいて,GraBがトレーニングと検証の両方のパフォーマンスにおいてランダムリシャッフルを上回り,また,100\times$以上のメモリ使用量を削減しつつ,最先端のgreedyオーダよりも優れていることを実証的に示す。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation [0.0]
m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。
サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
論文 参考訳(メタデータ) (2023-03-06T15:53:44Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳(メタデータ) (2023-02-13T00:22:28Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳(メタデータ) (2021-06-22T15:50:45Z) - SoS Degree Reduction with Applications to Clustering and Robust Moment
Estimation [3.6042575355093907]
我々は,新しい変数を導入することにより,二乗証明の総和の程度を大幅に減少させる汎用フレームワークを開発した。
クラスタリングとロバストモーメント推定という2つの重要な推定問題に対して,2乗和に基づくアルゴリズムを高速化する。
論文 参考訳(メタデータ) (2021-01-05T13:49:59Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳(メタデータ) (2020-06-10T17:57:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。