Differentially Private Random Forests for Regression and Classification
Shorya Consul 1 , Sinead Williamson 2, 3
1

Department of Electrical and Computer Engineering, The University of Texas at Austin
2
Department of Statistics and Data Science, The University of Texas at Austin
3
Department of Information, Risk and Operations Management, The University of Texas at Austin
shoryaconsul@utexas.edu, sinead.williamson@mccombs.utexas.edu

Abstract
Random forests are a popular method for classification andregression due to their versatility. However, this flexibility cancome at the cost of user privacy, since training random forests
requires multiple data queries, often on small, identifiable subsets of the training data. Privatizing these queries typicallycomes at a high utility cost, in large part because we are privatizing queries on small subsets of the data, which are easily
corrupted by added noise. In this paper, we propose DiPriMe
forests, a novel tree-based ensemble method for regression
and classification problems, that ensures differential privacy
while maintaining high utility. We construct trees based on a
privatized version of the median value of attributes, obtained
via the exponential mechanism. The use of the noisy medianencourages balanced leaf nodes. This avoids the need to query
very small subsets of the data, and ensures that the noise added
to the parameter estimate at each leaf is not overly large. The
resulting algorithm, which is appropriate for real or categorical covariates, exhibits high utility while ensuring differential
privacy.

1

Introduction

The prevalence of data has been one of the key drivers oftechnological innovation in the last decade. The abundance of
data, allied with ever-increasing computing power, has driven
the rapid development of sophisticated machine learningtechniques, many of which have achieved hitherto unseen
levels of performance. Data collection today is pervasive,across applications and devices. This has resulted in data
privacy becoming a matter of public concern.
It has long been known that querying even aggregated or
perturbed data can lead to leakage of private information(Dinur and Nissim 2003), motivating the development of
databases and algorithms that mitigate such privacy breaches.
Differential privacy (Dwork et al. 2006) is one of the most rigorous ways of analysing and ameliorating such privacy risks.
If an algorithm is -differentially private, it means we canapply a multiplicative bound to the worst-case leakage of anindividual’s private information. Many algorithms have beendeveloped with this goal in mind, such as differentially private variants of linear regression (Kifer, Smith, and Thakurta
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

2012), k-means clustering (Huang and Liu 2018; Su et al.
2016) and expectation maximization (Park et al. 2016).
Such privacy guarantees come at a cost—modifying analgorithm to be -differentially private typically involves
adding noise to any queries made by that algorithm, which
will tend to negatively affect the algorithm’s performance.
This cost will tend to be higher when privatizing more complex algorithms that require multiple queries of the data, suchas non-linear regression and classification algorithms (Smithet al. 2018; Abadi et al. 2016). One such family of non-linear
regression and classification algorithms, that allows for flexible modeling but involves multiple queries, is the class oftree-based methods, such as random forests and their variants(Breiman 2001; Geurts, Ernst, and Wehenkel 2006).
Tree-based ensemble methods make minimal assumptions
on the parametric forms of relationships within the data,and can be easily applied to a mixture of continuous andcategorical covariates. However, building trees that capture
the appropriate structure requires many queries of the data,
making them challenging to privatize. Further, since the trees
partition the data into arbitrarily small subsets, the noise thatmust be added to each subset to ensure differential privacy
can quickly swamp the signal.
We propose differentially private median (DiPriMe)
forests, a novel, differentially private machine learning algorithm for nonlinear regression and classification with potentially sensitive data. Rather than directly privatize queries inan existing random forest framework, we start by modifying
the underlying non-private trees to be robust to the additionof noise. We note that the negative impact of added noise
is greatest when there are few data points associated withcertain leaf nodes, especially in regression. Splitting basedon the median value at a node avoids such a scenario. The
low sensitivity of the median to perturbations of the datamean that, even after privatizing the median query, we stillachieve balanced leaf node occupancy, and therefore avoid
overwhelming the signal at each leaf with noise.
The DiPriMe algorithm offers several advantages overexisting private random forests. Because the underlying nonprivate algorithm is designed with privatization in mind, they
achieve impressive predictive performance across a range oftasks by minimizing the negative effects of added noise. The
fact that their construction explicitly depends on the distribution of the covariates facilitates the derivation of utility

bounds. Such bounds are challenging to derive for algorithms
without this form of dependence, since the utility is highly
dependent on the data distribution; as a result, this is to ourknowledge the first utility result for a fully differentially private tree-based algorithm. And finally, unlike most existing
approaches, they can easily deal with continuous or categorical covariates, without excessive additional privacy cost.
We begin by reviewing the concept of differential privacy,
and discussing related approaches, in Sec. 2, before introducing DiPriMe forests in Sec. 3. We provide theoretical andempirical guarantees on both the privacy and the utility of ourapproach. In Sec. 4 we show that our method outperforms existing differentially private tree-based algorithms on a variety
of classification and regression tasks.

2
2.1

Preliminaries

Differential Privacy

Differential privacy (DP, Dwork 2008) is a rigorous framework for limiting the amount of information that can be inferred from an individual’s inclusion in a database. Formally,a randomized mechanism F satisfies -differential privacy
for all datasets D1 and D2 differing on at most one element
and all S ⊆ Range(F) if
Pr[F(D1 ) ∈ S] ≤ e Pr[F(D2 ) ∈ S] .

(1)

This implies that the inclusion of an individual’s data canchange the probability of any given outcome by at most amultiplicative factor of e . A lower value of  provides astronger privacy guarantee, as it limits the effect the omissionof a data point can have on the statistic.
Typically, the mechanism F is a randomized form of somedeterministic query f . To determine the degree of randomization required to satisfy (1), we need to know the global
sensitivity ∆(f ) = maxD1 ,D2 kf (D1 ) − f (D2 )k1 , whichtells us the maximum change in the outcome of the query f
due to changing a single data point. Armed with the global
sensitivity, we can use a number of approaches to ensure-DP; we outline the two most common mechanisms below.
• Laplace mechanism Starting with a deterministic queryf : D → Rd , where D is the space of possible data sets,
we can construct an -DP query-answering mechanism that
adds appropriately scaled Laplace noise, so that (Dwork,
Roth et al. 2014)
F(X) =f (X) + (Y1 , Y2 , . . . , Yd )iid

