Anchored Clipping: Making Private Gradient Noise Shrink as the Model Converges

Training with differential privacy means each example's gradient is capped at a threshold $C$ (clipping) and Gaussian noise proportional to $C$ is added before each update. The noise level is therefore set by the clipping threshold, and the threshold does not know how close the model is to a good solution. Near the optimum the useful signal shrinks, but the noise does not. That fixed noise floor is one reason private training converges at the "slow" rate, with error falling like $1/\sqrt{n}$ in the sample size $n$. The same threshold is also the most fragile setting to tune under privacy, and the noise it controls is what is supposed to stop attackers from rebuilding training images out of shared gradients.

We propose to clip the change in each example's gradient relative to a periodically refreshed, privately computed anchor point, rather than the gradient itself, and to set the threshold automatically as a quantile of those change norms. For smooth problems the change norm is bounded by the distance to the anchor. So the injected noise variance falls in proportion to the remaining excess risk. That is the same variance-tracks-excess-risk structure (a "Bernstein condition") that learning theory uses to get fast $1/n$ rates. In plain terms, the privacy noise decays at the pace the theory needs. We aim to get fast-rate guarantees for mini-batch private SGD, to remove hand-tuning of the clipping threshold, and to test whether the resulting updates leak more or less to gradient-inversion attackers at matched privacy.

Core Claim

Fast-rate analyses of private learning so far hold only for full-batch gradient perturbation with a fixed normalization. Sharper Utility Bounds for Differentially Private Models and its pairwise-learning companion Towards sharper excess risk bounds for differentially private pairwise learning use the Generalized Bernstein condition to prove an $\mathcal{O}(\sqrt{p}/(n\epsilon))$ high-probability excess-risk bound under smoothness and a Polyak–Łojasiewicz condition, where $p$ is the dimension and $\epsilon$ the privacy budget. They leave mini-batch DP-SGD explicitly open. Adaptive clipping, as in Differentially Private Learning with Adaptive Clipping, tracks a quantile of raw per-example gradient norms using a privatized one-bit count and does away with threshold tuning. It has no excess-risk theory, though. We also argue it cannot close the gap in noisy, non-interpolating problems. At the optimum $w^*$ the average gradient is zero, but individual gradients $\nabla\ell(w^*;z)$ are not, so their median norm, and with it the noise, stays bounded away from zero.

Our claim is that the missing ingredient is a clipping target whose natural scale vanishes at the optimum. Let $\tilde w$ be an anchor refreshed every $K$ steps, and let $\hat g$ be its privatized full-data gradient: the average of clipped per-example gradients at $\tilde w$ plus Gaussian noise. Anchored clipping updates

$$w_{t+1} = w_t - \eta\Big[\hat g + \tfrac{1}{b}\Big(\textstyle\sum_{i\in S_t}\mathrm{clip}_{C_t}\big(\nabla\ell(w_t;z_i)-\nabla\ell(\tilde w;z_i)\big) + \mathcal{N}(0,\sigma^2C_t^2 I)\Big)\Big],$$

where $S_t$ is a mini-batch of size $b$, $\sigma$ is the noise multiplier, and $C_t$ is tracked as the $\gamma$-quantile of the difference norms with the private one-bit mechanism of Andrew et al. If each loss is $L$-smooth, every difference has norm at most $L\|w_t-\tilde w\|$. Under the Polyak–Łojasiewicz condition, the squared distance to the optimum is controlled by excess risk. Together these give

$$\mathbb{E}\,\|\text{injected noise}\|^2 \;\lesssim\; \sigma^2 p\, L^2\,\big(R(w_t)-R(w^*) + R(\tilde w)-R(w^*)\big),$$

where $R$ is population risk. The optimizer's own noise then satisfies a Bernstein-type condition with exponent one. That is the property that turns $\sqrt{\cdot}$ deviation terms into linear ones in the stability-based analysis of Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$.

