Exact Privacy Accounting for N:M Structured Gradient Compression

When clients in federated learning send compressed gradients, the randomness of the compressor can itself provide differential privacy. Differential privacy is the guarantee that an observer cannot reliably tell whether any one person's data was used. Earlier work showed that a randomized three-level compressor, which sends +1, −1, or nothing for each coordinate, gives strong privacy for free. Sending more zeros leaves an adversary less to test. That work used an unstructured pattern: any coordinate may be zeroed independently of the others. Unstructured patterns are expensive in practice. The message has a variable number of nonzeros at arbitrary positions, so it needs per-coordinate index encoding, and the server must merge many such messages with irregular scatter operations. The hardware-friendly alternative is N:M sparsity, where exactly N of every M consecutive entries are nonzero. It removes most of this cost, but nobody has worked out how much privacy an exactly-N-of-M compressor gives.

We propose a family of stochastic N:M ternary compressors and compute their privacy exactly, not asymptotically. The tool is the hypothesis-testing view of privacy, which describes a mechanism by the full curve of error rates an optimal adversary can achieve. A 2:4 block has only 24 possible outputs: 6 position patterns times 4 sign patterns. Its privacy curve can therefore be computed exactly by enumeration and then composed numerically across blocks and rounds. This removes the large-dimension approximation that current analyses rely on, and it answers a concrete question. Does forcing exactly N nonzeros per block (negatively coupled selections) leak more or less than independent per-coordinate dropping at the same density and the same message size?

Core Claim

The main claim concerns the joint distribution of an exactly-N-of-M position pattern and the signs sent at those positions. We claim this joint distribution has a computable privacy curve, a "trade-off function" in the language of f-differential privacy. We expect that, at a matched bit budget per coordinate, a suitably designed 2:4 or 2:8 stochastic compressor gives a privacy–accuracy trade-off no worse than independent ternary compression. It does so with fixed-length messages that the server can merge with dense, regularly indexed operations.

The bit budget is the crux. An unstructured ternary message at density one half has an entropy floor of 1.5 bits per coordinate before any index overhead. A 2:4 message costs $(\log_2 6 + 2)/4 \approx 1.15$ bits per coordinate with no index overhead at all. That puts it close to the 1-bit cost of sign compression.

The second claim is that exact per-block accounting matters most where the existing asymptotic analysis is weakest. That means small models, few blocks, and strong privacy targets. There, the approximation in current compressor analyses may misstate the privacy level.

What Exists and What Is Missing

This proposal builds on two papers. Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy derives privacy curves for binomial noise and a ternary stochastic compressor. It proves that compression amplifies privacy, and it reports that exact analysis tightens a loosely accounted ε of 3.18 to 1.67. It also reports ternary compression reaching ε≈0.2 where a competing compressor (SQKR) gives ε=2.

Its sparsity is coordinate-independent, and its vector-level results lean on a central limit theorem as dimension grows. Its authors list both the asymptotic slack and the lack of structured patterns as open problems. Noisy SIGNSGD Is More Differentially Private Than You (Might) Think does the analogous analysis for 1-bit sign compression with Gaussian noise. It reports about 1.5× more training iterations than uncompressed private SGD at the same budget, but it never zeros coordinates.

The underlying accounting machinery comes from Deep Learning with Gaussian Differential Privacy. That paper introduces Gaussian differential privacy, a privacy measure summarized by one parameter μ, and shows that its central-limit accounting gives ε=5.07 on MNIST where the older Moments Accountant gives 7.10. Hypothesis Testing Interpretations and Renyi Differential Privacy supplies the reduction of privacy to binary tests between worst-case output distributions. Our per-block enumeration rests on that reduction.

On the efficiency side, Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch establishes N:M as the pattern hardware handles well, and High Performance Unstructured SpMM Computation Using Tensor Cores shows that making unstructured sparsity fast requires reordering preprocessing. That preprocessing only pays off when the pattern is static. A per-round random compression pattern is the opposite of static, so the reordering route is closed for our setting.

