Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach

Abstract

Decentralized sparsity learning has attracted a significant amount of attention recently due to its rapidly growing applications. To obtain the robust and sparse estimators, a natural idea is to adopt the non-smooth median loss combined with a ${\ell }_1$ sparsity regularizer. However, most of the existing methods suffer from slow convergence performance caused by the {\em double} non-smooth objective. To accelerate the computation, in this paper, we proposed a decentralized surrogate median regression (deSMR) method for efficiently solving the decentralized sparsity learning problem. We show that our proposed algorithm enjoys a linear convergence rate with a simple implementation. We also investigate the statistical guarantee, and it shows that our proposed estimator achieves a near-oracle convergence rate without any restriction on the number of network nodes. Moreover, we establish the theoretical results for sparse support recovery. Thorough numerical experiments and real data study are provided to demonstrate the effectiveness of our method.

arXiv commentIEEE Transactions on Signal Processing, 2022

References in corpus (14)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• High-dimensional generalized linear models and the lasso
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Distributed Learning in Wireless Sensor Networks
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Monitoring and Optimization for Power Grids: A Signal Processing Perspective
• Sparse Distributed Learning Based on Diffusion Adaptation
• Quantile Regression Under Memory Constraint
• Adaptive robust variable selection
• Distributed Discrete-time Optimization in Multi-agent Networks Using only Sign of Relative State
• Efficient Distributed Learning with Sparsity
• Lower bounds on the smallest eigenvalue of a sample covariance matrix
• Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach

Cited by in corpus (1)

• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques