FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization

Amirhossein Reisizadeh; Aryan Mokhtari; Hamed Hassani; Ali Jadbabaie; Ramtin Pedarsani

Source-linked AI summary

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization

Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, Ramtin Pedarsani

arXiv:1909.13014v4Sep 28, 2019cs.LGcs.DCmath.OCstat.ML

TL;DR

Federated learning must reduce communication and scale across many devices despite heterogeneous participation. FedPAQ combines periodic averaging, partial participation, and quantization, achieving near-optimal guarantees while empirically characterizing communication-computation tradeoffs.

Problem
Federated learning still faces communication bottlenecks and scalability challenges because many devices must communicate with a parameter server.
Method
FedPAQ combines periodic local averaging, partial device participation, and quantized model updates to reduce federated-learning communication.
Results
FedPAQ achieves near-optimal guarantees for strongly convex and non-convex losses, including an expected O(1/T) strongly convex convergence rate, while characterizing communication-computation tradeoffs.
Takeaways & Limitations
FedPAQ improves communication efficiency while preserving the optimality and convergence guarantees of baseline methods within the analyzed settings.
Takeaways & Limitations
Choosing a large averaging period can increase system noise, reduce convergence accuracy, and require more training iterations to reach a target accuracy.

Abstract

from arXiv · show

Federated learning is a distributed framework according to which a model is trained over a set of devices, while keeping data localized. This framework faces several systems-oriented challenges which include (i) communication bottleneck since a large number of devices upload their local updates to a parameter server, and (ii) scalability as the federated network consists of millions of devices. Due to these systems challenges as well as issues related to statistical heterogeneity of data and privacy concerns, designing a provably efficient federated learning method is of significant importance yet it remains challenging. In this paper, we present FedPAQ, a communication-efficient Federated Learning method with Periodic Averaging and Quantization. FedPAQ relies on three key features: (1) periodic averaging where models are updated locally at devices and only periodically averaged at the server; (2) partial device participation where only a fraction of devices participate in each round of the training; and (3) quantized message-passing where the edge nodes quantize their updates before uploading to the parameter server. These features address the communications and scalability challenges in federated learning. We also show that FedPAQ achieves near-optimal theoretical guarantees for strongly convex and non-convex loss functions and empirically demonstrate the communication-computation tradeoff provided by our method.

1 Introduction

FedPAQ is proposed to address federated learning’s communication and scalability challenges through periodic averaging, partial device participation, and quantized message-passing. The method provides near-optimal convergence guarantees for strongly convex and non-convex losses while reducing communication overhead.

Motivation: Federated learning trains models on edge-node data while supporting privacy-preserving services, but communication and scalability remain central challenges.Applications include wearable devices, sentiment analysis, and location-based services.
Challenges: Communication is a bottleneck because many devices send local updates to a parameter server, motivating compressed and infrequent transmission.Federated networks can also contain thousands to millions of devices with varying availability, requiring partial participation or random sampling.
FedPAQ: FedPAQ combines periodic local SGD averaging, partial device participation, and quantized updates to reduce communication and support scalable federated learning.Devices perform local iterations before synchronization, only active devices participate in each round, and uploaded information is quantized.
Contributions: FedPAQ simultaneously incorporates these three features and provides near-optimal theoretical guarantees while remaining communication-efficient.The paper presents this combination as novel relative to prior work.
Theoretical guarantees: O(1/T) is the expected squared-distance rate after T iterations for strongly convex losses, while non-convex losses reach a first-order stationary point at O(1/T).The analysis covers strongly convex and non-convex loss functions and uses relaxed, customary assumptions.

2 Federated Learning Setup

The setup models federated learning as minimizing a population risk over distributed nodes whose local losses arise from local sample distributions. Under i.i.d. data, synchronizing all nodes can improve convex-risk accuracy from O(1/√m) locally to O(1/√nm) globally, while non-convex learning targets first-order stationary points.

Federated architecture: A parameter server seeks a model performing well across distributed users, which exchange local information with the server.The setup assumes all nodes’ data points are generated from a common probability distribution.
Risk formulation: Each node i has local objective fi(x) := Eξ∼Pi[ℓ(x, ξ)], while f(x) denotes the population risk.The model vector is x ∈ Rp, the random sample is ξ ∈ Ru, and ℓ is the stochastic loss function.
Data assumption: The analysis assumes data are independent and identically distributed across n nodes, implying common local distributions.The optimal model x∗ minimizes expected risk, with f∗ := minx f(x) = f(x∗).
Convex-risk approximation: O(1/√m) is the expected deviation for separately minimized local solutions, whereas synchronization can achieve O(1/√nm) accuracy.Each node has access to m samples; leveraging all nm samples yields E[f(ˆx) − minx f(x)] ≤ O(1/√nm).
Non-convex objectives: For non-convex losses, the goal is finding a first-order stationary point because solving or testing for a local optimum is NP-hard in many cases.The relaxed objective is to find a model satisfying the stationary-point condition for arbitrarily small approximation error ϵ.

