PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Learning over Wireless Networks: Convergence Analysis and Resource Allocation

Canh T. Dinh, Nguyen H. Tran, Minh N. H. Nguyen, Choong Seon Hong, Wei Bao, Albert Y. Zomaya, Vincent Gramoli

arXiv:1910.13067v4cs.LGcs.DCcs.NIstat.ML

TL;DR

FL faces statistical heterogeneity across UE data and resource heterogeneity across wireless devices, motivating methods with convergence guarantees and resource-aware training. The paper proposes FEDL, analyzes its convergence and wireless allocation structure, and reports faster convergence and higher testing accuracy than vanilla FedAvg.

  • Problem

    FL must address heterogeneous UE data and heterogeneous computation, energy, and wireless resources while maintaining convergence guarantees.

  • Method

    The paper proposes FEDL with approximate local surrogate optimization, then decomposes its non-convex wireless resource-allocation problem into three sub-problems.

  • Results

    FEDL outperforms vanilla FedAvg in convergence rate and testing accuracy, while the allocation formulation yields closed-form solutions for its sub-problems.

  • Takeaways & Limitations

    The analysis characterizes the trade-off between local computation and global communication rounds and between FL wall-clock time and UE energy consumption.

Abstract

from arXiv · show

There is an increasing interest in a fast-growing machine learning technique called Federated Learning, in which the model training is distributed over mobile user equipments (UEs), exploiting UEs' local computation and training data. Despite its advantages in data privacy-preserving, Federated Learning (FL) still has challenges in heterogeneity across UEs' data and physical resources. We first propose a FL algorithm which can handle the heterogeneous UEs' data challenge without further assumptions except strongly convex and smooth loss functions. We provide the convergence rate characterizing the trade-off between local computation rounds of UE to update its local model and global communication rounds to update the FL global model. We then employ the proposed FL algorithm in wireless networks as a resource allocation optimization problem that captures the trade-off between the FL convergence wall clock time and energy consumption of UEs with heterogeneous computing and power resources. Even though the wireless resource allocation problem of FL is non-convex, we exploit this problem's structure to decompose it into three sub-problems and analyze their closed-form solutions as well as insights to problem design. Finally, we illustrate the theoretical analysis for the new algorithm with Tensorflow experiments and extensive numerical results for the wireless resource allocation sub-problems. The experiment results not only verify the theoretical convergence but also show that our proposed algorithm outperforms the vanilla FedAvg algorithm in terms of convergence rate and testing accuracy.

I. INTRODUCTION

The paper addresses FL’s statistical and physical-resource heterogeneity by proposing FEDL and a wireless resource-allocation framework. It establishes convergence trade-offs, decomposes the non-convex allocation problem, and reports experimental advantages over FedAvg.

  • FL must handle diverse UE data distributions while providing convergence guarantees; FedAvg performs well experimentally but lacks theoretical convergence analysis.
  • Wireless FL wall-clock time depends on heterogeneous UE computation and communication resources, including CPU types, data sizes, channel gains, and transmission power.
  • FEDL uses a local surrogate function with hyper-learning rate η and local accuracy θ, requiring only strongly convex and smooth loss functions.The method uses primal convergence analysis to characterize linear convergence and the trade-off between local and global update rounds.
  • FEDL outperforms vanilla FedAvg in training loss, convergence rate, and test accuracy, while experiments also examine mini-batches, UE sampling, and non-convex losses.
  • The resource-allocation problem captures the trade-off between FEDL training time and UE energy, decomposing the non-convex formulation into three sub-problems with closed-form or convex solutions.The first two sub-problems address computation and communication allocation; the third determines η and θ.
  • FEDL convergence is ensured for sufficiently small η and θ satisfying Θ ∈(0, 1), while θ trades local rounds against global rounds.Smaller θ increases local rounds but reduces global rounds; η affects the global convergence rate.

V. FEDL OVER WIRELESS NETWORKS

The paper formulates FEDL resource allocation over a time-sharing wireless environment, decomposes the problem into three sub-problems, and derives closed-form solutions with supporting numerical analysis.

  • FEDL resource allocation is formulated for a time-sharing wireless environment.
  • The non-convex allocation problem is decomposed into three simpler sub-problems.
  • The analysis derives closed-form solutions and provides numerical support for the decomposed problems.

A. System Model

The system model captures synchronous computation and uplink communication for heterogeneous UEs, combining their time and energy costs into the FEDL optimization problem.

  • System and timing model: Synchronous FEDL requires all UEs to finish local computation before communication begins.Each global round includes computation and uplink communication; downlink time is treated as negligible.
  • System and timing model: The wall-clock duration of one global round is Tg := Tco + Kl Tcp.
  • Computation model: UE computation time depends on required CPU cycles cnDn and CPU frequency fn.The number of cycles per local round is cnDn, and the computation time is cnDn/fn.
  • Communication model: UE communication uses time-sharing access, with transmission rate determined by bandwidth, noise, power, and channel gain.
  • FEDL optimization: The optimization minimizes UE energy and training time through a weighted objective, subject to communication, computation, hardware, and local-accuracy constraints.The weight κ represents additional energy cost accepted for one unit of training time reduction.

