Calibrating Gaussian Noise for Spatial Aggregates

Calibrating the Gaussian mechanism for a spatial aggregate means computing the L2 sensitivity $\Delta_2$ of a vector-valued query — a per-cell count histogram, a spatial sum, a bounded coordinate mean — and then solving for the smallest noise scale $\sigma$ that satisfies $(\varepsilon, \delta)$ -differential privacy across the whole vector at once. Unlike the planar Laplace mechanism, which perturbs a single point under an L1 or metric guarantee, the Gaussian mechanism adds independent $\mathcal{N}(0, \sigma^2)$ noise to every component of an aggregate and pays for the Euclidean distance between neighbouring outputs. That distinction is what makes it the natural fit for the high-dimensional releases produced under differentially private spatial aggregation. This guide sits inside the spatial noise mechanisms guide of the Differential Privacy for Geospatial Data section, and it is narrow on purpose: how to bound $\Delta_2$ , why the textbook $\sigma$ bound wastes utility, and how to reach the tight scale through the analytic Gaussian mechanism and $\rho$ -zCDP.

Parameter Configuration and Calibration

The Gaussian mechanism has one output knob, $\sigma$ , but that knob is a function of four inputs you must fix first. Get any one wrong and the release is either non-private or needlessly destroyed by noise.

Knob	Symbol	Typical value	Consequence
L2 sensitivity	$\Delta_2$	$1$ , $\sqrt{c}$ , or clip bound $C$	Scales $\sigma$ linearly; the whole game is bounding it
Privacy loss	$\varepsilon$	$0.5$ – $3$ per release	Smaller $\varepsilon$ = more noise = stronger privacy
Failure probability	$\delta$	$\ll 1/N$ (e.g. $10^{-6}$ )	Probability the guarantee silently fails
zCDP budget	$\rho$	derived per release	Cleaner composition currency than $(\varepsilon,\delta)$
Contribution cap	$c$ or $C$	dataset-specific	Enforces the $\Delta_2$ you assumed

Computing $\Delta_2$ for spatial queries. L2 sensitivity is the maximum Euclidean norm of the change one subject can force on the output vector, over all neighbouring datasets $D \sim D'$ differing by adding or removing that subject:

\Delta_2 = \max_{D \sim D'} \lVert q(D) - q(D') \rVert_2.

Per-cell count vectors. If the grid partitions space so each subject falls in exactly one cell, adding a subject changes one component by $1$ , so $\Delta_2 = 1$ . If a subject can contribute to up to $c$ cells (overlapping buffers, multi-visit histograms), the worst-case change is a vector with $c$ entries of $\pm 1$ , giving $\Delta_2 = \sqrt{c}$ — the square-root, not $c$ , which is exactly why Gaussian noise scales better than Laplace on wide histograms.
Spatial sums. For a per-cell sum of a real attribute, clip each subject’s contribution vector to Euclidean norm $C$ before aggregation; then $\Delta_2 = C$ by construction. This is contribution bounding: the assumed sensitivity only holds because clipping enforces it.
Bounded coordinate means. A mean of coordinates over a fixed population of $N$ has per-axis sensitivity bounded by the coordinate range divided by $N$ ; clip coordinates to a bounding box of side $R$ and the two-axis mean has $\Delta_2 \le \sqrt{2}\,R/N$ .

The classic bound and why it is loose. The textbook Gaussian mechanism sets

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

This closed form is only valid for $\varepsilon \le 1$ and is loose everywhere: the $1.25$ constant comes from a union-bound slack in the original proof, and the bound diverges nonsensically as $\varepsilon \to 1$ . For a heatmap release at $\varepsilon = 2$ it can over-noise by 30–50%, wiping out spatial structure the analysts needed.

The analytic Gaussian mechanism (Balle & Wang, 2018). Instead of a slack-laden closed form, solve directly for the smallest $\sigma$ whose exact privacy profile meets $\delta$ . The mechanism is $(\varepsilon, \delta)$ -DP if and only if

\delta \ge \Phi\!\left(\frac{\Delta_2}{2\sigma} - \frac{\varepsilon\sigma}{\Delta_2}\right) - e^{\varepsilon}\,\Phi\!\left(-\frac{\Delta_2}{2\sigma} - \frac{\varepsilon\sigma}{\Delta_2}\right),

