arXiv CSopen access

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

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

Christian Janos Lebeda1,† , David Erb2,†,∗, Tudor Cebere1 , Aurélien Bellet1

arXiv:2605.22756v1 [cs.LG] 21 May 2026

† 1

Lead authors

PreMeDICaL, Inria, Université de Montpellier, INSERM, France 2 Technical University of Munich, Germany

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, privacypreserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel (ε,√δ)-DP heavy hitter detection algorithm for hierarchical data, whose error is Oε,δ ( 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.

1

Introduction

Random forests (RFs) [Breiman, 2001, Geurts et al., 2006] remain among the most accurate and most widely used methods for tabular prediction, often matching or outperforming more complex deep learning approaches [Fernández-Delgado et al., 2014, Grinsztajn et al., 2022, Kaggle, 2022, Uddin and Lu, 2024]. Built as ensembles of decision trees that recursively partition the feature space and aggregate predictions across leaves, RFs combine strong predictive performance with several practical advantages: they naturally accommodate heterogeneous feature types, require comparatively little hyperparameter tuning, and are often substantially more computationally efficient than deep neural networks [Grinsztajn et al., 2022]. These properties have made them a central tool in many high-stakes applications involving sensitive tabular data, from healthcare to financial risk assessment. At the same time, like other machine learning models, random forests can leak information about individual records used to train them. For instance, recent work has shown that, under certain conditions, some training examples can be reconstructed from publicly released random forest models [Ferry et al., 2024], motivating the need for formal privacy protections. Differential Privacy (DP) [Dwork et al., 2006] has emerged as the standard framework for addressing such risks by providing rigorous guarantees that an algorithm’s output changes only minimally when any one individual’s data is added or removed from the training set. ∗ Work done while visiting PreMeDICaL, Inria.

Preprint.

Figure 1: Toy example. Top row: fully random trees (depth=10) under ∞-DP. Bottom row: Lumberjack under (2, 10−6 )-DP. As the outlier class boundary shifts and the feature-space range changes (left to right), fully random trees fail to capture the structure, whereas our method continues to construct accurate trees.

Much of the literature on differentially private machine learning has focused on differentiable models, particularly deep neural networks trained with private optimization methods such as DP-SGD [Abadi et al., 2016, Ponomareva et al., 2023]. However, this paradigm can incur substantial utility costs under privacy constraints, because private gradient-based training injects noise into a high-dimensional optimization process, with costs that scale unfavorably with model dimensionality [Tramèr and Boneh, 2021]. As a result, private deep models may underperform substantially simpler learning methods. This motivates the exploration of alternative model classes with differently structured privacy-utility trade-offs, such as random forests. However, constructing differentially private RFs presents several challenges. The primary technical difficulty lies in building high-quality decision tree structures while satisfying strict privacy constraints. Decision tree algorithms recursively partition the dataset by selecting a feature and split threshold value. In standard non-private approaches [Breiman, 2001], these splits are chosen greedily by querying the data to optimize an impurity-based criterion. When adapted naively to the differentially private setting, such data-dependent procedures incur significant noise, leading to poor utility (e.g. [Patil and Singh, 2014, Fletcher and Islam, 2015a]).2 A common workaround is to use fully random trees, inspired by extremely randomized trees [Geurts et al., 2006]. In these approaches [Jagannathan et al., 2012, 2013, Fletcher and Islam, 2015b, 2017, Holohan et al., 2019], tree structures are generated using splits that are completely independent of the data, while the data is used only to label leaves. Unfortunately, fully random trees also suffer from significant limitations. Their performance is highly sensitive to tree depth: shallow trees yield overly large leaves, while deep trees produce leaves with too few samples for reliable privatized predictions. They are also strongly dependent on the underlying data distribution and often fail to capture informative structure, collapsing to majority-class predictions. We illustrate this behavior on a toy example in Figure 1, using an infinite privacy budget to emphasize that this is an inherent limitation of data-independent tree construction. Consequently, DP ensembles of fully random trees typically perform poorly. Overall, existing differentially private random forest methods, including both greedy and fully random variants, are of limited practical utility. Contributions. We introduce a novel differentially private random forest algorithm, Lumberjack. Our approach combines randomized tree construction, inspired by [Geurts et al., 2006] and prior work, with a principled privacy-aware mechanism that determines when to stop splitting. Concretely, we allocate part of the privacy budget to test whether a node contains a sufficient number of data points in feature space, allowing us to prune empty or low-density branches. A key challenge is enforcing this stopping criterion under differential privacy. We cast the problem of identifying split nodes as a private heavy-hitters problem over a tree of height h. While related problems have been studied by Ghazi et al. [2023], Biswas et al. [2024], their techniques do not directly apply. A naive approach that adds independent noise to each node count suffers from poor utility for deep trees, √ due to ℓ2 sensitivity (which determines the magnitude of noise needed for privacy) scaling as h. To overcome this, we exploit the monotone structure of rooted trees. Our key idea is to perform structured, highly overlapping noisy binary searches over the tree by querying nodes in a middle layer and propagating constraints upward and downward: heavy nodes imply 2 Unfortunately, the existing literature on differentially private random forests also includes several incorrect or flawed analyses. We found privacy issues in more than 10 papers, which we summarize in Section E. Despite the fact that these methods do not satisfy differential privacy as claimed, our approach still substantially outperforms their reported performance.

2

H Heavy

L

Light

?

Unmarked

H

3. Phase III (Top) Recurse top. Skip Heavy nodes.

H

?

L L

H L

?

L ?

L

1. Phase I (Mid Layer) Query layer. H marks up, L down.

L L

L

L

2. Phase II (Bottom) Recurse bottom. Skip Light nodes.

Figure 2: Example of a recursive iteration of our heavy hitter detector (Algorithm 1). Phase I (orange band) queries all nodes at the middle layer and marks them Heavy (H, blue) or Light (L, dashed orange), with implications for ancestors and descendants shown by arrows. Phase II (purple band) recursively explores subtrees containing unmarked nodes (?, gray), skipping Light nodes. Phase III (green band) recursively marks the upper half of the tree, skipping Heavy nodes.

heavy ancestors, while light nodes imply light descendants. As illustrated in Figure 2, this induces consistency constraints that reduce the problem to smaller independent subproblems of size at most p h/2, reducing sensitivity to 1 + log2 h. We further integrate techniques from sparse histogram estimation [Wilkins et al., 2024], improving both utility and computational efficiency. Finally, we develop a unified privacy analysis that bounds the privacy loss of the entire pruning procedure jointly over the forest construction, rather than relying on standard composition across trees, yielding a tighter privacy accounting. Empirically, Lumberjack enables the training of deep, high-utility random forests under strict privacy constraints, achieving new state-of-the-art results and consistently outperforming existing baselines across multiple datasets and privacy regimes.

2

Preliminaries

Problem setup. We consider a dataset D ∈ X n of n data points, where each point x ∈ D has a set of features and a label y ∈ Y. Features may be numerical or categorical; for numerical features we assume known bounds, and for categorical features a known domain. Our goal is to privately train a random forest to predict labels for unseen data. Random forests support both classification and regression; our contribution is a new differentially private tree-building algorithm applicable to both settings. We focus on classification in our presentation, as it is the primary setting in prior work. Random forests. A Random Forest (RF) is an ensemble method that combines predictions from multiple decision trees. Each tree recursively partitions the feature space based on feature-value splits until a stopping criterion is reached (e.g., maximum depth). Each leaf corresponds to a region of the feature space and defines a score function s : Y → [0, 1], typically derived from the training samples in that leaf. To predict, each tree outputs class scores, and the forest aggregates them (e.g., by summation) to select the class with highest total score. Common choices include majority vote, where each tree assigns all weight to a single class, or soft voting, where scores reflect class proportions within each leaf. Differential privacy. Differential privacy [Dwork et al., 2006] (DP) is a framework for rigorous, quantifiable privacy guarantees. Two datasets D ∼ D′ are neighbors if they differ by a single record (i.e., one addition or removal). Differential privacy requires that an algorithm’s output distribution is approximately indistinguishable on any pair of neighboring datasets. Several variants have been proposed to suit different settings. In this work, we report privacy guarantees in (ε, δ)-DP and use zero-concentrated differential privacy (zCDP) for simpler privacy accounting. Definition 1 ([Dwork and Roth, 2014] (ε, δ)-Differential Privacy). A randomized mechanism M : X ∗ → Z satisfies (ϵ, δ)-DP, if for any D ∼ D′ and every measurable set of outputs Z ∈ Z we have Pr[M(D) ∈ Z] ≤ eϵ Pr[M(D′ ) ∈ Z] + δ . Remark 1. When δ = 0, the guarantee is referred to as pure DP, or ε-DP. 3

Definition 2 ([Bun and Steinke, 2016] zero-Concentrated Differential Privacy). A randomized mechanism M : X ∗ → Z satisfies ρ-zCDP, if for any D ∼ D′ and all α ∈ (1, ∞), it holds that Dα (M(D) ∥ M(D′ )) ≤ ρα , where Dα (· ∥ ·) is the α-Rényi divergence between two distributions. We present some standard useful lemmas for (ε, δ)-Differential Privacy and ρ-zCDP in Section A.

3

Related Work

Differentially private random forests. Existing DP-RF methods fall into two main paradigms. The first paradigm [Patil and Singh, 2014, Fletcher and Islam, 2015a, Li and Li, 2017, Xin et al., 2019, Hou et al., 2019, Guan et al., 2020, Zhang et al., 2021, Consul and William, 2021, Vos et al., 2023, Suihkonen, 2023] allocates the privacy budget between private tree construction and leaf queries. Trees are built using impurity-based criteria similar to standard decision trees (e.g. Breiman [2001]), typically via the exponential mechanism [McSherry and Talwar, 2007]. We omit a detailed description due to the fact that our approach aligns more closely with the second paradigm, and because we identify privacy issues in all such works (see Section E). The second paradigm, loosely inspired by extremely randomized trees ("Extra Trees") [Geurts et al., 2006], constructs trees via random splitting [Jagannathan et al., 2012, 2013, Fletcher and Islam, 2015b, 2017, Holohan et al., 2019]. In these methods, splits are chosen independently of the data. A key limitation of these techniques is that trees are fully expanded to a fixed depth without data-dependent stopping. While this avoids spending privacy budget on structure learning, these approaches poorly adapt to the data and often leads to degraded performance, as illustrated in Figure 1 and in our experiments of Section 6. Our work departs from both paradigms by introducing a simple intermediate idea: we retain randomized splitting but use part of the privacy budget to determine when to stop splitting. Concretely, we build deep random trees and then privately prune them by identifying nodes that are sufficiently “heavy” in feature space; nodes whose parent is not heavy are removed. This allows data-dependent depth control without fully reverting to greedy tree construction. Leaf prediction is handled either by adding noise to label counts (e.g. Fletcher and Islam [2015a]) or by private majority selection (e.g. [Fletcher and Islam, 2017]). We support both variants in our implementation (see Section J). Remark 2. Most of the existing DP-RF methods rely on pure ε-DP, which is generally suboptimal for ensemble learning where privacy must be composed across many tree operations (e.g., repeated splits and leaf queries across many trees). Indeed, privacy costs compose linearly under ε-DP, leading to significantly higher noise compared to the approximate or concentrated DP variants we use in this work. Differentially private heavy hitters in trees. A key technical component of our work is a novel algorithm for heavy-hitters detection in hierarchical data. This problem is related to several classical tasks in differential privacy, including quantile estimation [Kaplan et al., 2022, Huang et al., 2021, Bun et al., 2015, Cohen et al., 2023] and private release of sparse histograms [Korolova et al., 2009, Cormode et al., 2012, Balcer and Vadhan, 2019, Wilson et al., 2020, Aumüller et al., 2022, Lebeda and Retschmeier, 2025, Kerschbaum √ et al., 2025]. Another related problem is count estimation in trees, where noise scales with O( h) with h the height of the tree. Despite extensive work on heavy hitters and hierarchical data release, there is limited work at their intersection. Ghazi et al. [2023] study 4.2 and 4.4), achieving a reduced dependence of √ √ a closely related problem (see Problems √ O( log h) at the cost of an additional n term, which is typically much larger than h. Another relevant prior work is Biswas et al. [2024], who consider private release of Hierarchical Heavy Hitters (HHH), a strict generalization of our setting; indeed, our problem can be addressed by post-processing the output for the HHH problem. While their construction would be applicable to our setting, we identify a subtle error in their privacy analysis (see Section D). We provide an expanded discussion of DP heavy hitters in Section B. 4

4

A Private Heavy Hitters Algorithm for Hierarchical Data

In this section, we present our novel private heavy hitters algorithm that will form the basis of our private random forest algorithm. We are given a tree structure T of height3 h. Each data point contributes to the count of a leaf node in T , and internal node counts are defined as the sum of their children’s counts. Our goal is to privately identify all nodes whose count exceeds a threshold τ , while ensuring that the selected nodes form a valid subtree. Baseline. A simple baseline traverses the tree in a top-down manner. At each node, we privately test whether its count exceeds the threshold τ , retaining nodes that pass and pruning subtrees whenever a node falls below the threshold. Since neighboring datasets affect counts along a single root-to-leaf √ path,p the sensitivity is h. We can thus apply the Gaussian mechanism to each count with noise scale σ = h/(2ρ) to satisfy ρ-zCDP. Our algorithm significantly improve upon this scaling in h. 4.1

Binary Search-Inspired Heavy Hitters Detection

High-level presentation of the approach. The pseudocode of our algorithm for finding heavy hitters in hierarchical data is given in Algorithm 1. The algorithm is parameterized by a private thresholding primitive C HECK T HRESHOLD, which privately tests whether a node count exceeds a threshold τ (it is "heavy"). The overall error of our method will be determined by the error of this primitive. Conceptually, the algorithm performs 2h highly overlapping noisy binary searches over the tree. To control privacy cost, nodes already identified as heavy by C HECK T HRESHOLD in one search are never queried again by another overlapping search. Figure 2 illustrates one iteration of the procedure. While noisy binary search is a classical tool for private quantile estimation in one dimension (e.g. the PrivQuant algorithm [Huang et al., 2021]), our main contribution is extending this idea to hierarchical tree structures and integrating it with sparse histogram techniques. Our key observationp is that each data point influences at most 1 + ⌊log2 h⌋ threshold√queries, yielding an ℓ2 -sensitivity of 1 + ⌊log2 h⌋. This is an exponential improvement over the h sensitivity of the standard top-down baseline. A naive implementation would still be impractical for deep trees due to the enormous number of empty nodes. To address this, we implement C HECK T HRESHOLD using techniques from the sparse histogram literature (Algorithm 2), allowing the algorithm to efficiently query only relevant (non-empty) nodes. This substantially improves both utility and computational efficiency. Finally, we derive tight (ε, δ)-DP guarantees by analyzing the privacy loss of the pruning procedure jointly, rather than through standard composition bounds. Technical details and analysis. We begin by establishing some basic properties of Algorithm 1. Formal proofs are deferred to Section F; here we focus on the intuition behind the main results. Lemma 3. For any tree T with height h and any x ∈ X , Algorithm 1 calls C HECK T HRESHOLD with at most 1 + ⌊log2 (h)⌋ (equivalently ⌈log2 (h + 1)⌉) nodes that contain x. Lemma 4. The error of Algorithm 1 is bounded by the error of C HECK T HRESHOLD. Specifically, if all calls to C HECK T HRESHOLD where #count(u) ≤ τ − α returns ⊥ then all nodes in T with count ≤ τ − α are labeled Light. Similarly, if C HECK T HRESHOLD returns ⊤ for all calls where #count(u) ≥ τ + β then all nodes with count ≥ τ + β are labeled Heavy. For Lemma 3, observe that each data point affects only a single query in Phase I and at most one recursive call of height at most h/2 (see Figure 2 for an illustration). This recursive structure directly yields the logarithmic sensitivity bound. For Lemma 4, we exploit the monotonicity of the tree. If a node is marked Heavy due to a heavy descendant, then the node itself must indeed be heavy since counts can only increase toward the root. Conversely, descendants of a Light node must also be light. These implications allow labels to propagate through the tree without additional queries. By Lemma 3, Algorithm 1 satisfies ρ-zCDP if we instantiate C HECK T HRESHOLD p with the Gaussian mechanism, analogous to the baseline but with ℓ2 -sensitivity reduced to 1 + ⌊log2 h⌋ (see Lemma 14). However, a direct implementation remains impractical for deep trees, since Phase I alone queries 2⌊h/2⌋ nodes. This leads not only to prohibitive computational and memory costs, 3We define the height as the number of nodes on a root-to-leaf path, including both endpoints. An alternative convention counts edges instead and thus differs by 1. We use depth to refer to this alternative convention. Thus, height(T ) = depth(T ) + 1.

5

Algorithm 1 M ARK H EAVY H ITTERS(T , h) Require: A tree T with height h and a threshold τ ∈ R. Require: A DP algorithm C HECK T HRESHOLDτ : N → {⊤, ⊥}. {Phase 1: Query the middle layer} 1: Let Lmid be the set of nodes at level ⌊h/2⌋ of T . 2: for all node u ∈ Lmid where u has not been marked do 3: if C HECK T HRESHOLDτ (#count(u)) = ⊤ then 4: Mark u and all ancestors of u as Heavy. 5: else 6: Mark u and all descendants of u as Light. 7: end if 8: end for {Phase 2: Recursively apply the algorithm to children that were not marked Light in Phase 1} 9: if h ≥ 3 then 10: Let Lmid + 1 be the set of nodes at level ⌊h/2⌋ + 1 of T . 11: for all node v ∈ Lmid+1 where v is NOT marked Light do 12: Let Tv be the subtree of T rooted at v. 13: M ARK H EAVY H ITTERS(Tv , h − ⌊h/2⌋ − 1). 14: end for 15: end if {Phase 3: Recursive apply the algorithm in the top part of the tree} 16: if h ≥ 2 then 17: Let T̂ be T restricted to layers {0, . . . , mid − 1}. 18: M ARK H EAVY H ITTERS(T̂ , ⌊h/2⌋). 19: end if p √ but also to error scaling as O(σ ln(2⌊h/2⌋ )) = Oε,δ ( h log h). Since most of these nodes are empty whenever h/2 > log2 n, we instead adapt techniques from sparse histogram estimation. Specifically, we introduce an adaptive variant of the method from Wilkins et al. [2024] to implement C HECK T HRESHOLD (see Algorithm 2). Threshold queries with sufficiently small counts are deterministically mapped to ⊥ (capturing all empty nodes under suitable parameters), while Gaussian noise is added only for the remaining queries before comparing against the threshold. Algorithm 2 GaussianSparseThreshold Require: Parameters σ, τ , and ∆. Require: Dataset D, adaptive counting queries q1 , q2 , q3 , . . . 1: for all i ∈ {1, 2, 3, . . . } do
2: Sample Zi ∼ N 0, σ 2 . 3: if qi (D) > τ − ∆ − 1 and qi (D) + Zi > τ then 4: Release ⊤. 5: else 6: Release ⊥. 7: end if 8: end for We present parameter settings for Algorithm 2 that ensure (ε, δ)-DP in Section G, and summarize them as part of our main theoretical result below. We next analyze the accuracy of the mechanism, measuring error in terms of worst-case misclassification. The following lemma follows from standard Gaussian tail bounds. Lemma 5. Let α ∈ R be the smallest value such that all nodes with count at least τ + α are marked Heavy by Algorithm 1, and all nodes with count at most τ − α are marked Light. If C HECK T HRESHOLD is implemented via Algorithm 2 with parameters σ > 0 and τ ≥ 1 + ∆, then with probability at least 1 − β, we have p α ≤ σ · 2 ln(2n⌈log2 (h + 1)⌉/β) . 6

We are now ready to present our main theoretical result. In contrast to prior work, which applies a composition theorem across trees to obtain privacy guarantees for the full forest, we directly analyze the privacy of the entire forest construction. This avoids the loss introduced by repeated composition under (ε, δ)-DP and yields a tighter overall bound. Theorem 6. Let A denote the algorithm that takes as input k trees with maximum height h, and runs Algorithm 1 where C HECK T HRESHOLD is instantiated as Algorithm 2 with parameters
σ, τ , and ∆. Then A satisfies (ε, δ)-DP where m = k(1 + ⌊log2 (h)⌋), γ(j) = (m − j) log Φ ∆ σ , and   m ∆ , δ ≥ max 1 − Φ σ  m−j   √  m−j   √  ∆ ∆ j (ε − γ(j))σ j (ε − γ(j)) σ √ √ +Φ max 1 − Φ Φ − − eε−γ(j) Φ − − , σ σ 2σ 2σ j∈[m] j j √   √  j (ε + γ(j)) σ j (ε + γ(j))σ √ √ max Φ − − eε+γ(j) Φ − − . 2σ 2σ j∈[m] j j If τ ≥ 1 + ∆, then with probability at least 1 − β, the algorithm correctly classifies all nodes with count ≤ τ − α as Light and all nodes with count ≥ τ + α as Heavy where p α ≤ σ · 2 ln(2kn⌈log2 (h + 1)⌉/β) . Furthermore, a variant of the algorithm that returns all nodes marked Heavy can be implemented in time and space O(knh). Proof. By Lemma 3 adding or removing a data point affects at most 1 + ⌊log(h)⌋ queries for each tree. The privacy guarantees thus follow from Lemma 15 (see Section G). The error bound holds for each tree with probability at least 1−β/k by Lemma 5, and thus with probability at least 1−β it holds for the entire forest simultaneously. For any τ ≥ 1 + ∆, Algorithm 2 returns ⊥ for all empty nodes. We may therefore avoid inspecting subtrees of empty nodes as we know these nodes would all be marked as Light. This does not affect the output distribution and thus preserves the DP guarantee. It is easy to see that there are at most O(nh) non-empty nodes in each tree. We discuss implementation details to achieve space and running time linear in the number of non-empty nodes in Section J. We use the parameters presented in Theorem 6 in our implementation, although the resulting privacy expressions are not very intuitive. For intuition, we provide below a simpler but looser closed-form bound in the regime ε < 1, which makes explicit the dependence on h, k, σ, and ∆. Lemma 7. Define A as in Theorem 6. If ε < 1, the parameters p p 2m ln(2.5/δ) σ= ∆ = σ · 2 ln(2m/δ) ε satisfy the condition in Theorem 6 for (ε, δ)-DP where m = k(1 + ⌊log2 h⌋). Remark 3. We give high probability bounds for the maximum error in Lemma 5 and Theorem 6. However, notice that the error for nodes with small counts is deterministically bounded by ∆. We can achieve a deterministic error bound using a variant of Algorithm 2 as discussed in Section H. 4.2

Lower Bound for Deep Trees

By Theorem 6, we should set the threshold τ to at least 1+∆. This ensures an efficient implementation for deep trees and improves utility by allowing us to deterministically label empty nodes. As a result, the threshold may be larger than what would be chosen in the non-private setting (e.g., in random forests), but we show below that this is unavoidable for any private method that supports deep trees. We now outline structural properties of heavy hitters algorithms that lead to our lower bound. First, observe that Algorithm 1 outputs at most n nodes per layer when τ ≥ 1 + ∆. While this is desirable, we allow for a broader class of algorithms that may output up to n2 nodes per layer, since slightly larger memory usage can still be practical. Any method exceeding this regime quickly becomes infeasible for moderate or large datasets, though the lower bound still applies for e.g. n3 nodes with slightly different constants. We additionally require that all sufficiently heavy nodes are recovered with high probability. Together, these conditions yield the following lower bound. 7

Lemma 8 (Informal). Let M denote an (ε, δ)-DP mechanism (for any ε > δ 2 ) that takes as input a tree T of height h > 4 log(n) and a dataset of size n, and outputs a set of at most n2 nodes per layer of T . Suppose that, with high probability, M outputs all nodes in T with count above some value  min(h,log(1/δ)) . τ̂ ∈ R. Then τ̂ ≥ Ω ε The lemma follows from a lower bound for sparse histograms [Balcer and Vadhan, 2019, Theorem 7.2], which (informally) states  that any (ε, δ)-DP mechanism that outputs few nonzero bins must incur  min(log d,log(1/δ)) error Ω for d-dimensional histograms. We can encode such a histogram over any ε d ≤ 2h−1 by using the leaf level of the tree. Technical details are deferred to Section I. √ Note that our algorithm is at most a factor O( log h) from optimal for ε < 1 (see Corollaries 17 and 18). We emphasize that tight lower bounds are not the main focus of this work, and leave closing this gap as an open problem.

5

Lumberjack: Our Differentially Private Random Forest Method

In this section, we describe how we use the heavy hitters algorithm from the previous section to instantiate our random forest method, Lumberjack. We split the algorithm into two components: one for privately constructing the tree structures and one for privatizing the leaf predictions. We ensure that constructing all trees together satisfies (ε1 , δ1 )-DP and that privatizing all leaf nodes across all trees satisfies (ε2 , δ2 )-DP. By basic composition, Lumberjack therefore satisfies (ε1 + ε2 , δ1 + δ2 )-DP. Tree construction. Given a maximum depth d, we recursively partition the feature space until this depth is reached. We then pass the resulting tree, restricted to nodes with depth {0, . . . , d − 1} (corresponding to height h = d) to our heavy hitters algorithm. The heavy hitters returned by the algorithm are retained as split nodes in the final tree. Any node whose parent is labeled Light is pruned, and the remaining Light nodes become the leaf nodes. To split the feature space, we select a feature uniformly at random. For numerical features, we assume access to a range [l, u] approximating the support of that feature (this is a standard assumption in DP). We then sample a threshold uniformly at random, t ∈ [l, u], and split the node accordingly. The ranges for the left and right child nodes are updated to [l, t] and [t, u], respectively. Categorical features are encoded using one-hot encoding, following common practice in non-private implementations (e.g., sklearn [Pedregosa et al., 2011]). When splitting on a categorical feature, we select a category that has not already been used in an ancestor node. Importantly, the privacy guarantees of Lumberjack are independent of the specific strategy used to generate random splits. Exploring alternative splitting schemes together with (privacy-preserving) data preprocessing is an interesting direction for improving utility in future work. Remark 4. Many non-private random forest algorithms train each tree on a subsample of the data using bootstrap sampling or sampling without replacement [Pedregosa et al., 2011, Athey et al., 2019], which improves diversity and reduces overfitting. In contrast, Lumberjack uses the full dataset for each tree, with randomness naturally coming from the splitting procedure, as in non-private Extra Trees [Geurts et al., 2006]. Leaf predictions. The last step is to privatize predictions in leaf nodes. Here, we focus the presentation on classification for simplicity, but the extension to regression is straightforward.4 We consider two mechanisms for privatizing leaf predictions. First, we support the exponential mechanism to select a single class label for each leaf. The prediction for the entire forest then consists of a majority vote across trees. Second, we support adding noise to class counts to obtain a private approximation of the class proportions, and average these proportions across trees. We did not observe significant performance differences between the two approaches in initial exploratory experiments; majority voting is used in our experiments. We perform privacy accounting in zCDP. Specifically, we compute the largest ρ such that any ρ-zCDP algorithm satisfies (ε2 , δ2 )-DP (see Lemma 9). We then apply a (ρ/k)-zCDP mechanism independently to each leaf, which yields an overall ρ-zCDP guarantee for the forest because each data point influences only a single leaf per tree. Additional implementation details are provided in Section J. 4 In this case, privatizing leaf predictions amounts to a set of private averaging queries.

8

6

Experiments

Baselines. We compare Lumberjack against several differentially private random forest methods, including three randomized tree-based approaches (IBM’s Differential Privacy Library DiffPrivLib [Holohan et al., 2019], SNR [Fletcher and Islam, 2015b] and Smooth Sensitivity [Fletcher and Islam, 2017]), and one greedy tree method (Suihkonen [Suihkonen, 2023]). As non-private baselines, we use sklearn’s Extra Trees and Decision Tree classifiers [Pedregosa et al., 2011]. We evaluate all methods across privacy budgets ε ∈ {0.5, 1, 2, 4, 8} with δ = 10−6 for Lumberjack. We note that some baselines have privacy issues, leading to weaker-than-claimed guarantees; this appears to be a recurring issue in prior work on DP random forests (see Section E). Datasets. We evaluate performance on the Adult dataset [Becker and Kohavi, 1996] and four binary classification tasks from Folktables (California 2018) [Ding et al., 2021]. We exclude ACSMobility due to uniformly poor performance across all methods, including non-private baselines. Dataset statistics are summarized in Table 1. Each experiment is repeated 5 times and results are averaged. Table 1: Summary statistics for the Adult and Folktables (CA) datasets. Dataset Features Categorical Classes Majority Datapoints Adult 14 8 2 76.1 % 48,842 ACSIncome (CA) 10 4 2 58.9 % 195,665 ACSEmployment (CA) 16 10 2 54.4 % 378,817 ACSPublicCoverage (CA) 19 10 2 63.1 % 138,554 ACSTravelTime (CA) 16 7 2 51.5 % 172,508 Hyperparameters. We use an 80-10-10 train/validation/test split. Hyperparameters for DiffPrivLib and non-private baselines are tuned on the validation set, without accounting for additional privacy cost. The performance of DiffPrivLib is sensitive to these choices. For SNR, Smooth Sensitivity, and Suihkonen, we use the settings recommended in the original papers. For Lumberjack, to demonstrate its robustness, we fix a maximum tree depth of 100 across all experiments. We train 30 trees on Adult and 50 trees on all Folktables tasks. We allocate 75% of the privacy budget to tree construction (ε1 = 0.75ε). We set τ = 1 + ∆ in all experiments. Results. As shown in Figure 3 (and Figure 4 in the appendix), Lumberjack consistently and significantly outperforms prior work across all evaluated privacy budgets. DiffPrivLib and Smooth Sensitivity achieve reasonable performance at small ε but do not improve as privacy relaxes. This is partly due to their reliance on data partitioning for leaf predictions, which allows them to perform accurate leaf predictions at small privacy budgets but shifts the burden to random tree construction. We also note that Smooth Sensitivity handles categorical features differently than DiffPrivLib: it splits on all values of a categorical feature instead of 1, which provides an advantage on Adult but does not generalize well to the other datasets. SNR outperforms the other baselines for some datasets but remains substantially below Lumberjack. Suihkonen matches previously reported results on Adult [Suihkonen, 2023] but performs poorly on the Folktables tasks. While a gap remains to non-private Extra Trees, Lumberjack often outperforms a non-private greedy decision tree even at moderate privacy levels. Overall, Lumberjack establishes a new stateof-the-art among DP random forest methods. Additional results are provided in Section C. Source code is available at https://github.com/daviderb/Lumberjack.

7

Conclusion

Despite the popularity of random forests in non-private machine learning, their differentially private counterparts remain relatively underdeveloped and, in many cases, problematic in both correctness and utility. Our work takes a step toward addressing these issues. We introduce Lumberjack, a new DP random forest method based on a combination of randomized tree construction and datadependent pruning based on a novel heavy hitters algorithm which may be of independent interest. Empirically, Lumberjack sets a new state-of-the-art in DP random forest methods. We believe that designing high-utility differentially private greedy random forests remains an open and promising direction. Achieving this goal will likely require more careful integration of advanced 9

Lumberjack (our work) SNR

Smooth Sensitivity DiffPrivLib

Sklearn Decision Tree

0.82

0.85

Accuracy

0.83 0.82 0.81

Accuracy

0.80

0.84

Accuracy

Suihkonen (greedy) Sklearn Extra Trees

0.78 0.76

0.80

0.78

0.74

0.80

0.76

0.72 2

4

6

8

2

4

6

8

2

4

6

Privacy Loss ε

Privacy Loss ε

Privacy Loss ε

a) Adult

b) ACSIncome

