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

arXiv:2309.01243v4 Announce Type: replace-cross Abstract: 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 elta between an arbitrary pair of multivariate Gaussians, parameterized by privacy parameter epsilon. 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 hi^2 distribution (which have efficient empirical estimators) to present a tool for white-box auditing of Gaussian-output algorithms.

Source: arXiv cs.LG | 2026-05-19