Related papers: Stability and Generalization of the Decentralized Stochastic Gradient Descent

Stability and Generalization of the Decentralized Stochastic Gradient Descent

URL: http://arxiv.org/abs/2102.01302v1
Date: Tue, 2 Feb 2021 04:23:23 GMT
Title: Stability and Generalization of the Decentralized Stochastic Gradient Descent
Authors: Tao Sun, Dongsheng Li, Bao Wang
Abstract summary: The stability and generalization of gradient-based methods provide valuable insights into the performance of machine learning models. We first establish the stability and guarantees for the decentralized gradient descent. Our results are built on a few common assumptions and that decentralization deteriorates of for the first time.
Score: 17.63112147669365
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The stability and generalization of stochastic gradient-based methods provide valuable insights into understanding the algorithmic performance of machine learning models. As the main workhorse for deep learning, stochastic gradient descent has received a considerable amount of studies. Nevertheless, the community paid little attention to its decentralized variants. In this paper, we provide a novel formulation of the decentralized stochastic gradient descent. Leveraging this formulation together with (non)convex optimization theory, we establish the first stability and generalization guarantees for the decentralized stochastic gradient descent. Our theoretical results are built on top of a few common and mild assumptions and reveal that the decentralization deteriorates the stability of SGD for the first time. We verify our theoretical findings by using a variety of decentralized settings and benchmark machine learning models.

Related papers

Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
arXiv Detail & Related papers (2023-10-31T11:27:01Z)
Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms [61.59448949684493]
We provide the stability and generalization analysis of compositional descent algorithms built from training examples. We establish the uniform stability results for two popular compositional gradient descent algorithms, namely SCGD and SCSC. We derive-independent excess risk bounds for SCGD and SCSC by trade-offing their stability results and optimization errors.
arXiv Detail & Related papers (2023-07-07T02:40:09Z)
A Unified Momentum-based Paradigm of Decentralized SGD for Non-Convex Models and Heterogeneous Data [0.261072980439312]
We propose a unified paradigm called U.MP, D-MP and GT-D, which provides a convergence guarantee for non general objectives. In theory we provide the convergence analysis objectives two approaches for these non-MP algorithms.
arXiv Detail & Related papers (2023-03-01T02:13:22Z)
Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
arXiv Detail & Related papers (2022-09-19T18:48:00Z)
A simplified convergence theory for Byzantine resilient stochastic gradient descent [0.0]
In distributed learning, a central server trains a model according to updates provided by nodes holding local data samples. In the presence of one or more malicious servers, standard algorithms for training model such as gradient descent (SGD) fail to converge.
arXiv Detail & Related papers (2022-08-25T05:37:14Z)
Enhancing Distributional Stability among Sub-populations [32.66329730287957]
Enhancing the stability of machine learning algorithms under distributional shifts is at the heart of the Out-of-Distribution (OOD) Generalization problem. We propose a novel stable risk minimization (SRM) algorithm to enhance the model's stability w.r.t. Experimental results are consistent with our intuition and validate the effectiveness of our algorithm.
arXiv Detail & Related papers (2022-06-07T03:29:25Z)
Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
This work concentrates on the decentralized setting, which is increasingly important but not well understood. We present lower bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available not only in the decentralized case, but also in the deterministic and non-distributed literature.
arXiv Detail & Related papers (2022-02-06T13:14:02Z)
Training Generative Adversarial Networks by Solving Ordinary Differential Equations [54.23691425062034]
We study the continuous-time dynamics induced by GAN training. From this perspective, we hypothesise that instabilities in training GANs arise from the integration error. We experimentally verify that well-known ODE solvers (such as Runge-Kutta) can stabilise training.
arXiv Detail & Related papers (2020-10-28T15:23:49Z)
Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
arXiv Detail & Related papers (2020-06-15T06:30:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.