Binary Classification under Local Label Differential Privacy Using Randomized Response Mechanisms
Authors: Shirong Xu
Chendi Wang
Will Wei Sun
Guang Cheng
Venue: Accepted by TMLR ()

Abstract: Label differential privacy is a popular branch of $\epsilon$-differential privacy for protecting labels in training datasets with non-private features. In this paper, we study the generalization performance of a binary classifier trained on a dataset privatized under the label differential privacy achieved by the randomized response mechanism. Particularly, we establish minimax lower bounds for the excess risks of the deep neural network plug-in classifier, theoretically quantifying how privacy guarantee $\epsilon$ affects its generalization performance. Our theoretical result shows: (1) the randomized response mechanism slows down the convergence of excess risk by lessening the multiplicative constant term compared with the non-private case $(\epsilon=\infty)$; (2) as $\epsilon$ decreases, the optimal structure of the neural network should be smaller for better generalization performance; (3) the convergence of its excess risk is guaranteed even if $\epsilon$ is adaptive to the size of training sample $n$ at a rate slower than $O(n^{-1/2})$. Our theoretical results are validated by extensive simulated examples and two real applications.

Published in Transactions on Machine Learning Research (10/2023)
Binary Classification under Local Label Differential Privacy Using Randomized Response Mechanisms
Shirong Xu
shirong@sttat. ucla
Deportment of Statistics and Data Science University of California, Los Angeles
Chendi Wang
chendi@hoharton.upeee wpw.eaarrrtoooooonoooommmmmmmme edu
Department Statistics and Dala Science University of Pennsylania
Will Wei Sun
sun2440purdue.ccm edu
Daniets School of Business
Purdue University
Guang Cheng
guangcheng@uucee edu
Department of Statistics and Data Science Universily of California, Los Angeles
Reviewed on OpenReview: https: // // openreview. net/ bet/forree forum? id= uXCGOu9bGG
Abstract
Label differential privacy is a popular branch e-differential privacy for protecting labels training datasets with non-private features. In this paper, we study the generalization performance of a binary classifier trained on dataset privatized under the label differential privacy achieved by the randomized response mechanism. Particularly, establish minimax lower bounds for the excess risks of the deep neural network plug-in classifier, theoretically quantifying how privacy guarantee affects its generalization performance. Our thcoretical result shows: (1) the randomized response mechanism slows down the convergence of excess risk by lessening the multiplicative constant term compared with the non-private case (e = oo); (2) as decreases, the optimal structure of the neural network should be smaller for better generalization performance; (3) the convergence of its excess risk is guaranteed even if is adaptive to the size of training sample rate slower than 0ln-1/2). Our theoretical results are validated by extensive simulated examples and two real applications.
1 Introduction
In the past decade, differential privacy (DP; Dwork 2008) has emerged as a standard statistical framework to protect sensitive data before releasing it to an external party. The rationale behind DP is to ensure that information obtained by an external party robust enough to the change of a single record a dataset.. Generally, the privacy protection via DP inevitably distorts the raw data and hence reduces data utility for downstream learning tasks (Alvim et al.) 2012. Kairouz al. 2016 Li et al.) 2023a). To achieve better privacy-utility tradeoff, various research efforts have been devoted to analyzing the effect of DP on learning algorithms in the machine lcarning community (Ghazi et al.) 2002 Bassily et al. 2022 Esfandiari et al. 2022). Depending on whether the data receiver is trusted or not, differential privacy can be calegorized inlo two main classes in the literature, including central differential privacy (central DP: Erlingsson et al. 2019 Girgis al. 2021 Wang al. 2023) and local differential privacy (local DP; Wang et al. 2017 Arachchige et al. 20119). Central DP relies on trusted curator to protect all data simultancously, whereas local DP perturbs data the users' side. Local DP becomes a more popular solution to privacy protection due to its

---

Published in Transactions on Machine Learning Research (10/2023)
successful applications, including Google Chrome browser (Erlingsson et al. 2014 and macOS Tang et al. 2017).
An important variant of differential privacy is label differential privacy (Label DP; Chaudhuri & Hsu 2011 which is a relaxation of DP for some real-life scenarios where input features are assumed to be publicly available and labels are highly sensitive and should be protected. Tabel DP has been gaining increasing at- tention in recent years due to the emerging demands in some real applications. For example, in recommender systems, users' ratings are sensitive for revealing users' preferences that can be utilized for advertising pur- poses (MeSherry & Mironov 2009 Xin & Jaakkola, 2014 In online advertising, user click behavior is usually treated as a sensitive label whereas the product description for the displayed advertisement is pub- licly available (McMahan et al.) 2013: Chapelle et al. 2014). These real scenarios motivate various research efforts to develop mechanisms for achieving label differential privacy and understanding the fundamental tradcoff between data utility and privacy protection. In literature, label DP can be divided into two main classes depending on whether labels are protected in a local or central manner. In central label DP, privacy protection is guaranteed by ensuring the outpul of randomized learning algorithm is robust to the change of single label in the dataset (Chaudhuri & Hsu 2011 Ghazi et al. 2021 Bassily et al. 2022 Ghazi et al. 2023 In local label DP, labels are altered at the users' side before they are released to learning algorithms. ensuring that it is difficult to infer the true labels based on the released labels Cunningham et al. 2022
Fekete et al. 2021
In the literature, various efforts has been devoted to developing mechanisms to achieve label DP efficiently and analyze their essential privacy-utility tradeoffs in downstream learning tasks. The original way
achieve label DP is via randomized response mechanisms (Warner 1965). ) which alters observed labels in
probabilistic manner. For binary labels, the randomized response mechanism flips labels onto the other
side with a pre-determined probability (Nayak & Adeshiyan 2009 Wang et al.)
2016b
Busa-Fekete et al.
2021). Originally designed to safeguard individuals' responses in surveys (Warner
1965
Blair et al. 2015
the RR mochanism has found extensive data collection applications (Wang et al.
2016b).
such as pairwise
comparisons in ranking data (Li et al., 2023bb and edges in graph data (Hehir el al.
2022 Guo el al.) 2023
Ghazi et al. (2021) proposed a multi-stage training algorithm called randomized response with prior, which flips training labels via prior distribution learned by the trained model in the previous stage. Such multi-stage training algorithm significantly improves the generalization performance of the trained model under the same privacy guarantee. Malek Esmacili et al. (2021) | proposed to apply Laplace noise addition to one-hot encodings of labels and utilized the iterative Bayesian inference to de-noise the outputs of the privacy- preserving mochanism. Bassily et al. (2022) developed a private learning algorithm under the contral label DP and established a dimensson-indepeedeen deviation margin bound for the generalization performance of several differentially private classifiers, showing that the margin guarantees that are independent of the input dimension. However, their developed learning algorithm relies on the partition of the hypothesis and is hence computationally inefficient. The current state-of-the-ar approach, outlined in Ghazi et al. (2023) presents a variant of RR that incorporates additional information from the loss function to enhance model performance. Analyzing this variant can be challenging due to its construction involving the solution of an optimization problem without a closed-form represenlation.
A critical challenge in differential privacy is to understand the essential privacy-utility tradeoff that sheds light on the fundamental utility limit for specific problem. For example, Wang & Xu (2019) studied the sparse linear regression problem under local label DP and establish the minimax risk for the estimation error under label DP. In this paper, we intend to study the generalization performance of binary classifiers satisfying cllocal label DP, aiming to thcoretically understand how the generalization performance of differentially private classifiers are affected by the local label DP under the margin assumption [Tsybakov] 2004). To this end, we consider the local label DP via the randomized response mechanism due to its remarkable ability to incurring less utility loss (Wang et al. 2016b). Specifically, Wang et al. (2016b) demonstrated that, while adhering to the same privacy standard, the RR mechanism exhibits smaller expected mean square errors between released and actual values compared to the Laplace mechanism. Furthermore, the effectiveness of the RR mechanism surpasses that of the output perturbation approach, particularly in scenarios where the sensitivity of output functions is high. This result can be explained from the perspective of statistical hypothesis testing that the RR mechanism achieves the optimal tradeoff between type I and type II errors
2

---

