Introduction

Every time a machine learning model trains on your medical record, your purchase history, or your private messages, it takes a small gradient step in the direction your data points. Then it does it again. And again. After millions of such steps the model is finished — and, in a very real sense, it has memorized fragments of every record it ever touched.

This is not speculation. Researchers routinely run membership inference attacks that determine, with high confidence, whether a specific person was in the training set — and reconstruction attacks that recover near-verbatim text or images from training data embedded in the model's weights.

Differentially Private Stochastic Gradient Descent (DP-SGD) is the algorithm that changes this. Proposed by Abadi et al. in 2016, it intervenes at the most granular level — the per-example gradient — to give a trained model a mathematical privacy guarantee: no matter what an adversary does with the finished model, they learn almost nothing about whether any particular individual was in the training set.

The two ingredients are simple: clip each example's gradient so no single record can dominate a step, then add Gaussian noise large enough to mask the clipped signal. Repeat for every mini-batch, every epoch. The privacy cost accumulates, like a running tally — the privacy budget — and DP-SGD lets you track exactly how much has been spent.

Try It: Watch the Budget Spend

Adjust the clipping threshold CC and the noise multiplier σ\sigma, then step through training epochs. The chart shows the privacy budget Δ\varepsilon accumulating — the smaller it stays, the stronger the privacy guarantee.

<!-- DP-SGD Privacy Budget Demo — adjust clipping threshold C and noise multiplier sigma -->
<div class="controls">
  <label>
    <span>Clip threshold <em>C</em></span>
    <input id="clip" type="range" min="0.1" max="2" step="0.1" value="1">
    <span id="clipVal" class="val">1.0</span>
  </label>
  <label>
    <span>Noise multiplier <em>&sigma;</em></span>
    <input id="noise" type="range" min="0.5" max="3" step="0.1" value="1.1">
    <span id="noiseVal" class="val">1.1</span>
  </label>
  <label>
    <span>Batch size</span>
    <input id="batch" type="range" min="16" max="256" step="16" value="64">
    <span id="batchVal" class="val">64</span>
  </label>
  <label>
    <span>Dataset size</span>
    <input id="ndata" type="range" min="500" max="5000" step="500" value="1000">
    <span id="ndataVal" class="val">1000</span>
  </label>
</div>
<div class="btns">
  <button id="btnStep" type="button">Step one epoch</button>
  <button id="btnRun" type="button">Run training</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="info-row">
  <span class="badge" id="epsBadge">&varepsilon; = 0.00</span>
  <span class="badge sec" id="epochBadge">Epoch 0</span>
  <span class="badge sec" id="deltaBadge">&delta; = 1e-5</span>
</div>
<canvas id="chart" width="480" height="200"></canvas>
<p id="verdict" class="verdict"></p>

