Federated Learning with Sparsified Model Perturbation: Improving Accuracy under Client-Level Differential Privacy

1 INTRODUCTION

• Client-level DP protects an entire client's participation, but repeated FL rounds and noise proportional to model size make accuracy difficult to maintain, especially for large models.The paper also notes that client-level protection covers a client's entire dataset rather than one record.Source: §1 · p. 1
• Fed-SMP sparsifies each client's local update before adding Gaussian noise to selected coordinates, aiming to improve the privacy-accuracy tradeoff and reduce communication cost.The paper says sparsification amplifies the privacy guarantee offered by the noise.Source: §1 · p. 2
• Fed-SMP makes lightweight modifications to FedAvg, enabling integration into existing packages while providing client-level differential privacy.The scheme is proposed for FL with a large number of clients.Source: §1 · p. 2
• Against DP-FedAvg, Fed-SMP uses sparsification to improve the privacy-utility tradeoff and communication efficiency simultaneously.The paper presents unbiased random and biased top-k sparsification; both require less added random noise for the same DP level and are compatible with secure aggregation.Source: §1 · p. 2
• Renyi differential privacy is used for tight end-to-end privacy accounting, and convergence is analyzed for both unbiased and biased sparsifications.The analysis says the optimal compression level balances increased compression error against reduced privacy error.Source: §1 · p. 2
• Fed-SMP achieves higher model accuracy than baseline approaches under the same level of differential privacy while saving communication cost.The reported evaluation includes IID and non-IID datasets.Source: §1 · p. 2

2 PRELIMINARIES

• Differential privacy is presented as a rigorous privacy notion, with (ϵ, δ)-DP defined through the behavior of a randomized mechanism on adjacent datasets.The section also introduces ℓ2-sensitivity and the Gaussian mechanism as tools for privacy analysis.Source: §2 · p. 2
• Renyi differential privacy bounds the Renyi divergence between a mechanism's outputs on adjacent datasets.The paper uses RDP because its tighter composition bound suits end-to-end privacy accounting for iterative algorithms.Source: §2 · p. 2
• An RDP guarantee can be converted to (ϵ, δ)-DP for δ > 0.The section presents this conversion as a way to express privacy guarantees in the paper's target form.Source: §2 · p. 2
• The Gaussian mechanism satisfies RDP when noise is calibrated to a query's ℓ2-sensitivity.The supplied lemma gives an (α, α/2σ^2)-RDP guarantee.Source: §2 · p. 2
• Subsampling without replacement changes the RDP guarantee according to the sampling ratio, while composing mechanisms adds their RDP bounds.The subsampling lemma is stated for a Gaussian mechanism and a dataset of m datapoints.Source: §2 · pp. 2–3

3.1 Problem Formulation

• Federated learning trains a global model under a central server by optimizing across clients' local losses, whose data distributions may differ.Each local loss is the expected model loss over that client's dataset.Source: §3.1 · p. 3

3.2 Attack Model

• The threat model includes honest-but-curious servers or clients, colluding parties, and passive outside attackers who eavesdrop but do not alter transmissions.The stated target is inference of a victim client's private data from shared messages.Source: §3.2 · p. 3

3.3 Achieving Client-level DP in FL

• FedAvg selects clients each round, has them run local SGD and upload updates, then aggregates those updates to update the global model.The process repeats across communication rounds until convergence criteria are met.Source: §3.3 · p. 3
• FedAvg's repeated exchange of large model updates can be costly and expose private information, while DP noise can reduce accuracy and prior studies did not consider communication cost.These concerns motivate a scheme that maintains accuracy while reducing communication cost.Source: §3.3 · pp. 3–4
• Client-level DP protects whether an entire client's dataset participates, whereas record-level DP protects a single example.The paper identifies client-level DP as more relevant to cross-device FL, where devices can contribute multiple records.Source: §3.3 · pp. 3–4
• DP-FedAvg clips each client's update, adds Gaussian noise, and sends encrypted updates through secure aggregation.Secure aggregation lets the server learn an aggregate of updates rather than each client's individual update.Source: §3.3 · p. 4
• In secure aggregation, zero-sum masks cancel when the server sums masked updates; the paper ignores finite-precision and modular-summation effects.The authors point to a strategy for converting real-valued vectors to integers while minimizing approximation error.Source: §3.3 · p. 4

