Privacy Budget Composition

Suppose a hospital wants to answer statistics questions about its patients without revealing anyone's personal record. Differential privacy (DP) is the gold standard for doing this: each answer is slightly randomized, so no single patient's data has much influence on the output. The parameter $\varepsilon$ (epsilon) measures the privacy cost — the smaller it is, the stronger the guarantee.

But data analysts rarely ask just one question. They run dozens — or thousands — of queries. And every query chips away at the same underlying dataset. The question becomes: how much total privacy cost has accumulated?

That is the problem of composition. The answer is not obvious. You might hope the costs cancel or stay flat, but they don't — they add up. Composition theorems give precise bounds on how fast $\varepsilon$ grows, and choosing the right theorem can mean the difference between a useful system and one that is either too noisy to be helpful or too revealing to be safe. See also differential privacy for the foundations.

Below you can set a per-query $\varepsilon$ and the number of queries, then watch how the total privacy cost grows under two different composition theorems.

<!-- {{c_intro}} -->
<div class="controls">
  <label>
    <span>{{lbl_eps}}</span>
    <input id="eps-input" type="range" min="0.05" max="1" step="0.05" value="0.1">
    <span id="eps-val" class="val-display">0.10</span>
  </label>
  <label>
    <span>{{lbl_queries}}</span>
    <input id="q-input" type="range" min="1" max="200" step="1" value="50">
    <span id="q-val" class="val-display">50</span>
  </label>
  <label>
    <span>{{lbl_delta}}</span>
    <input id="delta-input" type="range" min="1" max="6" step="1" value="3">
    <span id="delta-val" class="val-display">10<sup>-3</sup></span>
  </label>
</div>
<canvas id="chart" width="540" height="240"></canvas>
<div id="summary" class="summary"></div>
<div class="legend">
  <span class="dot basic"></span> {{legend_basic}}
  <span class="dot adv"></span> {{legend_adv}}
</div>
<button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
.controls label { display: flex; align-items: center; gap: .5rem; font-size: .85rem; }
.controls span:first-child { width: 9rem; flex-shrink: 0; }
.controls input[type=range] { flex: 1; }
.val-display { min-width: 3.5rem; text-align: right; font-weight: 700; font-size: .9rem; color: #1d3557; }
canvas { display: block; max-width: 100%; border: 1px solid #dde3ea; border-radius: 8px; background: #f8fafc; }
.summary { font-size: .85rem; margin: .5rem 0; line-height: 1.5; }
.summary strong { color: #1d3557; }
.legend { display: flex; gap: 1rem; font-size: .8rem; align-items: center; margin-top: .3rem; }
.dot { display: inline-block; width: 24px; height: 3px; border-radius: 2px; vertical-align: middle; }
.dot.basic { background: #e63946; }
.dot.adv { background: #457b9d; border-top: 2px dashed #457b9d; background: none; height: 0; border-bottom: none; }
button.ghost { margin-top: .5rem; font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
               background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }

// Code not found

Notice how basic composition (the solid line) grows strictly linearly — $k$ queries of cost $\varepsilon$ each gives total cost $k\varepsilon$. Advanced composition (the dashed line) grows like $O(\sqrt{k \ln(1/\delta)} \cdot \varepsilon)$, which is sublinear and lets you answer far more questions for the same total budget. The catch: advanced composition requires a tiny extra parameter $\delta$ — a small probability that the guarantee fails entirely.

There are three landmark results in privacy composition:

• Basic composition (trivial but tight in the worst case): run $k$ mechanisms each with privacy cost $\varepsilon_i$, and the composition costs at most $\sum_{i=1}^{k} \varepsilon_i$. If each query costs the same $\varepsilon$, total cost is $k\varepsilon$. This is tight — there exist adversarial input distributions where it cannot be improved. But in practice the adversary rarely chooses the worst case every time.

• Advanced composition (Dwork, Rothblum & Vadhan, 2010): for $k$ mechanisms each with cost $(\varepsilon, 0)$-DP, the composition is $(\varepsilon', \delta)$-DP where $$\varepsilon' = \varepsilon\sqrt{2k\ln(1/\delta)} + k\varepsilon(e^{\varepsilon}-1).$$ For small $\varepsilon$ this is roughly $O(\varepsilon\sqrt{k\ln(1/\delta)})$ — a square-root improvement over $k\varepsilon$.

• Optimal composition (Kairouz, Oh & Viswanath, 2017): the true worst-case privacy curve of $k$ identical mechanisms can be computed exactly from the privacy loss random variable of a single mechanism, yielding the tightest possible bound and sometimes beating even the advanced theorem by a constant.

The practical upshot: basic composition is safe and simple but wastes budget; advanced composition lets you answer roughly $O(1/\varepsilon^2 \ln(1/\delta))$ queries within a fixed total $\varepsilon^*$, far more than basic allows. The choice matters enormously at scale — a census bureau, a search engine, or a federated learning system may run millions of queries and needs every improvement it can get. Related ideas appear in zero-knowledge proofs, where a similar tension between soundness and the number of interaction rounds arises.

Composition is not an abstract theorem — it is the arithmetic that every real DP deployment must do:

• Differentially private machine learning: training a neural network via DP-SGD (Abadi et al., 2016) runs thousands of gradient steps, each consuming budget. The moments accountant — a fine-grained composition technique — is what made training large models feasible.
• Federated learning: millions of devices contribute local model updates. Advanced composition (or Rényi DP) is essential to keep the per-round cost from immediately exhausting the global budget.
• Census and survey data: the US Census Bureau's 2020 Decennial Census used differential privacy with explicit composition accounting to publish detailed tables while provably bounding re-identification risk.
• Database query interfaces: systems like Apple's local DP or Google's RAPPOR track per-user budgets; composition bounds determine how many queries a user can answer before their privacy guarantee degrades.

In every case, a tighter composition bound means either more utility (less noise per query) or more queries within the same budget — often both. The gap between basic and advanced composition can mean the difference between a system that is barely useful and one that drives real decisions.

Every differentially private query is a small withdrawal from a shared account — the privacy budget. Basic composition says the balance falls by $\varepsilon$ each time, linearly and relentlessly. Advanced composition says the effective withdrawal is closer to $\varepsilon/\sqrt{k}$ per query on average, letting you ask far more questions before the account runs dry.

Choosing the right composition theorem is not a technicality. It is the difference between a system that can serve thousands of useful queries and one that burns out after a handful. As DP moves from theory into production — in census bureaus, phone keyboards, and hospital databases — the arithmetic of composition is what makes the whole enterprise viable.

The deeper lesson: privacy is not binary. It is a resource that depletes, and the rate of depletion depends on theorems just as much as on good intentions. See differential privacy for the foundations that make this resource meaningful in the first place.