PaperlayerView exact revision on arXiv

Source-linked AI summary

FedBalancer: Data and Pace Control for Efficient Federated Learning on Heterogeneous Clients

Jaemin Shin, Yuanchun Li, Yunxin Liu, Sung-Ju Lee

arXiv:2201.01601v2cs.LG

TL;DR

Heterogeneous, private client data make equal treatment of all samples costly and slow in federated learning. FedBalancer prioritizes informative samples and adapts round deadlines using client-server coordination. Across five datasets from three domains, it improves time-to-accuracy and accuracy over existing deadline-configuration methods.

  • Problem

    Heterogeneous private client data make equal treatment of all samples waste local computation and slow global learning.

    Source: §1 · pp. 1–2

  • Method

    FedBalancer selects informative client samples using a privacy-preserving loss-threshold coordination scheme and adaptively controls deadlines as client training data vary.

    Source: §1 · p. 2

  • Results

    1.20∼4.48× better time-to-accuracy and 1.1%∼5.0% higher accuracy: FedBalancer outperformed existing FL algorithms with deadline configuration methods across five datasets from three domains.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    FedBalancer also improves time-to-accuracy performance when applied jointly with three orthogonal FL algorithms.

    Source: §1 · p. 2

    FedBalancer may perform worse on FL tasks with noisy data because its sample-selection module is likely to select noisy, high-loss samples.

    Source: §5 · p. 12

Abstract

from arXiv · show

Federated Learning (FL) trains a machine learning model on distributed clients without exposing individual data. Unlike centralized training that is usually based on carefully-organized data, FL deals with on-device data that are often unfiltered and imbalanced. As a result, conventional FL training protocol that treats all data equally leads to a waste of local computational resources and slows down the global learning process. To this end, we propose FedBalancer, a systematic FL framework that actively selects clients' training samples. Our sample selection strategy prioritizes more "informative" data while respecting privacy and computational capabilities of clients. To better utilize the sample selection to speed up global training, we further introduce an adaptive deadline control scheme that predicts the optimal deadline for each round with varying client training data. Compared with existing FL algorithms with deadline configuration methods, our evaluation on five datasets from three different domains shows that FedBalancer improves the time-to-accuracy performance by 1.20~4.48x while improving the model accuracy by 1.1~5.0%. We also show that FedBalancer is readily applicable to other FL approaches by demonstrating that FedBalancer improves the convergence speed and accuracy when operating jointly with three different FL algorithms.

1 INTRODUCTION

Federated learning’s heterogeneous private data and client hardware make efficient time-to-accuracy training difficult. FedBalancer selects informative samples while controlling round deadlines, and the paper reports faster training with improved accuracy across datasets and FL approaches.

1 INTRODUCTION

  • 1.20∼4.48×: time-to-accuracy is a key FL objective because training consumes substantial computation and network resources on edge devices.Faster convergence is useful for prototyping models and for service providers who frequently update models.Source: §1 · pp. 1–2
  • Treating all client data equally can waste computation and slow convergence when data are heterogeneous and private data cannot be shared for centralized importance sampling.The preliminary study found informative samples decreased from 93.2% to 20% as FL progressed; low-end devices may fail to send updates after training many unimportant samples.Source: §1 · pp. 1–2
  • FedBalancer prioritizes informative client samples to use computation efficiently and help low-end devices contribute within the round deadline.Sample selection is designed to avoid extra forward or backward passes for measuring sample utility.Source: §1 · p. 2
  • FedBalancer coordinates clients and server around a loss threshold, exposing differentially private statistics rather than sample-level information, and uses deadline efficiency to guide deadline selection.Deadline efficiency measures round-completed clients per unit time.Source: §1 · p. 2
  • 1.20∼4.48× faster time-to-accuracy and 1.1%∼5.0% higher accuracy: FedBalancer outperforms existing FL algorithms with deadline configuration methods across five datasets from three domains.The paper also reports improved time-to-accuracy performance when FedBalancer is combined with three orthogonal FL algorithms.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

FL must contend with imbalanced, non-IID private data and clients with varied hardware and connectivity. Motivational experiments show that sample importance changes during training and that no single deadline method performs best on both tested tasks.

2.1 Federated Learning

  • FL commonly requires hundreds to thousands of rounds, with substantial computation and network overhead for participating clients.The section frames time-to-accuracy as important for large-scale training, model prototyping, and repeated model updates.Source: §2.1 · p. 2
  • FL’s non-IID private client data cannot be filtered centrally, while differences in hardware and connectivity can produce up to 12× variation in round completion time.Round deadlines that drop late clients can reduce low-end clients’ contribution and potentially delay convergence or bias training.Source: §2.1 · p. 2

