Distributed Sparse Linear Regression

By Gonzalo Mateos, Juan Andrés Bazerque, Georgios B. Giannakis. 2010

531 citations recorded by the source corpus.

The Lasso is a popular technique for joint estimation and continuous variable selection, especially well-suited for sparse and possibly under-determined linear regression problems. This paper develops algorithms to estimate the regression coefficients via Lasso when the training data are distributed across different agents, and their communication to a central processing unit is prohibited for e.g., communication cost or privacy reasons. A motivating application is explored in the context of wireless communications, whereby sensing cognitive radios collaborate to estimate the radio-frequency power spectrum density. Attaining different tradeoffs between complexity and convergence speed, three novel algorithms are obtained after reformulating the Lasso into a separable form, which is iteratively minimized using the alternating-direction method of multipliers so as to gain the desired degree of parallelization. Interestingly, the per agent estimate updates are given by simple soft-thresholding operations, and inter-agent communication overhead remains at affordable level. Without exchanging elements from the different training sets, the local estimates consent to the global Lasso solution, i.e., the fit that would be obtained if the entire data set were centrally available. Numerical experiments with both simulated and real data demonstrate the merits of the proposed distributed schemes, corroborating their convergence and global optimality. The ideas in this paper can be easily extended for the purpose of fitting related models in a distributed fashion, including the adaptive Lasso, elastic net, fused Lasso and nonnegative garrote.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “Some algorithms aim at more specific optimization tasks such as distributed lasso regression [11], distributed support vector machines [12], and distributed random vector functional-link networks [13].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “Examples and works include decentralized averaging [7,15,34], learning [9,22,26], estimation [1,2,16,18, 29], sparse optimization [19, 35], and low-rank matrix completion [20] problems.”
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization (2013, methodology): “Then we develop the decentralized ADMM approach and provide a simpliﬁed decentralized algorithm (see Section II-B).”
Fast Distributed Gradient Methods (2011, methodology): “) In addition to distributed gradient methods, the literature also proposes distributed augmented Lagrangian dual or ordinary dual methods [5], [21]–[27].”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “The resulting algorithms include distributed dual decomposition [65] and decentralized alternating direction method of multipliers (ADMM) [5, 32].”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, background): “The goal is to cooperatively estimate the radio-frequency power spectrum density through minimizing a loss function deﬁned over the entire measured data by the sensors, which are scattered across a large geographical area [18].”
On Nonconvex Decentralized Gradient Descent (2016, background): “Some typical applications include: (i) the distributed compressed sensing problems [14], [30], [39], [45], [49]; (ii) distributed consensus [9], [29], [55], [58], [61], [69]; (iii) distributed and parallel machine learning [15], [21], [33], [43], [55].”
Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development (2017, background): “However, distributed ADMM ar X iv :1 70 2.”
Online Learning over a Decentralized Network Through ADMM (2015, unknown): “The decentralized ADMM has found successful applications in wireless sensor networks, computer networks, smart grids, etc [15–18].”
Distributed learning for Random Vector Functional-Link networks (2015, methodology): “In cases where, on a node, Nk B, we can exploit the matrix inversion lemma to obtain a more convenient matrix inversion step [23]: Hk Hk þ cI 1 1⁄4 c 1 I Hk cIþHkH T k Hk h i : ð28Þ”
DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs (2017, background): “D ISTRIBUTED computation and optimization have gained great interests due to their widespread applications in, e.g., large-scale machine learning [1], [2], model predictive con-trol [3], cognitive networks [4], [5], source localization [6], [7], resource scheduling [8], and message routing [9].”
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers (2016, methodology): “We consider solving the Lasso problem in a distributed way [30]:”
Quantized consensus ADMM for multi-agent distributed optimization (2015, background): “A tightupper bound on the consensus error is also obtained which does not depend on the size of the network.”
QD-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations (2012, background): “The existing literature on distributed optimization (see, for example, [36], [37], [38], [39], [40]) mostly consider static scenarios, in which, broadly the network goal is to minimize the sum (or average) of static (deterministic) local objectives, with each agent only aware of its local objective”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, background): “, 2015), distributed and parallel machine learning (Forero et al., 2011; Mateos et al., 2010; Shalev-Shwartz & Zhang, 2013), to distributed signal processing (Schizas et al.”
A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, background): “…and is a sparsity-promoting regularizer such as the -norm [4], [5]; (iii) optimization problems with per-agent constraints, where is a differentiable objective function of agent and is the indicator function of the constraint set of agent , that is, if satisﬁes the constraint and otherwise [6]–[8].”
Multi-agent mirror descent for decentralized stochastic optimization (2015, background): “I. INTRODUCTION This paper considers a network of agents that cooperate to solve the composite stochastic optimization problem, minimize E ⇠ [F (x, ⇠)] + (x) (1) with decision variable x 2 Rd in a decentralized manner.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “, 2018) and distributed computing (Shamma, 2008; Mateos et al., 2010).”