Plotting the Privacy–Utility Frontier for Spatial Queries

An epsilon chosen from a table is a guess. An epsilon chosen from a frontier — the curve of achievable error against privacy cost for your workload on your data — is a decision, and it usually lands somewhere the table would not have suggested. The frontier also does something a single number cannot: it identifies configurations that are strictly dominated, and those are the ones to argue about.

Core Calculation permalink

A configuration is a triple: an epsilon $\varepsilon$ , a mechanism $M$ , and a set of structural choices $\theta$ (grid resolution, hierarchy depth, budget split). Each triple yields an expected error on the workload $Q$ :

e(\varepsilon, M, \theta) = \mathbb{E}\!\left[\frac{1}{\lvert Q \rvert} \sum_{q \in Q} \lvert q(D_{\text{priv}}) - q(D) \rvert \right]

The frontier is the lower envelope over all mechanisms and structures at each privacy level:

e^{*}(\varepsilon) = \min_{M, \theta} e(\varepsilon, M, \theta)

A configuration is dominated when some other configuration is at least as good on both axes:

(\varepsilon_1, e_1) \text{ dominated} \iff \exists (\varepsilon_2, e_2) : \varepsilon_2 \le \varepsilon_1 \ \wedge\ e_2 \le e_1

For a flat grid under the Laplace mechanism the frontier has a closed form. With $m$ cells, sensitivity 1 and a uniform split, per-cell error is

e(\varepsilon) = \frac{\sqrt{2}\,m}{\varepsilon}

so the frontier is a hyperbola: halving the error costs a doubling of epsilon, forever. Real frontiers are not hyperbolas, because $\theta$ moves too — a coarser grid at low epsilon beats a fine one, and the envelope over structures bends the curve.

Quantity	Symbol	Role
Privacy parameter	$\varepsilon$	The x-axis; the thing being spent
Workload error	$e$	The y-axis; mean absolute error over $Q$
Structural choices	$\theta$	Grid size, hierarchy, budget split
Knee	$\varepsilon^{\dagger}$	Where $\lvert \mathrm{d}e/\mathrm{d}\varepsilon \rvert$ falls below the decision threshold
Dominated set	—	Configurations no one should choose

Worked numeric example permalink

A workload of 500 random rectangular range queries over a city, evaluated at six epsilons with two structures — a flat 128 × 128 grid and a 4-level hierarchy with a geometric budget split:

$\varepsilon$	Flat grid MAE	Hierarchy MAE	Frontier
0.1	4 210	1 180	1 180
0.25	1 684	512	512
0.5	842	279	279
1.0	421	161	161
2.0	210	104	104
4.0	105	79	79

The flat grid is dominated everywhere below $\varepsilon = 4$ , and even at 4 it is only marginally behind. That is the frontier’s first useful output: it kills a whole structure, not a parameter value.

Its second output is the knee. Between $\varepsilon = 0.5$ and $\varepsilon = 1.0$ the hierarchy’s error drops by 118 for 0.5 of epsilon — 236 error per unit. Between 2.0 and 4.0 it drops by 25 for 2.0 — 12.5 per unit. If your decision threshold is “50 error per unit epsilon is worth paying”, the knee is at $\varepsilon \approx 1.4$ , and everything above that is buying accuracy nobody asked for at a price everyone pays.

The dashed curve is what a team ships when it picks epsilon from a table and the grid from a map. The solid one costs the same privacy and is three to four times more accurate.

Python Implementation permalink

from __future__ import annotations

from dataclasses import dataclass
from typing import Callable, Sequence

import numpy as np


@dataclass(frozen=True)
class Config:
    """One point on the search: a mechanism, its structure, and an epsilon."""
    name: str
    epsilon: float
    build: Callable[[np.ndarray, float], np.ndarray]


def sweep(data: np.ndarray, queries: Sequence[Callable[[np.ndarray], float]],
          configs: Sequence[Config], trials: int = 30,
          seed: int = 0) -> list[dict]:
    """Measure mean absolute workload error for each configuration.

    Repeated trials matter: a single draw of Laplace noise can flatter or
    damn a configuration by a factor of two, and a frontier built from single
    draws will pick whichever mechanism got lucky.
    """
    rng = np.random.default_rng(seed)
    truth = np.array([q(data) for q in queries], dtype=float)
    rows = []

    for cfg in configs:
        errs = []
        for _ in range(trials):
            private = cfg.build(data, cfg.epsilon)
            est = np.array([q(private) for q in queries], dtype=float)
            errs.append(np.abs(est - truth).mean())
        errs = np.asarray(errs)
        rows.append({
            "name": cfg.name,
            "epsilon": cfg.epsilon,
            "mae": float(errs.mean()),
            "mae_p95": float(np.percentile(errs, 95)),
            "trials": trials,
        })
    return rows


