BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

arXiv:2610.10075v1 [cs.CR] 7 Oct 2026

BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

Ergute Bao Inria

Graham Cormode University of Oxford

Xiaokui Xiao National University of Singapore

Ting Yu Mohamed bin Zayed University of Artificial Intelligence

Abstract Finding heavy nodes in a tree—those whose counts exceed a given threshold—is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur√additive error margins of Ωε,δ (log h) or Ωε,δ ( log h) for tree height h. We introduce BetweenCut, an (ε, δ)-DP algorithm with an additive error margin of Oε,δ (log log h), improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.

1

INTRODUCTION

Many data spaces are naturally represented (implicitly or explicitly) as a hierarchy [3, 14, 35, 45, 49]. Searching for important nodes—those whose “weight” exceeds a given threshold τ —is a building block for analysis and learning over structured data, such as random forests [24, 38], frequent word discovery [49], and spatial partitioning pruning [47]. We study this task on a public hierarchical tree of height h, where each private record belongs to one leaf and contributes to every count on its root-to-leaf path. The goal is to classify all nodes simultaneously while satisfying record-level (ε, δ)-differential privacy ((ε, δ)-DP) [16], with an additive error margin around τ that remains

Preliminary work. Under review.

small even when h is large. A natural baseline releases a DP node histogram independently at each level and thresholds the released counts against τ . Within a level, the histogram bins contain disjoint sets of records. Across levels, however, the same record participates in h levels. The basic Laplace mechanism therefore gives noise scale h/ε, while √ the Gaussian mechanism gives scale proportional to h/ε at fixed δ, both leading to errors in O(poly(h)). One approach is to reduce the number of threshold tests. Lumberjack [38] searches middle levels first and propagates ‘Heavy’ labels upward and ‘Light’ labels downward. This balanced search reduces each record’s participation from h to O(log h) √tests and leads to an improved error margin of Oε,δ ( log h log log h). A different approach is to avoid a separate privacy charge for every test. The sparse vector technique (SVT) controls privacy through a bounded number of positive answers rather than the total number of query participation [16, 19]. Ghazi et al. [25] use this principle in a bottom-up tree classifier, and Biswas et al. [5] develop per-record threshold-monitoring arguments for hierarchical heavy hitters. These approaches can traverse many levels without a privacy budget proportional to their number, but their stated errors retain log h terms due to a union bound over all levels. This suggests a question: can a tree search make a small number of queries per record while avoiding a separate privacy charge for each query? These two requirements are distinct. The label propagation idea in Lumberjack [38] reduces the number of queries, but each query still triggers a separate privacy charge: a ‘High’ answer leaves descendants to be classified, whereas a ‘Low’ answer can leave ancestors unresolved; either answer may still recur along the same root-to-leaf path for a record. On the other hand, applying SVT-style threshold tests to hierarchal nodes still requires composing the privacy costs for all positive answers: Ghazi et al. [25] imposes a global O(M/τ ) positive-answer

Manuscript under review

budget, where M ≥ n is a public input database-size bound, introducing a different source of error. We provide a positive answer. Our algorithm fuses these two previously separate lines of work: histogram-based node counting [38] and threshold-testing [5, 25] with SVT accounting. We make a near-threshold answer terminate every affected root-to-leaf path through the queried node. This threshold test distinguishes ‘Low’, ‘High’, and ‘Middle’ outcomes using fresh Laplace noise and two fixed public thresholds around τ . ‘Low’ and ‘High’ outcomes propagate labels in one direction. A ‘Middle’ outcome does both: it labels every proper ancestor Heavy, and the queried node and all its descendants Light. In other words, the ‘Middle’ outcome terminates the search—there can be at most one ‘Middle’ outcome in any root-to-leaf path. In our analysis, we argue that the ‘Low’ and ‘High’ outcomes need not trigger privacy charges. This requires the introduction of a novel “one-target, finite horizon” variant of the Target-charging technique (TCT) [10], which itself generalizes the Sparse Vector Technique (SVT) [19] and BetweenThresholds [7]. This analysis permits reusing a noiseless threshold across multiple queries on disjoint paths, simplifying the algorithm and avoiding re-sampling and composition overheads. The co-creation of the algorithm and its analysis was not an easy task: prior work that attempted to use SVT for finding heavy nodes [5] suffered a subtle bug [38]; correcting this required extra privacy noise and a lengthy proof [5]. In contrast, our contribution is a clean algorithm that is similar in shape to the state-of-the-art [38] while achieving tighter asymptotic bounds. We count the clarity of the algorithm and its accompanying proofs as a major part of our contribution, allowing future work to adopt this framework and apply it to related private search problems.

2

PROBLEM FORMULATION

2.1

Heavy Node Classification

Tree structure and input. Let T be a rooted tree of height h and arity k. Let nodes/vertices be V and leaves be X. The tree structure and the ordering of its nodes are public. A private database D is a finite multiset of records in X. Each record contributes to the count of a leaf node. We write n := |D| as the size of D. For any leaf node v ∈ X, we write its count as P cv (D) = |{z ∈ D : z = v}|, with n = v∈X cv (D) (1) For any node u ∈ V , we write Desc(u) and Anc(u) as its descendants and ancestors, respectively. Both Desc(u) and Anc(u) include u itself. Proper ancestors and descendants are expressed as Anc(u) \ {u} and

Desc(u) \ {u}, respectively. The total count (or weight) of node u is P cu (D) = v∈X∩Desc(u) cv (D).

(2)

If v ∈ Desc(u), then cv (D) ≤ cu (D). The tree height h is the maximum number of nodes on a root-to-leaf path. We focus on deep trees and assume h ≥ 3 throughout. The depth of a node starts at zero, so the deepest leaves have depth h − 1. All logarithms are natural unless a base is explicitly indicated. Classification problem. Fix a public threshold τ ≥ 0. On any given input database D, the goal is to classify each node as Heavy or Light according to whether its count exceeds τ . We allow an additive error margin of E around the threshold while respecting record-level privacy (defined next). In particular, the following must hold simultaneously for every node u ∈ V , except with error probability at most β: • If cu (D) ≥ τ + E, we classify node u as Heavy. • If cu (D) < τ − E, we classify node u as Light. • If cu (D) ∈ [τ − E, τ + E), u may receive either label. Formally, we want to achieve the following: Definition 2.1 (Classification guarantee). Fix τ ≥ 0, E ≥ 0, and β ∈ [0, 1). A randomized algorithm A satisfies the (E, β) classification guarantee at threshold τ if on every input database D it returns an ancestorb ⊆ V such that closed set H  b Pr {u ∈ V : cu (D) ≥ τ + E} ⊆ H∧ (3)  b H ⊆ {u ∈ V : cu (D) ≥ τ − E} ≥ 1 − β, where the probability is over the internal randomness of A. A deterministic error margin means β = 0. 2.2

Differential Privacy

Definition 2.2 (Add/remove adjacency). Databases D, D′ are neighbors, written D ∼ D′ , when one is obtained from the other by adding one leaf record. Consider any leaf record z ∈ X and neighboring pairs D = D′ ⊎ {z}. Here ⊎{z} means adding one occurrence of z. Let Pz be the root-to-leaf path of z, then cu (D) − cu (D′ ) = 1{u ∈ Pz }.

(4)

Namely, the extra record z influences only the counts of the nodes that lie on Pz ; and its influence is exactly 1. Definition 2.3 (Sensitivity [18]). The sensitivity of function f is S(f ) := maxD∼D′ ∥f (D) − f (D′ )∥, where ∥ · ∥ is some norm of interest, e.g., the L1 norm. Definition 2.4 ((ε, δ)-differential privacy [17, 18]). A randomized algorithm A is (ε, δ)-DP if, for all D and D′ s.t. D ∼ D′ and every measurable output event S, Pr[A(D) ∈ S] ≤ eε Pr[A(D′ ) ∈ S] + δ.

(5)

Manuscript under review

Definition 2.5 (Laplace distribution). A random variable Z has a zero-mean Laplace distribution with scale b > 0, written Z ∼ Lap(b), if its density  probability  1 function (pdf) is pZ (z) = 2b exp

− |z| b

, for z ∈ R.

Lemma 2.6 (Laplace mechanism). Let f be a counting query with sensitivity 1. For ε > 0, define the Laplace mechanism for input D as A(D) = f (D)+Z with Z ∼
Lap 1ε . Then mechanism A satisfies (ε, 0)-DP. SVT and TCT. The sparse vector technique (SVT) is a fundamental tool for answering adaptively chosen threshold queries under differential privacy [19, 21, 23, 27, 32, 39–43]. It is useful when an analyst must examine many queries but expects only a small number of positive responses (in our case, nodes having count ≥ τ ). Under linear composition or advanced composition [16, 20,√30], posing K queries would impose a Θ(K) or Θ( K) multiplicative factor on the final ε parameter. As a result, more queries often lead to larger errors due to larger DP noise magnitude. In contrast, the privacy cost of SVT can be O(1). SVT’s basic AboveThreshold primitive compares noisy query values against a noisy threshold and stops at the first positive response; more general SVT procedures allow a prescribed number of positive responses. The privacy bound is governed by the number of positive responses rather than the total number of queries [16, 19, 21, 23, 27, 39, 43]. The target-charging technique (TCT) [10] extends SVTstyle accounting from threshold tests to general DP mechanisms. Each run is associated with a target, a subset of possible outputs from a DP mechanism. A target hit occurs when the released output belongs to that subset. Roughly speaking, the probability mass of the target decomposition and the observed number of target hits control the overall privacy cost. Similar to SVT, this cost can therefore be independent of the overall number of queries to the input database. For threshold testing over adaptive queries, TCT injects fresh noise into each query answer to compare it with a public pre-fixed (noiseless) threshold. Definition 2.7 (λ-Indistinguishability). For probability distributions P0 , P1 on an outcome space Y, we say P0 and P1 are λ-indistinguishable (written as P0 ≈λ P1 ) if, for every measurable S ⊆ Y,

N0 ≈λ N1 ,

minb∈{0,1} Nb (⊤) ≥ q.

(8)

We say the set ⊤ is a q-target of a randomized mechanism A with parameters (λ, κ) if this condition holds for (A(D), A(D′ )) for every neighboring pair D ∼ D′ . Sampling from C does not require knowing the bit b selecting the input. Sampling from Nb is a (λ, 0)-DP access to the input and hits the target with probability at least q. The unrestricted component Fb contributes to the exceptional probability κ. This simulation functions primarily as an analysis device and need not be explicitly implemented by the release mechanism.

3

HEAVY NODE CLASSIFICATION

Prior work relevant to the private heavy node classification problem has fallen into two categories: histogrambased and threshold-testing. Part of our contribution is to unite these previously separate approaches. Histogram-based counting. The naive full-tree baseline yields additive errors in Ω(poly(h)) for heavy node classification. The naive Gaussian mechanism [16] publishes a histogram of the node counts at every level in the tree, and labels a node heavy exactly when its noisy count is at least√τ . For a hierarchy of height h, the L2 sensitivity is h. Adding √ independent Gaussian noise of standard deviation O( h/ε) to each node count results in an additive error margin of Oε,δ (h) for classification (see Appendix A.1). Lebeda et al. [38] consider more sophisticated histogram approach. Their algorithm, named Lumberjack, queries middle layers and recurses down the tree if the noisy count is heavy, and up the tree if it is light. This is conceptually equivalent to performing (parallel) binary searches on a tree. The result is to publish a collection of histograms of node counts with bins of varying widths. Each leaf is√counted towards O(log h) histograms, resulting in O( log h) error under Gaussian noise. For 0 < ε < 1, [38, Corollaries 17–18] Lumberjack achieves absolute additive error ELJ , as   1p ELJ = O log(1/δ) log h log log h . (9) ε

