PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Federated Learning in Resource Constrained Edge Computing Systems

Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, Kevin Chan

arXiv:1804.05271v3cs.DCcs.LGmath.OCstat.ML

TL;DR

The paper addresses how to train models from distributed edge data without centralizing raw data despite limited computation and communication resources. It derives a convergence bound for federated gradient descent and uses it to adapt global aggregation frequency under a resource budget. Experiments on real datasets in prototype and simulated environments show near-optimal performance across models and data distributions.

  • Problem

    The paper asks how to learn from distributed edge data without sending raw data centrally while efficiently using limited computation and communication resources.

  • Method

    The paper derives a convergence bound for non-i.i.d. federated gradient descent and uses it to control global aggregation frequency under a resource budget.

  • Results

    Experiments on real datasets using a hardware prototype and simulation show near-optimal performance across machine-learning models and data distributions.

  • Takeaways & Limitations

    Adaptive control can determine the trade-off between local updates and global aggregation to minimize learning loss under resource constraints.

Abstract

from arXiv · show

Emerging technologies and applications including Internet of Things (IoT), social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent based approaches. We analyze the convergence bound of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

I. INTRODUCTION

The paper studies federated learning at resource-constrained edge nodes, where raw data remains distributed and global aggregation must be balanced against local computation and communication costs. It develops theory and an adaptive aggregation-control algorithm, then evaluates it across data distributions, models, and system settings.

  • Motivation: Edge nodes retain distributed raw data while collaboratively training models, avoiding centralized collection because bandwidth and privacy make sending all data impractical.The setting supports detection, classification, and prediction tasks using local storage, processing, and global coordination.
  • Problem Setting: Federated learning alternates local gradient updates with weighted global aggregation, whose frequency determines the trade-off between training accuracy and resource consumption.Local updates consume computation resources, while global aggregation consumes network communication resources.
  • Problem Setting: The central optimization problem is selecting local-update and aggregation frequencies to minimize global loss under a fixed resource constraint.The paper frames this as efficiently using limited computation and communication resources at the edge.
  • Contributions: The paper derives a convergence bound accommodating non-i.i.d. data and an arbitrary number of local updates between global aggregations.This addresses limitations of prior bounds that restrict local updates or assume i.i.d. data.
  • Contributions: Using the bound, the proposed control algorithm adapts global aggregation frequency in real time from data distribution, system dynamics, and model characteristics.Its objective is to minimize learning loss under a fixed resource budget.
  • Evaluation: Experiments on real datasets using a hardware prototype and simulation show near-optimal performance across data distributions, machine-learning models, and system configurations.The evaluation includes different numbers of edge nodes.

IV. PROBLEM FORMULATION

The problem formulation selects local-update and global-aggregation schedules that minimize training loss under resource budgets, while the convergence analysis supplies a bound for approximating this optimization.

  • IV. PROBLEM FORMULATION: Resource-constrained federated learning minimizes the global loss by choosing the number of iterations and local updates per aggregation under multiple resource budgets.Resources may include time, energy, or communication bandwidth, with local and global steps consuming different amounts.
  • IV. PROBLEM FORMULATION: The total number of global aggregations is K, with T iterations divided into intervals of τ local updates, so K = T/τ.The formulation assumes T is an integer multiple of τ.
  • IV. PROBLEM FORMULATION: Each resource type m imposes (T + 1)c_m + (K + 1)b_m ≤ R_m, combining local-update and global-aggregation costs.c_m and b_m denote per-step consumption, while R_m is the available budget.
  • IV. PROBLEM FORMULATION: The exact relationship between τ, K, and final loss is generally unavailable because convergence bounds and aggregation-frequency effects are not analytically exact.Time-varying resource costs further complicate the optimization.
  • IV. PROBLEM FORMULATION: The proposed solution analyzes distributed-gradient convergence, then uses the resulting bound to approximately choose τ and T for near-optimal resource utilization.The control algorithm adaptively selects these values rather than solving the loss relationship exactly.
  • A. Definitions: The convergence analysis partitions T iterations into K intervals whose endpoints contain global aggregation, using [k] = [(k − 1)τ, kτ].Figure 3 illustrates these interval definitions.
  • A. Definitions: Within each interval, an auxiliary centralized-gradient sequence v^[k](t) is synchronized with the averaged distributed parameter at the interval’s beginning.This sequence uses the global loss, whereas local iterations use each node’s local loss.
  • V. CONVERGENCE ANALYSIS: The convergence bound combines the divergence between distributed and centralized updates after τ local steps with centralized-gradient convergence within each interval.The analysis assumes local losses are convex, ρ-Lipschitz, and β-smooth, and separately measures gradient divergence caused by data distribution.

