In federated learning, each device trains on its own data and sends only a model update to a server. Those updates can leak the data they came from, so private systems clip each update, add calibrated Gaussian noise, and often send only a random subset of coordinates. Sending fewer coordinates saves bandwidth and also reduces how much noise privacy requires. The cost is that the server receives an update that is mostly zeros and heavily noisy. Momentum, the standard tool for cutting the number of training rounds, then accumulates noise instead of signal. This matters more under privacy than elsewhere, because every extra round spends privacy budget.
Our observation is simple. In a differentially private system, the server knows almost exactly how noisy each aggregated update is. The noise scale, the clipping bound, the coordinate-sampling rate, and the number of clients are all public design constants. The server can therefore compute, for every layer and every round, an upper bound on the error in the update it just received. It can shrink that layer's update toward zero by a precomputed amount before the update enters momentum, with no tuning and at zero privacy cost, because it is pure post-processing of an already-private quantity. We propose this "denoise, then accelerate" server rule. We will test whether it lets momentum survive aggressive sparsification (5% of coordinates kept) at strong privacy, $\epsilon \le 1$, where current methods have to back off to much denser updates.
Core Claim
The claim is that the right place to fight sparsification variance is before momentum, not inside it. Doing it per layer with a known error budget should beat both server-side Adam and a well-tuned momentum with a global learning-rate schedule. The idea borrows its mechanism from a different field. VDAMP accelerates compressed-sensing MRI reconstruction by more than 5× over FISTA. It does so by tracking the error variance separately in each frequency band ("colored" rather than uniform noise) and using Stein's Unbiased Risk Estimate, a formula that scores a denoiser without knowing the clean signal, to set thresholds with no free parameters. Private federated updates have the same structure. Layers differ wildly in gradient scale, as noted in the BLUR/LUS work, and yet every existing private sparsified method treats the noise as one flat scalar across the parameter vector.
Concretely, suppose layer $l$ has $m_l$ coordinates, per-layer clipping bound $C_l$, noise multiplier $\sigma$, $n$ participating clients, and each coordinate is kept with probability $p$ and rescaled by $1/p$. Then the aggregated update $y_l = g_l + e_l$, where $g_l$ is the true mean clipped update, has an error whose expected squared norm is bounded by public quantities:
$$ \mathbb{E}\|e_l\|^2 \;\le\; v_l \;=\; \frac{m_l \sigma^2 C_l^2}{p^2 n^2} + \frac{(1/p - 1)\, C_l^2}{n}. $$
The first term is the injected Gaussian noise, scaled up by the $1/p$ rescaling. The second term bounds the random-mask variance, since each clipped client update has norm at most $C_l$. The server applies the shrinkage factor $\lambda_l = \max(0,\, 1 - v_l / \|y_l\|^2)$ to each layer. This is the James–Stein form, which the risk-estimate argument yields for Gaussian-like error. The shrunk update $\lambda_l y_l$ is then fed to heavy-ball or Nesterov momentum. In a secondary component, the same estimated per-layer signal-to-noise ratio $(\|y_l\|^2 - v_l)/v_l$ sets a per-layer momentum damping.
This replaces the distance-between-iterates damping of MIDE. That rule self-tunes step sizes in MIMO detection, but under privacy the distance between successive iterates measures injected noise rather than progress.
The prediction has two sides. Gains should be largest at small $\epsilon$ and small $p$, and should vanish as $\epsilon$ grows, because $v_l$ then shrinks and $\lambda_l \to 1$. This matches the crossover Farokhi proved for sparsified private SGD. Beyond its sparsification benefit at $\epsilon \le 1$, that paper motivates this proposal: it shows lost information dominates at weak privacy, so a method that only removes noise should not help there.
Relation to Prior Work
The closest work splits into two groups.
The first group adds acceleration to sparsified private federated learning:
- Fed-SPA runs a server-side Adam-style optimizer on random-$k$ updates, which amplifies the privacy guarantee.
- DP-FCRN replaces local gradient steps with cubic-regularized Newton steps and sends random-$k$ coordinates.
- DO-ADP uses top-$k$ sparsification with error feedback in a decentralized network.
None of them uses the fact that the error scale is known. Adam estimates a second moment from the noisy stream itself, and at strong privacy that estimate is dominated by the injected noise. Our rule computes the error scale instead of estimating it.
The second group accelerates private optimization without sparsification. DP-NAG and DP-MASG smooth noisy gradients and schedule noise non-uniformly across stages, but they use dense gradients, need the problem constants $\mu$ and $L$, and are only evaluated at $d=20$. That paper constrains our design: it shows naive momentum under noise needs explicit noise handling. It also supplies a comparison point.
Two more papers shape the mechanism:
- DP-SparFL shows the clipping threshold can scale with the retention fraction, which is why our $v_l$ uses sparsity-aware clipping.
- The concern that data-dependent top-$k$ indices leak information leads us to keep random-$k$ selection throughout.
Research Program
We will build the server rule as a drop-in layer between secure aggregation and the server optimizer. It will be implemented for both heavy-ball and Nesterov momentum, with per-layer clipping on clients and privacy accounting identical to Fed-SPA's Rényi accountant. Because shrinkage is post-processing, the privacy guarantee is unchanged. We will verify this by running the accountant on the pre-shrinkage release.
The analysis part has two goals. We will derive the round-complexity improvement for strongly convex objectives when the momentum input is shrunk, measured against the noise accumulation factor $1/(1-\beta)$ that undenoised momentum suffers. We will then translate fewer rounds into lower per-round noise at a fixed total $\epsilon$, using standard composition, under which the required noise multiplier grows roughly with the square root of the number of rounds.
The empirical part tests three things: whether per-layer shrinkage beats a global scalar, whether denoising helps beyond a tuned learning rate, and where the benefit disappears as $\epsilon$ and $p$ vary.
Baselines
The naive reference point is dense private federated averaging with no sparsification and no momentum. The file's only reported number for a dense private baseline comes from the DO-ADP paper: 89.58% MNIST accuracy at $\epsilon = 1$ (DO-ADP). A second naive point is random-$k$ with plain averaging and no momentum. It shows how much any acceleration buys.
The strongest existing method on this exact question is Fed-SPA (Fed-SPA), because it targets the same tension, sparsification variance against round count, with the same random-$k$ mechanism and accounting. It reports 92.65% MNIST accuracy at $\epsilon=1.0$ and $p=0.05$, and 63% CIFAR-10 accuracy at $\epsilon=1.0$. On CIFAR-10, $p=0.4$ gave the best performance. We will reimplement it under identical conditions: the same client split, CNN architecture, number of clients, $\epsilon$, $\delta$, $p$, per-round client sampling, and total rounds. Beating it means one of two outcomes:
- higher CIFAR-10 accuracy at $\epsilon = 1$ at $p=0.05$ or $0.1$, the regime where Fed-SPA preferred denser updates;
- matching its 63% with at most a quarter of the transmitted coordinates.
DO-ADP's 93.35% is reported in a decentralized setting. We cite it as context, not as a head-to-head number.
For convex control we include DP-FCRN and dense DP-NAG with noise dividing (DP accelerated optimization) on the Epsilon logistic-regression dataset with 40 clients. The file has no reported suboptimality numbers on Lacuna for either method on this dataset, so we report rounds to a fixed suboptimality against our own runs. For user-level heterogeneity we include DP-FedAvg with BLUR+LUS on EMNIST (BLUR/LUS). That paper reports gains of up to 4–5% over vanilla DP-FedAvg, and we will reproduce its gap before adding our rule on top.
Every method gets the same hyperparameter grid size, tuned on a held-out public proxy split, so that no method silently spends extra privacy budget on tuning. Three ablations isolate the key ingredient: momentum without shrinkage, a single global shrinkage factor instead of per-layer factors, and shrinkage without momentum.
Why not just…?
Why not just use server-side Adam, as Fed-SPA does? Adam normalizes each coordinate by a running estimate of the squared update. Under strong privacy, that estimate mostly measures the injected noise, so Adam rescales noise rather than removing it. Fed-SPA's preferred CIFAR-10 setting was $p=0.4$, not $0.05$, which is consistent with this failure mode. The direct test is Fed-SPA against our rule at $p \in \{0.05, 0.1, 0.4\}$, plus a hybrid that feeds shrunk updates into Adam. If Adam matches our rule at $p = 0.05$, the known-noise idea adds little over adaptive scaling, and we will report that.
Why not just tune the momentum coefficient and learning-rate schedule carefully? This is the real threat. A global shrinkage factor that changes over rounds is mathematically a learning-rate schedule, and small-step momentum already averages away noise. The proposal's value therefore rests on the per-layer, per-round part. The decisive ablation is global against per-layer shrinkage, compared with a tuned heavy-ball given a cosine schedule and an equal tuning budget. If per-layer shrinkage does not beat both on CIFAR-10 and EMNIST at $\epsilon = 1$, the contribution reduces to a tuning-free way of picking the step size. That is still useful, since tuning spends privacy, but it is a smaller claim, and we would state it as such.
Why not just skip sparsification and run dense DP-NAG with noise dividing? The file's evidence argues against it at scale: dense private training reached 89.58% on MNIST, while sparsified DO-ADP reached 93.35% (DO-ADP). DP-NAG itself is only validated at $d=20$. We still run it on Epsilon, where $d=2000$ is small enough that it could win. Farokhi's analysis predicts dense methods win at large $\epsilon$. Our $\epsilon$ sweep checks whether the crossover appears where predicted.
Why not just use second-order steps like DP-FCRN? Newton-type client solvers cut rounds but impose heavy client compute, which DP-FCRN itself flags as a limitation. We compare the two on Epsilon by rounds and client FLOPs, and treat the result as a compute trade-off rather than an outright win.
Proposed Experiments
The main grid covers MNIST, CIFAR-10, and EMNIST (non-IID split by writer), with $\epsilon \in \{0.5, 1, 4, 8\}$ and $p \in \{0.05, 0.1, 0.4, 1\}$. We use Fed-SPA's CNNs and add a ResNet-18 on CIFAR-10. The convex check uses Epsilon logistic regression with 40 clients. We report three metrics:
- final accuracy at fixed total $\epsilon$;
- rounds to target accuracy;
- transmitted coordinates.
Four checks decide the claim.
- At $\epsilon=1$ and $p=0.05$ on CIFAR-10, our rule beats both Fed-SPA and tuned heavy-ball.
- The per-layer shrinkage beats the global scalar.
- The advantage shrinks toward zero at $\epsilon=8$, as the known-noise argument predicts. A persistent gain at large $\epsilon$ would mean something other than denoising is at work, and we would investigate it.
- Logged $\lambda_l$ values vary across layers and rounds. If they are nearly uniform, the colored-noise premise fails.
As a sanity check on the privacy claim, we run the gradient-inversion attack of Deep Leakage from Gradients on released updates with and without server shrinkage. Reconstruction quality should be identical, since shrinkage happens after release.
References
- An Approximate Message Passing Algorithm For Rapid Parameter-Free Compressed Sensing MRI
- Differentially Private Federated Learning with Local Regularization and Sparsification
- A Novel Iterative Discrete Estimation Algorithm for Low-Complexity Signal Detection in Uplink Massive MIMO Systems
- Gradient Sparsification Can Improve Performance of Differentially-Private Convex Machine Learning
- Federated Learning with Sparsification-Amplified Privacy and Adaptive Optimization
- Federated Cubic Regularized Newton Learning with sparsification-amplified differential privacy
- Decentralized Optimization with Amplified Privacy via Efficient Communication
- Differentially Private Accelerated Optimization Algorithms
- Gradient sparsification for efficient wireless federated learning with differential privacy
- Deep Leakage from Gradients