PaperlayerView exact revision on arXiv

Source-linked AI summary

A Field Guide to Federated Optimization

Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Peter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtarik, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, Wennan Zhu

arXiv:2107.06917v1cs.LG

TL;DR

Federated optimization must accommodate privacy protection, communication costs, heterogeneous data, and practical system constraints. This paper offers guidance for formulating, designing, evaluating, and analyzing algorithms through practical examples and simulations, while emphasizing that it presents no new theoretical results.

  • Problem

    Federated optimization algorithms must support privacy protection and account for communication costs and deployment-time constraints beyond standard optimization settings.

  • Method

    The paper provides recommendations for problem formulation, algorithm design, evaluation, and empirical analysis using concrete examples and practical simulations.

  • Results

    The paper presents guidance rather than new theoretical results for designing and evaluating federated learning algorithms.

  • Takeaways & Limitations

    Researchers and practitioners can use the paper as a guide and concise handbook for designing and evaluating federated optimization algorithms.

  • Takeaways & Limitations

    Practical federated learning must contend with non-uniform client availability, which remains a challenge for existing theory and algorithm design.

Abstract

from arXiv · show

Federated learning and analytics are a distributed approach for collaboratively learning models (or statistics) from decentralized data, motivated by and designed for privacy protection. The distributed learning process can be formulated as solving federated optimization problems, which emphasize communication efficiency, data heterogeneity, compatibility with privacy and system requirements, and other constraints that are not primary considerations in other problem settings. This paper provides recommendations and guidelines on formulating, designing, evaluating and analyzing federated optimization algorithms through concrete examples and practical implementation, with a focus on conducting effective simulations to infer real-world performance. The goal of this work is not to survey the current literature, but to inspire researchers and practitioners to design federated learning algorithms that can be used in various practical applications.

1 Introduction

Federated learning keeps raw data decentralized while coordinating collaborative learning through aggregated updates, motivated by privacy and practical deployment constraints. This guide addresses unresolved choices in federated optimization and offers recommendations for formulation, design, evaluation, and analysis.

  • Federated learning setting: Federated learning coordinates clients through a central server while keeping each client’s raw data local and exchanging focused updates for aggregation.This design supports collaborative learning without transferring raw client data.
  • Privacy constraints: Privacy motivates local storage, data minimization, and compatibility with differential privacy and secure aggregation.These privacy requirements add constraints to federated optimization algorithm design.
  • Open design questions: The field lacks consensus on optimization formalization, data heterogeneity, system constraints, evaluation metrics, experimental settings, and parameter tuning.The paper provides recommendations and commentary on these areas.
  • Guide scope: The guide connects optimization theory, practical simulations, and real-world systems through problem-formulation, algorithm-design, and empirical-analysis recommendations.It is intended as guidance for researchers and a handbook for practitioners rather than a specific algorithm proposal.
  • Scope boundary: The discussion is not a comprehensive literature review, survey, or benchmark of state-of-the-art methods, and practical experience is biased toward mobile devices and some Google systems.Advanced techniques are presented as representative examples of general guidelines.
  • Optimization challenges: Federated optimization must address communication efficiency, heterogeneous and imbalanced data, privacy and security, and other concerns absent from many centralized settings.Communication can be a bottleneck for mobile devices, while client data cannot be directly shared.

2 Problem Formulation

Federated optimization formulates learning around population or empirical objectives built from client-local losses, while accounting for heterogeneous data, privacy, limited availability, and partial participation. Practical algorithms combine stochastic local computation, client sampling, local steps, and server aggregation to reduce communication and implement optimization under these constraints.

  • 2 Problem Formulation: The global objective averages client-local objectives, whose data distributions and dataset sizes may differ across clients.Client heterogeneity can produce different local objectives and even arbitrarily different local minima.
  • 2 Problem Formulation: Federated datasets remain private: local data cannot be shared with the server or shuffled across clients.This constraint is part of the problem formulation rather than merely an implementation preference.
  • 2 Problem Formulation: Cross-device federated learning has extremely large client populations, with typically less than 1% available at a given time and population quantities unknown before training.Client eligibility and availability complicate direct computation of the global objective and gradient.
  • 2.1 Federated Optimization Basics: Gradient descent updates the global model using the gradient of the global objective, which equals the expectation of local objective gradients under regularity conditions.In federated settings, the server obtains this information indirectly through client communication.
  • 2.1 Federated Optimization Basics: Partial participation replaces all-client updates with updates from a sampled subset, reflecting practical availability conditions beyond server control.Theory requires sampling assumptions for convergence, and partial participation can increase communication rounds.
  • 2.1 Federated Optimization Basics: Stochastic approximation lets clients replace exact local gradients with unbiased stochastic gradients, especially when local datasets are large.The estimator satisfies Eξ∼Di[gi(x(t))] = ∇Fi(x(t)).
  • 2.1 Federated Optimization Basics: Local steps reduce communication by having active clients perform τi updates before the server aggregates their model deltas.This is a popular technique for reducing communication costs.
  • 2.2 The Generalized Federated Averaging Algorithm: FedAvg combines sampled clients, local SGD updates, model-change aggregation, and repeated rounds until convergence; cross-silo training can include all clients each round.Its generalized form permits different client and server optimizers and aggregation methods.

