Home
Differential Privacy for Location Data
Laplace & Gaussian Noise for Coordinate Data
Choosing Between Pure and Approximate DP for Map Releases

Choosing Between Pure and Approximate DP for Map Releases

Q: Can I use a large δ if ε is small?

The two parameters are not interchangeable. \varepsilon bounds how much the output distribution can shift; \delta bounds how often the bound does not apply at all. A tiny \varepsilon with a large \delta is a strong guarantee that frequently does not hold.

Approximate DP buys less noise on wide queries because it calibrates to L2 rather than L1 sensitivity, and it costs a failure probability $\delta$ that must be smaller than the reciprocal of the population. For a map with many cells the saving is large; for a single count it is nothing, and the $\delta$ is then pure cost.

Core Calculation permalink

Both mechanisms answer the same query and differ in what they calibrate against. For a histogram where one individual can touch at most $c$ cells by one each:

\Delta_1 = c, \qquad \Delta_2 = \sqrt{c}

The Laplace mechanism satisfies pure $\varepsilon$ -DP with scale $b = \Delta_1/\varepsilon$ ; the Gaussian mechanism satisfies $(\varepsilon, \delta)$ -DP with

\sigma = \frac{\Delta_2\sqrt{2\ln(1.25/\delta)}}{\varepsilon}

The comparison that matters is the per-cell standard deviation. Laplace with scale $b$ has standard deviation $b\sqrt{2}$ , so the ratio is

\frac{\sigma_{\text{Gauss}}}{\sigma_{\text{Lap}}} = \frac{\sqrt{c}\,\sqrt{2\ln(1.25/\delta)}}{c\sqrt{2}} = \frac{\sqrt{\ln(1.25/\delta)}}{\sqrt{c}}

The Gaussian mechanism wins whenever $c > \ln(1.25/\delta)$ . At $\delta = 10^{-6}$ that threshold is about 14 cells, and at $\delta = 10^{-9}$ about 21.

Worked numeric example permalink

An H3 resolution-8 mobility map, $\varepsilon = 0.5$ , contribution cap $c$ , $\delta = 10^{-6}$ where used:

Contribution cap $c$	Laplace σ	Gaussian σ	Winner
1 (one cell per person)	2.8	10.6	Laplace, by 3.7×
4	11.3	21.2	Laplace, by 1.9×
14	39.6	39.7	tie
50	141	74.9	Gaussian, by 1.9×
200	566	150	Gaussian, by 3.8×

The crossover is the whole decision. A release where each person contributes to one cell — a home-location map — gains nothing from $\delta$ and should be pure. A release where each person contributes to fifty cells — a daily-trajectory heatmap — is four times noisier under Laplace than it needs to be.

The contribution cap is the parameter that decides the mechanism, and it is set by the query rather than chosen. Fixing it first turns the mechanism choice into a lookup.

Python Implementation permalink

from __future__ import annotations

import math
from dataclasses import dataclass

@dataclass(frozen=True)
class MechanismChoice:
    contribution_cap: int
    epsilon: float
    population: int
    delta: float | None = None

    def __post_init__(self) -> None:
        if self.contribution_cap < 1:
            raise ValueError("contribution_cap must be at least 1")
        if self.delta is not None and self.delta >= 1.0 / self.population:
            # delta is the probability the guarantee simply fails. Above 1/N it is
            # a licence to release one person's record outright.
            raise ValueError(
                f"delta {self.delta:g} must be well below 1/N = {1/self.population:g}"
            )

    @property
    def laplace_sigma(self) -> float:
        return math.sqrt(2.0) * self.contribution_cap / self.epsilon

    @property
    def gaussian_sigma(self) -> float | None:
        if self.delta is None:
            return None
        return (math.sqrt(self.contribution_cap)
                * math.sqrt(2.0 * math.log(1.25 / self.delta)) / self.epsilon)

    def recommend(self) -> dict:
        if self.delta is None:
            return {"mechanism": "laplace", "sigma": self.laplace_sigma,
                    "because": "no delta was authorised"}
        g = self.gaussian_sigma
        assert g is not None
        if g < self.laplace_sigma:
            return {"mechanism": "gaussian", "sigma": g,
                    "ratio_vs_laplace": g / self.laplace_sigma,
                    "because": f"cap {self.contribution_cap} exceeds the crossover"}
        return {"mechanism": "laplace", "sigma": self.laplace_sigma,
                "ratio_vs_gaussian": self.laplace_sigma / g,
                "because": "the delta buys no noise reduction at this cap"}

The constructor’s refusal is the important line. A $\delta$ above $1/N$ is not a small relaxation — it is a probability, per release, that the mechanism produces an output which identifies someone, and at $\delta = 10^{-3}$ over a million people that is a thousand expected failures.

Verification permalink

def verify_choice(choice: MechanismChoice) -> dict:
    """Report both mechanisms side by side so the record shows what was rejected."""
    return {
        "contribution_cap": choice.contribution_cap,
        "epsilon": choice.epsilon,
        "delta": choice.delta,
        "laplace_sigma": round(choice.laplace_sigma, 2),
        "gaussian_sigma": (None if choice.gaussian_sigma is None
                           else round(choice.gaussian_sigma, 2)),
        "crossover_cap": (None if choice.delta is None
                          else round(math.log(1.25 / choice.delta), 1)),
        "delta_vs_inverse_n": (None if choice.delta is None
                               else choice.delta * choice.population),
        **choice.recommend(),
    }

Record both figures, not only the winner. A reviewer who sees “Gaussian, σ = 75” cannot tell whether the $\delta$ earned anything; one who also sees “Laplace would have been 141” can.