C. Solutions to FEDL

FEDL solves the non-convex allocation problem by decomposing it into convex CPU-resource subproblems and characterizing computation solutions through UE groups and virtual deadlines.

  • The FEDL allocation problem is non-convex because of constraint (19) and products of functions in the objective.
  • With fixed θ and η, FEDL decomposes into two sub-problems.
  • SUB1 controls CPU cycles for computation-time and energy minimization, and SUB2 controls uplink power and time sharing.Both sub-problems are convex after replacing constraint (19) in SUB1 with its equivalent form (23).
  • Algorithm 2 partitions UEs into bottleneck N1, strong N2, and interior-optimum N3 groups.N1 uses maximum frequency, N2 can finish before the deadline at minimum frequency, and N3 uses an interior feasible frequency.
  • The optimal SUB1 virtual deadline is determined by the longest deadline among the UE subsets.
  • The four SUB1 regions vary from minimum-frequency energy minimization to maximum-frequency computation-time minimization.Intermediate κ values produce energy-prioritized, balanced, or interior-frequency solutions.
  • For κ ≥ 1, computation-time minimization is prioritized and bottleneck UEs may run at maximum CPU frequency.Other UEs either adjust frequency to match the bottleneck completion time or finish earlier at minimum frequency.

2) SUB2 Solution:

SUB2 uses an indirect power-control function and an offer price κ to determine each UE’s transmission behavior, with heterogeneous channel gains producing different power regimes.

  • The function gn(·) maps the weight κ to a UE’s transmission-time control and is strictly decreasing.Its inverse supports price-based power selection: higher time priority corresponds to higher power and lower transmission time.
  • Each UE compares its energy-price function g_n^-1(·) with the system offer κ to choose how much power to provide.
  • Low, medium, and high offers lead respectively to minimum power, price-matching power, and maximum power.
  • κ = 0.1 is a medium offer for UEs 2, 3, and 4, but a high offer for UE 1 and a low offer for UE 5.
  • Unlike SUB1, SUB2 lets each UE independently select power without collecting all UE-load information.SUB1 requires global load information because computation times must synchronize, whereas SUB2’s time-sharing constraint decouples across UEs.

3) SUB3 Solution:

FEDL’s resource-allocation problem is decomposed into three sub-problems: two convex wireless-resource sub-problems and a generally non-convex sub-problem for η and θ. The resulting solutions provide stationary points and are evaluated through experiments covering batch size, local computation, heterogeneity, and non-convex learning.

  • SUB3 Solution:: SUB1 and SUB2 can be solved independently, and their solutions do not depend on θ.The corresponding optimal computation, frequency, communication-time, and energy quantities are determined from κ and then used by SUB3.
  • SUB3 Solution:: SUB3 is non-convex, so numerical methods such as NOVA are used to obtain stationary points.The optimal θ and η decrease as ρ increases, which also decreases Θ.
  • SUB3 Solution:: The combined solutions of SUB1, SUB2, and SUB3 are stationary points of the FEDL resource-allocation problem.This follows by decomposing the KKT conditions into three independent equation groups.
  • Experiments: FEDL outperforms FedAvg across batch-size settings, with testing-accuracy improvements of approximately 1.3%, 0.7%, and 0.8% for batch sizes 20, 40, and full batch.The corresponding training-loss improvements are approximately 9.1%, -0.2%, and 14%, respectively.
  • Experiments: Increasing local updates Kl improves FEDL convergence time but raises UE energy consumption through higher local computation.FEDL maintains a performance gap over FedAvg as Kl increases from 10 to 40, while minibatch FEDL outperforms GD FEDL on FEMNIST.
  • Experiments: FEDL also works empirically on the tested non-convex MNIST model, although its improvement over FedAvg is negligible relative to the strongly convex case.FEDL becomes less stable with small mini-batch sizes in this setting.

VII. NUMERICAL RESULTS

The numerical results examine heterogeneous UE settings and show how heterogeneity affects FEDL’s total cost and time–energy trade-off.

  • VII. NUMERICAL RESULTS: The numerical study increases the number of UEs to 50 and uses common UE computation settings in one experimental configuration.The stated configuration includes n = 2.0 GHz and cn = 20 cycles/bit.
  • VII. NUMERICAL RESULTS: Higher UE heterogeneity increases FEDL’s total cost as Lcp and Lco increase.Lcp controls computation heterogeneity, while Lco controls communication heterogeneity.
  • VII. NUMERICAL RESULTS: The Pareto curve captures the trade-off between minimizing time cost K(θ)Tg and energy cost K(θ)Eg.Reducing one cost requires increasing the other.
  • VII. NUMERICAL RESULTS: FEDL’s Pareto curve is more efficient under low UE heterogeneity, corresponding to small Lcp and/or Lco.The experiments vary computation and communication heterogeneity while maintaining average UE data size and distance in the respective settings.

