Securely Training Decision Trees Efficiently

Decision trees are an important class of supervised learning algorithms. When multiple entities contribute data to train a decision tree (e.g. for fraud detection in the financial sector), data privacy concerns necessitate the use of a privacy-enhancing technology such as secure multi-party computation (MPC) in order to secure the underlying training data. Prior state-of-the-art (Hamada et al.[18]) construct an MPC protocol for decision tree training with a communication of O(hmN log N), when building a decision tree of height h for a training dataset of N samples, each having m attributes.