PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Federated Learning in the Presence of Arbitrary Device Unavailability

Xinran Gu, Kaixuan Huang, Jingzhao Zhang, Longbo Huang

arXiv:2106.04159v1cs.LGmath.OC

TL;DR

Arbitrary device unavailability makes federated learning difficult when inactive devices delay or bias model updates. The paper proposes MIFA, which proceeds without waiting and reuses memorized updates; it proves minimax optimal convergence rates for strongly convex and smooth non-convex functions.

  • Problem

    Device availability can be non-stationary or adversarial, while participation assumptions in existing approaches may not capture such patterns.

    Source: §1 · p. 2

  • Method

    MIFA avoids waiting for inactive devices and uses their memorized latest updates to correct gradient bias.

    Source: §1 · p. 2, §4 · p. 4

  • Results

    MIFA achieves minimax optimal convergence rates for strongly convex and smooth non-convex functions, and recovers best-known FedAvg rates when all devices are active.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis treats inactive rounds as a driver of federated convergence, including under arbitrary device availability patterns.

    Source: §1 · p. 2, §8 · p. 10

    For non-convex convergence, the analysis relies on stronger assumptions and leaves convergence under weaker assumptions for future work.

    Source: §6 · p. 8

Abstract

from arXiv · show

Federated Learning (FL) coordinates with numerous heterogeneous devices to collaboratively train a shared model while preserving user privacy. Despite its multiple advantages, FL faces new challenges. One challenge arises when devices drop out of the training process beyond the control of the central server. In this case, the convergence of popular FL algorithms such as FedAvg is severely influenced by the straggling devices. To tackle this challenge, we study federated learning algorithms under arbitrary device unavailability and propose an algorithm named Memory-augmented Impatient Federated Averaging (MIFA). Our algorithm efficiently avoids excessive latency induced by inactive devices, and corrects the gradient bias using the memorized latest updates from the devices. We prove that MIFA achieves minimax optimal convergence rates on non-i.i.d. data for both strongly convex and non-convex smooth functions. We also provide an explicit characterization of the improvement over baseline algorithms through a case study, and validate the results by numerical experiments on real-world datasets.

1 Introduction

Federated learning coordinates devices to train a shared model while keeping data local, but heterogeneous participation complicates optimization. The paper introduces MIFA for arbitrary device unavailability and reports optimal convergence guarantees.

1 Introduction

  • The paper models device objectives as stochastic functions that can differ across devices, following prior work on non-i.i.d. data.It frames device variation as an optimization challenge in federated learning.Source: §1 · p. 1
  • Prior delayed-response models assume devices ultimately make roughly the same number of responses, unlike devices with very different active durations.The paper highlights arbitrary device availability as a less-studied form of heterogeneity.Source: §1 · p. 2
  • Existing approaches either rely on known response probabilities or may wait a long time for a selected device subset to respond.MIFA's formulation does not require devices to be online according to a known or unknown distribution.Source: §1 · p. 2
  • MIFA avoids waiting for inactive devices and corrects gradient bias by incorporating their memorized latest updates into the received updates.The method is agnostic to availability patterns and uses stale, noisy gradients to exploit descent-direction information.Source: §1 · p. 2
  • MIFA achieves minimax optimal convergence rates for strongly convex and smooth non-convex functions, with matching lower bounds and optimal rates when all devices are active.The introduction also reports empirical validation on real-world datasets.Source: §1 · p. 2

2 Related work

The related work spans FedAvg variants for data heterogeneity, delay-aware optimization, and methods that handle missing device responses. The paper distinguishes MIFA through its treatment of arbitrary inactive patterns and non-i.i.d. worker data.

