Noise-Efficient Learning of Differentially Private Partitioning Machine Ensembles

Zhanliang Huang, Yunwen Lei, Ata KabánECML/PKDD 2022 · OpenReview

Abstract

Differentially private decision tree algorithms have been popular since the introduction of differential privacy. While many private tree-based algorithms have been proposed for supervised learning tasks, such as classification, very few extend naturally to the semi-supervised setting. In this paper, we present a framework that takes advantage of unlabelled data to reduce the noise requirement in differentially private decision forests and improves their predictive performance. The main ingredients in our approach consist of a median splitting criterion that creates balanced leaves, a geometric privacy budget allocation technique, and a random sampling technique to compute the private splitting-point accurately. While similar ideas existed in isolation, their combination is new, and has several advantages: (1) The semi-supervised mode of operation comes for free. (2) Our framework is applicable in two different privacy settings: when label-privacy is required, and when privacy of the features is also required. (3) Empirical evidence on 18 UCI data sets and 3 synthetic data sets demonstrate that our algorithm achieves high utility performance compared to the current state of the art in both supervised and semi-supervised classification problems.

Introduction

Differential Privacy (DP) is widely regarded as the "gold standard" for data protection. However, implementing DP often incurs a significant "utility tax." To protect individual records, DP algorithms inject mathematical noise into the learning process. If the noise is too high, the model loses its utility; if it is too low, the privacy guarantee is compromised. Researchers from the University of Birmingham have proposed a novel framework to mitigate this trade-off by rethinking the construction of decision tree ensembles.

The Challenge: Privacy Budget Depletion

Standard decision tree construction involves a "greedy" search. At each node, the algorithm evaluates sensitive labels (e.g., medical diagnoses) to determine the optimal split. In a private setting, every such evaluation consumes a portion of the privacy budget ($\epsilon$). By the time the algorithm reaches the leaf nodes, the remaining budget is often insufficient to accurately count the classes, leading to high noise and poor predictive performance.

Furthermore, while labelled data is often scarce and sensitive, unlabelled data is typically more abundant. Existing private tree algorithms rarely leverage this unlabelled information to improve structural decisions.

The SSPE Framework

The proposed Supervised/Semi-Supervised Private Ensembles (SSPE) framework addresses these issues through three primary innovations:

  1. Density-Informed Median Splitting: Instead of using sensitive labels to find splits (e.g., via Gini index), SSPE uses the median of feature values. Since median splitting only requires feature data, it can be performed using unlabelled data. This preserves the entire "label budget" for the final leaf node counts, significantly reducing noise in the most critical part of the model.
  2. Geometric Privacy Budget Allocation: Estimating a private median becomes noisier as the data is partitioned into smaller subsets deeper in the tree. The authors derived a geometric scaling strategy, increasing the privacy budget by a factor of $1.5\times$ at each level. This ensures that splits remain accurate even as the sample size per node decreases.
  3. Random Candidate Sampling: To compute the private median efficiently, the algorithm samples a small set of candidates from the feature range and employs the Exponential Mechanism to select the best split point, balancing accuracy and privacy.
Comparison of accuracy between private median splitting, true median splitting, and random splitting across various privacy budgets.

Experimental Evaluation

The researchers evaluated SSPE against state-of-the-art methods, such as Smooth Random Trees (SRT) and Random Decision Trees (RDT), using 18 UCI datasets and 3 synthetic datasets to test scalability across different dimensionalities.

Key Results

  • Superior Utility: The Supervised Private Ensemble (SPE) outperformed competitors on 21 out of 22 datasets. Notably, on the Robot dataset, accuracy improved by over 25% compared to previous benchmarks.
  • Semi-Supervised Success: In scenarios where only 20% of data was labelled, the framework maintained high utility by using the 80% unlabelled data to build the tree structure.
  • Robustness: As shown in the experimental results, the "private median" approach consistently tracks the performance of the non-private "true median" baseline across a wide range of privacy budgets ($\epsilon$).
Experimental results demonstrating the stability and performance of the SSPE framework across different datasets and privacy levels.

Conclusion

By combining median-based splitting with geometric budget allocation, the SSPE framework provides a robust solution for building private decision forests. It effectively utilizes unlabelled data to "save" privacy budget for label classification, resulting in significant utility gains across both supervised and semi-supervised settings.

Summary updated

Abstract

Differentially private decision tree algorithms have been popular since the introduction of differential privacy. While many private tree-based algorithms have been proposed for supervised learning tasks, such as classification, very few extend naturally to the semi-supervised setting. In this paper, we present a framework that takes advantage of unlabelled data to reduce the noise requirement in differentially private decision forests and improves their predictive performance. The main ingredients in our approach consist of a median splitting criterion that creates balanced leaves, a geometric privacy budget allocation technique, and a random sampling technique to compute the private splitting-point accurately. While similar ideas existed in isolation, their combination is new, and has several advantages: (1) The semi-supervised mode of operation comes for free. (2) Our framework is applicable in two different privacy settings: when label-privacy is required, and when privacy of the features is also required. (3) Empirical evidence on 18 UCI data sets and 3 synthetic data sets demonstrate that our algorithm achieves high utility performance compared to the current state of the art in both supervised and semi-supervised classification problems.
BibTeX
@inproceedings{huang2022noise,
  author = {Zhanliang Huang and Yunwen Lei and Ata Kabán},
  title = {{Noise-Efficient Learning of Differentially Private Partitioning Machine Ensembles}},
  booktitle = {ECML/PKDD},
  year = {2022},
  url = {https://openreview.net/forum?id=2vzN6t77Ysd},
}
Figure