PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast-Convergent Federated Learning

Hung T. Nguyen, Vikash Sehwag, Seyyedali Hosseinalipour, Christopher G. Brinton, Mung Chiang, H. Vincent Poor

arXiv:2007.13137v2cs.LGcs.DC

TL;DR

Federated learning often requires many costly communication rounds, while selecting only a subset of heterogeneous devices can slow convergence. The paper proposes FOLB, which uses gradient-informed update weighting and efficient device sampling, and reports improved accuracy, convergence speed, and/or stability across tasks and datasets.

  • Problem

    Federated learning must reduce communication costs and convergence delays while handling statistical and system heterogeneity and selecting only a subset of devices.

  • Method

    FOLB approximates a near-optimal device-selection distribution and weights participating-device updates using gradient information, with adaptations for computation and communication heterogeneity.

  • Results

    Across synthetic, vision, and language datasets, FOLB improves model accuracy, training stability, and/or convergence speed relative to FedAvg and FedProx.

  • Takeaways & Limitations

    FOLB theoretically achieves a near-optimal lower bound for overall loss decrease and significantly reduces rounds needed to reach specified loss or accuracy levels across tasks and datasets.

Abstract

from arXiv · show

Federated learning has emerged recently as a promising solution for distributing machine learning tasks through modern networks of mobile devices. Recent studies have obtained lower bounds on the expected decrease in model loss that is achieved through each round of federated learning. However, convergence generally requires a large number of communication rounds, which induces delay in model training and is costly in terms of network resources. In this paper, we propose a fast-convergent federated learning algorithm, called FOLB, which performs intelligent sampling of devices in each round of model training to optimize the expected convergence speed. We first theoretically characterize a lower bound on improvement that can be obtained in each round if devices are selected according to the expected improvement their local models will provide to the current global model. Then, we show that FOLB obtains this bound through uniform sampling by weighting device updates according to their gradient information. FOLB is able to handle both communication and computation heterogeneity of devices by adapting the aggregations according to estimates of device's capabilities of contributing to the updates. We evaluate FOLB in comparison with existing federated learning algorithms and experimentally show its improvement in trained model accuracy, convergence speed, and/or model stability across various machine learning tasks and datasets.

I. INTRODUCTION

Federated learning reduces data-transfer concerns but faces statistical and system heterogeneity, communication costs, and slow convergence from uniform client selection. The paper introduces FOLB, which uses update-aware selection, gradient-based aggregation, and heterogeneity adaptation to accelerate training.

  • Federated learning trains models across private device datasets coordinated by a central server, avoiding network transfer of raw data.Its setting involves local learning, server aggregation, and synchronization across participating worker devices.
  • Full device participation can impose excessive communication costs, while uniform selection of only a fraction of clients slows convergence.These constraints arise alongside statistical heterogeneity in edge-device data.
  • FOLB targets faster convergence by accounting for the differing value of clients’ local updates in reducing global model loss.The paper first characterizes non-uniform FedProx selection and derives a lower bound on expected loss decrease.
  • FOLB adapts to computation and communication heterogeneity through an aggregation mechanism that groups unknown device-related constants into an optimizable hyper-parameter.The hyper-parameter can be optimized with line search.
  • FOLB uses an accurate, communication-efficient approximation of a near-optimal device-selection distribution to accelerate federated optimization.Its theoretical and algorithmic development is based on aggregating local gradient information.
  • Experiments on synthetic, vision, and language datasets compare FOLB with FedAvg and FedProx on accuracy, training stability, and convergence speed.

B. Standard Federated Learning Algorithms

