Who Gets Dropped by Gradient Compression? Minority Groups in Sparsified Federated Learning

Federated learning trains one model across many devices or institutions. Each participant computes a model update on its own data and sends only that update, never the raw records. To save bandwidth, deployed systems rarely send the full update. They send the largest few percent of its coordinates, a technique called Top-$k$ sparsification, and they often present this as a privacy benefit too, since a partial gradient seems harder to reverse into training data. This proposal asks a question nobody in the literature we found has measured: when a client keeps only the largest coordinates of its update, whose signal survives? We expect a direct parallel to a known result. In differentially private training, clipping each example's gradient bends the averaged update toward the majority group, and that bending is the main cause of privacy's unfair accuracy cost (Disparate Impact in Differential Privacy from Gradient Misalignment). Magnitude-based sparsification is another truncation of the update. When a batch is dominated by majority examples, the largest coordinates are majority coordinates, and a minority group's update may be dropped round after round.

The same selection step also decides privacy risk. Coordinates that survive compression are what an eavesdropper uses to rebuild training images. Generative attacks already recover faces, gender and skin tone from updates with 90% of entries pruned (Auditing Privacy Defenses in Federated Learning via Generative Gradient Leakage). Our claim is that one measurable quantity, the fraction of each demographic group's update that survives compression, controls both that group's accuracy loss and its exposure to reconstruction. If that holds, the bandwidth, fairness and privacy trade-off can be read, and tuned, group by group.

Core Claim

Write a client's local update as $u = \sum_g u_g$, where $u_g$ is the part contributed by examples from demographic group $g$. Let $C(\cdot)$ be the compressor. We define the group retention ratio

$$r_g = \frac{\langle C(u),\, u_g \rangle}{\|u_g\|^2},$$

which is the share of group $g$'s update direction that the transmitted message still carries. We make three claims. First, under Top-$k$ without correction, $r_g$ is systematically smaller for minority groups, and the gap widens as $k$ shrinks. Second, the gap in $r_g$ across groups predicts the gap in accuracy loss relative to dense training, which is the compression counterpart of the "privacy cost gap" in the clipping paper. Third, higher $r_g$ predicts better reconstruction of group-$g$ examples by gradient inversion. Taken together, these imply that any method which repairs fairness under compression will raise minority privacy exposure unless it is paired with an explicit defense. Existing systems handle at most two of the three quantities. ERIS compresses and resists reconstruction but never measures subgroup accuracy (ERIS). PUFFLE and RESFL handle fairness and privacy but send dense updates and never test gradient inversion (PUFFLE, RESFL).

Research Program

The first part is a measurement study. Following the clipping-misalignment paper, which does not need group labels at training time, we use group labels only to diagnose. We record $r_g$, the angle between the compressed update and the dense update, and per-group accuracy. We do this across compression rates and across compressors: Top-$k$, random-$k$, Top-$k$ with error feedback (unsent coordinates accumulate locally and are sent later), and low-bit quantization. Error feedback is the critical case. It may restore minority signal only after a delay, and under non-IID data and partial client participation a delayed signal can be a lost one. We will report whether it closes the gap.

The second part is a repair that does not use group labels. We call it balanced selection. The client decides which coordinates to send by ranking an update in which each microbatch's gradient is first rescaled to unit norm, so that a small, atypical cluster of examples gets a vote comparable to the dominant cluster. The client then transmits the original, unnormalized values at those coordinates. The mechanism is the same insight as DPSGD-Global-Adapt, which fixes direction by changing how magnitudes are treated. The difference is where it is applied: only to the choice of coordinates, not to the values sent, so convergence analysis for error-compensated sparsification still applies to the values. Microbatch normalization avoids the per-example gradient cost that the file flags as a burden of per-example defenses such as Gradient-Leakage Resilient Federated Learning. Microbatch size is the knob we will study.

The third part is a per-group privacy audit, which is the reason this work needs the privacy direction at all. Recent work shows fairness interventions open new attack surfaces (Do Fairness Interventions Come at the Cost of Privacy). The file also raises, as an open tension, that amplifying minority gradients could make minority samples easier to invert. We therefore run optimization-based gradient inversion and a generative-prior attack in the style of GGL against every compressor. We report reconstruction quality and attribute-recovery accuracy separately for each group. If balanced selection raises minority $r_g$, we expect it to raise minority exposure as well. The final component tests whether this exposure can be removed cheaply without giving back the fairness gain. Two candidate defenses are sharding the sparse message across aggregators, as in ERIS, and entangling updates with decoy gradients, as in Concealing Sensitive Samples against Gradient Leakage in Federated Learning.

Baselines

The naive reference is dense FedAvg with no compression. It fixes the accuracy each group would get with unlimited bandwidth, so every compressor's per-group cost is measured against it.

