論文の概要: Fast Convergence of Random Reshuffling under Over-Parameterization and
the Polyak-\L ojasiewicz Condition
- arxiv url: http://arxiv.org/abs/2304.00459v1
- Date: Sun, 2 Apr 2023 06:00:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-04 17:58:01.255986
- Title: Fast Convergence of Random Reshuffling under Over-Parameterization and
the Polyak-\L ojasiewicz Condition
- Title（参考訳）: 過パラメータ化下におけるランダムリシャッフルの高速収束とポリアック・オジャシエヴィチ条件
- Authors: Chen Fan, Christos Thrampoulidis, Mark Schmidt
- Abstract要約: ランダムリシャッフル法(RR)として知られるサンプリング無勾配勾配勾配勾配(SGD)の収束特性について検討する。
RRは各エポックの開始時にデータのランダムな置換を選択し、各サンプルは置換から次のサンプルを選択する。
- 参考スコア（独自算出の注目度）: 41.58274719943315
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Modern machine learning models are often over-parameterized and as a result
they can interpolate the training data. Under such a scenario, we study the
convergence properties of a sampling-without-replacement variant of stochastic
gradient descent (SGD) known as random reshuffling (RR). Unlike SGD that
samples data with replacement at every iteration, RR chooses a random
permutation of data at the beginning of each epoch and each iteration chooses
the next sample from the permutation. For under-parameterized models, it has
been shown RR can converge faster than SGD under certain assumptions. However,
previous works do not show that RR outperforms SGD in over-parameterized
settings except in some highly-restrictive scenarios. For the class of
Polyak-\L ojasiewicz (PL) functions, we show that RR can outperform SGD in
over-parameterized settings when either one of the following holds: (i) the
number of samples ($n$) is less than the product of the condition number
($\kappa$) and the parameter ($\alpha$) of a weak growth condition (WGC), or
(ii) $n$ is less than the parameter ($\rho$) of a strong growth condition
(SGC).
- Abstract（参考訳）: 現代の機械学習モデルは、しばしば過パラメータ化され、結果としてトレーニングデータを補間することができる。
このような場合,確率勾配降下 (sgd) のサンプリング・アウト・リプレースメント変種であるランダム・リシャフリング (rr) の収束特性について検討する。
イテレーション毎にデータを置換してサンプリングするsgdとは異なり、rrは各エポックの開始時にデータのランダムな順列を選択し、各イテレーションは順列から次のサンプルを選択する。
パラメータ以下のモデルでは、RRは特定の仮定の下でSGDよりも高速に収束することが示されている。
しかし、以前の研究では、rr が過度にパラメータ化された環境で sgd を上回ることは示されていない。
Polyak-\L ojasiewicz (PL) 関数のクラスについて、以下のいずれかが成り立つとき、RR は過パラメータ設定で SGD より優れていることを示す。
一 サンプル(n$)の数は、条件番号(\kappa$)の製品及び弱成長条件(WGC)のパラメータ(\alpha$)の製品より少ない。
(ii)$n$は、強成長条件(sgc)のパラメータ($\rho$)よりも少ない。
関連論文リスト
- Effect of Random Learning Rate: Theoretical Analysis of SGD Dynamics in Non-Convex Optimization via Stationary Distribution [6.144680854063938]
本研究では,その収束特性を明らかにするために,ランダムな学習率を持つ勾配降下(SGD)の変種を考察する。
ポアソンSGDによって更新されたパラメータの分布は、弱い仮定の下で定常分布に収束することを示した。
論文 参考訳（メタデータ） (2024-06-23T06:52:33Z) - Asymptotics of Random Feature Regression Beyond the Linear Scaling
Regime [22.666759017118796]
機械学習の最近の進歩は、トレーニングデータの近くにトレーニングされた過度にパラメータ化されたモデルを使用することによって達成されている。
モデル複雑性と一般化はパラメータ数$p$にどのように依存するか?
特に、RFRRは近似と一般化パワーの直感的なトレードオフを示す。
論文 参考訳（メタデータ） (2024-03-13T00:59:25Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - Preconditioned Score-based Generative Models [49.88840603798831]
直感的な加速度法はサンプリングの繰り返しを減らし、しかしながら重大な性能劣化を引き起こす。
本稿では,行列プレコンディショニングを利用したモデル非依存型bfem事前条件拡散サンプリング(PDS)手法を提案する。
PDSは、バニラSGMのサンプリングプロセスを限界余剰計算コストで変更し、モデルの再訓練を行わない。
論文 参考訳（メタデータ） (2023-02-13T16:30:53Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Characterizing & Finding Good Data Orderings for Fast Convergence of
Sequential Gradient Methods [0.0]
我々は、順序が収束速度に及ぼす影響を定量化し、選択された置換列に基づいて収束境界を求める。
我々は、訓練中に優れた順序を選択するための欲求アルゴリズムを開発し、RRよりも優れた性能(精度が14%以上)を達成した。
論文 参考訳（メタデータ） (2022-02-03T20:38:42Z) - Faster Convergence of Local SGD for Over-Parameterized Models [1.5504102675587357]
現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。
不均一なデータ設定における過パラメータ化関数に対する局所SGD(またはFedAvg)の収束を解析する。
一般凸損失関数に対しては、$O(K/T)$の誤差が成立する。
非剰余関数に対しては、どちらの場合も$O(K/T)$の誤差が証明される。
確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
論文 参考訳（メタデータ） (2022-01-30T04:05:56Z) - Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent:
Convergence Guarantees and Empirical Benefits [21.353189917487512]
勾配降下(SGD)とその変種は、機械学習問題のアルゴリズムとして確立されている。
我々は、最小バッチSGDが全ログ類似損失関数の臨界点に収束することを証明して一歩前進する。
我々の理論的な保証は、核関数が指数的あるいは固有デカイを示すことを前提としている。
論文 参考訳（メタデータ） (2021-11-19T22:28:47Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳（メタデータ） (2021-10-13T17:47:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。