# Topology-aware Generalization of Decentralized SGD

Source: [Topology-aware Generalization of Decentralized SGD](<https://www.sota2.com/research/paper/68fa77ea1e209131cea75f36>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:57:15.407Z

Authors: Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, Dacheng Tao

Published: 2022-06-25T16:03:48.000Z

## Abstract

This paper studies the algorithmic stability and generalizability of decentralized stochastic gradient descent (D-SGD). We prove that the consensus model learned by D-SGD is $\\mathcal{O}{(N^{-1}+m^{-1} +\\lambda^2)}$-stable in expectation in the non-convex non-smooth setting, where $N$ is the total sample size, $m$ is the worker number, and $1+\\lambda$ is the spectral gap that measures the connectivity of the communication topology. These results then deliver an $\\mathcal{O}{(N^{-(1+\\alpha)/2}+ m^{-(1+\\alpha)/2}+\\lambda^{1+\\alpha} + \\phi\_{\\mathcal{S}})}$ in-average generalization bound, which is non-vacuous even when $\\lambda$ is closed to $1$, in contrast to vacuous as suggested by existing literature on the projected version of D-SGD. Our theory indicates that the generalizability of D-SGD is positively correlated with the spectral gap, and can explain why consensus control in initial training phase can ensure better generalization. Experiments of VGG-11 and ResNet-18 on CIFAR-10, CIFAR-100 and Tiny-ImageNet justify our theory. To our best knowledge, this is the first work on the topology-aware generalization of vanilla D-SGD. Code is available at https://github.com/Raiden-Zhu/Generalization-of-DSGD.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2206.12680>)

[PDF](<https://arxiv.org/pdf/2206.12680.pdf>)
