Decision Tree for Locally Private Estimation with Public Data
Authors: Yuheng Ma
Han Zhang
Yuchao Cai
Hanfang Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: Local differential privacy
non-parametric regression
decision tree
public data
TL;DR: Use a small amount of public data to enhance the performance of locally private regression.

Abstract: We propose conducting locally differentially private (LDP) estimation with the aid of a small amount of public data to enhance the performance of private estimation. Specifically, we introduce an efficient algorithm called Locally differentially Private Decision Tree (LPDT) for LDP regression. We first use the public data to grow a decision tree partition and then fit an estimator according to the partition privately.  From a theoretical perspective, we show that LPDT is $\varepsilon$-LDP and has a mini-max optimal convergence rate under a mild assumption of similarity between public and private data, whereas the lower bound of the convergence rate of LPDT without public data is strictly slower, which implies that the public data helps to improve the convergence rates of LDP estimation. We conduct experiments on both synthetic and real-world data to demonstrate the superior performance of LPDT compared with other state-of-the-art LDP regression methods. Moreover, we show that LPDT remains effective despite considerable disparities between public and private data.

Decision Tree for Locally Private Estimation with Public Data
Yuheng Ma'
Han Zhang' Yuchao Cai²
Hanfang Yang 13+
School of Statistics, Renmin University of China
Faculty of Electrical Engineering, Mathematics and Computer Science, University Twente Center for Applied Statisties, Renmin University of China Cyma, hanzhang0816 hyang) (rru. @ruc. edu. cn
y. cai aaieutwente.r.
Abstract
We propose conducting locally differentially private (LDP) estimation with the aid of a small amount of public data to enhance the performance of private estimation. Specifically, we introduce efficient algorithm called Locally differentially Private Decision Tree (LPDT) for LDP regression. We first use the public data to grow a decision tree partition and then fit estimator according to the partition privately. From theoretical perspective, we show that LPDT is s-LDP and has a minimax optimal convergence rate under a mild assumption similarity between public and private data, whereas the lower bound of the convergence rate of LPDT without public data strictly slower. which implies that the public data helps to improve the convergence rates of LDP estimation. We conduct experiments on both synthetic and real-world data to demonstrate the superior performance of LPDT compared with other state-of-the-art LDP regression methods. Moreover, we show that LPDT remains effective despite considerable disparities between public and private data.
Introduction
Differential privacy (DP) 25 is widely-used technique to protect sensitive information, like in medical trials (20 recommendation systems [49] and census data sharing [3]. Local differential
privacy (LDP) 38 24), a variation of DP, has gained particular attention, especially among industry experts [27 35). Unlike DP, LDP assumes data is privatized before being sent to central collector.
However, LDP models need more data to be accurate compared to DP (24) and many common techniques in data analysis such as standardization [10) and tree partition
(59 are harder with LDP. This brings challenges to tasks such as density density estimation 23 mean estimation (24]. and
Gaussian estimation (36).
Fortunately, in some scenarios, private estimation performance can enhanced with an additional public dataset [ 77. The public dataset can be either in-distribution, consisting of data from users who agree to share their personal information [6]. or out-of-distribution, such as data from another source (34). From central DP perspective,
increasing amount of research has focused on leveraging public data facilitate private learning, where public data mainly serves two purposes. On one hand, the knowledge learned from public data is implicitly transferred into the private model. Empirical investigations have demonstrated the effectiveness of pretraining on public data and fine-tuning privately sensitive data 63
61]. By gradient pre-conditioning with subspace computed by public data, [65 62 37 managed to reduce the required amount of noise in
differentially private gradient descent and accelerate its convergence. Through unlabeled public data, fed knowledge privately into student models. On the other hand, on public data, we can
45 46
*Corresponiigg author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

conduct procedures that would be infeasible without access to the raw private data. For example, [T] used parameters computed by public data to standardize private data, which can augment the sample complexity of private mean estimation. Recently, [56] employed unlabeled public data to estimate the leading eigenvalue of the covariance matrix, resulting in an improved sample complexity for generalized linear models with non-interactive local differential privacy.
The paper focuses on the problem of non-parametric regression with LDP. While regression has been extensively studied in the central setting [50, I [4], the LDP case remains rarely explored. notable reason is that most gradient- based methods [50] are prohibited. In order to protect privacy, each data holder needs to compute the gradient of parameters locally, which requires large amount of memory, computing power, and communication capacity on the terminal machine [52]. 29 proposed to impose Laplace noise on the data directly to provide privacy. However, this method known to converge slowly [88] and suffer from the curse of dimensionality. More recently, p [3] investigated histogram-based approaches. Though theoretically optimal, histograms may perform poorly in practice, especially when the dimension of feature space is large. Thus, both methods proposed in [ 33 face challenges when applied to real-world problems.
Under such background, using the idea of borrowing public data information, we propose an LDP non-parametric regression algorithm called the Locally differentially Private Decision Tree (LPDT) that achieves both optimal convergence rate and superior empirical performance. We first create a tree partition on the public dataset using the proposed max-edge rule. According to the partition, each data holder encodes the private data and releases the encoding which is processed using the proposed privacy mechanism. Finally, the curator aggregates the information in each partition cell and outputs a decision tree estimator. LPDT is advantageous from least two perspectives: (i) LPDT integrates both benefits to leverage public data. It enables adaptive partitioning procedures which can eliminate some redundant cells and can transfer information from public data to private estimation through the tree partition. (ii) It inherits the merit of the decision tree model, such as interpretability, efficiency, stability, extensiveness to multiple feature types, and resistance to the curse of dimensionality.
We summarize our contributions. (i) For the first time, we propose to use public data in locally differentially private non- aar-aaametrrc regression. (ii) We propose novel LDP regression algorithm called the locally differentially private decision tree that achieves theoretical optimality while main- taining satisfying practical performance. (iii) Under mild assumptions on the similarity between the distribution of public and private data, we establish the optimal convergence rate of LPDT, whereas the supremum of excess risk of LPDT without public fails to converge to zero. This demonstrates the theoretical advantage of incorporating public data. (iv) In experiments, we compare LPDT with other existing non-parametric LDP regression methods using both synthetic and real-world datasets. Our results demonstrate the overwhelming performance of LPDT, which illustrates the empirical improvement brought by public data. Moreover, we show that LPDT performs well even in the presence of significant disparities between public and private data.
2 Methodology
This section is dedicated to the methodology of LPDT. In Section 2.1 preliminaries related to regression problems, followed by a recap of the definition of local differential privacy. Next, we introduce our hybrid privacy mechanism for general partition-based based estimation
we first present notations and
in Section 2.2 In Section 2.3] we propose our partition rule. Finally, in Section 2.4 we provide a comprehensive description of LPDT.
2.1 Preliminaries
Notations
For any vector x. let x. denote the i-th element of x. Recall that for 1 I p < co, the + + 1//p, Throughout this paper,
nor-norm of x = (xr fa.......0 xd)) is defined by ||a/||p := (|x-1 we use the notation on S bn and an 2 bn to denote that there exist positive constant and e' such that an I cb,, and a, 2 d'b,, for all n E N. In addition, we denote a, x b, if an S bn and b, S an. Let V 6 = max(a, b) and A = min(a, b). Besides, for any set A C Rd, the diameter of A is defined by (A) == suP || - x' 1l2. Let the standard Laplace random variable have the continuous probability density function p(x) -e- for J E IR.
2

---

Regression is to predict the value of an unobserved output variable Y based on the observed input vari- able X, based on a dataset D := {X,, Yi).................. (X,, }, consisting of i.i.d. observations drawn from an unknown probability measure on X y [0, 1 --M, M. The density function of P denoted as 8. In addition, we have a public dataset Drub == {(XT"), ypm .... (X Yz drawn from distribution Q on X' x y with sample size ny- Its density function denoted as q.
is legitimate to consider the least square loss L: X' x y x y + o0) defined by L(x, y, f(x)) == fx))² 2 for our target of regression. Then, for measurable decision function f f +y, the risk is defined by Rf, == Jxxy L(x, y. (x)) dF y). The Bayes risk, which is the smallest possible risk with respect to P and L, is given by Ri, == inf (R), X + measurable).
The function that achieves the Bayes risk is called Bayes function, namely, (=)x == B(Y|X= =).
Definition 2.1 (Local Differential Privacy). Given data ((x,, Y)) each (X; Y.) is mapped to a piece of privatized information 8; which is random variable on S. Let (S)) be the o-field on S. 8; is drawn conditional on (X;; Y,) via the distribution R. (S X; z, Y2 = y) for S oSS). Then the mechanism R. provides E-local differential privacy (s-LDP) if
( X, Y; v) sup (S X; Y. - E and x, x E X, n.y' E
This formulation of local privacy widely adopted [3 9 In contrast to central DP where the likelihood ratio is taken with respect to some statistics of all data, LDP requires individuals to guarantee their own privacy by considering the likelihood ratio with respect to each (X,, V.). Once the view 8 is provided, no further processing can reduce the deniability about taking a value (v, v) since any outcome s nearly as likely to have come from some other initial value (x' 3
2.2 Privacy mechanism for free partition
This section focuses on the hybrid privacy mechanism for general tree partitions. We first introduce the standard regression tree and then present our privacy mechanism based on the random response and Laplacian mechanism.
For index set I. let HAy be any tree partition of X with UjEzA, X' and A, n = 0. i * j. For any x E X, let the cell containing x be A(x). A population decision tree regressor with partition ı is defined
SA ('('') JA dP(x))
A,) [x()== - 1ir =
(I)
JEZ
Here, we let 0/0 = by definition. To get a empirical estimator given the data set ((X1, (X,,
we estimate the numerator and the denominator of (1) respectively. To
estimate the denominator, each sample (X,, Yi) contributes one-hot vector U, {0, 1) where the j-th element of U4 1(x; Ay}. Then an estimation of SA, dP(x) is n Em_ U. which is the number of samples in Aj divided by Analogously, an estimation of SA, f (x)dP(xx) is
n D Y. U/. Combining the pieces, a decision tree regressor is defined as
fx(x) = Σ1< EAIEEA11 2i=1 Y. Y U
(2)
EL_ U
JET
In other words, f (x) estimates f(x) by the average of the responses in the cell A(x). In the non- private setting, each data holder prepares U/ and Y; according to the partition π and sends it the curator. Then the curator aggregates the transmission following (
To protect the privacy of each data, propose to estimate the numerator and denominator of the population regression tree using a privatized method. Specifically, given U/, we independently sample 0y using the random response technique
57
U U
1
with probability e²/1
0/
1tee/4
1+ee/4
(3)
with probability 74
140774
3

---

Since ER 1/4 Ei= 06]
2h/+_1 Di=0% we take 5 Ei= 0/ as the estimator of ef/
SA (z)x). To privatize - Y we use the standard Laplace mechanism 25] Namely, we let
4M C
Y,
where & are i.i.d. standard Laplace random variables. Similarly, 2-/4_1 Ei=1 Y, 0 can be used
e//4
estimate JA (x))))))). Then using the privatized information (Ü,, Y,), 1,-.. - n,, we define the locally differentially private decision tree regressor as
( = 1xE Σ Y. Y. 09 E U
(S)
JEZ
Compared to which used the Laplacian mechanism to protect both U3 and Y,, our mechanism 3 considers the fact that U is a binary vector. When [Z] is large, (3) can be more efficient than the Laplace mechanism which has heavier-tailed distribution 123
2.3 Max-edge partition with variance reduction
While our privacy mechanism applies to any tree partition, can be challenging to use general partitions such as the original CART (M] for theoretical analysis. Following the heuristic of (15), we propose a new splitting rule called the max-edge partition rule using the variance reduction criterion. This rule amenable to theoretical analysis and can also achieve satisfactory practical performance. Given public dataset ((Xpub, ypuu) )
the partition rule is stated as follows:
Let Aj = 1] be the initial rectangular cell and == {[4))ez, be the initialized cell partition. Io = {1} stands for the initialized index set. In addition, let p E N represent the maximum depth of the tree and let nı represent the minimum sample size in each leaf. These parameters are fixed beforehand by the user and possibly depend on n.
Suppose have obtained partition T of X' after i i- steps of the recursion. Let n, 0. In the i-th step, for each A T--1. E I4-1, suppose is xb=llag be]. We choose the edge to be split among the longest edges. The index set of longest edges is defined as
M -
= {8:
lbx axl
max lbe ael, 1,...... d 6m 1, dd
Assume split along the f-th dimension for E Mi_,, A/_1 is then partitioned into left sub-cell A (f) and right sub-cell (1
(f) along the midpoint of the chosen dimension,
where 1/-1 (f) {or x x/ < ertby } and (12)(0) A/-//A/_,00 (e). Then the
dimension to be split is chosen using the variance reduction criterion:
S (XPrb))
arg min REM
(6)
1=1
Once l is selected, We count the number of samples in the sub-cells Σ 1(X,"bb A7 k 0, 1. If either of the cells contains fewer than samples, the splitting is
pruned and we ,; = n, U A! Otherwise, let n; = m. U (47-) (1), (0))
The complete process is presented in Algorithm 2 in the appendix. For each grid, the partition rule selects the midpoint of the longest edges that achieves the largest variance reduction. This procedure continues until there not enough samples contained in any leaf node, the depth of the tree reaches its limit.
2.4 Decision Tree with local differential privacy
With these preparations, we finally present the full procedure of LPDT in Algorithm

---

Algorithm 1: Locally differentially private decision tree (LPDT)
Input:
Private data D {X,, Y public data D {(XTu) y-Pud) 1
Parameters: Depth s, minimum leaf sample size ny.
Curator create tree partition following max-edge rule in Section 2.3 public data Druh
Data holders of D create privatized information (3) and (4) according to n.
Curator aggregates the privatized information and compute /DP by (5).
Output: The LPDT estimator /DP.
3 Theoretical results
In this section, we present our theoretical results and related comments. We first provide the E-LDP guarantee of LPDT in Section[..] In Section 3.2) we establish the optimal convergence rate of LPDT with max-edge partition and the excess risk lower bound of LPDT without public data, Finally, we discuss the complexity of LPDT in Section 3.3
3.1 Privacy guarantee for LPDT
Theorem 3.1. Let ग = [Ajheet be any partition of X with UjEIAj X and A; A, -
Then the privacy mechanism R (Ü, Y)X,Y) defined in 33 and (4) is E-LDP. Consequently. the LPDT
estimator foP in Algorithm 7 is E-LDP.
3.2 Convergence rate of LPDT
We first present the necessary assumptions the distribution P and Q-
Assumption 3.2. Let (0, 1]. Assume the true regression function I X + R is a-Hölder continuous, i.e. there exists a constant er > such that for all #1, 22 E X. ( s ez || x2 || Also, assume that the density function of P is bounded, i.c. p(z) for some > 0.
Assumption 3.3. We assume that there exists some constant > 1 such that for all cells A E
there holds -1 SA dx) S SA dP (x) S T SA (2).
Assumption 3.2 is a standard condition widely used in non- con-paraettric statistics. Assumption 3.3 depicts the similarity between the distribution of public data and private data. It is also mild assumption and requires only the probabilities in each cell under P and Qx to be similar. When p(x) and q(x:) are both bounded from O, this assumption is satisfied. Alternatively, it suffices to require that p(x)//(x)) is upper and lower bounded.
Theorem 3.4. Let IPP be the LPDT estimator in Algorithm ! Suppose Assumption 3.2 and 3.3 hold. Then, for ny 2 2a 22, if we set logne? nE? and n, ng/2",, 2", there holds
logn ng²
R RL,P(SPP) RĪ. S
5/n² with respect to p @ Q"v R" where R the joint distribution of privacy mechanisms in and
with probability 2/2
Note that only require ny I_ which means the sample size of public data can be much smaller than private data. As illustrated in [33], the minimax convergence rate over Hölder function space is (n(e - ) att, indicating that LPDT attains optimal rate when a/(a + d) < 1/3. In the case a/ (a + d) > 1/3, or cquivalently 2a > LPDT achieves fast yet sub-optimal convergence rate n J. Note that 2a > d only when d = and a Z 1/2, which rarely occurs. The next statement shows that LPDT fails without public data.
Theorem 3.5. Let IDP be the LPDT estimator in Algorithm Aad P be the class of distributions 0 i.e. there no public data, for any choice of s, Th, and e,
satisfying Assumption 3.2 For ng there holds
sup PEP
[E [RL,((DP)) RT.P) 2 1.
5

---

Under the same hypothesis function space, the supremum of excess risk of LPDT does not even converge without public data. Together with Theorem (34 this shows that the prior information contained in public data can greatly enhance the quality of the private estimation.
We compare our results with those of others. LPDT converges faster than deconvolution- based method
29] whose rate is n
2n [28]. As for histogram- methods, [9] achieves the optimal rate only
when the density function is lower bounded, which is strong condition. To avoid the condition, [33 derived an ad hoc estimator by adding a regularization to the marginal density estimation. LPDT takes another approach to avoid the condition. It does not apply any regularization or truncation on the estimator in each cell. Instead, as long as Assumption 3.3 holds, the low-density regions can be identified and treated with larger cells automatically by the parameter ny. As a sacrifice, the large cells restrict the approximation ability of LPDT and the convergence rate is no more than n n-1/3, In addition, our theoretical results hold in the sense of "with high probability", which is more closely related to practical needs than "in expectation" addressed in [9 (3).
Besides these advantages, we also discuss the benefit of public data for removing the range parameter
10 9.
Consider the example from 3 where the convergence rate is given by
When
the set X' x [a], b0] is unknown, it becomes necessary to create histogram partition over x x ]w.. introducing an additional factor of 2d However, with publicly available data, we can approximate the range of the j-th dimension using ai min, X and bi max, X Subsequently, we can perform min-mat min-max scaling on each data point from - then train LPDT [0= 1]. Any x: that falls outside the range xy=1 [0, 1] is predicted as 0. We demonstrate that by this approach, Theorem 3.4 holds with a probability of at least d/n See derivations in Section C.6 in the appendix.
[a), bi] to map it into - 1]. and
3.3 Complexity analysis
We demonstrate that LPDT is efficient method. We first consider the average computation complexity of LPDT. The training stage consists of two parts. The partition procedure takes O( (snndd) time and the computation of 55 takes Oss)) time. From the proof of Theorem 3.4 we know that
4 2 x (ns* / log n)) 22422 Thus the training stage complexity is around On log ne² + +ng log ne*).
Since each prediction of the decision tree takes ((s) time, the test time for each test instance is around (log ne?). ). As for storage complexity, since LPDT only requires the storage of the tree structure
and the prediction value at each node, the space complexity of LPDT is O((n= /logn) "=r ). In short, LPDT is an efficient method with a small number of parameters.
Table Comparison of complexities of LDP regression methods.
LPDT
PHIST 9
DECONV 29
Training Time Complexity Testing Time Complexity
Oln log ne² + n.d niglogne' ne") Ollo (((n=2/ / log n) m.m.
O (nd ne²) Olog ne")
O(nd)
Space Complexity
O( / log n)
O(nd)
We compare the complexities of LPDT with other LDP regression methods in Table ! Notably, 29 is inefficient due to its unacceptable test and space complexity. Also, the dominant term of training complexity of [9] is O(nd ne²). When d is large, we can choose a small ny such that LPDT yields a strictly lower complexity than [9]. In addition, although [9] enjoys the same order of space complexity as LPDT, the memory of histogram -based methods suffers from the curse of dimensionality in practice. Since the storage of O(h d) values is required, even h = 1/2 requires allocating an array of size 2d, which is problematic for large d. In contrast, LPDT can resist the curse of dimensionality by only splitting along the relevant features and keeping a small number of nodes.
Experiments
In the experiments, we first validate our theoretical findings with synthetic data in Section 4.1 Then, in Section 4.2 we show the superior performance of LPDT on real-world datasets with identically distributed public data. In Section 4.3 we apply LPDT to Chicago taxi data to show that LPDT

---

performs well even with considerable differences between private and public data. Also, we analyze the influence of the distribution shift between private and public data on LPDT.
Splitting rule Note that most tree methods design their partition rules based the information gained from the data. To boost the performance of LPDT, we also incorporate the variance reduction scheme from the original CART [1I] the tree construction. We denote the LPDT estimator using the max-edge partition rule with variance reduction in Section 2.3 as LPDT-M and denote the estimator
using the standard variance reduction rule in [1] as LPDT-V. Since Theorem 3.1 holds for any partition, LPDT-V is also E-LDP.
Experiment setup We choose the privacy budget E [0.5, 8], covering commonly seen magnitudes of privacy budgets from low to high privacy regimes. We compare LPDT-M and LPDT-V with the following methods: (i) Private Histogram (PHIST) 19. (ii) Adjusted Private Histogram (APHIST)
[3 (iii) Deconvolution Kernel (DECONV) 291 Introduction to the methods and all implementation details are presented in Appendix D.I We employ 5-fold cross-validation for parameter selection, and techniques for tuning parameters under LDP are discussed in Section D.2
The evaluation metric
is the mean squared error (MSE).
4.1 Synthetic experiments
Necessity of public data To demonstrate intuitively why public data is essential for LPDT, we first visualize its estimation on a synthetic model, == =in(16.X) c where X ~ (0.5,, 0.025) and ~~ N (0, 1). this case, the marginal distribution is highly imbalanced with the majority of samples located in the middle part of [0, 1] and a few samples the sides. For e 8, we fit two LPDT models: one with 500 public data and 7,000 private data, and another with 8,000 private data.
As shown in Figure (aa) without pub- lic data, LPDT struggles with the imbalanced marginal. The grids on the side produce unstable predictions since only a few samples fall into them. As a result, LPDT tends to decrease depth to stabilize its esti- mation. This leads to underfitting in the middle so that the predicted curve fails to capture the variation of the ground truth. In contrast, with the aid of public data, LPDT solves the issue as shown in Figure [(b) For the mid- dle zone where samples are abundant, LPDT creates small grids to enlarge approximation capacity. Meanwhile, it prunes the grids the sides to ensure stability. Even with fewer private data, the MSE of LPDT is reduced from 1.19 to 1.08 thanks to the additional public data. In summary. the experiment provides empirical evidence supporting the theoretical findings in Theorems 3.4 and 3.5 which highlight the necessity of public data for the effective performance of LPDT.
Samples
Sameles
fixt
LFDT
Yas-
Yos
-1.0-
1.0-
8.0
(a) Without public data
(b) With public data
Figure 1: The estimated regression curve of LPDT with and without public data. 1,000 samples are displayed in green.
Parameter analysis of depth s We conduct experiments to investigate the selection of partition depth in terms of MSE. We generate 6,000 training samples, 2,000 test samples, and 2,000 public samples following the synthetic model described above. We pick & E {3,4,6, 6, 8} and e (2,3, 4, 5, 63. For each pair of and e, we plot the 20 times averaged MSE versus 8. The result is displayed in Figure a Apparently, for each E, as s increases, MSE first decreases until s reaches a certain value. Then MSE begins to increase
grows. This further confirms the trade-off observed in Theorem 3.4 Moreover, the depth s at which the test error is minimized increases as E increases. This is compatible with theory since the optimal choice of x log ne² is monotonically increasing with respect to e.
Parameter analysis of minimum leaf sample size nn We conduct experiments to investigate the
choice of ny in terms of MSE. Following the same generating scheme, we choose E (3, 4, 6, 8) and plot MSE of LPDT versus n; for n; E (15, 25, ... 135). In Figure 2(b) the relation between MSE and ny is U-shaped under each s, which indicates that a properly chosen ny is necessary stated in
7

---

3.0
LPDT
DECONV
PHIST
19
MS5
MSE
MSE
1.7
2.0
155
1.3
100
10
(a) 8 MSE
(b) 7&r MSE
(c) 8 MSE
Figure 2: Different parameters versus MSE.
Theorem 3.4 Furthermore, LPDT achieves the best MSE for ny [35, 75] when 4, 6, while the minimum MSE occurred at = 125 when = 3. This finding is compatible with Theorem 3.4 which states that the optimal choice of ny monotonically decreasing with respect to
Our parameter analyses indicate that decreasing e favors smaller values of and larger values of n.- These choices lead decision partition with fewer grids. In summary, when facing higher levels of privacy demand, LPDT cuts down the number of grids to stabilize its estimation.
Privacy utility trade-off We analyze how privacy budget influences the quality of prediction. Under the same setup, we evaluate LPDT and other methods for e E {0.5, 1, 2. 10) with 50 repetitions. The results are displayed in Figure [(c) To show significance, we plot the (0.1, 0.9) quantiles as confidence intervals. When e increases, the MSE LPDT decreases much faster than the other methods. Note that the MSE of both PHIST and APHIST remains high, suggesting that their performances are limited by the histogram instead of the privacy mechanism.
4.2 Real data comparison with identically distributed public data
Experiment setup We conduct experiments on 12 real datasets, each repeated 50 times with ratio of 1:7:2 for public data, training data, and testing data each trial. The dataset details and pre-processing steps are summarized in Appendix (D3) To ensure significance, we adopt the Wilcoxon signed-rank test (58) with a significance level of 0.05 to check if result is significantly better. For better comparison, also train decision tree (denoted DT) on the original training data with no privacy protection, whose result will serve as a lower bound.
Table 2:
Average MSE over real data for LDP regression methods. The best results bolded and the second best results are underlined. The marked results with significance towards rest results are marked with *. Due to memory limitation, PHIST and APHIST are corrupted on two datasets which are marked with
==2 2
6
DT
L.DDTM
LPDTVV
APHIST
PHIST
DECONV
LPDT-M
LPDTV
APHIST
PHIST
DECONV
ABA
3.67c+0
10le+1
10lc+1
1.89+11
1.0c+11
10lc+7
8.38c+0*
7.34c+0*
2.05e+1
1.05c+1
1.09c+1
AIR 2.26c+1
4.80e+1
4.69c+1*
1.31e43
6.80+41
3.00++2
4.49+1*
3.60e+1*
1.60e43
4.98c+1
4.72e+1
ALG 2.12c-2
2.57e-1
2.4c-11
2.52e-1
2.52e-1
9.26c44
2.44e-1
2.46c-1
2.63e-1
2.47e-1
3.14c-1
AQU 1.92++0
2.99e+0*
2.99e+0*
4.01e+0
2.93e+0*
5.74e+3
2.73c+0*
2.67e+0*
4.75e+0
2.83+40
2.96e40
BUI 1.75e+5
1.50c46*
L66c+6**
120c+99
L44c+6*
1.3le+6*
2.04c+7
CBM 4.08e-27
2.12e40*
1.65e40**
9.53e+0
6,97e40
2.37e+3
7.62e-1*
1.23e-1*
4.94e40
3.21e40
1.23e+5
CCP
2.19c+1
1,50++2*
1.06e42*
2.07c+4
3.64e+2
3.03e+2
8.42c+1*
5.18e+1*
2.24c+4
3.28c+2
2.56c+2
CON 9. 9,38c+1
2.94c42*
2.89e42*
3.81e+2
3.00e+2
2.24c+7
2.44++2
2.13e+2*
4.16c42
2.96c42
3.13e+2
CPU 2.15c+1
3.41c+2
9,00e+11
9.26c+2
3.42c+2
2.15e45
3.02c42*
6.15e+1*
9,98c42
3.40c+2
3,98c+2
FIS 1.07e+0
2.15e40*
2.14e+0*
3.14e+0
2.22e+0
3.47e+3
1.65e40*
1.76e40*
3.60e40
2.16e40
2.21e+0
HOU 2.11e=1
8.10e+1*
8.22c+1*
1.06e+2
8.52c+1
1.92++4
7.43++1*
7.10e+1*
1.23c+2
8.21e+1
2.44e+2
MUS 3.00c+2
3,47e42*
3,46e+2"
9.50c+3
3.27e42
3,27e+2*
8.09c+3
RED 4.76c-1
7.08e-1*
7.03e-1*
3,18c+0
7,57e-1
1.23++8
6.75e-1"
6,12e-1*
3,80c40
7.12c-1
8.66c-1
WHI 5.77e-1
8.30e-1
8.42e-1
4.01e+0
8.15e-1
1.64e+7
7.03e-1*
6.61e-1*
4.45e10
8.03e-1
1.47e+0
Performance of accuracy and running time The representative results for & 2. 6 are displayed in Table Results of & 0.5, 1, 4, 8 is in Appendix [D.4] It can be seen that LPDT-M and LPDT-V both significantly outperform their competitors. All methods achieve higher MSE than DT, while the results for LPDT-M and LPDT-V are reasonably close to DT. Due to memory limitations, PHIST and APHIST fail on two datasets. We also compare the total running time in Table Appendix D.4, In general, both LPDT-M and LPDT-V achieve less running time than PHIST and APHIST, and are significantly faster than DECONV.

---

Table 3: Average MSE and standard deviation over Chicago taxi data.
DT
LPDT-M
PHIST
APHIST
Public Private
g 0.5 e
e- 2
e=
2
c
8
e 2 =
113.45
15.74
4.89
3.35
2.86
2.70
24.72
17.22
38.22 35.5
3.71
0.80
(14.23) (2.20) (0.54) (0.33) (0.10) (0.10) (0.02) (0.00)
(0.01) (0.01)
With the private and public distributions being identical, another alternative is to use solely public data to fit decision tree, We train such decision trees on public data (n, 0.1n). It is com- pared with the decision tree trained on private data and LPDT with E in Table 7 in Appendix. The results show that when Mg < n and E is large. training decision tree on public data is worse than using LPDT on most of the datasets.
With D
1.1
Without
1.0
MSE
0.9
0.8
0.7
The power of public data We conduct experiments to show the utility gain brought by public data. We take red wine dataset as an example. With ny 100 public data, we run LPDT (with DP) and PHIST (without DP). For 8 E {0.2, 0.4, 0.6, 0.8, 1}. Figure 3: Power of public data. we train each model on 8 n samples with 20 repetitions. The result is in Figure 3 PHIST with 1,100 samples achieves the same MSE as LPDT with 660 samples. The result shows that, with a small amount of public data, LPDT achieves the same performance with much fewer samples.
0.6
03 15
4.3 Real data comparison with non-identically distributed public data
We apply LPDT to the Chicago Taxi Dataset, a collection of taxi trips in Chicago provided by the Differential Privacy Temporal Map Challenge and contains sensitive information (1]). We the fare of each trip as labels and other information as features. Then we regard trips paid by PR card and credit card public data and private data, respectively. In Appendix D.5] we show the two parts are distributed differently. After preprocessing, the dataset has 101 features with 2,150,565 samples in private data and 24,436 samples in public data.
Performance We report the averaged MSE of LPDT over 20 repetitions for 8 = 0.5, 1,2, 6, and 8. As comparison to LPDT, we train two decision trees separately using the public and private datasets with no privacy protection. As for the comparison methods, DECONY fails due to the large sample size while PHIST and APHIST fail due to the dimensionality. However, after reducing the dimensionality by retaining only the continuous features, we are able to apply PHIST and APHIST. The results are displayed Table 3 A first observation is that the decision tree trained on public data yields considerably worse results than the decision tree trained on private data. This suggests that relying solely on public data leads to biased predictions. Learning solely from public data achieves an MSE higher than LPDT for all three values of e. Even for = 2, LPDT significantly outperforms histogram- based methods with e = 8. This indicates that LPDT remains effective even when substantial disparities exist between the distributions of public and private data.
How does non-identically distributed public data help? It is counterintuitive that non-identically distributed public data can benefit private estimation. We show the logic behind using such public data by investigating the first split feature in the tree partition. LPDT identifies whether a trip ends in Zone 32 as an important feature for predicting fare and initiates the recursive partitioning process by splitting along this feature. Figure 4 illustrates that trips ending in this zone generally have lower fares for both public and private data, although the actual fares differ significantly between the two datasets. This observation demonstrates that despite having different distributions, public and private data may exhibit similar patterns, thereby allowing the partition created on public data to still be effective on private data. Following this line of reasoning, to determine whether public data is suitable for specific private task, we can examine whether the qualitative relationships between labels and features remain consistent across both datasets. Whether a dataset can be utilized as public data can be of independent interest as in 32
Analysis of distribution shift In Table 3 the MSE of L.DT reduces as increases but remains higher than the MSE achieved by training a decision tree directly on private data. The performance

---

0.95
5.0
0.50
4.5
20-
0.80
3.5
15.
0.75
3.0
0.65
2.0
public
private
0.1
0.3
0.5
0.7
0.9
1.5
6.1
0.3
0.5
0.7
0.5
Figure Box plot for fares of trips dropping in and of Zone 32.
(a) Wine data
(b) Chicago data
Figure 5: Portion of public data versus MSE of LPDT.
gap can attributed the distribution shift between private data and public data. the following. we investigate how the difference between the two datasets affects the performance of LPDT. Besides the Chicago taxi data, we also adopt White Wine and Red Wine data in Section 4.2 as private and public data, respectively. The datasets contain the same variables but are distributed differently, as investigated in transfer learning literature [48]. On both datasets, we combine part the private samples with public data and perform the partition procedure the combined dataset, with the portion of public data denoted as 6. When small, there less difference between data used for partition and training. We report the average MSE of LPDT for E (0.1, 0.3, 0.5, 0.7, 0.9) after 20 repetitions. Figure shows that a small leads to a lower MSE for both datasets and all values e. Thus, LPDT is powerful when the public and private data distributed similarly, which also justifies the necessity of Assumption 3.3
Conclusion
This paper addresses the challenge of effectively performing LDP regression given both public data and private data by introducing the locally private decision tree. Due to the novel idea of leveraging public data, LPDT is accurate, efficient, and interpretable. Theoretically, guarantee and optimal convergence rate of LPDT. In experiments, we show the superior performance of LPDT regardless of the disparities between private and public data.
establish the privacy
6 Limitations and broader impact
LPDT addresses the challenge effectively performing LDP regression given both public data and private data. Future work may explore methodologies for incorporating public data in private learning using other models, such as linear models, and investigate the theoretical advantages of using public data private learning. One limitation of this paper that the measure of similarity between the public and private distribution considers only the marginal distribution. One may consider the similarities with respect the regression function, potentially following transfer learning literature [33] Moreover, in practice, public data may have different distribution than private data, which is damaging the learning process. The drawback yields the significance of public data selection or
public data quality test such as 32 60 In addition, the theoretical analysis deal with ng 2 n 2a
and ny while the intermediate zone for ny remains unexplored.
Acknowledgment
The authors would like to thank the reviewers for their constructive comments, which led to a significant improvement in this work. The project is supported by the Special Funds of the National Natural Science Foundation China (Grant No. 72342010) and was supported in part by the National Key R&D Program of China (2022YFB270240L, This research was supported by Public Computing Cloud, Renmin University of China.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC
10

---

conference on computer and communications security, pages 108-318, 2016.
[2] Faroudja Abid and Nouma Izeboudjen. Predicting forest fire in algeria using data mining techniques: Case study of the decision tree algorithm. In International Conference on Advanced Intelligent Systems for Sustainable Development, pages 363-370, Springer, 2020.
[3] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[4] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. Advances in neural information processing systems, 32, 2019.
[5] M Altosole, G Benvenuto, M Figari, and U Campora. Real-time simulation of a cogag naval ship propulsion system. Proceedings of the institution of mechanical engineers, part M: journal of engineering for the maritime environment, 223(1):47-62, 2009.
[6] Brendan Avent, Yatharth Dubey, and Aleksandra Korolova. The power of the hybrid model for mean estimation. Proceedings on Privacy Enhancing Technologies, (4):48-68, 2020.
[7] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu. Private query release assisted by public data. In International Conference on Machine Learning, pages 695-703. PMLR, 2020.
[8] Sergei N. Bernstein. The Theory of Probabilities. Gastehizdat Publishing House, Moscow, 1946.
[9] Thomas B Berrett, László Györfi, and Harro Walk. Strongly universally consistent nonpara- metric regression and classification with privatised data. Electronic Journal of Statisties, 15:2430-2453, 2021.
[10] Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Advances Neurul Information Processing Systems, 2022.
[11] Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and regression trees. 1984.
[12] Thomas Brooks, Stuart Pope, and Michael A Marcolini. Airfoil self-noise and prediction. Technical report, 1989.
[13] T Tony Cai and Hongming Pu. Transfer learning for nomparametric regression: Non-asympiotic minimax analysis and adaptive procedure. arXiv preprint arXiv:0000.0000, 2022.
[14] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-288) 28500, 2021.
[15] Yuchao Cai, Yuheng Ma Yiwei Dong, and Hanfang Yang. Extrapolated random tree for regression. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 3442-3468. PMLR, 23-29 Jul 2023.
[16] Chih-Chung Chang and Chih-Jen Lin, Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
[17] Thomas H Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
[18] Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis. Modeling wine preferences by data mining from physicochemical properties. Decision support systems, 47(4):547-553, 2009.
[19] Felipe Cucker and Ding-Xuce Xuan Zhou. Learning Theory: An Approximation Theory Viewpoint. Cambridge University Press, 2007.
[20] Fida Kamal Dankar and Khaled El Emam. Practicing differential privacy in health care: review. Trans. Data Priv., 6(1):35-67,2013 2013.

---

[21] Marie Douriez, Harish Doraiswamy, Juliana Freire, and Cláudio T Silva. Anonymizing nyc taxi data: Does matter? In 2016 IEEE international conference on data science and advanced analytics (DSAA), pages 140-148. IEFE, 2016.
[22] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[23] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 JEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438. IEEE, 2013.
[24] John C Duchi, Michael Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-200 2018.
[25] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[26] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
[27] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[28] Jianqing Fan and Young K Truong. Nonparametric regression with errors in variables. The Annals of Statistics, pages 1900-1925, 1993.
[29] Farhad Farokhi. Deconvoluting kernel density estimation and regression for locally differentially private data. Scientific Reports, 10(1):21361, 2020.
[30] Wei Gao and Zhi- Zhou, Towards convergence rate analysis of random forests for classifi- cation. Advances in neural information processing systems, 33:9300-9311 2020.
[31] Evarist Giné and Richard Nickl. Mathematical Foundations of Infinite-Dimensinn Staristical Models. Cambridge University Press, 2021.
[32] Xin Gu, Gautam Kamath, and Zhiwei Steven Wu. Choosing public datasets for private machine learning via gradient subspace distance. arXiv preprint arXiv:2303.01255 2023.
[33] László Györfi and Martin Kroll. On rate optimal private regression under local differential privacy. arXiv preprint arXiv:2206.0011 14, 2022.
[34] Jihun Hamm, Yingjun Cao, and Mikhail Belkin. Learning privately from multiparty data. In International Conference on Machine Learning, pages 555-563. PMLR, 2016.
[35] Apple Inc. Differential privacy technical overview. Technical Report Apple Inc., 2017.
[36] Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Steven Wu. Locally private gaussian estimation. Advances in Neural Information Processing Systems, 32, 2019.
[37] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces. In Conference on Learning Theory, pages 2717-2746. PMLR, 2021.
[38] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
[39] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning, pages 1376-1385. PMLR, 2015.
[40] Michael R. Kosorok. Introduction to Empirical Processes and Semiparametric Inference.
Springer Series in Statistics. Springer, New York, 2008
12

---

[41] Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differrntially private learners. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[42] Pascal Massart. Concentration Inequalities and Model Selection, volume 1896 of Lecture Notes in Mathematics. Springer, Berlin, 2007.
[43] Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky, Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.0297., 2022.
[44] Warwick J Nash, Tracy I. Sellers, Simon R Talbot, Andrew J Cawthorn, and Wes Ford. The population biology of abalone (haliotis species) in tasmania. i. blacklip abalone (h. rubra) from the north coast and islands of bass strait. Sea Fisheries Division, Technical Report, 48:p411, 1994.
[45] Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations, 2017.
[46] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ulfar Erlingsson. Scalable private learning with pate. In International Conference on Learning Representations, 2018.
[47] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2882 28300, 2011.
[48] Noam Segev, Maayan Harel, Shie Mannor, Koby Crammer, and Ran El- Yaniv. Learn on source, refine on target: A model transfer learning framework with random forests. IEEE transactions on pattern analysis and machine intelligence, (0(9):1811188 2016.
[49] Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. Privacy enhanced matrix factor- ization for recommendation with local differential privacy. IEEE Transactions on Knowledge and Data Engineering, 3079):177-11722, 2018.
[50] Shuang Song. Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing, pages 245 208.248..88 IEEE, 2013.
[51] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Science & Business Media, 2008
[52] Florian Tramèr, Gautam Kamath, and Nicholas Carlini. Considerations for differentially private learning with large-scale public pretraining. arXiv preprint 2r 2022.
[53] Pinar Tüfekci. Prediction of full load electrical power output of a base load operated combined cycle power plant using machine learning methods. International Journal of Electrical Power & Energy Systems,
140, 2014.
[54] Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer Series in Statistics. Springer-Verlass New York, 1996.
[55] Martin J Wainwright. diigh-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[56] Di Wang, Huangyu Zhang, Marco Gaboardi, and Jinhui Xu. Estimating smooth GLM in non-interactive local differential privacy model with public unlabeled data. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 1207-1213. PMLR, 16-19 Mar 2021.
[57] Stanley I. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 633399))63-69, 1965.
13

---

[58] Frank Wilcoxon. Individual comparisons by ranking methods. In Breakthroughs in statistics, pages 196-202 Springer, 1992.
[59] Xiaotong Wu, Lianyong Qi. Jiaquan Gao, Genlin Ji, and Xiaolong Xu. An ensemble of random decision trees with local differential privacy in edge computing. Neurocomputing, 485:181-195, 2022.
[60] Da Yu, Sivakanth Gopi, Janardhan Kulkarni, Zinan Lin, Saurabh Naik, Tomasz Lukasz Religa, Jian Yin, and Huishuai Zhang. Selective pre-training for private fine-tuning. arXiv preprint arXiv:2305. 13865, 2023.
[61] Da Yu. Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In The Tenth Interna- tional Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[62] Da Yu, Huishuai Zhang, Wei Chen, and Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Representations, 2021.
[63] Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Yan Liu. Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning, pages 1:208-12218 PMLR, 2021.
[64] Fang Zhou, Claire, and Ross D King. Predicting the geographical origin of music. In 2014 IEEE International Conference on Data Mining, pages 1115-1120, 120. IEEE, 2014.
[65] Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. International Conference on Learning Representa- tions, 2021.
14

---

Appendix
In this appendix, we provide the detailed results for the additional methodology (Appendix A the error analysis the main theoretical results (Appendix [B. the full proof of all theoretical results (Appendix Cj. and details well additional results of experiments (Appendix D)
A
Methodology of locally differentially private decision tree
A.1 Algorithm of max-edge partition with variance reduction rule
Algorithm Max-edge Partition Rule with Variance Reduction
Input: Public data D depth s, minimum leaf sample size nt-- Initialization:
[0, 1]s.
for = do T; = 01
for j in I do
Select as in 6
if E 1
E 1 (0) S for k = 0, then
ni U
end else
n4 = n. U (0)
end
end end
Output: Partition Vs
Error analysis
We rely on the following decomposition.
RI,P(fRP) RL,P(fx) RIPP(S DP RL,P(fx) + RI,P(fa) RT)
Privaiied Error
Sample Error
+ Rt,P(T=) - Rr,((f)
Approximation Error
where Fa. fo and fDP defined in (I. (2) and (5). respectively. Loosely speaking, the first error term quantifies the depravation brought by adding privacy noises to the estimator, which we call the privatized error. The second term corresponds to the expected estimation error brought by the randomness of the data, which we call the sample error. The last term is called approximation error, which arises due to the limited approximation capacity of piecewise constant functions. The following three lemmas provide bounds for each of the three errors.
Lemma B.1 (Bounding of Privatised Error). Let fDP be the LPDT estimator in Algorithum 7 Suppose Ja is the decision free regressor defined in (2) SSuppose π is generated by Algorithm 2 Let
Assumption 3.2 and 3.3 hold. Then, if we lake n4 n2/22 2 there holds
22 log
RE,
(s=) S
nE²
with probability p 3 Q @ RD at least 1 - 1/n2 1 4/n2.
Lemma B.2 (Bounding of Sample Error). Suppose f and Ja are the decision tree regressor and the population decision tree regressor defined in (2) and ( respectively. Let Assumption 3.2 and
3.3 hold. Then, if we take ni X ng/2", there holds
Rx)((fx) RI, (2) 2
(
with probability p & Q" at least 1 1/n2 1/n².
15

---

Lemma B.3 (Bounding of Approximation Error). Suppose f is the population decision tree regressor defined T Let Assumption 3.2 Then there holds
RL) RI,P( S 207 (2os/d)As
C Proofs
C.1 Proof of Theorem
Proof of Theorem 3.7 For each conditional distribution R Y x, Y,Y, g)) we can com-
pute the density ratio
R ((Ú,)) E s|x; = x, Y,
sup E. V. M.M M... R (Ü, S|X; = ,
dR {Ū < sup
dR dR(Ý)Y, = y)
sup E.'' dR = x²) M,MM
(8)
dR = y/)
(i) The first part is characterized by the random perturbation mechanism. Since the conditional density identical if x and x' belongs to same Aj, we have
dR(U =x) ar ER dR(U]X, x')
dR(ŪlU; = =u) E. I dR(UIU; u²)
sup
sup
The right-hand side can be computed as
dR(U U, = u) dR ( = rd)
L PŪū U = I PIU ='j
By definition, and u' are one-hot vectors and differ most two entries. generality, assume they differ on the first two elements. Also, the procedure in 3 yields that e e-/4 < U. = O//P(ū?/U = 0] s e/44 As result, 9 becomes
Without loss of
aR = u) u ( aR(ÜIU, w') u, (Z.1)lzz
II 11 PI w²)
11 PIU! = 2(5] S <e/nte/4= e (10)
sup
sup
(ii) For the second part, there holds
4x7 18 - y/
dR dR = v) dR = =0)
exp
sup B.y M.M
sup
v. M.M exp
(-4ir LÝ 5')
sup 3. 9.V'EI-M.M M.M] 10 and (TT) into ( yields the desired conclusion.
exp
ly 5/) s c²/2
(11)
4M
Bringing
C.2 Proof of Theorem
3.4
Proof of Theorem
3.4
Bringing Proposition
B.1
B.2
and
B.3
into the decomposition
7 we have
2 logg
2
RL.P(SPP) RL.P(f))
+
2 (22cee/d)aa
n=²
n
holds with probability P & Q & R" at least 2/n
5/n². When (2as/ ^ p 2as/d. d.
by choosing 2 x (nE²/ / log n)dd (2a i.c. x logne" we obtain RL, (fDD) RI, S (n=²/ log n) atd When (2as/ d) ^ s = s, by choosing x (næ²) log 1/3 1 i.c. x log nE² we
obtain R2 RL,((fx) $ (n=² log - 1/3 Note that 2as/d 2 s and only if a As result, we get
a+d 2 1/3.
log ng²
a 1
R R1 (FDP) - R1,r(fx)
with probability pa @ Q" @ R at least 1 2/n - 5/n²
16

---

C.3 Proof of Theorem 3.5
Proof of Theorem 3.5 We consider such Pe P such that for each dP xx) for some constant and E [0, 1/2 and dP x (0) = 1. Then for such Pe, the Bayes function is f(z) 0 and
R.. = O. For the excess risk of fPr we have
Ei= Y 02
RL,P(SRP)
Σ JEZ
dP dPax(x)
Ei=1 U
A,
16M
Cim1 E 0.
2
dP dPax(x).
(12)
82
Uy
Ag
JEZ
We first take expectation with respect to &. There holds
E&g
Σ E 03
Σ (0
(13)
For standard Laplace random variable ç. there holds Egg² 2. Each U/ takes either e5/44I which implies (0:)²
e=/4.1 or
(e*/441)²
Together,
13 becomes
27
gg
Σ & 0y!
(65/4 + 1)2
Bringing this into 12 leads to
32M n
S dP dPex(()). A
B (L.P((
(14)
52 (e=/4 1)²
22 siml
jeT
Next, we take the expectation of Up with respect to both P and Pn- Specifically, we have
Eú
> t
dt
n
0
Di=l
0
n
dt
Vnt
Vn
Vnt
1=1
1/n
1
1
P
<
dt
(15)
Vnt
Vnt
For any there exists some Pa with c < 1/(227)). For such Pe. we have
Vn f dP (x) = Vn 2 . -252 A
since when ny O, each grid has volumn 2 When t < 1/n, we have 1/ Vnt nt 2 1 2- -- for any s, which implies 1/vntz 2 2- vr SA, dP dPc.x(z) (z). Bring this into (15) we have
1/n TP
dl. (16) Vn / dP dFxx(x) S 2vnr
Eg
nt
Vn
n,
1=1
Using the central limit theorem, we know
Vn / dPax(I) 5 2/nl
IP
<
Σ
21
17

---

fort S 1/n. Then, 16 becomes
1/n
2
dt -
Eh== 02)2
This together with 14 yields
R (RLP(((PP)
2
3 n
Ri
/ dP dPcx(())
52 (ee/4 1)²
E
U1!
SEI
n Σ dP cxx
dP (x)x(())=1
JEI
A,
jEI
A,
C.4 Proofs of results in Section B
To prove lemmas in Section B first present several technical results. Their proof will be found in Section C.4
Lemma C.1. Suppose Çi, 1, n. are independent random variables such that a; S S S b;.
Then there holds
2+ 2i1z (0,-
P
2
2
S
2e
for any t 1.>0 O.
Lemma C.2. Suppose Ç, 1, n are independent standard sub-exponential random variables with parameters (v, 3) (55 Definition 2.9]. Then there holds
P
2t
<
2e
2
1=1
for any > O. Moreover, a standard Laplace random variable sub-exponential with parameters (V2,1). Lemma C.3. Let be a partition generated from Algorithm 2 Suppose Assumption 3.2 holds. Then for any D = {(X1, Y1), (Xn,, Yn)} drawn i..dd from P and any x E X, there holds
1 n T 1=1
(4d 5) log 2(4d log 8 21
4 n
E
- JAGO dpx(x') S
n
3n
with probability P" at least 1/n².
Lemma C.4. Let be a partition generated from Algorithm 2 Suppose Assumption 3.2 holds. Then for any D = {(X,, (X,, Y,)} drawn i.i.d. from P and any x E X. there holds
Y1(X, A(x)) - S ('d')dPx(
A(z)
SM/ - (4d + 5) logn 2M(4d 5) log
4M
+
n
3n
with probability p at least 1/n².
Lemma C.5. Let be partition generated from Algorithm using public data set Deub
{(XTub, yypub). (XPuh Ypub)). Suppose Assumption 3.2 and 3.3 hold. Suppose n ng 2
2" log² n. we take = ng/22 12" there holds
f
(AAE) dP (Px
18

---

with probability 1 1/ Moreover, the analogous conclusion holds for the empirical probability measure, i.e.
1(x, E A(x))= =2
with probability - 1/124 - 1/n2.
Lemma C.6. Let π == ( E (I,"..,),.J E (1,...
......,,]]]. = {Ajrī E I} be the variance
reduction decision tree partition generated by Algorithm 2 Then for any A& == la bil E
denote the depth of A as depth (A:) = Then for any A a, there holds
2 2-1 2 2-/ - diam(AA) - 2vd 2
This implies that for any Aj n, we have
2 2- 2 2-depth(AA)/4 S ddiam 2/d 2 dedetb((A))/
Lemma C.7. Let π == A (I.... .P).j E (I,.... ..]] = {Aj.í E I} be the variance
reduction decision tree partition generated by Algorithm A₂ as depth( AQ) = i. Then there holds
Then for any A n, denote the depth of
Σ JEZ
2 depth(())A)) 22.
Proof of Lemma B.1
We intend to bound
- = / 12 - -+))) [=(0)
=/ Eg 1fz AJ8 0/
Hi H U2 2
Σi, f0 ([EAA dPx(x).
Σn, 1xx E 1,30Y
For each j E I and any E Aj. the point-wise error can be decomposed as
Σi 1(x E A, 0
Ex, 1fx E A U?!
Σn 1f A,)U?
1 1fx E A2}U?
Σ (Yr - YO)O!
2 Σ Y.U Ei
$3.
Σ 0y
Ei= U. ER_10 Up
(11)
2
n 1=
YUU
フミ 0
Y.U Σm
Ei=
U
EE U3
(ITT)
using triangular inequality. We bound the three parts separately.
(i) For the numerator of (I), note that Y; Y 4M & and 03 E [-, Lemma C.2 yields that,
(% Y.)ūy are sub-exponential random variables with parameter (2V2M 1) and consequently
1 ΣS, (Y, YO S
128MS log
(17)
n 1=1
ng²
with probability at least
1/n?. For the denominator, applying Lemma C.1 yields
1 c/4 +1 1
Σ 0z
"
1
U/
log n
(18)
n e
im1
i=1
19

---

with probability at least - 2/n². Moreover, by Lemma C.5
we have
Σ
U Σ
1(X,EA) 2
i=1
i=1
holds with probability at least - 1/n2
1/n2. Then, can guarantee that
60/1 1
e//4
03
Up
Up
(19)
ec/4
+ 1
e
11n
1=1
1=1
2=1
1=1
e/4
log n
1
(20)
2
6514
2
with probability 1 1/n2 - 33/n². This together with yields
2 log
(T) S ne²
(21)
(if) For (IT),
first cancel the E.n Ug on both the numerator and the denominator. Then, applying we get
Lemma C.I
4/4 Σ
1
M log n
YOO
YOU?
S
6/44
1=1
1=1
with probability 2/n² since |Yi] S M. Combining this with 19 we get
22 logn
(IT) S
(22)
n
(ii) For (IIT), note that U/ E (0, 1}, we have Σ YoU S M Σm U. Thus,
E YU
U eM +1 E. i.
e1/4
nc/4 Σ i
0c/4
1=1
SM²
2i=1
اf/4+ ビi=1 0 フ U
r5/4 -i=1 0
225 llog
SM²
n
where the last inequality follows from 18 and 19
Combining this with 21 and 22).
we have
Σ., 1f E A,JÝ, 0/
Σ., 1/2 E A, Up!
22 log
Σ., 1fx E A,}0?
E,, 1fx A,JUy
n
with probability Pa x Q x R at least 1 - 4/n2 - 1/n for any x E X. This directly implies the desired bound of (PP) RI. (Jx).
Proof of Lemma
B.2
We intend to bound
Rr, RI,
|| (x) - -=(()) 2dP(())
x
Eny 1f2 A,YYU
ΣSET, 1fx E A,) (()))dxx(a) EjEt, 11s Aj) JA, dPx(x) dPx(x).
x
Ens 11x A,}U?
20

---

For any fixed j. we have
1 Ei Y.U? SA, (2))ddp((2)
JPP((a (x) - fa
+ Ei= U.
Jr dx)
Ei=1 Y.U! SA, dPx(x') - SA, ((2))d((') dPx(x))
- U/ SA, dPx(x)
(1)
- - (dd))())))))
JA (dd))
1/ Σ U/ JA, dP((x)
(IT)
We bound two terms separately. For (I), Lemma C.5 yields
dP
(x)
2-2s
(23)
7 A
with probability 1/n2 1/n2. For the numerator, Lemma C.4 yields
Σ YOU; -f ((t')a M
1
dP
dP S
2
Aj
.
i=1
Together, we get 2 /n. Analogously, by Lemma
2"
C.3
we have
1 dP (Px)x')
U
('x')dx(xa))
$ 2P.
1
22.22 22
A
1=1
This together with conclusion.
23 yields (II) S 2*/n. The bound of (I) and (II) together yields the desired
Proof of Lemma
B.3 We intend to bound
(SaCa) f(x f(r')dPx(z')
f(0)) dPx(x).
RLP (T) RL,((F))
JOEX SACas) dP dp'(x')
For each æ, if Assumption 3.2 holds, the point-wise error can be bounded by
SA( f (x') x (x')
SAID) dP (x') [(x) SACo) [5(x)) f(x))dPx(() x(x')
[A(e) dP (x')
SaCos cr.l1x' - xP
S cr.diam((()))
SACe) dP xxx')
Then bound the integral of point-wist by the sum of the integral of emror each Aj. namely
JEEN (AAia)
Hora) f(x')(())))
)dP (x')
dP(x) S Σ c diam(A,)) / A dPx(x). (24)
SACOs dP xxx)) f(x)
JEI
Apply Lemma C.5 and C.6
we have
o diammAA))2
(x) <
20 dd2 (ardepth(4A)/dds
jET
Σ
20f, V deptbb(A)) (eria4).2222dddpp((4444444))1 2ccceepttd44)//(ddedaaaaa-. (25)
jeI
21