3 Proposed FedPAQ Method

FedPAQ is a communication-efficient federated learning method built around periodic averaging, partial device participation, and quantized message passing. Its procedure has participating devices perform local updates before sending quantized model differences for server aggregation, addressing communication and bandwidth constraints.

Core components: FedPAQ combines periodic averaging, partial node participation, and quantized message passing as its three main modules.These modules are presented as the core components of the proposed method.
Periodic averaging: Periodic averaging reduces communication rounds, but excessively large local-update periods can increase noise and move local models toward local rather than global optima.A larger τ may therefore require more total iterations to reach a target accuracy ε.
Partial participation: In each training round, FedPAQ randomly selects r devices from n available devices, with r ≤n, to address limited base-station bandwidth and device participation constraints.The selected devices are assumed to be randomly and uniformly distributed over the network.
Quantized message passing: Devices apply quantization operators to transmitted updates, reducing communication overhead caused by limited uplink bandwidth.The quantizer’s accuracy determines the exchanged-message representation and resulting overhead reduction.
Algorithm: FedPAQ runs K periods of τ local updates, so T = Kτ iterations; selected devices initialize from xk, compute local updates, quantize their differences, and the server aggregates them into xk+1.The selected nodes receive the current server model before local optimization, and the procedure repeats for K periods.

4 Convergence Analysis

FedPAQ’s convergence analysis establishes guarantees under unbiased quantization, smooth local losses, and unbiased stochastic gradients with bounded variance. It addresses the bias introduced by multiple local updates and provides results for strongly convex and non-convex objectives, including communication-period tradeoffs.

