Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Approximate differential privacy Dwork et al. (2006), also called (ϵ,δ)(\epsilon, \delta)-differential privacy, has the following definition:

The new privacy parameter, δ\delta, represents a “failure probability” for the definition. With probability 1−δ1-\delta, we will get the same guarantee as pure differential privacy; with probability δ\delta, we get no guarantee. In other words:

  • With probability 1−δ1-\delta, Pr[F(x)=S]Pr[F(x′)=s]≤eϵ\frac{\mathsf{Pr}[F(x) = S]}{\mathsf{Pr}[F(x') = s]} \leq e^\epsilon

  • With probability δ\delta, we get no guarantee at all

This definition should seem a little bit scary! With probability δ\delta, anything at all could happen - including a release of the entire sensitive dataset! For this reason, we typically require δ\delta to be very small - usually 1n2\frac{1}{n^2} or less, where nn is the size of the dataset. In addition, we’ll see that the (ϵ,δ)(\epsilon, \delta)-differentially private mechanisms in practical use don’t fail catastrophically, as allowed by the definition - instead, they fail gracefully, and don’t do terrible things like releasing the entire dataset.

Such mechanisms are possible, however, and they do satisfy the definition of (ϵ,δ)(\epsilon, \delta)-differential privacy. We’ll see an example of such a mechanism later in this section.

Properties of Approximate Differential Privacy

Approximate differential privacy has similar properties to pure ϵ\epsilon-differential privacy. It satisfies sequential composition:

The only difference from the pure ϵ\epsilon setting is that we add up the δ\deltas as well as the ϵ\epsilons. Approximate differential privacy also satisfies post-processing and parallel composition.

The Gaussian Mechanism

The Gaussian mechanism is an alternative to the Laplace mechanism, which adds Gaussian noise instead of Laplacian noise. The Gaussian mechanism does not satisfy pure ϵ\epsilon-differential privacy, but does satisfy (ϵ,δ)(\epsilon, \delta)-differential privacy. According to the Gaussian mechanism, for a function f(x)f(x) which returns a number, the following definition of F(x)F(x) satisfies (ϵ,δ)(\epsilon, \delta)-differential privacy:

where ss is the sensitivity of ff, and N(σ2)\mathcal{N}(\sigma^2) denotes sampling from the Gaussian (normal) distribution with center 0 and variance σ2\sigma^2. Note that here (and elsewhere in these notes), log⁡\log denotes the natural logarithm.

For real-valued functions f:D→Rf : D \rightarrow \mathbb{R}, we can use the classic Gaussian mechanism with values of ϵ\epsilon equal to or less than 1, a range called "high privacy"Balle & Wang (2018). This is in contrast to the Laplace mechanism, which can be used in any privacy regime, high or low.

It’s easy to compare what happens under both mechanisms for a given value of ϵ\epsilon.

Source
epsilon = 1
vals_laplace = [np.random.laplace(loc=0, scale=1/epsilon) for x in range(100000)]

delta = 10e-5
sigma = np.sqrt(2 * np.log(1.25 / delta)) * 1 / epsilon
vals_gauss = [np.random.normal(loc=0, scale=sigma) for x in range(100000)]

plt.hist(vals_laplace, bins=50, label='Laplace')
plt.hist(vals_gauss, bins=50, alpha=.7, label='Gaussian');
plt.legend();
<Figure size 640x480 with 1 Axes>

Here, we graph the empirical probability density function of the Laplace and Gaussian mechanisms for ϵ=1\epsilon = 1, with δ=10−5\delta = 10^{-5} for the Gaussian mechanism.

Compared to the Laplace mechanism, the plot for the Gaussian mechanism looks “squished.” Differentially private outputs which are far from the true answer are much more likely using the Gaussian mechanism than they are under the Laplace mechanism (which, by comparison, looks extremely “pointy”).

So the Gaussian mechanism has two major drawbacks - it requires the use of the the relaxed (ϵ,δ)(\epsilon, \delta)-differential privacy definition, and it’s less accurate than the Laplace mechanism. Why would we want to use it?

Vector-Valued Functions and their Sensitivities

So far, we have only considered real-valued functions (i.e. the function’s output is always a single real number). Such functions are of the form f:D→Rf : D \rightarrow \mathbb{R}. Both the Laplace and Gaussian mechanism, however, can be extended to vector-valued functions of the form f:D→Rkf : D \rightarrow \mathbb{R}^k, which return vectors of real numbers. We can think of histograms as vector-valued functions, which return a vector whose elements consist of histogram bin counts.

We saw earlier that the sensitivity of a function is:

GS(f)=max⁡d(x,x′)≤1∣f(x)−f(x′)∣\begin{align} GS(f) = \max_{d(x,x') \leq 1} \lvert f(x) - f(x') \rvert \end{align}

How do we define sensitivity for vector-valued functions?

Consider the expression f(x)−f(x′)f(x) - f(x'). If ff is a vector-valued function, then this expression represents the difference between two vectors, which can be computed as the difference between their corresponding elements (the difference of two length-kk vectors is thus a new length-kk vector). This new vector is the distance between f(x)f(x) and f(x′)f(x'), represented as a vector.

The magnitude of this vector is the sensitivity of ff. There are several ways to compute the magnitude of a vector; we’ll use two of them: the L1L1 norm and the L2L2 norm.

L1 and L2 Norms

The L1L1 norm of a vector VV of length kk is defined as ∥V∥1=∑i=1k∣Vi∣\lVert V \rVert_1 = \sum_{i=1}^k \lvert V_i \rvert (i.e. it’s the sum of the vector’s elements). In 2-dimensional space, the L1L1 norm of the difference between two vectors yields the “manhattan distance” between them.

The L2L2 norm of a vector VV of length kk is defined as ∥V∥2=∑i=1kVi2\lVert V \rVert_2 = \sqrt{\sum_{i=1}^k V_i^2} (i.e. the square root of the sum of the squares). In 2-dimensional space, this is the “Euclidean distance”, and it’s always less than or equal to the L1L1 norm.

L1 and L2 Sensitivities

The L1L1 sensitivity of a vector-valued function ff is:

This is equal to the sum of the elementwise sensitivities. For example, if we define a vector-valued function ff that returns a length-kk vector of 1-sensitive results, then the L1L1 sensitivity of ff is kk.

Similarly, the L2L2 sensitivity of a vector-valued function ff is:

Using the same example as above, a vector-valued function ff returning a length-kk vector of 1-sensitive results has L2L2 sensitivity of k\sqrt{k}. For long vectors, the L2L2 sensitivity will obviously be much lower than the L1L1 sensitivity! For some applications, like machine learning algorithms (which sometimes return vectors with thousands of elements), L2L2 sensitivity is significantly lower than L1L1 sensitivity.

Choosing Between L1 and L2

As mentioned earlier, both the Laplace and Gaussian mechanisms can be extended to vector-valued functions. However, there’s a key difference between these two extensions: the vector-valued Laplace mechanism requires the use of L1L1 sensitivity, while the vector-valued Gaussian mechanism allows the use of either L1L1 or L2L2 sensitivity. This is a major strength of the Gaussian mechanism. For applications in which L2L2 sensitivity is much lower than L1L1 sensitivity, the Gaussian mechanism allows adding much less noise.

  • The vector-valued Laplace mechanism releases f(x)+(Y1,…,Yk)f(x) + (Y_1, \dots, Y_k), where YiY_i are drawn i.i.d. from the Laplace distribution with scale sϵ\frac{s}{\epsilon} and ss is the L1L1 sensitivity of ff

  • The vector-valued Gaussian mechanism releases f(x)+(Y1,…,Yk)f(x) + (Y_1, \dots, Y_k), where YiY_i are drawn i.i.d. from the Gaussian distribution with σ2=2s2log⁡(1.25/δ)ϵ2\sigma^2 = \frac{2s^2 \log(1.25/\delta)}{\epsilon^2} and ss is the L2L2 sensitivity of ff

The Catastrophe Mechanism

The definition of (ϵ,δ)(\epsilon, \delta)-differential privacy says that a mechanism which satisfies the definition must “behave well” with probability 1−δ1-\delta. That means that with probability δ\delta, the mechanism can do anything at all. This “failure probability” is concerning, because mechanisms which satisfy the relaxed definition may (with low probability) result in very bad outcomes.

Consider the following mechanism, which we will call the catastrophe mechanism:

With probability 1−δ1-\delta, the catastrophe mechanism satisfies ϵ\epsilon-differential privacy. With probability δ\delta, it releases the whole dataset with no noise. This mechanism satisfies the definition of approximate differential privacy, but we probably wouldn’t want to use it in practice.

Fortunately, most (ϵ,δ)(\epsilon, \delta)-differentially private mechanisms don’t have such a catastrophic failure mode. The Gaussian mechanism, for example, doesn’t ever release the whole dataset. Instead, with probability δ\delta, the Gaussian mechanism doesn’t quite satisfy ϵ\epsilon-differential privacy - it satisfies cϵc\epsilon-differential privacy instead, for some value cc.

The Gaussian mechanism thus fails gracefully, rather than catastrophically, so it’s reasonable to have far more confidence in the Gaussian mechanism than in the catastrophe mechanism. Later, we will see alternative relaxations of the definition of differential privacy which distinguish between mechanisms that fail gracefully (like the Gaussian mechanism) and ones that fail catastropically (like the catastrophe mechanism).

Advanced Composition

We have already seen two ways of combining differentially private mechanisms: sequential composition and parallel composition. It turns out that (ϵ,δ)(\epsilon, \delta)-differential privacy admits a new way of analyzing the sequential composition of differentially private mechanisms, which can result in a lower privacy cost.

The advanced composition theorem Dwork et al. (2010) is usually stated in terms of mechanisms which are instances of kk-fold adaptive composition.

Iterative programs (i.e. loops or recursive functions) are nearly always instances of kk-fold adaptive composition. A for loop that runs 1000 iterations, for example, is a 1000-fold adaptive composition. As a more specific example, an averaging attack is a kk-fold adaptive composition:

# works for sensitivity-1 queries
def avg_attack(query, epsilon, k):
    results = [query + np.random.laplace(loc=0, scale=1/epsilon) for i in range(k)]
    return np.mean(results)

avg_attack(10, 1, 500)
np.float64(10.017920091412918)

In this example, the sequence of mechanisms is fixed ahead of time (we use the same mechanism each time), and k=500k = 500.

The standard sequential composition theorem says that the total privacy cost of this mechanism is kϵk\epsilon (in this case, 500ϵ500 \epsilon).

The advanced composition theorem says:

import numpy as np
import matplotlib.pyplot as plt

# Fixed parameters
epsilon = 0.1          # base epsilon
delta = 1e-5           # base delta for each mechanism
delta_prime = 1e-6     # additional delta for advanced composition

# Range of composition depths
k_values = np.arange(1, 201)

# Advanced composition epsilon'
def advanced_composition(eps, k, delta_prime):
    term1 = np.sqrt(2 * k * np.log(1 / delta_prime)) * eps
    term2 = k * eps * (np.exp(eps) - 1)
    return term1 + term2

eps_advanced = advanced_composition(epsilon, k_values, delta_prime)

# Naive composition epsilon'
eps_naive = epsilon * k_values

# Plot
plt.figure(figsize=(8, 5))
plt.plot(k_values, eps_advanced, label='Advanced Composition', color='blue')
plt.plot(k_values, eps_naive, label='Naive Composition', color='red', linestyle='--')

plt.xlabel('Number of Compositions $k$')
plt.ylabel(r'Composed Privacy Budget $\epsilon^\prime$')
plt.title(r'Naive vs. Advanced Composition $(\epsilon=0.1, \delta=10^{-5})$')
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.show()
<Figure size 800x500 with 1 Axes>

The red dashed line (naive composition) shows linear growth. The blue curve (advanced composition) grows more slowly due to sublinear behavior of the square root term. This demonstrates how advanced composition can significantly improve privacy accounting in multi-query settings.

So advanced composition derives a much lower bound on ϵ′\epsilon' than sequential composition, for the same mechanism. What does this mean? It means that the bounds given by sequential composition are loose - they don’t tightly bound the actual privacy cost of the computation. In fact, advanced composition also gives loose bounds - they’re just slightly less loose than the ones given by sequential composition.

It’s important to note that the two bounds are technically incomparable, since advanced composition introduces a δ\delta. When δ\delta is small, however, we will often compare the ϵ\epsilons given by both methods.

Standard sequential composition, it turns out, beats advanced composition for kk smaller than about 37. Thus, advanced composition is only really useful when kk is large (e.g. more than 100). When kk is very large, though, advanced composition can make a big difference!

Advanced Composition for Approximate Differential Privacy

The description of advanced composition above requires the individual mechanisms being composed to satisfy pure ϵ\epsilon-differential privacy. However, the theorem also applies if they satisfy (ϵ,δ)(\epsilon, \delta)-differential privacy instead. The more general statement of the advanced composition theorem is as follows (Dwork et al. (2010), Theorem 3.20):

The only difference is in the failure parameter δ\delta for the composed mechanism, where we have an additional kδk\delta term. When the mechanisms being composed satisfy pure ϵ\epsilon-differential privacy, then δ=kδ=0\delta = k\delta = 0, and we get the same result as the statement above.

References
  1. Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006). Our Data, Ourselves: Privacy Via Distributed Noise Generation. In S. Vaudenay (Ed.), Advances in Cryptology - EUROCRYPT 2006 (pp. 486–503). Springer Berlin Heidelberg.
  2. Balle, B., & Wang, Y.-X. (2018). Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. In J. Dy & A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 394–403). PMLR. https://proceedings.mlr.press/v80/balle18a.html
  3. Dwork, C., Rothblum, G. N., & Vadhan, S. (2010). Boosting and Differential Privacy. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 51–60. 10.1109/FOCS.2010.12