APPENDIX

The appendix invokes L-smoothness and β-strong convexity to establish inequalities around the minimizer of each local objective.

  • APPENDIX: Assumption 1 requires Fn(·) to be L-smooth and β-strongly convex.These properties support the inequalities used in the appendix analysis.
  • APPENDIX: The appendix uses standard inequalities associated with smoothness and strong convexity of Fn(·).The cited results are attributed to Theorems 2.1.5, 2.1.10, and 2.1.12.
  • APPENDIX: The point w∗ is defined as the solution of minw∈Rd Fn(w).It is the optimizer of the local objective Fn.

B. Proof of Lemma 1

The proof of Lemma 1 combines smoothness and strong convexity inequalities with the iteration relation, then selects k to satisfy the θ-approximation condition.

  • B. Proof of Lemma 1: L-smoothness and β-strong convexity of Jn provide the inequalities used in the lemma proof.These inequalities are taken from the preceding relations (30) and (32).
  • B. Proof of Lemma 1: The proof combines the derived inequalities with (8) and sets z0 = wt−1 and zk = wt.This identifies the endpoints used in the iterative argument.
  • B. Proof of Lemma 1: The θ-approximation condition (3) is ensured when (1 −γ)k ≤ e−kγ satisfies the required bound.The proof then takes logarithms to complete the argument.

C. Proof of Theorem 1

The theorem proof bounds the global objective’s gradient using smoothness, Jensen’s inequality, Cauchy–Schwarz, and norm decompositions before completing the convergence argument.

  • C. Proof of Theorem 1: The proof begins by recalling the definition of Jt and introduces the quantity Z controlling the parameter conditions.Z is expressed as a function of η, θ, and ρ.
  • C. Proof of Theorem 1: F(·) is treated as L-Lipschitz smooth, allowing Jensen’s inequality and smoothness bounds to control gradient differences.The proof uses the bound ∥∇F(w) − ∇F(w′)∥ ≤ L∥w − w′∥.
  • C. Proof of Theorem 1: The proof derives intermediate bounds by adding and subtracting ∇¯F t−1 and ∇Fn(wt), then applying Cauchy–Schwarz and smoothness.These steps produce the norm bounds required for the theorem.
  • C. Proof of Theorem 1: Triangle inequality, Jensen’s inequality, and smoothness are used to bound the remaining norm terms.The final vector bound uses ∥x + y∥2 ≤ 2∥x∥2 + 2∥y∥2.

D. Proof of Lemma 2

The proof establishes Lemma 2 by showing SUB1 is a strictly convex optimization problem whose KKT solutions coincide with the algorithmic solutions across all relevant ranges of κ.

  • SUB1 has a strictly convex objective and convex feasible set, so its global optimum is characterized by KKT conditions.The proof introduces the SUB1 Lagrangian and corresponding non-negative dual variables.
  • Algorithm 2 partitions UEs into subsets N1, N2, and N3 according to κ-dependent conditions and associated thresholds.The proof constructs κ ranges in which these subsets and their threshold values satisfy the KKT conditions.
  • For sufficiently large κ, the condition at line 4 of Algorithm 2 holds because TN3 decreases as κ increases, ensuring N1 is non-empty.The proof considers κ ≥ the stated threshold and derives a corresponding non-empty subset satisfying the KKT characterization.
  • For small κ, N1 is empty and N2 is non-empty; for intermediate κ, N1 is empty and N3 is non-empty under the algorithm’s stated conditions.The proof separately examines these cases using the relevant inequalities and dual-variable conditions.
  • Across all cases, the KKT-characterized solutions are exactly the solutions provided by Lemma 2.This completes the equivalence between the optimization characterization and Algorithm 2’s construction.

E. Proof of Lemma 3

The proof establishes Lemma 3 by showing that SUB2 is convex and analyzing its KKT conditions, including the relationship λ∗=κ and the resulting variable characterization.

  • SUB2 is a convex problem because its objective is a sum of perspective functions of convex and linear functions over a convex feasible set.The proof therefore applies KKT conditions to characterize its optimum.
  • The SUB2 Lagrangian introduces non-negative dual variables λ, µn, and νn, whose optimal values satisfy the KKT conditions.These conditions provide the basis for deriving the optimal primal and dual variables.
  • The proof derives λ∗=κ and analyzes the resulting scalar equation using the substitution x := snτnB.This reduces the characterization to an equation involving the Lambert W function.
  • Because W(·) is strictly increasing in the stated region, gn(κ) is strictly decreasing and positive, as is its inverse function.This monotonicity supports the uniqueness and sign properties used in the KKT-based solution.
  • The remaining KKT cases determine when µ∗n can be positive and yield the corresponding optimal T∗n characterization.The proof uses equations (66)–(70) to complete the solution, including the case λ∗=κ>0.
Loading 1910.13067v4…