PaperlayerView exact revision on arXiv

Source-linked AI summary

Device Sampling for Heterogeneous Federated Learning: Theory, Algorithms, and Implementation

Su Wang, Mengyuan Lee, Seyyedali Hosseinalipour, Roberto Morabito, Mung Chiang, Christopher G. Brinton

arXiv:2101.00787v1cs.NIcs.DCcs.LG

TL;DR

FedL must contend with heterogeneous device resources and overlapping local data, which can add processing overhead. This paper jointly optimizes device sampling and D2D offloading; experiments report gains in accuracy, convergence speed, and resource utilization against baselines.

  • Problem

    FedL must account for heterogeneous device resources and overlapping local data, since processing similar data at multiple devices adds overhead.

    Source: §I · p. 1

  • Method

    The paper jointly optimizes device sampling and D2D data offloading, using estimated data dissimilarities to guide transfers among devices.

    Source: §I · p. 1

  • Results

    The joint method exceeds baseline performances in model accuracy, convergence speed, and resource utilization; convergence is on average 40% faster for MNIST and 50% for F-MNIST.

    Source: 2) Model convergence speed · p. 8, 3) Resource utilization · p. 9

  • Takeaways & Limitations

    Implementations using real-world datasets and IoT testbed measurements improve datapoints processed, training speed, and model accuracy compared with several algorithms, including all-device FedL.

    Source: §VI · p. 9

Abstract

from arXiv · show

The conventional federated learning (FedL) architecture distributes machine learning (ML) across worker devices by having them train local models that are periodically aggregated by a server. FedL ignores two important characteristics of contemporary wireless networks, however: (i) the network may contain heterogeneous communication/computation resources, while (ii) there may be significant overlaps in devices' local data distributions. In this work, we develop a novel optimization methodology that jointly accounts for these factors via intelligent device sampling complemented by device-to-device (D2D) offloading. Our optimization aims to select the best combination of sampled nodes and data offloading configuration to maximize FedL training accuracy subject to realistic constraints on the network topology and device capabilities. Theoretical analysis of the D2D offloading subproblem leads to new FedL convergence bounds and an efficient sequential convex optimizer. Using this result, we develop a sampling methodology based on graph convolutional networks (GCNs) which learns the relationship between network attributes, sampled nodes, and resulting offloading that maximizes FedL accuracy. Through evaluation on real-world datasets and network measurements from our IoT testbed, we find that our methodology while sampling less than 5% of all devices outperforms conventional FedL substantially both in terms of trained model accuracy and required resource utilization.

I. INTRODUCTION

The introduction motivates jointly choosing FedL participants and D2D data offloading to address heterogeneous device resources and overlapping local data. It contrasts this approach with prior sampling strategies and illustrates why compute, data similarity, and offloading connectivity matter together.

I. INTRODUCTION

  • Conventional FedL has devices train locally and periodically aggregate model parameters at a server, but independent processing and upstream communication become problematic at large scale.The introduction identifies networks with millions of heterogeneous wireless devices as the scaling context.Source: §I · p. 1
  • Overlapping device data can add FedL processing overhead, while centralized training may be infeasible because of transfer delays and privacy concerns.The introduction points to D2D offloading as a way to move processing from resource-poor to resource-rich devices.Source: §I · p. 1
  • The proposed methodology jointly selects training devices and offloads data based on estimated data dissimilarities, while exempting devices with privacy concerns.The authors report superior model performance to conventional FedL with reduced network resource use.Source: §I · p. 1

A. Related Work

  • Prior device-sampling work often uses static or uniform selection, whereas this work adapts sampling to resource heterogeneity and local-data similarity and jointly optimizes sampling with D2D offloading.The paper distinguishes its resource-efficiency objective from device fairness and transfer-learning objectives.Source: A. Related Work · pp. 1–2

