PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Local Descent Methods in Federated Learning

Farzin Haddadpour, Mehrdad Mahdavi

arXiv:1910.14425v2cs.LGcs.DCstat.ML

TL;DR

Federated learning needs communication-efficient optimization despite heterogeneous device data, partial participation, and privacy constraints. The paper analyzes periodic-averaging local GD/SGD for nonconvex federated objectives and shows that, with tuning based on gradient diversity, implicit variance reduction and sharp convergence rates extend beyond homogeneous data. The analysis also covers networked distributed optimization, but its guarantees depend on bounded gradient diversity and corresponding hyperparameter choices.

  • Problem

    The convergence and communication complexity of local SGD in heterogeneous federated learning lacked sufficient theoretical understanding despite empirical evidence of its applicability.

  • Method

    The paper analyzes local full and stochastic gradient descent with periodic averaging, extending the method to centralized and networked federated optimization under gradient-diversity-based tuning.

  • Results

    The analysis establishes best-known convergence rates for general nonconvex and PL-condition objectives, while showing implicit variance reduction in heterogeneous data.

  • Takeaways & Limitations

    Periodic-averaging local GD/SGD can have theoretically justified convergence in heterogeneous federated learning when learning rates, local updates, and participation are properly chosen.

  • Takeaways & Limitations

    The guarantees require bounded gradient diversity, and highly non-i.i.d. data can make learning-rate tuning difficult and may lead to convergence failure if the bound is violated.

Abstract

from arXiv · show

In federated distributed learning, the goal is to optimize a global training objective defined over distributed devices, where the data shard at each device is sampled from a possibly different distribution (a.k.a., heterogeneous or non i.i.d. data samples). In this paper, we generalize the local stochastic and full gradient descent with periodic averaging-- originally designed for homogeneous distributed optimization, to solve nonconvex optimization problems in federated learning. Although scant research is available on the effectiveness of local SGD in reducing the number of communication rounds in homogeneous setting, its convergence and communication complexity in heterogeneous setting is mostly demonstrated empirically and lacks through theoretical understating. To bridge this gap, we demonstrate that by properly analyzing the effect of unbiased gradients and sampling schema in federated setting, under mild assumptions, the implicit variance reduction feature of local distributed methods generalize to heterogeneous data shards and exhibits the best known convergence rates of homogeneous setting both in general nonconvex and under {\pl}~ condition (generalization of strong-convexity). Our theoretical results complement the recent empirical studies that demonstrate the applicability of local GD/SGD to federated learning. We also specialize the proposed local method for networked distributed optimization. To the best of our knowledge, the obtained convergence rates are the sharpest known to date on the convergence of local decant methods with periodic averaging for solving nonconvex federated optimization in both centralized and networked distributed optimization.

1 Introduction

Federated learning must optimize across heterogeneous devices while limiting costly communication and device participation. This paper theoretically analyzes periodic-averaging local GD/SGD and establishes convergence results under controlled gradient diversity.

  • 1 Introduction: Federated learning seeks a global model from distributed devices with different data distributions, while communication, privacy, and partial participation complicate optimization.The objective aggregates empirical risks across device shards or uses an agnostic minimax formulation.
  • 1 Introduction: Local GD/SGD performs device-local updates using local data, then periodically averages models to reduce communication rounds.The paper investigates this approach in both centralized and decentralized federated settings.
  • 1 Introduction: Heterogeneous shards make local gradients biased relative to the global objective, while periodic averaging introduces residual error requiring careful control.The analysis quantifies local-objective drift through gradient diversity.
  • 1.1 Contributions: The paper shows that implicit variance reduction extends to heterogeneous data when learning rates, local updates, and selected devices are chosen using gradient diversity.The result addresses both general nonconvex objectives and nonconvex objectives satisfying the PL condition.
  • 1.1 Contributions: For PL objectives, local GD avoids the residual error associated with prior bounds and matches distributed GD convergence, including the E = 1 case.The stated analysis also covers local SGD under heterogeneous distributions and removes a bounded-gradient assumption in the cited comparison.
  • 1.1 Contributions: In networked optimization, periodically communicating local SGD devices achieve an O(1/p^1.5) convergence rate under the paper’s stated analysis.The devices communicate with direct neighbors rather than relying solely on a central parameter server.

