Recovery Guarantees for Distributed-OMP

• URL: http://arxiv.org/abs/2209.07230v2
• Date: Tue, 31 Oct 2023 11:55:54 GMT
• Title: Recovery Guarantees for Distributed-OMP
• Authors: Chen Amiraz, Robert Krauthgamer and Boaz Nadler
• Abstract summary: We study distributed schemes for high-dimensional sparse linear regression. We prove that distributed-OMP schemes recover the support of the regression vector with communication per machine linear in its sparsity and logarithmic in the dimension. Our simulations show that distributed-OMP schemes are competitive with more computationally intensive methods, and in some cases even outperform them.
• Score: 8.393317912360564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study distributed schemes for high-dimensional sparse linear regression, based on orthogonal matching pursuit (OMP). Such schemes are particularly suited for settings where a central fusion center is connected to end machines, that have both computation and communication limitations. We prove that under suitable assumptions, distributed-OMP schemes recover the support of the regression vector with communication per machine linear in its sparsity and logarithmic in the dimension. Remarkably, this holds even at low signal-to-noise-ratios, where individual machines are unable to detect the support. Our simulations show that distributed-OMP schemes are competitive with more computationally intensive methods, and in some cases even outperform them.

Related papers

• Diffusion Generative Modelling for Divide-and-Conquer MCMC [0.0]
  Divide-and-conquer MCMC is a strategy for parallelising Markov Chain Monte Carlo sampling. We propose using diffusion generative modelling to fit density approximations to the subposterior distributions.
  arXiv  Detail & Related papers  (2024-06-17T15:48:46Z)
• Computing Low-Entropy Couplings for Large-Support Distributions [53.00113867130712]
  Minimum-entropy coupling has applications in areas such as causality and steganography. Existing algorithms are either computationally intractable for large-support distributions or limited to specific distribution types. This work addresses these limitations by unifying a prior family of iterative MEC approaches into a generalized partition-based formalism.
  arXiv  Detail & Related papers  (2024-05-29T21:54:51Z)
• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  We consider a joint device selection and aggregate beamforming design with the objectives of minimizing the aggregate error and maximizing the number of selected devices. To tackle the problems in a cost-effective manner, we propose a random aggregate beamforming-based scheme. We additionally use analysis to study the obtained aggregate error and the number of the selected devices when the number of devices becomes large.
  arXiv  Detail & Related papers  (2024-02-20T23:59:45Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• CoVO-MPC: Theoretical Analysis of Sampling-based MPC and Optimal Covariance Design [8.943418808959494]
  We characterize the convergence property of a widely used sampling-based Model Predictive Path Integral Control (MPPI) method. We show that MPPI enjoys at least linear convergence rates when the optimization is quadratic, which covers time-varying LQR systems. Our theoretical analysis directly leads to a novel sampling-based MPC algorithm, CoVo-MPC. Empirically, CoVo-MPC significantly outperforms standard MPPI by 43-54% in both simulations and real-world quad agile control tasks.
  arXiv  Detail & Related papers  (2024-01-14T21:10:59Z)
• Iterative Sketching for Secure Coded Regression [66.53950020718021]
  We propose methods for speeding up distributed linear regression. Specifically, we randomly rotate the basis of the system of equations and then subsample blocks, to simultaneously secure the information and reduce the dimension of the regression problem.
  arXiv  Detail & Related papers  (2023-08-08T11:10:42Z)
• Learning-based Control for PMSM Using Distributed Gaussian Processes with Optimal Aggregation Strategy [16.7267979284111]
  Machine learning techniques are widely employed to infer the unknown part of the system. For practical implementation, distributed GPR is adopted to alleviate the high computational complexity. A control-aware optimal aggregation strategy of distributed GPR for PMSMs is proposed based on the Lyapunov stability theory.
  arXiv  Detail & Related papers  (2023-07-26T03:56:24Z)
• Distributed Sparse Linear Regression under Communication Constraints [4.997371967242497]
  We focus on distributed learning of a sparse linear regression model, under severe communication constraints. In our schemes, individual machines compute debiased lasso estimators, but send to the fusion center only very few values. We show in simulations that our scheme works as well as, and in some cases better, than more communication intensive approaches.
  arXiv  Detail & Related papers  (2023-01-09T08:23:37Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Multiplierless MP-Kernel Machine For Energy-efficient Edge Devices [6.335302509003343]
  We present a novel framework for designing multiplierless kernel machines. The framework uses a piecewise linear (PWL) approximation based on a margin propagation (MP) technique. We propose a hardware-friendly MP-based inference and online training algorithm that has been optimized for a Field Programmable Gate Array (FPGA) platform.
  arXiv  Detail & Related papers  (2021-06-03T16:06:08Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)

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.