Research map / Federated learning and privacy / Communication-efficient FL
Compressed and distributed least-squares regression: convergence rates with applications to federated learning
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.
Analyzes compressed least-mean-squares SGD via a linear stochastic approximation framework with weak Hölder-type noise assumptions, showing the asymptotic rate scales with Tr(A H^{-1})/K where A is the algorithm-induced additive noise covariance, and compares unbiased compressors with equal variance.
Problem
Worst-case analyses of compression in distributed/federated SGD treat all unbiased compressors with the same variance bound as equivalent, hiding differences in convergence for least-squares regression.
Approach
Derives non-asymptotic rates for linear stochastic approximation under expected Hölder regularity of the noise field, showing the limit variance depends on the covariance of the algorithm-induced additive noise, which depends on the specific compressor (not just its variance); applies this to single-client and federated (covariate-shift, concept-shift) compressed LMS.
Key results
- Under a Hölder-type noise assumption, the asymptotic variance term scales as Tr(A H^{-1})/K, generalizing the sigma^2 d/K rate of vanilla LMS.
- For diagonal features, sparsification, rand-h and partial participation share the same asymptotic rate, while 1-quantization yields a slower eigenvalue decay and larger trace.
- Sketching (random Gaussian projection) introduces an isotropic noise component causing the trace to depend strongly on the strong-convexity constant mu.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use partial participation instead of sparsification, sketching, or Rand-h | Compressed LMS with standardized features · Features with constant-diagonal covariance | asymptotic convergence rate | Helped |
| Use partial participation instead of sparsification or Rand-h | Compressed LMS · Diagonal feature covariance | asymptotic convergence rate | No clear effect |
| Use partial participation instead of Gaussian random projection | Compressed LMS · Diagonal feature covariance | asymptotic convergence rate | Helped |
| Use sparsification instead of partial participation | Compressed LMS with standardized features · Features with constant-diagonal covariance | asymptotic convergence rate | Hurt |
| Use Rand-h instead of sparsification | Compressed LMS with standardized features · Features with constant-diagonal covariance | asymptotic convergence rate | Hurt |
| Use sketching instead of partial participation | Compressed LMS with standardized features · Features with constant-diagonal covariance | asymptotic convergence rate | Hurt |
| Use quantization instead of sparsification | Compressed LMS with standardized features · Features with constant-diagonal covariance | asymptotic convergence rate | Helped |
| Use quantization instead of sparsification or randomized coordinate selection | Compressed LMS · Standardized features | asymptotic convergence rate | Helped |
| Use quantization instead of sparsification or randomized coordinate selection | Compressed LMS · Independent normalized features | asymptotic convergence rate | Hurt |
| Use partial participation instead of other compressors | Compressed LMS · Non-diagonal feature covariance | asymptotic convergence rate | Helped |
| Use a horizon-dependent step-size γ = K^{-2/5} instead of a constant step-size | Compressed LMS with non-diagonal features · Synthetic data with high eigenvalue decay | excess loss: factor 100 | Helped |
| Use a decreasing step-size instead of a constant step-size | Compressed LMS with non-diagonal features · Synthetic data with high eigenvalue decay | convergence | Helped |
Surprising findings
- Unbiased compressors with identical variance bound omega can yield trace values differing by several orders of magnitude depending on the compressor and feature covariance.
- Partial participation is the only compressor whose induced noise is structured (proportional to H), so it is more robust to ill-conditioning.
Limitations
- Lower-order terms depend on the strong-convexity constant mu, so rates degrade for ill-conditioned problems without regularization.
- Analysis is for least-squares regression with linear-type noise structure; results are theoretical and validated on a single client plus simple federated settings.
- Non-linear compressors like quantization do not satisfy a Lipschitz-in-squared-expectation condition, leading to slower lower-order terms.
Experimental setup
Datasets: quantum cifar-10
Benchmarks: synthetic Gaussian least-squares data quantum cifar-10
Metrics: excess loss of Polyak-Ruppert averaged iterate trace of compressor covariance times H inverse
Baselines: uncompressed LMS 1-quantization sparsification rand-h sketching partial participation
Builds on: Bach and Moulines (2013) linear stochastic approximation Polyak-Ruppert averaging
Closest papers by meaning
- Distributed Sparse Regression via Penalization (NeurIPS 2024 · similarity 0.88)
- Feature-distributed sparse regression: a screen-and-clean approach (NeurIPS 2016 · similarity 0.86)
- Accelerating Federated Learning with Quick Distributed Mean Estimation (ICML 2024 · similarity 0.85)
- EFSkip: A New Error Feedback with Linear Speedup for Compressed Federated Learning with Arbitrary Data Heterogeneity (AAAI 2025 · similarity 0.84)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.83)
- SparsyFed: Sparse Adaptive Federated Learning (ICLR 2025 · 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.