Privatize the Forget Gradient, Not the Newton Step: Private Second-Order Federated Unlearning

When a participant in federated learning (many devices jointly training one model without sharing raw data) asks to be forgotten, the fastest known fix is a Newton step. Newton unlearning jumps the model toward where it would have landed without that participant's data, using the loss curvature (the Hessian, or its cheap cousin the Fisher information) to set how far to move in each direction. Recent attacks show that this unlearning message is itself a leak. The difference between the model before and after unlearning behaves like the deleted data's gradient, and gradient inversion recovers the deleted images. The deletion request is therefore the moment privacy fails. It is also structurally the weakest link: training updates can hide inside an aggregate of many clients, but an unlearning update comes from one client and cannot.

This note proposes a simple change of where the privacy noise goes. The forgetting client clips its gradient on the data to be forgotten, projects it into a small parameter subspace, adds noise, and sends that. The server then applies a damped inverse curvature, estimated from the remaining clients, as pure post-processing. Post-processing costs nothing extra in privacy. The main technical claim follows from this split. Once noise is present, the damping in the Newton step should no longer be a numerical-stability knob. It should be set by the noise level, because inverse curvature amplifies noise along flat directions. We predict that a noise-aware damping rule beats both existing defenses at a matched privacy budget and uplink byte budget. Those defenses are isotropic noise on the finished Newton step, which collapses accuracy, and noisy first-order gradient ascent, which ignores curvature.

Core Claim

Consider a Newton unlearning update $\Delta\theta = H^{-1} g_S$, where $g_S$ is the gradient of the loss on the forget set $S$ and $H$ is the Hessian of the training loss. The Right to be Forgotten in Federated Learning builds its rapid retraining on this form, but its guarantees rest on strongly convex losses and it transmits raw, unprotected updates.

There are two places to add privacy noise:

  • Noise on the step. Adding isotropic noise to $\Delta\theta$ requires calibrating to the sensitivity of $H^{-1} g_S$. That sensitivity scales with $1/\lambda_{\min}(H)$, which is enormous in deep networks.
  • Noise on the gradient. Adding noise $\xi \sim \mathcal{N}(0,\sigma^2 I)$ to a clipped $g_S$ (norm at most $C$) gives a standard Gaussian guarantee for the only quantity that depends on the client's data.

With the second option, the server computes $\widehat{\Delta\theta} = (H+\lambda I)^{-1}(g_S+\xi)$. Measured as the excess loss $\tfrac12 (\widehat{\Delta\theta}-\Delta\theta)^\top H(\widehat{\Delta\theta}-\Delta\theta)$ in the local quadratic model, the expected error splits along the eigen-directions of $H$:

$$ \mathbb{E}\,\text{excess loss} \;=\; \tfrac12\sum_i \frac{h_i}{(h_i+\lambda)^2}\Big(\tfrac{\lambda^2}{h_i^2} g_i^2 + \sigma^2\Big). $$

Here $h_i$ are the Hessian eigenvalues and $g_i$ the components of $g_S$ along them. The first term is the bias from damping and grows with the damping $\lambda$. The second is noise and shrinks with $\lambda$. The optimal $\lambda$ therefore increases with $\sigma$. At zero noise the rule recovers exact Newton; at high noise it approaches a scaled gradient step.

This yields three falsifiable predictions:

  1. Noise-aware damping helps. It should beat any fixed damping at every privacy budget $\epsilon$.
  2. Curvature has a limited range of usefulness. Its advantage over first-order ascent should shrink as $\epsilon$ decreases.
  3. Subspaces help twice. Restricting to a $p$-dimensional subspace, such as an adapter or the top curvature directions, removes the flattest directions. Those directions dominate the noise term, so the restriction cuts both bytes and error.

Relation to Prior Work

Two attack papers motivate the proposal.

  • FUIA shows that the before/after model difference in federated unlearning lets an honest-but-curious server reconstruct deleted images and identify removed classes. Pruning and perturbation defenses drop accuracy from about 84% to about 63%.
  • DRAUN extends reconstruction to unlearning losses where plain inversion fails. It includes a second-order variant that matches Hessian-vector products. On CIFAR-10 against ABL unlearning it reaches SSIM 0.6407 and PSNR 21.11, versus SSIM 0.0038 for the Hu et al. baseline (summary).