B. Motivating Toy Example

  • In the five-car example, selecting the most capable cars can be inefficient when their data are similar, while selecting the least-similar cars can sacrifice processing capability.The example motivates sampling and offloading together: sampling car C can combine its processing capability with data from neighboring cars D and E.Source: B. Motivating Toy Example · p. 2

C. Outline and Summary of Contributions

The paper combines device sampling and D2D data offloading to improve federated learning under network and device constraints. Its system model captures heterogeneous resources, transfer opportunities, data similarity, and distributed model updates.

C. Outline and Summary of Contributions

  • The paper formulates joint sampling and D2D offloading to maximize FedL accuracy under realistic network resource constraints.Theoretical offloading analysis yields a convergence bound and a sequential convex optimizer; a GCN learns sampling strategies from network properties, offloading, and expected accuracy.Source: C. Outline and Summary of… · p. 2
  • Experiments using real-world ML tasks and IoT testbed measurements report higher accuracy than all-device FedL with reduced processing requirements.The supplied passage does not specify numerical values for these comparisons.Source: C. Outline and Summary of… · p. 2

A. Edge Device Model

  • The system model represents devices with time-varying processing capacities, processing costs, transmit budgets, and transmission costs.These quantities reflect heterogeneous resources such as CPU, memory, power, bandwidth, and interference.Source: §II · p. 2, A. Edge Device Model · p. 2
  • Unsampled devices may still contribute their collected datasets through local D2D transfers to sampled training devices.The unsampled set can include stragglers with insufficient processing capacity to participate directly.Source: A. Edge Device Model · p. 3

B. Network Topology and Data Similarity Model

  • A time-varying D2D graph represents feasible transfers, while a similarity matrix estimates overlap between devices’ datasets.Higher similarity implies less offloading benefit; initial similarity estimates can use random data samples, and connectivity and similarity are combined in a matrix.Source: B. Network Topology and Data… · p. 3

C. Distributed Machine Learning Model

  • Sampled devices update local models by gradient descent, and the server periodically aggregates them using weights based on accumulated local data.The global loss is defined over data across the network, not only the sampled devices.Source: C. Distributed Machine Learning Model · p. 3

D. Joint Sampling and Offloading Optimization

The optimization jointly chooses a fixed-size set of participating devices and data transfers from unsampled to sampled devices. It models similarity-aware offloading and enforces network, device, and sampling constraints.

D. Joint Sampling and Offloading Optimization

  • The optimization selects a device set of size S and offloading ratios to minimize the time-averaged loss associated with the sampled devices’ global model.The binary vector x represents device selection, and Φ(t) represents offloading ratios.Source: D. Joint Sampling and Offloading… · p. 3
  • Constraints enforce device receive and processing capacities, transmission budgets, local dataset limits, single-hop transfers, and the sampling budget.Transfers are restricted to feasible D2D neighbors and from unsampled to sampled devices.Source: D. Joint Sampling and Offloading… · p. 4
  • Offloading transfers data from unsampled devices to sampled devices, with estimated overlap reducing the amount treated as useful data.Similarity estimates are updated according to transfers; sending all data from one device to another raises their estimated similarity to 1 and prevents further transfers on that link.Source: D. Joint Sampling and Offloading… · p. 4
  • The problem is difficult because deep-learning loss is generally intractable to model and coupled sampling and offloading form an NP-hard mixed-integer problem.The proposed approach first optimizes offloading for fixed sampling, then uses a GCN to learn relationships among network properties, sampling, offloading, and accuracy.Source: D. Joint Sampling and Offloading… · p. 4

III. DEVELOPING THE OFFLOADING OPTIMIZER

The offloading analysis uses a hypothetical centralized training process and defines the difference between gradients on full-network and sampled data. Its stated assumptions include convexity, Lipschitz continuity, and smoothness.

III. DEVELOPING THE OFFLOADING OPTIMIZER

  • The offloading analysis is intended to approximate its objective and produce a solver for the resulting optimization.The section studies the offloading subproblem; the stated analysis leads to an efficient approximation and solver.Source: §III · p. 4

