Fair federated learning under heterogeneity
A federated aggregation rule that follows the FedAvg direction and bends it only as much as needed to give every client a minimum of progress. It has one tolerance τ, keeps a short server-side memory of recently seen clients, and returns the FedAvg direction unchanged whenever no client falls short.
TL;DR
FedAvg trains one model for many clients by averaging their updates. When clients hold very different data, that average can make little, no, or even negative progress for some of them. Existing fairness-aware methods reweight clients, correct conflicting updates, or search for a common descent direction, and in doing so they often change the global direction or treat every client as a symmetric peer. FedPCD keeps the FedAvg direction as the primary objective and turns every client into a minimum-progress constraint. The server takes the direction closest to the average that still gives each client a τ-fraction of progress, and it remembers recently seen clients so that partial participation does not leave them unprotected. When the average already serves everyone, the direction is exactly FedAvg's.
Video
A ten-minute tour: why the average can leave clients behind, how FedPCD's projection and its client history work, what the theory guarantees, and the results on CIFAR-10, CIFAR-100 and Fashion-MNIST.
Narration voice generated with ElevenLabs.
The mechanism, interactively
Three clients send updates that pull in different directions, and their normalized average g̃0 is the FedAvg direction. Each client asks for a minimum of progress, g̃i⊤d̃ ≥ τ‖g̃i‖², which admits a half-space of directions. FedPCD projects the average onto the shaded region where every client is satisfied. Drag the client arrows and slide τ to see when the average has to bend, and by how much.
In the figure (click a layer to hide it)
At τ = 0, FedPCD only asks that no client gets worse, to first order. A larger τ tightens every constraint, and the update bends further toward the clients that need it.
Client directions
Unit client directions in two dimensions, with equal weights. The experiments use τ between 0.005 and 0.1. It is larger here so that the geometry is easy to see.
An interactive version of the gradient-space panel of Figure 2 in the paper, in the same colors. It opens on the paper's example: clients at 10°, 45° and 155° with τ = 0.25. Only client 3's constraint is active there, so the update is the average plus μ3⋆ = 0.36 of client 3's direction, and the other two clients still get more than their minimum.
The idea
FedPCD is a federated adaptation of Priority-Constrained Descent (PCD), a method for problems in which one objective matters more than the others. Here the FedAvg update takes the primary role, and each client's own update defines a secondary constraint.
Each participating client returns its model displacement Δi,t after K local steps, as in FedAvg. The server divides it by the local learning rate to obtain a pseudo-gradient, and aggregates these with the FedAvg weights:
The aggregate and every client direction are then normalized:
The update is the direction closest to the normalized average that still makes a τ-fraction of progress along every client's direction:
Each constraint is a half-space of acceptable directions. This small convex quadratic program is therefore the Euclidean projection of the FedAvg direction onto their intersection, and its solution is unique. Its optimality conditions give it one revealing form:
The average keeps a coefficient of one. A client enters only through a non-negative multiplier, and that multiplier is zero unless the client's constraint is active. FedPCD does not replace the global update with a reweighted or symmetric multi-objective direction. It retains the average as the primary direction and applies the minimal correction that the clients require.
Because the program works with normalized directions, the server rescales the solution to the length of the aggregate before taking the step:
When nothing needs fixing. If the average already satisfies every constraint, then d̃⋆ = g̃0, and the rescaling gives dt = ḡt. FedPCD introduces no directional correction in that round.
One round of FedPCD
Algorithm 1 in the paper. On the clients, it is a FedAvg round.
Partial participation
In practice only 5% or 10% of clients join each round, so each round's program sees only a handful of them. A client with unusual data can go unseen for many rounds, and while it is away nothing protects it.
FedPCD gives the server a history window of H rounds. It keeps the most recent pseudo-gradient of every client that took part within the window, and each cached direction adds one more constraint, h̃i,t⊤d̃ ≥ τ‖h̃i,t‖². A client that returns overwrites its entry, and an entry older than H rounds is removed. The primary direction ḡt is still computed only from the clients of the current round. History changes who is protected, not what the average is.
Under independent uniform participation at rate ρ, the expected number of distinct clients represented once the window has filled is
With N = 100 clients, ρ = 0.1 and H = 10, that is about 69 clients in every program instead of 10.
A simulation of the cache alone: 100 clients, sampled uniformly without replacement each round, as in the experiments. Set H = 0 to see what the program holds without history.
The window is a trade-off. A longer one represents more clients, and it also keeps older directions.
Guarantees
Whenever the program is feasible, its solution satisfies g̃i,t⊤d̃⋆ ≥ τ‖g̃i,t‖² for every client of the round and for every cached client. With τ > 0, the update is positively aligned with each of them by construction.
If the normalized average already meets every constraint, the projection is the identity and d̃⋆ = g̃0. After rescaling, dt = ḡt: the round keeps the conventional federated direction, with no correction.
Otherwise the solution is the unique closest admissible direction to the average, and only active constraints contribute to it. The result is rescaled to ‖ḡt‖, so the program changes the direction of the update and not its magnitude.
With full participation, deterministic local steps, no history, L-smooth client objectives and a uniform alignment margin γ, the round-averaged squared norm of the global gradient falls as O(1/T) with constant learning rates, including for K > 1 local steps (Theorem 4.1).
The same rate holds for the clients' own gradients. Under the same conditions every accumulation point is composite multi-stationary: each client is stationary on its own. That is stronger than Pareto stationarity, where nonzero client gradients may simply cancel (Corollary 4.2).
The alignment and local-drift lemmas, the descent argument behind the rate, and a careful account of what the client-progress and stationarity statements do and do not cover.
See the appendix →Theorem 4.1, for a server step 0 < ηg ≤ γeff / (LK(1+r)). Here r measures the drift of K local steps and γeff = γ(1−r) − r is the alignment margin that remains after it. The margin γ describes the geometry of the constrained direction and is not a hyperparameter.
Results
CIFAR-10, CIFAR-100 and Fashion-MNIST with 100 clients, at 5% and 10% participation and three levels of heterogeneity. That makes 18 settings, each averaged over five seeds, against ten baselines: FedAvg, AFL, q-FFL, Ditto, FedMGDA+, FedFV, FedLF, FedHEAL, FedPW and CRAFT.
On CIFAR-10 at 5% participation, FedPCD reaches 71.90% global accuracy, against 65.59% for the strongest baseline, FedLF, and 48.09% for FedAvg. Its worst 10% of clients reach 52.88%, more than 14 points above FedLF's.
Compared with FedAvg, the whole distribution of client accuracies moves to the right and its lower tail thins out. Compared with the strongest baseline, more of the clients sit near the top.
Numbers in the text are those of the paper's Table 1, at FedPCD's best τ. The figures fix τ = 0.02, so their labels differ slightly.
Spread alone can mislead, because a method can look even by keeping every client low. On CIFAR-100, AFL has the lowest σc in all six settings, at global accuracies between 5.64% and 14.55%.
Plotted against accuracy, FedPCD is at least as accurate and at least as even as all ten baselines on CIFAR-10 and Fashion-MNIST at 5% participation, and as at least nine of the ten at 10%.
On CIFAR-100 its spread is higher than the baselines', because σc grows with the accuracy it is measured around. Jain's fairness index does not, and it ranks FedPCD first in all six CIFAR-100 settings.
On CIFAR-10, FedPCD reaches FedAvg's final accuracy by round 110 of 500, about 4.5× fewer rounds. At 5% participation it reaches the final accuracy of the strongest baseline by round 280.
On CIFAR-100 it matches FedAvg's final accuracy by rounds 180 and 140, at 5% and 10% participation. On Fashion-MNIST it needs 40 and 30 of the 300 rounds.
What matters
Take the history away and FedPCD falls from 74.84% to 59.26% on CIFAR-10, close to FedAvg's 57.47%. The other components cost less to remove, and each of them still costs something.
Component ablation
CIFAR-10, 10% participation, α = 0.01, five seeds
From the paper's component ablation. Variants with history use τ = 0.01, the best value for this setting in Table 1. The history-free variant uses its own best tested value, τ = 0.1.
Scope
Citation
@misc{irshaid2026fedpcd,
title = {{FedPCD}: Priority-Constrained Federated Aggregation},
author = {Irshaid, Yousef and Varam, Dara and AlHajri, Mohamed I.},
year = {2026},
note = {Preprint, under review},
url = {https://daravaram.github.io/FedPCD/}
}
FedPCD builds on Priority-Constrained Descent (TMLR 2026). This entry will be updated when the preprint is on arXiv.