c) ACSEmployment

8

Figure 3: Test accuracy for the Adult and Folktables ACSIncome and ACSEmployment datasets. We exclude the Suihkonen baseline from ACSEmployment because its runtime was too high. tools from the DP literature, such as refined composition techniques, tighter privacy accounting, and problem-specific mechanisms that better exploit the structure of greedy splitting procedures. Overall, we hope our work helps clarify the design space and current status of DP random forests, and encourages further research on methods that more closely match the performance of their non-private counterparts while maintaining rigorous privacy guarantees.

Acknowledgements The work of David Erb was carried out while visiting the PreMeDICaL Inria team. The work of Christian Janos Lebeda, Tudor Cebere and Aurélien Bellet is supported by grant ANR-20-CE23-0015 (Project PRIDE) and the ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR. The work of Tudor Cebere is also supported by a Google PhD Fellowship in Privacy, Safety, and Security. This work was performed using HPC resources from GENCI–IDRIS (Grant 2023-AD011014018R2).

References Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, October 2016. doi: 10.1145/2976749.2978318. URL http://arxiv.org/abs/1607.00133. arXiv:1607.00133 [cs, stat]. John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson L. Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Review, 2, 2022. Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. 2019. Martin Aumüller, Christian Janos Lebeda, and Rasmus Pagh. Representing sparse vectors with differential privacy, low error, optimal space, and fast access. Journal of Privacy and Confidentiality, 12(2), Nov. 2022. doi: 10.29012/jpc.809. URL https://journalprivacyconfidentiality. org/index.php/jpc/article/view/809. Victor Balcer and Salil P. Vadhan. Differential privacy on finite computers. J. Priv. Confidentiality, 9 (2), 2019. Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 403–412. PMLR, 2018. Barry Becker and Ronny Kohavi. Adult, 1996. URL https://doi.org/10.24432/C5XW20. 10