A. Definitions and Assumptions

  • A hypothetical centralized model synchronizes with the federated global model at aggregation times and otherwise trains on the full network dataset.This process is introduced to support the theoretical analysis of federated learning.Source: A. Definitions and Assumptions · p. 4
  • The analysis defines the instantaneous difference between the gradient on all network data and the gradient on sampled data.It also defines δ_i(t) as an upper bound relating the gradient on device i’s data to that on the full network dataset.Source: A. Definitions and Assumptions · p. 4
  • The stated loss assumptions are convexity, L-Lipschitz continuity, and β-smoothness, while the authors report practical improvements for neural networks that violate them.The passage says the assumptions are common in prior work.Source: A. Definitions and Assumptions · p. 4

B. Upper Bound on Convergence

The section bounds the gap between sampled FedL and centralized learning, then relates that gap to sampled-device data quantities and the loss gap to the optimum. The analysis assumes offloaded data is transferred only once and retained by recipients.

C. Upper Bound on Convergence

  • The analysis assumes each device offloads the same data only once and recipients retain received data, keeping the optimal global model parameters constant over time.Source: B. Upper Bound on Convergence · p. 4
  • Theorem 1 bounds the parameter difference between sampled FedL and centralized learning within each local update period, assuming η ≤ β^-1.The bound concerns times before the k-th global aggregation.Source: B. Upper Bound on Convergence · p. 4
  • The parameter-gap bound is connected through δS(t) to the amount of data at sampled devices.The method first bounds the gradient discrepancy δi(t) and its weighted aggregate δS(t).Source: B. Upper Bound on Convergence · p. 5
  • The corollary bounds the loss induced by sampled FedL relative to the optimal model during a local update period.The bound is expressed using the accumulated discrepancy term ˆΥ(ˆK).Source: B. Upper Bound on Convergence · p. 5
  • A first-two-term Taylor approximation is used because g(ˆΥ(ˆK)) is non-convex in the data quantities through ˆΥ(ˆK).The authors state that ˆΥ(ˆK) is much less than 1.Source: B. Upper Bound on Convergence · p. 5

C. Offloading as a Sequential Convex Optimization

For a fixed sampling choice, the offloading problem is reformulated using gradient and data approximations. Sequential convex optimization makes it tractable, while gradients unavailable between global aggregations are estimated from the latest observed gradients.

C. Offloading as a Sequential Convex Optimization

  • The approximated objective is expressed in terms of sampled-device data quantities, with the offloading problem constrained by the stated network and allocation conditions.Source: C. Offloading as a Sequential Convex… · p. 5
  • Existing sum-of-ratios solvers handle roughly ten ratios, motivating an approximation of δS(t) by the sum of individual δi(t) terms for larger networks.The text notes contemporary networks may have hundreds of edge devices.Source: C. Offloading as a Sequential Convex… · p. 5
  • With ∇F(t) known, both objective terms are convex in the offloading variables, and the constraints are affine at each time instance, enabling sequential convex optimization.The implementation uses CVXPY.Source: C. Offloading as a Sequential Convex… · pp. 5–6
  • Real-time gradients are unknown between global aggregations, so the method approximates them from the most recently observed gradients and assumes linear decrease over time.The scaling factor is readjusted after each global aggregation.Source: C. Offloading as a Sequential Convex… · pp. 5–6, Figure 4 · p. 6

IV. SMART DEVICE SAMPLING WITH D2D OFFLOADING

The section couples sampling decisions with the offloading solution, then lays out a GCN rationale, network-characteristic training procedure, and iterative sample-set selection.

IV. SMART DEVICE SAMPLING WITH D2D OFFLOADING

  • Sampling decisions must be coupled with the offloading solution.Source: §IV · p. 6
  • The section first explains the rationale for its GCN-based approach.Source: §IV · p. 6
  • It then details a training procedure that encodes network characteristics and develops an iterative procedure for selecting the sample set.Source: §IV · p. 6

