PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Learning with Buffered Asynchronous Aggregation

John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Michael Rabbat, Mani Malek, Dzmitry Huba

arXiv:2106.06639v4cs.LG

TL;DR

Cross-device FL faces scalability limits in synchronous training and privacy constraints in fully asynchronous aggregation. FedBuff addresses both with buffered asynchronous aggregation, achieving up to 3.3× higher efficiency than FedAvgM and up to 2.5× than FedAsync while supporting privacy-preserving technologies. The paper also analyzes convergence and reports private-training comparisons.

  • Problem

    Synchronous FL has diminishing returns beyond a few hundred concurrent clients, while fully asynchronous aggregation is incompatible with Secure Aggregation.

  • Method

    FedBuff asynchronously trains clients and buffers K client updates before each server update, supporting Secure Aggregation and differential privacy.

  • Results

    FedBuff is up to 3.3× more efficient than FedAvgM and up to 2.5× more efficient than FedAsync.

  • Takeaways & Limitations

    FedBuff combines large-concurrency asynchronous training with compatibility with Secure Aggregation and differential privacy.

  • Takeaways & Limitations

    The convergence analysis is based on standard SGD and does not extend to momentum or adaptive learning rates.

Abstract

from arXiv · show

Scalability and privacy are two critical concerns for cross-device federated learning (FL) systems. In this work, we identify that synchronous FL - synchronized aggregation of client updates in FL - cannot scale efficiently beyond a few hundred clients training in parallel. It leads to diminishing returns in model performance and training speed, analogous to large-batch training. On the other hand, asynchronous aggregation of client updates in FL (i.e., asynchronous FL) alleviates the scalability issue. However, aggregating individual client updates is incompatible with Secure Aggregation, which could result in an undesirable level of privacy for the system. To address these concerns, we propose a novel buffered asynchronous aggregation method, FedBuff, that is agnostic to the choice of optimizer, and combines the best properties of synchronous and asynchronous FL. We empirically demonstrate that FedBuff is 3.3x more efficient than synchronous FL and up to 2.5x more efficient than asynchronous FL, while being compatible with privacy-preserving technologies such as Secure Aggregation and differential privacy. We provide theoretical convergence guarantees in a smooth non-convex setting. Finally, we show that under differentially private training, FedBuff can outperform FedAvgM at low privacy settings and achieve the same utility for higher privacy settings.

1 Introduction

Cross-device FL must address scalability at high concurrency while preserving privacy. FedBuff uses buffered asynchronous aggregation to combine scalable training with compatibility with secure aggregation and differential privacy.

  • Cross-device FL involves millions of clients, limited availability, and devices with constrained communication bandwidth and compute power.
  • Synchronous FL has diminishing speed and quality returns as concurrency increases, limiting efficient acceleration beyond a few hundred clients.
  • Privacy is threatened by inference attacks, while secure aggregation and differential privacy protect client information and are important for real-world cross-device FL.
  • FedBuff lets clients train asynchronously while the server securely buffers K client updates before performing a server update.The secure buffer can be implemented with Trusted Execution Environments.
  • 3.8× more efficient than competing synchronous FL algorithms, FedBuff achieves this without penalizing synchronous methods for stragglers.FedBuff is also reported as up to 2.5× more efficient than FedAsync, with K = 10 working across benchmarks without tuning.
  • FedBuff is compatible with Secure Aggregation and global user-level differential privacy, and can outperform synchronous private-training baselines at low privacy settings.For higher privacy settings, it is reported to be competitive.

2 Background

The background contrasts synchronous FL’s scalability and straggler limitations with asynchronous FL’s operational advantages and privacy constraints. It also reviews secure aggregation, differential privacy, and the diminishing-return behavior of high concurrency.

  • Synchronous FL: Synchronous FL is easier to analyze and implement and aggregates many clients, which helps reduce the effectiveness of inference attacks.
  • Synchronous FL: Synchronous FL is vulnerable to stragglers because each round proceeds at the pace of the slowest client.Over-selection can address stragglers by selecting more clients than the target cohort size.
  • Synchronous FL: Beyond a few hundred clients, synchronous FL cannot efficiently accelerate training because server learning-rate increases eventually saturate, producing sublinear speed-up.This behavior is analogous to diminishing returns in large-batch training.
  • Asynchronous FL: Asynchronous FL accommodates heterogeneous compute power and intermittent client availability by maintaining a relatively constant number of active clients.Prior methods also introduce deployment burdens such as profiling clients, broadcasting updates, or assuming equal client speeds.
  • Asynchronous FL: Fully asynchronous methods update the server after every client update, preventing Secure Aggregation and leaving user-level differential privacy feasible only through local differential privacy.
  • Privacy: Secure Aggregation hides individual updates by combining them, while FedBuff is compatible with this protection.
  • Privacy: Global differential privacy uses a trusted server to collect, clip, and aggregate client updates before adding noise to the aggregate.In cross-device FL, user-level adjacency is defined by adding or removing all examples associated with one client.