P1 (S) ≤ eλ P0 (S). (6)

This error margin is deterministic; namely, it holds with probability 1.

Definition 2.8 (q-target [10]). Let q ∈ (0, 1], λ > 0, and κ ∈ [0, 1). A measurable set ⊤ ⊆ Y is a qtarget for a pair of probability distributions (P0 , P1 ) with parameters (λ, κ) if there exist p ∈ [0, 1] and probability distributions C, N0 , N1 , F0 , F1 on Y such that, for b ∈ {0, 1},
Pb = (1 − κ) pC + (1 − p)Nb + κFb , and (7)

Threshold-testing. The second line of work uses SVT-like mechanisms to test which nodes’ weight is above the threshold, by traversing the hierarchy. [25, Algorithm 1] walks the tree from the deepest level toward the root, maintaining the unclassified nodes Si at each level i. It uses an SVT procedure to find the (disjoint) nodes in a level that are above the (noisy) threshold. Heavy nodes and all their ancestors are

P0 (S) ≤ eλ P1 (S)

and

Manuscript under review

removed, and the search proceeds to higher levels. The number of positive answers c is bounded by O(M/τ ), where M is an upper bound on the total count n. The resulting additive error margin EG is given by o n  2h eε/2 −1 . (10) EG = 2M max 48 ln , 6 ln 1 + ετ β δ A related but more challenging task is to find hierarchical heavy hitters. The (corrected) algorithm of Biswas et al. [5] also utilizes the idea of SVT and bottom-up traversal. They obtain an additive error margin of   log(1/δ) log [log(1/δ) + log(h/β)] . EB = O log(1/δ) ε ε (11)

Algorithm 1 Count query GuardedBT(c; a, b, R, λ) Input: Original node count c ∈ N; public thresholds a, b ∈ R with a < b, guarded margin R ≥ 1 for a deterministic error, local privacy parameter λ > 0 1: if c ≤ a − R then ▷ deterministic output 2: return L 3: else if c ≥ b + R then ▷ deterministic output 4: return H 5: else ▷ draw fresh DP noise 6: Draw fresh independent Z ∼ Lap(1/λ) 7: if c + Z < a then 8: return L 9: else if c + Z > b then 10: return H 11: else 12: return B

In summary, [5, 25] give threshold-based algorithms for heavy node classification with absolute additive error margins in Ωε,δ (log h) while the histogram-based √ method of [38] achieves error of Ωε,δ ( log h). In this work, we converge these paradigms in order to reduce the error for node classification to Oε,δ (log log h).

any post-processing of the response sequence, including its length. Then, for every integer 1 ≤ r ≤ K, A is
rλ, Kκ0 + 1{r<K} (1 − q)r -DP. (12)

Our problem is also related other fundamental tasks in differential privacy, such as heavy hitters and counting for non-hierarchical data [3, 6, 8, 44, 45, 48, 49], histogram release [4, 13, 28, 34, 36, 37], quantile estimation and learning thresholds [1, 7, 11, 15, 26, 29, 31, 33], and counting queries on trees and multi-dimensional spaces [2, 9, 12, 22, 25, 46, 47]. While some techniques could also be applicable to our setting, we aware of no algorithm that achieves a simultaneous error for all nodes with doubly-logarithmic dependence on tree height h and no dependence on input database size n.

Here r should be understood as describing the budget for draws from Nb —it is not an additional stopping rule for the interaction. In the pairwise simulation, each draw from Nb costs λ privacy budget in ε and hits its target with conditional probability at least q. Thus, more than r draws requires the first r to miss their targets, an event of probability at most (1 − q)r . This overflow is impossible when r = K. The term Kκ0 accounts for selecting the exceptional mass component in any of the calls. The proof appears in Appendix C.1.

4

OUR ALGORITHM

Count query. Given threshold τ , choose parameters 0 < λ ≤ 1 and R ≥ 1, and define

4.1

Building Blocks

Finite-horizon, one-hit TCT. We present the following specialization of the target-charging simulation of [10]: the interaction stops at its first target hit and makes at most K calls. Lemma 4.1 (Finite-horizon one-hit TCT). Fix an integer K ≥ 1 and parameters λ > 0, q ∈ (0, 1], and κ0 ∈ [0, 1). Let A be an algorithm that accesses its input database D only through adaptive calls to randomized mechanisms. At round i, A selects a mechanism Mi with finite output space Yi and a target ⊤i ⊆ Yi , and obtains Yi ∼ Mi (D) using fresh randomness. The selections depend only on public information and previous responses. For every round and every possible response history, assume that ⊤i is a q-target of Mi with parameters (λ, κ0 ) (Definition 2.8). Algorithm A stops making calls immediately after its first target hit Yi ∈ ⊤i , or after K calls if no hit occurs. Its output is

w = λ1 ,

a = τ − w,

b = τ + w,

(13)

Algorithm 1 is the building block for our algorithm. Given a (true) node count c to inspect, we call the routine GuardedBT(c; a, b, R, λ), and return L or H, indicating whether the noisy count is smaller or larger than the public thresholds a and b, respectively. If the returned value is B, i.e., ‘between’, that means the value is judged to be close to the thresholds a and b. The semantics of a B response is that the node count is on the borderline: it is small enough to be treated as effectively light (L), and simultaneously large enough to be treated as effectively heavy (H). Our algorithm will use this duality to treat any discovered B labeled nodes as marking the boundary between heavy ancestors and light descendants. Here, the parameter R can be thought of as the maximum deterministic error margin, which is used to avoid a union bound over all queries. λ can be viewed as the local privacy parameter (not the final ε).

Manuscript under review

Algorithm 2 Depth Traversal Ordering DepO(i, j) 1: if i > j then 2: return the empty list 3: m ← i + ⌊(j − i + 1)/2⌋ 4: return [m] ∥ DepO(m + 1, j) ∥ DepO(i, m − 1)

Public traversal ordering. On any tree T of height h, we call DepO(0, h − 1) (Algorithm 2) to determine the traversal ordering for the different levels of the public tree. It can be understood in terms of binary search: first the middle layer is visited, then recursively the lower layers, followed by the higher layers. This ordering is public; it does not rely on information from input database. For example, on h = 15, applying the definition gives the ordering [7, 11, 13, 14, 12, 9, 10, 8, 3, 5, 6, 4, 1, 2, 0]. Label propagation. For node u with count c, if GuardedBT(c; a, b, R, λ) returns L, we classify all its descendants as well as u as L, by monotonicity. Similarly, if GuardedBT(c; a, b, R, λ) returns H, we classify all its ancestors as well as u as H; if GuardedBT(c; a, b, R, λ) returns B, we leverage its boundary nature to classify all its descendants as well as u as L and all its ancestors (excluding u) as H. We refer to these routines as MarkUp(u) and MarkDown(u) for propagating H and L labels, respectively. Other nodes in the tree that don’t overlap with u’s records are unaffected by the marking procedure, since their counts are not directly comparable with u’s. For completeness, Algorithm 6 in Appendix B.1 formalizes this simple rule of label propagation, originating from node u. 4.2

The BetweenCut Algorithm

We present BetweenCut, listed as in Algorithm 3. The overarching idea is to turn a node u’s answer near the given threshold τ (in particular, a ‘between’ answer from Algorithm 1) into a stopping rule that resolves all affected paths through that node, by propagating labels to u’s ancestors and descendants (using Algorithm 6). Overall, on each root-to-leaf path, our algorithm makes at most ⌈log2 (h + 1)⌉ query calls of GuardedBT(cu (D); a, b, R, λ) through some node u in that path. This bound follows from the midpoint-first traversal and label propagation. Within any recursive interval of levels, the middle level is processed first. Consider node u on path Pz . A query at u labels its descendants Light for an L response, or its ancestors Heavy for an H response; a B response resolves the entire path. After the middle level is processed, all remaining queries on Pz within that interval lie in at most one of its two subintervals. Remark on consistency and termination. After

Algorithm 3 Node classifier BetweenCut(T, D, τ, λ, R) Input: Public tree T of height h; private leaf dataset D, public parameters τ, λ, R. 1: w ← 1/λ; a ← τ − w; b ← τ + w 2: Compute all original counts cu (D) 3: Initialize label[u] ← ? for all u ∈ V 4: for d in DepO(0, h − 1) do 5: for nodes u of depth d do 6: if label[u] ̸= ? then 7: continue 8: s ← GuardedBT(cu (D); a, b, R, λ) 9: if s = L then 10: MarkDown(u) 11: else if s = H then 12: MarkUp(u) 13: else 14: MarkUp(parent(u)) 15: MarkDown(u) b 16: return H = {u ∈ V : label[u] = H}

each node is processed, the Heavy set (labeled as H) is ancestor-closed and the Light set (labeled as L) is descendant-closed. The propagation rule of labels also cannot conflict with existing labels; hence, each node is labeled at most once and its label remains unchanged afterwards. Every node is eventually labeled, so the algorithm terminates with a complete classification. We formalize and prove these properties in Appendix B.2. The next two lemmas establish the query bound and stopping property crucial to the privacy analysis. Lemma 4.2 (Logarithmically many queries on each root-to-leaf path). For every database D and every execution of Algorithm 3, let Q be the set of nodes at which Algorithm 1 is invoked. Then every root-to-leaf path P of the public tree satisfies |Q ∩ P | ≤ ⌈log2 (h + 1)⌉.

(14)

Lemma 4.3 (At most one middle target on each root– to-leaf path). For every execution of Algorithm 3, a B response at a node u prevents all subsequent queries on every root-to-leaf path containing u. Consequently, if B is the set of queried nodes whose responses are B, then every root-to-leaf path P satisfies |B ∩ P | ≤ 1. If we can prove that {B} is a q-target for Algorithm 3 (recall Def. 2.8), then Lemmas 4.2 and 4.3 enable us to utilize Lemma 4.1—the bespoke TCT analysis with at most ⌈log2 (h + 1)⌉ calls and at most 1 target hit—to analyze the privacy of Algorithm 3.

Manuscript under review

5

PRIVACY AND UTILITY

In this section, we present the privacy and utility guarantees of Algorithm 3. The formal proofs are deferred to Appendix C.2 and C.3. Studying Algorithm 3 and its properties shown above, it is clear that it makes only O(log h) queries that depend on any input item. However, each such query materializes a noisy count, so it might appear that the privacy cost should be√ have like O(log h), or maybe O( log h) at best, due to composition bounds. This would give a result similar to the Lumberjack algorithm. Our approach to more tightly bounding this cost is based on the careful choice of query that is posed. The insight is that it is only the “boundary inputs” that incur a genuine privacy cost. Essentially, if the count of a node is far below the threshold τ , then we can reveal this fact without any impact on privacy; symmetrically, if the count is sufficiently far above the threshold, revealing this also does not cost privacy. It is only the inputs that reside close to τ that risk private information. However, for such inputs, we are most likely to receive a B output for them, which stems the leakage of further private information. In particular, we can bound the probability that boundary inputs along a path repeatedly fail to yield a B output. This fits neatly into the specialized version of TCT that we introduced in Section 4.1. 5.1

Privacy Analysis