A. Rationale and Overview of GCN Sampling Approach

The section motivates GCN-based sampling as a way to learn from network structure and data relationships, then describes its architecture and training. On MNIST, the caption reports a wide accuracy margin for smart sampling with offloading when S > 3.

A. Rationale and Overview of GCN Sampling Approach

  • Device value is difficult to quantify for knapsack-style sampling because it depends on the loss function, gradient descent, and D2D relationships.Source: A. Rationale and Overview of GCN… · p. 6
  • Active filtering of a GCN models the relationship between network characteristics, the sampling set, and resulting FedL model quality.Graph convolution layers capture connections among nodes in different neighborhoods.Source: A. Rationale and Overview of GCN… · p. 6
  • The GCN-branch addresses multiple strong sampling candidates by incorporating offloading into training and mapping outputs to a set using connectivity and data similarity.A node that performs poorly alone may still have high processing capacity and useful links to unsampled nodes with data and transfer capacity.Source: A. Rationale and Overview of GCN… · p. 6

B. GCN Architecture and Training Procedure

  • The GCN uses node features and an augmented connectivity-similarity matrix as inputs, then applies two graph-convolution layers with ReLU between them.Log-softmax converts the output into per-node probabilities of belonging to the sampled set.Source: B. GCN Architecture and Training… · p. 6
  • For S > 3, smart sampling with offloading consistently achieves a wide MNIST testing-accuracy margin over the compared schemes.Figure 6 compares sampling with and without offloading against FedL using all nodes, across sampled sizes and node counts.Source: Figure 6 · p. 7
  • Training examples pair network realizations with candidate sampling allocations whose offloading solutions and resulting FedL losses identify the minimum-loss target set.Source: B. GCN Architecture and Training… · p. 7
  • After training on tolerable network sizes, the learned graph-convolution weights can be applied to a target network of arbitrary size.The paper says experiments verify this network-size independence.Source: B. GCN Architecture and Training… · p. 7

C. Offloading-Aware Smart Device Sampling

The sampling procedure uses a GCN to choose devices based on data quantity, sampling probability, and dissimilarity, with offloading scheduled afterward. Experiments use measured IoT resources and synthetic overlapping, non-i.i.d. local datasets.

C. Offloading-Aware Smart Device Sampling

  • The sampling GCN-branch algorithm first selects a high-probability device from the top 2% in initial data quantity, then recursively chooses high-probability neighbors with dissimilar data.The selected set is formed at FedL initialization, and offloading is scheduled afterward using the solver for the offloading subproblem.Source: C. Offloading-Aware Smart Device… · p. 7
  • On F-MNIST, smart sampling with offloading has a wide accuracy improvement over smart sampling without offloading, consistent with MNIST.The comparison emphasizes jointly considering sampling and offloading for FedL optimization.Source: Figure 7 · p. 7
  • The sequential convex offloading optimizer is embedded within GCN-based sampling, which generates the sampled set and offloading configuration for the target network.The GCN is trained on sample network realizations before application to the target network.Source: C. Offloading-Aware Smart Device… · p. 7, 2) Datasets and large-scale network… · p. 8

1) Network characteristics via wireless testbed:

  • The IoT testbed uses Jetson Nano, Coral Dev Board TPU, and UP Squared AI Edge boards; measured compute, power, and WiFi offloading costs inform model parameters.D2D bandwidth is limited to 1, 6, or 9 Mbps to model external tasks; the dedicated WiFi links saturated at 12 Mbps.Source: 1) Network characteristics via… · pp. 7–8
  • Table I compares global aggregations needed to reach 85% MNIST and 65% F-MNIST accuracy at S = 6 across varying network sizes, and reports the joint method as fastest.The caption states that smart sampling with offloading consistently obtains the fastest training time.Source: Table I · p. 8

2) Datasets and large-scale network generation:

  • Experiments use MNIST and F-MNIST with a two-convolution-layer CNN and synthetic Erdős–Rényi networks of 100–800 devices.Local datasets are overlapping and non-i.i.d., with each device sampling data from three labels; initial data quantities follow a normal distribution.Source: 2) Datasets and large-scale network… · p. 8
  • The GCN is trained on ten-device networks with sampling budgets of 3–6 and thousands of training samples, then its weights are reused on larger networks.Separate graph convolutional layer weights are saved for each sampling budget.Source: 2) Datasets and large-scale network… · p. 8

B. Results and Discussion

Across the reported experiments, joint sampling and offloading outperform baseline methods in model accuracy, convergence speed, and resource utilization. The gains include higher accuracy while sampling at most 5% of devices and reduced data processing to reach a reference accuracy.

B. Results and Discussion

  • The experiments compare smart, random, and heuristic sampling, each with and without offloading, against all-device FedL without offloading.Random sampling averages five device combinations; heuristic sampling chooses the highest-capacity devices, and its offloading greedily maximizes received data points.Source: B. Results and Discussion · p. 8

3) Resource utilization:

  • 40% fewer datapoints on average are processed as the target accuracy rises; Fig. 8 compares schemes at a 60% reference accuracy.Smart sampling, with or without offloading, outperforms the other schemes in all reported resource-utilization cases.Source: Figure 8 · p. 8, 3) Resource utilization · p. 9

1) Model accuracy:

  • At most 5% of devices, smart sampling with offloading beats every method except all-device FedL in two cases; without offloading, gains exceed 20% on MNIST and 10% on F-MNIST.Smart offloading improves accuracy over no offloading in most cases, while differences are smaller for heuristic and random sampling.Source: 1) Model accuracy · p. 8

2) Model convergence speed:

  • 40% for MNIST and 50% for F-MNIST faster training speeds on average; without offloading, several baseline cases fail to reach the specified accuracy threshold.The comparison counts global aggregations needed to reach 85% of all-device FedL accuracy on MNIST and 65% on F-MNIST, with S = 6 and N = 600, 700, or 800.Source: 2) Model convergence speed · p. 8

B. Results and Discussion

  • The joint optimization method exceeds baseline performances in model accuracy, convergence speed, and resource utilization, including comparisons with FedL using all devices.The conclusion reports significant improvements in datapoints processed, training speed, and model accuracy compared with several algorithms, including all-device FedL.Source: 3) Resource utilization · p. 9, §VI · p. 9

APPENDIX A

The appendix bounds the distance between sampled and full-data model updates through smoothness, triangle-inequality, and prior-lemma arguments. It then rearranges the bound toward the referenced convergence result.

APPENDIX A

  • The update difference is analyzed using the sampled-data and full-data gradient steps, with re-synchronization setting the model distance to zero at aggregation times.The appendix expresses the distance between updates in terms of the intervals between re-synchronizations.Source: Appendix A · p. 9
  • The derivation simplifies an intermediate bound using gradient expansion, β-smoothness, the triangle inequality, Lemma 3 from, and the definition of δS(t).The appendix then rearranges the resulting inequality.Source: Appendix A · p. 9
  • The proof defines excess losses relative to the optimum and uses positivity of the resulting bound to derive the referenced convergence inequality.It combines prior results and assumptions from [16], then takes a reciprocal to obtain equation (22).Source: Appendix A · p. 9

APPENDIX C

The appendix treats a local-data gradient as an average over device samples, then applies the central limit theorem to relate it to the full-data mean gradient. It uses this framing to upper-bound an earlier expression.

APPENDIX C

  • The local-data gradient is viewed as an average over device samples from a distribution whose mean is the full-data gradient, enabling an upper bound on equation (24).The stated upper-bound step uses the definition in equation (1), followed by the triangle inequality.Source: Appendix C · p. 9
Loading 2101.00787v1…