Initialization Matters: Privacy-Utility Analysis of Overparameterized
  Neural Networks
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.
Jiayuan Ye, Zhenyu Zhu, Fanghui Liu, Reza Shokri, Volkan Cevher
# Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks

###### 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.

## 1 Introduction

Deep neural networks (DNNs) in the over-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 as membership inference attacks [44] and reconstruction attacks [17; 7; 29]. This leakage can be mathematically measured by the extent to which the algorithm's output distribution changes if DNNs are trained on a neighboring dataset (differing only in a one record), following the differential privacy (DP) framework [23].

To train differential private model, a 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 [2]. 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 its 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 over-parameterization of neural networks (under different initializations) affect the privacy bound of the training algorithm over_ worst-case _datasets?_
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. 2 It avoids an artificial setting in DP-SGD [2] where a 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). 3 By proving precise upper bounds on the expected \(\ell_{2}\)-norm of this gradient difference, we thus obtain KL privacy bounds for fully connected neural network (Lemma 3.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 1, and highlight our key observations below.

Footnote 2: 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).

Footnote 3: We focus on KL privacy loss because it is a more relaxed distinguishability notion than standard \((\varepsilon,\delta)\)-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, as studied in recent works [39; 28].

* 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 a 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-parameterization 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 a gradient norm constant \(B\) throughout training (Corollary 6.4). 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 1). To our best knowledge, this is the first time that such a gain in privacy-utility trade-off due to over-parameterization (increasing depth) is shown. Meanwhile, prior results only prove (nearly) dimension-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-utility analysis in understanding the effect of over-parameterization.

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline \multirow{2}{*}{Initialization} & \begin{tabular}{c} Variance \(\beta_{l}\) \\ for layer \(l\) \\ \end{tabular} & \begin{tabular}{c} Gradient norm \\ constant \(B\) (7) \\ \end{tabular} & \begin{tabular}{c} Approximate lazy \\ training distance \\ \(R\) (9) \\ \end{tabular} & 
\begin{tabular}{c} Excess Empirical risk \\ under \(\varepsilon\)-KL privacy \\ (Corollary 6.4) \\ \end{tabular} \\ \hline LeCun [34] & \(1/m_{l-1}\) & \(\frac{\text{\small{\small{\small{\small{\small{\small{\small{\small{\small{ \begin{array}{c}{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{ \tiny }}}}}} \left[{\left[{{\tiny{{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\left}}}}}}}}{{{\tiny{{ \tiny{\tiny{{\tiny{\tiny{\tiny{\tiny{\{\left}}}}}}{{{\tiny{{\tiny{\tiny{\tiny{{ \tiny{\left}}}}}}{{{\tiny{{\tiny{{\tiny{\tiny{\{}}}}}}{{ \tiny{{\tiny{{\tiny{\tiny{\left}}}}}{{{\tiny{{\tiny{\tiny{\tiny{\left}}}}{{{\tiny{{ \tiny{\left}}}}{{{\tiny{{\tiny{\tiny{{\left}}}}{{{\tiny{\tiny{\tiny{{\left}}}}{{{ \tiny{\tiny{\left}}}{{{\tiny{{\tiny{\left}}}}{{{\tiny{{\tiny{\left}}}{{{ \tiny{\tiny{\left}}}{{{\tiny{{\left{\left}}}}{{{\tiny{{\tiny{\left{}}}}{{ \tiny{{\tiny{\left{\left}}}{{{\tiny{\left{{\left}}}}{{{\tiny{{\tiny{\left{{\left}}} }}{{{{\tiny{{\left{\left}}}}{{{\tiny{{\tiny{\left{\left}}}}{{{\tiny{{\left{{ \left}}}}{{{\tiny{{\left{\left}}}{{{\tiny{\left{{\left}}}}{{{ \tiny{{\left{\left{{\left}}}}{{{\tiny{{\left{\left{\left{}}}}{{\tiny{{\left{{ \left}}}}{{{\left{{\left{\left{\left}}}{{{\left{\left{{{}}} {\left{\left{{\left{\left}}}}{{{\left{\left{{\left{}}}}{{\left{{\left{{ }}}}{{\left{\left{{\left{\left{{\left}}}}{{{\left{\left{{{ }}}}{{\left{\left{{\left{\left}}}{{{\left{{{}}} {\left{{\left{\left{\left}}}}{{{\left{{\left{\left{{\left}}}}{{\left{{{{ }}}}{\left{\left{{\left{{\left}}}{{\left{{{{{{{}}}}} {\left{\left{{\left}}}}{{\left{\left{\left{{{{\left}}}}}{{\left{{ \left{{\left{{{\left}}}}}{{\left{\left{\left{{{{\left}}}}{{\left{{{{{{{{{{{}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\}\}\}\}\}\}\}\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\{\{\{\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\}\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\}\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\}\}\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\
### Related Works

over-parameterization in DNNs and NTK.Theoretical demonstration on the benefit of over-parameterization in DNNs occurs in global convergence [3; 21] and generalization [4; 16]. 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, over-parameterization has been demonstrated to be beneficial/harmful to several topics in deep learning, e.g., robustness [15; 54], covariate shift [50]. However, the relationship between over-parameterization 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 [2]) to enforce privacy constraints.

Membership inference privacy risk under over-parameterization.A recent line of works [47; 48] investigates how over-parameterization affects the theoretical and empirical privacy in terms of membership inference advantage, and proves novel trade-off between privacy and generalization error. These literature are closet to our objective of investigating the interplay between privacy and over-parameterization. However, Tan et al. [47; 48] focus on proving upper bounds for an average-case privacy risk defined by the advantage (relative success) of membership inference attack on 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. [47; 48]. The employed analysis tools are accordingly different.

Differentially private learning in high dimensionStandard results for private empirical risk minimization [9; 46] and private stochastic convex optimization [11; 12; 5] 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, it is possible to seek for the dimension-dependency in proving risk bounds for certain class of problems (such as generalized linear model [45]). Recently, there is a growing line of works that proves dimension-independent excess risk bounds for differentially private learning, by utilizing the low-rank structure of data features [45] or gradient matrices [32; 37] during training. Several follow-up works [33; 13] 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 a general high-dimensional problem for private learning, rather than separating the study for different network choices such as 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 over-parameterization.

## 2 Problem and Methodology

We consider the following standard multi-class supervised learning setting. Let \(\mathcal{D}=(\mathbf{z}_{1},\cdots,\mathbf{z}_{n})\) be an input dataset of size \(n\), where each data record \(\mathbf{z}_{i}=(\mathbf{x}_{i},\mathbf{y}_{i})\) contains a \(d\)-dimensional feature vector \(\mathbf{x}_{i}\in\mathbb{R}^{d}\) and a label vector \(\mathbf{y}_{i}\in\mathcal{Y}=\{-1,1\}^{o}\) on \(o\) classes. We aim to learn a neural network output function \(\mathbf{f}_{\mathbf{W}}(\cdot):\mathcal{X}\rightarrow\mathcal{Y}\) parameterized by \(\mathbf{W}\) via empirical risk minimization (ERM)

\[\min_{\mathbf{W}}\mathcal{L}(\mathbf{W};\mathcal{D}):=\frac{1}{n}\sum_{i=1}^{n}\ell( \mathbf{f}_{\mathbf{W}}(\mathbf{x}_{i});\mathbf{y}_{i})\,, \tag{1}\]

where \(\ell(\mathbf{f}_{\mathbf{W}}(\mathbf{x}_{i});\mathbf{y}_{i})\) is a loss function that reflects the approximation quality of model prediction \(f_{\mathbf{W}}(\mathbf{x}_{i})\) compared to the ground truth label \(\mathbf{y}_{i}\). For simplicity, throughout our analysis, we employ the cross-entropy loss \(\ell(\mathbf{f}_{\mathbf{W}}(\mathbf{x});\mathbf{y})=-\langle\mathbf{y},\log\text{softmax}(\mathbf{ f}_{\mathbf{W}}(\mathbf{x}))\rangle\) for multi-class network with \(o\geq 2\), and \(\ell(\mathbf{f}_{\mathbf{W}}(\mathbf{x});\mathbf{y})=\log(1+\exp(-\mathbf{y}\mathbf{f}_{\mathbf{W}}(\mathbf{x}))\) for single-output network with \(o=1\).

Fully Connected Neural NetworksWe consider the \(L\)-layer, multi-output, fully connected, deep neural network (DNN) with ReLU activation. Denote the width of hidden layer \(l\) as \(m_{l}\) for \(l=1,\cdots,L-1\). For consistency, we also denote \(m_{0}=d\) and \(m_{L}=o\). The network output \(f_{\mathbf{W}}(\mathbf{x})\coloneqq\mathbf{h}_{L}(\mathbf{x})\) is defined recursively as follows.

\[\mathbf{h}_{0}(\mathbf{x})=\mathbf{x};\quad\mathbf{h}_{l}(\mathbf{x})=\phi(\mathbf{W}_{l}\mathbf{x})\text{ for }l=1,\cdots,L-1;\quad\mathbf{h}_{L}(\mathbf{x})=\mathbf{W}_{L}\mathbf{h}_{L-1}(\mathbf{x})\,, \tag{2}\]
where \(h_{l}(\mathbf{x})\) denotes the post-activation output at \(l\)-th layer, and \(\{\mathbf{W}_{l}\in\mathbb{R}^{m_{l}\times m_{l-1}}:l=1,\ldots,L\}\) denotes the set of per-layer weight matrices of DNN. For brevity, we denote the vector \(\mathbf{W}\coloneqq(\text{Vec}(\mathbf{W}_{1}),\ldots,\text{Vec}(\mathbf{W}_{L}))\in \mathbb{R}^{m_{1}\cdot d+m_{2}\cdot m_{1}+\cdots+o\cdot m_{L-1}}\), i.e., the the concatenation of vectorizations for weight matrices of all layers, as the model parameter.

Linearized NetworkWe also analyze the following _linearized network_, which is used in prior works [35, 3, 41] as an important tool to (approximately and qualitatively) analyze the training dynamics of DNNs. Formally, the linearized network \(\mathbf{f}_{\mathbf{W}}^{lin,0}(\mathbf{x})\) is a first-order Taylor expansion of the fully connected ReLU network at initialization parameter \(\mathbf{W}_{0}^{lin}\), as follows.

\[\mathbf{f}_{\mathbf{W}}^{lin,0}(\mathbf{x})\equiv\mathbf{f}_{\mathbf{W}_{0}^{lin}}(\mathbf{x})+\frac{ \partial\mathbf{f}_{\mathbf{W}}(\mathbf{x})}{\partial\mathbf{W}}\Big{|}_{\mathbf{W}=\mathbf{W}_{0}^{ lin}}\left(\mathbf{W}-\mathbf{W}_{0}^{lin}\right), \tag{3}\]

where \(\mathbf{f}_{\mathbf{W}_{0}^{lin}}(\mathbf{x})\) is the output function of the fully connected ReLU network (2) at initialization \(\mathbf{W}_{0}^{lin}\). We denote \(\mathcal{L}_{0}^{lin}(\mathbf{W};\mathcal{D})=\frac{1}{n}\sum_{i=1}^{n}\ell\left( \mathbf{f}_{\mathbf{W}_{0}^{lin}}(\mathbf{x}_{i})+\frac{\partial\mathbf{f}_{\mathbf{W}}(\mathbf{x})}{ \partial\mathbf{W}}|_{\mathbf{W}=\mathbf{W}_{0}^{lin}}(\mathbf{W}-\mathbf{W}_{0}^{lin});\mathbf{y}_{i}\right)\) as the empirical loss function for training linearized network, by plugging (3) into (1).

Langevin DiffusionRegarding the optimization algorithm, we focus on the _Langevin diffusion_ algorithm [36] with per-dimensional noise variance \(\sigma^{2}\). Note that we aim to _avoid gradient clipping_ while still proving KL privacy bounds. After initializing the model parameters \(\mathbf{W}_{0}\) at time zero, the model parameters \(\mathbf{W}_{t}\) at subsequent time \(t\) evolves as the following stochastic differential equation.

\[\mathrm{d}\mathbf{W}_{t}=-\,\nabla\mathcal{L}(\mathbf{W}_{t};\mathcal{D})\mathrm{d}t+ \sqrt{2\sigma^{2}}\mathrm{d}\mathbf{B}_{t}\,. \tag{4}\]

Initialization DistributionThe initialization of parameters \(\mathbf{W}_{0}\) crucially affects the convergence of 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 \(l=1,\cdots,L\), we have

\[[\mathbf{W}^{l}]_{ij}\sim\mathcal{N}(0,\beta_{l})\text{, for }(i,j)\in[m_{l}]\times[m_{l-1}]\,, \tag{5}\]

where \(\beta_{1},\cdots,\beta_{L}>0\) are the per-layer variance for Gaussian initialization. By choosing different variances, we recover many common initialization schemes in the literature, as summarized in Table 1.

### Our objective and methodology

We aim to understand the relation between privacy, utility and over-parameterization (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 \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) as neighboring datasets if they are of same size and only differ in one record. For brevity, we also denote the differing records as \((\mathbf{x},\mathbf{y})\in\mathcal{D}\) and \((\mathbf{x}^{\prime},\mathbf{y}^{\prime})\in\mathcal{D}^{\prime}\).

**Assumption 2.2** (Bounded Data).: For simplicity, we assume bounded data, i.e., \(\|\mathbf{x}\|_{2}\leq\sqrt{d}\).

We now give the definition for KL privacy, which is a more relaxed, yet closely connected privacy notion to the standard \((\varepsilon,\delta)\) differential privacy [22], see Appendix A.2 for more discussions. KL privacy and its relaxed variants are commonly used in previous literature [8, 10, 53].

**Definition 2.3** (KL privacy).: A randomized algorithm \(\mathcal{A}\) satisfies \(\varepsilon\)-KL privacy if for any neighboring datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\), we have that the KL divergence \(\mathrm{KL}(\mathcal{A}(\mathcal{D})\|\mathcal{A}(\mathcal{D}^{\prime}))\leq\varepsilon\), where \(\mathcal{A}(\mathcal{D})\) denotes the algorithm's output distribution on dataset \(\mathcal{D}\).

In this paper, we prove KL privacy upper bound for \(\max_{\mathcal{D},\mathcal{D}^{\prime}}\mathrm{KL}(\mathbf{W}_{[0:T]}\|\mathbf{W}_{[0:T]} ^{\prime})\) when running Langevin diffusion on any _worst-case_ neighboring datasets. For brevity, here (and in the remaining paper), we abuse the notations and denote \(\mathbf{W}_{[0:T]}\) and \(\mathbf{W}_{[0:T]}^{\prime}\) as the distributions of model parameters trajectory during Langevin diffusion processes Eq. (4) with time \(T\) on \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) respectively.

For utility analysis, we prove the upper bound for the excess empirical risk given any fixed KL divergence 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** ([40; 20; 21]).: The training data \(\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\) are i.i.d. samples from a distribution \(P_{x}\) that satisfies \(\mathbb{E}[\mathbf{x}]=0,\|\mathbf{x}\|_{2}=\sqrt{d}\) for \(\mathbf{x}\sim P_{x}\), and with probability one for any \(i\neq j\), \(\mathbf{x}_{i}\nparallel\mathbf{x}_{j}\).

Our ultimate goal is to precisely understand how the excess empirical risk bounds (given a 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-based 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 \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\).

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 clipping).

**Theorem 3.1** (KL composition under possibly unbounded gradient difference).: _The KL divergence between running Langevin diffusion (4) for DNN (2) on neighboring datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) satisfies_

\[\mathrm{KL}(\mathbf{W}_{[0:T]}\|\mathbf{W}_{[0:T]}^{\prime})=\frac{1}{2\sigma^{2}} \int_{0}^{T}\mathbb{E}\left[\|\nabla\mathcal{L}(\mathbf{W}_{t};\mathcal{D})- \nabla\mathcal{L}(\mathbf{W}_{t};\mathcal{D}^{\prime})\|_{2}^{2}\right]\mathrm{d}t\,. \tag{6}\]

Proof sketch.: We compute the partial derivative of KL divergence with regard to time \(t\), and then integrate it over \(t\in[0,T]\) to compute the KL divergence during training with time \(T\). For computing the limit of differentiation, we use Girsanov's theorem to compute the KL divergence between the trajectory of Langevin diffusion processes on \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\). The complete proof is in Appendix B.1.

Theorem 3.1 is an extension of the standard additivity [51] of KL divergence (also known as chain rule [1]) for a finite sequence of distributions to continuous time processes with (possibly) unbounded drift difference. The key extension is that Theorem 3.1 does not require bounded sensitivity between the drifts of Langevin Diffusion on neighboring datasets. Instead, it only requires finite second-order moment of drift difference (in the \(\ell_{2}\)-norm sense) between neighboring datasets \(\mathcal{D},\mathcal{D}^{\prime}\), 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 \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\).

**Lemma 3.2** (Drift Difference in Noisy Training).: _Let \(M_{T}\) be the subspace spanned by gradients \(\{\nabla\ell(f_{\mathbf{W}_{t}}(\mathbf{x}_{i};\mathbf{y}_{i}):(\mathbf{x}_{i},\mathbf{y}_{i})\in \mathcal{D},t\in[0,T]\}_{i=1}^{n}\) throughout Langevin diffusion \((\mathbf{W}_{t})_{t\in[0,T]}\). Denote \(\|\cdot\|_{M_{T}}\) as the \(\ell_{2}\) norm of the projected input vector onto \(M_{T}\). Suppose that there exists constants \(c,\beta>0\) such that for any \(\mathbf{W}\), \(\mathbf{W}^{\prime}\) and \((\mathbf{x},\mathbf{y})\), we have \(\|\nabla\ell(f_{\mathbf{W}}(\mathbf{x});\mathbf{y})\rangle-\nabla\ell(f_{\mathbf{W}^{\prime}} (\mathbf{x});\mathbf{y})\|_{2}<\max\{c,\beta\|\mathbf{W}-\mathbf{W}^{\prime}\|_{M_{T}}\}\). Then running Langevin diffusion Eq. (4) with Gaussian initialization distribution (5) satisfies \(\varepsilon\)-KL privacy with \(\varepsilon=\frac{\max_{\mathcal{D},\mathcal{D}^{\prime}}\int_{0}^{T}\mathbb{ E}\left[\|\nabla\mathcal{L}(\mathbf{W}_{t};\mathcal{D})-\nabla\mathcal{L}(\mathbf{W}_{t}; \mathcal{D}^{\prime})\|_{2}^{2}\right]\mathrm{d}t}{2\sigma^{2}}\) where_

\[+\underbrace{\frac{2\beta^{2}}{n^{2}(2+\beta^{2})}\left(\frac{ \epsilon^{(2+\beta^{2})T}-1}{2+\beta^{2}}-T\right)\cdot\left(\mathbb{E}\left[ \|\nabla\mathcal{L}(\mathbf{W}_{0};\mathcal{D})\|_{2}^{2}\right]+2\sigma^{2} \text{rank}(M_{T})+c^{2}\right)}_{\text{gradient difference fluctuation during training}}+\underbrace{\frac{2c^{2}T}{n^{2}}}_{\text{non- smoothness}}.\]

Proof sketch.: The key is to reduce the problem of upper bounding the gradient difference at any training time \(T\), to analyzing its two subcomponents: \(\|\nabla\ell(f_{\mathbf{W}_{t}}(\mathbf{x});\mathbf{y}))-\nabla\ell(f_{\mathbf{W}_{t}}(\mathbf{x}^{\prime});\mathbf{y}^{\prime}) \|_{2}^{2}\leq\underbrace{2\left\|\nabla\ell(f_{\mathbf{W}_{0}}(\mathbf{x});\mathbf{y}) \right\|-\nabla\ell(f_{\mathbf{W}_{0}}(\mathbf{x}^{\prime});\mathbf{y}^{\prime})\right\|_ {2}^{2}}_{\text{gradient difference at initialization}}+2\beta^{2}\underbrace{\left\|\mathbf{W}_{t}- \mathbf{W}_{0}\right\|_{M_{T}}^{2}}_{\text{parameters' change after time $T$}}+2c^{2}\), where \((\mathbf{x},\mathbf{y})\) and \((\mathbf{x}^{\prime},\mathbf{y}^{\prime})\) are the differing data between neighboring datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\). This inequality is by the Cauchy-Schwartz inequality. In this way, the second term in Lemma 3.2 uses the change of parameters
to bound the gradient difference between datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) at time \(T\), via the relaxed smoothness assumption of loss function (that is explained in Remark 3.5 in details). The complete proof is in Appendix B.2.

_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 \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) 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 a subspace \(M_{T}\) spanned by gradients of all training data. Intuitively, this fluctuation is because Langevin diffusion adds per-dimensional noise with variance \(\sigma^{2}\), thus perturbing the training parameters away from the initialization at a scale of \(O(\sigma\sqrt{\text{rank}(M_{T})})\) in the expected \(\ell_{2}\) distance.

_Remark 3.5_ (Relaxed smoothness of loss function).: The third term in Lemma 3.2 is due to the assumption \(\|\nabla\ell(f_{\mathbf{W}}(\mathbf{x});\mathbf{y})\|_{2}<\max\{c,\beta\|\mathbf{W}-\mathbf{W}^{ \prime}\|_{M_{T}}\}.\) This assumption is similar to smoothness of loss function, but is more relaxed as it allows non-smoothness at 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.

_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\to 0\), the second component in Lemma 3.2 contains a small factor \(\frac{e^{(2+\beta^{2})T}-1}{2+\beta^{2}}-T=o(T)\) by Taylor 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 a fixed training time \(T\) and noise scale \(\sigma^{2}\), Lemma 3.2 predicts that the KL divergence upper bound in Theorem 3.1 is dependent on the gradient difference and gradient norm at initialization, and the rank of gradient subspace \(\text{rank}(M_{T})\) throughout training. We now discuss the how these two terms change under increasing width and depth, and whether there are possibilities to improve them under over-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 KL privacy bound) by using specific initialization schemes, as we later show in Section 4 and Section 5.
2. Regarding the rank of gradient subspace \(\text{rank}(M_{T})\): when the gradients along the training trajectory span the whole optimization space, \(\text{rank}(M_{T})\) 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 (over-parameterization) in the worst-case. However, if the gradients are low-dimensional [45; 32; 43] or sparse [37], \(\text{rank}(M_{T})\) 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-parameterization

In this section, we focus on the training of linearized networks (3), which fosters a refined analysis on the interplay between KL privacy and over-parameterization (increasing width and depth). Analysis of DNNs via linearization is a 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 over-parameterization and privacy.

To derive a composition-based KL privacy bound for training a linearized network, we apply Theorem 3.1 which requires an upper bound for the norm of gradient difference between the training
processes on neighboring datasets \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) at any time \(t\). Note that the empirical risk function for training linearized models enjoys convexity, and thus a 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 a 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 \(t\in[0,T]\), running Langevin diffusion on a linearized network in Eq. (3) satisfies that_

\[\mathbb{E}\left[\|\nabla\mathcal{L}(\mathbf{W}_{t}^{lin};\mathcal{D})-\mathcal{ L}(\mathbf{W}_{t}^{lin};\mathcal{D}^{\prime})\|_{2}^{2}\right]\leq\frac{4B}{n^{2}} \,,\text{ where }B\coloneqq d\cdot o\cdot\left(\prod_{i=1}^{L-1}\frac{\beta_{i}m_{i}}{2} \right)\sum_{l=1}^{L}\frac{\beta_{L}}{\beta_{l}}\,, \tag{7}\]

_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 \(\{m_{i}\}_{i=1}^{L}\), and the per-layer variances \(\{\beta_{i}\}_{i=1}^{L}\) 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 network with Gaussian weight matrices. Our proof borrows some techniques from [3, 54] for computing the gradient distribution, refer to Appendix C.1 and C.2 for the full proofs. By plugging Eq. (7) into Theorem 3.1, 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 and neural networks (3) initialized by Gaussian distribution with per-layer variance \(\{\beta_{i}\}_{i=1}^{L}\), running Langevin diffusion for linearized network with time \(T\) on any neighboring datasets satisfies that_

\[\mathrm{KL}(\mathbf{W}_{[0:T]}^{lin}\|\mathbf{W}_{[0:T]}^{lin})\leq\frac{2BT}{n^{2} \sigma^{2}}\,, \tag{8}\]

_where \(B\) is the constant that specifies the gradient norm upper bound, given by Eq. (7)._

Over-parameterization affects privacy differently under different initialization.Corollary 4.2 and Theorem 4.1 prove the role of over-parameterization in our KL privacy bound, crucially depending on how the per-layer Gaussian initialization variance \(\beta_{i}\) scales with the per-layer network width \(m_{i}\) and depth \(L\). We summarize our KL privacy bound for the linearized network under different width, depth and initialization schemes in Table 1, and elaborate the comparison below.

**(1) LeCun initialization** uses small, width-independent variance for initializing the first layer \(\beta_{1}=\frac{1}{d}\) (where \(d\) is the number of input features), and width-dependent variance \(\beta_{2}=\cdots=\beta_{L}=\frac{1}{m}\) for initializing all the subsequent layers. Therefore, the second term \(\sum_{l=1}^{L}\frac{\beta_{L}}{\beta_{l}}\) in the constant \(B\) of Eq. (7) increases linearly with the width \(m\) and depth \(L\). However, due to \(\frac{m_{l}\cdot\beta_{l}}{2}<1\) for all \(l=2,\cdots,L\), the first product term \(\prod_{l=1}^{L-1}\frac{\beta_{l}m_{l}}{2}\) 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**\(\beta_{l}=\frac{\mathcal{Z}}{m_{l-1}+m_{l}}\), we prove that the KL privacy bound (especially the constant \(B\) (7)) improves with increasing depth as long as the depth is large enough.

**(2) NTK and He initializations** use large per-layer variance \(\beta_{l}=\begin{cases}\frac{2}{m_{l}}&l=1,\cdots,L-1\\ \frac{1}{o}&l=L\end{cases}\) (for NTK) and \(\beta_{l}=\frac{2}{m_{l-1}}\) (for He). Consequently, the gradient difference under NTK or He initialization is 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.

## 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), we perform experiments for
DNNs training via noisy GD to numerically estimate the KL privacy loss. We will show that if the total training time is small, it is indeed possible to 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 \(\mathcal{D}\), we consider all 'car' and 'plane' images of the CIFAR-10. For neighboring dataset, we consider all possible \(\mathcal{D}^{\prime}\) that removes a record from \(\mathcal{D}\), or adds a test record to \(\mathcal{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.

_Numerically validate the growth of KL privacy loss with regard to training time_. Figure 1 shows numerical KL privacy 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. However, 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.

_Numerically validate the dependency of KL privacy loss on network width, depth and initializations_. Figure 2 shows the numerical KL privacy loss under different network depth, width and initializations, for a fixed training time. In Figure 1(c), we 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 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

Figure 1: Numerically estimated KL privacy loss for noisy GD with constant 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, taking worst-case over all neighboring datasets. The numerical KL privacy loss grows with the number of training epochs under all initializations. The growth rate is close to linear at beginning of training (epochs \(<10\)) and is faster than linear at epochs \(\geq 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 \(6\) training runs, taking worst-case over all neighboring datasets. Under increasing width, the KL privacy loss always grows under all evaluated initializations. Under increasing depth, at the beginning of training (20 epochs), the KL privacy loss worsens with depth under He initialization, but first worsens with depth (\(\leq 8\)) and then improves with depth (\(\geq 8\)) under Xavier and LeCun initializations. At later phases of the training (50 epochs), KL privacy worsens (increases) with depth under all evaluated initializations.
and network depth depends on the initialization distributions and the training time. Specifically, in Figure (a)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 (b)b, KL privacy loss worsens with increasing depth under all initializations. 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.

## 6 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-parameterization 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 privacy-preserving initialization schemes.

Convergence of training linearized networkWe 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 over-parameterization. The proof is deferred to Appendix D.1.

**Lemma 6.1** (Extension of [42, Theorem 2] and [45, Theorem 3.1]).: _Let \(\mathcal{L}_{0}^{lin}(\mathbf{W};\mathcal{D})\) be the empirical risk function of a linearized network in Eq. (3) expanded at initialization vector \(\mathbf{W}_{0}^{lin}\). Let \(\mathbf{W}_{0}^{*}\) be an \(\alpha\)-near-optimal solution for the ERM problem such that \(\mathcal{L}_{0}^{lin}(\mathbf{W}_{0}^{*};\mathcal{D})-\min_{\mathbf{W}}\mathcal{L}_{0 }^{lin}(\mathbf{W};\mathcal{D})\leq\alpha\). Let \(\mathcal{D}=\{\mathbf{x}_{i}\}_{i=1}^{n}\) be an arbitrary training dataset of size \(n\), and denote \(M_{0}=\left(\nabla f_{\mathbf{W}_{0}^{lin}}(\mathbf{x}_{1}),\cdots,\nabla f_{\mathbf{W}_{0 }^{lin}}(\mathbf{x}_{n})\right)^{\top}\) as the NTK feature matrix at initialization. Then running Langevin diffusion (4) on \(\mathcal{L}_{0}^{lin}(\mathbf{W})\) with time \(T\) and initialization vector \(\mathbf{W}_{0}^{lin}\) satisfies_

\[\mathbb{E}[\mathcal{L}_{0}^{lin}(\tilde{\mathbf{W}}_{T}^{lin})]-\min_{\mathbf{W}} \mathcal{L}_{0}^{lin}(\mathbf{W};\mathcal{D})\leq\alpha+\frac{R}{2T}+\frac{1}{2} \sigma^{2}rank(M_{0})\,,\]

_where the expectation is over Brownian motion \(B_{T}\) in Langevin diffusion in Eq. (4), \(\bar{\mathbf{W}}_{T}^{lin}=\frac{1}{T}\int\tilde{\mathbf{W}}_{t}^{lin}\mathrm{d}t\) is the average of all iterates, and \(R=\|\mathbf{W}_{0}^{lin}-\mathbf{W}_{0}^{*}\|_{M_{0}}^{2}\) is the gap between initialization parameters \(\mathbf{W}_{0}^{lin}\) and solution \(\mathbf{W}_{0}^{*}\)._

Remark 6.2.: The excess empirical risk bound in Lemma 6.1 is smaller if data is low-rank, e.g., image data, then \(\text{rank}(M_{0})\) is small. This is consistent with the prior dimension-independent private learning literature [32, 33, 37] and shows the benefit of low-dimensional gradients on private learning.

Lemma 6.1 highlights that the excess empirical risk scales with the gap \(R\) 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 \(\sigma^{2}\). We have discussed how over-parameterization affects the gradient norm constant \(B\) and the gradient subspace rank \(\text{rank}(M_{0})\) 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-parameterizationIt 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 \(\ell_{2}\) 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 [40].

**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 \(m_{0},\cdots,m_{L}=\tilde{\Omega}(n)\) are large. Let \(\mathcal{L}_{0}^{lin}(\mathbf{W})\) be the empirical risk Eq. (1) for
linearized network expanded at initialization vector \(\mathbf{W}_{0}^{lin}\). Then for any \(\mathbf{W}_{0}^{lin}\), there exists a corresponding solution \(\mathbf{W}_{0}^{\frac{1}{n^{2}}}\), s.t. \(\mathcal{L}_{0}^{lin}(\mathbf{W}_{0}^{\frac{1}{n^{2}}})-\min_{\mathbf{W}}\mathcal{L}_{0 }^{lin}(\mathbf{W};\mathcal{D})\leq\frac{1}{n^{2}}\), \(\text{rank}(M_{0})=n\) and_

\[R\leq\tilde{\mathcal{O}}\left(\max\left\{\frac{1}{d\beta_{L}\left(\prod_{i=1} ^{L-1}\beta_{i}m_{i}\right)},1\right\}\frac{n}{\sum_{l=1}^{L}\beta_{l}^{-1}} \right)\,, \tag{9}\]

_with high probability over training data sampling and random initialization Eq. (5), where \(\tilde{\mathcal{O}}\) ignores logarithmic factors with regard to \(n\), \(m\), \(L\), and tail probability \(\delta\)._

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 1. 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 4 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 for \(\sigma^{2}=\frac{2BT}{\varepsilon n^{2}}\) and \(T=\sqrt{\frac{\varepsilon nR}{2B}}\), releasing all iterates of Langevin diffusion with time \(T\) satisfies \(\varepsilon\)-KL privacy, and has empirical excess risk upper bounded by_

\[\mathbb{E}[\mathcal{L}_{0}^{lin}(\bar{\mathbf{W}}_{T}^{lin})] -\min_{\mathbf{W}}\mathcal{L}_{0}^{lin}(\mathbf{W};\mathcal{D})\leq \tilde{\mathcal{O}}\left(\frac{1}{n^{2}}+\sqrt{\frac{BR}{\varepsilon n}}\right) \tag{10}\] \[=\tilde{\mathcal{O}}\left(\frac{1}{n^{2}}+\sqrt{\frac{\max\{1,d \beta_{L}\prod_{l=1}^{L-1}\beta_{l}m_{l}\}}{2^{L-1}\varepsilon}}\right) \tag{11}\]

_with high probability over random initialization Eq. (5), where the expectation is over Brownian motion \(B_{T}\) in Langevin diffusion, and \(\tilde{O}\) ignores logarithmic factors with regard to width \(m\), depth \(L\), number of training data \(n\) and tail probability \(\delta\)._

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 \(\varepsilon\), thus contributing to a 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 on network width, depth and initialization distributions, and we prove privacy utility trade-offs for training linearized network under commonly used initialization distributions, as summarized in Table 1.

We would like to highlight that our privacy utility trade-off bound under LeCun and Xavier initialization 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-parameterization is shown in literature. This shows the benefits of precisely bounding the gradient norm (Appendix C.1) in our privacy and utility analysis.

## 7 Conclusion

We prove new KL privacy bound for training fully connected ReLU 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 over-parameterization (width and depth) that crucially relies on what initialization distribution is 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 it as an important open problem as to whether our privacy utility trade-off results for linearized network could be generalized to deep neural networks.
## 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_205011, Google PDPO faculty research award, Intel within the www.private-ai.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.