What remains is the cost of the anchor gradients. These are exactly the full-batch perturbations Kang et al. already analyze. We therefore expect the mini-batch method to inherit their $\mathcal{O}(\sqrt{p}/(n\epsilon))$ rate, while spending most steps on cheap mini-batch updates. The anchor-difference idea is related to variance-reduced optimization. The file contains no private variance-reduced method, so we cannot rule out that a private variance-reduced method with fixed clipping exists elsewhere. The contribution we claim is the pairing of anchor differences with a quantile-tracked threshold and a Bernstein-coupled rate proof. We do not claim the anchor trick itself.

Research Program

The theoretical part proves a high-probability excess-risk bound for anchored clipping under smoothness, the PL condition and the Generalized Bernstein condition. Privacy is accounted by composing the anchor refreshes with subsampled mini-batch steps and the one-bit quantile queries. Two questions decide whether the result is worth having. The first is how the refresh period $K$ trades anchor privacy cost against drift. The second is whether the quantile tracker's lag can break the coupling in the displayed bound. The tracker's multiplicative update means an overly large initial threshold, which Andrew et al. flag as a failure mode, decays only geometrically, so we will bound that transient explicitly. We will also say which quantile $\gamma$ the theory prefers. If the bound depends on $\gamma$ only through constants, the method has no clipping threshold to tune. That addresses the tuning-privacy cost raised by Differentially Private Normalizing Flows for Privacy-Preserving Density Estimation.

The empirical part asks whether the mechanism survives outside the smooth, PL regime, and what it costs on two fronts. The first cost is generalization. The privacy-regularization literature argues that DP noise prevents memorization. Towards Better Generalization of Adaptive Gradient Methods, for instance, deliberately injects DP noise into Adam and reports Penn Treebank perplexity of 60.66 versus 66.02 for Adam. Shrinking the noise late in training could give that benefit back. So the generalization gap is a measured outcome, not an assumption.

The second cost is leakage. Anchored updates reveal per-example gradient differences, which behave roughly like a per-example curvature applied to $w_t-\tilde w$. The formal $\epsilon$ is fixed by $\sigma$ alone, so it is identical to DP-SGD at matched $\sigma$. Empirical reconstruction risk could still differ. The motivation for measuring it is On the utility and protection of optimization with differential privacy and classic regularization techniques, which found DP-SGD noise can make model inversion easier while plain weight decay improved inversion resistance by 73.8% on average.

Baselines

The naive reference point is DP-SGD with a fixed clipping threshold as in Deep Learning with Differential Privacy. That paper reports 97% MNIST test accuracy and 73% CIFAR-10 test accuracy at $\epsilon=8$. We give it an oracle advantage: its threshold is tuned in hindsight over a grid, and that tuning is not charged to its privacy budget. Anchored clipping is charged for everything it does.

The strongest competitor on the tuning question is quantile adaptive clipping from Differentially Private Learning with Adaptive Clipping, run with its median default. This comparison isolates the anchor, since it is our method with the anchor removed. Its gains over the best fixed threshold are only plotted in that paper, so there is no reported numerical result on Lacuna for adaptive clipping.

The strongest existing fast-rate method is m-NGP from Sharper Utility Bounds for Differentially Private Models, which is full-batch. Its accuracy is reported only in figures on Iris and Adult, so there is no reported numerical result on Lacuna for m-NGP. On deep, heavy-tailed tasks we add DC-DPSGD from Clip Body and Tail Separately, which reports up to 9.72% accuracy gains over standard DP-SGD clipping variants on CIFAR-10 and CIFAR-10-HT.

Two ablations complete the set: anchored differences with a fixed tuned threshold, and anchored clipping at several refresh periods $K$. The first separates the anchor from the tracker. The second tests whether the rate depends on $K$ as the theory predicts.

