Introduction

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.

Try It

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.

<!-- Privacy Budget Composition demo — compare basic vs advanced composition -->
<div class="controls">
  <label>
    <span>Per-query ε:</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>Queries (k):</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>δ (advanced only):</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> Basic composition (linear)
  <span class="dot adv"></span> Advanced composition (sqrt)
</div>
<button id="reset-btn" type="button" class="ghost">Reset</button>

/* Demo styles: controls, chart canvas, legend, summary text */
* { 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; }

/* Privacy budget composition: visualise how total epsilon grows with number of queries */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* DOM element references */
const epsInput   = document.getElementById('eps-input');
const epsVal     = document.getElementById('eps-val');
const qInput     = document.getElementById('q-input');
const qVal       = document.getElementById('q-val');
const deltaInput = document.getElementById('delta-input');
const deltaVal   = document.getElementById('delta-val');
const canvas     = document.getElementById('chart');
const ctx        = canvas.getContext('2d');
const summary    = document.getElementById('summary');

const DELTA_EXPS = [1, 2, 3, 4, 5, 6]; // delta = 10^(-exp), exp ranges 1..6
const DEFAULTS = { eps: 0.1, queries: 50, deltaExp: 3 };

function getDelta() {
  // convert slider position to delta value
  return Math.pow(10, -DELTA_EXPS[parseInt(deltaInput.value, 10) - 1]);
}

// Basic composition: total epsilon grows linearly with k
function basicCompose(eps, k) { return eps * k; }

// Advanced composition: Dwork-Rothblum-Vadhan 2010, sublinear growth
function advCompose(eps, k, delta) {
  if (k === 0) return 0;
  const term1 = eps * Math.sqrt(2 * k * Math.log(1 / delta));
  const term2 = k * eps * (Math.exp(eps) - 1);
  return term1 + term2;
}

