Research map / Federated learning and privacy / Differential privacy

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

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Differentially private clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Lumberjack, a DP random forest that grows deep random trees and prunes them privately using a new (ε,δ)-DP heavy-hitter detector whose sensitivity grows only as sqrt(log h), outperforming prior DP random forest baselines on Adult and Folktables.

Problem

Differentially private random forests typically lose so much utility that they are impractical; fully random trees are depth-sensitive and data-independent, and greedy DP trees are costly in privacy budget and often flawed.

Approach

Build deep random trees with data-independent splits, then use a privacy-preserving heavy-hitter detector over the tree (overlapping binary searches querying middle layers with monotone propagation, plus sparse-histogram thresholding) to prune light nodes, reducing sensitivity from sqrt(h) to sqrt(1+log2 h) and analyzing the whole forest's privacy jointly.

Key results

• Lumberjack consistently and significantly outperforms prior DP random forest methods (DiffPrivLib, SNR, Smooth Sensitivity, Suihkonen) across privacy budgets epsilon in {0.5,1,2,4,8} with delta=1e-6 on Adult and Folktables tasks.
• The heavy-hitter detector achieves l2 sensitivity sqrt(1+floor(log2 h)) instead of sqrt(h) for the standard top-down baseline, with error O(sqrt(log h)) for trees of height h.
• Lumberjack often outperforms a non-private greedy decision tree even at moderate privacy levels, though a gap to non-private Extra Trees remains.

Surprising findings

• The authors identify privacy flaws in more than 10 published DP random forest papers, including in all greedy-tree works they examined, and in the SVT-based hierarchical heavy hitters algorithm of prior work.
• Some DP baselines (DiffPrivLib, Smooth Sensitivity) plateau in accuracy as epsilon grows, indicating their tree construction limits utility rather than privacy noise.

Limitations

• Gap remains to non-private Extra Trees; method only matches or beats greedy trees at moderate privacy.
• Lower bound shows the algorithm is only within O(sqrt(log h)) of optimal for epsilon<1, not tight.
• Uses fixed max depth 100 and random feature/threshold splits, leaving data-dependent splitting unexplored.

Experimental setup

Datasets: Adult Folktables ACSIncome (CA) Folktables ACSEmployment (CA) Folktables ACSPublicCoverage (CA) Folktables ACSTravelTime (CA)

Benchmarks: Adult Folktables ACSIncome (CA) Folktables ACSEmployment (CA) Folktables ACSPublicCoverage (CA) Folktables ACSTravelTime (CA)

Metrics: test accuracy

Baselines: DiffPrivLib random forest SNR Smooth Sensitivity random forest Suihkonen greedy DP trees sklearn Extra Trees (non-private) sklearn Decision Tree (non-private)

Builds on: Extremely randomized trees Sparse histogram DP thresholding Noisy binary search for private quantiles zCDP

Closest papers by meaning

• Improving Private Random Forest Prediction Using Matrix Representation (AAAI 2025 · similarity 0.89)
• On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)
• Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.86)
• Scalable Private Partition Selection via Adaptive Weighting (ICML 2025 · similarity 0.85)
• Privacy Profiles for Private Selection (ICML 2024 · similarity 0.85)
• Trained Random Forests Completely Reveal your Dataset (ICML 2024 · similarity 0.85)