  Decision trees are interpretable models that are well-suited to non-linear
learning problems. Much work has been done on extending decision tree learning
algorithms with differential privacy, a system that guarantees the privacy of
samples within the training data. However, current state-of-the-art algorithms
for this purpose sacrifice much utility for a small privacy benefit. These
solutions create random decision nodes that reduce decision tree accuracy or
spend an excessive share of the privacy budget on labeling leaves. Moreover,
many works do not support continuous features or leak information about them.
We propose a new method called PrivaTree based on private histograms that
chooses good splits while consuming a small privacy budget. The resulting trees
provide a significantly better privacy-utility trade-off and accept mixed
numerical and categorical data without leaking information about numerical
features. Finally, while it is notoriously hard to give robustness guarantees
against data poisoning attacks, we demonstrate bounds for the expected accuracy
and success rates of backdoor attacks against differentially-private learners.
By leveraging the better privacy-utility trade-off of PrivaTree we are able to
train decision trees with significantly better robustness against backdoor
attacks compared to regular decision trees and with meaningful theoretical
guarantees.
