Dwork Roth 2014 - Laplace Mechanism

Summary

For numeric queries $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$, adding independent $\mathrm{Lap}(\Delta f/\epsilon )$ noise to each coordinate gives $(\epsilon ,0)$-DP (Thm. 3.6), where $\Delta f$ is the ${\ell }_1$-sensitivity. With probability $1-\delta$ no coordinate is off by more than $\ln (k/\delta )\Delta f/\epsilon$ (Thm. 3.8). Counting and histogram queries have sensitivity $1$, so error is $\approx 1/\epsilon$ independent of database size and, for histograms, of the number of cells.

Overview

Numeric queries “are one of the most fundamental types of database queries”. How accurately they can be answered under DP is governed by their ${\ell }_1$-sensitivity: “the magnitude by which a single individual’s data can change the function $f$ in the worst case, and therefore, intuitively, the uncertainty in the response that we must introduce in order to hide the participation of a single individual.”

Main Content

Definition 3.1 - ${\ell }_1$-sensitivity (p. 31)

The ${\ell }_1$-sensitivity of $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$ is

$$\Delta f=\underset{x,y\in {\mathbb{N}}^{|\mathcal{X}|},\Vert x-y{\Vert }_1=1}{\max }\Vert f(x)-f(y){\Vert }_1.$$

Definition 3.2 - Laplace distribution (p. 31)

The Laplace distribution (centred at $0$) with scale $b$ has density $\mathrm{Lap}(x\mid b)=\frac{1}{2b}\exp (-\frac{|x|}{b})$ and variance ${\sigma }^2=2b^2$. Write $\mathrm{Lap}(b)$ for the distribution or a random variable $X\sim \mathrm{Lap}(b)$. It is a symmetric version of the exponential distribution.

Definition 3.3 - Laplace mechanism (p. 32)

Given $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$, the Laplace mechanism is ${\mathcal{M}}_L(x,f(\cdot ),\epsilon )=f(x)+(Y_1,\dots ,Y_k)$ with $Y_i$ i.i.d. $\mathrm{Lap}(\Delta f/\epsilon )$.

Theorem 3.6 (p. 32)

The Laplace mechanism preserves $(\epsilon ,0)$-differential privacy.

Proof (p. 32)

Let $x,y$ with $\Vert x-y{\Vert }_1\le 1$ and let $p_x,p_y$ be the densities of ${\mathcal{M}}_L(x,f,\epsilon )$ and ${\mathcal{M}}_L(y,f,\epsilon )$. At an arbitrary point $z\in {\mathbb{R}}^k$:

$$\frac{p_x(z)}{p_y(z)}=\prod _{i=1}^k\frac{\exp (-\epsilon |f(x{)}_i-z_i|/\Delta f)}{\exp (-\epsilon |f(y{)}_i-z_i|/\Delta f)}=\prod _{i=1}^k\exp \left(\frac{\epsilon (|f(y{)}_i-z_i|-|f(x{)}_i-z_i|)}{\Delta f}\right)\le \prod _{i=1}^k\exp \left(\frac{\epsilon |f(x{)}_i-f(y{)}_i|}{\Delta f}\right)=\exp \left(\frac{\epsilon \Vert f(x)-f(y){\Vert }_1}{\Delta f}\right)\le \exp (\epsilon ).$$

The first inequality is the triangle inequality, the last is the definition of $\Delta f$. The bound $p_x(z)/p_y(z)\ge \exp (-\epsilon )$ follows by symmetry.

Footnote (p. 31): Gaussian noise with variance calibrated to $\Delta f\ln (1/\delta )/\epsilon$ achieves $(\epsilon ,\delta )$-DP (Appendix A), but the Laplace mechanism is cleaner and the two behave similarly under composition (Thm. 3.20).

Counting, linear and histogram queries

Example 3.1 - Counting queries (pp. 32-33)

Setup. “How many elements in the database satisfy Property $P$?” Counting is “an extremely powerful primitive”: it captures everything learnable in the statistical queries model and many data-mining tasks. Sensitivity. Adding or deleting one individual changes a count by at most $1$, so $\Delta f=1$. Release. $(\epsilon ,0)$-DP by adding $\mathrm{Lap}(1/\epsilon )$; expected distortion $1/\epsilon$, independent of database size. Many queries. A fixed arbitrary list of $m$ counting queries has worst-case sensitivity $m$ (one individual may change every count), so noise scaled to $m/\epsilon$ per answer is needed. Responding to large numbers of arbitrary queries is the query release problem.

Example 3.2 - Histogram queries (p. 33)

