Federated Gradient Boosting using Minimal Variance Sampling

Abstract Federated learning (FL) has emerged as a paradigm for training machine learning models on decentralized data while preserving privacy. This paper introduces a novel approach called Federated gradient BOOsting using Minimal variance sampling (FedBOOM). FedBOOM leverages gradient boosting to construct a robust global model by iteratively aggregating weak learners trained on locally sampled data from clients. Crucially, it employs minimal variance sampling (MVS) to select relevant data points from each client, reducing overhead communication and mitigating the impact of data heterogeneity. Through theoretical analysis and extensive experiments, we find that FedBOOM achieves a superior performance with a subsampling fraction of less than 1.0. In most experiments, a fraction of 0.4-0.6 is optimal and outperforms that of no subsampling (fraction of 1.0) with on average 5.5\%. Use of optimal subsampling fraction for FedBOOM can also reduce communication cost with 40\% on average.