13 end

FedAvg is generalized into a flexible framework, while federated optimization also supports alternative formulations such as personalization, composite objectives, and probabilistic inference. These extensions reflect the breadth of federated learning problems beyond the canonical global objective.

  • Generalized FedAvg: Generalized FedAvg allows designers to change client updates, global-model updates, and aggregation methods.The framework is parameterized by client and server gradient-based optimizers.
  • Relation to Local SGD: FedAvg generalizes Local SGD but differs through partial client participation and analyses that must account for federated data conditions.Classic Local SGD analyses often assume homogeneous local data.
  • Alternative formulations: The federated optimization formulation has been extended to applications including neural architecture search and other rapidly emerging settings.The paper characterizes its list of alternative formulations as incomplete.
  • Personalization and multi-task learning: Data heterogeneity motivates personalization and multi-task learning because a single global model may not match individual users’ data and usage patterns.The concern is the utility of a global solution for individual users.
  • Federated composite optimization: Federated composite optimization adds non-smooth regularization or hard constraints to the standard federated objective.Examples include sparsity, low-rankness, and monotonicity.
  • Probabilistic view: A probabilistic formulation treats federated learning as inference of a global posterior that decomposes into local posterior distributions.The resulting federated posterior averaging method resembles generalized FedAvg and has the same computation and communication complexity.

3 Practical Algorithm Design

Practical federated optimization design must balance communication, privacy, data and computational heterogeneity, client sampling, and compatibility with distinct application settings. The paper presents representative methods that improve over vanilla FedAvg while exposing trade-offs and unresolved consistency issues.

  • Application settings: Algorithms should specify their target application setting because cross-device and cross-silo FL have different client, state, and system constraints.Cross-device methods often require stateless clients, whereas methods requiring persistent client memory are more suitable for cross-silo FL.
  • Communication efficiency: Local updates reduce communication rounds but can increase convergence error, especially with non-IID client data.The additional error term grows with local steps, creating a trade-off between communication savings and convergence.
  • Client sampling: Sampling fewer clients can reduce per-round communication cost and mitigate stragglers, but sampling and inactivity complicate theoretical guarantees.Practical cross-device sampling can produce time-varying aggregation weights, and convergence and consistency remain open problems.
  • Privacy compatibility: Privacy-compatible aggregation must account for how weighting affects client influence and the difficulty of bounding sensitivity for differential privacy.Uniform weighting is used by DP-FedAvg, while non-uniform weighting can give one client’s update greater influence.
  • Representative algorithms: Server-side momentum and adaptive methods can accelerate convergence and improve validation performance without increasing client computation or per-round communication.FedAdam and FedYogi outperform vanilla FedAvg on multiple benchmark datasets, and server-side methods remain compatible with client sampling ratios below 1%.
  • Representative algorithms: Alternative local-objective regularization and aggregation methods address client drift or parameter-averaging problems, but their applicability depends on system assumptions.FedDyn requires persistent client states and is therefore more suitable for cross-silo FL, while coordinate-wise averaging can be harmful because hidden-layer parameters are permutation invariant.

4 On Evaluating Federated Optimization Algorithms

