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

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.