2 Related work

  • FedProx adds a proximal term, while FSVRG and SCAFFOLD use variance reduction to address data heterogeneity in FedAvg.FedAvg was first proposed in.Source: §2 · p. 2
  • Prior missing-response methods assume either known availability patterns or server-selected subsets, while this work permits adversarial inactivity under non-distributional assumptions and still proves convergence.The cited comparison notes that one prior method diverges when any device is inactive in every communication round.Source: §2 · pp. 2–3
  • Unlike shared-data asynchronous optimization, this work assumes workers hold non-i.i.d. data, so a local stochastic gradient is not an unbiased estimator of the global gradient.Shared-data methods assume workers can access the whole dataset.Source: §2 · p. 3
  • Related distributed-data methods differ in their assumptions: cited approaches use full local gradients, known stochastic delay distributions, bounded delays, or universally available workers.The paper characterizes its own formulation as distribution-free.Source: §2 · p. 3

3 Problem Setup

The setup treats federated optimization as minimizing a global objective built from device-specific stochastic losses. It distinguishes arbitrary device unavailability from settings where all devices respond, possibly with delays.

3 Problem Setup

  • The global objective is formed from device-specific losses, with w as the optimization variable, N devices, and ξ_i representing randomness in device i's local data distribution.Each device contributes a local loss function f_i.Source: §3 · p. 3
  • The participation model makes no distributional assumption on which devices are active in a round.A(t) denotes the set of devices that complete computation and return updates in round t.Source: §3 · p. 3
  • Unlike ideal or delayed setups, the paper allows arbitrary device inactivity while making each communication interval long enough for active devices to return updates.In the delayed setup all devices remain available and eventually return roughly equal numbers of responses; in the proposed setup devices can have unequal response counts.Source: §3 · p. 3, Figure 1 · p. 4
  • Three FedAvg variants address inactivity differently: direct averaging can be biased, subset sampling can wait on stragglers, and importance sampling requires i.i.d. participation with known probabilities.The subset-sampling approach may update the model fewer than T times over T communication rounds because it waits for all selected devices.Source: §3 · p. 4

4 Memory-augmented Impatient Federated Averaging (MIFA)

MIFA stores each device's latest update and proceeds without waiting for inactive devices, averaging stored and newly received updates. Its memory mechanism reuses stale, noisy gradients to address update bias.

4 Memory-augmented Impatient Federated Averaging (MIFA)

  • MIFA maintains an update array containing each device's latest update and averages the available stored updates to update the global model.Active devices perform K local SGD steps; the server replaces their stored updates with the newly received ones.Source: §4 · p. 4
  • MIFA avoids waiting for inactive devices and uses their latest stored updates as surrogates for missing responses.The method is described as progressing without waiting for unavailable devices.Source: §4 · p. 4
  • The method's memory augmentation corrects update bias by reusing inactive devices' noisy updates more than once, unlike traditional asynchronous methods.The authors state that these stale, noisy gradients contain information about the descent direction.Source: §4 · p. 5
  • A direct server implementation requires memory for every device's latest update, scaling with both model size and device count.The paper suggests distributing memory consumption among devices as one way to avoid exhausting server memory.Source: §4 · p. 5

5 Convergence Analysis for strongly convex objective functions

For strongly convex objectives, MIFA’s leading convergence term is minimax optimal under stated availability conditions, and its bound recovers the full-participation FedAvg rate when all devices are active. In an i.i.d. Bernoulli participation case study, MIFA is less sensitive to low-participation devices than FedAvg and SCAFFOLD.

5 Convergence Analysis for strongly convex objective functions

  • MIFA’s availability assumption allows inactive rounds to grow as O(t), but convergence requires τmax,T = o(T) and t0 = o(T).The assumption also requires τ(t, i) ≤ t0 + 1 + bt, with b = 40(L/µ)^1.5.Source: §5 · pp. 5–6
  • The leading convergence term is minimax optimal, while the O(1/T^2) term is negligible when the leading term dominates.The lower-bound result applies to stochastic strongly convex problems and is independent of the distributed or federated setup.Source: §5 · p. 6
  • With all devices active, the setup reduces to full-participation FedAvg and recovers the known rate up to logarithmic terms.In this case, the average and maximum inactive-round quantities are both zero.Source: §5 · p. 6
  • The analysis assumes every device responds in the first round so the server obtains a stochastic gradient evaluation for each device.The paper says this can be achieved by waiting for all devices’ updates on w1 at the beginning.Source: §5 · p. 6

