Research map / Learning theory and algorithms / Matrix and tensor methods
Distributed Sparse Regression via Penalization
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.
Studies sparse linear regression over a network via a penalized consensus LASSO solved by distributed proximal gradient (DGD-like), proving near-optimal centralized sample rate O(s log d/N) with linear convergence whose rate scales as O(d), i.e., a speed-accuracy dilemma.
Problem
High-dimensional sparse linear regression over a decentralized network without a central node: statistical and computational guarantees of penalty-based consensus LASSO and its distributed proximal gradient method were unknown.
Approach
Formulates the network LASSO as a quadratic consensus-penalized problem, proves a restricted-strong-convexity-like in-network RE condition holds w.h.p. under Gaussian design so the averaged local estimation error matches centralized LASSO rate O(s log d/N) without local sample conditions, and shows the proximal DGD iterates converge linearly to a statistical-precision tolerance at rate scaling wit
Key results
- The averaged local estimation error of the penalized network LASSO matches the O(s log d/N) centralized rate under suitable lambda and gamma, with no condition on local sample size.
- Proximal gradient iterates converge linearly up to a tolerance of the order of the centralized statistical error, with iteration count scaling as O(d m log m/(1-rho)) per the stated bound.
- Experiments show a careful gamma (5e-4 for fully connected, 1e-4 for sparser ER graph with N=220, m=20, d=400) is needed to recover centralized error, and gamma scales roughly as 1/d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a sufficiently small penalty parameter γ | Penalized LASSO on the fully connected synthetic network · Synthetic data, N=220, m=20, d=400 | squared estimation error: γ=5×10^{-4} | Helped |
| Use γ=5×10^{-4} rather than a smaller value on the weakly connected graph | Penalized LASSO on the weakly connected synthetic network · Synthetic data, p=0.1, ρ≈0.973 | squared estimation error: 5×10^{-4} | Hurt |
| Decrease γ to 1×10^{-4} on the weakly connected graph | Penalized LASSO on the weakly connected synthetic network · Synthetic data, p=0.1, ρ≈0.973 | squared estimation error: 1×10^{-4} | Helped |
| Decrease γ as dimension d grows | Penalized LASSO · Synthetic data, dimensions 360, 800, and 1560 | squared estimation error: \mathcal{O}(1/d) | Helped |
| Use a smaller γ for a weaker-connected graph | Penalized LASSO · Synthetic data, fully connected versus weakly connected graphs | squared estimation error: 1/\gamma=\mathcal{O}(d/(1-\rho)) | Helped |
| Apply the distributed proximal-gradient algorithm to the penalized formulation | Penalized LASSO · Synthetic data | optimization error: \mathcal{O}(d) | Helped |
| Increase network size while holding total samples and dimension fixed | Distributed proximal gradient · Complete and Erdős–Rényi graphs | communication rounds: \widetilde{\mathcal{O}}(m) | Mixed |
| Use the distributed method on real data with a suitable γ | Penalized LASSO · eyedata test set | MSE | Helped |
| Decrease γ to improve statistical accuracy | Distributed proximal gradient on real data · eyedata test set, weakly connected graph | MSE | Mixed |
Surprising findings
- Achieving centralized statistical accuracy requires gamma to shrink with dimension, causing the linear convergence rate to degrade as O(d), a speed-accuracy dilemma.
- Naive decentralization of divide-and-conquer methods via local consensus fails to achieve centralized statistical consistency.
Limitations
- Linear convergence rate degrades with dimension d (roughly O(d) iterations), leading to total communication cost O(d^2).
- Theoretical guarantees rely on Gaussian random design and RSC-type conditions; the in-network RE condition is assumed/derived under these assumptions.
- Experiments use modest sizes (d up to 1560) and Monte Carlo with 30 repetitions.
Experimental setup
Datasets: synthetic Gaussian design data eyedata (NormalBeta-Prime package)
Metrics: average l2 estimation error optimization error MSE on test set communication rounds
Baselines: centralized LASSO local LASSO Avg-Debias CSL EDSL
Builds on: LASSO decentralized gradient descent (DGD) restricted eigenvalue condition
Closest papers by meaning
- Efficient Distributed Learning with Sparsity (ICML 2017 · similarity 0.89)
- Feature-distributed sparse regression: a screen-and-clean approach (NeurIPS 2016 · similarity 0.89)
- Compressed and distributed least-squares regression: convergence rates with applications to federated learning (ICML 2025 · similarity 0.88)
- Implicit Regularization of Decentralized Gradient Descent for Sparse Regression (NeurIPS 2024 · similarity 0.84)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.84)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.82)
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.