function drawChart(eps, maxK, delta) {
  const W = canvas.width, H = canvas.height;
  const PAD = { top: 16, right: 16, bottom: 36, left: 52 };
  const pw = W - PAD.left - PAD.right;
  const ph = H - PAD.top  - PAD.bottom;
  ctx.clearRect(0, 0, W, H);

  // compute max values for y-axis scaling
  const basicMax = basicCompose(eps, maxK);
  const advMax   = advCompose(eps, maxK, delta);
  const yMax     = Math.max(basicMax, advMax, eps) * 1.1;

  const xScale = (k) => PAD.left + (k / maxK) * pw;
  const yScale = (v) => PAD.top + ph - (v / yMax) * ph;

  // draw background grid lines and axis tick labels
  ctx.strokeStyle = '#dde3ea';
  ctx.lineWidth = 1;
  for (let i = 0; i <= 4; i++) {
    const y = PAD.top + (ph / 4) * i;
    ctx.beginPath(); ctx.moveTo(PAD.left, y); ctx.lineTo(PAD.left + pw, y); ctx.stroke();
    const label = ((yMax * (4 - i)) / 4).toFixed(2);
    ctx.fillStyle = '#888'; ctx.font = '10px system-ui'; ctx.textAlign = 'right';
    ctx.fillText(label, PAD.left - 4, y + 4);
  }
  for (let i = 0; i <= 4; i++) {
    const x = PAD.left + (pw / 4) * i;
    ctx.beginPath(); ctx.moveTo(x, PAD.top); ctx.lineTo(x, PAD.top + ph); ctx.stroke();
    const label = Math.round((maxK / 4) * i);
    ctx.fillStyle = '#888'; ctx.font = '10px system-ui'; ctx.textAlign = 'center';
    ctx.fillText(label, x, PAD.top + ph + 14);
  }

  // draw the basic (linear) composition curve in red
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 2.2;
  ctx.setLineDash([]);
  ctx.beginPath();
  for (let k = 0; k <= maxK; k++) {
    const x = xScale(k), y = yScale(basicCompose(eps, k));
    k === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();

  // draw the advanced (sqrt) composition curve in blue dashed
  ctx.strokeStyle = '#457b9d';
  ctx.lineWidth = 2.2;
  ctx.setLineDash([6, 4]);
  ctx.beginPath();
  for (let k = 0; k <= maxK; k++) {
    const x = xScale(k), y = yScale(advCompose(eps, k, delta));
    k === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();
  ctx.setLineDash([]);

  // draw axis labels
  ctx.fillStyle = '#444'; ctx.font = '11px system-ui';
  ctx.textAlign = 'center';
  ctx.fillText('Number of queries (k)', PAD.left + pw / 2, H - 4);
  ctx.save(); ctx.translate(12, PAD.top + ph / 2); ctx.rotate(-Math.PI / 2);
  ctx.fillText('Total ε', 0, 0); ctx.restore();
}

function updateSummary(eps, maxK, delta) {
  const b = basicCompose(eps, maxK).toFixed(3);
  const a = advCompose(eps, maxK, delta).toFixed(3);
  const ratio = (basicCompose(eps, maxK) / Math.max(advCompose(eps, maxK, delta), 0.0001)).toFixed(1);
  summary.innerHTML =
    '<strong>' + i18nFmt('Basic: %k% queries × ε=%eps% → total ε = %total%', { k: maxK, eps: eps.toFixed(2), total: b }) + '</strong><br>' +
    i18nFmt('Advanced: total ε = %total% (%ratio%× smaller than basic)', { total: a, ratio: ratio });
}

function update() {
  const eps   = parseFloat(epsInput.value);
  const maxK  = parseInt(qInput.value, 10);
  const delta = getDelta();
  const exp   = DELTA_EXPS[parseInt(deltaInput.value, 10) - 1];
  epsVal.textContent  = eps.toFixed(2);
  qVal.textContent    = maxK;
  deltaVal.innerHTML  = '10<sup>-' + exp + '</sup>';
  drawChart(eps, maxK, delta);
  updateSummary(eps, maxK, delta);
}

function resetAll() {
  epsInput.value   = DEFAULTS.eps;
  qInput.value     = DEFAULTS.queries;
  deltaInput.value = DEFAULTS.deltaExp;
  update();
}

epsInput.addEventListener('input', update);
qInput.addEventListener('input', update);
deltaInput.addEventListener('input', update);
document.getElementById('reset-btn').addEventListener('click', resetAll);
update();
Result
Console

Notice how basic composition (the solid line) grows strictly linearly — kk queries of cost ε\varepsilon each gives total cost kεk\varepsilon. Advanced composition (the dashed line) grows like O(kln⁡(1/δ)⋅ε)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.

The Real Complexity

There are three landmark results in privacy composition:

  • Basic composition (trivial but tight in the worst case): run kk mechanisms each with privacy cost εi\varepsilon_i, and the composition costs at most ∑i=1kεi\sum_{i=1}^{k} \varepsilon_i. If each query costs the same ε\varepsilon, total cost is kε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 kk mechanisms each with cost (ε,0)(\varepsilon, 0)-DP, the composition is (ε′,δ)(\varepsilon', \delta)-DP where $ε′=ε2kln⁡(1/δ)+kε(eε−1).\varepsilon' = \varepsilon\sqrt{2k\ln(1/\delta)} + k\varepsilon(e^{\varepsilon}-1).$ For small ε\varepsilon this is roughly O(εkln⁡(1/δ))O(\varepsilon\sqrt{k\ln(1/\delta)}) — a square-root improvement over kεk\varepsilon.

  • Optimal composition (Kairouz, Oh & Viswanath, 2017): the true worst-case privacy curve of kk 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/ε2ln⁡(1/δ))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.

Where It Matters

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.

Conclusion

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 ε/k\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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/privacy-budget-composition/Content licensed under CC BY-NC 4.0.