When queries are structurally disjoint, noise need not scale with the number of queries. The universe is partitioned into cells and the query asks how many elements lie in each. Because cells are disjoint, one element affects exactly one cell by at most $1$, so the histogram has sensitivity $1$ and each count is answered by adding an independent $\mathrm{Lap}(1/\epsilon )$ draw.

Fact 3.7 (p. 33)

If $Y\sim \mathrm{Lap}(b)$ then $\mathrm{Pr}[|Y|\ge t\cdot b]=\exp (-t)$.

Theorem 3.8 - Accuracy of the Laplace mechanism (p. 34)

Let $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$ and $y={\mathcal{M}}_L(x,f(\cdot ),\epsilon )$. Then for all $\delta \in (0,1]$:

$$\mathrm{Pr}\left[\Vert f(x)-y{\Vert }_{\infty }\ge \ln \left(\frac{k}{\delta }\right)\cdot \frac{\Delta f}{\epsilon }\right]\le \delta .$$

Proof (p. 34)

$\mathrm{Pr}[{\max }_i|Y_i|\ge \ln (k/\delta )\Delta f/\epsilon ]\le k\cdot \mathrm{Pr}[|Y_i|\ge \ln (k/\delta )\Delta f/\epsilon ]=k\cdot \delta /k=\delta$, by the union bound and Fact 3.7 with $t=\ln (k/\delta )$, $b=\Delta f/\epsilon$.

Example 3.3 - First names (p. 34)

Setup. Which first names, from 10,000 potential names, were most common among participants of the 2010 census? The query is $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^{10000}$, a histogram query, so $\Delta f=1$ (each person has at most one first name). Solution. All 10,000 name frequencies can be released simultaneously with $(1,0)$-DP; with probability 95% no estimate is off by more than $\ln (10000/0.05)\approx 12.2$. Interpretation. “That’s pretty low error for a nation of more than 300,000,000 people!”

Differentially private selection

The task in Example 3.3 is differentially private selection: the outcome space is discrete and the goal is to output a “best” answer (here, the most populous cell). Example 3.4 and Report Noisy Max (next note) show how to do this at noise cost $1/\epsilon$ even when the vector of counts has high ${\ell }_1$-sensitivity: Dwork Roth 2014 - Report Noisy Max and the Exponential Mechanism.

Examples

import numpy as np, math
rng = np.random.default_rng(0)
 
def laplace_mechanism(f_x, sensitivity, eps, rng=rng):
    f_x = np.atleast_1d(np.asarray(f_x, float))
    return f_x + rng.laplace(0.0, sensitivity / eps, size=f_x.shape)
 
# Example 3.3: 10,000-cell histogram, eps = 1, Delta f = 1
counts = rng.poisson(30_000, size=10_000)
noisy = laplace_mechanism(counts, 1.0, 1.0)
bound = math.log(10_000 / 0.05) * 1.0 / 1.0
print(np.abs(noisy - counts).max(), bound)       # max error vs ln(k/delta)*Delta/eps = 12.2
 
# fraction of runs with error beyond the bound should be <= delta = 0.05
bad = np.mean([np.abs(laplace_mechanism(counts, 1, 1) - counts).max() > bound for _ in range(500)])
print(bad)

Reading Theorem 3.8. The bound has only a $\ln k$ dependence on the number of released counts, so releasing $10^4$ cells at $\epsilon =1$ costs a maximum error near 12, versus about $10^4$ for $m$-query noise scale $m/\epsilon$ with a high-sensitivity query set (Example 3.1).

Connections

• Marketing measurement. A report of conversions by campaign (each user converting in at most one campaign, or contributions capped) is a histogram with $\Delta f=1$ (or the cap): per-cell noise of scale $1/\epsilon$ with a maximum error across $k$ cells near $\ln (k/\delta )/\epsilon$. For $k=500$ campaign-days at $\epsilon =1$ and 95% confidence that is about $\ln (500/0.05)\approx 9.2$ conversions: negligible for large cells and dominant for cells with fewer than about 50 conversions. Compare with the sampling noise discussion in Geo-Experiment Design and Power Analysis: DP noise adds a variance term of $2(\Delta f/\epsilon {)}^2$ per cell that can be modelled explicitly.
• The union-bound $\ln (k/\delta )$ inflation is the same structure as a Bonferroni correction (Multiple Testing Corrections).

See Also

• Dwork Roth 2014 - Report Noisy Max and the Exponential Mechanism
• Dwork Roth 2014 - Advanced Composition and the Gaussian Mechanism
• Dwork 2006 - Sensitivity and the Laplace Mechanism (original statement and the adaptive version)
• Wasserman Zhou 2010 - Histogram Release Mechanisms (histograms perturbed with Laplace noise, statistical rates)