4 FED-SMP: FEDERATED LEARNING WITH SPARSIFIED MODEL PERTURBATION

• SMP sparsifies local model updates before adding Gaussian noise to the selected coordinates, combining compression with client-level DP.Clients clip the sparsified update before perturbation; the noisy update is encrypted and sent through secure aggregation.Source: §4 · pp. 4, 6
• Fed-SMP sends only k coordinates per local update and uses a shared active-coordinate set so clients can use secure aggregation without losing sparsification’s communication benefit.Naive per-client masks can require encrypting all d coordinates, eliminating that benefit.Source: §4 · pp. 4–5
• Randk selects coordinates uniformly at random, while topk selects the largest-magnitude coordinates using a small public dataset assumed to resemble clients’ data distribution.The public dataset lets the server choose top-k coordinates without privacy leakage from the selection.Source: §4 · pp. 4–5
• Randk updates are scaled by d/k for an unbiased estimate, whereas topk retains high-magnitude coordinates but its data-dependent selection requires privacy protection.Randk selection alone does not provide a DP guarantee; it must be combined with Gaussian noise.Source: §4 · pp. 4–5

5.1 Privacy Analysis

• Fed-SMP’s privacy analysis uses Renyi differential privacy, subsampling amplification, and composition to establish an end-to-end client-level guarantee over T rounds.The guarantee is for clients sampled without replacement with probability q = r/n.Source: §5.1 · p. 6

5.2 Convergence Analysis

• The convergence result applies under Assumptions 1–3 and stated conditions on the local learning rate and clipped update norm.The assumptions include smooth local objectives, unbiased stochastic gradients with bounded variance, and bounded dissimilarity.Source: §5.2 · p. 6, §5 · p. 6
• The convergence bound separates optimization error from compression and privacy errors, with smaller k increasing compression error while decreasing privacy error.The analysis identifies an optimal k that balances the two errors to minimize the bound.Source: §5.2 · p. 6

6.1 Dataset and Model

• Experiments span Fashion-MNIST and SVHN image classification and Shakespeare next-character prediction, using models with about 1.6M, 3.4M, and 0.8M parameters, respectively.The benchmarks involve 6,000 clients for Fashion-MNIST and SVHN and 715 speaking-role clients for Shakespeare.Source: §6.1 · pp. 7–8

6.2 Experimental Settings

• Across datasets, experiments use five seeds and report best testing accuracy; dataset-specific noise multipliers and clipping thresholds set privacy, while p=k/d controls compression.The compression ratio is the fraction of coordinates retained; smaller p means more update coordinates are zeroed.Source: §6.3 · p. 8, §6.2 · p. 8

6.3 Experiment Results

• At matched DP, Fed-SMP-topk reaches 80.76% on Fashion-MNIST (+11% vs DP-FedAvg), 81.12% on SVHN (+12%), and 56.76% on Shakespeare (+11%).Fed-SMP-randk also outperforms DP-FedAvg on all three datasets at the same privacy level.Source: §6.3 · p. 8

6.3.1 Communication efficiency of Fed-SMP

• On MNIST, top-k/rand-k save 99%/70% of uplink communication cost versus DP-FedAvg; at target accuracies 72% on SVHN and 50% on Shakespeare, savings are 99%/82% and 95%/60%, respectively.Fed-SMP converges more slowly but finishes at higher accuracy than DP-FedAvg; top-k is more communication-efficient than rand-k.Source: §6.3.1 · p. 9

6.3.2 Tradeoff between privacy and compression errors

• Fed-SMP accuracy rises then falls as p increases, unlike monotonically improving FedAvg-randk/topk; too-small p leaves compression error dominant, while too-large p weakens privacy amplification.The figure plots training loss and testing accuracy against compression ratio.Source: Figure 3 · p. 10, §6.3.2 · p. 10

