Research map / Optimization / Distributed and compressed
Sketched Adaptive Distributed Deep Learning: A Sharp Convergence Analysis
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.
Proposes Sketched Adaptive Federated Learning (SAFL), which sends randomly sketched updates to an AMSGrad-style server optimizer, and proves an O(1/sqrt(T)) convergence bound whose sketch size scales only logarithmically in model dimension via Hessian intrinsic dimension.
Problem
Communication-efficient federated learning with adaptive optimizers: existing convergence analyses of compressed adaptive FL show iteration or communication complexity scaling linearly with the number of model parameters d, which is prohibitive for deep models.
Approach
Use unbiased random linear sketching (Gaussian, SRHT, Count-Sketch) of client updates so that the server runs AMSGrad on desketched updates, and bound the entry-wise sketching noise in preconditioners and first moments using the Hessian intrinsic dimension (sum of absolute eigenvalues over the largest), yielding a sketch size b = O(log d) for dimension-independent rates.
Key results
- SAFL with sketch size 4e5 on CIFAR-10 ResNet (42M params) outperforms other compressed optimizers in validation error by a significant margin, with 99% compression.
- On SST-2 with BERT (100M params), SAFL reaches comparable accuracy at sketch size 2e4 (99.98% compression) relative to unsketched training.
- Theory gives a high-probability O(1/sqrt(T)) dimension-independent rate with sketch size b = O(log d) under the intrinsic dimension assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SAFL instead of the compared optimizers at sketch size b=4e5 | ResNet101 on CIFAR-10 (training from scratch) · CIFAR-10 validation | validation error | Helped |
| use SAFL instead of FetchSGD or CDAdam at sketch size b=4e6 | ResNet101 on CIFAR-10 (training from scratch) · CIFAR-10 validation | validation error | Helped |
| use SAFL instead of the compared baseline methods | ViT-Base on CIFAR-10 (fine-tuning) · CIFAR-10 validation | validation error | Helped |
| use SAFL instead of other algorithms at sketch size b=2e5 | BERT on SST2 · SST2 validation | validation error | Helped |
| use SAFL instead of other algorithms at sketch size b=2e6 | BERT on SST2 · SST2 validation | validation error | Helped |
| increase the sketch size (ablation) | SAFL with ResNet101 on CIFAR-10 · CIFAR-10 training | training error | Helped |
| vary the sketch size (ablation) | SAFL with ResNet101 on CIFAR-10 · CIFAR-10 validation | validation error | Mixed |
| increase the sketch size (ablation) | SAFL with BERT · SST2 | convergence speed | Helped |
| reduce the sketch size to extremely tiny values (ablation) | SAFL on CIFAR-10 and SST2 · CIFAR-10 and SST2 validation | convergence | No clear effect |
Surprising findings
- Validation error is not monotonic in sketch size (peak error at b=4e4 on CIFAR-10), while training error is monotonic, suggesting sketching may implicitly improve generalization.
- Extremely small sketch sizes (down to 2e4 for a 100M-parameter BERT) still converge at comparable speed to full-dimensional training.
Limitations
- Analysis relies on a bounded-Hessian-intrinsic-dimension assumption and sub-Gaussian noise assumptions, and the bounds contain many logarithmic and constant factors.
- Experiments are small-scale (5 clients, ResNet/ViT/BERT) and SAFL is stated not to beat production-grade methods.
- Sketching is applied to the concatenated full gradient vector rather than layer-wise.
Experimental setup
Datasets: CIFAR-10 SST-2 (GLUE)
Benchmarks: CIFAR-10 SST-2 (GLUE)
Metrics: validation error training error
Baselines: FetchSGD MARINA CDAdam 1-bit Adam CocktailSGD
Builds on: AMSGrad FetchSGD 1-bit Adam CocktailSGD MARINA
Closest papers by meaning
- Sketching for Distributed Deep Learning: A Sharper Analysis (NeurIPS 2024 · similarity 0.91)
- Communication-efficient Distributed SGD with Sketching (NeurIPS 2019 · similarity 0.88)
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning (ICML 2025 · similarity 0.87)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.86)
- Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers (NeurIPS 2025 · similarity 0.86)
- Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise (ICLR 2025 · similarity 0.86)
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.