Giulia Bernardini, Philip Bille, Inge Li Gørtz, and Teresa Anna Steiner. Differentially private substring and document counting. Proc. ACM Manag. Data, 3(2):95:1–95:27, 2025. Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, and Zhengyi Zhou. Differentially private hierarchical heavy hitters. Proc. ACM Manag. Data, 2(5):208:1–208:25, 2024. Leo Breiman. Random forests. Machine learning, 45(1):5–32, 2001. Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635–658. Springer, 2016. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634–649. IEEE Computer Society, 2015. Sílvia Casacuberta, Michael Shoemate, Salil P. Vadhan, and Connor Wagaman. Widespread underestimation of sensitivity in differentially private libraries and how to fix it. In CCS, pages 471–484. ACM, 2022. Tudor Cebere, David Erb, Damien Desfontaines, Aurélien Bellet, and Jack Fitzsimons. Privacy in theory, bugs in practice: Grey-box auditing of differential privacy libraries. CoRR, abs/2602.17454, 2026. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. In STOC, pages 472–482. ACM, 2023. Shorya Consul and Sinead A William. Differentially private random forests for regression and classification. Association for the Advancement of Artificial Intelligence, 2021. Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Thanh T. L. Tran. Differentially private summaries for sparse data. In ICDT, pages 299–311. ACM, 2012. Matt Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon, and Shengyu Zhu. Optimizing hierarchical queries for the attribution reporting api. In AdKDD@KDD, 2023. URL https://ceur-ws.org/ Vol-3556/adkdd23-dawson-optimizing-ceur-paper.pdf. Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021. Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3–37, 2022. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pages 265–284, Berlin, Heidelberg, 2006. Springer. Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. In STOC, pages 425–438. ACM, 2020. Manuel Fernández-Delgado, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hundreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(1):3133–3181, 2014. Julien Ferry, Ricardo Fukasawa, Timothée Pascal, and Thibaut Vidal. Trained random forests completely reveal your dataset. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 13545–13569. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr. press/v235/ferry24a.html. Sam Fletcher and Md Zahidul Islam. A differentially private decision forest. In AusDM, volume 168 of CRPIT, pages 99–108. Australian Computer Society, 2015a. 11

