Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks
Authors: Jiayuan Ye
Zhenyu Zhu
Fanghui Liu
Reza Shokri
Volkan Cevher
Venue: NeurIPS 2023 poster (2023)
Keywords: overparameterized neural network
privacy

Abstract: We analytically investigate how over-parameterization of models in randomized machine learning algorithms impacts the information leakage about their training data. Specifically, we prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets, and explore its dependence on the initialization, width, and depth of fully connected neural networks. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training. Notably, for the special setting of linearized network, our analysis indicates that the squared gradient norm (and therefore the escalation of privacy loss) is tied directly to the per-layer variance of the initialization distribution. By using this analysis, we demonstrate that privacy bound improves with increasing depth under certain initializations (LeCun and Xavier), while degrades with increasing depth under other initializations (He and NTK). Our work reveals a complex interplay between privacy and depth that depends on the chosen initialization distribution. We further prove excess empirical risk bounds under a fixed KL privacy budget, and show that the interplay between privacy utility trade-off and depth is similarly affected by the initialization.

Initialization Matters: Privacy-Utiitty Analysis of Overparameterized Neural Networks
Jiayuan Yei, Zhenyu Zhu Fanghui Liu Reza Shokrit, Volkan Cevhert
National University of Singapore "jjayuan, "jiaayuan,rezaaycom nus edu. ag 'fanghui. liuwvarwick.ac. ac.
EPFL, Switzerland 3 University of Warwick "Zhenny. zhu, volkan. cewher)
Abstract
We analytically investigate how over over-varamenn rreerearamtttiintooonn models in randomized machine learning algorithms impacts the information leakage about their training data. Specifically, we prove privacy bound for the KL divergence between model distributions on worst-case neighboring datasets, and explore its dependence on the initialization, width, and depth of fully connected neural networks. We find that this KL. privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training. Notably, for the special setting linearized network, our analysis indicates that the squared gradient norm (and therefore the escalation of privacy loss) is tied directly to the per-layer variance of the initialization distribution. By using this analysis, bound improves with increasing depth under certain initializations (LeCun and Xavier). while degrades with increasing depth under other initializations (He and NTK). Our work reveals a complex interplay between privacy and depth that depends on the chosen initialization distribution. We further prove excess empirical risk bounds under fixed KI, privacy budget, and show that the interplay between privacy utility trade-off and depth is similarly affected by the initialization.
demonstrate that privacy
Introduction
Deep neural networks (DNNs) in the over wer-parameterized regime (i.e., more parameters than data) perform well in practice but the model predictions can easily leak private information about the training data under inference attacks such membership inference attacks 44 and reconstruction attacks 117
7 29 This leakage can be mathematically measured by the extent to which the algorithm's output distribution changes DNNs are trained on neighboring dataset (differing only in one record), following the differential privacy (DP) framework [23].
To train differential private model, typical way is to randomly perturb each gradient update in the training process, such as stochastic gradient descent (SGD), which leads to the most widely applied DP training algorithm in the literature: DP-SGD 22. To be specific, in each step. DP-SGD employs gradient clipping, adds calibrated Gaussian noise, and yields differential privacy guarantee that scales with the noise multiplier (i.e., per-dimensional Gaussian noise standard deviation divided by the clipping threshold) and number of training epochs. However, this privacy bound (2 is overly general as gradient clipping artificially neglects the network properties (e.g., width and depth) and training schemes (e.g., initializations). Accordingly, a natural question arises in the community:
How does the peerptaramttriization of neural networks (under different initializations) affect the privacy bound of the training algorithm over worst-case datasets?
Work was done while Fanghui was at LIONS, EPFL.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Our privacy utility trade-off bounds for training linearized network (3) via Langevin diffusion. under different -adernllayer width m, depth L and initializations. The per-layer widths ma = d. mi;" mir-1 = m and my = o where d is the data dimension and o is number of classes. For KL. privacy bounds, we assume Assumption 2.2 holds and I. 2 2 for simplicity. For the excess risk bounds, we assume = 1, d, m = Ω (n) are large, and Assumption 2.2 Under LeCun and Xavier, we prove privacy utility trade-offss that improve with ovrr-parraettniizationn (increasing depth).
Approximate lazy training distance
Excess Empirical risk under e- E-KL privacy (Corollary 6.4
Variance 31 for layer I
Gradient norm constant B 7
Initialization
R (
LeCun 34
1 1/ml-
om 1+ )
1
1 n
+
1
2
1+ L
2
He 30
2/ml-1
om([ L + mm
Ö m
1
0
1
1
L-1+
n-
2
NTK 3
2/mi, < 1/0, L
dm L-1 +
δ m
L-1 1
1
d
Xavier 27
Ann 24 (1+
od( 1-L-11 14
d+n
① (1+ [1+
Ô n
1R 1191
11+ m
L
2
2m
To answer this question, we circumvent the difficulties of analyzing gradient clipping, and instead algorithmically focus on analyzing privacy for the Langevin diffusion algorithm without gradient clipping nor Lipschitz assumption on loss function. It avoids an artificial setting in DP-SGD 2 where constant sensitivity constraint is enforced for each gradient update and thus makes the privacy bound insensitive to the network over- parameterization. Theoretically, we prove that the KL privacy loss for Langevin diffusion scales with the expected gradient difference between the training on any two worst-case neighboring datasets (Theorem 3.1 F By proving precise upper bounds on the expected f--norm of this gradient difference, we thus obtain KI. privacy bounds for fully connected neural network (I (Lemma (.2) and its linearized variant (Corollary 4.2) that changes with the network width, depth and per-layer variance for the initialization distribution. We summarized the details of our KL privacy bounds in Table I and highlight our key observations below.
Width always worsen privacy, under all the considered initialization schemes. Meanwhile, the interplay between network depth and privacy is much more complex and crucially depends on which initialization scheme is used and how long the training time is.
Regarding the specific initialization schemes, under small per-layer variance in initialization (e.g. in LeCun and Xavier), if the depth is large enough, our KL privacy bound for training fully connected network (with small amount of time) as well as linearized network (with finite time) decays exponentially with increasing depth. To the best of our knowledge, this is the first time that an improvement of privacy bound under over over- vreeparrmettiizttionnn is observed.
We further perform numerical experiments (Section 5) on deep neural network trained via noisy gradient descent to validate our privacy analyses. Finally, we analyze the privacy utility trade-off for training linearized network, and prove that the excess empirical risk bound (given any fixed KL privacy budget) scales with a lazy training distance bound R (i.e., how close is the initialization to a minimizer of the empirical risk) and gradient norm constant B throughout training (Corollary 6.44) By analyzing these two terms precisely, we prove that under certain initialization distributions (such as LeCun and Xavier), the privacy utility trade-off strictly improves with increasing depth for linearized network (Table [T. To our best knowledge, this is the first time that such gain in privacy-utility trade-off due to over-parametterizatin (increasing depth) is shown. Meanwhile, prior results only prove (nearly) dimension- coanension-independdee independent privacy utility trade-off for such linear models in the literature 45 32 37.. Our improvement demonstrates the unique benefits of our algorithmic framework and privacy-utilin analysis in understanding the effect of over pwer-paramttrrzzation.
A key difference between this paper and existing privacy utility analysis of Langevin diffusion 26 is that we analyze in the absence of gradient clipping or Lipschitz assumption on loss function. Our results also readily extend to discretized noisy GD with constant step-size (as discussed in Appendix E
'We focus on KL privacy loss because it is a more relaxed distinguishability notion than standard (c. dP- and therefore could be upper bounded even without gradient clipping. Moreover, KL divergence enables upper bound for the advantage (relative success) of various inference attacks, studied in recent works (3 28

---

1.1 Related Works
over-parameterization in DNNs and NTK. Theoretical demonstration the benefit of over- parameterization in DNNs occurs in global convergence 3 21 and generalization [6]. Under proper initialization, the training dynamics of over-parameterized DNNs can be described by a kernel function, termed as neural tangent kernel (NTK) [31], which stimulates a series of analysis in DNNs. Accordingly, wver-parameterization has been demonstrated be beneficial/harmful to several topics in deep learning, c.g., robustness [T]] [4], covariate shift [50]. However, the relationship between wverparraettriization and privacy (based on the differential privacy framework) remains largely an unsolved problem, as the training dynamics typically change [14 after adding new components in the privacy-preserving learning algorithm (such as DP-SGD 22 to enforce privacy constraints.
Membership inference privacy risk under over-parameterization. A recent line of works [47 48 investigates how prrpeaaamettiizitionn affects the theoretical and empirical privacy in terms of membership inference advantage, and proves novel trade-off between privacy and generalization error. These literature closet to objective of investigating the interplay between privacy and over- parameterization. However, Tan et al. [4 48 focus on proving upper bounds for an average-cass privacy risk defined by the advantage (relative success) of membership inference attack models trained from randomly sampled training dataset from a population distribution. By contrast, our KL privacy bound is heavily based on the strongest adversary model in the differential privacy definition, and holds under an arbitrary worst-case pair of neighboring datasets, differing only in one record. Our model setting (e.g., fully connected neural networks) is also quite different from that of Tan et al. The employed analysis tools are accordingly different.
47 48.
Differentially private learning in high dimension. Standard results for private empirical risk prove that there is an unavoidable factor d in the empirical risk and population risk that depends on the model dimension. However, for unconstrained optimization, is possible to seek for the dimension-deependenny in prov- ing risk bounds for certain class of problems (such as generalized linear model (5)). Recently, there is a growing line of works that proves wwweeniionnindeendeee excess risk bounds for differentially private learning, by utilizing the low-rank structure of data features [45] gradient matrices [32 (37 during training. Several follow-up works 33 B further explore techniques to enforce the low-rank property (via random projection) and boost privacy utility trade-off. However, all the works focus on investigating general high-dimensional problem for private learning, rather than separating the study for different network choices such width, depth and initialization. Instead, our study focuses on the fully connected neural network and its linearized variant, which enables us to prove more precise privacy utility trade-off bounds for these particular networks under praamtttrtrtiiiinnnn.
minimization [ 46) and private stochastic convex optimization [1] 12 5
2 Problem and Methodology
We consider the following standard multi-class supervised learning setting. Let D = (zi,... 2n) be an input dataset of size n, where each data record 2; (x,, yı) contains d-dimensional feature vector E Rdd and a label vector y; E y = 1-1, 1 classes. We aim to learn a neural network output function fw (-) X - y parameterized by W via empirical risk minimization (ERM)
1 Σ (fw( n
min L(W: W
where f(fw (z:);: y1) is a loss function that reflects the approximation quality of model prediction fw( (ax) compared to the ground truth label yi. For simplicity, throughout our analysis, we employ the cross-entropy loss {(Jw y) = (y, log softmax fw((x)) for multi-class network with 2 and ((f(());))
log(1 exp( (xp(-yfww/ (æ)) for single-output network with o 1.
Fully Connected Neural Networks. We consider the L-layer, multi-output, fully connected, deep neural network (DNN) with ReLU activation. Denote the width of hidden layer I as m, for 1 == 1.... L 1. For consistency, we also denote mo = and m. o. The network output (x) == hz is defined recursively as follows.
ho( x;;
hz(x)= & (Wixz) for I = I,... L - 1; hr(x)= (2),
(2)
3

---

where hy( denotes the post-activation output at (-th layer, and { ( E R 1:1=1... L}
denotes the set of per-layer weight matrices of DNN, For brevity, we denote the vector W ==
i.e., the the concatenation of vectorizations for weight matrices of all layers, as the model parameter.
Vec.W)). ..... Vec Wt)) ) E I -
Linearized Network. We also analyze the following linearized network, which is used in prior works 33 3 41 as an important tool to (approximately and qualitatively) analyze the training dynamics of DNNs. Formally, the linearized network f(i (ax) is first-order Taylor expansion of the fully connected ReLU network at initialization parameter Wiin, as follows.
plnn.0 (z) = Swi (ax) + 0f (x)
(W - w))",
(3)
where fwi. (ax) is the output function of the fully connected ReLU network 2 at initializaaion Wi
We denote C (W; D) = = Σ;= (Swgen (x:) + pirical loss function for training linearized network, by plugging
afw
aw w WW-Wiji (W- W y:) as the em-
3 into
Langevin Diffussion. Regarding the optimization algorithm, we focus on the Langevin diffusion algorithm (36) with per-dimensional noise variance o². Note that we aim avoid gradient clipping while still proving KI. privacy bounds. After initializing the model parameters Wo at time zero, the model parameters W, at subsequent time t evolves as the following stochastic differential equation.
dW,
Vd
Initialization Distribution. The initialization of parameters Wo crucially affects the convergence
of I Langevin diffusion, as observed in prior literatures [52 25 24). In this work, we investigate the following general class of Gaussian initialization distributions with different (possibly depth-
dependent) variances for the parameters in each layer. For any layer I 1,, 1.,..... I, we have
[W' ~ (O, for (i.j) [m]] x [m:-1),
(5)
where $1, .3 > 0 are the per-layer variance for Gaussian initialization. By choosing different variances, recover many common initialization schemes in the literature, summarized in Table
2.1 Our objective and methodology
We aim to understand the relation between privacy, utility and over- paraaattetttitnnoonnnn (depth and width) for the Langevin diffusion algorithm (under different initialization distributions). For privacy analysis, we prove a KL privacy bound for running Langevin diffusion on any two worst-case neighboring datasets. Below we first give the definition for neighboring datasets.
Definition 2.1. We denote D and D' as neighboring datasets if they are of same size and only differ in one record. For brevity, we also denote the differing records as (æ, y) E D and (a' y') E D'.
Assumption 2.2 (Bounded Data). For simplicity, we assume bounded data, i.e., ||0||| S Vd.
We now give the definition for KL privacy, which is a more relaxed, yet closely connected privacy notion to the standard (s, 6) differential privacy (2) see Appendix A.2 for more discussions. KL
privacy and its relaxed variants are commonly used in previous literature g 10 53).
Definition 2.3 (KL privacy). A randomized algorithm A satisfies K-KL privacy if for any neighboring datasets 'D and DD' we have that the KL divergence (L()) < s, where A(D) denotes the algorithm's 's output distribution on dataset D.
In this paper, we prove KL privacy upper bound for maxp, DD' KL W [o:T] W% (0:77) when running Langevin diffusion on any worst-case neighboring datasets. For brevity, here (and in the remaining paper). we abuse the notations and denote Wo:rr and W [0:rr] as the distributions of model parameters trajectory during Langevin diffusion processes Eq. with time T on and D' respectively.
For utility analysis, we prove the upper bound for the excess empirical risk given any fixed KL diver- gence privacy budget for a single-output neural network under the following additional assumption (it is only required for utility analysis and not needed for our privacy bound).

---

Assumption 2.4 Pz that satisfies E [x] O, | v for x: ~ Ps. and with probability one for any i # j. az H z--
40 20
21
The training data æ1, ... Zn are i..d. samples from a distribution
Our ultimate goal is to precisely understand how the excess empirical risk bounds (given fixed KL privacy budget) are affected by increasing width and depth under different initialization distributions.
3 KL Privacy for Training Fully Connected ReLU Neural Networks
In this section, we perform the composition-baset KL privacy analysis for Langevin Diffusion given random Gaussian initialization distribution under Eq. (5) for fully connected ReLU network. More specifically, we prove upper bound for the KL divergence between distribution of output model parameters when running Langevin diffusion on an arbitrary pair of neighboring datasets D and D'.
Our first insight is that by a Bayes rule decomposition for density function, KL privacy under a relaxed gradient sensitivity condition can be proved (that could hold without gradient elipping).
Theorem 3.1 (KL composition under possibly unbounded gradient difference). The KL divergence between running Langevin diffusion (4) for DNN (2) on neighboring datasets DD and D' satisfies
/
KL(W (o:T] [W (orT)) 20
E
- 1") dt.
(6)
sketch. sketch. We compute the partial derivative of KL divergence with regard to time 4, and then integrate it over / E [0, 7] to compute the KI. divergence during training with time T. For computing the limit of differentiation, we use Girsanov's theorem to compute the KI. divergence between the trajectory of Langevin diffusion processes on D and D', The complete proof is in Appendix BB.
Theorem 3.1 is an extension of the standard additivity S of KL divergence (also known as chain rule (T) for a finite sequence of distributions to continuous time processes with (possibly) unbounded drift difference. The key extension that Theorem 3.1 does not require bounded sensitivity between the drifts of Langevin Diffusion on neighboring datasets. Instead, it only requires finite second-ord -odder moment of drift difference (in the l -n-mm sense) between neighboring datasets D, D'D', which can be proved by the following Lemma. We prove that this expectation of squared gradient difference incurs closed-form upper bound under deep neural network (under mild assumptions), for running Langevin diffusion (without gradient clipping) on any neighboring dataset 'D and D'
Lemma 3.2 (Drift Difference in Noisy Training). Let Mr be the subspace spanned by gradients (VL(fw, (2v 34) (I,, y:) E D,t E [0, T]}= throughout Langevin diffusion (Wi) te Denote a1-1las, as the Eg norm of the projected input vector onto My. Suppose that there exists constants
c, 3 0 such that for any W, W' and (z. y). we have [[V[(fw(() (z);y) Vf(fw: (x); y)
max(e, (c, @ - -W'M, ). Then running Langevin diffisiin Eq. (4) with Gaussian initialization
max
maxp, Jo D. - -
distribution 5
satisfies K-KL privacy with =
where
20²
E VL(:W: V'WW di s 2T E VE(W: D'11
gradlent difference at inirialization
2,32 n2 9P)
e(2+00)T
2c2T
r ) [1V D) + 20 ree2rank(M0 (Mr) + c2)
2 82
n
non-snnossiness
gradient difference fluctuation during training
The key is to reduce the problem of upper bounding the gradient difference at any Proof sketch.
training time T, to analyzing its subcomponents: [/V (m) v)) Vf(Sw, F[(Jw,ax') v') s
2 (w( - -&(/w (xe') ); 212 +2
I Woll +2c². where (æ, y) and
gradient difference initialization
parameters' change after time T
(ar', yn) are the differing data between neighboring datasets D and D'. This inequality is by the Cauchy- Sccwar-S inequality. In this way, the second term in Lemma 3.2 uses the change of parameters
5

---

to bound the gradient difference between datasets D and D' at time T, via the relaxed smoothness assumption of loss function (that explained in Remark 3.3 in details). The complete proof is in
Appendix [..)]
Remark 3.3 (Gradient difference at initialization). The first term and in our upper bound linearly scales with the difference between gradients on neighboring datasets D and D' at initialization. Under different initialization schemes, this gradient difference exhibits different dependency on the network depth and width, as we will prove theoretically in Theorem 4.1
Remark 3.4 (Gradient difference fluctuation during training). The second term in Lemma 3.2 bounds the change of gradient difference during training, and is proportional to the the rank of subspace Mr spanned by gradients of all training data. Intuitively, this fluctuation is because Langevin diffusion adds per-dimensional noise with variance o², thus perturbing the training parameters away from the initialization at scale of O( / rank My)) in the expected Eg distance.
Remark 3.5 (Relaxed smoothness of loss function). The third term in Lemma 3.2 is due to the assumption || [ ()) is similar to smoothness of loss function, but is more relaxed as it allows non-smoothness places where the gradient is bounded by c. Therefore, this assumption is general to cover commonly-used smooth, non-smooth activation functions, e.g., sigmoid, ReLU.
(f(fw:()); y)]l2 < max(c, B|| - |,,,,, This assumption
Growth of KL privacy bound with increasing training time T. The first and third terms in our upper bound Lemma 3.2 grow linearly with the training time T, while the second term grows exponentially with regard to T. Consequently, for learning tasks that requires a long training time to converge, the second term will become the dominating term and the KL privacy bound suffers from exponential growth with regard to the training time. Nevertheless, observe that for small T + 0,
the second component in Lemma 3.2 contains a small factor _221 - T = o(T) by Taylor 24,3"
expansion. Therefore, for small training time, the second component is smaller than the first and the third components in Lemma 3.2 that linearly scale with T, and thus does not dominate the privacy bound. Intuitively, this phenomenon is related to lazy training [19]. In Section 5 and Figure 2 we also numerically validate that the second component does not have a high effect on the KL privacy loss in the case of small training time.
Dependence of KL privacy bound on network over-parameterization Under fixed training time T and noise scale o², Lemma predicts that the KL divergence upper bound in Theorem 3.1 is depen- dent the gradient difference and gradient norm at initialization, and the rank of gradient subspace rank( My) throughout training. We now discuss the how these two terms change under increasing width and depth, and whether there possibilities to improve them under wwer-parameterization..
1. The gradient norm at initialization crucially depends on how the per-layer variance in the Gaussian initialization distribution scales with the network width and depth. Therefore, it is possible to reduce the gradient difference at initialization (and thus improve the KI. privacy bound) by using specific initialization schemes, we later show in Section and Section 5
2. Regarding the rank of gradient subspace rank(Mrr: when the gradients along the training trajectory span the whole optimization space, rank (M) would equal the dimension of the learning problem. Consequently, the gradient fluctuation upper bound (and thus the KL privacy bound) worsens with increasing number of model parameters paerrparramttrizzaioon) in the worst-case. However, if the gradients are low-dimensional [5] 32 43 or sparse (37], rank rank(Mr) could be dimension-independent and thus enables better bound for gradient fluctuation (and KL privacy bound). We leave this as an interesting open problem.
4 KL privacy bound for Linearized Network under over-parameterizatio
In this section, we focus on the training of linearized networks 3). which fosters refined analysis on the interplay between KL privacy and over parameterization (increasing width and depth). Analysis of DNNs via linearization is commonly used technique in both theory [19] and practice [43] 41).
We hope our analysis for linearized network serves as an initial attempt that would open a door to theoretically understanding the relationship between peer-parameterization and privacy.
To derive a composition-basse KI. privacy bound for training a linearized network, we apply The- orem 3.1 which requires an upper bound for the norm of gradient difference between the training

---

processes on neighboring datasets D and D' at any time t. Note that the empirical risk function for training linearized models enjoys convexity, and thus relatively short amount of training time is enough for convergence. In this case, intuitively, the gradient difference between neighboring datasets does not change a lot during training, which allows for a tighter upper bound for the gradient difference norm for linearized networks (than Lemma 3.2
In the following theorem, we prove that for linearized network, the gradient difference throughout training has a uniform upper bound that only depends on the network width, depth and initialization.
Theorem 4.1 (Gradient Difference throughout training linearized network). Under Assumption 2.2 taking over the randomness of the random initialization and the Brownian motion, for any E [0.T], T].
running Langevin diffusion a linearized network in Eq. (3) satisfies that
[IVC(W
L(W,lin; (')
4B n²
where B d
( Bem
II
Σ
L
B
(7)
2
3
1=1
1=1
where n. is the training dataset size, and B is a constant that only depends the data dimension d, the number of classes o, the network depth L, the per-layer network width {ma)i=n- and the per-layer variances {3,)1=11 of the Gaussian initialization distribution.
Theorem 4.1 provides a precise analytical upper bound for the gradient difference during training
linearized network, by tracking the gradient distribution for fully connected feed-forward ReLU net- work with Gaussian weight matrices. Our proof borrows some techniques from [3 (4) for computing the gradient distribution, refer to Appendix C.T
and C.2 for the full proofs. By plugging Eq. 7 into Theorem B.I, we obtain the following KL privacy bound for training a linearized network.
Corollary 4.2 (KL privacy bound for training linearized network). Under Assumption 2.2 neural
networks 3 initialized by Gaussian distribution with per-layer variance {3.) running Langevin diffusion for linearized network with time T on any neighboring datasets satisfies that
KT(W | tlin
2BT
(o:T]
(O:T)) S n²a2²
(8)
where the constant that specifies the gradient norm upper bound, given by Eq. 77.
neeerparamettrizationn affects privacy differently under different initialization. Corollary 4.2 and Theorem prove the role of over-parameterrizaion in our KI. privacy bound, crucially depending on how the per-layer Gaussian initialization variance 3 scales with the per-layer network width m, and depth L. We summarize our KL privacy bound for the linearized network under different width, depth and initialization schemes in Table and elaborate the comparison below.
(1) LeCun initialization uses small, width-inndependent variance for initializing the first layer 31 = d (where d is the number of input features), and width-dependent variance B3 = _... 31 = 1 m for initializing all the subsequent layers. Therefore, the second term El= fr. in the constant B of Eq. 3,
increases linearly with the width and depth L. However, due to mi::: for all 2, L. the first product term I Zome in constant B decays with the increasing depth. Therefore, by combining the two terms, we prove that the KL privacy bound worsens with increasing width, but improves with increasing depth (as long as the depth is large enough). Similarly, under Xavier initialization 3 + we prove that the KL privacy bound (especially the constant B 7 improves with increasing depth as long as the depth is large enough.
L-1
2
1= 1= L
(2) NTK and He initializations use large per-layer variance 3r
(for
1-L
NTK) and Bi 2 (for He). Consequently, the gradient difference under NTK or He initialization significantly larger than that under LeCun initialization. Specifically, the gradient norm constant B in Eq. (7) grows linearly with the width m and the depth L under He and NTK initializations, thus indicating a worsening of KL privacy bound under increasing width and depth.
mi-1
5 Numerical validation of our KL privacy bounds
To understand the relation between privacy and over-parameterization in practical DNNs training (and to validate our KL privacy bounds Lemma 3.2 and Corollary 4.2) perform experiments for
7

---

DNNs training via noisy GD to numerically estimate the KL privacy loss. We will show that if the total training time is small, is indeed possible obtain numerical KL privacy bound estimates that does not grow with the total number of parameter (under carefully chosen initialization distributions).
Numerical estimation procedure. Theorem 3.1 proves that the exact KL privacy loss scales with the expectation of squared gradient norm during training. This could be estimated by empirically average of gradient norm across training runs. For training dataset D. we consider all 'car' and pplane' images of the CIFAR-10. For neighboring dataset, consider all possible D' that removes record from D, adds a test record to D, i.e., the standard "add-or remove-one" neighboring notion (2). We run noisy gradient descent with constant step-size 0.01 for 50 epochs on both datasets.
0.4
Numerical KL, privacy lass
Xavier Intiiaiizttion
LeCun Initiclization
0.2
0.1
10
20 40
Epochs
Numerically validate the growth of KL privacy loss with regard to training time. [ numerical KL pri- vacy loss under different initializations, for fully connected networks with width 1024 and depth 10. We observe that the KL privacy loss grows linearly at the beginning of training (< 10 epochs), which validates the first and third term in the KL privacy bound Lemma 3.2 Moreover, the KL privacy loss under LeCun and Xavier initialization is close to zero at the beginning of training (< 10 epochs). This shows LeCun and Xavier initialization induce small gradient norm at small training time, which is consistent with Theorem 4.1] How- ever, when the number of epochs is large, the numerical KL privacy loss grows faster than linear accumulation under all initializations, thus validating the second term in Lemma 3.2
Figure I: Numerically estimated KL. privacy loss for noisy GD with con- stant step-size 0.001 on deep neural network with width 1024 and depth 10. We report the mean and standard deviation across 6 training runs, tak- ing worst-case over all neighboring datasets. The numerical KL privacy loss grows with the number of train- ing epochs under all initializations. The growth rate is close to linear at be- ginning of training (epochs < 10) and is faster than linear at epochs 2 10.
Iniissicaain
Numeical KL. paivay los
Xavier Inmolization
LeCun Iniiaiitaaiion
410
600
1,000
Beyt
depth
wide
(a) Privacy vs depth (20 epochs. 0.01, width = 1024)
(b) Privacy vs depth (50 epochs, 0.01, width = 1024)
(c) Privacy vs width (50 epochs, 0.01, depth 10)
Figure 2: Numerically estimated KL privacy loss for noisy GD with constant step-size on fully connected ReLU network with different width, depth and initializations. We report the mean and standard deviation across training runs, taking worst-case over all neighboring datasets. Under increasing width, the KI privacy loss always grows under all evaluated initializations. Under increasing depth, at the beginning of training (20 epochs), the KI. privacy loss worsens with depth under He initialization, but first worsens with depth (5. and then improves with depth (2 8) under Xavier and LeCun initializations. At later phases of the training (50 epochs), KL privacy worsens (increases) with depth under all evaluated initializations.
Numerically validate the dependency of KL privacy loss network width, depth and initializations. F shows the numerical KL privacy loss under different network depth, width and initializations, for a fixed training time. In Figure 2c observe that increasing width and training time always increases KL privacy loss. This is consistent with Theorem 4.1 which shows that increasing width worsens the gradient norm initialization (given fixed depth), thus harming KI. privacy bound Lemma 3.2 at the beginning of training. We also observe that the relationship between KI. privacy
8

---

and network depth depends on the initialization distributions and the training time. Specifically, in Figure Pa] when the training time is small (20 epochs), for LeCun and Xavier initializations, the numerical KI. privacy loss improves with increasing depth when depth >> 8. Meanwhile, when the training time is large (50 epochs) in Figure 2b KI. privacy loss worsens with increasing depth under all intializations. This shows that given small training time, the choice of initialization distribution affects the dependency of KL privacy loss on increasing depth, thus validating Lemma 3.2 and Theorem 4.1
Utility guarantees for Training Linearized Network
Our privacy analysis suggests that training linearized network under certain initialization schemes (such as LeCun initialization) allows for significantly better privacy bounds under over- parameterization by increasing depth. In this section, we further prove utility bounds for Langevin diffusion under initialization schemes and investigate the effect of over-parametcrization on the privacy utility trade-off. In other words, we aim to understand whether there is any utility degradation for training linearized networks when using the more
initialization schemes.
Convergence of training linearized network. We now prove convergence of the excess empirical risk in training linearized network via Langevin diffusion. This is a well-studied problem in the literature for noisy gradient descent. We extend the convergence theorem to continuous-time Langevin diffusion below and investigate factors that affect the convergence under vee-pparaettrrization. The proof is deferred to Appendix D.I
Lemma 6.1 (Extension of [42] Theorem 2] and [45] Theorem 3.1]). Let C (W;D) D) be the empirical risk function of linearized network in Eq. (3) expanded at initialization vector W Let We be an a-near-optimal solution for the ERM problem such that L (Wo; D))
minw C (W;D) S a. Let D
{a,)ī=] be an arbitrary training dataset of size n, and denote Mo fW (x1), ... fw (In) as the NTK feature matrix at initialization. Then running
Langevin diffusion on Clin (W) with time T and initialization vector Whin satisfies
Elchin [Wii)] min Clin (W:D) S sa 2T +
R
rrnn
W
where the expectation is over Brownian motion BT in Langevin diffusion in Eq. Wlin Wo 12,, is the gap between initialization J Wiinng dt is the average of all iterates, and R = W! lin parameters Whin and solution W
Remark 6.2. The excess empirical risk bound in Lemma 6. I is smaller if data is low-rank, e.g., image data, then rank MM) is small. This is consistent with the prior dimension-indeeendeer private learning
literature 32 33
37
and shows the benefit of -ineeninniooall gradients on private learning.
Lemma 6. highlights that the excess empirical risk scales with the gap between initialization and solution (denoted as lazy training distance). the rank of the gradient subspace, and the constant B that specifies upper bound for expected gradient norm during training. Specifically, the smaller the lazy training distance R is, the better is the excess risk bound given fixed training time T and noise variance o², We have discussed how over-parameterizzaion affects the gradient norm constant B and the gradient subspace rank (Mo( in Section 3 Therefore, we only still need to investigate how the lazy training distance R changes with the network width, depth, and initialization, as follows.
Lazy training distance R decreases with model over-paramettricationn It is widely observed in the literature [19 (55 38) that under appropriate choices of initializations, gradient descent on fully connected neural network falls under a lazy training regime. That is, with high probability, there exists a (nearly) optimal solution for the ERM problem that is close to the initialization parameters in terms of Eg distance. Moreover, this lazy training distance R is closely related to the smallest eigenvalue of the NTK matrix, and generally decreases as the model becomes increasingly overparameterized. In the following proposition, we compute a near-optimal solution via the pseudo inverse of the NTK matrix, and prove that it has small distance to the initialization parameters via existing lower bounds for the smallest eigenvalue of the NTK matrix 44)
Lemma 6.3 (Bounding lazy training distance via smallest eigenvalue of the NTK matrix). Under Assumption 2.4 and single-output linearized network Eq. 3 with o = 1, assume that the per-layer network widths mo. m ((()) are large. Let (W) be the empirical risk Eq. 11 for

---

linearized network expanded at initialization vector W Then for any W there exists corresponding solution Wo s.t. Lin (Wo") minw b (W; D) n rank(Aoo) n and
RSO
max
1 J 37
dir (II Bems)
Ei=1
with high probability over training data sampling and random initialization Eq. togarithmic with regard to n, m, L, and tail probability d.
5 where O ignores
The full proof is deferred to Appendix D.2, By using Lemma 6.3 we provide a summary of bounds for R under different initializations in Table I We observe that the lazy training distance R decreases with increasing width and depth under LeCun, He and NTK initializations, while under Xavier initialization R. only decreases with increasing depth.
Privacy & Excess empirical risk tradeoffs for Langevin diffusion under linearized network. We now use the lazy training distance R to prove empirical risk bound and combine it with our KL privacy bound Section to show the privacy utility trade-off under over parameterization.
Corollary 6.4 (Privacy utility trade-off for linearized network). Assume that all conditions in Lemma 6.3 holds. Let B be the gradient norm constant in Eq. (7). and let R be the lazy training distance bound in Lemma 6.3 Then o² 2BT and - diffusion with time T satisfies E-KI. privacy, and has empirical excess risk upper bounded by
anR 2B"
releasing all iterates of Langevin
1 n
BR en
(WT" > min Cl:nWW;WWWW (W; D) < 6
+
(10)
max 113rr
I 3mm}
(11)
22
2
with high probability over random initiailization Eq. 5). where the expectation is over Brownian motion By in Langevin diffusion, and O ignores logarithmic factors with regard to width depth L, number of training data n and tail probability
See Appendix D.3 for the full proof. Corollary 6.4 proves that the excess empirical risk worsens in the presence of a stronger privacy constraint, i.e., a small privacy budget E, thus contributing to trade-off between privacy and utility. However, the excess empirical risk also scales with the lazy training distance R and the gradient norm constant B. These constants depend depth and initialization distributions, and we prove privacy utility trade-offs for training linearized network under commonly used initialization distributions, summarized in Table [
network width,
We would like to highlight that our privacy utility trade-off bound under LeCun and Xavier ini- tialization strictly improves with increasing depth as long as the data satisfy Assumption 2.4 and the hidden-layer width is large enough. To our best knowledge, this is the first time that a strictly improving privacy utility trade-off under over-vorannnnee parameterizaaion is shown in literature. This shows the benefits precisely bounding the gradient norm (Appendix C.T in our privacy and utility analysis.
7 Conclusion
We prove new KI. privacy bound for training fully connected ReL.U network (and its linearized variant) using the Langevin diffusion algorithm, and investigate how privacy is affected by the network width, depth and initialization. Our results suggest that there is a complex interplay between privacy and pverpparamtterization (width and depth) that crucially relies on what initialization distribution used and the how much the gradient fluctuates during training. Moreover, for a linearized variant of fully connected network, we prove KL privacy bounds that improve with increasing depth under certain initialization distributions (such as LeCun and Xavier). We further prove excess empirical risk bounds for linearized network under KL privacy, which similarly improve as depth increases under LeCun and Xavier initialization. This shows the gain of our new privacy analysis for capturing the effect of over-parameterization. We leave as an important open problem as to whether our privacy utility trade-off results for lincarized network could be generalized to deep neural networks.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Yaxi Hu and anonymous reviewers for helpful discussions on drafts of this paper. This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043), and the Swiss National Science Foundation (SNSF) under grant number 200021 000211205011, Google PDPO faculty research award, Intel within the www.private- ar.org center, Meta faculty research award, the NUS Early Career Research Award (NUS ECRA award number NUS ECRA FY19 P16). and the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
References
[1] Entropy, Relative Entropy, and Mutual Information, chapter 2, pages 13-55. John Wiley & Sons, Ltd, 2005. ISBN 9780471748823, doi:
cch2. URL
https:///omlineellraayyy wwley
[2] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[3] Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterizzaion.. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[4] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analy- sis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[5] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in 11 geometry. In International Conference on Machine Learning, pages 393 403. PMLR, 2021.
[6] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
[7] Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1138-1156 IEEE, 2022.
[8] Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv: 1412.445, 2014.
[9] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
[10] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046-1059, 2016.
[11] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[12] Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic opti- mization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34:9317-9329, 2021.
[13] Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Differentially private learning with margin guarantees. arXiv preprint 2rXiv:2204.10376 2022.
11

---

[14] Zhiqi Bu, Hua Wang, and Qi Long. On the convergence and calibration of deep learning with differential privacy, arXiv preprint arXiv:2106.07830, 2021.
[15] Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Journal of the ACM, 70(2):1-18, 2023.
[16] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
[17] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom B Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In USENIX Security Symposium, volume 6, 2021.
[18] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209. 11215, 2022.
[19] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. Advances in neural information processing systems, 32, 2019.
[20] Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes parapaaraeteri neural networks. arXiv preprint arXiv:
2018.
[21] Simon S. Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
[22] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265 284. Springer, 2006.
[23] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-077, 2014.
[24] Yoav Freund. Yi-An Ma, and Tong Zhang. When is the convergence time of langevin algorithms dimension independent? composite optimization viewpoint. Journal of Machine Learning Research, 23(214):1-33) 2022.
[25] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin meme. Advances in Neural Information Processing Systems, 33:7222-7233, 2020.
[26] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Langevin diffusion: An almost univer- sal algorithm for private euclidean (convex) optimization. arXiv preprint arXiv:2204.01585. 2022.
[27] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings. 2010.
[28] Chuan Guo, Alexandre Sablayrolles, and Maziar Sanjabi. Analyzing privacy leakage in machine learning via multiple hypothesis testing: A lesson from fano. arXiv preprint arX1:22210.13662. 2022.
[29] Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. arXiv preprint arXiv:2206.0r9 07758, 2022.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification. In Proceedings of the IEEE international conference computer vision, pages 1026-1034, 2015.
[31] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
12

---

[32] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces. In Conference on Learning Theory, pages 2717-2746. PMLR, 2021.
[33] Shiva Prasad Kasiviswanathan. Sgd with low- low-dimensional gradients with applications to private and distributed learning. In Uncertuinty in Artificial Intelligence, pages 1905-1915. PMLR, 2021.
[34] Yann LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9-50. Springer, 2002.
[35] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
[36] DS Lemons, A Gythiel, and Paul Langevin's s. Sur la théoric du mouvement brownien [on the theory of brownian motion]. CR Acad. Sci. (Paris) 146:530-533, 1908.
[37] Xuechen Li. Daogao Liu, Tatsunori B Hashimoto, Huseyin Inan, Janardhan Kulkarni, Yin- Tat Lee, and Abhradeep Guha Thakurta. When does differentially private learning not suffer in high dimensions? Advances in Neural Information Processing Systems, 35:28616-2866 2022.
[38] Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang. Phase diagram for two-layer relu neural networks at infinite-width limit. The Journal of Machine Learning Reseurch, 22(1): 3327-3373, 2021.
[39] Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint arXiv:2204.06106 2022.
[40] Quynh Nguyen, Marco Mondelli, and Guido F Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning, pages 81 3119-81 8129. PMLR, 2021.
[41] Guillermo Ortiz-Jiménez, Seyed-Mohsen Mohsen Moosavi-Dezfooll, and Pascal Frossard. What can linearized neural networks actually say about generalization? Advances in Neural Information Processing Systems, 34:8998 99099, 2021.
[42] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. International conference on machine learning, pages 71-79. PMLR, 2013.
[43] Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Ken Keil, Jonathan Ragan- Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. International Conference Machine Learning, pages 8614-8621 PMLR, 2020.
[44] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[45] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages 2638-2646. PMLR, 2021.
[46] Kunal Talwar, Abhradeep Thakurta, and Li Zhang, Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv preprint 1rXiv:1411.550 2014.
[47] Jasper Tan, Blake Mason, Hamid Javadi, and Richard Baraniuk. Parameters or privacy: A provable tradeoff between overparameterization and membership inference. Advances in Neural Information Processing Systems, 35:17488-17508 2022.
[48] Jasper Tan, Daniel LeJeune, Blake Mason, Hamid Javadi, and Richard G Baraniuk. A blessing of dimensionality in membership inference through regularization. In International Conference on Artificial Intelligence and Statistics, pages 10968-10993. PMLR, 2023.
13

---

[49] Leonida Tonelli. Sull' Sull'integr per parti. Rend. Acc. Naz. Lincei, 5(18):246-23 253, 1909.
[50] Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Covariate shift in high-dimensional random feature regression. arXiv preprint arXiv:2111.08234, 2021.
[51] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leiie divergence. IEEE Transactions Information Theory, 60(7):3797-3820, 2014.
[52] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[53] Yu- fu-Xiang Wang, Jing Lei, and Stephen E Fienberg. On-average kl-privacy and its equivalence generalization for max-entropy mechanisms. Privacy in Statistical Databases: UNESCO Chair in Data Privacy, International Conference, PSD 2016, Dubrovnik, Croatia, September 14-16, 2016, Proceedings, pages 121-134. Springer, 2016.
[54] Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization). arXiv preprint arXiv:2209.07263, 2022.
[55] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-492, 2020.
14

---

Contents
Introduction
Related Works
Problem and Methodology
2.1
Our objective and methodology
3 KL Privacy for Training Fully Connected ReLU Neural Networks
KL privacy bound for Linearized Network under over-paramettrization
Numerical validation of our KL privacy bounds
Utility guarantees for Training Linearized Network
Conclusion
10
A Symbols and definitions
15
A. Additional notations)
15
A.2 Relation between KI. privacy Definition 2.3 to differential privacy
16
Deferred proofs for Section 3
16
B.1 Deferred proofs for Theorem 3.1
16
B.2 Deferred proois for Lemma 3.2
18
Deferred proofs for Section 4
20
Bounding the gradient norm at initialization
20
Deferred proof for Theorem 4.1
22
Deferred proofs for Section
23
D.I Deferred proof for Lemma 6. on convergence of training linearized network
23
D.2 Deferred proof for Lemma 6.3
24
D.3 Deferred proof for Corollary 6.4
27
Discussion on extending our results to Noisy GD with constant step-size
27
A Symbols and definitions
A.1 Additional notations
Vecorization Vee(-) denotes the transformation that takes an input matrix A (as))ie(r).jil) E Rexe (with rows and columns) and outputs a re-dimensional column vector: Vec(A)
(01,1)"" ,,,, 41,2 0r.2, 01,es ar.e)
Softmax function: softmax(y)
E. Df where is the number of output classes.
number of output classes for the neural network.
15

---

A.2 Relation between KL privacy Definition 2.3 to differential privacy
KL privacy is more relaxed, yet closely connected privacy notion to (z, differential privacy
1. KL privacy and differential privacy both worst-case privacy notions over all possible neighboring datasets, by requiring bounded distinguishability between the algorithm's 's output distributions neighboring datasets in statistical divergence. The difference is that KI. privacy requires bounded KL divergence, while (s, --dffferrnnt privacy is equivalent to bounded Hockey-stick divergence [6].
2. KL privacy and differential privacy are both definitions based on the privacy loss random variable log P[A(D)=o) P(A(D')=o) o A(D) (following the definition in 2 Equation IJ). KL privacy implies that the privacy loss random variable has a bounded first order moment, while differential privacy requires high probability argument that the privacy loss random variable is bounded by with probability - 6. Therefore, KL. privacy is generally a more relaxed notion than differential privacy.
3. Translation to each other: For 0. KL privacy (bounded first-order moment of privacy loss random variable) implies (0, d)ffifferet privacy with v by Pinsker inequality. Higher order moments of the privacy loss random variable suffice prove (s, 8)-differential privacy for > 0. Note that (e, 5)DDP with 5 > O does not necessarily imply KI. privacy, as the privacy loss random variable may large at the tail event with probability.
4. Due the connection to the privacy loss random variable (which is closely connected to the likelihood ratio test for membership hypothesis testing), both differential privacy and KL privacy incur upper bound on the performance curve of inference attacks, such as the membership inference and attribute inference (39 28), as we discuss in Footnote 3
B Deferred proofs for Section 3
B.1 Deferred proofs for Theorem 3.1
To prove the new composition theorem, we will use the Girsanov's Theorem. Here we follow the presentation of 18 Theorem 6).
Theorem B.1 (Implication of Girsanov's 's theorem 18 Theorem 6]). Let (X+)te(o.)) and (X))ett be two continuous-time processes over IR.. Let Pr be the probability measure that corresponds the trajectory of (X)) and let QT be the probability measure that corresponds to the trajectory of (Xe)se(o.))- Suppose that the process (Xi)te(o.n) follows
dX; b,dt + odB.,
where (Bi)rejo,T) is a standard Brownian motion over Pr, and the process (X1))e(o.n) follows
dX; b,dt + odB,,
where (Bi)sejo,ry is standard Brownian motion over Qr with dB, = dB, + (b.-b)) Assume that a is a r X symmetric positive definite matrix. Then, provided that Novikov's 's condition holds,
( 2
I - -b)113d1 00,
Eqr exp
(12)
we have that
dPr dQt
exp (f"0- -0- b.)dß, f"10- 1|o l(b -6.))13d
We are now ready to apply Girsanov's theorem to prove the following new KL, privacy composition theorem for Langevin diffusion processes neighboring datasets D and D', For case of description, we repeat Theorem3 3.1 as below.
16

---

Theorem 3.1
[KL composition under possibly unbounded gradient difference] The KL divergence between running Langevin diffusion for DNN on neighboring datasets 'D and D' satisfies
!
KL(WWo::) (o:T] W (::T)) 20
E - -VC dt.
(13)
Proof. Recall that W, denotes the model parameter after running Langevin diffusion on dataset DD with time i, and W denotes the model parameter after running Langevin diffusion dataset 'D' with time To avoid confusion, we further denote P[r and P(tysta) the distributions of model parameters trajectories Wi [estta] and W [(i:f2] during time inteval [t1, t2] respectively. By definition of partial derivative, we have that
ØKL W [o::)] W
[0:4]
KL(WWo:r W WWo+tt/l (0:+ml - KL(W [0:t) [ (o:1))
lim 7-50
(14)
Now we compute the term KL W [u:++m]] W (0:r+n) as follows.
log P(tst+m]][0at] (Wlntto) (mooa) Plont (W(o.a)
KL W [0:
W [ (0:4+1)) = E Ewoo Plo.ti
P Pla++]]]0:
(W(ettoo) (()0:))
Plozn (W(az)
E oo PPocetl log Mict+il ( [1:++]]] ((ooe))
Plo:e (urjos))
+ log
+( [[ (W(o:))
M/o.q] (w
(15)
where [0 (wioas)) is the conditional distribution during running Langevin diffusion on dataset D. given fixed values for model parameters trajectory (o::]] w(o.t]- Similarly,
Pic:t+nil(o-1] [W(o.)) is the conditional distribution during running Langevin diffusion on dataset D'.
Therefore by using the Markov property of the Langevin diffusion process and the definition of KI.
divergence in Eq. [5). we have that
W (or++)) = Excerpp KI. (Plesttolle (ws)) [ws))|[/eneoo)e [wne))] + KL (16)
KT KL [0+++)))
Now to compute the term KL (Pico+t]ll( (wx)) ( Pfesttilel (wvs) we only need to apply Theorem B. to the following two Langevin diffusion processes (W (Wessj))s((o.)) and (W (W(+s)))s(oon)) conditioning on the observation Wije W wy time 1.
dW c+s|s VL(W D)dt + V202dB.
dw Ctaft = VL(W D' at v20dd..
Note that when 1 is small enough, we have that the Novikov's condition in Eq. (12 holds because the exponent inside integration --"lo=-*( (b.- - 1l scales linearly with that can be arbitrarily small. Therefore, by applying Girsanov's theorem, we have that
KL (Proetmile( (wx) Plestnjic (wne) -E [ - -b. - b.)dB, - 2 1" 11o 1lo- 1
where -b. b. VVC(W Ws tss D) + VLCWE+s11 D'). By dB, dB, + (b. -b.) and Itō
integration with regard to W [t we have that
S VC(W D) - -VLWW (+ s/;
KL (Plestallee lus>)/pieeetolee (-1wx))
202
(17)
17

---

By plugging Eq.
17
into Eq.
16
we have that
E
F[(WW+s: (+(: + (L
KL (P Plet+n)
(18)
2x²
By plugging Eq. 18) into Eq. have that
14
and by exchanging the order of expectation and integration,
So Bpst.
VL((Wess)) VL(W k+ :D: ds
OKL Pb)
lim n00
0t
2
77
Ep. [VC(W. VC(W; D')
(19)
20
Note that here we exchange the order of expectation and integration by using the Tonelli's The- Integrating
orem 449 for non-negative integrand function VVL(W++s: VL(W==s;D") E [0, T] finishes the proof.
Eq. 19
B.2 Deferred proofs for Lemma 3.2
Lemma 3.2
Let Mr be the subspace spanned by gradients [VE(fw. (z;; yt) (I y.) E D,t te E [0, Ti throughout Langevin diffusion (W (Wi) Denote II-laa,, as the l norm of the projected
imput vector onto Mr. Suppose that there exists constants c, B > 0 such that for any W W and (ar, y). have [[ : V((fw.(x:) y) I2 maxfe. W W }. Then running Langevin diffusion Eq. (4) with Gaussian initialization distribution satisfies E-KL privacy with
pa 1o VD( -1 de where
20²
E
VL(W; VL(W; dt s ST 2T E (VL( V[Wo:
gradient difference at initialization
2,32
2c2T
+
T r) -B [IVL(Wo D)12 + 2o (ank(Mr) +c?)
+F2++87
+ g2
n²
HOm-
gradient difference fluctuution daring training
Proof. By definition of the neighboring datasets D and D', and the definition of empirical risk in Eq. I we have that for any W. it satisfies that
1 D' n² ((((f()); - ve(ff(x'); 3')
VL(W:D) VL(W; (E(W:D))1
(20)
where (x. y) and (x'. are the differing records between neighboring datasets D amd D'. By the assumption that [[V[[w (m): y)) Vê(fw- y)ll
Bax W and by the Cauchy-Schward inequality, we further have that for any W and W.. it satisties that
(x)) Ve(Sw. (2 2 $2 (V[Vw, (m); VE(Sw, 9'))
+ W Wo 1 1 + 2c2.
(21)
The first term Ve(ff.(z)) y)) ve(fwo (x'); y 21 is constant during training (as it only depends on the initialization). Therefore, we only need to bound the second term IWW Wolls,, For brevity, denote the function ((W) IW 1 Recall our definition, p. the distribution of model parameters after rumning Langevin diffusion dataset D with time and p' the distribution of model parameters after running Langevin diffusion on dataset D' with time Then we have that
i Ep. / (W))
Ep... (W) Ep, ($(W)
lim 7-00
(22)
at
Denote Г, as the following random operator on model parameters 0.
r. (.W) sVL(W;D) + 220
18

---

where Z ~ (O,,I) I). We first claim that the following equation holds.
E P ( (W)
- Ep, [T (W(T)
lim 7-
(23)
This is by using Buler-Maruyame discretization method to approximate the solution W. of SDE Eq. 44. More specifically, the approximation enror fp._,,1((W) Ep, [T, (W)) is of size (rr)") for small 17, where r is the dimension of W.
Therefore, by plugging Eq. 23 into Eq.
22 we have that
a Ōt
E (T,
W]] Ep. (W)
p. 4 (W)
lim 7-0
1
Recall that (W) exists almost everywhere with regard to W ~ Pc. Therefore we could approximate the term Ep, (W), D'] via its second-order Taylor expansion at W as follows.
0
E. (VF( - (W: + 2222))) VZ +
Ep. [#(W) lim
Øt
71+0
= =- Ep, (V VL(W; P)) + -'p, [Tr (V2
(24)
By plugging (WW IIW - Wollis, into Eq. 24D. we have that
0
Ep, W Wollirr1 S 212 ((W - Wo, VL(W:D)) + 2o"rank
(25)
0t
-12pp ((W Wo. VL(W;; D)) 202ranki (
2Tp ((W
Wo. VL(W: D) V.(Wo; D))
V. D) + E,, || Wol + 2o 2o²rank(M7)
(26)
+ Ep,, Woll + E,, [V D) VL(Wo; D)1)),
(27)
where the last inequality is by using the Cauchy-schwards inequality. By plugging the assumption that [V((f((z):)) V((fw(());
max W [W'll into the above inequality, we
have that
i Øt
Ep. Woll M S (2 8²) E W Wol + E|| VL D) + 2oakknk(Mr)) + oZ.
(28)
By solving the above ordinary differential inequality
E [0, T). we have that
Ep. (] WollBe,
[E VL D) + (aTr + +o?)
(29)
2
g2
By plugging Eq. 22 into Eq.
21 and Eq. 20 followed by integration over time t [0,
have that
Ep. []L(W;D) - -LL0--LLWW;11))
dt < 2T Ep,
- VL(W; [VC:::D)V<<(:>))1 (30)
2,32
7) (Eoo [IV + Foo2rnk(MM) + (
20
n² n² + (2)
2 g2
n²
(31)
which concludes our proof.
19

---

C Deferred proofs for Section 4
C.1 Bounding the gradient norm at initialization
To bound the moment of l norm of the gradient @f(m) of network output function, we need the following (extended) lemmas from Zhu et al. [54].
aw,
Lemma C.I (154, Lemma 1J). Let w oN)), then for two fixed non-zero vectors h1, h2 E In whose correlation is unknown, define two random variables X = (w h1 hu2h220>> )² and = s(w h1)², where Ber(1, 1/2) follows Bernoulli distribution with 1 trial and 3/2 success rate, and and w are independent random variables. Then X and Y have the same distribution.
Lemma C.2 (Extension of [54] Lemma 2J). Given a fixed non-zero matrix H1 E TRxx and a fixed non-zero vector h2 RpP and, ler W RAxP be random matrix with i.i.d. entries Wij (0.
and matrix (or vector) V o' ('(Why h2) W E R2xr then, have E8 V
q8
Proof. According to the definition of V
E Rexr, have:
= DirlW )
where Dú,; = 1 h210)) wil [il the i-th row of W, and Ie is the j-th column vector H
Therefore by Lemma C.1 with i.d. Bernoulli random variable Pl, Pq ~ Ber(1, 1/2), we have
|V
W b
P
(32)
i=1j=1
where úis (Wi+), H! H
(V01
81| |+ 12 By the fact that W has i.i.d. Gaussian entries, for 1, . independently. Therefore, we have
any fixed j, we have that Wij NO, 1),2
933 Ell H1
E [
E E 3 H BE
Now, ready prove output gradient expectation at random initialization follows.
Lemma C.3 (Output Gradient Expectation Bound at Random Initialization). Fix any data record then over the randomness of the initialization distributions for WI. WL. i.e. Wi W NO0 3/11) for = L.... L 1, it satisfies that
0f(x)
L-1
8,m
Br.
Ew
||
@Vec(W W)
17 = =1
II
2
3
(33)
Proof. We use Vec(Wi) to denote the concatenation of all row vector of the parameter matrix W,. By chain rule, for = 1,.... LL- 1, we have that
0f(x: WVi(Wi) )
oh (a:)
Ih, ((x)
Thy Vee
(34)
Wi)
h
L-1-1
W
II i=1
o' W
(35)
0
0
h
my X X1
20

---

Similarly, for the L-th layer, we have that
h
0f(x) VVe
(36)
f.
h
exomL
By properties of ReLU activation 6, have ø (rrgssgn(W.sshh..oo ))), where sgn(3))
[1 x >
operates coordinate-wise with regard to the input matrix. Therefore, we have that for
[0 00 1 1= 1-,,.,,--
h4-1 0
0f(x) @Vec(Wi))
WEE
II
diag(sgn(Wiht.s
h
172 X 17777777
For notational simplicity, we introduce the notation of t for / = 1,... L and I S l < follows.
L as
h
L-1-1
II
II ( Li=L-
diaglsgn(Wihh-a
0
h
my X111101-11
Then by definition, we have that
Of(x)
W T. 112
|| He/-111 1
| |
Ew
1 = Eww [l] 1. 1 = Ew (Ve)
||
||t/-111
|| 1e/--2113
[16/1p Ewat
||//t112
W
11
Ew Wi
... Ewz
||
||t1
I1?
By rotational invariance of Gaussian column vectors, we prove that for any possible value of t (which is completely determined by W,,..., Wr. and æ), for any / = 1,..,,,..
have that
W 1 4- 11
W
Ewz
Ewz
Byo.
(37)
11
||e
By Lemma C.2 for any = 1,... L and / S < L - 2, we have that
||t| || I|?
12
Br+1
Ewi+1
mp+1
(38)
We now bound the last term Ew,.... wi [[]t/11]]]] for l = 1,... L 1. By definition, we have that
mi
Ew wi [| = Ew,,...
(w] h 1114-111 = mi Ew, .......... EE h [1]]
2
(39)
To bound the Ew,... wi 1111111113 note that by Lemma C.2 prove that for any 1 1,... T.
| (x)
8
E Ew
mi-1
(40)
2
21

---

Therefore, for any 1 = 1,... L, we have that
|/
1
| (3)
112
Ew Wi-1 Wi-1 [1]b4-1(2] (x) [[ = Ew Wi-1
||
(41)
2
11
8 mi
|
|
(42)
2
By plugging 42
into 39
we have that
Ew 1e Wi
771
3
m²;
|
(43)
2
By combining
37
38
and
43
we have for any 1 = 1,
L
--1
(x
Ew
1
(eec Wi)
my
II
3:
mi -Br ||0012
31
|
1.0
II
B.m
2
2
B1
2
i=1+1
i=
On the other hand, by plugging Eq.
42
(under 8 = L) into Eq.
(36).
have that
0f(x)
8
Ew
(eec
W1)
m
|
Therefore,
(f
0f(x)
L-1
8am
B1
Ew ||
1
1 = |
100100
II
(Vec(W> W)
oW;
2
3
1=1
which suffices to prove Eq.
(33
C.2
Deferred proof for Theorem 4.1
Finally, we prove that the gradient difference between two training datasets under linearized network bounded by a constant throughout training (which only depends on the network width, depth and initialization distribution..
Theorem 4.1 Under Assumption 2.2
taking over the randomness of the random initialization and the Brownian motion, for any E 0. T, rumning Langevin diffussoo on linearized network Eq. (3) satisfies that
4B n
E L(W!i :D) L(W!!m; D')
(44)
where n is the training dataset size, and B is a constant that only depends on the data dimension d, the number of classes o, the network depth L, the per-layer network width 24 and the per-layer variances {B:) of the Gaussian initialization distribution as follows.
L-1
B :=
II
8,m,
31
(45)
2
3
Proof. Denote W as the initialization parameters and denote W as the parameters for linearized network after training time l. Then the gradient difference under linearized network and cross-entropy loss function is as follows.
LWW: D) VL(W;; D')
V fww ( (softmax (fwnmmaxwwwwWie (m)) y) fww(x') (softmax(fwe (2r)) yy)
n
n
2 (Z) Vfw (
n
Plugging Lemma
C.3 into the above equation with data Assumption 2.2
2.2 suffice to prove the result. -
22

---

D Deferred proofs for Section 6
D.I Deferred proof for Lemma 6.1 on convergence of training lincarized network
In this section, we prove empirical risk bound for the average of all iterates of Langevin diffusion, building standard results [42] Theorem 2] and [5 Theorem 3.1] for the (discrete time) stochastic gradient descent algorithm.
Lemma 6.1
(Extension of [42 Theorem 2] and 45 Theorem 3.1 Let So (W; D) be the empirical
risk function of linearized newtork Eq. expanded at inirialization vector W Let W be an a-near-optimal solution for the ERM problem such that (W;; D) minw L (W; :) S 01,-". ... Enn be an arbitrary training dataset of size and denote Mo =
a. Let D
(V (21)..... Swwjin (xx)) as the NTK feature matrix at initialization. Then running
Langevin diffusion (4) on C (W) with time T and initialization vector Whnh satisfies
R
Bich" (W]") min Clin (W; S +
2T
where the expectation is over Brownian motion By in Langevin diffusion Eq. 4 Whin
+ J w dt is the average of all iterates, and R W W; Will,, is the gap between ini- tialization parameters W and solution Wü.
Proof. Our proofs are heavily based the idea in 45 Theorem 3.1] to work only in the parameter space spanned by the input feature vectors. And our proof serves as an extension of their bound to the continuous-time Langevin diffusion algorithm. We begin by using convexity of the empirical loss function Clin (W; D) for linearized network to prove the following standard results
Elin (Wlmn; :D Clin (Wi: D) S (W Wi V. (W))m:))))
(46)
S (z)) and compute the gradient under cross entropy loss and linearized network, we have V v (W4in; D) lies the column space of Mg. Denote II the projection operator to the column space of Mu, then (46) can be rewritten
Denote Mo- Swi (.1)
cb WW lin D) clin (Wo: D)= < (I (Wi W;), V 2ln (W/ :D).
(47)
By taking expectation over the randomness of Brownian motion in Langevin diffusion, we have
El ([CCh((Wii))) (Whi
Cbin DW <
1
/" E [[LM. (Wiin W V (W! D)) dt. (48)
T
We now rewrite E [[MM (W!in - Wi), v C/ (W! lin, D)}} by computing B Wū 1
M
where W W5 12,4 11,, (W/in W;) MMM (W - Wi). By applying (24) with Pt being the distribution for W in Langevin diffusion for lincarized network starting from point initialization With. and with function d(W) W Wo lar we have that
0t W
Wolla
( (W!lin W)) V (W:in; + o (rrank(MM)
(49)
Therefore by plugging
(49 into 48 we have that
E(clin (Wii")) c!in ( D) <
1
('' at
Bl W. Wi M, let + 1
o rorran((Mo)
0
(50)
2T
11 + 1
<
Wiin
W;
0
(51)
27
23

---

D.2 Deferred proof for Lemma 6.3
To bound lazy training distance of training linearized network, we would need the following auxiliary Lemma about high probability upper bound for the final layer output of linearized network at initialization.
Lemma D.1. Fix any data record a, then with high probability å over random initialization Eg. 5 of model weight matrices W Wh for layer 1, I, i.e, Wi ~ (0, B,T), it satisfies that
L-1
II 3.m+ ))
(x) S 1=
Br
(52)
where Ô ignores logarithmic terms with regard width m, depth L and tail probability
Proof. To bound the term ||f (2:))1 12
by definition Eq. ( for any æ, we have that
(1)
(x) | (a)
If (x)
(53)
h x
hn(())]
We now bound the terms in the right-hand-side of Eq. (53) one by one.
(aiil
Regarding the first term we have that
Eq. (33) observe that by the network output definition Eq. (2)
[ 1
(2))1 | |h
(54)
where ~ NN00 1) and the last equality is by rotaional invariance of Gaussian distribution used for initializing L-th layer weight matrix W E I Therefore, by tail probabilty expression for standard Gaussian random variable, we have that with high probability 1 à over random initialization of WL E Rlxm it satisfies that
I,
(x)) h (x)
L - 23r log
(55)
(x))
Regarding the terms
in Eq. (53) for layer 1,... , - - 1, by setting H1
-22 = 44-1
[4, 1(m))
Eq. 32). we immediately prove that over random initialization of weight matrix w 1m it satisfies that
[/((
mi
(56)
|1 (x)
where "I,-. PPm 3...d.
Ber(1, ()) and . Tm: NO 1) and pr and W; are independent.
By tail probabilty expression for Gaussian random variable w. we have that P( 2 t) < et/2 1/2 for any > By union bound over 1.... my, we prove that for any /ayer/=1, high probability 1 zr over random initialization of weight matrix WI E m it satisfies that
1, with
max wf < 22log 2m4L
(57)
Moreover, by applying Hoeffding's s inequality to i.i.d. Bernoulii r.V.S PI. ...... PP,. we prove with high probability 1 - 27. it satisfies that Σ P: < (1 + log(2L/5)) By combining with Eq. (7) via union bound, and plugging the result into Eq. (59). we prove for any =....., 1, satishes with high probability 1 z over random initialization of weight matrix Wi m that
2m
m log
(1 + log(2l1/5))
(58)
8
24

---

By using union bound over Eq. (58) for layer = 1, .... .. and Eq. (55). we have that with high
probability 1 å over random inittalization Eq. (5). it satisfies that
[ (<))
T-1
S 0 II 3.m))
(59)
|
2=1
where Ô ignores logarithmic factors with regard m, L and 6.
By plugging Eq. (59) into Eq. (53), we prove that with high probability over initialization Eq. (5), the following bound holds.
L-1 8L
( S |=130
(60)
where ① ignores logarithmic terms with regard to width m. depth L and tail probability 6.
(Bounding lazy training distance via smallest eigenvalue of the NTK matrix) Under Assumption 2.4 and single-output linearized network Eq. (3) with o 1, assume that the per-layer network widths m m (2()) are large. Let (W) be the empirical risk Eq. ( for linearized network expanded initialization vector Wii. Then for any Whkn there exists
Lemma 6.3
corresponding solution W s.t. L (W,' minw L (W;D) S n2 rank(Mo) n and
R RSO max
72
(61)
d3L
1-1 Bem.) [T
Σi= BT
with high probability over training data sampling and random initialization Eq. logarithmic factors with regard to n, m, L, and tail probability
5 where O ignores
Proof. Given an arbitrary initialization parameter vector Wiin we first construct an solution W 0 that is nearly optimal for the ERM problem over C (W), as follows.
2 2nn y1 Swain (x11)
Whin My
(62)
2lnn yo - fwim (xx)
V fwij (211)
where Mo =
is the gradient matrix at initialization and i denotes pseudo-inverse.
V fwgin (xn))
We now prove that the solution " is close the initialization parameters Wiin in l2 distance with high probability. By applying the holder inequality in 62). we have that
lnn yn Swaen (x11)
W +
113
|
(63)
2 2nn Un fwie (xx))
12
22n V1 Swi (x11
(64)
Au
2lnn 3n fwgin (xn))
where do is the smallest non-zero eigenvalue of the PSD matrix MoM, When the data regularity
assumption Assumption 2.4 holds and the per-layer width mo. ... my {i(n), by applying existing
bounds for the smallest eigenvalue of the NTK matrix MoM for single-output network in (40
25

---

Theorem 4.11, we prove that with high probability over data sampling and random initialization Eq. it satisfies that
))
I Bt
Ao
1=1
1=1
)
Ω
Bt
(65)
where we have the auxiliary variables & my ((x) are large enough for | = 0,. (where n is the number of training data).
40
Theorem 4.1] because the per-layer width
Therefore, by using Eq. (65). we have that with high probability over data sampling and random initialization Eq. it satisfies that
1 So Ao
(
mi) (TL 3.) -E (
(66)
where my is the width of layer and is the number of training data.
For the second term in Eq. (64). by Cauchy-Schward inequality, we have that
2 In in Swiin (x1)
2. (2 Σ
2 yi
+ >
II [wiin (2%))12
(67)
2lun Yn - Swiin (2en)
By Lemma we have that || f (x)ll2 S Ō 3r. (II Bems)) with high probability over
the random initialization Eq. (5) By plugging this result and yı E { {-1,1} 13 into Eq. 667p. have that with high probability over random initialization Eq. (5), it satisfies that
Inn- 91 Swgii((1)
n ( ndßr,
II B.m. Bmm.)
))
=
(68)
2 Un. Swgin (xn))
where Ô ingores logarithmic factors with regard n, m. L, and tail probability d. Therefore, by
combining Eq. (66) and Eq. (68) with union bound, and by plugging the result into Eq. (64), we have that with high probability over data sampling and random initialization Eq. (5). it satishes that
(IT--) Bemm)
n -d33
R RSO
θ
L-1 Bim) [1Br.
EEhn B7
1
s Ô
max
d3g
(II 3em,
Σ BT
where my is the width of layer I, is the number of training data, and Ô ignores logarithmic factors with regard to n, m, L, and tail probability
We finally prove that W n² _ -earr--ptimmal solution. Note that Eq. 65 implies that with high probability Mo is full rank, i.e., rank M. Therefore M, Mo (M
f
+ (x1)
w
2 Inn y1
and
with high probability over the training data sampling and
(wn).
2nan V/
w random initialization Eq.
5 By plugging it into the cross-entropy loss for the single-output network
26

---

defined below Eq. T we have that with high probability over the training data sampling and random
initialization Eq. the solution W satisfies
1 n2
Co (Wo*) min Co (W;D) s log(1 + exp((=2lnn) <
(69)
D.3 Deferred proof for Corollary 6.4
Corollary 6.4
(Privacy utility trade-off for linearized network) Assume that all conditions in be the gradient norm constant proved in be the lazy training distance bound
Lemma 6.3 holds. Let B d
[II [ 8.m.
Br
Bi
Eq. and let R s δ max dBu (11 Bems)
2 BT
proved in Lemma 6.3 Then for o²
2B releasing all iterates of Langevin diffusion with time I satisfies e e-KL privacy, and has empirical excess risk upper bounded by
2BT
and T
v
endt
en²
BR EN
min Chin (W;D) W
+
(70)
n2
L-1
=
2L-18 max 1, d3L
II 3mm}
(71)
12
with high probability over random initiailization Eq. 5). where the expectation is over Brownian motion Br Langevin diffusion, and Ô ignores logarithmic factors with regard to width m, depth L, number of training data n and tail probability 8. A summary of our excess empirical risk bounds under different initializations is in T
Proof. By setting W = W in Lemma 6.1 with W constructed as Lemma 6.3 high probability over random initialization Eq.
we have with
have
R
22n
E EICba lin [W]i)]]
min Clin W; D) W
(72)
n1
2T
where Ō max
do (TT 8em))
A. by Lemma 6.3
Meanwhile, ensure KL privacy, by Corollary 4.2 we only need set o²
2BT
where
en
1- 9.m.
Σl S.
by for single-output network with 1. By plugging o²
2BT
2
en3
into
72
prove that
1
R
BT
LLchin lin Whin
E
min clin W
(W;D)
773)
n
27
Setting T
SnR in 73 and elaborating the computations suffice to prove the result.
E Discussion on extending our results to Noisy GD with constant step-size
In this section, we discuss how to extend our privacy analyses to noisy GD with constant step-size. Specifically, we only need to extend the KI. composition theorem under possibly unbounded gradient difference, i.c., Theorem 3.1 to the noisy GD algorithm.
Theorem F.1 (KI composition for noisy GD under possibly unbounded gradient difference). the iterative update in noisy GD algorithm be defined by: W(K+1) W()) (VV
27

---

2210 kk where Zμ (O, Then the KL divergence between ramning noisy GD for DNN 2 on neighboring datasets and D' satisfies
K
((:W()))) ((.k))
Σ n E
(k)) (CDD))-C((Wee))) [12
(74)
2
Proof. Denote P(k)) the distribution of model parameters after running noisy GD on dataset D with steps, and similarly denote P(M) as the distribution of model parameters after run- ning noisy GD dataset D' with & steps. Similarly, denote P(1-)) the joint distribution of (W (1), W(R)), and denote P(a.a) as the joint distribution of (W (1):""' ((a)). Now we expand the term K (((((1,+)))) ((14))))PP. P(I,o+1)) by the Bayes rule follows.
K (A
(75)
P(++1)((:)) W (K+1) W (ass) Pa ( (1:4))
= (Wa
log
P(+DIIC W (k++1) ((sse)) ( (((:)))
P(++1]((1A)) W (K++1) (a:s))
P(1:a) W (1:s))
log -E PP
E8
pa (Wars))
log
P(++1111))) W (16+1))
W(1:s))
Plaaas (((ss))
=E, -Erass L P
(76)
Observe that conditioned fixed model parameters (1:k) at iteration I, k, the distributions P(++1))(::)) ((x42))())))) are Gaussian with per-dimensional variance o², Therefore, by computing KL divergence between two multivariate Gaussians, we have that
1 KEAP) = 20 7 | (N): D) VL( (s) D'
(77)
Therefore, by plugging Eq. (77 into Eq. (76). we have that
KL(P(IA- 2 E
V (w): - VL(W (1): D 11 + K (P P(ua)) (78)
By summing (78) over = 0.... KK 1 and observing that (P( P(oy)) = 0 (as the initialization
distribution is the same between noisy GD on D and D'), we finish the proof for Eq. 774..
28


Reviews:
[{"review_id": "2ZDniO9z0M", "reviewer": "Reviewer_LMCn", "summary": "The authors propose a KL privacy bound for DP-SGD that depend on the width, depth, and initialisation of the neural network. They show that the privacy bound improves with increasing depth for the LeCun and Xavier initialisation while it degrades with increasing depth. ", "questions": "1. The result about the improving privacy bound is really surprising. Do the authors have an intuition why this is the case? ", "limitations": "Limitations are not explicitly mentioned. The authors touch upon the restrictive results on linearised networks but this limitation is mostly underplayed. It would be interesting to discuss more when this simplification can lead to worse results. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors came up with an original idea exploring a topic that has so far received little attention in the literature\n2. the findings are somewhat surprising and unintuitive ", "weaknesses": "1. Often there are mistakes in privacy proofs. Having some experiments with privacy auditing to back up the surprising results would make the results more credible. \n\n2. There are many typos in the middle of the paper. Especially related to the use of articles (articles missing) or repetitive words. \n\n3. The authors motivate their contribution by the loose privacy bounds of DP-SGD. But the privacy bounds are then not used to improve the privacy accounting of the neural network. \n\n4. Limitations not discussed in depth ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for spotting the typos, we will correct them in revisions of the paper. Below we clarify the questions and concerns. \n\n---\n\n> Often there are mistakes in privacy proofs. Having some experiments with privacy auditing to back up the surprising results would make the results more credible.\n\nWe have added numerical experiments to validate our privacy bound under different width, depth and initialization. Please see general response point 2  for a detailed discussion, and see the attached pdf for complementary plots.\n\n---\n\n> The result about the improving privacy bound is really surprising. Do the authors have an intuition why this is the case? \n\nSee general response point 1 for a detailed discussion about intuition for improving privacy bound.\n\n---\n\n>The authors motivate their contribution by the loose privacy bounds of DP-SGD. But the privacy bounds are then not used to improve the privacy accounting of the neural network.\n\nWe are not arguing DP-SGD privacy bound is loose and do not claim a contribution for improving upon the DP-SGD privacy bound in terms of privacy accounting. Indeed, we focus on a different KL privacy notion and a different algorithm (without clipping), and are therefore not comparable with DP-SGD privacy bound. Instead, **we argue that prior analysis for privacy under overparameterization for the DP-SGD algorithm are overly general to network properties such as width, depth and initializations**. And this is due to the significant difficulty for analyzing the effect of gradient clipping in DP-SGD training. \n\nOur approach circumvents this difficulty of analyzing gradient clipping (and thus provides a precise understanding of privacy under overparameterization) by focusing on a new algorithm Langevin diffusion, i.e.,  noisy GD **WITHOUT** gradient clipping. To the best of our knowledge, there is no existing differential privacy bound for this setting (no clipping). Therefore, we focus on KL privacy (which is generally a more relaxed definition than DP), and analyze the interplay between overparameterization and privacy.\n\nWe would like to highlight that our main result Theorem 3.1. is a general KL privacy bound that applies to training arbitrary deep neural networks (as exemplified by Lemma 3.2 and our added numerical KL privacy loss in the general response). For the special case of linearized networks, we are further able to analytically analyze how privacy and utility changes with model width, depth and initialization. \n\n\n---\n\n- [Discussion on limitation] \n\nWe thank the reviewer for pointing out the limitation of linearized network. We have added a discussion in our [general response point 3](https://openreview.net/forum?id=IKvxmnHjkL&noteId=jh61g9pgBi), and will clarify this in future revisions of the paper.\n"}, {"review_id": "VF2rBX1bXp", "reviewer": "Reviewer_Ej4s", "summary": "This paper theoretically analyzes how the width, depth, and initialization of deep neural networks affect the privacy utility trade-off. For the special setting of linearized networks, the paper shows that gradient norm and privacy loss hinge on the per-layer variance of the initialization distributions. Thus, the privacy trade-off can be governed by width, depth, and initialization. Interestingly, for LeCun's initialization, the utility can be amplified by increasing depth which is against common intuition that overparameterized models will worsen the privacy utility trade-off. ", "questions": "1. What is the relation between the KL privacy bound and the differential privacy bound? What is the motivation to study the KL privacy bound?\n2. Can you explain the counterintuitive derivation given a variable factor in $\\beta_l$? See Weakness 3 for details.\n\n----- Update after reading rebuttals ---\nThe authors have addressed most of my concerns.", "limitations": "The authors did not discuss the limitations or potential social impacts of the paper. \n1. The paper presents some promising privacy improvement through proper initialization and also demonstrate some increasing risks if networks are not properly initialized. The results could be an important signal for people to treat the initialization seriously. I suggest the authors make the social impact clearly in the paper.\n2. The paper has some inherent limitations due to the analysis tools of Lagevian diffusion algorithms, for example, the requirement for linearized networks, large depths, etc. The limitations are hard to address in the scope of the paper but is worth to mention for readers to under the proper use cases.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical finding on the connection between depth and privacy-utility trade-off is interesting, that the deeper network can achieve better tradeoff than the shallow ones given LeCun's initialization.\n2. It is novel that the network properties, e.g., initialization is analyzed through the Lagevian dynamics on linearized networks.", "weaknesses": "1. The presentation coould be improved. Some typos in the formulations make the paper hard to follow.\n   * KL privacy bound is used before the definition or explanation in Line 38. Especially, what is the relation between the KL privacy bound and differential privacy bound?\n   * The definition of the non-lazy training regime in Table 1 is not defined.\n   * For the definition of LeCun initialization, the $\\beta$ is layer-independent in Line 262 as $\\beta_2=\\cdots =\\beta_L={1\\over m}$. But in Table 1, the $\\beta$ is layer-dependent as $\\beta_l = \\frac{1}{m_{l-1}}$.\n   * In Line 24, `is randomze` should be `is randomizing`.\n2. The difference between LeCun's initialization $\\beta_l=1/m_{l-1}$ and others $\\beta_l=2/m_{l-1}$ is mainly in the factor, `2`. The authors could give a more intuitive explanation for why the factor is crucial for privacy. \n3. More generally regarding the factor in initialization, analyzing the best factor (probably some value between 0 and 2) may lead to a counterintuitive trade-off between privacy and utility. If I follow the derivations in Line 264-265, the excess empirical risk for LeCun's initialization with $\\beta_t=\\frac{a}{m_{l-1}}$  with $a\\in (0,2)$ could be proportional to $\\frac{a}{2}^{L/2}$. This means that the risk bound will be greatly reduced when $a$ approaches zero. However, this is counterintuitive, as a smaller $a$ implies smaller $\\beta_t$, and therefore model will be initialized almost as zero. As common knowledge, zero parameters are not favored for the initialization of a deep network. In brief, smaller initial parameters will quickly vanish the activations by layer and therefore the model cannot converge or of low utility. Unless I missed some assumptions, the derivation is problematic due to the above counterintuitive results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the detailed comments and pointers to typos, which we clarify below.\n\n---\n\n> [Definition for KL privacy] \n\nA randomized algorithm $\\mathcal{A}$ satisfies $\\varepsilon$-KL privacy if for any neighboring datasets $D$ and $D'$, we have that the KL divergence $KL(\\mathcal{A}(D)\\rVert \\mathcal{A}(D'))\\leq \\varepsilon$, where $\\mathcal{A}(D)$ denotes the algorithm's output distribution on dataset $D$.\n\nKL privacy and relaxed variants of it are commonly used in previous literature [b, c, d].\n\n---\n\n> [Relation to differential privacy] \n\nKL privacy is a more relaxed, yet closely connected privacy notion to $(\\varepsilon, \\delta)$ differential privacy. \n\n1. KL privacy and differential privacy are both worst-case privacy notions over all possible neighboring datasets. \n\n2. KL privacy and differential privacy are both definitions based on the privacy loss random variable $\\log\\frac{P(A(D) = o)}{P(A(D’) = o)}, o\\sim A(D)$ (following the definition in Abadi et al. Equation 1). KL privacy implies that the privacy loss random variable has a bounded first order moment, while differential privacy requires a high probability argument that the privacy loss random variable is bounded by $\\varepsilon$ with probability $1-\\delta$. Therefore, KL privacy is generally a more relaxed notion than differential privacy. \n\n3. Translation to each other: For $\\varepsilon = 0$, KL privacy (bounded first-order moment of privacy loss random variable) implies $(0, \\delta)$-differential privacy with $\\delta = \\sqrt{\\frac{\\varepsilon}{2}}$ by Pinsker inequality. Higher order moments of the privacy loss random variable suffice to prove (\\varepsilon, \\delta)-differential privacy for $\\varepsilon >0$. Reversely, $\\varepsilon, \\delta)$-DP with $\\delta>0$ does not imply KL privacy, as the privacy loss random variable may be large at the tail event with $\\delta$ probability.\n\n4. Due to the connection to the privacy loss random variable (which closely connects to likelihood ratio attack), both differential privacy and KL privacy incur upper bound on the performance curve of inference attacks, such as the membership inference and attribute inference [32, 22], as we discuss in the footnote 2.\n\n---\n\n> [Definition for non-lazy training in Table 1] \n\nFollowing the ‘condensed regime’ defined in [31, equation 16], we refer to non-lazy training as settings with unbounded ratio $\\frac{\\lVert W_t - W_0\\rVert_2}{\\lVert W_0\\rVert_2}$ between the change of model parameters after GD training with time $t$, and the L2 norm of model parameters $W_0$ at initialization. We will add this in the revised version.\n\n---\n\n> [Definition of per-layer variance of LeCun initialization] \n> For the definition of LeCun initialization, the $\\beta$ is layer-independent in Line 262 as $\\beta_2 = … = \\beta_L = \\frac{1}{m}$. But in Table 1, the $\\beta$ is layer-dependent as $\\beta_l = \\frac{1}{m_{l-1}}$\n\nThese two lines define the same per-layer variances. This is because $m_1 = … = m_{L-1} = m$ (as in the second line of Table 1 caption), i.e., all the hidden-layers have the same width. We will clarify this in future revisions of the paper.\n\n---\n\n> The difference between LeCun's initialization and others is mainly in the factor, 2. The authors could give a more intuitive explanation for why the factor is crucial for privacy.\n\nSee general response point 1 for a detailed discussion.\n\n---\n\n> [Counter intuitive example of privacy utility trade-off for point initialization at 0] \n\nWe thank the reviewer for bringing up this very insightful example. We will add it to future versions of the paper. **This is not a counterexample to our analysis, because we prove utility in excess empirical risk (not empirical risk).**\n\nOur privacy and utility bounds hold under setting initialization variance $\\beta = a/m$ for $a$ that is in a constant order (independent of width m and depth L). If we set $a$ to be zero, the KL privacy bound (Corollary 4.2) and the excess empirical risk bound (Corollary 5.4) will indeed both be zero, as pointed out by the reviewer. This is because the linearized network (Equation 3) expanded at point initialization 0 is a family of constant prediction functions (that maps all input data to 0), no matter what the expansion weights $W$ are (due to the zero NN gradient at 0). Consequently, the gradient throughout noisy GD training is zero. Similarly, the excess risk, which is the training loss difference between the trained model and the optimal model in the family of linearized networks expanded initialization, is also zero. \n\nHowever, the empirical risk (not the excess empirical risk) is still high despite zero excess empirical risk, because the approximation error of linearized networks expanded at zero is large. That is, excess risk bound for the linearized network with zero initialization setting becomes meaningless.\n\nThis is why in this paper we only analyze excess empirical risk bound for commonly used initialization distributions, for which the approximation error is small empirically (Figure 5 [a]). To guide the privacy utility trade-off for arbitrary initialization distributions, it would be necessary to conduct a more comprehensive utility analysis that covers approximation error for linearized networks under different initialization. We leave this as interesting future work. \n\n---\n\n> [Discussion on limitation]\n\nWe thank the reviewer for pointing out the limitation. We have updated our discussion in general response point 3.\n\n\n**References**\n\n[a] Ortiz-Jiménez, Moosavi-Dezfooli, Frossard. What can linearized neural networks actually say about generalization?. NeurIPS 2021.\n\n[b] Barber, Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451.\n\n[c] Bassily, Nissim, Smith, Steinke, Stemmer, Ullman. Algorithmic stability for adaptive data analysis. STOC 2016.\n\n[d] Wang, Lei, Fienberg. On-average kl-privacy and its equivalence to generalization for max-entropy mechanisms. PSD 2016.\n"}, {"review_id": "XnPSorVmoc", "reviewer": "Reviewer_NB2b", "summary": "This paper presents the KL privacy bound for training fully connected networks and its linearized variant using the Langevin diffusion algorithm. The study delves into the impact of network width, depth, and initialization on privacy. Notably, the paper reveals that, with specific parameter initialization, the KL privacy bound can be enhanced by increasing the depth of the network. Additionally, the author provides a proof that the privacy-utility trade-off of linearized networks can be improved with depth when employing LeCun initialization.", "questions": "Questions:\n1. In Lemma 3.2, Equation (7) suggests that for relatively large T, the dominant factor in the KL privacy bound is the fluctuation term of gradient differences, which appears to be independent of the differences between neighboring datasets $D$ and $D'$. Could the author provide further clarification on this matter?\n2. Additionally, I am curious about the evolution of the rank of $M_T$ with respect to time T. The author briefly touches upon this aspect, but a more detailed explanation would be appreciated.\n\nSome suggestions and corrections for the paper:\n1. In Assumption 2.2, it would be preferable to use a commonly recognized constant symbol such as 'C' instead of '\\phi' to denote a constant.\n2. There seems to be some confusion in the notations in lines 151 and 152. Is it intended that x_1 = x, y = y_1, and y' = y_2?", "limitations": "See above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The author investigates an intriguing problem that is likely to capture significant interest within the community.\n\n2.The results presented in the paper are not only interesting but also coherent, aligning well with the research topic.\n\n3.The paper is skillfully written, allowing for easy comprehension and smooth flow of ideas.", "weaknesses": "The paper lacks numerical experiments to validate the disparity between empirical KL privacy leakage and the privacy bound proposed in this paper. This would shed light on the tightness of the bound. Given that the arguments are based on the upper bound, providing numerical experiments demonstrating the evolution of empirical KL privacy leakage with varying depths and widths, aligned with the theoretical findings, would enhance the persuasiveness of the research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper lacks numerical experiments to validate the disparity between empirical KL privacy leakage and the privacy bound proposed in this paper. This would shed light on the tightness of the bound. Given that the arguments are based on the upper bound, providing numerical experiments demonstrating the evolution of empirical KL privacy leakage with varying depths and widths, aligned with the theoretical findings, would enhance the persuasiveness of the research.\n\nWe have added numerical experiments to validate our privacy bound under different width, depth and initialization. Please see [general response point 2](https://openreview.net/forum?id=IKvxmnHjkL&noteId=jh61g9pgBi) for a detailed discussion, and see the [attached pdf](https://openreview.net/attachment?id=jh61g9pgBi&name=pdf) for complementary plots.\n\n---\n\n> In Lemma 3.2, Equation (7) suggests that for relatively large T, the dominant factor in the KL privacy bound is the fluctuation term of gradient differences, which appears to be independent of the differences between neighboring datasets $D$ and $D'$. Could the author provide further clarification on this matter?\n\nYes, the dominating fluctuation term in Lemma 3.2 does not explicitly depend on the gradient difference between datasets $D$ and $D'$. However, it upper bounds the gradient difference at time $T$, due to the relaxed smoothness assumption of loss function, as we explain below.\n\nThe key of our analysis in Lemma 3.2, is to reduce the problem of upper bounding the gradient difference at any training time T, to analyzing its two subcomponents. Let $(x, y)$ and $(x', y')$ be the differing data between neighboring datasets $D$ and $D'$, then $\\left\\lVert \\nabla\\ell(f_{W_t}(x); y)) - \\nabla\\ell(f_{W_t}(x'); y')\\right\\rVert_2^2\\leq  \\underbrace{2 \\left\\lVert \\nabla\\ell(f_{W_0}(x); y)) - \\nabla\\ell(f_{W_0}(x'); y')\\right\\rVert_2^2}\\_{\\text{gradient difference at initialization}} + 2 \\beta^2 \\underbrace{ \\lVert W_t - W_0\\rVert_{M_T}^2}\\_{\\text{parameters' change after training time $T$}}  + 2 c^2.$ This is by the Cauchy-Schwartz inequality, and by the relaxed smoothness assumption that $\\lVert \\nabla \\ell(f_W(x); y)) - \\nabla\\ell(f_{W'}(x); y)\\rVert_2 < \\max(c, \\beta \\lVert W - W'\\rVert_{M_T})$ for any parameters $W, W'$ and data $(x, y)$. This assumption is similar to assuming $\\beta$-smoothness for the loss function, with a relaxation threshold $c$. \n\nObserve that the second component (parameters' change) in the above equation only depends on the parameter change after training on the dataset $D$ for time $t$. Consequently, its upper bound, as captured by the fluctuation term of gradient difference in Lemma 3.2, does not explicitly depend on the gradient difference between datasets $D$ and $D'$. Instead, the fluctuation term implicitly constrains the gradient difference at training time $T$ by the relaxed smoothness assumption and the computed upper bound on the parameters' change. \n\n\n---\n\n> Additionally, I am curious about the evolution of the rank of  $M_T$ with respect to time T. The author briefly touches upon this aspect, but a more detailed explanation would be appreciated.\n\nWe thank the reviewer for bringing up this important question. For simple models, such as generalized linear models (Song et al. [38]), this rank of gradient space is smaller than the rank of training data covariance matrix, and thus has a constant upper bound throughout training. For more complex deep neural networks, however, upper bounding the rank is significantly more difficult. This is due to the additive noise, which makes the gradient subspace not exactly low-rank, as the model parameters have non-zero probability of landing at regions where the gradients have high rank (or even full rank). Nevertheless, prior empirical results (such as [a, Figure 2] and [b, Figure 2]) show promises that the gradient space could have a constant or even increasingly small rank as training time $T$ increases. Intuitively, this is the effect of optimization, when the gradient at the reached optima in training has low rank. It remains an interesting open problem to establish theoretical bounds for the evolution of the rank of gradient space during training.\n\nOn the other hand, there is now a significant amount of literature [1, 26, 27, a, b] that enforces low rank for the gradient space artificially during training. This is especially popular for public-data assisted private training, where a standard approach is to estimate a low-rank gradient space on a public dataset [1, 26] or historical gradients [a, b], and then project the gradients to this space during private training.\n\n\n---\n\n> Some suggestions and corrections for the paper:\n\nThanks for the suggestions and pointers to typos, we will correct them in future revisions of the paper.\n\n\n**References**\n\n[a] Yu, D., Zhang, H., Chen, W., Yin, J., & Liu, T. Y. (2021, July). Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning (pp. 12208-12218). PMLR.\n\n[b] Yu, D., Zhang, H., Chen, W., & Liu, T. Y. (2021). Do not let privacy overbill utility: Gradient embedding perturbation for private learning. arXiv preprint arXiv:2102.12677."}, {"review_id": "iSDXjmiWJ5", "reviewer": "Reviewer_R6b6", "summary": "This work aims to connect the structure of a neural network and its initialization scheme to the privacy guarantees it can offer. KL divergence is used as privacy metric, under the settings of Langevine diffusion.", "questions": "third line of caption of figure 1: you write $d = m$ first, and then you mention that you assume $m \\geq d$. Is this a typo?\n\nwould your results still hold if we consider a more natural scaling of the data $\\| x_i\\|_2 \\leq \\sim d$?\n\nYour results are valid only in the case of ReLU networks. Is the analysis generalizable?\n\nIn the discussion after Lemma 3.2 you mention that there are two important keys to control privacy: initialization and training time. You focus your analysis on the first one, and you motivate why the second component is not relevant in the case of small training time. Correct? If yes, how do you verify this hypothesis? Is it a consequence of lazy training?\n\nYour Lemma 4.1 looks to exploit a worst-case bound over the layers of the network, plus the property of the ReLU activation. Can you confirm?", "limitations": "No limitations discussion needed", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper aims to solve a very important problem, i.e. the effects of overparameterization on privacy for overparametrized deep learning models. The analysis through KL divergence allows the problem to be treated analytically, and to connect the structure of the network to privacy bounds.", "weaknesses": "fifth line of caption of Table 1: $n$ and $\\phi$ appear here for the first time. It looks like they represent the number of training samples and your regularity condition parameter respectively. Probably better to mention this in the caption as well.\n\nsame line: $m = \\Omega(n^{14} L^{16} \\phi^{-4})$. To me this assumption looks severely irrealistic for any deep learning model.\n\nThe trade-offs in the table are simply upper-bounds. It is unclear to me how these upper-bounds can be considered tight, therefore telling anything about a possible comparison between different initializations / widths.\n\nActivation function and regularity parameter have the same notation $\\phi$\n\nAssumption 2.1 enforces the samples to respect $\\| x_i\\|_2 \\leq 1$. This scaling is quite innatural considering your initializations schemes. which are designed to renormalize the preactivations when the input norms scale with $\\sqrt d$ (more natural assumption).\n\nEnd of line 151, are the subscripts a typo here?\n\nIt looks that the main bound in Lemma 4.1 derives from a worst case, per-layer computation, under the assumption of ReLU activation. This suggests the bound to be non tight, and therefore to not be informative about how different initializations really affect the preservation of privacy.\n\nLack of experimental validation on the claims in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing out the typos and repeated symbols. Below we clarify the questions and concerns.\n\n> same line: $m = \\Omega(n^{14}L^{16}\\phi^{-4})$. To me this assumption looks severely irrealistic for any deep learning model.\n\nThis condition comes as is from the prior analysis [48] for lazy training distance in the deep ReLU network. This is a standard and fair condition on the polynomial order of $n$ and $L$ in the deep learning theory community.\n\nSince then, there have been various improved analyses on how much over-parameterization is enough in deep learning theory. With some modifications, e.g., the excess risk under a high probability setting, the width requirement in our work can be relaxed from the $\\Omega(ploy(n))$ order to $\\Omega(n)$, see Appendix D.3 for details.\n\nRelaxation on the width requirement is always an important direction in DL theory and we believe that any relevant advances for the lazy training distance analysis in the literature could be used off-the-shelf in Corollary 5.4.\n\n\n> The trade-offs in the table are simply upper-bounds. It is unclear to me how these upper-bounds can be considered tight, therefore telling anything about a possible comparison between different initializations / widths.\n\nTo the best of our knowledge, there are no instance-specific lower bounds for linearized networks derived from fully connected ReLU networks. Nevertheless, our trade-off bounds are based on (and therefore at least as tight as) the prior known tight excess empirical risk bounds for generalized linear model [39]. We leave more fine-grained instance-specific lower bounds as an important open problem.\n\nAdditionally, we have added numerical validation experiments in general response point 2 to validate our KL privacy bound under different width, depth and initialization. We observe that the numerical results are consistent with the trends predicted by Lemma 3.2 and Corollary 4.2. See [general response point 2](https://openreview.net/forum?id=IKvxmnHjkL&noteId=jh61g9pgBi) for details.\n\n> Would your results still hold if we consider a more natural scaling of the data $|x_i| \\leq d$?\n\nThis assumption is only for simplicity of presentation. Our bounds readily extend to $|x_i| \\leq d$, up to a multiplicative factor of $d$. Since $d$ remains constant as the network width and depth increases, it does not affect our conclusion of how overparameterization affects privacy and utility under different initializations. \n\n> End of line 151, are the subscripts a typo here?\n\nYes, it is a typo. It should be $\\forall (x_1, y_1), (x_2, y_2)\\in D$ with $y_1\\neq y_2$.\n\n> third line of caption of figure 1: you write $d=m$ first, and then you mention that you assume $m\\geq d$. Is this a typo?\n\nThis is not a typo. We use $m_l$ to refer to the width of layers $l$. In Figure 1 caption, we write $d = m_0$, meaning that the input 0-th layer has width equal to the data domain dimension. We also write $m_1 =...=m_{L-1} = m$, which means all hidden layers $1, ..., L-1$ have a same width $m$ that is larger than the data dimension $m\\geq d$. We make it clearer in the revised version.\n\n> Your results are only valid for ReLU networks. Is the analysis generalizable?\n\nThe primary challenge in extending our privacy constraints to different network functions lies in adapting our gradient norm constraint from Lemma 4.1. While we focus on dissecting ReLU activation for the sake of analytical clarity, the potential exists to broaden our outcomes to encompass alternative activation functions through analogous analytical calculations [a]. Furthermore, the applicability can be extended to other architectural designs such as ResNet [b,c] and CNN [d, e], leveraging the global convergence outcome. We consider the pursuit of these extensions a crucial avenue for future exploration.\n\n> In the discussion after Lemma 3.2 you mention that there are two important keys to control privacy: initialization and training time. You focus your analysis on the first one, and you motivate why the second component is not relevant in the case of small training time. Correct? If yes, how do you verify this hypothesis? Is it a consequence of lazy training?\n\nYes, the second component does not dominate the privacy bound at small training time $T$, because its factor related to $T$ is $\\frac{e^{(2+\\beta^2)T} - (2+\\beta^2)T}{2+\\beta^2}$. This factor is is smaller than (sublinear to) $T$ for small $T\\leq \\frac{1}{2(2+\\beta^2)}$, which is smaller than the first and the third components in Lemma 3.2 that are linear to $T$. We also numerically validate this point in general response point 2 and attached pdf. Intuitively, this phenomenon is related to lazy training.\n\nFor the special case of linearized networks, there is no second component because the its gradient during training is upper bounded by the network’s gradient at initialization. (See Lemma 4.1 for more details.)\n\n\n> Your Lemma 4.1 looks to exploit a worst-case bound over the layers of the network, plus the property of the ReLU activation. Can you confirm?\n\nNo, Lemma 4.1 is not a worst-case bound over the layers. Instead, it computes the exact expected squared gradient norm at initialization (Lemma C.3). The key insight is that the ratio between the squared norm of gradient at $l+1$-th layer and $l$-th layer follows a Chi-squared distribution multiplied by Bernoulli distribution, thus allowing a recursion equality over the layers. See general response point 1 for more explanations for intuition of this gradient norm bound.\n\n**References**\n\n[a] Generalization properties of NAS under activation and skip connection search. NeurIPS 2022.\n\n[b] Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks?---A Neural Tangent Kernel Perspective. NeurIPS 2020.\n\n[c] Generalization Ability of Wide Residual Networks\n\n[d] On Exact Computation with an Infinitely Wide Neural Net. NeurIPS 2019.\n\n[e] What Can Be Learnt With Wide Convolutional Neural Networks? . ICML 2023.\n"}]

Author rebuttal:
# General response

We’d like to thank the reviewers for their insightful comments. Below we address the shared questions and concerns.

---

**1. Intuition for improving privacy bound**

On the one hand, when depth is fixed, increasing width $m$ always increases the gradient norm and thus harms our KL privacy bound Corollary 4.2., which is consistent with the empirical observations in the literature. On the other hand, if we inverse proportionally set the per-layer initialization variance with the width, and increase the network depth, then the gradient difference norm decreases (thus the KL privacy bound improves). 

To see why this is happening, observe at the analytical computation of gradient with regard to each layer, which scales with the post-activation output at its previous layer. This pre-activation output is weighted sum of outputs from the preceding layer, and is thus proportional to the initialization variance $\beta$ times the number of neurons $m$ in one layer (i.e., the $\beta_im_i$ factor in Lemma 4.1). After that, the Relu activation flattens the gradient to zero with a 1/2 probability, which divides the factor by two to be $\frac{\beta_im_i}{2}$. By a recursive argument over the number of layers (i.e., depth L), we have that when $\frac{\beta_im_i}{2}<1$ (such as under LeCun and Xavier initialization), the gradient norm (and thus the KL privacy bound) decays exponentially with increasing depth. (See Lemma C.3 for detailed derivations.) 

For LeCun initialization, such decrease of gradient norm under increasing depth is not a new phenomenon, and has been widely referred to as  “gradient vanishing” in the literature. A similar phenomenon is also observed in the context of robustness [46].

---

**2. Additional numerical experiments to validate privacy bounds**

**_Numerical estimation procedure._** Theorem 3.1 suggests that KL privacy upper bound scales with the squared gradient norm during training. This could be estimated by empirically average of gradient norm across training runs. We consider training dataset $D$ with 'car' and 'plane' of the CIFAR-10, and all of its neighboring datasets $D'$ that removes a record from $D$, or adds a test record to $D$. We run noisy GD with constant step-size $0.01$ for $50$ epochs on both datasets. .


**_Numerical KL privacy loss validates Lemma 3.2 and Lemma 4.1 for the the growth of KL privacy bound with regard to training time_** Figure 1 of the attached pdf shows numerical KL privacy loss under different initialization distributions, for fully connected networks with width $1024$ and depth $10$. We observe that the KL privacy loss grows linearly at the beginning of training ($<10$ epochs), which validates the first term in the KL privacy bound Lemma 3.2. Moreover, the KL privacy loss under LeCun and Xavier initialization is close to zero at the beginning of training ($<10$ epochs). This shows LeCun and Xavier initialization induce small gradient norm at small training time, which is consistent with our gradient norm bound Lemma 4.1.  However, when the number of epochs is large, the KL privacy loss in Figure 1 grows faster than linear accumulation, thus validating the second term in our KL privacy bound Lemma 3.2 that exponentially grows with training time.


**_Numerical KL privacy loss validates the dependency of KL privacy bounds (Lemma 3.2 and Lemma 4.1) on network width and depth under different initializations_** Figure 2 of the attached pdf show numerical KL privacy loss under different network depth, width and initializations, for a fixed training time. We observe that increasing width and training time always increases KL privacy loss. This is consistent with Lemma 4.1, which shows that increasing width worsens the gradient norm at initialization (given fixed depth), thus harming KL privacy bound Lemma 3.2 at the beginning of training. We also observe that the relationship between KL privacy and network depth depends on the initialization distributions and the training time. Specifically, in Figure 2 (a), when the training time is small (20 epochs), for LeCun and Xavier initializations, the numerical KL privacy loss improves with increasing depth when depth > 8. Meanwhile, when the training time is large (50 epochs) in Figure 2 (b), KL privacy loss worsens with increasing depth throughout all depths. This shows that when the training time is small, the choice of initialization distribution affects the dependency of KL privacy loss on increasing width and depth, thus validating Lemma 3.2 and 4.1.

---

**3. Social impact, Limitations and Future Works**

We thank the reviewers for pointing out several missing discussions. We summarize them below and will add to future revisions.

(1) For DNNs that satisfy a relaxed smoothness condition, our KL privacy bound Lemma 3.2 is dominated by gradient difference at initialization for small training time, while it scales with gradient space rank for large training time. It remains an open problem to compute this bound by estimating the gradient space rank, and to improve it under more relaxed assumptions. 

(2) For the simplified setting of linearized neural networks, we prove analytical privacy utility trade-off that improves with increasing depth under certain initializations, given that the width is large enough. Future works include relaxing the assumptions on width and network. Our results also suggest that the choice of activation function crucially affects how privacy changes with increasing width and depth. It is an an interesting open problem as to whether such conclusions generalize to deep neural networks.

(3) Lastly, our utility analysis focus on excess empirical risk, which is only meaningful when the approximation error is small (which is the case for commonly used initialization distribution). To prove meaningful privacy utility trade-off under arbitrary initialization distributions, future works include a more comprehensive utility analysis in approximation error.


Meta-review: The authors investigate a novel question of how initialization and the structure of neural networks affect the privacy guarantee of DP-SGD. This leads to a surprising finding that privacy bound improves with increasing depth for the LeCun and Xavier initialization while it degrades with increasing depth. The reviewers agree that the findings are interesting and the techniques are novel in the privacy literature.
Decision: Accept (poster)