where $\Phi$ is the standard normal CDF. The right-hand side is monotone decreasing in $\sigma$ , so a bisection finds the exact minimal scale. It is valid for all $\varepsilon > 0$ and never over-noises.

$\rho$ -zCDP framing for composition. Zero-concentrated DP gives a cleaner accounting currency. The Gaussian mechanism with scale $\sigma$ satisfies $\rho$ -zCDP with $\rho = \Delta_2^2 / (2\sigma^2)$ , equivalently

\sigma = \frac{\Delta_2}{\sqrt{2\rho}}.

Under zCDP, $k$ releases with budgets $\rho_1,\dots,\rho_k$ compose linearly to $\big(\sum_i \rho_i\big)$ -zCDP — no $\delta$ bookkeeping between steps — and you convert once at the end via $\varepsilon = \rho + 2\sqrt{\rho\ln(1/\delta)}$ . This is the accounting model the privacy budget management guide recommends for any pipeline that issues more than a handful of Gaussian queries against the same population.

Choosing $\delta$ . Treat $\delta$ as the probability the mechanism silently leaks a record wholesale, so it must be cryptographically small relative to dataset size: the standard rule is $\delta \ll 1/N$ , often $\delta = N^{-1.1}$ or a fixed $10^{-6}$ to $10^{-9}$ . A common error is reusing $\delta = 10^{-5}$ regardless of $N$ ; for a billion-row mobility feed that is far too weak, because in expectation more than one subject can be exposed.

Reference Implementation

The function below calibrates $\sigma$ with the analytic Gaussian mechanism using only the standard library plus numpy, and apply_gaussian draws the isotropic noise. The classic bound is included as a reference so the validation harness can confirm the analytic scale is genuinely tighter.

python

from __future__ import annotations

import math
from typing import Optional

import numpy as np


def _phi(x: float) -> float:
    """Standard normal CDF via the error function (stdlib only, no SciPy)."""
    return 0.5 * (1.0 + math.erf(x / math.sqrt(2.0)))


def classic_gaussian_sigma(l2_sensitivity: float, epsilon: float, delta: float) -> float:
    """Textbook bound sigma >= Delta2 * sqrt(2 ln(1.25/delta)) / epsilon.

    Only valid for epsilon <= 1 and loose everywhere; kept for comparison.
    """
    return l2_sensitivity * math.sqrt(2.0 * math.log(1.25 / delta)) / epsilon


def calibrate_gaussian_sigma(
    l2_sensitivity: float,
    epsilon: float,
    delta: float,
    *,
    rtol: float = 1e-12,
) -> float:
    """Smallest sigma making the Gaussian mechanism (epsilon, delta)-DP.

    Uses the analytic Gaussian mechanism (Balle & Wang, 2018): it solves the
    exact privacy-profile equation instead of the slack-laden closed form, so
    it stays tight for epsilon > 1 and never over-noises a spatial aggregate.

    Args:
        l2_sensitivity: Delta_2, the max Euclidean change one subject can force
            on the aggregate vector. MUST already reflect contribution clipping;
            an underestimate here is a silent privacy violation, not a bug.
        epsilon: target privacy loss (> 0).
        delta: target failure probability. Choose delta << 1/N so, in
            expectation, fewer than one subject can ever be exposed.
    Returns:
        The minimal sigma; the returned value always satisfies the DP bound.
    """
    if l2_sensitivity <= 0.0:
        raise ValueError("l2_sensitivity (Delta_2) must be positive")
    if epsilon <= 0.0:
        raise ValueError("epsilon must be positive")
    if not (0.0 < delta < 1.0):
        raise ValueError("delta must lie strictly in (0, 1)")

    a = l2_sensitivity

    def delta_of_sigma(sigma: float) -> float:
        # Exact (epsilon, delta) trade-off of an isotropic Gaussian at scale sigma.
        # Monotone decreasing in sigma, so bisection is safe.
        return (
            _phi(a / (2.0 * sigma) - epsilon * sigma / a)
            - math.exp(epsilon) * _phi(-a / (2.0 * sigma) - epsilon * sigma / a)
        )

    # Bracket: grow the upper bound until it over-satisfies the delta target.
    lo, hi = 1e-12, max(1.0, a)
    while delta_of_sigma(hi) > delta:
        hi *= 2.0
    # Bisect. hi always keeps delta_of_sigma(hi) <= delta, so returning hi is safe.
    for _ in range(200):
        mid = 0.5 * (lo + hi)
        if delta_of_sigma(mid) > delta:
            lo = mid
        else:
            hi = mid
        if hi - lo <= rtol * hi:
            break
    return hi