Assumptions: The analysis assumes unbiased quantization with variance proportional to the squared l2-norm of its input, L-smooth local losses, and unbiased stochastic gradients with variance bounded by σ2.These conditions also imply Lipschitz continuity of local and aggregate gradients.
Challenges: With τ > 1, local updates are biased estimators of the corresponding global-gradient step, and this bias propagates as the period length increases.The resulting bias variance is not uniformly bounded under the stochastic-gradient assumption, complicating the analysis.
Strongly convex loss: For strongly convex losses, Theorem 1 gives a convergence guarantee under Assumptions 1–4 using the stepsize ηk,t = ηk = 4µ−1/kτ+1.The theorem applies to iterates generated by FedPAQ and defines a threshold k0 for the guarantee.
Strongly convex loss: The fastest strongly convex convergence occurs at τ = 1, while any period length satisfying the stated τ = o( condition ensures convergence to the global optimum.Setting τ = 1, q = 0, and r = n recovers vanilla parallel SGD’s O(1/T) rate.
Non-convex losses: For smooth non-convex losses, Theorem 2 establishes a first-order stationary condition when the total iterations T and period length τ satisfy its stated conditions.The result assumes Assumptions 1–3 and depends on the quantization parameter q and active-node count r.
Non-convex losses: Non-convex convergence is fastest at τ = 1, but larger periods reduce communication; the theorem recovers vanilla parallel SGD when τ = 1, q = 0, and r = n.The analysis also recovers the no-quantization, full-participation result when q = 0 and r = n.

5 Numerical Results and Discussions

The section empirically evaluates FedPAQ’s communication–computation trade-off, arising because periodic averaging, partial participation, and quantization reduce communication but can require more training iterations. Experiments examine logistic regression on MNIST and a non-convex neural-network objective on CIFAR-10 under communication bottlenecks.

Communication–computation trade-off: FedPAQ’s three communication-reduction modules trade lower communication load for reduced convergence accuracy and potentially more training iterations.The modules are periodic averaging, partial node participation, and quantization.
Experimental setup: Communication time is modeled as uploaded bits per round divided by fixed bandwidth, with r · |Q(p, s)| total uploaded bits.|Q(p, s)| is the encoded size of a p-dimensional quantized vector using s levels.
Experimental setup: Each node’s computation time follows a shifted-exponential model with deterministic cost τ · B · shift and random exponential mean τ · B · scale−1.The model applies to gradient computation over τ iterations with batchsize B.
Experimental setup: The experiments use Ccomm/Ccomp ≫1 to represent communication as substantially more costly than computation.The ratio measures communication cost for a length-p vector relative to the average computation cost for one gradient vector.
Logistic regression on MNIST: MNIST experiments train regularized logistic regression for T = 100 iterations on n = 50 nodes, using 200 samples per node and Ccomm/Ccomp = 100/1.The experiments vary one of quantization levels s, active nodes r, or period length τ while fixing the other two.
Neural network on CIFAR-10: CIFAR-10 experiments train a four-hidden-layer neural network with more than 92K parameters and Ccomm/Ccomp = 1000/1 for T = 100 iterations.The network uses n = 50 nodes and 10K samples from CIFAR-10 with 10 labels.

6 Conclusion

The paper proposes FedPAQ to address communication and scalability challenges in federated learning while providing provable performance guarantees. FedPAQ combines periodic averaging, partial node participation, and quantization.

FedPAQ overview: FedPAQ is presented as a communication-efficient federated learning method with provable performance guarantees.The method targets communication and scalability challenges in federated learning.
Periodic averaging: Periodic averaging lets each edge node perform local iterative updates before model aggregation.This module reduces the need for continuous server-side averaging.
Partial node participation: Partial node participation models the random availability of edge nodes during federated training.Only available nodes are represented as participating in the process.
Quantization: Quantization compresses each model before it is uploaded to the server.This module directly addresses communication overhead during model transmission.

7 Proof of Theorem 1

The proof of Theorem 1 decomposes the server model’s optimality gap into terms controlled by four lemmas, then combines these bounds under the theorem’s stepsize condition. It uses strong convexity, smoothness, unbiased quantization, and independent random sampling and quantization to establish the final convergence result.

Proof structure: Lemma 1 decomposes the parameter server’s optimality gap at each period into terms analyzed by Lemmas 2–4.The decomposition concerns E∥x_k+1 − x*∥2 and is stated for sequences generated by FedPAQ under Assumption 1.
Auxiliary lemmas: Lemma 3 characterizes a decomposition term for FedPAQ under Assumptions 1–4 and the same stepsize restriction.The proof uses the unbiased quantizer and independently performed quantizations across iterations and workers.
Auxiliary lemmas: Lemma 4 bounds the term involving participating-node contributions under Assumptions 1–4, with r denoting the number of nodes contributing in each period.Its proof applies the quantization bound and concludes the lemma by substituting the preceding bound.
Final convergence argument: The combined recursion is controlled by choosing η_k = 4µ^-1/(kτ+1); Lemma 5 then gives a convergence bound for the resulting non-negative sequence.For k ≥ k0, the proof establishes a contraction condition on C0 before applying Lemma 5 and rearranging terms to obtain Theorem 1.
Randomness handling: Uniform random node sampling, unbiased quantization, and independence between the two randomness sources justify the expectation steps used in the decomposition.The conditional expectations are taken with respect to the history through iteration τ in period k.
Auxiliary lemmas: Lemma 2 bounds the averaged local model’s optimality gap using strong convexity, Lipschitz gradients, stochastic-gradient effects, and the stepsize condition η_k ≤ min{µ/L^2, 1/Lτ}.The proof compares local SGD updates with an auxiliary Gradient Descent sequence on the global loss, both initialized at x_k.

8 Proof of Theorem 2

The proof of Theorem 2 establishes auxiliary bounds under the stated assumptions, combines Lemmas 6–9 into a recursive inequality, and derives the convergence rate by selecting a valid stepsize and summing over periods.

Proof of Theorem 2: The four lemmas are combined to derive a recursive inequality for the expected function values of parameter-server models {x_k}.The recursion concerns models updated at the parameter servers for k = 1, · · · , K.
8.1 Stepsize constraint: η = 1/L^T is selected subject to Theorem 2’s condition (16), ensuring the recursive inequality also satisfies condition (81).The proof separately verifies that the theorem’s stepsize choice obeys the constraint required by the recursion.
8.1 Stepsize constraint: T ≥2 ensures η ≤0.9/L for η = 1/L^T, while the remaining constraint is equivalent to the condition in (89).The stepsize constraint is analyzed through a quadratic inequality in y = ητ.

9 Additional Numerical Results

The section extends FedPAQ’s numerical evaluation to more complicated datasets and model configurations while keeping the Section 5 network, communication, and computation models unchanged. Results report training loss versus training time for CIFAR-10, CIFAR-100, and Fashion-MNIST scenarios.

Experimental scope: Additional experiments evaluate FedPAQ on more complicated datasets and model parameters under the same network, communication, and computation models as Section 5.The section presents these results to further illustrate FedPAQ’s practical performance.
CIFAR-10: The CIFAR-10 experiment uses a four-hidden-layer neural network with more than 248K parameters and 10K samples spanning 10 labels.Figure 2 plots training loss against training time.
CIFAR-100: The CIFAR-100 experiment uses a one-hidden-layer neural network trained on 10K samples spanning 100 labels.Figure 3 plots training loss against training time.
Fashion-MNIST: The Fashion-MNIST experiment uses a one-hidden-layer neural network trained on 10K samples spanning 10 labels.Figure 4 plots training loss against training time.
Common settings: Across all scenarios, samples are uniformly distributed among n = 50 nodes, with Ccomm/Ccomp = 1000/1, B = 10, and a finely tuned stepsize for each training run.These settings match the Section 5.2 setup for data distribution, communication-computation ratio, and batchsize.