Sharper Generalization Guarantees for Asynchronous SGD: Beyond Lipschitzness, Smoothness and Data Homogeneity

Asynchronous stochastic gradient descent (ASGD) is widely adopted in distributed and federated learning. In this paper, we develop a sharp generalization analysis for ASGD by leveraging the concept of on-average model stability. For convex and smooth objectives, we establish stability and excess risk bounds under minimal assumptions, removing Lipschitz continuity, bounded noise, bounded parameter or data domains, while allowing randomly partitioned data and arbitrary delays. Our bounds are optimistic and explicitly characterize the impact of worker participation, recovering the minimax-optimal rate $O(1/\sqrt{mn})$ in balanced regimes where $mn$ denotes the sample size and implying fast rates under low-noise conditions. We further extend the analysis to non-smooth objectives with Hölder-continuous gradients and to heterogeneous data settings via random ASGD, obtaining non-vacuous excess risk guarantees in both settings. Experimental results support our theoretical findings.

Asynchronous stochastic gradient descent (ASGD) is widely used to accelerate the training of large-scale machine learning tasks. However, this acceleration introduces a bias caused by computers updating and communicating independently. We wondered if this bias affects the performance of ASGD, especially on unseen data. We mathematically quantify this performance by excess risk and use an algorithmic stability framework to analyze it, relaxing the impractical assumptions used in prior theoretical studies. Our results indicate that this bias has a provably limited effect on ASGD's performance, showing that in certain cases, it can perform as well as standard methods while enjoying a faster speed. Also, we prove that a random variant of ASGD performs well even in a more complex case where training data comes from several different distributions. Our findings deepen the theoretical understanding of ASGD under realistic assumptions.