Both are attacks only. The second-order DRAUN variant is exactly the threat our design must survive, because a server that knows $H$ can undo the preconditioning.

Three papers supply parts of the method.

  • On Optimization Complexity of Second-Order Certified Unlearning introduces curvature-shaped anisotropic Gaussian noise for certified Newton unlearning. It is centralized, restricted to generalized linear models, and assumes an exact minimizer. We move the noise to the party that holds the data and the curvature to the party that holds the retained population. That split is what federated deployment requires and what their single-machine setting cannot express.
  • DP-FCRN proves that random-$k$ sparsification lowers sensitivity in federated Newton training. We reuse that amplification on the forget gradient before preconditioning. This sidesteps the tension noted in the file, that sparsifying a finished Newton step corrupts its curvature.
  • Deep Unlearning via Randomized Conditionally Independent Hessians and the adapter-sized payloads of FedDPGu (about 185k parameters) suggest the subspaces we restrict to.

Two papers constrain the design.

  • Starfish protects unlearning with two-party computation. It needs two non-colluding servers and heavy communication, which we deliberately avoid.
  • Subspace based Federated Unlearning shows that first-order ascent, when projected away from the retained clients' gradient subspace, can already be nearly harmless to clean accuracy. On MNIST it drops about 1 point, versus about 47 points for unconstrained ascent. This makes it the competitor most likely to erase our advantage once noise is added.

Research Program

Threat model. Training updates are protected by secure aggregation or DP-FedAvg. The single-client unlearning message is the new exposure. The server is honest-but-curious and knows the model and an estimate of the curvature.

Protocol.

  • Client side. The forgetting client computes $g_S$ at the current global model and projects it onto a server-announced subspace of dimension $p$. It optionally applies random-$k$ sparsification, clips to norm $C$, adds Gaussian noise, and uploads $k$ numbers.
  • Server side. The server holds a curvature estimate in the same subspace. This is either a low-rank or Kronecker-factored Fisher aggregated across retained clients under secure aggregation during training, or a diagonal Fisher in the style of Liu et al. The server applies $(H+\lambda(\sigma)I)^{-1}$.
  • Recovery. An optional few rounds of ordinary federated training with the retained clients follow.

Damping rule. We fit $\lambda(\sigma)$ from the bias–variance expression above. The eigenvalues come from the server's curvature estimate and the unknown $g_i^2$ are replaced by a public proxy. The protocol also tolerates the fact that federated training stops early. The retained-data gradient at the current model is not zero, so we include the retained clients' current aggregate gradient in the step, rather than assume $\nabla L_D(\theta^*)=0$.

Analysis. For logistic regression on the Epsilon dataset, where DP-FCRN and Doikov–Koloskova's assumptions hold, we will prove a bound on the distance to retraining as a function of $\epsilon$, $p$, $k$, and $\lambda$. For deep networks the claim is empirical.

Baselines

Undefended reference. Two points bound the problem from each side:

  • Undefended Newton unlearning following Liu et al.. It reports a 9.1x speedup over retraining and SAPE $2.235\times10^{-3}$ on CelebA. This is the utility ceiling and the privacy floor.
  • Federated retraining from scratch without the client, run with the same DP-FedAvg used in training. This is the gold standard for unlearning quality and the cost ceiling.

Isotropic noise on the Newton step. This is the defense evaluated in FUIA and DRAUN, calibrated to the step's sensitivity. It is the natural first thing anyone would try. The reported accuracy drop to about 63% is the number to beat on utility at matched attack resistance. The file reports no DRAUN numbers under any Newton-step defense; no reported result found on Lacuna for that pairing.

Noisy projected ascent. This is SFU with the forget client's ascent vector clipped and noised at the same $\epsilon$, and projected with the paper's recommended SVD coverage of 0.9–0.95. It is the strongest competitor because it is first-order, one round, and already nearly harmless to clean accuracy. We will also run FedADP-style adaptive-budget rollback. That approach reports membership-inference success of 25.51% on MNIST versus about 48% without DP, so it serves as a storage-based comparison point.

