Cluster on a Noisy Sketch, Train on a Noisy Update

Federated learning trains one shared model across many devices that keep their data locally and send only model updates to a server. When devices hold very different data, for example handwriting scanned at different rotations or hospitals with different patient mixes, a single shared model serves nobody well. Clustered federated learning addresses this by grouping similar devices and training one model per group. Grouping requires the server to compare what devices send, and what they send are gradients, the vectors that tell a model how to change. Gradients are also exactly what attackers invert to reconstruct private training images. Adding the calibrated noise of differential privacy, a formal guarantee that any single training record has a bounded effect on what is released, stops these attacks. The same noise also blurs the differences between devices, so the grouping step fails.

This proposal separates two questions that current methods answer with the same high-dimensional message: which group does this device belong to? and how should that group's model change? The first question needs very little information. A device can answer it with a short random projection of its averaged per-example gradients, a vector of perhaps one hundred numbers instead of millions. Privacy noise added to a short vector is far smaller in total than noise spread over every model parameter. The server clusters these private sketches once. Cluster membership is then a post-processing of a differentially private release, so it carries no extra privacy cost. Each cluster model is afterwards trained with ordinary differentially private updates. The claim is that this split recovers near-oracle clustering at privacy budgets where private clustering in full parameter space collapses. It should do so without the full-batch first round that the leading method requires, and it should resist both passive and server-side gradient inversion, including attacks aimed at one specific cluster.

What exists and where the gap is

On the clustering side, IFCA lets each client pick the candidate model with lowest local loss and report its choice. CFL-GP has the server stack client gradients from broadcast reference models into a profile matrix, reduce it with a singular value decomposition, and run spectral clustering. CFL-GP reaches perfect clustering (adjusted Rand index 1.0) within 20 rounds on Rotated MNIST and keeps near-perfect clustering on COST2100 under 10,000-fold gradient compression. That compression result is the observation this proposal builds on: the signal that separates clusters lives in very few dimensions. CFL-GP itself sends raw gradients, which Deep Leakage from Gradients shows can be inverted pixel by pixel, and IFCA's reported cluster index exposes a client's group, as the survey by Morafah and Morafah notes. Both papers therefore motivate the proposal and supply its clustering machinery.

The closest work is Differentially Private Clustered Federated Learning, together with its companion robust clustering paper. It shows that private IFCA misassigns clients and that uniform noise hurts minority groups. Its method, R-DPCFL, fits a Gaussian mixture to full-dimensional noisy model updates from a first round in which each client uses its entire dataset as one batch. It then uses soft assignments and finally lets each client select its cluster through the exponential mechanism, a formal private selection rule. R-DPCFL still clusters in the full parameter dimension, so the noise it must overcome grows with model size. It relies on a full-batch round that the authors concede degrades when data are scarce, and it never measures reconstruction attacks.

We keep its insight that clustering should be decided early and privately. We change the space in which clustering happens, so that noise scales with sketch size instead of model size. We also pay for membership privacy through post-processing rather than a separate selection mechanism.

Two other strands are relevant. Social-aware clustered FL uses trust graphs to aggregate before adding local noise. It needs a social graph and trains one global model, so it addresses a different setting. The adapter-clustering methods FL-TAC and FedLFC cluster low-rank adapters with no privacy at all.

The attack literature constrains the design. GIAS/GIML shows that generative priors defeat large batches and survive 99% gradient pruning. MineGrad/PEFTLeak shows that a malicious server can craft weights that turn low-rank adapter gradients into near-copies of image patches, even at batch size 128. Heuristic defenses are therefore ruled out, and any defense must hold when the server chooses the model the client evaluates. The f-DP limits paper warns that the training-phase trade-off cannot be made arbitrarily favorable. For that reason the proposal targets the clustering phase, where dimension can actually be cut, rather than promising cheaper private training.

Core Claim

Fix a reference model $W_0$ broadcast by the server and a public random projection matrix $P \in \mathbb{R}^{m \times d}$, where $d$ is the parameter count and $m \ll d$ is the sketch size. Client $i$, holding $n_i$ examples, streams over minibatches and releases one vector:

$$s_i = \frac{1}{n_i}\Big(\sum_{x \in D_i} \mathrm{clip}_C\big(P\,\nabla_W \ell(x; W_0)\big) + \mathcal{N}(0, \sigma^2 C^2 I_m)\Big).$$