The private-pruning works Differential Privacy Meets Neural Network Pruning and Pre-Pruning and Gradient-Dropping Improve Differentially Private Image Classification motivate the idea that fewer active coordinates help private training. They use central private training with scalar ε accounting and unstructured masks. Their masks are data-independent, so they claim no amplification from the masking itself. We study the different case where the selection is randomized per message and hidden inside a compressor whose output is all the server ever sees.

We deliberately do not claim Sparse Tensor Core speedups for training. The efficiency argument here is narrower and checkable. It covers fixed message size, the absence of index coding, and regular decoding and aggregation at the server.

Research Program

The compressor family. Each client bounds every coordinate to $[-c, c]$, as in the ternary compressor of the NeurIPS 2023 paper above. For each M-block, the client then samples exactly N positions. The inclusion probabilities interpolate, under a parameter $\lambda \in [0,1]$, between uniform ($\lambda=0$, so the pattern carries no data) and magnitude-proportional ($\lambda=1$, so the pattern carries magnitude information). The sampling uses conditional Poisson sampling so that the inclusion probabilities are exact. At each kept position the client emits +1 with probability $\tfrac{1}{2}(1 + x_i/B)$ and −1 otherwise, where $B \ge c$ controls how close the sign is to a coin flip. A server-side rescaling makes the estimate unbiased.

The $\lambda=0$ member is the cleanest object. All of its privacy comes from sign randomness plus hiding which coordinates were sampled. Larger $\lambda$ trades privacy for lower variance.

Exact per-block privacy curves. Neighboring datasets change one client's vector. With coordinate-wise bounds, the blocks are conditionally independent, so the full mechanism is a product of block mechanisms. For one block we compute the privacy curve exactly. We enumerate the $\binom{M}{N}2^N$ outcomes, sort them by likelihood ratio, and trace the optimal test, which is exact for finite outcome spaces. We take the worst case over pairs of block inputs.

We will try to prove that the extreme pair (all coordinates at +c versus all at −c) is worst for symmetric designs, using monotone likelihood ratios. Failing a proof, we will certify it by exhaustive search on a fine grid of vertices. Composition across $d/M$ blocks and $T$ rounds is done numerically on the distribution of the log-likelihood ratio, the privacy loss distribution, using discretization and fast Fourier transform convolution. This gives a non-asymptotic curve with explicit discretization error. We compare it against the Gaussian-differential-privacy central-limit approximation to measure when that shortcut fails.

The coupling question. We compare the 2:4, 2:8 and 4:8 compressors against independent ternary compression at the same expected density and the same B. This isolates whether forcing exactly N nonzeros per block helps or hurts the privacy curve. The answer is not obvious. Negative correlation between selections reduces variance in how many coordinates are revealed, which could tighten the tails of the privacy loss, but the pattern also reveals more joint structure.

Systems measurement. We implement client-side compression and server-side decoding and aggregation for both message formats on a GPU. N:M messages are stored as a fixed-shape value tensor plus a pattern index per block. A 2:4 message has the same values-plus-metadata shape that Ampere sparse kernels consume, which we note for format compatibility only and make no claims about. Unstructured ternary messages are stored with index coding and merged by scatter-add. We report bits per coordinate and server aggregation time as the number of clients and the model size scale.

Baselines

The naive reference point is uncompressed private federated SGD: clipping plus Gaussian noise, accounted with the Gaussian-differential-privacy method of Deep Learning with Gaussian Differential Privacy. It uses 32 bits per coordinate. It bounds how much accuracy compression may cost, and gives a reference ε at matched noise.

The strongest communication-efficient competitor is G-NoisySign from Noisy SIGNSGD Is More Differentially Private Than You (Might) Think. It sends 1 bit per coordinate with Gaussian noise before the sign, and the paper reports roughly 1.5× more iterations than private SGD at an equal budget. The file gives no reported accuracy number for its CIFAR-10 or Fashion-MNIST non-IID runs, so we will rerun it with its accounting.

The closest method competitor is the unstructured ternary compressor of Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy, whose reported figures are ε=1.67 versus 3.18 under loose accounting, and ε≈0.2 versus SQKR's ε=2. We reproduce these on its distributed mean estimation setting before extending it.