The paper recommends evaluating federated optimization under realistic communication, computation, data, and system conditions rather than relying on a single metric or setting. Simulated studies illustrate how tuning, communication rounds, local epochs, cohort size, and evaluation metrics can change conclusions.

  • 4.1 Example Evaluations: The authors implement recommendations in simulated evaluations of three federated optimization algorithms across four datasets.The datasets are GLD-23k, GLD-160k, CIFAR-10, and Stack Overflow; the algorithms use matched communication and client computation per round.
  • 4.2.1 Use Realistic Tuning Strategies: Held-out-set tuning may be impractical in federated systems with limited client availability, making federated hyperparameter tuning an open problem.The paper notes that learning hyperparameters jointly with the model is one alternative.
  • 4.2.2 Tune Client and Server Learning Rates: Learning-rate tuning can require jointly searching client and server rates because Algorithms A and B exhibit inter-dependent, staircase-shaped near-optimal regions.Algorithm C’s rectangular tuning pattern permits sequential tuning, avoiding a quadratic increase in tuning effort.
  • 4.2.4 Treat Local Training Steps as a Hyperparameter: Increasing local epochs can strongly affect Algorithm A’s initial accuracy but leaves Algorithm C comparatively robust across the tested settings.When measured by processed examples, E = 16 performs 8× as much work as E = 2, and benefits from increasing E saturate or decrease.
  • 4.2.4 Treat Local Training Steps as a Hyperparameter: The effect of local epochs depends on the simulated setting: GLD-23k shows different example-efficiency patterns, whereas CIFAR-10 yields roughly comparable processed-example counts across accuracies.This demonstrates that conclusions about local training should not be assumed to transfer unchanged across federated datasets.
  • 4.2.5 Understand the Impact of Cohort Size: Cohort-size comparisons should account for total client computation, because larger cohorts can increase electricity use, carbon emissions, and straggler-related delays.Accuracy-versus-examples plots can reverse the communication-round view: Algorithm C remains comparable across cohort sizes, while Algorithm A may require more examples at higher cohort sizes.
  • Using alternate evaluation metrics: Evaluations should supplement overall test accuracy with metrics such as mean accuracy across test clients to account for test-client data imbalance.The recommendation addresses a limitation of aggregating correctness over all test samples.

5 System Constraints and Practices

Federated optimization must be evaluated against real deployment constraints rather than idealized simulations, including heterogeneous resources, communication costs, privacy overhead, and data fidelity. The paper proposes a basic round-time model and emphasizes realistic simulation practices to improve transfer to production.

  • 5 System Constraints and Practices: Simulation environments often make communication free and continuously available, unlike real systems with extreme compute and communication heterogeneity.This mismatch is especially pronounced in cross-device settings, while geographically separated cross-silo participants can also incur large communication costs.
  • 5 System Constraints and Practices: Communication rounds capture only part of deployment cost; elapsed training time and the factors determining where time is spent should also be measured.Relevant dimensions include bandwidth, computation, and other communication costs.
  • 5 System Constraints and Practices: Real-world systems must account for bandwidth dynamics, stragglers, privacy overhead, resource heterogeneity, system policies, and client computation limits.Synchronous rounds can be blocked by the slowest participant, secure aggregation adds cryptographic cost, and shared device resources can restrict participation.
  • 5 System Constraints and Practices: The proposed basic system model estimates communication efficiency and execution time to compare algorithms and support system–algorithm co-design.The model is intended as a bridge from simulation to deployment and uses constants including Bdown ∼0.75 MB/secs, Bup ∼0.25 MB/secs, Rcomp ∼7, and Ccomp ∼10 secs.
  • 5 System Constraints and Practices: In the GLD-23k example, larger local-epoch settings converge faster by communication rounds but can drastically slow total training because client computation increases.The estimated per-example processing time is 0.127 seconds, and smaller E can allow more rounds within a fixed wall-clock time.
  • 5 System Constraints and Practices: Simulation observations transfer more reliably when pseudo-client data match production heterogeneity, client-example counts, and sequence-length distributions.The paper describes an iterative loop in which production failures improve simulations and subsequent on-device models.

6 Federated Optimization Theory