Standard federated learning repeatedly selects participating devices, performs local optimization, aggregates their updates, and synchronizes the resulting model. FedProx extends FedAvg with a proximal term, while the paper’s non-uniform framework motivates gradient-informed communication-efficient selection.

  • Each federated round selects K devices from N, performs local updates, aggregates returned parameters, and synchronizes devices with the new model.The server may sample devices according to a probability distribution, with replacement.
  • FedAvg directly minimizes each device’s local loss during local updates using gradient descent before global aggregation.Local gradients can be computed as averages over each device’s data.
  • FedProx adds the proximal term µ/2 ∥w − w_t∥^2 to local losses, restricting parameter divergence and potentially making local objectives easier to optimize.Setting µ = 0 recovers the FedAvg-style local objective.
  • The analysis permits non-convex local losses under Lipschitz-gradient, bounded-gradient-dissimilarity, Hessian, and inexact-solver assumptions.The Hessian condition yields strong convexity for the proximal local objective when µ′ = µ − σ > 0.
  • Non-uniform federated learning samples K devices according to a target distribution and weights repeated selections more heavily during aggregation.This framework is called FedNu and provides the starting point for estimating device-selection probabilities.
  • FOLB addresses the communication cost of directly computing the near-optimal distribution by using independent device sets and gradient information.The near-optimal distribution is linked to inner products between local and global gradients.

III. FEDNU: NON-UNIFORM FEDERATED LEARNING

The paper analyzes non-uniform device selection through expected per-round loss decrease and derives a near-optimal distribution based on local–global gradient alignment. FOLB approximates this distribution efficiently while retaining practical sampling and aggregation flexibility.

  • III. FEDNU: NON-UNIFORM FEDERATED LEARNING: The framework analyzes non-uniform selection and gradient-informed aggregation to derive a selection update achieving an efficient lower bound on expected per-round loss decrease.
  • A. Non-Uniform Device Selection: Devices are sampled K times from round-t probability distribution P_k^t, allowing repeated selections in the resulting multiset.Each unique selected device performs a local update, and repeated appearances increase its aggregation weight.
  • A. Non-Uniform Device Selection: The bound weakens as local and global gradients become more dissimilar, with E[f(w_{t+1})] proportional to B^2.The paper relates B to variation among local data distributions.
  • A. Non-Uniform Device Selection: The near-optimal selection distribution is based on inner products between local and global gradients and is designed to maximize the corresponding convergence-bound term.

B. Aggregation with Gradient Information

Gradient information strengthens federated aggregation by identifying harmful updates and motivating device-selection probabilities proportional to local–global gradient alignment. The resulting bound is stronger than FedProx’s uniform-selection bound and supports faster convergence.

  • Devices with negative local–global gradient inner products can hurt model performance under ordinary averaging.A signum-based aggregation rule negates these updates.
  • Replacing inner products with absolute values yields a stronger expected-loss-decrease lower bound.The stronger bound is stated in Proposition 1 and is attributed to incorporating gradient information.
  • The bound’s expectation depends on the selected-device set, and optimizing that expectation is difficult because sampling and selection probabilities are coupled.The paper therefore uses a candidate distribution favoring larger inner-product magnitudes.
  • The LB-near-optimal selection distribution assigns probability proportional to |⟨∇f(wt), ∇Fk(wt)⟩|.It prioritizes devices whose local gradients have greater alignment magnitude with the global gradient.
  • The LB-near-optimal bound is more general and stronger than FedProx’s bound restricted to uniform device selection.Applying the bound over rounds gives gradient convergence under suitable parameter constraints, with a faster corresponding rate.
  • The target probabilities require local and global gradient inner products that the server cannot evaluate before device selection.This motivates an efficient algorithm that matches the target loss decrease without substantially increasing communication.

D. Naive Algorithms for Fast Convergence