def sigma_from_zcdp(l2_sensitivity: float, rho: float) -> float:
    """Gaussian scale for a rho-zCDP budget: sigma = Delta_2 / sqrt(2 rho)."""
    if rho <= 0.0:
        raise ValueError("rho must be positive")
    return l2_sensitivity / math.sqrt(2.0 * rho)


def apply_gaussian(
    vec: np.ndarray,
    sigma: float,
    *,
    rng: Optional[np.random.Generator] = None,
) -> np.ndarray:
    """Add isotropic N(0, sigma^2) noise to every component of an aggregate.

    Noise is drawn independently per cell; the (epsilon, delta) guarantee holds
    for the WHOLE vector because sigma was calibrated to its L2 sensitivity.
    Any downstream transform (clamping to >= 0, smoothing, rendering a heatmap)
    is post-processing and consumes no further budget.
    """
    rng = np.random.default_rng() if rng is None else rng
    return vec.astype(float) + rng.normal(0.0, sigma, size=vec.shape)

The apply_gaussian docstring names the load-bearing property: because $\sigma$ was calibrated to the vector’s $\Delta_2$ , the joint release is private, and post-processing — clamping negative counts to zero, rendering tiles — is free. Never re-noise a derived quantity thinking it needs its own budget; that only wastes utility.

Validation Checkpoint

A mis-set $\Delta_2$ or a $\sigma$ off the tight frontier fails silently: the release still looks noised. The harness below asserts the calibrated scale actually satisfies the analytic bound, that it beats the classic bound, that the zCDP conversion is consistent, and that the empirical noise standard deviation matches $\sigma$ .

python

def _validate() -> None:
    rng = np.random.default_rng(7)

    eps, delta, d2 = 1.5, 1e-6, math.sqrt(4.0)   # subject touches <= 4 grid cells

    sigma = calibrate_gaussian_sigma(d2, eps, delta)

    # 1. The analytic sigma satisfies the exact (eps, delta)-DP condition.
    a = d2
    achieved = (
        _phi(a / (2 * sigma) - eps * sigma / a)
        - math.exp(eps) * _phi(-a / (2 * sigma) - eps * sigma / a)
    )
    assert achieved <= delta + 1e-12, "calibrated sigma violates the DP bound"

    # 2. The analytic scale is strictly tighter than the classic closed form.
    assert sigma < classic_gaussian_sigma(d2, eps, delta), "analytic must beat classic"

    # 3. zCDP round-trip: rho = Delta2^2 / (2 sigma^2) reproduces the same sigma.
    rho = d2 ** 2 / (2 * sigma ** 2)
    assert math.isclose(sigma_from_zcdp(d2, rho), sigma, rel_tol=1e-9)

    # 4. Empirical noise std matches sigma on a large per-cell count vector.
    counts = rng.integers(0, 500, size=200_000).astype(float)
    noised = apply_gaussian(counts, sigma, rng=rng)
    emp_std = float(np.std(noised - counts))
    assert abs(emp_std - sigma) / sigma < 0.02, f"empirical std {emp_std} != {sigma}"

    print(f"OK: sigma={sigma:.4f}  rho={rho:.5f}  empirical_std={emp_std:.4f}")


if __name__ == "__main__":
    _validate()

Incident Response and Edge Cases

Gaussian calibration errors do not throw — they quietly ship a release that is either non-private or unusable. The four that surface most on live spatial pipelines:

