論文の概要: Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds
- arxiv url: http://arxiv.org/abs/2306.12498v1
- Date: Wed, 21 Jun 2023 18:14:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-23 16:34:07.693547
- Title: Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds
- Title（参考訳）: シャッフルsgdによる経験的リスク最小化 : 初歩的視点と限界の改善
- Authors: Xufeng Cai, Cheuk Yin Lin, Jelena Diakonikolas
- Abstract要約: 勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
- 参考スコア（独自算出の注目度）: 13.858051019755285
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent (SGD) is perhaps the most prevalent optimization
method in modern machine learning. Contrary to the empirical practice of
sampling from the datasets without replacement and with (possible) reshuffling
at each epoch, the theoretical counterpart of SGD usually relies on the
assumption of sampling with replacement. It is only very recently that SGD with
sampling without replacement -- shuffled SGD -- has been analyzed. For convex
finite sum problems with $n$ components and under the $L$-smoothness assumption
for each component function, there are matching upper and lower bounds, under
sufficiently small -- $\mathcal{O}(\frac{1}{nL})$ -- step sizes. Yet those
bounds appear too pessimistic -- in fact, the predicted performance is
generally no better than for full gradient descent -- and do not agree with the
empirical observations. In this work, to narrow the gap between the theory and
practice of shuffled SGD, we sharpen the focus from general finite sum problems
to empirical risk minimization with linear predictors. This allows us to take a
primal-dual perspective and interpret shuffled SGD as a primal-dual method with
cyclic coordinate updates on the dual side. Leveraging this perspective, we
prove a fine-grained complexity bound that depends on the data matrix and is
never worse than what is predicted by the existing bounds. Notably, our bound
can predict much faster convergence than the existing analyses -- by a factor
of the order of $\sqrt{n}$ in some cases. We empirically demonstrate that on
common machine learning datasets our bound is indeed much tighter. We further
show how to extend our analysis to convex nonsmooth problems, with similar
improvements.
- Abstract（参考訳）: 確率勾配降下(SGD)は、おそらく現代の機械学習において最も一般的な最適化手法である。
置換なしでデータセットからサンプリングし、各エポックで(可能な)再シャッフルする経験的な実践とは対照的に、理論上のSGDは置換を伴うサンプリングの仮定に依存している。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
凸有限和問題と$n$成分と各成分関数に対する$L$-平滑性仮定では、十分小さい -- $\mathcal{O}(\frac{1}{nL})$ -- ステップサイズで上と下の境界が一致する。
しかし、これらの境界は悲観的すぎるように見える ― 実際、予測された性能は、完全な勾配降下よりも一般的には良くなく、経験的な観察に一致しない。
本研究では,シャッフルsgdの理論と実践のギャップを狭めるため,一般有限和問題から線形予測器による経験的リスク最小化へ焦点を絞る。
これにより、原始双対的な視点を採り、二辺の巡回座標更新を伴う原始双対法としてSGDを解釈することができる。
この観点から、データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
特に、バウンドは、既存の解析よりもずっと速い収束を予測できます -- 場合によっては$\sqrt{n}$のオーダーの係数によって。
私たちは、一般的な機械学習データセットでは、バウンドの方がずっとタイトであることを実証的に示しています。
さらに、同様の改良を加えながら、解析を非滑らかな問題に展開する方法を示す。
関連論文リスト
- A Unified Analysis for Finite Weight Averaging [50.75116992029417]
Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。
本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
論文 参考訳（メタデータ） (2024-11-20T10:08:22Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex
Optimization [9.019243171993553]
トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。
まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。
近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
論文 参考訳（メタデータ） (2023-03-19T20:24:33Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。