Two naive strategies can target the LB-near-optimal distribution, but each sacrifices an important efficiency or accuracy criterion. Direct computation incurs excessive communication, while norm-based estimation lacks a guarantee of accurate selection probabilities.

  • 1) Direct computation of LB-near-optimal distribution:: Directly computing the LB-near-optimal distribution requires sending the global model to all devices and collecting full local gradients.Although this obtains the target distribution and fast convergence, the extra communication defeats the purpose of selecting only K of N devices.
  • 1) Direct computation of LB-near-optimal distribution:: The direct-computation strategy requires one expensive server-to-all-devices communication iteration.The gradient has the same dimensionality as the model parameters.
  • 1) Direct computation of LB-near-optimal distribution:: Federated learning can still benefit from local multi-step updates and stochastic-gradient behavior even if additional gradient communication were affordable.These are presented as reasons not to replace the federated procedure with exact centralized gradient descent.
  • 2) Sub-optimal estimation of LB-near-optimal distribution:: A cheaper estimator samples devices proportionally to local gradient norms rather than local–global gradient inner products.Each device sends one scalar norm after receiving the global model, reducing upload demand.
  • 2) Sub-optimal estimation of LB-near-optimal distribution:: The norm-based estimator has no guarantee that the Cauchy–Schwarz upper bound accurately approximates the required inner products.Consequently, it may fail to satisfy LB-near-optimality.
  • 2) Sub-optimal estimation of LB-near-optimal distribution:: On MNIST, both naive LB-near-optimal methods reportedly converge faster than FedAvg and FedProx after only a few communication rounds.These observations motivate FOLB, which targets the same distribution without the extra communication.

IV. FOLB: AN LB-NEAR-OPTIMAL-EFFICIENT FEDERATED LEARNING ALGORITHM

FOLB addresses the cost and unavailable-gradient problems by uniformly sampling two independent device sets and calibrating updates with estimated gradient importance. Its design targets LB-near-optimal loss decrease while limiting communication overhead.

  • FOLB addresses the challenge of estimating LB-near-optimal probabilities without collecting all local gradients or adding substantial communication.The algorithm is designed around fast convergence and low communication overhead.
  • FOLB uniformly samples two multisets of K devices at the start of each round.One set supplies model updates and gradient information; the other supports calibration.
  • Devices in the first sampled set compute inexact local updates and send them with gradient-related information, while the second set sends gradients for calibration.The second set does not perform the same update computation.
  • FOLB weights received local updates by estimated importance rather than combining them through simple averaging.The calibration uses gradient correlation with the global gradient and normalizes weights using a second unbiased estimate of total correlation.
  • The calibration uses an unbiased global-gradient estimate from the first set and an unbiased total-correlation estimate from both sets.These estimates support update weighting relative to the global gradient.

B. Proof of LB-Near-Optimality

FOLB matches the lower bound achieved by LB-near-optimal device selection while reducing the communication burden through practical sampling adjustments. The resulting bound can exceed the LB-near-optimal bound when device data distributions are relatively uniform, but can be worse in highly concentrated cases.

  • Proof of LB-Near-Optimality: FOLB matches the LB-near-optimal lower bound on expected global-loss decrease under Theorem 2’s assumptions.The theorem establishes this property for Algorithm 2.
  • Proof of LB-Near-Optimality: Algorithm 2 requires local updates from 2K devices because it uses two device sets for updates and gradient estimation.Standard federated learning algorithms sample K devices and communicate both updates and gradients in this construction.
  • Optimizing FOLB Communication Efficiency: Using one device set for both updates and weight normalization reduces the total number of selected devices to K.The adjustment sets S_t^1 = S_t^2 and reuses received gradients.
  • Optimizing FOLB Communication Efficiency: The modified aggregation rule also leverages devices whose gradient alignment is negative by aggregating the negatives of their updates.This avoids discarding those device updates.
  • Optimizing FOLB Communication Efficiency: The practical single-set modification loses the independence used in the proof of Theorem 2, so Proposition 2 gives its corresponding loss-decrease bound.The proposition analyzes the modified aggregation rule under the same assumptions as Theorem 1.
  • Comparison with LB-Near-Optimal Selection: When device data are uniformly distributed, the new bound is K times better than the LB-near-optimal bound; with data on one device, it is K/N times worse.The paper states that practical cases are expected to be closer to the uniform-distribution case.