Sam Fletcher and Md Zahidul Islam. A differentially private random decision forest using reliable signal-to-noise ratios. In Australasian Conference on Artificial Intelligence, volume 9457 of Lecture Notes in Computer Science, pages 192–203. Springer, 2015b. Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth sensitivity. Expert systems with applications, 78:16–31, 2017. Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3–42, 2006. Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On differentially private counting on trees. In ICALP, LIPIcs, pages 66:1–66:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon. Denoising the us census: Succinct block hierarchical regression. arXiv preprint arXiv:2603.10099, 2026. Michaela Gotz, Ashwin Machanavajjhala, Guozhang Wang, Xiaokui Xiao, and Johannes Gehrke. Publishing search logs—a comparative study of privacy guarantees. IEEE Transactions on Knowledge and Data Engineering, 24(3):520–532, 2012. doi: 10.1109/TKDE.2011.26. Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. Zhitao Guan, Xianwen Sun, Lingyun Shi, Longfei Wu, and Xiaojiang Du. A differentially private greedy decision forest classification algorithm with high utility. Comput. Secur., 96:101930, 2020. Peaker Guo, Rayne Holland, and Hao Wu. Fast and optimal differentially private frequent-substring mining. CoRR, abs/2603.09166, 2026. Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, and Daniel Kifer. Accurate and scalable matrix mechanisms via divide and conquer. arXiv preprint arXiv:2604.00868, 2026. Naoise Holohan, Stefano Braghin, Pól Mac Aonghusa, and Killian Levacher. Diffprivlib: The ibm differential privacy library, 2019. URL https://arxiv.org/abs/1907.02444. James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27, 2015. Jun Hou, Qianmu Li, Shunmei Meng, Zhen Ni, Yini Chen, and Yaozong Liu. DPRF: A differential privacy protection random forest. IEEE Access, 7:130707–130720, 2019. Ziyue Huang, Yuting Liang, and Ke Yi. Instance-optimal mean estimation under differential privacy. In NeurIPS, pages 25993–26004, 2021. Geetha Jagannathan, Krishnan Pillaipakkamnatt, and Rebecca N. Wright. A practical differentially private random decision tree classifier. Trans. Data Priv., 5(1):273–295, 2012. Geetha Jagannathan, Claire Monteleoni, and Krishnan Pillaipakkamnatt. A semi-supervised learning approach to differential privacy. In ICDM Workshops, pages 841–848. IEEE Computer Society, 2013. Kaggle. 2022 Kaggle Machine Learning & Data Science Survey, 2022. URL https://www.kaggle. com/c/kaggle-survey-2022. Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In International Conference on Machine Learning, pages 10751–10761. PMLR, 2022. Florian Kerschbaum, Steven Lee, and Hao Wu. Optimal pure differentially private sparse histograms in near-linear deterministic time. CoRR, abs/2507.17017, 2025. 12

Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In WWW, pages 171–180. ACM, 2009. doi: 10.1145/1526709. 1526733. Christian Janos Lebeda and Lukas Retschmeier. The correlated gaussian sparse histogram mechanism. In FORC, LIPIcs, pages 23:1–23:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. Christian Janos Lebeda, Aleksandar Nikolov, and Haohua Tang. Weighted fourier factorizations: Optimal gaussian noise for differentially private marginal and product queries. CoRR, abs/2512.21499, 2025. Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. VLDB J., 24(6):757–781, 2015. Zekun Li and Shuyu Li. Random forest algorithm under differential privacy. In 2017 IEEE 17th International Conference on Communication Technology (ICCT), pages 1901–1905. IEEE, 2017. Jing Liu, Xianxian Li, Quanmin Wei, Songfeng Liu, Zhaohui Liu, and Jinyan Wang. A two-phase random forest with differential privacy. Appl. Intell., 53(10):13037–13051, 2023. Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv:1603.01699, 2016. Ryan McKenna and Daniel Sheldon. Permute-and-flip: A new mechanism for differentially private selection. In NeurIPS, 2020. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94–103. IEEE Computer Society, 2007. Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In ICLR. OpenReview.net, 2022. Abhijit Patil and Sanjay Singh. Differential private random forest. In ICACCI, pages 2623–2630. IEEE, 2014. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825–2830, 2011. Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ML: A practical guide to machine learning with differential privacy. J. Artif. Intell. Res., 77:1113–1201, 2023. doi: 10.1613/JAIR.1.14649. URL https://doi.org/10.1613/jair.1.14649. Ryan Rogers and Thomas Steinke. A better privacy analysis of the exponential mechanism. DifferentialPrivacy.org, 07 2021. https://differentialprivacy.org/ exponential-mechanism-bounded-range/. Sini Suihkonen. Differential privacy applied to random forest classification. Master’s thesis, University of Helsinki, November 2023. URL https://helda.helsinki.fi/handle/10138/. Master’s Programme in Data Science. Florian Tramèr and Dan Boneh. Differentially Private Learning Needs Better Features (or Much More Data), February 2021. URL http://arxiv.org/abs/2011.11660. arXiv:2011.11660 [cs, stat]. Shahadat Uddin and Haohui Lu. Confirming the statistically significant superiority of tree-based machine learning algorithms over their counterparts for tabular data. PLOS ONE, 19(4):1–12, 04 2024. doi: 10.1371/journal.pone.0301541. URL https://doi.org/10.1371/journal.pone. 0301541. Daniël Vos, Jelle Vos, Tianyu Li, Zekeriya Erkin, and Sicco Verwer. Differentially-private decision trees and provable robustness to data poisoning. arXiv preprint arXiv:2305.15394, 2023. 13

Arjun Wilkins, Daniel Kifer, Danfeng Zhang, and Brian Karrer. Exact privacy analysis of the gaussian sparse histogram mechanism. J. Priv. Confidentiality, 14(1), 2024. Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private SQL with bounded user contribution. Proc. Priv. Enhancing Technol., 2020(2):230–250, 2020. doi: 10.2478/POPETS-2020-0025. URL https: //doi.org/10.2478/popets-2020-0025. Yingtai Xiao, Guanlin He, Danfeng Zhang, and Daniel Kifer. An optimal and scalable matrix mechanism for noisy marginals under convex loss functions. In NeurIPS, 2023. Bangzhou Xin, Wei Yang, Shaowei Wang, and Liusheng Huang. Differentially private greedy decision forest. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2672–2676. IEEE, 2019. Yaling Zhang, Pengfei Feng, and Yao Ning. Random forest algorithm based on differential privacy protection. In 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pages 1259–1264. IEEE, 2021.

A

Additional Preliminaries

Here we present standard technical results from differential privacy. Any ρ-zCDP guarantee can be converted to (ε, δ)-DP guarantees as follows. Lemma 9 ([Bun and Steinke, 2016]). Let M : X ∗ → Z be a randomized mechanism that satisfies ρ-zCDP. Then, M satisfies (ε, δ)-DP. for all ε ≥ ρ and 2

