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

arXiv: https://arxiv.org/abs/2210.08371 · HTML: https://mlsanity.com/paper/2210.08371/

## 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 (most cited first, 30 of 52)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [FedBN: Federated Learning on Non-IID Features via Local Batch Normalization](https://mlsanity.com/paper/2102.07623/) (2021)
- [Federated Learning with Matched Averaging](https://mlsanity.com/paper/2002.06440/) (2020)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [iDLG: Improved Deep Leakage from Gradients](https://mlsanity.com/paper/2001.02610/) (2020)
- [Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning](https://mlsanity.com/paper/1702.07464/) (2017)
- [See through Gradients: Image Batch Recovery via GradInversion](https://mlsanity.com/paper/2104.07586/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [A Joint Learning and Communications Framework for Federated Learning over Wireless Networks](https://mlsanity.com/paper/1909.07972/) (2019)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Privacy-preserving Federated Brain Tumour Segmentation](https://mlsanity.com/paper/1910.00962/) (2019)
- [A Survey of Privacy Attacks in Machine Learning](https://mlsanity.com/paper/2007.07646/) (2020)
- [Hacking Smart Machines with Smarter Ones: How to Extract Meaningful Data from Machine Learning Classifiers](https://mlsanity.com/paper/1306.4447/) (2013)
- [Multi-site fMRI Analysis Using Privacy-preserving Federated Learning and Domain Adaptation: ABIDE Results](https://mlsanity.com/paper/2001.05647/) (2020)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [A Framework for Evaluating Gradient Leakage Attacks in Federated Learning](https://mlsanity.com/paper/2004.10397/) (2020)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)

## Built on by (most cited first, 25 of 25)

- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails](https://mlsanity.com/paper/2405.17529/) (2024)
- [A Convergence Theory for Federated Average: Beyond Smoothness](https://mlsanity.com/paper/2211.01588/) (2022)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learning](https://mlsanity.com/paper/2408.13787/) (2024)
- [Federated Gradient Matching Pursuit](https://mlsanity.com/paper/2302.10755/) (2023)
- [Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysis](https://mlsanity.com/paper/2411.06770/) (2024)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2411.10906/) (2024)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)
- [Scaling Federated Linear Contextual Bandits via Sketching](https://mlsanity.com/paper/2605.00500/) (2026)

## 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.