5.1 Case Study: i.i.d. Bernoulli participation

  • Under i.i.d. Bernoulli participation, inactive-round counts grow logarithmically in t with high probability, and Assumption 4 holds for a mild choice of t0.Each device is active independently with a fixed probability in the case study.Source: §5.1 · p. 7
  • MIFA’s convergence rate depends on the average of 1/pi, whereas FedAvg and SCAFFOLD are more vulnerable to stragglers and their sampled-device rounds incur expected waiting of at least 1/pmin.The comparison concerns FedAvg and SCAFFOLD sampling S devices uniformly at random.Source: §5.1 · p. 7

6 Convergence result for non-convex objective functions

For non-convex objectives, MIFA’s guarantee is presented under assumptions controlling gradient behavior and device inactivity; its leading O(1/T) term is theoretically optimal for zero-respecting algorithms.

6 Convergence result for non-convex objective functions

  • The non-convex guarantee assumes Hessian-Lipschitz objectives, bounded gradient noise and dissimilarity, and uniformly bounded device inactivity.The theorem also assumes the stated smoothness and availability conditions.Source: §6 · p. 8
  • The leading O(1/T) term is theoretically optimal for zero-respecting algorithms.A lower bound is established for stochastic non-convex problems satisfying Assumptions 1, 2, 5, and 7.Source: §6 · p. 8
  • The tightness example requires the noise bound δ to scale with T; whether that requirement can be relaxed is left open.The passage states that this does not change the optimality of the first term, which is independent of δ.Source: §6 · p. 8

7 Numerical Experiments

Experiments on non-i.i.d. MNIST and CIFAR-10 compare MIFA with FedAvg variants under device availability patterns correlated with local data; MIFA avoids straggler waits and performs competitively with importance-sampled FedAvg.

7 Numerical Experiments

  • The comparison includes MIFA, FedAvg-IS, biased FedAvg, and device-sampled FedAvg, including MIFA’s initial wait to initialize its update array.The authors include those initial rounds for a fair comparison.Source: §7 · p. 9
  • Experiments use 100 devices, each holding samples from two classes, with logistic regression on MNIST and LeNet-5 on CIFAR-10.The datasets are constructed to be non-i.i.d., with equal sample counts per device and no data augmentation.Source: §7 · p. 9
  • Device availability is modeled by independent Bernoulli trials, with lower participation probabilities assigned to devices holding smaller-label data.The experiments use pmin values of 0.1 and 0.2 and control participation randomness across algorithm comparisons.Source: §7 · p. 9
  • Figure 2 reports training losses and test accuracies across logistic MNIST and LeNet-5 CIFAR-10 experiments, averaged over five random seeds with error bars.The passage reports that all five-seed runs exhibited similar training curves.Source: §7 · p. 9, Figure 2 · p. 9
  • MIFA avoids waiting for stragglers, converges fast without bias, and is competitive with FedAvg-IS, which requires participation probabilities.FedAvg with device sampling progresses relatively slowly; biased FedAvg has prominent optimality gaps on harder CIFAR-10 and at small pmin.Source: §7 · p. 9, Figure 2 · p. 9

8 Conclusions and Discussions

The paper concludes that MIFA avoids straggler waits by reusing memorized updates and establishes convergence guarantees for strongly convex and non-convex smooth functions. It also identifies open questions about the bounds and assumptions.

