PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Federated Gradient Boosting Decision Trees

Qinbin Li, Zeyi Wen, Bingsheng He

arXiv:1911.04206v2cs.LGstat.ML

TL;DR

Existing horizontal federated GBDT methods face efficiency or accuracy limitations. SimFL uses locality-sensitive hashing and weighted boosting under relaxed privacy constraints, and reports improved accuracy with low training overhead, approaching joint-data GBDT accuracy.

  • Problem

    Existing horizontal federated GBDT approaches are not efficient or effective enough for practical use because of costly cryptographic transformations or reduced accuracy from differential privacy.

  • Method

    SimFL uses locality-sensitive hashing to collect cross-party similarity information and Weighted Gradient Boosting to train trees without exposing raw data.

  • Results

    SimFL significantly improves predictive accuracy over training on individual parties’ data and achieves accuracy close to a GBDT trained on joint data.

  • Takeaways & Limitations

    SimFL provides a practical horizontal federated GBDT framework with good accuracy and fast training under a relaxed privacy model.

  • Takeaways & Limitations

    The privacy model is weaker than secure multi-party computation and may remain vulnerable to background-knowledge inference attacks.

Abstract

from arXiv · show

Gradient Boosting Decision Trees (GBDTs) have become very successful in recent years, with many awards in machine learning and data mining competitions. There have been several recent studies on how to train GBDTs in the federated learning setting. In this paper, we focus on horizontal federated learning, where data samples with the same features are distributed among multiple parties. However, existing studies are not efficient or effective enough for practical use. They suffer either from the inefficiency due to the usage of costly data transformations such as secret sharing and homomorphic encryption, or from the low model accuracy due to differential privacy designs. In this paper, we study a practical federated environment with relaxed privacy constraints. In this environment, a dishonest party might obtain some information about the other parties' data, but it is still impossible for the dishonest party to derive the actual raw data of other parties. Specifically, each party boosts a number of trees by exploiting similarity information based on locality-sensitive hashing. We prove that our framework is secure without exposing the original record to other parties, while the computation overhead in the training process is kept low. Our experimental studies show that, compared with normal training with the local data of each party, our approach can significantly improve the predictive accuracy, and achieve comparable accuracy to the original GBDT with the data from all parties.

1 Introduction

Horizontal federated GBDT methods face a practical trade-off between predictive accuracy and training efficiency. SimFL addresses these limitations with relaxed privacy constraints, similarity-based learning, and low-overhead training.

  • Existing horizontal federated GBDT approaches are not effective or efficient enough for practical use.
  • Model accuracy: Differential-privacy-based training can reduce accuracy because each tree uses only local-party data.
  • Efficiency: Cryptographic approaches incur high training overhead from complex encryption and many comparison operations.
  • SimFL uses a weaker privacy model that prevents recovery of actual raw records while permitting more efficient and effective GBDT designs.
  • SimFL combines locality-sensitive hashing with Weighted Gradient Boosting to use cross-party similarity information without exposing raw data.
  • Experiments report good accuracy and fast training for practical use.

2 Preliminaries

The preliminaries introduce LSH for approximate similarity detection and GBDTs as additive ensembles of decision trees optimized through split gains and regularized objectives.

  • Locality-Sensitive Hashing (LSH): LSH increases the probability that neighboring points share a hash while separating non-neighboring points.
  • Locality-Sensitive Hashing (LSH): The p-stable LSH function uses a random projection, an offset, and a window size r to compute hash values.
  • Gradient Boosting Decision Trees (GBDTs): GBDTs train a sequence of decision trees as an ensemble over a loss function and dataset of n instances with d features.
  • Gradient Boosting Decision Trees (GBDTs): The regularization term penalizes model complexity, with γ and λ as hyper-parameters, T_l as the leaf count, and w as the leaf weight.
  • Gradient Boosting Decision Trees (GBDTs): GBDTs build trees by evaluating gradient statistics and selecting feature splits that maximize gain.

3 Problem Statement

The paper targets horizontal federated learning, where parties with the same features retain private data but seek the accuracy benefits of joint modeling. It defines a weaker, heuristic privacy model and an efficient GBDT objective.

  • Horizontal federated learning distributes records with the same feature set across parties that do not share private data.
  • Improved model accuracy over each party’s local model is described as a pre-condition for collaboration.
  • The setting assumes multiple parties, each owning an instance set with globally unique identifiers.
  • Privacy model: The privacy definition considers honest-but-curious parties and requires infinitely many possible inputs for the same observed output.
  • Privacy model: This privacy model is weaker than secure multi-party computation and does not address potential inference attacks.
  • Problem definition: The stated objective is an efficient and effective GBDT model over the union of parties’ instance sets under the defined privacy model.

4 The SimFL Framework

SimFL trains horizontally federated GBDTs through two stages: preprocessing collects cross-party similarity information with LSH, and training uses that information in weighted gradient boosting while sharing learned trees.

  • Overview: SimFL has separate preprocessing and training stages, with preprocessing reusable across multiple training runs until the data are updated.The preprocessing stage computes similarity information; the training stage sequentially builds trees at each party.
  • Preprocessing Stage: Each party hashes its instances with randomly generated LSH functions, and AllReduce builds and broadcasts global hash tables.The global tables union instance IDs having identical hash values.
  • Preprocessing Stage: LSH identifies cross-party similar instances because similar records have a higher probability of receiving identical hash values across multiple functions.For each local instance, the other-party instance with the highest identical-hash count is selected as similar.
  • Training Stage: During training, each party builds trees from local instances while replacing local gradients with aggregated gradients from similar instances.Aggregating gradients locally reduces communication cost and protects individual gradients.
  • Training Stage: Weighted Gradient Boosting gives greater weight to instances similar to many others, then builds and shares each tree among the parties.The resulting tree uses local instances together with weighted first- and second-order gradients.