Yi ∼ Laplace(0, ∆i (f )/),(2)

where ∆i (f ) denotes the sensitivity of the i-th coordinateof the output. Note how the noise added scales as 1/
– increased privacy directly translates to increased noise
variance.
• Exponential mechanism The Laplace mechanism assumes that our query returns values in Rd . A more generally applicable privacy mechanism is the exponential
mechanism (McSherry and Talwar 2007), which allows
us to pick an outcome r ∈ R, where R is some arbitrary
space. We define a scoring function q : D × R → R
with global sensitivity ∆(q), and a base measure µ on

R. For any dataset D ∈ D, selecting an outcome r withprobability
Pr[F(D) = r] ∝ eq(D,r)/2∆(q) × µ(r)(3)
ensures -differential privacy. Clearly, the scoring function
q should be constructed such that preferred outputs are
assigned higher scores.
Often, algorithms will involve multiple queries, requiring us to account for the overall differential privacy of thecomposite algorithm. We can make use of two composition
theorems to obtain the overall privacy level (McSherry 2009):• Sequential composition tells us that a sequence of differentially private queries maintains differential privacy. Let
Fi each provide i -differential
Pprivacy. Then sequentiallyevaluating Fi (X) provides ( i i )−differential privacy.
• Parallel composition tells us that the privacy guarantee
for a set of queries on disjoint subsets of data is only
limited by the worst-case privacy guarantee for any of thequeries. If Fi each provide i -differential privacy, and Di
are arbitrary disjoint subsets of the dataset D, then thesequence of Fi (X ∩ Di ) provides (maxi i )−differential
privacy.

2.2

Differentially private tree-based methods

There have been several methods proposed in recent literature
to learn ensembles of decision trees for classification in adifferentially private manner (although, to the best of ourknowledge, this paper is the first to consider regression);
Fletcher and Islam (2019) provide an excellent survey. As wediscuss in Sec. 3, most algorithms use the Laplace mechanism
to privatize leaf node counts, and differ on the method of tree
construction.
Most algorithms can be seen as privatized versions of random forests (Breiman 2001), which greedily choose optimal
splits at internal nodes, and store sufficient statistics at theleaf nodes. One way of determining the splits in a decision
tree is to choose the split with lowest entropy. Friedman andSchuster (2010) privatizes this by noising the node counts
using the Laplace mechanism, and then selecting an attributeto split on using the exponential mechanism with entropy as
the score. Sub-trees are iteratively constructed for each valueof the attribute thus chosen. This method is built upon in the
differentially private random forest (DP-RF) algorithm (Patiland Singh 2014), which builds multiple private trees usingbootstrapped samples and considers multiple splitting metics.
The trees are grown iteratively until they reach a specified
maximum depth or the node is pure, i.e., contains instancesof a single class. The differentially private decision forest(DP-DF) (Fletcher and Islam 2015) uses local sensitivity toprivatize the leaf-node sufficient statistics, and incorporates a
pruning method. The differentially private greedy decision
forest (Xin et al. 2019) partitions the data into disjoint subsets, to reduce the overall privacy cost. (Rana, Gupta, andVenkatesh 2015) proposes a relaxation on the DP-RF approach so that the ensemble of trees preserves the variance,
instead of the entire distribution of the data. This relaxation
enables their method to achieve better performance, and allows for numerical covariates, at the expense of losing any
claim to -differential privacy.

The above algorithms all assume categorical covariates,
and at each node, there is one child node per category of
the selected attribute. Continuous covariates must therefore
be discretized in some manner; if this is done in a datadependent manner, we must expend privacy budget to do so(Kotsiantis and Kanellopoulos 2006). Friedman and Schuster(2010) do propose a method of splitting continuous covariates via the exponential mechanism, but this significantly
increases the privacy budget, as discussed in Fletcher andIslam (2015).
An alternative approach is to bypass the greedy splitting mechanism altogether, generating and selecting splits
at random similar to the extremely randomized trees algorithm (Geurts, Ernst, and Wehenkel 2006). Jagannathan, Pillaipakkamnatt, and Wright (2009) and Bojarski et al. (2014)
both use random splits to build their trees, allowing the entire privacy budget to be devoted to privatizing the leaf node
sufficient statistics, and allowing categorical or continuous
covariates.

3

Differentially private median forests

When designing differentially private algorithms, we wish tominimize the negative impact of privatization on the overall
utility. In a tree-based setting, we need to privatize two things:
determining the locations of splits, and estimating the node
parameters. We consider these in turn.
Estimating leaf node parameters In a tree-based model,
we estimate appropriate sufficient statistics at each leaf node—
typically the mean in a regression setting, and the classcounts in a classification context. In both cases, we can use
the Laplace mechanism to provide appropriately privatizedstatistics—the approach taken by almost all existing differentially private tree algorithms. To render the count queryat a given node ` -DP, we can add Laplace(0, 1/` ) noise toeach class count. In the regression context, if we have Ni data
points associated with the ith leaf node, and we have boundedtarget Y ≤ B, we can achieve ` -DP at a single leaf nodeby adding Laplace(0, 2B/Ni ` ) noise to the mean. Since theleaf nodes are disjoint, the set of all leaf-node queries is also` -DP, following the parallel composition theorem.
The utility of the resulting estimate at the ith leaf depends
on two things: the value of ` , and the number Ni of data
points associated with the leaf node. Small values of ` , andsmall values of Ni , both lead to the Laplace noise dominating
the signal of interest. Therefore, to improve the utility of ourestimates, we must either increase the per-leaf-node privacy
budget, or increase the number of data points Ni . In particular,
we wish to avoid the situation where the privacy budget ` isless than 1/Ni , which implies that the expected magnitudeof the Laplace noise is greater than that of the signal.
Obtaining non-leaf node splits In most non-private random forests, the value at which a non-leaf node is split isdetermined by maximizing some score, such as the Gini
index. We can privatize this by randomizing the selection procedure, an approach taken by Friedman and Schuster (2010),
Patil and Singh (2014) and Fletcher and Islam (2015). In

