# Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization
Guarantees

Haotian Ju‡ Dongyue Li‡ Hongyang R. Zhang‡

Northeastern University, Boston

###### Abstract

We consider transfer learning approaches that fine-tune a pretrained deep
neural network on a target task. We study the generalization properties of
fine-tuning to understand the problem of overfitting, which commonly occurs in
practice. Previous works have shown that constraining the distance from the
initialization of fine-tuning improves generalization. Using a PAC-Bayesian
analysis, we observe that besides distance from initialization, Hessians
affect generalization through the noise stability of deep neural networks
against noise injections. Motivated by the observation, we develop Hessian
distance-based generalization bounds for a wide range of fine-tuning methods.
Additionally, we study the robustness of fine-tuning in the presence of noisy
labels. We design an algorithm incorporating consistent losses and distance-
based regularization for fine-tuning, along with a generalization error
guarantee under class conditional independent noise in the training set
labels. We perform a detailed empirical study of our algorithm on various
noisy environments and architectures. On six image classification tasks whose
training labels are generated with programmatic labeling, we find a 3.26%
accuracy gain over prior fine-tuning methods. Meanwhile, the Hessian distance
measure of the fine-tuned model decreases by six times more than existing
approaches.

##  1 Introduction

Fine-tuning a large pretrained model is a common approach to performing
transfer learning. As foundation models become readily available, fine-tuning
these large models is an effective adaptation strategy in many settings. While
this approach improves upon supervised learning in various cases [108],
overfitting has also been observed during fine-tuning [78]. Understanding the
cause of overfitting is challenging since dissecting the issue in practice
requires a precise measurement of generalization errors for deep neural
networks. In this work, we analyze the generalization error of fine-tuned deep
models using PAC-Bayes analysis and data-dependent measurements based on
deepnet Hessians. Based on the analysis, we design an algorithm to improve the
robustness of fine-tuning with limited and noisy labels.

There is a large body of work concerning generalization in deep neural
networks, whereas less is understood in transfer learning and fine-tuning
[104]. A central result of the recent literature shows norm or margin bounds
that improve over classical capacity bounds [79, 87]. These results can be
applied to the fine-tuning setting, following a distance from the
initialization perspective [93, 101]. [119] and [122] show generalization
bounds depending on various norms between fine-tuned and initialization
models. These results highlight that distance from initialization crucially
affects generalization for fine-tuning and informs the design of distance-
based regularization to mitigate overfitting due to fine-tuning a large model
on a small training set.

Our motivating observation is that in addition to distance from
initialization, Hessians crucially affect generalization. We follow the PAC-
Bayesian analysis approach of [87] and [85]. Previous work has identified
noise stability properties of deep networks that require Lipschitzness of the
activation mappings. We propose to quantify the stability of a deep model
against noise perturbations using Hessians. This is a practical approach as
computational frameworks for deepnet Hessians have been developed [114]. We
show that incorporating Hessians into the distance-based measure accurately
correlates with the generalization error of fine-tuning. See Figure 1 for an
illustration.

Figure 1: By incorporating Hessians with distance from initialization, the
Hessian distance measure better correlates with the generalization error of
fine-tuned models.

Method | Generalization error bound
---|---
Fine-tuning | $\frac{\sum_{i=1}^{L}\sqrt{v_{i}^{\top}\mathbf{H}_{i}^{+}v_{i}}}{\sqrt{n}}$
Distance-based Reg. | $\frac{\sum_{i=1}^{L}\sqrt{\operatorname{Tr}\left[\mathbf{H}_{i}^{+}\right]\cdot\|v_{i}\|^{2}}}{\sqrt{n}}$
Consistent loss w/ Reg. | $\frac{\sum_{i=1}^{L}\sqrt{\left\|(F^{-1})^{\top}\right\|_{1,\infty}\cdot\left\lvert\operatorname{Tr}\left[\mathbf{H}_{i}\right]\right\rvert\cdot\|v_{i}\|^{2}}}{\sqrt{n}}$

Table 1: Summary of theoretical results: Our results require computing
Hessians from the data, which can be done with existing Hessian-vector product
libraries. See Section 2.1 for the definition of the notations.

##### Results.

Our theoretical contribution is to develop generalization bounds for fine-
tuned multilayer feedforward networks using Hessians. Our result applies to a
wide range of fine-tuning approaches, including vanilla fine-tuning with or
without early stopping, distance-based regularization, and fine-tuning with
weighted losses. To describe the result, we introduce a few notations. Let
$f_{W}$ be an $L$ layer feedforward neural network with weight matrices
$W_{i}$ for every $i$ from $1$ to $L$. Given a pretrained initialization
$f_{W^{(s)}}$ with weight matrices $W^{(s)}_{1},\dots,W^{(s)}_{L}$, let
$v_{i}$ be a flatten vector of $W_{i}-{W}_{i}^{(s)}$. For every $i=1,\dots,L$,
let $\mathbf{H}_{i}$ be the loss Hessian over $W_{i}$. For technical reasons,
denote $\mathbf{H}_{i}^{+}$ as a truncation of $\mathbf{H}_{i}$ with only
nonnegative eigenvalues. We prove that on a training dataset of size $n$
sampled from a distribution $\mathcal{D}$, with probability at least $0.99$,
the generalization error of a fine-tuned $L$-layer network $f_{W}$ scales as:

$\displaystyle\mathcal{\textup{O}}\left(\sum_{i=1}^{L}\sqrt{\frac{{\max_{(x,y)\sim\mathcal{D}}v_{i}^{\top}{\mathbf{H}_{i}^{+}[\ell(f_{W}(x),y)]}v_{i}}}{n}}\right).$
(1)

See Theorem 2.1 for the complete statement. Based on this result, one can
derive a generalization bound for distance-based regularization of fine-
tuning, assuming constraints on the norm of $v_{i}$ for every $i$.

Next, we study fine-tuning given noisy labels within a class conditional
independent noise setting [75]. Given training labels independently flipped
with some probability according to a confusion matrix $F$, we extend our
result to this setting by incorporating a statistically-consistent loss. Table
1 summarizes the theoretical results. Compared with the proof technique of
[85], our proof involves a perturbation analysis of the loss Hessian, which
may be of independent interest.

Our analysis leads to the design of a new algorithm, which incorporates
statistically-consistent losses with distance-based regularization for
improving the robustness of fine-tuning. We evaluate this algorithm on various
tasks. First, under class-conditional label noise, our algorithm performs
robustly compared to the baselines, even when the noise rate is as high as
60%. Second, on six image classification tasks whose labels are generated by
programmatic labeling [124], our approach improves the prediction accuracy of
fine-tuned models by 3.26% on average compared to existing fine-tuning
approaches. Third, for various settings, including fine-tuning vision
transformers and language models, we observe similar benefits from applying
our approach. In ablation studies, we find that the strong regularization used
in the method reduces the Hessian distance measure more than six times
compared with several fine-tuning methods.

###  1.1 Related work

A well-known article by [84] finds that modern deepnets have the capacity to
fit random labels, suggesting that they are overparametrized; see also [120]
and [115]. Norm and margin bounds are since then proposed for deepnets [79,
87]. These results improve upon classical capacity notions such as the VC
dimension of neural networks, which scales with the number of parameters of
the network [89]. For instance, [94] find that (path) norm bounds consistently
correlate with empirical generalization loss for overparametrized networks.

Recent work finds that generalization measures need to be data-dependent to
better capture the empirical generalization properties of deepnets [109, 98].
Geometric measures such as sharpness have been shown to correlate with
empirical performance [118, 107]. Several studies consider numerically
optimizing the prior, and the posterior of the PAC-Bayes bound [80, 128]. To
our knowledge, provable generalization bounds that capture geometric notions
such as sharpness have not been developed. We note that the Hessian-based
measure differs from the sharpness-based measure of [118] since the Hessian
measures average perturbation, whereas sharpness measures worst-case
perturbation. Compared with existing generalization bounds, our techniques
require Lipshictz-continuity of second-order gradients. Our experiments with
numerous datasets and architectures suggest that Hessians are practical tools
for measuring generalization in deep neural networks.

Next, we discuss related approaches for studying transfer learning from a
theoretical perspective. The work of [73] and the earlier work of [69, 71, 72]
derive generalization bounds for learning from multiple sources. Recent works
explore new theoretical frameworks and techniques to explain transfer,
including transfer exponent [92], task diversity [106], random matrix theory
[126, 110], and minimax estimators [121]. [125] consider a deep linear network
and the impact of the similarity between the source (on which a model is
pretrained) and target domains on transfer.

Our approach is to use PAC-Bayesian bounds for fine-tuned models [67]. Early
works apply PAC-Bayes bounds to analyze generalization in model averaging [66]
and co-training [68]. Recent work has applied this approach to analyze
generalization in deep networks [87, 85, 86]. Besides, the PAC-Bayesian
analysis has been used to derive the generalization loss of graph neural
networks [123], and data augmentation [116]. We refer the readers to a recent
survey for additional references [91].

There is a significant body of work about learning with noisy labels, leaving
a comprehensive discussion beyond the current scope. Some related works
include the design of robust losses [76], the estimation of the confusion
matrix [82, 113, 127], the implicit regularization of early stopping [99, 70],
and label smoothing [102]. The work most related to ours within this
literature is [75], which provides Rademacher complexity-based learning bounds
under class conditional label noise. Our work builds on this work and expands
their result in two aspects. First, our bounds are derived using the PAC-
Bayesian analysis, and the bounds depend on the data through the Hessian
matrix. Second, we consider deep neural networks as the hypothesis class. Our
experimental results highlight the importance of explicit regularization for
improving generalization given limited and noisy labels.

##### Organization.

The rest of this paper is organized as follows. In Section 2, we first define
the problem setup formally. Then, we present our main result following a
Heassian-based PAC-Bayes analysis. In Section 3, we present experiments to
validate our proposed algorithm. In Section 4, we summarize our contributions
and discuss several open questions for future work. We provide the complete
proofs for our results in Appendix A. Lastly, we fill in missing experiment
details in Appendix B.

##  2 Hessian-based Generalization for Fine-tuned Models

This section presents our approach to understanding generalization in fine-
tuning. After setting up the problem formally, we present PAC-Bayesian bounds
for vanilla fine-tuning and distance-based regularization. Then, we extend the
results for fine-tuning from noisy labels by incorporating a statistically-
consistent loss. Lastly, we overview the proof techniques behind our main
result.

###  2.1 Problem setup

Consider predicting a target task given a training dataset of size $n$. Denote
the feature vectors and labels as $x_{i}$ and $y_{i}$, for $i=1,\dots,n$, in
which $x_{i}$ is $d$-dimensional and $y_{i}$ is a class label between $1$ to
$k$. Assume that the training examples are drawn independently from an unknown
distribution $\mathcal{D}$. Let $\mathcal{X}$ be the support set of the
feature vectors of $\mathcal{D}$.

Given a pretrained $L$-layer feedforward network with weight matrices
$\hat{W}^{(s)}_{i}$, for $i=1,\dots,L$, we fine-tune the weights to solve the
target task. Let $f_{W}$ be an $L$-layer network initialized with
$\hat{W}^{(s)}$. The dimension of layer $i$, $W_{i}$, is $d_{i}$ by $d_{i-1}$.
Let $d_{i}$ be the output dimension of layer $i$. Thus, $d_{0}$ is equal to
the input dimension $d$, and $d_{L}$ is equal to the output dimension $k$. Let
$\phi_{i}(\cdot)$ be the activation function of layer $i$. Given a feature
vector $x\in\mathcal{X}$, the output of $f_{W}$ is

$\displaystyle
f_{W}(x)=\phi_{L}\left(W_{L}\cdot\phi_{L-1}\Big{(}W_{L-1}\cdots\phi_{1}\big{(}W_{1}\cdot
x\big{)}\Big{)}\right).$ (2)

Given a loss function $\ell:{}^{k}\times\\{1,\dots,k\\}\rightarrow\real$, let
$\ell(f_{W}(x),y)$ be the loss of $f_{W}$. The empirical loss of $f_{W}$,
denoted by $\hat{\mathcal{L}}(f_{W})$, is the loss of $f_{W}$ averaged among
the training examples. The expected loss of $f_{W}$, denoted by
${\mathcal{L}}(f_{W})$, is the expectation of $\ell(f_{W}(x),y)$ over $x$
sampled from $\mathcal{D}$ with label $y$. The generalization error of $f_{W}$
is defined as its expected loss minus its empirical loss.

##### Notations.

For any vector $v$, let $\|v\|$ be the Euclidean norm of $v$. For any matrix
$X\in{}^{m\times n}$, let $\|X\|_{{}_{F}}$ be the Frobenius norm and
$\left\|X\right\|_{2}$ be the spectral norm of $X$. Let
$\left\|X\right\|_{1,\infty}$ be defined as $\max_{1\leq j\leq
n}\sum_{i=1}^{m}{\left|{X_{i,j}}\right|}$. If $X$ is a squared matrix, then
the trace of $X$, $\operatorname{Tr}\left[X\right]$, is equal to the sum of
$X$’s diagonal entries. For two matrices $X$ and $Y$ with the same dimension,
let $\langle X,Y\rangle=\operatorname{Tr}\left[X^{\top}Y\right]$ be the matrix
inner product of $X$ and $Y$. For every $i$ from $1$ to $L$, let
$\mathbf{H}_{i}[\ell(f_{W}(x),y)]$ be a $d_{i}d_{i-1}$ by $d_{i}d_{i-1}$
Hessian matrix of the loss $\ell(f_{W}(x),y)$ over $W_{i}$. Given an
eigendecomposition of the Hessian matrix, $UDU^{\top}$, let
$\mathbf{H}_{i}^{+}[\ell(f_{W}(x),y)]=U\max(D,0)U^{\top}$ be a truncation of
$\mathbf{H}_{i}^{+}$ inside the positive eigenspace. Let $v_{i}$ be a flatten
vector of $W_{i}-\hat{W}_{i}^{(s)}$.

For two functions $f(n)$ and $g(n)$, we write $g(n)=O(f(n))$ if there exists a
fixed value $C$ that does not grow with $n$ such that $g(n)\leq C\cdot f(n)$
when $n$ is large enough.

###  2.2 Generalization bounds using PAC-Bayesian analysis

To better understand what impacts fine-tuning performance, we begin by
investigating it following a PAC-Bayesian approach, which has been crucial for
deriving generalization bounds for deepnets [87, 85, 123]. We consider a prior
distribution $\mathcal{P}$ defined as a noisy perturbation of the pretrained
weight matrices $\hat{W}^{(s)}$. We also consider a posterior distribution
$\mathcal{Q}$ defined as a noisy perturbation of the fine-tuned weights
$\hat{W}$. From a PAC-Bayesian perspective, the generalization performance of
a deep network depends on how much noisy perturbations affect its predictions.

Previous work by [85] has explored the noise stability properties of deep
networks and showed how to derive stronger generalization bounds that depend
on the properties of the network. Let $\ell_{\mathcal{Q}}(f_{W}(x),y)$ be the
loss of $f_{W}(x)$, after a noisy perturbation following $\mathcal{Q}$. Denote
$\ell_{\mathcal{Q}}(f_{W}(x),y)$ minus $\ell(f_{W}(x),y)$ as
$\mathcal{I}(f_{W}(x),y)$: A lower value of $\mathcal{I}(f_{W}(x),y)$ means
that the network is more error resilient. The result of [85] shows how to
quantify the error resilience of $f_{W}$ using Lipschitzness and smoothness of
the activation functions across different layers. However, there is still a
large gap between the generalization bounds achieved by [85] and the empirical
generalization errors. Thus, a natural question is whether one can achieve
provable generalization bounds that better capture empirical performance.

The key idea of our approach is to measure generalization using the Hessian of
$\ell(f_{W}(x),y)$. From a technical perspective, this goes beyond the
previous works by leveraging Lipschitness and smoothness of the derivatives of
$f_{W}$. Besides, computational frameworks [114] are developed for efficiently
computing deep net Hessians, such as Hessian vector products [77, 88, 95, 90,
112]. Our central observation is that incorporating Hessians into the distance
from initialization leads to provable bounds that accurately correlate with
empirical performance.

To illustrate the connection between Hessians and generalization, consider a
Taylor’s expansion of $\ell(f_{W+U}(x),y)$ at $W$, for some small perturbation
$U$ over $W$. Suppose the mean of $U$ is and its covariance matrix is
$\Sigma$. Then, $\mathcal{I}(f_{W}(x),y)$ is equal to
$\langle\Sigma,\mathbf{H}[\ell(f_{W}(x),y)]\rangle$ plus higher-order
expansion terms. While this expansion applies to every sample, it remains to
argue the uniform convergence of the Hessians. This requires a perturbation
analysis of the Hessian of all layers but can be achieved assuming
Lipschitness and smoothness of the derivatives of the activation mappings. We
state our results formally below.

######  Theorem 2.1.

Assume the activation functions $\phi_{i}(\cdot)$ for all $i=1,\dots,L$ and
the loss function $\ell(\cdot,\cdot)$ are all twice-differentiable, and their
first-order and second-order derivatives are all Lipschitz-continuous. Suppose
the loss function $\ell(x,y)$ is bounded by a fixed value $C$ for any
$x\in\mathcal{X}$ with class label $y$. Given an $L$-layer network
$f_{\hat{W}}$, with probability at least 0.99, for any fixed $\epsilon$ close
to zero, we have

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}\leq\big{(}1+\epsilon\big{)}\hat{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}+{\frac{(1+\epsilon)\sqrt{C}\sum_{i=1}^{L}\sqrt{\mathcal{H}_{i}}}{\sqrt{n}}}+\xi,$
(3)

where $\mathcal{H}_{i}$ is defined as
$\max_{(x,y)\in\mathcal{D}}v_{i}^{\top}\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]v_{i}$,
for all $i=1,\dots,L$, and $\xi=O(n^{-3/4})$ represents an error term from the
Taylor’s expansion.

Theorem 2.1 applies to vanilla fine-tuning, with or without early stopping. A
corollary of this result can be derived for distance-based regularization,
which restricts the distance between $W_{i}$ and $\hat{W}_{i}^{(s)}$ for every
layer [119]:

$\left\|W_{i}-\hat{W}_{i}^{(s)}\right\|_{F}\leq\alpha_{i},~{}\forall\,i=1,\dots,L.$
(4)

Notice that
$\mathcal{H}_{i}\leq\alpha_{i}^{2}\left({\max_{(x,y)\in\mathcal{X}}\operatorname{Tr}[\mathbf{H}_{i}^{+}(\ell(f_{\hat{W}}(x),y))]}\right)$,
the result from equation (3) could then be adopted for distance-based
regularization of fine-tuning.

We demonstrate that the generalization bound of Theorem 2.1 accurately
correlates with empirical generalization errors. We experiment with seven
methods, including fine-tuning with and without early stopping, distance-based
regularization, label smoothing, mixup, etc. Figure 2 shows that the Hessian
measure (i.e., the second part of equation (3)) correlates with the
generalization errors of these methods. Second, we plot the value of
$\mathcal{D}_{i}$ (averaged over all layers) between fine-tuning with implicit
(early stopping) regularization and explicit (distance-based) regularization.
We find that $\mathcal{D}_{i}$ is smaller for explicit regularization than
implicit regularization.

(a) ResNet-50

(b) ResNet-50

(c) BERT-Base

(d) Average $\mathcal{D}_{i}$

Figure 2:  2(a), 2(b), 2(c): The Hessian measures accurately correlate with
empirical generalization errors for seven fine-tuning methods. 2(d):
$\mathcal{D}_{i}$ is smaller for fine-tuning with explicit distance-based
regularization than implicit early-stopped regularization. Each dot represents
the generalization error and the Hessian measures for one fine-tuned model
using a particular regularization method. Further details are described in
Appendix B.

###  2.3 Incorporating consistent losses with distance-based regularization

Next, we consider the robustness of fine-tuning with noisy labels. We consider
a random classification noise model where in the training dataset, each label
$y_{i}$ is independently flipped to $1,\dots,k$ with some probability [65].
Denote the noisy label by $\tilde{y}_{i}$. With class conditional label noise
[81], $\tilde{y}$ is equal to $z$ with probability $F_{y,z}$, for any
$z=1,\dots,k$, where $F$ is a $k$ by $k$ confusion matrix.

Previous works [75, 82] have suggested minimizing statistically-consistent
losses for learning with noisy labels. Let $\bar{\ell}$ be a weighted loss
parametrized by a $k$ by $k$ weight matrix $\Lambda$,

$\displaystyle{\bar{\ell}(f_{W}(x),\tilde{y})=\sum_{i=1}^{k}\Lambda_{\tilde{y},i}\cdot\ell(f_{W}(x),i).}$
(5)

It is known that for $\Lambda=F^{-1}$ (recall that $F$ is the confusion
matrix), the weighted loss $\bar{\ell}$ is unbiased in the sense that the
expectation of $\bar{\ell}(f_{W}(x),\tilde{y})$ over the labeling noise is
$\ell(f_{W}(x),y)$:

$\displaystyle{\mathop{\mathbb{E}}_{\tilde{y}}\left[\bar{\ell}(f_{W}(x),\tilde{y})\mid
y\right]=\ell(f_{W}(x),y).}$ (6)

See Lemma 1 in [75] for the binary setting and Theorem 1 in [82] for the
multiclass setting. As a result, a natural approach to designing a
theoretically-principled fine-tuning algorithm is to minimize weighted losses
with $\Lambda=F^{-1}$. However, this approach does not take overfitting into
consideration.

Our proposed approach involves incorporating consistent losses with distance-
based regularization. Let $\bar{\mathcal{L}}(f_{W})$ be the average of the
weighted loss $\bar{\ell}(f_{W}(x_{i}),\tilde{y}_{i})$ over $i=1,\dots,n$. We
extend Theorem 2.1 to this setting as follows.

######  Theorem 2.2.

Assume the activation functions $\\{\phi_{i}(\cdot)\\}_{i=1}^{L}$ and the loss
function $\ell(\cdot,\cdot)$ satisfy the assumptions stated in Theorem 2.1.
Suppose the noisy labels are independent of the feature vector conditional on
the class label. Suppose the loss function $\ell(x,z)$ is bounded by $C$ for
any $x\in\mathcal{X}$ and any $z\in\\{1,\dots,k\\}$. With probability $0.99$,
for any fixed $\epsilon$ close to zero, we have

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}\leq(1+\epsilon)\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}+\frac{(1+\epsilon)\sqrt{{C\left\|(F^{-1})^{\top}\right\|_{1,\infty}}}\sum_{i=1}^{L}\sqrt{\alpha_{i}^{2}\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert}}{\sqrt{n}}+\xi,$

where $\alpha_{i}$ is any value greater than
$\|\hat{W}_{i}-\hat{W}_{i}^{(s)}\|_{{}_{F}}$, for any $i=1,\dots,L$, and
$\xi=O\big{(}n^{-3/4}\big{)}$ represents an error term from the Taylor’s
expansion.

Theorem 2.2 shows that combining consistent losses leads to a method that is
provably robust under class conditional label noise. Notice that this result
uses the trace of the Hessian $\mathbf{H}_{i}$ instead of the truncated
Hessian $\mathbf{H}_{i}^{+}$. The reason is that the reweighing matrix
$\Lambda$ might include negative coefficients and $\mathbf{H}_{i}^{+}$ deals
with this problem. Based on the theory, we design an algorithm to instantiate
this idea. Our approach uses a projection step proposed in [119]. In Section
3, we evaluate the robustness of Algorithm 1 for both image and text
classification tasks.

Algorithm 1 Statistically-consistent loss reweighting with layerwise
projection

Input: Training dataset $\\{(x_{i},\tilde{y}_{i})\\}_{i=1}^{n}$ with input
feature $x_{i}$ and noisy label $\tilde{y}_{i}$, for $i=1,\dots,n$.
Require: Pretrained network $f_{\hat{W}^{(s)}}$, layerwise distance
$\alpha_{i}$ for $i=1,\dots,L$, number of epochs $T$, learning rate $\eta$,
and confusion matrix $F$.
Output: A trained model $f_{W^{(T)}}$.

1: Let $\Lambda=F^{-1}$.

2: At $t=0$, initialize model parameters with weight matrices
$W^{(0)}=\hat{W}^{(s)}$.

3: while $0<t<T$ do

4: Let
$\bar{\mathcal{L}}(f_{W^{(t-1)}})=\frac{1}{n}\sum_{i=1}^{n}\sum_{c=1}^{k}\Lambda_{\tilde{y}_{i},c}\cdot\ell(f_{W^{(t-1)}}(x_{i}),c)$.

5: Update $W^{(t)}\leftarrow
W^{(t-1)}-\eta\cdot\nabla\bar{\mathcal{L}}(f_{W^{(t-1)}})$ using stochastic
gradient descent.

6: Project $W_{i}^{(t)}$ inside the constrained ball:
$W_{i}^{(t)}\leftarrow\min\Big{(}1,\frac{\alpha_{i}}{\|W_{i}^{(t)}-W_{i}^{(0)}\|_{{}_{F}}}\Big{)}\big{(}W_{i}^{(t)}-W_{i}^{(0)}\big{)}+W_{i}^{(0)}$,
$\forall\,i=1,\dots,L$.

7: end while

###  2.4 Proof overview

We give an overview of the proof of Theorems 2.1 and 2.2. First, we show that
the noise stability of an $L$-layer neural network $f_{W}$ admits a layerwise
Hessian approximation. Let $U\sim\mathcal{Q}$ be a random variable drawn from
a posterior distribution $\mathcal{Q}$. We are interested in the perturbed
loss, $\ell_{\mathcal{Q}}(f_{U}(x),y)$, which is the expectation of
$\ell(f_{U}(x),y)$ over $U$.

######  Lemma 2.3.

In the setting of Theorem 2.1, for any $i=1,2,\cdots,L$, let
$U_{i}\in{}^{d_{i}d_{i-1}}$ be a random vector sampled from a Gaussian
distribution with mean zero and variance $\Sigma_{i}$. Let the posterior
distribution $\mathcal{Q}$ be centered at $W_{i}$ and perturbed with an
appropriately reshaped $U_{i}$ at every layer. Then, there exists a fixed
value $C_{1}>0$ that does not grow with $n$, such that the following holds for
any $x\in\mathcal{X}$ and $y\in\\{1,\dots,k\\}$:

$\displaystyle\ell_{\mathcal{Q}}(f_{W}(x),y)-\ell(f_{W}(x),y)\leq\sum_{i=1}^{L}\left(\big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{W}(x),y)]\big{\rangle}+C_{1}\left\|\Sigma_{i}\right\|_{F}^{3/2}\right).$
(7)

See Appendix A.5 for the proof of Lemma 2.3. Interestingly, we find that the
Hessian estimate is remarkably accurate in practice. We use ResNet-18 and
ResNet-50 fine-tuned on the CIFAR-100 dataset. We estimate the left-hand side
of equation (7) by randomly sampling $500$ isotropic Gaussian perturbations
and averaging the perturbed losses. Then, we compute the Hessian term on the
right-hand side of equation (7) by measuring the traces of the loss’s Hessian
at each layer of the network and average over the same data samples. Table 2
shows the result. The relative error of the Hessian estimate is within 3% on
ResNet.

Table 2: Showing the relative residual sum of squares (RSS) of the Hessian approximation (7) under isotropic noise perturbation of variance $\sigma^{2}$. The noise stability results are estimated by the average of 500 noise injections. All the experiments are done with the CIFAR-100 dataset. $\sigma$ | ResNet-18 | ResNet-50
---|---|---
Noise Stability | Hessian Approx. | Noise Stability | Hessian Approx.
0.01 | $0.86\pm 0.19$ | 1.07 | $0.39\pm 0.10$ | 1.24
0.011 | $1.13\pm 0.24$ | 1.29 | $1.12\pm 0.20$ | 1.50
0.012 | $1.45\pm 0.29$ | 1.54 | $1.56\pm 0.26$ | 1.79
0.013 | $1.82\pm 0.35$ | 1.80 | $2.10\pm 0.33$ | 2.10
0.014 | $2.23\pm 0.40$ | 2.09 | $2.71\pm 0.38$ | 2.43
0.015 | $2.65\pm 0.43$ | 2.34 | $3.30\pm 0.40$ | 2.79
0.016 | $3.07\pm 0.45$ | 2.73 | $3.80\pm 0.40$ | 3.18
0.017 | $3.47\pm 0.47$ | 3.08 | $4.17\pm 0.40$ | 3.59
0.018 | $3.84\pm 0.49$ | 3.46 | $4.60\pm 0.44$ | 4.02
0.019 | $4.15\pm 0.51$ | 3.85 | $4.77\pm 0.44$ | 4.48
0.020 | $4.43\pm 0.55$ | 4.27 | $5.03\pm 0.82$ | 4.97
Relative RSS | 0.75% | 2.98%

Based on the Hessian approximation, consider applying a PAC-Bayes bound over
the $L$-layer network $f_{W}$ (see Theorem A.1 in Appendix A for a statement).
The KL divergence between the prior distribution and the posterior
distribution is equal to

$\sum_{i=1}^{L}\left\langle\Sigma_{i}^{-1},v_{i}v_{i}^{\top}\right\rangle.$
(8)

Minimizing the sum of the Hessian estimate and the above KL divergence (8) in
the PAC-Bayes bound will lead to a different covariance matrix for every
layer, which depends on $v_{i}$ and
$\mathop{\mathbb{E}}\left[\mathbf{H}_{i}^{+}\right]$:

$\sum_{i=1}^{L}\Big{(}\langle\Sigma_{i},\mathop{\mathbb{E}}_{x,y}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\rangle+\frac{1}{n}\langle\Sigma_{i}^{-1},v_{i}v_{i}^{\top}\rangle\Big{)}\leq\sum_{i=1}^{L}\Big{(}\langle\Sigma_{i},\mathop{\mathbb{E}}_{x,y}\left[\mathbf{H}_{i}^{+}[\ell(f_{W}(x),y)]\right]\rangle+\frac{1}{n}\langle\Sigma_{i}^{-1},v_{i}v_{i}^{\top}\rangle\Big{)},$
(9)

where the $1/n$ factor is inherited from the PAC-Bayes bound (cf. Theorem
A.1). Thus, minimizing the above over the covariance matrices leads to the
Hessian distance-based generalization bound of Theorem 2.1.

The above sketch highlights the crux of the result. The rigorous proof, on the
other hand, is significantly more involved. One technical challenge is arguing
the uniform convergence to the population Hessian operator $\mathbf{H}_{i}$
(over $\mathcal{D}$) from the empirical loss Hessians. This requires a
perturbation analysis of the Hessian and assumes that the second-order
derivatives of the activation functions (and the loss) are Lipschitz-
continuous.

######  Lemma 2.4.

In the setting of Theorem 2.1, there exist some fixed values $C_{2},C_{3}$
that do not grow with $n$ and $1/\delta$, such that with probability at least
$1-\delta$ over the randomness of the training set, we have

$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}},$
(10)

for any $i=1,\dots,L$, where
$C_{2}=4\mathcal{H}_{i}\sqrt{\sum_{i=1}^{L}d_{i}d_{i-1}}$,
$C_{3}=5L\Big{(}\sqrt{\sum_{i=1}^{L}\|W_{i}\|_{{}_{F}}^{2}}\Big{)}G/\mathcal{H}_{i}$,
and $G$ is a fixed value that depends on $\prod_{i=1}^{L}\|W_{i}\|_{2}$, the
Lipschitzness of the activation functions, and the Lipschitzness of their
first-order and second-order derivatives (cf. equation (30) in Proposition A.5
for the precise value of $G$).

See Appendix A.3 for the proof of Lemma 2.4, which is based on an
$\epsilon$-net argument. The rest of the proof of Theorem 2.1 can be found in
Appendix A.1.

The key idea for dealing with noisy labels is a consistency condition for the
weighted loss $\bar{\ell}(f_{W}(x),\tilde{y})$ with noisy label $\tilde{y}$:

$\mathcal{L}(f_{W})=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\mathop{\mathbb{E}}_{\tilde{y}|y}\left[\bar{\ell}(f_{W}(x),\tilde{y})\right].$

Thus, consider a noisy data distribution $\tilde{D}$, with the label $y$ of
every $x$ flipped independently to $\tilde{y}$. Our key observation is that
$\bar{\ell}(f_{W}(x),\tilde{y})$ enjoys similar noise stability properties as
$\ell(f_{W}(x),y)$. See Figure 3 for an illustration. A complete proof of
Theorem 2.2 can be found in Appendix A.2.

(a) ResNet-18 on
CIFAR-10

(b) ResNet-50 on
CIFAR-10

(c) ResNet-18 on
CIFAR-100

(d) ResNet-50 on
CIFAR-100

Figure 3: Illustrating the intuition behind Theorem 2.2: With consistent
losses, the noisy stability of the loss Hessian with noisy labels is equal to
the noise stability of the loss Hessian with class labels in expectation.
Thus, the unbiased weighted losses enjoy similar noise stability properties as
training with class labels. Further, the unbiased loss favors stable models as
the trace of the Hessian is smallest when $\tilde{y}=y$.

##  3 Experiments

This section conducts experiments to evaluate our proposed algorithm. We
evaluate the robustness of Algorithm 1 under various noisy environments and
architectures. First, we validate that when the training labels are corrupted
with class conditional label noise, our approach is robust even under up to
60% of label noise. Second, on six weakly-supervised image classification
tasks, our algorithm improves the prediction accuracy over prior approaches by
3.26% on average. Lastly, we present a detailed analysis that validates the
theory, including comparing our generalization bound with previous results and
comparing the Hessian distance measure for various fine-tuning methods.