Approximate DP is a genuine relaxation with a probability attached. Stating it as an expected head-count rather than an exponent is what lets a non-specialist reviewer decide whether to accept it.

Reading the Crossover in Practice permalink

The crossover formula $c > \ln(1.25/\delta)$ looks like a clean decision rule, and in practice three things complicate applying it.

The contribution cap is often not what the query says. A histogram query might cap each person at four cells, but if the release also publishes a second histogram over the same population at a different resolution, the joint sensitivity spans both. The cap that goes into the formula is the cap over everything the release exposes, not the cap enforced inside one aggregation step. Teams routinely compute the mechanism choice from a single query and then add a second view to the same release, which moves the crossover without anybody re-deriving it.

The delta has to be chosen before the comparison, not after. Because a larger $\delta$ moves the crossover left, it is possible to justify the Gaussian mechanism at any cap by loosening the failure probability. That is backwards: $\delta$ is fixed by how many individuals the organisation is willing to expose, and only then does the crossover fall where it falls. A review that sees $\delta$ and the mechanism decided together should treat that as a signal to re-derive both.

The tail shape matters independently of σ. The comparison above is entirely about the standard deviation, and for a map that a human will read, the shape of the tail matters as much. Laplace noise produces occasional cells whose released value is several times the true one, and on a choropleth those read as genuine hotspots — a reader has no way to distinguish an outlier draw from a real cluster. The Gaussian mechanism’s lighter tail makes that failure much rarer. Where the map’s purpose is to direct attention to the largest cells, that consideration can dominate a modest σ advantage in the other direction.

A fourth, more mundane point is worth stating: for a single count query the whole comparison is moot. The cap is one, the Laplace mechanism wins by a wide margin, and introducing a failure probability buys nothing at all. If a release consists of one number, the answer is pure differential privacy and there is nothing to weigh.

Edge Cases & Adjustments permalink

An unbounded contribution. Neither mechanism is calibrated until the per-person contribution is capped. Enforce the cap in the query — count each person at most once per cell, at most $c$ cells — before choosing anything.
Composition across a series. $\delta$ adds under basic composition, so twelve monthly releases at $10^{-6}$ leave a programme at $1.2 \times 10^{-5}$ . Track it in the ledger beside $\varepsilon$ , or convert both to $\rho$ under zero-concentrated accounting as in composing privacy budgets across spatial queries.
ε above 1. The closed-form Gaussian calibration above is only valid for $\varepsilon \le 1$ . For larger budgets use the analytic Gaussian mechanism, which yields a smaller and correct σ.
Heavy tails matter for the map. Laplace produces occasional extreme cell values that look like real hotspots. Where a reader will interpret the largest cells, the Gaussian mechanism’s lighter tail is worth something beyond the σ comparison.
Regulatory posture. Some reviewers will not accept a non-zero failure probability at all. That is a legitimate position and it settles the question regardless of the arithmetic — record it as the reason rather than re-arguing the crossover.

The σ comparison is the whole story for an analyst reading numbers and only half of it for a reader reading colours. Where the map's job is to direct attention, the tail shape can outweigh a modest σ advantage.

Recording the Decision permalink

The release record should carry both mechanisms’ figures and the reason the losing one was rejected, because the crossover moves whenever the query changes and the next person to touch the pipeline will need to know which side of it the current design sits on.

Three fields are enough: the contribution cap that was enforced, the σ each mechanism would have required at the chosen ε, and — if approximate DP was used — the δ expressed as an expected head-count against the population. A record that states only “Gaussian, σ = 75” tells a reviewer what was done and nothing about whether it was the right thing; one that adds “Laplace would have been 141 at a cap of 50” makes the decision auditable in a line.

Where the release is part of a programme, add the cumulative δ alongside the cumulative ε. Both accumulate, both have ceilings, and a series that tracks one and not the other will breach on the untracked one first.

FAQ permalink

Is approximate DP weaker?

Yes, definitionally: the bound is allowed to fail with probability $\delta$ . Whether that matters depends on the size of $\delta$ relative to the population and on how many releases compose. It is a real relaxation, not a technicality.

Can I use a large δ if ε is small?

The two parameters are not interchangeable. $\varepsilon$ bounds how much the output distribution can shift; $\delta$ bounds how often the bound does not apply at all. A tiny $\varepsilon$ with a large $\delta$ is a strong guarantee that frequently does not hold.

What if my query is a coordinate rather than a count?

Then the contribution cap is 1 and pure DP is almost always the right choice — or, for a released point rather than an aggregate, the metric formulation in geo-indistinguishability.

How do I explain δ in an impact assessment?

As an expected number of individuals per release for whom the guarantee does not hold, computed as $\delta N$ . That framing is what the figure means and it is the one a reviewer can act on.

Laplace & Gaussian Noise for Coordinate Data — the two mechanisms in full
Calibrating Gaussian Noise for Spatial Aggregate Queries — deriving σ once the mechanism is chosen
Composing Privacy Budgets Across Spatial Queries — how δ accumulates
Geo-Indistinguishability & the Planar Laplace Mechanism — the metric alternative for released points

← Back to Laplace & Gaussian Noise for Coordinate Data

Choosing Between Pure and Approximate DP for Map Releases

Core Calculation # permalink

Worked numeric example # permalink

Python Implementation # permalink

Verification # permalink

Reading the Crossover in Practice # permalink

Edge Cases & Adjustments # permalink

Recording the Decision # permalink

FAQ # permalink

Related # permalink

Related topics