Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

Lumberjack tackles a specific failure mode in differentially private random forests: fully random trees are privacy-friendly but collapse on deep, sparse tabular data, while greedy private splits are brittle and often incorrectly analyzed. The paper’s core novelty is to build very deep random trees first, then privately prune them using a new hierarchical heavy-hitter detector with error scaling O(log h) in tree height h, rather than the O(√h) sensitivity of naive node counting. The detector uses a middle-layer query, monotonicity-based propagation of Heavy/Light labels, and an adaptive Gaussian sparse-histogram thresholding mechanism, yielding a tight joint privacy analysis over the entire forest. In the forest itself, Lumberjack splits features uniformly at random as in Extra Trees, prunes branches whose nodes are not sufficiently populated, and privatizes leaves with either the exponential mechanism for majority vote or Gaussian-noised class proportions under zCDP accounting. Empirically, on Adult and four Folktables California classification tasks, with ε in {0.5, 1, 2, 4, 8} and δ=10^-6, Lumberjack consistently outperforms prior DP random forest baselines including DiffPrivLib, SNR, Smooth Sensitivity, and Suihkonen, often by several accuracy points and sometimes beating a non-private greedy decision tree at moderate privacy. The paper also reports privacy flaws in more than 10 prior DP random-forest papers and shows a lower bound indicating that some threshold growth with tree depth is unavoidable, making Lumberjack’s logarithmic-height detector close to optimal up to a √log h factor.