###  3.1 Experimental setup

Datasets. We evaluate the robustness of our approach in image and text
classification tasks. For image classification, we use six domains of object
classification tasks from the DomainNet dataset. We consider two kinds of
label noise. First, we generate synthetic random noise by randomly flipping
the labels of training samples uniformly with a given noise rate. Second, we
create labels using weak supervision approaches [124]. The statistics of the
six datasets are described in Table 7 from Section B.2. We refer the reader to
the work of [124] for more details.

For text classification, we use the MRPC dataset from the GLUE benchmark,
which is to predict whether two sentences are semantically equivalent.

Table 3: Test accuracy of fine-tuning with noisy labels. We consider two settings: one where the training labels are independently flipped to incorrect labels and another where the training labels are created using programmatic labeling approaches. The reported results are averaged over 10 random seeds. Independent label noise | Sketch, ResNet-18 | Sketch, ResNet-101 | MRPC, RoBERTa-Base
---|---|---|---
40% | 60% | 40% | 60% | 20% | 40%
Early Stopping |  72.41$\pm$3.53 |  53.84$\pm$3.09 |  77.14$\pm$3.09 |  61.39$\pm$1.28 |  81.39$\pm$0.73 |  66.05$\pm$0.63
Label Smooth |  74.69$\pm$1.97 |  55.35$\pm$1.60 |  81.47$\pm$1.36 |  64.90$\pm$2.93 |  80.00$\pm$0.62 |  65.87$\pm$0.95
Mixup |  70.65$\pm$1.85 |  58.49$\pm$3.25 |  76.04$\pm$2.29 |  60.12$\pm$2.37 |  80.62$\pm$0.14 |  68.37$\pm$1.33
FixMatch [105] |  73.35$\pm$3.15 |  61.51$\pm$2.17 |  76.19$\pm$1.39 |  62.19$\pm$1.57 |  81.10$\pm$1.76 |  68.48$\pm$1.43
ELR [100] |  74.29$\pm$2.52 |  63.14$\pm$2.05 |  80.00$\pm$1.45 |  64.35$\pm$3.98 |  82.78$\pm$0.86 |  67.86$\pm$1.44
APL [103] |  75.63$\pm$1.81 |  64.69$\pm$2.72 |  78.69$\pm$2.45 |  64.82$\pm$2.41 |  80.49$\pm$0.24 |  66.49$\pm$0.93
SAT [97] |  75.18$\pm$1.54 |  62.33$\pm$2.24 |  80.00$\pm$2.96 |  65.58$\pm$2.91 |  82.80$\pm$0.42 |  67.50$\pm$1.00
GJS [117] |  73.22$\pm$2.34 |  59.63$\pm$5.15 |  77.14$\pm$2.46 |  63.27$\pm$2.37 |  81.42$\pm$1.03 |  67.57$\pm$1.53
DualT [113] |  72.49$\pm$3.17 |  59.59$\pm$3.44 |  77.96$\pm$0.33 |  62.31$\pm$3.98 |  82.49$\pm$0.53 |  66.49$\pm$0.93
SupCon |  75.14$\pm$1.73 |  61.06$\pm$3.20 |  78.86$\pm$1.80 |  63.92$\pm$2.15 |  82.30$\pm$1.80 |  68.32$\pm$1.16
SAM [118] |  77.63$\pm$2.16 |  64.53$\pm$2.84 |  80.57$\pm$2.70 |  67.27$\pm$2.39 |  82.61$\pm$0.91 |  69.06$\pm$1.41
Ours (Alg. 1) | 81.96$\pm$0.98 | 70.00$\pm$1.71 | 85.44$\pm$1.26 | 71.84$\pm$2.72 | 83.55$\pm$0.63 | 72.64$\pm$1.77
Correlated label noise | DomainNet, ResNet-18
Clipart | Infograph | Painting | Quickdraw | Real | Sketch
41.47% | 63.29% | 44.50% | 60.54% | 34.64% | 47.68%
Early Stopping |  73.88$\pm$2.04 |  38.82$\pm$2.59 |  69.69$\pm$1.35 |  44.16$\pm$1.92 |  78.52$\pm$1.03 |  61.84$\pm$3.67
Label Smooth |  74.56$\pm$2.30 |  38.40$\pm$2.67 |  70.76$\pm$1.74 |  46.50$\pm$3.03 |  81.39$\pm$0.93 |  62.29$\pm$2.48
Mixup |  72.88$\pm$0.94 |  39.27$\pm$3.10 |  69.28$\pm$3.18 |  47.66$\pm$3.20 |  80.17$\pm$2.05 |  62.08$\pm$3.06
FixMatch [105] |  77.04$\pm$2.52 |  41.95$\pm$1.52 |  73.31$\pm$2.10 |  48.74$\pm$2.08 |  86.33$\pm$2.54 |  64.61$\pm$3.28
ELR [100] |  76.08$\pm$2.03 |  40.14$\pm$2.74 |  72.06$\pm$1.73 |  47.40$\pm$3.09 |  83.64$\pm$2.09 |  65.76$\pm$3.19
APL [103] |  77.40$\pm$2.33 |  41.22$\pm$2.58 |  73.61$\pm$3.12 |  49.88$\pm$3.24 |  85.79$\pm$1.59 |  64.69$\pm$2.30
SAT [97] |  75.24$\pm$2.79 |  39.58$\pm$1.47 |  70.69$\pm$2.69 |  48.18$\pm$2.95 |  81.90$\pm$1.07 |  65.39$\pm$2.77
GJS [117] |  77.20$\pm$2.59 |  40.94$\pm$2.19 |  72.51$\pm$2.87 |  48.14$\pm$3.40 |  85.05$\pm$1.94 |  65.43$\pm$3.35
DualT [113] |  75.24$\pm$2.02 |  38.75$\pm$2.12 |  70.27$\pm$2.24 |  46.62$\pm$3.16 |  83.33$\pm$3.01 |  65.47$\pm$1.91
SupCon |  76.56$\pm$3.53 |  40.38$\pm$1.94 |  72.51$\pm$2.45 |  49.20$\pm$2.63 |  81.87$\pm$0.84 |  65.67$\pm$2.90
SAM [118] |  79.04$\pm$1.57 |  41.50$\pm$1.94 |  73.23$\pm$2.29 |  50.10$\pm$1.66 |  84.61$\pm$2.04 |  66.73$\pm$2.88
Ours (Alg. 1) | 83.28$\pm$1.64 | 43.38$\pm$2.45 | 76.32$\pm$1.08 | 50.32$\pm$2.74 | 92.36$\pm$0.78 | 66.86$\pm$3.29

##### Models.

For fine-tuning from noisy labels, we use pretrained ResNet-18 and ResNet-101
models on image classification tasks and extend our results to Vision
Transformer (ViT) model. We use the RoBERTa-Base model on text classification
tasks.

##### Baselines.

We consider the following three kinds of baselines: (i) Regularization: Fine-
tuning with early stop (Early stopping), label smoothing, Mixup [111], and
Early-Learning Regularization (ELR) [100]; (iii) Self-training: FixMatch [105]
and Self-Adaptive Training (SAT) [97]; (ii) Robust loss function: Active
Passive Loss (APL) [103], Generalized Jensen-Shannon Divergence (GJS) [117],
dual transition estimator (DualT) [113], Supervised Contrastive learning
(SupCon), and Sharpness-Aware Minimization (SAM) [118].

To implement our algorithm, we use the confusion matrix $F$ estimated by the
method from the work of [113]. We use layerwise distances [122] for applying
the regularization constraints in Equation (4). We describe the implementation
details and hyper-parameters in Section B.2.

###  3.2 Experimental results

Improved robustness against independent label noise. Our result in Section 2.3
illustrates why our algorithm might be expected to achieve provable robustness
under class conditional label noise. To validate its effectiveness, we apply
our algorithm to image and text classification tasks with different levels of
synthetic random labels. Table 3 reports the test accuracy.

  * •

First, we fine-tune ResNet-18 on the Sketch domain from the DomainNet dataset
with 40% and 60% synthetic noise. We observe that our algorithm improves upon
the baseline methods by 6.43% on average. The results corroborate our theory
that provides generalization guarantees for our algorithm.

  * •

Second, to evaluate our algorithm with deeper models, we apply ResNet-101 on
the same label noise settings. We observe a higher average performance with
ResNet-101, and our algorithm achieves a similar performance boost of 6.03% on
average over the previous methods.

  * •

Third, we fine-tune the RoBERTa-Base model on the MRPC dataset with 20% and
40% synthetic noise. Our algorithm outperforms previous methods by 2.91% on
average. These results show that our algorithm is robust to label noise across
various tasks and architectures.

##### Improved robustness against correlated label noise.

Next, we show that our algorithm can achieve competitive performance under
real-world label noise. We evaluate our algorithm on weakly-supervised image
classification tasks. We fine-tune ResNet-18 on the six domains from the
DomainNet dataset and report the test accuracy in Table 3. We find that
Algorithm 1 outperforms previous methods by 3.26%, averaged over the six
tasks.

We expect our results under correlated label noise to hold with various model
architectures. As an extension of the above experiment, we fine-tune vision
transformer models on the same set of tasks. Table 4 reports the results on
the Clipart and Sketch domains. We notice that using ViT as the base model
boosts the performance across all approaches significantly (e.g., over 4% for
early stopping). We find that our approach outperforms baseline methods by
2.42% on average.

Table 4: Test accuracy of fine-tuning vision transformers with correlated noisy labels on Clipart and Sketch domains from the DomainNet dataset. Results are averaged over 10 random seeds. Correlated label noise | DomainNet, ViT-Base
---|---
Clipart | Sketch
Early Stopping |  80.48$\pm$2.65 |  66.29$\pm$3.82
Label Smooth |  80.00$\pm$3.23 |  67.02$\pm$1.38
Mixup |  81.44$\pm$2.33 |  69.06$\pm$1.05
FixMatch [105] |  81.92$\pm$1.35 |  68.08$\pm$2.52
ELR [100] |  82.48$\pm$2.32 |  68.33$\pm$3.27
APL [103] |  79.12$\pm$3.75 |  68.33$\pm$2.39
SAT [97] |  81.20$\pm$2.35 |  68.57$\pm$2.70
GJS [117] |  80.48$\pm$2.61 |  66.94$\pm$2.98
DualT [113] |  82.24$\pm$3.55 |  67.92$\pm$2.97
SupCon |  82.64$\pm$2.80 |  65.22$\pm$2.18
SAM [118] |  80.16$\pm$2.00 |  68.24$\pm$2.36
Ours | 84.40$\pm$1.94 | 71.02$\pm$1.81

##### Ablation study.

We study the influence of each component of our algorithm: the weighted loss
scheme and the regularization constraints. We ablate the effect of our
weighted loss and regularization constraints, showing that both are crucial to
the final performance. We run the same experiments with only one component
from the algorithm. As shown in Table 5, removing either component affects the
performance negatively. This suggests that both the weighted loss and the
regularization constraints play an important role in the final performance.

Table 5: Removing either component in Algorithm 1 degrades the test accuracy. Results are averaged over 10 random seeds. Correlated label noise | DomainNet, ResNet-18
---|---
Clipart | Infograph | Painting | Quickdraw | Real | Sketch
Using only loss reweighting |  77.96$\pm$1.57 |  41.78$\pm$2.86 |  72.13$\pm$1.66 |  49.10$\pm$2.42 |  85.34$\pm$1.51 |  64.78$\pm$1.60
Using only regularization |  82.84$\pm$1.11 |  42.34$\pm$1.92 |  75.81$\pm$2.07 |  49.76$\pm$2.86 |  91.67$\pm$0.85 |  65.96$\pm$2.73
Alg. 1 | 83.28$\pm$1.64 | 43.38$\pm$2.45 | 76.32$\pm$1.08 |  50.32$\pm$2.74 | 92.36$\pm$0.78 | 66.86$\pm$3.29

###  3.3 Further numerical results

##### Comparison of Hessian-based distance measures.

The design of our algorithm is motivated by our Hessian-based generalization
guarantees. We hypothesize that our algorithm can effectively reduce the
Hessian distance measure $\sum_{i=1}^{L}\sqrt{\mathcal{H}_{i}}$ (cf. Equation
3) of fine-tuned models. We compare the Hessian quantity of models fine-tuned
by different algorithms. We select five baseline methods to compare with our
algorithm and expect similar results for comparison with other baselines.
Figure 4 shows the results of ResNet-18 models fine-tuned on the Clipart
dataset with weak supervision noise. We notice that our algorithm reduces the
quantity by six times more than previous fine-tuning algorithms.

##### Comparison of generalization bounds.

Our result suggests that Hessian-based generalization bounds correlate with
the empirical performance of fine-tuning. Next, we compare our result with
previous generalization bounds, including norm bounds [101, 119, 122], and
margin bounds [87, 83, 85]. See Appendix B.1 for references on the measurement
quantities. For our result, we numerically calculate
${\sum_{i=1}^{L}\sqrt{C\cdot\mathcal{H}_{i}}/{\sqrt{n}}}+\xi$ from equation 3.
We compute $\mathcal{H}_{i}$ using Hessian vector product functions in
PyHessian [114]. We take the maximum over the training and test dataset.
Following prior works, we evaluate the results using the CIFAR-10 and
CIFAR-100 datasets. We use ResNet-50 as the base model for fine-tuning.
Additionally, we evaluate our results on text classification tasks, including
MRPC and SST-2 from the GLUE benchmark. We use BERT-Base-Uncased as the base
model for fine-tuning. Table 6 shows the result. We find that our bound is
orders of magnitude smaller than previous results. These results show that our
theory leads to practical bounds for real-world settings.

Figure 4: Comparison of the Hessian-based distance measure (cf. equation (3))
between existing and our fine-tuning approaches.

Table 6: Numerical comparison between our and known generalization bounds
measured with ResNet-50 and BERT-Base as the base model.

Generalization bound | CIFAR-10 | CIFAR-100 | MRPC | SST2
---|---|---|---|---
[83] | 5.51E+10 | 3.13E+12 | / | /
[85] | 1.62E+06 | 9.66E+07 | / | /
[101] | 6.30E+13 | 8.32E+13 | / | /
[119] | 2.04E+69 | 2.72E+69 | / | /
[122] | 1.63E+27 | 1.31E+29 | / | /
[87] | 3.13E+11 | 1.62E+13 | / | /
Our result | 2.26 | 7.23 | 3.83 | 9.71

##  4 Conclusion

This work approached generalization for fine-tuning deep networks using a PAC-
Bayesian analysis. The analysis shows that besides distance from
initialization, Hessians play a crucial role in measuring generalization. Our
theoretical contribution involves Hessian distance-based generalization bounds
for various fine-tuning methods on deep networks. We empirically show that the
Hessian distance measure accurately correlates with the generalization error
of fine-tuning in practice. Although we state our results for fine-tuned
models, it is worth mentioning that the same statement holds in the supervised
learning setting. In this case, the distance vector $v_{i}$ in statement (3)
corresponds to the difference between the random initialization of the network
and the final trained weight matrix. Besides, our theoretical result suggests
a principled algorithm for fine-tuning with noisy labels. Experiments
demonstrate the robustness of our algorithm under both synthetic and real-
world label noise.

We describe two questions for future work. First, our result requires the
activation mappings of the neural network to be twice-differentiable: While
this is a fairly technical issue, it would be interesting to extend our result
to differentiable activation functions. For example, in the practical use of
ReLU activations, it is conceivable that non-differentiable points rarely
occur. One way is to use smoothed analysis to argue that such non-
differentiable points occur with negligible probability. Second, it would be
interesting to apply Hessians to understand generalization in other black-box
models. More broadly, we hope our work inspires further study on the interplay
between second-order gradients and generalization.

## Acknowledgment

Thanks to the anonymous referees for their constructive feedback. Thanks to
Rajmohan Rajaraman and Jason Lee for the helpful discussions. Also, thanks to
Pratik Chaudhari for pointing out several references from the earlier
literature. HJ and DL acknowledge the support of a startup fund and a
seed/proof-of-concept grant from the Khoury College of Computer Sciences,
Northeastern University.

[sorting=nyt]

