Differentially Private Learning with Margin Guarantees
Authors: Raef Bassily
Mehryar Mohri
Ananda Theertha Suresh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
margin theory
generalization bounds

Abstract: We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees. For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviation margin guarantees, as well as an efficient DP learning algorithm with margin guarantees.  We also present a new efficient DP learning algorithm with margin guarantees for kernel-based hypotheses with shift-invariant kernels, such as Gaussian kernels, and point out how our results can be extended to other kernels using oblivious sketching techniques.  We further give  a pure DP learning algorithm for a family of feed-forward neural networks for which we prove margin guarantees that are independent of the input dimension.  Additionally, we describe a general label DP learning algorithm, which benefits from relative deviation margin bounds and is applicable to a broad family of hypothesis sets, including that of neural networks. Finally, we show how our DP learning algorithms can be augmented in a general way to include model selection, to select the best confidence margin parameter.

Differentially Private Learning with Margin Guarantees
Raef Bassily The Ohio State University & Google Research NY bassi ly 100csuueee edu
Mehryar Mohri Google Research & Courant Institute mohri@googll com
Ananda Theertha Suresh Google Research, NY theertha@google.. com
Abstract
We present a series of new differentially private (DP) algorithms with dimension- independent margin guarantees. For the family of linear hypotheses, give pure DP learning algorithm that benefits from relative deviation margin guarantees, as well an efficient DP learning algorithm with margin guarantees. We also present a new efficient DP learning algorithm with margin guarantees for kernel-based hypotheses with shift-invariant kernels, such Gaussian kernels, and point out how our results can be extended to other kernels using oblivious sketching techniques. We further give pure DP learning algorithm for family of feed-forward neural networks for which we prove margin guarantees that are independent of the input dimension. Additionally, we describe general label DP learning algorithm. which benefits from relative deviation margin bounds and is applicable to a broad family of hypothesis sets, including that of neural networks. Finally, we show how our DP learning algorithms can be augmented in general way to include model selection, select the best confidence margin parameter.
Introduction
Preserving privacy is crucial objective for machine learning algorithms. A widely adopted criterion in statistical data privacy the notion of differential privacy (DP) [DMNS06, Dwo06, DR which ensures that the information gained by adversary roughly invariant to the presence absence of an individual in a dataset. Despite the remarkable theoretical and algorithmic progress in differential privacy over the last decade or more, however, its application to learning still faces several obstacles. A recent series of publications have shown that differentially private PAC learning of infinite hypothesis sets is not possible, even for common hypothesis such that of linear functions. In fact, this is the case for any hypothesis set containing threshold functions [BNSV15, ALMM19). These results imply serious limitations for private agnostic learnability.
Another rich body of literature has studied differentially private empirical risk minimization (DP- ERM) and differentially private stochastic convex optimization (DP-SCO) (e.g., [CMS11, JT14, BST14, BFTT19, FKT20, SSTT21, BGN21, AFKT21, BGM21J). When the underlying optimization problem is constrained (constrained setring). tight upper and lower bounds have been derived for the excess empirical risk of DP-ERM [BST14] and for the excess population risk for DP-SCO [BFTT19, FKT20J. These results show that learning guarantees necessarily admit dependency on the dimension d of the form /d/m, where m is the sample size. This dependency is persistent, even in the special case of generalized linear losses (GLLs) [BST14], which limits the benefit of such guarantees, since learning algorithms typically deal with high-dimensional spaces.
When the underlying optimization problem is unconstrained (unconstrained setting) and the loss generalized linear loss, the bounds given by [JT14], [SSTT21] and [BGM21] are dimension- independent but they admit dependency on w 12, where w" is the unconstrained minimizer of the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

expected loss (population risk), or | where W is the unconstrained minimizer of the empirical loss. Since the problem is unconstrained, the norm of these vectors can be very large. even for classification problems for which the minimizer of the zero-one loss admits a relatively small norm. Thus, in both the constrained and unconstrained settings, the learning guarantees derived from DP-ERM and DP-SCO are weak for hypothesis sets commonly used in machine learning.
The results just mentioned raise some fundamental questions about private learning: is differentially private learning with favorable sets? Must one resort to distribution-dependdee bounds instead? In view of the negative PAC-learning results and other learning bounds mentioned earlier, we will seek instead optimistic margin based learning bounds.
guarantees possible for standard hypothesis
In the context of classification, learning bounds for linear hypotheses based on the dimension or, more generally, based on the VC-dimension of the hypothesis set known to be too pessimistic since they deal with the worst case. Instead, margin bounds have been shown to be the most informative and useful guarantees [KP02. SFBL97]. This motivates our study of differentially private learning algorithms with margin- guarantees. Note that our confidence-margin analysis and guaranteess do not require the hard-margin separability assumptions adopted in [BDMN05, LNUZ20J, which is a strong assumption that typically does not hold in practice. Another existing study that deals with somewhat related questions that of [CHS14]. But, the paper deals with a specific class of maximization problems and adopts standaadd definition of margin. Another related line of work that of [RBHT09] and [CMSII] on DP Kernel classifiers. These works either provide suboptimal. cumeension-deeedenn learning guarantees or make strong assumptions about the Fourier coefficients of the kernel predictors. We discuss these prior works in more detail in Section 1.1.
Main contributions. We present a series of new differentially private (DP) algorithms for learning linear classifiers, kernel classifiers, and neural-network classifiers with dimension-indeeeedenl confidence-margin guarantees. In Section 3, we study the family of linear hypotheses. We first give a pure DP learning algorithm with relative deviation margin guarantees. Next, we present an efficient DP learning algorithm with margin guarantees. Our algorithm is based on faster construction for the JL-transform and faster DP-ERM algorithm. While the general structure of our algorithms for linear classifiers is similar to that of [LNUZ20]. our results require new analysis that takes into account the scale-sensitive nature of the margin loss and the p-hinge loss. In Section 4, We present a new efficient DP learning algorithm with margin guarantees for kernel- -ased hypothesis sets, assuming that the positive definite kernel used is shift-invariant, as with the most commonly used Gaussian kernels. Our algorithm combines kernel approximation with the use of the JL-transform. Our result is based on a new style of analysis that uses regularized ERM as reference. These ideas enable us to attain a bound that nearly matches the non-private margin bound, without resorting to the strong assumptions in prior work. Our confidence-margin bounds for DP learning of linear and kernel classifiers nearly match the standard, non- non-private confidence-mant margin bounds. In Section 5, we initiate the study of DP learning of neural networks with margin guarantees. We design a pure DP learning algorithm for family of feed-forward neural networks for which we prove independent of the input dimension and exhibits better dependence on the network parameters than the bounds attained via uniform convergence. Our result entails new analysis of embedding-bel based "network compression" technique. Our margin bound for neural networks is the first of its type. The bound is independent of the input dimension and scales only linearly with the number of activation units. In Appendix E, We further present a label privacy learning algorithm, which we show benefits from relative deviation margin bounds. The algorithm and its guarantee are applicable family of hypothesis sets, including that of neural networks. Finally, we show in Appendix F how our DP learning algorithms can be augmented in general way to include model selection, to select the best confidence margin parameter.
cefiidence-aargnn bound that is
broad
1.1 Related work
Prior work on unconstrained GLLs [JT14] and [SSTT21] showed that it is possible to derive dimension-independer risk bounds for DP-ERM and DP-SCO in the context of linear prediction, when the parameter space is unconstrained and the loss function is convex and Lipschitz (GLL). However, their bounds scale with || I, the norm of the optimal unconstrained minimizer of the expected surrogate loss such as the hinge loss. Also, using their techniques for unconstrained DP- ERM for GLLs together with uniform convergence would yield generalization error bounds that scale with the norm of the unconstrained empirical risk minimizer w. The first issue with this line of work is that the norms of such unconstrained solutions can be very large, thereby resulting in uninformative
2

---

distribution mass
1-a
pasitions
-7
+Y
+
Figure 1: Simple example in dimension one for which the minimizer of the expected hinge loss B[[ (hine((w)) is w" and thus /w") |I J >> 1 yor << 1. Here, any other w > O, in particular with a small norm, achieves the same zero-one loss w²
bounds. In fact, one can construct simple, low-dimensional examples, where || 3mm) while there is a predictor w with || = O(1) that attains the same expected zero-one error, see Figure 1 (a detailed analysis of that example is given in Appendix H). More importantly, the paradigm adopted in this line of work is to first devise an algorithm and next derive bounds for its excess risk. In contrast, we start from strong generalization error bounds, which we use to guide the design of our algorithm.
Prior work on DP learning of hard-margin halfspaces. [BDMN05] and [LNUZ20] studied DP learning of linear classifiers in the separable setting, that is with hard- or geometric margin. [BDMN05] gave a construction based on a private version of the Perceptron algorithm, which results in dimension-dependerr bound the expected error. This result was later improved by [LNUZ20] who gave new constructions with iineensioonindpeedeee guarantees based their nice idea of using embeddings, namely, the fohnson-Lindenstrauss (JL. transform, to reduce the dimensionality of the problem from d to 1/7, where 7 is the geometric margin. Note that the hard-margin separability is strong assumption that typically does not hold in practice. Moreover, the constructions proposed in [LNUZ20] require the knowledge of the margin for their guarantees to be valid. In contrast, our work considers the more general notion of confidence margin, which does not require the existence of a geometric margin and applies to realistic scenarios with non-separable data. Moreover, the confidence-margit parameter, p. in our algorithms tunable and can be optimized. Importantly, our algorithms still yield meaningful learning guarantees even if this parameter is not optimized. Our algorithms for linear classifiers also make use of an embedding as a pre-processing step. However despite the similar structure to that of [LNUZ20], our algorithm requires a new analysis and different settings of parameters. This new analysis is necessary to deal with the scale-sensitive nature of our bounds, due to the absence of a hard-margin.
Prior work on DP Kernel classifiers. [RBHT09] were the first to provide differentially private constructions for SVMs in both the finite-dimensional feature space and kernel settings. However, their constructions are suboptimal and the resulting bounds suffer from polynomial dependence on the dimension of the feature space. In addition, their error bound has sub-optimal dependence on the sample size m and also has an explicit dependence on the fn-norm of the dual variables of the SVM. In general, this norm can be as large as vm, in which case their error bound becomes vacuous. [CMS11] gave a similar construction for shift-invariant kernels. However, their error guarantees are based on the kernel approximation results of [RR08] and hence entail a relatively strong condition on the Fourier coefficients of the kernel predictors and the kernel density. We note that the standard assumption of bounded Reproducing Kernel Hilbert Space (RKHS) norm does not imply such condition. [JT13] gave algorithms for DP predictions with kernels, where the goal to privately generate predictions (labels) on small test set that admits no privacy constraints. In such scenarios, their algorithms do not output a classifier. [JT13] also gave construction for private learner that outputs kernel classifier, however, their construction is computationally inefficient and the resulting error guarantees are dimension-dependent.
2 Preliminaries
We consider an input space X, a binary output space y = {-1,+1} and a hypothesis set H of functions mapping from X' to IR. We denote by D a distribution over Z = X' y and denote by (h) the generalization error and by (h) the empirical error of a hypothesis h e HC:
(h)
E ==(EN)--1 [u)(())
Rs(h) ==
- [1M()))o))
E
where we write ~ S to indicate that is randomly drawn from the empirical distribution defined by S. Given p 2 0, we similarly define the p-margin loss and empirical p-margin loss of h E H:
Reg (h)
E ==(x.))-D [1 [T)N())s)]
Rg(h))
( [1uM())so]
E
==(x-))s
3

