Federated learning trains one model across many phones or sensors. Each round, a server picks a few devices to send back their model updates. Two research lines pick those devices for opposite reasons. Wireless scheduling picks whichever devices currently have the strongest radio links. Radio signal strength fluctuates randomly from moment to moment, an effect called fading, and in a large population someone is always lucky. Diversity-based selection instead picks devices whose updates best summarize the whole population. It uses greedy algorithms that come with provable worst-case guarantees. We propose to merge these two lines with one observation. The redundancy that diversity selection treats as waste is exactly what wireless scheduling needs. If twenty devices hold near-duplicate data, the server does not care which one it hears from. So it can hear from whichever of the twenty has the best channel right now, and that device needs far less transmission time than an average one.
The concrete proposal is a per-round selection rule. It maximizes a coverage objective over client updates, subject to a fixed budget of total airtime (transmission time), where each client's airtime is set by its current channel. A cost-aware greedy algorithm solves it with a constant-factor guarantee. We pair this rule with a finite-population scaling analysis. The analysis predicts how quickly the airtime needed to reach a given level of population coverage falls as within-cluster redundancy grows. It plays the same role for learning that degrees-of-freedom scaling laws play for interference networks.
Core Claim
In each round $t$, the server holds a possibly stale update vector $g_u$ for every client $u$ in the population $V$. It also knows each client's current signal-to-noise ratio $\text{SNR}_i(t)$, which is ordinary scheduling feedback. Uploading a $b$-bit update over bandwidth $W$ takes airtime $c_i(t) = b / (W \log_2(1+\text{SNR}_i(t)))$. We select
$$S_t = \arg\max_{S \subseteq V,\ \sum_{i\in S} c_i(t) \le B} \ \sum_{u \in V} \max_{v \in S} \text{sim}(g_u, g_v),$$
where $B$ is the airtime per round and $\text{sim}$ is the similarity used by DivFL.
Within a round the costs are known numbers, not random ones. The problem is therefore ordinary monotone submodular maximization under a knapsack constraint. A standard greedy method fits it: rank clients by marginal coverage gain per unit airtime, and also compare against the best single client. This gives a constant-factor guarantee every round. The randomness of fading enters only across rounds, which is where opportunism pays off.
The claim that would be new concerns redundancy. Suppose clients fall into clusters of $m$ near-duplicates, with within-cluster dissimilarity $\epsilon$, under independent Rayleigh fading. Then the best channel within a cluster grows roughly like $\log m$, because the maximum of $m$ exponential gains grows logarithmically. The airtime needed to cover every cluster therefore shrinks by about a $1/\log m$ factor relative to channel-oblivious selection. The coverage lost by substituting a lucky duplicate is at most $\epsilon$ per covered client. Clusters of size one, meaning rare clients, get no such discount. Instead, their large uncovered marginal gain makes the greedy rule schedule them in rounds when they happen to fade upward. This is the behavior a fixed SNR threshold destroys.
Relation to Prior Work
Three papers motivate the gap from the learning side. DivFL shows that selecting clients with a facility-location objective, which approximates the full-population gradient, reaches target loss about 10x faster than random selection on synthetic IID data and about 5x faster on non-IID data. SUBTRUNC and UNIONFL add fairness through truncation and a look-back window. FedCG runs continuous greedy across clients under matroid constraints. All three treat the network as an error-free pipe with uniform cost per client. We keep DivFL's objective and stale-gradient trick unchanged and replace its cardinality constraint with a fading-driven airtime knapsack.
From the wireless side, Federated Learning Over Wireless Fading Channels has its digital scheme schedule the single best-channel device. That scheme ignores data diversity, and it trails over-the-air analog aggregation (nearly 90% versus under 80% on MNIST with 25 devices). This result is a constraint on our design: the digital baseline we must improve on is weak, and analog aggregation is a serious competitor. Distributed user selection through random access ranks clients by update novelty through contention backoff. It optimizes no collective set function and models no fading.
The closest structural precedent is Coordinated Multicasting With Opportunistic User Selection. It also trades coverage, the fraction of users who decode, against rate within each fading block. It reports group-rate gains often over 20% at low SNR, using a reverse-pruning heuristic that has no approximation guarantee. Our setting differs: its users are interchangeable receivers of one file, whereas our coverage is measured in gradient space. Our forward greedy method also carries a provable ratio.
The scaling analysis borrows its viewpoint from the opportunistic interference literature. (n, K)-user interference channels and OIA user scaling laws derive how large a user pool must be to buy degrees of freedom. Those papers also concede that small, finite pools collapse. Our analysis asks the finite-pool question directly, with redundancy $m$ playing the role of pool size.
Research Program
The work has three parts. The first is the algorithm. We will build cost-benefit greedy for the per-round knapsack, with stochastic subsampling of candidates in DivFL's style to cut the $O(kN)$ evaluation cost. Stale gradients will feed the similarity matrix. Channel feedback will set the costs.
The second part is analysis, with three results. The first is the per-round approximation ratio, which follows from the knapsack structure. The second bounds the additive coverage error from stale gradients in terms of model drift between rounds. The third is the redundancy scaling result above: the expected airtime to reach a coverage fraction, as a function of $m$, $\epsilon$, path-loss spread, and $B$, under Rayleigh fading. We will state that result for finite $n$ rather than as a limit.
The third part is integration into federated training. We will measure accuracy against cumulative airtime and energy, not against rounds. Measuring per round favors schemes that spend unbounded airtime.
Baselines
The naive reference is random selection of a fixed number of clients, each given the airtime its channel requires, with rounds truncated at budget $B$. Every scheme is measured against cumulative airtime under the same channel trace. Without that trace, no comparison is meaningful.
The channel-only opportunistic baseline is the digital scheme from Federated Learning Over Wireless Fading Channels. We extend it from one device to filling the budget with the best-channel devices. Its reported MNIST figure is that digital schemes "struggled to exceed 80%" with 25 devices, while analog aggregation reached "nearly 90%". We include analog over-the-air aggregation as a separate competitor. It gets the same transmit power cap and truncated channel inversion for deep-faded devices.
The strongest learning-side baseline is DivFL. It runs with the same stale gradients, the same similarity function, and its own client count tuned on a grid matching our tuning of $B$. We will also run Power-of-Choice, reported as up to 3x faster than random with 10% higher accuracy on FMNIST and CIFAR-10, and SUBTRUNC, reported at 83.72% test accuracy on non-IID MNIST. Neither of those figures was obtained under an airtime model, so we re-run both rather than quote them.
Beating these baselines means reaching DivFL's final accuracy with clearly less cumulative airtime on FEMNIST and CelebA, and matching or improving client-accuracy variance.
Two ablations isolate the key ingredient. The first is two-stage filtering: an SNR threshold followed by DivFL. The second is a "channel-weighted DivFL" that keeps the cardinality constraint but scales each candidate's gain by its rate. If either matches the knapsack formulation, the knapsack structure is not doing the work.
Why not just…?
Why not just threshold on SNR and then run DivFL? This is the cheapest version and it will often work when clusters are large. Its failure is predictable. Rare clients with persistently weak path loss rarely clear a fixed threshold, so they drop out of coverage entirely. Power-of-Choice analysis shows that pre-filtering of this kind introduces selection skew and a non-vanishing error floor. Our planted-rare-client experiment tests this directly. We will report every threshold value we try, because a well-tuned threshold may close much of the gap on balanced partitions.
Why not just multiply each client's diversity gain by its rate inside DivFL? This is the real threat, since cost-benefit greedy is close to such a heuristic. The difference lies in the constraint. A fixed client count cannot spend saved airtime on extra clusters in lucky rounds, and it loses the per-round guarantee. The second ablation settles the question. If it ties our method across redundancy levels, we will report that the guarantee costs nothing and gains nothing in practice.
Why not just use over-the-air analog aggregation? It wins in the 25-device MNIST setting reported in Federated Learning Over Wireless Fading Channels. It averages updates without selecting among them, and it is limited by the weakest device under a power cap. We expect it to lose when path loss varies widely and data is heavily non-IID, and to possibly win in small homogeneous cells. The path-loss-spread sweep will show where the crossover lies.
Proposed Experiments
The benchmarks are FEMNIST (500 clients), CelebA (515), and Shakespeare (109) from LEAF, plus Dirichlet-partitioned MNIST and CIFAR-10. Clients are dropped uniformly into a cell with log-distance path loss and block Rayleigh fading. Metrics are test accuracy against cumulative airtime and energy, airtime to reach a target accuracy, variance of per-client accuracy, and participation entropy.
The decisive check is the redundancy sweep. On synthetic federated data, we replicate each data partition $m$ times with small perturbation $\epsilon$. We then measure the airtime needed to reach 90% of the coverage of the channel-oblivious selection. The theory predicts a roughly $1/\log m$ decrease. If the curve stays flat, the core claim is false.
The second check plants rare clients at the cell edge. It asks whether our method covers them through occasional upward fades while thresholding drops them.
The third check is Shakespeare, where DivFL reports weak gains because its gradients are sparse. If similarity breaks down there, channel-aware coverage should collapse to channel-only scheduling, and we will report it as such.
References
- Diverse Client Selection for Federated Learning via Submodular Maximization
- Submodular Maximization Approaches for Equitable Client Selection in Federated Learning
- Decomposable Submodular Maximization in Federated Setting
- Federated Learning over Wireless Fading Channels
- Federated Learning over a Wireless Network: Distributed User Selection through Random Access
- Coordinated Multicasting with Opportunistic User Selection in Multicell Wireless Systems
- (n, K)-User Interference Channels: Degrees of Freedom
- On the Achievable DoF and User Scaling Law of Opportunistic Interference Alignment in 3-Transmitter MIMO Interference Channels
- Towards Understanding Biased Client Selection in Federated Learning
- LEAF: A Benchmark for Federated Settings