  Differential Privacy (DP) (and its variants) is the most common method for
machine learning (ML) on privacy-sensitive data. In big data analytics, one
often uses randomized sketching/aggregation algorithms to make processing
high-dimensional data tractable. Intuitively, such ML algorithms should provide
some inherent privacy, yet most existing DP mechanisms do not leverage or
under-utilize this inherent randomness, resulting in potentially redundant
noising. The motivating question of our work is: (How) can we improve the
utility of DP mechanisms for randomized ML queries, by leveraging the
randomness of the query itself?
  Towards a (positive) answer, our key contribution is (proving) what we call
the NDIS theorem, a theoretical result with several practical implications. In
a nutshell, NDIS is a closed-form analytic computation for the
(varepsilon,delta)-indistinguishability-spectrum (IS) of two arbitrary normal
distributions N1 and N2, i.e., the optimal delta (for any given varepsilon)
such that N1 and N2 are (varepsilon,delta)-close according to the DP distance.
The importance of the NDIS theorem lies in that (1) it yields efficient
estimators for IS, and (2) it allows us to analyze DP-mechanism with
normally-distributed outputs, as well as more general mechanisms by leveraging
their behavior on large inputs. We apply the NDIS theorem to derive DP
mechanisms for queries with normally-distributed outputs--i.e., Gaussian Random
Projections (RP)--and for more general queries--i.e., Ordinary Least Squares
(OLS). Compared to existing techniques, our new DP mechanisms achieve superior
privacy/utility trade-offs by leveraging the randomness of the underlying
algorithms. We then apply the NDIS theorem to a data-driven DP notion--in
particular relative DP introduced by Lu et al. [S&P 2024]. Our method
identifies the range of (varepsilon,delta) for which no additional noising is
needed.