V. HANDLING COMPUTATION AND COMMUNICATION HETEROGENEITY

FOLB models communication delays and device-specific optimization quality, then adjusts aggregation to account for both forms of heterogeneity. The resulting analysis identifies devices as more beneficial when their updates align with the global gradient and their local solvers return more optimal solutions.

  • Modeling heterogeneous communication and computation: Each device’s communication delay is modeled by an upper bound T_c_k, estimated from the 99th percentile of its delay distribution.The paper gives an exponential distribution as an example for modeling communication delay.
  • Modeling heterogeneous communication and computation: Devices may use different γ_k-inexact local solvers, with γ_k varying by round according to available computation resources.The framework allows device-specific optimization quality instead of assuming one uniform γ-inexact solver.
  • Modeling heterogeneous communication and computation: During a server-defined round lasting τ, device k optimizes for τ − T_c_k time and returns its updated parameter and γ_k.This permits devices to use any available resources and local optimization algorithm within the allotted time.
  • V. HANDLING COMPUTATION AND COMMUNICATION HETEROGENEITY: FOLB adapts to heterogeneous communication and computation by modifying its aggregation scheme to target a near-optimal convergence rate.The section treats differing communication delays and computing capabilities across devices.
  • New loss bound with heterogeneity presence: The heterogeneous loss bound depends on local-global gradient inner products and the optimality of the solutions returned by individual devices.Theorem 3 gives the expected global-objective decrease under device probabilities P_t_k.
  • Implications of Theorem 3: A more beneficial device has an update aligned with the global gradient and sufficient resources to obtain a decent solution, represented by small γ_k.The paper notes that evaluating both criteria before selection would require expensive prior communication and computation.
  • FOLB aggregation for communication and computation heterogeneity: The near-optimal heterogeneous selection distribution prioritizes devices with high γ_k∥∇f(w_t)∥^2, while FOLB implements the corresponding aggregation rule.The section separately describes the distribution and the aggregation used by FOLB.
  • Avoiding constant estimations: Instead of estimating constants B, L, and µ′ beforehand or on-the-air, FOLB can tune ψ through a line search over {10^-1, 1, 10, 10^2}.The paper reports this tuning range as effective in its experiments.

VI. EXPERIMENTS

The experiments compare FOLB with FedAvg and FedProx across synthetic, vision, and language settings, including statistical and system heterogeneity. Results examine accuracy, training loss, stability, convergence speed, model architectures, device counts, and non-IID data.

  • Experiments compare FOLB with FedAvg and FedProx across synthetic, vision, and language datasets.The setup includes multinomial logistic regression and nonlinear models, with simulated computation and communication heterogeneity.
  • FOLB is evaluated using linear models on MNIST, FEMNIST, and synthetic datasets, with device data distributed under non-IID constraints.MNIST and FEMNIST devices receive images from only two digits, while synthetic datasets support multinomial logistic regression experiments.
  • FOLB is also evaluated with CNN, three-layer MLP, and LSTM models to test performance across neural-network architectures.The neural-network experiments include MNIST comparisons and nonlinear-model evaluations across various datasets.
  • The experiments vary participating-device counts and non-IID settings to assess convergence and robustness under different federated-learning conditions.The non-IID experiments assign each device images from a fixed number of digits, while device-count experiments vary the number selected per round.

B. Experimental results

