Private Boosted Decision Trees via Smooth Re-Weighting

Vahid R. Asadi, Marco L. Carmosino, MohammadMahdi Jahanara, Akbar Rafiey, Bahar Salamatian

Introduction

Boosting is a cornerstone of modern machine learning, building powerful classifiers by sequentially combining a committee of "weak" base learners. However, the iterative nature of boosting presents a significant challenge for Differential Privacy (DP). Standard boosting algorithms, such as AdaBoost or Gradient Boosting, work by concentrating attention—and thus numerical weight—on the most difficult-to-classify examples. In a privacy-sensitive context, this mechanism is problematic: if an algorithm focuses intensely on outliers, the resulting model may effectively memorize individual data points, leading to privacy leaks.

This paper introduces LazyBB (Weighted Lazy-Bregman Boosting), a practical algorithm designed to navigate the trade-off between model utility and privacy. By employing a technique known as "smooth re-weighting," the authors demonstrate that it is possible to achieve high accuracy and interpretability even under strict privacy constraints.

The LazyBB Framework

The core innovation of LazyBB lies in how it manages the distribution of weights across the training set. To prevent any single individual's data from exerting too much influence on the final model, the algorithm enforces a mathematical constraint called smoothness.

Smooth Distributions

After updating example weights in each boosting round, LazyBB projects these weights onto a space of $\kappa$-smooth distributions. This acts as a hard cap: no single training example is permitted to hold more than a specific fraction ($1/\kappa n$) of the total probability mass. This capping mechanism inherently limits the sensitivity of the learning process to any single data point, providing a foundation for robust privacy guarantees.

Novel Privacy Mechanisms

Applying DP to boosting is complex because the weight distribution shifts every round. To select the optimal tree splits under these changing conditions, the authors developed the Weighted Exponential Mechanism and Weighted Return Noisy Max. These mechanisms are built upon a new concept termed robust sensitivity, which quantifies how much a function's output can change when both the underlying dataset and the weight distribution are perturbed simultaneously.

The Efficacy of Decision Stumps

A surprising insight from this research is that "simpler is better" when privacy is a requirement. In non-private settings, boosting typically utilizes decision trees with depths ranging from 3 to 7. However, in the DP regime, the authors found that 1-Rules (decision stumps) are significantly more effective.

Decision stumps are depth-1 trees that split on a single feature. Because they are ultra-simple, they are remarkably resilient to the random noise injected to satisfy DP requirements. In contrast, deeper trees tend to "overfit" to the noise, leading to degraded performance. Furthermore, because the privacy budget limits the number of boosting rounds, the final model remains sparse and highly interpretable—often resembling an $L_1$-regularized linear model that relies on only a handful of features.

Empirical Results

The authors evaluated LazyBB on three standard tabular datasets: Adult (census data), Cod-RNA (biological data), and Mushroom (categorical classification).

  • High Accuracy: In high-privacy regimes ($\epsilon \le 1$), LazyBB paired with decision stumps consistently matched or outperformed established baselines, including DP Logistic Regression and DP Gradient Boosting.
  • Extreme Sparsity: On the Adult dataset, with a strict privacy budget of $\epsilon = 0.4$, the algorithm achieved 82% accuracy while utilizing an average of only 6.4 features out of 162 available. This level of sparsity is particularly valuable in fields like medicine or finance, where auditability is as crucial as accuracy.
  • Pure vs. Approximate DP: The study found that "pure" differential privacy ($\delta = 0$) performed nearly as well as "approximate" DP ($\delta > 0$) when hyperparameters were properly tuned, suggesting that the simplicity of boosted stumps makes them less reliant on the relaxed constraints of approximate DP.

Bridging Theory and Practice

The research highlights a notable gap between current theoretical frameworks and empirical reality. Standard generalization theories, such as Rademacher complexity, provide bounds that are far more pessimistic than the results observed in practice. Additionally, while boosting theory often relies on a "weak learning assumption" (the idea that base learners always perform better than random guessing), the authors observed that LazyBB continued to generalize well even after this assumption appeared to fail in the private setting.

Conclusion

LazyBB offers a robust, interpretable, and highly accurate solution for training boosted decision trees under differential privacy. By combining smooth re-weighting with simple decision stumps, the authors have created a method that is not only theoretically sound but also practically superior for high-stakes tabular data applications. The success of this approach motivates further research into new theoretical frameworks that can better explain the generalization dynamics of non-adaptive, private models trained on small samples.

Summary updated

BibTeX
@article{asadi2023private,
  author = {Vahid R. Asadi and Marco L. Carmosino and MohammadMahdi Jahanara and Akbar Rafiey and Bahar Salamatian},
  title = {{Private Boosted Decision Trees via Smooth Re-Weighting}},
  journal = {J. Priv. Confidentiality},
  year = {2023},
  doi = {10.29012/jpc.808},
}
Figure