For Algorithm 1, we instantiate the q-target decomposition (recall Definition 2.8) for target outcome {B}. Informally, we decompose the probability that our algorithm outputs B into component probabilities. Definition 5.1 (Target decomposition for outcome {B}). The target {B} is a q-target for a pair (P0 , P1 ) with parameters (λ, κ) if there is p ∈ [0, 1] and probability distributions C, N0 , N1 , F0 , F1 s.t., for b ∈ {0, 1},
Pb = (1 − κ) pC + (1 − p)Nb + κFb , (15) where N0 ≈λ N1 and minb Nb (B) ≥ q. Note that the common component C costs no privacy for the fixed pair. The residual component Nb is a pure-private access and has a substantial chance to hit the target (i.e., with probability ≥ q). The component Fb is paid for in final δ. This decomposition is for analysis purpose only; it is never computed by the released mechanism and need not be common to different neighboring pairs. Next, we bound the parameters, exceptional mass κ and target hit probability q. Target decomposition under pure-DP. We warm up with a pure-DP version of Algorithm 1. Let BT(c; a, b, λ) denote Algorithm 1 without either deterministic guard, listed as in Algorithm 4. Let Pc be

Algorithm 4 No-guard count query BT(c; a, b, λ) Input: Original node count c ∈ N; public thresholds a, b ∈ R with a < b, local privacy parameter λ > 0 1: Draw fresh independent Z ∼ Lap(1/λ) 2: if c + Z < a then 3: return L 4: else if c + Z > b then 5: return H 6: else 7: return B its law on {L, B, H}. Applying the “Effectiveness of the between target” Lemma [10, Lemma G.1], we obtain the following. For completeness, we provide the full self-contained proof in Appendix C.2. Lemma 5.2 (Target decomposition for BT). Fix λ > 0 and public thresholds a < b satisfying b − a = 2/λ. For each count c ∈ Z≥0 , let Pc denote the output distribution of the unguarded mechanism BT(c; a, b, λ) on Y := {L, B, H}. For any c0 , c1 ∈ Z≥0 with |c1 − c0 | ≤ 1, the singleton target {B} is a qλ -target for the pair (Pc0 , Pc1 ) with parameters (λ, 0), where
1 − e−(b−a)λ (eλ − 1) 1 − e−2 qλ = = . (16) 2λ e −1 1 + eλ Specifically, there exist p ∈ [0, 1] and probability distributions C, N0 , N1 on Y such that Pci = pC + (1 − p)Ni ,

i ∈ {0, 1},

(17)

N0 ≈λ N1 ,

min Ni (B) ≥ qλ .

(18)

and

i∈{0,1}

Target decomposition of Algorithm 1. We now analyze the full version of the algorithm which includes the deterministic outputs for inputs that are truly far from the threshold. This requires an approximate DP analysis. Restoring these deterministic guards recovers Algorithm 1. Lemma 5.3 (Target decomposition for GuardedBT). Fix public parameters 0 < λ ≤ 1, R ≥ 1, and b − a = 2/λ. For each count c ∈ Z≥0 , let Qc denote the output distribution of the guarded mechanism GuardedBT(c; a, b, R, λ) on Y := {L, B, H}. For any c0 , c1 ∈ Z≥0 with |c1 − c0 | ≤ 1, the singleton target {B} is a qλ -target for the pair (Qc0 , Qc1 ) with parameters (λ, κ) for some κ ∈ [0, δ0 ], where qλ is defined in Eq. (16) and δ0 = 12 e−λ(R−1) .

(19)

Specifically, there exist κ ∈ [0, δ0 ], p ∈ [0, 1], and probability distributions C, N0 , N1 , F0 , F1 on Y such that
Qci = (1 − κ) pC + (1 − p)Ni + κFi , i ∈ {0, 1}, (20) and N0 ≈λ N1 ,

mini∈{0,1} Ni (B) ≥ qλ .

(21)

Manuscript under review

The guard test ensures that any count that is far above a or below b is classified correctly with probability 1. This property does not come for free in the analysis. We pay with an additional δ0 in privacy. Then the proof of Lemma 5.3 is rather intuitive. There are three cases to consider: i) both inputs c0 and c1 are below a − R or above b + R ii) both c0 and c1 are within [a − R, b + R], iii) one of c0 or c1 is below a − R or above b + R while the other is within [a − R, b + R]. Note that the case where one of c0 and c1 appears (−∞, a − R) and the other appears in (b + R, ∞) is impossible, since R ≥ 1 and by assumption we have |c0 − c1 | ≤ 1. Case i) is trivial to handle; case ii) degenerates to the no-guard Algorithm 4, which is handled by Lemma 5.2. For case iii), we bound the error probability δ0 that the answers on c0 and c1 disagree, which is the probability that Z ≥ R − 1 for Z ∼ Lap(1/λ). For neighboring databases differing by one leaf record z, only counts on the root-to-leaf path Pz change. Algorithm 3 makes at most ⌈log2 (h+1)⌉ queries on this path and makes no further query there after a B response (namely, a target hit). Fixing the off-path responses, we can apply the bespoke finite-horizon one-hit TCT bound in Lemma 4.1 to the affected queries on Pz , and then reconstructs the complete transcript for Algorithm 3. This gives the following privacy guarantee. The full proof is deferred to Appendix C.2. Theorem 5.4 (Privacy of Algorithm 3). Let T be a finite public rooted tree of height h ≥ 1, with fixed public traversal orders. Fix public parameters τ ≥ 0, 0 < λ ≤ 1, and R ≥ 1. Run Algorithm 3 with thresholds a := τ − 1/λ and b := τ + 1/λ, using fresh independent noise in every randomized invocation of GuardedBT. −2 . For every integer Write L := ⌈log2 (h+1)⌉, qλ := 1−e 1+eλ 1 ≤ r ≤ L, Algorithm 3 is
rλ, L2 e−λ(R−1) + 1{r<L} (1 − qλ )r -DP. (22) Here the integer r ∈ {1, . . . , L} is referred to as the private-call cutoff. It is used for analysis purpose only. We charge at most r calls to the data holder (i.e., the mechanism runs on Nb in Eq. (15)). This leads to a factor of r in the multiplicative privacy parameter (accounted in the final ε) and we treat the event of more than r such calls as an additive privacy failure (accounted in the final δ). The conclusion holds for every such r ∈ [1, L] = [1, ⌈log2 (h + 1)⌉]. We now choose the public parameters so that Algortihm 3 is calibrated to (ε, δ)-DP. Theorem 5.5 (Privacy with explicit parameters). Let T be a finite public rooted tree of height h ≥ 1, with fixed public traversal orders, and let τ ≥ 0 be a public count threshold. Fix privacy parameters 0 < ε ≤ 1 and 0 < δ < 1/10. Set L := ⌈log2 (h + 1)⌉ and r0 :=

l

ln(2/δ) ln(5/4)

m . Choose r := min {L, r0 } and define

ε λ := , r

w :=

1 r = , λ ε

R := 1 +

r L ln . (23) ε δ

Then Algorithm 3 with λ, R and thresholds a := τ − w and b := τ + w satisfies (ε, δ)-DP. 5.2

Utility Analysis

By Theorem 5.5 and the construction of the count query GuardedBT (Algorithm 1), we have the following privacy-utility trade-off for Algorithm 3. Theorem 5.6 (Utility guarantee). Fix h ≥ 1, τ ≥ 0, 0 < ε ≤ 1, and 0 < δ < 1/10. Let L, r, λ, w, and R be defined as in Theorem 5.5. Then Algorithm 3 is (ε, δ)-DP . In addition, the output labels satisfy the (E, β) classification guarantee of Definition 2.1 with error probability β = 0 and additive error margin
(24) E := w + R = 1 + rε 1 + ln Lδ . Eq. (24) satisfies the explicit relaxation   E ≤ 1 + 5 ln(2/δ) 1 + ln logδ2 h = Oε,δ (log log h) , ε (25) which is doubly logarithmic in h at fixed ε and δ. Remark on time complexity. Algorithm 3 marks every node in tree T . For a tree of arity k and height h, the overall time complexity is O(k h ). This cost can be reduced to O(nh), where n is the input database size, utilizing a sparsity-aware implementation of Algorithm 3. The algorithm, its properties, and proofs are deferred to Appendix D; we focus on the privacy-utility trade-off in the main paper. 5.3

Discussion and Comparison to Prior Work

Table 1 compares BetweenCut, Lumberjack [38], Ghazi et al. [25] and Biswas et al. [5] on one public tree, at the same threshold τ and under (ε, δ)-DP. An additive margin E guarantees that, simultaneously for all nodes, counts at least τ + E are labeled Heavy and counts below τ − E are labeled Light, except with probability at most β. Here h is the tree height, n is the database size, and M ≥ n is a public size bound when required. We take privacy parameters 0 < ε ≤ 1 and 0 < δ < 1/10, and error probability 0 < β < 1/2; deterministic guarantees are indicated by β = 0. For [25], we convert relative error α to additive by setting E = ατ . Height dependence. For fixed privacy parameters, our error margin is O(log log h), with error probability β = 0. For fixed ε, δ, β > 0, Ghazi et al.’s bound is O( M τ log h); Biswas et al.’s algorithm gives O(log h).

Manuscript under review

Table 1: Additive error margin comparison at height h. An entry f denotes an error margin E = O(f ). Method

Additive error margin O(·)

Probabilistic error guarantee (β> 0)   1M h ε Ghazi et al. [25] + log log 1 + ε τ δ β      log( 1δ ) log( 1δ ) 1 h log Biswas et al. [5] log + log ε ε δ β s   1 M log h Lumberjack [38] log(1/δ) log h log ε β Deterministic error guarantee (β = 0) q
1 Lumberjack [38] log(1/δ) log h log(1/δ) + log log h ε
1 Ours log(1/δ) log(1/δ) + log log h ε

Lumberjack reduces each record’s participation to O(log h) comparisons and pays a Gaussian √ square-root composition factor, giving errors in O( log h log log h). While the deterministic simultaneous accuracy (β = 0) is already available in Lumberjack, our improvement concerns the exponentially better dependence on h. On input size n ≤ M . Our deterministic error guarantee and the deterministic version of Lumberjack do not require an upper bound on the input size n. In Ghazi et al. [25], M impacts the utility trade-off through the privacy budget: there can be at most O(M/τ ) positive answers during the SVT invocations. In the probabilistic version of Lumberjack [38], the M factor is introduced by the union bound over O(n) independent, unbounded noises. On parameter regime ε ≤ 1. Our results can be extended to any ε > 1. The ε ≤ 1 restriction simplifies our parameter calibration rather than being intrinsic to BetweenCut. In particular, it ensures that λ = ε/r ≤ 1 in each call of GuardedBT, hence the q-target decomposition satisfies qλ ≥ 1/5, so the TCT overflow term is bounded by (4/5)r . Lumberjack similarly assumes ε ≤ 1 in its closed-form Gaussian calibrations for simplicity—their restriction comes from the classical Gaussian mechanism bound used to obtain a noise scale proportional to 1/ε [16]. Accordingly, BetweenCut can be calibrated for ε > 1, but exploiting the larger privacy budget requires more detailed analysis on the residual-call cutoff threshold. We omit this additional analysis for brevity here. Relation to lower bounds in [25]. Our result is consistent with the lower √ bounds in [25]. [25, Theorem 5.2] establish an Ωε,δ ( h) lower bound for numerical estimation of all node counts under an additive-only error criterion. Our BetweenCut releases only Heavy/Light labels at a single public threshold τ , not numerical

