Source-linked AI summary
Towards Flexible Device Participation in Federated Learning
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, Carlee Joe-Wong
TL;DR
Traditional federated learning can require devices to remain available throughout training, even though resource constraints and long runs make this difficult. This paper analyzes and adapts aggregation for flexible device participation, including incomplete updates, inactivity, arrivals, and departures. It reports that adaptive aggregation can preserve convergence to a global optimum, while fast-rebooting is beneficial when training time is insufficient.
Problem
Traditional convergence requirements assume selected devices can complete assigned rounds, although constrained devices may be unavailable during long training.
Source: §1 · p. 1Method
Results
Adaptive aggregation can control the convergence-bound increase under flexible participation and establish convergence to the global optimum.
Source: §1 · p. 2, §3.2 · p. 4Takeaways & Limitations
A mild degree of inactivity will not impact convergence, and fast-rebooting is beneficial when insufficient training time remains.
Source: §4.2 · p. 7, §6 · p. 9Fast-rebooting and non-rebooted models eventually converge to the same global optimum if there are no future interrupts.
Source: §4.2 · p. 7
Abstract
from arXiv · showhide
Traditional federated learning algorithms impose strict requirements on the participation rates of devices, which limit the potential reach of federated learning. This paper extends the current learning paradigm to include devices that may become inactive, compute incomplete updates, and depart or arrive in the middle of training. We derive analytical results to illustrate how allowing more flexible device participation can affect the learning convergence when data is not independently and identically distributed (non-IID). We then propose a new federated aggregation scheme that converges even when devices may be inactive or return incomplete updates. We also study how the learning process can adapt to early departures or late arrivals, and analyze their impacts on the convergence.
1 Introduction
Cross-device federated learning must cope with non-IID data and resource-constrained devices that may not remain available throughout training. The paper analyzes flexible participation and proposes methods for incomplete updates, inactivity, arrivals, and departures.
1 Introduction
- Traditional convergence guarantees can require selected devices to complete every assigned round, despite long training and constrained device resources making continuous availability difficult.This limits which devices and datasets can participate in federated learning.Source: §1 · pp. 1–2
- The paper considers four participation patterns: incomplete updates, inactivity, early departures, and late arrivals.Inactive devices are expected to return; departing devices inform the coordinator that they will not rejoin, and arrivals and departures require distinct treatments.Source: §1 · p. 2
- Adaptive aggregation coefficients can reduce bias from incomplete or inactive participation and establish convergence to a global optimum.The analysis attributes bias to both participation heterogeneity and non-IID local data.Source: §1 · p. 2
- For arrivals, the paper proposes extra updates from new devices to reboot training rapidly; for departures, it frames applicability around whether to retain or exclude the departing device’s data.The departure decision depends on which objective yields smaller training loss, with remaining training time identified as key.Source: §1 · p. 2
2 Related Works
Prior work addresses non-IID data, resource constraints, or incomplete updates, but generally does not analyze convergence across flexible participation patterns. This paper models participation as random and compares convergence rates for three aggregation schemes.
2 Related Works
- Existing non-IID FedAvg analyses simplify device heterogeneity or change the optimized objective, while multi-task approaches still require dedicated participation.FedAvg performance degrades with non-IID data across devices.Source: §2 · pp. 2–3
- Edge-computing modifications address communication overhead or resource budgets, but do not consider device unavailability or joining at different times.Asynchronous online-learning work does not analyze convergence effects of inactivity, incomplete updates, and data heterogeneity.Source: §2 · p. 3
- Prior work on device variation does not show its effect on convergence or incorporate user-data heterogeneity into algorithm design.Work on incomplete devices also omits other dynamic participation patterns and probabilistic participation models.Source: §2 · p. 3
- This paper models device participation as random variables and compares convergence rates for three aggregation schemes.Source: §2 · p. 3
3 Convergence Analysis
The analysis extends FedAvg to heterogeneous devices that may complete different numbers of local updates, including none, and allows aggregation coefficients to vary. It bounds convergence under flexible participation and examines how arrivals and departures change the global objective and the training trajectory.
3.1 Algorithm Description
- Each device may complete between zero and E local updates per round, with arbitrary update-count distributions and time-varying aggregation coefficients.Zero updates define inactivity; a positive count below E defines an incomplete round.Source: §3.1 · pp. 3–4, §3 · p. 3
3.2 General Convergence Bound
- Linear growth in Mτ, such as from departures, can leave FedAvg at a suboptimal point; controlling its growth through aggregation coefficients can preserve convergence to the global optimum.The bound links participation heterogeneity to Mτ and the non-IID data measure Γk to D.Source: §3.2 · p. 4
3.3 Shifts in the Global Objective
- An objective shift changes the global objective by adding or removing a device; the optimum offset shrinks when data are more IID or the device owns fewer data points.A new device must trigger a shift, while a departure may be excluded from the objective or retained if that gives smaller training loss.Source: §3.3 · p. 5
- After an objective shift, increasing the learning rate allows convergence toward the new objective to be bounded; the shift also causes a one-time loss increase.For arrivals, extra gradient updates from the new device can accelerate training through fast-reboot.Source: §3.3 · p. 5
4 Main Results
Section 4 turns the analysis into guidance for flexible participation, comparing incomplete-update schemes, extra updates for arrivals, and objective shifts after departures.
4.1 Debiasing on Incomplete Aggregation
- Scheme C is the only scheme that guarantees convergence with heterogeneous participation; Schemes A and B fail to reach the global optimum even when all devices are active.Scheme C works when inactive devices do not occur in every round.Source: §4.1 · p. 5, Table 1 · p. 6
- Scheme C enlarges incomplete gradients to offset the extra local epochs completed by other devices, yielding unbiased aggregation where Schemes A and B favor devices running more epochs.For E = 5, it scales updates from devices completing 3 and 4 epochs by 5/3 and 5/4, respectively.Source: Figure 1 · p. 6, §4.1 · p. 6
- More participating devices speed loss decay, but frequent inactivity slows Scheme C, and a device that never responds prevents its training loss from converging to zero.Non-IID heterogeneity is a major convergence obstacle; in heterogeneous settings, D grows with Γ and can dominate training loss.Source: §4.1 · p. 6
4.2 Fast-rebooting on Arrivals
- Extra updates from an arriving device are most likely to help when the model is near the old optimum; they may hurt when it is farther away.The benefit is temporary: without future interruptions, models with and without fast-reboot eventually reach the same global optimum.Source: §4.2 · pp. 6–7, Figure 2 · p. 6
4.3 Redefining Applicability on Departures
- After a departure, retaining the device in the objective leaves a structural bias D/E; shifting the objective raises the bound initially, then it declines toward the new optimum.Exclusion is preferable when the remaining training time is at least O(√(Γ_l τ0)).Source: §4.3 · p. 7
5 Experiments
Simulations using participation traces test aggregation under heterogeneous participation, fast-rebooting after arrivals, and model behavior after departures. Scheme C performs better as participation becomes more heterogeneous and data less IID; fast-reboot speeds recovery after arrivals, while excluding a departed device eventually becomes more beneficial.
5.1 Experiment Setup
- Experiments use computer simulations with real-world participation traces, three datasets, and models suited to MNIST, EMNIST, and SYNTHETIC.The traces come from Raspberry Pi workers under varied CPU workloads and bandwidth conditions; the first five traces contain no inactive cases.Source: §5 · p. 7, §5.1 · pp. 7–8, Table 2 · p. 8
5.2 Comparison of Aggregation Schemes
- Scheme C yields higher accuracy as device participation becomes more heterogeneous and data less IID, while Scheme A performs extremely badly with large |T|.Scheme C is no different from, or worse than, Scheme B in more homogeneous settings; with inactive devices (|T| ≥ 6), it becomes less stable.Source: Table 3 · p. 8, Figure 3 · p. 8, §5.2 · p. 8
5.3 Effectiveness of Fast-Reboot
- With multiple non-IID MNIST arrivals, fast-reboot accelerates convergence after every arrival, including arrivals before the model fully converges.The final three devices arrive at 50-epoch intervals after the initial seven have trained for 100 global epochs.Source: Figure 5 · p. 9, §5.3 · p. 9
- Fast-reboot consistently shortens recovery after an arrival and works better for later arrivals.EMNIST-CNN improves less because its models have not fully converged to the old optima when new devices arrive.Source: Table 4 · p. 9, §5.3 · p. 9, Figure 4 · p. 9
5.4 Model Applicability upon Departures
- After a device departs, excluding it initially increases test loss, but the include and exclude curves eventually cross and exclusion becomes more beneficial.The epochs until the crossover increase with later departure time τ0 and with the SYNTHETIC non-IID metric (α, β).Source: §5.4 · p. 9, Table 5 · p. 9
6 Conclusion and Future Work
The conclusion extends federated learning to flexible device participation, including incomplete updates, inactivity, arrivals, and departures. It summarizes convergence findings and techniques for arrivals and departures, while identifying groups of arrivals or departures and dynamic dataset updates as future work.
6 Conclusion and Future Work
- Scaling aggregation coefficients lets incomplete local updates be used, and mild device inactivity does not impact convergence.The analysis also relates convergence to heterogeneity in device participation and data.Source: §6 · p. 9
- The paper proposes fast-reboot techniques for new arrivals and an analytical criterion for excluding departing devices.Source: §6 · p. 9
- Future work will analyze groups of arrivals or departures and whether users can dynamically update their datasets during training.Source: §6 · p. 9
A.1.1 Equivalent View
The equivalent view uses virtual variables to represent local-epoch participation and extends the global weight to arbitrary time steps.
A.1.1 Equivalent View
- For each client and global round, the analysis introduces virtual variables that determine the distribution of local epochs.Source: §A.1.1 · p. 12
- The analysis assumes no particular distributions or correlations for the virtual variables, and its results hold for any realization of local epochs.Source: §A.1.1 · p. 12
- The equivalent view defines the global weight at arbitrary time t, rather than only at multiples of E.The global weight at t = 0 is w_G.Source: §A.1.1 · p. 12
A.1.2 Key Lemmas
The appendix introduces key lemmas and uses them in a covariance-based derivation for independently running clients.
A.1.2 Key Lemmas
- The appendix introduces key lemmas before presenting a covariance argument based on clients running independently.Source: §A.1.2 · pp. 12–13
- Lemma A.3 is stated for i = 0, …, E − 1 and all τ and k.Source: §A.1.2 · p. 13
- The derivation substitutes equation (25) into (23), then equations (26) and (27) into (22).Source: §A.1.2 · p. 14
A.1.3 Bounding ∥¯wτE+i+1 −w∗∥2
The derivation uses convexity and strong convexity to bound the update, under a specified restriction on the step size.
A.1.3 Bounding ∥¯wτE+i+1 −w∗∥2
- The derivation invokes convexity of the l2 norm to obtain a bound.Source: §A.1.3 · p. 15
- The objective functions Fk are assumed to be µ-strongly convex.Source: §A.1.3 · p. 15
- When ητ ≤ 1/[2(1+θ)L], the defined γτ satisfies ητ ≤ γτ ≤ 2ητ.Source: §A.1.3 · p. 16
A.1.4 Bounding ∥¯wτE −w∗∥
The appendix derives convergence bounds for stationary and time-varying participation distributions, then examines scheme-specific behavior and the effect of an additional update for an arriving device.
A.1.4 Bounding ∥¯wτE −w∗∥
- The A.1.4 proof defines expected squared distance to the optimum and seeks a lower bound for that distance.Source: §A.1.4 · p. 19
A.2 Proof of Theorem 3.1
- When the skτ distributions are stationary, the proof of Theorem 3.1 proceeds by induction with a specified ητ step size.Source: §A.2 · p. 20
A.2.1 Extension to Time-Varying Distributions
- With time-varying skτ distributions, convergence can still be established using slightly different definitions, with the expected-distance bound given in (66).Source: §A.2.1 · p. 21
A.4.1 Scheme A
- For heterogeneous participation, Scheme A does not converge to the global optimum and has remainder loss bounded by D/E; under homogeneous participation, zτ and Mτ are zero.Source: §A.4.1 · pp. 23–24
A.4.2 Scheme B
- Scheme B does not converge to the global optimum when E[sτ]/pk varies across devices, while homogeneous participation gives zτ = Mτ = 0.Source: §A.4.2 · p. 24
A.4.3 Scheme C
- In the heterogeneous-participation case for Scheme C, zτ = 0 only if Iτ = 1, and Mτ is defined cumulatively across prior rounds.Source: §A.4.3 · p. 25
A.5 Proof of Corollary 4.0.2
- For a device that arrives, an additional update helps fast-reboot when A(w, δl) < 0.Source: §A.5 · p. 25
A.6 Proof of Corollary 4.0.3
- For the decreasing f0 case, described as more commonly observed in experiments, the proof considers a root of f0(τ) = f1(τ).Source: §A.6 · p. 26