2e−(ε−ρ) /4ρ q δ= . 4 2 1 + ε−ρ (1 + ε−ρ 2ρ + 2ρ ) + πρ The consecutive execution of differentially private mechanisms yields another differentially private mechanism. We use the following composition theorems. Lemma 10 ([Dwork and Roth, 2014] Basic Composition). Let M1 : X ∗ → Z1 , M2 : X ∗ × Z1 → Z2 be randomized mechanisms that satisfy (ε1 , δ1 )-DP and (ε2 , δ2 )-DP respectively, then the composed mechanism M(D) = M2 (D, M1 (D)) satisfies (ε1 + ε2 , δ1 + δ2 )-DP. Lemma 11 ([Bun and Steinke, 2016] zCDP Composition). Let M1 : X ∗ → Z1 , M2 : X ∗ × Z1 → Z2 be randomized mechanisms that satisfy ρ1 -zCDP and ρ2 -zCDP respectively, then the composed mechanism M(D) = M1 (D, M2 (D)) satisfies ρ1 + ρ2 -zCDP. A key property of differential privacy is that the usage of the output of a private mechanism in any computation cannot make the output less private. Definition 12 ([Dwork and Roth, 2014] Post-Processing). A randomized mechanism M : X ∗ → Z with privacy guarantee g is immune to post-processing if for any randomized mapping f : Z → W, f ◦ M : X ∗ → W satisfies g. Lemma 13 ([Dwork and Roth, 2014, Bun and Steinke, 2016]). Every mechanism that satisfies a (ε, δ)-DP or ρ-zCDP guarantee is immune to post-processing. The Gaussian mechanism as presented below is one of the most used DP techniques. Lemma 14 ([Bun and Steinke, 2016, Balle and Wang, 2018], The Gaussian mechanism). Let ′ q : X ∗ → Rd be a set of queries with ℓ2 sensitivity ∆q := maxD∼D′ ∥q(D)
− q(D )∥2 . 2Then the 2 2 mechanism that outputs q̃(D) = q(D) + Z where Z ∼ N 0, (∆q) σ Id satisfies (2/σ )-zCDP and (ε, δ)-DP for

1 1 δ ≥ Φ 2σ − εσ − eε Φ − 2σ − εσ . 14

B

More Details of Related Work for Differentially Private Heavy Hitters

Here we present an expanded discussion of the related work on differentially private heavy hitters. A key technical component of our work is a novel algorithm for the heavy hitters problem for hierarchical data. For this problem, we are given a tree T with height h. Each data point increase the count of a single leaf by 1, and each internal node stores the sum of counts for all child nodes.5 We want to privately detect all nodes with count above some threshold τ . Notice that the root of T is always heavy and the set of heavy hitters form a tree with the same root (except for the special case where no nodes are heavy). We exploit this structure in our algorithm. This problem has connections both to differentially private quantile estimation and sparse histograms. If we restrict our view to a single path from the root to the leaf, we want to find the first node with count below the threshold. This is equivalent to a quantile query (also known as threshold queries). In the (discrete) quantile problem, we have n data points xi ∈ {1, . . . , h}. The goal is to find the largest q such that |{i ∈ [n] : xi ≤ q}| ≤ τ for some threshold τ . Standard approaches include √ private selection using the exponential mechanism which has rank error O(log h/ε) (or O(log h/ ρ) under p ρ-zCDP) [Kaplan et al., 2022] and noisy binary search which has rank error O( log h log log h/ρ) for ρ-zCDP [Huang et al., 2021]. Other techniques achieve better dependence on h (e.g. Bun et al. [2015], Cohen et al. [2023]), but have larger constants and are only preferred for very large h. If we instead restrict out view to a single layer of the tree, the problem is equivalent to detecting heavy hitters in a histogram. For deeper layers in the tree, this histogram must be sparse, since the number of nodes exceeds the number of data points. In the sparse histogram problem, we have n data points xi ∈ [d] for some d ≫ n. We want to privately estimate |{i ∈ [n] : xi = j}| for all j ∈ [d]. Variants of this problem have been thoroughly studied in the differential privacy literature [Korolova et al., 2009, Cormode et al., 2012, Gotz et al., 2012, Balcer and Vadhan, 2019, Wilson et al., 2020, Aumüller et al., 2022, Wilkins et al., 2024, Lebeda and Retschmeier, 2025, Kerschbaum et al., 2025]. The optimal error for this problem is O(min(log(d), log(1/δ))/ε). We rely on a lower bound from this literature to derive a lower bound for our setting. As such, the heavy hitters problem we consider generalizes both quantile queries and sparse histograms. In fact, we leverage and adapt techniques from both problems in our algorithm. A related problem is the task of releasing counts√for hierarchical data. The straightforward approach samples independent Gaussian noise √ scaled by h to each count (here h is the maximum height of a tree and thus the ℓ2 sensitivity is h). Several papers [Honaker, 2015, Dawson et al., 2023, Ghazi et al., 2026] leverage redundancy in the tree structure to achieve better utility by post-processing the noisy queries. An alternative approach to exploiting redundancy in queries is to directly add correlated noise using the factorization mechanism framework [Li et al., 2015, Edmonds et al., 2020]. Assuming that all nodes on the same layer in T have the same branching factor, the tree structure can be encoded as h marginal queries. Marginal queries have received significant study in differential privacy and recent results provide optimal factorizations [Xiao et al., 2023, Lebeda et al., 2025, He et al., 2026]. Both the postprocessing techniques and the √ factorization framework lead to useful constant factor improvements, but the noise still scales with h. Since there arep2h − 1 noise samples, one for each node, the expected largest noise sample has magnitude Oε,δ (σ log(2h )) = Oε,δ (h). In many use cases, h is relatively small; for instance, the data used for the US 2020 Decennial Census [Abowd et al., 2022, He et al., 2026] has √ 6 levels √ (Country, State, County, Tract, Block Group, and Block), so multiplying noise by a factor h = 6 ≈ 2.45 is acceptable for these problems. We aim to support significantly deeper trees, and thus require a much lower dependency on the tree height. Despite a lot of prior work in differential privacy both on heavy hitters estimation and release of hierarchical data, there is limited work on the intersection. Ghazi et al. [2023] consider the same heavy hitters problem as us as part√ of their work (see Problems 4.2 and√4.4 therein). They reduce the dependency on√the height to O( log h). However, they introduce a n term, which is typically much higher than h. The most relevant related work is by Biswas et al. [2024] who consider the task of privately releasing Hierarchical Heavy Hitters (HHH), a generalization of the heavy hitters problem. In the HHH problem, the count of a hierarchical heavy hitter is not included in the sum for 5We focus on binary trees in the presentation but our algorithm works with any branching factor. More generally, our heavy hitters algorithm is applicable to any setting where adding a data point only changes the value of nodes that are all part of the same path from root to leaf and the value of a parent node is never smaller than any child value.

15

the parent node. Note that this is a strictly harder problem, since we can recover the tree of heavy hitters by post-processing the HHH set. Biswas et al. [2024] study the problem in both the static and the streaming settings. In the static setting they propose an algorithm inspired by the Sparse Vector Technique (SVT) [Dwork and Roth, 2014, Lyu et al., 2016] with noise scale independent of the height of the tree. The error scales only with O(max(log(nh), log(h/δ))/ε). Since their setting is strictly harder than our heavy hitters problem, we would ideally use their algorithm for detecting heavy hitter. Unfortunately, we have discovered a subtle mistake in their privacy proof, as we discuss in Section D. Two recent papers [Bernardini et al., 2025, Guo et al., 2026] study the problem of privately identifying frequent substrings. Their techniques relies on a tree-based data structure. Although the setting is not directly comparable to the problem we consider in this paper, we believe (adaptations of) our algorithm may be relevant for identifying frequent substrings under approximate DP.

C

Additional Experimental Results and Details

Results on additional datasets. Figure 4 shows results for datasets that were left out of the main text. Similar to Figure 3, we outperform all the private competitors. Lumberjack (our work) SNR

Smooth Sensitivity DiffPrivLib

Suihkonen (greedy) Sklearn Extra Trees

Sklearn Decision Tree

0.66 0.72 0.64 0.70

Accuracy

Accuracy

0.62

0.68

0.60

0.58 0.66 0.56 0.64 0.54 1

2

3

4

5

6

7

8

1

2

3

4

5

Privacy Loss ε

Privacy Loss ε

a) ACSPublicCoverage

b) ACSTravelTime

6

7

8

Figure 4: Experimental results for two additional Folktables classification tasks.

Hyperparameters for baselines. The SNR implementation computes most hyperparameters based on the input. They do not support continuous features directly, so the domain has to be discretized. We set the number of bins to 5 reflecting parameters used in the paper [Fletcher and Islam, 2015b]. For Smooth Sensitivity, we only set the number of trees since the depth is computed using the number of features. We train 30 trees for all benchmarks because they used 30 trees for their experiments with Adult [Fletcher and Islam, 2017]. Note that we used the original implementation which contains a known privacy bug. The bug is fixed in the DiffPrivLib variant of the algorithm, but we include the original source code as a baseline because the implementations handle categorical features in 2 different ways. For DiffPrivLib, we tuned hyperparameters using the validation set. Strictly speaking, one should spend part of the privacy budget for this tuning, since the choice of hyperparameters can reveal information about the dataset (See Papernot and Steinke [2022]). However, we do not include this in the privacy cost to mimic the best case scenario where an analyst picked good hyperparameters. This implementation often predicts the majority class for all data points if we pick bad parameters. We consider forest sizes in increments of 5 trees and explore tree depth up to 19. The typical selected parameters were 10-20 trees and depth 15-17. Note that increasing the search to deeper trees quickly becomes infeasible due to memory usage since DiffPrivLib, unlike Lumberjack, stores all empty nodes in the tree. For example, at depth 20, there are more than a million nodes in a tree so most of the memory usage is dedicated to nodes that contain no data points. For DiffPrivLib, we did not use one-hot encoding for categorical features. The implementation does not support weighted feature 16

sampling, and the classifier performs much worse with one-hot encoding. Instead, we set the value to the index in the order of the original data. For Suihkonen, we used the same hyperparameters that the original work used for Adult, which is a forest of 15 trees with depth 7. When splitting on categorical featuresn they split on a set rather than a single category. They use a parameter to determine the size of subsets, which we set to 8. The accuracy on Adult roughly matches the plot from [Suihkonen, 2023]. We did not change the hyperparameters for the Folktables tasks except for only considering "one vs. all" splits on categorical attributes. This was required for runtime purposes. The choice of this parameter affects the performance on these datasets, but extensive hyperparameter tuning for this algorithm was impractical since certain choices are computationally expensive. Note that we did not include the implementation of Suihkonen [2023] for ACSEmployment because the runtime was too high for this dataset. We found privacy concerns in all papers from the greedy decision tree paradigm (see Appendix E), making it unclear which technique should be regarded as the prior state of the art. We use Suihkonen as a representative technique from this paradigm. As it performs very poorly on folktables experiments, we considered including an additional baseline based on greedy decision trees. However, we did not find any suitable candidate among existing literature. Early works such as Patil and Singh [2014], Fletcher and Islam [2015a] are known to perform poorly in general, and they do not directly support continuous features. The runtime of Consul and William [2021] is exponential in the size of categorical features, which is infeasible for several of the datasets we consider. Many of the other papers do not provide any source code. Toy Example in Figure 1. The dataset is constructed by combining the make_moons and make_blobs dataset generators from scikit-learn. We create 10000 data points in total, 5500 red points, 4000 blue points, and 500 green points. We add an offset to the moons such that the feature bounds are non-negative. The center of the green outlier blob is distance 1 from the upper bound of both features. We set the bounds to [0, 5], [0, 50], and [0, 5000] for Feature 1 and [0, 4], [0, 40], and [0, 4000] for Feature 2. We train 25 trees and use majority voting for classification. We tested various depths for the fully random trees for the [0, 5] × [0, 4] setting and found that depth 10 splits the classes fairly well. When the bounds increase, most of the feature space is empty. As a result, many of the random splits create empty nodes, and the fully random trees completely fail to separate the moons. For Lumberjack, we set ε1 = 0.75ε and use a max depth of 100. Although many of the early splits in each trees create empty leaves for the extreme [0, 5000] × [0, 4000] setting, our algorithm eventually locates the relevant part of the feature space because it adapts to the number of data points.

