Stochastic gradient descent (SGD) performed in an asynchronous manner plays a
crucial role in training large-scale machine learning models. However, the
generalization performance of asynchronous delayed SGD, which is an essential
metric for assessing machine learning algorithms, has rarely been explored.
Existing generalization error bounds are rather pessimistic and cannot reveal
the correlation between asynchronous delays and generalization. In this paper,
we investigate sharper generalization error bound for SGD with asynchronous
delay $\tau$. Leveraging the generating function analysis tool, we first
establish the average stability of the delayed gradient algorithm. Based on
this algorithmic stability, we provide upper bounds on the generalization error
of $\tilde{\mathcal{O}}(\frac{T-\tau}{n\tau})$ and
$\tilde{\mathcal{O}}(\frac{1}{n})$ for quadratic convex and strongly convex
problems, respectively, where $T$ refers to the iteration number and $n$ is the
amount of training data. Our theoretical results indicate that asynchronous
delays reduce the generalization error of the delayed SGD algorithm. Analogous
analysis can be generalized to the random delay setting, and the experimental
results validate our theoretical findings.

基于生成函数分析工具，我们研究了异步延迟 SGD 的泛化误差上界，结果表明异步延迟减少了延迟 SGD 算法的泛化误差。