Research map / Optimization / Nonconvex and smooth optimization
Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes on-average model stability and generalization bounds for asynchronous SGD without Lipschitz assumptions, including the first non-smooth (Hölder continuous gradient) analysis, with excess-risk bounds showing that moderate asynchronous delay can improve generalization.
Problem
Generalization of asynchronous SGD (ASGD) with delayed gradients is poorly understood: existing bounds are vacuous or require Lipschitz/smooth and quadratic-only assumptions, and no analysis covers non-smooth losses.
Approach
Uses on-average model stability with an approximately non-expansive lemma for delayed gradient updates, replacing the Lipschitz constant with loss values via self-bounding properties; extends to (α,β)-Hölder continuous gradients and yields excess generalization bounds where average delay τ appears as an improving term.
Key results
- Theory gives an on-average stability and generalization bound of O(1/τ + 1/√K) under learning rate c(τ√K)^-1 without Lipschitz assumption, improving on vacuous O(K^τ/n^τ) bound of prior work.
- Excess generalization bound O(1/τ + ||w1-w*||^2/n) for smooth convex losses in the low-noise case (F(w*)=0).
- Experiments on RCV1, CIFAR100 and SST-2 show generalization error decreases as average delay τ increases under learning rate 0.1/τ, consistent with theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase average asynchronous delay while scaling the learning rate inversely with delay | ASGD · general convex problems | generalization error: O(1/τ + 1/√K) | Helped |
| increase average asynchronous delay while scaling the learning rate inversely with delay | ASGD · low-noise convex problems, K ≍ n | excess generalization error: O(1/τ + ∥w1 − w∗∥²/n) | Helped |
| increase average asynchronous delay while scaling the learning rate inversely with delay | ASGD with Hölder-continuous gradients · low-noise convex problems, K ≍ n | excess generalization error: O(1/√τ + ∥w1 − w∗∥^(4α/(1+α))/√n^(1+α)) | Helped |
| choose a better initial model, closer to w∗ | ASGD · general convex problems | algorithmic stability | Helped |
| choose a better initial model, closer to w∗ | ASGD · low-noise convex problems, K ≍ n | excess generalization error: O(1/τ + ∥w1 − w∗∥²/n) | Helped |
| increase the number of training samples | ASGD · low-noise convex problems | excess generalization error: O(1/τ + ∥w1 − w∗∥²/n) | Helped |
| increase the number of training iterations | ASGD · general convex problems | algorithmic stability | Hurt |
| increase the number of training iterations | ASGD · general convex problems | generalization performance | Hurt |
| increase asynchronous delay with learning rate 0.1/τ | ASGD · RCV1 | generalization error | Helped |
| increase asynchronous delay with learning rate 0.1/τ | ResNet18 trained with ASGD · CIFAR100 | generalization error | Helped |
| increase asynchronous delay with learning rate 0.1/τ | BERT trained with ASGD · SST-2 | generalization error | Helped |
Surprising findings
- Larger asynchronous delay improves generalization when learning rate is scaled inversely with delay.
- Under delay-independent constant learning rates, asynchronous training still appears beneficial for generalization, contrary to the pessimistic theoretical bound.
Limitations
- Stability analysis relies on convexity of the loss, so non-convex settings are not covered.
- Experiments approximate on-average stability by removing a random sample rather than replacing sample-by-sample, due to resource limits.
- Generalization bounds in the non-smooth and general case retain a bounded-domain assumption and rely on the learning rate scaling with delay.
Experimental setup
Datasets: RCV1 CIFAR10 CIFAR100 SST-2
Benchmarks: RCV1 CIFAR100 SST-2
Metrics: generalization error (train-test error gap) model stability ||A(S)-A(S^(i))||^2
Baselines: Regatti et al. ASGD uniform stability bound Deng et al. ASGD average stability bound Lei and Ying SGD bounds
Builds on: Lei and Ying on-average model stability Hardt et al. uniform stability of SGD Stich and Karimireddy ASGD convergence Deng et al. ASGD average stability
Closest papers by meaning
- Sharper Generalization Guarantees for Asynchronous SGD: Beyond Lipschitzness, Smoothness and Data Homogeneity (ICML 2026 · similarity 0.95)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.91)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.91)
- Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity (ICML 2025 · similarity 0.89)
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.89)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.