💻 computer science

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

The paper introduces Lumberjack, a differentially private random forest algorithm that leverages a novel heavy hitter detection method to construct and prune deep trees, thereby achieving state-of-the-art utility-privacy trade-offs that significantly outperform existing approaches.

Original authors: Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The Privacy vs. Accuracy Dilemma

Imagine you are a detective trying to solve a crime using a team of experts (a Random Forest). Each expert looks at the clues (data) and builds a decision tree to figure out what happened. Usually, these teams are incredibly accurate.

However, there's a catch: if you let the experts look at the clues too closely, they might accidentally memorize specific details about a single witness, leaking their private information. To prevent this, we use Differential Privacy (DP). Think of DP as a "noise machine" that adds static to the clues so the experts can't see individual details, only the general pattern.

The problem is that in the past, turning on this "noise machine" made the experts so confused that they stopped being useful. They would either guess randomly or give up entirely.

Lumberjack is a new method that lets the experts build deep, detailed trees while keeping the noise machine running, without losing their accuracy.

The Old Ways: Why They Failed

Before Lumberjack, there were two main ways to try to build these private trees, and both had major flaws:

The "Greedy" Approach (The Over-Thinker):
- How it worked: The experts tried to find the perfect split for every branch by looking at the data.
- The problem: To find the perfect split, they had to ask the data too many specific questions. The noise machine got so loud that the answers became garbled. It was like trying to hear a whisper in a hurricane.
- Result: The trees were built poorly, and the predictions were bad.
The "Fully Random" Approach (The Gambler):
- How it worked: To avoid asking too many questions, the experts just guessed where to cut the tree branches, completely ignoring the data. They only looked at the data at the very end to see who won.
- The problem: This was too careless. If the tree was too deep, the branches would end up in empty rooms with no data at all. The experts would just guess the most common answer (e.g., "It's always blue") because they had no data to guide them.
- Result: The trees were too shallow to be smart, or too deep to be accurate.

The Lumberjack Solution: The "Heavy Hitter" Detector

Lumberjack combines the best of both worlds. It starts by building a massive, deep tree using random guesses (like the Gambler), but then it uses a special tool to prune (cut away) the useless parts.

The Core Innovation: Finding "Heavy Hitters"

Imagine the tree is a giant building with many floors and rooms.

Light Rooms: Empty rooms or rooms with very few people.
Heavy Rooms: Rooms packed with people (data points).

In a private setting, you can't just walk into every room and count the people (that reveals too much info). You need a way to find the crowded rooms without checking every single empty one.

Lumberjack uses a clever "Heavy Hitter Detector" (a new algorithm the authors invented). Here is how it works, using a Binary Search analogy:

The Middle Floor: Instead of checking every floor from top to bottom, the detector jumps straight to the middle floor of the building.
The Check: It asks, "Is this floor crowded?" (Privately, with a little noise).
- If YES (Heavy): It knows the whole floor above it is also crowded (because people come from above). It marks the whole upper section as "Keep."
- If NO (Light): It knows the whole floor below it is empty (because if the top is empty, the bottom must be too). It marks the whole lower section as "Cut."
The Recursion: It repeats this process on the remaining sections, jumping to the middle of the new sections.

Why is this magic?
In the old methods, checking every room required a huge amount of "privacy budget" (noise) that grew with the height of the building. Lumberjack's method is like a smart search that only checks a logarithmic number of spots. It finds the crowded rooms with much less noise, allowing the trees to be much deeper and more accurate.

The Result: A New State of the Art

The authors tested Lumberjack on real-world datasets (like the "Adult" dataset used for income prediction and various US Census data).

The Comparison: They compared Lumberjack against previous private methods and even non-private "Extra Trees" (a standard, non-private algorithm).
The Outcome:
- Lumberjack consistently beat all previous private methods.
- In many cases, it performed better than a standard non-private decision tree, even while protecting privacy.
- It successfully handled deep trees (up to 100 levels deep) without collapsing into useless guesses.

Summary of the "Heavy Hitter" Algorithm

The paper also highlights that the "Heavy Hitter" algorithm itself is a major contribution. It solves a specific math problem: How do you find the crowded nodes in a tree structure without spending too much privacy budget?

Old way: Noise scales with the square root of the tree height ( $\sqrt{h}$ ).
Lumberjack way: Noise scales with the square root of the logarithm of the height ( $\sqrt{\log h}$ ).
Analogy: If the tree height is 1,000, the old way adds noise based on 31. The new way adds noise based on roughly 3. This massive reduction in noise is what allows the trees to be deep and accurate.

Conclusion

Lumberjack proves that you don't have to choose between privacy and accuracy. By using a smart, recursive search to find where the data actually is (the "Heavy Hitters") and pruning the empty spaces, we can build powerful, private decision trees that were previously thought impossible.

Problem Statement
Random forests (RFs) are a dominant method for tabular data prediction, offering high accuracy and computational efficiency. However, their application in sensitive domains (e.g., healthcare, finance) is hindered by the risk of leaking information about individual training records. While Differential Privacy (DP) provides a rigorous framework for mitigating these risks, existing approaches to enforcing DP on random forests suffer from severe utility degradation.

Current methods generally fall into two paradigms, both of which face significant limitations:

