Localized Linear Regression in Networked Data

Abstract

The network Lasso (nLasso) has been proposed recently as an efficient learning algorithm for massive networked data sets (big data over networks). It extends the well-known least absolute shrinkage and selection operator (Lasso) from learning sparse (generalized) linear models to network models. Efficient implementations of the nLasso have been obtained using convex optimization methods lending to scalable message passing protocols. In this paper, we analyze the statistical properties of nLasso when applied to localized linear regression problems involving networked data. Our main result is a sufficient condition on the network structure and available label information such that nLasso accurately learns a localized linear regression model from a few labeled data points. We also provide an implementation of nLasso for localized linear regression by specializing a primaldual method for solving the convex (non-smooth) nLasso problem.

References in corpus (9)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Sampling of graph signals with successive local aggregations
• Network Lasso: Clustering and Optimization in Large Graphs
• A General Analysis of the Convergence of ADMM
• Greedy Sampling of Graph Signals
• Proximal Splitting Methods in Signal Processing
• Localized Lasso for High-Dimensional Regression
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs

Cited by in corpus (5)

• Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs
• On the Duality between Network Flows and Network Lasso
• Federated Learning From Big Data Over Networks
• Pursuit of the Cluster Structure of Network Lasso: Recovery Condition and Non-convex Extension
• Learning Networked Exponential Families with Network Lasso