Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure

Noise perturbation is one of the most fundamental approaches for achieving (𝜖, 𝛿)-differential privacy (DP) guarantees when releasing the result of a query or function 𝑓 (•) ∈ R 𝑀 evaluated on a sensitive dataset 𝒙. In this approach, calibrated noise n ∈ R 𝑀 is used to obscure the difference vector 𝑓 (𝒙) -𝑓 (𝒙 ′ ), where 𝒙 ′ is known as a neighboring dataset. A DP guarantee is obtained by studying the tail probability bound of a privacy loss random variable (PLRV), defined as the Radon-Nikodym derivative between two distributions. When n follows a multivariate Gaussian distribution, the PLRV is characterized as a specific univariate Gaussian. In this paper, we propose a novel scheme to generate n by leveraging the fact that the perturbation noise is typically spherically symmetric (i.e., the distribution is rotationally invariant around the origin). The new noise generation scheme allows us to investigate the privacy loss from a geometric perspective and express the resulting PLRV using a product measure, 𝑊 × 𝑈 ; measure 𝑊 is related to a radius random variable controlling the magnitude of n, while measure 𝑈 involves a directional random variable governing the angle between n and the difference 𝑓 (𝒙) -𝑓 (𝒙 ′ ). We derive a closed-form moment bound on the product measure to prove (𝜖, 𝛿)-DP. Under the same (𝜖, 𝛿)-DP guarantee, our mechanism yields a smaller expected noise magnitude than the classic Gaussian noise in high dimensions, thereby significantly improving the utility of the noisy result 𝑓 (𝒙) + n. To validate this, we consider privacypreserving convex and non-convex empirical risk minimization (ERM) problems in high dimensional space. We propose leveraging our developed noise in output perturbation, objective perturbation, and gradient perturbation to establish DP guarantees when solving ERMs. Experiments on multiple datasets show that our method achieves significant utility improvements for convex ERM models (e.g., regression and SVM) under the same privacy guarantees. For non-convex models (e.g., neural networks), it provides substantially stronger privacy guarantees under comparable utility. 1

• Theory of computation → Randomness, geometry and discrete structures; • Security and privacy → Data anonymization and sanitization.