# The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 3 Sep 2023.

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

- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems](https://mlsanity.com/paper/2011.12945/) (2020)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Differentially Private Mixture of Generative Neural Networks](https://mlsanity.com/paper/1709.04514/) (2017)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Differentially Private Bayesian Linear Regression](https://mlsanity.com/paper/1910.13153/) (2019)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Bayesian Differential Privacy through Posterior Sampling](https://mlsanity.com/paper/1306.1066/) (2013)
- [Private Outsourced Bayesian Optimization](https://mlsanity.com/paper/2010.12799/) (2020)
- [Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise](https://mlsanity.com/paper/1902.04688/) (2019)
- [Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms](https://mlsanity.com/paper/1801.09236/) (2018)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [MVG Mechanism: Differential Privacy under Matrix-Valued Query](https://mlsanity.com/paper/1801.00823/) (2018)
- [Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression](https://mlsanity.com/paper/2207.13289/) (2022)
- [Improved Differentially Private Regression via Gradient Boosting](https://mlsanity.com/paper/2303.03451/) (2023)
- [Differentially Private Linear Algebra in the Streaming Model](https://mlsanity.com/paper/1409.5414/) (2014)
- [Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing](https://mlsanity.com/paper/1410.2470/) (2014)
- [Distributed Sketching Methods for Privacy Preserving Regression](https://mlsanity.com/paper/2002.06538/) (2020)
- [Differentially Private Distributed Bayesian Linear Regression with MCMC](https://mlsanity.com/paper/2301.13778/) (2023)

## Abstract (arXiv)

We investigate the privacy of em any algorithm whose outputs have Gaussian distribution. This work is motivated by the prevalence of such algorithms in several useful (ML) applications, and the comparatively little research that focuses on privacy-preserving learning outside of adding Gaussian noise to the data (such as DP-SGD). em What is the DP of any algorithm with multivariate Gaussian output? We answer the above research question with a general lemma which we call em Normal Distributions Indistinguishability Spectrum (NDIS), a closed-form analytic computation of the hockey-stick divergence δ between an arbitrary pair of multivariate Gaussians, parameterized by privacy parameter ε. To show its practical implications, we prove several properties of our NDIS lemma. These properties form a em toolbox of results which lead to potentially em easier privacy proofs for any Gaussian-output algorithm. As an example application of our toolbox, we prove a tighter parametrisation of the privacy of em random projection (RP), and obtaining from it a more noise-frugal DP mechanism. Beyond random projection, NDIS can be used to lift em any Gaussian-output algorithm with a `sensitivity' (which we define) to a Gaussian-output DP mechanism. The mechanism boosts the existing randomness in the algorithm, so that one can describe the mechanism's privacy as the IS between a single pair of Gaussians, which can then be analyzed via NDIS. Lastly, we leverage the connections between NDIS and the CDF of the generalized chi2 distribution (which have efficient empirical estimators) to present a tool for white-box auditing of Gaussian-output algorithms.