Federated learning trains a shared model across many devices that each keep their data local and send back only model updates. Making this private and cheap forces two lossy steps onto every update. First, the update is clipped: its length is capped at a threshold so that differential privacy (a formal limit on how much any one participant can influence the output) can be enforced by adding calibrated Gaussian noise. Second, the update is compressed so that it fits through a slow phone uplink or a congested data-center link. Each step has its own repair trick, and both tricks work the same way: keep a local memory of what was cut off and add it back next round. This is called error feedback. The obvious combination is to run two such memories, one for clipping and one for compression. It is also the fragile one. The two memories contaminate each other, they double client state, and they go stale when a device sits out for many rounds.
We propose a single memory that absorbs both losses. Each round, every participating client takes the gap between its current gradient and its remembered estimate. It keeps only the part of that gap that falls in a random subspace chosen from a seed shared by everyone, clips that low-dimensional piece, adds noise to it, and sends it. Because the subspace does not depend on private data, the privacy accounting is an ordinary Gaussian mechanism in $k$ dimensions rather than $d$. Because every client uses the same subspace, the server can sum updates coordinate by coordinate, which works with standard all-reduce and secure aggregation. And because the dropped part and the clipped part are geometrically orthogonal, one memory can repair both without compounding error.
Core Claim
The closest existing method is Clip21-SGD2M. It extends Clip21, which treats clipping as a lossy compressor and fixes its bias with a per-client "shift" (a running estimate of that client's gradient). Clip21-SGD2M adds client momentum to smooth mini-batch noise and server momentum to smooth privacy noise. It removes clipping bias under arbitrary client heterogeneity. However, it sends full-precision dense vectors and is not analyzed under partial participation. The communication-side counterpart, Fed-EF, recovers full-precision convergence rates with TopK or sign compression but has no privacy at all. It also shows that stale error buffers under partial participation slow convergence by a factor of $\sqrt{n/m}$, where $n$ is the number of clients and $m$ the number active per round. PORTER does combine clipping, compression, and error feedback under local privacy, but it clips before averaging and leaves the clipping bias uncorrected.
Our claim is that the shift variable of Clip21-SGD2M can serve as the error-feedback memory for compression too, provided the compressor is a data-independent orthogonal projection. Write $v_i$ for client $i$'s shift, $g_i$ for its momentum-smoothed gradient, and $P_t$ for an orthogonal projection onto a random $k$-dimensional subspace drawn from the round-$t$ public seed. The client sends
$$ u_i = \mathrm{clip}_\tau\big(P_t(g_i - v_i)\big) + \xi_i, \qquad v_i \leftarrow v_i + \mathrm{clip}_\tau\big(P_t(g_i - v_i)\big), $$
where $\tau$ is the clipping threshold and $\xi_i$ is Gaussian noise supported on the same subspace. Write $r = g_i - v_i$. The clipped block lies inside the range of $P_t$, and the discarded part $(I - P_t)r$ lies outside it. The residual the shift fails to capture therefore splits into two orthogonal pieces:
$$ \|r - \mathrm{clip}_\tau(P_t r)\|^2 = \|P_t r - \mathrm{clip}_\tau(P_t r)\|^2 + \|(I-P_t)r\|^2 . $$
The second term has expectation $(1 - k/d)\|r\|^2$ over the random subspace. The first term is exactly the clipping loss that Clip21 already shows "heals" once residuals become small.
This decomposition is why a single buffer suffices and why the "compression corrupts the clipping accumulator" tension described for combined schemes does not arise here. It also gives a second, less obvious effect. The projected residual has expected squared length $(k/d)\|r\|^2$, so for a fixed $\tau$ clipping triggers far less often than it does on the dense residual. That shortens the biased early phase.
What is new relative to the cited work is threefold. We use one memory rather than two stacked buffers. The compression mask is shared across clients and chosen independently of the data, so it leaks nothing about client data, unlike TopK indices, which reveal which coordinates were large. And we analyze it under partial participation with privacy noise.
Research Program
The theoretical work extends the Clip21-SGD2M analysis to the composed operator $\mathrm{clip}_\tau \circ P_t$. The goal is a stochastic nonconvex rate in which compression enters only as a $d/k$ slowdown of the healing phase, while the privacy term shrinks from noise in $d$ dimensions to noise in $k$ dimensions. The per-coordinate trade-off is not free: each coordinate is refreshed roughly once every $d/k$ rounds. The analysis must therefore state honestly whether total rounds to a target accuracy grow with $d/k$. We expect them to grow in the deterministic regime and to be partly offset in the noise-dominated regime.
Partial participation is analyzed as the setting where this design should matter most. Under central client-level privacy with secure aggregation, the server stores only $\bar v = \frac{1}{n}\sum_i v_i$. Absent clients therefore contribute their last shift, which resembles a stored-gradient estimator. We will show whether this staleness produces Fed-EF's $\sqrt{n/m}$ penalty or something milder. Our reason to expect something milder is that the shift is a gradient estimate rather than an accumulated error that must eventually be flushed. We will also test a decayed-shift variant that trades a small bias for freshness.
Two instances of $P_t$ are built. The first uses random coordinate blocks: it is cheap, compatible with all-reduce, and adds no compute on the client. The second uses a Gaussian sketch, to test whether the privacy amplification by sketching claimed in Sketched Gaussian Mechanism for Private Federated Learning can be kept once the shift lives in the ambient space. For the block instance we claim no amplification. For the sketch instance we use Fed-SGM's accounting only if its dense-isotropic-sketch assumptions hold exactly, and otherwise we report ordinary Gaussian-mechanism accounting. Adaptive optimizers are out of scope; server momentum and SGD follow Clip21-SGD2M.
Baselines
The naive reference point is DP-FedAvg with standard per-client clipping, Gaussian noise, and no compression. This is the setting Fed-SGM compares against with noise multiplier 0.8. We also run it with shared-seed random-block compression and no memory, so that the raw cost of compression without repair is visible.
The strongest competitor on utility is dense Clip21-SGD2M. It already removes clipping bias under heterogeneity, and our method is its compressed special case, so the question is whether we can match it while sending a fraction $k/d$ of the payload. The file gives no reported accuracy for Clip21-SGD2M; its MNIST results are described only qualitatively. We therefore reimplement it and use their momentum settings.
The strongest competitor on communication under privacy is Fed-SGM. It reports a noise scale of 0.0883 versus 0.8 for DP-FedAvg on EMNIST ByClass with ResNet-101 at equal privacy. The file gives no exact accuracy for this setting, so we reproduce it. DP-REC is the extreme-compression reference. It reports under 6.5% accuracy drop at $\epsilon < 1$ on FEMNIST, 105x communication reduction on StackOverflow, and 1705x on MNIST.
The two-buffer stack is the natural composite competitor: Clip21-SGD2M for clipping plus a Fed-EF compression buffer, run with shared-seed random-block and, separately, TopK. TopK is included as a non-private upper reference only, because its data-dependent indices leak information. For a centralized sanity check of the bias correction we use the DiceSGD figure of 86.5% versus 78.9% for DP-SGD on CIFAR-100 with a pretrained ViT-small at $\epsilon = 2$. That figure is not a federated number and is used only to confirm that our reimplementation of bias correction behaves as expected.
The ablation that isolates the key ingredient keeps our projection and noise but removes the shift update. That arm is Fed-SGM-style clipping inside a random subspace. A second ablation uses a client-specific rather than shared subspace, which isolates the aggregation-alignment effect.
All methods receive the same client partitions, participation schedule, total privacy budget accounted with Rényi differential privacy (a standard way of summing privacy loss over many rounds) and client subsampling, and total uplink bits. Each gets an equal grid of 24 configurations over learning rate, $\tau$ or $C$, and momentum. Beating a baseline means one of two things: higher final accuracy at matched $\epsilon$ and matched uplink bits across three seeds, or matched accuracy with at least 10x fewer bits than dense Clip21-SGD2M.
Why not just…?
Why not just tune or adapt the clipping threshold, as with quantile-based adaptive clipping? Andrew et al. adapt the threshold $C$ privately, but Revisiting Gradient Clipping proves that any clipped stochastic method without correction stalls at a gradient-norm floor of $\Omega(\min\{\sigma, \sigma^2/c\})$ however $c$ is scheduled. DiceSGD's robustness across $C$ from 0.1 to 100 is the empirical counterpart. We still include adaptive clipping combined with random-block compression as a baseline. If it matches us at small $\epsilon$ on EMNIST, the bias correction is not earning its memory cost there, and we will report that.
Why not just stack Clip21-SGD2M with a separate Fed-EF compression buffer? This is the most serious alternative, and it is run directly. Our argument is that the orthogonal split makes the second buffer redundant for projection compressors, that it doubles client state, and that the second buffer accumulates noisy, clipped mass whose staleness Fed-EF already shows costs $\sqrt{n/m}$. If the stack matches us at equal bits and participation of 1–5%, the contribution shrinks to the memory saving and the analysis. The experiments below are designed to settle this.
Why not just use parameter-efficient fine-tuning and send dense updates for a small adapter? For small adapters, sending dense updates is indeed cheap, and this is a real threat on SST-2. However, adapter updates are still clipped and still biased, as the GeoClip study of low-dimensional clipping distortion suggests. Su et al. also note that frozen backbones struggle on strongly shifted clients. We therefore run every method both on the full model and on a low-rank adapter. If dense adapter updates with Clip21-SGD2M win on accuracy per bit, we will say our method's value is confined to full-model and large-embedding regimes.
Why not just use Fed-SGM's sketch, which already gives privacy amplification? Fed-SGM's amplification is a genuine advantage that our block instance lacks. Its clipping, however, happens before sketching and is uncorrected. The no-shift ablation and the Gaussian-sketch arm of our method separate the two effects: one measures the value of amplification, the other the value of bias correction.
Proposed Experiments
Experiments follow the benchmarks used by the closest papers. Federated EMNIST ByClass with ResNet-101 matches Fed-SGM. FEMNIST partitioned by writer and StackOverflow match DP-REC. CIFAR-10 with ResNet-18 under Dirichlet non-IID splits matches Fed-EF. SST-2 with BERT-Base split across clients matches Fed-SGM's language experiment. Settings are $\epsilon \in \{1, 2, 5\}$, compression ratios $k/d \in \{1, 1/10, 1/100\}$, and participation fractions of 1%, 5%, and 20%. Metrics are test accuracy, total uplink bits, client memory, and wall-clock time per round on an 8-GPU all-reduce simulation, the last connecting to the synchronization bottleneck that Tong Xiao et al. measure at up to half of training time.
The decisive mechanistic check logs the cosine similarity between the privatized aggregate and the true unclipped mean client gradient on a held-out probe. It also logs the fraction of rounds in which clipping is active. The orthogonal-split argument predicts that clipping frequency falls roughly in proportion to $k/d$ at fixed $\tau$, and that cosine similarity recovers toward the unclipped value over rounds. The no-shift ablation should instead plateau.
The decisive staleness check fixes a total budget and sweeps participation fraction. It fits the slope of rounds-to-target against $\sqrt{n/m}$ for our single-shift method and for the two-buffer stack. The claim fails if our slope is not clearly smaller.
The decisive practical check requires dense Clip21-SGD2M accuracy to be matched within one point at $k/d = 1/100$ on EMNIST and FEMNIST. It also requires beating reproduced Fed-SGM at equal bits and equal $\epsilon$. If either fails, the single-buffer design is not worth adopting over its dense parent.
References
- Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
- Clip21: Error Feedback for Gradient Clipping
- Analysis of Error Feedback in Federated Non-Convex Optimization with Biased Compression
- Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression
- Sketched Gaussian Mechanism for Private Federated Learning
- DP-REC: Private & Communication-Efficient Federated Learning
- Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach
- Differentially Private Learning with Adaptive Clipping
- Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees
- GeoClip: Geometry-Aware Clipping for Differentially Private SGD
- Federated Adaptive Prompt Tuning for Multi-Domain Collaborative Learning
- Fast Parallel Training of Neural Language Models