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

• URL: http://arxiv.org/abs/2605.22756v1
• Date: Thu, 21 May 2026 17:23:04 GMT
• Title: Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
• Abstract summary: We introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility.<n>A key component of our approach is a novel $(varepsilon,)$-DP heavy hitter detection algorithm for hierarchical data.<n>Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods.
• Score: 13.259647860047982
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random forests are widely used in fields involving sensitive tabular data, but existing approaches to enforcing differential privacy (DP) typically degrade performance to the point of impracticality. In this paper, we introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility by constructing large random decision trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel $(\varepsilon,δ)$-DP heavy hitter detection algorithm for hierarchical data, whose error is $O_{\varepsilon,δ}(\sqrt{\log h})$ for trees of height $h$ and may be of independent interest. This favorable scaling enables the use of significantly deeper trees than in prior work, leading to improved expressiveness under privacy constraints. Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods, establishing a new state of the art. In particular, our approach yields substantial improvements in the privacy-utility trade-off for practical privacy budgets. Our findings suggest that carefully designed DP random forests can close much of the utility gap, highlighting a promising and underexplored direction for future research.

Related papers

• Entropy-Tree: Tree-Based Decoding with Entropy-Guided Exploration [52.52685988964061]
  Entropy-Tree is a tree-based decoding method that exploits entropy as a signal for branching decisions.<n>It unifies efficient structured exploration and reliable uncertainty estimation within a single decoding procedure.
  arXiv  Detail & Related papers  (2026-01-02T07:14:05Z)
• DiNo and RanBu: Lightweight Predictions from Shallow Random Forests [2.2080796858692575]
  DiNo and RanBu convert a small set of depth-limited trees into efficient, distance-weighted predictors.<n>RanBu matches or exceeds the accuracy of full-depth random forests in high-noise settings.<n>Both methods extend directly to quantile regression, maintaining accuracy with substantial speed gains.
  arXiv  Detail & Related papers  (2025-10-23T20:12:08Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Adaptive Split Balancing for Optimal Random Forest [8.916614661563893]
  We propose a new random forest algorithm that constructs the trees using a novel adaptive split-balancing method. Our method achieves optimality in simple, smooth scenarios while adaptively learning the tree structure from the data.
  arXiv  Detail & Related papers  (2024-02-17T09:10:40Z)
• Differentially-Private Decision Trees and Provable Robustness to Data Poisoning [8.649768969060647]
  Decision trees are interpretable models that are well-suited to non-linear learning problems. Current state-of-the-art algorithms for this purpose sacrifice much utility for a small privacy benefit. We propose PrivaTree based on private histograms that chooses good splits while consuming a small privacy budget.
  arXiv  Detail & Related papers  (2023-05-24T17:56:18Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Generalized Linear Bandits with Local Differential Privacy [4.922800530841394]
  Many applications such as personalized medicine and online advertising require the utilization of individual-specific information for effective learning. This motivates the introduction of local differential privacy (LDP), a stringent notion in privacy, to contextual bandits. In this paper, we design LDP algorithms for generalized linear bandits to achieve the same regret bound as in non-privacy settings.
  arXiv  Detail & Related papers  (2021-06-07T06:42:00Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. We propose a private sketch that supports a multitude of machine learning tasks including regression, classification, density estimation, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm.
  arXiv  Detail & Related papers  (2020-06-16T17:47:48Z)
• Balance is key: Private median splits yield high-utility random trees [4.90655427233754]
  We propose DiPriMe forests, a novel tree-based ensemble method for differentially private regression and classification. We show theoretically and empirically that the resulting algorithm exhibits high utility, while ensuring differential privacy.
  arXiv  Detail & Related papers  (2020-06-15T21:59:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.