2.2 Motivational Study

  • The motivational experiments simulated heterogeneous training latency and network connectivity using FEMNIST and Shakespeare.Prior approaches vary local epochs, model subsets, personalization, or client selection, but still treat each client’s data equally.Source: §2.2 · pp. 2–3
  • The study used gradient norm to assess sample-level contribution, removed the top 5% of samples to avoid noisy samples, and scaled values to [0.0, 1.0].The x-shaped plot markers indicate where scaled gradient norm equals 0.2.Source: §2.2 · p. 3, Figure 1 · p. 3
  • 80.0% of FEMNIST samples and 54.8% of Shakespeare samples had scaled gradient norm below 0.2 in the final measured rounds, versus 6.8% and 6.7% in early rounds.The authors interpret this pattern as a shrinking share of samples contributing knowledge as training progresses, leaving current methods to spend time on samples with negligible model-update contribution.Source: §2.2 · p. 3, Figure 1 · p. 3
  • The findings motivate starting with all samples and then gradually removing samples the model has already learned.Deadline choice also matters because client computation changes with sample selection, so a deadline should adapt to the selected workload.Source: §2.2 · p. 3
  • 43.6%, 47.0%, and 77.9% faster: on FEMNIST, deadline 1.0𝑇 reached test accuracy .750 sooner than SmartPC, deadline 1.5𝑇, and deadline 2.0𝑇, respectively, while reaching final accuracy .815.On Shakespeare, SmartPC reached final accuracy .488 and was 61.7%, 42.8%, and 45.4% faster than deadlines 1.0𝑇, 1.5𝑇, and 2.0𝑇, respectively, in reaching test accuracy .450; deadline 0.5𝑇 did not achieve high accuracy in either task.Source: §2.2 · p. 3, Figure 2 · p. 3

3.1 Overview

FedBalancer adapts client sample selection and round deadlines together. Its round-level process exchanges model weights, a loss threshold, a deadline, and client metadata to choose settings for the next round.

3.1 Overview

  • FedBalancer controls the loss threshold, which determines client training data, and the deadline, which determines when the round ends.The system updates both variables for each round.Source: §3.1 · p. 4
  • Clients use the received loss threshold to select partial training data, train the received model, and return model updates and metadata for server aggregation.The server uses client metadata to choose the next round’s loss threshold and deadline.Source: §3.1 · p. 4
  • The framework addresses three design challenges: selecting useful samples without accuracy loss, preserving privacy, and predicting deadlines as selected workloads vary.Its stated goal is sample selection without exposing privacy-invasive sample-level information.Source: §3.1 · p. 4

3.2 Client Sample Selection

FedBalancer uses sample loss to prioritize training data while coordinating privacy-preserving metadata and adaptive threshold control. Client selection is also adjusted to account for the dynamically selected samples.

3.2.1 Sample selection module.

  • Clients first check whether they can train their full dataset within the deadline; if not, they select a subset using stored sample losses.A whole-dataset forward pass generates the loss list only the first time a client is selected, and selected-sample losses are updated during training to avoid repeated forward-pass latency.Source: §3.2.1 · p. 5
  • FedBalancer uses sample loss as a measure of statistical utility and prioritizes samples above a server-maintained loss threshold.The threshold supports gradually dropping already-learned samples while retaining some under-threshold samples to avoid catastrophic forgetting.Source: §3.2 · p. 4, §3.2.1 · p. 5

3.2.2 Loss threshold selection module.

  • Clients send differentially private low-loss and 80th-percentile high-loss statistics so the server can estimate the current loss range without collecting raw sample-level information.The 80th percentile is used instead of the maximum because noisy samples may have abnormally high loss.Source: §3.2 · p. 4, §3.2.2 · p. 5
  • The server interpolates between estimated low and high sample losses using a threshold ratio that starts at 0.0 and increases by a step size.Increasing the ratio starts training with all samples and gradually removes already-learned samples.Source: §3.2.2 · p. 5
  • FedBalancer evaluates each round’s configuration using selected-sample loss sum divided by selected-sample count and deadline, using only clients that completed and sent updates.It adjusts the loss-threshold ratio based on past versus recent utility, while controlling the deadline ratio in the opposite direction.Source: §3.2.2 · pp. 5–6

3.2.3 Client selection with sample selection.

  • The client-selection formulation adapts statistical utility calculations to FedBalancer’s dynamically selected samples.It collects the sum of squared losses and sample count from the over-threshold group as differentially private metadata.Source: §3.2.3 · p. 6

3.3 Adaptive Deadline Control

