Differentially Private SGD

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.

Adjust the clipping threshold $C$ 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.

<!-- {{c_demo_intro}} -->
<div class="controls">
  <label>
    <span>{{lbl_clip}} <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>{{lbl_noise}} <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>{{lbl_batch}}</span>
    <input id="batch" type="range" min="16" max="256" step="16" value="64">
    <span id="batchVal" class="val">64</span>
  </label>
  <label>
    <span>{{lbl_n}}</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">{{btn_step}}</button>
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="info-row">
  <span class="badge" id="epsBadge">&varepsilon; = 0.00</span>
  <span class="badge sec" id="epochBadge">{{lbl_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>

/* {{c_css_intro}} */
* { 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; }

// Code not found

Notice the trade-off: lower noise trains faster but drains the budget quickly. Higher noise keeps $\varepsilon$ small but slows learning. The clipping threshold $C$ 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 mechanism is simple; the accounting is subtle.

The basic guarantee. A randomized algorithm $\mathcal{M}$ is $(\varepsilon, \delta)$-differentially private if, for any two datasets $D$ and $D'$ differing in exactly one row, and any output set $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$ where $n$ is the dataset size).

Sensitivity and the Gaussian mechanism. The $\ell_2$-sensitivity of a gradient is the maximum by which one example can shift it. Clipping each gradient to norm $C$ bounds this sensitivity at $C$. The Gaussian mechanism then adds noise $\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: $T$ steps each with privacy cost $\varepsilon_0$ add up to $T\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 \cdot \varepsilon_0$ where $q = \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 $\varepsilon \approx 8$ reach accuracy only a few percentage points below non-private baselines on large datasets (ImageNet, C4). Tight $\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.

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.

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.