Co-Scheduling Noise and Sketch Size in Private Federated Learning

In federated learning, phones or hospitals train a shared model by sending gradient updates to a server instead of raw data. Those updates are expensive to transmit, and they leak. An attacker who sees a single update can often reconstruct the training images behind it. The standard protection is differential privacy (DP): clip each update and add Gaussian noise, with a guarantee accumulated across all rounds. Two ideas from separate literatures make this cheaper. First, privacy spending can vary over time: decaying the noise as training converges improves accuracy under the same total guarantee. Second, compressing updates by random projection before adding noise, the "sketched Gaussian mechanism," cuts bandwidth and also reduces how much noise the same guarantee requires.

This note proposes treating the noise level and the sketch size as one joint per-round schedule, chosen under three budgets at once: a total privacy budget, a total upload budget, and a per-round floor on how well any single intercepted update can be inverted. The motivating observation is that noise-decay schedules concentrate risk in late rounds. Late rounds are cheap in total accounting, but they hand an attacker the least-noisy updates of the whole run. The proposal is to shrink the sketch in those rounds so that each update carries too few measurements to invert. The bet is that late-stage gradients live in a low-dimensional subspace, which would make this shrinkage nearly free for accuracy.

Core Claim

Under a fixed composed privacy guarantee and a fixed total number of uploaded coordinates, a jointly chosen schedule of noise $\sigma_t$ and sketch dimension $b_t$ should do two things at once. It should match the accuracy of noise-decay schedules. It should also hold worst-round reconstruction error at the level of static noise, which spends privacy uniformly and therefore has no weak round. Formally, with $\rho(\sigma, b)$ the per-round zero-concentrated DP cost of the sketched Gaussian mechanism, $R_t(\sigma, b)$ the reconstruction error an adaptive attacker achieves on the round-$t$ update, and $U$ final validation accuracy, we solve

$$ \max_{\{\sigma_t, b_t\}} U \quad \text{s.t.} \quad \sum_{t=1}^{T} \rho(\sigma_t, b_t) \le \rho_{\text{tot}}, \qquad \sum_{t=1}^{T} b_t \le B_{\text{tot}}, \qquad \min_t R_t(\sigma_t, b_t) \ge r_{\min}. $$

The first constraint is the usual accounting; zero-concentrated DP composes additively, so heterogeneous per-round parameters are allowed. The second constraint is bandwidth. The third constraint is what the dynamic-budget literature lacks.

The optimization and security "views" of scheduling are described as contradictory in that literature. Under this formulation they separate into different quantities. Accuracy responds to $\sigma_t$, while the attacker's per-round leverage responds to both $\sigma_t$ and $b_t$. Once bandwidth is a scheduled variable, the two views no longer have to fight over a single knob.

Relation to Prior Work

Three papers motivate the proposal. Noise decay is well supported. Differentially Private Model Publishing for Deep Learning uses exponential, step and polynomial noise decay and reports a 4% CIFAR-10 gain over uniform allocation. Research on Adaptive Noise Mechanism for Differential Privacy Optimization in Federated Learning sets $\sigma_t$ from gradient norms and convergence state and reports 15 versus 22–25 rounds to converge. Neither paper compresses updates, and neither tests reconstruction attacks.

Against these, An Adaptive Differential Privacy Method Based on Federated Learning argues for more noise late, when updates become predictable. Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding argues for more noise early, when active attacks bite. We take this disagreement as evidence that per-round leakage is real and time-varying. It is not something a total-ε accountant sees.

Two papers supply the method. Sketched Gaussian Mechanism for Private Federated Learning proves that projecting clipped gradients to dimension $b$ before noising amplifies privacy. On EMNIST ByClass it lowers the required noise from 0.8 to 0.0883 for the same guarantee. It ties convergence to the model's intrinsic dimension, but it keeps $\sigma$ and $b$ fixed and never runs an inversion attack. We reuse its accountant, making it per-round.

On the Interaction Between Differential Privacy and Gradient Compression in Deep Learning shows that compression acts as a variance-reducing filter on DP noise rather than a double penalty. It explicitly leaves open compression-aware adaptation. We take that direction up, but through the schedule rather than through clipping.

Three papers supply the measurement of leakage and constrain the design. Inverting Gradients - How easy is it to break privacy in federated learning? provides the cosine-similarity attack. Learning To Invert: Simple Adaptive Attacks for Gradient Inversion in Federated Learning provides the adaptive attacker, a network trained on auxiliary data passed through the defense. It reports an MSE of 0.012 on CIFAR-10 under static noise $\sigma=0.1$. Understanding Deep Gradient Leakage via Inversion Influence Functions provides a closed-form lower bound on reconstruction error, more than 500 times cheaper than running attacks. It also shows that leakage is uneven across directions and classes.

The adaptive-attack paper is also a constraint. Any claim that small sketches "hide" data must be tested against an attacker who trains through the exact sketch-plus-noise pipeline, not only against optimization attacks.

Research Program

The work has three parts.

Schedule search. Adapting the schedule to private signals leaks through the schedule itself, as Differentially Private Model Publishing for Deep Learning and Jun Wang et al. warn. We therefore fix the schedule before private training. It comes from a low-dimensional family: piecewise-linear $\log \sigma_t$ and $\log b_t$ with four knots each. The family is searched on a public proxy task.

Reconstruction estimate. The proxy run gives, per checkpoint, three quantities. The first is the inversion-influence lower bound, which estimates $R_t$ for every candidate $(\sigma, b)$ without running attacks. The second is the singular spectrum of the gradients, which tests the low-intrinsic-dimension hypothesis directly. The third is the accuracy sensitivity to $b$.

