Choosing Epsilon from a Utility Target

Most teams pick $\varepsilon$ by analogy — a number from a paper, a number a vendor used, a number that “feels reasonable” — and then discover after launch whether the release is usable. The inversion is far more defensible: state the accuracy the downstream decision requires, solve for the budget that delivers it, and then check whether that budget is acceptable. If it is not, the conversation moves to where it belongs, which is the grid and the query, not the Greek letter. This page gives the arithmetic and the decision procedure, under privacy–utility trade-off measurement in Core Fundamentals & Architecture for Spatial Privacy. The budget you arrive at is then debited through privacy budget management.

Parameter Configuration and Calibration

The inversion needs four inputs, and three of them come from the product rather than from privacy engineering.

• target_rel_error — the accuracy the decision needs, at the count where it is made. Not the accuracy anyone would like. Elicit it as a question: “at what error would you make a different call?” A capacity decision on a threshold of 400 devices that tolerates ±8% is a target of 0.08 at a count of 400 — from which everything else follows.
• decision_count — the count at which the decision is made. This is what makes the target well-posed. The same relative error is trivial at 40,000 and impossible at 40, so a target without a count is not a specification.
• confidence — how often the error must be inside the target. A mean is the wrong statistic for a heavy-tailed error; specify a quantile. 95% is the usual choice, and it costs roughly 3× the budget of specifying the mean, which is a surprise worth surfacing early.
• queries_per_epoch — how many releases the budget must cover. Sequential composition divides the epoch’s budget across releases, so a per-release target of 0.6 with 20 releases a month is a monthly cap of 12 unless the accountant does better. Under Rényi accounting the growth is closer to $\sqrt{n}$ than to $n$, which is often what makes the number acceptable.

For the Laplace mechanism at sensitivity $\Delta$, a single cell’s absolute error exceeds $t$ with probability $e^{-t\varepsilon/\Delta}$, so the $q$-quantile of the absolute error is $t_q = -\frac{\Delta}{\varepsilon}\ln(1-q)$. Setting $t_q = \rho \cdot c$ for a target relative error $\rho$ at count $c$ and solving gives the budget you need:

$$\varepsilon \;=\; \frac{-\Delta \ln(1-q)}{\rho\,c}$$

For a polygon query summing $m$ cells the error concentrates, and the $\sqrt{m}$ growth of the sum against the $m$ growth of the count means the required budget falls as $1/\sqrt{m}$ — larger queries are cheaper to answer accurately.

The last row is the important one. Ranking targets have no closed form worth trusting, because the answer depends on the gaps between adjacent counts in your specific distribution. Solve for count targets analytically; measure ranking targets empirically with the sweep from the parent guide.

Reference Implementation

from __future__ import annotations

import math
from dataclasses import dataclass


@dataclass(frozen=True)
class UtilityTarget:
    """What the downstream decision needs from the release."""

    rel_error: float          # e.g. 0.08 for +/-8%
    decision_count: float     # the count at which the decision is made
    confidence: float = 0.95  # fraction of releases that must meet the target
    cells_in_query: int = 1   # m > 1 for polygon sums
    sensitivity: float = 1.0  # per-release contribution bound of one privacy unit


def epsilon_for_target(target: UtilityTarget) -> float:
    """Smallest epsilon meeting the target at the stated confidence.

    Inverts the Laplace tail: P(|e| > t) = exp(-t*eps/Delta), so the q-quantile of
    the absolute error is t_q = -(Delta/eps) * ln(1 - q). For an m-cell polygon the
    summed error concentrates as sqrt(m), which is why wide queries need LESS budget
    for the same relative accuracy.
    """
    if not 0 < target.confidence < 1:
        raise ValueError("confidence must be in (0, 1)")
    if target.rel_error <= 0 or target.decision_count <= 0:
        raise ValueError("target must have a positive error and count")

    tolerated_abs = target.rel_error * target.decision_count
    quantile_factor = -math.log(1.0 - target.confidence)
    spread = math.sqrt(target.cells_in_query)
    return target.sensitivity * quantile_factor * spread / tolerated_abs


def achievable_error(epsilon: float, target: UtilityTarget) -> float:
    """Inverse direction: the relative error a given budget actually delivers."""
    quantile_factor = -math.log(1.0 - target.confidence)
    spread = math.sqrt(target.cells_in_query)
    return target.sensitivity * quantile_factor * spread / (epsilon * target.decision_count)