Here $\mathrm{clip}_C$ rescales each projected per-example gradient to norm at most $C$, and $\sigma$ sets the noise level for the record-level budget $\epsilon_s$ spent on the sketch. The sum can be accumulated one minibatch at a time, so memory use is that of a single minibatch rather than a full batch. Because clipping happens after projection, the guarantee holds for any $W_0$ and $P$ the server sends, including adversarially crafted ones.

The noise contributes a vector of norm about $\sigma C\sqrt{m}/n_i$. Random projection approximately preserves the distance $\Delta$ between cluster centroids, by the Johnson–Lindenstrauss property. Clustering is therefore reliable roughly when

$$\Delta \gtrsim \frac{\sigma C \sqrt{m}}{n_i}.$$

This requirement is weaker by a factor of about $\sqrt{d/m}$ than the corresponding condition for clustering full-dimensional noisy updates. For a small convolutional network that factor is roughly two orders of magnitude.

Clustering is cheap only up to a point. The bound also says honestly where the method fails: clients with very few examples, where $n_i$ is small and no projection can rescue them.

Research Program

The method has three phases. In the first round, the server broadcasts a small number $R$ of reference models, as CFL-GP does, with $R$ between one and three. Each client returns concatenated sketches. Composition over the $R$ sketches is counted against the budget $\epsilon_s$.

In the second phase, the server clusters the sketches. It uses spectral clustering, with the number of clusters $K$ chosen by the eigen-gap of the sketch similarity matrix. CFL-GP's singular-gap heuristic suggests this works, and the question is newly testable here because the noise floor of the sketch is known in closed form. We will derive the expected noise eigenvalue and accept a cluster only if its eigenvalue clears that floor. This gives a principled answer to the fixed-$K$ problem that both IFCA and R-DPCFL leave open.

In the third phase, each cluster trains its own model with DP-SGD on budget $\epsilon_t$, where $\epsilon_s + \epsilon_t$ equals the total budget. Assignments are frozen. The sketch can optionally be refreshed every few rounds, which spends more budget, and this lets us study drift without the oscillation that full-dimensional private reclustering suffers.

The analysis has two parts. First, a misclustering bound in terms of $\Delta$, $m$, $n_i$ and $\sigma$, using standard spectral-clustering perturbation arguments on the projected centroids. Second, an accounting of how best to split the budget between $\epsilon_s$ and $\epsilon_t$.

The gradient-leakage direction enters as the evaluation lens rather than as a new attack family. We will attack two channels separately: the sketch channel and the cluster training channel.

On the sketch channel, we run the DLG and GIAS objectives with gradient matching replaced by sketch matching. We also run an active variant in which the server crafts $W_0$ and $P$ in the style of PEFTLeak to concentrate per-example information.

On the training channel, we test a threat that is specific to clustered learning. A malicious server knows the cluster memberships and can send a poisoned model to one small cluster, for example the minority rotation. Its goal is to target that sub-population. We will measure whether a smaller cluster, whose aggregate is averaged over fewer clients, leaks more than a global model at the same $\epsilon_t$.

Baselines

The naive reference points are global DP-FedAvg and local-only training, both run at the same total record-level budget, which is irrelevant for local-only training. On Rotated MNIST, IFCA reports that, without privacy, a global model reaches 88.73% and local-only training 80.05%, against 95.25% for IFCA (IFCA). These numbers anchor the gap that private clustering must preserve.

The non-private upper bounds are IFCA itself (95.25% on Rotated MNIST with four clusters, 81.51% on Rotated CIFAR-10, about 88% on FEMNIST) and CFL-GP, run with the official code and reporting an adjusted Rand index of 1.0 within 20 rounds on Rotated MNIST. We add an oracle that uses true cluster labels and trains with DP-SGD at the full budget. It is the ceiling for any private clustering method because it spends nothing on clustering.

The strongest existing competitor is R-DPCFL (Differentially Private Clustered Federated Learning). It is the only method in the file that targets private clustered training with personalized cluster models. No reported result was found on Lacuna for R-DPCFL's accuracy on MNIST, FMNIST, or CIFAR-10, so we will reimplement it and report its numbers alongside ours. For fairness, R-DPCFL gets the same total budget, the same architecture, client counts, and round count, and the same hyperparameter search budget. That search covers clipping norm, learning rate, and its soft-clustering duration. It also gets its full-batch first round, which we additionally emulate with gradient accumulation so that memory is not the only axis of comparison.

Private IFCA with noisy updates and the exponential mechanism is included as the cheaper variant that R-DPCFL shows breaking down.