Federated optimization theory characterizes convergence, communication savings, and the effects of local updates under heterogeneous data. It also identifies when specialized methods or optimizer choices improve guarantees, while emphasizing persistent gaps between theory and practice.

  • Convergence guarantees: Theorem 1, supported by per-round progress and bounded-drift lemmas, provides convergence guarantees for convex local functions under η ≤ 1/(4L).The theorem is used to analyze FedAvg and local-update algorithms.
  • Communication efficiency: When stochastic noise is nonzero and T is sufficiently large, performing local steps does not degrade the convergence rate.Multiple local steps introduce additional error terms, but these decay with the learning rate and communication horizon.
  • Communication efficiency: Local updates can reduce communication: with fixed total computation K = MτT, local-update methods use T rounds versus τT for synchronous SGD.The largest allowable local-step count determines the maximum communication-round savings.
  • Effects of data heterogeneity: Data heterogeneity worsens local-update effects: additional error scales as O(τ^2), while the largest useful τ decreases when heterogeneity is high.If client objectives are identical, the additional error becomes linear in the number of local steps.
  • Comparison with large-batch synchronous SGD: FedAvg is not universally better than large-batch synchronous SGD; it can improve bounds under very low heterogeneity, but can be inferior when heterogeneity is large or local steps are few.Under homogeneous data, FedAvg can be better when τ is sufficiently large, whereas lower bounds restrict improvements in difficult heterogeneous regimes.
  • Extensions and improvements: SCAFFOLD and Mime achieve stronger convergence results under specified regularity conditions, while advanced server or client optimizers can improve rates or empirical performance.The cited analyses include optimal or accelerated rates and preservation of vanilla FedAvg’s rate with improved empirical behavior.

7 Privacy, Robustness, Fairness, and Personalization

Federated optimization must account for privacy, robustness, fairness, and personalization as constraints that shape both objectives and algorithm dynamics. The section highlights trade-offs and open problems spanning secure aggregation, private training, attacks, client performance disparities, and personalized models.

  • Privacy: Federated optimization methods can expose downstream information about client datasets through model updates, motivating privacy-aware algorithm design.Raw data remains local, but gradients can sometimes be used to reconstruct client data to some extent.
  • Privacy: Secure aggregation computes sums or weighted averages without revealing individual updates, but excludes algorithms requiring non-sum aggregations.This constraint creates a compatibility boundary for optimization-method design.
  • Privacy: Differential privacy creates a privacy–utility trade-off: stronger privacy with smaller (ϵ, δ) often sacrifices accuracy, although tailored mechanisms can mitigate it.The passage describes this trade-off as generally unavoidable in formal, information-theoretic ways.
  • Privacy: Conventional differentially private optimization can increase stochastic-gradient variance to order d, reducing accuracy for models with millions or billions of parameters.Increasing participating clients or using public data are discussed as possible mitigation strategies.
  • Robustness: Cross-device defenses against adversarial attacks remain limited because trusted server data is often unavailable, and targeted backdoor attacks remain difficult to detect.Existing memory-based defenses are described as designed for cross-silo settings, leaving cross-device extension open.
  • Fairness and Personalization: Fairness can be formulated through uniformity of model-performance distributions, while personalization may help address tensions among fairness, robustness, and privacy.Personalization gives each client a model suited to its own data and is presented as an active research area.

8 Concluding Remarks

The manuscript offers practical guidance for designing and evaluating federated optimization algorithms while connecting optimization to privacy, security, systems, and other constraints. It emphasizes careful, setting-specific evaluation and notes that its discussion is weighted toward cross-device federated learning.

  • Concluding Remarks: The manuscript guides new researchers and practitioners on designing and evaluating federated optimization algorithms, with practical considerations and introductory theory.It also discusses how federated optimization intersects with broader FL considerations.
  • Concluding Remarks: Evaluation should specify application settings and compare methods under the same constraints rather than recommend one universally superior algorithm.The manuscript uses generalized FedAvg-like algorithms to illustrate evaluation principles instead of directly ranking algorithms.
  • Concluding Remarks: The discussion is biased toward cross-device settings because they impose stricter practical constraints, including local computation, communication efficiency, and client availability.The authors attribute this emphasis partly to their practical familiarity with cross-device settings.
  • Concluding Remarks: Privacy, security, and system issues should receive attention alongside communication, heterogeneity, and computation when designing federated optimization algorithms.The manuscript frames optimization and these considerations as requiring co-design.
  • Concluding Remarks: The authors hope the guidelines help researchers and practitioners design and apply federated learning algorithms.

A.1 GLD-23k and GLD-160k Datasets

GLD-23k is a federated subset of GLD-160k, with images partitioned across clients by original authorship. GLD-160k is larger and has more landmark labels and clients than its GLD-23k subset.

  • A.1 GLD-23k and GLD-160k Datasets: Figure 10 presents statistics of the GLD-23k dataset.
  • A.1 GLD-23k and GLD-160k Datasets: GLD-160k contains 164,172 training images, 2028 landmark labels, and 1,262 clients.Its single test set is not federated and contains 19,526 images.
  • A.1 GLD-23k and GLD-160k Datasets: GLD-23k contains 23,080 training images, 203 landmark labels, and 233 clients.It is a subset of GLD-160k, whose clients represent image authors.

