Public Masks for Private, Index-Free Gradient Sparsification

Federated learning trains a shared model by having each device send back an update (a gradient) instead of its raw data. Two problems follow. The updates are large, so uploading them is slow. They also leak: an attacker who sees a gradient can often reconstruct the training images, labels, or text that produced it. Sending only a few coordinates of each gradient, which is called sparsification, is the standard fix for the first problem and is often offered as a fix for the second. The usual way to pick coordinates is to keep the largest ones. That choice creates a quiet contradiction. The list of which coordinates were kept is computed from private data, so it is itself a leak. In a language model, the nonzero rows of the word-embedding gradient are exactly the words in the client's batch. The list also costs bits: a coordinate index can take several times more bits than the value it points to.

We propose choosing the mask from information the server has already published: the trajectory of past, privacy-noised global updates. Every client derives the same mask from public state, adds a small random exploration set, transmits only the values, and adds differential-privacy noise only on the selected coordinates. Because the mask depends on nothing private in the current round, it reveals nothing about the current batch. It needs no index bits. It also costs no privacy budget, since any computation on an already-private output stays private (the "post-processing" property). The open question is whether a mask built from public history captures enough gradient energy to beat random coordinate selection. Random selection has a formal privacy advantage, so this is far from obvious, and this note proposes the method, the accounting, and the experiments that would settle it.

Core Claim

Under client-level differential privacy at a fixed privacy level and a fixed upload budget, we claim that a mask derived from the noised global trajectory, plus a small random exploration set, gives higher accuracy than uniformly random sparsification. We further claim it removes the index channel through which magnitude-based sparsification leaks labels and tokens.

The mechanism comes down to one tradeoff. Suppose a client's clipped update $g$ is restricted to a $k$-coordinate mask that captures a fraction $\eta$ of its squared norm, and Gaussian noise of scale $\sigma C$ is added on those $k$ coordinates. Here $C$ is the clipping norm and $\sigma$ is set by the target privacy level. The error of the average over $n$ clients is then roughly

$$ \mathbb{E}\,\|\hat g - \bar g\|^2 \approx (1-\eta)\,\|\bar g\|^2 + \frac{k\,\sigma^2 C^2}{n}, $$

where $\bar g$ is the true average update. The first term is signal lost to the mask; the second is injected noise, which grows with $k$ rather than with the full dimension $d$.

The two approaches differ on each term. Uniform random selection, used by Fed-SPA, captures only $\eta \approx k/d$ on average. In return, the attacker's uncertainty about which coordinates were sampled lets it use a smaller $\sigma$. A public mask gets no such reduction in $\sigma$, but it can achieve $\eta \gg k/d$ if important coordinates persist from round to round. Time-Correlated Sparsification reports exactly this kind of persistence in a non-private setting. The claim therefore reduces to a measurable quantity: whether the measured $\eta$ of the public mask compensates for the noise reduction that random sampling earns.

Relation to Prior Work

Three papers supply the ingredients we reuse.

  • Mask persistence. Time-Correlated Sparsification shows that a mask agreed from the previous global step, plus a small local exploration mask, removes index overhead. With ResNet-18 on CIFAR-10 it reaches 92.44% accuracy at about 0.017 bits per parameter. It makes no privacy claim, and its local exploration mask is data-dependent. We keep the persistence idea, make the exploration part uniformly random, and derive the global part only from privatized aggregates.
  • Privacy from random sampling. Fed-SPA and Privacy Amplification via Compression show that random coordinate sampling strengthens formal privacy. Their proofs require the coordinates to be chosen uniformly at random, which is why magnitude-based sparsifiers have had no formal guarantee.
  • Noise growing with the kept set. Gradient Sparsification Can Improve DP Convex ML and Constrained DP Federated Learning for Low-Bandwidth Devices show that restricting updates to a low-dimensional or pre-selected subset makes the noise scale with the subset rather than the full model. They provide the second term of the equation above.

The constrained-DP work is the closest relative. It selects its subset in advance and keeps it fixed. Our subset is re-derived each round from released aggregates. The question is whether that adaptivity is worth the engineering, and the fixed-subset baseline below tests it directly.

Three papers motivate the proposal by showing that the index set leaks.

  • Clover identifies leakage through top-$k$ indices. It hides the indices with three-server secret sharing, which fails if two servers collude.
  • FILM recovers a batch's bag of words from the nonzero embedding-gradient rows. Top-$k$ on a language model would send that set in the clear.
  • LLG reads label counts from the signs and magnitudes of output-layer gradients.

Two results constrain the design. Huang et al. find that magnitude pruning alone must remove more than 99% of coordinates to stop strong image inversion, which costs about 10 points of CIFAR-10 accuracy. We therefore do not rely on sparsification itself for protection against inversion; the differential-privacy noise does that work. Deep Leakage from Gradients reported that 20% pruning sufficed, but Huang et al. show stronger attacks bypass that threshold. We treat 20% as a historical number, not a design target.

Research Program

The method has three parts.

  1. Mask construction. Each round, the server ranks coordinates by an exponential moving average of the magnitudes of past privatized aggregates. The top $k_g$ coordinates form the public mask. Clients can compute this mask themselves from the global models they already download, so it adds no extra downlink traffic.
  2. Exploration. Each client adds $k_r$ coordinates drawn uniformly at random. This lets important coordinates that are missing from the public mask enter it.
  3. Clipping, noise, and accounting. Clients clip the restricted vector and add Gaussian noise on the selected $k_g + k_r$ coordinates. The uplink sends values in a fixed, known order with no indices. The random exploration part can use the subsampling analysis of Fed-SPA; the public part is accounted for with standard Rényi composition, a way of adding up privacy cost over many rounds.