D

Technical Issue with SVT-based Argument by Biswas et al. [2024]

In this section, we describe a subtle mistake that we discovered in the privacy analysis of an algorithm designed by Biswas et al. [2024] to find Hierarchical Heavy Hitters. At a high level, their algorithm traverses the tree in bottom-up order and privately compares the count of each node against a noisy threshold. Crucially, the noise for this comparison does not scale with h as the algorithm use a technique inspired by the popular Sparse-Vector-Technique (SVT) [Dwork and Roth, 2014, Lyu et al., 2016]. Biswas et al. [2024] consider a more general version of the problem that we address in Section 4, their technique could in principle be used to implement a variant of Lumberjack. However, as we show below, the strong privacy properties of SVT do not appear to transfer directly to trees. Despite our efforts, we have not been able to resolve√the issue with their algorithm (apart from the trivial fix of increasing the noise scale by a factor O( h)). At a high level, the proof of the (ε, δ)-DP privacy guarantee for Algorithm 1 of the paper [Biswas et al., 2024, Theorem 3.1] proceeds as follows for any two neighboring datasets X and X ′ = X ∪ x′ : Separate the nodes of the tree into (i) the path that is affected by adding or removing the element x′ and (ii) the remaining part of the tree. For the former, they apply an argument similar to the proof of the Sparse-Vector-Technique (SVT) [Dwork and Roth, 2014, Lyu et al., 2016]. Since they add a noise sample to the threshold which correlates all these queries, they can output any number of "negative" comparisons (⊥) on the path at no additional privacy cost. They ensure that each data point is only part in one "positive" query (⊤), which ultimately achieves a noise scale that is independent of the height of the tree. For the latter, they point out that the output distributions for these nodes are unaffected by the change in datasets. 17

We argue that each analysis on it’s own is correct, but the two arguments are not compatible and therefore break when combined. On a high level the issue is that the first argument utilizes the fact that the entire output sequence of their algorithm is slightly correlated to achieve stronger privacy, while the second argument relies on parallel composition which requires separate parts of the output to be completely independent. Thus we cannot benefit from the first privacy properties of SVT while simultaneously ignoring the effect on the other part of the output. We point out concrete parts of the proof that breaks in more details below. The proof in the paper divides the nodes into three groups, but, to point out the issue in the proof, it is sufficiently to only consider the partition into the affected ("Active" nodes in the paper) and the unaffected ("Unrelated" and "After" nodes in the paper) nodes. Equation 9 in the paper then writes the probability of observing any output ⃗a = (a1 , . . . , am ) as m Y i=1

p(βi , ai ) =

Y

p(βi , ai ) ·

i∈Iaffected

Y

p(βi , ai ) ,

i∈Iunaffected

where m is the number of nodes in the tree, βi is the random variable of the value of node i in the output of the h mechanism using iinput X and ai is the observed output. p(βi , ai ) is shorthand notation for Pr βi = ai |β⃗−i = ⃗a−i where β⃗−i = (β1 , . . . , βi−1 ) and ⃗a−i = (a1 , . . . , ai−1 ). The nodes are indexed in a bottom-up level order, and βi takes on the value ⊥ or ⊤. βi′ will denote the corresponding random variable when the mechanism is run on X ′ . For the unaffected nodes, the proof in [Biswas et al., 2024] states (page 20 and 21, paragraphs Unrelated Nodes and After Nodes) that for any i ∈ Iunaffected p(βi , ai ) = p(βi′ , ai ). However, β⃗−i can also include βj with j ∈ Iaffected . This means that even though βi and βi′ would have the same distribution unconditionally (Pr[βi = ai ] = Pr[βi′ = ai ]), the equality does not hold, because the conditions of the probabilities are not identical. The noise sample added to the threshold is denoted by γ, and we have Pr[βj = aj |γ] ̸= Pr[βj′ = aj |γ] for any j ∈ Iaffected . The value of γ affects all queries and observing βj and βj′ reveal different information about γ which breaks the equality. Regarding the affected nodes, the proof applies an SVT-style argument (page 22 and 23, paragraph Active Nodes), in which an essential part is conditioning on the threshold noise γ [Lyu et al., 2016]. The proof of Lyu et al. [2016] leverages the fact that the noisy threshold is never revealed to avoid the cost of composition. Unfortunately, in this setting, conditioning on γ in this way is not as straightforward, since the conditions can be affected by observations βj with j ∈ Iunaffected . Intuitively, we learn information about γ from all the outputs of the unaffected nodes. In the SVT argument, we do not pay the privacy cost for additional queries that return ⊥. However, queries for Iunaffected can contain both ⊥ and ⊤, so we cannot ignore their impact in the privacy argument. In extreme cases for huge worst-case input we could infer the approximate value of γ from just the unaffected queries. It becomes clear that both directions of the privacy proof break due to the shared dependence on γ. It is not possible to index the nodes in a way such that this does not occur, which shows the incompatibility between the two arguments.

E Privacy Concerns in Prior Work on Differentially Private Random Forests We identified privacy concerns in many published papers on differentially private random forests. In this section, we summarize a selection of these issues. Our goal is not to provide a comprehensive review of all privacy proofs in the literature; rather, we aim to highlight recurring pitfalls. While differential privacy algorithms and implementations are known to be error-prone in general (see, e.g., [Casacuberta et al., 2022, Cebere et al., 2026]), this line of work nonetheless concentrates a number of mistakes that should be readily apparent to experts in differential privacy. Some of these issues directly affect the core claims of the corresponding works, while others could likely be resolved through relatively minor modifications to the algorithms. We do not attempt to categorize the severity of the identified problems. We also note that several papers are written in a way that makes their technical claims difficult to verify. We hope that this discussion will help improve the rigor, reproducibility, and comparability of future work in this area. 18

An additional purpose of this section is to justify our decision not to include several prior works as baselines in Section 6. Due to the identified privacy concerns, it is unclear which papers should be regarded as the prior state of the art for differentially private random forests. In particular, we found at least one privacy issue in every technique based on greedy random forests. Nevertheless, our method matches or exceeds the performance claimed by these works (e.g., those using Adult typically report an accuracy of around 79-82%). Recurring problems. Several types of differential privacy violations appear repeatedly throughout this line of work. One common issue concerns the stopping criterion used during tree construction. In non-private decision trees, it is standard practice to stop splitting when all data points in a node share the same label. Under differential privacy, however, this condition cannot be checked deterministically, since doing so directly reveals information about the underlying data. Unfortunately, we found this issue to be widespread in the literature [Patil and Singh, 2014, Xin et al., 2019, Hou et al., 2019, Guan et al., 2020, Zhang et al., 2021, Liu et al., 2023, Vos et al., 2023, Suihkonen, 2023]. Another recurring problem arises in methods that use the exponential mechanism to select split points for continuous features. The candidate split set itself must be chosen in a privacy-preserving manner. In particular, using the observed feature values directly as the only candidate split points reveals information about the exact locations of data points and therefore violates differential privacy. One possible remedy is to sample intervals between adjacent data points proportionally to their length and utility, and then select a point uniformly within the chosen interval, as proposed by Kaplan et al. [2022]. Nevertheless, several works instead construct a data-dependent discrete candidate set, which violates differential privacy [Li and Li, 2017, Guan et al., 2020]. Finally, Patil and Singh [2014], Li and Li [2017] employ bootstrapping without properly accounting for its privacy cost, resulting in incorrect privacy guarantees. Specific issues in each paper.

Below we point to the location of specific issues in each paper.

1. Patil and Singh [2014] deterministically stop splitting when all samples in a node belong to the same class (Section IV, subsection D, point 2). This data-dependent control flow in the construction of the tree violates DP. Additionally, they do not properly account for bootstrapping which results in an inaccurate privacy guarantee (Algorithm 1, step 3). 2. Fletcher and Islam [2015a] calculate the local sensitivity based on noisy values instead of using data-independent global sensitivity (Algorithm 1, line 17). 3. Li and Li [2017] use the midpoint between adjacent data points as candidates when splitting continuous features (Section III, Subsection D, Equation 5). This is heuristically better than using the data points themselves, but it still breaks DP. They also do not properly account for bootstrapping (Step 2a of the algorithm in Section III, Subsection B). 4. Hou et al. [2019] use a deterministic data-dependent stopping criterion in the splitting algorithm (Algorithm 1, Line 5). Quoting directly from the paper: "The condition that the decision tree stops growing includes: 1) All samples in the node have the same classification result". 5. Xin et al. [2019] have data-dependent stopping conditions in their tree-building process. They do not split nodes with 10 or fewer data points (Algorithm 2, Line 1), and they deterministically stop splitting pure nodes (Algorithm 2, line 5). 6. Guan et al. [2020] sort values of continuous attributes and use the average of buckets with 5 data points as candidates for the splitpoint (Algorithm 1, Line 10). The candidate set differs between neighboring datasets which breaks DP. Their implementation also deterministically does not split on pure nodes (Algorithm 1, line 4). 7. Zhang et al. [2021] deterministically stop splitting when all samples in a node belong to the same class (Algorithms 1, 2, and 3, see termination condition). 8. Consul and William [2021] use data-dependent sensitivity in both the splits (Equation 6) and the leaf nodes in the case of regression trees (Section 3, paragraph Estimating leaf node parameters).6 6 Incidentally, we note that we could not use this algorithm as a baseline for computational reasons. They inspect all possible subsets when splitting categorical features. This is infeasible for features with many values. The native-country feature from the Adult dataset has 41 possible values so they should evaluate 240 possible splits.

19

9. Liu et al. [2023] deterministically stop splitting on pure nodes (Algorithm 2, Line 4). In the second part of their algorithm they sample points with weights based on misclassification without accounting for it (Algorithm 3, Line 9). This leads to a higher privacy loss for outlier data points. 10. Vos et al. [2023] (who focus on the setting of a single decision tree rather than building a forest) deterministically stop splitting at pure nodes (Algorithm 1, line 7). 11. While we use Suihkonen [2023] as a baseline for greedy forests in our experiments, the code does contain some privacy violations including data-dependent stopping criteria for splitting (line 496 in the implementation), deterministically labeling pure leaf nodes (line 492 in the implementation) and sensitivity miscalibration (line 242 in the implementation). Finally, we note that Fletcher and Islam [2017] originally contained a privacy error that was later corrected. The original algorithm used a variant of the exponential mechanism calibrated with smooth sensitivity. Their random forest method was subsequently implemented in the popular open-source library DiffPrivLib [Holohan et al., 2019]. During the development, Naoise Holohan identified a mistake in the privacy proof for the smooth sensitivity approach. As a result, the DiffPrivLib implementation was updated to use the Permute-and-Flip algorithm [McKenna and Sheldon, 2020] instead, and Fletcher & Islam later added an addendum to an updated arXiv version of the paper describing the issue. We commend Fletcher & Islam, and the DiffPrivLib developers, for publicly documenting and correcting the issue.

