Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914833184587776 |
|---|---|
| author | Bars, Batiste Le Bellet, Aurélien Tommasi, Marc Scaman, Kevin Neglia, Giovanni |
| author_facet | Bars, Batiste Le Bellet, Aurélien Tommasi, Marc Scaman, Kevin Neglia, Giovanni |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_02939 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm Bars, Batiste Le Bellet, Aurélien Tommasi, Marc Scaman, Kevin Neglia, Giovanni Machine Learning 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. |
| title | Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2306.02939 |