2023/06/05 by Batiste Le Bars, Aurélien Bellet, Bars, Batiste Le +7 · 4 citations
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2306.02939
openalex publication_date 2023/06/05 · openalex created_date 2023/06/07 · openalex updated_date 2026/07/30
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.