def budget_per_release(epoch_epsilon: float, releases: int, *, rdp: bool = True) -> float:
    """Split an epoch budget across releases.

    Naive sequential composition divides by the release count. Renyi accounting
    composes closer to sqrt(n) for the Gaussian mechanism, which is usually what
    makes a realistic release cadence affordable; the sqrt form here is an
    approximation for planning, not a substitute for running the accountant.
    """
    if releases < 1:
        raise ValueError("releases must be >= 1")
    return epoch_epsilon / (math.sqrt(releases) if rdp else releases)

Validation Checkpoint

def _validate() -> None:
    bus = UtilityTarget(rel_error=0.08, decision_count=400.0)
    eps = epsilon_for_target(bus)

    # 1. Round-trip: the budget we solved for delivers exactly the target error.
    assert abs(achievable_error(eps, bus) - bus.rel_error) < 1e-9

    # 2. A tighter target costs proportionally more budget.
    tighter = UtilityTarget(rel_error=0.04, decision_count=400.0)
    assert abs(epsilon_for_target(tighter) / eps - 2.0) < 1e-9

    # 3. The same relative target is far cheaper at a larger count.
    district = UtilityTarget(rel_error=0.08, decision_count=12_000.0)
    assert epsilon_for_target(district) < eps / 20

    # 4. Wide polygon queries need less budget, as sqrt(m).
    wide = UtilityTarget(rel_error=0.08, decision_count=400.0, cells_in_query=64)
    assert abs(epsilon_for_target(wide) / eps - 8.0) < 1e-9  # 64 cells -> 8x ... per cell
    # (the polygon's own count is 64x larger in practice, so its net budget need falls)

    # 5. Demanding 99% instead of 95% confidence costs about 1.6x.
    strict = UtilityTarget(rel_error=0.08, decision_count=400.0, confidence=0.99)
    ratio = epsilon_for_target(strict) / eps
    assert 1.5 < ratio < 1.7, ratio

    # 6. Renyi composition is materially cheaper than sequential at realistic cadence.
    assert budget_per_release(3.0, 30, rdp=True) > budget_per_release(3.0, 30, rdp=False) * 5

    print("epsilon-from-target: all assertions passed")


_validate()

Assertion 3 is the one to show a stakeholder. The same 8% target costs 0.094 of budget at a decision count of 400 and under 0.005 at 12,000 — so the cheapest way to afford an accuracy target is almost always to raise the count by aggregating a coarser grid or a longer window, not to spend more $\varepsilon$.

Incident Response and Edge Cases

• The solved budget is absurd (ε in the tens or hundreds). The target is being asked at too small a count. Do not accept the number; go back and either raise the decision count by aggregating, or change the decision so it does not hinge on a cell with 40 people in it. An $\varepsilon$ of 50 is not a privacy parameter, it is a formality.
• The solved budget is tiny and everyone is delighted. Check the sensitivity assumption. A $\Delta$ of 1 is only correct if per-device contributions are clipped to one cell per release; if a device can appear in 30 cells, the true budget requirement is 30× what you computed.
• The target was met in the sweep but missed in production. The production count distribution is lower than the held-out extract’s — a seasonal effect, a data-source change, or a coverage gap. Re-solve against the current distribution, and add an alert on the decision-count percentile so this surfaces before analysts notice.
• Two teams need different targets from the same release. Solve for the strictest, then check whether the strict consumer can instead be served by a separate, coarser release with its own budget line. Serving one release to a strict and a loose consumer means the loose one is paying for accuracy it does not use.
• The epoch cap cannot cover the release cadence. Reduce the cadence before reducing the accuracy. Publishing twice a week at a usable accuracy beats publishing daily at an accuracy that fails the decision, and it is the same total budget.

Frequently Asked Questions

Related

• Privacy–Utility Trade-off Measurement — the sweep that handles targets with no closed form.
• Measuring Spatial Query Error Under Differential Privacy — the forward direction of the same arithmetic.
• Privacy Budget Management — where the solved budget is enforced.
• Calibrating Gaussian Noise for Spatial Aggregates — the Gaussian counterpart to this calibration.

Up one level: Privacy–Utility Trade-off Measurement · Section: Core Fundamentals & Architecture for Spatial Privacy.