# PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 41 references that are in the map.
- First posted on arXiv 4 May 2024.

## Builds on (most cited first, 26 of 26)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Cost-Effective Federated Learning Design](https://mlsanity.com/paper/2012.08336/) (2020)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Efficient Privacy-Preserving Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1910.13659/) (2019)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Distributed Training of Deep Learning Models: A Taxonomic Perspective](https://mlsanity.com/paper/2007.03970/) (2020)
- [The Value of Collaboration in Convex Machine Learning with Differential Privacy](https://mlsanity.com/paper/1906.09679/) (2019)
- [Private and Communication-Efficient Edge Learning: A Sparse Differential Gaussian-Masking Distributed SGD Approach](https://mlsanity.com/paper/2001.03836/) (2020)
- [Tailoring Gradient Methods for Differentially-Private Distributed Optimization](https://mlsanity.com/paper/2202.01113/) (2022)
- [Asynchronous Federated Learning with Differential Privacy for Edge Intelligence](https://mlsanity.com/paper/1912.07902/) (2019)
- [LEASGD: an Efficient and Privacy-Preserving Decentralized Algorithm for Distributed Learning](https://mlsanity.com/paper/1811.11124/) (2018)

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

- [DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication](https://mlsanity.com/paper/2512.13583/) (2025)
- [Client Clustering Meets Knowledge Sharing: Enhancing Privacy and Robustness in Personalized Peer-to-Peer Learning](https://mlsanity.com/paper/2506.20413/) (2025)
- [ADP-VRSGP: Decentralized Learning with Adaptive Differential Privacy via Variance-Reduced Stochastic Gradient Push](https://mlsanity.com/paper/2510.20157/) (2025)
- [Private Decentralized Optimization with Noise Reduction and Bias Correction](https://mlsanity.com/paper/2609.27658/) (2026)

## Abstract (arXiv)

In this paper, we propose a differentially private decentralized learning method (termed PrivSGP-VR) which employs stochastic gradient push with variance reduction and guarantees (ε, δ)-differential privacy (DP) for each node. Our theoretical analysis shows that, under DP Gaussian noise with constant variance, PrivSGP-VR achieves a sub-linear convergence rate of O(1/√nK), where n and K are the number of nodes and iterations, respectively, which is independent of stochastic gradient variance, and achieves a linear speedup with respect to n. Leveraging the moments accountant method, we further derive an optimal K to maximize the model utility under certain privacy budget in decentralized settings. With this optimized K, PrivSGP-VR achieves a tight utility bound of Oleft( √dlog left( frac1δ right)/(√nJε) right), where J and d are the number of local samples and the dimension of decision variable, respectively, which matches that of the server-client distributed counterparts, and exhibits an extra factor of 1/√n improvement compared to that of the existing decentralized counterparts, such as A(DP)2SGD. Extensive experiments corroborate our theoretical findings, especially in terms of the maximized utility with optimized K, in fully decentralized settings.