B. Main Results

The paper derives convergence bounds for distributed gradient descent and uses them to characterize how local-update frequency and data heterogeneity affect the optimality gap. It then proposes an algorithm that adapts aggregation frequency to resource conditions.

  • Convergence analysis: Theorem 1 bounds the difference between distributed and centralized gradient descents within each local-update interval.The centralized trajectory is synchronized with the distributed model at each interval's beginning.
  • Convergence analysis: The distributed–centralized gap can grow exponentially within an interval when τ > 1 because of the local-gradient divergence.The gap begins after the second local update following global aggregation.
  • Convergence analysis: The convergence proof combines within-interval convergence with the distributed–centralized descent gap to obtain the final bound.The analysis proceeds through a lemma under stated step-size and regularity conditions.
  • Convergence analysis: The bound accommodates arbitrary data distributions by capturing their effect through gradient divergence δ in h(τ).The function h(τ) is non-negative, non-decreasing in τ, and proportional to δ.
  • Convergence analysis: Larger τ or δ increases the optimality gap, whereas larger total local-update count T decreases it.When τ = 1, the gap converges to zero as T grows; when τ > 1, convergence is guaranteed only to a non-zero gap.
  • Algorithmic implication: The proposed algorithm approximately solves the resource-constrained choice of aggregation frequency and total updates, including settings with unknown, time-varying parameters.It estimates resource consumption and other system or model parameters and adjusts τ dynamically.

A. Approximate Solution to (7)

The paper approximates the resource-constrained optimization by replacing the exact loss with its convergence-bound approximation and searching over integer aggregation intervals. The resulting analysis establishes asymptotic and finite-budget properties of the selected interval.

  • Approximate optimization: The optimization minimizes the convergence-bound approximation to F(wf)−F(w∗) over aggregation interval τ and iteration count K under resource constraints.The objective decreases with T, so the largest feasible K is selected for each τ.
  • Approximate optimization: Ignoring floor-rounding yields an approximately optimal K from the largest feasible total-update count under the resource budget.The approximation substitutes a continuous expression for T = Kτ.
  • Theoretical properties: limRmin→∞τ ∗= 1, so unlimited minimum resource budget favors global aggregation after every local update.This follows from the monotonicity of the limiting objective with respect to τ.
  • Theoretical properties: Using τ ∗ from the approximate solution guarantees zero optimality gap as resource budgets and total updates become unbounded.The result uses limRmin→∞τ ∗= 1 together with h(1) = 0.
  • Theoretical properties: For finite budgets, the optimal aggregation interval is bounded above by a finite τ0 determined by model, data, and resource parameters.The proof shows the objective increases beyond τ0.
  • Computational solution: No closed-form solution exists for τ ∗ because the objective combines polynomial and exponential terms, so finite integer search is used.The search is possible because τ ∗ is a positive integer and has a finite range.

B. Adaptive Federated Learning

The adaptive federated-learning controller recomputes the aggregation interval at every global aggregation using updated estimates of resource usage and learning dynamics. It implements this policy through coordinated aggregator and edge-node procedures.

  • Controller design: The controller recomputes τ ∗ at every global aggregation using the most recent system-state estimates.The theoretical results guide each recomputation.
  • Aggregator procedure: The aggregator coordinates model transmission, parameter aggregation, loss evaluation, resource accounting, and termination decisions.Its procedures initialize the model and resource counter, receive node updates, search for τ ∗, and monitor stopping conditions.
  • Parameter estimation: The controller estimates resource costs from node and aggregator measurements, with energy using summed local-update costs and time using maximum node computation time.The estimates are maintained for each resource type.
  • Parameter estimation: It estimates ρ, β, and δ from local and global losses and gradients when the corresponding model parameters are available.Nodes must access local and global parameters at the same iteration, which occurs during global aggregation.
  • Controller design: The search recomputes τ ∗ over integer values up to γ times the current interval and τmax to limit growth under estimation error.The bounded search prevents inaccurate initial estimates from causing τ ∗ to grow too quickly.

