PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerating Federated Learning via Momentum Gradient Descent

Wei Liu, Li Chen, Yunfei Chen, Wenyi Zhang

arXiv:1910.03197v2cs.LGstat.ML

TL;DR

The paper addresses the limitation that federated learning typically uses gradient descent without preceding-iteration information. It introduces momentum federated learning, proves convergence properties, derives rate bounds, and reports accelerated convergence over FL under certain conditions, confirmed by MNIST simulations.

  • Problem

    Existing FL solutions generally use gradient descent without accounting for preceding iterations, although incorporating them can potentially improve convergence.

  • Method

    MFL introduces momentum gradient descent into the local update step of federated learning.

  • Results

    MFL is globally convergent, has a derived convergence-rate upper bound, and accelerates convergence relative to FL under certain conditions; MNIST simulations confirm faster convergence.

  • Takeaways & Limitations

    Momentum can improve federated-learning convergence by incorporating the last iteration into local updates, within the conditions established by the analysis.

Abstract

from arXiv · show

Federated learning (FL) provides a communication-efficient approach to solve machine learning problems concerning distributed data, without sending raw data to a central server. However, existing works on FL only utilize first-order gradient descent (GD) and do not consider the preceding iterations to gradient update which can potentially accelerate convergence. In this paper, we consider momentum term which relates to the last iteration. The proposed momentum federated learning (MFL) uses momentum gradient descent (MGD) in the local update step of FL system. We establish global convergence properties of MFL and derive an upper bound on MFL convergence rate. Comparing the upper bounds on MFL and FL convergence rate, we provide conditions in which MFL accelerates the convergence. For different machine learning models, the convergence performance of MFL is evaluated based on experiments with MNIST dataset. Simulation results comfirm that MFL is globally convergent and further reveal significant convergence improvement over FL.

I. INTRODUCTION

The paper proposes Momentum Federated Learning (MFL), which applies momentum gradient descent during local federated updates to address convergence limitations of standard FL. It develops convergence guarantees and evaluates MFL against FL using distributed-learning models and MNIST simulations.

  • Motivation: Federated learning distributes computation to edge nodes holding local data, reducing the need to transmit raw user data to a central server.The system uses edge nodes with local datasets and a central server for model-parameter aggregation.
  • Motivation: Existing FL solutions generally use one-step gradient descent, whose updates depend only on the current gradient and omit preceding iterations.Prior work on momentum gradient descent indicates that incorporating the last iteration can improve convergence over GD.
  • Evaluation: Under certain conditions, MFL accelerates convergence relative to FL, and MNIST simulations with different machine-learning models confirm faster convergence.The reported experiments evaluate convergence performance through loss-function curves and comparisons between FL and MFL.
  • MFL Design: MFL introduces a momentum term into the FL local update and uses momentum gradient descent to optimize the loss at edge nodes.The proposed design applies MGD during local iterations while retaining the federated setting.
  • Convergence Analysis: The paper proves global convergence for MFL on convex optimization problems and derives an upper bound on its convergence rate.It also compares the theoretical convergence performance of MFL and FL under specified conditions.

1) Local Update:

MFL replaces FL’s local GD updates with MGD, alternating local optimization and weighted global aggregation. Momentum can reduce oscillation and accelerate convergence, while communication intervals introduce delayed global updates.

  • A. Motivation: MGD combines the current gradient with a momentum component, allowing parameter updates to deviate toward the optimum and mitigate oscillation.The paper illustrates GD taking seven iterations to reach the optimum, compared with three for MGD.
  • A. Motivation: MFL targets resource-constrained edge networks by using faster local convergence to improve distributed-learning resource utilization.The paper motivates convergence acceleration because edge nodes commonly have limited resources.
  • Algorithm: The MFL procedure alternates local updates and global aggregation for T local iterations, with aggregation frequency τ = T/K.The algorithm returns the best model between the previous final model and the latest globally aggregated model.
  • 1) Local Update:: MFL applies momentum gradient descent to each node’s local loss function during local updates.The local momentum and model parameters are updated in parallel before aggregation.
  • 2) Global Aggregation:: At every aggregation interval, the server takes weighted averages of node model and momentum parameters and broadcasts them back.The aggregated parameters initialize the next local-update interval.

V. CONVERGENCE ANALYSIS

The convergence analysis establishes MFL’s behavior under convexity, smoothness, Lipschitz, and strong-convexity assumptions, while quantifying its gap from centralized MGD. Delayed aggregation creates a convergence-performance gap when τ > 1.

  • Convergence Analysis: The paper derives an upper bound on MFL’s convergence rate and analyzes its dependence on related parameters.The convergence properties are established after introducing definitions and assumptions for the analysis.
  • Assumptions: The analysis assumes each local loss is convex, ρ-Lipschitz, β-smooth, and µ-strongly convex.These conditions support the global convergence analysis and apply to models including SVM, linear regression, and logistic regression.
  • Preliminaries: MFL accounts for gradient divergence between global and node-specific gradients caused by differences in data distributions.The analysis defines node-wise bounds δ_i and their average δ.
  • Convergence Gap: MFL with τ > 1 performs worse than centralized MGD because global parameters are delayed until after multiple local updates.Centralized MGD updates globally every iteration, whereas MFL communicates only at aggregation intervals.

B. Gap between MFL and Centralized MGD in Interval [k]

MFL matches centralized MGD when aggregation occurs after every local update, but delayed aggregation creates a growing gap influenced by local gradient divergence. Under stated conditions, MFL globally converges linearly, with performance depending on aggregation frequency and data heterogeneity.

  • When τ = 1, MFL is theoretically equivalent to centralized MGD and has zero performance gap.
  • For τ > 1, delayed global updates cause the gap between MFL and centralized MGD to increase within aggregation intervals.The bound can increase exponentially with the local iteration position when τ > 1.
  • The MFL–centralized MGD gap grows with the average gradient divergence δ across nodes.Identical local datasets yield δ = 0 and eliminate the gap.
  • Under cos θ ≥ 0, 0 < ηβ < 1, 0 ≤ γ < 1, and α > 0, MFL is globally convergent with a derived upper bound.The bound is expressed as a function of total iterations T and aggregation frequency τ.
  • With τ = 1, the convergence bound approaches zero linearly; with τ > 1, aggregation delay and heterogeneity introduce a nonzero limiting term.The paper identifies a trade-off between communication frequency and convergence performance.

VI. COMPARISON BETWEEN FL AND MFL

The paper compares theoretical convergence bounds for MFL and FL under matched settings. For small learning rates and sufficiently short runs, momentum yields faster convergence when its parameter lies in the stated acceleration range.

  • The comparison uses matched datasets, models, initialization, aggregation frequency, learning rate, and other parameters for MFL and FL.
  • As γ → 0, MFL degenerates into FL and both methods have the same convergence-rate upper bound.
  • For η → 0 and T < T1, the MFL and FL bounds simplify to f1(T) ≈ 1/T ωα and f2(T) ≈ 1/T ηϕ, respectively.
  • Under η → 0, T < T1, and 0 < γ < 1, Proposition 3 establishes faster MFL convergence than FL.
  • When ωα > ηϕ, the simplified MFL bound is smaller than the FL bound.

VII. SIMULATION AND DISCUSSION

MNIST simulations evaluate MFL, FL, and centralized MGD across SVM, linear regression, and logistic regression. MFL converges faster than FL, while momentum strength and aggregation frequency materially affect performance.

  • A. Simulation Setup: The simulations use SVM, linear regression, and logistic regression in a federated framework evaluated on MNIST.The experiments compare MFL with FL and centralized MGD.
  • 1) Convergence:: Across all three models, MFL loss curves descend faster than FL, while centralized MGD converges fastest.
  • 1) Convergence:: When γ = 0, MFL overlaps FL; as γ increases from 0 to 0.9, both loss and accuracy convergence rates increase.
  • 1) Convergence:: For 0 < γ < 0.95, final loss decreases with γ, whereas γ > 0.95 worsens convergence and may prevent convergence.
  • 2) Effect of τ: With T = 1,000, MFL has lower final loss than FL for every τ; with T = 60,000, larger τ increasingly degrades MFL convergence, especially beyond τ > 100.
  • The conclusion reports linear global convergence under stated conditions and accelerated convergence over FL in both theory and MNIST experiments.

