Source-linked AI summary
FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
Zheng Chai, Yujing Chen, Ali Anwar, Liang Zhao, Yue Cheng, Huzefa Rangwala
TL;DR
Federated learning must address stragglers, non-i.i.d. data, communication bottlenecks, and bias toward faster clients. FedAT combines tiered synchronous and asynchronous training with weighted aggregation and polyline compression, reporting higher prediction performance and lower communication cost than state-of-the-art methods.
Problem
Federated learning faces stragglers from heterogeneous clients, communication bottlenecks, and potential bias toward faster tiers.
Method
FedAT combines synchronous intra-tier training, asynchronous cross-tier updates, slower-tier-weighted aggregation, and polyline compression.
Results
FedAT improves prediction performance by up to 21.09% and reduces communication cost by up to 8.5× compared with FedAsync.
Takeaways & Limitations
FedAT provides a tiered hybrid training approach with provable convergence guarantees and empirically high prediction performance, fast convergence, and communication efficiency.
Takeaways & Limitations
The evaluation assumes that a client dropping out does not return to the training process.
Abstract
from arXiv · showhide
Federated learning (FL) involves training a model over massive distributed devices, while keeping the training data localized. This form of collaborative learning exposes new tradeoffs among model convergence speed, model accuracy, balance across clients, and communication cost, with new challenges including: (1) straggler problem, where the clients lag due to data or (computing and network) resource heterogeneity, and (2) communication bottleneck, where a large number of clients communicate their local updates to a central server and bottleneck the server. Many existing FL methods focus on optimizing along only one dimension of the tradeoff space. Existing solutions use asynchronous model updating or tiering-based synchronous mechanisms to tackle the straggler problem. However, the asynchronous methods can easily create a network communication bottleneck, while tiering may introduce biases as tiering favors faster tiers with shorter response latencies. To address these issues, we present FedAT, a novel Federated learning method with Asynchronous Tiers under Non-i.i.d. data. FedAT synergistically combines synchronous intra-tier training and asynchronous cross-tier training. By bridging the synchronous and asynchronous training through tiering, FedAT minimizes the straggler effect with improved convergence speed and test accuracy. FedAT uses a straggler-aware, weighted aggregation heuristic to steer and balance the training for further accuracy improvement. FedAT compresses the uplink and downlink communications using an efficient, polyline-encoding-based compression algorithm, therefore minimizing the communication cost. Results show that FedAT improves the prediction performance by up to 21.09%, and reduces the communication cost by up to 8.5x, compared to state-of-the-art FL methods.
1 Introduction
Federated learning must handle heterogeneous clients, stragglers, non-i.i.d. data, and communication bottlenecks simultaneously. FedAT combines tiered synchronous and asynchronous training with weighted aggregation and polyline compression to improve performance and communication efficiency.
- Federated learning keeps client data decentralized while coordinating local model training through a server.
- Resource and data heterogeneity create stragglers, while large client populations make server communication a crucial design choice.
- FedAT partitions clients by response latency, synchronizes updates within tiers, and asynchronously updates the global model across tiers.
- FedAT weights slower tiers more heavily to counter faster-tier bias and uses polyline encoding to compress transferred model data.
- 21.09% higher prediction accuracy and 8.5× lower communication cost are reported for FedAT compared with FedAsync.
2 Related Work
Prior federated learning approaches address stragglers, communication, or training efficiency through synchronous, asynchronous, tiered, and compressed updates. FedAT combines these directions while adding weighted aggregation and compressing both communication directions.
- Stragglers in Federated Learning: Synchronous FL can wait for slow clients, whereas asynchronous FL avoids waiting but requires more frequent communication and can increase communication costs.
- Stragglers in Federated Learning: TiFL uses synchronous intra-tier updates, but its adaptive tier selection requires repeated client accuracy collection and may incur communication, duration, and bias costs.
- Stragglers in Federated Learning: FedAT combines intra-tier synchronous training with cross-tier asynchronous training and can tolerate mis-tiering from profiling errors or performance variation.
- Communication-Efficient Federated Optimization: FedAvg reduces communication frequency through multiple local SGD iterations and supports partial client participation.
- Communication-Efficient Federated Optimization: FedAT combines synchronous and asynchronous updates, applies server-side weighted aggregation, and compresses uplink and downlink communication.
3 Preliminaries: Federated Learning and FedAvg
Federated learning optimizes a shared model from decentralized, often non-i.i.d. client data, while FedAvg synchronously aggregates local updates. Stragglers can prolong training and increase prediction-accuracy variance.
- Federated Learning: Federated learning coordinates decentralized client training through a centralized server that aggregates local models.
- Federated Learning: The objective aggregates each client’s local empirical loss, weighted by its number of stored data samples.
- FedAvg: FedAvg randomly selects clients, performs multiple local SGD epochs, and synchronously aggregates their updates.
- Federated Learning: Non-i.i.d. training can drive clients toward local optima instead of a global optimum.
- Stragglers: Stragglers lengthen training, impede convergence toward the optimum, and can increase prediction-performance variance.
- Stragglers: Robustness against stragglers is evaluated using convergence speed, accuracy variance across clients, and prediction performance.
4 FedAT: Federated Learning with Asynchronous Tiers
FedAT combines synchronous intra-tier updates with asynchronous cross-tier global updates, using weighted aggregation and polyline encoding to balance training and reduce communication overhead.
- FedAT partitions clients into performance tiers based on response latency and maintains a model for each tier alongside an asynchronously updated global model.
- Each tier synchronously aggregates selected client updates, while tiers asynchronously update the global model whenever they finish local training.The server receives compressed models, updates the corresponding tier model, and aggregates the latest models from all tiers.
- FedAT restricts local updates toward the global model with a constraint term to address divergence under Non-i.i.d. data.
- FedAT assigns relatively higher weights to slower tiers according to their update frequencies to reduce bias toward faster tiers and improve convergence.The weighted aggregation objective dynamically adjusts tier weights based on historical global updates.
- FedAT uses polyline encoding to compress both uplink and downlink model communication, achieving a compression ratio of up to 3.5× under the evaluated FL scenarios.The method flattens layer weights, encodes decimal values as compressed ASCII strings, and transmits layer dimensions for decompression.
5 Convergence Analysis
FedAT's convergence analysis establishes guarantees under stated smoothness, convexity, inexactness, and gradient assumptions for both strongly convex and non-convex objectives on Non-i.i.d. data.
- FedAT is analyzed for convergence to the global optimum under both strongly convex and non-convex objectives on Non-i.i.d. data.
- γ-inexactness allows local objectives to be solved flexibly by tuning local iterations and the tradeoff between local computation and communication.
- The strongly convex convergence theorem assumes an L-smooth, μ-strongly convex central objective, γ-inexact local functions, and specified stochastic-gradient assumptions.
- Under these conditions, after T global server updates, FedAT converges to a global optimum w*.
- The non-convex convergence theorem assumes an L-smooth central objective, γ-inexact local functions, and Assumptions 5.1–5.3.
6 Experimental Setting
The evaluation uses five federated datasets and compares FedAT with five synchronous and asynchronous FL methods across heterogeneous experimental settings.
- Federated Datasets: The study evaluates FedAT on CIFAR-10, Fashion-MNIST, Sentiment140, FEMNIST, and Reddit federated datasets.The datasets span image, text, and naturally heterogeneous client distributions, including 100 to 3,550 clients in the described settings.
- FL Methods: The experiments compare FedAT against five synchronous and asynchronous federated learning methods.
- FL Methods: FedAvg is included as a synchronous baseline that samples clients, trains locally for E epochs, and averages their model weights.
7 Evaluation
Across datasets, objectives, and participation settings, FedAT generally converges faster, achieves higher accuracy, and lowers communication cost than the compared FL methods. Its weighted aggregation improves accuracy, while compression reduces transferred data with a measurable accuracy–cost tradeoff.
- FedAT converges faster toward the optimal solution than all three compared methods on both non-convex and convex objectives.
- 8.04% is FedAT’s maximum prediction-performance improvement over FedAvg across the evaluated CIFAR-10 Non-i.i.d. levels.FedAT outperforms the other FL methods at every tested Non-i.i.d. level, with the largest gap in the 2-class case.
- 5.27×, 5.67×, and 5.82× are the longer training times of TiFL, FedAvg, and FedProx than FedAT to reach 47% accuracy on CIFAR-10.On Sentiment140, TiFL, FedAvg, FedProx, and FedAsync take 3.39×, 5.41×, 4.49×, and 0.3× longer than FedAT, respectively.
- 9.5× is FedAsync’s approximate communication cost relative to FedAT, while FedAT requires up to 1.28× less uploaded data than other methods for equal CIFAR-10 performance.FedAT’s compression and weighted aggregation contribute to the lowest reported communication cost.
- 36.41% and 67.3% are the reductions in uploaded data from Precision 4 versus Precision 6 and No Compression at the same 50% target accuracy.Precision 4 approaches the no-compression accuracy, and FedAT reaches an overall compression ratio of up to 3.5×.
- 1.39% to 4.05% is the best-test-accuracy improvement from weighted aggregation versus uniform aggregation across three datasets.The heuristic assigns more weight to tiers that participate less frequently, counteracting bias toward faster tiers.
8 Conclusion
FedAT combines tiering, asynchronous cross-tier updates, weighted aggregation, and polyline compression to improve prediction performance while reducing communication cost. Its analysis covers convex and non-convex losses, with experiments validating the theoretical results against state-of-the-art methods.
- FedAT combines tiering, asynchronous global updates, weighted aggregation, and polyline compression in one federated learning framework.
- FedAT provides theoretical analysis for both convex and non-convex loss functions.
- Experiments show that FedAT achieves the highest prediction performance, fastest convergence, and communication efficiency versus state-of-the-art federated learning methods.
A Theoretical Analysis of FedAT
This section analyzes FedAT in convex and non-convex settings using the server's model parameters and an aggregated gradient expression. The resulting update is expressed through the server model and the aggregate gradient.
- FedAT is analyzed under both convex and non-convex loss settings.
- The analysis defines w_t as the server's model parameters at global round t.
- The server update uses an aggregated gradient expression across clients and tiers to obtain w_t+1 from w_t.
A.1 Proof of Lemma 5.1
The proof of Lemma 5.1 introduces lemmas, applies local-objective inexactness, and takes expectations under an assumption to derive the stated result.
- The proof begins by introducing two lemmas for establishing Lemma 5.1.
- It uses the notion of γ-inexactness for each local objective.
- The argument takes expectations and invokes Assumption 5.2.
A.2 Proof of Lemma 5.2
The proof of Lemma 5.2 constructs a quadratic auxiliary function under strong convexity, identifies its minimizer, and proceeds through assumptions and lemmas to complete the convergence proof.
- The proof uses μ-strong convexity of f(w) to construct and analyze the auxiliary function Γ(w′).
- Γ(w′) is minimized where ∇f(w_t) + μ(w′ − w_t) = 0.
- The convergence argument applies Definition 5.1, Lemmas 5.1 and 5.2, and Assumption 5.3 while rearranging successive inequalities.
- The final bound follows by summing over global iterations and recognizing a geometric series with ratio 1 − 2μησ/B.