Two analysis tasks follow.

  • Accounting. We write the per-round privacy cost of the hybrid mask and confirm that deriving the mask is post-processing. This holds only if the aggregates are privatized; the ablation below with non-noised aggregates is an explicit warning case.
  • Energy capture. We measure $\eta$ across rounds, layers, and degrees of data heterogeneity, the quantity on which the claim rests.

For the attack side, we build mask-aware adaptive attacks. These include a gradient-matching attack restricted to the revealed coordinates, in the style of the cosine-similarity attack used by Huang et al., and an LLG variant that uses only the masked output-layer entries. Without adaptive attacks, a sparsification defense looks better than it is.

Baselines

Naive references. The first is dense DP-FedAvg with client-side clipping and noise. It sets the accuracy floor at each privacy level and the 32-bits-per-parameter communication ceiling. The second is non-private top-$k$ with indices transmitted. It sets the leakage ceiling, both for label and token recovery from indices and for inversion. Both run on the same data partitions, models, and rounds as our method.

Random sparsification under DP. The strongest formal competitor is Fed-SPA: random-$k$ sparsification with local Rényi privacy and a server-side adaptive optimizer. It reports 63% CIFAR-10 accuracy at $\epsilon=1$, and 92.65% MNIST accuracy at $\epsilon=1$ with $p=0.05$ (Fed-SPA). We will re-run it with our models and partitions, using the same server optimizer for both methods. This isolates mask selection from Fed-SPA's other ingredient, adaptive server optimization. We match $\epsilon$, $\delta$, total uplink bits, and the hyperparameter search budget. Beating it means higher accuracy at equal $\epsilon$ and equal bits, across at least three $k/d$ ratios and three seeds, with non-overlapping confidence intervals.

Cryptographic index hiding. The strongest systems competitor is Clover: top-$k$ with secret-shared aggregation that hides indices. It reports about 75% CIFAR-10 accuracy with ResNet-18 under DP (Clover), but the file does not give the $\epsilon$ for that number. We will therefore re-implement its accuracy behavior: top-$k$ with DP noise, assuming the indices are perfectly hidden. This gives an upper bound on what index hiding can buy. Our method wins if it comes within about one accuracy point of this bound without requiring non-colluding servers. If it does not, we will report that Clover's trust assumption is buying real accuracy.

Ablations.

  • Public mask only ($k_r = 0$) and random only ($k_g = 0$, essentially Fed-SPA). These separate the contributions of the two mask parts.
  • Fixed pre-selected mask, in the spirit of Constrained DP FL. This tests whether re-deriving the mask each round matters.
  • Mask derived from non-privatized aggregates. This shows the privacy accounting would break.
  • Stale masks updated every $T$ rounds. This measures how quickly importance drifts.

Why not just…?

Why not just add noise first and then take top-$k$? Selecting after noise is post-processing, so the indices are safe. However, at realistic noise levels in million-dimensional models, the largest noisy coordinates are mostly noise, so the selection captures little signal. This is the same problem of total noise growing with dimension that motivates the sparsification-for-DP line of work. We include this baseline at matched $\epsilon$ and bits and report its measured $\eta$. If it matches our method, the public-mask machinery is unnecessary, and we would say so.

Why not just use random sparsification as Fed-SPA does? This is the real threat. The extra privacy from random sampling reduces noise, and the comparison could go either way. The energy-capture measurement and the matched-budget sweep settle it directly. Discrepancy-aware calibration finds that selection quality matters a great deal under heavy compression, but that evidence is non-private, which is exactly why the private comparison is needed.

Why not just hide indices with cryptography, or exclude the leaky layers? Clover, EdgeDetect, and SHE-LoRA protect updates with secret sharing or homomorphic encryption. Each needs either non-colluding servers or a shared key, and the encryption-based schemes add compute that grows poorly with model size. FILM shows that freezing embeddings stops text recovery while barely changing perplexity (11.48 vs. 11.40). That fix targets one layer, and it does not help with output-layer label leakage or with models whose embeddings must be trained. We include embedding freezing in the text experiments. Cryptography is complementary: a public mask could be combined with it. Our claim is only that the index channel can be closed without any trust assumption.

Proposed Experiments

Vision. We train ResNet-18 on CIFAR-10 and a small CNN on MNIST, with Dirichlet non-IID partitions, at $\epsilon \in \{1, 4, 8\}$. We report three things:

  • accuracy as a function of total uplink bits;
  • measured $\eta$ by layer and round;
  • reconstruction quality (LPIPS, a learned measure of perceptual similarity between images) under the mask-aware gradient-matching attack, with Huang et al.'s undefended LPIPS of 0.45 as the reference.

We also report LLG label-recovery accuracy for each method.

Language. We train GPT-2 on WikiText-103 and Enron using the FILM code. We report perplexity, ROUGE-L of recovered text, and bag-of-words recall from the transmitted index set. For our method, that recall should be at chance by construction, and the experiment checks this end to end.

Decisive checks. The proposal succeeds if, at $\epsilon = 1$ and matched bits, the public-plus-exploration mask beats re-run Fed-SPA on CIFAR-10. It must also leave index-based token and label recovery at chance, where non-private top-$k$ exposes them. The proposal fails if measured $\eta$ stays near $k/d$ under non-IID data, since then public history carries no usable information. It also fails if the fixed-mask ablation matches the adaptive mask, since then re-deriving the mask each round adds nothing over existing pre-selection methods.