3 FedBuff: Federated Learning with Buffered Asynchronous Aggregation

FedBuff combines asynchronous client training with buffered server aggregation, allowing secure aggregation while decoupling concurrency from server update frequency. Its buffer supports privacy-preserving extensions including SecAgg and differential privacy.

  • Optimization formulation: The paper analyzes FedBuff in a federated optimization setting where each client’s loss is locally accessible and the goal is a weighted average fit across clients.Client-specific loss functions and weights define the optimization objective.
  • Buffered asynchronous aggregation: FedBuff stores asynchronously arriving client updates and performs a server update only after K updates enter the buffer.K controls the update frequency independently of client concurrency; K = 10 is reported as a good choice without tuning.
  • Buffered asynchronous aggregation: The optimization framework aggregates client updates in a secure buffer before applying server updates.The secure buffer can be implemented with a Trusted Execution Environment or a cryptographic algorithm.
  • Privacy: FedBuff is compatible with Secure Aggregation when K > 1 because individual updates remain hidden within the aggregate.This compatibility supports extending FedBuff to global differential privacy.

4 Convergence Analysis

The convergence analysis establishes guarantees for FedBuff in a smooth, non-convex setting under bounded gradients, smoothness, variance, and staleness assumptions. It characterizes trade-offs involving buffer size, local computation, staleness, and communication.

  • Guarantee: FedBuff’s convergence analysis provides a guarantee for asynchronous client training followed by buffered aggregation and server updates.The analysis uses a smooth, non-convex setting and the perturbed iterate framework.
  • Algorithm: The FedBuff server algorithm uses client and server learning rates, Q local SGD steps, buffer size K, and optional clipping and noise for DP.Client updates are clipped and accumulated in a protected execution environment before buffered aggregation.
  • Trade-offs: The convergence bound captures initialization, local and global variance, client drift from local steps, staleness, and buffer-size effects.The theorem bounds an ergodic gradient norm squared, which is used to characterize convergence toward a first-order stationary point.
  • Trade-offs: Increasing local steps Q reduces loss faster but increases local drift, variance effects, and the impact of worst-case staleness.The trade-off follows from the distinct terms in the convergence bound.
  • Trade-offs: Staleness effects decay at O(1/T), while increasing buffer size K reduces maximum staleness.The buffer also introduces a communication-cost trade-off because each server step involves K client trips.

5 Practical Improvements

FedBuff adds staleness scaling and learning-rate normalization as practical improvements. These changes target stale asynchronous updates and variable client batch sizes, with learning-rate normalization reported to improve FedBuff.

  • Staleness scaling: FedBuff down-weights stale client updates using s(τi(t)) := 1/(1 + τi(t))^0.5.The scaling function reduces the weight of updates with greater staleness.
  • Learning-rate normalization: FedBuff linearly scales a local step’s learning rate when the actual client batch is smaller than the prescribed batch size B.The normalized rate is ηLRN := ηℓ·ni,q/B, where ni,q is the actual batch size.
  • Learning-rate normalization: The paper reports that learning-rate normalization can improve FedBuff and provides a theoretical justification in Appendix C.6.The adjustment addresses clients that perform local updates with fractions of the common batch size.

6 Experiments

The experiments compare FedBuff with synchronous and asynchronous FL using client trips as a common efficiency measure. FedBuff scales better at high concurrency, with K=10 performing well across benchmarks and maintaining privacy-utility advantages under differential privacy.

  • Evaluation setup: Client trips measure download, local training, and upload costs, serving as a proxy for wall-clock training time across asynchronous and synchronous methods.
  • Scalability: FedBuff scales better than FedAvgM as concurrency increases because K=10 enables more frequent server updates, despite introducing staleness.The experiments report that the benefits of frequent server updates outweigh the cost of stale client model updates.
  • Choice of K: K=10 is a good FedBuff setting across benchmarks at fixed concurrency.Table 2 evaluates client trips to target validation accuracy on CelebA, Sent140, and CIFAR-10.
  • Differential privacy: Under differential privacy, FedBuff can outperform FedAvgM with amplified DP-SGD and DP-FTRL at high ϵ and remain competitive at lower ϵ.These comparisons fix communication at 600 thousand client trips and use K=10 for FedBuff.

7 Related Work