The main compression competitor is Top-$k$ with error compensation, implemented as the shifted-compression scheme of ERIS. It is the strongest method in the file that jointly targets bandwidth and reconstruction: it cut a 1.3B-parameter model's upload "from 5.2GB to 46.8MB". We run it at identical compression rates, client counts, local epochs and learning-rate sweeps. Balanced selection counts as beating it only if it lowers the per-group accuracy gap at an equal number of transmitted bits, without lowering overall accuracy by more than seed-to-seed variation. We found no reported result on Lacuna for the subgroup accuracy of Top-$k$ or ERIS.

The strongest fairness competitor is PUFFLE, run from its public code (lucacorbucci/PUFFLE) with its demographic-parity regularizer placed on top of the same compressor. It reports unfairness reduced by up to 75% at a maximum utility drop of 17% across its datasets, in the dense setting. Unlike our method, it needs group labels at clients. The fair comparison therefore matches its tuning budget for $\lambda$ to our budget for microbatch size.

For label-free direction repair, the reference point is DPSGD-Global-Adapt (Disparate Impact in Differential Privacy from Gradient Misalignment). On Unbalanced MNIST it raised minority-class accuracy from 26.3% to 65.5% relative to standard DPSGD, and reduced the privacy cost gap by nearly 50%. We use it in the private-training arm, combined with compression.

Two ablations isolate the key ingredient. The first is an oracle that selects coordinates using true group labels to balance retention; it sets an upper bound. The second varies microbatch size, with size equal to the full batch recovering plain Top-$k$. This tests whether normalization at selection time is what drives any gain.

Why not just…?

Why not just use error feedback, which eventually sends every coordinate? This is the most serious threat to the proposal. If error feedback fully closes the minority gap at realistic compression rates and participation levels, then balanced selection is unnecessary, and the contribution becomes the measurement plus a recommendation. The measurement study settles this directly by comparing per-group accuracy curves for Top-$k$ with and without error feedback against dense training. We will report that outcome whichever way it goes.

Why not just use random-$k$ sparsification, which has no magnitude bias? Random selection preserves each group's share in expectation. However, it adds variance that scales with the full dimension and usually needs far more bits to reach the same accuracy. It is a baseline at every bit budget. If it matches balanced selection on fairness at equal bits and equal accuracy, the proposed selection rule is not needed.

Why not just reweight minority examples with a fairness method such as FairGrad before compressing? Reweighting with FairGrad requires group labels at the client. Some clients hold only one group, which makes local fairness estimates degenerate, as the file notes for PUFFLE, and FedFair found local-only fairness constraints give worse global models (FedFair). We include reweighting plus Top-$k$ as a labeled baseline. Our privacy audit tests whether it inflates minority reconstruction more than balanced selection does.

Why not just add secure aggregation so the server never sees individual updates? Secure aggregation hides individual updates in transit but leaves the accuracy gap untouched, because the compressor bias occurs before encryption. Its cost is also what ERIS was designed to avoid. It is orthogonal to the fairness finding. We treat it as a threat-model variant rather than a competitor.

Proposed Experiments

The primary testbed is CelebA smiling prediction with sex as the protected attribute. It has fairness labels and is a standard target for gradient inversion. We partition it non-IID so that some clients hold mostly one group. We add Unbalanced MNIST, where digit 8 makes up 1% of the data, because the clipping-misalignment paper gives a reference point there. We add ACS Income partitioned by U.S. state as a naturally federated tabular task, and Dutch census as a second tabular task. For compression rates of 10%, 1% and 0.1% of coordinates, we report overall accuracy, per-group accuracy, the gap in accuracy loss relative to dense training, the equal-opportunity gap, bits sent upstream, and $r_g$.

For privacy, we attack single-client updates at several batch sizes. We report reconstruction PSNR and SSIM per group, and for the generative attack, the accuracy of an attribute classifier applied to the reconstructions. Published reference points calibrate the attack pipeline. With no defense, reconstruction PSNR is 59.20 on MNIST, falling to about 7.84 under the decoy-gradient defense (Concealing Sensitive Samples against Gradient Leakage in Federated Learning). GGL keeps PSNR above 5.7 on ImageNet against DP and other defenses. No per-group reconstruction numbers under compression were found on Lacuna.

Three results are decisive. First, under Top-$k$, the cross-group gap in $r_g$ must correlate with the cross-group gap in accuracy loss across rates, datasets and seeds; if it does not, the core claim fails. Second, balanced selection must shrink the fairness gap relative to error-compensated Top-$k$ at equal bits. It must also stay within noise of the labeled oracle as microbatch size shrinks. Third, the per-group audit must show whether raising minority $r_g$ raises minority reconstruction quality. If it does, adding sharding or decoy entanglement must remove that increase without reopening the accuracy gap. That last result is what would show fairness, privacy and bandwidth being traded off together, per group, in one protocol.