## References

  * [1] Dana Angluin and Philip Laird  “Learning from noisy examples”  In _Machine Learning_ Springer, 1988
  * [2] Sanjeev Arora  “Technical perspective: Why don’t today’s deep nets overfit to their training data?”  In _Communications of the ACM_ 64.3 ACM New York, NY, USA, 2021, pp. 106–106
  * [3] Sanjeev Arora, Rong Ge, Behnam Neyshabur and Yi Zhang  “Stronger generalization bounds for deep nets via a compression approach”  In _International Conference on Machine Learning_ , 2018
  * [4] Antonio Valerio Miceli Barone, Barry Haddow, Ulrich Germann and Rico Sennrich  “Regularization techniques for fine-tuning in neural machine translation”  In _EMNLP_ , 2017
  * [5] Peter Bartlett, Dylan J Foster and Matus Telgarsky  “Spectrally-normalized margin bounds for neural networks”  In _Neural Information Processing Systems_ , 2017
  * [6] Peter L Bartlett, Nick Harvey, Christopher Liaw and Abbas Mehrabian  “Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks”  In _The Journal of Machine Learning Research_ JMLR. org, 2019
  * [7] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira and Jennifer Wortman Vaughan  “A theory of learning from different domains”  In _Machine learning_ , 2010
  * [8] Shai Ben-David and Reba Schuller Borbely  “A notion of task relatedness yielding provable multiple-task learning guarantees”  In _Machine learning_ 73.3 Springer, 2008, pp. 273–287
  * [9] Shai Ben-David, Johannes Gehrke and Reba Schuller  “A theoretical framework for learning from a pool of disparate data sources”  In _KDD_ , 2002
  * [10] Evangelos Chatzipantazis, Stefanos Pertigkiozoglou, Edgar Dobriban and Kostas Daniilidis  “Learning Augmentation Distributions using Transformed Risk Minimization”  In _arXiv preprint arXiv:2111.08190_ , 2021
  * [11] Koby Crammer, Michael Kearns and Jennifer Wortman  “Learning from Multiple Sources”  In _Journal of Machine Learning Research_ 9.8, 2008
  * [12] Sanjoy Dasgupta, Michael Littman and David McAllester  “PAC generalization bounds for co-training”  In _Advances in neural information processing systems_ 14, 2001
  * [13] Gintare Karolina Dziugaite and Daniel M Roy  “Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data”  In _UAI_ , 2017
  * [14] Erik Englesson and Hossein Azizpour  “Generalized Jensen-Shannon Divergence Loss for Learning with Noisy Labels”  In _Neural Information Processing Systems_ , 2021
  * [15] Pierre Foret, Ariel Kleiner, Hossein Mobahi and Behnam Neyshabur  “Sharpness-aware minimization for efficiently improving generalization”  In _ICLR_ , 2021
  * [16] Behrooz Ghorbani, Shankar Krishnan and Ying Xiao  “An investigation into neural net optimization via hessian eigenvalue density”  In _International Conference on Machine Learning_ , 2019
  * [17] Henry Gouk, Timothy M Hospedales and Massimiliano Pontil  “Distance-Based Regularisation of Deep Networks for Fine-Tuning”  In _ICLR_ , 2021
  * [18] Benjamin Guedj  “A Primer on PAC-Bayesian Learning”  In _Proceedings of the French Mathematical Society_ 33, 2019, pp. 391–414  Société Mathématique de France
  * [19] Steve Hanneke and Samory Kpotufe  “On the value of target data in transfer learning”  In _NeurIPS_ , 2019
  * [20] Moritz Hardt and Benjamin Recht  “Patterns, predictions, and actions: A story about machine learning”  In _arXiv preprint arXiv:2102.05242_ , 2021
  * [21] Lang Huang, Chao Zhang and Hongyang Zhang  “Self-adaptive training: beyond empirical risk minimization”  In _NeurIPS_ , 2020
  * [22] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan and Samy Bengio  “Fantastic generalization measures and where to find them”  In _ICLR_ , 2020
  * [23] Qi Lei, Wei Hu and Jason Lee  “Near-optimal linear regression under distribution shift”  In _ICML_ , 2021
  * [24] Dongyue Li and Hongyang Zhang  “Improved Regularization and Robustness for Fine-tuning in Neural Networks”  In _NeurIPS_ , 2021
  * [25] Mingchen Li, Mahdi Soltanolkotabi and Samet Oymak  “Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks”  In _AISTATS_ , 2020
  * [26] Renjie Liao, Raquel Urtasun and Richard Zemel  “A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks”  In _ICLR_ , 2021
  * [27] Sheng Liu, Jonathan Niles-Weed, Narges Razavian and Carlos Fernandez-Granda  “Early-learning regularization prevents memorization of noisy labels”  In _NeurIPS_ , 2020
  * [28] Tongliang Liu and Dacheng Tao  “Classification with noisy labels by importance reweighting”  In _IEEE Transactions on pattern analysis and machine intelligence_ IEEE, 2015
  * [29] Philip M Long and Hanie Sedghi  “Generalization bounds for deep convolutional neural networks”  In _ICLR_ , 2020
  * [30] Michal Lukasik, Srinadh Bhojanapalli, Aditya Menon and Sanjiv Kumar  “Does label smoothing mitigate label noise?”  In _International Conference on Machine Learning_ , 2020, pp. 6448–6458  PMLR
  * [31] Xingjun Ma, Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani and James Bailey  “Normalized loss functions for deep learning with noisy labels”  In _International Conference on Machine Learning_ , 2020
  * [32] Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach and Eli Upfal  “Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees”  In _ICML_ , 2021
  * [33] David A McAllester  “PAC-Bayesian model averaging”  In _Proceedings of the twelfth annual conference on Computational learning theory_ , 1999
  * [34] David A McAllester  “Some pac-bayesian theorems”  In _Machine Learning_ Springer, 1999
  * [35] David A McAllester  “A PAC-Bayesian tutorial with a dropout bound”  In _arXiv preprint arXiv:1307.2118_ , 2013
  * [36] Vaishnavh Nagarajan and J Zico Kolter  “Generalization in deep networks: The role of distance from initialization”  In _arXiv preprint arXiv:1901.01672_ , 2019
  * [37] Vaishnavh Nagarajan and Zico Kolter  “Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience”  In _International Conference on Learning Representations_ , 2018
  * [38] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar and Ambuj Tewari  “Cost-Sensitive Learning with Noisy Labels.”  In _J. Mach. Learn. Res._ , 2017
  * [39] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar and Ambuj Tewari  “Learning with noisy labels”  In _Advances in neural information processing systems_ , 2013
  * [40] Behnam Neyshabur, Srinadh Bhojanapalli and Nathan Srebro  “A pac-bayesian approach to spectrally-normalized margin bounds for neural networks”  In _ICLR_ , 2018
  * [41] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun and Nathan Srebro  “Towards understanding the role of over-parametrization in generalization of neural networks”  In _ICLR_ , 2019
  * [42] Behnam Neyshabur, Hanie Sedghi and Chiyuan Zhang  “What is being transferred in transfer learning?”  In _NeurIPS_ , 2020
  * [43] Vardan Papyan  “The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size”  In _arXiv preprint arXiv:1811.07062_ , 2018
  * [44] Vardan Papyan  “Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians”  In _ICML_ , 2019
  * [45] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock and Lizhen Qu  “Making deep neural networks robust to label noise: A loss correction approach”  In _CVPR_ , 2017
  * [46] Konstantinos Pitas, Mike Davies and Pierre Vandergheynst  “Pac-bayesian margin bounds for convolutional neural networks”  In _arXiv preprint arXiv:1801.00171_ , 2017
  * [47] Levent Sagun, Leon Bottou and Yann LeCun  “Eigenvalues of the hessian in deep learning: Singularity and beyond”  In _arXiv preprint arXiv:1611.07476_ , 2016
  * [48] Gal Shachaf, Alon Brutzkus and Amir Globerson  “A Theoretical Analysis of Fine-tuning with Linear Teachers”  In _Advances in Neural Information Processing Systems_ , 2021
  * [49] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang and Colin Raffel  “Fixmatch: Simplifying semi-supervised learning with consistency and confidence”  In _NeurIPS_ , 2020
  * [50] Nilesh Tripuraneni, Michael Jordan and Chi Jin  “On the theory of transfer learning: The importance of task diversity”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 7852–7862
  * [51] Yusuke Tsuzuku, Issei Sato and Masashi Sugiyama  “Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using pac-bayesian analysis”  In _ICML_ , 2020
  * [52] Tu Vu, Tong Wang, Tsendsuren Munkhdalai, Alessandro Sordoni, Adam Trischler, Andrew Mattarella-Micke, Subhransu Maji and Mohit Iyyer  “Exploring and predicting transferability across NLP tasks”  In _EMNLP_ , 2020
  * [53] Martin J Wainwright  “High-dimensional statistics: A non-asymptotic viewpoint”  Cambridge University Press, 2019
  * [54] Colin Wei and Tengyu Ma  “Improved sample complexities for deep neural networks and robust classification via an all-layer margin”  In _International Conference on Learning Representations_ , 2020
  * [55] Sen Wu, Hongyang R Zhang and Christopher Ré  “Understanding and improving information transfer in multi-task learning”  In _ICLR_ , 2020
  * [56] Sen Wu, Hongyang R Zhang, Gregory Valiant and Christopher Ré  “On the generalization effects of linear transformations in data augmentation”  In _International Conference on Machine Learning_ , 2020  PMLR
  * [57] Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang and Rong Ge  “Dissecting hessian: Understanding common structure of hessian in neural networks”  In _arXiv preprint arXiv:2010.04261_ , 2020
  * [58] Fan Yang, Hongyang R Zhang, Sen Wu, Weijie J Su and Christopher Ré  “Analysis of Information Transfer from Heterogeneous Sources via Precise High-dimensional Asymptotics”  In _arXiv preprint arXiv:2010.11750_ , 2021
  * [59] Rubing Yang, Jialin Mao and Pratik Chaudhari  “Does the data induce capacity control in deep learning?”  In _International Conference on Machine Learning_ , 2022, pp. 25166–25197  PMLR
  * [60] Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu and Masashi Sugiyama  “Dual t: Reducing estimation error for transition matrix in label-noise learning”  In _NeurIPS_ , 2020
  * [61] Yuan Yao, Lorenzo Rosasco and Andrea Caponnetto  “On early stopping in gradient descent learning”  In _Constructive Approximation_ 26.2 Springer, 2007, pp. 289–315
  * [62] Zhewei Yao, Amir Gholami, Kurt Keutzer and Michael W Mahoney  “Pyhessian: Neural networks through the lens of the hessian”  In _IEEE International Conference on Big Data_ , 2020
  * [63] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals  “Understanding deep learning requires rethinking generalization”  In _ICLR_ , 2017
  * [64] Mingyuan Zhang, Jane Lee and Shivani Agarwal  “Learning from noisy labels with no change to the training process”  In _International Conference on Machine Learning_ , 2021, pp. 12468–12478  PMLR

## References

  * [65] Dana Angluin and Philip Laird  “Learning from noisy examples”  In _Machine Learning_ Springer, 1988
  * [66] David A McAllester  “PAC-Bayesian model averaging”  In _Proceedings of the twelfth annual conference on Computational learning theory_ , 1999
  * [67] David A McAllester  “Some pac-bayesian theorems”  In _Machine Learning_ Springer, 1999
  * [68] Sanjoy Dasgupta, Michael Littman and David McAllester  “PAC generalization bounds for co-training”  In _Advances in neural information processing systems_ 14, 2001
  * [69] Shai Ben-David, Johannes Gehrke and Reba Schuller  “A theoretical framework for learning from a pool of disparate data sources”  In _KDD_ , 2002
  * [70] Yuan Yao, Lorenzo Rosasco and Andrea Caponnetto  “On early stopping in gradient descent learning”  In _Constructive Approximation_ 26.2 Springer, 2007, pp. 289–315
  * [71] Shai Ben-David and Reba Schuller Borbely  “A notion of task relatedness yielding provable multiple-task learning guarantees”  In _Machine learning_ 73.3 Springer, 2008, pp. 273–287
  * [72] Koby Crammer, Michael Kearns and Jennifer Wortman  “Learning from Multiple Sources”  In _Journal of Machine Learning Research_ 9.8, 2008
  * [73] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira and Jennifer Wortman Vaughan  “A theory of learning from different domains”  In _Machine learning_ , 2010
  * [74] David A McAllester  “A PAC-Bayesian tutorial with a dropout bound”  In _arXiv preprint arXiv:1307.2118_ , 2013
  * [75] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar and Ambuj Tewari  “Learning with noisy labels”  In _Advances in neural information processing systems_ , 2013
  * [76] Tongliang Liu and Dacheng Tao  “Classification with noisy labels by importance reweighting”  In _IEEE Transactions on pattern analysis and machine intelligence_ IEEE, 2015
  * [77] Levent Sagun, Leon Bottou and Yann LeCun  “Eigenvalues of the hessian in deep learning: Singularity and beyond”  In _arXiv preprint arXiv:1611.07476_ , 2016
  * [78] Antonio Valerio Miceli Barone, Barry Haddow, Ulrich Germann and Rico Sennrich  “Regularization techniques for fine-tuning in neural machine translation”  In _EMNLP_ , 2017
  * [79] Peter Bartlett, Dylan J Foster and Matus Telgarsky  “Spectrally-normalized margin bounds for neural networks”  In _Neural Information Processing Systems_ , 2017
  * [80] Gintare Karolina Dziugaite and Daniel M Roy  “Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data”  In _UAI_ , 2017
  * [81] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar and Ambuj Tewari  “Cost-Sensitive Learning with Noisy Labels.”  In _J. Mach. Learn. Res._ , 2017
  * [82] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock and Lizhen Qu  “Making deep neural networks robust to label noise: A loss correction approach”  In _CVPR_ , 2017
  * [83] Konstantinos Pitas, Mike Davies and Pierre Vandergheynst  “Pac-bayesian margin bounds for convolutional neural networks”  In _arXiv preprint arXiv:1801.00171_ , 2017
  * [84] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals  “Understanding deep learning requires rethinking generalization”  In _ICLR_ , 2017
  * [85] Sanjeev Arora, Rong Ge, Behnam Neyshabur and Yi Zhang  “Stronger generalization bounds for deep nets via a compression approach”  In _International Conference on Machine Learning_ , 2018
  * [86] Vaishnavh Nagarajan and Zico Kolter  “Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience”  In _International Conference on Learning Representations_ , 2018
  * [87] Behnam Neyshabur, Srinadh Bhojanapalli and Nathan Srebro  “A pac-bayesian approach to spectrally-normalized margin bounds for neural networks”  In _ICLR_ , 2018
  * [88] Vardan Papyan  “The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size”  In _arXiv preprint arXiv:1811.07062_ , 2018
  * [89] Peter L Bartlett, Nick Harvey, Christopher Liaw and Abbas Mehrabian  “Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks”  In _The Journal of Machine Learning Research_ JMLR. org, 2019
  * [90] Behrooz Ghorbani, Shankar Krishnan and Ying Xiao  “An investigation into neural net optimization via hessian eigenvalue density”  In _International Conference on Machine Learning_ , 2019
  * [91] Benjamin Guedj  “A Primer on PAC-Bayesian Learning”  In _Proceedings of the French Mathematical Society_ 33, 2019, pp. 391–414  Société Mathématique de France
  * [92] Steve Hanneke and Samory Kpotufe  “On the value of target data in transfer learning”  In _NeurIPS_ , 2019
  * [93] Vaishnavh Nagarajan and J Zico Kolter  “Generalization in deep networks: The role of distance from initialization”  In _arXiv preprint arXiv:1901.01672_ , 2019
  * [94] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun and Nathan Srebro  “Towards understanding the role of over-parametrization in generalization of neural networks”  In _ICLR_ , 2019
  * [95] Vardan Papyan  “Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians”  In _ICML_ , 2019
  * [96] Martin J Wainwright  “High-dimensional statistics: A non-asymptotic viewpoint”  Cambridge University Press, 2019
  * [97] Lang Huang, Chao Zhang and Hongyang Zhang  “Self-adaptive training: beyond empirical risk minimization”  In _NeurIPS_ , 2020
  * [98] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan and Samy Bengio  “Fantastic generalization measures and where to find them”  In _ICLR_ , 2020
  * [99] Mingchen Li, Mahdi Soltanolkotabi and Samet Oymak  “Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks”  In _AISTATS_ , 2020
  * [100] Sheng Liu, Jonathan Niles-Weed, Narges Razavian and Carlos Fernandez-Granda  “Early-learning regularization prevents memorization of noisy labels”  In _NeurIPS_ , 2020
  * [101] Philip M Long and Hanie Sedghi  “Generalization bounds for deep convolutional neural networks”  In _ICLR_ , 2020
  * [102] Michal Lukasik, Srinadh Bhojanapalli, Aditya Menon and Sanjiv Kumar  “Does label smoothing mitigate label noise?”  In _International Conference on Machine Learning_ , 2020, pp. 6448–6458  PMLR
  * [103] Xingjun Ma, Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani and James Bailey  “Normalized loss functions for deep learning with noisy labels”  In _International Conference on Machine Learning_ , 2020
  * [104] Behnam Neyshabur, Hanie Sedghi and Chiyuan Zhang  “What is being transferred in transfer learning?”  In _NeurIPS_ , 2020
  * [105] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang and Colin Raffel  “Fixmatch: Simplifying semi-supervised learning with consistency and confidence”  In _NeurIPS_ , 2020
  * [106] Nilesh Tripuraneni, Michael Jordan and Chi Jin  “On the theory of transfer learning: The importance of task diversity”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 7852–7862
  * [107] Yusuke Tsuzuku, Issei Sato and Masashi Sugiyama  “Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using pac-bayesian analysis”  In _ICML_ , 2020
  * [108] Tu Vu, Tong Wang, Tsendsuren Munkhdalai, Alessandro Sordoni, Adam Trischler, Andrew Mattarella-Micke, Subhransu Maji and Mohit Iyyer  “Exploring and predicting transferability across NLP tasks”  In _EMNLP_ , 2020
  * [109] Colin Wei and Tengyu Ma  “Improved sample complexities for deep neural networks and robust classification via an all-layer margin”  In _International Conference on Learning Representations_ , 2020
  * [110] Sen Wu, Hongyang R Zhang and Christopher Ré  “Understanding and improving information transfer in multi-task learning”  In _ICLR_ , 2020
  * [111] Sen Wu, Hongyang R Zhang, Gregory Valiant and Christopher Ré  “On the generalization effects of linear transformations in data augmentation”  In _International Conference on Machine Learning_ , 2020  PMLR
  * [112] Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang and Rong Ge  “Dissecting hessian: Understanding common structure of hessian in neural networks”  In _arXiv preprint arXiv:2010.04261_ , 2020
  * [113] Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu and Masashi Sugiyama  “Dual t: Reducing estimation error for transition matrix in label-noise learning”  In _NeurIPS_ , 2020
  * [114] Zhewei Yao, Amir Gholami, Kurt Keutzer and Michael W Mahoney  “Pyhessian: Neural networks through the lens of the hessian”  In _IEEE International Conference on Big Data_ , 2020
  * [115] Sanjeev Arora  “Technical perspective: Why don’t today’s deep nets overfit to their training data?”  In _Communications of the ACM_ 64.3 ACM New York, NY, USA, 2021, pp. 106–106
  * [116] Evangelos Chatzipantazis, Stefanos Pertigkiozoglou, Edgar Dobriban and Kostas Daniilidis  “Learning Augmentation Distributions using Transformed Risk Minimization”  In _arXiv preprint arXiv:2111.08190_ , 2021
  * [117] Erik Englesson and Hossein Azizpour  “Generalized Jensen-Shannon Divergence Loss for Learning with Noisy Labels”  In _Neural Information Processing Systems_ , 2021
  * [118] Pierre Foret, Ariel Kleiner, Hossein Mobahi and Behnam Neyshabur  “Sharpness-aware minimization for efficiently improving generalization”  In _ICLR_ , 2021
  * [119] Henry Gouk, Timothy M Hospedales and Massimiliano Pontil  “Distance-Based Regularisation of Deep Networks for Fine-Tuning”  In _ICLR_ , 2021
  * [120] Moritz Hardt and Benjamin Recht  “Patterns, predictions, and actions: A story about machine learning”  In _arXiv preprint arXiv:2102.05242_ , 2021
  * [121] Qi Lei, Wei Hu and Jason Lee  “Near-optimal linear regression under distribution shift”  In _ICML_ , 2021
  * [122] Dongyue Li and Hongyang Zhang  “Improved Regularization and Robustness for Fine-tuning in Neural Networks”  In _NeurIPS_ , 2021
  * [123] Renjie Liao, Raquel Urtasun and Richard Zemel  “A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks”  In _ICLR_ , 2021
  * [124] Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach and Eli Upfal  “Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees”  In _ICML_ , 2021
  * [125] Gal Shachaf, Alon Brutzkus and Amir Globerson  “A Theoretical Analysis of Fine-tuning with Linear Teachers”  In _Advances in Neural Information Processing Systems_ , 2021
  * [126] Fan Yang, Hongyang R Zhang, Sen Wu, Weijie J Su and Christopher Ré  “Analysis of Information Transfer from Heterogeneous Sources via Precise High-dimensional Asymptotics”  In _arXiv preprint arXiv:2010.11750_ , 2021
  * [127] Mingyuan Zhang, Jane Lee and Shivani Agarwal  “Learning from noisy labels with no change to the training process”  In _International Conference on Machine Learning_ , 2021, pp. 12468–12478  PMLR
  * [128] Rubing Yang, Jialin Mao and Pratik Chaudhari  “Does the data induce capacity control in deep learning?”  In _International Conference on Machine Learning_ , 2022, pp. 25166–25197  PMLR