2) Recomputing

The implementation separates local updates at edge nodes from aggregation and control at the aggregator, while extending the procedure to stochastic gradients and experimental evaluation. Complexity scales with aggregation count, local updates, nodes, resource types, and the search limit.

  • Edge-node procedure: Each edge node performs τ ∗ local updates between aggregations and sends updated parameters, losses, gradients, and resource estimates to the aggregator.The node procedure repeats local updates until receiving a STOP flag.
  • Aggregation procedure: Global aggregation sends the updated model back to nodes, while the final model wf is selected at the aggregator after evaluating candidate losses.The evaluation of a model can lag by one aggregation round.
  • Complexity: The aggregator's computational complexity is O(K(NM + τmax)), while each edge node has complexity O(T + KM).The terms account for aggregation across N nodes and M resource types, linear search, local updates, and aggregation-step processing.
  • SGD extension: With stochastic gradient descent, each local iteration uses a newly sampled mini-batch, while the first post-aggregation iteration reuses a mini-batch for more stable parameter estimation.The aggregator also coordinates additional evaluation to reduce mini-batch approximation error when selecting wf.
  • Evaluation: Experiments evaluate the algorithm on a five-node networked prototype and simulations ranging from 5 to 500 nodes.The prototype combines Raspberry Pi devices and laptops with heterogeneous computational capabilities.
  • Evaluation: The experiments compare centralized gradient descent, fixed-frequency federated learning, and synchronous distributed gradient descent under matched resource budgets.Both deterministic and stochastic gradient descent are considered.

3) DGD and SGD:

The experiments evaluate adaptive aggregation across models, datasets, node distributions, resource budgets, and synchronous versus asynchronous updates. The proposed approach stays near the optimum under fixed resource budgets, while synchronous updates generally outperform asynchronous ones for heterogeneous, non-uniform settings.

  • Models and Datasets: The evaluation covers DGD and SGD across four models and five datasets, including convex SVM and linear regression and non-convex K-means and CNN tasks.The models and datasets span varied computational and learning settings.
  • Models and Datasets: Data are distributed through cases ranging from random assignment and label-specific nodes to nodes holding the full dataset.These cases represent uniform, non-uniform, and full-information distributions across edge nodes.
  • Loss and Accuracy Values: The adaptive approach operates close to the optimal loss or accuracy across models and cases, whereas a fixed aggregation interval does not work well universally.The proposed solution uses one adaptive operating point per case, while baseline curves use fixed τ values.
  • Loss and Accuracy Values: The proposed approach performs better than or similar to the fixed τ = 10 baseline in all evaluated cases.τ = 10 is selected as an empirically strong non-adaptive baseline across cases.
  • Resource Budget: With larger total time budgets, the proposed τ* generally decreases except when all nodes hold the same dataset.This behavior is consistent with τ* approaching one when the resource budget becomes sufficiently large.
  • Sensitivity of: Asynchronous gradient descent performs much worse than synchronous descent for non-uniform data in Cases 2 and 4, with slower convergence and sudden changes.Across Cases 1–4, the paper therefore uses synchronous gradient descent, while heterogeneous-resource efficiency remains open.

APPENDIX

This appendix establishes intermediate relations for distributed gradient descent by tracking local parameters within aggregation intervals and connecting the τ = 1 case to centralized gradient descent.

  • Distributed vs. Centralized Gradient Descent: When τ = 1, all local parameters equal the global parameter at each iteration.This equality is used to derive the recurrence relation for the global iterate.
  • Distributed vs. Centralized Gradient Descent: Linearity of the gradient operator permits the aggregated distributed update to be rewritten in terms of the global loss gradient.The proof explicitly attributes the equality to gradient linearity.
  • Distributed vs. Centralized Gradient Descent: For τ = 1, the distributed gradient descent recurrence is logically equivalent to centralized gradient descent on the global loss F(w).This is the appendix’s stated conclusion for the one-local-update setting.
  • Local-Update Interval Analysis: Within an aggregation interval, the proof tracks the deviation between each local parameter and an interval reference through induction.The argument uses the absence of global aggregation inside the interval and bounds the deviation with a function g_i.
  • Local-Update Interval Analysis: The interval-bound argument is assembled from initialization at the interval boundary, induction, triangle inequality, and the definition of the reference iterate.These steps establish the stated bounds for each interval.

