# The Relative Gaussian Mechanism and its Application to Private Gradient Descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 29 Aug 2023.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [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)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization](https://mlsanity.com/paper/2102.04259/) (2021)
- [Private optimization in the interpolation regime: faster rates and hardness results](https://mlsanity.com/paper/2210.17070/) (2022)

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

- [BadGD: A unified data-centric framework to identify gradient descent vulnerabilities](https://mlsanity.com/paper/2405.15979/) (2024)

## Abstract (arXiv)

The Gaussian Mechanism (GM), which consists in adding Gaussian noise to a vector-valued query before releasing it, is a standard privacy protection mechanism. In particular, given that the query respects some L2 sensitivity property (the L2 distance between outputs on any two neighboring inputs is bounded), GM guarantees R'enyi Differential Privacy (RDP). Unfortunately, precisely bounding the L2 sensitivity can be hard, thus leading to loose privacy bounds. In this work, we consider a Relative L2 sensitivity assumption, in which the bound on the distance between two query outputs may also depend on their norm. Leveraging this assumption, we introduce the Relative Gaussian Mechanism (RGM), in which the variance of the noise depends on the norm of the output. We prove tight bounds on the RDP parameters under relative L2 sensitivity, and characterize the privacy loss incurred by using output-dependent noise. In particular, we show that RGM naturally adapts to a latent variable that would control the norm of the output. Finally, we instantiate our framework to show tight guarantees for Private Gradient Descent, a problem that naturally fits our relative L2 sensitivity assumption.