mlsanityData to 14 Oct 2026

Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability

arXiv 2210.08371 ↗First posted 15 Oct 2022cs.LG cs.CRcited by 25

Not on the map. Why?

Abstract (arXiv)

Sketching is one of the most fundamental tools in large-scale machine learning. It enables runtime and memory saving via randomly compressing the original large problem into lower dimensions. In this paper, we propose a novel sketching scheme for the first order method in large-scale distributed learning setting, such that the communication costs between distributed agents are saved while the convergence of the algorithms is still guaranteed. Given gradient information in a high dimension d, the agent passes the compressed information processed by a sketching matrix R∈ ℝs× d with sll d, and the receiver de-compressed via the de-sketching matrix R^top to ``recover'' the information in original dimension. Using such a framework, we develop algorithms for federated learning with lower communication costs. However, such random sketching does not protect the privacy of local data directly. We show that the gradient leakage problem still exists after applying the sketching technique by presenting a specific gradient attack method. As a remedy, we prove rigorously that the algorithm will be differentially private by adding additional random noises in gradient information, which results in a both communication-efficient and differentially private first order approach for federated learning tasks. Our sketching scheme can be further generalized to other learning settings and might be of independent interest itself.

Key facts. Cited by 25 papers in the map (data through 14 Oct 2026). Builds on 52 of its 106 references that are in the map. First posted on arXiv 15 Oct 2022.

Builds on

52 of 106 references.

References · 52

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2022Generative Adversarial Networkscited by 5,627
  3. 2019Advances and Open Problems in Federated Learningcited by 3,046
  4. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,281
  5. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  6. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  7. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  8. 2018Federated Learning with Non-IID Datacited by 1,108
  9. 2019Deep Leakage from Gradientscited by 1,021
  10. 2015The Limitations of Deep Learning in Adversarial Settingscited by 790
  11. 2020Inverting Gradients -- How easy is it to break privacy in federated learning?cited by 712
  12. 2018Local SGD Converges Fast and Communicates Littlecited by 605
38 more
  1. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 571
  2. 2020Federated Learning with Matched Averagingcited by 564
  3. 2018Exploiting Unintended Feature Leakage in Collaborative Learningcited by 520
  4. 2020iDLG: Improved Deep Leakage from Gradientscited by 382
  5. 2017Deep Models Under the GAN: Information Leakage from Collaborative Deep Learningcited by 334
  6. 2021See through Gradients: Image Batch Recovery via GradInversioncited by 326
  7. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2019A Joint Learning and Communications Framework for Federated Learning over Wireless Networkscited by 263
  10. 2018Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learningcited by 246
  11. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  12. 2019Privacy-preserving Federated Brain Tumour Segmentationcited by 169
  13. 2020A Survey of Privacy Attacks in Machine Learningcited by 146
  14. 2013Hacking Smart Machines with Smarter Ones: How to Extract Meaningful Data from Machine Learning Classifierscited by 130
  15. 2020Multi-site fMRI Analysis Using Privacy-preserving Federated Learning and Domain Adaptation: ABIDE Resultscited by 122
  16. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  17. 2020A Framework for Evaluating Gradient Leakage Attacks in Federated Learningcited by 64
  18. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  19. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  20. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  21. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  22. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  23. 2017Relative Error Tensor Low Rank Approximationcited by 45
  24. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  25. 2016Defeating Image Obfuscation with Deep Learningcited by 43
  26. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  27. 2014Optimal CUR Matrix Decompositionscited by 29
  28. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  29. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22
  30. 2022A Sublinear Adversarial Training Algorithmcited by 22
  31. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  32. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  33. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  34. 2022Dynamic Tensor Product Regressioncited by 17
  35. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  36. 2019"The Squawk Bot": Joint Learning of Time Series and Text Data Modalities for Automated Financial Information Filteringcited by 13
  37. 2016Distributed Low Rank Approximation of Implicit Functions of a Matrixcited by 12
  38. 2020Improved Guarantees for k-means++ and k-means++ Parallelcited by 12

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 14; 2024: 6; 2025: 2; 2026: 1.

25 papers.

Sort:

By area:

  1. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  2. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  3. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 30
  4. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  5. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  6. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  7. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  8. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  9. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  10. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  11. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  12. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
13 more
  1. 2023Adaptive Compression in Federated Learning via Side Informationcited by 6
  2. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  3. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 5
  4. 2022A Convergence Theory for Federated Average: Beyond Smoothnesscited by 4
  5. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  6. 2024Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learningcited by 2
  7. 2023Federated Gradient Matching Pursuitcited by 1
  8. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1
  9. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  10. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  11. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  12. 2025Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programmingcited by 0
  13. 2026Scaling Federated Linear Contextual Bandits via Sketchingcited by 0