these works, the authors score attribute-specific candidate
splits with one child node for each category of that attribute,and then selects an attribute according to the exponential
mechanism.
Unfortunately, the design decisions made in these private
algorithms are at odds with the goal of maximizing per-leaf
node utility. In each case, a subtree is learned for each category of the chosen categorical covariate (or each unique valueof the discretized continuous covariate), leading to more lowoccupancy nodes than would be expected in a binary tree.
This in turn leads to more low-occupancy leaf nodes where
the added Laplace noise overwhelms the signal from the data.
In addition to harming the leaf node utility, low-occupancy
sub-trees are a major hindrance to good regression trees.
Typically, the sensitivity of the scoring function is inversely
proportional to the node count, meaning that the selectionof attribute to split on will also be very noisy; sufficiently
low counts would result in this selection being no better thanrandom. Private versions of Extremely Random Trees, suchas those proposed by Bojarski et al. (2014) and Jagannathan,
Pillaipakkamnatt, and Wright (2009), avoid diverting budget
from the leaf nodes by picking their splits entirely at random.
In practice, this can sometimes improve performance, if thebenefit of increased leaf node privacy budget ` outweighs
the benefit of chasing the optimal tree structure. However,
the relatively large per-leaf node ` is unfortunately pairedwith highly variable leaf node occupancy Ni , since splits are
selected without consideration of the data distribution.

3.1

Differentially Private Median (DiPriMe)
Forests

As discussed above, generating all possible splits for a given
attribute, or selecting a split at random, can lead to lowoccupancy nodes. In a non-private context, there is little
downside to such behavior. But once we begin seeking differential privacy, low-occupancy nodes increase noise in thetree-selection process and lead to poor leaf-node utility. We
therefore design an algorithm centered on creating balanced
leaf nodes.
In a non-private context, if an attribute is continuous, we
could achieve optimal leaf node balance by choosing to split
on the median value. In a private context, we can use a differentially private estimate of the median. Let Di = (Xi , Yi )be a numeric dataset, to be split on attribute a with bounded
range Ra = [aL , aU ] ⊂ R. We score potential splits r ∈ Ra
according to q(r) = ||Xi,a ∩[aL , r)|−|Xi,a ∩[r, aU ]||, notingthat q(r) is piecewise constant between the data points. The
sensitivity of q(r) is 1, so we can achieve s -DP by selecting
a bin with probabilityn os
P r(r) ∝ exp − |Xi,a ∩ [aL , r)| − |Xi,a ∩ [r, aU ]| .
2
(4)
If attributes are categorical, in a non-private context we
can achieve optimal leaf node balance by calculating q(C) =||C| − |Xi \ C|| for all possible splits (C, Xi \ C) that areconsistent with values of the selected attribute, and selecting
the maximizing split. The sensitivity of q(C) is 1, so we canAlgorithm 1 Differentially Private Median (DiPriMe) Tree
1: class D IPRIME T REE (i, imax , k) . Initialize empty tree2:
if i ≤ imax then
3:
d←i
4:
dmax ← imax
5:
K←k
6:
end if
7: end class8:
9: procedure F IT T REE(T ,D,A,RA ,B,,ρ)10:
N = |D|11:s ← 2dρ, a ← 2dρ, ` ← (1 − ρ)
max
max
12:
if T.d = T.dmax or A = ∅ then13:
Store privatized mean or class counts in T .
14:return T
15:
end if16:
T.ind, T.val ← F IND S PLIT(D,A,RA ,B, s , T.K)
R
17:
RL
A ,RA ,AL ,AR ,DL ,DR ← S PLIT R ANGE (RA ,A,

T.ind,T.val)

18:
19:
TR ← D IPRIME T REE(T.d + 1, T.dmax ,T.K)
20:
F IT T REE(TR ,DR ,AR ,RAR ,B,,ρ)21:
TL ← D IPRIME T REE(T.d + 1, T.dmax ,T.K)
22:
F IT T REE(TL ,DL ,AL ,RAL ,B,,ρ)23: end procedure24:
25: procedure F IND S PLIT(D,A,RA ,B,s ,K)26:
N = |D|27:
AS ← size-min{K, |A|} subset of attributes A.
28:
for all a ∈ AS do
29:
if a is categorical then30:
Draw subset Ca ⊂ Ra according to (5)31:else. a is a continuous attribute
32:
Draw split location r ∈ Ra according to (4)33:Ca = Ra ∩ (−∞, r)
34:
end if
35:
M SEa ← mean squared error for chosen split36:
end for37:
Pick attribute ã according to (6).
38:
return ã, Cã
39: end procedure40:
41: procedure S PLIT R ANGE(RA ,A, a,Ca ,D)R
42:
RL
A , RA ← RA
43:
AL , AR ← A
44:
RaL ← Ca , RaR ← Ra \ Ca45:
if RaL cannot be further split (single category) then46:
AL ← AL \ a47:
end if48:
if RaR cannot be further split (single category) then49:
AR ← AR \ a50:
end if51:
DL = {(x, y) ∈ D : x ∈ RL
A}
R
L
52:
D =D\D
R
53:
return RL
A ,RA ,AL ,AR ,DL ,DR
54: end procedure

achieve s -DP by selecting a split (C, Xi \C) with probability
o
n 
s
(5)
P r(C, Xi \ C) ∝ exp − |C| − |Xi \ C| .
2
Having selected a candidate split for each attribute, wepick an attribute to split on using the exponential mechanism,
using the negative mean squared error as the scoring function.
The sensitivity of the mean-squared error is 4B 2 /Ni , where
the target value lies in [−B, B]. So, for a single split, we canachieve a -differential privacy by splitting on attribute ã withprobability a Ni MSE(ã),(6)
P r(ã) ∝ exp −8B 2
where M SE(ã) is the mean squared error associated withthat split.
We note that, unlike existing differentially private tree
algorithms, the non-private version of our algorithm does
not correspond to a commonly used tree model. Mediansplits are not typically used in random forests. Such splits are
deterministic given the covariates, and agnostic to the target
variable, thereby leading to higher errors. While Breiman(2004) considers median splits for lower branches of trees asa simplifying assumption when obtaining consistency results,
he categorically states that the use of median splits will resultin higher error rates than greedily learned splits. Indeed, inSec. 4 we see that non-private median forests underperform
random forests and extremely random trees in general.
Median splits are, however, successful in a private context.
Having well-balanced splits offers little advantage in a nonprivate setting, but is critical to ensuring good performance ina differentially private setting. We find, in Sec. 4, that the resulting robustness to the detrimental impacts of privatization
outweighs the benefits of using more sophisticated splitting
method. Further, the privatization of the median eliminates
the deterministic nature of the median splits, allowing better
performance when the optimal split is far from the median.
Privacy analysis We can calculate the overall privacy budget of our algorithm using the parallel and sequential composition theorems. Since the candidate splits are on separate
attributes, the total privacy cost of selecting a differentiallyprivate median for all attributes is s , making the total privacy cost of selecting private medians for each attribute thenselecting an attribute s + a . Since the splits at a given depth
are performed on disjoint subsets of the data, the total privacy
cost of building the tree is therefore dmax (s + a ) (where
dmax is the maximum tree depth), and the total cost including
privatizing the leaf nodes is dmax (s + a ) + ` .
As is common in tree-based algorithms, rather than use
a single tree, we construct an ensemble of NT trees. We
partition our data into NT subsets, and learn a DiPriMetree on each subset. Partitioning has two benefits. First, itmeans that the overall privacy budget for the forest is still
dmax (s +a )+` , due to parallel composition. Second, it encourages variation between the tree structures, allowing better
exploration of the space. If we choose not to partition our data,
the overall privacy budget would NT (dmax (s + a ) + ` ).