8 Conclusions and Discussions

  • MIFA avoids waiting for straggling devices by reusing their memorized latest updates as surrogates when they are unavailable.The analysis considers arbitrary, potentially non-stationary and adversarial participation patterns.Source: §8 · p. 10
  • The authors identify removing the τmax,T dependency and analyzing non-convex convergence under weaker assumptions as future directions.They characterize participation patterns as a bottleneck and emphasize how inactive-round counts affect convergence rates.Source: §8 · p. 10

A Baseline algorithms

  • The baseline-algorithm box summarizes three FedAvg variants, including importance sampling and device sampling that waits for all selected S devices to respond.The algorithm box also includes the biased FedAvg baseline.Source: A Baseline algorithms · p. 13

B Proof of convergence for smooth and strongly convex objective functions

This appendix establishes MIFA’s convergence for smooth, strongly convex objectives by verifying the needed induction condition and deriving convergence bounds through supporting lemmas and a telescoped descent argument under stated assumptions.

B Proof of convergence for smooth and strongly convex objective functions

  • Under Assumptions 1–4, the stated device-availability condition, and a specified learning rate, Theorem B.1 gives MIFA’s convergence bound after T−1 communication rounds.The theorem is presented as a more general version of Theorem 5.1; the supplied passages do not include the bound’s full formula.Source: B Proof of convergence for smooth and… · p. 13

B.2 Preliminary lemmas

  • The preliminary lemmas bound local gradients by distance to the global optimum, establish perturbed strong convexity, and bound local-update drift under a learning-rate condition.The drift condition is stated as ˜ηt ≤ 1/(10L).Source: §B.2 · pp. 14–15

B.3 The descent lemma for smooth and strongly convex problems

  • For learning rates ηt ≤ 1/(25KL), the MIFA updates satisfy a descent lemma when Assumptions 1–3 hold and all devices are initially available.Source: §B.3 · p. 16

B.3.1 Bounding the first term

  • The first-term analysis separates errors from local steps, inactivity, their interaction, and reused noisy updates; inactivity-related terms vanish when devices are available.The analysis also notes that some terms involving local updates vanish when K = 1.Source: §B.3.1 · pp. 19, 22

B.3.2 Bounding the second term

  • The second-term analysis combines with the first-term bounds to establish the descent lemma under its stated learning-rate condition.Source: §B.3.2 · p. 23

B.4.1 Bounding the distance from the global optimum

  • Lemma B.6 bounds the expected squared distance from the global optimum for each round, using induction and a learning rate determined by the smoothness, strong-convexity, and delay parameters.The appendix then connects bounds and learning rates across rounds, simplifies higher-degree and square-root terms, and verifies the two relations used in the induction.Source: §B.4.1 · p. 23, §B.4.4 · p. 27, §B.4.5 · p. 27

B.4.6 Verifying relation (a)

  • Substituting Bt and ˜ηt verifies relation (24), completing the induction step and proving Lemma B.6.The verification reduces to the displayed inequality involving E, F, G, and σ².Source: §B.4.6 · p. 28

B.5 Proof of Theorem B.1

  • Telescoping the descent bound and applying convexity yields Theorem B.1; since ¯dmax,T ≤ τ^2, Theorem 5.1 follows.The proof bounds E[f(wT)] − f(w*) using the bound for ΔT.Source: §B.5 · pp. 28–29

C Proof of convergence for smooth and non-convex objective functions

This appendix establishes MIFA convergence for smooth non-convex objectives under a relaxed inactivity assumption, then derives a bounded-inactivity corollary. Its proof builds preliminary bounds and a descent lemma before deriving the convergence rate.

C Proof of convergence for smooth and non-convex objective functions

C.6 Deriving the convergence rate

  • Theorem C.1 summarizes MIFA’s performance for smooth non-convex problems under Assumptions 1, 2, and 5–7 and the relaxed availability condition in Assumption 9.The theorem also specifies a learning-rate choice and a lower bound on T, but the supplied theorem statement does not expose its final bound.Source: C Proof of convergence for smooth and… · p. 30