A.2 Stack Overflow Dataset

Stack Overflow is a language dataset built from questions and answers posted on the Stack Overflow forum, with metadata and user-based client partitions.

  • A.2 Stack Overflow Dataset: Each Stack Overflow client corresponds to a user, and that client’s examples are all of the user’s posts.Posts include metadata such as tags, creation time, question titles, scores, and post type.

A.3 CIFAR-10 Dataset

CIFAR-10 provides labeled 32 × 32 × 3 images for evaluating federated learning under an artificially constructed non-IID client partition.

  • CIFAR-10 contains 32 × 32 × 3 images with 10 possible labels.
  • The dataset includes 50,000 training examples and 10,000 test examples.
  • Clients receive non-IID data by drawing label distributions from a symmetric Dirichlet distribution with parameter α.Examples are assigned by sampling images corresponding to labels drawn from each client’s multinomial distribution.

B Empirical Evaluation - Details

The empirical evaluation uses three obfuscated FedOpt algorithms with identical client computation and communication, differing in their server optimizers and selected experimental settings across three tasks.

  • Algorithms A, B, and C correspond to FedAvg, FedAvgM, and FedAdam, respectively.The names are obfuscated to avoid comparisons of algorithmic efficacy because the section focuses on evaluation guidance.
  • All three algorithms use SGD on clients but differ in their server optimizers.FedAvg uses SGD, FedAvgM uses SGD with momentum, and FedAdam uses Adam.
  • The three methods perform the same amount of client computation and communication at each round.
  • The implementations vary client learning rate η and server learning rate ηs, with fixed optimizer-specific parameters for FedAvgM and FedAdam.FedAvgM uses momentum 0.9; FedAdam uses β1 = 0.9, β2 = 0.99, and ϵ = 0.001.
  • The experiments use one model per dataset: a modified ResNet-18 for CIFAR-10, MobileNetV2 variants for GLD datasets, and a three-layer Transformer for Stack Overflow.Normalization and dropout configurations are specified separately for the vision and language models.

C.1 More results for Section 4.2

The additional results examine hyperparameter selection and sensitivity across datasets, algorithms, local-update choices, cohort sizes, and communication or client-processing budgets.

  • Figure 11 compares Stack Overflow test accuracy for Algorithms A, B, and C using learning rates selected from training, validation, or testing accuracy.Training- and validation-based selection can be closely related in large-scale cross-device settings, whereas testing indicates capacity but is impractical for tuning.
  • Figures 12 and 13 show test accuracy across client and server learning rates for Algorithms A, B, and C on CIFAR-10 and GLD23k.These plots expose hyperparameter sensitivity, while test accuracy is described as impractical for tuning.
  • Figures 14–16 evaluate Stack Overflow validation accuracy across communication rounds, local epochs per round E, and total client-processed examples.Figure 16 uses η = 0.01 and ηs = 1.0 for Algorithm C.
  • Figures 17–19 examine how cohort size M affects accuracy versus communication rounds or client-processed examples on GLD-23k and Stack Overflow.

C.2 Basic Model to Estimate On-Device Training Times in Section 5.4

These figures compare accuracy against communication rounds and estimated completion time while varying local epochs per round on GLD-23k and fixed test subsets.

  • Figure 20 plots Algorithm C’s GLD-23k test accuracy for varying local epochs per round against communication rounds and estimated completion time.
  • Figures 21 and 22 plot accuracy on fixed sets of 10,000 randomly selected test examples for Algorithms A and C under varying local epochs per round E.Each figure compares test accuracy against communication rounds and estimated completion time using the model above.

D Proofs

The proofs derive bounds using convexity, smoothness, bounded covariance, and client independence, then combine and telescope these inequalities under a stepsize condition.

  • Convexity and L-smoothness of F_i provide the starting inequality for the proof bounds.
  • The proof combines intermediate inequalities and bounds terms using smoothness and convexity.
  • Bounded covariance assumptions and independence across clients justify the final inequality in the conditional-expectation argument.
  • The analysis imposes the stepsize condition η ≤ 1 4L when substituting bounds into the argument.
  • Telescoping over k from 0 to τ completes the proof of Lemma 1, followed by a separate proof of Lemma 2.
Loading 2107.06917v1…