count estimates with uniformly bounded additive error. Their pure-DP lower bound [25, Theorem 5.1] also does not apply to our approximate-DP guarantee. For every fixed multiplicative tolerance 0 < α < 1, a geometricthreshold reduction using BetweenCut achieves αmRMSE Oα,ε,δ (log log h), improving the height dependence of the Oα,ε,δ (log h) bound in [25, Theorem 4.1]. The construction and proofs appear in Appendix E. We leave matching height-dependent lower bounds for approximate-DP heavy-node classification and additive– multiplicative tree counting to future work. Relation to Lumberjack’s algorithmic design. BetweenCut shares Lumberjack’s balanced traversal and upward/downward label propagation; the twosided deterministic guards to avoid union bounding over all node also appear in [38]. Our central innovation is to turn a middle ‘Between’ response into a permanent cut (hence the name BetweenCut): all proper ancestors are marked Heavy, while the queried node and its descendants are marked Light. This stops every subsequent query on every root-to-leaf path through that node, so each record participates in at most one middle response. Constructing the q-target decomposition, we obtain a finite-horizon TCT analysis that charges O(log(1/δ)) calls to the actual private input, with the overflow probability absorbed into δ. This avoids accounting for all O(log h) affected tests, which would lead to an Ω(poly(log h)) error as in [38]. This approach allows us to obtain an exponential improvement in height dependence over [38]. The compact design of our solution—one public schedule, a three-outcome test, and deterministic label propagation—offers a promising primitive for private hierarchical counting and other structured-data applications.

6

CONCLUSION

We introduce an (ε, δ)-DP algorithm for heavy node classification on a public tree of height h, with an input size-independent additive error margin of Oε,δ (log log h) that holds simultaneously for all nodes with probability one (Theorem 5.6). The key idea is to turn a target hit (middle answer for the BetweenThresholds mechanism) into a final cut: each record can affect at most one target hit, while balanced level search limits its affected queries to O(log h). Our analysis instantiates target-charging technique in this finite-horizon, one-target-hit setting, yielding the explicit privacy guarantee (Lemma 4.1), which may be of independent interest—our formulation is useful when at most one target can be encountered and there are too few target hits to amortize the overhead of the general TCT analysis. A limitation of the current analysis is that the hidden constants are sufficiently large that the point where BetweenCut achieves smallest

Manuscript under review

absolute error is only for extremely deep trees. Future directions therefore include tightening the dependence on ε and δ, determining the optimal height dependence, and investigating downstream applications. AI use statement In this work, we used generative AI tools for checking our proof details, identifying potential errors and ambiguities, deriving constants in the big-oh analyses, and improving the paper writing such as finding grammatical errors and missing references. The research questions and main results are determined and produced by the authors. We have not used generative AI tools for designing the algorithm, and experiments are not applicable to this complexity-focused work. We have reviewed all AI-assisted work: we have confirmed that the computation is correct line by line. We take responsibility for the final content of this work, including all claims and proofs produced with the aid of generative AI. References [1] Daniel Alabi, Omri Ben-Eliezer, and Anamay Chaturvedi. Bounded space differentially private quantiles. TMLR, 2023. [2] Ece Alptekin, Berkay Kemal Balioglu, and M. Emre Gursoy. Hierarchical spatial decompositions under local differential privacy. TKDD, 19 (7), August 2025. [3] Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. Practical locally private heavy hitters. In NIPS, page 2285–2293, 2017. [4] Akash Bharadwaj and Graham Cormode. Sample and threshold differential privacy: Histograms and applications. In AISTATS, 2022. [5] Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, and Zhengyi Zhou. Differentially private hierarchical heavy hitters. PACMMOD, 2 (5), November 2024. [6] Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private l2 -heavy hitters in the sliding window model. In ICLR, 2023. [7] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634–649, 2015. [8] Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra McMillan, , and Kunal Talwar. Differentially private heavy hitter detection using federated analytics. In ICML, 2023.

[9] Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In ICML, 2021. [10] Edith Cohen and Xin Lyu. The target-charging technique for privacy analysis across interactive computations. In NeurIPS, 2023. [11] 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, page 472–482, 2023. [12] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Differentially private spatial decompositions. In ICDE, pages 20–31, 2012. [13] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, and Thanh T. L. Tran. Differentially private summaries for sparse data. In ICDT, page 299–311, 2012. [14] Differential Privacy Team. Learning with privacy at scale, December 2017. URL https://machinelearning.apple.com/ research/learning-with-privacy-at-scale. Accessed: 2026-10-05. [15] David Durfee. Unbounded differentially private quantile and maximum estimation. In NeurIPS, 2023. [16] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. FTCS, 2014. [17] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006. [18] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006. [19] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, 2009. [20] Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In FOCS, 2010. [21] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC, 2015. [22] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT, pages 735–751, 2015.

Manuscript under review

[23] Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In COLT, 2017. [24] Julien Ferry, Ricardo Fukasawa, Timothée Pascal, and Thibaut Vidal. Trained random forests completely reveal your dataset. In ICML, 2024. [25] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On differentially private counting on trees. In ICALP, 2023. [26] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In ICML, 2021. [27] Justin Hsu, Aaron Roth, and Jonathan Ullman. Differential privacy for the analyst via private equilibrium computation. In STOC, 2013. [28] Ziyue Huang, Yuting Liang, and Ke Yi. Instanceoptimal mean estimation under differential privacy. In NeurIPS, 2021. [29] Jacob Imola, Fabrizio Boninsegna, Hannah Keller, Anders Aamand, Amrita Roy Chowdhury, and Rasmus Pagh. Differentially private quantiles with smaller error. In NeurIPS, 2025. [30] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In ICML, 2015.

[37] Christian Janos Lebeda and Lukas Retschmeier. The Correlated Gaussian Sparse Histogram Mechanism. In FORC, 2025. [38] Christian Janos Lebeda, David Erb, Tudor Cebere, and Aurélien Bellet. Lumberjack: Better differentially private random forests through heavy hitter detection in trees. In NeurIPS, 2026. [39] Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. Accuracy first: selecting a differential privacy level for accuracyconstrained erm. In NIPS, 2017. [40] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. PVLDB, 2017. [41] Anupama Nandi and Raef Bassily. Privately answering classification queries in the agnostic pac model. In ALT, 2020. [42] Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. In ALT, 2018. [43] Jonathan Ullman. Private multiplicative weights beyond linear queries. In PODS, 2015. [44] Tianhao Wang, Ninghui Li, and Somesh Jha. Locally differentially private heavy hitter identification. TDSC, 18(2):982–993, 2021.

[31] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In COLT, 2020.

[45] Hao Wu and Anthony Wirth. Asymptotically optimal locally private heavy hitters via parameterized sketches. In AISTATS, 2022.

[32] Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In COLT, 2021.

[46] Yonghui Xiao, Li Xiong, Liyue Fan, Slawomir Goryczka, and Haoran Li. Dpcube: Differentially private histogram release through multidimensional partitioning. TDP, 2014.

[33] Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In ICML, 2022. [34] Florian Kerschbaum, Steven Lee, and Hao Wu. Optimal pure differentially private sparse histograms in deterministic linear time. PACMMOD, 4(2), May 2026. [35] Kunho Kim, Sivakanth Gopi, Janardhan Kulkarni, and Sergey Yekhanin. Differentially private ngram extraction. In NIPS, pages 5102–5111, 2021. [36] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In WWW, 2009.

[47] Jun Zhang, Xiaokui Xiao, and Xing Xie. PrivTree: A differentially private algorithm for hierarchical decompositions. In SIGMOD, pages 155–170, 2016. [48] Yuemin Zhang, Qingqing Ye, and Haibo Hu. Federated heavy hitter analytics with local differential privacy. PACMMOD, 3(1), 2025. [49] Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. Federated heavy hitters discovery with differential privacy. In AISTATS, 2020.

Manuscript under review

A

EXTENDED DISCUSSION ON RELATED WORKS

A.1

Naive Baselines for Differentially Private Heavy Nodes

The following full-tree baselines visit every node, adds independent noise to their true node count, and labels them heavy exactly when their noisy count is at least τ . Algorithm 5 gives a common template for the Laplace and Gaussian variants; their noise distributions are specified below. Algorithm 5 Full-tree Classification Baseline Input: Public tree T of height h; public threshold τ ; private database D; noise distribution P. 1: for i = h − 1, h − 2, . . . , 0 do 2: for each u at depth i do 3: Draw Zu ∼ P independently. 4: e cu (D) ← cu (D) + Zu . 5: if e cu (D) ≥ τ then 6: Classify node u as Heavy 7: else 8: Classify node u as Light
Laplace baseline. For ε > 0, choose the noise distribution P to be Lap hε . Each node count has sensitivity one. Within each level, the descendant leaf sets are disjoint, so the full count vector for all nodes has an ℓ1 -sensitivity of h. The thresholding step is then just post-processing of the DP output [16]. Using the Laplace tail bound and a union bound over all N = k h−1 nodes (k is the arity),     εE Pr max |Zu | > E ≤ N exp − . u∈V h Therefore, a sufficient simultaneous classification margin is     h N h N ln(1/β) 2 ELap := ln =O ln =O h , ε β ε β ε

(26)

(27)

with h = O(log N ) substituted. Gaussian baseline.

For 0 < ε < 1 and 0 < δ < 1/2, choose the noise distribution P to be N (0, σ 2 ), with

2h ln(1.25/δ) . (28) ε2 Adding or removing one individual √ changes at most h coordinates of the full count vector, each by one. Its ℓ2 -sensitivity is therefore at most h. Consequently, the vector Gaussian mechanism [16] gives (ε, δ)-DP. The Gaussian tail bound and the union bound give     E2 Pr max |Zu | > E ≤ 2N exp − 2 . u∈V 2σ σ2 =

Thus, a sufficient simultaneous classification margin is s EGauss := σ 2 = ε

2 ln

2N β

(29)

h ln

1.25 2N ln δ β

(30)

s

! h ln(1/δ) ln(2N/β) =O ε ! p ln(1/δ) ln(1/β) =O h . ε p

More advanced mechanisms aim at sublinear dependencies on h, as reviewed in Section 3.

(31)

(32)

Manuscript under review

A.2

Additive Error Guarantee of Ghazi et al.

Ghazi et al. [25] originally uses a relative tolerance γ ∈ [0, 1) rather than the additive absolute tolerance E. It also includes a public mass bound M ≥ n. Its required answers are Heavy for cu (D) ≥ (1 + γ)τ and Light for cu (D) < (1 − γ)τ , provided n ≤ M . We show how to translate their relative error guarantee to our absolute error guarantee. Define    2h eε/2 − 1 ΛG (h, β, ε, δ) = max 48 ln , 6 ln 1 + . β δ Lemma 4.3 of [25] gives an (ε, δ)-DP algorithm with a relative tolerance γ ∈ (0, 1/2), whenever s 2M ΛG . τ≥ γε

(33)

(34)

We consider failure probability 0 < β < 1/2, following [25]. At a fixed τ , rearranging Eq. (34) gives EG := γτ 2M ΛG ≥ ετ    2M 2h eε/2 − 1 = max 48 ln , 6 ln 1 + . ετ β δ

(35) (36) (37)

Therefore, at a prescribed threshold τ , [25] provides an algorithm that certifies an additive margin in O(log h). A.3

Other Related Works

PrivTree. PrivTree [47] provides depth-independent noise calibration for private hierarchical decomposition, but its splitting rule includes a depth-dependent bias. In particular, for node v at depth d, its noisy count is compared with a threshold biased by O(d). It does not automatically achieve a bounded error margin and is not comparable with our method. Threshold-release reduction. In Section 1.3 of [25], Ghazi et al. discuss a reduction from the tree counting problem to the learning thresholds problem [7]. This would give an additive error   Oε,δ (log∗ |X |)O(1) (log n)2.5 . (38) We note that the error is dependent on the size of the input database, n. It is therefore not directly compared with our method: Our method has a size-independent error margin while the error of [7] depends on the input size due to the (log n)2.5 factor.

B

FURTHER ALGORITHMIC DETAILS FOR BETWEENCUT

B.1

Label Propagation

Algorithm 6 implements the deterministic label propagation routines used by Algorithm 3. The routines inspect only the public tree and the current labels and make no additional count queries. B.2

Algorithm Properties