##  Appendix A Proofs

We will analyze the generalization performance of fine-tuning using PAC-
Bayesian analysis. One chooses a prior distribution, denoted as $\mathcal{P}$,
and a posterior distribution, denoted as $\mathcal{Q}$. The perturbed
empirical loss of $f_{W}$, denoted by
$\hat{\mathcal{L}}_{\mathcal{Q}}(f_{W})$, is the average of
$\ell_{\mathcal{Q}}(f_{U}(x),y)$ over the training dataset. The perturbed
expected loss of $f_{W}$, denoted by ${\mathcal{L}}_{\mathcal{Q}}(f_{W})$, is
the expectation of ${\ell_{\mathcal{Q}}(f_{W}(x),y)}$, for a sample $x$ drawn
from $\mathcal{D}$ with class label $y$. We will use the following PAC-Bayes
bound from Theorem 2, [74].

######  Theorem A.1.

Suppose the loss function $\ell(x,y)$ lies in a bounded range $[0,C]$ given
any $x\in\mathcal{X}$ with label $y$. For any $\beta\in(0,1)$ and
$\delta\in(0,1]$, with probability at least $1-\delta$, the following holds

$\mathcal{L}_{\mathcal{Q}}(f_{W})\leq\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{W})+\frac{C\Big{(}KL(\mathcal{Q}||\mathcal{P})+\log\frac{1}{\delta}\Big{)}}{2\beta(1-\beta)n}.$
(11)

This result provides a flexibility in setting $\beta$. Our results will set
$\beta$ to balance the perturbation error of $\mathcal{Q}$ and the KL
divergence between $\mathcal{P}$ and $\mathcal{Q}$. We will need the KL
divergence between the prior $\mathcal{P}$ and the posterior $\mathcal{Q}$ in
the PAC-Bayesian analysis. This is stated in the following result.

######  Proposition A.2.

Suppose the noise perturbation at layer $i$ is drawn from a Gaussian
distribution with mean zero and covariance $\Sigma_{i}$, for every
$i=1,\dots,L$. Then, the KL divergence between $\mathcal{P}$ and $\mathcal{Q}$
is equal to

$\displaystyle
KL(\mathcal{Q}||\mathcal{P})=\frac{1}{2}\sum_{i=1}^{L}{\bm{\mathrm{vec}}}(W_{i}-\hat{W}_{i}^{(s)})^{\top}\Sigma_{i}^{-1}{\bm{\mathrm{vec}}}(W_{i}-\hat{W}_{i}^{(s)}).$

As a corollary, if the population covariance of the noise distribution at
every layer is isotropic, i.e., $\Sigma_{i}=\sigma_{i}^{2}\operatorname{Id}$,
for any $i=1,\dots,L$, then the KL divergence between $\mathcal{P}$ and
$\mathcal{Q}$ is equal to

$\displaystyle
KL(\mathcal{Q}||\mathcal{P})=\sum_{i=1}^{L}\frac{\|W_{i}-\hat{W}_{i}^{(s)}\|_{F}^{2}}{2\sigma^{2}_{i}}.$

###### Proof.

The proof is based on the definition of multivariate normal distributions. Let
$Z_{i}$ be the weight matrix of every layer $i$ in the posterior distribution,
for $i$ from $1$ to $L$. By the definition of the KL divergence between two
distributions, we have

$\displaystyle
KL(\mathcal{Q}||\mathcal{P})=\mathop{\mathbb{E}}_{Z\sim\mathcal{Q}}\left[\log\Big{(}\frac{\mathcal{Q}(Z)}{\mathcal{P}(Z)}\Big{)}\right]=\mathop{\mathbb{E}}_{Z\sim\mathcal{Q}}\left[\log\mathcal{Q}(Z)-\log\mathcal{P}(Z)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{Z\sim\mathcal{Q}}\left[\sum_{i=1}^{L}-\frac{1}{2}{\bm{\mathrm{vec}}}(Z_{i}-W_{i})^{\top}\Sigma_{i}^{-1}{\bm{\mathrm{vec}}}(Z_{i}-W_{i})+\frac{1}{2}{\bm{\mathrm{vec}}}(Z_{i}-\hat{W}_{i}^{(s)})^{\top}\Sigma_{i}^{-1}{\bm{\mathrm{vec}}}(Z_{i}-\hat{W}_{i}^{(s)})\right]$
$\displaystyle=$
$\displaystyle-\frac{1}{2}\mathop{\mathbb{E}}_{Z\sim\mathcal{Q}}\left[\sum_{i=1}^{L}\operatorname{Tr}\left[{\bm{\mathrm{vec}}}(Z_{i}-W_{i}){\bm{\mathrm{vec}}}(Z_{i}-W_{i})^{\top}\Sigma_{i}^{-1}\right]-\operatorname{Tr}\left[{\bm{\mathrm{vec}}}(Z_{i}-\hat{W}_{i}^{(s)}){\bm{\mathrm{vec}}}(Z_{i}-\hat{W}_{i}^{(s)})^{\top}\Sigma_{i}^{-1}\right]\right].$

In the above equation, we recall that the expectation of $Z_{i}$ is $W_{i}$.
Additionally, the population covariance of $Z_{i}$ is $\Sigma_{i}$. Therefore,
after cancelling out common terms, we get

$\displaystyle
KL(\mathcal{Q}||\mathcal{P})=\sum_{i=1}^{L}\frac{1}{2}{\bm{\mathrm{vec}}}(W_{i}-\hat{W}_{i}^{(s)})^{\top}\Sigma_{i}^{-1}{\bm{\mathrm{vec}}}(W_{i}-\hat{W}_{i}^{(s)}).$

The proof is complete. ∎

As stated in Theorem 2.1, we require the activation functions
$\phi_{i}(\cdot)$ (for any $1\leq i\leq L$) and loss function
$\ell(\cdot,\cdot)$ to be twice-differentiable. Additionally, we require that
they are Lipschitz-continuous. For brevity, We restate these conditions below.

######  Assumption A.3.

Assume that the activation functions $\phi_{i}(\cdot)$ (for any $1\leq i\leq
L$) and the loss function $\ell(\cdot,\cdot)$ over the first argument are
twice-differentiable and $\kappa_{0}$-Lipschitz. Their first-order derivatives
are $\kappa_{1}$-Lipschitz and their second-order derivatives are
$\kappa_{2}$-Lipschitz.

We give several examples of these Lipschitz constants for commonly used
activation functions.

######  Example A.4.

For the Sigmoid function $S(x)$, we have $S(x)\in(0,1)$ for any $x\in\real$.
Since the derivative of the Sigmoid function $S^{\prime}(x)=S(x)(1-S(x))$, we
get that $\kappa_{0}$, $\kappa_{1}$, and $\kappa_{2}$ are at most 1/4.

For the Tanh function $\text{Tanh}(x)$, we have $\text{Tanh}(x)\in(-1,1)$ for
any $x\in\real$. Since the derivative of the Tanh function satisfies
$\text{Tanh}^{\prime}(x)=1-(\text{Tanh}(x))^{2}$, we get that $\kappa_{0}$,
$\kappa_{1}$, and $\kappa_{2}$ are at most 1.

For the GELU function $\text{GELU}(x)$, we have $\text{GELU}(x)=x\cdot F(x)$
where $F(x)$ be the cumulative density function (CDF) of the standard normal
distribution. Let $p(x)$ be the probability density function (PDF) of the
standard normal distribution. We have that $F^{\prime}(x)=p(x)$ and
$p^{\prime}(x)=-xp(x)$. Then, we can get that $\kappa_{0}$, $\kappa_{1}$, and
$\kappa_{2}$ at most $1+e^{-1/2}/\sqrt{2\pi}\approx 1.242$.

###  A.1 Proof of Theorem 2.1

###### Proof of Theorem 2.1.

First, we separate the gap of $\mathcal{L}(f_{\hat{W}})$ and
$\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})$ into three parts:

$\displaystyle\mathcal{L}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})=\mathcal{L}(f_{\hat{W}})-\mathcal{L}_{\mathcal{Q}}(f_{\hat{W}})+\mathcal{L}_{\mathcal{Q}}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})+\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}}).$

By the Taylor’s expansion of Lemma 2.3, we can bound the noise stability of
$f_{\hat{W}}(x)$ with respect to the empirical loss and the expected loss:

$\displaystyle\mathcal{L}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})\leq$
$\displaystyle\Bigg{(}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\Big{\rangle}\right]+\sum_{i=1}^{L}C_{1}\left\|\Sigma_{i}\right\|_{F}^{3/2}\Bigg{)}$
$\displaystyle+\Bigg{(}\mathcal{L}_{\mathcal{Q}}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})\Bigg{)}+\frac{1}{\beta}\Bigg{(}\frac{1}{n}\sum_{i=1}^{L}\sum_{j=1}^{n}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\Big{\rangle}+\sum_{i=1}^{L}C_{1}\left\|\Sigma_{i}\right\|_{F}^{3/2}\Bigg{)},$

which is equivalent to the following equation:

$\displaystyle\mathcal{L}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})\leq$
$\displaystyle\Bigg{(}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\Big{\rangle}\right]+\frac{1}{n\beta}\sum_{i=1}^{L}\sum_{j=1}^{n}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\Big{\rangle}\Bigg{)}$
$\displaystyle+\Big{(}\frac{1}{\beta}+1\Big{)}\sum_{i=1}^{L}C_{1}\left\|\Sigma_{i}\right\|_{F}^{3/2}+\Big{(}\mathcal{L}_{\mathcal{Q}}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})\Big{)}.$
(12)

Next, we combine the upper bound of the noise stability of $f_{\hat{W}}(x)$
with respect to the empirical loss and the expected loss:

$\displaystyle\frac{1}{n\beta}\sum_{i=1}^{L}\sum_{j=1}^{n}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\Big{\rangle}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\Big{\rangle}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{\beta}\sum_{i=1}^{L}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\langle\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\Big{\rangle}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\langle\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\Big{\rangle}\right]\Bigg{)}$
(13)
$\displaystyle+\Big{(}\frac{1}{\beta}-1\Big{)}\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\right]\Big{\rangle}.$

We use the uniform convergence result of Lemma 2.4 to bound equation (13),
leading to:

$\displaystyle\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}(\ell[f_{\hat{W}}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\right]\Big{\rangle}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\right]\right\|_{F}$
$\displaystyle\leq$
$\displaystyle\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}.$
(14)

Recall that $v_{i}$ is a flatten vector of the matrix
$\hat{W}_{i}-\hat{W}_{i}^{(s)}$. By the PAC-Bayes bound of Theorem A.1 and the
KL divergence result of Proposition A.2,

$\displaystyle\mathcal{L}_{\mathcal{Q}}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})\leq\frac{C\big{(}KL(\mathcal{Q}||\mathcal{P})+\log\frac{1}{\delta}\big{)}}{2\beta(1-\beta)n}\leq\frac{C\Big{(}\frac{1}{2}\sum_{i=1}^{L}\langle
v_{i},\Sigma_{i}^{-1}v_{i}\rangle+\log\frac{1}{\delta}\Big{)}}{2\beta(1-\beta)n}.$
(15)

Combining equations (12), (14), (15) with probability at least $1-2\delta$, we
get

$\displaystyle\mathcal{L}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})\leq$
$\displaystyle\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\beta\sqrt{n}}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}+\Big{(}\frac{1}{\beta}-1\Big{)}\sum_{i=1}^{L}\Big{\langle}\Sigma_{i},\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),y_{j})]\right]\Big{\rangle}$
$\displaystyle+\Big{(}\frac{1}{\beta}+1\Big{)}C_{1}\sum_{j=1}^{L}\left\|\Sigma_{i}\right\|_{F}^{3/2}+\frac{C(\frac{1}{2}\sum_{i=1}^{L}\langle
v_{i},\Sigma_{i}^{-1}v_{i}\rangle+\log\frac{1}{\delta})}{2\beta(1-\beta)n}.$

Recall the truncated Hessian $\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]$ is
equal to $U_{i}\max(D_{i},0)U_{i}^{T}$, where $U_{i}D_{i}U_{i}^{T}$ is the
eigendecomposition of $\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]$. Notice that

$\displaystyle\big{\langle}\Sigma_{i},\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\big{\rangle}\leq\big{\langle}\Sigma_{i},\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\big{\rangle},$

for any $(x,y)\sim\mathcal{D}$. Thus, the above inequality holds after taking
an expectation over $(x,y)\sim\mathcal{D}$ on both sides. Next, the upper
bound of
$\mathcal{L}(f_{\hat{W}})-\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})$
relies on $\Sigma_{i}$ and $\beta$. Our goal is to select $\Sigma_{i}$ and
$\beta\in(0,1)$ so that this quantity is minimized. For any $x\in\mathcal{X}$,
let $\Sigma_{i}$ be the matrix that satisfies:

$\displaystyle\Big{(}\frac{1}{\beta}-1\Big{)}\big{\langle}\Sigma_{i},{\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\right]}\big{\rangle}=\frac{C\langle
v_{i},\Sigma_{i}^{-1}v_{i}\rangle}{4\beta(1-\beta)n},$ (16)

which implies

$\displaystyle\Sigma_{i}=\sqrt{\frac{C}{4(1-\beta)^{2}n\|v_{i}\|^{2}}}\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\right]^{-\frac{1}{2}}v_{i}v_{i}^{\top}.$
(17)

If the truncated Hessian is zero, then $\Sigma_{i}$ is set as zero. Next, we
substitute $\Sigma_{i}$ into equation (16) and get:

$\displaystyle\Big{(}\frac{1}{\beta}-1\Big{)}\big{\langle}\Sigma_{i},\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}(\ell(f_{\hat{W}}(x),y))\right]\big{\rangle}=$
$\displaystyle\frac{C\langle
v_{i},\Sigma_{i}^{-1}v_{i}\rangle}{4\beta(1-\beta)n}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{C}{4\beta^{2}n\|v_{i}\|^{2}}}\Big{\langle}\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\right]^{\frac{1}{2}},v_{i}v_{i}^{\top}\Big{\rangle}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{C}{4\beta^{2}n\|v_{i}\|^{2}}}\left\|\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\right]^{\frac{1}{2}}v_{i}\right\|\cdot\|v_{i}\|$
$\displaystyle=$ $\displaystyle\sqrt{\frac{C\cdot
v_{i}^{\top}\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}^{+}[\ell(f_{\hat{W}}(x),y)]\right]v_{i}}{4\beta^{2}n}}\leq\sqrt{\frac{C\mathcal{H}_{i}}{4\beta^{2}n}}.$

Thus, we have shown that equation (16) is less than
$\sqrt{\frac{C\mathcal{H}_{i}}{4\beta^{2}n}}$. Next, the gap between
$\mathcal{L}(f_{\hat{W}})$ and $\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})$
is

$\displaystyle\mathcal{L}(f_{\hat{W}})\leq$
$\displaystyle\Bigg{(}\frac{1}{\beta}\hat{\mathcal{L}}(f_{\hat{W}})+\sum_{i=1}^{L}\sqrt{\frac{C\mathcal{H}_{i}}{\beta^{2}n}}\Bigg{)}$
$\displaystyle+\Bigg{(}\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\beta\sqrt{n}}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}+\Big{(}1+\frac{1}{\beta}\Big{)}C_{1}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}^{3/2}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}\Bigg{)}.$
(18)

Based on equation (18), we set $\epsilon=(1-\beta)/\beta$. Then we have

$\displaystyle\mathcal{L}(f_{\hat{W}})\leq$
$\displaystyle(1+\epsilon)\Big{(}\hat{\mathcal{L}}(f_{\hat{W}})+\sum_{i=1}^{L}\sqrt{\frac{C\mathcal{H}_{i}}{n}}\Big{)}$
$\displaystyle+\Bigg{(}\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\beta\sqrt{n}}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}+\Big{(}1+\frac{1}{\beta}\Big{)}C_{1}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}^{3/2}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}\Bigg{)}.$

Let $\xi$ be defined as follows:

$\displaystyle\xi=\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\beta\sqrt{n}}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}+\Big{(}1+\frac{1}{\beta}\Big{)}C_{1}\sum_{i=1}^{L}\left\|\Sigma_{i}\right\|_{F}^{3/2}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}=O\Big{(}n^{-3/4}\Big{)},$

where we use the fact that
$\left\|\Sigma_{i}\right\|_{F}=O\left(n^{-1/2}\right)$ from equation (17).
Hence, we conclude that:

$\displaystyle\mathcal{L}(f_{\hat{W}})\leq(1+\epsilon)\hat{\mathcal{L}}(f_{\hat{W}})+(1+\epsilon)\sum_{i=1}^{L}\sqrt{\frac{C\mathcal{H}_{i}}{n}}+\xi.$

Thus, we have shown that equation (3) holds. The proof is now finished. ∎

##### Remark.

The proof of this theorem bears resemblance to a classical result about PAC-
Bayes bounds for Lipschitz functions.111See, e.g., Example 4.4 of John Duchi’s
lecture notes: https://web.stanford.edu/class/stats311/lecture-notes.pdf. The
analysis crucially relies on the condition that the activation functions and
their derivatives are Lipschitz-continuous. The crux of this analysis is
showing the layerwise Hessian decomposition of the generalization gap. Notice
that similar Hessian measures have appeared in several prior and concurrent
works [107, 128]. Mathematically formulating these ideas requires deal with
several technical challenges as discussed in Section 2.4.

###  A.2 Proof of Theorem 2.2

###### Proof of Theorem 2.2.

By equation (6), we have the expected loss of $f_{\hat{W}}$ using $\bar{\ell}$
as

$\mathcal{L}(f_{\hat{W}})=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\bar{\ell}(f_{\hat{W}}(x),y)\right]=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D},\tilde{y}|y}\left[\bar{\ell}(f_{\hat{W}}(x),\tilde{y})\right].$

Denote the empirical loss of $f_{\hat{W}}$ using $\bar{\ell}$ as

$\bar{\mathcal{L}}(f_{\hat{W}})=\frac{1}{n}\sum_{i=1}^{n}\bar{\ell}(f_{\hat{W}}(x_{i}),\tilde{y}_{i}).$

We separate the gap between $\mathcal{L}\big{(}f_{\hat{W}}\big{)}$ and
$\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}$ into three parts:

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}\leq\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}+\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}+\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}.$

We denote $\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x),\tilde{y})$ as an
expectation of $\bar{\ell}(f_{\hat{W}}(x),\tilde{y})$ under the posterior
$\mathcal{Q}$. Define $\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}$ as
$\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D},\tilde{y}|y}\left[\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x),\tilde{y})\right]$.
Define $\bar{\mathcal{L}}_{\mathcal{Q}}(f_{\hat{W}})$ as
$\frac{1}{n}\sum_{i=1}^{n}\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x_{i}),\tilde{y}_{i})$.
By equation (6), we have

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D},\tilde{y}|y}\left[\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x),\tilde{y})-\bar{\ell}(f_{\hat{W}}(x),\tilde{y})\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathop{\mathbb{E}}_{\tilde{y}|y}\left[\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x),\tilde{y})-\bar{\ell}(f_{\hat{W}}(x),\tilde{y})\right]\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\ell_{\mathcal{Q}}(f_{\hat{W}}(x),y)-\ell(f_{\hat{W}}(x),y)\right].$

Then, by equation (5), the noise stability of $f_{\hat{W}}$ with respect to
the empirical loss is equal to

$\displaystyle\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}=$
$\displaystyle\frac{1}{n\beta}\sum_{j=1}^{n}\bar{\ell}_{\mathcal{Q}}(f_{\hat{W}}(x_{j}),\tilde{y}_{j})-\frac{1}{n\beta}\sum_{j=1}^{n}\bar{\ell}(f_{\hat{W}}(x_{j}),\tilde{y}_{j})$
$\displaystyle=$
$\displaystyle\frac{1}{n\beta}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\Bigg{(}\sum_{j=1}^{n}\big{(}\ell_{\mathcal{Q}}(f_{\hat{W}}(x_{j}),l)-\ell(f_{\hat{W}}(x_{j}),l)\big{)}\Bigg{)}.$

By the Taylor’s expansion of Lemma 2.3, we can bound the noise stability of
$f_{\hat{W}}$ with respect to the empirical loss and the expected loss:

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}\leq$
$\displaystyle\Bigg{(}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\sigma_{i}^{2}\operatorname{Tr}\big{[}\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\big{]}\right]+\sum_{i=1}^{L}C_{1}\sigma_{i}^{3}\Bigg{)}+\Big{(}\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}\Big{)}$
$\displaystyle+\frac{1}{\beta}\Bigg{(}\frac{1}{n}\sum_{i=1}^{L}\sigma_{i}^{2}\Big{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\big{(}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]\big{)}\Big{)}+\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\sum_{i=1}^{L}C_{1}\sigma_{i}^{3}\Bigg{)},$

which is equivalent to the following equation:

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}\leq$
$\displaystyle\Bigg{(}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\sigma_{i}^{2}\operatorname{Tr}\big{[}\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\big{]}\right]+\frac{1}{n\beta}\sum_{i=1}^{L}\sigma_{i}^{2}\Big{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\big{(}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]\big{)}\Big{)}\Bigg{)}$
$\displaystyle+\Bigg{(}\sum_{i=1}^{L}C_{1}\sigma_{i}^{3}+\frac{1}{\beta}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\sum_{i=1}^{L}C_{1}\sigma_{i}^{3}\Bigg{)}+\Big{(}\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}\Big{)}.$
(19)

Next, we combine the upper bound of the noise stability of $f_{\hat{W}}(x)$
with respect to the empirical loss and the expected loss:

$\displaystyle\frac{1}{n\beta}\sum_{i=1}^{L}\sigma_{i}^{2}\Big{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\big{(}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]\big{)}\Big{)}-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\sum_{i=1}^{L}\sigma_{i}^{2}\operatorname{Tr}\big{[}\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\big{]}\right]$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{L}\sigma_{i}^{2}\Bigg{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\Big{(}\frac{1}{n}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\operatorname{Tr}\big{[}\mathbf{H}_{i}[\ell(f_{\hat{W}}(x),y)]\big{]}\right]\Big{)}\Bigg{)}$
(20)
$\displaystyle+\Big{(}\frac{1}{\beta}-1\Big{)}\sum_{i=1}^{L}\sigma_{i}^{2}\Bigg{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\Big{(}\frac{1}{n}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]\Big{)}\Bigg{)}.$
(21)

We use the uniform convergence result of Lemma 2.4 to bound equation (20),
leading to a concentration error term of

$\displaystyle\sum_{i=1}^{L}\sigma_{i}^{2}\max_{\tilde{y}}\sum_{j=1}^{L}{\left|{\Lambda_{\tilde{y},j}}\right|}\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}=\frac{C_{2}\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\sigma_{i}^{2}\rho.$
(22)

For equation (21), the upper bound will be

$\displaystyle\Big{(}\frac{1}{\beta}-1\Big{)}\sum_{i=1}^{L}\sigma_{i}^{2}\Bigg{(}\sum_{l=1}^{k}\Lambda_{\tilde{y},l}\Big{(}\frac{1}{n}\sum_{j=1}^{n}\operatorname{Tr}\left[\mathbf{H}_{i}[\ell(f_{\hat{W}}(x_{j}),l)]\right]\Big{)}\Bigg{)}\leq\Big{(}\frac{1}{\beta}-1\Big{)}\sum_{i=1}^{L}\sigma_{i}^{2}\rho\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert,$
(23)

where $\rho=\|\Lambda^{\top}\|_{1,\infty}$. Recall that $v_{i}$ is a flatten
vector of the matrix $\hat{W_{i}}-\hat{W_{i}}^{(s)}$. By the PAC-Bayes bound
of Theorem A.1 and Proposition A.2,

$\displaystyle\mathcal{L}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}_{\mathcal{Q}}\big{(}f_{\hat{W}}\big{)}$
$\displaystyle\leq\frac{C\Big{(}KL(\mathcal{Q}||\mathcal{P})+\log\frac{1}{\delta}\Big{)}}{2\beta(1-\beta)n}$
$\displaystyle\leq\frac{C\Big{(}\sum_{i=1}^{L}\frac{\left\|v_{i}\right\|^{2}}{2\sigma_{i}^{2}}+\log\frac{1}{\delta}\Big{)}}{2\beta(1-\beta)n}.$
(24)

Combining equations (19), (23), (24), with probability at least $1-2\delta$,
we get

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}\leq$
$\displaystyle\frac{C_{2}\rho\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\sigma_{i}^{2}+\Big{(}\frac{1}{\beta}-1\Big{)}\rho\sum_{i=1}^{L}\sigma_{i}^{2}\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert$
$\displaystyle+\Big{(}\frac{\rho}{\beta}+1\Big{)}\sum_{j=1}^{L}C_{1}\sigma_{i}^{3}+\frac{C(\sum_{i=1}^{L}\frac{\left\|v_{i}\right\|^{2}}{2\sigma_{i}^{2}}+\log\frac{1}{\delta})}{2\beta(1-\beta)n}.$
(25)

In equation (25), the upper bound of
$\mathcal{L}\big{(}f_{\hat{W}}\big{)}-\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}$
relies on $\sigma_{i}$ and $\beta$. Our goal is to select $\sigma_{i}>0$ and
$\beta\in(0,1)$ to minimize equation (25). This is achieved when:

$\displaystyle\sigma_{i}^{2}=\sqrt{\frac{C\left\|v_{i}\right\|^{2}}{4\rho(1-\beta)^{2}n\cdot\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert}},$
(26)

for any $1\leq i\leq L$, following the condition:

$\displaystyle\Big{(}\frac{1}{\beta}-1\Big{)}\rho\sigma_{i}^{2}\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert=\frac{C}{2\beta(1-\beta)n}\frac{\left\|v_{i}\right\|^{2}}{2\sigma_{i}^{2}}.$

Then, equation (25) becomes

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}\leq$
$\displaystyle\Bigg{(}\frac{1}{\beta}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}+\sum_{i=1}^{L}\sqrt{\frac{C\rho\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert\cdot\left\|v_{i}\right\|^{2}}{\beta^{2}n}}\Bigg{)}$
(27)
$\displaystyle+\Bigg{(}\frac{C_{2}\rho\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\sigma_{i}^{2}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}+\Big{(}\frac{\rho}{\beta}+1\Big{)}C_{1}\sum_{i=1}^{L}\sigma_{i}^{3}\Bigg{)}.$
(28)

Set $\beta$ as a fixed value close to 1 that does not grow with $n$ and
$1/\delta$. Let $\epsilon=(1-\beta)/\beta$. We get

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}\leq$
$\displaystyle(1+\epsilon)\Bigg{(}\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}+\sum_{i=1}^{L}\sqrt{\frac{C\rho\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert\cdot\left\|v_{i}\right\|^{2}}{n}}\Bigg{)}$
$\displaystyle+\Bigg{(}\frac{C_{2}\rho\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\sigma_{i}^{2}+\Big{(}\frac{\rho}{\beta}+1\Big{)}C_{1}\sum_{i=1}^{L}\sigma_{i}^{3}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}\Bigg{)}.$

Let $\xi$ be defined as follows. We have

$\displaystyle\xi=\frac{C_{2}\rho\sqrt{\log(C_{3}n/\delta)}}{\sqrt{n}}\sum_{i=1}^{L}\sigma_{i}^{2}+\Big{(}\frac{\rho}{\beta}+1\Big{)}C_{1}\sum_{i=1}^{L}\sigma_{i}^{3}+\frac{C}{2\beta(1-\beta)n}\log\frac{1}{\delta}=O\Big{(}n^{-3/4}\Big{)},$

where we notice that $\sigma_{i}^{2}=O\left(n^{-1/2}\right)$ because of
equation (26). Thus, we conclude that

$\displaystyle\mathcal{L}\big{(}f_{\hat{W}}\big{)}\leq(1+\epsilon)\bar{\mathcal{L}}\big{(}f_{\hat{W}}\big{)}+(1+\epsilon)\sum_{i=1}^{L}\sqrt{\frac{C\rho\max_{x\in\mathcal{X},y\in\\{1,\dots,k\\}}\left\lvert\operatorname{Tr}[\mathbf{H}_{i}(\ell(f_{\hat{W}}(x),y))]\right\rvert\cdot\left\|v_{i}\right\|^{2}}{n}}+\xi.$

Since $\left\|v_{i}\right\|\leq\alpha_{i}$, for any $i=1,\dots,L$, we have
finished the proof. ∎

###  A.3 Proof of Lemma 2.4

In this section, we provide the proof of Lemma 2.4. We need a perturbation
analysis of the Hessian as follows. Given an $L$-layer neural network
$f_{W}:\mathcal{X}\rightarrow\mathbb{R}^{d_{L}}$ and any input
$z^{0}\in\mathcal{X}$, let $z_{W}^{i}=\phi_{i}(W_{i}z_{W}^{i-1})$ be the
activated output vector from layer $i$, for any $i=1,2,\dots,L$.

We show that the Hessian matrix is Lipschitz-continuous. In particular, there
exists a fixed value $G$ that does not grow with $n$ and $\delta^{-1}$, such
that the changes in the Hessian can be quantified below.

######  Proposition A.5.

Suppose that Assumption A.3 holds. The change in the Hessian of output of the
loss function $\ell(f_{W}(x),y)$ with respect to $W_{i}$ under perturbation
$U$ can be bounded as follows:

$\displaystyle\left\|\mathbf{H}_{i}[\ell(f_{W}(x),y)]\mid_{W_{i}+U_{i},\forall
1\leq i\leq L}-\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right\|_{F}\leq
G\|U\|_{{}_{F}},$ (29)

