mlsanityData to 7 Oct 2026

Recovery Guarantees for Distributed-OMP

arXiv 2209.07230 ↗First posted 15 Sep 2022stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 13 of its 76 references that are in the map. First posted on arXiv 15 Sep 2022.

Builds on

13 of 76 references.

References · 13

  1. 2015Best Subset Selection via a Modern Optimization Lenscited by 99
  2. 2016CoCoA: A General Framework for Communication-Efficient Distributed Optimizationcited by 69
  3. 2016Efficient Distributed Learning with Sparsitycited by 38
  4. 2013Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimationcited by 23
  5. 2014On the Optimality of Averaging in Distributed Statistical Learningcited by 14
  6. 2019Distributed Learning with Sublinear Communicationcited by 9
  7. 2021Clustered Federated Learning via Generalized Total Variation Minimizationcited by 7
  8. 2021Distributed Sparse Normal Means Estimation with Sublinear Communicationcited by 3
  9. 2020The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penaltycited by 2
  10. 2021Distributed Sparse Feature Selection in Communication-Restricted Networkscited by 2
  11. 2015Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approachcited by 1
  12. 2016Distributed recovery of jointly sparse signals under communication constraintscited by 1
1 more
  1. 2019Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noisecited by 1

Built on by

Not cited yet.