論文の概要: Topology-aware Generalization of Decentralized SGD
- arxiv url: http://arxiv.org/abs/2206.12680v1
- Date: Sat, 25 Jun 2022 16:03:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 14:05:46.870510
- Title: Topology-aware Generalization of Decentralized SGD
- Title（参考訳）: 分散sgdのトポロジー認識による一般化
- Authors: Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song,
Dacheng Tao
- Abstract要約: 本稿では,分散型Valpha-10安定降下(D-SGD)の一般化可能性について検討する。
D-SGDの一般化性は、初期訓練段階における接続性と正の相関があることを証明した。
- 参考スコア（独自算出の注目度）: 89.25765221779288
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the algorithmic stability and generalizability of
decentralized stochastic gradient descent (D-SGD). We prove that the consensus
model learned by D-SGD is $\mathcal{O}{(m/N+1/m+\lambda^2)}$-stable in
expectation in the non-convex non-smooth setting, where $N$ is the total sample
size of the whole system, $m$ is the worker number, and $1-\lambda$ is the
spectral gap that measures the connectivity of the communication topology.
These results then deliver an
$\mathcal{O}{(1/N+{({(m^{-1}\lambda^2)}^{\frac{\alpha}{2}}+
m^{-\alpha})}/{N^{1-\frac{\alpha}{2}}})}$ in-average generalization bound,
which is non-vacuous even when $\lambda$ is closed to $1$, in contrast to
vacuous as suggested by existing literature on the projected version of D-SGD.
Our theory indicates that the generalizability of D-SGD has a positive
correlation with the spectral gap, and can explain why consensus control in
initial training phase can ensure better generalization. Experiments of VGG-11
and ResNet-18 on CIFAR-10, CIFAR-100 and Tiny-ImageNet justify our theory. To
our best knowledge, this is the first work on the topology-aware generalization
of vanilla D-SGD. Code is available at
https://github.com/Raiden-Zhu/Generalization-of-DSGD.
- Abstract（参考訳）: 本稿では,分散確率勾配勾配(D-SGD)のアルゴリズム的安定性と一般化性について検討する。
d-sgd によって学習されたコンセンサスモデルは、n$ がシステム全体のサンプルサイズ、$m$ がワーカー番号、$-\lambda$ が通信トポロジーの接続を測定するスペクトルギャップである非凸非スムース設定の期待値が $\mathcal{o}{(m/n+1/m+\lambda^2)} であることが証明される。
これらの結果は$\mathcal{o}{(1/n+{({(m^{-1}\lambda^2)}^{\frac{\alpha}{2}}+m^{-\alpha})}/{n^{1-\frac{\alpha}{2}}})} 平均の一般化境界を与える。
本理論は,d-sgdの一般化性がスペクトルギャップと正の相関を持つことを示すものであり,初期訓練段階におけるコンセンサス制御がより良い一般化を保証できる理由を説明できる。
CIFAR-10, CIFAR-100, Tiny-ImageNetにおけるVGG-11とResNet-18の実験は、我々の理論を正当化する。
我々の知る限り、これはバニラD-SGDの位相認識一般化に関する最初の研究である。
コードはhttps://github.com/Raiden-Zhu/Generalization-of-DSGDで入手できる。
関連論文リスト
- On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Convergence Analysis of Decentralized ASGD [1.8710230264817358]
本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。
我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
論文 参考訳（メタデータ） (2023-09-07T14:50:31Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。
本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。
1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
論文 参考訳（メタデータ） (2021-10-13T17:50:46Z) - Removing Data Heterogeneity Influence Enhances Network Topology
Dependence of Decentralized SGD [15.112499553818953]
D$2$/Exact-diffusionアルゴリズムの非同相収束特性について検討する。
既存の分散アルゴリズムと比較して、D$2$/Exact-diffusionはネットワークトポロジに最も敏感です。
論文 参考訳（メタデータ） (2021-05-17T17:16:52Z) - SGD Generalizes Better Than GD (And Regularization Doesn't Help) [39.588906680621825]
我々は、勾配勾配(SGD)の一般化性能と全バッチ勾配(GD)の分離結果を与える。
同じステップ数で、GD はオーバーフィットし、$Omega(1)$ generalization error で解を出力することを示した。
本稿では,GDによる経験的リスクの最小化が,基本的には上記の結果を変えるものではないことを論じ,安定性,暗黙バイアス,一般化における学習アルゴリズムの役割を再考する。
論文 参考訳（メタデータ） (2021-02-01T19:18:40Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。