---

The p-margin loss is not convex. Hence, we also consider the p-hinge loss to provide computationally- efficient algorithms. For any p > define the p-hinge loss as (P(u) = max (1 - u/p. 0), e R. Similar to the above definitions, given p 0, for sample S, we define the expected and the empirical p-hinge losses as follows:
(w)
E ==(a.y)-1
[ee (yi (w,x,))
[2((w=
E ==(a,))-8
sle _ee (ys (w,z;))
In the context of learning, differential privacy is defined as follows.
Definition 2.1 (Differential privacy). Let ô O. Let A: (X x)) HH be randomized algorithm. We say that A is (e. 8)-DP for any measurable subset H and all S,S' e (X x y) that differ in one sample, the following inequality holds:
P(A(S) E 0) S (FAA(S))
(I)
If 8 0, we refer to this guarantee pure differential privacy.
Private Algorithms for Linear Classification with Margin Guarantees
In this section, we present two private learning algorithms for linear classification with margin guarantees: first, computationally inefficient pure DP algorithm, which we show benefits from relative deviation margin bounds, next, a computationally efficient DP algorithm with a dimension- independent bound expressed terms of the empirical p-hinge loss.
Let (r) e {ar Rd |a: $ r) denote the Euclidean ball in Rd of radius and let X (r) denote the feature space. We will use the shorthand [B for B (1))). We consider the class of linear predictors X defined by HLin {hwi x (w,x) w (A))-. Note that one can represent the general class of affine functions over Rdd as linear functions over IR+ by simply mapping each x Rd to will consider HLin- Here, we view d as possibly much larger than the sample size m. We also note that even though the predictors in the input class Hiin admit A-bounded norm, do not constrain the algorithm output a predictor with bounded norm, which circumvents the necessary dependence on the dimension in constrained DP optimization [BST14].
f =(x, Rd Thus, without loss of generality,
3.1 Pure DP Algorithm for Linear Classification
standard method for designing differentially private algorithms for a continuous hypothesis class is to apply the exponential mechanism [MT07] cover of the hypothesis class. Since HLin is d-dimensional, the size of a useful cover is about 20(4) thus, direct application of the exponential mechanism yields an ((d)-bound; we give a simple example illustrating that in Appendix G. Thus, instead, we seek reduce the size of the cover without impacting its accuracy, using random projections. This results in a mapping & from Rd to a lower-dimensional space IR.
For linear classification, we wish to preserve intra-point distances and angles, that is x x' Φx uzz for points r and z'. known that this property can be fulfilled as a corollary of the lemma [Nel11, Theorem 109]. For completeness, Appendix A. More interestingly, we show that can reduce the dimension to Ö(A77² 1A2r2/pb p²), without the error decreasing significantly. We then run the exponential mechanism in this power-dimensione space and next compute a classifier t in that space. We finally derive classifier in the original space by applying the transpose of the original projection matrix 4 w. Note that the final output " n has expected norm O Vdp) and may not lie in (A).
provide full proof in
Algorithm 1 gives the pseudocode of the full algorithm. The algorithm and the analysis in this section include dimensionality reduction technique for mapping the feature vectors from the input d-dimensional space A-dimennional space, where k O(A??"/p²) for some & e (0, Ar Hence, will be dealing with "compressed" parameter vectors in R To distinguish these two spaces, we will denote the empirical error and the empirical p-margin error in this k-dimensional space as Rsg (w') and R(h) (Ww"), w'), respectively, where w' = and S' (I* >))"

---

Algorithm AprivMeg: Private Learner of Linear Classifiers with Margin Guarantees
Require: Dataset S (1) (Tm,ym)) e (X x (+1))"; privacy parameter 0; margin parameter p Ar]: confidence parameter ,3 0.
1: Let k 0 Aa log
2: Let & be random & d matrix with entries drawn i.i.d. uniformly from {+ Vk
3: Let Sa (x y) 5), where for any R zq. 4x e IR*.
4: Let C. be -over of B (2A).
5: Run the Exponential mechanism over C. with privacy parameter E, sensitivity 1/m, and score function ((( (w) for w E C, to select ú e C.
6: return " Priv x w. where oh denotes the transposition of Φ.
Theorem 3.1. Algorithm I is e-differentially private. For any B E (0, 1), with probability at least
1 3 over the draw of sample S of size from D, the solution w Priv it returns satisfies:
RC Rg(( δ o(v Re (2g(w) ())
A2T2
A
(o
min (E)
mp² p² min (1,))
The proof is given in Appendix B.I. The theorem provides margin guarantee for the private solution. Note that no assumption is made about separability or the existence of a favorable hard- margin. Instead, through the first term, the bound is based the distribution of the empirical margins 2(w-2 I). The theorem suggests that, when the empirical p-margin loss remains small for a relatively large value of the confidence margin parameter p. then w Priv benefits from a strong generalization guarantee. These comments hold similarly for other margin bounds presented in this paper.
This result, although given for a computationally inefficient method, is stronger than several previ- ously known ones: First, it is (s, 0) -pure differential privacy guarantee; second, it is dimension- independent and furthermore, unlike prior work, the norm the optimal hypothesis does not appear in the bound. Furthermore, since it is relative deviation margin bound, it smoothly interpolates between the realizable case of (2) 0 and the case of R²(()) (w) 0. For sample of size m, interpolation between 1//m-term that includes the square-root of the
the bound is based empirical margin loss as a factor and another term in 1/m. In particular, when the empirical margin loss is zero, the bound only admits the 1/m fast rate term. As corollary, note that, up to constants, one can always obtain privacy for E essentially for free.
Dependence on A/p: Our bound depends on the choice of A/p. We note that this fundamentally different from the dependence on ||w"|| in prior works on GLLs [JT14, SSTT21] for two reasons: First, unlike II. A/p i is a measurable and, more importantly, tunable quantity, which we can select an optimal setting for (as we do Appendix F). Second, the optimal choice for this parameter can be much smaller than ||"" as demonstrated in Appendix H.
3.2 Efficient Private Algorithm for Linear Classification
The p-margin loss is not convex and it is known that its minimization is generally intractable. Instead, devise computationally efficient algorithm, whose guarantees are expressed in terms of the empirical p-hinge loss. Algorithm 2 shows the pseudocode of our algorithm. We now discuss the key steps of the algorithm.
Fast JL-transform, Our algorithm entails a dimensionality reduction step (step 3) as in Algorithm 1. Here, we note that the new dimension l is chosen to be Ö(mz), which enables us to control the influence of the dimensionality reduction the empirical hinge loss. We also note that this step is carried out via a fast construction for the JL-transform (Lemma A.4), which takes Oollog(d) d)) time, assuming d em.
Note that, without loss of generality, set A and optimize only with respect p.
5

---

Algorithm 2 AEMPriiMMg:: Efficient Private Learner of Linear Classifiers with Margin Guarantees
Require: Dataset S = U1)..... (Im, Vm)) e (B' (R) (+1))" privacy parameters e, 6; norm bound A; margin parameter p (0, Ar]; confidence parameter / > O.
1: Let k cm log(mn/
log 2 (1/8) (1/(1
2: Let d be random i d matrix from the construction in Lemma A.4.
3: Let Ss = (2 (x.); (x, e S), where for any E R F.p 4 tee e I& and (l)) is the Euclidean projection on B (2r).
4: Privately solve the convex ERM problem: argmin Ir (w) via Algorithm 4 (Appendix B.2) (2A)(2A)
and return to é BB (2A).
5: return w. Priv Tiú where TT denotes the transposition of Φ.
Near linear-time DP convex ERM. After this step, invoke an efficient algorithm for DP-ERM (step in Algorithm 2) find an approximate minimizer of the empirical p-hinge loss I's (w). rather than using the exponential mechanism to find an approximate minimizer for the empirical zero-one loss Rss,, (w). To improve the running time of step 4, Algorithm 2] to solve DP-ERM near-linear time and with high-probability guarantee on the excess empirical risk (see Algorithm 4 in Appendix B.2). The algorithm of [BGM21] is devised for DP-SCO with respect to non-smooth generalized linear losses. It is based on a combination of a smoothing technique via proximal steps and the phased SGD algorithm [FKT20, Algorithm 2] for smooth DP-SCO. The algorithm of [BGM21] can be used for DP-ERM if it is fed with sample from the empirical distribution of the dataset. However, the privacy guarantee requires a careful privacy analysis to deal with the fact that this sample may contain duplicate entries from the original dataset.
the construction in [BGM21,
Moreover, since the original algorithms in [FKT20, BGM21] provide only expectation guarantees and we aim at peebh-bbbbblltyy learning bounds, we use a standard private confidence boostingg technique to provide high-pre bigohbpbbabblityy guarantec the excess risk of our variant. We summarize the guarantees of this variant in the following lemma. The details of the construction and the proof of the lemma below be found in Appendix B.2.
Lemma 3.1. Let m N. 0 8 < 1, and 0 E log(1/6). Algorithm 4 (Appendix B.2) is (E, 8)-D. m²
Let 8 e (0,1). Let & N. and i, O. Let 5 E (IB (+1))" be the input dataset and B B*(A) be the parameter space. With probability 1 - over the randomness in Algorithm 4, the output w satisfies
o
Volog& 3 log( 2)
AF O (g(
1
I5(w)+ S min (E3
vm
Em
Moreover, Algorithm 2 requires (m (og(mmmm log(1/B)) gradient computations.
We now state our main result in this section, which we prove in Appendix B.3.
Theorem 3.2. Let O < < 1 and 0 < é log( (18). Algorithm 2 is (e, (),6)-DP. Let 3 E (0, 1). Let S 1 for distribution D over Bd(r) (+1). Algorithm 2 outputs w Priv e Rd such that with probability at least 1 - 3, we have
R (w Priv)
Dz(w)= + δ
Ar
s
min
web
PV mmmminn,s))m
Moreover, Algorithm 2 runs in time O (md log( (aa (d, m)) + em2 log(m)/ log logo (1/6))
Private Algorithms for Kernel-Based Classifiers with Margin Guarantees
In this section, we present private algorithms with margin guarantees for kernel-based predictors [SS02, STC04]. We first consider a continuous, positive definite, shift-im inftrianv kernel K:X'X' + R, where K ((xx2) x) 22 for all e X. The associated feature map is defined as vxx) # K(.x), e X. where X (r).

---

Overview of the technique. Our approach is based on approximating the feature map ab by fintee-dimensionl feature map 3o X - B (r) determined via Random Fourier Features (RFFs). The dimension 2D of the approximate feature map is chosen to be sufficiently large to ensure that for all pairs of feature vectors Z1, 2. in training set S = ((11,31).-.
(Fm, Um ) we have (T)))) (xr))) K K x,)] & m with high probability over the randomness of v (due to RFFs). This suffices to derive an upper bound (margin bound) on the true error of a finiteddimensional linear predictor trained on the sample made of the labeled points (v))), y). (I, y) E S, that is essentially the same the margin bound known for the kernel classifier. Hence, in effect, we reduce the problem to that of learning a linear classifier in a 2D-dimensional space, which we can solve privately using Algorithm 2. Note that the output predictor in this case is diite--imensional linear function rather than function in the Reproducing Kernel Hilbert Space. A full description of our DP learner of kernel classifiers is given in Algorithm 3 below.
Bochner's Theorem and RFFs. Since the kernel K' is shift-invariant, it can be expressed as k(x,x') = r ((= x.), x' E X for some function K: Z - IR where Z = (= = x x':x, ). Moreover, since K is positive-definit, K is the Fourier transform of a probability distribution PR:
kxx)= fxx edw.))) PR (w(W)d..
This follows from Bochner's Theorem [Rud17]. Random Fourier Features (RFFs) provide a simple method introduced in [RR07] to approximate kernel feature maps in data-independent fashion. The idea is based on Bochner's s theorem. In particular, we first sample wi,.... wD independently from the probability distribution PR. Then, we define an approximate feature map as follows:
x
sin (cos (wi, x), sin (w),)),.. x).... cos (WD, x), sin (wD,.)), Var E X.
(2)
For D sufficiently large, it can be shown that (T(x), ((x') concentrates around K (z,x') for all pairs z, x' e X [MRT18, Theorem 6.28]. In our analysis below, we only need that concentration to hold uniformly over pairs x, x' from a fixed training set rather than uniformly over all pairs x, e X. This leads to a simpler approximation guarantee, which we formally state below.
Theorem 4.1. Let Sx (zq,...,,Iml where kxx,x) = x², Vx E X. Let PR be the probability distribution associated with K. Suppose wi...., WW are drawn independently from PR. With probability 1, we huve [[ = r, Va E X. For any B (0, 1), with probability least for all i, [m]] such that i # j we have
X Let K a shift-invariant, positive definite kernel,
log 3
(V(x:) K (z,, (I,, 2
D
Proof. The first assertion related to [x(x)) 2 Vr X' follows directly from the definition of (z) and basic trigonometric identity. The proof of the second assertion about the inner products follows from the identity wi....
[(V();))
xz) that holds for all Ty, the application of
Hoeffding's 's bound combined with the union bound over all æ m² pairs 3i Sx The unbiasedness of (*(),, ((x,),,(x;)) follows from the fact that the expectation is the Fourier transform of r P2 (w).
which, by Bochner's Theorem, is ,2 K (2; - 2z) K 2z).
We now state our main result, which we prove in Appendix C.
Theorem 4.2. Let r > O. Let K : X x X + E be a
positive definite kernel, where
K(,,x)= x2 for all x X. For any 0 and d (0, 1), Algorithm 3 is (E, (e,8) -differentially private. Define HA = (h E H: ||w]aa S A}, where ll-laa is the norm corresponding to the reproducing kernel Hilbert space (RKHS) H. associated with the kernel K. Let 3 (0. 1). Given an input sample S of m
examples drawn i.i.d. from distribution D over X x {=1}, Algorithm 3 outputs h yom such that with probability at least 8, we have
Ar
Ro (1. ( ) min IG (t) Ō
heMe
PV min (1,
7

---

Algorithm 3 AprivKerMrg Efficient Private Learner of Kernel Classifiers with Margin Guarantees
Require:
" shift-invariant, positive definite kernel K : X' X - R with K (T,,a) = =r" for all E X, privacy parameters e, o. Reproduc-
Dataset 5 = ((11,3)).... ...., (fm::mm) y (X x {+1))
ing kernel Hilbert space (RKHS) norm bound A; margin parameter p (0, 2Ar]; confidence
parameter 3> 0.
1: Let Px be the probability distribution associated with K.
2: Let D = m² log(2m/3).
3: Draw Wi....,WD independently from Pg.
4: Let $3 ((i()z),, U:): [m]): where ub is as defined in (2).
5: Privv + AEErPiIMMggg (Sp. E, 2A, p. 3.2),) where AERPiivMMg is the private learner described in
Algorithm 2. Note that the input dimension AERPrivMrg 2D rather than d, and the norm bound parameter is 2A.
6: return Private predictor Nyp X R defined as Vx E X, h wpr (x) + Pur (())).
where, for any h E H.. (h) = n. E with the kernel K and (::)) is the inner product associated with the RKHS H.
E (ys (h, (z:)) where & is the feature map associated
Our results can he extended to polynomial kernels using a different approach to construct finite-dimensional approximation of the kernel. A polynomial kernel of degree p. denoted as Kp, can be expressed as (p, xx) = ((r, xir,z") + c)², x, x' 6 X and > is some constant. Note that feature map u associated with such kernel can be expressed as vector in R where d = Odd)). ). In particular, V (x) is the vector of all monomials of a p-th degree polynomial. Ignoring computational efficiency considerations (or when p is a small constant), there is simpler private construction than the one used for shift-invariant kernels. In that case, we can directly use the JL-transform to embed (1)(()))..... (2 } into a k-dimensional subspace exactly as in Section 3.2, which would result in a k-dimensional approximation of the kernel (by the properties of the JL-transform). Hence, we can directly use Algorithm 2 on the dataset S (x1) (x1), (.)))....... ..... v ) ym )). We therefore obtain the same bound on the expected error as above except that would then be rp, That dependence on re is inherent in this case even non-rrivately since Kip (x, 2) can be as large as r² However, as discussed below, more efficient solutions can be designed for approximating these and many other kernels.
Polynomial kernels:
Further extensions. Our work can directly benefit from the method of [LSS13], which is computa- tionally faster than that of [RR07], O ((m++d) +d) log d), instead of O(d).. Their technique also extends to any kernel that is a function of an inner product in the input space. We can further use, instead of the JL-transform, the oblivious sketching technique of [AKK* 20] from numerical linear algebra, which builds on previous work by [PP13] and [ANW14], 14]. to design sketches for polynomial kernel with target dimension that is only polynomially dependent on the degree of the kernel function, as well as a sketch for the Gaussian kernel on bounded datasets that does not suffer from an exponential dependence on the dimensionality of input data points. More recently. [SWYZ2I] presented new oblivious sketches that further considerably improved upon the running- tamingg-imme time complexity of these techniques. Their method also applies to other slow- growing kernels such as the neural tangent (NTK) and arc-cosine kernels.
5 Private Algorithms for Learning Neural Networks with Margin Guarantees
In this section, we describe a private learning algorithm that benefits from favorable margin guarantees when run with family of neural networks with very large input dimension.
We consider a family HNN of L-layer feed-forward neural networks defined over (r),,, with d potentially very large compared to the sample size m. A function h in HNN can be viewed as a cascade of linear maps composed with a non-linear activation function (see Figure 2, left column). Here, Wi,... W, are the weight matrices defining the network and 1 is a non-linear activation. For simplicity, the width (number of neurons) each hidden layer, denoted by N, assumed to be the same for all the layers. Also, assume that the output of the network is
8

---

real scalar and hence we have WE E R. Furthermore, we assume no activation in the output layer. We also assume the same activation uh: R. + EN for all layers and choose it to be sigmoid function: for any u (u1,-.., ux) I (b)) (on( ... (a.)) ,,,(x)),, for some > O, where (a((a= = --e- mhm R. Note that o, is n-Lisschitz and thus & is n--ipschitz with respect to Il for any u, u IR [lv)(u) (1)ll2 s 1 u - rll2. A typical choice for 17 in practice is 7) = 1, but we will keep the dependence on for generality. We define NNNA as the subset of HNN with weight matrices that are A-bounded in their Frobenius norm: for all j E [L]. [1W F S A for some A
We design pure DP algorithm for learning L-layer feed forward net- works in NNNS that benefits from the following margin- maagen-based guarantee.
1
4b gd
Theorem 5.1. Let E > 3, (0, 1), and p O. Then, there is an E-DP algorithm which returns an L-layer network Prr with N neurons per layer that with probability at least 1 - B over the draw of sample ~ DTm and the internal randomness of the algorithm admits the following guarantee:
W 3x
NxX
8 MM
R: e 1p
(h) + O r(2 VNO (22AA)2 NO
Rh s
min
P:R 3" W, E
he HNAA NNA
P/m
Peem
R
where 0 = logllog(/L///) (og(((1)11)
h HNN
W7 R y
Note that this guarantee is independent of d and, assuming L is a constant, the bound scales roughly as V p.m p²em* where p is the
N N
h E Hii
confidence-margin parameter and é is the privacy parameter. Note that, for E # 1, the bound scales with v# neurons, which more favorable than standard bounds obtained via uniform convergence argument, which depend on d, as well as the total number of edges ((N2)) in addition to a similar dependence on A
Figure 2: Illustration of the neural networks before and af- ter JL-trrnsforms.
Our construction. Our DP learner is based on using embeddings & RR- p.... Pr.11 RR given by data-independent JL-transform matrices to reduce the dimension of the inputs in each layer, including the input layer, to k 0(
((22)))) p²
We randomly generate a set +- = (Po...., 2r.11)
of L independent JL matrices whose dimensions are described as above. We let JCNN denote the family of T.-layer neural networks, where each network h HGNN is associated with weight matrices T W..... T 1-1 WL for W, e RR*N .j e [L - 1], and WL E IR lx1 (see Figure 2, right column). We define H NN c Hr where [[Wll s 2A for all j [T]. We start by creating 7-cover C of the product space of the matrices W W,...,, WE associated with HCB NNZA. where 0 (())))=
C is a y-cover of B (2A) x... B NBA)NNNNN= x B (2A) with respect to V 1. We define Re NNa KNN be the corresponding family of networks whose associated matrices are in C. Given an input dataset S = (I),,)))..... (Zm: )) e (BT(r) (=1))"", we then run the exponential mechanism over with privacy parameter e, the score function being the empirical zero-one loss Rs (h): e Feh T and the sensitivity 1/m, to return a neural network Priv Fe
NNZA.
6 Conclusion
We presented series of new differentially private algorithms with dimension-indeepeneen margin guarantees, including algorithms for linear classification, kernel-based classification, or learning with a family of feed-forward neural networks, and label DP learning with general hypothesis sets. Our kernel-based based algorithms can be extended to non-linear classification with many other kernels, including a variety of kernels that can be approximated using polynomial kernels, using techniques based on oblivious sketching. Our study of DP algorithms with margin guarantees for family of neural networks can be viewed as an initiatory step that could serve as the basis for a more extensive analysis of DP algorithms for broader families of neural networks.

---

Acknowledgments and Disclosure of Funding
This work was done while RB was visiting scientist at Google, NY. RB's work OSU on this research is supported by NSF Award AF-1908281 I and Google Faculty Research Award.
10

---

References
[AC06] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson- Lindenstrauss transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557-563, 2006.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in geometry. arXiv preprint arXiv:2103.01516, 2021.
[AKK*20] Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 141-160. SIAM, 2020.
[AL09] Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series dual BCH codes. Discrete & Computational Geometry, 42(4);6 15-6600, 2009.
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. Moses Charikar and Edith Cohen, editors, Proceedings of the st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852 352-860. ACM, 2019.
[ANW14] Haim Avron, Huy L. Nguyen, and David P. Woodruff. Subspace embeddings for the polynomial kernel. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q Weinberger, editors, Advances in Neural Information Process- ing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 2258-2266, 2014.
[Bar98] Peter L Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions Information Theory, 44(2):525- 536, 1998.
[BDMN05] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Chen Li, editor, Proceedings of the twenty-fourth ACM SIGACT- SEEMOD-SIGARY Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA, pages 128-138. ACM, 2005.
[BFSV*21a 21a] Robert Istvan Busa-Fekete, Umar Syed, Sergei Vassilvitskii, et al. On the pitfalls of label differential privacy. In NeurlPS 202/ Workshop LatinX in AI, 2021.
[BbSV+21b] Robert Istvan Busa-Fekete, Umar Syed, Sergei Vassilvitskii, et al. Population level privacy leakage in binary classification wtih label noise. In NeurIPS 202/ Workshop Privacy in Machine Learning, 2021.
[BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochas- tic convex optimization with optimal rates. arXiv preprint arXiv:1908.000 2019.
[BGM21] Racf Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochas- tie optimization: New results in convex and non-convex settings. arXiv preprint MrXiv:2107.05585. Appeared at NeurIPS 2021., 2021.
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. arXiv preprint arXiv:2103.01277 2021.
[BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 649. IEEE Computer Society, 2015.
[BST99] Peter Bartlett and John Shawe-Taylor Generalization performance of support vector machines and other pattern classifiers. Advances in kernel methods: support vector learning, pages 43-54, 1999.
11

---

[BST14] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk mini- mization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 464-433 IEEE Computer Society, 2014.
[CGM19] Corinna Cortes, Spencer Greenberg, and Mehryar Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelligence, 85(1) 3:45700, 2019.
[CHS14] Kamalika Chaudhuri, Daniel J. Hsu, and Shuang Song. The large margin mechanism for differentially private maximization. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Infor- mation Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Monireal, Quebec, Canada, pages 1287-1295, 2014.
[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069-1 11009 2011.
[CMTS21] Corinna Cortes, Mehryar Mohri, and Ananda Theertha Suresh. Relative deviation margin bounds. In International Conference on Machine Learning, pages 2122-2131.
PMLR, 2021.
[DMNS06]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY. USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):21 1-407, 2014.
[Dw006] Cynthia Dwork. Differential privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Progrumming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1-12. Springer, 2006.
[EMSV21] Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. arXiv preprint urXiv:21 2021.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex opti- mization: optimal rates in linear time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, II. USA, June 22-26, 2020, pages 439-449. ACM, 2020.
[GGK*21] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. On deep learning with label differential privacy. arXiv preprint arXiv:2102 060662 2021.
[JL84] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space 26. Contemporary mathematics, 26:28, 1984.
[JT13] Prateek Jain and Abhradeep Thakurta. Differentially private learning with kernels. In International conference on machine learning, pages 118-126 PMLR, 2013.
[JT14] Prateck Jain and Abhradeep Thakurta. (near) dimension independent risk bounds for differentially private learning. In ICML, 2014.
[KP02] Vladmir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. Annals of Statistics, 30, 2002.
12

---

[WW11] Felix Krahmer and Rachel Ward. New and improved SeansonnLindenstrauue embed- dings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 1383):1269-1281, 2011.
[LN17] Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstraus lemma. In 20/7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638. IEEE, 2017.
[LNUZ20] Huy Nguyen, Jonathan Ullman, and Lydia Zakynthinou. Efficient private algorithms for learning large-margin halfspaces. In Algorithmic Learning Theory, pages 704-724, PMLR, 2020.
[LSS13] Quoe V. Le, Tamás Sarlós, and Alexander J. Smola. Fastfood computing Hilbert space expansions in loglinear time. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 244-252. JMLR.org. 2013.
[MRT18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of machine learning. MIT press, 2018.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
[Nel10] Jelani Nelson. Mainson-Lindenstraant notes, 2010.
[Nel11] Jelani Jelani Osei Nelson. Sketching and streaming high-dimensionall vectors. Phl) thesis, Massachusetts Institute of Technology, 2011.
[Nel15] Jelani Nelson. Dimensionality reduction notes 2, 2015.
[PP13] Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239-249 2013.
[RBHT09] Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in large function space: perecc-preservinggg mechanisms for svm learning. arXiv preprint arXiv:0911.5708, 2009.
[RR07] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 1177-1184. Curran Associates, Inc., 2007.
[RR08] Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replac- ing minimization with randomization learning. Advances in neural information processing systems, 21, 2008
[RS16] Sofya Raskhodnikova and Adam Smith. Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 495-504. IEEE, 2016.
[Rud17] Walter Rudin. Fourier anulysis groups. Courier Dover Publications, 2017.
[SFBL97] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In ICML, pages 322-330, 1997.
[SS02] Bernhard Schölkopf and Alex Smola. Learning with Kernels. MIT Press: Cambridge, MA, 2002.
13

---

[SSTT21] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse dimensionality in unconstrained private glms. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2638-2644 PMLR, 13-15 Apr 2021.
[STC04] John Shawe- Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cam- bridge Univ. Press, 2004.
[SWYZ21] Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9812-9823, PMLR, 2021.
[YSMN21] Sen Yuan, Milan Shen, llya Mironov, and Anderson CA Nascimento. Practical, label private deep learning training based on secure multiparty computation and differential privacy. Cryptology ePrint Archive, 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] There are no foreseeable negative societal impact for this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs are provided in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "w2m6G-OMaP", "reviewer": "Reviewer_kUdN", "summary": "This paper develops several differentially private algorithms with dimension-independent utility guarantees. The results include a pure DP-algorithm and an efficient private algorithm for linear classification. The paper further extends these results to kernel-based hypotheses with shift-invariant kernels and feed-forward neural networks. For all the algorithms, the paper develops margin guarantees independent of the dimension.", "questions": "Question\n- In the introduction, the authors say that learning guarantee necessarily admits a dependency on $d$ for constrained setting. However, it seems that the paper considers a constrained problem setting: Algorithm 2 involves a minimization over $B^k(2\\Lambda)$, the linear predictors are also constrained as $w\\in B^d(\\Lambda)$. Therefore, it is a bit confusing to me whether the dimension-independent bounds contradict with existing results.\n- The paper uses the technique of margin and random projection. It is not clear to me which one is essential to develop dimension-independent guarantee. It would be helpful if the authors could comment on how the margin technique is useful in improving the DP guarantee.\n\nTypos:\n\nSection 4: $(\\tilde{\\Psi}(x),y))$\n\nSection 4: can designed\n\nSection 4: builds on on\n\nLemma A.2: the meaning of fat is not rigorous", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe existing DP algorithms suffer from a bound with a dependency on either the dimension or the norm of the optimal model, which would not be effective if the dimension or the norm of the optimal model is large. This paper shows that these dependency can be removed and develops several algorithms based on margin guarantees. Therefore, the results are interesting to the differential privacy community.\n\nWeakness:\n- The bound in Theorem 5.1 suffers from an exponential dependency on the depth. Therefore, the result is not efficient if $L$ is moderately large.\n- For the pure DP algorithm, the bounds have a quadratic dependency on $1/\\rho$. The bounds would not be effective if $\\rho$ is small.\n- The paper presents a series of results. While these results are comprehensive, they may make the paper not focused.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "spzIy5XVtLO", "reviewer": "Reviewer_kj5q", "summary": "This paper introduces several new differentially private learning algorithms with performance guarantees that are independent from the data input dimension and instead given in terms of a confidence margin parameter.\nAlgorithms are presented for linear classification, kernel classifiers, and neural networks. One of the key tools of the analysis is to use the JL transform to map the hypotheses to a lower-dimensional space, perform learning there, and then to “invert” the transform.", "questions": "What is $r$ in Theorem 5.1? It appears undefined in the main text.  \nCan the algorithm for learning the NN be efficiently implemented? What is the significance of the bounded norm assumption?\n\nMinor comments: The sentence in lines 102-104 should be fixed  \n111 and 112: yields/makes: remove s  \n128: “gave construction”  \n138 and 139: the term “$\\rho$-hinge loss” is overloaded  \nAlg. 1 line 4: “an”  \n186: “empirical $\\rho$-margin” should be “empirical $\\rho$-margin loss”?  ", "limitations": "The impact of the assumptions that are made is not extensively discussed in the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides interesting results regarding a relevant topic. While many of the main ideas appear to be similar to prior work, the analysis requires non-standard technical extensions, and the resulting bounds are clear improvements.\nThe models that are studied cover a wide variety of use cases, and both inefficient algorithms, but which are stronger in terms of privacy guarantees, as well as computationally efficient algorithms, at the cost of weaker privacy guarantees, are considered.\n\nIn terms of weaknesses, the practicality of the results and limitations could be discussed to a further extent. The bound in Theorem 5.1 could be further discussed to elucidate the role of the parameters—it appears that $r$ is not even defined here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cEd9xL_o2pt", "reviewer": "Reviewer_6Kj9", "summary": "The paper presents differentially private algorithms with dimension-independent margin guarantees for various classification problems such as linear classification, kernel-based classification, and feed-forward neural network classification. The key to the algorithm for linear classification is using the FAST JL transform for feature space reduction and then using the DP-ERM algorithm from  [BGM21] for solving the convex optimization problem (along with standard boosting techniques). The key to the algorithm for private kernel-based classification is to first approximate the feature map by a finite-dimensional map determined via Random Fourier Features. Finally, for  Feed Forward Neural Networks classification, the authors rely once again on the JL transform to reduce the dimensionality before each layer and apply the exponential mechanism to achieve pure differential privacy.\n\nOverall, this is a compressive and systematic study on differentially private classification and I recommend it be expected.", "questions": "None.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a bunch of elegant algorithms for differentially private classification. While the technical components used in the algorithms are well known, the literature review, as well as results, are comprehensive. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M7eRxNAyGmR", "reviewer": "Reviewer_NXiP", "summary": "This paper proposes a series of DP algorithms for learning linear classifiers, kernel classifiers, and neural-network classifiers with dimension-independent and confidence-margin guarantees. It leverages JL-transform and a faster DP-ERM algorithm to design the faster DP linear classifier with margin guarantees. It combines kernel approximation with the use of the JL-transform to design the DP kernel classifiers with margin guarantees. And in the end, the authors propose a DP neural network learning algorithm for a family of feed-forward neural networks for which they prove a confidence-margin bound that is independent of the input dimension via embedding-based ``network compression'' technique. This enables a broader analysis of DP neural network in the future.", "questions": "1. Is it possible to apply advanced composition during the privacy leakage analysis?", "limitations": "Yes. The authors have addressed  potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper introduces its DP algorithms step by step from the DP linear classifer, to the DP kernel classifier and finally the DP neural nework with a very large input dimension and margin guarantees, which makes it easier to understand.\n2. Using fast JL-transform to reduce the high dimensionality to improve the time complexity is a nice optimization.\n3. Using the embedding-based network compreesion technique to improve the DP neural network learning algorithm.\n\nWeakness:\n1. There is no experiments to enhance the theoretical conclusions. It will be better even if the authors can run toy experiments on some small datasets.\n2.  It is possible to improve the privacy leakage via advanced composition.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept