Source-linked AI summary
Client and Training Data Selection for Computationally Efficient Synchronized Federated Learning
Muzaffer Citir, Hiroki Nishikawa, Sangyoung Park
TL;DR
The paper addresses slow synchronized federated learning under stragglers and non-iid client data. It jointly selects clients and training data using timing and class-balance considerations. The authors report better convergence than prior selection schemes and higher tail-class accuracy than the baselines.
Problem
Stragglers can delay synchronized aggregation, while non-iid client data can leave classes underrepresented and undermine accuracy.
Source: §I · p. 1Method
The paper jointly selects clients and training data, using probabilistic timing estimates and per-class allocation to maximize expected training data contribution while balancing classes.
Source: §I · pp. 1–2, §IV · p. 5Results
The method achieves better convergence than prior selection schemes; tail-class accuracy is 15.3% versus probPart's 6.8% and 3.5% for MinCost.
Source: A. Performance of Data Allocation… · p. 6, §VI · p. 7Takeaways & Limitations
Explicitly balancing the collective class distribution in each round keeps accuracy more consistent across classes and more equally shared among them.
Source: A. Performance of Data Allocation… · p. 6
Abstract
from arXiv · showhide
Federated learning (FL) is a promising paradigm of machine learning, which preserves user privacy by enabling learning without sharing raw data with a cloud server. Straggling clients have been a problem for FL as they introduce delays in aggregating the local models and hence, the convergence of the global model. Therefore, it is important to have a mechanism that ensures fast convergence of the global model as well as good FL participation rate. Another issue for the convergence of a model in FL is the non-independent and identically distributed (non-iid) data across the clients. Prior approaches based on probabilistic client selection do not work well under non-iid data especially when the number of clients is small. We show scenarios where such approaches fail and propose a joint client-training data selection algorithm for fast convergence of FL models. Our experiments on CIFAR-100 dataset show that convergence of the FL model can be significantly improved over prior works that can consider non-iid data and heterogeneous computation and higher model accuracy.
I. INTRODUCTION
Synchronous FL faces deadline delays from stragglers and accuracy challenges from non-iid data. The paper proposes probabilistic joint client and training-data selection that accounts for computation and class balance.
I. INTRODUCTION
- Synchronous FL can miss deadlines because of stragglers, while non-iid data can undermine accuracy when some classes are underrepresented on resource-constrained devices.Fig. 1 contrasts a deadline miss with avoiding it through proper data allocation.Source: §I · p. 1, Figure 1 · p. 2
- The proposed algorithm jointly selects clients and training data, using probabilistic estimates to maximize expected training data contribution while balancing class distributions.It targets per-iteration timing constraints despite uncertainty in training completion and interruptions.Source: §I · pp. 1–2
- The paper examines how training-dataset size and class distribution affect training times and model accuracy.Source: §I · p. 2
II. RELATED WORK
Prior FL work addresses resource allocation, scheduling, and latency, but the paper distinguishes its approach by combining non-iid-aware class balancing with deterministic selection that does not wait for local training to finish.
II. RELATED WORK
- Several resource-optimization systems address computation, communication, or device configuration, but assume iid client data, –.Source: §II · p. 2
- Other work considers non-iid scheduling and communication,, latency reduction,, or loss-based client selection that requires local training first.The loss-based approach can spend computation on a client that is not selected for that round.Source: §II · p. 2
- Workload-distribution and probability-based methods target computational time, accuracy, or energy –.Source: §II · p. 2
- The authors distinguish their method by balancing class distributions under non-iid data, selecting without completed local training, and deterministically choosing helpful clients.Source: §II · p. 2
A. Overall FL Architecture
The system has a cloud server and edge devices with local datasets, from which devices use deadline-constrained training subsets. Each FL round broadcasts a global model, performs local updates, and aggregates timely uploads.
A. Overall FL Architecture
- The system comprises one cloud server and M edge devices, each with a local dataset D_i and a training subset d_i used to meet the iteration deadline.Source: A. Overall FL Architecture · p. 2
- The paper assumes devices know their dataset sizes and class information.Source: A. Overall FL Architecture · p. 3
- Each round broadcasts the global model to randomly selected devices, which perform local gradient-descent updates and upload by the deadline; the server aggregates timely uploads.Updates from devices that miss the deadline are discarded.Source: A. Overall FL Architecture · p. 3
B. Probabilistic Modeling of Time-sensitive FL
The model treats each round’s total latency as computation, interruption, and communication components, then estimates whether training meets a deadline. Measurements on CIFAR-10 support the computation-latency model while noting it may not capture every delay aspect.
B. Probabilistic Modeling of Time-sensitive FL
- Total latency combines computation, interruption, and communication, whose components are approximated as independent because training and communication latency are weakly dependent.This independence assumption yields the cumulative deadline-probability model.Source: B. Probabilistic Modeling of… · pp. 3–4
- Local computation latency follows a shifted exponential model, with minimum time a_i d_i and parameters reflecting device capacity and computation fluctuation.The parameters depend on edge-device performance and FL application characteristics.Source: B. Probabilistic Modeling of… · p. 3
- 660 CIFAR-10 training runs showed a linear relationship between dataset size and training time, while a 120-run histogram roughly followed an exponential distribution.Fig. 2 plots image count against measured seconds, and Fig. 3 shows the training-time distribution for 5×10^3 images; the model may not mimic every aspect of computation delay.Source: B. Probabilistic Modeling of… · p. 3, Figure 2 · p. 3, Figure 3 · p. 3
- Interruptions from preempting tasks are modeled with an M/M/1 queue, using λ_intr as the interruption rate and μ_intr as the service rate.The service rate is constrained to be at least the interruption rate.Source: B. Probabilistic Modeling of… · p. 3
- Communication latency is modeled as Gaussian, with its mean and standard deviation used to characterize the component.Source: B. Probabilistic Modeling of… · p. 4
C. Problem Formulation
The formulation optimizes each device’s training-data size against the probability of meeting a deadline. It defines a latency–accuracy tradeoff and assumes server-side aggregation latency is negligible.
C. Problem Formulation
- The central optimization chooses each device’s dataset size to improve learning while satisfying a probabilistic deadline constraint.Training utility is the expected dataset size weighted by the probability total latency meets the deadline.Source: C. Problem Formulation · p. 4
- The parameter α represents the accuracy–latency tradeoff, while ε sets the acceptable probability of exceeding the deadline for a real-time application.Source: C. Problem Formulation · p. 4
- The formulation assumes that the server’s model-aggregation latency is negligible because of its stronger computation capability.Source: C. Problem Formulation · p. 4
- The algorithm’s stated inputs include client datasets and class distributions, device and interruption parameters, and average image-use counts; its output includes selected clients and per-class training-data sizes.Source: C. Problem Formulation · p. 4
IV. JOINT CLIENT AND DATA SELECTION ALGORITHM
The algorithm jointly selects clients and class-balanced training data, accounting for data reuse and collective class coverage. It assumes larger datasets and unseen data aid convergence and that class imbalance harms underrepresented-class accuracy.
IV. JOINT CLIENT AND DATA SELECTION ALGORITHM
- The algorithm rests on assumptions that larger training datasets and unseen data contribute to faster convergence and higher accuracy, while unbalanced class distributions reduce underrepresented-class test accuracy.Repeatedly selecting fast clients can reuse their local data, motivating attention to image-use history.Source: §IV · p. 4
- The server uses client data, class counts, computation and interruption parameters, and image-use averages to produce selected clients, per-class sample sizes, and updated use counts.Source: §IV · p. 4
- For each client, the algorithm chooses a dataset size maximizing expected usable data, then assigns samples as evenly across classes as available data permits.If a class has fewer than its equal share, all its images are used and the remaining classes receive equal allocations.Source: §IV · p. 5
- Clients are greedily selected by a weighted usefulness metric combining dataset size discounted by prior image use, need for the least-represented class, and warm-up class coverage.The prior-use term discourages repeatedly choosing clients whose data has already been used often.Source: §IV · p. 5
- After selection, actual training samples are drawn randomly within each client’s per-class allocation, and the image-use averages are carried into later rounds.The greedy loop updates client usefulness as the selected clients’ data and class coverage accumulate.Source: §IV · p. 5
V. EXPERIMENTS
The experiments evaluate the scheduling algorithm on CIFAR-100 with MobileNetV2 and compare it with MinCost and probPart baselines. The supplied passages describe the evaluation setup but do not report comparative outcomes.
V. EXPERIMENTS
- The comparison includes MinCost and probPart based on, both selected as baselines able to address non-iid data and computation heterogeneity.Source: §V · p. 5
- MinCost assigns a fixed total training dataset D with α controlling non-iid-aware allocation, while the probPart variant sets client selection probability proportional to G_i.The probPart G_i values are calculated by training on a small data batch.Source: §V · p. 5
- Evaluation uses CIFAR-100 with 50,000 training images and 10,000 test images, and a 3.5M-parameter MobileNetV2 model trained with AdamW and cross-entropy loss.The federated system uses no data compression.Source: §V · p. 5
A. Performance of Data Allocation Algorithm
The proposed method converges better than MinCost and probPart by jointly addressing computation heterogeneity and class distribution. It also improves accuracy on under-represented CIFAR-100 classes relative to both baselines.
A. Performance of Data Allocation Algorithm
- The evaluation assumes 50 clients and selects 10 per FL round; it compares absolute training times rather than iteration counts, while synchronous baselines wait for the slowest device before aggregation.The setup uses label-skewed Dirichlet partitioning with α = 0.3; the baselines use a predefined training-data size of 500.Source: A. Performance of Data Allocation… · pp. 5–6
- The proposed algorithm outperforms MinCost and probPart in convergence, processing more training data per unit time while reducing client slack.Fig. 4 compares test accuracy over time; the paper attributes the improvement to selecting computationally capable clients without repeatedly reusing their data and adjusting training-data size to limit slack.Source: Figure 4 · p. 6, A. Performance of Data Allocation… · p. 6
- Explicitly balancing class distribution distinguishes the proposed method from MinCost’s class-presence criterion and probPart’s random client selection.The paper says random selection does not guarantee every class is represented each iteration, while MinCost may include too few examples of a represented class.Source: A. Performance of Data Allocation… · p. 6
- 15.3% versus 6.8% tail-class accuracy for the proposed method and probPart, respectively; MinCost achieves 3.5%.Tail-class accuracy is the mean for the 10 lowest-accuracy classes; the proposed method also has the lowest coefficient of variation and Gini coefficient.Source: Table II · p. 6, A. Performance of Data Allocation… · p. 6
- The proposed method has the lowest coefficient of variation and Gini, indicating more uniform and equitable per-class accuracy than the baselines.Lower coefficient of variation means more consistent per-class accuracy; a Gini of 0 denotes perfect equality.Source: A. Performance of Data Allocation… · p. 6, Table II · p. 6
B. Ablation and Sensitivity Analysis of the Usefulness Metric
The ablation study finds that the freshness penalty contributes most to the usefulness metric’s performance, while its other terms provide smaller complementary gains. The ordering of variants remains consistent across the two tested non-iid severities.
B. Ablation and Sensitivity Analysis of the Usefulness Metric
- Disabling the freshness penalty leaves accuracy well below every other variant at both severities, with a deeper degradation at α = 0.1.Fig. 5 reports test accuracy over time for α = 0.3 and α = 0.1; variants disable one usefulness-metric component at a time.Source: B. Ablation and Sensitivity Analysis… · p. 6, Figure 5 · p. 7
- The dataset-size factor, class-balance term w2, and coverage term w3 each provide smaller complementary gains, and the full metric attains the highest accuracy.The w1 term’s freshness penalty and dataset-size preference are ablated separately.Source: B. Ablation and Sensitivity Analysis… · p. 6
- Variant ordering is preserved across α = 0.3 and α = 0.1, suggesting the design generalizes across these tested degrees of non-iidness without one weight dominating.The ablations use a single random seed under the same deadline-based, equal-time protocol as Fig. 4.Source: B. Ablation and Sensitivity Analysis… · p. 6, Figure 5 · p. 7
VI. CONCLUSIONS
The paper concludes that its joint client and training-data selection algorithm improves FL convergence by balancing dataset size, class distribution, and data staleness. The experiments and proposed follow-up work leave specific modeling and evaluation extensions open.
VI. CONCLUSIONS
- The joint client and training-data selection algorithm achieves better FL convergence than other selection schemes by addressing computation heterogeneity and non-iid data.The approach estimates training times and balances training-data size, class distribution per iteration, and data staleness.Source: §VI · p. 7
- More concrete application-specific interruption models and dynamic aspects of FL applications remain future work.Source: §VI · p. 7
- The current experiments use one setting of 10 selected clients out of 50; planned extensions include other client-pool distributions, selection ratios, and joint weight combinations.Source: §VI · p. 7