2 Additional Related Research

The related work covers periodic local GD/SGD, federated optimization, and decentralized communication schemes. The paper positions its contribution as theoretical convergence analysis for heterogeneous, nonconvex federated settings without requiring explicit variance reduction.

  • Local SGD with Periodic Averaging: Prior local-SGD studies analyze periodic averaging mainly under i.i.d. data, while selected work examines non-i.i.d. trade-offs, momentum, or explicit variance reduction.The paper claims comparable performance without applying an explicit variance-reduction technique and adds local-GD analysis for heterogeneous data.
  • Federated Optimization: The proposed work analyzes local SGD with periodic averaging for heterogeneous data under weaker assumptions than concurrent work, including removal of a bounded-gradient assumption.It also reports improved dependence on the number of local updates in the cited comparison.
  • Federated Optimization: Federated-optimization research has shown empirical effectiveness, but theoretical understanding for general nonconvex objectives with non-i.i.d. data remains limited.Earlier analyses include strongly convex objectives or dissimilarity assumptions.
  • Related decentralized methods: Decentralized local SGD can alternate multiple local updates with multiple neighbor communications, whereas the paper extends its local federated method to networked optimization.The algorithmic context includes random device selection and periodic server broadcasts.
  • Local Federated Descent: The paper’s LFD algorithm takes an initial shared model, a local-update count, and sampled devices with probabilities q, then periodically aggregates and broadcasts models.The algorithm is presented as a modified version of local SGD specialized to full and stochastic gradients.

3 Local Federated Optimization

This section introduces Local Federated Descent with periodic averaging for heterogeneous federated optimization and analyzes its convergence in centralized and networked settings. The guarantees depend on tuning local updates, sampled devices, and learning rates according to gradient diversity.

  • Convergence guarantees: Bounded gradient diversity enables convergence guarantees for local GD and SGD on general nonconvex objectives and objectives satisfying the PL condition.The paper states informal convergence theorems for LFGD and LFSGD under standard assumptions and suitable choices of learning rate and local updates.
  • Algorithm: LFD periodically averages local models and exposes three controls: local updates E, sampled devices K, and machine weights q.The method specializes local SGD to federated sampling and can be extended to direct-neighbor network communication.
  • Challenges and assumptions: Heterogeneous data make local gradients biased relative to the global gradient, requiring careful tuning for convergence.The analysis quantifies local-objective drift through gradient diversity and removes the need for an additional bounded-gradient assumption.
  • Dependence on heterogeneity: The permitted learning rate or number of local updates becomes more restrictive as gradient diversity increases.When local gradients align, diversity is small and larger learning rates or more local updates can be used; highly divergent gradients can make tuning difficult.
  • Rates and extensions: The centralized LFSGD bound matches a known sharp local-SGD rate when all devices participate, while networked analysis incorporates heterogeneous data distributions.The results also allow larger local-update periods and establish convergence results for networked federated optimization.

4 Convergence Analysis

The paper analyzes local GD and SGD with periodic averaging for heterogeneous federated learning, deriving convergence guarantees under bounded gradient diversity and suitable parameter choices. The results cover general nonconvex, PL-condition, and networked settings, with rates matching known homogeneous counterparts in key cases.

  • Technical approach: The analysis models local federated descent as perturbed SGD, where heterogeneity biases averaged local gradients and periodic averaging creates residual error.The proof controls both gradient bias and deviations between local iterates and a virtual averaged solution.
  • Local GD: The convergence proofs require learning rates and local-update counts chosen using an upper bound on weighted gradient diversity.The same diversity parameter also appears in the theorem conditions and resulting bounds.
  • Local GD: With proper E, local GD has an asymptotic convergence rate similar to distributed GD and independent of the number of devices.This independence is attributed to devices being agnostic to the sampling schema.
  • PL-condition SGD: For stochastic local SGD under the PL condition, the paper derives convergence bounds under learning-rate conditions involving gradient diversity, device count, and local updates.The theorem assumes common initialization and bounds the average-squared gradient after the stated iterations.
  • SGD and networked extension: The heterogeneous-data local SGD rate matches the best-known homogeneous rate, while vanilla local SGD exhibits implicit variance reduction comparable to explicit variance reduction.The networked local SGD analysis likewise reports a rate matching the best-known homogeneous counterpart.