---

For each j. we can guarantee
2 2xvdgpth(A4///dddddmbba
<
$ 22(1-(20/4)A1)
(26)
since (2a/d) /d) A < 1. Bringing 26 into 25 we get
Σ
c7 (Aj) (A,)2a 2a (2) I (2as/d))as
Σ
209, v vd2" depth(())
jEZ
A
JEI
By applying Lemma
we immediately have
of diaam(A) / A
dP(x)) S 20 2c0,2((0s/ (20s/d)8s
JET
This together with (24 yields the desired conclusion.
C.5 Proofs of results in Section C.4
Proof of Lemma C.7
The conclusion follows from Example 2.4 and Proposition 2.5 in 55
Proof of Lemma C.2
The conclusion follows from (2.18) in [55]
In the subsequent proof, we define the empirical measure D : E. -.= ((X.)))) given samples (I), Yi),....
(Xn, Y,)), where å is the Dirac function. To conduct our analysis, first need to recall the definitions VC dimension (VC index) and covering number, which are frequently used in capacity-involved arguments and measure the complexity of the underlying function class 554 40 311.
D {X1,,
Definition C.8 (VC dimension). Let B be class of subsets of and C be finite set. The trace of B on A is defined by {B n A B C B}. Its cardinality is denoted by A (A)). We say that B shatters A if A (A) = 2*))), that is, if for every A' C A, there exists B C B such that A' Bn A. For N, let
m mB (n)) =
sup (A)).
(27)
ACA, #(A)=n
Then, the set B is a minimal of such n is called the VC dimension of B, and abbreviate VC(B).
class if there exists n < oc such that m mm()) < 2" and the
Since an arbitrary set of n points {_i..... x..) possess 2n subsets, we say that B picks out a certain subset from (. } if this can be formed as set of the form B n ( Fn for B E B. The collection shatters {.1,..., rn } if each of its 2" subsets can be picked out this manner. From Definition C.8 we that the VC dimension of the class B is the smallest n for which set of size n is shattered by B, that is,
VC(B) = inf n max
(z Inn) S 2"
where A larger is its index.
## #1Bn (ZI.... mn) } B B). Clearly, the more refined B is, the
To further bound the capacity of the function sets, need to introduce the following fundamental descriptions of covering number which enables an approximation of an infinite set by finite subsets. Definition C.9 (Covering Number). Let (X be metric space and A X. For > 0, the e-covering number of A is denoted as
N(A,d, = min n 2 1: Ao In E X' such that c U B(arre)
where B(x,e) = {x' X d(xxx')) 5e).
To prove Lemma C.10 we need the following fundamental lemma concerning with the VC dimension
of random partitions in Section 2.3 which follows the idea put forward by [30] of the construction of random forest. To this end, p E be fixed and Tp be partition of 2' with number of splits s and T(p) denote the collection of all partitions Tp.
22

---

Lemma C.10. Let A be the collection of all cells x;=1la,, b,] in R. The VC index of A equals 2d + Moreover, for all ε < there exists universal constant C such that
N( A. |l (I))(()),)) E) C(2d (0(4))2++((L)) (12)+1))4))++((1)))))))
Proof of Lemma C.10 The first result of VC index follows from Example 2.6.1 in 54 The second result of covering number follows directly from Theorem 9.2 in
Before we proceed, we list the well-known Bernstein's 's inequality that will be used frequently in the proofs, Lemma C.11 was introduced in 3 and can be found in many statistical learning textbooks,
see ..g.. 42 11I
Lemma C.11 (Bernstein's inequality). Let > and > be real numbers, and n 2 be an integer. Furthermore, let .i....,En En be independent random variables satisfying EpE, 0, l15i I B, and EpE, S o² for all i = 1,...,n. n. Then for all T >> O, we have
20
2BT
P
Se
3n
Proof of Lemma C.3 Let Å be the collection all cells x [a,, bi] Rd. Applying Lemma C.10
with Q = =Dxx + Px)/2, there exists an E-net { C with
K < C(2d + (4e 2d+ (1/5)2d
(28)
such that for any Ip. there exist some k: (1, (1...., K} such that
|| E 13) 1fz (1 Se,
Since
[1 E A1) 1(x E (c)
-1/2 || A²) - 1fz E *
+ 1/2 1| A/) - 1fx E Aetllmapx
we get
|1[x E
- [
AnHll,,(Dx) 2s, 11{ E [1)= 1fx Ax)ll,,(Px) 2e. (29)
Consequently, by the definition of the covering number and the triangle inequality, for any j E Ip. there holds
1f E A2)(x,) - / dPx(x')
1x E (x(())) - / dPx(x')
+ +111< E 1/} - 11f E Axhlla((x))
Σ 1 Ax)(X.) - f dPx(ct) +4c.
n
+ [1(e 4/) 1fx AnHle,(Px)) S
An
Therefore, we get
1l ()(x)) / dP dpx(2') jzg.
1 1(x E Av - / A Σ n
n
dPx(x') 4s.
sup jET
sup ISRSK
n
(30)
For any fixed < k: < K, let the random variable & be defined by & = 1(X, E 4+) SA. dP x
(a
Then we have Ep & = 0, || < 1, and Ep. e < SA. dax(x'). According to Assumption 3.2
there holds Epp c < 7 2- Applying Bernstein's inequality Lemma C.Il we obtain
1(x, E A - 1 dPx(x') S
7 2.21 2-21...5
2r log n
3n
23

---

with probability P at least -.
Then the union bound together with the covering number
estimate 28 implies that
1x A&t A - / dPx dPx(x') S
c. 8.21~*(TT (2g()
2(T + log(2K)) log n
sup ISASK
Ax
n
3n
with probability P" at least 1 Let log and and 1/n. Then for any N₁ (2C)
(2e),) we have +logg(2k) = 2 log (4d+ 5) log n. Therefore, have
(dd S
Σ 1xx As) / Jsc dP dPx(x') s
8.2 (4d + 5) log n 2.21-s(44
2(4d + 5) logn
sup ISKSK
n
3n
1=1
(31)
with probability pa at least 1 - 1/n2. This together with (30) yields that
1 Σ
1fx E A/) - / dPx(x') <
/c. (4d + 5) log n
2(4d + 5) log
sup jEZ 1=1
Az.
-
3n
Proof of Lemma C.4 Let A be the collection of all cells x==1o=; b.] in Rd. Then there exists C Á with K bounded by (28) such that for any j I. (29) holds for some
an E-net { 1K k E {l,..... K.. Consequently, by the definition of the covering number and the triangle inequality, for any j E Ip. there holds
1(x, E ABJY, S JAz ((C')apx(())
1(x e AnDYs - -n, M(d))
11 E A/) 1-11-'
+ Σ 1xx - E AgHl|
Σ 1x, E Ā 1,, ((o))ax((o))
max . |1f E A/} 1f2 AsHlle((DS) + M 11f2 e 4/) - 1fx As)llen(px) Isisn
(X:YY, - (((')dd((x') +4M..
(32)
where the last inequality follow from the condition y' C C- M).
For any fixed < & < K, let the random variable E be defined by E := 1(X; E A&YY
SA, (x') dP, (x'). Then we have EpÊ, 0, ||E]l < 1, and Ep < 2 JA, dP(z'). According
to Assumption 3.2 there holds EpÊ? < 2 2- 2 Applying Bernstein's 's inequality in Lemma
C.II we obtain
Σ 1xx e ANtY - / ('a')d S
E
M 7 2-22 21-1-
2M log
Au
3n
with probability P" at least 1 - -T, Similar to the proof of Lemma n Ni, there holds
C.3 one can show that for any
Σ 14x e AstY - / ((+))dPx(2)) & MM
7. 2 T
2M log n
sup 1 I
3n
24

---

with probability p" at least 1 - 1/n2. This together with 32
yields that
Σ 1{x E /
(())dPx(xx)
(33)
Ag
c. (4d + 5) log
2Md + 5) log
4M n
SMV
(34)
3n
Proof of Lemma C.5
Since πT generated by Algorithm 2 the number of public samples in each of
its leaf cell A,.J E I is no fewer than vy,, i.e.
n
Σ 1(xpub E EA 2 n4, Ip
which implies nyy
Σx= == 1 E E 22 2 Hence, by Lemma C.3
there holds
I dQx(x')
1
7 2 (4d + 5) log
2(4d + 5) log ng
4
1(x Aj}
A3
Tl
nh
3r1g
Tl
c. 21 s (dd + 5) log
2(4d + 5) log nhg
2
n4
3ng
Ylg
with probability Q" at least 1- 1/n By Assumption 12 max(c, 1) (4d + 5), there holds
3.3
for sufficiently large with log n >
[ ddx((') x
/ dQ dQx
1
1
-
3
(35)
2
6
2
-
where we used condition ng 2 2 log n. For the opposite direction, notice that by Assumption and 3.2 there holds
3.3
J A
(Px(d))sT / dQx(x')
T.T
(36)
A
2
35
and 36
together yields the first conclusion. For the second conclusion, again by Lemma C.3
we have
- dPx(x') S
c. 21 (4d + log +
2(4d + 5) log n
1x, E A,}
n
n
3n
(37)
2
2 log n
for j E Ip with probability p at least - 1//n2. Consequently, there holds
Σ 1x, E A,2 / dPx(x') 2a log n
"
1
1
2T
2
4T
2
4T
2
for sufficiently large Also,
M EIXEAA / dPx(x') log n
1
2.7
2.7
26
+
2
2
A,
for large n. In conclusion, we have
Σ 1xxe A
(38)
2
38
holds when the first conclusion and both hold, which yields a probability Q" x pnn least
1/n2 1/n²..
D
25

---

Proof of Lemma C.6 According to the max- max-edge partition rule, when the depth of the tree is multiple of dimension d, each cell of the tree partition a high-dimensional cube with a side length 2 2-1/d, On the other hand, when the depth of the tree s not a multiple of dimension d, we consider the max-edge tree partition with depth [i/d] and [i/d], whose corresponding side length of the higher dimensional cube is 2-1s/d] and 2-11/41, Note that in the splitting procedure of max-edge partition, the side length of each sub-rectangle decreases monotonically with the increase of s, so the side length of random tree partition cell is between 2 [k/d] and 2 [6/d]_ This implies that
Vd 2 [b/d] < diam( (A)) S Vd 2 Li/d
Since i/d-15 [i/d] & [i/d] & i/d + 1, we immediately get 2 1 Vd. 2- < (A3) S 2vd. 2-t/4
Proof of Lemma C.7 For binary tree partition n, we can grow π to a perfect binary tree with depth meaning that all interior nodes have two children and all leaf nodes have the same depth 8. Then, we can compute the number of leaf nodes on и. On one hand, depth-s perfect binary tree has 2 leaf nodes [17]. On the other hand, consider the perfect tree grown by æ. Each leaf node Aj, when grown to depth s, is the root node of a depth-(s - depth(A,,) perfect binary tree. Thus, the node A, with induce 2*-depth(A) 4,) leaf nodes. Immediately, the total number of тे can be computed as EjEz 2e)eept(AA) Matching the results of these two computations yields the desired conclusion.
C.6 Derivation of removing the range parameter
At present, we assume that Px = Qx. but the analogous conclusion holds as long as their density ratio is bounded. Let X be scaled to X. The excess risk can be decomposed by
RL, (FPP)- - R2,r
L(x
DP (z))) v) Sp.11=
L(x, ( y)
0.11
DP (2))dP(Z,)) 1 o (x))
+
LII
1.11dcc
log
+ M2P(X & x9=110,1))
ng2
Note that
P(X & X5=1 (0, 1]) P(X $ x==1 (1) s Σ
P(X) & (a)
j=1
Denote the CDF of X as F3, Since
P ((il@)) (p(()))--(aa)) rd( >
2 ny
= P
Fr (aJ) >
2 log ng
ngg
Tlg
2 log ny
my
1
Thg
Tt
and similar result holds for bi, we have P(X & (12.b))) S log n. with probability 1 - 1/n2. Thus, there holds P(X & l lai 1o)) < log na
with probability 1 - d/nž. Note that if we restrict (instead of my 2 n 20222 as the paper, which a minor change), there holds P(X & x x0=110,11) 1J) & (ns²)~ - log n. Thus, up to log factor, Theorem 3.4 holds with probability
my
ng 2 (ne2)
dv20 20+2d
1 d/n..
26

---

D Experiment details
D.1 Implementation details
All experiments are conducted on a machine with 72-core Intel Xeon 2.60GHz and 128GB of main memory. The code of LPDT is available GitHut Each round of training and testing of LPDT may take less than a second for small data with thousands of samples. For large datasets such as Chicago taxi data, may take minutes.
For LPDT-M and LPDT-V, we choose my E {2, 5. 10, 20. 40. 60, 80, 100, 120, 140, 160)
and s E {1, 2, 3, 4} in Section For large data Section 4.3 we let {4, 6, 8, 10). In addition, we add one more parameter adjusting the allocation of the privacy budget on the numerator and denominator. Specifically, let (3) and 44 be
U/-
with probability 1+e0r/2
1 U.
with probability
1t0p5/2
14e0r/2-
as well as
2M
Y, = Y, +
(1 - p)e &
for E [0, 1]. In this case, the mechanisms are respectively Pc-LDP and (1 - P)e-LDP, which means the hybrid mechanism is still s-LDP. We select p {0.3, 0.73.
Decision Tree (DT): For standard non-private decision trees, we use the implementation
by Seikit-Learn
47 We select max_ -en__h in 21, 4] in Section 4.2 For large data in Section 4.3 we let maar_eppla
{4,6, 8, 10].
Private Histogram (PHIST): We implement the Private Histogram proposed by 9 in Python. PHIST applies the Laplacian mechanism privatize the estimation of marginal and joint probabilities for a cubic histogram partition with bandwidth h. In cells with a marginal probability less than estimation is truncated to O. We let h E (1/4, 1/3, 1/2, 1}, resulting in the number of grids in each feature to be 3,, 1]. Due to memory limitations, we set h 1 for datasets with d > 21. We the truncation parameter / {0.01, 0.05).
Adjusted Private Histogram (APHIST): We implement the Adjusted Private Histogram proposed by [33 in Python. APHIST modifies PHIST by replacing the privatized marginal probability with an average of marginal probability and volume of the cell. In cells with an averaged probability less than I, estimation truncated to We let (1/4, 1 1/3, 1/2, 1}, resulting in the number of grids in each feature to be (4, 1). Due to memory limitations, we set h = for datasets with > 21, We set the truncation parameter / (0.01, 0.05).
Deconvolution kernel (DECONV): DECONV imposes noise to (X,, Yú directly to provide privacy. It then treats the regression procedure as a measurement error problem and solves it conventionally using a deconvolution kernel. We implement DECONV proposed by 29 in Python. We set the bandwidth E (0.02, 0.05, 0.1, 0.2, 1, 1)
D.2 Parameter tuning strategy
To disentangle the parameter tuning problem under local differential, we propose to leave part of the private data as a validation set, whose sample size is Ry. For each set of parameters on the parameter grid, the model is partitioned on Xpub and trained on X. Then the model is passed to each data holder in the validation set. The data holder computes the point-wise error If(z))
f(x) 2 for each model and returns a privatized value to the curator. By advanced composition [26 39 for A parameter grids,
we can guarantee the e- privacy of x with a noise / E/e where & is standard Laplace random
variable. Then, the estimated validation mean squared error is 1 E.
no
VT Es/e. As long as Vinz'e-1 are sufficiently small, the validation procedure can be well conducted. As result, the capacity of parameter grids is restricted by o(n,e). In many cases, large amount of data can be acquired if LDP is posed. In such a scenario, we can assure ny to be large enough to cover the desired parameter grid.
27

---

D.3 Details of real data sets
We summarize the details of real data sets in Table 4 with the number of instances and features after pre-processing reported. Each feature is min-max scaled to the range [0, 1] individually. We also present additional information of the data sets including the data source and the pre-processing details.
Table 4: Description of real datasets
DATASET
DATASET
d
ABA
1177
8
CPU
8192
12
AIR
1503
6
FIS
908
6
ALG
244
12
HOU
506
13
AQU
546
MUS
1059
68
BUI
372
105
WHI
4898
12
CBM
11934
16
RED
4898
12
CCP
9568
CON
1030
8
ABA: The Abalone dataset originally comes from biological research 44] and now it is accessible on UCI Machine Learning Repository [22]. ABA contains 4177 observations of one target variable and 8 attributes related to the physical measurements of abalone.
AIR: The Airfoil Self-Noise dataset UCI Machine Learning Repository records the result of series of aerodynamic and acoustic tests of airfoil blade sections conducted in an anechoic wind tunnel [12]. It comprises 1503 instances of 6 attributes including wind tunnel speeds and angles of attack.
ALG: The Algerian Forest Fires dataset on UCI Machine Learning Repository contains 244 instances of 11 attributes and output attribute. The task is to predict the condition of forest fires in Algeria 21. The attribute date is omitted when conducting regression in our experiments.
AQU: The QSAR aquatic toxicity dataset used develop quantitative regression QSAR models to predict acute aquatic toxicity towards the fish Pimephales promelas (fathead minnow) on a set of 908 chemicals. It contains 546 instances of 8 input attributes and output attribute.
CON: The Concrete Compressive Strength dataset on UCI Machine Learning Repository contains 1030 instances of 8 input attributes and 1 output attribute. The task is to predict the concrete compressive strength which is a regression problem.
BUI: The Residential Building Data Set Data Set dataset on UCI Machine Learning Repository includes construction cost, sale prices, project variables, and economic variables corresponding to real estate single-family residential apartments in Tehran, Iran. It contains 372 instancesa of 103 input attributes and 2 output attributes.
The Condition Based Maintenance of Naval Propulsion Plants dataset S on UCI Machine Learning Repository instances of 16 features.
CBM:
generated from sophisticated simulator of Gas Turbines. It contains 11934
CCP: The Combined Cycle Power Plant Data Set dataset 53 contains 9568 data points. There are features that can be used predict the net hourly electrical energy output of the power plant.
on UCI Machine Learning Repository
CPU: The cpusmall dataset from LIBSVM [66. It contains 8192 instances, each with 12 attributes.
FIS: The QSAR fish toxicity dataset on UCI Machine Learning Repository was used to develop quantitative regression QSAR models predict acute aquatic toxicity towards the fish Pimephales promelas (fathead minnow) on set of 908 chemicals. It contains 908 instances of 7 features.
RED: This dataset contains the information on red wine of the Wine Quality dataset [18] on UCI Machine Learning Repository. There are 11 input variables to predict the output variable wine quality. 4898 instances are collected in the dataset.
28

---

WHI: This dataset also originates from the Wine Quality dataset [8] on UCI Machine Learning Repository. There are 11 features related to white wine to predict the corresponding wine quality.
HOU: The Housing-Boowe Borton dataset can be acquired from LIBSVM datasets of NTU, which is comprised of 506 observations with 13 features. The dataset is used predict the price of house in Boston.
MUS: The Geographical Original of Music dataset was built from a personal collection of 1059 tracks covering 33 countries/areas. The program MARSYAS [64] was used to extract audio features from the wave files. We used the default MARSYAS settings in single vector format (68 features) to estimate the performance with basic timbal information covering the entire length of each track.
D.4 Additional result of the real data experiment
We present the additional result of the real data experiment omitted in the main text due to page limitation.
Table 5: Additional results for average MSE over real data sets for LDP regression methods. The best results are bolded and the second best results are underlined. The marked results with significance towards the rest results are marked with *, Due to exceeding the memory limit, PHIST and APHIST are corrupted on two data sets which are marked with
0.5
LPDT-M
LPDI-V
APHIST
PHIST
DECONV
LPDE-M
LPDTV
APHIST
PHIST
DECONV
ABA
5.67et0
T.00et
1.07++1
1.12+1
I.6e41
1.05+7
1.fe+t
L0les1
1.6c+1
1.07e+1
3.0644
AIR 2.26c+1
3.79e+2
1,29c+2*
2,10e+2*
3.10e42
1,19446
167e+2
1.17e=2
9.25++1*
1.26e42
5.64e47
ALG 2.12a-2
2.59c-1'
2,59c-1*
2.740-1
2,83c-1
8881+22
2.40e-1*
2
2.56e-1
2
1.73c+2
AQU 1.92++0
1.35e+1
3.0Ie+0*
3.68e+0*
4,06e40
6.02e+4
3,06e+0
3.63e=0
2.99++0*
3.11e+0
9.55e43
BUI 1.75c+5
3,54c+6*
1.70e46*
1.20c49
2.46c46*
1.54c+6*
3,30c+9
CBM 4.08c-27
6.96c40
6.64e+0*
6.96<+0*
6,99c40
9.69c46
2.40er0
1.90+0**
6.91e40
6.92c40
1,58c46
CCP 2.19ct1
4.52e+2*
4.89++2*
6.79e+1
9,31e+2
1.23e+10
4.72e+2
4.72e+1
4.15c+2*
4.82c+2
1.43++7
CON 9.38c+1
4.56c+2
4.56c42
3.24e+2*
3.38c+2*
3.33e+8
3.08c+2
3,42++2
2.99c42
3.03e42
3. 38c47
CPU 2.15e+1
3.56e++
3.56e+2
3.56e+2
3.68442
6.6le+7
3.41et2
9.37e+1*
3.41e+2
3.47e+2
9.37e+7
FIS 1.07c+0
3.66c40
3.66e+0
2.62e+0*
2.81e40+
1.68+45
2,48++0
2.48c40
2.24c+0*
2.30c40
1,57e44
HOU 2.11e+1
1.05e42*
1.04e+2
1.08c+2
1.17042
2.34c+5
8,56c+1*
8.56e+1*
9,00e+1*
9.320+1
1.55e+7
MUS 3.00++2
6.21e+24
6.21e+2*
2.18c+5*
4.26e+2*
4.26e+2*
1,29+66*
RED 4.762-1
8,78c-1*
8.94c-1*
1.09+0
1.30c+0
2,74046
7
7.04c-1*
8.01c-1
8
1.15et5
WHI 5.77G-1
8.77c-1*
8.69-11
9.45e-1
1.03c40
1.28c+9
8.68c-1
8.48-11
8.32e-1
8.56e1
1,58c66
DT
LPDT.M
LPDTV
APHIST
==4 4
PHIST
DECONV
LPDTTM
LPDT-V
APHIST
==8
PHIST
DECONV
ABA 55676-0
9,46e+00*
9.54c+0*
2,00c+1
1.05+11
1.14e+1
7.96+40*
6.9Mc+0*
2.07e+1
1.05++1
1.05+t1
AIR 2.26e+1
4.67e+1*
4.15e+1*
1.52e+3
5.28e+1
4.85e+1
4.45e+1*
3.47++1*
1.64e43
4.87e+1
4.71e+1
ALG 2.12e-2
2.40ee11
2.42e-1*
2.59c-1
2.48c-1
2.03e+3
2.43e-1
2.46e-1
2.64e-1
2.46e-1
2.54c-1
AQU 1.92c-0
2.81e+0
2.77c+0*
4.54c+0
2.85c+0
5,23e+0
2.71c+0*
2.63e+0*
4.86c40
2.83e+0
2.85c+0
BUI 1.75e+5
1.49+6**
1.35++6*
3.90++7
1.40+66*
1.28e+6*
1.38++7
CBM 2.
T*
5.10ee11
7.45e+0
6.48e+0
1.41et5
7.08e
3.77e-2*
4.49e+0
2.00e+0
6.44e+0
CCP 2.19
9.08e+1
6.78e+1*
2.20e+4
3.34e+2
2.86e+2
8.27e+1
4.76e++*
2.26c44
3.26e+2
2.10e+2
CON 9,380-1
2,70c+2*
2.54c+2
4.06e+2
2.97c+2
3,93e+2
2.34c+2*
2.Mec42
4,21e42
2,96e+2
2.9le42
CPU 2.15e=1
3,05c+2*
8.36e+1*
9.65c+2
3,40c+2
3,93e45
3.01e+2+
4.85c+1*
1.02e43
3,40c+2
3,42c+2
FIS 1.07e-0
1,90
2.07+00
3,47e40
2.17c+0
2.40e+0
1,55++0+
1.5e+00
3.67e40
2.15e40
2.17c+0
HOU 2.11e=1
7.80++1
7.37e+1*
1.18e+2
8.27e+1
1.31e+3
7.32e+1+
7.02e+1
1.26++2
8.19e+1
1.27e+2
MUS 3.00e+2
3.33+42
3.46442
8.03et4
3.2le+2
3.26c42*
2.25ct4
RED 4.76c-1
7.13e-1
6,92e-1
3.63c40
7.19c-1
4.03e+2
6.14c-1*
5.79e-1
3.88c+0
7.09e-1
6.94c-1
WHI 5.77e-1
7.39--1*
7.50a-1
4.34++0
8.05e-1
1.88c+4
6.93e-1*
6.40e-18
4.50c40
8.02e-1
8.21e-1
D.5 Details of Chicago taxi dataset
The dataset used in this study was obtained from the Differential Privacy Temporal Map Challenge (DeID2), which aims to develop algorithms that preserve data utility while guarantceing individual privacy protection. The dataset contains quantitative and categorical information about taxi trips in Chicago, including time, distance, location, payment, and service provider. These features include the identification number of taxis (tazi_id) time of each trip (seconds), the distance of each trip (miles), index of the zone where the trip starts (pea), index of the zone where the trip ends (dca), service provider (compang), the method used to pay for the trip caaimentttypo amount of tips (tips), and amount of fares (fare).
To preprocess the data, we selected locations in the central region of the map data to ensure sufficient passenger pick-up and drop-off orders, and we chose the top 10 taxi companies with the highest number of orders. We then divided the dataset based the payment feature to distinguish between
29

---

Table 6: Average time over real data sets for LDP regression methods. Due to exceeding the memory limit, PHIST and APHIST are corrupted on two data sets which are marked with
DT
LPDT-M
LPDT-V
APHIST
PHIST
DECONV
ABA
3.34c-3
1.78c-2
3.23c-2
2.70c-2
2.71c-2
1.47c+0
AIR
2.63c-3
1.13--2
1.76c-2
9.68c-3
9.58c-3
1.29c-1
ALG
1.79p:3
2.02e-3
2.81e-3
6.10e-3
5.55e-3
1.17e-2
AQU
2.21e-3
3.38e-3
5.21e-3
7.17e.3
5.62e-3
3.12e-2
BUI
3.87e-3
4.09e-3
2.6le-2
1.35e-1
2.58c-2
8.980-2
1.23e-1
1.0c-1
1.0c-1
2.76c+1
CCP
8.11c-3
6.28c-2
6,98c-2
4.65c-2
4.70c-2
4.42c+0
CON
3.28c-3
6.38e-3
1.0le-2
7,45e-3
7.14c-3
9.06e-2
CPU
1.52e-2
3,99e-2
6.40e-2
5.86e-2
5.80c-2
9.75e40
FIS
3.00c-3
4.53c-3
7.63c-3
6.64c-3
6.01c-3
5.530-2
2.52c-3
3.370-3
5.30c-3
5.21e:3
5.54c-3
5.030-2
MUS
6.24e-3
6.64e-3
4,94e-2
6.49e-1
RED 3,49p:3
9.01e-3
1.41e-2
1.17e-2
1.18e-2
2.65e-1
WIlI
7.16e-3
1.68e-2
4.26e-2
3.29e-2
3.29e-2
2,70e+0
Table 7: Additional results for average MSE over real data sets for decision trees.
The best results are bolded.
DT-pub
PDT-M
PDT-V
ABA
5.67c40
7.93e40
8.38c+0
7.34c40
AIR
2.26c+1
4.28c+1
4.49c+1
3.60e+1
ALG
2.12c-2
2.59c-1
2.44c-1
2.46c-1
AQU
1.90+00
2.42c+0)
2.73e+0
2.67e40
BUI
1.75e+5
1.39c+6
1.44++6
1.31e+6
CBM
4.11c-27
1.57c40
7.62c-1
1,23e-1
CCP
2.19c+1
7.21c+1
8.42c+1
5.18e+1
CON
9.38c+1
2,21e42
2.44c42
2.13e+2
CPU
2.10c+1
2.92c+2
3.02e+2
6.15e+1
FIS
1.07+00
1.4e+0
1.65e+0
1.76+40
HOU
2.11e+1
5,58e+1
7.43++1
7.10e+1
MUS
3.00e+2
3,38e+2
3.27e+2
3.27e+2
RED
4.76e-1
5.69e-1
6.75e-1
6.12e-1
WHI
5.76e-1
7.10e-1
7.03e-1
6.6le-1
private and public data, which is in accordance with the fact that we only had access to specific data holders. Additionally, we converted all categorical features, including pea, dea, and company, into one-hot values, resulting in 102-dimensional feature vector. Ultimately, we made predictions for the fares of the entire trip.
Figure shows a boxplot the prediction feature the Chicago taxi dataset. As we can see from the plot, the public data and private data differ in distribution, which we referred to distribution shift in the main text.
35
30
25
20
15
10
5
0
public
private
Figure 6: Boxplot of fare in Chicago taxi dataset
30


Reviews:
[{"review_id": "rZU4IVFXBF", "reviewer": "Reviewer_9jqb", "summary": "This paper proposes a locally differentially private (LDP) decision-tree (DT) regressor algorithm that takes advantage of public data for utility improvement.\nThe proposed algorithm, LPDT, uses Randomized Response (RR) and the Laplace mechanism to protect the tree partition step.\nThis paper also introduces a new splitting rule named \"max-edge partition rule\" by using the variance as a reduction criterium.\nTheoretical results were presented for convergence rates, training/testing time and space complexity, with important gains in comparison with the state-of-the-art.\nExperimental results were provided with synthetic and many real-world datasets to validate the proposed approach, with significative gains over the state-of-the-art.", "questions": "- Why only presenting results for medium to high privacy regimes?\n- In lines 73 & 74 \"we show that LPDT performs well even in the presence of significant disparities between public and private data.\", it is unclear how \"performs well\" is concise with the results of Fig. 4. For instance, training only on private date led to MSE=0.8 (Table 3). Using only \\alpha=1 as public data, with \\epsilon=3 (medium regime), the MSE~3.5 is ~4.5x larger. How worse would that be in high privacy regimes?", "limitations": "Although using public data can lead to utility improvements, the authors did not discuss the limitation of having such data in real-world applications. Indeed, following my last question on \"data heterogeneity\", the learning process could be really damaged if public and private data have different distributions. I recommend the authors to further discuss this paper's limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The motivation behind using Locally Differentially Private (LDP) methods for decision trees is well-founded. The idea of using public data is new and has proven to bring advantages in many fields (e.g., vision, languages).\nTheoretical and experimental validation were presented showing advancement over the state-of-the-art.", "weaknesses": "The experiments only considered medium privacy regimes \\epsilon >= 2. The paper would greatly benefit from including high privacy regimes \\epsilon <=1 and the utility gain of using public data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: The paper would greatly benefit from including high privacy regimes $\\epsilon$ <=1 and the utility gain of using public data.\n\nA1: Please see R1 of the global response for small $\\varepsilon$ and Experiment 4 for the utility gain. \n\nQ2: In lines 73 \\& 74 ... How worse would that be in high privacy regimes?\n\nA2: \nWe apologize for the unclearness of our statement. \nThe conclusion aims to state that the overhead brought by the distribution shift is minor compared to the overhead brought by privacy. \nFor instance, using $\\varepsilon = 4$ and $\\delta = 0$ results an MSE ~2.3, which increased 1.5 compared to  $\\varepsilon = \\infty$ and $\\delta = 0$. \nYet, using $\\varepsilon = 3$ and $\\delta = 1$ leads to an MSE ~2.9, which is ~0.6 higher. \nThe results of the high privacy regime are in Experiment 2 in the global response. \n\n\n\n\n\nQ3: Although using public data can lead to utility improvements, the authors did not discuss the limitation of having such data in real-world applications. Indeed, following my last question on \"data heterogeneity\", the learning process could be really damaged if public and private data have different distributions.\n\n\n\nA3: \nPlease see R2 in the global response for a discussion of public data. \nWe will add the discussion of the limitations."}, {"review_id": "Zq3r6SejBo", "reviewer": "Reviewer_QZtg", "summary": "This work studies non-parametric estimation under local differential privacy with public data. The authors propose a locally private decision tree algorithm and show that it is min-max optimal under some regimes. The authors also test the algorithm on real and synthetic datasets.", "questions": "Can existing algorithms be easily modified to take advantage of public data? I feel it is best to fully investigate the possibility of leveraging existing algorithms before inventing something entirely new. Extension based on prior algorithms also serve as a necessary baseline to compare against.\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea to leverage public data in LDP estimation is practically relevant. \n2. The experiment results are extensive. It includes both synthetic and real-world data and discussion on the effect of various parameters. Empirically the algorithm outperforms existing algorithms in most experiment settings.\n3. The authors provide a thorough theoretical analysis of the proposed algorithm in terms of sample complexity and computation cost.  The proposed algorithm has improved time complexity over prior works.", "weaknesses": "1. The proposed algorithm does not seem to improve too much in terms of sample complexity with public data. We normally hope that using public data should improve the performance somehow (e.g. in reference [8], with public data the prior bound on the mean can be removed), but it seems that the algorithm merely attains the optimal bound without public data only when $\\varepsilon\\lesssim 1$. Existing algorithms that do not use public data can also achieve the same sample complexity.\n2. Given the first point, the fact that the proposed algorithm does not work without public data appears to be a significant disadvantage. While LPDT has advantages in time complexity and empirically outperforms existing methods, it comes at the expense of additional resource of public data. It is thus in some sense unfair to compare with existing methods that do not use public data.\n\n#### Some minor problems\n\n1. The lower bound only matches the upper bound in Theorem 3.4 when $\\varepsilon\\lesssim 1$ (since $e^{\\varepsilon}-1\\simeq \\varepsilon$ only with small $\\varepsilon$), but all experiment results are for large $\\varepsilon\\ge 2$.\n2. The notation $p$ is used first for the density function and then again used for decision tree depth. Please consider changing one of them to avoid confusion.\n\n#### Update\n- Increased my score to 5 after the authors added new results for small $\\varepsilon$ and introduced a new algorithm that matches the lower bound for all ranges of $\\varepsilon$.\n- Increased to 6 after the authors resolved my question for removing range parameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: The proposed algorithm does not seem to improve too much ... the same sample complexity.\n\nA1: Please see the R2 of the global response for the theoretical improvements.\n\n\nQ2: Given the first point, the fact that the proposed algorithm does not work without public data appears to be a significant disadvantage. While LPDT has advantages in time complexity and empirically outperforms existing methods, it comes at the expense of additional resources of public data. It is thus in some sense unfair to compare with existing methods that do not use public data.\n\nA2: We agree with the reviewer that the additional public data can be an unfair comparison. \nGiven both private data and public data, one has three choices: leveraging only private data, only public data, or both. \nPrevious methods focus on the first choice, while the second choice is prohibited since we allow $\\mathrm{P}$ and $\\mathrm{Q}$ to be completely different. \nWhen $E_P[Y|X] = E_Q[Y|X] + 1$, this could lead to a trivial risk. \nOur method explores the third choice for the first time and works well as long as a small amount of public data exists.\nFor better illustration, we conduct an additional set of experiments (Experiment 4 in the global response) to show that, to attain similar performance, the sample size $n$ and $n_q$ required by LPDT can be much smaller than previous methods. \nThe observation suggests that, when data-collecting resources are limited, organizations can put up rewards to get a small amount of public data rather than collecting a large amount of private data. \n\n\nQ3: The lower bound only matches the upper bound in Theorem 3.4 ...\n\nA3: We propose the following improvements to fix the gap between theory and empirical findings. \n\n1. We present the experiment results for small $\\varepsilon$ as in R3.\n\n2. An upper bound that matches the lower bound can be derived by introducing a novel mechanism, as described below. Upon partitioning $\\mathcal{X}$, a corresponding partition is created for $\\mathcal{Y}$ (done uniformly or using information from public data), denoted as ${B_1, B_2, \\ldots, B_k, \\ldots}$. Subsequently, each data holder generates one-hot encodings $V_i^{j,k} = \\mathbf{1}{X_i \\in A_j, Y_i \\in B_k}$ and $U_i^j$ as in the paper. These quantities are privatized using random responses and can be utilized to estimate equation (1) in the paper. The use of random response can improve the convergence rate to $(n(e^{\\varepsilon} - 1)^2)^{-\\frac{\\alpha}{\\alpha + d}}$. Nevertheless, the new mechanism might be less effective in practical applications. Due to the substantial number of grids, only a limited number of samples exist within each $A_j \\times B_k$, resulting in high instability during estimation within each grid.\n\n\nQ4:  The notation  $p$ is used first for the density function ... to avoid confusion.\n\nA4: We apologize for the misuse of notations. We will use $s$ to denote the depth. \n\nQ5:  \nCan existing algorithms be easily modified to take advantage of public data? I feel it is best to fully investigate the possibility of leveraging existing algorithms before inventing something entirely new. Extension based on prior algorithms also serves as a necessary baseline to compare against.\n\nA5: \nThe reviewer brings up an interesting question. \nOne of the potential strategies is to form a private estimator from $\\mathrm{P}$ data and a normal estimator from $Q$ data. Then one can take the weighted average of the estimators, following [3], or adaptively choose one of them, following [2]. \nYet, both approaches require additional assumptions on the regression functions $P_{Y|X}$ and $Q_{Y|X}$. \nWe hope the reviewer can provide some clues about how the existing methods can be modified. \n\n\n[2] T Tony Cai and Hongming Pu. Transfer learning for nonparametric regression: Non-asymptotic minimax analysis and adaptive procedure. arXiv preprint arXiv:0000.0000, 2022.\n\n[3] T Tony Cai and Hongji Wei. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. 2021."}, {"review_id": "FJsrR1lzW8", "reviewer": "Reviewer_xd2A", "summary": "The paper studies nonparametric regression under local differential privacy (LDP) constraints with the aid of public data. The paper proposes an algorithm, locally differentially private decision tree (LPDT), which uses public data to construct the splitting criteria for the decision tree and private data to compute the regressed values for each leaf node. The paper shows that under certain assumptions, with a small amount of public data, the algorithm can achieve a near-optimal convergence rate for decision tree regression under LDP constraints. The paper also demonstrates the effectiveness of the algorithm through experiments.", "questions": "See the questions above.\n\nAdditional questions:\n1. In Theorem 3.4, how does the error depend on tau? Could you comment on the dependence on tau as well?\n2. Figure 4(b), when delta = 0, and eps is large, does the proposed method recover the non-private training rate?\n3. For LDP estimation, the dependence on eps can be improved to inverse exponential in eps when eps is large, e.g. in Feldman et al 2022. Can the rate in Theorem 3.4 improve to a similar dependence on eps as well? It seems the considered eps's in the experimental section are mostly large.\n\n[Feldman et al 2022] Vitaly Feldman, Jelani Nelson, Huy Nguyen, Kunal Talwar. Private Frequency Estimation via Projective Geometry", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies an interesting problem, which has not been studied before to the best of my knowledge. The paper also proposes an algorithm that achieves an optimal convergence rate under reasonable assumptions. \n\n2. The paper shows that without public data, decision tree learning will have a nontrivial risk with any amount of private data. This suggests the importance of public data for decision tree regression under LDP constraints.", "weaknesses": "1. The importance of public data has been established for different learning tasks recently, especially under the central notion of differential privacy. Extending a similar observation to decision tree learning under local DP constraints is interesting, but less surprising.\n\n2. The similarity assumption between P and Q, Assumption 3.3, looks weird. The assumption doesn't pose any requirement on how y is correlated with x. Imagine the case when P and Q have the same marginal on the feature space while the correlation between X and Y are completely different under P and Q. It would be hard to learn useful information about how x can be used to predict y from public data, and hence the structure of a good decision tree. I am not sure whether I have missed other important assumptions.\n\n3. Another baseline to compare (theoretically, and empirically) would be to only use public data to train the decision tree. How would the proposed method compare against this baseline? E.g., in the experiment in Section 4.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nQ1: The importance of public data has been established  ... but less surprising.\n\nA1: \nWe agree with the reviewer that the idea of using public data is less surprising. \nHowever, we would like to emphasize our motivation for utilizing public data. \nMost public data usage, such as gradient preconditioning or public pretraining, uses public data to accelerate convergence. \nOur public data is used for adaptive partitioning, which is impossible under LDP constraints without public data. \nAs a result, we claim our contribution as using public data to conduct procedures that would be infeasible without access to the raw private data. \n\n\nQ2: The similarity assumption between P and Q, Assumption 3.3, looks weird ... whether I have missed other important assumptions.\n\nA2: \nThe reviewer is correct. Please see R2 in the global response. \nWithout posing strong assumptions, utilizing information in $Y|X$ is hard even in the non-private case [2,3] and can be regarded as future research directions.  \n\nQ3: Another baseline to compare (theoretically, and empirically) would be to only use public data ... in the experiment in Section 4.2.\n\nA3: \nIn the setting of Section 4.2, the public and private distributions are identical. \nIn this case, theoretically, using $n_q \\gtrsim (n\\varepsilon^2)^{\\frac{2\\alpha + d}{2\\alpha + 2d}}$ public samples can be more effective that LPDT. \nEmpirically, we conduct experiments with respect to such baseline in R1 of the global response. \nThe result shows that, when the privacy level is low and the public data is insufficient, LPDT is still the best choice. \n\n\nMoreover, we would like to argue that, once under different public and private distributions, using public data will fall both theoretically and empirically. \n\n\n\n \nQ4: In Theorem 3.4, how does the error depend on tau? Could you comment on the dependence on tau as well?\n\nA4: When the parameter $\\tau$ is not treated as a constant, the upper bound becomes $(\\frac{\\tau^2\\log n}{n \\varepsilon^2})^{\\frac{\\alpha}{\\alpha+d} \\wedge \\frac{1}{3}}$. \nThe smaller $\\tau$ is, the closer $\\mathrm{P}_X$ and $\\mathrm{Q}_X$ are, the tighter the upper bound gets. \n\nQ5:\nFigure 4(b), when delta = 0, and eps is large, does the proposed method recover the non-private training rate?\n\nA5: \nThe MSE for $\\delta = 0$ and $\\varepsilon = 1000$ is 1.11. \nThere is a slight performance gap caused by creating the partition from one dataset and fit on the other. \nBut generally, the MSE matches the performance of training a decision tree directly on private data. \n\n\nQ6:\nFor LDP estimation, the dependence on eps ... the considered eps's in the experimental section are mostly large.\n\nA6: \nTechnically speaking, under the proposed mechanisms, we do not think the improvement of the upper bound is possible. \nThe Laplace mechanism necessitates the inclusion of a $\\varepsilon^2$ term and cannot be changed to $(e^\\varepsilon - 1)^2$. Conversely, the lower bound is drawn using techniques in [4] and must include a factor of $(e^\\varepsilon - 1)^2$. However, we propose the following improvements to fix the gap between theory and empirical findings. \n\n1. We present the experiment results for small $\\varepsilon$ as in R3.\n\n2. An upper bound that matches the lower bound can be derived by introducing a novel mechanism, as described below. Upon partitioning $\\mathcal{X}$, a corresponding partition is created for $\\mathcal{Y}$ (done uniformly or using information from public data), denoted as ${B_1, B_2, \\ldots, B_k, \\ldots}$. Subsequently, each data holder generates one-hot encodings $V_i^{j,k} = \\mathbf{1}{X_i \\in A_j, Y_i \\in B_k}$ and $U_i^j$ as in the paper. These quantities are privatized using random responses and can be utilized to estimate equation (1) in the paper. The use of random response can improve the convergence rate to $(n(e^{\\varepsilon} - 1)^2)^{-\\frac{\\alpha}{\\alpha + d}}$. Nevertheless, the new mechanism might be less effective in practical applications. Due to the substantial number of grids, only a limited number of samples exist within each $A_j \\times B_k$, resulting in high instability during estimation within each grid.\n\n\n[2] T Tony Cai and Hongming Pu. Transfer learning for nonparametric regression: Non-asymptotic minimax analysis and adaptive procedure. arXiv preprint arXiv:0000.0000, 2022.\n\n[3] T Tony Cai and Hongji Wei. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. 2021.\n"}, {"review_id": "sdk4girfKj", "reviewer": "Reviewer_HsA8", "summary": "In this paper, the authors propose a scheme for training decision trees on a combination of public and private data. By using local differential privacy the algorithm guarantees that adversaries learn little about the private data from the outcomes of the algorithm. Under assumptions and a specific splitting rule for the algorithm's public part, the authors prove properties about the convergence and generalization of the algorithm. The algorithm is empirically evaluated on 15 real and 1 synthetic dataset and compared against private histograms and deconvolution.", "questions": "1. Does assumption 3.2 hold when considering decision trees that make discontinuous partitions?\n2. Does the proposed algorithm still outperform existing work when considering better privacy protection with $\\epsilon < 1$?\n3. Can the theoretical guarantees be applied to categorical data (where distances such as 'diam' do not make sense)?", "limitations": "The limitations are moved to the appendix with the only limitation discussed being assumption 3.3.\n\nDepending on the answer to question 1 I believe assumption 3.2 needs to be added to the limitations and a discussion on the choices of $\\epsilon$ should be added. The limitations should be given in the main text.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is written in clear English.\n- Substantial theoretical analysis.\n- Empirical evaluation on many (15) datasets shows that this method outperforms private histograms and deconvolution.\n- The effect of different hyperparameter settings was clearly explored.", "weaknesses": "Major:\n- Assumption 3.2 is key to deriving error bounds but I am unsure if this holds. Decision trees are discontinuous models that are often used to model discontinuous data.\n- Sections 2 and 3 are very dense in mathematical notation and use complicated phrasing to say simple things. E.g. section 2.2 spends a full page that is hard to read on explaining that: an estimated regression tree predicts the mean of samples in a leaf and that the private tree predicts it based on private estimates of reaching the leaf (U) and the sample value (Y), privatized using randomized response and Laplace mechanism.\n- Only relatively high values of $\\epsilon$ were explored. While it is debatable what is a good value, to the best of my knowledge $\\epsilon < 1$ is generally considered 'good privacy'.\n\nMinor:\n- Although I understand the 'max-edge partition with variance reduction' was introduced to prove theoretical properties it suffers from data that is non-uniformly distributed or contains useless features.\n    - Useless features: the algorithm will never choose the same feature to split on twice unless depth > d (as a result of splitting on the largest distance). This means that if there are few informative features these will be split on only once.\n    - Non-uniform data: the splits are determined on the midpoint between minimum and maximum values of a feature instead of looking at how data is distributed in the feature. This means data with e.g. long tails will cause a split to create one leaf with almost all data and one leaf with almost none.\n- The algorithm and analyses are based on continuous features but the datasets used for evaluation also contain categorical features. E.g. 'sex' in Abalone.\n- Limitations and broader impact have been moved to the appendix while these should be part of the main text.\n- The visualizations only show mean estimates, no standard deviations / standard errors.\n- It would be nice to compare to (global) differentially private decision trees to get an idea of the cost of decentralization in this task.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nQ1:\nAssumption 3.2 is key to deriving error bounds but I am unsure if this holds. Does assumption 3.2 hold when considering decision trees that make discontinuous partitions?\n\nA1: \nThe reviewer is correct. \nWe apologize for the misleading statement of Assumption 3.2. \nAssumption 3.2 is posed on the true regression function $f^*(x) = \\mathbb{E} [Y|X = x]$ instead of any regression function $f$.\nThus, the assumption is irrelevant to the fitted decision tree and holds for any estimator. \n\n    \nQ2: \nSections 2 and 3 are very dense in mathematical notation and use complicated phrasing. \n\nA2:\nWe apologize for the dense mathematical notations. \nThese definitions and writing flows (defining the population estimator and its empirical estimate) are broadly seen in nonparametric statistics. \nWe will revise to avoid complicated notations.\n\nQ3:\nOnly relatively high values of $\\varepsilon$ were explored.\n\nA3: Please see R1 in the global response. \n\n\nQ4: \nAlthough I understand the 'max-edge partition with variance reduction' was introduced to prove theoretical properties it suffers from data that is non-uniformly distributed or contains useless features. \n\n\nA4: \nWe thank the reviewer for the valuable and surprisingly insightful comment. \nIn practice, we find that the max-edge rule actually works well given certain preprocess procedures. \ni) uniformizing (for each feature, map the value of each sample to the empirical CDF). \nAfter uniformizing, the data is approximately uniformly distributed along each feature and the issue caused by non-uniformly distribution is legitimated. \nii) PCA/feature selection. The useless features can be eliminated by the dimension reduction technique. \nPCA is recommended. Feature selection may retain some binary features, when $p> 2d$, the binary features will be split twice, which is meaningless.  \n \n\n\nQ5: The algorithm and analyses are based on continuous features.\nCan the theoretical guarantees be applied to categorical data (where distances such as 'diam' do not make sense)? \n\nA5: \nIn the context of decision tree studies, this is a common gap between theory and experiment. \nThe theoretical framework applies only to continuous features. \nMeanwhile, decision trees are well suited for dealing with categorical features in practice. \n    \nQ6:\nLimitations and broader impact have been moved to the appendix while these should be part of the main text. \nThe limitations are moved to the appendix with the only limitation discussed being assumption 3.3.\nDepending on the answer to question 1 I believe assumption 3.2 needs to be added to the limitations and a discussion on the choices  \n should be added. The limitations should be given in the main text.\n\n\nA6:\nWe apologize for doing so due to page limitations. \nWe will add discussions about other assumptions as well. \n\n\nQ7: The visualizations only show mean estimates, no standard deviations / standard errors.\n\n\nA7: We will add the error bar to the figures as shown in the PDF.\nBut we do not have time to create well-presented figures for all experiments during rebuttal time. \n\nQ8: It would be nice to compare to (global) differentially private decision trees to get an idea of the cost of decentralization in this task.\n\nA8: \nTo the best of our knowledge, there is no existing private decision tree algorithm for regression. \nBut generally, central DP models perform much better than LDP models under the same privacy budget. \n\n\n\n\n\n\nQ9: Does the proposed algorithm still outperform existing work when considering better privacy protection with?\n\nA9: Yes, please see R1 and R3 in the global response. "}]

Author rebuttal:
We express our gratitude to the reviewers for their insightful questions and valuable comments. Reviewers are encouraged to refer to their individual rebuttals, where we direct them to the relevant sections in the text provided below. 

R1: We did not incorporate the results of $\varepsilon < 1$ due to the following two principal reasons:

1. Challenges in High Privacy Regime: The LDP nonparametric regression problem becomes particularly challenging in a high privacy regime. Consequently, model performances tend to resemble random noise, making them difficult to distinguish. When $\varepsilon < 1$, model performance degrades significantly, as shown in [4]. Additionally, nonparametric regression presents greater complexity compared to more commonly encountered LDP problems such as heavy hitters. Nonparametric regression involves estimating both the joint density and the marginal density, each utilizing a privacy budget of $\varepsilon / 2$. 

2. The mild privacy budgets $\varepsilon > 1$ meet practical needs. For instance, Apple conduct most tasks under $\varepsilon \geq 2$ [8]. Also, for LDP nonparametric regression, prior empirical studies have exclusively focused on scenarios where $\varepsilon > 1$ [5]. 

We do have the experimental results for the high privacy regime in R3.

R2: We summarize how the estimator benefits from public data, both theoretically and empirically. 

1. Theoretically, the advantages of LPDT lie in two aspects: i) LPDT allows the marginal density to be arbitrarily low with no truncation procedure. ii) LPDT eliminates the range parameter that appeared in the previous work [1,7]. This is not emphasized in the paper. The range parameter appears due to the unknown support $\mathcal{X}$. But with public data, we can min-max scale $X$ to $[0,1]^d$. With high probability, this is equivalent to working under known $\mathcal{X} = [0,1]^d$.  From a theoretical perspective, LPDT benefits from the public data through marginal distribution only.

2. Empirically, the labels of public data can boost performance by creating more informative partitions. When the regression function of $\mathrm{P}$ and $\mathrm{Q}$ are identical, LPDT creates similar partitions as in the non-private case. When the regression function of $\mathrm{P}$ and $\mathrm{Q}$ have similar trends but are distinct (e.g. when $Y$ are monotonic with respect to each $X$ in both $\mathrm{P}$ and $\mathrm{Q}$), the partition created on public data can be informative for private estimation. However, employing public data in the estimation process will result in asymptotically biased estimation. In cases where the regression function of $\mathrm{P}$ and $\mathrm{Q}$ are completely different, using public data to create partitions is non-informative.

3. Whether public data is advantageous or not can often be intuitively determined based on the data source. For example, a website might consider the data of users who willingly share their information as public data, as the behaviors of users who choose to share information or not are similar. Quantitatively determining whether a dataset can be utilized as public data can be of independent interest, as demonstrated by [6].

R3: The additional experiment results with tables and plots in the PDF.

1. Experiment 1: We replicate the same experiment outlined in Section 4.2 with two privacy parameters, namely $\varepsilon = 0.5$ and $\varepsilon = 1$. The results are shown in Table 1. Under high privacy constraints, both LPDT-M and LPDT-V consistently outperform their competitors. However, it's noteworthy that the performance of all models is worse than the optimal lower bound (decision tree) for $\varepsilon = 0.5$. For some results, the deviation from the optimal lower bound increases even by magnitudes. 

2. Experiment 2: We replicate the same experiment conducted on taxi data with $\varepsilon = 0.5, 1, 2$. The results are in Table 2. 
 As anticipated, the performance of LPDT is notably compromised for small $\varepsilon$ values. Specifically, when $\epsilon < 3$, the performance of LPDT is inferior to training a decision tree directly on public data. However, it's important to note that LPDT still demonstrates superior performance compared to other LDP methods.

3. Experiment 3: We replicate the privacy utility trade-off experiment on the synthetic dataset with extended privacy regime $\varepsilon = 0.5, 1, 2$. The results are in Figure 1(a). In the high privacy regime, LPDT, PHIST, and APHIST exhibit comparable performance.

4. Experiment 4: We conduct experiments to show the utility gain brought by public data. We take red wine data as an example. With $n_q = 100$ public data, we run LPDT (with $D^{\mathrm{P}}$) and PHIST (without $D^{\mathrm{P}}$). For $\delta \in \{0.2, 0.4, 0.6, 0.8,1\}$, we train each model on $\delta \cdot n$ samples with 20 repetations. The result is in Figure 1(b). PHIST with ~1,100 samples achieves the same MSE as LPDT with ~660 samples. The result shows that, with a small amount of public data, LPDT achieves the same performance with much fewer samples. 

[1] Thomas B Berrett et all. Strongly universally consistent nonparametric regression and classification with privatised data. 2021.

[2] T Tony Cai et al. Transfer learning for nonparametric regression: Non-asymptotic minimax analysis and adaptive procedure. 2022.

[3] T Tony Cai et al. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. 2021.

[4] John C Duchi et al. Minimax optimal procedures for locally private estimation. 2018.

[5] Farhad Farokhi. Deconvoluting kernel density estimation and regression for locally differentially private data. 2020.

[6] Xin Gu et al. Choosing public datasets for private machine learning via gradient subspace distance. 2023.

[7] László Györfi et al. On rate optimal private regression under local differential privacy. 2022.

[8] Apple Inc. Differential privacy technical overview. Technical Report Apple Inc., 2017.

Meta-review: Reviewers remained mum during the discussion, so I took a look at the reviews and responses myself. It seems like most of the weaknesses identified by reviewers were comparatively minor, and the authors did more experiments for some of the gaps identified by the reviewers. These additional results and experiments should appear in the final paper. Overall, since all reviewers generally had a positive sentiment, this paper is appropriate for publication at NeurIPS.
Decision: Accept (poster)