Differential Privacy Optimization

Privacy Saturation in Noisy-SGD

By Aayushman, Kaushik Doddamani, and Pranav

August 17, 2026 · IIT Madras · 9 min read

Every standard privacy accountant for differentially private training tells you the same story: run the optimizer for more steps, and you pay more privacy budget. Full stop, no exceptions. It turns out that story is wrong — or at least incomplete — for a large and useful class of training problems. Under the right conditions, privacy loss can stop growing altogether, long before training ends.

This post walks through why that happens, working from the paper “Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss” by Altschuler and Talwar (2023), which we studied and wrote up as a course report. The result is called privacy saturation, and the argument behind it is a nice example of how thinking about an algorithm as a dynamical process, rather than a sequence of independent leaks, changes the answer.

The puzzle

Differentially private machine learning almost always means one thing in practice: DP-SGD, also called Noisy-SGD. It's an easy modification of ordinary stochastic gradient descent — clip each per-example gradient so no single training point can dominate the update, average the clipped gradients over a minibatch, and add Gaussian noise before applying the step. Popularized by Abadi et al. in 2016, it's now the default primitive behind TensorFlow Privacy, Opacus, and most JAX-based private training stacks.

The question this post is about is not how well Noisy-SGD optimizes — it's how its privacy cost behaves as a function of the number of iterations \(T\). The textbook analysis treats every noisy gradient step as its own little privacy-releasing mechanism, then composes the cost across all \(T\) steps. Using Rényi differential privacy (RDP), which composes cleanly, this gives a bound of the form

$$\varepsilon_{\mathrm{RDP}}(T) \lesssim \frac{\alpha L^2}{n^2 \sigma^2}\,T.$$

That bound is linear in \(T\). Every additional epoch, every additional pass over the data, adds a fixed increment to your privacy budget — even if your model converged thousands of steps ago and is no longer doing anything with the data except quietly restating what it already learned. That has always felt like it's leaving something on the table: composition bounds are worst-case over what an adversary could extract from each step, but they don't account for the fact that Noisy-SGD is not a sequence of unrelated queries. It's an iterative, noisy, contractive process, and contractive processes tend to forget.

The saturation result

Altschuler and Talwar make that intuition precise. For convex, \(L\)-Lipschitz, \(M\)-smooth losses over a bounded convex domain \(K \subset \mathbb{R}^d\) of diameter \(D\), and step size \(\eta \le 2/M\), the privacy loss doesn't grow forever — it grows for a while and then flattens.

The result, informally

$$\varepsilon_{\mathrm{RDP}}(T) \;\lesssim\; \frac{\alpha L^2}{n^2\sigma^2}\, \min\!\left\{T,\; \frac{Dn}{L\eta}\right\}.$$

The privacy loss increases linearly with \(T\), exactly as before — but only up to a burn-in time \(\bar T \approx \dfrac{Dn}{L\eta}\). After that, running the optimizer for more iterations costs essentially nothing extra.

This is privacy saturation: past the burn-in period \(\bar T\), you can keep training — more epochs, more passes, more convergence — without the privacy accountant charging you for it beyond a constant factor. That's a qualitatively different shape than the straight line every standard composition theorem draws.

Why saturation happens: two forces in tension

The mechanism behind the bound is a competition between two effects that push in opposite directions as you look further back into the training run.

Sampling makes recent steps expensive

At each iteration, a changed data point only shows up in the minibatch with probability \(b/n\). This is the standard privacy amplification by sampling argument used throughout the DP-SGD literature: because the sensitive point is usually absent from the minibatch, each individual step is cheaper than it would be if the point were always included. Applied to a block of \(R\) consecutive iterations, this contributes a cost that grows linearly in \(R\):

$$\text{sampling cost} \;\approx\; \frac{\alpha L^2}{n^2\sigma^2}\, R.$$

Iteration makes distant steps cheap

Here's the part that composition-based analyses miss entirely. Take two runs of Noisy-SGD on adjacent datasets, and suppose that \(R\) iterations before the end they were sitting at two different points inside \(K\). Because \(K\) has diameter \(D\), those two starting points are at most \(D\) apart. From there, every subsequent update is a projected gradient step — which, for \(\eta \le 2/M\), is non-expansive — composed with an injection of Gaussian noise. Non-expansive maps don't amplify the gap between the two trajectories, and Gaussian noise blurs whatever gap remains. So the more iterations \(R\) you let this contract-and-blur process run for, the harder it becomes to tell the two trajectories apart. This is privacy amplification by iteration (Feldman, Mironov, Talwar, and Thakurta), and it contributes a cost that shrinks as \(R\) grows:

$$\text{iteration cost} \;\approx\; \frac{\alpha D^2}{\eta^2\sigma^2 R}.$$

Balancing the two