All methods share data splits, model architecture, total $\epsilon$ and $\delta$, and a gradient-evaluation budget. Every baseline gets the same number of hindsight-tuned learning-rate trials.

Beating the baselines means two things. In the convex setting, excess risk must fall with a log-log slope near $-1$ in $n$ where fixed and median clipping show slopes near $-1/2$. On deep tasks, accuracy at matched $\epsilon$ must be no lower than oracle fixed clipping without any threshold search. For leakage, the baseline is GIAS from Gradient Inversion with Generative Image Prior, which reports 15.58 dB PSNR on 64×64 ImageNet against undefended models. The undefended reference is 59.20 dB on MNIST from Concealing Sensitive Samples against Gradient Leakage in Federated Learning.

Why not just…?

Why not just use median adaptive clipping, which already lets the threshold fall? This is the most serious threat. Our argument is that raw per-example gradient norms do not go to zero at the optimum of a noisy problem, so the median, and the noise with it, plateau. That is an empirical claim, and we test it directly by logging the tracked threshold against excess risk on Adult and Bank-marketing logistic regression. If the median threshold already decays in proportion to the square root of excess risk and matches our excess-risk slope, the anchor adds nothing. In that case the contribution shrinks to a fast-rate proof for Andrew et al.'s method, and we would report it that way.

Why not just use mega-batches? Simple Baselines Are Strong Performers for Differentially Private Natural Language Processing shows that large batches make simple DP-Adam competitive. Larger batches divide the noise by $b$, but the noise floor is still set by a threshold that does not shrink. Under fixed $\epsilon$, larger batches also mean fewer steps. We sweep batch size at fixed $\epsilon$ for both methods. If mega-batch fixed clipping reaches the same excess-risk slope, the rate argument fails. Federated clients also cannot hold very large batches, which matters for the FEMNIST setting.

Why not just use weight decay and skip formal privacy, given that it resisted inversion better? The comparison in the utility-and-protection paper is real evidence. However, it concerns a custom model-inversion attack, not generative-prior gradient inversion, and weight decay provides no $\epsilon$. We include weight decay without noise as a leakage reference under GIAS. If it matches our method's reconstruction resistance at equal accuracy, we will say so. The value of formal privacy then rests on its guarantee against adaptive attackers, such as the meta-learned prior GIML described in the GIAS paper, rather than on measured PSNR.

Proposed Experiments

The first experiment is the decisive check on the theory. It uses $\ell_2$-regularized logistic regression on Adult, Bank-marketing, Breast Cancer and Credit Card Fraud, the benchmarks used by Kang et al. We subsample $n$ over a decade at $\epsilon\in\{0.5,1,4\}$ and plot excess risk, measured against a non-private solution on held-out data, as a function of $n$. The prediction is a slope near $-1$ for anchored clipping and m-NGP, and near $-1/2$ for fixed and median clipping. We also check that anchored clipping reaches m-NGP's risk with a fraction of its full-data gradient passes.

The second experiment moves to deep, non-convex models. We use MNIST and CIFAR-10 in the centralized setting and FEMNIST across clients, at $\epsilon\in\{1,4,8\}$. We report test accuracy, the generalization gap and threshold trajectories, and we track the difference-norm bound empirically to see where smoothness breaks down. Success means matching or exceeding oracle-tuned fixed clipping with zero threshold search. The generalization gap tells us whether shrinking noise sacrifices the regularization benefit.

The third experiment measures leakage under a threat model where the attacker sees the privatized update. We run GIAS on CIFAR-10 and 64×64 ImageNet at batch sizes up to 32, attacking both fixed-clip DP-SGD and anchored clipping at identical $\sigma$. We also run an adaptive variant of GIAS that knows the anchor and inverts the difference. We report PSNR and SSIM at matched accuracy. If anchored updates are markedly easier to invert, that negative finding matters, because it would show that a fast convergence rate can be bought with empirical leakage while the formal guarantee stays unchanged.