mlsanityData to 14 Oct 2026

Federated Gradient Matching Pursuit

arXiv 2302.10755 ↗First posted 20 Feb 2023cs.LG cs.IT cs.NAcited by 1

Not on the map. Why?

Abstract (arXiv)

Traditional machine learning techniques require centralizing all training data on one server or data hub. Due to the development of communication technologies and a huge amount of decentralized data on many clients, collaborative machine learning has become the main interest while providing privacy-preserving frameworks. In particular, federated learning (FL) provides such a solution to learn a shared model while keeping training data at local clients. On the other hand, in a wide range of machine learning and signal processing applications, the desired solution naturally has a certain structure that can be framed as sparsity with respect to a certain dictionary. This problem can be formulated as an optimization problem with sparsity constraints and solving it efficiently has been one of the primary research topics in the traditional centralized setting. In this paper, we propose a novel algorithmic framework, federated gradient matching pursuit (FedGradMP), to solve the sparsity constrained minimization problem in the FL setting. We also generalize our algorithms to accommodate various practical FL scenarios when only a subset of clients participate per round, when the local model estimation at clients could be inexact, or when the model parameters are sparse with respect to general dictionaries. Our theoretical analysis shows the linear convergence of the proposed algorithms. A variety of numerical experiments are conducted to demonstrate the great potential of the proposed framework -- fast convergence both in communication rounds and computation time for many important scenarios without sophisticated parameter tuning.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 38 of its 68 references that are in the map. First posted on arXiv 20 Feb 2023.

Builds on

38 of 68 references.

References · 38

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 906
  5. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 851
  6. 2019Towards Federated Learning at Scale: System Designcited by 832
  7. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 564
  8. 2021A Field Guide to Federated Optimizationcited by 315
  9. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2019SGD: General Analysis and Improved Ratescited by 207
  12. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 193
26 more
  1. 2019A Survey on Distributed Machine Learningcited by 188
  2. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  3. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  4. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
  5. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  6. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  7. 2020Optimal Client Sampling for Federated Learningcited by 124
  8. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  9. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 107
  10. 2021PPFL: Privacy-preserving Federated Learning with Trusted Execution Environmentscited by 93
  11. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  12. 2021On Large-Cohort Training for Federated Learningcited by 74
  13. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  14. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  15. 2020Federated Composite Optimizationcited by 49
  16. 2021Anarchic Federated Learningcited by 42
  17. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  18. 2020FedSKETCH: Communication-Efficient and Private Federated Learning via Sketchingcited by 20
  19. 2016A Tight Bound of Hard Thresholdingcited by 16
  20. 2014Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraintscited by 13
  21. 2022Fast Composite Optimization and Statistical Recovery in Federated Learningcited by 12
  22. 2018MISSION: Ultra Large-Scale Feature Selection using Count-Sketchescited by 11
  23. 2020Federated Nonconvex Sparse Learningcited by 10
  24. 2019Iterative Hard Thresholding for Low CP-rank Tensor Modelscited by 9
  25. 2020Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applicationscited by 6
  26. 2017Stochastic Greedy Algorithms For Multiple Measurement Vectorscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Federated Domain Generalization: A Surveycited by 25