5 Theoretical Analysis

The analysis establishes SimFL’s privacy condition and characterizes its approximation, generalization, computation, and communication costs. The results show privacy when L < d, with low-order preprocessing and training overhead but approximation error that can grow with data held by other parties.

  • 5.1 Privacy Level Analysis: SimFL satisfies the privacy model when L < d, where L is the number of hash functions and d is the data dimensionality.Under this condition, each output corresponds to infinitely many possible inputs, preventing recovery of other parties’ actual raw data.
  • 5.2 The Error of Weighted Gradient Boosting: The WGB approximation error may increase as the number of instances held by other parties increases.Theorem 2 bounds the approximation error by O(N − Nm) with respect to the number of instances.
  • 5.2 The Error of Weighted Gradient Boosting: WGB may still achieve low generalization error as the total number of training instances N increases.Vanilla GBDT generalization error tends to decrease as N increases, supporting the stated behavior for WGB.
  • 5.3 Computation and Communication Efficiency: The preprocessing computation overhead is O(NL + Nd) on average.Hash computation costs O(Nd), while unioning hash buckets and finding frequent matching instance IDs costs O(NL).
  • 5.3 Computation and Communication Efficiency: The training computation overhead is O(NT), because weighted-gradient calculation uses simple sum operations while tree construction otherwise matches vanilla GBDTs.T denotes the number of trees and N the total number of training instances.
  • 5.3 Computation and Communication Efficiency: The training-stage communication overhead is 8T[N + (2D −1)(M −1)] bytes.This includes aggregated gradients and sharing each depth-D tree with the other M −1 parties.

6 Experiments

Experiments evaluate SimFL's accuracy across partition strategies, party counts, and similarity ratios, then measure its training and communication efficiency. SimFL generally improves over local or distributed baselines while remaining close to centralized performance and adding limited overhead.

  • 6.1 Test Errors: SimFL improves accuracy over SOLO by about 4% on average under unbalanced partitioning with θ = 80%.Its test error is also close to ALL-IN and lower than TFL across the evaluated data parts.
  • 6.1 Test Errors: Across ratios from 60% to 90%, SimFL works especially well when θ is high.The experiments use Figure 2 to examine how the unbalanced partition ratio affects test error.
  • 6.1 Test Errors: Under balanced partitioning, SimFL outperforms SOLO and TFL across six datasets and sometimes has lower test error than ALL-IN.SOLO and ALL-IN are close because each party's local data is generally sufficient for training.
  • 6.1 Test Errors: As the number of parties increases, SimFL's test error generally rises but remains below SOLO's minimum error in most cases.SimFL is more stable than TFL for both balanced and unbalanced partitions.
  • 6.2 Efficiency: SimFL's training time is close to SOLO, its computation overhead is less than 10% of total training time, and communication costs no more than 10MB per tree.Preprocessing can be reused across training runs, while SimFL trains trees from local instances rather than the full joint dataset.

7 Conclusions

The paper concludes that SimFL offers a practical horizontal federated GBDT framework by combining relaxed privacy with similarity-based learning. It improves predictive accuracy over isolated local training while approaching joint-data accuracy and avoiding costly cryptographic operations.

  • 7 Conclusions: SimFL addresses low efficiency and low model accuracy in existing horizontal federated GBDT systems.The framework is designed for a federated setting where parties collaborate without sharing individual records.
  • 7 Conclusions: Locality-sensitive hashing collects similarity information without exposing individual records or relying on costly secret sharing or encryption.Weighted Gradient Boosting then uses this information to build decision trees with bounded errors.
  • 7 Conclusions: SimFL significantly improves predictive accuracy over training on each party's data alone and approaches the model trained on joint data from all parties.This conclusion summarizes the reported experimental comparison.

A Proof of Theorem 1

The proof argues that a party cannot uniquely recover another instance from its observed hash values and aggregated gradients. It establishes this by showing infinitely many compatible instances.

  • A Proof of Theorem 1: The potentially dishonest party observes other instances' hash values and aggregated gradients of similar instances during the protocol.The proof analyzes security against one party without loss of generality.
  • A Proof of Theorem 1: Each instance's LSH values imply L compound inequalities that constrain, but do not uniquely determine, its feature vector.The inequalities are represented using the feature functions F_j and hash width r.
  • A Proof of Theorem 1: When the feature dimension d exceeds the number of equations L, the corresponding linear system has infinitely many solutions once one solution is known.Therefore, infinitely many instances can produce the same hash values known to the observing party.

B Proof of Theorem 2

The proof bounds how similarity-based tree construction affects gradients and generalization as instances from other parties reach the same leaves. It combines tree-depth probabilities with concentration bounds.

  • B Proof of Theorem 2: The proof assumes globally unique instance IDs and uses g_i and h_i for an instance's first- and second-order gradients.These notational assumptions support the subsequent gradient analysis.
  • B Proof of Theorem 2: The analysis considers instances from different parties reaching the same tree leaf under uniformly distributed feature values and random feature-value splits.The relevant distance scale is represented by d_t, the maximum feature-space distance between instances in the leaf.
  • B Proof of Theorem 2: For a tree of depth D, the probability that another instance follows the required directions is bounded using the ratio d_t/d_m.The proof then counts the number of nonzero contributions among N − N_m other instances.
  • B Proof of Theorem 2: Hoeffding's inequality provides a high-probability bound on the number of other-party instances contributing to the analysis.The resulting bound is combined with earlier equations to complete the theorem's error analysis.
Loading 1911.04206v2…