  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.