/* Layout and colour for the DP-SGD privacy budget visualiser */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: grid; grid-template-columns: 1fr 1fr; gap: .5rem 1rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .85rem; }
label span:first-child { min-width: 7rem; }
input[type=range] { flex: 1; accent-color: #1d3557; }
.val { min-width: 2.8rem; text-align: right; font-weight: 600; font-variant-numeric: tabular-nums; }
.btns { display: flex; gap: .5rem; margin-bottom: .6rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.info-row { display: flex; gap: .5rem; margin-bottom: .5rem; flex-wrap: wrap; }
.badge { font: 700 13px ui-monospace, monospace; padding: .25rem .55rem;
         border-radius: 6px; background: #e63946; color: #fff; }
.badge.sec { background: #1d3557; }
canvas { width: 100%; border: 1px solid #cdd9e3; border-radius: 8px; display: block; }
.verdict { font-size: .9rem; font-weight: 600; margin: .45rem 0 0; min-height: 1.3em; }
.verdict.good { color: #0a7d33; }
.verdict.warn { color: #b45a00; }
.verdict.bad  { color: #c92f3c; }

/* DP-SGD privacy budget simulator — Renyi DP moments accountant (simplified) */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* training history — one epsilon value per step */
let history = [];
let animId = null;

/* parameter controls */
const $ = id => document.getElementById(id);
const clip  = $('clip');
const noise = $('noise');
const batch = $('batch');
const ndata = $('ndata');

function getParams() {
  return {
    C:     parseFloat(clip.value),
    sigma: parseFloat(noise.value),
    q:     parseInt(batch.value, 10) / parseInt(ndata.value, 10),
    delta: 1e-5
  };
}

/* Renyi DP per-step cost (simplified Gaussian mechanism with subsampling) */
function rdpStep(alpha, C, sigma, q) {
  /* per-step RDP cost for Gaussian mechanism with subsampling rate q */
  const sens = 1.0;
  const base = alpha / (2 * sigma * sigma) * sens * sens;
  return q * q * base;
}

/* convert accumulated RDP to (epsilon, delta)-DP */
function epsilonFromRdp(rdpEps, alpha, delta) {
  /* RDP to approx (eps, delta)-DP via standard conversion */
  return rdpEps + Math.log(1 / delta) / (alpha - 1);
}

function computeEpsilon(steps, C, sigma, q, delta) {
  /* minimise over Renyi orders alpha to get the tightest epsilon */
  const alphas = [2, 4, 8, 16, 32, 64];
  let best = Infinity;
  for (const alpha of alphas) {
    const rdp = steps * rdpStep(alpha, C, sigma, q);
    const eps = epsilonFromRdp(rdp, alpha, delta);
    if (eps < best) best = eps;
  }
  return best;
}

const STEPS_PER_EPOCH = 50;

function currentEpoch() { return Math.floor(history.length / STEPS_PER_EPOCH); }

function stepOnce() {
  const { C, sigma, q, delta } = getParams();
  const step = history.length + 1;
  const eps  = computeEpsilon(step, C, sigma, q, delta);
  history.push(eps);
  draw();
  updateBadges();
}

function draw() {
  const canvas = $('chart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  /* draw chart axes with padding */
  const pad = { t: 14, r: 12, b: 32, l: 42 };
  const iW = W - pad.l - pad.r;
  const iH = H - pad.t - pad.b;

  const maxSteps = Math.max(history.length, STEPS_PER_EPOCH);
  const maxEps   = Math.max(...history, 1, 10);

  /* horizontal grid lines with y-axis labels */
  ctx.strokeStyle = '#e0e6ec';
  ctx.lineWidth = 1;
  for (let i = 0; i <= 4; i++) {
    const y = pad.t + (iH * i / 4);
    ctx.beginPath(); ctx.moveTo(pad.l, y); ctx.lineTo(pad.l + iW, y); ctx.stroke();
    ctx.fillStyle = '#666'; ctx.font = '10px system-ui'; ctx.textAlign = 'right';
    ctx.fillText((maxEps * (1 - i / 4)).toFixed(1), pad.l - 4, y + 3);
  }

  /* x-axis epoch labels */
  ctx.fillStyle = '#666'; ctx.font = '10px system-ui'; ctx.textAlign = 'center';
  for (let e = 0; e <= Math.ceil(maxSteps / STEPS_PER_EPOCH); e++) {
    const x = pad.l + (e * STEPS_PER_EPOCH / maxSteps) * iW;
    ctx.fillText(String(e), x, H - pad.b + 14);
  }
  ctx.fillStyle = '#444'; ctx.font = '11px system-ui';
  ctx.fillText('Epoch', pad.l + iW / 2, H - 2);

  /* rotated y-axis label */
  ctx.save(); ctx.translate(11, pad.t + iH / 2); ctx.rotate(-Math.PI / 2);
  ctx.textAlign = 'center'; ctx.fillText('Δ (privacy cost)', 0, 0); ctx.restore();

  /* reference epsilon thresholds (strong / moderate / weak) */
  const thresholds = [{ v: 1, label: 'Δ=1', col: '#0a7d33' }, { v: 8, label: 'Δ=8', col: '#b45a00' }, { v: 20, label: 'Δ=20', col: '#c92f3c' }];
  for (const t of thresholds) {
    if (t.v > maxEps * 1.05) continue;
    const y = pad.t + iH * (1 - t.v / maxEps);
    ctx.strokeStyle = t.col; ctx.setLineDash([4, 3]); ctx.lineWidth = 1;
    ctx.beginPath(); ctx.moveTo(pad.l, y); ctx.lineTo(pad.l + iW, y); ctx.stroke();
    ctx.fillStyle = t.col; ctx.font = '9px system-ui'; ctx.textAlign = 'left';
    ctx.fillText(t.label, pad.l + 2, y - 2);
  }
  ctx.setLineDash([]);

  /* draw the epsilon curve */
  if (history.length > 0) {
    ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2;
    ctx.beginPath();
    history.forEach((eps, i) => {
      const x = pad.l + ((i + 1) / maxSteps) * iW;
      const y = pad.t + iH * (1 - Math.min(eps, maxEps) / maxEps);
      i === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
    });
    ctx.stroke();
  }
}

function updateBadges() {
  const eps = history.length ? history[history.length - 1] : 0;
  $('epsBadge').textContent = 'Δ = ' + eps.toFixed(2);
  $('epochBadge').textContent = 'Epoch ' + currentEpoch();

  const v = $('verdict');
  if (history.length === 0) { v.textContent = ''; v.className = 'verdict'; return; }
  if (eps <= 1)       { v.textContent = i18nFmt('Δ = %eps% — strong privacy. Model leaks very little.', { eps: eps.toFixed(2) }); v.className = 'verdict good'; }
  else if (eps <= 8)  { v.textContent = i18nFmt('Δ = %eps% — moderate privacy. Acceptable for many real deployments.', { eps: eps.toFixed(2) }); v.className = 'verdict warn'; }
  else                { v.textContent = i18nFmt('Δ = %eps% — weak privacy. Budget nearly exhausted; consider more noise.', { eps: eps.toFixed(2) }); v.className = 'verdict bad'; }
}

function syncLabels() {
  $('clipVal').textContent  = parseFloat(clip.value).toFixed(1);
  $('noiseVal').textContent = parseFloat(noise.value).toFixed(1);
  $('batchVal').textContent = batch.value;
  $('ndataVal').textContent = ndata.value;
}

function reset() {
  if (animId) { clearInterval(animId); animId = null; }
  history = [];
  const canvas = $('chart');
  canvas.getContext('2d').clearRect(0, 0, canvas.width, canvas.height);
  draw();
  updateBadges();
  $('btnRun').textContent = 'Run training';
}

function runAuto() {
  if (animId) {
    clearInterval(animId); animId = null;
    $('btnRun').textContent = 'Run training';
    return;
  }
  $('btnRun').textContent = 'Pause';
  animId = setInterval(() => {
    stepOnce();
    if (history.length >= STEPS_PER_EPOCH * 10) {
      clearInterval(animId); animId = null;
      $('btnRun').textContent = 'Run training';
    }
  }, 60);
}

$('btnStep').addEventListener('click', stepOnce);
$('btnRun').addEventListener('click', runAuto);
$('btnReset').addEventListener('click', reset);
[clip, noise, batch, ndata].forEach(el => {
  el.addEventListener('input', () => { syncLabels(); reset(); });
});

syncLabels();
draw();
Result
Console

Notice the trade-off: lower noise trains faster but drains the budget quickly. Higher noise keeps Δ\varepsilon small but slows learning. The clipping threshold CC controls how much a single example can influence any one step — tighter clipping reduces sensitivity, so the same noise goes further. This three-way tension between privacy, utility, and compute is the heart of private machine learning — exactly what PAC learning formalized for ordinary learnability.

The Real Complexity

The mechanism is simple; the accounting is subtle.

The basic guarantee. A randomized algorithm M\mathcal{M} is (Δ,ÎŽ)(\varepsilon, \delta)-differentially private if, for any two datasets DD and Dâ€ČD' differing in exactly one row, and any output set SS:

Pr⁥[M(D)∈S]≀eΔ⋅Pr⁥[M(Dâ€Č)∈S]+ÎŽ\Pr[\mathcal{M}(D) \in S] \le e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta

Small Δ\varepsilon means the model behaves nearly identically whether or not your record was included. Ύ\delta is a tiny failure probability (usually <1/n< 1/n where nn is the dataset size).

Sensitivity and the Gaussian mechanism. The ℓ2\ell_2-sensitivity of a gradient is the maximum by which one example can shift it. Clipping each gradient to norm CC bounds this sensitivity at CC. The Gaussian mechanism then adds noise N(0, σ2C2I)\mathcal{N}(0,\, \sigma^2 C^2 \mathbf{I}) to mask the contribution. A single step is private — but training runs hundreds of thousands of steps.

Composition is the hard part. Naive composition would say: TT steps each with privacy cost Δ0\varepsilon_0 add up to TΔ0T\varepsilon_0. That blows the budget immediately. The key insight of Abadi et al. (2016) was the moments accountant, later unified under RĂ©nyi Differential Privacy (RDP). Because each mini-batch is a random subsample of the dataset, privacy amplification by subsampling kicks in: the effective Δ\varepsilon per step scales as q⋅Δ0q \cdot \varepsilon_0 where q=batch/nq = \text{batch}/n is the sampling ratio, often much less than 1. Tracking the RĂ©nyi divergence across steps gives a tight final (Δ,ÎŽ)(\varepsilon, \delta) at the end of training — orders of magnitude better than naive composition.

The utility cost. Adding noise degrades the signal-to-noise ratio of each gradient update. In practice, models trained with DP-SGD at Δ≈8\varepsilon \approx 8 reach accuracy only a few percentage points below non-private baselines on large datasets (ImageNet, C4). Tight Δ≈1\varepsilon \approx 1 still costs a measurable accuracy drop — the fundamental tension that no algorithm can fully escape, because PAC learning bounds tell us information must flow from data to model, and DP limits that flow.

Where It Matters

DP-SGD is not a research curiosity — it is in production at the world's largest technology companies:

  • Google's Gboard: the on-device language model that suggests your next word is trained with DP-SGD and federated learning, so your keystrokes never leave your phone in a form that could identify you.
  • Apple's on-device models: keyboard, emoji prediction, and Siri personalization all use differential privacy techniques rooted in DP-SGD.
  • Medical AI: hospitals and research consortia use DP-SGD to train diagnostic models across institutions without sharing patient records — a direct regulatory requirement under HIPAA and GDPR.
  • Financial fraud detection: banks train anomaly detectors on transaction data where individual records are highly sensitive and legally protected.
  • Large language models: OpenAI, Google DeepMind, and academic groups have published DP-trained variants of transformer models, studying how much privacy costs in perplexity.

The key enabler is federated learning with DP-SGD: each device computes gradients locally, clips them, adds noise locally, and only the noisy aggregate is ever sent to a server. No raw data leaves the device and the server-side model has a formal privacy guarantee — the combination that makes large-scale private ML feasible. This intersects directly with the study of what is learnable at all, as explored in PAC learning and non-convex optimization.

Conclusion

DP-SGD answers a question that used to seem impossible: can you teach a model without letting it remember who taught it? The answer is yes — if you are willing to pay in noise. Clip every gradient, add calibrated Gaussian noise, track the budget with the moments accountant, and the resulting model carries a formal certificate: no adversary, no matter how powerful, can learn much more about any individual than they could from the model trained without that individual.

The algorithm is settled. What is not settled are the trade-offs: how much accuracy must be sacrificed for a given Δ\varepsilon, how to spend the budget wisely across heterogeneous layers, and whether stronger privacy guarantees can be achieved with less noise through better architectures. Those remain active research questions — and the privacy budget ticking down with each epoch is a constant reminder that in machine learning, nothing comes for free.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/dp-sgd/Content licensed under CC BY-NC 4.0.