Fair comparison. All methods share:

  • the same Dirichlet-partitioned data and backbone;
  • the same total privacy budget, accounted with the same Gaussian accountant;
  • the same uplink byte budget;
  • the same number of recovery rounds;
  • the same hyperparameter search budget.

Hyperparameters are tuned on a held-out deletion request.

Ablations. Four ablations isolate the key ingredients:

  • noise-on-gradient versus noise-on-step at identical $\epsilon$ (the placement claim);
  • noise-aware $\lambda(\sigma)$ versus the best fixed $\lambda$ (the damping claim);
  • full-dimension diagonal Fisher versus a $p$-dimensional subspace (the subspace claim);
  • sparsification amplification on versus off.

Success criterion. Beating the baselines means lower distance-to-retrained-model and higher retained accuracy than noisy projected ascent. It must hold at matched $\epsilon$ and bytes, and at a DRAUN-HVP SSIM no higher than the competitor's.

Why not just…?

Why not just retrain from scratch? Retraining leaks nothing new and is exact. However, it needs all retained clients online for hundreds of rounds, which is the cost Liu et al.'s 9.1x speedup and FisherMask's 2.1 versus 91.7 epochs measure. We keep it as the quality target and report our method's round and byte cost as a fraction of it.

Why not just add isotropic noise to the unlearning update? Both attack papers report that this degrades reconstruction only at an accuracy collapse. The placement ablation tests the explanation directly: the sensitivity of $H^{-1}g_S$, not the noise itself, is what hurts. We expect a large gap at equal $\epsilon$. If the gap is small, the curvature spectrum in practice is not ill-conditioned enough to matter, and the placement claim fails.

Why not just add noise to first-order projected ascent and skip curvature? This is the real threat. The core equation predicts that at high noise the optimal damping makes our step behave like a scaled gradient. Below some $\epsilon$, noisy SFU should therefore match us. The experiments will report this crossover budget rather than hide it. The proposal is worthwhile only if the crossover sits at a smaller $\epsilon$ than the practically used budgets. If it does not, the finding that curvature buys nothing under local privacy is itself the result we will report.

Why not just use two-party computation like Starfish? It protects exact computation but needs two non-colluding servers and costs significant communication per round. Our design targets deployments with one untrusted server. We report bytes against Starfish's round-selected protocol where it is reproducible.

Proposed Experiments

Settings.

  • CIFAR-10 and CIFAR-100 with ResNet-18 under Dirichlet non-IID splits, which are the DRAUN and FUIA settings.
  • FEMNIST by writer.
  • CelebA with 10 cross-silo clients, matching Liu et al.
  • AG News with a frozen RoBERTa-Base and a prompt-generator subspace, matching FedDPGu.
  • Epsilon logistic regression for the theory check.

Deletion requests cover a whole client, a class (FUIA's identification test), and a sample subset.

Metrics.

  • Leakage: SSIM and PSNR under FUIA and under DRAUN including its HVP extension, with the attacker given the server's curvature. We also report FUIA's removed-class identification rate.
  • Unlearning quality: forget-set accuracy, membership inference on the forget set, and parameter and prediction distance to retrained-from-scratch.
  • Utility: retained test accuracy.
  • Cost: uplink bytes and client compute.

Results are reported across $\epsilon$ from 0.2 to 8.

Decisive checks. Three results decide the proposal's claims:

  • Placement. At the $\epsilon$ where DRAUN-HVP SSIM falls near the 0.0038 non-attack level, noise-on-gradient keeps retained accuracy well above the roughly 63% regime reported under isotropic defenses.
  • Damping. The empirical optimal damping tracks the $\lambda(\sigma)$ predicted from the server's eigenvalues. If it does not, the quadratic model is wrong for deep networks.
  • Curvature. The curve of distance-to-retrain against $\epsilon$ for our method against noisy SFU locates the budget below which second-order information stops paying for its curvature estimate.