C.1 Additional notation

  • The additional notation tracks accumulated gradients and inactivity measures, including the average squared number of inactive rounds across devices and rounds.The proof uses these quantities while telescoping the descent bound to derive the convergence rate.Source: §C.1 · p. 30, §C.6 · p. 36

C.2 Preliminary lemmas

  • The preliminary lemmas bound non-convex drift and parameter differences across rounds, supporting the later descent analysis.The parameter-difference bound applies when the round gap is at most l and the scaled learning rate satisfies a stated upper condition.Source: §C.2 · p. 31

C.3 The descent lemma for smooth and non-convex problems

  • The descent lemma is proved by bounding three terms, including a first term affected by reuse of noisy updates and gradients correlated with the current model.The proof invokes smoothness, Jensen’s inequality, and the preceding drift and parameter bounds.Source: §C.3 · p. 32, §C.3.1 · p. 33, §C.4 · p. 35

D Proofs in Section 5.1

  • Under i.i.d. Bernoulli participation, a device’s inactivity count τ(t, i) is a truncated geometric random variable taking values from 0 to t−1.The proof notes that all devices participate in the first round, so τ(t, i) cannot reach t.Source: D Proofs in Section 5.1 · p. 39

D.1 Proof of Theorem 5.2

The appendix bounds inactivity under Bernoulli participation and discusses the waiting time incurred when algorithms wait for selected devices. It also characterizes the inactivity count’s distribution and concentration properties.

D.1 Proof of Theorem 5.2

  • With probability at least 1−δt, τ(t, i) is bounded by 1 plus a logarithmic term involving δt and the device’s participation probability pi.The bound follows by treating inactivity as a truncated geometric variable and choosing a tail threshold.Source: §D.1 · p. 40

D.2 Proof of Theorem 5.3

  • The average inactivity measure τ̄T is bounded in expectation, and its centered version is sub-exponential with scale proportional to 1/pi.The proof applies Bernstein’s inequality to obtain a high-probability bound.Source: §D.2 · p. 40

D.3 Additional Discussion on the Expected Waiting Time

  • For a randomly selected subset S, the expected wait until every selected device is active is at least 1/min_{i∈S} pi.The argument uses the expected activation time 1/pi for an individual device under i.i.d. Bernoulli participation.Source: §D.3 · p. 41

E Proof of Proposition 5.1

This proof constructs a strongly convex, smooth stochastic-optimization instance and reduces accurate optimization to distinguishing Bernoulli distributions. It uses that reduction to establish a lower-bound argument, with a related proof for Proposition 6.1.

E Proof of Proposition 5.1

  • When each device responds every 2τ communication rounds, only Θ(NKT/τ̄T) stochastic gradients are evaluated over T rounds.The proof uses this evaluation count to connect a lower bound in gradient queries to the setting with inactive devices.Source: E Proof of Proposition 5.1 · p. 41
  • Theorem E.1 sets up a lower bound for any algorithm using k stochastic-gradient queries on a one-dimensional function class that is 1-smooth and μ-strongly convex.The construction assumes unbiased stochastic gradients with variance at most σ²; the supplied theorem statement omits the bound itself.Source: E Proof of Proposition 5.1 · p. 41
  • The proof uses Yao’s minimax principle to reduce randomized algorithms to deterministic ones, then maps optimization outputs to a procedure distinguishing two Bernoulli distributions.The constructed problem and noise distributions depend on a target accuracy parameter ϵ.Source: E Proof of Proposition 5.1 · pp. 41–42
  • If optimization error is small, Lemma E.1 yields a procedure that distinguishes Bernoulli distributions with parameters p0 and p1 using k samples.Lemma E.2 bounds the distinguishing procedure, and the proof combines the lemmas to obtain its lower-bound conclusion.Source: E Proof of Proposition 5.1 · pp. 42–44

F Proof of Proposition 6.1

Loading 2106.04159v1…