Research map / Optimization / Implicit bias and generalization
Implicit Regularization of Decentralized Gradient Descent for Sparse Regression
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.
Shows that decentralized gradient descent on an unregularized over-parameterized Hadamard-product least-squares reformulation, with small initialization and early stopping, recovers the statistically optimal sparse estimator, and proposes a top-s truncated variant (T-DGD) for communication efficiency.
Problem
Decentralized sparse linear regression over mesh networks without explicit l1 regularization; whether decentralized gradient methods can compute statistically optimal sparse solutions via implicit regularization and reduce communication cost.
Approach
Applies DGD to an over-parameterized nonconvex least-squares problem (w = u⊙u − v⊙v) with small initialization and early stopping, instead of LASSO with explicit penalty; analyzes inexact multiplicative updates caused by consensus error by separately controlling consensus errors on support and non-support coordinates; adds top-s truncation of transmitted vectors (T-DGD).
Key results
- Theorem 1 gives conditions (initialization scale, step size, spectral gap rho ≲ d-dependent bound) under which DGD with early stopping achieves the centralized minimax statistical rate O(sigma sqrt(s log d / N)) in l2 error, with stopping time logarithmic in d.
- In simulations, DGD with small initialization matches centralized statistical error, while poorly connected networks (large rho) fail to reach optimal error, indicating a phase transition in network connectivity.
- T-DGD, which transmits only s entries per round, succeeds where truncated LASSO-based decentralized methods fail in the experiments (d=1000, s=5, m=50).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DGD with small initialization and early stopping instead of explicit sparse penalization | Overparameterized decentralized sparse regression · Sparse linear regression | ℓ2 estimation error | Helped |
| Improve network connectivity | DGD · Sparse linear regression | iterations to optimal statistical error | Helped |
| Use a network that does not satisfy the connectivity condition | DGD · Sparse linear regression | statistical error | Hurt |
| Increase initialization scale (ablation) | DGD · Sparse linear regression | statistical error | Hurt |
| Truncate transmitted vectors to their s largest-magnitude elements (ablation) | DGD (T-DGD) · Sparse linear regression | ℓ2 estimation error | No clear effect |
| Use truncated updates when each agent has inadequate samples (ablation) | DGD (T-DGD) · Sparse linear regression, N = 100 | statistical error | Hurt |
| Use truncated updates at higher noise level (ablation) | DGD (T-DGD) · Sparse linear regression, σ = 0.5 | recovery | Hurt |
| Use truncated updates at lower noise level (ablation) | DGD (T-DGD) · Sparse linear regression, σ = 0.1 | recovery | Helped |
| Replace DGD with explicit-regularization decentralized methods | Decentralized sparse regression · Three network connectivity settings | recovery performance | Hurt |
| Apply the same Top-s truncation operator to explicit-regularization decentralized methods (ablation) | CTA-DGD, ATC-DGD, and DGT · Sparse linear regression | recovery | Hurt |
Surprising findings
- Standard DGD without gradient tracking or gradient correction suffices for accurate statistical recovery in heterogeneous data settings, challenging common beliefs in decentralized optimization.
- Naively truncating iterates of existing LASSO-based decentralized methods fails to recover the sparse signal, while T-DGD succeeds.
Limitations
- Requires the global RIP condition with delta ≲ 1/sqrt(s), which is more restrictive than restricted eigenvalue conditions.
- Step size and spectral gap conditions depend on network connectivity; poorly connected networks may fail to achieve optimal error or require multiple communication rounds.
- T-DGD guarantee requires high SNR and sufficient local samples per agent.
Experimental setup
Datasets: synthetic Gaussian linear measurements
Benchmarks: synthetic sparse regression simulations
Metrics: l2 estimation error convergence iterations
Baselines: DGD-CTA (LASSO) DGD-ATC (LASSO) DGT (NetLASSO) Trun-CTA-DGD Trun-ATC-DGD Trun-DGT
Builds on: Hadamard product overparameterization implicit regularization (Vaskevicius et al DGD DGD-CTA DGD-ATC NetLASSO
Closest papers by meaning
- Implicit Regularization for Optimal Sparse Recovery (NeurIPS 2019 · similarity 0.90)
- Implicit Sparse Regularization: The Impact of Depth and Early Stopping (NeurIPS 2021 · similarity 0.90)
- Acceleration in Distributed Sparse Regression (NeurIPS 2022 · similarity 0.89)
- Decentralised Learning with Random Features and Distributed Gradient Descent (ICML 2020 · similarity 0.89)
- Decentralized Accelerated Proximal Gradient Descent (NeurIPS 2020 · similarity 0.88)
- DGD^2: A Linearly Convergent Distributed Algorithm For High-dimensional Statistical Recovery (NeurIPS 2022 · similarity 0.88)
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.