Research map / Federated learning and privacy / Communication-efficient FL
Sketching for Distributed Deep Learning: A Sharper 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.
Gives a dimension-independent convergence analysis for sketching-based distributed learning (Count-Sketch, no Top-r or heavy-hitter assumption) by exploiting restricted strong smoothness and predictor-Hessian spectrum of deep networks.
Problem
Existing convergence bounds for sketched distributed/federated deep learning scale with the ambient parameter dimension p, contradicting empirical success; prior dimension-free fixes need heavy-hitter assumptions and Top-r with error feedback.
Approach
Replace global isotropic smoothness with restricted strong smoothness (RSS) and the predictor Hessian eigenspectrum (intrinsic dimension kappa) so that the sketch-desketch error does not pick up a factor of p, yielding unbiased sketching without Top-r or error feedback.
Key results
- Theory: sketch dimension b needs only polylog(p) dependence, and communication complexity depends on kappa rather than ambient dimension p, improving on Song et al. (2021).
- Experiment: Count-Sketch distributed learning (Algorithm 1) performs competitively with FetchSGD on ResNet-18 / CIFAR-10 with 100 clients, 5 local full-batch iterations.
- Empirical Hessian: estimated kappa (sum of absolute predictor Hessian eigenvalues over max) is much smaller than p for ResNet-18 on CIFAR-10 subset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Count-Sketch without a server-side Top-r step | Sketch-DL (Algorithm 1), compared with FetchSGD · CIFAR-10 | accuracy | No clear effect |
Surprising findings
- Plain Count-Sketch without Top-r or error feedback performs competitively with FetchSGD, contrary to pessimistic dimension-dependent bounds.
Limitations
- Analysis for federated learning with client dropout left to future work
- Multi-local-step analysis requires bounded gradient assumption
- No differential privacy analysis; error-feedback-free approach DP compatibility not evaluated
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: test accuracy vs communication
Baselines: FetchSGD local Top-r Song et al. (2021) sketching bound
Builds on: FetchSGD Song et al. sketching analysis restricted strong smoothness (Banerjee et al.) Top-r sparsification
Closest papers by meaning
- Sketched Adaptive Distributed Deep Learning: A Sharp Convergence Analysis (NeurIPS 2025 · similarity 0.91)
- Efficient Sketches for Training Data Attribution and Studying the Loss Landscape (NeurIPS 2024 · similarity 0.86)
- SketchINR: A First Look into Sketches as Implicit Neural Representations (CVPR 2024 · similarity 0.85)
- Sketch Down the FLOPs: Towards Efficient Networks for Human Sketch (CVPR 2025 · similarity 0.84)
- FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning (AAAI 2024 · similarity 0.84)
- It's All About Your Sketch: Democratising Sketch Control in Diffusion Models (CVPR 2024 · similarity 0.83)
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.