5 Conclusion and Future Directions

The conclusion presents local full and stochastic descent with periodic averaging as theoretically convergent for heterogeneous federated learning under gradient-diversity-based tuning. It identifies open questions involving adaptive synchronization, communication complexity, mini-batch schedules, variance reduction, agnostic settings, and gradient diversity.

  • Conclusion: The paper establishes best-known convergence rates for local GD and SGD in heterogeneous federated learning under general nonconvex and PL-condition objectives.The analysis addresses biased stochastic gradients and residual errors from local updates.
  • Conclusion: The proposed analysis extends to networked distributed optimization and relies on tuning learning rates and local updates using gradient diversity.The algorithm also includes sampled-device parameters and device weights in its federated formulation.
  • Future directions: Future work includes adaptive synchronization, dynamic mini-batch sizes, tighter variance-reduced SGD analysis, agnostic settings, and mechanisms for reducing local-gradient diversity.The paper also identifies rigorous communication-complexity benefits of local updates as unresolved.
  • Future directions: The authors state that rigorous understanding of local updates’ communication-complexity advantage remains open in both homogeneous and heterogeneous settings.This is framed as a future research direction rather than an established result.

A Proof of Theorem 4.1

The proof of Theorem 4.1 combines bounds on sampled-device gradients, local-solution deviation, and a recursion controlled by learning-rate and local-update choices. These steps yield the stated local federated GD convergence bound.

  • Sampling: The convergence argument uses full local gradients, so its expectation is only over random selection of K devices with probabilities q1, q2, ..., qp.No mini-batch sampling is present in the local GD proof.
  • Gradient bounds: The proof bounds the averaged gradient over sampled devices relative to full gradients on individual local data shards.This addresses the sampling component of the local federated GD analysis.
  • Local drift: A separate lemma bounds the deviation between each local solution and the virtual averaged solution over a communication period.The deviation depends only on iterations since the most recent communication round because local GD restarts after averaging.
  • Recursion: The proof chooses the learning rate and local-update count so coefficients of local-deviation terms can be eliminated from the recursive bound.The resulting condition is then summed over iterations to obtain the theorem’s convergence rate.

B Proof of Theorem 4.2

The proof of Theorem 4.2 develops lemmas for stochastic-gradient interactions, sampled-device effects, and local-solution drift under the PL condition. Appropriate learning-rate schedules and local-update conditions reduce the resulting recursion to the stated convergence bound.

  • Sampling and drift: Additional lemmas bound sampling effects and the average distance of local solutions from their virtual average.These bounds are combined with the stochastic-gradient lemmas in the main recursion.
  • Stochastic-gradient control: The proof bounds the expected inner product between stochastic and full-batch gradients using smoothness and the PL property.This supplies a central descent term for the stochastic local SGD recursion.
  • Rate derivation: A decreasing learning-rate schedule η_t = 4/[µ(t+a)] is used after imposing a sufficient condition on the number of local updates E.The conditions ensure the recursive inequality can be iterated over the analysis period.

C Proof of Theorem 4.4

This section derives the convergence rate of LFSGD for general nonconvex objectives under the stated assumptions. The proof combines expectation over randomly selected devices with auxiliary lemmas and iteration averaging.

  • The LFSGD rate is derived for general nonconvex objectives using Assumption 1 and expectation over random device selection.The proof uses the auxiliary quantity ˜g(t) from Eq. (33).
  • Lemma C.1 supplies a bound under Assumptions 3 for controlling a term in the main inequality.It is introduced as a specialization of Lemma B.5 over the entire iteration range.
  • The proof applies Lemmas B.2 and C.1 to upper-bound the main inequality before rearranging and averaging it over all iterations.The averaging covers iterations t = 1, 2, . . . , T.

