Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm
This work addresses generalization guarantees for decentralized optimization in machine learning, providing insights that challenge previous assumptions about graph connectivity, though it appears incremental as it refines existing analysis.
The paper tackles the problem of generalization error in Decentralized Stochastic Gradient Descent (D-SGD) by showing that it can achieve generalization bounds similar to classical SGD, regardless of the communication graph, and reveals that poorly-connected graphs can sometimes improve generalization.
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 increased instability due to decentralization and a detrimental impact of poorly-connected communication graphs on generalization. On the contrary, we show, for convex, strongly convex and non-convex functions, that D-SGD can always recover generalization bounds analogous to those of classical SGD, suggesting that the choice of graph does not matter. We then argue that this result is coming from a worst-case analysis, and we provide a refined optimization-dependent generalization bound for general convex functions. This new bound reveals that the choice of graph can in fact improve the worst-case bound in certain regimes, and that surprisingly, a poorly-connected graph can even be beneficial for generalization.