where $G$ has the following equation:

$\displaystyle
G=\frac{3}{2}(L+1)^{2}e^{6}\kappa_{2}\kappa_{1}^{2}\kappa_{0}^{3(L+1)}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{l=0}^{L}d_{l}\prod_{h=1}^{L}\left\|W_{h}\right\|_{2}\Big{)}^{3}\Big{(}\max_{1\leq
i\leq
L}\frac{1}{\left\|W_{i}\right\|_{2}^{2}}\sum_{h=1}^{L}\frac{1}{\left\|W_{h}\right\|_{2}}\Big{)}.$
(30)

where $\kappa_{0},\kappa_{1},\kappa_{2}\geq 1$ is the maximum over the
Lipschitz constants, first-order derivative Lipschitz constants, and second-
order derivative Lipschitz constants of all the activation functions and the
loss function.

Provided with the Lipschitzness conditions, now we are ready to state the
proof of Lemma 2.4, which shows the uniform convergence of the loss Hessians.

###### Proof of Lemma 2.4.

Let $B$, $\epsilon>0$, $p=\sum_{i=1}^{L}d_{i}d_{i-1}$, and let
$S=\\{\text{vec}(W)\in{}^{p}:\left\|\text{vec}(W)\right\|_{2}\leq B\\}$. Then
there exists an $\epsilon$-cover of $S$ with respect to the $\ell_{2}$-norm at
most $\max\Big{(}\big{(}\frac{3B}{\epsilon}\big{)}^{p},1\Big{)}$ elements from
Example 5.8, [96]. From Proposition A.5, the Hessian
$\mathbf{H}_{i}[\ell(f_{W}(x),y)]$ is $G$-Lipschitz for all $(W+U),W\in S$ and
any $i=1,2,\cdots,L$. Then we have

$\displaystyle\left\|\mathbf{H}_{i}[\ell(f_{W+U}(x),y)]-\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right\|_{F}\leq
G\left\|U\right\|_{F},$

where $G$ is defined in equation (30). We will follow the proof in the lecture
notes of Ma
(2021).222https://raw.githubusercontent.com/tengyuma/cs229m_notes/main/master.pdf
For parameters $\delta,\epsilon>0$, let $\mathcal{N}$ be the $\epsilon$-cover
of $S$ with respect to the $\ell_{2}$-norm. Define the event

$\displaystyle E=\Big{\\{}\forall
W\in\mathcal{N},\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq\delta\Big{\\}}.$

By the matrix Bernstein inequality,333e.g., Theorem 6.1.1 in Joel Tropp’s
online lecture notes. we have

$\text{Pr}(E)\geq
1-4|\mathcal{N}|d_{i}d_{i-1}\exp(-n\delta^{2}/(2\mathcal{H}_{i}^{2})).$

Next, for any $W\in S$, we can pick some $W+U\in\mathcal{N}$ such that
$\left\|U\right\|_{F}\leq\epsilon$. We have

$\displaystyle\left\|\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W+U}(x),y)]\right]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq
G\left\|U\right\|_{F}\leq G\epsilon,\text{ and}$
$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W+U}(x_{j}),y_{j})]-\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]\right\|_{F}\leq
G\left\|U\right\|_{F}\leq G\epsilon.$

Therefore, for any $W\in S$, we obtain:

$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq
2G\epsilon+\delta.$

We also need to choose the suitable parameter $\delta$ and $\epsilon$. First,
set $\epsilon=\delta/(2G)$ so that conditional on $E$,

$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq
2\delta.$

The event $E$ happens with probability at least:

$\displaystyle
1-4|\mathcal{N}|d_{i}d_{i-1}\exp(-n\delta^{2}/(2\mathcal{H}_{i}^{2}))=1-4d_{i}d_{i-1}\exp(\log|\mathcal{N}|-n\delta^{2}/(2\mathcal{H}_{i}^{2})).$

We have $\log|\mathcal{N}|\leq p\log(3B/\epsilon)=p\log(6BG/\delta)$. If we
set

$\delta=\sqrt{\frac{4p\mathcal{H}_{i}^{2}\log(3\tau BGn/\mathcal{H}_{i})}{n}}$

so that $\log(3\tau BGn/\mathcal{H}_{i})\geq 1$ (because
$n\geq\frac{e\mathcal{H}_{i}}{3BG}$ and $\tau\geq 1$), then we get

$\displaystyle p\log(6BG/\delta)-n\delta^{2}/(2\mathcal{H}_{i}^{2})=\,$
$\displaystyle
p\log\left({\frac{6BG\sqrt{n}}{\sqrt{4p\mathcal{H}_{i}^{2}\log(3\tau
BGn/\mathcal{H}_{i})}}}\right)-2p\log(3\tau BGn/\mathcal{H}_{i})$
$\displaystyle=\,$ $\displaystyle
p\log\left({\frac{3BG\sqrt{n}}{\mathcal{H}_{i}\sqrt{p\log(3\tau
BGn/\mathcal{H}_{i})}}}\right)-2p\log(3\tau BGn/\mathcal{H}_{i})$
$\displaystyle\leq$ $\displaystyle p\log(3\tau
BGn/\mathcal{H}_{i})-2p\log(3\tau BGn/\mathcal{H}_{i})$ ($\tau\geq
1,\log(3\tau BGn/\mathcal{H}_{i})\geq 1$) $\displaystyle=\,$
$\displaystyle-p\log(3\tau BGn/\mathcal{H}_{i})$ $\displaystyle\leq$
$\displaystyle-p\log(e\tau).$ ($3BGn/\mathcal{H}_{i}\geq e$)

Therefore, with probability greater than

$1-4|\mathcal{N}|d_{i}d_{i-1}\exp(-n\delta^{2}/(2\mathcal{H}_{i}^{2}))\geq
1-4d_{i}d_{i-1}(e\tau)^{-p}\geq 1-4d_{i}d_{i-1}/(e\tau),$

the following estimate holds:

$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq\sqrt{\frac{16p\mathcal{H}_{i}^{2}\log(3\tau
BGn/\mathcal{H}_{i})}{n}}.$

Denote $\delta^{\prime}=4d_{i}d_{i-1}/(e\tau)$,
$C_{2}=4\mathcal{H}_{i}\sqrt{p}$, and
$C_{3}=12d_{i}d_{i-1}BG/(e\mathcal{H}_{i})$. With probability greater than
$1-\delta^{\prime}$, the final result is:

$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\mathbf{H}_{i}[\ell(f_{W}(x_{j}),y_{j})]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\mathbf{H}_{i}[\ell(f_{W}(x),y)]\right]\right\|_{F}\leq
C_{2}\sqrt{\frac{\log(C_{3}n/\delta^{\prime})}{n}}.$

This completes the proof of Lemma 2.4. ∎

###  A.4 Proof of Proposition A.5

We divide the proof of Proposition A.5 into several parts. The bulk of the
calculation is devoted to getting an explicit value of $G$.

First, we derive the perturbation of the network output.

######  Claim A.6.

Suppose that Assumption A.3 holds. For any $j=1,2,\cdots,L$, the change in the
output of the $j$ layer network $z_{W}^{j}$ with perturbation $U$ can be
bounded as follows:

$\displaystyle\left\|z_{W+U}^{j}-z_{W}^{j}\right\|\leq\Big{(}1+\frac{1}{L}\Big{)}^{j}\kappa_{0}^{j}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)}.$
(31)

where $\kappa_{0}\geq 1$ is the maximum over the Lipschitz constants of all
the activation functions and the loss function.

See Lemma 2 in [87] for a proof. Second, we derive the perturbation of the
derivative of the network.

######  Claim A.7.

Suppose that Assumption A.3 holds. The change in the Jacobian of output of the
$j$ layer network $z_{W}^{j}$ with respect to $W_{i}$ under perturbation $U$
can be bounded as follows:

$\displaystyle\left\|\frac{\partial}{\partial
W_{i}}z_{W}^{j}\Big{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-\frac{\partial}{\partial W_{i}}z_{W}^{j}\right\|_{F}\leq
A_{i,j}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)}.$
(32)

For any $j=1,2,\cdots,L$, $A_{i,j}$ has the following equation:

$\displaystyle
A_{i,j}=(j-i+2)\Big{(}1+\frac{1}{L}\Big{)}^{3j}\kappa_{1}\kappa_{0}^{2j-1}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{l=i-1}^{j}d_{l}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\Bigg{)},$

where $\kappa_{0},\kappa_{1}\geq 1$ is the maximum over the Lipschitz
constants and first-order derivative Lipschitz constants of all the activation
functions and the loss function.

###### Proof.

For any fixed $i=1,2,\cdots,L$, we will prove using induction with respect to
$j$. If $j<i$, we have $\frac{\partial}{\partial W_{i}}z_{W}^{j}=0$ since
$z_{W}^{j}$ remains unchanged regardless of any change of $W_{i}$. When $j=i$,
we have

$\displaystyle\left\|\frac{\partial}{\partial
W_{i}^{p,q}}z_{W}^{i}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
i}-\frac{\partial}{\partial
W_{i}^{p,q}}z_{W}^{i}\right\|=\left\|\frac{\partial}{\partial
W_{i}^{p,q}}\phi_{i}(W_{i}z_{W}^{i-1})\Bigg{|}_{W_{k}+U_{k},\forall 1\leq
k\leq i}-\frac{\partial}{\partial
W_{i}^{p,q}}\phi_{i}(W_{i}z_{W}^{i-1})\right\|$ $\displaystyle=$
$\displaystyle{\left|{[z^{i-1}_{W+U}]^{q}\phi_{i}^{\prime}\Bigg{(}\sum_{r=1}^{d_{i-1}}\Big{(}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}\Big{)}\Bigg{)}-[z_{W}^{i-1}]^{q}\phi_{i}^{\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|},$

where $W_{i}^{p,q},U_{i}^{p,q}$ are the $(p,q)$’th entry of $W_{i}$ and
$U_{i}$.

Let $[z_{W}^{i-1}]^{q}$ be the $q$’th entry of $z_{W}^{i-1}$. By the triangle
inequality, the above equation is smaller than

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}}\right|}{\left|{\phi_{i}^{\prime}\Big{(}\sum_{r=1}^{d_{i-1}}\Big{(}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}\Big{)}-\phi_{i}^{\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|}$
(33)
$\displaystyle+{\left|{[z_{W+U}^{i-1}]^{q}-[z_{W}^{i-1}]^{q}}\right|}{\left|{\phi_{i}^{\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|}.$
(34)

Since $\phi_{i}^{\prime}$ is $\kappa_{1}$-Lipschitz by Assumption A.3,
equation (33) is at most

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}}\right|}\cdot\kappa_{1}{\left|{\sum_{r=1}^{d_{i-1}}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}-\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}}\right|}.$
(35)

Since Assumption A.3 holds, we have
${\left|{\phi_{i}^{\prime}(\cdot)}\right|}\leq\kappa_{0}$, by the Lipschitz
condition on the first-order derivatives. Thus, equation (34) is at most

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}-[z_{W}^{i-1}]^{q}}\right|}\cdot\kappa_{0}.$
(36)

Taking equation (35) and (36) together, the Frobenius norm of the Jacobian is

$\displaystyle\left\|\frac{\partial}{\partial
W_{i}}z_{W}^{i}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
i}-\frac{\partial}{\partial W_{i}}z_{W}^{i}\right\|_{F}$ $\displaystyle=~{}$
$\displaystyle\sqrt{\sum_{p=1}^{d_{i}}\sum_{q=1}^{d_{i-1}}\left\|\frac{\partial}{\partial
W_{i}^{p,q}}z_{W}^{i}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
i}-\frac{\partial}{\partial W_{i}^{p,q}}z_{W}^{i}\right\|^{2}}$
$\displaystyle\leq~{}$ $\displaystyle d_{i}\left\|z_{W+U}^{i-1}\right\|\cdot
k_{1}d_{i-1}\left\|\big{(}W_{i}+U_{i}\big{)}z_{W+U}^{i-1}-W_{i}z_{W}^{i-1}\right\|+\kappa_{0}d_{i}\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|.$

By the Lipschitz continuity of $z_{W+U}^{i-1}$ and equation (31) in Claim A.6,
we have

$\displaystyle\left\|z_{W+U}^{i-1}\right\|$
$\displaystyle\leq\Big{(}1+\frac{1}{L}\Big{)}^{i-1}\kappa_{0}^{i-1}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}.$
(37) $\displaystyle\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|$
$\displaystyle\leq\Big{(}1+\frac{1}{L}\Big{)}^{i-1}\kappa_{0}^{i-1}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}\sum_{h=1}^{i-1}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}.$
(38)

By the triangle inequality, we have

$\displaystyle\left\|\big{(}W_{i}+U_{i}\big{)}z_{W+U}^{i-1}-W_{i}z_{W}^{i-1}\right\|\leq\left\|W_{i}+U_{i}\right\|_{2}\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|+\left\|U_{i}\right\|_{2}\left\|z_{W}^{i-1}\right\|.$
(39)

From equation (37), (38), and (39), we finally obtain that the Jacobian of
$z_{W}^{i}$ with respect to $W_{i}$ is at most

$\displaystyle\left\|\frac{\partial z_{W}^{i}}{\partial
W_{i}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq i}-\frac{\partial
z_{W}^{i}}{\partial W_{i}}\right\|_{F}$ $\displaystyle\leq$
$\displaystyle\Bigg{(}2\Big{(}1+\frac{1}{L}\Big{)}^{2i-1}\kappa_{1}\kappa_{0}^{2i-1}d_{i}d_{i-1}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}\Bigg{)}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i}\left\|W_{h}\right\|_{2}\sum_{h=1}^{i}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)}.$

Hence, we know that equation (31) will be correct when $j=i$.

Assuming that equation (31) will be correct for any $i$ up to $j\geq i$, we
have

$\displaystyle\left\|\frac{\partial z_{W}^{j}}{\partial
W_{i}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j}-\frac{\partial
z_{W}^{j}}{\partial W_{i}}\right\|_{F}$ $\displaystyle\leq$
$\displaystyle(j-i+2)\Big{(}1+\frac{1}{L}\Big{)}^{3j}\kappa_{1}\kappa_{0}^{2j-1}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{l=i-1}^{j}d_{l}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\Bigg{)}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)}.$

From layer $i$ to layer $j+1$, we show the derivative on
$z_{W}^{j+1}=\phi_{j+1}(W_{j+1}z_{W}^{j})$ with respect to $W_{i}^{p,q}$:

$\displaystyle\frac{\partial\phi_{j+1}(W_{j+1}z_{W}^{j})}{\partial
W_{i}^{p,q}}=\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{)},$

where $\odot$ is the Hadamard product operator between two vectors. Then we
have

$\displaystyle\left\|\frac{\partial z_{W}^{j+1}}{\partial
W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j+1}-\frac{\partial
z_{W}^{j+1}}{\partial W_{i}^{p,q}}\right\|$ $\displaystyle=$
$\displaystyle\left\|\phi_{j+1}^{\prime}\big{(}(W_{j+1}+U_{j+1})z_{W+U}^{j}\big{)}\odot\Bigg{(}(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\Bigg{)}-\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{)}\right\|.$

By the Cauchy-Schwarz inequality and the triangle inequality, the above
equation is at most

$\displaystyle\left\|\phi_{j+1}^{\prime}\big{(}(W_{j+1}+U_{j+1})z_{W+U}^{j}\big{)}-\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\right\|\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\right\|$ (40)
$\displaystyle+\left\|\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\right\|\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-W_{j+1}\frac{\partial z_{W}^{j}}{\partial W_{i}^{p,q}}\right\|.$ (41)

Using the triangle inequality and the $\kappa_{1}$-Lipschitz of
$\phi_{j+1}^{\prime}(\cdot)$, equation (40) is at most

$\displaystyle\kappa_{1}\Big{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|z_{W+U}^{j}-z_{W}^{j}\right\|+\left\|U_{j+1}\right\|_{2}\left\|z_{W}^{j}\right\|\Big{)}\cdot\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\right\|.$

Using the triangle inequality and
$|\phi_{j+1}^{\prime}(\cdot)|\leq\kappa_{0}$, equation (41) is at most

$\displaystyle
d_{j+1}\kappa_{0}\cdot\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-\frac{\partial z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|+\left\|U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\right\|\Bigg{)}.$

From Claim A.6, we have the norm of the derivative of $z_{W}^{j}$ with respect
to $W_{i}^{p,q}$ bounded by its Lipschitzness in equation (31):

