論文の概要: Faster Convergence of Local SGD for Over-Parameterized Models
- arxiv url: http://arxiv.org/abs/2201.12719v1
- Date: Sun, 30 Jan 2022 04:05:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 18:26:22.507377
- Title: Faster Convergence of Local SGD for Over-Parameterized Models
- Title(参考訳): 過パラメータモデルに対する局所SGDの高速収束
- Authors: Tiancheng Qin, S. Rasoul Etesami and C\'esar A. Uribe
- Abstract要約: 現代の機械学習は、経験的損失をゼロにすることでデータを高度に表現的に補間する。
我々は、$O(K/T)に縛られるエラーを示す。
このような収束率を合理的に小さなステップで厳密な例を提供する。
- 参考スコア(独自算出の注目度): 2.3572498744567123
- 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. We show an error bound of $\O(\exp(-T))$ for strongly-convex
loss functions, where $T$ is the total number of iterations. 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. We also extend our results for non-convex loss
functions by proving an error bound of $\O(K/T)$. Before our work, the
best-known convergence rate for strongly-convex loss functions was
$\O(\exp(-T/K))$, and none existed for general convex or non-convex loss
functions under the overparameterized setting. We complete our results by
providing problem instances in which such convergence rates are tight to a
constant factor under a reasonably small stepsize scheme. Finally, we validate
our theoretical results using numerical experiments on real and synthetic data.
- Abstract(参考訳): 現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。
通常は過パラメータ化され、経験的損失を0に近づけることでデータを補間することができる。
ヘテロジニアスなデータ設定における過パラメータ化モデルに対する局所SGD(またはFedAvg)の収束を分析し、以下の収束率を確立することにより既存の文献を改善する。
強凸損失関数に対して$\o(\exp(-t))$の誤差境界を示し、ここで$t$は反復の総数である。
一般凸損失関数に対しては、軽度のデータ類似性仮定の下で$\O(1/T)$の誤差境界と$\O(K/T)$のエラー境界を定め、そうでなければ$K$は局所的なステップの数である。
また、誤差境界が$\O(K/T)$であることを証明することで、非凸損失関数に対する結果を拡張する。
我々の研究以前は、強凸損失関数の最もよく知られた収束率は$\o(\exp(-t/k))$であり、オーバーパラメータ設定下では一般凸関数や非凸損失関数には存在しなかった。
我々は,そのような収束率を,合理的に小さなステップ化スキームの下で定数因子に密接な問題インスタンスを提供することにより,この結果を完成させる。
最後に,実データと合成データの数値実験を用いて理論的結果を検証する。
関連論文リスト
- Globally Convergent Accelerated Algorithms for Multilinear Sparse
Logistic Regression with $\ell_0$-constraints [2.323238724742687]
多重線形ロジスティック回帰は多次元データ解析の強力なツールである。
本稿では,$ell_0$-MLSRを解くために,アクセラレーションされた近位置換最小値MLSRモデルを提案する。
また、APALM$+$が一階臨界点に大域収束し、クルディ・ロジャシエヴィチ性質を用いて収束を確立することも示している。
論文 参考訳(メタデータ) (2023-09-17T11:05:08Z) - Asymptotic Characterisation of Robust Empirical Risk Minimisation
Performance in the Presence of Outliers [18.455890316339595]
我々は,次元$d$とデータ点数$n$が固定比$alpha=n/d$で分岐した場合,高次元の線形回帰について検討し,出力率を含むデータモデルについて検討する。
我々は、$ell$-regularized $ell$, $ell_$, Huber損失を用いて、経験的リスク最小化(ERM)のパフォーマンスの正確性を提供する。
論文 参考訳(メタデータ) (2023-05-30T12:18:39Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Statistical Hypothesis Testing Based on Machine Learning: Large
Deviations Analysis [15.605887551756933]
機械学習(ML)分類手法の性能、特に誤差確率がゼロに収束する速度について検討する。
例えば $sim expleft(-n,I + o(n) right) のように指数関数的に消滅する誤差確率を示すMLの数学的条件を提供する。
言い換えれば、分類誤差確率はゼロに収束し、その速度はトレーニング用に利用可能なデータセットの一部で計算できる。
論文 参考訳(メタデータ) (2022-07-22T08:30:10Z) - $\alpha$-GAN: Convergence and Estimation Guarantees [7.493779672689531]
一般CPE損失関数 GAN の min-max 最適化と、関連する$f$-divergences の最小化との対応性を証明する。
次に、$alpha$-GAN を $alpha$-loss で定義し、いくつかの GAN を補間し、有元発散の最小化に対応する。
論文 参考訳(メタデータ) (2022-05-12T23:26:51Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - Gradient-Based Empirical Risk Minimization using Local Polynomial
Regression [39.29885444997579]
この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。
損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
論文 参考訳(メタデータ) (2020-11-04T20:10:31Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-18T02:18:44Z) - Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。
実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
論文 参考訳(メタデータ) (2020-07-05T18:58:47Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳(メタデータ) (2020-06-09T02:05:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。