Stability and Generalization of the Decentralized Stochastic Gradient Descent
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Stability and Generalization for Decentralized Markov SGD
Stochastic gradient methods are central to large-scale learning, yet their generalization theory typically relies on independent sampling assumptions. In many practical applications, data are generated by Markov chains a…
Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm
The growing size of available data has attracted increasing interest in solving minimax problems in a decentralized manner for various machine learning tasks. Previous theoretical research has primarily focused on the co…
Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm
This paper presents a new generalization error analysis for Decentralized Stochastic Gradient Descent (D-SGD) based on algorithmic stability. The obtained results overhaul a series of recent works that suggested an incre…
Generalization BoundsStability and Generalization of Stochastic Compositional Gradient Descent Algorithms
Many machine learning tasks can be formulated as a stochastic compositional optimization (SCO) problem such as reinforcement learning, AUC maximization, and meta-learning, where the objective function involves a nested c…
Learning TheoryMeta-LearningUniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters
We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic o…