# Distributed Sparse Regression via Penalization

arXiv: https://arxiv.org/abs/2111.06530 · HTML: https://mlsanity.com/paper/2111.06530/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 62 references that are in the map.
- First posted on arXiv 12 Nov 2021.

## Builds on (most cited first, 19 of 19)

- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [First-order Newton-type Estimator for Distributed Estimation and Inference](https://mlsanity.com/paper/1811.11368/) (2018)
- [On the Optimality of Averaging in Distributed Statistical Learning](https://mlsanity.com/paper/1407.2724/) (2014)
- [Second-order Guarantees of Distributed Gradient Algorithms](https://mlsanity.com/paper/1809.08694/) (2018)
- [Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems](https://mlsanity.com/paper/1512.09302/) (2015)
- [Communication-efficient sparse regression: a one-shot approach](https://mlsanity.com/paper/1503.04337/) (2015)
- [Subregularity of subdifferential mappings relative to the critical set and KL property of exponent 1/2](https://mlsanity.com/paper/1812.00558/) (2018)

## Built on by (most cited first, 1 of 1)

- [Distributed Sparse Linear Regression under Communication Constraints](https://mlsanity.com/paper/2301.04022/) (2023)

## Abstract (arXiv)

We study sparse linear regression over a network of agents, modeled as an undirected graph (with no centralized node). The estimation problem is formulated as the minimization of the sum of the local LASSO loss functions plus a quadratic penalty of the consensus constraint -- the latter being instrumental to obtain distributed solution methods. While penalty-based consensus methods have been extensively studied in the optimization literature, their statistical and computational guarantees in the high dimensional setting remain unclear. This work provides an answer to this open problem. Our contribution is two-fold. First, we establish statistical consistency of the estimator: under a suitable choice of the penalty parameter, the optimal solution of the penalized problem achieves near optimal minimax rate O(s log d/N) in ℓ2-loss, where s is the sparsity value, d is the ambient dimension, and N is the total sample size in the network -- this matches centralized sample rates. Second, we show that the proximal-gradient algorithm applied to the penalized problem, which naturally leads to distributed implementations, converges linearly up to a tolerance of the order of the centralized statistical error -- the rate scales as O(d), revealing an unavoidable speed-accuracy dilemma.Numerical results demonstrate the tightness of the derived sample rate and convergence rate scalings.