Lemma B.1 (Consistency and termination). For every execution of Algorithm 3 on a finite rooted tree T , the following statements hold. (i) Structural consistency. Immediately after initialization and after each completed iteration of the inner node loop (lines 5–15), the Heavy set is ancestor-closed, the Light set is descendant-closed, and the two sets are disjoint.

Manuscript under review

Algorithm 6 Marking routines 1: procedure MarkUp(u) 2: while u ̸= null and label[u] ̸= H do 3: label[u] ← H 4: u ← parent(u) 5: procedure MarkDown(u) 6: if label[u] = L then 7: return 8: label[u] ← L 9: for each child v of u, in public child order do 10: MarkDown(v)

(ii) Permanent labels. During Algorithm 3, every label assignment after initialization changes an unknown label to Heavy or Light: ? −→ H, ? −→ L. Consequently, each node is labeled at most once, and its label thereafter remains unchanged. (iii) Termination and completeness. Algorithm 3 terminates, and every node is labeled Heavy or Light when it returns. Lemma B.2 (Positive-count query bound). Fix a database D of size n. For any execution of Algorithm 3, let Q be the set of nodes at which GuardedBT (Algorithm 1) is invoked, and define Q+ := {u ∈ Q : cu (D) > 0}.

(39)

Then |Q+ | ≤

X

cu (D) ≤ n⌈log2 (h + 1)⌉.

(40)

u∈Q

B.2.1

Dense implementation cost

We analyze the dense implementation of Algorithm 3. Computational conventions. We assume that accessing counts and labels, moving along one tree edge, arithmetic, comparisons, and Laplace sampling each take constant time. Each node identifier, count, or label occupies constant space. Each record gives direct access to its leaf, and the public height h is given. Auxiliary space excludes the input database and the given public tree. Lemma B.3 (Dense implementation cost). Let n := |D| and N := |V |. For every execution of Algorithm 3, the following hold. (i) Scans, queries, and assignments. The inner node loop considers each node exactly once. There are at most N calls to GuardedBT and exactly N marking assignments (i.e., labeling a node to H or L) after initialization. (ii) Total cost. Under the computational conventions above, the total marking work is O(N ). Including count computation, level-list construction, traversal, and output, the algorithm can be implemented in O(n + N ) time and O(N ) auxiliary space. B.3

Proofs of Algorithmic Properties

Proof of Lemma B.1. (i)–(ii) Consistency and permanent labels. We induct on the completed iterations of the inner node loop. Initially, both labeled sets are empty, and skipping an already labeled node changes nothing. Otherwise, let u be the queried node and H, L the current Heavy and Light sets. Since u is unknown, the closure invariant implies Anc(u) ∩ L = ∅, Desc(u) ∩ H = ∅. Thus upward marking encounters no Light node, and downward marking encounters no Heavy node. In the Between case, the upward call modifies only proper ancestors of u, disjoint from Desc(u), so it cannot introduce a

Manuscript under review

conflict for the downward call. Both routines stop before assigning to a node already carrying the intended label. Hence every assignment changes an unknown label to Heavy or Light. By the closure invariant, early stopping omits only ancestors already Heavy or subtrees already Light. Consequently, High adds Anc(u) to H, Low adds Desc(u) to L, and Between adds Anc(u) \ {u} to H and Desc(u) to L. These updates preserve closure and disjointness, completing the induction. (iii) Termination and completeness. The recursive intervals in DepthOrder strictly shrink and partition the current interval except for its middle depth. Thus the recursion terminates and lists each depth exactly once, so every node is considered exactly once. Each query terminates, and each marking call traverses a finite ancestor chain or subtree; hence Algorithm 3 terminates. When considered, a node is either already labeled or receives a label from its query, regardless of the answer. By (ii), this label persists, so every node is labeled at return. Proof of Lemma 4.2. We induct on the number s of levels in a recursive interval of DepthOrder, proving that it contains at most ⌈log2 (s + 1)⌉ queried nodes of any root-to-leaf path P in any execution. The case s = 0 is immediate. For s ≥ 1, processing the middle level contributes at most one query on P and leaves every node at that level labeled. By the closure and permanence properties of Lemma B.1, all remaining queries on P within the interval lie in at most one subinterval, containing at most ⌊s/2⌋ levels. The induction hypothesis therefore bounds the total by 
 1 + log2 ⌊s/2⌋ + 1 = ⌈log2 (s + 1)⌉. Taking s = h proves the claim. Proof of Lemma B.2. Counting identity. List the records of D as z1 , . . . , zn , including repetitions. A record zr contributes to cu (D) exactly when u ∈ Pzr . Interchanging the two finite sums gives X u∈Q

cu (D) =

n XX

1{u ∈ Pzr } =

u∈Q r=1

n X X

1{u ∈ Pzr } =

r=1 u∈Q

n X

|Q ∩ Pzr |.

(41)

r=1

Query bound. Every node in Q+ has an integer count of at least one, so X |Q+ | ≤ cu (D).

(42)

u∈Q

By the counting identity and Lemma 4.2, X u∈Q

cu (D) =

n X

|Q ∩ Pzr | ≤

r=1

n X

⌈log2 (h + 1)⌉.

(43)

r=1

Proof of Lemma 4.3. Let B be the set of queried nodes at which Algorithm 1 returns B. We prove the following two items: (i) If a query at u returns B, then, after the corresponding inner-loop iteration, every node on every root-to-leaf path through u is labeled. No subsequent query occurs on any such path. (ii) Every root-to-leaf path P satisfies |B ∩ P | ≤ 1. Proof for (i). When a query at u returns B, the algorithm calls MarkUp on parent(u) and MarkDown on u. After these calls, every proper ancestor of u is Heavy, and u and all its descendants are Light. Every node on a root-to-leaf path through u belongs to one of these two sets. By Lemma B.1, these labels are permanent, and Algorithm 5 skips labeled nodes. Hence no subsequent query occurs on such a path. Proof for (ii). Suppose two distinct nodes of B were comparable under the ancestor relation. They would lie on a common root-to-leaf path. By (i), the Between answer at whichever node was queried first would prevent the other from being queried, leading to a contradiction. Thus |B ∩ P | ≤ 1 for every root-to-leaf path P .

Manuscript under review

Proof of Lemma B.3. (i) Scans, queries, and assignments. The depth order lists each depth exactly once, and each node appears in exactly one level list. Only unknown nodes are queried, so there are at most N calls to GuardedBT. By Lemma B.1, every marking assignment labels a previously unknown node and every node is eventually labeled. Hence there are exactly N such assignments. (ii) Total cost. Each successful MarkUp iteration labels a previously unknown node, so there are at most N such iterations in total. Each invocation has at most one final stopping test. MarkDown scans a node’s child list only when that node first becomes Light, so each of the N − 1 tree edges is scanned at most once by this routine. Every recursive downward call is charged to such an edge. Each query initiates at most one upward and one downward call. Together with (i), these bounds give O(N ) total marking work, without requiring bounded arity. Initialize all counts to zero, tally the n leaf records, and sum child counts in a bottom-up traversal, taking O(n + N ) time. An ordered depth-first traversal builds the level lists in O(N ) time, with each list following the order induced by the public child order. The depth order is generated in O(h) time. Label initialization, node scans, GuardedBT calls, and output take O(N ) additional time. Since h ≤ N , the total time is O(n + N ). Counts, labels, level lists, and traversal stacks use O(N ) auxiliary space.

C

PRIVACY AND UTILITY PROOFS

C.1

Proof for the Bespoke Analysis for TCT

Proof of Lemma 4.1. Fix neighboring inputs D0 , D1 and fix the analyst’s data-independent randomness. We work with an analysis-only augmented transcript. At each call, use the decomposition
Pb = (1 − κ) pC + (1 − p)Nb + κFb

(44)

to generate the output as follows. First define a branch in exceptional, common, and residual J ∈ {exc, com, res}

(45)

(1 − κ)p,

(46)

with probabilities κ,

(1 − κ)(1 − p),

respectively. Conditional on the branch, sample from Fb , C, or Nb , respectively. The parameters of the decomposition may depend on the preceding transcript, but for a fixed preceding history the branch probabilities are the same under D0 and D1 . Exceptional branches.

Let Eexc := {an exceptional branch is selected at some call}.

(47)

For i ∈ {1, . . . , K}, let Ei be the event that the ith call occurs and selects the exceptional branch. Conditional on every history preceding that call, its exceptional probability is at most κ0 . Hence, for either b ∈ {0, 1}, Pr[Ei ] ≤ κ0 , b

and therefore Pr[Eexc ] ≤ b

Residual overflow.

K X i=1

Pr[Ei ] ≤ Kκ0 . b

(48)

(49)

Call a sample from Nb a residual draw. Define the overflow event: Eov := {at least r + 1 residual draws occur before any exception}.

(50)

For j ≥ 0, define Aj to be the event that the first j residual draws all occur before any exceptional branch and all j outputs miss their respective targets. In particular, A0 is satisfied with certainty.

Manuscript under review

We claim that, for either input, Pr[Aj ] ≤ (1 − q)j . b

(51)

Suppose Aj−1 has occurred. The interaction may terminate before another residual draw is reached. If a jth residual draw is reached, however, its conditional law is Nb , and therefore its conditional probability of missing the target is at most 1 − q. Consequently, Pr[Aj | Aj−1 ] ≤ 1 − q, b

(52)

and induction gives (51). If Eov occurs, then the first r residual draws must all miss their targets; otherwise a target hit would have stopped the interaction before the (r + 1)st residual draw. Thus Eov ⊆ Ar ,

(53)

Pr[Eov ] ≤ (1 − q)r .

(54)

and hence b

When r = K, the event Eov is impossible, because there are at most K calls in total. The good event.

Let E>r := {more than r residual draws occur during the interaction},

(55)

c c G := Eexc ∩ E>r .

(56)

and define

Thus G is the event that no exceptional branch occurs and at most r residual draws occur. By De Morgan’s law, Gc = Eexc ∪ E>r .

(57)

Decompose the second event according to whether an exceptional branch occurs: c E>r = (Eexc ∩ E>r ) ∪ (Eexc ∩ E>r ).

(58)

Eexc ∩ E>r ⊆ Eexc ,

(59)

c Gc = Eexc ∪ E>r ⊆ Eexc ∪ (Eexc ∩ E>r ).

(60)

Eov := {the (r + 1)st residual draw occurs before any exceptional branch}.

(61)

Since

we obtain

Recall the overflow event

c On the event Eexc ∩ E>r , no exceptional branch occurs anywhere in the interaction and at least r + 1 residual draws occur. Therefore the (r + 1)st residual draw necessarily occurs before any exceptional branch, and hence c Eexc ∩ E>r ⊆ Eov .

(62)

Gc ⊆ Eexc ∪ Eov .

(63)

Consequently, Taking probabilities and applying the union bound gives, for either b ∈ {0, 1}, Pr[Gc ] ≤ Pr[Eexc ] + Pr[Eov ] ≤ Kκ0 + 1{r<K} (1 − q)r . b

b

b

(64)

Manuscript under review

Now fix an augmented transcript ω ∈ G. Since no exceptional branch occurs, every factor in its probability comes either from a common branch or from a residual branch. The branch-selection probabilities are identical under the two inputs, and the common distribution C is also identical. Hence these factors cancel in the likelihood ratio. For each residual draw, N0 (y) ≤ eλ N1 (y)

N1 (y) ≤ eλ N0 (y).

and

(65)

Since ω ∈ G contains at most r residual draws, Pr[ω] ≤ erλ Pr[ω], 0

Pr[ω] ≤ erλ Pr[ω].

1

1

(66)

0

Finally, let S be any event in the released transcript space, and let Se be its inverse image in the augmented transcript space. Using Eq. (64) and Eq. (66), Pr[S] ≤ Pr[Se ∩ G] + Pr[Gc ] 0