def pareto_front(rows: Sequence[dict]) -> list[dict]:
    """Keep only configurations no other configuration beats on both axes."""
    keep = []
    for r in rows:
        dominated = any(
            o is not r and o["epsilon"] <= r["epsilon"] and o["mae"] <= r["mae"]
            and (o["epsilon"] < r["epsilon"] or o["mae"] < r["mae"])
            for o in rows
        )
        if not dominated:
            keep.append(r)
    return sorted(keep, key=lambda r: r["epsilon"])


def find_knee(front: Sequence[dict], threshold: float) -> float | None:
    """Smallest epsilon beyond which |de/dε| falls below `threshold`.

    `threshold` is a policy input, not a statistic: it is the error you are
    willing to pay one unit of epsilon to remove. Someone has to state it.
    """
    for a, b in zip(front, front[1:]):
        d_eps = b["epsilon"] - a["epsilon"]
        if d_eps <= 0:
            continue
        slope = (a["mae"] - b["mae"]) / d_eps
        if slope < threshold:
            return a["epsilon"]
    return front[-1]["epsilon"] if front else None

Most configuration debates are about dominated points. Plotting the front first turns a twelve-way argument into a four-way one.

Verification permalink

Every point must be an average, not a draw. Thirty trials is the minimum for a hierarchy — the variance across draws at low epsilon is large enough that a single measurement will invert two adjacent structures. Report the p95 alongside the mean and reject any configuration whose p95 exceeds the fitness threshold even when its mean passes, because the release is a single draw and the analyst does not get to average.

The workload must be the real one. A frontier built on uniformly random rectangles will flatter hierarchies, which are optimised for exactly that shape. Sample the query set from the access logs of the system that will consume the release, and if there are no logs yet, state that the frontier is provisional.

def frontier_report(rows: list[dict], threshold: float) -> dict:
    """The three facts a frontier exists to produce."""
    front = pareto_front(rows)
    front_names = {r["name"] for r in front}
    return {
        "front": [(r["name"], r["epsilon"], round(r["mae"], 1)) for r in front],
        "dominated": sorted({r["name"] for r in rows} - front_names),
        "knee_epsilon": find_knee(front, threshold),
        # A frontier with one point means the sweep was too narrow to be
        # informative — widen the structural search before reading anything
        # into it.
        "sweep_adequate": len(front) >= 3,
    }

The sweep must be wide enough to have a shape. If the Pareto front contains one point, you swept one structure and the answer is an artefact. Vary the grid resolution across at least a factor of eight and include at least two mechanism families before drawing a curve anyone will quote.

The spread at low epsilon is wide enough to reorder adjacent configurations, which is why the sweep runs thirty trials rather than one.

Edge Cases & Adjustments permalink

Composition across the workload. If the release answers all $\lvert Q \rvert$ queries from one noisy structure, the epsilon on the axis is the total. If each query gets its own noise, the axis is per-query and the totals differ by a factor of $\lvert Q \rvert$ — label the axis explicitly, because the two curves look identical and mean entirely different things.
Relative versus absolute error. Mean absolute error is dominated by the largest cells. If the decision is about small-area estimates, plot relative error or median absolute percentage error instead; the frontier’s shape and its knee both move.
A frontier that is flat. If error barely responds to epsilon across two orders of magnitude, the error is structural — grid resolution, edge effects, sampling bias — and no amount of privacy budget will fix it. That is a valuable negative result: it says spend the effort on the structure and keep the epsilon low.
Re-running after data changes. The frontier is a property of the data as much as the mechanism. Re-run it when the population changes materially, and treat a previously chosen epsilon as provisional until it has been re-checked.
Delta in the approximate-DP case. With $(\varepsilon, \delta)$ -DP the x-axis is two-dimensional. Fix $\delta$ at the release policy’s value and sweep epsilon; a curve that mixes deltas is not a frontier.

FAQ permalink

Where does the knee threshold come from?

From a person, not the data. It is the answer to “how much workload error is one unit of epsilon worth removing?” and it depends on what the release is for. The frontier makes the question answerable; it does not answer it.

Is the knee always the right choice?

No. It is the point beyond which spending gets inefficient, which is an argument for not going higher, not an argument for going that high. If a lower epsilon still clears the fitness threshold, take it.

How many configurations should a sweep contain?

Enough that the Pareto front has at least three points and at least two mechanism families appear among the candidates. Below that the front is a description of your assumptions.

Can I reuse a published frontier from a paper?

Only for orientation. Published frontiers are computed on their data and their workload, and both terms move the curve by more than the mechanism choice does.

Accuracy vs Utility Trade-offs in Geospatial DP — the parent trade-off this curve makes concrete
Choosing Between Pure and Approximate DP for Map Releases — the mechanism family the sweep should include
Privacy Budget Allocation for Spatial Queries — the split that forms part of $\theta$
Utility Preservation Metrics for Masked Maps — alternatives to mean absolute error on the y-axis

← Back to Accuracy vs Utility Trade-offs in Geospatial DP

Plotting the Privacy–Utility Frontier for Spatial Queries

Core Calculation # permalink

Worked numeric example # permalink

Python Implementation # permalink

Verification # permalink

Edge Cases & Adjustments # permalink

FAQ # permalink

Related # permalink

Related topics