$\displaystyle\left\|\frac{\partial z_{W}^{j}}{\partial W_{i}^{p,q}}\right\|$
$\displaystyle\leq(1+\frac{1}{L})^{j}\kappa_{0}^{j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(42) $\displaystyle\left\|\frac{\partial z_{W}^{j}}{\partial
W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j}\right\|$
$\displaystyle\leq(1+\frac{1}{L})^{2j-1}\kappa_{0}^{j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(43)

Then, the Frobenius norm of the Jacobian is at most

$\displaystyle\left\|\frac{\partial z_{W}^{j+1}}{\partial
W_{i}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j+1}-\frac{\partial
z_{W}^{j+1}}{\partial W_{i}}\right\|_{F}$ $\displaystyle\leq$
$\displaystyle~{}d_{i}d_{i-1}\cdot\kappa_{1}\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|z_{W+U}^{j}-z_{W}^{j}\right\|+\left\|U_{j+1}\right\|_{2}\left\|z_{W}^{j}\right\|\Bigg{)}\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\right\|$ (44)
$\displaystyle~{}+d_{j+1}\kappa_{0}\cdot\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-\frac{\partial z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|_{F}+d_{i}d_{i-1}\left\|U_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\right\|\Bigg{)}.$ (45)

From equation (37), (38), (43), we have equation (44) will be at most

$\displaystyle\Big{(}1+\frac{1}{L}\Big{)}^{3j+3}\kappa_{1}\kappa_{0}^{2j+1}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{l=i-1}^{j+1}d_{l}\prod_{h=1}^{j+1}\left\|W_{h}\right\|_{2}\Big{)}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j+1}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j+1}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Big{)}.$
(46)

From the induction and equation (37) and (42), the term in equation (45) will
be at most

$\displaystyle(j-i+2)\Big{(}1+\frac{1}{L}\Big{)}^{3j+3}\kappa_{1}\kappa_{0}^{2j+1}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{l=i-1}^{j+1}d_{l}\prod_{h=1}^{j+1}\left\|W_{h}\right\|_{2}\Big{)}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j+1}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j+1}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Big{)}.$
(47)

After we combine equation (46) and (47), the proof is complete. ∎

####  A.4.1 Lipchitz constant for the Hessian

Based on the above two results, we state the proof of Proposition A.5.

###### Proof of Proposition A.5.

We will prove using induction. Let $z_{W}^{j}$ be an $j$ layer neural network
with parameters $W$. The change in the Hessian of output of the $j$ layer
network $z_{W}^{j}$ with respect to $W_{i}$ under perturbation $U$ can be
bounded as follows:

$\displaystyle\left\|\mathbf{H}_{i}[z_{W}^{j}]\Big{|}_{W_{k}+U_{k},\forall
1\leq k\leq j}-\mathbf{H}_{i}[z_{W}^{j}]\right\|_{F}\leq
G_{i,j}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Big{)}.$
(48)

For any $j=1,2,\cdots,L$, $G_{i,j}$ has the following equation:

$\displaystyle
G_{i,j}=\frac{3}{2}(j-i+2)^{2}\Big{(}1+\frac{1}{L}\Big{)}^{6j}\kappa_{2}\kappa_{1}^{2}\kappa_{0}^{3j-3}\prod_{l=i-1}^{j}d_{l}^{3}\Big{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\Big{)}^{2},$

For any fixed $i=1,2,\cdots,L$, we will prove using induction with respect to
$j$. If $j<i$, we have $\frac{\partial^{2}}{\partial W_{i}^{2}}z_{W}^{j}=0$
since $z_{W}^{j}$ remains unchanged regardless of any change of $W_{i}$. When
$j=i$, we have

$\displaystyle\left\|\frac{\partial^{2}z_{W}^{i}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
i}-\frac{\partial^{2}z_{W}^{i}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}\right\|$ $\displaystyle=$
$\displaystyle{\left|{\big{(}[z^{i-1}_{W+U}]^{q}[z^{i-1}_{W+U}]^{t}\big{)}\phi_{i}^{\prime\prime}\Bigg{(}\sum_{r=1}^{d_{i-1}}\Big{(}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}\Big{)}\Bigg{)}-([z_{W}^{i-1}]^{q}[z_{W}^{i-1}]^{t})\phi_{i}^{\prime\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|},$

where $p=s$. If $p\neq s$, we have $\frac{\partial^{2}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}z_{W}^{i}=0$, where $W_{i}^{p,q},U_{i}^{p,q}$
are the $(p,q)$’th entry of $W_{i}$ and $U_{i}$.

Let $[z_{W}^{i-1}]^{q}$ be the $q$’th entry of $z_{W}^{i-1}$. By the triangle
inequality, the above equation is at most

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}}\right|}{\left|{\phi_{i}^{\prime\prime}\Big{(}\sum_{r=1}^{d_{i-1}}\Big{(}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}\Big{)}-\phi_{i}^{\prime\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|}$
(49)
$\displaystyle+{\left|{[z_{W+U}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}-[z_{W}^{i-1}]^{q}[z_{W}^{i-1}]^{t}}\right|}{\left|{\phi_{i}^{\prime\prime}\Big{(}\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}\Big{)}}\right|}.$
(50)

Since $\phi_{i}^{\prime\prime}$ is $\kappa_{2}$-Lipschitz by Assumption A.3,
equation (49) is at most

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}}\right|}\cdot\kappa_{2}{\left|{\sum_{r=1}^{d_{i-1}}(W_{i}^{p,r}+U_{i}^{p,r})[z_{W+U}^{i-1}]^{r}-\sum_{r=1}^{d_{i-1}}W_{i}^{p,r}[z_{W}^{i-1}]^{r}}\right|}.$
(51)

Again by Assumption A.3,
${\left|{\phi_{i}^{\prime\prime}(\cdot)}\right|}\leq\kappa_{1}$ following the
Lipschitzness of the second-order derivatives. Thus, equation (50) is at most

$\displaystyle{\left|{[z_{W+U}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}-[z_{W}^{i-1}]^{q}[z_{W}^{i-1}]^{t}}\right|}\cdot\kappa_{1}$
$\displaystyle\leq$
$\displaystyle\Bigg{(}{\left|{[z_{W+U}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}-[z_{W}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}}\right|}+{\left|{[z_{W}^{i-1}]^{q}[z_{W+U}^{i-1}]^{t}-[z_{W}^{i-1}]^{q}[z_{W}^{i-1}]^{t}}\right|}\Bigg{)}\cdot\kappa_{1}.$
(52)

We use the triangle inequality in the last step.

Taking equation (51) and (52) together, the Frobenius norm of the Hessian is

$\displaystyle\left\|\mathbf{H}_{i}[z_{W}^{i}]\Big{|}_{W_{k}+U_{k},\forall
1\leq k\leq i}-\mathbf{H}_{i}[z_{W}^{i}]\right\|_{F}$ $\displaystyle\leq~{}$
$\displaystyle d_{i}\left\|z_{W+U}^{i-1}\right\|^{2}\cdot
k_{2}d_{i-1}\left\|\big{(}W_{i}+U_{i}\big{)}z_{W+U}^{i-1}-W_{i}z_{W}^{i-1}\right\|+\kappa_{1}d_{i}\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|\Bigg{(}\left\|z_{W+U}^{i-1}\right\|+\left\|z_{W}^{i-1}\right\|\Bigg{)}.$

By the Lipschitz continuity of $Z_{W+U}^{i-1}$ and equation (31) in Claim A.6,
we have

$\displaystyle\left\|z_{W+U}^{i-1}\right\|\leq$
$\displaystyle\Big{(}1+\frac{1}{L}\Big{)}^{i-1}\kappa_{0}^{i-1}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}.$
(53) $\displaystyle\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|\leq$
$\displaystyle\Big{(}1+\frac{1}{L}\Big{)}^{i-1}\kappa_{0}^{i-1}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}\sum_{h=1}^{i-1}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}.$
(54)

By the triangle inequality, we have

$\displaystyle\left\|\big{(}W_{i}+U_{i}\big{)}z_{W+U}^{i-1}-W_{i}z_{W}^{i-1}\right\|\leq\left\|W_{i}+U_{i}\right\|_{2}\left\|z_{W+U}^{i-1}-z_{W}^{i-1}\right\|+\left\|U_{i}\right\|_{2}\left\|z_{W}^{i-1}\right\|,$
(55)

From equations (53), (54), and (55), we finally obtain that the Hessian of
$z_{W}^{i}$ with respect to $W_{i}$ is at most

$\displaystyle\left\|\mathbf{H}_{i}[z_{W}^{i}]\Big{|}_{W_{k}+U_{k},\forall
1\leq k\leq i}-\mathbf{H}_{i}[z_{W}^{i}]\right\|_{F}$ $\displaystyle\leq~{}$
$\displaystyle
3\Big{(}1+\frac{1}{L}\Big{)}^{3i}\kappa_{2}\kappa_{1}\kappa_{0}^{3i-3}d_{i}d_{i-1}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i-1}\left\|W_{h}\right\|_{2}\Bigg{)}^{2}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{i}\left\|W_{h}\right\|_{2}\sum_{h=1}^{i}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)}.$

Thus, we have known that equation (48) is correct when $j=i$ with respect to
$\mathbf{H}_{i}$.

Assume that equation (48) is correct for any $i$ up to $j\geq i$ with respect
to $\mathbf{H}_{i}$. Thus, the following inequality holds:

$\displaystyle\left\|\mathbf{H}_{i}[z_{W}^{j}]\Big{|}_{W_{k}+U_{k},\forall
k}-\mathbf{H}_{i}[z_{W}^{j}]\right\|_{F}\leq
C\prod_{l=i-1}^{j}d_{l}^{3}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\Bigg{)}^{2}\Bigg{(}\max_{x\in\mathcal{X}}\left\|x\right\|\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}\sum_{h=1}^{j}\frac{\left\|U_{h}\right\|_{2}}{\left\|W_{h}\right\|_{2}}\Bigg{)},$

where
$C=\frac{3}{2}(j-i+2)^{2}\Big{(}1+\frac{1}{L}\Big{)}^{6j}\kappa_{2}\kappa_{1}^{2}\kappa_{0}^{3(j-1)}$.

Then, we will consider the second-order derivative of
$z_{W}^{j+1}=\phi_{j+1}(W_{j+1}z_{W}^{j})$ with respect to $W_{i}^{p,q}$ and
$W_{i}^{s,t}$:

$\displaystyle\frac{\partial^{2}\phi_{j+1}(W_{j+1}z_{W}^{j})}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}=~{}$
$\displaystyle\phi_{j+1}^{\prime\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{)}\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{s,t}}\Bigg{)}+\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{)},$

where $\odot$ is the Hadamard product operator between two vectors. Then, we
have

$\displaystyle\left\|\frac{\partial^{2}z_{W}^{j+1}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j+1}-\frac{\partial^{2}z_{W}^{j+1}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}\right\|$ $\displaystyle=~{}$
$\displaystyle\Bigg{\|}\phi_{j+1}^{\prime\prime}((W_{j+1}+U_{j+1})z_{W+U}^{j})\odot\Bigg{(}(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\Bigg{)}\odot\Bigg{(}(W_{j+1}+U_{j+1})\frac{\partial z_{W}^{j}}{\partial
W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j}\Bigg{)}$
$\displaystyle~{}~{}+\phi_{j+1}^{\prime}((W_{j+1}+U_{j+1})z_{W+U}^{j})\odot\Bigg{(}(W_{j+1}+U_{j+1})\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\Bigg{)}$
$\displaystyle~{}~{}-\phi_{j+1}^{\prime\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{)}\odot\Bigg{(}W_{j+1}\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{s,t}}\Bigg{)}-\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\odot\Bigg{(}W_{j+1}\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{)}\Bigg{\|}.$

By the Cauchy-Schwarz inequality and the triangle inequality, the above
equation is at most

$\displaystyle\left\|\phi_{j+1}^{\prime\prime}((W_{j+1}+U_{j+1})z_{W+U}^{j})-\phi_{j+1}^{\prime\prime}(W_{j+1}z_{W}^{j})\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k}}\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k}}\right\|$ (56)
$\displaystyle+$
$\displaystyle\left\|\phi_{j+1}^{\prime\prime}(W_{j+1}z_{W}^{j})\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k}}-W_{j+1}\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k}}\right\|$ (57)
$\displaystyle+$
$\displaystyle\left\|\phi_{j+1}^{\prime\prime}(W_{j+1}z_{W}^{j})\right\|\cdot\left\|W_{j+1}\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-W_{j+1}\frac{\partial z_{W}^{j}}{\partial W_{i}^{s,t}}\right\|$ (58)
$\displaystyle+$
$\displaystyle\left\|\phi_{j+1}^{\prime}((W_{j+1}+U_{j+1})z_{W+U}^{j})-\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\right\|$ (59) $\displaystyle+$
$\displaystyle\left\|\phi_{j+1}^{\prime}(W_{j+1}z_{W}^{j})\right\|\cdot\left\|(W_{j+1}+U_{j+1})\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-W_{j+1}\frac{\partial^{2}z_{W}^{j}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}\right\|.$ (60)

Next, we will deal with the above quantities one by one. The idea is
essentially using the Lipschitzness properties of the activation functions.

Using the triangle inequality and the fact that $\phi^{\prime\prime}(\cdot)$
is $\kappa_{2}$-Lipschitz, equation (56) is at most

$\displaystyle\kappa_{2}\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|z_{W+U}^{j}-z_{W}^{j}\right\|+\left\|U_{j+1}\right\|_{2}\cdot\left\|z_{W}^{j}\right\|\Bigg{)}\left\|W_{j+1}+U_{j+1}\right\|_{2}^{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k}}\right\|\cdot\left\|\frac{\partial}{\partial
W_{i}^{s,t}}z_{W}^{j}\Bigg{|}_{W_{k}+U_{k}}\right\|.$

Using the triangle inequality and the fact that
$|\phi^{\prime\prime}(\cdot)|\leq\kappa_{1}$, equation (57) is at most

$\displaystyle\kappa_{1}d_{j+1}\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{p,q}}\Bigg{|}_{W_{k}+U_{k}}-\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|+\left\|U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|\Bigg{)}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k}}\right\|.$

Similarly, using the triangle inequality and
$|\phi^{\prime\prime}(\cdot)|\leq\kappa_{1}$, equation (58) is at most

$\displaystyle\kappa_{1}d_{j+1}\left\|W_{j+1}\right\|_{2}\left\|\frac{\partial
z_{W}^{j}}{\partial
W_{i}^{p,q}}\right\|\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall
k}-\frac{\partial z_{W}^{j}}{\partial
W_{i}^{s,t}}\right\|+\left\|U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial
z_{W}^{j}}{\partial W_{i}^{s,t}}\right\|\Bigg{)}.$

Lastly, using the fact that $\phi^{\prime}(\cdot)$ is $\kappa_{1}$-Lipschitz,
equation (59) is at most

$\displaystyle\kappa_{1}\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|z_{W+U}^{j}-z_{W}^{j}\right\|+\left\|U_{j+1}\right\|_{2}\cdot\left\|z_{W}^{j}\right\|\Bigg{)}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}\right\|.$

Using the fact that $|\phi^{\prime}(\cdot)|\leq\kappa_{0}$, equation (60) is
at most

$\displaystyle\kappa_{0}d_{j+1}\Bigg{(}\left\|W_{j+1}+U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq
j}-\frac{\partial^{2}z_{W}^{j}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}\right\|+\left\|U_{j+1}\right\|_{2}\cdot\left\|\frac{\partial^{2}z_{W}^{j}}{\partial
W_{i}^{p,q}\partial W_{i}^{s,t}}\right\|\Bigg{)}.$

From Claim A.6, we know that the norm of the derivative of $z_{W}^{j}$ with
respect to $W_{i}^{p,q}$ is bounded by its Lipschitzness in equation (31):

$\displaystyle\left\|\frac{\partial}{\partial W_{i}^{p,q}}z_{W}^{j}\right\|$
$\displaystyle\leq(1+\frac{1}{L})^{j}\kappa_{0}^{j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(61) $\displaystyle\left\|\frac{\partial}{\partial
W_{i}^{p,q}}z_{W}^{j}\Big{|}_{W_{k}+U_{k},\forall 1\leq k\leq j}\right\|$
$\displaystyle\leq(1+\frac{1}{L})^{2j-1}\kappa_{0}^{j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(62)

From Claim A.7, the norm of the twice-derivative of $z_{W}^{j}$ with respect
to $W_{i}^{p,q}$ and $W_{i}^{s,t}$ is bounded by its Lipschitzness in equation
(32):

$\displaystyle\left\|\frac{\partial^{2}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}z_{W}^{j}\right\|$ $\displaystyle\leq
A_{i,j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(63) $\displaystyle\left\|\frac{\partial^{2}}{\partial W_{i}^{p,q}\partial
W_{i}^{s,t}}z_{W}^{j}\Bigg{|}_{W_{k}+U_{k},\forall 1\leq k\leq j}\right\|$
$\displaystyle\leq\Big{(}1+\frac{1}{L}\Big{)}^{2j-2}A_{i,j}\max_{x\in\mathcal{X}}\left\|x\right\|\frac{1}{\left\|W_{i}\right\|_{2}}\prod_{h=1}^{j}\left\|W_{h}\right\|_{2}.$
(64)