0

rλ

≤e

rλ

≤e

0

Pr[Se ∩ G] + Kκ0 + 1{r<K} (1 − q)r 1

Pr[S] + Kκ0 + 1{r<K} (1 − q)r . 1

Exchanging D0 and D1 gives the reverse inequality. The important point for this Lemma that we will use subsequently is that r is an analysis parameter that we are free to tune: increasing r weakens the ε component but strengthens the δ component of the (ε, δ)-DP guarantee. We will use this freedom subsequently to choose a value of r that achieves the target (ε, δ) pair for the main theorem. C.2

Proofs for Privacy

Proof of Lemma 5.2. Write Pi := Pci for i ∈ {0, 1}, and exchange the indices if necessary so that c0 ≤ c1 . Set ξ := eλ > 1,

γ := 1 − e−λ(b−a) .

(67)

We will specify the probabilities of each output under C, N0 , N1 and prove that Pi = pC + (1 − p)Ni ,

N0 ≈λ N1 ,

Ni (B) ≥

γ . 1+ξ

(68)

Step 1: The original output probabilities. For Z ∼ Lap(1/λ), define ℓi := Pi (L) = Pr[ci + Z < a],

(69)

mi := Pi (B) = Pr[a ≤ ci + Z ≤ b],

(70)

ui := Pi (H) = Pr[ci + Z > b].

(71)

These are ordinary real numbers satisfying ℓi + mi + ui = 1. In particular, mi > 0 because a < b and the Laplace density is positive everywhere. Since c0 ≤ c1 , ℓ0 ≥ ℓ1 ,

u0 ≤ u1 .

(72)

λ(|x−c1 |−|x−c0 |) The densities fi (x) = (λ/2)e−λ|x−ci | satisfy ff01 (x) ∈ [ξ −1 , ξ], since |c1 − c0 | ≤ 1. Integrating (x) = e over the regions corresponding to any set of output symbols gives

P0 (S) ≤ ξP1 (S),

P1 (S) ≤ ξP0 (S),

S ⊆ {L, B, H}.

(73)

Manuscript under review

Step 2: Choose how much probability is shared. We assign the same amount αL of the Low probability under each input to the common component, and similarly assign αH of the High probability. We assign no Middle probability to the common component. The amounts must be chosen so that the remaining probabilities still satisfy the factor-ξ privacy bounds. For the Low and High outputs, respectively, choose them to satisfy ℓ0 − αL = ξ(ℓ1 − αL ),

u1 − αH = ξ(u0 − αH ).

(74)

ξu0 − u1 . ξ−1

(75)

Solving these scalar equations gives αL :=

ξℓ1 − ℓ0 , ξ−1

αH :=

These choices are valid fractions of probability mass to assign to the common component. Indeed, Eq. (73) gives ℓ0 ≤ ξℓ1 and u1 ≤ ξu0 , so both quantities are nonnegative. Also, by Eq. (72) ℓ0 − ℓ1 ≤ ℓ1 ≤ ℓi , ξ−1 u1 − u0 αH = u0 − ≤ u0 ≤ ui . ξ−1 αL = ℓ1 −

(76) (77)

Thus neither amount exceeds the corresponding output probability under either input. Set p := αL + αH ,

ρ := 1 − p.

(78)

For each i, we have 0 ≤ p ≤ ℓi + ui = 1 − mi < 1, so ρ ≥ mi > 0. Step 3: Define the distributions and verify the mixture. If p > 0, define C by its three output probabilities: αL αH C(L) := , C(B) := 0, C(H) := . (79) p p If p = 0, define C(L) = 1 and C(B) = C(H) = 0; this choice is immaterial because C then has mixture weight zero. In either case, C is a probability distribution and pC(L) = αL ,

pC(B) = 0,

pC(H) = αH .

(80)

For each i ∈ {0, 1}, define Ni by ℓi − αL , ρ mi Ni (B) := , ρ ui − αH Ni (H) := . ρ All three quantities are nonnegative by Step 2, and their sum is Ni (L) :=

ℓi − αL + mi + ui − αH 1−p = = 1. ρ ρ

(81)

(82)

Hence Ni is a probability distribution. Now consider sampling from C with probability p, and from Ni with probability ρ = 1 − p. For each output, the resulting probability is pC(L) + ρNi (L) = αL + (ℓi − αL ) = ℓi ,

(83)

pC(B) + ρNi (B) = 0 + mi = mi ,

(84)

pC(H) + ρNi (H) = αH + (ui − αH ) = ui .

(85)

Thus this sampling procedure reproduces Pi exactly. Equivalently, Pi = pC + (1 − p)Ni .

(86)

Manuscript under review

Step 4: Verify privacy of the residual pair. The two equations used to choose the common amounts in Step 2, together with the common normalizing factor ρ, give N0 (L) = ξN1 (L),

N1 (H) = ξN0 (H).

(87)

These identities also hold when the corresponding residual probabilities are zero. At the Middle output, N0 (B) =

m0 m1 ≤ξ = ξN1 (B), ρ ρ

(88)

and the reverse inequality also holds from Eq. (73). Consequently, N0 ≈λ N1 . Step 5: Bound the residual Middle probability. By construction, Ni (B) = mi /ρ. Thus it remains to show that the remaining total probability ρ is not too large relative to mi . First, applying Eq. (73) to the non-Low and non-High events gives 1 − ℓ1 ≤ ξ(1 − ℓ0 ),

1 − u0 ≤ ξ(1 − u1 ).

(89)

Using the first inequality and αH ≥ 0, we obtain ρ := 1 − (αL + αH ) ≤ 1 − αL =

(ξ 2 − 1)(1 − ℓ0 ) ξ(1 − ℓ1 ) − (1 − ℓ0 ) ≤ = (1 + ξ)(1 − ℓ0 ) ≤ (1 + ξ)(1 − ℓi ). (90) ξ−1 ξ−1

Similarly, using the second inequality and αL ≥ 0, ρ ≤ 1 − αH =

ξ(1 − u0 ) − (1 − u1 ) (ξ 2 − 1)(1 − u1 ) ≤ = (1 + ξ)(1 − u1 ) ≤ (1 + ξ)(1 − ui ). ξ−1 ξ−1

(91)

Fix i ∈ {0, 1}. There are three cases, depending only on the location of ci . If ci ≤ a, the Laplace upper-tail formula gives 1 − ℓi =

1 −λ(a−ci ) e , 2

mi =

1 −λ(a−ci ) e 1 − e−λ(b−a) = γ(1 − ℓi ). 2

(92)

Therefore, by Eq. (90), Ni (B) =

mi γ(1 − ℓi ) γ ≥ = . ρ (1 + ξ)(1 − ℓi ) 1+ξ

(93)

If ci ≥ b, the Laplace lower-tail formula gives 1 − ui =

1 −λ(ci −b) e , 2

mi =

1 −λ(ci −b) e 1 − e−λ(b−a) = γ(1 − ui ). 2

(94)

Eq. (91) yields γ(1 − ui ) γ = . (1 + ξ)(1 − ui ) 1+ξ

Ni (B) ≥

(95)

If a < ci < b, set x := e−λ(ci −a) ,

y := e−λ(b−ci ) .

(96)

x+y . 2

(97)

Then x, y ∈ (0, 1), xy = e−λ(b−a) = 1 − γ, and mi = 1 −

Since (1 − x)(1 − y) ≥ 0, we have x + y ≤ 1 + xy = 2 − γ, and hence mi ≥ γ/2. Because ρ ≤ 1 and 1 + ξ > 2, Ni (B) =

mi γ γ ≥ mi ≥ ≥ . ρ 2 1+ξ

(98)

Manuscript under review

The bound holds for each i, regardless of the location of the other count. In particular, it covers pairs lying on different sides of a threshold. Finally, since b − a = 2/λ, γ 1 − e−2 1 − e−λ(b−a) = = qλ . = 1+ξ 1 + eλ 1 + eλ

(99)

Together with Steps 3–4, this proves the required pure target decomposition. Proof of Lemma 5.3. Write Pi := Pci for the unguarded output laws from Lemma 5.2, and Qi := Qci for the guarded output laws. Let ∆s denote the probability distribution that returns s ∈ Y with probability one. Whenever κ = 0, choose the unused distributions F0 = F1 = ∆B . Exchange the indices if necessary so that c0 ≤ c1 . If the counts are distinct, c1 = c0 + 1. Identical guarded laws. If c0 = c1 , or both counts lie in the same deterministic region, then Q0 = Q1 . Choose κ = 0,

p = 1,

C = Q0 = Q1 ,

N0 = N1 = ∆B .

(100)

These choices give the required decomposition, with identical residual laws and residual target probability one. Both counts are in the randomized region. Suppose a − R < c0 ≤ c1 < b + R. Then Qi = Pi for both inputs. By Lemma 5.2, there exist p ∈ [0, 1] and probability distributions C, N0 , N1 such that Qi = Pi = pC + (1 − p)Ni , N0 ≈ λ N1 ,

i ∈ {0, 1},

(101)

min Ni (B) ≥ qλ .

(102)

i