F

Missing Proofs from Main Body

Here we present proofs of technical results from the main body of the paper. Proof of Lemma 3. Proof. The element x is associated with a unique path Px from the root to a leaf. We want to show that at most 1 + ⌊log2 (h)⌋ nodes along Px are queried. In Phase 1, the algorithm queries one node u ∈ Px at level mid = ⌊h/2⌋ (if it is not already marked). We show in the following that Px is queried in at most one recursive call of the algorithm, which implies the desired bound. The mark of u determines which recursive phase may subsequently query nodes on Px : • Case 1: u is marked Light. All descendants of u (the bottom half of Px ) are marked Light. Consequently, the recursive step containing Px is skipped in Phase 2 by the condition on Line 11. Any further queries to Px occur in the recursive call on the top part of the tree in Phase 3. • Case 2: u is marked Heavy. All ancestors of u (the top half of Px ) are marked Heavy. Because marked nodes are skipped by Line 2, Phase 3 never queries any nodes in Px . When h > 2, Px is part of exactly one recursive call in Phase 2 via the subtree Tv that contains Px . In both cases, x is involved in exactly one query and at most one recursive call on a tree of height ≤ ⌊h/2⌋. Let Q(h) be the maximum number of queries for x in a tree of height h. We have the recurrence: Q(h) ≤ 1 + Q(⌊h/2⌋). With the base case Q(1) = 1, this yields Q(h) ≤ 1 + ⌊log2 (h)⌋ as desired. Proof of Lemma 4. Proof. It follows from the monotonicity of the tree structure. The statement clearly holds for any nodes that are queried by C HECK T HRESHOLD. We have to show that it also holds for nodes that are marked without being directly queried. Such nodes that are marked Light are descendants of some node u where we had C HECK T HRESHOLDτ (#count(u)) = ⊥. These nodes therefore have a count < τ + β since u cannot have a lower count than any of it’s descendant. Similarly, nodes that are marked Heavy are ancestors of some node where C HECK T HRESHOLD returned ⊤ and thus must have a count of > τ − α. 20

Proof of Lemma 5. Proof. Since 0 ≤ τ − ∆ − 1 all empty nodes are correctly classified as Light. Let m denote the number of calls to C HECK T HRESHOLD with non-zero counts performed by Algorithm 1. It follows from Lemma 3 that m ≤ n⌈log2 (h + 1)⌉. Let (Z1 , . . . , Zm ) denote the noise samples for these queries. By a standard Gaussian tail bound we have Pr[|Zi | ≥ t · σ] ≤ 2 exp(−t2 /2) and thus Pr[|Zi | ≥ α] ≤ β/m. By applying a union bound we thus have Pr[maxi∈[m] |Zi | ≥ α] ≤ β. Proof of Lemma 7. Proof. Here we use the looser add-the-deltas approach discussed in Wilkins et pal. [2024]. The √ Gaussian noise is calibrated to satisfy (ε, δ/2)-DP for ℓ2 -sensitivity m = k(1 + ⌊log2 h⌋) using [Dwork and Roth, 2014, Appendix A]. We have that Pr[N (0, σ 2 ) ≥ ∆] ≤ δ/(2m) which implies that the maximum noise for m queries is less than ∆ with probability at least 1 − δ/2.

G

Privacy Guarantees of Algorithm 2

Algorithm 2 is an adaptive variant of the Gaussian Sparse Histogram Mechanism from [Wilkins et al., 2024]. The privacy properties from their work apply to this adaptive setting when the number of queries affected by any data point is bounded. Lemma 15. Let (q1 , . . . , qd ) be (adaptively chosen) counting queries such that for any x ∈ X , we have qi (x) = 1 for at most m values of i ∈ [d] and qj (x) = 0 for all other queries. Then Algorithm 2
and with parameters σ and ∆ satisfies (ε, δ)-differential privacy where γ(j) = (m − j) log Φ ∆ σ   m ∆ δ ≥ max 1 − Φ , σ  m−j  m−j   √   √  (ε − γ(j))σ (ε − γ(j)) σ ∆ ∆ j j ε−γ(j) √ √ − − max 1 − Φ +Φ Φ −e Φ − , σ σ 2σ 2σ j∈[m] j j √   √  j (ε + γ(j)) σ j (ε + γ(j))σ √ √ max Φ − − − eε+γ(j) Φ − . 2σ 2σ j∈[m] j j Proof. It follows from the proof of [Wilkins et al., 2024, Theorem 5.4]. Wilkins et al. [2024] study an algorithm in the non-adaptive setting, but the algorithm does not rely on any correlation between queries so the same analysis can be applied for adaptive queries. The privacy guarantees follow from standard composition properties of the Gaussian mechanism combined with a bound of the probability of infinite privacy loss events for queries that have a value < τ − ∆ − 1 for one dataset and ≥ τ − ∆ − 1 for the other. The proof implicitly requires that the queries are monotonic. That is, all d queries should be either non-increasing or non-decreasing between neighboring datasets. This assumption clearly holds for our setting since we, like [Wilkins et al., 2024], study counting queries.

H

Deterministic Error Bound for Heavy Hitter Algorithm

Here we present a variant of our heavy hitters algorithm with deterministic error bound. We modify Algorithm 2 to always output ⊤ for queries that are sufficiently above the threshold. We use the add-the-deltas technique discussed in Wilkins et al. [2024] to analyze the privacy guarantees. Lemma 16. Let (q1 , . . . , qd ) be (adaptively chosen) counting queries such that for any x ∈ X , we have qi (x) = 1 for at most m values of i ∈ [d] and qj (x) = 0 for all other queries. Then Algorithm 3 with parameters σ and ∆ satisfies (ε, δGauss + δinf )-differential privacy where √   √   m m εσ m εσ ∆ ε δGauss = Φ −√ −e Φ − −√ , and δinf = 1 − Φ . 2σ 2σ σ m m Proof. By Definition 1, we have to show that for any pair of neighboring datasets D and D′ and all sets of outputs Z we have Pr[GSTT(q1 (D), . . . , qd (D)) ∈ Z] ≤ eε Pr[GSTT(q1 (D′ ), . . . , qd (D′ )) ∈ Z] + δGauss + δinf . 21

Algorithm 3 GaussianSparseTwosidedThreshold (GSTT) Require: Parameters σ, τ , and ∆. Require: Dataset D, (adaptive) counting queries q1 , q2 , q3 , . . . 1: for all i ∈ {1, 2, 3, . . . } do
2: Sample Zi ∼ N 0, σ 2 . 3: if qi (D) ≥ τ + ∆ + 1 or (qi (D) > τ − ∆ − 1 and qi (D) + Zi > τ ) then 4: Release ⊤. 5: else 6: Release ⊥. 7: end if 8: end for

We prove that the inequality above by introducing a series of values (q̂1 , . . . , q̂d ) that "lies between" (q1 (D), . . . , qd (D)) and (q1 (D′ ), . . . , qd (D′ )). Consider the set of all possible counting queries Q. Let S ⊆ Q denote the set of counting queries that are not classified deterministically for D. That is, q(D) ∈ [τ − ∆ − 1, τ + ∆ + 1] if and only if q ∈ S and define similarly S ′ and Ŝ. We construct the intermediate values such that S ′ = Ŝ. For all qi ∈ (S ∩S ′ ) we set q̂i = qi (D) and for all qi ∈ / (S ∩S ′ ) ′ ′ we set q̂i = qi (D ). In other words, we construct (q̂1 , . . . , q̂d ) such that (1) (q1 (D ), . . . , qd (D′ )) and (q̂1 , . . . , q̂d ) only differ in entries that are in both S and S ′ (2) (q1 (D), . . . , qd (D)) and (q̂1 , . . . , q̂d ) only differ in entries that are in only one of S and S ′ . This allows us to analyze each case separately to derive our values for δGauss and δinf . Note that the values (q̂1 , . . . , q̂d ) might not correspond to evaluating counting queries on any existing dataset D̂. We just use the values only for the proof and utilize the fact that Algorithm 3 only access the count. Notice that we cannot have any query where qi (D) < τ − ∆ − 1 and qi (D′ ) > τ + ∆ + 1 or vice versa. As such, whenever qi ∈ / (S ∪ S ′ ) the deterministic output of Algorithm 3 is the same for both datasets. Therefore we only have to consider queries that are deterministic for exactly one or for none of the datasets. The intermediate values allow us to analyze the two cases separately. First we show that Pr[GSTT(q1 (D), . . . , qd (D)) ∈ Z] ≤ Pr[GSTT(q̂1 , . . . , q̂d ) ∈ Z] + δinf . Since qi (D) ̸= q̂i for at most m queries any change in output distribution is due to those queries. For each such query, one of the outputs is deterministic. Without loss of generality, assume that qi (D) < τ −
∆ − 1 such that the output is always ⊥. The probability that the output is ⊥ with q̂i is at least Φ ∆ σ , since Zi must be larger than ∆ to
change the output to ⊤. The probability that all the m m queries are identical is therefore at least Φ ∆ which gives the bound for δinf . σ Next consider the case of (q̂1 , . . . , q̂d ) and (q1 (D′ ), . . . , qd (D′ )). These inputs only differ for queries √ in [τ − ∆ − 1, τ + ∆ + 1]. There are at most m differing queries, so the ℓ2 -distance is bound by m. The algorithm can be seen as running the Gaussian mechanism on values in [τ − ∆ − 1, τ + ∆ + 1] and post-processing the values. The tight bound for the Gaussian mechanism (Lemma 14) gives us Pr[GSTT(q̂1 , . . . , q̂d ) ∈ Z] ≤ eε Pr[GSTT(q1 (D′ ), . . . , qd (D′ )) ∈ Z] + δGauss . Note that we technically cannot apply Lemma 14 directly, since the Gaussian mechanism is typically analyzed in the static setting, while we allow adaptively chosen queries. A more rigorous proof would fix the neighboring datasets and study the input as a series of adaptive queries rather than a fixed sequence. Under Gaussian Differential Privacy [Dong et al., 2022] we (informally) allow an analyst to make m queries that are each 1/σ-GDP and an unlimited number of 0-GDP queries (those where the counts are the same in our original setup). Using the adaptive composition property and conversion from µ-GDP to (ε, δ)-DP recovers the inequality above. We leave the details as an exercise for the reader. Combining the two inequalities above give us the desired bound Pr[GSTT(q1 (D), . . . , qd (D)) ∈ Z] ≤ Pr[GSTT(q̂1 , . . . , q̂d ) ∈ Z] + δinf ≤ eε Pr[GSTT(q1 (D′ ), . . . , qd (D′ )) ∈ Z] + δGauss + δinf .

22

Similarly to Lemma 7, we give a simple upper bound for the values of σ and ∆. Corollary 17. When ε < 1 then the parameters p  √ p 2m ln(2.5/δ) m log(1/δ) ∆ = σ · 2 ln(2m/δ) = O σ= ε ε satisfy the condition in Lemma 16 for (ε, δ)-DP. In the last equality we assume that m ≪ 1/δ. Since Algorithm 3 clearly can only misclassify queries in the interval [τ − ∆ − 1, τ + ∆ + 1], it follows that we achieve a deterministic error bound for the heavy hitters problem. Corollary 18. Let A denote an algorithm that takes as input k trees with maximum height h. The algorithm runs Algorithm 1 for each tree where C HECK T HRESHOLD is instantiated as Algorithm 3 with parameters σ, τ , and ∆. Then A satisfies (ε, δ)-DP with values specified by Lemma 16. Let α ∈ R denote the smallest value such that all nodes with at least count τ +α are marked as Heavy and all nodes with at most count τ − α are marked Light. Then it holds with probability 1 that α ≤ 1 + ∆. Furthermore, when τ ≥ 1 + ∆ we can implement the algorithm to run in time and space O(knh). We note that it is possible to get tighter results using a case by case analysis similar to Lemma 15.

I

Proof of Lower Bound (Lemma 8)

Here we discuss the lower bound for deep trees presented in Lemma 8. We use the lower bound of Balcer and Vadhan [2019] which we restate below. Note that Balcer and Vadhan use a different definition of differential privacy. They study the problem under the replacement definition for neighboring datasets where the size of the dataset is known (bounded DP) while we use the add/remove (unbounded DP) definition. However, we can still use their result since any DP mechanism under add/remove satisfies DP with slightly worse parameters under bounded DP by a simple group privacy argument. Lemma 19. A heavy hitters algorithm M that satisfies (ε, δ)-DP under the add/remove neighboring relation satisfies (2ε, (1 + eε )δ)-DP under the replacement definition. Proof. This is well known in differential privacy. We include a short proof for completeness. Let i be the index that differs between some pair of neighboring datasets D ∼ D′ under replacement. That is, Dj = Dj′ for all j ̸= i. Then define an intermediate dataset D̂ = D \ {Di } = D′ \ {Di′ }. We have Pr[M(D) ∈ Z] ≤ eε Pr[M(D̂) ∈ Z] + δ ≤ eε (eε Pr[M(D′ ) ∈ Z] + δ) + δ = e2ε Pr[M(D′ ) ∈ Z] + (1 + eε )δ , where the inequalities follow from the fact that D ∼ D̂ and D̂ ∼ D′ are pairs of neighboring datasets under the add/remove definition for which M satisfies (ε, δ)-DP. Lemma 20 (Theorem 7.2 of Balcer and Vadhan [2019]). Let M be a (ε, δ)-differentially private algorithm (under bounded DP) that takes as input any dataset of size n and d counting queries (q1 (D), . . . , qd (D)) where each data point satisfies exactly one counting query. Assume that M has the following error guarantee ∀D ∈ X n

∀i ∈ [d]

Pr[|M(D)i − qi (D)| ≤ α] ≥ 1 − β

with β ∈ (0, 1/2]. If M outputs at most n̂ non-empty bins. Then     1 1 d 1 ε α ≥ · min ln − 1, ln − 1, n . 2 2ε 16β n̂ ε 4δ Balcer and Vadhan refer to the type of error guarantee from the above lemma as the (α, β)-Per-Query error. We use the following statement in the proof. Lemma 21 ([Balcer and Vadhan, 2019, Figure 3]). The mechanism that adds Geometric noise to all counting queries satisfies (α, β)-Per-Query accuracy (under bounded DP) for any α ≥ ⌈2/ε · ln(1/β)⌉ . 23

Now we restate an exact version of our informal lower bound Lemma 8. Note that we do not optimize constants. For simplicity, we state the result only for ε < 1. This restriction is only used to easily deal with the eε part of the (1 + eε )δ term that arises from changing DP definitions. For a tighter analysis, one should directly analyze our mechanism under replacement DP or carry out the lower bound proof of Balcer and Vadhan [2019] under add/remove DP. Lemma 22. Let M denote an (ε, δ)-DP mechanism (for some ε < 1) that takes as input a tree T of height h > 6 + log2 (n2 /β 15 ) and a dataset of size n and outputs a set of at most n2 nodes per layer of T . Suppose that with probability at least 1 − β, M outputs all nodes in T with count above some value τ̂ ∈ R. Then    h−1  ε 1 1 1 2 − 1, − 1, n . τ̂ ≥ · min ln ln 2 8ε 32βn2 4ε 4δ . Proof. We can encode any sparse histogram (see Lemma 20) with d = 2h−1 queries in the leaves of the tree. Label the leaves in arbitrary order and set the count of the first leaf to q1 (D), the count of the second leaf to q2 (D) etc. By Lemma 19, M satisfies (2ε, (1 + eε )δ) < (2ε, 4δ)-DP in the setting of Balcer and Vadhan [2019]. We can spend additional privacy budget to add Geometric noise calibrated for (2ε, 0)-DP to the all leaves of T that are part of the output of M. This clearly does not violate the requirement of outputting at most n̂ = n2 non-empty bins. For any leaf that was part of the output of M, the (α, β) accuracy is ⌈1/ε · ln(1/β)⌉ by Lemma 21. Thus all queries above τ̂ have this error with failure probability at most 2β. By our assumption on h the error of nodes above τ̂ is lower than the error required by the lower bound. The leaves with value below τ̂ must therefore increase the (α, β)-Per-Query error. We have no requirements on M for nodes with count less than τ̂ . If we simply output an estimate of zero for all nodes not in the output of M, these leaves can therefore have expected error up to τ̂ . Since the mechanism above is (4ε, 4δ)-DP and has failure probability at most 2β by Lemma 20 we must have     ε 1 d 1 1 ln − 1, ln − 1, n . τ̂ ≥ · min 2 8ε 32βn2 4ε 4δ

J

Implementation Details

Tree construction. In this section we present implementation details of our algorithm. In particular, we discuss how to implement Algorithm 1 to run in time and space O(ℓ), where ℓ is the number of nodes with true count at least τ − ∆ − 1. Since each data point increments the count for a single node in each layer of the tree we clearly have ℓ = O(nh) as claimed in Theorem 6. Note that in the pseudocode we explicitly mark all nodes either Heavy or Light which is infeasible for large trees. In practice, we implement the algorithm to return the set of nodes marked Heavy. Any nodes that are not explicitly marked by the algorithm are not returned as they are implicitly Light. First, we briefly discuss how we build the unpruned decision tree in time O(nh) starting with the root. We assume that we always select a splitting feature and threshold in time O(1). We then split a node with m points in time O(m) using a simple pass over the nodes to classify them for the left or right child node. Since each data point is part of exactly one split in each layer, the total running time is O(nh). We do not split empty nodes since all nodes in empty subtrees are eventually marked Light when τ > 1 + ∆. If the threshold is larger, we can similarly stop splitting nodes with less than τ − ∆ − 1 data points. Next, we show that each part of Algorithm 1 can be implemented in linear running time in the size of the tree O(ℓ). In Phase 1 we query all nodes in Lmid and mark ancestors or descendants. Marking ancestor of a node takes up to time O(h). However, we stop early when we encounter a node which was already marked, so in total over the entire run of the algorithm this takes at most time O(ℓ). We do not actually need to explicitly mark all descendants of Light nodes, since we skip those recursive calls in Phase 2. After we finish marking nodes in the tree we find the set of heavy hitters by adding nodes starting from the root. Since we stop exploring any path when we encounter a Light node, we never explore the unmarked subtrees. 24

Now, notice that we call C HECK T HRESHOLDτ (#count(u)) for any node u at most once for the entire execution of all recursive calls. If we can access all non-zero nodes in Lmid in time O(|Lmid |) the entire algorithm therefore runs in O(ℓ) (We assume that we sample a Gaussian in time O(1)). However, simply traversing the tree from the root to find Lmid takes time up to O(h|Lmid |). We reduce the running time with some algorithmic engineering. We label the nodes (including missing empty nodes) in top-down and left-to-right order. The root has label 1, the layer below the root has labels 2 and 3, the next layer contains labels 4 to 7 etc. For any node with label i, the left child has label 2 · i and the right child has label 2 · i + 1. This is a standard technique for storing a binary tree in an array without using pointers. This labeling is convenient, because when the top node in T has label i, then Lmid are exactly the nodes with labels from i · 2mid to (i + 1) · 2mid − 1, inclusive. However, for large trees most of these nodes do not exist, so we need to efficiently find all such nodes without explicitly querying each label. Ideally, we do not want to use any advanced data structure to avoid adding unnecessary complexity. Notice that our algorithm always explores the tree in left-to-right order. In particular, if we recursively call the algorithm in ascending label order in Phase 2, then for any particular layer we query the nodes in ascending label order. As such, when we call C HECK T HRESHOLDτ (#count(u)) we know that no recursive call will ever need to query C HECK T HRESHOLDτ (#count(v)) for any v where u and v has the same depth in the full tree and label(v) < label(u). We utilize this observation to achieve an efficient implementation. We store a queue for each layer in the tree and add all nodes in the tree to the corresponding queue using a single traversal of the tree. When we need to access Lmid in a recursive call where the root of the subtree has label i we discard all nodes in the corresponding queue with label < i · 2mid . We then query all nodes from the queue with label < (i + 1) · 2mid . Those are exactly the non-empty nodes in Lmid and we query them in left-to-right order as desired. Leaf algorithm. We now briefly discuss the privacy analysis of the two leaf algorithms used in our implementation. The techniques we use are standard. We use the exponential mechanism for majority vote and Gaussian noise for approximate class distributions. We use zCDP for accounting in both cases. For the class distribution we simply add noise from N (0, k/(2ρ)) to each class count. This can create negative counts, but we can clip to non-negative values as post-processing. Rogers and Steinke [2021] show that the exponential mechanism with privacy parameter ε satisfies 1 2 8 ε -zCDP by showing it satisfies a condition known as bounded range ε-bounded range. Moreover, in the proof for Lemma 3 in [Rogers and Steinke, 2021], they make use of the bound −∆ ≤ ℓ(y, x′ ) − ℓ(y, x) ≤ ∆ which can be improved in our case, because the scoring function - being the count of each class - is monotonic. Depending on whether we add or remove a row from the dataset, the term ℓ(y, x′ ) − 1 2 ℓ(y, x) is in [0, ∆] or [−∆, 0]. It follows that the mechanism satisfies ε/2-bounded range and 32 ε zCDP. Monotonicity therefore makes it sufficient to set the ε parameter of the standard exponential mechanism McSherry and Talwar [2007] to √ 1 instead of √ 2 . 8ρ/k

25

8ρ/k