C. Proof of Lemma 2

The proof of Lemma 2 defines interval-wise loss gaps, uses smoothness and convexity to bound their evolution, and aggregates those bounds across global-aggregation intervals.

  • Proof of Lemma 2: β-smoothness, convexity, Cauchy–Schwarz, and the interval deviation bounds are combined to control successive values of θ[k](t).The proof introduces intermediate lemmas before substituting these inequalities into the interval recurrence.
  • Proof of Lemma 2: For interval [k], θ[k](t) is defined as the global loss gap F(v[k](t)) − F(w*) over (k − 1)τ ≤ t ≤ kτ.This quantity measures the interval reference iterate’s loss relative to the optimal parameter.
  • Proof of Lemma 2: The final bound combines the initial and terminal loss-gap inequalities with the convergence lower bound for gradient descent.The proof also invokes the condition ωη(1 − βη/2) − ρh(τ)τε^2 > 0.
  • Proof of Lemma 2: Summing the interval inequalities over k = 1, 2, ..., K yields a bound on the cumulative loss-gap terms.The relation v[k+1](kτ) = w(kτ) connects interval endpoints to the global iterate.
  • Proof of Lemma 2: The proof assumes the loss gap remains at least ε and uses monotonicity to preserve that lower bound throughout each interval.The same assumption is also applied at the terminal iterate.

D. Proof of Proposition 2

The proof of Proposition 2 shows that the objective governing aggregation frequency increases beyond a finite threshold, implying an upper bound on the optimal aggregation interval.

  • Proof of Proposition 2: The proof first establishes that the threshold τ0 is finite by considering the cases defining ν and bounding the relevant resource-dependent terms.The cases are combined to conclude finiteness of τ0.
  • Proof of Proposition 2: After defining c and b from the index ν, the proof rewrites G(τ) for τ > τ0.This reduction prepares the monotonicity argument for the two component functions.
  • Proof of Proposition 2: For τ > τ0, both H1(τ) and H2(τ) are shown to increase with τ using bounds involving η and β.The proof uses logarithmic and derivative inequalities to establish the required monotonicity.
  • Proof of Proposition 2: Because G(τ) increases for τ > τ0, the optimal aggregation interval satisfies τ* ≤ τ0.This is the proposition’s stated conclusion after the monotonicity proof.

E. Parameters for Generating Resource Consumptions in Simulation

This section specifies how simulation resource consumptions are generated for distributed DGD, distributed SGD, and centralized SGD. The parameters are based on prototype measurements using the SVM model, with distributions chosen according to each case’s data-processing or mini-batch characteristics.

  • Simulation resource-consumption parameters are derived from prototype measurements while running the SVM model.The reported mean and standard deviation values are used for random resource-consumption generation.
  • Tables III, IV, and V report the resource-consumption parameters for distributed DGD, distributed SGD, and centralized SGD, respectively.
  • Distributed DGD uses different resource-consumption distributions across cases because Case 3 processes a different number of data samples.
  • Distributed SGD uses the same resource-consumption distribution across all cases because the mini-batch size remains unchanged.

G. Additional Results on Varying Total Time Budget

The additional results examine SVM behavior under different global aggregation times and total time budgets, including instantaneous results for SVM trained with SGD using the proposed algorithm.

  • Figure 12 reports loss function values and classification accuracy for SVM trained with DGD under different global aggregation times.
  • Figure 13 reports loss function values and classification accuracy for SVM trained with DGD under different total time budgets.
  • Figure 14 presents instantaneous results for SVM trained with SGD using the proposed algorithm.
Loading 1804.05271v3…