In federated learning, many devices train one shared model without sending their raw data anywhere. Some devices are always slow, and these are called stragglers. Practitioners usually handle them in one of three ways: drop them, give them smaller sub-models, or let them report late. Each choice changes which people the server effectively hears from in each round. Device speed often tracks income and region, so the slowest devices may hold a disproportionate share of a protected group. In that case the straggler policy quietly reweights the very group statistics a fairness constraint depends on. We think part of the well-known fragility of fairness hyperparameters comes from this. The weight on a fairness penalty, or the allowed disparity bound, may be tuned under one participation pattern and then deployed under another.
The proposal rests on a simple observation. The quantities a fairness constraint needs are tiny linear sums: per-group counts, per-group positive predictions, and per-group errors. Coded computing is the technique of adding mathematical redundancy so that a result can be rebuilt from any sufficiently large subset of workers. It is expensive when applied to full gradients, but nearly free when applied to a few dozen numbers. We propose a split protocol. The fairness statistics travel on a protected channel: each client computes them first, then sends them redundantly through peers so the server can always rebuild their sum. The model weights travel on an ordinary channel that may be compressed, shed, or dropped. The goal is a fairness constraint whose server-side estimate stays unbiased whatever the straggler pattern. That in turn should make its tuning parameter transferable across deployment conditions.
Core Claim
Let client $c$ hold $n_{c,g}$ examples of group $g$, with local constraint quantity $r_{c,g}$, such as a positive-prediction rate. Let $p_c$ be the probability that the client reports in a round. A server that aggregates only from clients who report sees, in expectation,
$$\hat r_g = \frac{\sum_c p_c\, n_{c,g}\, r_{c,g}}{\sum_c p_c\, n_{c,g}},$$
which equals the true group rate only when participation $p_c$ is uncorrelated with $r_{c,g}$. When slow devices are concentrated in one group, the constraint the optimizer believes it is satisfying differs from the one evaluated at test time. The tuned penalty weight or disparity bound then absorbs this bias, and the absorbed bias changes whenever the straggler regime changes.
Our claim has two parts, and both can be tested. First, an augmented Lagrangian fair trainer (a method that keeps a running price on constraint violations and raises it while the constraint is broken) can be fed the exact population constraint sum. This is done by protecting only the sufficient statistics with coded redundancy. The result should be a disparity bound $\epsilon$ that transfers across straggler regimes, which tuned penalty weights do not. Second, the redundancy needed costs a negligible share of uplink bandwidth, because the coded payload has roughly $4G$ entries for $G$ groups under equalized odds, compared with millions of weights.
This differs from the closest prior work in what gets coded and why. Coded Computing for Federated Learning at the Edge codes the whole gradient. To do so it linearizes the model with random Fourier features and ships parity data to the server, which limits it to kernel-style models and raises privacy questions it leaves unquantified. Coded Cooperative Networks for Semi-Decentralized Federated Learning relays maximum-distance-separable coded model updates through peers to survive channel outages, but pays for that redundancy at full model size and tracks no fairness metric. We reuse its peer-relay coding but apply it only to the fairness statistics. That choice works with deep networks, needs no parity data, and makes redundancy cheap.
Research Program
The protocol has three components.
The first is stats-first ordering. At the start of each round, every client runs one forward pass of the current global model over a fixed local evaluation subsample and computes its per-group sufficient statistics. It sends this vector before starting local training. This removes compute straggling from the fairness channel, because a forward pass is far cheaper than local epochs. It is also the simplest version of the idea, and we treat it as an ablation in its own right.
The second is coded peer relaying, which handles devices that fall silent from channel outages or disconnects. Each client shares its statistics vector with $d$ neighbors. Following the two-stage diversity network code of Coded Cooperative Networks, the neighbors forward coded linear combinations to the server, so the server can decode the population sum $\sum_c s_c$ from any sufficient subset of transmissions. The server needs only the sum, so each forwarded message stays at statistics size. We will use the numerically stable circulant and rotation embeddings of Numerically stable coded matrix computations via circulant and rotation matrix embeddings in place of Vandermonde codes, which become ill-conditioned in floating point. Where devices fail at known and uneven rates, we will set redundancy per client using the duality-based allocation of Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers.
The third is the optimizer. The server runs the smoothed, linearized stochastic augmented Lagrangian method (SSL-ALM) from Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks. That benchmark found SSL-ALM gave the best fairness-accuracy compromise on Folktables. It also found the switching-subgradient method satisfied constraints at high error and the ghost method was extremely hyperparameter-sensitive. Under our protocol, the dual variables are updated from the decoded population statistics. The model weights are updated from whichever clients finish, through any standard straggler policy, including invariant dropout from FLuID or code-masked sub-models from Fast Server Learning Rate Tuning for Coded Federated Dropout.
One limitation has to be stated up front. Correcting the constraint estimate does not supply weight updates from groups whose devices never finish training. A correct dual price can only steer the clients who do report. Our analysis will therefore separate two sources of bias: bias in the constraint estimate, which the protocol removes, and bias in the weight updates, which it does not. We expect the second to matter most when slow devices are both rare and the only holders of a group.
There is an architectural reading of this limitation. Rethinking Bias Mitigation: Fairer Architectures Make for Fairer Face Recognition shows that network wiring itself drives demographic bias. FLuID-style load shedding effectively hands slow, possibly minority-heavy clients a different and smaller architecture. We will measure how much of the residual disparity tracks the sub-model capacity each group receives.
We treat architecture search mainly as a cost constraint, not a component. Federated search such as FedNAS doubles per-round uplink, because clients send both weights and architecture parameters. A fix confined to the constraint channel should be ruled in or out before anyone pays for fair federated architecture search.
The motivating evidence comes from two places. Fairness in Federated Learning: Fairness for Whom? reviews 121 papers and finds that only 8.4% of the federated learning literature evaluates group fairness, and that 90% of studies use synthetic splits. Correcting Overparameterization Effects in Fair Empirical Risk Minimization shows that training-time fairness can be an illusion that fails at test time in overparameterized models. That second result constrains us: correct training statistics are necessary but may not be sufficient. For this reason we always report disparity on held-out clients and groups.
Baselines
The naive reference point is federated averaging with a fixed fairness penalty, where stragglers are dropped at a round deadline. The penalty weight is tuned once under full participation and then deployed unchanged under each straggler regime. This is what a practitioner gets by default, and it isolates the hyperparameter-transfer failure we hypothesize.
The strongest existing fairness competitor is federated SSL-ALM with drop-stragglers aggregation. It is the best-performing constrained method in the Folktables benchmark Benchmarking Stochastic Approximation Algorithms, here run with naive aggregation of constraint statistics. That paper reports qualitative rankings only. No reported result was found on Lacuna for exact SSL-ALM accuracy or disparity values on Folktables, and none for any federated variant. We will therefore establish this baseline's numbers ourselves, using the same model, data, rounds, and a matched tuning budget of an equal number of $\epsilon$ and step-size configurations, chosen on a validation regime separate from the test regimes.
The strongest straggler-handling competitors are FLuID and coded federated dropout, each run with SSL-ALM on top. For reference, FLuID reports 81.1% accuracy on FEMNIST against 80.6% for random and ordered dropout (FLuID). Coded federated dropout reports reaching 99.6% of no-dropout accuracy with 2.43× less bandwidth on EMNIST62 (Coded Federated Dropout). Neither paper reports a fairness metric. Our protocol counts as beating them if it matches their accuracy within one point and wall-clock time within 5%, while reducing the change in test disparity across straggler regimes by at least half at a fixed $\epsilon$.
We also include an inverse-participation-weighted aggregator. It divides each reported statistic by an estimated $p_c$, which is the standard unbiasing fix and our most serious competitor. Two ablations isolate the key ingredient: stats-first ordering without coded relaying, and coded relaying without stats-first ordering. Full-gradient coded relay in the style of Coded Cooperative Networks serves as an upper bound on recovery and a lower bound on bandwidth efficiency.
Why not just…?
Why not just reweight reported statistics by inverse participation probability? This is unbiased in expectation, and it is a real threat when straggling is mild and participation rates are known. It fails in two cases. When the slowest clients report rarely, dividing by a small $p_c$ makes the estimate high-variance. Mini-batch noise in constraint estimates is already the failure mode the Folktables benchmark identifies for stochastic Lagrangian methods. And when $p_c$ must itself be estimated, errors feed directly into the constraint. We will sweep the minimum participation probability from 0.5 down to 0.05. We expect reweighting to match our protocol at high participation and to diverge at low participation. If it does not diverge, we will report that the coding component is unnecessary.
Why not just send the statistics first and skip the coding? Stats-first ordering alone may well remove most of the bias caused by slow computation, and we expect it to. It cannot help a device that is disconnected or whose upload fails. The test is whether coded relaying adds anything beyond stats-first ordering under channel-outage regimes. Coded Cooperative Networks reports accuracy gains of up to 7% and 21% over anonymous and non-anonymous uncoded schemes under outages on non-IID MNIST, which suggests outages matter. If stats-first ordering suffices even there, the honest conclusion is a simpler protocol, and we would say so.
Why not just retune the fairness hyperparameter for each deployment? The straggler regime at deployment is rarely known in advance, and it changes over time. A separate tuning run per regime multiplies a cost that is already high, given the hyperparameter fragility documented in Fairness-Aware Vision Transformer via Debiased Self-Attention and the Folktables benchmark. Our cross-regime transfer experiment measures exactly what retuning would recover, and the per-regime oracle-tuned baseline gives that ceiling.
Why not just search for a fairer architecture federatedly? Rethinking Bias Mitigation shows that searched architectures can Pareto-dominate standard backbones: 3.10% against 4.35% error on CelebA for ArcFace, with combined debiasing improving a fairness metric by 98.9%. But it trained 355 configurations centrally, and federated search adds dual weight-and-architecture uplink. Architecture also does not fix a biased constraint estimate. We view search as complementary and treat it as out of scope until the cheaper fix to the constraint channel has been tested.
Proposed Experiments
The primary testbed is Folktables income prediction with US states as clients. This gives naturally non-IID clients and real protected attributes, which answers the synthetic-split critique in Fairness for Whom?. We simulate four straggler regimes:
- no stragglers;
- 30% uncorrelated compute stragglers;
- 30% compute stragglers whose probability rises with the share of a protected group on the client;
- correlated channel outages.
Latency distributions are drawn from the five-phone heterogeneity profile in FLuID. The secondary testbed is CelebA partitioned into clients, with gender and age as protected attributes. It uses a ResNet-18 backbone so that the sub-model capacity effects of load shedding are visible.
The decisive check is hyperparameter transfer. For every method, we tune once under one regime and deploy under each of the others. We then report three quantities:
- the absolute change in test equalized-odds gap and demographic-parity gap;
- the change in accuracy;
- the width of the hyperparameter interval that keeps test disparity under a target, which measures sensitivity directly.
The core claim is supported if, at a fixed $\epsilon$, SSL-ALM with the protected channel shows a disparity change across correlated regimes that is at most half that of drop-stragglers SSL-ALM, with accuracy within one point. It is refuted if the gap stays the same, or if inverse-participation reweighting matches the protocol at every participation level.
We will also measure uplink bytes, expecting the coded statistics to add under 0.1% of model payload. We will measure wall-clock time against FLuID and coded federated dropout. Finally, we will decompose residual disparity into bias in the constraint estimate and bias in the weight updates by comparing against an oracle server that sees exact population statistics. This tells us how much fairness can be recovered by fixing the constraint channel alone and how much requires slow clients to actually train.
References
- Coded Computing for Federated Learning at the Edge
- Coded Cooperative Networks for Semi-Decentralized Federated Learning
- Numerically stable coded matrix computations via circulant and rotation matrix embeddings
- Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers
- Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks
- FLuID: Mitigating Stragglers in Federated Learning using Invariant Dropout
- Fast Server Learning Rate Tuning for Coded Federated Dropout
- Rethinking Bias Mitigation: Fairer Architectures Make for Fairer Face Recognition
- FedNAS: Federated Deep Learning via Neural Architecture Search
- Fairness in Federated Learning: Fairness for Whom?
- Correcting Overparameterization Effects in Fair Empirical Risk Minimization
- Fairness-Aware Vision Transformer via Debiased Self-Attention