Algorithm 2 Differentially Private Median (DiPriMe) Forest
1: class D IPRIME F OREST (nT , dmax , k)2:NT ← nT , T ← {}3:
for i ← 1, nT do
4:T ← D IPRIME T REE(0, dmax , k)5:
T ←T ∪T6:
end for
7: end class8:
9: procedure F IT F OREST(F ,D,A,RA ,B,,ρ)10:
NT = F.NT
11:
Partition D = (X, Y ) into {Di }i=1,...,NT
12:
i←0
13:
for all T ∈ F.T do
14:
T ← F IT T REE(T ,Di ,A,RA ,B,,ρ)
15:
i←i+1
16:
end for17: end procedure

We split the overall privacy budget  between the threequery-specific budgets ` , s and a . We set ` = (1 − ρ),and s = a = ρ/2dmax , for some ρ ∈ (0, 1).
We summarize the process of constructing a single
DiPriMe tree in Algorithm 1. Algorithm 2 describes how
we can combine multiple DiPriMe trees into a forest. We use
the following notation in Algorithms 1 and 2: D = (X, Y )refers to the set of data points to which the tree T is being
fit. X denotes the input features and Y denotes the corresponding target values. A refers to the set of attributes thatthe tree can split on with RA = {Ra : a ∈ A} denoting
the corresponding range or categories. B is the upper boundon the absolute value of the target, i.e., |yi | ≤ B,  is thetotal privacy budget for the tree, and ρ is the fraction of theprivacy budget allocated to determine the median split. We
include code in the supplement, and will make this public
upon publication.

3.2

Utility analysis

In general, the utility of a random forest—and the change
in utility due to privatizing that random forest—will depend
heavily on the data distribution. Particularly, the loss of utility
due to adding noise to a greedy split selection mechanism will
depend on how well alternative splits capture variation in thedata. This likely explains why, while utility results have beenobtained for differentially private trees with random splits(Bojarski et al. 2014), to the best of our knowledge there
are no existing utility guarantees for differentially private
random forests with data-dependent splits.
The utility of the full DiPriMe tree algorithm, as describedin Algorithm 1, also depends on the data, due to the mechanism for selecting the attribute on which to split. However, if
we simplify our assumption to select the attribute at random,
then we can provide bounds on the utility, relative to a nonprivate version of the same algorithm. In practice, we foundthat using the exponential mechanism to select the attributegave greater utility than random selection on the datasets weconsidered.

In our analysis, we consider the regression task, and assume all covariates are continuous and that the dataset can bepartitioned into equal-occupancy leaf nodes, i.e. N = c · 2dfor some nonnegative integer c. Both assumptions can easily
be relaxed. Let Obji the the sum of squared errors at
Pthe ithleaf node of the non-private median tree, and Obj = i Obji
be the overall loss. Then we can bound the utility loss due toprivatizing the non-leaf node splits.
Theorem 1. Let Obj∗i be the loss under a median tree where
the splits have been privatized following (4), but where thesufficient statistics at the leaf nodes are not privatized. LetNi∗ be the number of data points at the ith leaf node of thistree, and let c be the number of data points at the leaf nodeof the non-private tree. Then, for any t > 0,|Obji − Obj∗i | ≤ 4B 2 t with probability min(ζ1 , ζ2 )where |Y | ≤ B andγζ1 = 2 2
s t
n
o
2 2
ζ2 = max 2e−s t /4γ , 2e−s βt/2−2dwith γ = 8(1−23Corollary 1.1.

)

p
, β 2 = 21 ( 1 − 2/e + 1).

|Obj − Obj∗ | ≤ 2d+2 B 2 t with probability min(ζ1 , ζ2 )We can then bound the utility loss due to privatizing both
non-leaf and leaf node queries.
g total loss due to both privatizing median
Theorem 2. Let Obj
gsplitsand privatizingleaf node means. Then, E[Obj]−Obj
≤

