PaperlayerView exact revision on arXiv

Source-linked AI summary

FedCM: Federated Learning with Client-level Momentum

Jing Xu, Sen Wang, Liwei Wang, Andrew Chi-Chih Yao

arXiv:2106.10874v1cs.LG

TL;DR

Federated learning must handle limited participation and heterogeneous client data without centralizing private data. The paper proposes FedCM, which uses past global gradient information to modify client updates, and reports matching convergence bounds, stronger empirical performance, and robustness across federated scenarios. The paper also notes communication and analysis trade-offs that bound the method’s scope.

  • Problem

    Federated optimization faces limited client participation and client heterogeneity, which can cause client drift, slower or unstable convergence, and difficulty maintaining client states.

  • Method

    FedCM maintains a server momentum term aggregating global gradient information from previous rounds and uses it to modify client gradient descent without requiring client-side state.

  • Results

    FedCM matches the best known convergence rates for distributed gradient algorithms and is reported to outperform existing algorithms while remaining robust to client heterogeneity and low participation.

  • Takeaways & Limitations

    FedCM provides an approach for using past gradients to adjust client descent directions under partial participation and heterogeneous federated learning conditions.

  • Takeaways & Limitations

    FedCM increases server-to-client communication by transmitting the momentum term, and its convergence analysis uses an auxiliary weighted average when the learning rate is constant.

Abstract

from arXiv · show

Federated Learning is a distributed machine learning approach which enables model training without data sharing. In this paper, we propose a new federated learning algorithm, Federated Averaging with Client-level Momentum (FedCM), to tackle problems of partial participation and client heterogeneity in real-world federated learning applications. FedCM aggregates global gradient information in previous communication rounds and modifies client gradient descent with a momentum-like term, which can effectively correct the bias and improve the stability of local SGD. We provide theoretical analysis to highlight the benefits of FedCM. We also perform extensive empirical studies and demonstrate that FedCM achieves superior performance in various tasks and is robust to different levels of client numbers, participation rate and client heterogeneity.

1 Introduction

Federated learning must operate under limited participation and heterogeneous client data, which can make local updates drift and convergence slower or unstable. FedCM addresses these challenges by using server-maintained momentum to incorporate past global gradient information into client updates.

  • Challenges: Limited and unreliable communication means only a small portion of cross-device clients can participate in each round, complicating state maintenance.The setting may involve millions of devices, while slow or expensive communication limits participation.
  • Challenges: Heterogeneous client data can induce client drift, causing slower and unstable convergence; server-only adaptation does not modify local update directions.Client distributions reflect individual device usage and may differ substantially from the population distribution.
  • FedCM: FedCM aggregates global gradient information from previous rounds in a momentum term that modifies client gradient steps.The method integrates momentum into the client and server gradient steps of FedAvg rather than directly applying traditional momentum to only client or server updates.
  • FedCM: FedCM requires no client-side state between rounds and combines each local gradient with global momentum containing information from other clients.These design choices target low participation and reduce the influence of client heterogeneity.
  • Contributions: FedCM is reported to match the best known convergence communication bounds and consistently outperform strong baselines across varied client numbers, participation rates, and heterogeneity.Experiments use CIFAR10 and CIFAR100 under multiple federated scenarios.

2 Related works

Related work situates federated learning within broader optimization research and emphasizes client heterogeneity as a central challenge. Existing approaches address this challenge through regularization, variance reduction, primal-dual methods, or personalization, but may require costly participation, communication, or storage.

  • Client heterogeneity: Federated learning research addresses non-iidness, also called client heterogeneity, including differences in client data distributions and system capabilities.This work focuses mainly on statistical heterogeneity, where client data distributions differ.
  • Client heterogeneity: Client heterogeneity has been linked to significant FedAvg degradation on non-iid data, motivating personalization and other mitigation strategies.Personalization methods can be combined with the paper’s approach.
  • Federated optimization: The optimization literature includes FedAvg and later methods using proximal regularization, variance reduction, and primal-dual approaches to adapt distributed optimization to federated settings.FedAvg reduces communication by performing multiple local gradient updates per communication round.
  • Federated optimization: Many existing methods for client heterogeneity require full participation, additional communication, or client storage, which can be problematic in federated learning.These requirements are especially relevant to federated settings with constrained participation and communication.

3 Preliminaries

