Research map / Federated learning and privacy / Differential privacy
Approximate Differential Privacy of the $\ell_2$ Mechanism
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes the approximate DP guarantees of the l2 (K-norm) mechanism via spherical-cap bounds on the privacy loss, giving an algorithm to calibrate its scale sigma for (epsilon, delta)-DP and showing it beats Laplace and analytic Gaussian in mean squared error for intermediate dimensions.
Problem
Calibrating the noise scale of the l2 mechanism (a K-norm mechanism with density proportional to exp(-||y-T(X)||_2/sigma)) to achieve approximate (epsilon, delta)-DP, whose guarantees were not well understood.
Approach
Bounds the privacy loss random variable's high-loss region with spherical caps: upper bounds the first term and lower bounds the second term of the approximate DP characterization using Riemann sums over radii and regularized incomplete beta/gamma functions, then binary searches sigma; also gives a parallel sampler via Gamma and uniform-ball decomposition.
Key results
- The l2 mechanism dominates both Laplace and analytic Gaussian in mean squared l2 error for (1, 1e-5)-DP; its gap over the better of the two peaks at about 50% at d=7 and is 5% at d=100 and under 1% at d=500.
- Algorithmic privacy estimates closely track empirical estimates of the privacy loss for d from 1 to 100 with n_r=n_R=1000.
- Computing sigma for the l2 mechanism takes about 0.1 seconds and does not grow with d, roughly 100x slower than the analytic Gaussian computation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the ℓ2 mechanism instead of the better of the Laplace and analytic Gaussian mechanisms | Mean squared ℓ2 error under (1, 10^-5)-DP · Dimensions between 1 and 500 | mean squared ℓ2 error: 0 at d=1; peaks at 50% at d=7; 5% at d=100; <1% at d = 500 | Helped |
| Use the Laplace mechanism instead of the analytic Gaussian mechanism | Mean squared ℓ2 error under (1, 10^-5)-DP · Small d | mean squared ℓ2 error | Helped |
| Use the analytic Gaussian mechanism instead of the Laplace mechanism | Mean squared ℓ2 error under (1, 10^-5)-DP · Larger d | mean squared ℓ2 error | Helped |
| Use the ℓ2 mechanism instead of the Laplace mechanism | Mean squared ℓ2 error · d=1 | mean squared ℓ2 error: 0 | No clear effect |
| Use the ℓ2 mechanism instead of the analytic Gaussian mechanism | Mean squared ℓ2 error · Dimensions evaluated under (1, 10^-5)-DP | mean squared ℓ2 error | Helped |
Surprising findings
- The Laplace mechanism's approximate DP guarantee is only negligibly better than its pure DP guarantee for realistic delta, so approximate DP offers little utility gain for Laplace.
Limitations
- Privacy calibration requires numerical approximation with Riemann sums (n_r = n_R = 1000), so the bounds are approximations rather than closed form.
- Sigma computation is about 100x slower than the analytic Gaussian calibration.
- The l2 mechanism's pure DP guarantee does not directly yield tight guarantees under RDP, zCDP or Gaussian DP, and amplification by subsampling is looser.
Experimental setup
Metrics: mean squared l2 error estimated privacy loss (empirical vs algorithmic) runtime to compute sigma runtime to sample
Baselines: Laplace mechanism analytic Gaussian mechanism generalized Gaussian mechanism
Builds on: K-norm mechanism analytic Gaussian mechanism privacy loss characterization of (epsilon, delta)-DP
Closest papers by meaning
- Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy (ICML 2026 · similarity 0.92)
- Pain-Free Random Differential Privacy with Sensitivity Sampling (ICML 2017 · similarity 0.90)
- Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy (ICML 2026 · similarity 0.89)
- Differential Privacy without Sensitivity (NeurIPS 2016 · similarity 0.89)
- Optimality of Matrix Mechanism on $\ell_p^p$-metric (ICLR 2025 · similarity 0.89)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.