Greedy Tree Construction: Adapting standard decision tree algorithms (which select splits based on data-dependent impurity criteria) to the DP setting requires injecting noise into the split selection process. This noise accumulates rapidly, leading to poor tree structures and low utility.
Fully Random Trees: Inspired by "Extra Trees," these methods generate tree structures independent of the data, using the data only to label leaves. While this avoids spending the privacy budget on structure learning, these trees are highly sensitive to depth. Shallow trees result in overly large leaves, while deep trees produce leaves with insufficient samples for reliable privatized predictions. Furthermore, without data-dependent stopping, they often fail to capture informative structures in the feature space, collapsing to majority-class predictions.

Methodology: Lumberjack
The paper introduces Lumberjack, a novel differentially private random forest algorithm designed to bridge the gap between the expressiveness of deep trees and the constraints of differential privacy. The core innovation is a two-stage process: constructing large, fully random trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes.

Randomized Construction: Lumberjack builds deep random trees (similar to Extra Trees) where splits are chosen uniformly at random from the feature space, independent of the data. This avoids the high noise cost associated with greedy split selection.
Privacy-Preserving Pruning via Heavy Hitter Detection: The critical challenge is determining which nodes contain enough data points to be retained without violating privacy. Lumberjack frames this as a heavy hitter detection problem over a hierarchical tree structure. The goal is to identify nodes where the count of data points exceeds a threshold $\tau$ .
Novel Heavy Hitter Algorithm: The authors propose a new $(\epsilon, \delta)$ $(ϵ, δ)$ -DP algorithm for detecting heavy hitters in trees of height $h$ $h$ .
- Mechanism: Instead of a naive top-down traversal which incurs $\ell_2$ sensitivity scaling as $\sqrt{h}$ , the algorithm performs structured, overlapping noisy binary searches. It queries nodes in a middle layer, marking them as "Heavy" or "Light."
- Propagation: Due to the monotonic nature of tree counts (a parent's count is the sum of its children), a "Heavy" node implies all its ancestors are Heavy, and a "Light" node implies all its descendants are Light. This allows the algorithm to skip large portions of the tree.
- Sensitivity Reduction: By exploiting this structure, the algorithm reduces the $\ell_2$ sensitivity from $O(\sqrt{h})$ to $O(\sqrt{\log h})$ .
- Sparse Histogram Integration: To handle the computational infeasibility of querying all nodes in deep trees (most of which are empty), the algorithm integrates techniques from sparse histogram estimation. It deterministically maps queries with sufficiently small counts to "Light" (empty) and only adds Gaussian noise to queries that might be non-empty.
Unified Privacy Accounting: The authors perform a unified privacy analysis for the entire forest construction rather than relying on standard composition across individual trees, yielding a tighter privacy bound.

Key Contributions

Lumberjack Algorithm: A new DP random forest method that combines randomized tree construction with data-dependent pruning, enabling the training of deep, high-utility trees under strict privacy budgets.
Novel Heavy Hitter Detection: A new algorithm for $(\epsilon, \delta)$ -DP heavy hitter detection in hierarchical data with error scaling of $O_{\epsilon, \delta}(\sqrt{\log h})$ for trees of height $h$ . The authors note this component may be of independent interest for other hierarchical data problems.
Theoretical Analysis: A tight privacy analysis that avoids the loose bounds of standard composition theorems and establishes a lower bound showing that the $O(\sqrt{\log h})$ scaling is near-optimal for methods supporting deep trees.
Empirical State-of-the-Art: Extensive evaluation demonstrating that Lumberjack consistently outperforms existing DP random forest baselines (including DiffPrivLib, SNR, Smooth Sensitivity, and greedy variants) across multiple datasets and privacy regimes.

Results
The authors evaluated Lumberjack on the Adult dataset and four binary classification tasks from the Folktables (California 2018) dataset.

Performance: Lumberjack consistently outperformed all prior DP random forest methods across privacy budgets $\epsilon \in \{0.5, 1, 2, 4, 8\}$ .
Comparison to Non-Private: While a gap remains compared to non-private Extra Trees, Lumberjack often outperforms non-private greedy decision trees even at moderate privacy levels.
Baseline Issues: The paper notes that many existing DP-RF baselines (particularly those using greedy tree construction) contain privacy flaws, such as data-dependent stopping criteria or incorrect sensitivity calculations, which the authors detail in an appendix. Despite these flaws in prior work, Lumberjack still surpasses their reported performance.
Scalability: The method successfully handles deep trees (depth up to 100) without the utility collapse seen in fully random tree approaches.

Significance and Claims
The paper claims that Lumberjack establishes a new state-of-the-art for differentially private random forests. The authors argue that their findings suggest carefully designed DP random forests can "close much of the utility gap" with non-private counterparts. They highlight that the combination of randomized construction with principled, privacy-aware pruning is a promising and underexplored direction.

The authors explicitly state that while they have addressed the utility gap for randomized forests, designing high-utility DP greedy random forests remains an open challenge. They suggest that future work may require more refined composition techniques and problem-specific mechanisms to further improve the privacy-utility trade-off. The paper also serves as a cautionary note regarding the rigor of privacy proofs in the existing literature, identifying privacy violations in over 10 prior papers.