Two low-dimensional private clustering baselines carry most of the risk to the idea. The first is privatized client loss vectors over the $K$ candidate models, in the spirit of CLoVE, with Gaussian noise on a $K$-dimensional clipped vector. The second is privatized classifier-head or label-histogram signatures, following the one-shot final-layer clustering of Islam et al..

The key ablation sets $m = d$ with otherwise identical streaming, clipping, and budget. This isolates dimension reduction as the cause of any gain. A sweep over $m$ from 16 to 1024 then traces the predicted $\sqrt{m}$ dependence.

Beating R-DPCFL means two things on Rotated MNIST, Rotated CIFAR-10, and FMNIST at total $\epsilon \in \{1, 3, 8\}$. The first is higher worst-cluster accuracy, which is the minority-cohort metric that R-DPCFL itself emphasizes. The second is higher clustering adjusted Rand index. The comparison must hold at matched memory and must not lose on mean accuracy. If we only match R-DPCFL at large $n_i$ while removing the full-batch requirement, we will report that as a systems result rather than an accuracy result.

Why not just…?

Why not just privatize a $K$-dimensional loss vector instead of a gradient sketch? This is a real threat, because it is even lower-dimensional than our sketch. Its weakness is circular: loss vectors only separate clusters once the $K$ candidate models have already specialized. At initialization, every client's losses on random models look alike, which is why IFCA needs about 30 rounds to identify clusters and why R-DPCFL defers loss-based selection to late rounds. Gradients at a common reference model already differ under covariate shift at round one. We will run privatized loss-vector clustering at the same $\epsilon_s$, both at round one and after warm-up rounds. If it matches our method after cheap warm-up, the gradient sketch only buys earlier clustering, and we will scale the claim down accordingly.

Why not just cluster on privatized label histograms or classifier heads? These are low-dimensional and cheap, and they work when groups differ by label mix. They are blind to rotations and other feature shifts, where every client has the same label distribution. Rotated MNIST and Rotated CIFAR-10 are built exactly that way, and FEMNIST's writer styles are similar. We expect this baseline to win or tie on Dirichlet-split CIFAR-10 and to fail on the rotated benchmarks. A mixed benchmark that combines rotation with label skew will show whether gradient sketches capture both kinds of difference.

Why not just use R-DPCFL with gradient accumulation to remove the memory problem? Accumulation does fix memory. It does not change the fact that noise is spread over all $d$ parameters. The $m = d$ ablation is exactly this alternative, run with our accounting, so the comparison directly measures what dimension reduction buys.

Why not just train one global DP model? The file reports that uniform noise disproportionately erases minority cohorts (robust clustering paper), and even without noise the global model loses more than six points to IFCA on Rotated MNIST. We include it so that the gap is measured under privacy, not assumed.

Proposed Experiments

Utility experiments use Rotated MNIST with four and with eight rotation groups, Rotated CIFAR-10 with two groups, FMNIST with covariate and concept shift as in R-DPCFL, FEMNIST split by writer, and Dirichlet-split CIFAR-10. We vary the number of examples per client to locate the predicted failure point. We report mean and worst-cluster accuracy, adjusted Rand index of the recovered clusters, accuracy of the estimated $K$, and peak client memory, all at total $\epsilon \in \{1, 3, 8\}$ with $\delta$ fixed. The budget split between sketch and training is swept.

The first decisive check is the scaling test. Plotting clustering error against $\sigma\sqrt{m}/(n_i \Delta)$ should collapse results from different $m$ and $n_i$ onto one curve. If it does not, the mechanism we claim is not the operative one.

Leakage experiments report reconstruction PSNR for DLG and GIAS and patch reconstruction rate for the active attack. The non-private references from the file are a GIAS PSNR of 15.58 dB on CIFAR-10 versus 13.78 dB for pixel-space attacks, and PEFTLeak recovering 82.8% of CIFAR-10 patches at batch size 32 (MineGrad/PEFTLeak). We reproduce these first on raw updates to validate our attack implementations, and only then attack our sketch and cluster-training channels.

The second decisive check is the cluster-targeted active attack. At matched $\epsilon_t$, does a poisoned model sent only to the smallest cluster reconstruct more than the same attack on a global model? A yes would be a new negative finding: clustering concentrates leakage onto minorities even under formal privacy. That would argue for a per-cluster minimum-size rule, or for allocating budget by cluster size. We will report the finding either way.

The third check is membership leakage. We train a classifier that predicts a client's true group from everything the server sees, and compare its accuracy with the bound implied by $\epsilon_s$. This confirms that the post-processing argument holds in practice and is not undone by information the server can observe outside the accounted releases, such as which cluster model a client is trained on.