The preliminaries model federated learning as minimizing average client loss with private, potentially heterogeneous datasets and server-client communication. FedAvg samples clients, performs local stochastic updates, and averages their resulting models to produce the next global model.

  • Problem formulation: Each of N clients holds private data drawn from its own distribution D_i, which may differ across clients and represent client heterogeneity.The client loss f_i is defined as the expected loss under D_i.
  • Problem formulation: The federated learning objective is to minimize the average loss across all clients.The formulation uses client losses aggregated over the participating population.
  • FedAvg: In FedAvg, the server broadcasts the current model to a sampled subset of clients, which perform K local stochastic gradient steps using private data.The resulting client models are sent back to the server.
  • FedAvg: The server averages received client parameters to obtain the next global model, with a server learning rate applied to the gradient average.The original FedAvg formulation corresponds to η_g = Kη_l in the paper’s notation.
  • FedAvg: FedAvg repeats communication rounds by sampling a client subset and running local updates in parallel.The pseudocode initializes model and learning-rate parameters before iterating over communication rounds.

4 Algorithm

FedCM modifies FedAvg by using a server-maintained momentum term to guide client updates, incorporating historical global gradient information without requiring client-side state. This design addresses client heterogeneity and limited participation while adding only server-to-client communication.

  • FedCM algorithm: FedCM uses the previous round’s server descent direction together with current client gradients to update local models.The server updates the momentum term by averaging participating clients’ parameter changes.
  • Momentum mechanism: The momentum term is an exponential moving average of past client gradients, retaining information from clients inactive in the current round.This historical information makes the method robust to partial participation.
  • Heterogeneity correction: FedCM adds a correction to local gradient directions that asymptotically aligns with the difference between global and local gradients.The correction is intended to reduce client heterogeneity and improve performance.
  • Client-state requirements: Clients do not maintain local states, allowing new clients to join without warmup and reducing storage burdens on mobile devices.This history-free design also avoids stale client states under low participation.
  • Communication: FedCM increases only server-to-client communication, while client-to-server communication remains unchanged.The design is presented as compatible with asymmetric networks whose uplink is typically slower than downlink.

5 Convergence analysis

The convergence analysis establishes FedCM under standard smoothness, convexity, bounded-gradient, variance, and heterogeneity assumptions. Its communication-round rates match the best known distributed SGD results, while the bound remains stable as participation becomes sparse.

  • Assumptions: The analysis assumes smooth local losses, convexity, bounded global gradients, unbiased stochastic gradients with bounded variance, and bounded client heterogeneity.These assumptions cover optimization regularity, stochastic noise, and the difference between local and global gradients.
  • Convergence guarantees: Theorem 5.1 derives convergence results for strongly convex, general convex, and non-convex objectives under uniform client sampling and suitable learning rates.The theorem analyzes an auxiliary sequence z_t in the stated results.
  • Rates: FedCM’s communication-round bounds match the best known results for distributed SGD algorithms across strongly convex, general convex, and non-convex settings.The paper reports these bounds for achieving precision ϵ.
  • Partial participation: Unlike SCAFFOLD and FedDyn, FedCM’s convergence bound is free of the participation-ratio term N/S.Consequently, the bound avoids the divergence issue described for vanishing participation rates.
  • Momentum parameter: A smaller α uses more global gradient information and alleviates client heterogeneity, although an extremely small α can slow convergence.The dominant term in the bounds is α-free, so small α does not ruin the theorem’s asymptotic results.
  • Interpretation of the bound: The theorem analyzes a weighted average of intermediate results and an auxiliary z_t rather than only the final model x_t.The paper notes that decaying learning rates can avoid the weighted-average issue.

6 Experiments

Experiments on CIFAR10 and CIFAR100 compare FedCM with four baselines across participation and heterogeneity settings. FedCM consistently achieves higher accuracy and remains robust as participation and heterogeneity vary, while its α sensitivity is also evaluated.

  • Experimental setup: FedCM is compared with FedAvg, SCAFFOLD, FedDyn, and FedAdam on CIFAR10 and CIFAR100 under 100-client/10% and 500-client/2% participation settings.The evaluation targets federated scenarios with different participation rates and client counts.
  • Overall results: FedCM consistently outperforms the competing baselines in test accuracy across the evaluated tasks and settings.It also exceeds FedAdam despite not using an adaptive learning rate.
  • Participation robustness: FedCM’s CIFAR10 accuracy drops only 1.07% for IID and 1.37% for Dirichlet-0.6 when participation decreases, versus approximately 8% for FedAvg and 6% for SCAFFOLD.The experiment fixes the expected number of active clients at 10 to isolate participation-rate effects.
  • Heterogeneity robustness: FedCM achieves the highest accuracy under different heterogeneity levels, with a CIFAR10 accuracy drop of 0.31% versus 0.77% for FedAdam and 0.66% for FedAvg.The comparison uses 100 clients with 10% participation.
  • Sensitivity analysis: FedCM converges to stationary points for all tested α values, but different α choices produce different generalization performance.The sensitivity study tests α ∈ {0.01, 0.03, 0.05, 0.1, 0.3, 1.0}; performance is reported as best near α = 0.1.

7 Conclusion