The hypotheses of that lemma hold because |c1 − c0 | ≤ 1 and b − a = 2/λ. Taking κ = 0 therefore gives the desired guarded decomposition without changing any of these witnesses. One guard is crossed. The counts cannot lie in opposite deterministic regions: that would require c1 − c0 ≥ b − a + 2R > 1. Thus the only remaining cases have one randomized input and one deterministic input. Define ( (1, L, a − c1 ), c0 ≤ a − R < c1 , (j, s, d) := (103) (0, H, c0 − b), c0 < b + R ≤ c1 . Here j indexes the randomized input, and s is the deterministic output on the other input. Hence Qj = Pj ,

Q1−j = ∆s .

(104)

In the lower-guard case, c1 = c0 + 1 ≤ a − R + 1; in the upper-guard case, c0 = c1 − 1 ≥ b + R − 1. Consequently, in either case, d ≥ R − 1 ≥ 0. Define κ to be the probability that the randomized input does not return s. The Laplace tail formulas used in the proof of Lemma 5.2 give 1 −λd 1 e ≤ e−λ(R−1) = δ0 . 2 2

(105)

N0 = N1 = ∆B ,

(106)

κ := Pj (Y \ {s}) = In particular, 0 < κ ≤ δ0 ≤ 1/2. Choose p = 1,

C = ∆s ,

F1−j = ∆s ,

and define the remaining exceptional distribution by its output probabilities: ( 0, y = s, Fj (y) := (107) Pj (y)/κ, y ̸= s. P This is a probability distribution because y̸=s Pj (y) = κ. Moreover, Pj (s) = 1 − κ, so, for every y ∈ Y, Qj (y) = (1 − κ)C(y) + κFj (y),

(108)

Manuscript under review

Q1−j (y) = C(y) = (1 − κ)C(y) + κF1−j (y).

(109)

Since p = 1, these identities give exactly
Qi = (1 − κ) pC + (1 − p)Ni + κFi ,

i ∈ {0, 1}.

(110)

The residual distributions have zero mixture weight, but still satisfy the conditions of the target definition: N0 = N1 = ∆B ,

N0 ≈λ N1 ,

Ni (B) = 1 ≥ qλ .

(111)

These cases exhaust all neighboring count pairs. In every case, the constructed witnesses satisfy the required residual privacy and target bounds, with exceptional mass κ ≤ δ0 . Transcript privacy. For a database D, let Tr(D) := ((u1 , s1 ), . . . , (um , sm ))

(112)

denote the complete query transcript of Algorithm 3, where uj is the node queried at call j, sj ∈ Y is its returned symbol, and m is the total number of calls. Set L := ⌈log2 (h + 1)⌉. Substituting parameters from Lemma 5.3 to Lemma 4.3, we obtain the following privacy guarantees. Lemma C.1 (Transcript privacy). Let T be a finite public rooted tree of height h ≥ 1. Fix public parameters τ ≥ 0, 0 < λ ≤ 1, and R ≥ 1. Run Algorithm 3 with thresholds a := τ − 1/λ and b := τ + 1/λ, using fresh independent noise in every randomized invocation of GuardedBT. Let qλ and δ0 be as in Eqs. (16) and (19), respectively. For every neighboring pair D0 ∼ D1 and every integer 1 ≤ r ≤ L, the transcripts Tr(D0 ) and Tr(D1 ) obtained from Algorithm 3 are (rλ, δr ) -indistinguishable for δr := Lδ0 + 1{r<L} (1 − qλ )r .

(113)

Proof of Lemma C.1. Fix neighboring databases and orient them as D1 = D0 ⊎ {z}, where z is a leaf record. Let Pz be its root-to-leaf path. The original node counts satisfy cu (D1 ) − cu (D0 ) = 1{u∈Pz } .

(114)

Call a query affected if its node belongs to Pz . For a fixed preceding query-response transcript, the next queried node and any stopping decision are determined by the public traversal order and the labels obtained from earlier responses. Fix the off-path randomness. Recall from Lemma 5.3 that Qc is the guarded output law of GuardedBT (Algorithm 1) on input count c. For each u ∈ / Pz , independently pre-sample an output Wu ∼ Qcu (D0 ) = Qcu (D1 ) ,

(115)

independently also of all randomness used at affected queries. The equality follows from Eq. (114). Write W = (Wu )u∈P / z and let µ denote its law. For this fixed neighboring pair, µ is the same under both inputs. Algorithm 3 invokes GuardedBT (Algorithm 1) at each node at most once. Consequently, using Wu as the answer whenever an off-path node u is queried, and using fresh randomness at affected queries, reproduces the original transcript distribution exactly. Apply Lemma 4.1 to the affected queries. Fix a realization w with µ(w) > 0. Consider a simulator that knows D0 , D1 , w, but whose private input is only the bit i ∈ {0, 1}. It follows Algorithm 3, answers every off-path query at u by wu , and obtains an affected response at u ∈ Pz by invoking the two-input mechanism Mu (i) ∼ Qcu (Di )

with target {B}.

(116)

Let Aw (i) denote the query-response transcript of these affected invocations only. Since w is fixed, the simulator’s next affected request and its decision that no affected requests remain are functions of the preceding affected transcript, the fixed quantities D0 , D1 , w, and the public tree and traversal order. The affected responses use fresh randomness, so their conditional laws are exactly the displayed laws of Mu .

Manuscript under review

For every affected request, the two counts differ by one. Lemma 5.3 therefore gives the required target decomposition with local parameter λ, target parameter qλ , and exceptional mass at most δ0 . Then we can apply Lemma 4.1 on the two-element input space {0, 1}, with 0 and 1 designated neighbors, and with K = ⌈log2 (h + 1)⌉,

q = qλ ,

κ0 = δ0 .

(117)

It follows that Aw (0) and Aw (1) are (rλ, δr )-indistinguishable, uniformly over w. Recover the complete transcript. For fixed w, the full transcript can be reconstructed by replaying the public traversal, using wu at off-path queries and the recorded responses in Aw (i) at affected queries. This also reconstructs any off-path queries after the last affected query. Hence there is a deterministic map Φw , the same for both values of i, such that Φw (Aw (i)) has the full transcript law in the simulation with off-path answers w. For any event S in the complete transcript space: X Pr[Tr(D0 ) ∈ S] = µ(w) Pr[Φw (Aw (0)) ∈ S] w

≤

X

µ(w) erλ Pr[Φw (Aw (1)) ∈ S] + δr

w

= erλ Pr[Tr(D1 ) ∈ S] + δr .

(118)

Exchanging the inputs completes the proof for Eq. (113). The released heavy set is a deterministic function of Tr(D) and the public tree and traversal order. Post-processing preserves DP, so the guarantee in Lemma C.1 also holds for Algorithm 3, which was presented as Theorem 5.4. Proof of Theorem 5.5. Since h ≥ 1, we have L := ⌈log2 (h+1)⌉ ≥ 1. Also, r0 ≥ 1, so 1 ≤ r ≤ L and 0 < λ = rε ≤ 1. Moreover, L/δ > 1 implies R > 1, and w = 1/λ. Theorem 5.4 applies. The multiplicative privacy parameter is rλ = ε. The guard term satisfies L −λ(R−1) L δ e = e− ln(L/δ) = . 2 2 2

(119)

If r = L, term 1{r<L} (1 − qλ )r vanishes, proving (ε, δ/2)-DP. Otherwise, r = r0 < L. Applying Theorem 5.4, we obtain  r 4 δ (1 − qλ )r ≤ = e−r ln(5/4) ≤ e− ln(2/δ) = . 5 2

(120)

Combining Eq. (119) and Eq. (120), the total additive privacy parameter is at most δ. This proves (ε, δ)-DP. C.3

Proofs for Utility

Theorem C.2 (Exact deterministic margin). On any input database D, Algorithm 3 satisfies the following with probability 1. b =⇒ cu (D) > a − R = τ − (w + R), u∈H b =⇒ cu (D) < b + R = τ + (w + R). u∈ /H

(121) (122)

Consequently E = w + R is a simultaneous deterministic margin as required in Definition 2.1. Combining Theorem 5.5 and Theorem C.2 gives exactly the utility guarantees in Theorem 5.6. Proof of Theorem C.2. A query can return H or B only if its count is strictly greater than a − R, because counts at or below that lower guard return L deterministically. Every Heavy label has a queried witness: either that node or a descendant returned H or B. The witness count is greater than a − R. Hence, its ancestor’s count is greater than a − R. This proves Eq. (121).

Manuscript under review

The proof for Eq. (122) is similar. A query can return L or B only if its count is strictly less than b + R, because counts at or above that upper guard return H deterministically. Every Light node is the queried witness itself or a descendant of a query returning L or B. Its count is at most the witness count, proving Eq. (122). By termination every node receives one of these two labels, according to Lemma B.1.

D

SPARSE IMPLEMENTATION

The dense implementation of Algorithm 3 stores and scans all nodes of the public tree. The sparse implementation instead stores only the union of the root-to-leaf paths of the input records, removing branches that contain no records (namely, nodes with zero weight). When the threshold is at least the deterministic error margin, every zero-count query returns Low and affects only zero-count descendants. Such nodes can therefore be omitted from invocations of GuardedBT, with the omitted nodes treated as Light. We apply the same query and marking rules to the retained nodes, while classification still concerns the entire original public tree. This preserves the Heavy-set distribution and gives O(nh) time and auxiliary space for an input database of size n. Throughout this section, write n := |D| and assume τ ≥ E := w + R,

w = 1/λ,

0 < λ ≤ 1,

R ≥ 1,

with the original thresholds a = τ − w and b = τ + w. Stored subtree.

Define V+ := {u ∈ V : cD (u) ≥ 1} =

[

Pz ,

T+ := T [V+ ],

m := |V+ |,

z∈D

where Pz is the root-to-leaf path of record z. Thus T+ contains exactly the positive-count nodes and the original edges between them. Every ancestor of a positive-count node also has positive count. T+ is a rooted subtree of T with the same root. It retains the original depths and public child order; no paths are contracted. Since each record path contains at most h nodes, X m≤ |Pz | ≤ nh, (123) z∈D

where repeated records are counted separately. Implementation. If D = ∅, return ∅ immediately. Otherwise, build T+ by inserting each record path and increasing the count of every node on that path by one, starting newly stored counts at zero. The resulting counts are exactly the original counts cu (D). Initialize all stored labels to unknown and apply the query and marking steps of Algorithm 3 to the stored nodes. Keep the original public parameters, height h, and depth order, even if T+ is shorter. At each depth, consider only stored nodes, in the restriction of the original public order, and skip those already labeled. Use the same marking routines: MarkUp follows the original ancestor chain, all of which is stored, and MarkDown visits only stored children. Their stopping rules are unchanged. Omitted nodes are implicitly Light. Return only the set of stored nodes labeled Heavy. Proposition D.1 (Dense–sparse equivalence). Under τ ≥ E, for every database D, the sparse implementation and Algorithm 3 admit a coupling in which the sparse query–response sequence is the dense sequence with all zero-count queries deleted, and the final labels agree on all of V , interpreting omitted nodes as Light. Consequently, they have the same Heavy-set distribution and, with the same parameter calibration, the same (ε, δ)-DP guarantee and simultaneous deterministic classification margin E. Proof. For fixed public information, the dense traversal is determined by its responses: starting from unknown labels, each response fixes the marking updates, and the public scan order fixes the next query or termination. Since a − R = τ − E ≥ 0, zero-count queries return Low and mark only zero-count descendants. Upward marking starts from a High or Between response at a positive-count node and stays within V+ . Thus zero-count queries do not affect stored labels, and omitted nodes never become Heavy.

Manuscript under review

Fix D and couple the executions using independent Zu ∼ Lap(1/λ) for u ∈ V+ , with both using Zu whenever the randomized branch at u is reached. Since each node is queried at most once, this preserves the required fresh-noise distributions. We can then make an inductive argument over the stored nodes in their common traversal order. Their labels initially agree, and intervening dense zero-count queries cannot change them. Both executions therefore skip the next stored node or query it with the same count and noise, obtaining the same response. Upward marking follows the same ancestor chain. Downward marking has the same effect on stored nodes, because omitted children have no stored descendants and the stopping tests agree on stored nodes. Hence the stored labels continue to agree, proving the query correspondence. At termination, all omitted nodes are Light in both executions and all stored labels agree. Equality of the Heavy-set distributions transfers the established privacy and utility guarantees. Running time and space. Use the computational conventions in Appendix B.2.1, and assume bounded arity and O(h)-time access to each record path without enumerating the public tree. Inserting all paths builds T+ and its counts in O(nh) time. An ordered depth-first traversal of T+ groups the stored nodes into one list per depth, preserving their inherited public order within each list. Building these lists and generating the original depth order by emitting each depth once together take O(m + h) time and space. Each stored node is considered once and queried at most once. The marking argument of Lemma B.3 gives O(m) total marking work. Including construction, traversal, and output, the total time is O(nh + m + h) and the auxiliary space is O(m + h). Since m ≤ nh, both bounds are O(nh). For n = 0, the algorithm returns immediately in O(1) time and auxiliary space.

E

FROM HEAVY-NODE CLASSIFICATION TO NUMERICAL TREE COUNTING

E.1

Tree Counting through Classification

Let T be a finite public rooted tree with node set V and height h ≥ 3. The private database D consists of leaf records, and cu (D) is the count of node u, as in the main paper. The numerical tree counting problem [25] asks for an estimate e cu of every count. The mRMSEα error criterion. Fix a multiplicative tolerance 0 < α < 1. Following [25, Definition 1.4], we allow an error of αcu (D) and measure only the amount by which the absolute error exceeds this allowance. For an estimator e c = A(D), define the residual error at node u by
ru (D) := |e cu − cu (D)| − αcu (D) + , (x)+ := max{x, 0}. (124) For example, when α = 0.1 and cu (D) = 1000, an absolute error of 130 gives residual error 30. The multiplicative maximum root-mean-square error is p mRMSEα (A; T ) := sup max E[ru (D)2 ], (125) D

u∈V

where the expectation is over the estimator’s randomness and the supremum ranges over all input databases. Thus mRMSEα (A; T ) ≤ B means that E[ru (D)2 ] ≤ B 2 for every database and node. The tolerance α is fixed in advance; it is the root-mean-square residual error that we bound as a function of h. The approach of Ghazi et al. Ghazi et al. [25, Section 4.2] use classification at geometrically spaced thresholds to obtain numerical estimates. Their reduction processes larger thresholds first, assigns estimates to nodes identified as Heavy, and continues on a forest of lighter, disjoint subtrees at smaller thresholds. Classifications place estimated counts between nearby thresholds, giving multiplicative accuracy; counts below the smallest scale are handled by an additive allowance. Combining this reduction with their SVT-based classifier gives an estimator AG satisfying [25, Theorem 4.1] when α, ε, δ are fixed mRMSEα (AG ; T ) = Oα,ε,δ (log h).

(126)

Manuscript under review

Using BetweenCut. Our classifier (i.e., Algorithm 3) has an additive classification margin Oε,δ (log log h) that holds simultaneously for all nodes with probability one and is independent of the database size. To address the tree counting problem, we can use the same geometric-threshold idea, but run increasing thresholds on the original tree. A node receives an estimate when it first becomes Light. Unless this happens in the first round, its preceding Heavy answer gives a lower bound on its count, and its Light answer gives an upper bound. Close threshold spacing makes these bounds differ by only a small multiplicative factor. Nodes that are Light in the first round have small counts and can be estimated by zero. The main issue is to account for all classification calls without introducing dependence on the number of rounds. We assign decreasing privacy budgets whose sums are bounded by ε and δ. Although smaller budgets increase the later classification margins, the thresholds grow faster, through our careful construction. This keeps each margin small relative to its threshold and makes error bound Oα,ε,δ (log log h), an exponential improvement over the error of Oα,ε,δ (log h) in [25]. E.2

Construction

Fix 0 < ε ≤ 1 and 0 < δ < 1/10. A call to BetweenCut below means invoking Algorithm 3 with its local parameters calibrated to the specified privacy budget as in the main paper. A uniform classification bound. Because the privacy parameters will vary across calls, we first obtain a margin bound with one numerical constant valid throughout the parameter range. Let Eh (ε′ , δ ′ ) denote the calibrated deterministic classification margin. The explicit utility bound for Algorithm 3 gives, for every h ≥ 3, 0 < ε′ ≤ 1, and 0 < δ ′ < 1/10,   2 5 L ′ ′ Eh (ε , δ ) ≤ 1 + ′ log ′ 1 + log ′ , L := ⌈log2 (h + 1)⌉ . (127) ε δ δ To simplify this expression, write ℓ := log(1/δ ′ ) > log 10 > 2 and t := log log h > 0. Since the height h ≥ 3 is an h integer, L = 1 + ⌊log2 h⌋ ≤ 1 + log log 2 ≤ 3 log h. Thus log L ≤ log 3 + t, and the two logarithmic factors satisfy 2 3 = ℓ + log 2 ≤ ℓ ′ δ 2 L 1 + log ′ ≤ ℓ + t + 1 + log 3 ≤ 2ℓ + t ≤ 2(ℓ + t). δ log

(128) (129)

Substituting these bounds gives Eh (ε′ , δ ′ ) ≤

16 ℓ(ℓ + t). ε′

(130)

  1 log ′ + log log h . δ

(131)

We therefore fix C := 16 once and define C 1 eh (ε , δ ) := ′ log ′ ε δ ′

′

The derivation proves Eh (ε′ , δ ′ ) ≤ eh (ε′ , δ ′ ) for every allowed h, ε′ , δ ′ —the same C works for all calls. b satisfying, In particular, a call at threshold θ ≥ 0 is (ε′ , δ ′ )-DP and returns an ancestor-closed Heavy set H simultaneously with probability one, b =⇒ cu (D) ≥ θ − eh (ε′ , δ ′ ), u∈H b =⇒ cu (D) < θ + eh (ε′ , δ ′ ). u∈ /H

(132)

These are the lower and upper bounds on counts used by the reduction. Thresholds and privacy budgets. We choose thresholds a factor g > 1 apart and keep each classification margin at most a fraction γ of its threshold. Set γ :=

α , 8

g := 1 +

α , 2

ρ := g −1/2 ,

p := 1 − ρ.

(133)

Manuscript under review

Define the initial threshold by θ1 :=

eh (εp, δp) . γ

(134)

For every potential round j ≥ 1, use θj := θ1 g j−1 ,

εj := εpρj−1 ,

δj := δpρj−1 .

(135)

It suffices to apply basic composition to demonstrate that the overall procedure achieves (ε, δ)-DP. Since 0 < ρ < 1 and p = 1 − ρ, the finite geometric-sum formula gives, for every integer J ≥ 1, J X

εj = ε(1 − ρJ ) ≤ ε

(136)

δj = δ(1 − ρJ ) ≤ δ.

(137)

j=1 J X j=1

Thus, the budgets allocated to the executed calls never exceed ε and δ, even though their number is not fixed in advance. The counting procedure. For rounds j = 1, 2, . . ., run BetweenCut at threshold θj with privacy budget (εj , δj ). Each call starts with fresh labels and randomness on the original tree and database. When a node u is first classified Light, record its round j(u) and permanently assign ( 0, j(u) = 1, e cu := (138) (1 + γ)θj(u) , j(u) ≥ 2. The procedure stops if the root is Light, and then releases the estimate vector. Denote this estimator by Acount . E.3

Guarantee and proof

Theorem E.1 (Numerical tree counting from BetweenCut). For every finite public rooted tree of height h ≥ 3, 0 < α < 1, 0 < ε ≤ 1, and 0 < δ < 1/10, the estimator Acount is (ε, δ)-DP. Its nonnegative estimates satisfy, simultaneously with probability one, |e cu − cu (D)| ≤ max{αcu (D), B}

for every u ∈ V,

(139)

where B := (1 + γ)θ1 = Oα,ε,δ (log log h).

(140)

mRMSEα (Acount ; T ) ≤ B = Oα,ε,δ (log log h).

(141)

Consequently,

Comparison with Ghazi et al. [25]. Compared with mRMSEα (AG ; T ) = Oα,ε,δ (log h) from [25], Eq. (141) is an exponential improvement in h. Ghazi et al. [25] also considers a threshold-based utility notion with a public accuracy threshold τu for each node u, requiring |e cu − cu (D)| ≤ α max{cu (D), τu }. Our Theorem E.1 directly }, without requiring such node-specific thresholds. gives |e cu − cu (D)| ≤ α max{cu (D), B α Proof of Theorem E.1. Classification accuracy at every round. The function eh defined in Eq. (131) upper-bounds the calibrated deterministic margin. It suffices to show that eh (εj , δj ) ≤ γθj . Write A := log

1 , δp

t := log log h.

(142)

Manuscript under review

Since 0 < p < 1 and δ < 1/10, we have A > log 10 > 2. Also, t > 0 because h ≥ 3. Fix a round j ≥ 1 and set x := (j − 1) log

1 ≥ 0. ρ

(143)

The construction schedule in Eq. (135) and ρ = g −1/2 give εj = εpe−x ,

log

1 = A + x, δj

θj = θ1 e2x .

(144)

Using the definition of eh , we obtain eh (εj , δj ) =

C C (A + x)(A + x + t) = ex (A + x)(A + x + t). −x εpe εp

(145)

The choice θ1 = eh (εp, δp)/γ yields γθj = γθ1 e2x = eh (εp, δp)e2x =

C 2x e A(A + t). εp

(146)

Since t > 1, 1 + y < ey for any y, and A > 2, we have C

x

eh (εj , δj ) εp e (A + x)(A + x + t) = C 2x γθj εp e A(A + t) A+xA+x+t A A+t    x x = e−x 1 + 1+ A A+t  2 x ≤ e−x 1 + A −x 2x/A ≤e e ≤ 1. = e−x

(147) (148) (149) (150) (151) (152)

Consequently, every call’s deterministic classification margin is at most eh (εj , δj ) ≤ γθj , with probability 1. Termination. Fix a finite database D and write n := |D|. By our construction, (1 − γ)θj is increasing in each round by a factor of (1 + α2 ). Hence, JD := min{j ≥ 1 : (1 − γ)θj > n}

(153)

is finite. On the probability-one event above, if round JD is reached, then n < (1 − γ)θJD ≤ θJD − eh (εJD , δJD ), according to what we just proved—eh (εj , δj ) ≤ γθj . Namely, the root will be classified as Light at round JD . The procedure therefore stops after at most JD calls. Simultaneous numerical accuracy. Fix a database D and work on the probability-one event where all classification guarantees hold. For each node u, let j(u) be its first Light round, which exists by the above termination argument. If j(u) = 1, then |e cu − cu (D)| = cu (D) < θ1 + eh (ε1 , δ1 ) ≤ (1 + γ)θ1 = B

(154)

Otherwise, write j := j(u) ≥ 2 for readability. The node was Heavy in round j − 1 and is Light in round j. Therefore, cu (D) ≥ θj−1 − eh (εj−1 , δj−1 ) ≥ (1 − γ)θj−1

(Heavy in round j − 1)

(155)

(margin bound in round j − 1),

(156)

Manuscript under review

cu (D) < θj + eh (εj , δj ) ≤ (1 + γ)θj =: e cu

(Light in round j)

(157)

(margin bound in round j).

(158)

The lower bound is positive because γ < 1 and θj−1 > 0. We obtain e cu (1 + γ)θj g(1 + γ) (1 + α/2)(1 + α/8) α(4 − 3α) ≤ = = =1+α− ≤ 1 + α. cu (D) (1 − γ)θj−1 1−γ 1 − α/8 16(1 − α/8)

(159)

Together with e cu ≥ cu (D), this implies |e cu − cu (D)| = e cu − cu (D) ≤ αcu (D).

(160)

Combining the two cases proves Eq. (139) simultaneously for all nodes. Expanding the definition of B gives B = (1 + γ)θ1 =

(1 + γ)C A A + log log h . γεp

(161)

For fixed α, ε, δ, the quantities γ, p, and A are fixed and independent of both h and D. Consequently, B = Oα,ε,δ (log log h), with no database-size dependence. Therefore, for every database and node
ru (D) = |e cu − cu (D)| − αcu (D) +
≤ max{B, αcu (D)} − αcu (D) +
= B − αcu (D) +

by Eq. (139)

≤ B. Thus mRMSEα (Acount ; T ) = sup max D

u∈V

p

E[ru (D)2 ] ≤ B = Oα,ε,δ (log log h).

(162)

Fixed tree height. The assumption h ≥ 3 concerns the height of the original public tree T , not the number of levels still awaiting classification. Every counting round invokes Algorithm 3 on the same tree with the same height parameter h. Thus the assumption h ≥ 3 remains valid throughout. Each call starts with fresh Heavy/Light labels, while previously assigned numerical estimates remain unchanged. Increasing thresholds. The classifier in [25] depends on an upper bound M on the root count through the ratio M/τ . Their decreasing-threshold reduction controls this ratio by continuing on lighter subtrees, whose root-count bounds decrease along with the thresholds [25]. In contrast, BetweenCut’s classification margin does not depend on a root-count bound, so we can repeatedly classify the original tree without this subtree refinement. Increasing thresholds let us start at a public, database-size-independent accuracy scale and stop when the root becomes Light, without first estimating an upper bound on the database size. This direction simplifies the construction.

Related documents

• BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height#1234442
• Local Node Differential Privacy#1186420
• Differentially-Private Decision Trees and Provable Robustness to Data Poisoning#1105885
• FairLint-DL: An IDE-Native Tool for Fairness Debugging of Deep Learning Software#1110686
• FairLint-DL: An IDE-Native Tool for Fairness Debugging of Deep Learning Software#919474