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

• URL: http://arxiv.org/abs/2202.05498v1
• Date: Fri, 11 Feb 2022 08:16:01 GMT
• Title: Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach
• Authors: Weidong Liu, Xiaojun Mao, Xin Zhang
• Abstract summary: We propose a decentralized surrogate median regression (deSMR) method for efficiently solving the decentralized sparsity learning problem. Our proposed algorithm enjoys a linear convergence rate with a simple implementation. We also establish the theoretical results for sparse support recovery.
• Score: 10.850336820582678
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery [0.0]
  We focus on distributed estimation and support recovery for high-dimensional linear quantile regression. We transform the original quantile regression into the least-squares optimization. An efficient algorithm is developed, which enjoys high computation and communication efficiency.
  arXiv  Detail & Related papers  (2024-05-13T08:32:22Z)
• Decentralized Learning Strategies for Estimation Error Minimization with Graph Neural Networks [94.2860766709971]
  We address the challenge of sampling and remote estimation for autoregressive Markovian processes in a wireless network with statistically-identical agents. Our goal is to minimize time-average estimation error and/or age of information with decentralized scalable sampling and transmission policies.
  arXiv  Detail & Related papers  (2024-04-04T06:24:11Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  This paper studies a distributed multi-agent convex optimization problem. We show that the proposed algorithm converges linearly with an improved rate of convergence than the traditional and adaptive gradient-descent methods. We demonstrate our algorithm's superior performance compared to prominent distributed algorithms for solving real logistic regression problems.
  arXiv  Detail & Related papers  (2021-08-19T13:19:54Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Decentralized Statistical Inference with Unrolled Graph Neural Networks [26.025935320024665]
  We propose a learning-based framework, which unrolls decentralized optimization algorithms into graph neural networks (GNNs) By minimizing the recovery error via end-to-end training, this learning-based framework resolves the model mismatch issue. Our convergence analysis reveals that the learned model parameters may accelerate the convergence and reduce the recovery error to a large extent.
  arXiv  Detail & Related papers  (2021-04-04T07:52:34Z)
• Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference [9.983824799552774]
  This paper develops an efficient distributed inference algorithm, which is robust against a moderate fraction of Byzantine nodes. To the best of our knowledge, this is the first normality result in the setting of Byzantine-robust distributed learning.
  arXiv  Detail & Related papers  (2021-03-04T06:50:52Z)
• Adaptive Serverless Learning [114.36410688552579]
  We propose a novel adaptive decentralized training approach, which can compute the learning rate from data dynamically. Our theoretical results reveal that the proposed algorithm can achieve linear speedup with respect to the number of workers. To reduce the communication-efficient overhead, we further propose a communication-efficient adaptive decentralized training approach.
  arXiv  Detail & Related papers  (2020-08-24T13:23:02Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Gradient tracking and variance reduction for decentralized optimization and machine learning [19.54092620537586]
  Decentralized methods to solve finite-sum problems are important in many signal processing and machine learning tasks. We provide a unified algorithmic framework that combines variance-reduction with gradient tracking to achieve robust performance.
  arXiv  Detail & Related papers  (2020-02-13T07:17:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.