6.3.3 Tradeoff between privacy and accuracy

• At fixed p, accuracy falls as privacy loss ε decreases, while the optimal p also shifts downward under stricter privacy to balance privacy and compression errors.For Shakespeare top-k, the reported optimal p falls from 0.1 at ε = 11.51 to 0.01 at ε = 3.39.Source: §6.3.3 · p. 11

• Prior FL techniques include shuffling,, sparsification –, and wireless aggregation, often for specific settings; Fed-SMP instead targets client-level DP.Source: §7 · p. 11
• Methods, apply only to convex settings and disallow partial participation, while secure MPC and homomorphic encryption do not protect against leakage from server-observed final models.Source: §7 · pp. 11–12
• Fed-SMP jointly addresses privacy and communication, unlike cpSGD, which treats them separately and has compounded errors reported as higher than privacy-only [55].Source: §7 · p. 12
• Zhang et al. add noise before sparsification, while Kerkouche et al. assume updates have few nonzero coordinates, which seldom holds in practice.Source: §7 · p. 12

• Fed-SMP with randk and topk improves the privacy-accuracy tradeoff and communication efficiency simultaneously compared with existing methods.The paper reports extensive evaluation on two common benchmark datasets.Source: §8 · p. 12
• The paper reports rigorous analyses of Fed-SMP's convergence and end-to-end differential privacy guarantee.Source: §8 · p. 12
• Future work will consider low-rank approximation and quantization, and extend Fed-SMP to alternative FL settings such as shuffled model.Source: §8 · p. 12

• With clients sampled without replacement at probability q = r/n, each Fed-SMP round satisfies (α, ρt(α))-RDP, and T-round composition gives (α, Tρt(α))-RDP.Source: Appendix A · p. 14
• The proof converts the composed RDP guarantee to (ε, δ)-DP using Lemma 1 and chooses α = 1 + 2 log(1/δ)/ε under conditions on α and σ.Source: Appendix A · p. 14
• After rearranging the resulting inequality, the proof applies the constraint on ε to complete the argument.Source: Appendix A · p. 14

B.1 Notations

• Fed-SMP's global update uses sparsified noisy client updates, and uniform sampling without replacement makes client sampling unbiased.Source: §B.1 · p. 14

B.2 Useful Inequalities

• The cited passages state Jensen’s inequality and give the bound ∥a + b∥2 ≤ (1 + α)∥a∥2 + (1 + α−1)∥b∥2 for all α > 0 (15).Source: §B.2 · p. 14

B.3 Detailed Proof

• For randk, the sparsifier is (d/k) randk; the proof uses L-smoothness and takes expectations over sampled clients, minibatches, and the sparsifier.Source: §B.3 · p. 15
• Intermediate bounds use nonnegative averaged gradients, Lemmas 5 and 6, smoothness, and independence of Gaussian noise.Source: §B.3 · p. 15
• Under stated learning-rate bounds, the proof bounds intermediate terms, sums the inequality over rounds, and divides by T.Source: §B.3 · p. 16

• The topk proof assumes the public distribution is similar to the overall client distribution and invokes L-smoothness.Source: Appendix C · p. 16
• The analysis takes expectations over sampled clients and mini-batches and uses unbiased stochastic gradients and Gaussian noise.Source: §B.3 · p. 15, Appendix C · p. 17
• Theorem 2 summarizes convergence for randk and topk sparsifiers with γ = 1/3, which satisfies γ < 1/2.Source: Appendix C · p. 19

• Lemma 9 establishes bounded-sparsification properties for randk and topk.Source: Appendix D · p. 19
• The expected topk sparsification error is no greater than the expected randk sparsification error.Source: Appendix D · p. 19
• Lemma 10 bounds the local model difference at each round.Source: Appendix D · p. 19
• The local-update proof unrolls its recursion when η_l ≤ 1/(3τL).Source: Appendix D · p. 20
• Lemma 11 bounds the local model update at each round.Source: Appendix D · p. 20