Underestimated $\Delta_2$ from uncapped contributions. A subject who appears in more grid cells than assumed — repeated visits, an oversized buffer — makes the true $\Delta_2$ exceed the value passed to calibrate_gaussian_sigma, so the actual privacy loss is larger than $\varepsilon$ . Detection: audit the maximum number of cells (or the maximum contribution norm) any single subject reaches against the assumed $c$ or clip bound $C$ . Remediation: enforce contribution bounding before aggregation — cap cells per subject at $c$ or clip the per-subject vector to norm $C$ — and recalibrate. The assumed sensitivity is only real if clipping makes it real.
Using the classic bound at $\varepsilon > 1$ . The closed form $\sigma \ge \Delta_2\sqrt{2\ln(1.25/\delta)}/\varepsilon$ is not valid above $\varepsilon = 1$ and either over-noises or, worse, is misapplied as if valid. Detection: flag any release where $\varepsilon > 1$ still routes through the closed form. Remediation: switch to calibrate_gaussian_sigma; the analytic scale is provably tight for all $\varepsilon$ .
$\delta$ too large for the population. A fixed $\delta = 10^{-5}$ on a dataset of tens of millions of subjects violates $\delta \ll 1/N$ , so the residual failure probability covers more than one real record. Detection: compare $\delta$ against $1/N$ at release time. Remediation: set $\delta = N^{-1.1}$ or a hard floor like $10^{-7}$ , then recalibrate — $\sigma$ grows only logarithmically in $1/\delta$ , so tightening $\delta$ costs little utility.
Composition tracked in $(\varepsilon,\delta)$ instead of $\rho$ . Summing $(\varepsilon,\delta)$ pairs naively across many heatmap tiles overcounts the true loss and exhausts the budget prematurely. Detection: a budget ledger that adds $\varepsilon$ per query without an accountant. Remediation: convert each Gaussian release to $\rho = \Delta_2^2/(2\sigma^2)$ , sum $\rho$ linearly, and convert once — the discipline the privacy budget management guide enforces.

Frequently Asked Questions

When should I use the Gaussian mechanism instead of Laplace for a spatial release?

Reach for Gaussian when the query is a high-dimensional vector — a per-cell count histogram, a multi-cell spatial sum — because it pays for L2 (Euclidean) distance, and a subject touching c cells gives sensitivity of only the square root of c, versus c for Laplace under L1. Gaussian also composes cleanly under zCDP. Prefer Laplace for scalar or low-dimensional queries and for perturbing a single location, where the planar Laplace mechanism gives a metric guarantee Gaussian does not.

Why is the analytic Gaussian mechanism better than the classic sigma formula?

The classic bound is a closed form derived with union-bound slack; it is only valid for epsilon at most 1 and over-noises everywhere else, often by 30 to 50 percent on a heatmap at epsilon of 2. The analytic Gaussian mechanism solves the exact privacy-profile equation for the smallest sigma that meets delta, is valid for every epsilon, and never wastes utility. It is a short numerical bisection, so there is no reason to keep using the loose form in production.

How do I choose delta for a Gaussian spatial aggregate?

Treat delta as the probability the guarantee silently fails and set it well below one over the number of subjects, so in expectation fewer than one record can be exposed. A billion-row mobility feed needs delta near ten to the minus nine, not the ten to the minus five that suffices for a small cohort. Because sigma grows only with the square root of the log of one over delta, tightening delta costs very little noise, so err small.

Do I need to add noise again to a heatmap rendered from a noised aggregate?

No. Once sigma is calibrated to the vector's L2 sensitivity and the noise is added, every downstream transform — clamping negative counts to zero, smoothing, colour-mapping into tiles — is post-processing and consumes no additional budget. Re-noising a derived product only destroys utility. Track the single Gaussian release in the accountant and leave the rendering alone.

Spatial Noise Mechanisms — the parent guide covering how noise is calibrated and added across the DP geospatial stack.
Planar Laplace Noise for Location Privacy — the L1 / metric-DP sibling for perturbing individual points rather than aggregates.
Differentially Private Spatial Aggregation — the aggregation layer whose count vectors and sums this calibration protects.
Privacy Budget Management — composing Gaussian releases under zCDP and tracking cumulative spend.
Building Differentially Private Heatmaps — a concrete release that consumes a calibrated Gaussian scale.

Up: Spatial Noise Mechanisms · Differential Privacy for Geospatial Data