The key ablation is an independent-Bernoulli ternary compressor matched to each N:M configuration in density, sign parameter B and selection rule $\lambda$. It differs only in the exactly-N coupling.

All methods share the same data partitions, model, number of rounds, client sampling and clipping procedure. Each gets the same hyperparameter search budget over learning rate, B or σ, and c. All are evaluated at matched final privacy, μ or (ε, δ=1e-5), computed with each method's tightest available accountant.

The proposal beats the baselines if it reaches higher test accuracy or lower mean-squared error than independent ternary compression at the same privacy and fewer or equal bits. It must also be within a small margin of G-NoisySign accuracy at matched privacy, at 1.15 versus 1 bits per coordinate, while beating the unstructured ternary compressor on server aggregation time.

Why not just…?

Why not just use Noisy SignSGD, which already costs only 1 bit and has a tight privacy analysis? This is the real threat. Sign compression sends every coordinate densely, and its 1.5× iteration gain at equal budget is a strong result. N:M ternary must justify its extra 0.15 bits per coordinate through better privacy per round. Hiding which coordinates were sampled is an amplification source that sign compression lacks. The matched-privacy, matched-bits comparison on Dirichlet-partitioned Fashion-MNIST and CIFAR-10 settles this directly. If sign compression wins across the board, we will report N:M as useful only where its exact accounting or variable density matters.

Why not just keep unstructured ternary compression and entropy-code it? Entropy coding can bring an unstructured message near its 1.5-bit floor at density one half. That is still above the 1.15 bits of a 2:4 message. It also leaves variable-length decoding and scatter-based aggregation at the server. The reordering route that makes unstructured patterns fast, from High Performance Unstructured SpMM Computation Using Tensor Cores, only amortizes for static patterns, while ours change every round. Our aggregation-time measurements quantify the gap. If it is negligible at realistic client counts, the systems half of the claim falls. The accounting half survives only if coupling does not hurt privacy.

Why not just apply the existing central-limit accounting to N:M compressors? For large models the central-limit approximation may well be accurate, and then exact enumeration adds rigor but little practical gain. We test this directly by plotting the gap between the exact and approximate curves as a function of block count and target δ. We predict the gap is material for small d and small δ, consistent with the asymptotic-slack limitation acknowledged by the NeurIPS 2023 paper. If it is not, we will say so.

Why not just prune with a fixed public mask, as in private sparse SGD? A data-independent mask fixed for all of training reduces the noise-receiving dimension. It adds no randomness hiding the client's message, so it gives none of the amplification we study. It also addresses central training, not compressed federated messages. The two are complementary. We include a fixed 2:4 mask variant only as a sanity check that per-round randomized selection, not sparsity alone, drives any privacy gain.

Proposed Experiments

The first check is analytic and cheap. On distributed mean estimation with synthetic bounded vectors, the setting of the NeurIPS 2023 paper, we compute exact composed privacy curves for 2:4, 2:8 and 4:8 at $\lambda \in \{0, 0.5, 1\}$. We do the same for their Bernoulli-matched twins and for the original ternary compressor. We report ε at δ=1e-5 and mean-squared error against dimension d. This settles the coupling question and measures the error of the central-limit approximation. We first reproduce the 1.67-versus-3.18 figure to validate our pipeline.

The second check is federated training on Fashion-MNIST and CIFAR-10 with Dirichlet non-IID partitions, following the Noisy SignSGD protocol. We plot test accuracy against final μ for all baselines at matched bits. The file reports no prior accuracy numbers for these runs, so every number is regenerated under one harness.

The third check is systems. On a single modern GPU, we measure server aggregation time and peak memory for 10 to 1,000 clients on models from a small CNN to ResNet-18 size. We compare N:M messages with index-coded unstructured ternary messages, and report the realized bits per coordinate including all metadata.

The decisive outcome is the joint one. If 2:4 compression matches or beats independent ternary compression on privacy-accuracy at fewer bits, and aggregates measurably faster, structured compression is a strict improvement. If coupling costs privacy, the exact per-block curves still deliver the first non-asymptotic accounting for any structured compressor, and they say precisely how much privacy hardware-friendly structure costs.