論文の概要: Faster Convergence of Local SGD for Over-Parameterized Models
- arxiv url: http://arxiv.org/abs/2201.12719v3
- Date: Mon, 10 Jun 2024 15:04:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-13 01:45:51.256443
- Title: Faster Convergence of Local SGD for Over-Parameterized Models
- Title（参考訳）: 過パラメータモデルに対する局所SGDの高速収束
- Authors: Tiancheng Qin, S. Rasoul Etesami, César A. Uribe,
- Abstract要約: 現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。
不均一なデータ設定における過パラメータ化関数に対する局所SGD(またはFedAvg)の収束を解析する。
一般凸損失関数に対しては、$O(K/T)$の誤差が成立する。
非剰余関数に対しては、どちらの場合も$O(K/T)$の誤差が証明される。
確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
- 参考スコア（独自算出の注目度）: 1.5504102675587357
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern machine learning architectures are often highly expressive. They are usually over-parameterized and can interpolate the data by driving the empirical loss close to zero. We analyze the convergence of Local SGD (or FedAvg) for such over-parameterized models in the heterogeneous data setting and improve upon the existing literature by establishing the following convergence rates. For general convex loss functions, we establish an error bound of $\O(1/T)$ under a mild data similarity assumption and an error bound of $\O(K/T)$ otherwise, where $K$ is the number of local steps and $T$ is the total number of iterations. For non-convex loss functions we prove an error bound of $\O(K/T)$. These bounds improve upon the best previous bound of $\O(1/\sqrt{nT})$ in both cases, where $n$ is the number of nodes, when no assumption on the model being over-parameterized is made. We complete our results by providing problem instances in which our established convergence rates are tight to a constant factor with a reasonably small stepsize. Finally, we validate our theoretical results by performing large-scale numerical experiments that reveal the convergence behavior of Local SGD for practical over-parameterized deep learning models, in which the $\O(1/T)$ convergence rate of Local SGD is clearly shown.
- Abstract（参考訳）: 現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。
通常は過パラメータ化され、経験的損失を0に近づけることでデータを補間することができる。
ヘテロジニアスなデータ設定における過パラメータ化モデルに対する局所SGD(またはFedAvg)の収束を解析し、以下の収束率を確立することにより既存の文献を改善する。
一般凸損失関数に対しては、軽度のデータ類似性仮定の下で$\O(1/T)$の誤差境界と$\O(K/T)$のエラー境界を定め、そうでなければ、$K$は局所的なステップの数であり、$T$は反復の総数である。
非凸損失関数に対しては、誤差境界が$\O(K/T)$であることを証明する。
これらの境界は、両方の場合において$\O(1/\sqrt{nT})$の最良の前の境界で改善される。
確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
最後に,実測過度学習モデルの局所SGDの収束挙動を明らかにするための大規模数値実験を行い,局所SGDの収束速度を$\O(1/T)$とする理論結果を検証した。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Convergence Analysis of Decentralized ASGD [1.8710230264817358]
本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。
我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
論文 参考訳（メタデータ） (2023-09-07T14:50:31Z) - Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds [12.699376765058137]
勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
論文 参考訳（メタデータ） (2023-06-21T18:14:44Z) - Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳（メタデータ） (2023-06-15T16:30:08Z) - Improved Convergence Rates for Sparse Approximation Methods in
Kernel-Based Learning [48.08663378234329]
カーネル・リッジ・レグレッションやガウシアン・プロセスのようなカーネル・ベース・モデルは機械学習の応用においてユビキタスである。
既存のスパース近似法は計算コストを大幅に削減することができる。
我々は,Nystr"om法と疎変動ガウス過程近似法に対して,新しい信頼区間を提供する。
論文 参考訳（メタデータ） (2022-02-08T17:22:09Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - Gradient-Based Empirical Risk Minimization using Local Polynomial
Regression [39.29885444997579]
この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。
損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
論文 参考訳（メタデータ） (2020-11-04T20:10:31Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。