Accounting, then audit. Accounting uses Poisson client sampling, so the accountant's sampling assumption matches the implementation. This avoids the reshuffling mismatch flagged in Differentially Private Model Publishing for Deep Learning. The final schedule is then run on private data and audited empirically, round by round. The audit uses a sketch-aware cosine attack that assumes the attacker knows the projection matrix, which is the worst case. It also uses a round-specific learning-to-invert attacker, retrained for each audited round on auxiliary data passed through that round's exact $(\sigma_t, b_t)$.

Two outcomes would break the idea, and we would report either. If late-round gradient spectra are not concentrated, shrinking $b_t$ late will cost accuracy and the mechanism fails. If no round is invertible at realistic budgets, the floor constraint is vacuous and the contribution reduces to two-budget scheduling.

Baselines

Naive reference. Uncompressed DP federated averaging with static noise, tuned for accuracy, anchors both the utility gap and the bandwidth cost.

Strongest existing method. Static sketched Gaussian mechanism, as in Sketched Gaussian Mechanism for Private Federated Learning, is the strongest competitor. It already delivers compression and amplification with a proven accountant. Its reported figure is the noise reduction from 0.8 to 0.0883 on EMNIST ByClass with ResNet101. No reported accuracy result was found on Lacuna for that configuration, so we will reproduce it. We sweep its single $(\sigma, b)$ pair using the same total ε, the same total uploaded coordinates, and the same public-proxy tuning budget, measured in proxy GPU-hours, as our schedule search.

Decoupled schedule. Separately tuned noise decay layered on top of static sketching isolates the key ingredient. It pairs the exponential decay of Differentially Private Model Publishing for Deep Learning with the best static $b$, where $b$ is chosen to fit the same bandwidth budget. The comparison with our schedule isolates whether $b_t$ must move jointly with $\sigma_t$.

Ablation. The joint schedule is run without the reconstruction-floor constraint, isolating what the floor costs in accuracy.

Compression without DP. Mixed quantization from Mixed Quantization Enabled Federated Learning to Tackle Gradient Inversion Attacks is included only in the attack audit, as the reference for deterministic scrambling.

What counts as beating the baselines. Beating static sketching means higher final accuracy at matched ε and bits, by more than two seed standard deviations, with worst-round learning-to-invert MSE no lower than static sketching's. Beating the decoupled schedule means either higher accuracy at matched worst-round MSE, or higher worst-round MSE at matched accuracy.

Why not just…?

Why not just use static sketching with a well-tuned single configuration? It has no weak round by construction, and it may be the real answer. The benefit of scheduling depends on the noise-to-signal ratio changing substantially during training. Research on Adaptive Noise Mechanism for Differential Privacy Optimization in Federated Learning and Differentially Private Model Publishing for Deep Learning report that it does, but only without compression. Compression already filters noise, per On the Interaction Between Differential Privacy and Gradient Compression in Deep Learning, so the decay gains may shrink. The matched-budget comparison above settles this directly. We will report a null result if the gap falls within seed variance.

Why not just add noise decay on top of static sketching, without scheduling the sketch? This is the most serious threat. It captures the known accuracy gain with no new machinery. Our claim is that it pays for that gain with low-noise, full-size late updates. Those should be the easiest to invert with a round-specific learning-to-invert attacker. If the per-round audit shows no rise in late-round leakage under decoupled decay, the floor constraint buys nothing. Joint scheduling would then have to justify itself on bandwidth-utility grounds alone, which we would state plainly.

Why not just drop DP and rely on quantization or sharding? Mixed Quantization Enabled Federated Learning to Tackle Gradient Inversion Attacks drops optimization-attack PSNR from 55.3 to 8.1, but only against optimization attacks. Learning To Invert: Simple Adaptive Attacks for Gradient Inversion in Federated Learning shows that a learned inverter recovers images under sign compression, at MSE 0.014 versus about 0.11 for the optimization attack. ERIS: Enhancing Privacy and Communication Efficiency in Serverless Federated Learning assumes non-colluding aggregators. Our audit includes quantization under the learned attacker to confirm this on our models.

Proposed Experiments

Setups. The main benchmarks are two. CIFAR-10 uses a ResNet-20-scale network, where Inverting Gradients - How easy is it to break privacy in federated learning? reports about 14 dB PSNR for cosine inversion without defense. EMNIST ByClass uses the sketched-mechanism setup, to connect with its accountant. FEMNIST provides non-IID writer partitions, and LFW provides a face-reconstruction audit. Public proxies are a held-out CIFAR-100 split for CIFAR-10, and disjoint EMNIST writers for the character tasks.

Metrics. Utility is final accuracy at total ε ∈ {1, 4, 8} with δ fixed. Bandwidth is total uploaded coordinates. Leakage is per-round reconstruction MSE and PSNR under both attackers, summarized by its minimum over rounds. We also measure agreement between the inversion-influence estimate and realized attack error across rounds.

Decisive checks. There are four. First, whether decoupled noise decay in fact produces a late-round minimum in reconstruction error that static sketching does not. Second, whether late-round gradient spectra on the proxy concentrate enough that halving $b_t$ costs under one point of accuracy. Third, whether the joint schedule clears both the static and the decoupled baselines under the criteria above. Fourth, whether the inversion-influence bound ranks rounds in the same order as the learned attacker, since the offline schedule search depends on it. If that ranking agreement is poor, the search must switch to running attacks on the proxy, at higher cost.