C.1 Proof of (Informal) Theorem 3.3

This section verifies that the choices made in the convergence argument satisfy the required conditions. It derives a condition on E + 1 and establishes that the conditions can hold simultaneously.

  • The proof first chooses E using the bound involving T and then checks that this choice does not violate the learning-rate condition.The argument explicitly links the choice of E to the condition in Eq. (70).
  • A further condition on E + 1 is derived to complete the compatibility check.The proof simplifies the relevant condition before concluding feasibility.
  • Both conditions can be satisfied simultaneously.

D Proof of Theorem 4.7

This section proves the networked distributed result using shorthand notation, adaptive auxiliary variables, smoothness, and bounds involving the mixing matrix. The proof derives the claimed bound under the stated assumptions.

  • D Proof of Theorem 4.7: A distinguishing feature of the proof is defining auxiliary variables ¯w(t) and ˜g(t) adaptively to the data samples at each device.This differentiates the proof from the approach in [33].
  • D Proof of Theorem 4.7: The network update is rewritten using matrix relations and W1p×1 = 1p×1, leading to Eq. (75).The derivation multiplies the reformulated update by 1p×1 and uses Assumption 4.
  • D Proof of Theorem 4.7: L-smoothness yields an inequality that is then averaged in expectation and summed over all iterations.This supplies the descent component of the proof.
  • D Proof of Theorem 4.7: Lemmas D.1 and D.2 provide bounds under Assumptions 3 and under Assumptions 1, 3, and 4, respectively.Lemma D.2 uses the second-largest eigenvalue ζ of the mixing matrix W and extends a result from [33].
  • D Proof of Theorem 4.7: The proof applies these bounds to upper-bound the target expression and derives the claimed result under an additional condition.The remainder is stated to be similar to the proof of Theorem 4.4.

D.1 Derivation of Conditions in Theorem 3.4

This section reduces the condition in Eq. (83) using the approach from [33].

  • D.1 Derivation of Conditions in Theorem 3.4: The condition in Eq. (83) is reduced by adopting the approach associated with Eq. (145) in [33].

E Proof of Omitted Lemmas

This section proves omitted lemmas by analyzing sampled-device gradients, local-model deviations, variance reduction, and learning-rate conditions under the paper’s assumptions.

  • Consequences: The resulting analysis supports linear speedup and convergence bounds based on summing inequalities over communication periods.The section also uses the upper bound on weighted gradient diversity when concluding the final inequalities.
  • Sampling and gradient bounds: The proofs use uniform-with-replacement device sampling and weighted gradient diversity to bound averaged gradients and local-model quantities.The sampling set may contain repeated devices, and the diversity parameter is bounded by λ.
  • Learning-rate conditions: Learning-rate conditions recursively eliminate coefficients of deviation terms and establish the required bounds by induction across local iterations.The analysis introduces Δ = 1 − μη and B ≜ 2ληL^2E, then chooses the learning rate so the relevant coefficients become nonpositive.
  • Variance and local deviations: Local-model deviation bounds relate stochastic-gradient variance to unbiased estimation, independent i.i.d. mini-batch sampling, and Assumption 3.The argument proceeds by first relating deviation to variance, then applying unbiasedness and sampling independence, and finally bounding the remaining terms.

E.12 Proof of Lemma C.1

This lemma bounds the distance between the averaged virtual model and local models by decomposing it into variance, unbiased-sampling, and Assumption 3 components.

  • Virtual-model representation: The proof represents local solutions after a communication time as updates from the shared model and computes the corresponding average virtual model.Time is decomposed into communication rounds and local-update indices.
  • Deviation bound: For intermediate local iterations, the averaged-model deviation is bounded in three steps: variance comparison, unbiased i.i.d. sampling, and Assumption 3.The same decomposition is stated explicitly for tc + 1 ≤ t ≤ tc + E.
  • Worker averaging: Expectation over randomly selected workers and summation across communication periods complete the bound using Fact E.1 and weighted gradient diversity.The final aggregation invokes the bound Λ(w, q) ≤ λ.
Loading 1910.14425v2…