FedBalancer adapts the deadline to changing client training times by selecting the deadline with the highest deadline efficiency (DDL-E). Across FEMNIST and Shakespeare, DDL-E peaks at specific deadlines, and the next-round deadline is interpolated between peak-efficiency deadlines for different epoch counts.

3.3.1 Efficiency of a deadline.

  • DDL-E measures completed clients per unit time, balancing longer deadlines with more completions against very short deadlines with few completions.The paper describes low efficiency at both extremes: long deadlines and extremely short deadlines.Source: §3.3.1 · p. 6
  • FEMNIST peaks at 172 seconds with DDL-E 2.57, while Shakespeare peaks at 157 seconds with DDL-E 0.13.The measurements use real-world client connectivity and training-latency data, across deadlines from 1 to 1200 seconds.Source: §3.3.1 · p. 6, Figure 4 · p. 6
  • FedBalancer estimates client completion time from downlink speed, uplink speed, and batch training latency, accounting for the selected training data size.It searches deadlines from the smallest value upward, selecting the deadline with maximum DDL-E among the selected clients in that round.Source: §3.3.1 · p. 6

3.3.2 Deadline selection module.

  • For the next round, the deadline selection module linearly interpolates between peak-DDL-E deadlines for one epoch and E epochs.The interpolation ratio starts at 1.0 and is gradually decreased; the range accommodates clients training different numbers of epochs within a deadline.Source: §3.3.2 · p. 7

3.4 Collaboration with FL Methods

FedBalancer can be added to FL methods that do not select client samples or control deadlines. For Oort, the paper introduces OortBalancer, which selects more important samples for its one-batch-per-epoch training.

3.4 Collaboration with FL Methods

  • FedBalancer adds sample selection and deadline control to orthogonal FL approaches that do neither.The paper reports improved performance when combining it with three existing FL methods.Source: §3.4 · p. 7
  • OortBalancer adapts FedBalancer's sample selection to Oort by fixing L to the batch size.This targets more important samples within Oort's one randomly selected batch per local epoch.Source: §3.4 · p. 7

4 EVALUATION

The evaluation compares FedBalancer across five real-user datasets and several settings, reporting faster time-to-accuracy and higher final accuracy than baselines. It also examines parameter choices, component effects, compatibility with other FL algorithms, and performance on Android devices.

4.1 Experimental Setup

  • Evaluation spans five real-user datasets across computer vision, natural language processing, and activity recognition, using time-to-accuracy and final accuracy averaged over three random seeds.The datasets are FEMNIST, Celeba, Reddit, Shakespeare, and UCI-HAR.Source: §4.1 · p. 7

4.2 Speedup and Accuracy on Five FL Tasks

  • Across five datasets, FedBalancer improved time-to-accuracy over evaluated baselines and final accuracy over baselines on every dataset.On NLP, it achieved 1.20∼4.48× speedup over FedAvg-based methods, 1.05∼1.23× over Prox-based methods, and 1.41∼2.95× over SampleSelection; accuracy gains were 1.1∼5.0% over FedAvg-based methods, 0.6∼3.2% over Prox-based methods, and 1.0∼5.0% over SampleSelection.Source: Table 1 · p. 8, §4.2 · pp. 8–9

4.3 Parameter Sensitivity Analysis

  • Parameter sensitivity differed by dataset: w=20 and d_ss=0.05 performed well on both FEMNIST and Reddit, while l_ss and p trends diverged.FEMNIST performed better with l_ss≥0.05 and p=1.00, whereas Reddit performed better with l_ss≤0.05 and p=0.75; the authors suggest parameter choices depend on training progression.Source: Table 3 · p. 9, §4.3 · p. 9, Figure 5 · p. 10
  • Increasing metadata noise reduced accuracy, but FedBalancer with NF 0.5 or 5.0 still outperformed Prox in time-to-accuracy and accuracy.Accuracy was 81.9% at NF 0.0, 81.4% at NF 0.5, and 81.1% at NF 5.0.Source: Figure 5 · p. 10, §4.3 · p. 10

4.4 Effect of FedBalancer Components

  • Component effects varied by dataset: adding sample selection reduced FEMNIST performance but improved Reddit performance, while deadline control further improved time-to-accuracy with sample selection.The authors attribute FEMNIST’s drop to reduced statistical utility per round under the same deadline, and suspect Reddit benefited from selecting important samples and clients holding them.Source: Figure 6 · p. 10, §4.4 · p. 10