The paper proposes FedCM, which modifies local gradient updates using a momentum term that aggregates global gradient information. Its analysis and experiments support robustness to client heterogeneity and low participation, while future work considers higher-order past-gradient information.

  • Contribution: FedCM modifies local gradient updates with a momentum term that aggregates global gradient information.The conclusion describes the algorithm as efficient and robust.
  • Theory and evaluation: FedCM’s convergence rates match the best known results for distributed gradient algorithms.The conclusion also reports extensive experiments against existing federated learning algorithms.
  • Supported scope: The theoretical and empirical evaluations highlight robustness to client heterogeneity and low participation in federated learning tasks.The paper frames these as the principal challenges addressed by FedCM.
  • Future direction: Future work includes using higher-order information from past gradients to extend adaptive optimization into client and server updates of Federated Averaging.This is identified as a direction rather than a demonstrated capability.

A Additional related works

The related-work discussion contrasts FedCM with momentum and control-variate methods for federated or distributed optimization. It emphasizes FedCM’s lighter momentum computation and use of the full local optimization trajectory.

  • MimeLite: MimeLite applies server statistics such as momentum to client gradient steps, while FedCM and MimeLite both target client heterogeneity with global momentum.MimeLite can be generalized into Mime by adding a control variate.
  • Momentum computation: MimeLite computes momentum with an additional full-batch gradient, whereas FedCM updates momentum using averaged minibatch gradients.The passage presents this as the main computational distinction.
  • Efficiency: FedCM avoids MimeLite’s extra client computation and client-to-server communication by incorporating momentum updates into client-model aggregation.The resulting method is described as more efficient and lightweight.
  • Information used: FedCM computes momentum from all model parameters along the local optimization trajectory, whereas MimeLite uses the previously synchronized model, which can become stale.The trajectory parameters are described as closer to the current model and therefore more informative.
  • Other comparisons: SLOWMO applies an additional momentum step to averaged server models, while QG-DSGDm uses quasi-global momentum in decentralized optimization.FedCM instead addresses the centralized federated setting.

B.2 Proof of the main theorem

The proof develops auxiliary sequences and bounds client drift and update norms before completing the main convergence argument. It handles convex and non-convex cases using smoothness, sampling, variance, and step-size conditions.

  • Proof setup: The proof introduces an auxiliary sequence {z_t} and establishes update rules for it and related deviation sequences.These sequences organize the recursion used in the main convergence proof.
  • Federated update structure: The analysis models each client’s local trajectory while only selected clients transmit updates to the server.The proof notes that this modified description leaves the algorithm’s output unchanged.
  • Drift bounds: Client drift and the norm of the associated update deviation are bounded using smoothness, sampling without replacement, and variance properties.These bounds are assembled through Lemmas B.8 and B.9.
  • Recursive control: The norm relation between Δ_t and its modified counterpart follows from Δ_{t+1} = α ˜Δ_t + (1 − α)Δ_t and Jensen’s inequality.This relation is used to control the recursive deviation sequence.
  • Convex and non-convex cases: For the non-convex case, the proof expands f(z_{t+1}) using smoothness and selects an appropriate global step size through the preceding lemmas.The convex case uses a perturbed strong-convexity inequality.

C.1 Dataset generation

Experiments use CIFAR10 and CIFAR100 with balanced client data, comparing IID and Dirichlet-based heterogeneous splits. Hyperparameters vary by dataset and federated optimization method.

  • CIFAR10 and CIFAR100 experiments use standard 50000-image training and 10000-image test splits, with normalization applied to both.
  • Each client holds the same amount of training data across all settings.
  • IID splits randomly assign training data, while non-IID splits sample client class distributions from a Dirichlet distribution.
  • Larger Dirichlet concentration parameter α produces more similar data distributions across clients and therefore lower heterogeneity.
  • Local epochs, minibatch sizes, learning rates, decay parameters, and algorithm-specific coefficients are selected from specified candidate sets.
  • CIFAR10 uses five local epochs and batch size 50, whereas CIFAR100 generally uses two local epochs with method-specific batch sizes.

C.3 Convergence plots

Convergence plots compare FedCM with baselines on CIFAR10 and CIFAR100 across IID and Dirichlet 0.6 splits at 10% and 2% participation. FedCM outperforms strong baselines and converges more stably, especially under severe participation constraints and heterogeneity.

  • FedCM outperforms strong baselines across different participation rates and heterogeneity levels.
  • The performance gap is larger with 500 devices and 2% participation, supporting FedCM's robustness to limited participation.
  • FedCM converges more stably than FedAdam, whose curves show substantial oscillation, especially under the Dirichlet-0.6 setting.
  • The plots cover CIFAR10 and CIFAR100 under IID and Dirichlet 0.6 splits with 10% and 2% client participation rates.
Loading 2106.10874v1…