2
2B
2
d+2
B t + 2 (N/2d −t) 2
with probability at least 1 − ζ,`

where ζ = 21−d min(ζ1 , ζ2 ).
Proofs of Theorems 1 and 2, and empirical evidence
demonstrating the tightness of the bound in Theorem 1, areprovided in the supplement.

4

Experiments

To consider the utility of our proposed algorithm, we look at
the estimate qualities obtained across a range of regression
and classification tasks, comparing against state-of-the-art
private and non-private algorithms. For classification, we
compare against two privatized versions of random forests(DP-DF (Fletcher and Islam 2015) and DP-RF (Patil andSingh 2014)), and a privatized version of extremely random
trees (DP-ERT, (Bojarski et al. 2014)). There has been little
focus on regression in the literature, limiting our comparisons
for the regression task. We modified DP-ERT to estimate themean, rather than counts, at each leaf. It is not straightforward
to modify DP-DF and DP-RF in this manner, however, as
their split selection mechanisms are based on the assumptionof categorical targets. We created a regression analogue of
DP-RF, in which splits are scored by mean squared error
and means were stored instead of class counts. The hyperparameters (NT , dmax ) were chosen based on the dataset
size to avoid low-occupancy nodes; we do not optimize these
hyperparameters as this would increase the privacy cost.

4.1

Regression

We consider three datasets to benchmark our method’s regression performance: the Parkinson’s telemonitoring dataset(N = 5875) and the Appliance Energy Prediction dataset(N = 19735) from the UCI Machine Learning Repository(Dua and Graff 2017), and the Flight Delay dataset used by
Jagannathan, Pillaipakkamnatt, and Wright (2009). The UCI
datasets contain a mixture of categorical and numeric features, while the Flight Delay dataset contains only numericfeatures. For the purposes of computational complexity, we
sampled 800,000 data instances from the Flight Delay dataset
for this experiment. We bin the numeric features into 5 binsfor DP-RF as it requires categorical features. For each dataset,
we scaled the target variable to lie in [0, 1], took 90% of thedata as the training set and computed the mean squared error(MSE) over the test set. The results shown in Table 1 are for
NT = 10 trees in each ensemble, with the number of covariate splits to consider set to K = 10 for all but the DP-ERT.
The private methods were run for  = 10 and ρ = 0.5. The
maximum depth was 5 for the two UCI datasets and 10 for
the Flight Delay dataset.

RF
ERTMedianDP-RF (2014)
DP-ERT
DiPriMe

Parkinson’s

Appliances

Flight Delay−2−3

2.11 × 10−4
2.16 × 10−4
2.30 × 10−4
1.40 × 10−2
2.34 × 10−4
2.37 × 10−4

2.04 × 10
2.98 × 10−2
2.54 × 10−2
2.65 × 10−1
3.41 × 10−2
3.10 × 10−2

8.49 × 10
9.11 × 10−3
9.28 × 10−3
1.97 × 10−1
1.01 × 10−2
9.88 × 10−3

the sensitivity of the mean at the leaf nodes as there are likely
to be fewer data instances in deeper nodes. Increasing thenumber of trees in the ensemble results in a similar trade-off,as shown in Figure 1(b); the number of data points to learn
each tree is inversely related to the number of trees in theensemble. So, while more trees are expected to generally
reduce the mean squared error, each tree has less data to learn
from.

4.2

RF
ERT
MedianDP-DF (2015)
DP-RF (2014)
DP-ERT
DiPriMe

Table 1: MSEs obtained with DiPriMe, and with non-private
and private tree-based ensemble methods for regression,
NT = 10, K = 10,  = 10, ρ = 0.5.
We see in Table 1 that DiPriMe clearly outperforms DPERT as a private tree-based ensemble learner for regression,even in datasets where the non-private median tree underperforms the non-private ERT algorithm. As hypothesized, we
achieve better performance in the private setting by modifying our base algorithm to mitigate the impact of additional
noise, even though those modifications are not helpful in the
non-private setting: the benefit of additional robustness tonoise outweighs the utility loss due to median splits. The
effect of low-occupancy nodes is evidenced by the terrible
performance of the regression analogue of DP-RF – it consistent gives an MSE at least an order of magnitude worse thanany other method.
In Figure 1, we see how performance varies with privacy
budget , the number of trees in the forest NT , and the maximum tree depth dmax , on the Appliances dataset. We haveomitted DP-RF from these figures as it vastly underperforms
the other methods. We see that for most parameter settings,
DiPriMe outperforms DP-ERT. Figure 1(a) illustrates theinherent trade-off between learning deeper trees and utility.
Deeper trees give a finer approximation of the data, demonstrated by the decreasing MSE of the non-private methods.
However, this deteriorates the utility of DiPriMe by (a) reducing the privacy budget for the split at each node (b) increasing

Classification

We use three datasets from the UCI Machine Learning Repository (Dua and Graff 2017)—the Banknote Authentication(N = 1372), Credit Card Default (N = 30000) and WallFollowing Robot Navigation (N = 5456) datasets—to compare the performance of our proposed algorithm to DP-DF,
DP-RF, and DP-ERT. The Credit Card Default data contains
both numeric and categorical features, while the other two
datasets contain only numeric features. As DP-DF and DP-RF
require categorical features, we bin the numeric features into
5 bins. We chose this data-agnostic discretization procedure
to avoid leaking privacy. While alternative data-dependent
discretization algorithms have been proposed in the literature(Patil and Singh 2014), such methods must be privatized andhence incur additional privacy budget.
Banknote

Credit Card

Robot

0.964
0.949
0.920
0.551
0.804
0.642
0.935

0.823
0.788
0.785
0.785
0.795
0.664
0.785

0.987
0.916
0.877
0.595
0.662
0.620
0.788

Table 2: Comparison of DiPriMe with various non-private
and private tree-based ensemble methods for classification,
NT = 10, K = 5, dmax = 5,  = 2, ρ = 0.5.
Table 2 shows the classification errors obtained by eachmethod. In the non-private setting, median forests underperform both extremely random trees and random forests.
However, as we introduce privacy, we see that the performance of DiPriMe far exceeds that of DP-ERT, DP-RF and
DP-DF. This can likely be attributed to (a) DiPriMe’s capability to directly utilize and split on numeric features without theneed for prior discretization (b) the robustness of the median
construction to privatization, due to its preference for balanced node splits. As we see in Figure 2, while DiPrime has anotable loss of accuracy compared with the non-private algorithms for small values of , we get comparable performanceas  increases. By contrast, DP-ERT and DP-DF continue tounderperform even as  increases, and DP-RF requires muchlarger  to attain comparable performance.

4.3

Balancedness of splits

Our hypothesis for the superior performance of DiPriMe
is that it discourages low occupancy nodes, which in turn
reduces the impact of the injected noise on selecting optimal

(a)  = 10, NT = 10(b)  = 10, dmax = 8(c) dmax = 8, NT = 10

Figure 1: Mean squared error of DiPriMe, Random Forest, Extremely Randomized Trees and DP-ERT at various values of ,
dmax and NT on the Appliances Energy prediction dataset.

Figure 2: Performance of DiPriMe, Random Forest, Extremely Randomized Trees, DP-ERT and DP-DF at various
values of  for the Banknote Authentication data (dmax = 5,
NT = 10, ρ = 0.5).

splits and estimating leaf-node parameters. The claim that
DiPriMe trees discourage low-occupancy nodes is borne out
by a closer inspection of the ensembles of trees learned on
the Robot data. Figure 3 shows that DP-ERT, DP-RF and
DP-DF have very heavy-tailed distributions over the per-leaf
node occupancy, with the majority of nodes having very
low occupancy. This is exacerbated in the trees generated
by DP-RF and DP-DF, where each split generates multiple
child nodes, one for each category of the selected attribute,compared with the binary splits used by DiPriMe and DPERT: DP-DF and DP-RF generated an average of 290 nodes
and 381 nodes respectively, compared with 63 for DiPriMe
and DP-ERT. By contrast, we see that the DiPriME trees havea much larger proportion of higher occupancy nodes.
We can explore this phenomenon by comparing splits generated by DiPriMe, with those generated by DP-ERT on the
Banknote Authentication dataset. Figure 4 shows that the
splits generated by DP-ERT have highly imbalanced occupancy with high probability. By contrast, the median-based
splits used by DiPriMe tend to assign similar occupancies toboth child nodes.

Figure 3: Histogram of fraction of instances residing at eachleaf node for Robot data.

Figure 4: Fraction of instances assigned to left child, on
Banknote data.

5

Discussion

We have presented a new, differentially private, tree-based
method for regression and classification, based on random
forests with median splits. Our algorithm can easily be used
for either regression or classification, and works with both categorical and numeric covariates. Moreover, we have demonstrated, both theoretically and empirically, that our algorithm
obtains impressive utility to competing methods, while maintaining the same level of differential privacy.

References
Abadi, M.; Chu, A.; Goodfellow, I.; McMahan, H. B.;
Mironov, I.; Talwar, K.; and Zhang, L. 2016. Deep learningwith differential privacy. In Proceedings of the 2016 ACM
SIGSAC Conference on Computer and Communications Security, 308–318.
Bagdasaryan, E.; Poursaeed, O.; and Shmatikov, V. 2019.
Differential Privacy Has Disparate Impact on Model Accuracy. In Advances in Neural Information Processing Systems
32, 15479–15488.
Blum, A.; Dwork, C.; McSherry, F.; and Nissim, K. 2005.
Practical privacy: the SuLQ framework. In Proceedings of thetwenty-fourth ACM SIGMOD-SIGACT-SIGART symposiumon Principles of database systems, 128–138.
Bojarski, M.; Choromanska, A.; Choromanski, K.; and LeCun, Y. 2014. Differentially-and non-differentially-private
random decision trees. arXiv preprint arXiv:1410.6973 .
Breiman, L. 2001. Random forests. Machine learning 45(1):
5–32.

Geurts, P.; Ernst, D.; and Wehenkel, L. 2006. Extremely
randomized trees. Machine learning 63(1): 3–42.
Hensman, J.; Fusi, N.; and Lawrence, N. D. 2013. Gaussian
processes for big data. arXiv preprint arXiv:1309.6835 .
Huang, Z.; and Liu, J. 2018. Optimal differentially private
algorithms for k-means clustering. In Proceedings of the 37th
ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems, 395–408.
Jagannathan, G.; Pillaipakkamnatt, K.; and Wright, R. N.
2009. A practical differentially private random decision treeclassifier. In 2009 IEEE International Conference on Data
Mining Workshops, 114–121. IEEE.
Kifer, D.; Smith, A.; and Thakurta, A. 2012. Private convex
empirical risk minimization and high-dimensional regression.
In Conference on Learning Theory, 25–1.
Kotsiantis, S.; and Kanellopoulos, D. 2006. Discretization
techniques: A recent survey. GESTS International Transactions on Computer Science and Engineering 32(1): 47–58.

Breiman, L. 2004. Consistency for a simple model of random forests. Technical Report 670, Statistics Department,
University of California at Berkeley.

Lakshminarayanan, B.; Roy, D. M.; and Teh, Y. W. 2016.
Mondrian forests for large-scale regression when uncertainty
matters. In Artificial Intelligence and Statistics, 1478–1487.

Cummings, R.; Gupta, V.; Kimpara, D.; and Morgenstern, J.
2019. On the compatibility of privacy and fairness. In Adjunct Publication of the 27th Conference on User Modeling,
Adaptation and Personalization, 309–315.

Liu, J.; and Talwar, K. 2019. Private selection from private
candidates. In Proceedings of the 51st Annual ACM SIGACT
Symposium on Theory of Computing, 298–309.

Dinur, I.; and Nissim, K. 2003. Revealing information while
preserving privacy. In Proceedings of the twenty-second
ACM SIGMOD-SIGACT-SIGART symposium on Principles
of database systems, 202–210.

McSherry, F.; and Talwar, K. 2007. Mechanism design via
differential privacy. In 48th Annual IEEE Symposium on
Foundations of Computer Science (FOCS’07), 94–103. IEEE.

Dua, D.; and Graff, C. 2017. UCI Machine Learning Repository. URL http://archive.ics.uci.edu/ml.

McSherry, F. D. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In
Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, 19–30.

Dwork, C. 2008. Differential privacy: A survey of results.
In International conference on theory and applications ofmodels of computation, 1–19. Springer.

Mozannar, H.; Ohannessian, M. I.; and Srebro, N. 2020. Fair
Learning with Private Demographic Data. arXiv preprint
arXiv:2002.11651 .

Dwork, C.; and Lei, J. 2009. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM
symposium on Theory of computing, 371–380.

Park, M.; Foulds, J.; Chaudhuri, K.; and Welling, M. 2016.
DP-EM: Differentially private expectation maximization.
arXiv preprint arXiv:1605.06995 .

Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. 2006.
Calibrating noise to sensitivity in private data analysis. In
Theory of cryptography conference, 265–284. Springer.

Patil, A.; and Singh, S. 2014. Differential private random forest. In 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2623–
2630. IEEE.

Dwork, C.; Roth, A.; et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends R in
Theoretical Computer Science 9(3–4): 211–407.
Fletcher, S.; and Islam, M. Z. 2015. A Differentially Private
Decision Forest. In AusDM, 99–108.

Rana, S.; Gupta, S. K.; and Venkatesh, S. 2015. Differentially private random forest with high utility. In 2015 IEEE
International Conference on Data Mining, 955–960. IEEE.

Fletcher, S.; and Islam, M. Z. 2019. Decision tree classification with differential privacy: A survey. ACM Computing
Surveys (CSUR) 52(4): 1–33.

Roig-Solvas, B.; and Sznaier, M. 2020. Novel Tractable
Bounds on the Lambert Function with Application
to Maximum Determinant Problems.
arXiv preprint
arXiv:2004.01115 .

Friedman, A.; and Schuster, A. 2010. Data mining withdifferential privacy. In Proceedings of the 16th ACM SIGKDD
international conference on Knowledge discovery and data
mining, 493–502.

Smith, M.; Álvarez, M.; Zwiessele, M.; and Lawrence, N. D.
2018. Differentially private regression with Gaussian processes. In International Conference on Artificial Intelligenceand Statistics, 1195–1203.

Su, D.; Cao, J.; Li, N.; Bertino, E.; and Jin, H. 2016. Differentially private k-means clustering. In Proceedings of thesixth ACM conference on data and application security andprivacy, 26–37.
Voigt, P.; and Von dem Bussche, A. 2017. The eu generaldata protection regulation (gdpr). A Practical Guide, 1st Ed.,
Cham: Springer International Publishing .
Wainwright, M. J. 2019. High-dimensional statistics: A nonasymptotic viewpoint, volume 48. Cambridge University
Press.
Xin, B.; Yang, W.; Wang, S.; and Huang, L. 2019. Differentially Private Greedy Decision Forest. In ICASSP 2019 2019 IEEE International Conference on Acoustics, Speechand Signal Processing (ICASSP), 2672–2676.

Appendix
We derive sensitivities used in the main paper in Section A and provide proofs for the theorems in Section B. Algorithm 3
provides additional implementation details. Section C provides some additional experimental results
We shall use the following constants in our analysis. We assume all the target values are bounded, i.e., |yi | ≤ B

ASensitivity analysis

We assume have a set A with data points {y1 , y2 , . . . , yN } such that |yi | ≤ B. A|j denotes the set of all data points besides yj ,i.e., A|j = {y1 , y2 , ...yj−1 , yj+1 , ..., yN }.

A.1

Mean
N

1 X
µA =
yi
N i=1
µA|j =

N
X
1
yi
N −1
i=1,i6=j

N
X
yj
1
yi +
N (N − 1)NµA − µA|j 1 = −i=1,i6=j12B≤N∴ ∆(µA ) = 2B
N

A.2

Mean squared error

The mean squared error is equivalent to the variance. Denoting the variance by σ 2 ,
N

1
1 X 2
2
y − 2
σA
=
N i=1 i
N
2
σA|j
=

1
N −1

N
X

!2
yi

i=1



N
X

yi2 −

i=1,i6=j1
(N − 1)2

N
X

2
yi 

i=1,i6=jUsing the triangle inequality repeatedly, we get

2
N
N
X
X
2N
−
1
1
2
2

σA
− σA|j≤ −yi2 + 2yi N (N − 1)
N (N − 1)21
i=1,i6=ji=1,i6=j1

+N − 1 2 2yj 
y − 2
N2 j
N

N
X

i=1,i6=jyi 1

N −1 22(N − 1) 2
N −1 2
≤
B
+
B
+
B
2
N2
N
N2
1
1
1
≤

2
∴ ∆(σA) = 4B
N

2

4B 2
N

B
B.1

Proofs

Theorem 1

In a depth-d median tree, there are c = N/2d data points at the ith leaf node. W,l.o.g. let these be A = {y1 , y2 , . . . , yc }. Then,the value of our objective function isc
XObji =(yi − ȳ1 )2
i=1
2
= cσA

Assuming there be a subset C ⊂ A of M − δ data points at node i with private median splits, our noisy objective value is
Obj∗i = (c − δ)σC2
Sensitivity of objective W.l.o.g., we take excluded points to be {y1 , y2 , . . . yδ }. We assume all the points are bounded, i.e.,|yi | ≤ B.

2
cσA
=

c
X

1
yi2 −
c

i=1
c
X

(c − δ)σB2 =

c
X

yi2 −

i=δ+1

!2
yi

i=1

!2

c
X

1
c−δ

yi

i=δ+1

Hence,2cσA− (c − δ)σB2 1 =δc(c − δ)
+

2
c

c
X
i=δ+1
δ
X
i=1

!
yi

!2
yi

+

i=δ+1

1
yi2 −

i=1

1
c
X

δ
X

c

δ
X
i=1

!2
yi
1

!
yi
1

δ(c − δ) 2
2δ(c − δ) 2≤
B + δB 2 +Bcc≤ 4B 2 δ

Returning to the utility analysis, we see that noising the median by δ leads to a maximum change of 4B 2 δ in the objective
value at node i.
Extending this to tree of depth d, if Ni∗ denotes the number of data points at the ith leaf node, then|Ni∗ − c| ≤ t =⇒ |Obj∗i − Obji | ≤ 4B 2 t
Corollary 1.1 follows from applying the above result over all the 2d leaf nodes of a depth-d tree.

B.2

Theorem 2

We consider a depth-d tree. Let δ1 be the noise added at the first level, δ2 be the noise added at the second level, and so on. In thenoised tree, at the leaf node (depth d), we will therefore have
Ni∗ =

=

n
N X δj+, δj ∼ Laplace(0, 1/s )2d j=1 2d−jdN X+∆j , ∆j ∼ Laplace(0, 2j−d /s )2d i=jdata points.
P

Pn
d
j=1 ∆j is unbounded, so we bound the tail probability instead, i.e., find an upper bound on P
j=1 ∆j ≥ t . We shall use
two approaches to arrive at this bound: (a) sub-exponential random variables (b) Chebyshev’s inequality.

Using sub-exponential random variablesM∆j (t) = E[et∆j ]
1
1
2j−n
,
|t|
<
,
b
=
i
1 − b2j t2
bj
s
2 2
1
≤ e2bj t , ∀|t| ≤αj=This implies that ∆j ∈ SE(4b2j , αi ) where SE() denotes the class of sub-exponential random variables. To find αj , we need tofind the range of t for which
2 21≤ e2bj t22
1 − bj t


1
−2
2 2
=⇒ bj t ≤ W0+12e2
where W0 (x) is the principal branch of the Lambert W function. For ease of analysis, we use the lower bound on W0 (x) from
(Roig-Solvas and Sznaier 2020):√
W0 (x) ≥ ex + 1 − 1 for 1/e ≤ x ≤ 0
to get1 p( 1 − 2/e + 1)
2b2j
bj
1 p
=⇒ αj = , β 2 = ( 1 − 2/e + 1) ≈ 0.757
β
2
t2 ≤

−2d

Let γ = 8(1−23). Then,

2γ
2s
2
2βγ
ν∗
=
α∗
s
We can now bound the tail probabilities (Wainwright 2019) as
 (

2
2
d
X
2e−t /(2ν∗ ) ,∆i ≥ t ≤P
2e−t/(2α∗ )
j=1
(
2 2
2e−s t /(4γ) ,=2e−s βt/2
ν∗2 =

ν2

0 ≤ t ≤ α∗∗
ν2t > α∗∗
0 ≤ t ≤ 2βγ
st > 2βγsUsing Chebyshev’s inequality A simpler method of bounding the tail probabilities is to use Chebyshev’s inequality. This
gives
P



d
n
V ar
X
j=1 ∆jP∆j ≥ t ≤
t2
j=1
=

γ
2s t2This is tighter than the sub-exponential bound for
s
s



!
√
γ
1
1
2 −W0 − , −2 −W−1 −
t∈
s
8
8
√
γ
(0.76, 3.61)∈
sFigure 5: Tail probabilities of Ni∗ − 2Nd for d = 10 are estimated from the histogram. The red line depicts the tighter of the twobounds derived above; the blue line depicts the empirical estimate.
There is a clear dependence on 1/s in the bounds which intuitively makes sense as the noise scales by that factor.We observethat the derived bound on tail probablity of Ni∗ − 2Nd holds empirically from 5 with the bound becoming tighter for larger t.
Let us now use the above bound on tail probabilities to bound the effect of noising the mean of the ith leaf node. We haveg = Obj∗ + Ni∗ ρ2i
Objii
where ρi ∼ Laplace(0, 2B/Ni∗ ` ).
The conditional expectation of the perturbation due to this noise is∗ 2
E[Ni ρi |Ñi ] =8B 2
Ni∗ 2`2

8B
Note that Ni∗ ≥ N/2d − t =⇒ E[Ni∗ ρ2i |Ni∗ ] ≤ 2 (N/2d −t) .
`