4.6 Testbed Experiments with Android Clients

  • On Android testbed devices, FedBalancer achieved 1.34× speedup and 3.3% accuracy improvement over FedAvg-based baselines, and was 1.29× and 1.34× faster than Prox and SampleSelection.Its accuracy improvements over Prox and SampleSelection were 2.5% and 3.9%, respectively.Source: Table 5 · p. 10, §4.6 · p. 11

4.5 Collaboration with FL Algorithms

  • With Oort, q-FFL, and Structured Updates, FedBalancer improved time-to-accuracy and accuracy in all three combinations.The reported speedups were 1.84×, 1.19×, and 1.31×, with accuracy improvements of 2.6%, 2.5%, and 1.7%, respectively.Source: §4.5 · p. 10, Figure 7 · p. 11

4.6 Testbed Experiments with Android Clients

  • Testbed communication latency varied more than training latency, rising up to 3.91× its mean; its mean coefficient of variation was 1.5× the simulated value.Fixed-deadline baselines could miss updates, while SmartPC and Wait-for-All could wait longer during poor connectivity; FedBalancer also experienced client failures, but outperformed baselines with adaptive deadline configuration.Source: Figure 8 · p. 11, §4.6 · p. 11

5 DISCUSSION

FedBalancer supports both local-epoch training policies, but their communication and training-time trade-offs differ. Its discussion also identifies possible noise-related and group-bias limitations of sample selection.

Local Epoch Training Policies

  • FedBalancer improves time-to-accuracy performance with both single-batch and full-data local-epoch training, which trade shorter client training for more communication against longer rounds and fuller per-round data use.The model developer determines which policy to use.Source: §5 · p. 11

Effect of Forward Pass at a Client

  • On FEMNIST, adding a forward pass made FedBalancer slower; maintained, sometimes outdated loss values encourage more diverse samples while prioritizing informative ones.A sample’s maintained loss is updated when that sample is selected and trained.Source: §5 · p. 12

Robustness of Sample Selection

  • Noisy samples may be selected because the sample-selection module prioritizes high loss, so FedBalancer might perform worse on noisy-data tasks.The authors report improvements on five real-world user datasets that may already contain some noise, and leave combining with robust training approaches as future work.Source: §5 · p. 12

Potential Bias of Sample Selection

  • Prioritizing informative samples may favor certain classes or sensitive groups and degrade performance for less-sampled entities.The authors leave combining selection with approaches designed for unbiased training as future work.Source: §5 · p. 12

6 RELATED WORK

Related work covers sample selection in machine learning and federated learning, as well as deadline control. The paper positions FedBalancer as jointly selecting how many and which client samples to train, while adapting deadlines as sample counts change.

Sample Selection in Machine Learning

  • Curriculum learning orders samples from easier to harder, but applying it in FL is challenging because a reference model for determining difficulty is often unavailable.The cited work describes curriculum learning as aiming to improve convergence speed and generalization.Source: §6 · p. 12
  • Active learning queries users to label informative unlabeled data, while FL makes this difficult because client data are isolated and labels are known but not shared externally.Source: §6 · p. 12
  • Importance sampling prioritizes training samples, but how many and which to use per FL round, and when to calculate importance, remain open questions in the cited discussion.Source: §6 · p. 12

Sample Selection in FL

  • FedBalancer is presented as the first FL framework to determine both how many and which client samples to select during training, unlike prior approaches that leave one decision unspecified or use random sampling.Tuor et al. select data before training and require an example dataset; Li et al. do not specify the number of samples, while FedSS uses random sampling.Source: §6 · p. 12

Deadline Control in FL

  • FedBalancer’s deadline strategy accommodates dynamically changing client sample counts, whereas SmartPC assumes clients use the same data each round.SmartPC determines a deadline so a specified proportion of devices can complete a round.Source: §6 · p. 12

7 CONCLUSION

FedBalancer combines round-wise sample selection with adaptive deadline control. Across five real-world datasets in three domains, it improves time-to-accuracy and model accuracy over existing FL algorithms with deadline configuration methods, and is also applied alongside three existing FL algorithms.

7 CONCLUSION

  • 1.20∼4.48× speedup over existing FL algorithms with different deadline configuration methods, alongside a 1.1%∼5.0% improvement in model accuracy, is reported across five real-world datasets from three domains.Source: §7 · p. 12
  • FedBalancer selects samples with high statistical utility through client-server coordination at each FL round without exposing users’ private information.Source: §7 · p. 12
  • The framework combines sample selection with adaptive deadline control that predicts an optimal deadline for each round as client sample counts change.Source: §7 · p. 12
  • Joint implementations with three existing FL algorithms report improved time-to-accuracy performance and model accuracy.Source: §7 · p. 12

Related papers

Loading 2201.01601v2…