Related work connects FedBuff to asynchronous optimization and large-batch scalability while distinguishing the federated setting. The paper emphasizes that FedBuff’s speedup combines straggler resilience with improved efficiency at high concurrency and supports privacy technologies.

  • Asynchronous stochastic optimization: Asynchronous training is resilient to stragglers, while prior buffered-update analyses have used assumptions that differ from FedBuff’s bounded-staleness assumption.
  • Positioning FedBuff: FedBuff is presented as more private than asynchronous FL proposals because buffered aggregation is compatible with Secure Aggregation and differential privacy.
  • Asynchronous stochastic optimization: FedBuff considers heterogeneous objectives and attributes speedup in large-scale FL to both avoiding stragglers and improving efficiency at high concurrency.
  • Large-batch training: Synchronous methods eventually saturate as concurrency grows, but much prior scalability research studies server workers with iid data rather than federated clients.

8 Conclusions

The paper concludes that buffered asynchronous aggregation addresses high-concurrency scalability while retaining compatibility with privacy-preserving technologies. It reports convergence analysis and empirical efficiency gains, but limits the analysis to standard SGD.

  • Contributions: FedBuff combines asynchronous training with buffered aggregation, scaling to large concurrency values while supporting Secure Aggregation and differential privacy.
  • Theory: The paper analyzes FedBuff’s convergence in a smooth non-convex setting and notes that increasing K reduces average delay.
  • Empirical results: 3.3× greater efficiency than FedAvgM and 2.5× greater efficiency than FedAsync are reported in empirical evaluation.
  • Limitation: The convergence analysis covers standard SGD, leaving momentum and adaptive learning rates for future work.

B.1 Datasets and Models

The experiments use three federated datasets spanning text and image classification, with client populations ranging from 5,000 to 660,120. Models, training, simulation, and hyperparameters are specified for reproducible comparisons.

  • Datasets and models: Sent140 uses an LSTM sentiment classifier over 660,120 Twitter-account clients, with 100 hidden units and 300-dimensional pretrained word embeddings.
  • Datasets and models: CIFAR-10 uses a four-layer CNN and a Dirichlet partition into 5,000 non-iid clients with parameter 0.1.
  • Experimental setup: Experiments implement algorithms in PyTorch, repeat runs with three seeds, simulate constant-rate arrivals, and model asynchronous delays with a half-normal distribution.
  • Hyperparameters: Hyperparameters are tuned with Bayesian optimization using client minibatch SGD and targets based on rounds required to reach validation accuracy.

C.1 Robustness to Delay Distributions.

FedBuff remains robust across delay and staleness conditions while improving resource efficiency and retaining diverse clients, including slower clients.

  • FedBuff’s speedup remains consistent across different staleness distributions and production delays observed over millions of clients.The production setting uses concurrency = 1000 and K = 100.
  • Increasing concurrency lowers wall-clock convergence time for all algorithms, but synchronous FL uses substantially more resources than asynchronous FL.Figure 6 evaluates runtime and client trips to reach target accuracy on Sent140.
  • FedBuff incorporates clients with large local datasets, whereas synchronous FL with over-selection drops slow clients and introduces selection bias.This comparison uses a random exponential time model across straggler parameters λ.
  • 25%-41% faster than FedAvgM, FedBuff reaches target accuracy despite using 30% lower concurrency, even when FedAvgM uses over-selection.Table 6 reports wall-clock time and client trips on CelebA and Sent140 with large K.
  • FedBuff with DP-FTRL achieves better utility and faster convergence than synchronous FL with DP-FTRL at the same ϵ.At low ϵ, FedBuff matches synchronous FL with amplified DP-SGD at the cost of slower convergence.

C.6.2 Empirical Evaluation

The empirical evaluation examines weighting schemes, staleness robustness, and buffer sizes across benchmark datasets, highlighting FedBuff’s behavior under heterogeneous client data and delays.

  • LR-Norm significantly outperforms Example Weight and Uniform Weight on Sent140, where clients have highly imbalanced data sizes.On CelebA, all three weighting schemes perform similarly because clients have one batch and relatively centered example counts.
  • FedBuff is robust to different staleness distributions, while synchronous algorithms are unaffected because they wait for every client in a round.The comparison uses training curves in Figures 9, 10, and 11.
  • K = 10 reaches target validation accuracy quicker than other tested K values on both CelebA and Sent140.The results suggest a balance between convergence speed and variance reduction.

D.1 Proof of Theorem 1

The proof derives bounds for FedBuff’s convergence by decomposing update effects into staleness, local drift, and stochastic-gradient variance under smoothness assumptions.

  • Under the stated learning-rate conditions, Algorithm 1 achieves an ergodic convergence rate in the smooth non-convex setting.
  • Conditional expectations over client participation and stochastic gradients establish the expected update terms used in the convergence analysis.The proof invokes unbiasedness of client gradients and independence across sampled clients.
  • The proof bounds T3 by separately accounting for staleness, local drift during client training, and client-side stochastic-gradient variance.It also requires an upper bound on the staleness of the initial model used for client training.
  • Choosing the global and local learning rates so T4 + T5 ≤ 0 enables the subsequent convergence-rate bound.The condition applies across all local steps q = 0, · · · , Q −1.
Loading 2106.06639v4…