8B 2
As the distribution of Ni∗ is symmetric about N/2d , we have E[Ni∗ ρ2i |Ni∗ ] ≤ 2 (N/2d −t) with probability 1 − ζi , where`N∗
P Ni − 2d ≥ t ≤ 2ζi .

P
2d+3 R2
Applying the union bound on the leaf nodes, and setting ζi = 21−d ζ, we get i E[Ni∗ ρ2i |Ni∗ ] ≤ 2 (N/2d −t) with probability`
1 − ζi . The result of Theorem 2 follows from combining this with that of Corollary 1.1.

C(a)  = 10, NT = 10

Additional results(b)  = 10, dmax = 8(c) dmax = 8, NT = 10

Figure 6: Mean squared error of DiPriMe without partitioning data, Random Forest, Extremely Randomized Trees and DP-ERT
at various values of , dmax and NT on the Appliances Energy prediction dataset.
Figure 6 displays the results for DiPriMe without paritioning the data for each tree. The trends are similar to those seen in Figure
1. An observation of note is that the optimal maximum depth for trees fit on all the data is higher than that fit on disjoint subsets

of data. This is congruent with the intuition that low-occupancy nodes are noised more heavily. Hence, trees fitted to more data
can be grown deeper before suffering from a similar loss of utility. This line of reasoning leads us to believe that learning an
ensemble of DiPriME trees on disjoint subsets of data will be a more powerful learner with larger amounts of training data. We
see a similar trend for the task of classification (see Figure 7).

Figure 7: Performance of DiPriMe without partitioning data, Random Forest, Extremely Randomized Trees, DP-ERT and DP-DF
at various values of  for the Banknote Authentication data (dmax = 5, NT = 10, ρ = 0.5).
Figure 8 once again exhibits improved performance with larger privacy budgets. It also shows that increasing NT improves
performance only to a certain limit before the increased noise reduces the utility of the DiPriMe trees. The key insight here is theimportance of the hyperparameter ρ for good performance; large values of ρ leaves less privacy budget for storing the means,
resulting in deterioration in the MSE. This effect is more pronounced at smaller values of  as the noise scales as 1/. Note thatdata-driven hyperparameter selection has to be done privately as well (Liu and Talwar 2019). This would require additional
privacy budget, i.e., a larger .

(a) NT = 10, dmax = 8, K = 10,
data partitioned(b) dmax = 8,  = 10, ρ = 0.5,
data partitioned(c) NT = 10, dmax = 8, K = 10,
data not partitioned(d) dmax = 8,  = 10, ρ = 0.5,
data not partitioned

Figure 8: Mean squared error of DiPriMe on the Appliances Energy Prediction dataset for various hyperparameter settings