Topology-aware Generalization of Decentralized SGD
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}{(m/N+1/m+\lambda^2)}$-stable in
expectation in the non-convex non-smooth setting, where $N$ is the total sample
size of the whole system, $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}{(1/N+{({(m^{-1}\lambda^2)}^{\frac{\alpha}{2}}+
m^{-\alpha})}/{N^{1-\frac{\alpha}{2}}})}$ 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 has a positive
correlation 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.