Add the two contributions and you get a function of \(R\) that first falls, then rises — classic \(AR + B/R\) shape. Minimizing over \(R\) (formally: taking the derivative and setting it to zero) gives the optimal window length

$$R^{\star} \;\asymp\; \frac{Dn}{L\eta},$$

which is exactly the burn-in time \(\bar T\) from the theorem above. Below this scale, sampling composition dominates and the bound is linear in \(T\), same as the naive analysis. Above it, the story changes: no matter how large \(T\) gets, you only ever need to pay for the last \(\bar T\) iterations, because the earlier ones have been geometrically “forgotten” by the contraction.

The proof, sketched

The elegant move in the proof is a restart trick: instead of trying to bound the privacy loss of all \(T\) iterations directly, fix a cutoff \(\tau = T - R\) and only analyze the final \(R\) iterations. The first \(\tau\) iterations are never directly “charged” — their only relevance is that they leave both trajectories, \(W_\tau\) and \(W_\tau'\), somewhere inside the bounded set \(K\), and therefore no more than \(D\) apart. This is where boundedness of the domain is doing real work: it's what lets the proof throw away everything before time \(\tau\) and still get a meaningful starting condition for the last stretch.

Making the restart argument rigorous requires a way to talk about “this initial gap of size \(D\)” and “this later divergence in distribution” in the same currency. That's where optimal transport enters. The key object is the shifted Rényi divergence

$$D_\alpha^{(z)}(\mu \Vert \nu) \;=\; \inf_{\tilde\mu:\, W_\infty(\tilde\mu,\mu) \le z} D_\alpha(\tilde\mu \Vert \nu),$$

where \(W_\infty\) is the \(\infty\)-Wasserstein distance — the smallest \(z\) such that \(\mu\) and \(\nu\) can be coupled so that the corresponding random variables never differ by more than \(z\). The shifted divergence says: before you measure how distinguishable two distributions are, you're allowed to move one of them by up to \(z\) at no cost. It's exactly the right notion for a noisy contractive process, because it lets you separate two very different kinds of distance:

A pair of lemmas convert between the two: a shift-reduction lemma shows that convolving with Gaussian noise turns a unit of remaining geometric shift \(a\) into a Rényi cost of \(\alpha a^2 / 2\sigma^2\), and a contraction-reduction lemma shows that pushing two coupled points through a non-expansive map never increases the shift you need to account for. Chaining these step by step from \(t=T\) back to \(t=\tau+1\), and using that the total gap at time \(\tau\) is at most \(D\), gives the diameter-aware bound

$$D_\alpha\!\left(P_{W_T} \,\Vert\, P_{W_T'}\right) \;\le\; \frac{\alpha}{2}\sum_{t=\tau+1}^{T} \frac{a_t^2}{\sigma_t^2}$$

for any allocation of “shift budget” \(a_{\tau+1},\dots,a_T\) that sums (with the per-step contraction amounts) to exactly cancel the initial gap \(D\) by the end. Choosing this allocation uniformly, \(a_t = D/R\), and combining with the sampling-term bound from the same window, reproduces the \(AR + B/R\) trade-off above — and optimizing over \(\tau\) (equivalently, over \(R\)) gives the saturation theorem.

What this means in practice

The practical upshot is a genuinely different way to think about the privacy cost of training runs that have converged:

  1. Privacy accounting for DP-SGD need not be a straight line against iteration count — in the convex, smooth, bounded-domain setting, it plateaus.
  2. The plateau point \(\bar T \approx Dn/(L\eta)\) is set by the geometry of the problem (domain size, dataset size, smoothness, step size) rather than by how long you happen to train for.
  3. This matters most exactly where naive composition hurts most: many-epoch training, federated settings with huge round counts, and any pipeline where you'd like the freedom to keep optimizing without continuously eating into an \(\varepsilon\) budget.

Where this breaks down

The saturation argument leans on three ingredients that don't come for free: convexity, smoothness with a step size satisfying \(\eta \le 2/M\), and a bounded domain \(K\). Take any of them away and the restart trick loses its footing — without a diameter \(D\), there's no bound on the initial gap at time \(\tau\); without non-expansiveness, contraction can't be relied on to shrink that gap at all. Extending privacy saturation to the nonconvex, unconstrained settings that dominate modern deep learning — where DP-SGD is actually deployed most often — remains open, and is, to us, the most interesting direction the paper leaves on the table.

This report was written for a graduate course on privacy and optimal transport. An LLM was used only for permitted support tasks — understanding background material, locating related work, and clarifying technical concepts. All factual claims, references, equations, and proof steps were independently verified against the original papers and standard scholarly sources.

Read the full report (PDF), which includes the complete proofs, the background on computational optimal transport, and the appendix lemmas summarized above.

References