Federated clients often compress what they send by transmitting only the few largest gradient coordinates. They do this to save bandwidth. The privacy literature treats that same sparsification as one of the better defenses against gradient inversion, meaning attacks that reconstruct a client's training images from the gradients it shares. The optimization literature points out that naive sparsification stalls training on non-convex neural-network losses. Its fix is error feedback, and the version with the cleanest non-convex theory, EF21, has each client send a compressed correction to a running gradient estimate. The server needs that estimate to take its update step, so it keeps an exact replica of each client's copy.
We argue this replica is a privacy problem nobody has measured. Suppose the client uses full local gradients, or large batches that differ little from round to round. Then the replica converges to that client's true dense local gradient, and every round reveals the exact values of the transmitted coordinates. The server also learns an upper bound on every coordinate it did not receive. The feature that makes EF21 converge would then silently undo the privacy that compression appeared to buy. This note proposes to measure that effect with a state-aware inversion attack. It also tests a minimal repair: each client hides its estimate behind a private random offset, and the offsets cancel across clients. The repair keeps EF21's convergence proof intact and pays its privacy cost in a single, explicit term of that proof.
Core Claim
EF21 (EF21) replaces classical error feedback with the recursion
$$g_i^{t+1} = g_i^t + c_i^t, \qquad c_i^t = \mathcal{C}\big(\nabla f_i(x^{t+1}) - g_i^t\big),$$
where $x^t$ is the global model, $\nabla f_i$ is client $i$'s local gradient, $\mathcal{C}$ is a contractive compressor such as Top-$k$, and $c_i^t$ is the only thing client $i$ transmits. EF21 proves an $\mathcal{O}(1/T)$ stationarity rate for smooth non-convex objectives with biased compressors, with no bounded-gradient assumption. That property is exactly what earlier error-feedback methods lacked.
The server knows $g_i^0$ and every $c_i^t$, so it knows $g_i^t$ exactly. On the $k$ coordinates selected in round $t$, the server's copy $g_i^{t+1}$ equals $\nabla f_i(x^{t+1})$ exactly. With deterministic local gradients the tracking error contracts toward zero, so the server's copy approaches the client's dense gradient. With stochastic minibatches it approaches a lagged blend of recent minibatch gradients.
Our first claim is empirical and falsifiable. An attack that inverts the server's reconstructed state, instead of the individual compressed messages, will recover images from EF21-with-Top-$k$ at fidelity close to that of an undefended client. This holds even at compression ratios where message-level inversion fails.
Our second claim concerns a repair that costs almost nothing in EF21's theory. Each client initializes $g_i^0 = \nabla f_i(x^0) + r_i$, where $r_i$ is a private random offset. The offsets are drawn from pairwise shared seeds so that $\sum_i r_i = 0$. This is the same trick secure aggregation uses for masks, but it is done once rather than every round. Because the offsets cancel, the server's aggregate $g^t = \frac{1}{M}\sum_i g_i^t$ is unchanged. The server's view of client $i$ is now
$$S_i^t := \sum_{s<t} c_i^s = g_i^t - r_i \;\longrightarrow\; \nabla f_i(x^t) - r_i,$$
which is the client's gradient shifted by a vector the server never learns. The only place $r_i$ enters the EF21 analysis is the initial tracking error, which is part of EF21's Lyapunov function. We therefore expect $\|r_i\|$ to cost an additive term that decays as $1/T$, not a change in rate. Verifying the exact constant is part of the work.
The offset does not hide gradient differences: $S_i^t - S_i^s \to \nabla f_i(x^t) - \nabla f_i(x^s)$. Whether differences between nearby iterates, which act roughly like Hessian-vector products on the client's data, are invertible is the central open question. We treat it as the decisive experiment and do not assume the answer.
Research Program
The first component is the state-aware attack. The attacker maintains the replica $g_i^t$ and uses the coordinates known exactly as equality constraints. It uses the untransmitted coordinates, which are bounded by the $k$-th largest residual magnitude, as interval constraints. On this partially observed dense gradient it runs standard cosine-distance gradient matching with total-variation regularization. We also run a variant that searches in a generative prior's latent space, following Gradient Inversion with Generative Image Prior. That paper reconstructs batches of 32 at quality earlier attacks reached only at batch 4, which makes it the strongest prior-based attacker available to us.
For stochastic EF21 we extend matching across a window of rounds. The attacker simulates the recursion over candidate inputs and known iterates $x^t$. In spirit this resembles the update-matching of Gradient Inversion Attacks Beyond SGD, which inverts Adam by simulating the optimizer from a known state. The difference is that EF21's state is not merely assumed known; the protocol itself gives it to the server.
The second component is the offset defense and its theory. We restate EF21's non-convex and Polyak-Łojasiewicz results with the offset folded into the initial error. We show that the aggregate trajectory is unchanged in distribution, and we give the convergence penalty as a function of $\|r_i\|$ and the compressor's contraction constant. Under an honest-but-curious server, we also characterize what the server can still identify: the Top-$k$ support pattern, gradient differences, and anything available through collusion among clients who share seeds.
The third component attacks the defense. We build a difference-matching adversary that optimizes candidate inputs so that the simulated $\nabla f_i(x^t) - \nabla f_i(x^s)$ matches the observed $S_i^t - S_i^s$, over a range of round gaps. If this attack succeeds, the honest conclusion is that error feedback with a server-side replica needs per-round secure aggregation or noise. That conclusion is itself a useful negative result for the compression-as-defense line. If the attack fails, the offset gives the first compression scheme that has both a non-convex convergence guarantee and resistance to inversion.
The non-convex direction plays the role of constraint here, not decoration. The rugged landscape is why error feedback is needed at all: plain Top-$k$ stalls. EF21's non-convex proof is the property any fix must preserve.
Baselines
The naive reference points are an uncompressed, undefended client and plain Top-$k$ with no error feedback. For the undefended case, Mixed Quantization Enabled Federated Learning reports that the DLG attack reaches 55.3 dB PSNR on its LeNet-5 setup. Plain Top-$k$ matters because it is the "compression is a defense" position. Evaluating Gradient Inversion Attacks and Defenses finds that standalone pruning needs more than 99% sparsity to be effective, at roughly a 10% accuracy cost. Data Reconstruction Attacks and Defenses finds pruning gives a better utility-privacy trade-off than additive noise or clipping.
The strongest privacy-plus-compression competitor is mixed quantization with client-held scaling factors (Mixed Quantization). It reports PSNR falling from 55.3 to 8.1 dB and 96.67% MNIST accuracy, but it has no non-convex convergence guarantee and no error feedback. Its idea, keeping part of the encoding secret on the client, is the closest relative of our offset. The strongest perturbation baseline is client-side differential privacy, Fed-αCDP (Securing Distributed SGD against Gradient Leakage Threats), which reports 97.9% MNIST accuracy against a 98% non-private baseline. The strongest combined empirical defense is 90% pruning plus InstaHide ($k=4$) from Evaluating Gradient Inversion Attacks and Defenses, reported at LPIPS 0.73 and 86.10% CIFAR-10 accuracy against 93.37% undefended.
On the optimization side, EF21 itself is the convergence reference. The file contains only qualitative bit-efficiency claims on LibSVM, so we have no reported EF21 number to quote. No reported result was found on Lacuna for any inversion attack against EF21.
The key ablations are classical error feedback (client-side residual, no server replica), EF21 without offsets, and EF21 with offsets of varying scale. Classical error feedback is a sharp control. It keeps the residual on the client, so any privacy gap between it and EF21 isolates the server-replica mechanism.
All methods share the same data splits, client count, architecture, bit budget per round (for compressed methods), and attack budget: the same iterations, restarts, and prior. Each method's hyperparameters get an equal tuning grid. Beating a baseline means lower attack fidelity (lower PSNR, higher LPIPS) at matched final accuracy and matched bits communicated. For the attack, it means higher fidelity than message-level inversion against EF21.
Why not just…?
Why not just run EF21 under per-round secure aggregation, so the server only sees the sum? This is the real threat to the defensive half of the proposal, because the server only needs the aggregate. Its cost is that clients choose different Top-$k$ supports, so masked summation must cover the union of supports or fall back to dense masks. That erodes the bandwidth saving that motivated compression. The file also notes that cryptographic aggregation is heavy for edge devices (Mixed Quantization). Our offset needs one seed agreement at initialization. We will report per-round bits for both, and if the difference attack breaks the offset we will say secure aggregation is required.
Why not just add client-side differential privacy noise? Fed-αCDP is strong on MNIST, but per-example clipping is expensive on edge devices (Gradient-Leakage Resilient Federated Learning). Its utility argument rests on classification margins, not non-convex rates. We run it at matched accuracy and compare attack fidelity. If it dominates at equal compute, the offset loses.
Why not just use plain Top-$k$ and accept slower training? Pruning is only protective at extreme sparsity with a substantial accuracy loss (Evaluating Gradient Inversion Attacks and Defenses). EF21 exists precisely because biased compression without feedback fails on non-convex losses. Our convergence-versus-bits curves will show the gap directly.
Why not just use mixed quantization? It is the closest idea but offers no convergence theory. It also has not been tested against an attacker who accumulates messages across rounds. We run our multi-round attacker against it as well.
Proposed Experiments
Convergence runs use the LibSVM datasets (a9a, w8a, mushrooms, phishing) with logistic regression plus a non-convex regularizer and 20 clients, matching EF21's setup. They check whether the offset penalty behaves as the modified bound predicts, sweeping $\|r_i\|$ and $k$. Privacy runs use CIFAR-10 and CIFAR-100 with LeNet-5 and a small ResNet over 15 clients, as in the mixed-quantization study. We add LFW to test faces and MNIST to compare with the reported DP numbers. We cover batch sizes 1, 8, and 32 and Top-$k$ ratios of 1% and 10%, with both deterministic and minibatch EF21. Metrics are PSNR, LPIPS, test accuracy, and bits to target accuracy.
The first decisive check: if the state-aware attack on EF21 does not substantially beat message-level inversion at 1% Top-$k$, the replica-leakage claim is wrong. The second: if difference matching recovers images from offset-protected EF21 at fidelity near the undefended case, the offset is insufficient and we report that result. The third: if classical error feedback and offset-EF21 leak similarly while plain EF21 leaks far more, that isolates the server-side replica as the mechanism.
References
- EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
- Gradient Inversion with Generative Image Prior
- Gradient Inversion Attacks Beyond SGD
- Mixed Quantization Enabled Federated Learning to Tackle Gradient Inversion Attacks
- Evaluating Gradient Inversion Attacks and Defenses in Federated Learning
- Data Reconstruction Attacks and Defenses: A Systematic Evaluation
- Securing Distributed SGD Against Gradient Leakage Threats
- Gradient-Leakage Resilient Federated Learning