Across models, datasets, and experimental conditions, FOLB generally improves loss, accuracy, convergence speed, or stability relative to FedAvg and FedProx. Its heterogeneity-aware aggregation further improves stability, while a multi-period device-selection strategy remains future work.

  • Quantifying the effectiveness of the proposed aggregation rule: FOLB’s aggregation rule yields lower loss and higher accuracy than FedProx, especially during early iterations and at smaller proximal parameters.The aggregation is designed to maximize a lower bound on loss decrease in each iteration.
  • Experiments with different neural network models: FOLB converges faster and more stably than FedProx across CNN and three-layer MLP experiments on MNIST.The comparison uses µ = 0.01.
  • Experiments with different number of devices: With more participating devices, FOLB converges faster and stabilizes quicker than FedProx; with few devices, its aggregation approaches simple averaging.The device-count experiment uses MNIST with a three-layer CNN and µ = 0.01.
  • Experiments with different non-IID settings: FOLB outperforms FedProx particularly under the most extreme MNIST non-IID setting.Devices are assigned images from only a fixed number of digits, including the case where each device has one digit.
  • Comparisons on various datasets and models: Across linear and nonlinear tasks, FOLB consistently reduces loss and improves accuracy relative to FedAvg and FedProx.On Synthetic 1 1, FOLB reaches a high-accuracy, low-loss level within 20 iterations, whereas the baselines do not reach it within 100 iterations.
  • Comparisons on various datasets and models: FOLB usually requires about half as many rounds as FedProx and FedAvg to reach the same accuracy level.On Synthetic 1 1, FOLB requires 19 rounds, compared with 154 for FedProx and 177 for FedAvg.
  • FOLB with and without communication and computation heterogeneity consideration: Accounting for communication and computation heterogeneity makes FOLB more stable than its heterogeneity-agnostic variant.The comparison varies ψ on Synthetic 1 1 and EMNIST, where FOLB performance varies most.
  • Conclusion: The paper concludes that FOLB achieves a near-optimal lower bound on per-round loss decrease and significantly reduces rounds needed to reach target loss or accuracy.The conclusion covers different tasks and datasets and incorporates statistical and system heterogeneity.

APPENDIX

The appendix develops theoretical bounds for FOLB by applying smoothness, convexity, solver, and gradient-dissimilarity assumptions to the aggregation update. It separately bounds update-norm and gradient-inner-product terms before combining them.

  • The proof begins from the L-Lipschitz inequality for the global loss and bounds the final terms on its right-hand side.The appendix then treats the last two terms separately.
  • Strong convexity and the inexact local-solver assumption bound each device’s local update.The proof also uses triangle inequality and gradient dissimilarity to control aggregated updates.
  • The aggregation step is used to expand the global-gradient inner product with the update and bound each resulting term.This is the main term-specific step in the theorem proof.
  • Substituting the derived bounds and taking expectations produces the stated inequality, while terms independent of device selection remain outside the expectation.The proof explicitly separates selection-dependent and selection-independent contributions.
  • The second proof changes the decomposition of the global-gradient inner product and then substitutes the resulting expressions into the bound.This establishes the corresponding result using the altered decomposition.

C. Proof of Lemma 1

The proof of Lemma 1 evaluates expectations under uniform random device selection by summing over device triples and pairs. It uses independent random selections and Taylor expansion to obtain the lemma’s stated relations.

  • The proof expands P_1 and averages over all combinations of three devices under uniform random selection.Each device triple has the same probability in the expectation.
  • The expectation is rewritten as a sum over possible device pairs and simplified analogously to the triple-device calculation.The proof treats all possible pair combinations.
  • Taylor expansion is applied to independently selected device sets to derive an equivalent expectation inequality.The derivation then uses Lemma 1 equations for the numerator and denominator.
  • The resulting expression is identified with the target equation, completing the proof.

E. Proof of Theorem 3

The proof bounds the update difference and its inner product with the gradient, then combines the resulting inequalities to complete the theorem.

  • The argument begins from the L-Lipschitz continuity of f.
  • The proof bounds w_t+1 − w_t using an argument analogous to the proof of Theorem 1.
  • It separately bounds ⟨∇f(w_t), w_t+1 − w_t⟩ by following similar steps to Theorem 1.
  • The proof combines the displayed bounds to obtain the claimed result.
  • After the combination step, the authors state that the proof is complete.
Loading 2007.13137v2…