APPENDIX A MFL VS. CENTRALIZED MGD

Appendix A proves that setting the aggregation frequency to one makes MFL identical to centralized MGD. This follows because each node’s momentum and model parameters coincide with the centralized quantities.

  • For τ = 1, every node’s local momentum and model parameters equal the centralized MGD parameters.
  • With τ = 1, linearity of the gradient operator makes the aggregated local update equal to the centralized MGD update.

APPENDIX B PROOF OF PROPOSITION 1

The proof bounds the discrepancy between local iterates and aggregated or global iterates over each aggregation interval. It uses recursive inequalities, weighted summation, and induction to establish the result needed for Proposition 1.

  • Lemma 4 supplies formulas used to match the inequalities required in Lemma 5.
  • For each interval, the proof derives bounds on the differences between local iterates and interval reference iterates.The derivation applies triangle inequalities and recursive relations involving β, γ, and δ_i.
  • Weighted summation of the recursive inequalities yields an inductive bound on the local-reference gap.The induction establishes ∥e_wi(t)−w^[k](t)∥ ≤ f_i(t−(k−1)τ) throughout the interval.
  • The discrepancy is zero at the beginning of each aggregation interval under the stated definitions and aggregation rules.
  • The local-reference bound is then extended to a bound between the global iterate w(t) and the interval reference w^[k](t), completing the proof preparation for Proposition 1.This extension combines the previously derived bounds over the interval and uses the definitions of the global and aggregated iterates.

APPENDIX C PROOF OF INCREASING OF h(x)

This appendix proves that h(x) increases with x by establishing an auxiliary inequality for powers involving A, B, C, D, and γ. The proof handles integer cases and uses Jensen’s inequality for x > 1.

  • Lemma 6 establishes the inequality needed to prove that h(x) increases with x.
  • The proof verifies the auxiliary inequality separately for the initial integer cases x = 0 and x = 1.
  • For integer x > 1, Jensen’s inequality is used to establish the required bound.
  • The established inequality is equivalent to h(x) increasing with x, completing the appendix’s argument.

APPENDIX D PROOF OF LEMMA 2

The proof of Lemma 2 derives an upper bound for MFL’s convergence behavior under assumptions on smoothness, momentum, gradient direction, and interval-related error. It then uses MGD convergence and summation across intervals.

  • The proof introduces the angle between ∇F(w^[k](t)) and d^[k](t), together with a bound on the product of their norms.
  • Under the lemma’s conditions and Assumption 1, the sequence generated by MGD converges to the optimum point.
  • The proof bounds the change in c^[k](t) and combines convexity, Cauchy–Schwarz, and the convergence property of MGD.
  • The resulting inequalities are summed over local updates and aggregation intervals, with T = Kτ, to obtain the lemma’s final convergence bound.The argument also uses assumptions maintaining a lower bound ε on the objective gap at relevant interval endpoints.

APPENDIX E PROOF OF PROPOSITION 2

The proof of Proposition 2 specializes Lemma 2 to the case ρh(τ) = 0 and verifies its conditions using assumptions on γ, ηβ, ε, and the angle between update directions. It concludes with the stated objective-gap bound.

  • When ρh(τ) = 0, the assumptions 0 < ηβ < 1, 0 ≤ γ < 1, and cos θ ≥ 0 ensure the first condition of Lemma 2.
  • Because α > 0, the fourth condition of Lemma 2 is satisfied in this specialization.
  • Choosing an arbitrarily small ε allows the remaining conditions to be considered, leading to the proposition’s bound.
  • The final result bounds the objective gap at the selected final point by the objective gap at T.
  • The proof resolves the alternative cases by showing that either an interval endpoint or the final iterate has objective gap at most ε0.

APPENDIX F

Appendix F establishes that h(τ) vanishes as τ approaches zero and records limiting values for B and F, with the final equality justified using L’Hospital’s rule.

  • limτ→0 h(τ) = 0.
  • As τ approaches zero, B tends to 1 and F tends to γ (1−γ)2.
  • The final equality is justified by applying L’Hospital’s rule.
Loading 1910.03197v2…