Published in Transactions on Machine Learning Research (10/2023)
under e-label DP (Dong et al. 2022). Additionally, the RR mechanism has succinct representation, which allows us to develop certain theories related to deep learning.
In literature, few attempts are made to theoretically quantify the generalization performance of classifiers under local label DP even though binary classification has already become an indispensable part of the machine learning community. An important characteristic distinguishing binary classification problem is that the convergence of the generalization performance depends on the behavior of data in the vicinity of the decision boundary, which is known the margin assumption [Tsybakov] 2004). Therefore, our first contribution is that theoretically quantify how local label DP alters the margin assumption, which allows us to bridge the connection between the local label DP and the generalization performance. Additionally, we mainly consider two scenarios for the function class of classifiers in this paper. First, we consider the large margin classifier with its hypothesis space being a parametric function class and the deep neural network plug-in classifier. For these two scenarios, we establish their upper bound and the minimax lower bound for their excess risks, which theoretically quantifics how affects the gencralization performance. The implications of our theoretical results are three-fold. First, the Bayes classifier stays invariant to the randomized response mechanism with any small e, which permits the possibility of learning the optimal classifier from the privatized dataset. Second, the local label DP achieved via the randomized response mechanism implicitly reduces the information for estimation. Specifically, we theoretically prove that the convergence rate of excess risk is slowed down with an additional multiplicative constant depending on c. Third, based on our theoretical results, we show that the excess risk fails to converge when the e adaptive to the training sample size n the order O(n (1/)), which is independent of the margin assumption. To the best of our knowledge, existing literature related classification under DP or corrupted labels (Cannings et al., 2020 van Rooyen & Williamson 2018) has investigated the effects of noise neural network structures. Our theoretical results are supported by extensive simulations and two real applications.
The rest of this paper is organized as follows. After introducing some necessary notations in Section 1.1 Scction 2 introduces the backgrounds the binary classification problem, neural network, and the local label differential privacy. In Section 3 we introduce the framework of the differentially private learning under the label differential privacy and present theoretical results regarding the asymptotic behavior of the differentially private classifier. Section quantifics how affects the generalization performance of the deep neural network plug-in classifier by establishing minimax lower bound. Section 5 and Section G conduct series of simulations and real applications support our theoretical results. All technical proofs are provided in the Appendix.
1.1 Notation
For vector æ RP, we denote its lı-norm and 12-norm as ||>||| = Ei |aral and ||ж|| = (2 1 1/2 respectively. For a function f: X' + R, we denote its Lp-norm with respect to the probability measure μ [Ifl = (Jx (d()))))(())) 1/v 1/2 For a real number a, we let |a] denote the largest integer not larger than a. For a set S. we define S. |I Il) as the minimal number of b-balls needed to cover S under a generic metric || ||. For two given sequences (An)xeN and {Ba MeN, we write An 2 Bn if there exists a constant C> >>0 such that An 2 CBn for any n N. Additionally, we write An Bn if An 2 Bn and An S Bn.
2 Preliminaries
2.1 Binary Classification
The goal in binary classification is to learn a discriminant function S, which well characterizes the functional relationship between the feature vector X X and its associated label Y e [-1,1]. To measure the quality of f, the 0-1 risk is usually employed,
R(f) = E (1((x)) - (f(sig((((() #Y)
where I(-) denotes the indicator function and the expectation taken with respect to the joint distribution of (X,Y).
3

---

Published in Transactions on Machine Learning Research (10/2023)
In addition to 0-1 loss, the false negative error (FNE) and false positive error (FPE) are frequently used to assess classifier performance when dealing with highly imbalanced datasets. Specifically, FNE measures the percentage of positive samples being classified as negative, whereas FPE measures the percentage of negative samples being classified as positive. For a margin classifier f, the expected false positive error (EFNE) and false iositive error (EFPE) are written as
EFNE()) =  (T((( < -1) -1p= =P)=pssig(((())) + xY
EFPE()) - IE (I(1(X) > 0)\2 - =11 = - s # E1Y = - -1).
Furthermore, the 0-1 risk R(J) can be re-written as weighted combination of EFNE and EFPE:
R(F)= EFNE(D)(Y =1 BFPE())(( =-1).
Let =iifff R(f) denote the minimizer of R(f), which refers to as the Bayes docision rule. Generally, f is obtained by minimizing R()) in point-wise manner and given as [*(X) sign (nn( - 1/2) with nx() P(Y = x) The minimal risk R()*) can be written as R( = Ex min - (X))) In practico, the underlying joint distribution on (X unavailable, but set of i..d. realizations D {(x; }=)
is given. Therefore, it is a common practice to consider the estimation procedure based on minimizing the sample average of surrogate loss, which is given as
R = 1 n Σ (f(()))))
where (6-) is the surrogate loss function replacing the 0-1 loss since the 0-1 loss is computationally intractable (Arora et al. 1997).
Let (f) = (()(((x))) denote the d-risk. Given that & classification calibrated, the minimizer
fo arg migmingaa R.g consistent with the Bayes decision rule (Lin 2004),, i.e., sign sign(n (1/
for any x E X. In literature, there are various clasifiiationn-ciiireeee loss functions
Zhang 2004 Bartlett
ct al. 2006); such exponential loss, hinge loss, logistic loss, and gi-loss (Shen et al. 2003
2.2
Deep Neural Network and Function Class
Let f(x; O) be an L-layer neural network with Rectified Lincar Unit (RcLU) activation function, that is,
f(x; 6) A h (.....(x)))) bL+1,
where o denotes function composition, h((x) = o(Aiz + by) denotes the 1-th layer, and O {
denotes all the parameters. Here A, E RRX is the weight matrix, by E R& is the bias term, Pt is the number of neurons in the 1-th layer, and axx) = max(0, is the ReLU function. To characterize the network architecture of f, we denote the number of layers in θ as T(O), the maximum number of nodes as A()), the number of non-zero parameters as ||O]|o, the largest absolute value in θ as |0]| For a given n, we denote by FNN (Iny Nn, Pny BnG Vn) a class neural networks, which is defined as
FNN FNN, Na, Pay Br, Vn) [[( θ) T(0) < Ln, A(O) S N..
|O||o < P.. ||||| x S B,, || S Vn.).
Let B 3>0 0 be degree of smoothness, then the Hölder space is defined as H(B, x) (f e Cla [|fll < co).
where (2)) the class of [8] times continuously differentiable functions the open set X and the Hölder norm [[fll((())))) is given as
Jmm f(x) ym f(y)
max sup 1hth f(*)(())+ [lfll m: milmm [ øE
+ m: m l [=
max
sup
|
-
8
4

---

Published in Transactions on Machine Learning Research (10/2023)
where 8m f(x) am
Dur u (z) denotes the partial derivative of order with respect to and (,.,...,, mp) No multi-index with No No {0). Further, we let H(B X M) (/ H(3,
[[))) I 3 be closed ball of radius M in X)).
The Hölder assumption serves as common assumption for studying the generalization capabilities of neural networks for approximating functions possessing à certain degree of smoothness or regularity (Audibert & Tsybakov, 2007 Kim et al. 2021.. This assumption is useful in developing a tighter generalization bounds. However, is essential to acknowledge that the Hölder assumption presupposes a level of smoothness in the underlying function. In reality, many real-world problems involve functions that deviate from this idealized smoothness. When the actual smoothness of the function does not align with the assumption, algorithms reliant on it may fall short of the anticipated generalization performance.
2.3 Local Label Differential Privacy
Label differential privacy (Label DP; Chaudhuri & Hsu 2011 is proposed as a relaxation of differential privacy (Dwork) 2008), aiming to protect the privacy of labels in the dataset, whereas training features are non-sensitive and hence publicly available. An effective approach to label DP is the randomized response mechanism [Busa-Fekete et al., 2021p. As its name suggests, it protects the privacy of labels via some local randomized response mechanisms under the framework of local differential privacy.
Definition 1. (Label Differential Privacy: Ghazi et al. 20211 A randomized training algorithm A taking imput dataset is said to be (c, (label differentially private if for any two datasets D and D' that differ in the label of single ezample, and for any subset S of the outputs of A, it is the case that ((A(D) E S) s eTP((A(D)) E S) + 8, then A is said to be e-label differentially privale (e-label DP).
A direct way to achieve c-Label DP in binary classification is to employ the randomized response mechanism (Warner 1965 Nayak & Adeshiyan 2009 Wang et al.) 2016b Karwa et al. 2017). The main idea of the binary randomized response mechanism is to flip observed labels indepdently with a fixed probability. Specifically, let As denote the randomized response mechanism parametrized by 0. For an input label Y, we define
Y, -Y, with probability 1 A
with probability 0,
Ao
where 0 > 1/2 denotes the probability that the value of Y stays unchanged. It is straightforward to verify that the randomized response mechanism satisfics cllbbel DP with c = log(#/(1 - 0)) (Ghazi et al.] 2021 Busa-Leekete et al. 2021 In this paper, we denote the e-label DP achieved through the randomized response mechanism as e-local label DP.
3
Differentially Private Learning
3.1 Effect of Locally-Label Differential Privacy
Under the setting of local differential privacy, users do not trust the data curator and hence privatize their sensitive data via some randomized mechanisms locally before releasing them to central servers. We let D = ((), 91 denote the original dataset containing n i.i.d. realizations of the random pair (X, Y). As illustrated in Figure [ users' labels are privatized by locally differentially private protocol Ag, and then the untrusted curator receives a privatized dataset, which we denote D {(x,, 7:)
A natural question is what the quantitative relation between c-label DP and the discrepancy between the distributions of DD and D is. This is useful to analyze how privacy parameter e deteriorates the utility of data for downstream learning tasks.
Notice that J. are generated locally and independently, therefore the randomized response mechanism only alters the conditional distribution of given X, whereas the marginal distribution of X stays unchanged. Hence, assume D is a set of i.i.d. realizations of (X,Y) Y), and it is straightforward to verify that the
5

---

Published in Transactions on Machine Learning Research (10/2023)
(i,,)s)
(1)
User
(x
Untrusted Doto Curator
User
(c)
Dbar
Figure 1: The framework of local label differential privacy.
conditional distribution of y given X = x can be written as
(xx) P(Y X = x) = 0n(a)) + (1 (1-0)(1 17(x))
Clearly, Ag amplifies the uncertainty the observed labels by shrinking 7)xx) towards 1/2. Particularly, ((X) = 1/2 almost surely when 0 = 1/2. In this case, the privatized dataset D conveys no information for learning the decision function.
The following Lemma quantifies how the randomized response mechanism alters the conditional distribution of Y and Y given the feature x via the Kullback-Leibler divergence (KL) divergence between these two Bernoulli distributions. Specifically, the inequalities in 1 explicates how the divergence changes with privacy guarantee e.
Lemma 1. Suppose the randomized response mechanism Y AY) satisfies c-label DP with 0 cxp(c)/(1+ exp(t)), then for any X il holds that
a(e, S DKL. (PrIx== Py PrIx=m) S u((e,a),
(1)
where DKL. (Py|xxx B prx==)) denoles the Kullback-Leibler divergence (KL) divergence between pyxx== and Py|x=n: L(e,z) = (x) - 11 exp(c))=2 and u(e,z) min (c, x), U2(c, with (1
(2n(1:) - 1) -
(1x()))))))))))))))))))))))))))) -1x=)) exp(e)) and U2(e, = (2n(2) - 1)3 exp((e)
In Lemma 1 the lower bound L(e, ar) and the upper bound l1(c, .) share a factor (1 + +xx((-c))2 indicating that (K IP ) decreases exponentially with respect to e.
3.2
Differentially Private Classifier
On the side of the untrusted curator, inference tasks vary according to the purpose of data collector, such estimation of population statistics (Joseph et al.) 2018 Yan et al., 2019) and supervised learning (Ghazi
et al. 2021 Esfandiari et al. 2022). In this paper, we suppose that the computation based on D implemented by the untrusted curator is formulated as the following regularized empirical risk minimization task,
min Ln) = min Σ (ff(:))))) + J()(
(2)
JEF
JEF n
where is a surrogate loss, An is a tuning parameter, J(-) is a penalty term, and F is a pre-specified hypothesis space.
We denote by R(F) (()) + Y] the risk with expectation taken with respect to the joint distribu- tion of (x, 8) and let f = arg min, R(f) denote the Bayes decision rule under the distribution of (X, Y). The excess risk of ʃ under the distributions of (X,Y) Y) and (X,Y) denoted as D(S.S*) R(J) R(S*)
and D(f.F*) R(f)- - R(F*), respectively.
Lemma 2. Y (Y with 0 > 1/2, then f*(x) (xx) for any X and D(J (20-1)D(f.f) for any

---

Published in Transactions on Machine Learning Research (10/2023)
Lemma 2 shows that the Bayes decision rule stays invariant under the randomized response mechanism. It is clear to see that D*) diminishes as 0 gets close to 1/2. Particularly, D( is equal to 0 when 0 = 1/2. This is as expected since 0 = 1122 implies that (x)) 1/2 almost surely, where all classifiers deteriorates in performance simultancously. This result demonstrates that the optimal classifiers for the underlying distributions of and D are identical. Basically, Lemma 2 reveals an inherent debiasing process in the development of the generalization performance of the differentially private classifier f. To be more specific, we can deduce the excess risk of f by the relation R(j) R(f*) _ (R(f) R((*)) under e-local label DP.
Let f3 = arg m (f) and f3 arg arg miny Rf(F) be the minimizers of ø-risk under the joint distributions of (X and (X,Y), Y), respectively. For illustration, we only consider hinge loss xxx) = max (1 x; 0} in this paper, and similar results can be easily obtained for other loss functions by the comparison theorem
Bartlett et al.
2006 Bartlett & Wegkamp 2008). With ((.) being the hinge loss, we have / = S = -
Bartlett al. 2006 Lecue 2007]] With a slight abuse of notation, we use f to refer these four functions
simultancously in the sequel.
3.3 Consistency under the Randomized Response Mechanism
In this section, we establish the asymptotic behavior the classifier trained on privatized datasets. Specif- ically, we theoretically quantify how the randomized response mechanism affects the convergence rate of excess risk under the low-noise assumption (Lecué 2007).
We suppose that the randomized response mechanism satisfies the e-label DP, which indicates that log(0/(1 0)). Furthermore, we denote that fr. arg min L (f) and H(f.f*) = Ro(f) - R&(f"). In classification problems, (ff,f") is an important metric that admits the decomposition into the estimation error and the approximation error (Bartlett et al., 2006
H(S = HJ, + H*),
where f+= arg min fer (f). Here (ff is the estimation error and Hff,, f*) is the approximation error. The estimation error depends on the learning algorithm in finding f3 based on a dataset with finite
samples, where the searching difficulty is unavoidably affected by the complexity of F as the approximation error. Generally, the richness of F can be measured by VC dimension (Blumer et al.] 1989 Vapnik &
Chervonenkis 2015), Rademacher complexity (Bartlett & Mendelson 2002 Smale & Zhou 2003). and
metric entropy methods {Zhoul 2002, Shaley-Shwartz & Ben-David 2014].
Assumption 1. (Low-noise assumption) There ezists constant e and 7 S to0 such that P (((2((X) 11 S ct",, for any e [0. 1).
Assumption is known as the low-noise assumption in the binary classification (Lecué 2007 Shen et al.,
2003 Bartlett et al.) 2006), which characterizes the behavior of 27(x) - 1 around the decision boundary (xx)
1/2. Particularly, the case with too and c implics that the labels yi's are deterministic in that n n(X) takes values in {0, 1} almost surely, resulting in the fastest convergence rate of the estimation error.
Lemma 3. Denote that K. = (e" - 1)/(ee + +1). Under Assumption for any O E (1/2, 1], it holds that
(1) (12 S sox for any E 10,1),
(2) Ro(f) Ro( - ne (4c) 1/7 E -
fx)]
for any fEF,
Lemma 3 presents some insights regarding the influence of the randomized response mechanism on the low- noise assumption and the margin relation (Locué, 2007]. showing that the low-noise structure and margin relation are both invariant the randomized response mechanism in the sense that only the multiplicative terms are enlarged by the effect of the privacy guarantee e.

---

Published in Transactions on Machine Learning Research (10/2023)
Assumption 2.
We assume that F is properly chosen satisfying that lIfll S 1 for any F and log 1og.N(g,FF11 (()())) (i( log(1 + + (2()),, and (C(=))=>11
(g((f())) = 1} FEJ), VC(GF) denotes the VC dimension of GF, denotes the marginal distribution of X, θ denotes the parameters of f, and (1(@) and V2(O) are some functions de- pending on O.
where
Assumption 2 characterizes the complexity function class F through the metric entropy (Zhou 2002 Bousquet et al. 2003 Lei et al.] (016)), where (e) and V2(+) are quantities increasing with the size of O. Assumption generally holds for function classes of parametric models (Wang al. 2016a [u et al.
2021), most notably for deep neural networks (Bartlett et al. 2019 Schmidt-Hieber 2020). Additionally,
Assumption also holds for those VC classes with VC dimensions increasing with the size of Q (Wellner
ct al. 2013 Bartlett et al. 2019 Lee et al. 1994).
Thcorem 1. Under Assumptions and for any minimizer Fn of 22, there exist some positive constants
A and A2 such that.
A
(1) nR?
1+1
sup [x[ - s { =EP,
(1(()) log(n)
+ Tn
+ sn
nn?
where Py be a class of distributions of (X,Y) salisfying Assumplion 1 8n suPREP, inF H(,,'), and Tn = SuPREP, jer f*).
Theorem quantifies the asymptotic behavior of Fm by establishing its upper and lower bounds, which explicitly demonstrates the quantitative relation between the effect of privacy guarantee and the excess risk. The upper bound is proven through uniform concentration incquality under the framework of empirical risk minimization analysis. The estimator Jn is derived from pre-specified function class F that may not include the true underlying function f". Consequently, šn represents the approximation error, quantifying the capability the optimal function within F to approximate f* The accuracy of ostimating the optimal function in FF for approximating f depends on the complexity of F (Assumption 2 and the size of the training set n. A larger F may reduce 8n but can increase the estimation error. Thus, achieving the best convergence rate involves striking the right balance between these two sources of error. The proof of the lower bound is similar to Theorem 2 in Lecué (2007), mainly applying the Assouad's lemma YYul 1997) to analytic subset of Py. Further details regarding the proof are provided in the Appendix.
It is worth noting that the upper bound matches the lower bound except for a logarithmic factor when the
approximation error term 8n S
7+2 This shows that the randomized response mechanism slows
down the convergence rate by enlarging the multiplicative constant. Moreover, based on Theorem D we obtain the optimal convergence rate of the excess risk in classification problem under the low-noise assumption (Lecué 2007) by setting
and [F| X0. Lemma 4. Denote that M max{ (EFNE(f) EFNE(F"), EFPE()) - EFPE(F") Under Assumption for any margin classifier J, it holds that
2c (2c-tHe R() -RJ)) < MS (Pi P(Y -1)3
1
R() - -R(M),
(3)
where e and 7 are as defoned in Assumplion maryin classifier f. ( becomes
Porticularly, if Assumplion holds with 7 00, for any
3 R()) -R) 2 m (P(Y P), = -1) (R())
Lemma Jestablishes a crucial relationship between excess risk and the maximum of excess EFNE and EFPE for any classifier f, which also includes as special case. This connection enables us to demonstrate the convergence of EFNE(J.) and EFPF((,) based on that of the excess risk. Remarkably, this finding
betwee
8

---

Published in Transactions on Machine Learning Research (10/2023)
implies that the differentially private classifier fn will exhibit similar false negative and false positive rates to those of the Bayes classifier as the sample size tends to infinity. In addition, increasing the degree of data imbalance will enlarge the upper bound in (3), indicating that data imbalance slows down the convergence rates of EF) and EF)E(F.). Particularly, under the low-noise assumption with y oo, which implies that samples are separable, both excess EFNE and EFPE of fn exhibit the same convergence rate as the excess risk regardless of the degree of class imbalance. Furthermore, this result. indicates that the privacy guarantee has similar impact on the excess EFNE and EFPE as it does on the excess risk.
4 Deep Learning with Local Label Differential Privacy
A typical class of models that are popularly considered in the domain of differential privacy is deep neural network GGaazi et al. 2021 Yuan et al. 2021) due to its success in various applications in the past decade. Unlike Section 3.3 considering the estimation and approximation errors separately, we establish theoretical results regarding the convergence rate of the excess risk of the deep neural network plug-in classifier trained from D, which is obtained by making tradcoff between the estimation and approximation errors of deep neural nelworks (Schmidt-Hieber 2020). Our theoretical results not only quantify how the optimal structure of the deep neural network changes with the privacy parameter e, but also derive the optimal privacy guarantee we can achieve for the deep neural network classifier.
Remind that D = {< 0.)) is the privatized dataset with To An(vs) and 0 = exp(e)/(1 + exp(c)). The deep neural network is solved as
Frm = arg min
(f(z)) =
(4)
(L.
where 7, = +0;+1)/2 and FNN (Ln, (Ln B., V,,) The plug-in classifier based on fan can be obtained 8nn sign(fmn 1/2). To quantify the asymptotic behavior of Snn, we further assume that the support of x is 1]", which is common assumption for deep neural networks (Yrrotsky 2017 Nakada & Imaizumi 2020
is a class of multilayer perceptrons defined in Section 2.2
Theorem 2. Let PT.3 be a class of probability mensures on X' x [-1,1} satisfying Assumption and
(x() H(B, 1],, M). For any minimizer Fun in (A) with L,, log(ken/ log(n)), Nn (sen2/ log(n)
B, = 1, and Pa x Nn log(n.n/ (n)n//oo(())) we have
Bis+21+P
+1)
- sup E, [2[[((nm) R(f*)] 2
log n nkk
20(++1) 20(++2=-((52))
(5)
n
*EP
Porticularly, supaeP,, E [((mn)) R( = o(1) given that e Z n 1/245 for any ( > 0.
In Theorem 2 we quantify the asymptotic behavior of the excess risk of oun by providing upper and lower bounds for suP [ Similar to Theorem 1 the proof of the lower bound of d5) relies on the Assouad's 's lemma. A significant distinction of the upper bound in (5) from that of Theorem is explicating the approximation error sn with respect to the structure of neural network and making the optimal tradeoff between estimation and approximation errors to achieve the fastest convergence rate. should be noted that if oc which refers to the non-private case, the upper and lower bounds in (5) match with existing theoretical results established in Audibert & Tsybakov (2007). Moreover, Theorem 2 goes step further by
precisely characterizing the impact of on the convergence of 5nm to the Bayes decision rule. Additionally, it specifies how the optimal neural network's structure contracts c decreases, crucial for achieving the fastest convergence rate. Specifically, altaining this rapid convergence necessitates reducing the maximum number of hidden units at an order of ((2r/(88t)) when compared to the non-private case. Furthermore, we leverage Theorem 2 to derive the fastest adaptive rate of c under the consistency of _nn- Specifically, we find that e - n 11/++c for any Ç <>0 to achieve this desired consistency rate. This result represents a crucial step towards understanding the interplay between privacy and performance in our framework.
9

---

Published in Transactions on Machine Learning Research (10/2023)
5 Simulated Experiments
This section aims to validate our theoretical results through extensive simulated examples. Specifically, we show that the excess risk of a differentially private classifier converges to 0 for any fixed whereas the convergence is not achievable as long as is adaptive to the size the training dataset with some properly
chosen orders as shown in Theorems 1 and 2
5.1 Support Vector Machine
This simulation experimentally analyzes the effect of label DP on the SVM classifier. The generation of simulated datasets is as follows. First, we set the regression function in classification as n(x) 1/(1 + exp(-8% æ)), where Bg E R' and a are both p-dimensional vectors generated via 9oo, H; ~ Unif( - 1) for ......p. For each feature æ, its label y is chosen from {1, [1. with probabilities n)x) and
())), respectively. Repeating the above process n times, we obtain a non-private training dataset D {a;, y4) 1=)) Subsequently, apply the randomized response mechanism to generate Y: y/ = Ao(y:) where 0 = exp(e)/(1 + exp(e)) and is the privacy guarantee. Therefore, the obtained privatized training dataset
D (( R= satisfies e-Label DP. Based D, we obtain the SVM classifier (Cortes & Vapnik 1995).
1 n E (1-0,88aa x;)+ -T--) + 11
Jn arg min
B n
where (x) = max 0}. Next, we evaluate the performance of Fn in terms of the empirical excess risk and the classification error,
Neeat
B(Fr)=
(sign((r((()) sigu(n(a{) 1/2)) (2n(x)) 1/.
Theet
Meest
CE((M)=
(sigu(Fn sign(n((x)) 1/2))
Teant
where w/'s are testing samples generated in the same way as x.'s.
Scenario I. In the first scenario, we aim to verify that ((F) will converge to 0 as sample size increases when the privacy parameter is a fixed constant. To this end, we consider cases (n, = {100 x 2', 0.1 8} x {1, 2, o.).
Scenario II. In the second scenario, we explore the asymptotic behavior of B(Fa) with adaptive to the sample size n. Specifically, we set < 5 and consider cases (n, () = {100 x 2 i = 0, 1,....8) 8) x (1/5, /3, 1/2,2/3, 1}. We also include the worst case e = as a baseline.
112 the dividing line between whether not the excess risk converges. To this end, we consider three kinds of adaptive c, including n 1/2 x log(n))-1/2, and 6 = log (m)m-111 The size of 'D is set as (100 x 3 i 0, 0,.,. , For all cases, we report the averaged empirical excess risk in 1,000 replications as well as their 95% confidence intervals.
Scenario III. In the third scenario, we intend verify that
For Scenario and Scenario II, we report the averaged empirical excess risk and the classification error in 1, 1,000 replications for each setting in Figure 2 and Figure 3 respectively. From the left panel of Figure 2 we can see that the empirical excess risks and the classification errors with fixed c converge to 0 regardless of the value of e, showing that the randomized response mechanism with fixed fails prevent the third party from learning the optimal classifier based on D. Moreover, estimated excess risks present decreasing pattern as the sample size increases, whercas that of the case Ç deteriorates steadily and the curve finally overlaps with that of the worst case = 0. It is also interesting to observe that the curve of ( = 1/2 remains unaffected by the sample size. All these phenomenons are in accordance with the results of Theorem
seen from Figure 3 when Ç 1/2 the
As can be seen in Figure 4 the curve of the case e x 112 remains unchanged as sample size increases as in Scenario II. This is due to the offset of information gain yielded by increasing the sample size and the
10

---

Published in Transactions on Machine Learning Research (10/2023)
0.30
Canuioatio Fraloo Citecciiaa Cal
Empriical Elccos Rick 866
0.05
0.20
0.34
8.00
0.15
6.20
The treining biat stalic (agple(300)
The training aus log stale 201
Figure 2: The averaged classification errors (Left) and averaged empirical excess risks (Right) of settings with Neett 50, 000 in Scenario I.
1.3
(-1
C-1/4
0.10
0.8
(-1/3
6.14
Closoitation Eror CETA
Emoiica Exccus Rick
[-]
0.8
0.00
0.2
0.34
0.0
The braning s28 on log scale Ioc,1102000
The traiiing 50e on log scale 100.0111000
Figure 3: The averaged classification errors (Left) and averaged empirical excess risks (Right) of all settings with Dest 50, 000 in Scenario IT.
tin
C-n
Caloglatett
0.8
Moin 12
Voin
30
Clazs Rozsencennni Dron C333
6-0
Empitcaal ExcoS B63
6.12
C-
0.6
0.4
0.00
5.
The beining size on log scale logo0100000
The baining size on scale kog00112001
Figure 4: The averaged classification errors (Left) and averaged empirical excess risks (Right) of all settings with Nleat 50, 000 in Scenario III.
information loss in the label-flipingg mechanism. As expected, the additional logarithmic term significantly -1/2 1/2 the performance of fn
alters the original curve pattern. Specifically, for the case with x log ln)n deteriorates significantly and approaches the worst case with e = 0. On the contrary, the performance fn in the case x log(n)n-1/2 improves significantly with B((x)) converging to Therefore, x -1/2 appears
11

---

Published in Transactions on Machine Learning Research (10/2023)
to be the dividing line that determines whether the excess risk converges, which completely matches theoretical results.
5.2 Deep Neural Network Classifier
The simulation in this section aims to verify our theoretical results in Theorem 2 which mainly lies in two aspects. First, we intend to verify the effect of e of Label DP on the optimal structure of deep neural networks for classification problems. Specifically, as stated in Theorem 2, label noise yiclded by the randomized response mechanism increases, a smaller deep neural network should be employed to strike a better balance between the approximation error and the estimation error achieve a better generalization error. Second, the consistency in estimating the decision boundary prohibited provided that adaptive to the training size at some specific orders. To these ends, consider generating training datasets D {( }))== follows. First, we set the regression function as Thn (2:) = Σÿ= sin(2 / +/2 with Biy ~ Un, 1) for any j. Then we generate Yi from (1,-1) with probabilities (2,) and 1 Mon (2:)) respectively. As in the last simulation, we then apply the randomized response mechanism Ag to each yı to generate 0 (s4) with 0 = exp(c)((1 + exp(c)). Then we set the hypothesis space to be the class of I-layer fully connected neural network with equal width and the ReLU activation function, where h denotes the widths in all hidden layers.
The overall training process of the neural network is implemented in Tensorflow (Abadi et al. 2016 with the Adam optimizer and learning rate being 0.001. Additionally, we employ the carly-stopping technique with patience 10 and maintain the parameter with the smallest. training error.
monitor the training Let Fm denote the resultant neural network obtained from minimizing (4). We construct the associated plug-in classifier as 6nn sign(fnn 1/2) and evaluate its performance by the empirical excess risk and the classification error as in Section 5.1
Scenario I. In the first scenario, consider privacy guarantees E 21, and neural network structures with L = 2 and h E {8, 12, 16, 20, 24) with We report the averaged empirical excess risks and the classifi- cation errors of all cases in 100 replications as well as their 95% confidence intervals in Figure 5 Clearly, if
c c= 1, the optimal neural network structure is h = 8, whereas those the cases e < and = co are = 20 and h = 24, respectively. Such results show that a smaller neural network preferred when stronger privacy protection of labels (smaller e) is considered, which coincides with our theoretical results Theorem that the optimal neural network structure to achieve the fastest convergence rate of excess risk should diminish decreases. Moreover, as the training sample size increases from 2,000 to 4,000, the optimal structure of the neural network enlarges for the cases and 2 due to their new tradeoffs between the estimation and approximation errors.
0.40
C.10
W0 4 020.11
(0,0)= 000,
Clanaficatto cuGial
(0,00033)
Empiiccll Exocoss Rich: E00ml
000
60 030.2)
10.00 000
0.30
67- 020
(n.0- (4 030
0.08
6.20
18
12 Numoer of Hidden Units:
Numbor of Hiddon Units:
Figure 5: The averaged classification errors (Left) and averaged empirical excess risks (Right) of all cases with Deest = 50, 000.
Scenario II. In the second scenario, we fix the neural network structure as (L, h) (2, 16) and consider training sample sizes (2 103; 0, 3, To verify our theoretical results, compare two privacy
12

---

Published in Transactions on Machine Learning Research (10/2023)
schemes xx n and < 1og(n)n=112, 1/22. We also include the case with invariant privacy scheme e < 4 as baseline. For comparing their difference in trend patterns, the multiplicative constants of two adaptive privacy schemes are chosen such that they have the same starting point as e = 4 when = 1, 000. We report the averaged empirical excess risks, the classification errors of all cases in 100 replications, and their 95% confidence intervals in Figure G Clearly, the performances of the cases e = 4 and 6 = log(n)n 1122 improve as n increases. However, the performance of case c <= n-1/2 presents a different pattern in generalization performance as n increases. Most notably, as n increases from 8,000 to 16,000, it performance deteriorates while the other two cases still observe significant improvements, showing that the additional logarithmic term plays deterministic role in the convergence of excess risk, which perfectly aligns with our theoretical findings in Theorem 2
0.300
0.025
0.75
Cologiain
0.250
Empeiiaal Rak 610
0.25
0.023
0200
0.15
0.03
0.25
0.100
3000
8000
2000
10902090
4000
6000
15900
5Gc of To ning Dataset:
5ize of Taaiigg maraset:
Figure 6: The averaged classification errors (Left) and averaged empirical excess risks (Right) of all cases with West = 50, 000.
6 Real Applications Mnisst Dataset
This experiment considers similar settings of the privacy parameter e Section 5.2 in order to verify our
theoretical findings of DNN on the MNIST dataset (LeCun 1998). The MNIST dataset consists of 60,000 training images and 10,000 testing images, and each sample is a 28x grey-scale pixel image of one of the 10 digits. In this experiment, we consider a binary classification problem by only including samples of digits 2 and 3 for training and lesting due to their similarity appearance. The resultant. training dalaset contains 12,089 training samples and 2,042 testing samples.
For the hyperparameters setting, consider the neural network with three convolutoo layers with ReLU activation and two fully-connected layers. For the three convolution layers, we set their kernel sizes and numbers of channels as 4 x 4 and 4, respectively. Additionally, each convolution layer is followed by a max pooling layer with size 2 x 2. The first fully-comnected layer has 10 hidden units with ReLU activation, and the last layer outputs the probability of an image being digit 2. As in Section 5.2 the neural network is trained with the Adam optimizer and learning rate being 0.001, and the carly-stopping technique to monitor the training error with patience 10 and maintain the parameter with the smallest training error. We evaluate of the trained model by the testing error on 2,042 testing samples. We consider training sample size (2xix 1 = 1, 3, 5). We mainly consider two scenarios, including the fixed privacy guarantee with (1, ]o) and the adaptive privacy schemes with e x log(n)Vn=' e x 11/2 and log (og=~(n) (n)nn1122
The averaged testing error of each case in 50 replications is reported in Figure 7
Figure 7 presents similar results as in Section 5.2 First, when is fixed, differentially private classifiers improve in generalization performance as the training sample size increases and attain competitive perfor- mance as the privptivate classifier (e = oo) when the training sample size is large enough. This result accords with our theoretical findings Theorem | that fixed privacy guarantee in the label DP slows down the convergence to the optimal classifier with a multiplicative constant. In stark contrast, as shown in the right plot of Figure 7 the convergence to the optimal classifier is prevented if n -1/2 boosting the
13

---

Published in Transactions on Machine Learning Research (10/2023)
0.175
C.12
0130
0.10
0.075
0.053
0.025
0.029
2030
3330
4000
19000
P000
W000
ICRD
4E00
100
2000 1007 4300
1000
60000
3000
4000
10300
Gim of The ming Detaveton
Sire of Training Detesetin
Figure The averaged testing errors with fixed e (Left) and adaptive e (Right) under different training sample sizes in MNIST dataset
training size from 2,000 10,000 fails to significantly improve the testing error. This again aligns with our Theorem 1
References
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Trving, Michael Isard, al. (TensorFlow): system for (Targe-Scale) machine learning. In 12th USENIX Symposium Operating Systems Design and Implementation (OSDI
16), pp. 265 283, 2016.
Mário Alvim, Miguel Andrés, Konstantinos Chatzikokolakis,, Pierpaolo Degano, and Catuscia Palamidessi. Differential privacy: on the trade-off between utility and information leakage. In Inter- national Workshop on Formal Aspects in Security and Trust, pp. 39 54. Springer, 2012.
Pathum Chamikara Mahawaga Arachchige, Peter Bertok, Ibrahim Khalil, Dongxi Liu, Seyit Camtepe, and Mohammed Atiquzzaman. Local diffcrential privacy for deep Icarning. IEEE Internet of Things Journal, 7(7):5827 5842, 2019.
Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, (12):317-33)) 1997.
Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. statistics, (5()):608-68) 633, 2007.
The Annals of
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Peter Bartlett and Marten Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 98), 2008.
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):113 (473))138-1156 116, 2006.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2301, 2019.
Racf Bassily, Mchryar Mohri, and Ananda Thoertha Suresh. Open problem: Better differentially pri- vate learning algorithms with margin guarantees. In Po-Ling Loh and Maxim Raginsky (eds.), Pro- ceedings of Thirly Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learn-
14

---

Published in Transactions on Machine Learning Research (10/2023)
ing Research, pp. 8638-5648 PMLR, 02-05 Jul 2022. URL http::/ppooeeding..ll....p / oper-prroblem-bassilyy..e html
Græeme Blair, Kosuke Imai, and Yang-Yang Zhou. Design and analysis of the randomized response technique.
Journal of the Americon Stalistical Association, 110(511):1304-311) 2015.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkiis dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, pp. 169-207. Springer, 2003.
Robert Istvan Busa-Fekete Umar Syed, Sergei Vassilvitskii, al. Population level privacy leakage in binary classification wtih label noise. In NeurIPS 2021 Workshop Privacy in Machine Learning, 2021.
Timothy Cannings, Yingying Fan, and Richard J Samworth. Classification with imperfoct training labels. Biomelrika, 107(2):311 13000,,,,,0000 04 2020. doi: 10.1093 10000////ooe///saa011111 URL https:://doo http:///dd..oog//... org/10..093//
biomet/asaa011
Olivier Chapelle, Eren Manavoglu, and Romer Rosales. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST), 5(4):1-34, 2014.
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In Pro- ceedings of the 24th Annual Conference on Learning Theory, pp. 155-186. JMLR Workshop and Conference Proceedings, 2011.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3):273 297, 1995.
Toddy Cunningham, Konstantin Klemmer, Hongkai Wen, and Hakan Ferhatosmanoglu. Geopointgan: Syn- thetic spatial data with local label differential privacy. arXiv preprint arXiw:2205.0855 2022.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-54, 2022.
Cynthia Dwork. Differential privacy: survey of results. In International Conference on Theory and Applications of Models of Computation, pp. 1-19. Springer, 2008
Ü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 Communécations Security, pp. 1054-1067, 2014.
Ülfar Erlingsson, Vitaly Feldman, llya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Pro- ceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2468 2479. SIAM, 2019.
Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. In International Conference on Artificial Intelligence and Statistics, pp. 7055-7075. PMLR, 2022.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. Advances in Neural Information Processing Systems, 94:27131-27144 2021.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, and Chiyuan Zhang. Regression with label differential privacy. In The Eleventh International Conference Learning Representations, 2023. URL https::/openreviier
Antonious Girgis, Doepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2521 2529.. PMLR, 2021.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Xiao Guo, Xiang Li, Xiangyu Chang, and Shujic Ma. distributed multiple networks. arXiv preprint or Xiv:2300 15709, 2023.
community detection for locally
Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu. Consistent spectral clustering of network block models under local differential privacy. Journal of Privacy and Confidentiality, 12(2), 2022.
Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner. Local differential privacy for evolving data. Advances in Neural Information Processing Systems, 31, 2018.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. The Journal of Machine Learning Research, 17(1):492 542, 2016.
Vishosh Karwa, Pavel N Krivitsky, and Aleksandra B Slavković. Sharing social network data: differentially private estimation of exponential family random-graph models. Journal of the Royal Statistical Society: Series C (Applied Statistics), 66(3):481-500, 2017.
Yongdai Kim, Issang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Newrul Networks, 138:179 197, 2021.
Vladimir Koltchinskii. Oracle inequalities in empirical risk minimization and sparse recovery problems: École D D'Été de Probabilités de Saint-Flour XXXVIII-200S, volume 2033. Springer Science & Business Media, 2011.
Guillaume Lecué. Optimal rates of aggregation in classification under low noise assumption. Bernoulli, 13 (4):1000-1022, 2007.
Yann LeCun. The mnist database of handwritten digits. http://yarm. lecun. com com/exdb/mmiese /mmist// 1998.
Wee Sun Lee, Peter Bartlett, and Robert C Williamson. Lower bounds on the VC-dimension of smoothly parametrized function classes. In Proceedings of the Sevendh Annual Conference on Compulational Learn- ing Theory, pp. 362 367, 1994.
Yunwen Lei, Lixin Ding, and Yingzhou Bi. Local rademacher complexity bounds based on covering mumbers. Neurocompuling, 218:320 330, 2016.
Ximing Li, Chendi Wang, and Guang Cheng. Statistical theory of differentially private marginal-based data synthesis algorithms. The Fleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.nee net, 2023a. URL httppss:/ppeeeeeeeeeetttt//eeeee
bxU
Zhechen Li, Ao Liu, Lirong Xia, Yongzhi Cao, and Hanpin Wang. Differentially private condorcet voting, In Proceedings of the AAAT Conference on Artificial Intelligence, volume 37, pp. 5755-5763, 2023b.
Yi Lin. A note on margin-basee loss functions in classification. Statistics & Probability Letters, 68(1):73 82, 2004.
Mani Malek Esmaeili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934-699 6945, 2021.
H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. Ad click prediction: view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1230, 2013.
Frank McSherry and Πya Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 627-636, 636, 2009.
16

---

Published in Transactions on Machine Learning Research (10/2023)
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, (1(14)):1338, 2020.
Tapan K Nayak and Samson A Adeshiyan. unified framework for analysis and comparison of randomized response surveys of binary characteristics. Journal of Stalistical Planning and Inference, (39(8))2767-276)) 2009.
Igal Sason and Sergio Verdú, f-divergence inequalities. IEEE Transactions on Information Theory, 62 62(11): 5973 6006, 2016.
Johannos Schmidt-Hicber. Nonparametric regrossion using deep neural networks with relu activation func- tion. The Arnals of Statisties, 48(4):1875 1897, 2020.
Shai Shaley-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
Xiaotong Shen and Wing Hung Wong. Convergence rate of sieve estimates. The Annals of Statistics, pp. 610,615,11 1994.
Xiaotong Shen, George C Tseng, Xuegong Zhang, and Wing Hung Wong. On learning Journal of the American Slatistical Association, 98(463):724 7444 2003.
Steve Smale and Ding- Zhou. Estimating the approximation error in learning theory. Analysis and Applications, (011):17-41, 2003.
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arxiv 709.02753, 2017.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1)3135-166, 2004.
Brendan van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(22)):1-50, 2018. URL http://jmmr: http:///haa...r//pppptsss//////s wttp//perrppp///1/////555 111166633.ham
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complenity, pp. 11-30. Springer, 2015.
Chendi Wang, Buxin Su, Jiayuan Ye, Reza Shokri, and Weijie Su. Unified enhancement of privacy bounds for mixture mechanisms via f-differential privacy. In NewrIPS, 2023.
Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pp. 0628-6631 PMLR, 2019.
Junhui Wang, Xiaotong Shen, Yiwen Sun, and Annie Qu. Classification with unstructured predictors and application to sentiment analysis. Journal of the American Statistical Association, 111 (515):1222211255 2016a.
Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pp. 729 745, 2017.
Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In EDBT/ICDT Workshops, volume 1558, pp. 0090 6778, 2016b.
Stanley L Warner. Randomized responsc: A survey technique for climinating evasive answer bias. Journal of the American Slatistical Association, 60(3)))663 69, 1965.
Jon Wellner et al. Weak convergence and empirical processes: with applications to statistics. Springer Science & Business Media, 2013.
Yu Xin and Tommi Jaakkola. Controlling privacy in recommender systems. Advances in Neural Information Processing Systems, 27, 2014.
17

---

Published in Transactions on Machine Learning Research (10/2023)
Shirong Xu, Ben Dai, and Junhui Wang. Sentiment analysis with covariato-assisted word embeddings. Electronic Journal of Slatistics, 15(1):3015330% 2021.
Ziqi Yan, Qiong Wu, Meng Ren, Jiqiang Liu, Shaowu Liu, and Shuo Qiu. Locally private jaccard similarity eslimation. Concurrency and Compulation: Praclice and Experience, 31(24):e4889, 2019.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114 2017.
Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam: Research Papers in Probabilily and Statistics, pp. 423 435. Springer, 1997.
Sen Yuan, Milan Shen, Πya Mironov, and Anderson CA Nascimento. Practical, label private deep learning training based secure multiparty computation and differential privacy. Cryptology ePrint Archive, 2021.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-88) 2004.
Ding- Xuan Zhou. The covering number in learning theory. Journal of Complexity, 18(3):739- 767, 2002.
A Appendix
Lemma 1 (Restatement of Lemma 1). Suppose the randomized response mechanism Y As(Y) satisfies L-Label DP with 0 = exp(e)/(1 + exp(e)), then for any x E it holds that
x(e,x) s DKL(PP (RI(PiixeulPyy x {((E,x))
where DKL (Kr prixx=-PPiii-- x denotes the Kullback-Leite divergence (KL) divergence between yyx== and Py|x==; [(c,z) = (x) 11 + exp(c))-² and U(e, x)) = min (c. x), U2(c, with U1(e, =
(2n(x)) - 11)))1((=))))))))))))))))1111) - (-)x) exp(e)) and U2(e, = (2n(x) - (xpeep((e)
Proof of Lemma We first prove the lower bound of DKL P which is mainly based on the Pinsker's incquality (Sason & Verdú 2016). Without loss of generality, we assume that 17(x) > 1/2.
Define
1-p S(p, g) = plog + (1 p) log 1 1-
2(p - -
where p.q E 1]. Let S(p, 9) take the partial derivative with respect to q, we get
4) s O, for q p. 1 1-P P + A(p 4) -pp- 4)( q(1 g) aS(p, q) p + 1-9 Oq
where the last incquality follows from that fact that q(1 - 9) < 1/4 for E [0, 1] and the equality holds when 9- Suppose that Ag satisfies e-Label DP, which equivalent to set 0 = exp(e)/(1 + exp(e)). Therefore, it holds that
DKr.
(((()) 7(=))² 2(2n(x)) =(2n)=)) 1) exp(c)) L(e,
Next, we proceed to prove the upper bound. For any pair of distribution and Q, we have
DKL(P = Dre (PP + 15 exp(DxL Q)) 1.
18

---

Published in Transactions on Machine Learning Research (10/2023)
Recall that Y and y take values in {-1, 1/, we have
DKL. Py Pr|x==| PP 1 7|x==/
S exp (DRT. PPrIX= x -1
<n(xx) 7(x))
7xx)
+ +(1 n7(x))
1- (2) = n)(x)) 17(x)
11) + +(1 -(1-1(2))
11-1111100 7(xx)
(1 1 7(xx)
1)
1 1 7((x)
17(x))
17(x) 77(x))
(7(x) -
(n(x) 7j(x)) 2
- -n(xx)
(1 n(2z)))
1 7/(2z)
7)xx)
17xx) - 77(x))
Note that
(1=x)(1-((()) - (On(z) + (1 0) -((x(()))
(11 (1--0) 0)((2) + 0(1 0 n((x))
-0(1
+ ( - + -0)) + 0 0)(1 n7x2)))
2 -(x))
It then follows that
(n(()) 7((x)) 2
DKL Pyyx= max (1x)))2)(1 (1-n)xx)) B(1 -1 8)}
(6)
Plugging 0 = exp(c)/(1 + exp(e)) into G yields that
(2n(x)- - 1)²
Dk (Prix=ulPyix-e) max 1/ (1 + exp(e))), exp(t))
x(),x).
This completes the proof.
Lemma 2 (Restatement of Lemma 2). Vf Ao(Y) with > 1/2, then (' = (x)) for any x E and
D" = (20 1*) for any f.
Proof of Lemma 2 By the definition of 7j(x), we can obtain
(7)(2) 1 (20 1)(2n())) 1).
(7)
Clearly, 2n(x)= > indicates that 277xz) > 1 provided that 0 > 1/2. By the fact that f*(x) = sign(n(z)-1/2)
it holds that f*(x) (x: for any X. Recall that the excess risk in terms of (-1 loss can be written
R(f) R(f*) = E sign(f((X) * (f)) 11].
Combined with 7 it holds that
R(() R(()) (X -
=(20 |)E||sigu([(L) (f()) + sign(f (7((X) - 11] -(20 - ()() - R(S"))
This completes the proof.
Lemma 3 (Restatement of Lemma 3). Denote that Ke = (e - 1)/(e* +1). Under Assumption 7 for any
(1/2,1), 1], it holds that
(1) F ((2T() -11 11 st) S 76, for any E 10,
(2) Rs( - Ro(s') 2 kx(46) (E[IX(( - -x(X) * for any f F,
19

---

Published in Transactions on Machine Learning Research (10/2023)
Proof of Lemma 3 By the assumption that ||f I and the fact that 0-1 loss is upper bounded by
hinge loss, we obtain Ro(s) R,( R(f) - R(f*). Since & is set as hinge loss, it holds that
Rx(f) ((f)-RR(ff) =Bx [X
21Ex [[ - (x)) 2n( t)]
By the fact that I(11 27(x) > t) = 1 - 1[|1 - 2n)( & t). it then follows that
Rs(f) - Rs( 2t (xx (xx (x) 2P 2n(X) st)
2/ 2xx Ex (I((X) (X) 2cl2)
-IEx
-20
where the last inequality follows from Assumption we get
Choosing such that ( - -x)] = 4ct
R$(f) - Ro(f" (4c) 1/7 ([(f((x)-f(x)))))) T!!
Next, we proceed to establish the relation between - and the conditional risk is given as
For each æ X,
(x(o((())) x -- - +1 (1
= =(Or(z))(((x)) + 0(1 - -(x)))(( + (11 -1--0)( 0) (0-00))a-)))0000000000-----)))))
Taking the expectation with respect to X yiclds that
B 0000)))))000000001---000000000)-
(8)
Notice that o is hinge loss, hence
- -o( RT(-f*) 1 Ro(-A),
for any f with bl S follows that
Ro(f) Rx(f* -
(20 - 1)(R(() - Ro(s"))
(20- - ()((c) -1/1 (B(1((X)) 7
This completes the prool.
E
Lemma 4 (Restatement of Lemma 4). Denote that M max max EFNEE)) EFNE(F"), EFPE(())
EFPE(f)) Under Assumption 1 for any margin classifier f, it holds that
R(F) - R(F) min = 1), P(Y -1)3 2c + -(F))) + R(f) - R(()).
where e and y are as defined in Assumption margin classifier becomes
Particularly, if Assumption holds with 7 50, for any
R(f) R()* SS
2 min (P(Y = 1), P(Y = -1)} ( (B())
20

---

Published in Transactions on Machine Learning Research (10/2023)
Proof of Lemma We first prove the left-hand side of (3. By the relation among R(f), EFNE(f), and (F one has
R(f) - R(f*) = (EFNE()) - EF) = 1)
(EFPE(S) EFPE(F)))(( = =
max (EFNE(f) (ENE(")), =)
max (EFNE()) EFNE( EFPE()) E))E(/"))
Next, we prove the right-hand side of 3 We first define
Si() - far X sign (x)) = } and S_1(S) = {xr E X sign( =-1..
Clearly, it can be verified that S1( = (0 (7))) > 1/2} and S_1(5*) (æ: n1(x) < 1/23. With these, we further get
1 (LeLn ( n(x))Px(x)da 2_()
[S_ x
EFNE(S) EFNE(
11)
1
(1 ((=) x (2:)
JS_(MAAS x
P(Y 1)
1
SSLCS (1
EF EFPE(F)) P(Y -1)
(1-7(1)) (x))) (x)
S((()))
P(Y --1) ( [1-n(z))Px((a)
1
(1- ( (z))zz)
where AS_1 = -=_((t) and AS = S)(ff) We can easily verify that S-1(f) AS = (1()) \ AS and (1) \ AS = (-*( AS-1. Therefore, it follows that
R(f) - R(f*) -0 (/1, nx))Px ((e))x(x)d==
/ (1 n(x)))x((xxdll
(x) 22 (ʃ, x (x)
((x))Px
11
/ x(x)P((x)dxx
Px(x)ddx
A2
where A S-(()) \ and A2 =2= AS
Then
/ xx S Sava, (x(x))dx+ R(F) - -R(S")
A. (x)))((a)dd
$ [ 1(12)(()) -11 S 1)l (z) (x0) + /
JAJUA, 1((2)(0) 11> x + B() - R(F*)
AJUAS
<el' + I
JAJUA T(12)(xx)= - 1| > 1) 2n)(x) - 1
x (x)dx + R()) - R((*)
t
<at + R(f)) + R(F) R(f*)
where the last inequality follows from the low-noise assumption. Choosing / = (R()) - R((()) T /CTtT, we
get
f (xx))Pxxxx))
/ x I 2c -())) + -R())
Finally, we have
EFNE()) EFNE((")
1
22 (R() R()) R(()).
(9)
2P(Y =)
21

---

Published in Transactions on Machine Learning Research (10/2023)
Using similar steps, we also have
1 EFPE(S) E)PE( S 2P(Y = -1) (2c (20- 147 - ((
(10)
Combining
9
and 10
yields that
max (EFNE(() - EFNE(F") EFPE()) EFPE(f"))
2 mPin = 1), P(Y = -1}} 2c + (R() R(())) + R() - R(S))
The desired results immediately follows by letting 7 go to infinity, which completes the proof.
Theorem (Restatement of Theorem 1). Under Assumptions and [ for any minimizer Jn of 2 there
exist some positive constants A and A2 such that
A V (1) n
(1(( sup E ((()) R()) s ( log(n) TEP,
+
+ 8n0
nk?
where Py be a class of distributions of (X,Y) satisfying Assumption 1 8n SUP inF H(), and Tn = suPrep, jer f))
Proof of Theorem I Proof of the upper bound. The proof of the upper bound mainly utilizes a uniform concentration inequality. We first denote that lff, = Rf( - Ro(f"). Next, we proceed to prove that (T l*) 2 5n) converges to zero as goes to infinity for some convergent sequence 6,, > 0. H(,, For any 8n > 0, we let Fo, = (JE): 2 8n}. If In E FB,, one has
Σ (f+ + (
Σ (() 2 0.
sup fEFon
This follows from the optimality of Jn for minimizing 2
Therefore,
P P() JT) 2
SPP
sup SEF
Σ
+
- -((x))))
=I.
n
Next, it suffices prove the convergence of I with n. To this end, we proceed to provide an upper bound for I. Define that Hij = {f E F 2'-18, S (f, ft) < 2' 2', 20- - J(f) 2' Jo} for 2 and j 2 1 and Hoo = (ʃ E F 2 < H*) < 2'5,, J(] S Jo). It can be easily verified that Fs.. admits the decomposition as Fs. - Up Hej. With this, I can be upper bounded as
Σ d of + An)( 1 Σ o(f(z)))) - 20)())20)
n
I -=P
sup JEFAm
00
oa
1
{(f(x))0s - XnJ(()) 20)
P
sup fEH.,
π iml
n iml
im
j
0
20
80 ΣDn
PP
sup
1
Σ (4(f))2)
Σ 2x) 2 An
inf J(F) - Jo) + inf B(o(f(X.))) -((G)))))))(((())) SEH,
SEH.,
n
fEHs
aml
where 2, (Ir, and 1z( = ((f(x))))) - B(o(f(x.) Here it is important to note that
inf B(olf(X,) E(O = inf
Ra) Ro( Ro(ft) + R₂()*)
SEH.
fEHL
inf H(J. #)))) JEHig
inf fEHi
(20
22

---

Published in Transactions on Machine Learning Research (10/2023)
Let v(i,)) = Xn (nnf J(f) Jo) inf B(((f, - E((o(f3, By the definition of Hay. we get V(i.5) 2 (i.j) An (, (2' - 1144)m, for i.j 1,
(11)
where the inequality follows by assuming that (20- 1)s,, S 1/45.. Next, we suppose that Jo S 1/40,, we further have
M(i,0) 0) 2
2 20n for i2 1.
(12)
Plugging
11
and
12
into I, it follows that
00
00
n 1 Σ 2)
1 - 2(.))) Σ Psj.
00 00
S
P
sup feH n
ni
1=0
Therefore, bounding reduces to bounding P. separately. Let On = 1 Ei= (lo 2i) - Lolf, zi)), then Pi can be written as
Ps = P sup Qn - 1 sup JEHg
Qn) 2 M(i,) E8| SENU
sup Qnl
JENI,
Next, we proceed to bound Pej by the Talagrand's inequality (see Theorem 2.6 in Koltchinskij 2011). lj. To this end, we first establish the relation between E sup Qn] and (i. Let off. ((.)))))) (((()))) and z' = (zf..... 2/x be a ghost sample.
n
E sup Qn EEH,
E
sup SEH.
(f. (0((((((f2)
71
=E,
Ez SEH,,
sup
1 Σ
n
(f. 24)
1 n Σ
alf. 4)1=)
71
n
n (f,
1 n
<F,,z'
sup /EHo
Σ ql a(f
11
n
a as(1(S, 2z) - a(S, =10)
sup nEHis
<2E_ E.g
sup fEHyy
az 21) 2R, (Plig).
By Theorem 3.11 in Koltchinskil
2011h, it follows that there exists some constant C2 such that
C2 Rr, (Hir) <
C₂ Vn
R
log (w, Hug. (2()))) S
E
(V)
(og
(2)
where Øg- V su,,, 1 of lffl = v ( and Lo u) is the
minimal number of Ly(P,, balls of radius u to cover Hij-
Notice that for: /Vi (V2( is concave function with respect to oz therefore
Eoy
/oot
E
(o(()) 12)))d < (og
<
(O) 1z
1 By the definition of oij we have E [ sup à 1 traction inequalities, get
Using symmetrization and con-
1 & sup Elg²(J, + SR, /EHr,
23

---

Published in Transactions on Machine Learning Research (10/2023)
Next, proceed to bound (f.
(f) = -
((f{(x) -000000((())))) + 2E (lfF(x))) o(((8)81 -((F()))))00(0000)
22
22R ( -(0)()((())))))) + 2 - -((3(x))
28h 2E || 2- 2E fXx - (x)
(13)
where the second inequality follows from the assumption that | S Combining this with Lemma yields that
3
sup fEHi,
2) 10
- (2(())) - 4C1 - 1)=
=71 (2' 7
where C1 (4c) गे., Consequently, we get
C2 (islt)
Rn(H) - nn
(14)
where Uiz(f) = min ( 1/40, (C -2)
SR, (H.)). due to the fact that [g(f. 2) s 1. Then,
the right-hand side of 14h can be upper bounded as
C2 (S)
Pi((
Uc(f)/Va(e)
(o())) (V2()))du (ogg)))))())(
log
du
Vn 0
vn
C2V2(0) (
1 log (u)du 2C2 (O)
V2(O)
log
(15)
Vn
Va(el u²
Vn
(iz(f)
Combining 15 with
14
yiclds that
4CHvi (4C (21 13 (2'8m) क. (His)
(2) log Ufr(f)
(R (His))
(16)
Solving 16 gives RT, S max (n - 1) 2citi o 26+3 (f, Her) I 1/48, provided that
Therefore, we get
(M(())n)) - (20 1 log (oggn///1/ (e)) S CS..
(17)
for some large constants C. Hence, as n goes to infinity, it follows that
Rn,() < 1/46, 1/4M(i,
With this, we get
E[ sup Q.] < Rn, < 1/4M fCH:
Therefore, Ps can be further bounded as
Qm) 2 1/2
Pιş
P sup Qn ---E
E
sup fEH,s
(18)
JEHis
24

---

Published in Transactions on Machine Learning Research (10/2023)
Applying Talagrand's incquality to the right-hand side, it follows that there exists some positive constants C4 such that
M(i 1)
Pg S C1 exp
log (1 +
2C4
2
As proved above, we can verify that there exists some constant Cs
Blog] v sup + S Cs (20 -
+ M(..))
SEHl
Notice that ( o
converges to 0 as n increases, therefore there exists some constant 0 < C7 < 1 such that
log(1 + x) 2 Cg for I E [0,1/ It then follows that
CTnM2(1))) Pij v exp (- (C2 - 1) (M(i, सम. M(i.i))
Since M(i,j) < (20 - 1) ने. (M),, when - 1/2 = o(1) and M(i,j) = o(1), we have
Ps S C. exp ( (- [CCan(20 - 1) न M M (1.5))
where Cg = C7)(AC,Cs). Therefore, we have
n ΣΣ
n
[_CsMM 7+1 (i,1)
742 CanM 7-1 (i,
C4 expp
Σ C4exp
I1 + 12-
(20 1) 7x TデT
(20
(20 - -TT
1=
1=1
Note that for any i,j 2 1,
M (1.0)2 1/4)6, >, (2 - 1)Jo) 777
712 उका
2(2 1/4)0 + (20-1 - (I)
21/20n
212
+ (j (An 7..
Hence I is upper bounded as
242 -Can i/20 5. + (j 1)( 777
4
C1 exp
(20 - 1) TTT
1=1
2+2
Cano, T+T
exp
2(20 1) 5|1
1
-Cnos
-C4
< 4CA exp
exp
-Cand,711
T+?
exp
-Can(An, Jo)
7+T
2(20 - 1)= 771
1(20-1) 7+1
2(28-1) TFT
2+3
}
Cons .+
-Can8g-14 1/3
where the last incquality holds when max exp true when n goes to infinity. Similarly, for 12, we get
.ep
S 1/2, which holds
2(20-1) 5
2(28-1) -
i/4Csnd, 7F (200-
Csni --
I < C4 exp
S 2C exp
(20 - 1 アम.
4(20 1 57
25

---

Published in Transactions on Machine Learning Research (10/2023)
Combining 1 and I2, it follows that
7+4 Cgnon ++
7+2
1 6C₁ exp
T1 exp
-T2 (28 1) 577
--T 4(28 1
where Ti 6C4 and T2 Cs/4. Therefore, we conclude that
112
n2. 2-44
P ((i((nn 6n) s Ti exp
-72
(28 1)
With choice of 8n such that on > Cg 1) 0 log(n/1(1)) 712 for some positive constants
Cg > O, we have (f.: f*) = (1),, which implics that E (f.: f²) = Op(5,). Notice that T1 and To are both independent of n, therefore we further have
sup P P( f*) 5n) s ST exp -T2 n2n T1I
(19)
Tp,,
(20 - 1)-=+4 741
By the relation between excess risk and excess r-risk E (D(n f*) s <Ez( (Hn. ft) further have
(Brtlettt et al. 2006
sup E5 (D(Fn. (') O(ōx). =((b))) =EP,
Combining this with the Lemma that D(Fn, f*) = (20 11)0-11) f" we get
sup Es ((( = 120 1)
=EP,
The fastest rate for 8n can be obtained by choosing the fastest rate such that the right-hand side of converges to sero with and 177 holds, which yields that
19
8 (Vi)))) 733 (20 1 log(n).
This completes the proof of the upper bound.
Proof of lower bound. We first define the minimax excess risk as
Wn inf sup -(()(())R(()) f xEP,
which admits the decomposition as
W, inf sup =EP,
E [ - inf R()] Je
+ inf R(F) - R(F)) Jer
where the second term the right-hand follows, we proceed to consider sub-family of P., such that fnr R(f) = R(f*). For example, let P' C P,, be such a sub-family, then we have
hand side denotes the approximation error under the 0-1 risk. In what
W, inf sup f TEP
E (R())
inf R()}} sup inf R(f) -R(F)) feF
TEP, feF
= inf sup
E [((F) - ] + sup inf R(f) R((*))
f TEP
TEP, fef
=(20 - 1) inf sup
[B)[ - R({})}}
+ sup ( inf R(f) R(S)), TPP feF
TEP((0)
26

---

Published in Transactions on Machine Learning Research (10/2023)
where the last inequality follows from Lemma 2 and (0)) is set of probability measures से on (X, Y) such that any probability distribution मे (0) is associated with an π p with it and π having the same marginal distribution on X and Y = AY)).
To provide lower bound for Wn, it suffices to bound infy sup (0) 5 [R(f]( {1 For ease of notation, denote W, inf, sup Ep [R(f) R(f*) and P,( - T P,).
Then we procoed construct P'(0) C (0). First, following from Lemma we have for any क E P,)
P [ 1 s 11)= s sc(20-1) 1)
where the probability is measured under म.
By Assumption 2 we know VC(G>) x V1()). For any N such that N x Vi(O), there exist N distinct points 2,...., N such that (#1,.... #N is shattered by gz. Therefore, we consider distribution supported on {æi...., .N}. J. Let w E 1) be number satisfying (N - 1) I 1. Let Q be the probability mcasure on X' such that
Q(x,)
w.
i i= I....,N--- - 1,
( 1- 1- - 1) i= N.
In what follows, we consider the hypercube C= 1-1,1]8-1 For any , .N....)))N E EC, we define the regression function as
Itaph 2 i= I....., -
Mor (xx)
i=N.
Next, we let Ho denote the associated probability measure on X' x (-1,1) with Q being marginal distribution on X and io (ar) being the regression function. With this, we obtain
P (( (x) 11 t) = (N - 1)w1(( (h S t).
By assuming (N - 1) I c(28 h)² we have P( (X) 1| s t) = c(29 - 1) for any E (0, which indicates that T. (0). By setting P'(0)= ( C)2 have
Wn inf sup
E R()() R R(F:))
f EP(0))
where fx1)) = oi for i I,...,N--
Under R..
R( - R(()))
E2 [| sign (x
- E-
2 (siin(((X))
fx - x7)
t E.
(iig(((x)) - -z (1 (1- 2711-27(X7 xX) S t)
P([1
2
2 (20 1) -c) 1/7
[iggn(((X)) - fx
N-1
2 (20- - -6)
(f::)) (ax))
1=1
Under the distribution Ro, we have (xx; = o; for 1...., 1, which then implies that
si,n(f(æx)) -o:)) I11
RU - R(({)) 2 (20 12 1/1 w 211
27

---

Published in Transactions on Machine Learning Research (10/2023)
Taking the expectation of both sides with respect to D yields that
-o:1) 1
R(fE) 2(20 - 1/7
1-1
Bp
sign (f(;))();)) 0:l)
2(28 - 1)(44 E
7
sign(f(a:)))
where the second inequality follows from Jensen's 's inequality.
For ease of notation, we let X(1, 0) -20 - 1)(4 -2) 1)) -//
sup E (
2 sup
X( 7, 0)
sign(((ax)) - -o:)]
D
(0)
EP((8)
X(w,7,0BB
t11 O)B
sfgn(f(x:) - -0:1]
2 OEC
D
X(w, 7. 0)B
241
I (fign(((z;)) # #o:)
2N
D
aCC
N
[ sign(( + oo:))) =
=X(w, 0)
2N-1
D
aCC. i=1
N-1
=X(w,>,0)
P- (sign(f(z:)) # #o:))
2
EC
For each i, we observe that
Σ
Pa no
(i:)((( t0:)
N
OEC
Par (sig((((=))) & oz)
2N-1 Σ
P.r sign((((;)) # oo:)
2N1
ne
0:0;=1
0:0:=-1
-2 (sign(f(z;) * #1) + 2F 2F-1 (sign( # -1) 2 2 - 2TV +i Po.)
where P++ = 2 Emo,= Pa p-i = - Eose=-
Pa. " and TV(P7,, Pm,) denotes the total variation
between p00n and ppn Notice that for any probability measures P and Q, we have
TV(P,Q) - / [M(z) q(z))dx=
/ [Vppx) V Valel + vg(x)ddo
S / (Vp()))-V(())))
- vq(x)) dx) 1/2 <VH2(P,Q))
1/2 ) (/((VVl)))) (VVpl))+Valz))))
Vo(z))) dx))
where H²(P,Q) Q) denotes the Hellienger distance between P and Q. Let a and o' be two indexes such that a of for 1 1 i and o. = - = 1, then we have
TV(P WVPPH.POE pon)
2 2 TV
PPS p@n) F.
S max
(p pon) TV
S max
HPS pC"
ood To T..
0.o"
By the definition of To and oo,,, we get
2 + (V1 (V1- 1o (2:)) v1 1or (1x:)
H2 Pa
( 1/
(2:)) [2x))
v Nor (27.)
Far Tio
=2w(1 v1 - 112) S 2whh
28

---

Published in Transactions on Machine Learning Research (10/2023)
for any h [0, 1] By the fact that (P -2- we have
PP =2 - 2[1 w(1 - V1 - " - nw(1 v - h2)
2m - - 12) < 1/16,
where the last inequality holds by choosing and h such that wh? 1 n from which it follows that TV(PP PP4,) S 1/4. Notice that w and h are chosen to satisfy (N-1) S c(20- - -1)-0> and wh2 S n 1/2.
For simplicity, we obtain the following solution by considering the case equalities hold.
(N 1) (20 1) and w
c5+z 1) गेズ (20 1) +
(32cn)
(32n) नス
Therefore, we can conchide that
27-2 イイイ
2- 742
(N 1)
(20 1)
3(N 1)
sup E (5(((() - R(fG)) 2(20 - 1)(4" -1/7 542
1/76
To EP(0)
(32n)
7+1
2
(N - 1) 772 (20
1)
12
3
7+1
=(20- - 7) 1/7
(32n)
7+2
2
N - 1
7+1 7+2
3 1_1
-20 (1(4"-7--//--
1/76 / オサズ
32n 1)2
Choosing N x V1(0) yields that
inf
sup
E5 [(()) - R((r)) 2 (20 1)
(9)
342
n220 - 1)?
To (O)
where A2 x Following from Lemma 2 it holds that
-'2 (1 पोडे (3/2) 2
inf sup E [R() - ((()))(())) 2 A2 n22 - 1)2
(O)
1+1
7+2
(in R(J) - -R(3))
+ sup
jjst TEP,
/ TEP,
This completes the proof of the lower bound.
Corollary 1. Suppose that F is chosen such that 8n =0 and is adaptive to n such that = o(1) There exists some constants Aa > 0 such that suPRER, B (R(T) - R((*]] 2 As provided that S n 11/2,
Proof of Corollary 1 By Theorem we have
sup _ - - Ar (6(()(6)) (2((0) =EP,
# +
nn?
Tnj
Since 8n = implies Tn = 0, we further have
E [R(F.))) R(F)] 2 Ao (2(((i(6)
sup
nk?
EEP,
Without loss of generality, we assume that e since e = o(1). Then, by the definition of Ne, Ke x e when 0. Therefore, have
(i()) (c()(()))(c) + 1)2 +1 nRR
(1(
> ne2
(20)
n(exp(()) - 1)2
where the last inequality follows from the fact that e² ex for any x E (0, 1). Further, if = o(1/vm) we have ne² = o(1). Therefore, it follows that (0)m 1x_² 2 (V) for some constants C. The desired result immediately follows by setting A3 22 and this completes the proof.
29

---

Published in Transactions on Machine Learning Research (10/2023)
Theorem 2 (Restatement of Theorem 2). Let py,s be class of probability measures on xx1 satisfying
Assumption 1 and n(x) E H(3, [0, 1|", MM) For any minimizer fnn in 4 with Ln x log(k.n/ log(n))), N₂ x (n.n/ log(n)) aoto, Bn = 1, and P. Nn log(k.n/ log(n)), we have
11) DEST2ITF
log nR
2017
sup *EP
(((mn)) -R(f)]] ~
20
nu?
Purticularly, s B (( R(S*)] = o(1) given that e 2 n 11/245 for any ( > 0.
Proof of Theorem Proof of the upper bound. Let z= -I + 1)/2. We intend to establish the connection between the excess risk of fan and [| =)( Here the proof is mainly based on Lemma 5.2 in Audibert & Tsybakov 2007
R(5nn) - R(f*) -E
27 (X) 1| 1( (X) + (x))
| (X) - 1/2 ((5an (X) + l (X)) (I(( s)
<2B
+ 2E
[ 1/2) 1(5mm (X) * fx)) I((((x) 1/21 > t)]
[m(X) Fn (x) T(( 1/2 < r)
22
+ 2F
(x) Frm ( [x] [(7(() Fun (x) > 1))
(21)
where the last incquality follows from the fact that (X) - 1/2 7x(x - Fnz (x) when 3nn (x) + f" (X). Next, by Cauchy- Schwarz inequality, (21) can be further bounded as
2E xx) - Frn (x) (177 1/2| s :) + 2E [m(x Fan (x) 1121
2 - Fn / 1/21 5 2/ - Jun 122(ex)
52' -2 || (xx
7/262/2 2 Frn (x)
Choosing 11 (7(x) Re we get
2x
R(5mn) - R(F)) Ric 7 17 Fuall (P(x))
x+2
Subsequently, by Lemma 2 it follows that
R(5 R(f)) = =xx0===, (R((5m))R(F))) i (n,321 - Frmm (
773
(22)
Next, we proceed to establish the convergence rate of | - Tnnlllipexxx Let JNN n.on /lliapxs 2 5.). For any 8n > O,
= 1s E JNN 17
n- n (x;) -2,)² n Σ - 6m))
PP -
2 8n) SP
inf JEFNN
where fün = arg mi || - 7lliA((x))
For case of notation, we denote that Un( = n- -n =2,² and U(f) E(f(X) Z)2. Then, we
have
P P(I7- Fnnll220))) 2 5m) <P((
inf JEFNN
Un(Sin) 2 20)
30

---

Published in Transactions on Machine Learning Research (10/2023)
Notice that F.t,, admits the decomposition as FNN fllia(2)) & 2. Therefore, we further have
1 with H4 {f FNN 2 1
P(I - Inn (1 8n
5
inf - SEN,
1=1
Clearly, suffices to bound P( (inlSEH, For i 2 1,
20) for upper bounding P P(1 (17 Jun (inl12((ex) 2 2m))
P
inf SEH,
- (u(fm))-U(()) 20)
<TP
inf /EH, [Un()in) U(Snn)] [Un(S) U()) 2 inf U() U(fimn)
SEH.
=P
inf /EH;
(fn)) U(fin)) (Ux(F) U(f) 2 inf U(f) - U(T) +( U(fmm)
SEH;
<P(
inf SEH:
(fn() -U( (U,(F) U()) 2 2 - -Iffin 71
Assuming Ilā - Mll (Fxx) S 5n/2 yields that
IP inf (fin)i)) (f) 2 0) = P inf (Un(fin) U(fin) - U()) 2 22-28%) JEHL
SEH.
Denote that Mi- = 2 We turn to establish the relation between the variance of (fin (X) - -2)² (f(x) - 2)² and M,.
sup Var (f (X) -)² - (f((x - 2)
SEH,
sup Var (fin (X) - f(X)) (X) + f(X) ( - SEH,
S sup E (ffn (X) - f(x)) ( (fr (X) + f(X) - -2) 1 sup 4V - fllie())) /EH,
SEH,
sup 8V2 [Ifinn - m + || fl122((x)) s <6VV, jEH,
Vi.
In the following, proceed to verify conditions (4.5)-(4.7) in Shen & Wong 1994). First, the relation between M, and Vi directly implies (4.6) with T = 32V2 and 6 = 1/2. Second, by Lemma of Schmidt-
Hieber (2020).
(e,, F.NNN (Lns Nn, Pa. Br, Vn), (1 s log.V( (e,
(Pn + l)g (Ln + 1) + 1) max Bn 13).
It then follows that
f
v.
V log.V( c, FNN (Lns
(NN, Nn, Pn: Bn, Vz). (Fe) de/M:
2/ M,
$ V1/2
+ I) max (Ba, 13 1)),,/dee////e de/M.. V [2 + +1) (P log (e-t(Ln
(23)
M.
Notice that the right-han hand side of (3) is non-increasing in í and M,, it then follows that
12/2
(Pn + 1) log (Ln + 1) + 1) max((nn 13 de)de// de/M,
$1 1//22
1 2n (Pn + + log (e- + 1)(N, + 11) m)xaa((B Bn. 1).dd/ddd//ee/ de/MM
M,
31

---

Published in Transactions on Machine Learning Research (10/2023)
With this, condition (4.7) can be satisfied by imposing
2/aa 2L + 1) log (L, + 1)(N, + 1) max 13 de/Mi 2 n/12
(24)
M1
which directly implies the condition (4.5) by appropriate choices of La and Sn. By Theorem in Shen Wong (1994). we get
nM, PP P(I Fan (1 8n) Σ exp M, 2M/33
exp ( n22 26n)
By the fact 2 2 (i 1/2) for i 12 1, there exists some constants C such that
P |1 1 2 2nn) S exp(pCCnn,
provided that nō o().
Next, we proceed to consider the approximation error of neural network to meet the assumption that [| nl S 6n. Notice that nxX) ) E H(3, [0, 1J,, M). By Theorem 5 of Schmidt-Hlieber (2020), there exists a class of neural networks JNN (Im; Nu, Pn, Ba, Vn) such that for any < 4/n <1
inf (L.
||ʃ !|l S Kgg Vin
log(ne/ /v), Nn x (x. vn) pn) p/8 Bn = 1, V2 2 M + and Ln x log(re/ Vn). Let Thn denote the optimal function JNN NLn:N Pn. Bn, oo) to approximate 17. Suppose that Mmn L-layer neural network and formulated as
where Pa x
(n)
Tan (x) = AL+191(x)) bL+1,
where (1(x)) hy o h .... o (2)). We construct new neural network that Mun
Man (a) - mm (x) + () (x:)
- (a) + 0br + - ( A ALt1gi( + +11 bl+1))
=(20 A) + -20012111-00 1)bL+1 + (1 0)1
It can be easily verified that 7mn FNN (Lay Nn, Pa, B,, V,,). This along with the fact that 7(xx) 0n((z) + (1 0)(1 n(x)) with B, results in
(1- 11 - (x(() =I(0mmm + (1 - 0) - mmn) - On -1 -1-1) 0) rm)x)
=(20- 1)llnan 7111. Ke kellytm - -ll,,>(pxx) S en.
Therefore,
Ilf - 771 2
inf (In.N P., |lf - 7 S Mm - Mi2 (Fx) (Fx) S w/?
Plugging Pn x (Nr (b -p/ log(kse/ p 2299) - 1o S ) Combining this with the assumption that viz S 8n, it follows that on x 122 = me
(oe((e///))) /vn,, Nn x (t) and Ln x log(se/ (/ee///n)) into (44g yields that
2p/(28))) (log nogn//))200 22222/2220+P)) Plugging this into 22 yields that
E R(G - R(F) S
log n n
28 34(5+9)
(25)
Notice that the proof of 25 is independent the distribution of X, therefore in Pa.s, which implies that
25 holds for any distribution
R(3mn) - $ R(({}]
log noe
20 21
28(x+1)
sup X XEP, P
32

---

Published in Transactions on Machine Learning Research (10/2023)
Proof of the lower bound. The proof is based on the well-known Assouad's lemma. The overall proof for the lower bound is mainly based on the proofs Theorem 3.5 and 4.1 in Auddiberr & Tsybakov (0007). We first introduce the partition { )= of the cube [0, 1J using the grid Gg S [0, defined by
G -
(
2k +1
2kp + +1) 29
: k (0,.... :9- 1),8 (1,..., .p)]
2q
where q 2 is an integer. For any I E TR, let (x))) E Gg be the unique point which is the closest point x E RP among all points in Gg. Without loss of gencrality, we assume the uniqueness of (z(x) by choosing the one closest to O. We define a partition { of Rº as follows. For æ, E R. x and are in the same cell X; if and only if (x) = (t)) Then, for m S qe, we define X; as X; X for S S m and Xo = / - Rz
Let u R2 + R be a non-increasing infinitely differentiable function such that u 1 on (0. 1/4] and u on 10) Let Φ = Cau([[ar]] [)), where Co S is laken small enough such that ø H(3 [0, 1J, M)) For a given = (...... (m) E { we construct distribution To on Rº x {-1,1] as follows. Let μ be the Lebesgue measure. For 0 < < 1 and Ao S Mo with p(Ao) > 0, we construct the marginal distribution Px on Iº that has the density function
= { ((B(U.--1/1))>
x E B(2.9-1444) for some E Guy
Px(x)=
(1- -m) m/m/m((A)))))
x E Ao: otherwise.
0,
The conditional distribution on {-1, 1] is defined by
{
1t0, 2
for x E x = 1,,.,, m,
(x)) = P(Y = 1|x = =x)- =
1/2.
x E No.
where p(x:)= = (00((((nnn((1)) Correspondingly, for any a, To is given as for x E = 1,.,,, m,
14(20-1)))0(a))
Tor (20) = 07 (x) + (1 - (1 - (xx)) =
2
1/2,
x Xo.
Notice that Dd = 0 - -ng(x))) for any s E N with |s| I B. Thus, no ( belongs H(B, [0, 1|2, M).
11o (x) - 1/21 1/211-11) mP mP(olyla ((((()))((z))) S 2tq²)) )
=m
1 (0(g(z zo)) s $28g²)
M(B(O, (44) dx
(()0)(40)-11
m [ B(001/4)) 1 1()(x) S 210²) (B((0, 1/4))
w
de = mww (1 (12 C2/(22))
where 2g ( [ (x Clearly, the low-noise assumption of %o can be satisfied by setting me S yr) Let PT,8 denote the set of joint distributions of (X,Y) satisfying the low-noise assumption and 7/(x)= E H(3, 1J, For any o, we have To E Pr,,, implying P' :To {-1,1)m Py,g. Therefore,
sup E5 R((m)) R({*) xEP,,9
sup E R(5nn) - -((5) Te EP'
Let Pr be a set of probability measures on (X, (X, satisfying that for each To E P' there exists an To Pr such that To and To have the same marginal distribution of X and (xx) = f (z) + (1 - 0) - no (z)) It follows that
sup E R(5nn) R(F)) 2 (20 - 1)-1 sup E E- Th EP!
R(5mm) - -R(P))
R. Ep:
33

---

Published in Transactions on Machine Learning Research (10/2023)
Next, we proceed to bound sup E B R(3mn) - R(ft){. therefore we fö to characterize its dependence a.
Notice that f varies with the value of o
sup B R(3mn) A())== -((()) sup EP
[B Ex
12 (X) - 1 (enn (X)ox)))
x Ep
(20 1) sup
1 Ex-Px ((X)1 fonn (XX
EP
where (n) = if the statement x is true.
Let IT be the distribution of a Rademacher random variable a, that is, IT( = 1) = IT(o = -1) -1)=11) =1/2. Then
E Ex-ex (T (x0+(((()))) }]}
2 E1r. B Ex~ex ( (rnn (x,,0)0))
sup
To EPD
Note that for x E No, 1 - m 2 (2x)- and (pxx) = Thus, we have
B11m
E
Ex~Px ((X) (onm (x)x
E
Enr.
E
Ex-rx
j=l
Let jrr (01,... J5-1.
0-+1,"' ", 5m) for r 11. Here orr denotes vector deduced from by
fixing its j-th element to r. We have
Emp=
Ex-ex ( (x))1 (o.. (x,,(
d= Ex-px (x(()1 (x,,
EmTm
E
10,00
din
dā di
=
E
E
ExxPx
(x(X) (onn (X),
where Toy has the same marginal distribution as Px and Ho..o and Ho differ in the conditional distribution over the points in Xz. Specifically,
Na, (x) = 1/2, i E X,, To(()) otherwise.
It then follows that
d
11--1
E~
Baywll
x ((()) (ono (X) xxX,)
$63.0
dm
d ExxPx (x(X) 1 (Gnn ( ditazo
= -1
Ex
Eg B0yn11
di dioo
ExxPx
E
o (X) 17g To
BoyylI
( (x)#05)
((x)1 (F
1 p0_
(znn (8nn(X) + -1)] (x))
> -mp
ExxPx
to (3mm (X) + 1) +
2
52,--1
{EX=EX (x(X) (1-TV - 2o }
2 Emp
where TV is the total variation distance between two distributions. Since Px (x())) w, have
E { E
Ex-xx
(((X) (xx_((
w
(1- -
34

---

Published in Transactions on Machine Learning Research (10/2023)
Notice that the above inequality holds for any index j E [m]] In conclusion, obtain
m
E mm
E
Exxxx
E
(x())
(x 2
mw Ex-px (x(X) X E 2j) (1 -.....
2
Now we bound TV _o...)) First, it holds
TV T
To
Σ
72
-1 w)
(
1=1
where 1/ = TV(T") #|) with n, = To. (1 E R2). Note that
2
(T-1
))
Vi VS 7t)
2 1-
2
where H is the Hellinger distance and
X (T, Ex~Px (VI- (20 1)2;(x)) ( x
= -1
2
Since 1 -1 -1-11x 2²)//22 z lx? for 12 and O, we have Vi by7 and
2
TV m..
I P
Ciw 1) vi s bVnw,
1=1
where e, are i..dd random variables such that P(e: 1) = 1 - P((ei = -1). In conclusion, we have
sup
Eg
R(3en)
R. 2 mwb'(1 - b/nw),
Var EP
where
37 1/2
1 E V (20 1))p((x)) X E Ex2 {)]
b
x x20 1)g
b' E (20
((2
1)((()) x E x2)) x (20 1)9
As a result, we have
sup Eg R(5nn) R³ 2 mwwq (1 m (2- 1)q Vvow) E
28
Take w = 1yz and m = qp, we obtain
(++1))
sup Ep (((aa) ne] 2 gotp TEP
1
(++2)++
nk?
num
by taking q x (n(20 - 1)2) 6+220+9 Particularly, when x n 1/2+c, we have
sup E5 R(Gmn) - R² < =EP
log nH?
200 200;-2)+s(raa)
log(n)
20(x+2)-p((+2)
20(r+1)
as n + 00.
This completes the proof.
35


Reviews:
[{"review_id": "PusVZ2YsBy", "reviewer": "Reviewer_LvK2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My apologies for such a long delay in submitting the reviews. At a high level, I liked reading the paper. The paper contains a good mix of theoretical as well as experimental results. I was unable to through the entire appendix (even with such a delay) and I trust the authors have done a good job of verifying their results. \n\nIn the sense of the main result of the paper, it seems like the paper shows that if we aim for a really low privacy regime ${1 \\over \\sqrt{n}}$, then we do not have the error to go to $0$. I really did not get the intuition why for an even smaller privacy regime, we have that error that goes to $0$. Perhaps, the authors can clarify it. If they have already clarified it in a revision, then it is great. Also, why would one care for such a low privacy regime? Is there a practical setting where one would consider such a low-privacy regime? \n\nI am not entirely sure that the local label DP definition is the correct one. It is based on my one-time look at the definition given in Ghazi, Golowich, Kumar, Manurangsi, Zhang. Perhaps, I am missing something here. Can the authors inform me that the definition is really the same? \n\nTo parse the main theorem and get an intuition as to why it should be true, I really had to go back and forth a lot. Perhaps, the authors can give me a high-level overview of how they arrived at their results. It would also help to understand what are the technical challenges in arriving at their result. Honestly, I do not care that much about the technical lemmas (which end up being just the maths to validate the result), but more about the intuition. \n\nOverall, the paper's result are definitely interesting and deserves to be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Label differential privacy was introduced by Hsu and Chaudhari and was implicit in that paper. It has been extended to the local setting by Ghazi et al. recently. For privacy, they use randomized response, which seems intuitive (though I am not convinced it is the optimal one). They give extensive experiments to support their theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Give some high-level overview of the result and some intuition why the mechanism is the right choice. \n\nSome discussion on high-privacy regime and why the authors think that there is a sharp threshold where you have model error converging to zero or not. \n\nUnless I am mistaken, the definition of local label DP needs to be checked.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lttqxHtNv9", "reviewer": "Reviewer_7nL3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The LLDP and the learning theoretic quantities are well introduced formally.\n\n2. The presented results are rigorously proved.\n\n3. The theoretical findings are experimentally verified.\n\n\n**Weaknesses**\n\n1. Motivation of the setup: It's very hard to understand why studying such a specific setup. At least the related work does not make it evident to me. Why specifically local DP is interesting here not central DP? Why studying randomised response as the privacy preserving mechanism? May be I am missing some context which I will like to be introduced to.\n\n2. Proof sketches: Addition of proof sketches have improved the readability of the work significantly. But still it is not evident what is non-trivial or challenging in the analysis? Pointing out such challenges would make the proof more appreciable. Also, in the supplementary proof steps are often skipped or sparsely explained. Explaining proofs in the appendix would be very helpful.\n\n3. Second part of Theorem 2: As a corollary of Thm 2, it is stated that the convergence of the excess risk is achievable if $\\epsilon$ decreases at a rate slower than $O(1/\\sqrt{n})$. But no proof of it is provided in the paper. A proof should be added.\n\n4. Excess EFNE and EFPE results under LLDP: The impact of class imbalance is shown for normal classifier but not the one trained with LLDP labels. It is said that the DP classifier also satisfies the same rate but a proof is needed to claim this result.\n\n5. Holder space: Can you give two examples (its okay even if it is a generalised linear model) where the Holder's assumption does and does not hold?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the impact of local label DP on the excess risk of binary classification, when the local label DP is achieved by randomized response method. The paper proves consistency of the classifier trained on the LLDP-preserving labels. The analysis shows that the excess risk under LLDP still converges but application of LLDP slows down the convergence depending on the privacy level $\\epsilon$. The result is further instantiated for a neural network of finite width and composed of ReLU activation nodes. The additional assumption is that the NN belongs to a bounded $\\beta$-Holder space. The analysis shows that (a) the size of the neural network should be smaller for higher privacy level to ensure generalization and (b) the convergence of the excess risk is achievable if $\\epsilon$ decreases at a rate slower than $O(1/\\sqrt{n})$. The results are further verified experimentally. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Addressing the weaknesses will be appreciated.", "broader_impact_concerns": "The paper rigorously shows an intuitive phenomenon that having label DP would slower down the convergence of the classifier. The other interesting result is that as privacy barrier increases the NN should have smaller depth to ensure better generalisation. These results are interesting though the problem of interest seems very specific from the present draft.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JrNk41ceEN", "reviewer": "Reviewer_vvPN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Comments:\n- I thought the experiments were interesting, well setup and nicely corroborated the theoretical results. I was particularly interested in the behavior as epsilon was varied with n. The stark change in the behavior between eps=1/log(n)sqrt(n), 1/sqrt(n) and logn/sqrt(n), while predicted by the theory was nice to see in practice. Figure 4 and Figure 7 were particularly nice.\n- The authors fixed at the beginning of the paper that their DP algorithm was going to be to perform randomized response on the labels. They then analyzed the impact on downstream tasks of taking these labels at face value. I have two concerns about this setup:\n    - The authors don’t give any justification for the use of binary randomized response in this context. It seems like a somewhat reasonable thing to do, but some justification is required.\n    - When using the local reports in downstream tasks, to the best of my understanding, the authors did not use the fact they they knew the statistical disclosure method. For example, when using randomized response to estimate the mean of a Bernoulli, one does a debasing step since the expectation of the mean resulting from the responses using randomized response is not the mean of the original data. As the authors discuss in Lemma 2, since they are rounding some of this effect disappears, but it wasn’t clear to me that the presence of privacy noise should not be taken into account when defining the optimization problem.\n- The authors make the comment “Lemma 2 theoretically validates the concern that privatized dataset generated by randomized response mechanism might still maintain utility for learning a consistent classifier in downstream binary classification tasks. Therefore, the estimated classifier can be used to infer the labels in the training dataset and leads to privacy leakage of the labels” and a similar comment later in the paper. These comments seem to indicate that the authors are conflating “learning statistical properties of the underlying dataset” with “violating privacy”. I would argue that the key insight of differential privacy is the argument that these are not the same. The privacy loss of each individual is approximately the same as if they had not participated in the data collection (since the classifier would still have been learnt with approximately the same accuracy). I encourage the authors to read the first chapter of the book “The Algorithmic Foundations of Differential Privacy” for more discussion.\n- The main theorems Theorem 1 and Theorem 2 are quite technical and little intuition is given for their proof. In the experimental section the authors give some discussion about what these results imply about how the error trends with various parameters (particularly epsilon). However, it was difficult to absorb these theorems without some discussion of their proof. \n- I did not read the technical proofs in detail but did not see any errors.\n\nMinor Comments:\n- The statement “generally the privacy protection in differential privacy is achieved by injecting noise implicitly to the raw data” is not really true, even in the local model.\n- CDP is not a good acronym for central DP because it is more commonly used for concentrated DP.\n- The authors briefly discuss an add/delete version of label DP described as “robust to the presence or absence of a single label”. I don’t think this makes sense? How can only the label be missing?\n- Something is amiss about the definition of LLDP in Definition 1. This is just the definition of what it means for an algorithm with binary input and output to be eps-DP. The definition doesn’t mention labels at all. I think the authors are conflating a label DP mechanism (which should take (x,y) pairs as input) and the fact that one way to create a label DP mechanism is to release (x,f(y)) where f is eps-DP. On a minor note, I think the log should be inside the absolute value.\n- My understanding is that Lemma 1 is really just a fact about the KL divergence between Bernoulli distributions? If so, I think it would be easier to parse if it was stated in this way, then applied to the specific setting. \n- I found “the exponential term of the training size” to be confusing title. Perhaps just specifying that the training size was on a log scale would be easier to parse?\n- Typo in the second line of the proof of Lemma 2\n- My personal preference would be to have the theorem and lemma statements duplicated in the appendix to minimize flipping between the main body and the appendix. I although think it would be worthwhile to include more intuition in the proofs in the appendix, they are currently quite hard to read. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study use of randomized response to report binary labels under label differential privacy. In particular, they consider the impact of the privacy mechanism on downstream tasks like training neural networks to perform classification. They give several theoretical bounds on the impact on the convergence rate. Their theoretical bounds are supplemented with empirical studies on both synthetic and real datasets. The empirical results provide evidence for the authors 3 main hypotheses (driven by their theoretical results) that 1) for fixed epsilon, the model error converges to 0 as n increases, 2) eps=1/sqrt(n) is a dividing line, above which the model error does not converge to 0 and below which the error does converge to 0. While the first hypothesis is unsurprising, the stark evidence for the second is surprising and convincing. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Justify the use of randomized response as the local randomizer and why no debiasing is required.\n- Provide intuition for proofs of Theorems 1 and 2 to make both the theorem statements and the proofs easier to parse.\n- Either elaborate on or remove comments that imply that learning the estimator even under DP is a bad thing for privacy.", "broader_impact_concerns": "I have no ethical concerns for this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YGiF5sW8P1", "reviewer": "Reviewer_3ueR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. the impact of the randomized response on the bayes opt classifier is essentially the same as the estimation error when the randomized response is used in surveys, therefore, I am not sure if the novelty really exists here.\n\n2. I also think it is generally understood that reducing the privacy parameter --- epsilon --- would require us to design learning algorithms with fewer parameters, and in terms of neural networks, the structure of it should be simplified.\n\n3. in binary classification, it might be more interesting to analyze the impact on the False Positive Rate and the True Positive Rate since often the two classes are imbalanced and the positive samples are rare. Simply looking at accuracy may not reflect the practical impact of the randomized responses. \n\n4. In section 3.2, the authors claimed that the bayes decision rule would stay invariant to the choice of privacy parameters. However, it only would only stay the same when the positive and negative samples are balanced. Perhaps the authors meant to say that the excess risk would stay the same which is proven by Lemma 2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. the submission analyzed the impact of Randomized Response on the performance of a binary classifier, including both the Bayes optimal classifier and a constrained neural network.\n\n2. the analysis also showcases the increase of errors in the estimation with local label privacy implemented through differential privacy.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would recommend the authors think more toward class-imbalanced scenarios. For example, in Ads, the number of people who viewed or clicked on an ad is very rare and usually controlled in A/B testing, therefore, classifying every data sample as a negative sample would lead to very high accuracy, but the true positive rate would be low. Also in the medical domain, patients who are diagnosed with a certain disease or treated with a specific drug are sparse. Thus, it might be more interesting in that direction. ", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally agreed that the results are interesting and sound, albeit focused on a very narrow setting (label DP with randomized response mechanism for downstream binary classification).
Decision: Accept (poster)