# Generalization Guarantees of Gradient Descent for Multi-Layer
Neural Networks

Puyu Wang1 Yunwen Lei2 Di Wang3 Yiming Ying4∗ Ding-Xuan Zhou5
1 Hong Kong Baptist University, Hong Kong
2 The University of Hong Kong, Hong Kong
3 King Abdullah University of Science and Technology, Saudi Arabia
4 State University of New York at Albany, USA
5 University of Sydney, Australia

###### Abstract

Recently, significant progress has been made in understanding the
generalization of neural networks (NNs) trained by gradient descent (GD) using
the algorithmic stability approach. However, most of the existing research has
focused on one-hidden-layer NNs and has not addressed the impact of different
network scaling parameters. In this paper, we greatly extend the previous work
[23, 34] by conducting a comprehensive stability and generalization analysis
of GD for multi-layer NNs. For two-layer NNs, our results are established
under general network scaling parameters, relaxing previous conditions. In the
case of three-layer NNs, our technical contribution lies in demonstrating its
nearly co-coercive property by utilizing a novel induction strategy that
thoroughly explores the effects of over-parameterization. As a direct
application of our general findings, we derive the excess risk rate of
$\mathcal{O}(1/\sqrt{n})$ for GD algorithms in both two-layer and three-layer
NNs. This sheds light on sufficient or necessary conditions for under-
parameterized and over-parameterized NNs trained by GD to attain the desired
risk rate of $\mathcal{O}(1/\sqrt{n})$. Moreover, we demonstrate that as the
scaling parameter increases or the network complexity decreases, less over-
parameterization is required for GD to achieve the desired error rates.
Additionally, under a low-noise condition, we obtain a fast risk rate of
$\mathcal{O}(1/n)$ for GD in both two-layer and three-layer NNs.
††footnotetext:  ∗The corresponding author is Yiming Ying.

##  1 Introduction

Deep neural networks (DNNs) trained by (stochastic) gradient descent (GD) have
achieved great success in a wide spectrum of applications such as image
recognition [21], speech recognition [18], machine translation [5], and
reinforcement learning [36]. In practical applications, most of the deployed
DNNs are over-parameterized, i.e., the number of parameters is far larger than
the size of the training data. In [39], it was empirically demonstrated that
over-parameterized NNs trained with SGD can generalize well to the test data
while achieving a small training error. This has triggered a surge of
theoretical studies on unveiling this generalization mastery of DNNs.

In particular, norm-based generalization bounds are established using the
uniform convergence approach [6, 7, 16, 27, 32, 31]. However, this approach
does not take the optimization algorithm and the data distribution into
account. Another line of work is to take into account the structure of the
data distribution and provide algorithm-dependent generalization bounds. In
[9, 26], it is shown that SGD for over-parameterized two-layer NNs can achieve
small generalization error under certain assumptions on the structure of the
data. [1] studies the generalization of SGD for two-layer and three-layer NNs
if there exists a true (unknown) NN with low error on the data distribution.
The other important line of work is the neural tangent kernel (NTK)-type
approach [3, 10, 12, 33] which shows that the model trained by GD is well
approximated by the tangent space near the initialization and the
generalization analysis can be reduced to those of the convex case or kernel
methods. However, most of them either require a very high over-
parameterization or focus on special function classes.

Recently, the appealing work [34] provides an alternative approach in a
kernel-free regime, using the concept of algorithmic stability [8, 17, 22].
Specifically, it uses the model-average stability [24] to derive
generalization bounds of GD for two-layer over-parameterized NNs. [23]
improves this result by deriving generalization bounds for both GD and SGD,
and relaxing the over-parameterization requirement. [38] derives fast
generalization bounds for GD under a separable distribution. However, the
above studies only focus on two-layer NNs and a very specific network scaling.

Contributions. We study the stability and generalization of GD for both two-
layer and three-layer NNs with generic network scaling factors. Our
contributions are summarized as follows.

$\bullet$ We establish excess risk bounds for GD on both two-layer and three-
layer NNs with general network scaling parameters under relaxed over-
parameterization conditions. As a direct application of our generalization
results, we show that GD can achieve the excess risk rate
$\mathcal{O}(1/\sqrt{n})$ when the network width $m$ satisfies certain
qualitative conditions related to the scaling parameter $c$, the size of
training data $n$, and the network complexity measured by the norm of the
minimizer of the population risk. Further, under a low-noise condition, our
excess risk rate can be improved to $\mathcal{O}(1/n)$ for both two-layer and
three-layer NNs.

$\bullet$ A crucial technical element in the stability analysis for NNs
trained by GD is establishing the almost co-coercivity of the gradient
operator. This property naturally holds true for two-layer NNs due to the
empirical risks’ monotonically decreasing nature which no longer remains valid
for three-layer NNs. Our technical contribution lies in demonstrating that the
nearly co-coercive property still holds valid throughout the trajectory of GD.
To achieve this, we employ a novel induction strategy that fully explores the
effects of over-parameterization (refer to Section 4 for further discussions).
Furthermore, we are able to eliminate a critical assumption made in [23]
regarding an inequality associated with the population risk of GD’s iterates
(see Remark 2 for additional details).

$\bullet$ Our results characterize a quantitative condition in terms of the
network complexity and scaling factor under which GD for two-layer and three-
layer NNs can achieve the excess risk rate $\mathcal{O}(1/\sqrt{n})$ in under-
parameterization and over-parameterization regimes. Our results shed light on
sufficient or necessary conditions for under-parameterized and over-
parameterized NNs trained by GD to achieve the risk rate
$\mathcal{O}(1/\sqrt{n}).$ In addition, our results show that the larger the
scaling parameter or the simpler the network complexity is, the less over-
parameterization is needed for GD to achieve the desired error rates for
multi-layer NNs.

##  2 Problem Formulation

Let $P$ be a probability measure defined on a sample space
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{Y}\subseteq\mathbb{R}$. Let
$S=\\{z_{i}=(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$ be a training dataset drawn
from $P$. One aims to build a prediction model
$f_{\mathbf{W}}:\mathcal{X}\mapsto\mathbb{R}$ parameterized by $\mathbf{W}$ in
some parameter space $\mathcal{W}$ based on $S$. The performance of
$f_{\mathbf{W}}$ can be measured by the population risk defined as
$L(f_{\mathbf{W}})=\frac{1}{2}\iint_{\mathcal{X}\times\mathcal{Y}}\big{(}f_{\mathbf{W}}(\mathbf{x})-y\big{)}^{2}dP(\mathbf{x},y).$
The corresponding empirical risk is defined as

$L_{S}(f_{\mathbf{W}})=\frac{1}{2n}\sum_{i=1}^{n}\big{(}f_{\mathbf{W}}(\mathbf{x}_{i})-y_{i}\big{)}^{2}.$
(1)

We denote by
$\ell(\mathbf{W};z)=\frac{1}{2}(f_{\mathbf{W}}(\mathbf{x})-y)^{2}$ the loss
function of $\mathbf{W}$ on a data point $z=(\mathbf{x},y)$. The best possible
model is the regression function $f^{*}$ defined as
$f^{*}(\mathbf{x})=\mathbb{E}[y|\mathbf{x}]$, where
$\mathbb{E}[\cdot|\mathbf{x}]$ is the conditional expectation given
$\mathbf{x}$. In this paper, we consider the prediction model $f_{\mathbf{W}}$
with a neural network structure. In particular, we are interested in two-layer
and three-layer fully-connected NNs.

Two-layer NNs. A two-layer NN of width $m>0$ and scaling parameter
$c\in[1/2,1]$ takes the form

$f_{\mathbf{W}}(\mathbf{x})=\frac{1}{m^{c}}\sum_{k=1}^{m}a_{k}\sigma(\mathbf{w}_{k}\mathbf{x}),$

where $\sigma:\mathbb{R}\mapsto\mathbb{R}$ is an activation function,
$\mathbf{W}=[\mathbf{w}_{1}^{\top},\ldots,\mathbf{w}_{m}^{\top}]^{\top}\in\mathcal{W}$
with $\mathcal{W}=\mathbb{R}^{m\times d}$ is the weight matrix of the first
layer, and a fixed $\mathbf{a}=[a_{1},\ldots,a_{m}]$ with
$a_{k}\in\\{-1,+1\\}$ is the weight of the output layer. In the above
formulation, $\mathbf{w}_{k}\in\mathbb{R}^{1\times d}$ denotes the weight of
the edge connecting the input to the $k$-th hidden node, and $a_{k}$ denotes
the weight of the edge connecting the $k$-th hidden node to the output node.
The output of the network is scaled by a factor $m^{-c}$ that is decreasing
with the network width $m$. Two popular choices of scaling are Neural Tangent
Kernel (NTK) [2, 3, 4, 19, 15, 14] with $c=1/2$ and mean field [12, 13, 28,
29] with $c=1$. [35] studied two-layer NNs with $c\in[1/2,1]$ and discussed
the influence of the scaling by trading off it with the network complexity. We
also focus on the scaling $c\in[1/2,1]$ to ensure that meaningful
generalization bounds can be obtained. We fix the output layer weight
$\mathbf{a}$ and only optimize the first layer weight $\mathbf{W}$ in this
setting.

Three-layer NNs. For a matrix $\mathbf{W}$, let $\mathbf{W}_{s:}$ and
$\mathbf{W}_{is}$ denote the $s$-th row and the $(i,s)$-th entry of
$\mathbf{W}$. For an input $\mathbf{x}\in\mathbb{R}^{d}$, a three-layer fully-
connected NN with width $m>0$ and scaling $c\in(1/2,1]$ is

$f_{\mathbf{W}}(\mathbf{x})=\frac{1}{m^{c}}\sum_{i=1}^{m}a_{i}\sigma\big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}_{is}^{(2)}\sigma(\mathbf{W}_{s:}^{(1)}\mathbf{x})\big{)},$

where $\sigma:\mathbb{R}\mapsto\mathbb{R}$ is an activation function,
$\mathbf{W}=[\mathbf{W}^{(1)},\mathbf{W}^{(2)}]\in\mathcal{W}=\mathbb{R}^{m\times(d+m)}$
is the weight matrix of the neural network, and
$\mathbf{a}=[a_{1},\ldots,a_{m}]$ with $a_{i}\in\\{-1,+1\\}$ is the fixed
output layer weight. Here, $\mathbf{W}^{(1)}\in\mathbb{R}^{m\times d}$ and
$\mathbf{W}^{(2)}\in\mathbb{R}^{m\times m}$ are the weights at the first and
the second layer, respectively. We consider the setting of optimizing the
weights in both the first and the second layers.

We consider the gradient descent to solve the minimization problem:
$\min_{\mathbf{W}}L_{S}(f_{\mathbf{W}}).$ For simplicity, let
$L(\mathbf{W})=L(f_{\mathbf{W}})$ and
$L_{S}(\mathbf{W})=L_{S}(f_{\mathbf{W}})$.

######  Definition 1 (Gradient Descent).

Let $\mathbf{W}_{0}\in\mathcal{W}$ be an initialization point, and
$\\{\eta_{t}:t\in\mathbb{N}\\}$ be a sequence of step sizes. Let $\nabla$
denote the gradient operator. At iteration $t$, the update rule of GD is

$\mathbf{W}_{t+1}=\mathbf{W}_{t}-\eta_{t}\nabla L_{S}(\mathbf{W}_{t}).$ (2)

Target of Analysis. Let
$\mathbf{W}^{*}=\arg\min_{\mathbf{W}\in\mathcal{W}}L(\mathbf{W})$ where the
minimizer is chosen to be the one enjoying the smallest norm. For a randomized
algorithm $\mathcal{A}$ to solve (1), let $\mathcal{A}(S)$ be the output of
$\mathcal{A}$ applied to the dataset $S$. The generalization performance of
$\mathcal{A}(S)$ is measured by its excess population risk, i.e.,
$L(\mathcal{A}(S))-L(\mathbf{W}^{*})$. In this paper, we are interested in
studying the excess population risk of models trained by GD for both two-layer
and three-layer NNs.

We denote by $\|\cdot\|_{2}$ the standard Euclidean norm of a vector or a
matrix. For any $\lambda>0$, let
$\mathbf{W}^{*}_{\lambda}=\operatorname*{argmin}_{\mathbf{W}}\big{\\{}L(\mathbf{W})+\frac{\lambda}{2}\|\mathbf{W}-\mathbf{W}_{0}\|_{2}^{2}\big{\\}}$.
We have the following error decomposition

$\displaystyle\mathbb{E}[L(\mathcal{A}(S))]-L(\mathbf{W}^{*})=$
$\displaystyle\mathbb{E}\big{[}L(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))\big{]}+\mathbb{E}\big{[}L_{S}(\mathcal{A}(S))-L_{S}(\mathbf{W}^{*}_{\lambda})-\frac{\lambda}{2}\|\mathbf{W}^{*}_{\lambda}-\mathbf{W}_{0}\|_{2}^{2}\big{]}$
$\displaystyle+\big{[}L(\mathbf{W}^{*}_{\lambda})+\frac{\lambda}{2}\|\mathbf{W}^{*}_{\lambda}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})\big{]},$
(3)

where we use
$\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\lambda})]=L(\mathbf{W}^{*}_{\lambda})$. The
first term in (2) is called the generalization error, which can be controlled
by stability analysis. The second term is the optimization error, which can be
estimated by tools from optimization theory. The third term, denoted by
$\Lambda_{\lambda}=L(\mathbf{W}^{*}_{\lambda})+\frac{\lambda}{2}\|\mathbf{W}^{*}_{\lambda}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})$,
is the approximation error which will be estimated by introducing an
assumption on the complexity of the NN (Assumption 3 in Section 3.1).

We will use the on-average argument stability [24] to study the generalization
error defined as follows.

######  Definition 2 (On-average argument stability).

Let $S=\\{z_{i}\\}_{i=1}^{n}$ and $S^{\prime}=\\{z^{\prime}_{i}\\}_{i=1}^{n}$
be drawn i.i.d. from an unknown distribution $P$. For any $i\in[n]$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z^{\prime}_{i},z_{i+1},\ldots,z_{n}\\}$ as
the set formed from $S$ by replacing the $i$-th element with $z_{i}^{\prime}$.
We say $\mathcal{A}$ is on-average argument $\epsilon$-stable if

$\mathbb{E}_{S,S^{\prime},\mathcal{A}}\big{[}\frac{1}{n}\sum_{i=1}^{n}\|\mathcal{A}(S)-\mathcal{A}(S^{(i)})\|_{2}^{2}\big{]}\leq\epsilon^{2}.$

We say a function $\ell:\mathcal{W}\times\mathcal{Z}\rightarrow\mathbb{R}$ is
$\rho$-smooth if for any $\mathbf{W},\mathbf{W}^{\prime}\in\mathcal{W}$ and
$z\in\mathcal{Z}$, there holds
$\ell(\mathbf{W};z)-\ell(\mathbf{W}^{\prime};z)\leq\langle\nabla\ell(\mathbf{W}^{\prime};z),\mathbf{W}-\mathbf{W}^{\prime}\rangle+\frac{\rho}{2}\|\mathbf{W}-\mathbf{W}^{\prime}\|_{2}^{2}$.
The following lemma establishes the connection [24] between the on-average
argument stability and the generalization error.

######  Lemma 1.

Let $\mathcal{A}$ be an algorithm. If for any $z$, the map
$\mathbf{W}\mapsto\ell(\mathbf{W};z)$ is $\rho$-smooth, then

$\displaystyle\mathbb{E}[L(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))]\leq\frac{\rho}{2n}\sum_{i=1}^{n}\mathbb{E}[\|\mathcal{A}(S)-\mathcal{A}(S^{(i)})\|_{2}^{2}]+\bigl{(}\frac{2\rho\mathbb{E}[L_{S}(\mathcal{A}(S))]}{n}\sum_{i=1}^{n}\mathbb{E}[\|\mathcal{A}(S)-\mathcal{A}(S^{(i)})\|_{2}^{2}]\bigr{)}^{\frac{1}{2}}.$

Our analysis requires the following standard assumptions on activation and
loss functions [23, 34].

######  Assumption 1 (Activation function).

The activation function $a\mapsto\sigma(a)$ is continuous and twice
differentiable with $|\sigma(a)|\leq B_{\sigma}$, $|\sigma^{\prime}(a)|\leq
B_{\sigma^{\prime}}$ and $|\sigma^{\prime\prime}(a)|\leq
B_{\sigma^{\prime\prime}}$, where
$B_{\sigma},B_{\sigma^{\prime}},B_{\sigma^{\prime\prime}}>0.$

Both sigmoid and hyperbolic tangent activation functions satisfy Assumption 1
[34].

######  Assumption 2 (Inputs, labels and loss).

There exist constants $c_{\mathbf{x}},c_{y},c_{0}>0$ such that
$\|\mathbf{x}\|_{2}\leq c_{\mathbf{x}}$ , $|y|\leq c_{y}$ and
$\max\\{\ell(\mathbf{0};z),\ell(\mathbf{W}_{0};z)\\}\leq c_{0}$ for any
$\mathbf{x}\in\mathcal{X},y\in\mathcal{Y}$ and $z\in\mathcal{Z}$.

##  3 Main Results

In this section, we present our main results on the excess population risk of
NNs trained by GD.

###  3.1 Two-layer Neural Networks with Scaling Parameters

We denote $B\asymp B^{\prime}$ if there exist some universal constants
$c_{1},c_{2}>0$ such that $c_{1}B\geq B^{\prime}\geq c_{2}B$. We denote
$B\gtrsim B^{\prime}$ ($B\lesssim B^{\prime}$) if there exists a constant
$c>0$ such that $B\geq cB^{\prime}$ ($cB\leq B^{\prime}$). Let
$\rho=c_{\mathbf{x}}^{2}\big{(}\frac{B_{\sigma^{\prime}}^{2}+B_{\sigma}B_{\sigma^{\prime\prime}}}{m^{2c-1}}+\frac{B_{\sigma^{\prime\prime}}c_{y}}{m^{c}}\big{)}.$
The following theorem presents generalization error bounds of GD for two-layer
NNs. The proof can be found in Appendix A.1.

######  Theorem 2 (Generalization error).

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta_{t}\equiv\eta\leq 1/(2\rho)$ based on $S$. Assume

$\displaystyle m\gtrsim\big{(}{(\eta T)^{2}(1+\eta\rho)\sqrt{\rho(\rho\eta
T+2)}}\big{/}{n}\big{)}^{\frac{2}{4c-1}}+(\eta T)^{\frac{3}{4c-1}}+\big{(}\eta
T\big{)}^{\frac{1}{c}}.$ (4)

Then, for any $t\in[T]$, there holds

$\mathbb{E}[L(\mathbf{W}_{t})-L_{S}(\mathbf{W}_{t})]\leq\big{(}\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}+\frac{4e\eta\rho}{n}\big{)}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}.$

######  Remark 1.

Theorem 2 establishes the first generalization results for general
$c\in[1/2,1]$, which shows that the requirement on $m$ becomes weaker as $c$
becomes larger. Indeed, with a typical choice $\eta T\asymp
n^{\frac{c}{6\mu+2c-3}}$ (as shown in Corollary 5 below), the assumption (4)
becomes $m\gtrsim n^{\frac{1}{6\mu+2c-3}(1+\frac{51-96\mu}{8(8c-3)})}$. This
requirement becomes milder as $c$ increases for any $\mu\in[0,1]$, which
implies that large scaling reduces the requirement on the network width. In
particular, our assumption only requires $m\gtrsim\eta T$ when $c=1$. [23]
provided a similar generalization bound with an assumption $m\gtrsim(\eta
T)^{5}/n^{2}+(\eta T)^{2}$, and our result with $c=1/2$ is consistent with
their result.

The following theorem to be proved in Appendix A.2 develops the optimization
error bounds of GD.

######  Theorem 3 (Optimization error).

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta_{t}\equiv\eta\leq 1/(2\rho)$ based on $S$. Let
$\tilde{b}=c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}(\frac{2B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}+\sqrt{2c_{0}})$
and assume (4) holds. Assume

$m\gtrsim\big{(}\tilde{b}T(\sqrt{\eta T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2})\big{(}\frac{e^{2}\eta^{3}\rho^{2}T^{2}}{n^{2}}+\frac{e\eta^{2}T\rho}{n}+1\big{)}\big{)}^{\frac{1}{c}}.$
(5)

Then we have

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})]-L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-\frac{1}{2\eta T}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}]$
$\displaystyle\\!\leq\\!\frac{2\tilde{b}}{m^{c}}(\\!\sqrt{2\eta
Tc_{0}}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2})\big{(}\big{(}\frac{8e^{2}\eta^{3}\rho^{2}T^{2}}{n^{2}}\\!+\\!\frac{8e\eta^{2}T\rho}{n}\big{)}\\!\sum_{s=0}^{T-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})\\!\\!-\\!L(\mathbf{W}^{*})\big{]}\big{)}.$

Recall that $\Lambda_{\frac{1}{\eta T}}=L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})$ is the approximation error. We
can combine generalization and optimization error bounds together to derive
our main result of GD for two-layer NNs. It is worth mentioning that our
excess population bound is dimension-independent, which is mainly due to that
stability analysis focuses on the optimization process trajectory, as opposed
to the uniform convergence approach which involves the complexity of function
space and thus is often dimension-dependent. Without loss of generality, we
assume $\eta T\geq 1$.

######  Theorem 4 (Excess population risk).

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta_{t}\equiv\eta\leq 1/(2\rho)$. Assume (4) and (5) hold. For any
$c\in[1/2,1]$, if $\eta Tm^{1-2c}=\mathcal{O}(n)$ and $m\gtrsim(\eta
T(\sqrt{\eta T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}))^{1/c}$, then there holds

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{\eta
Tm^{1-2c}}{n}L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}\big{)}.$

######  Remark 2 (Comparison with [34, 23]).

Theorem 4 provides the first excess risk bounds of GD for two-layer NNs with
general scaling parameter $c\in[1/2,1]$ which recovers the previous work [34,
23] with $c=1/2$. Specifically, [34] derived the excess risk bound
$\mathcal{O}\big{(}\frac{\eta T}{n}L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta
T}}\big{)}$ with $m\gtrsim(\eta T)^{5}$, we relax this condition to
$m\gtrsim(\eta T)^{3}$ by providing a better estimation of the smallest
eigenvalue of a Hessian matrix of the empirical risk (see Lemma A.5). This
bound was obtained in [23] under a crucial condition
$\mathbb{E}[L(\mathbf{W}_{s})]\geq L(\mathbf{W}^{*}_{\frac{1}{\eta T}})$ for
any $s\in[T]$, which is difficult to verify in practice. Here, we are able to
remove this condition by using $L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}_{s})\leq L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}^{*})\leq\Lambda_{\frac{1}{\eta T}}$ since
$L(\mathbf{W}_{s})\geq L(\mathbf{W}^{*})$ when controlling the bound of GD
iterates (see Lemma A.6 for details). Furthermore, our result in Theorem 4
implies that the larger the scaling parameter $c$ is, the better the excess
risk bound is. The reason could be that the smoothness parameter related to
the objective function along the GD trajectory becomes smaller for a larger
$c$ (see Lemma A.2 for details).

As a direct application of Theorem 4, we can derive the excess risk rates of
GD for two-layer NNs by properly trade-offing the generalization, optimization
and approximation errors. To this end, we further introduce the following
assumption on network complexity to control the approximation error by noting
that $\Lambda_{\frac{1}{\eta T}}\leq\|\mathbf{W}^{*}\|_{2}^{2}/2\eta T$.

######  Assumption 3 ([35]).

There is $\mu\\!\in\\![0,1]$ and population risk minimizer $\mathbf{W}^{*}$
with $\|\mathbf{W}^{*}\|_{2}\\!\leq\\!m^{\frac{1}{2}-\mu}$.

######  Corollary 5.

Let assumptions in Theorem 4 hold and Assumption 3 hold. Suppose ${c\over
3}+\mu>{1\over 2}$.

  1. (a)

If $c\in[1/2,3/4)$ and $c+\mu\geq 1$, we can choose $m\asymp(\eta
T)^{\frac{3}{2c}}$ and $\eta T$ such that $n^{\frac{c}{6\mu+2c-3}}\lesssim\eta
T\lesssim n^{\frac{c}{3-4c}}$. If $c\in[3/4,1]$, we can choose $m\asymp(\eta
T)^{\frac{3}{2c}}$ and $\eta T$ such that $\eta T\gtrsim
n^{\frac{c}{6\mu+2c-3}}$. Then there holds

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{\sqrt{n}}\big{)}.$

  2. (b)

Assume $L(\mathbf{W}^{*})=0$. We can choose $m\asymp(\eta T)^{\frac{3}{2c}}$
and $\eta T$ such that $\eta T\gtrsim n^{\frac{2c}{6\mu+2c-3}}$, and get

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{n}\big{)}.$

Figure 1: Scaling parameter $c$ versus Network complexity parameter $\mu$ for
Part (a) in Corollary 5 (left) and Part (a) in Corollary 9 (right). Blue
Region without dots: values of $c$ and $\mu$ where over-parameterization is
necessary to achieve error bound $\mathcal{O}(1/\sqrt{n})$. Blue Region with
dots: values of $c$ and $\mu$ where under-parameterization is sufficient to
achieve error bound $\mathcal{O}(1/\sqrt{n})$. Pink Region: the desired bound
cannot be guaranteed.

Interpretation of the Results: Corollary 5 indicates a quantitative condition
via the network complexity and scaling factor where GD for two-layer NNs can
achieve the excess risk rate $\mathcal{O}(1/\sqrt{n})$ in under-
parameterization and over-parameterization regimes. We use the left panel of
Figure 1 to interpret the results.

Let us first explain the meanings of the regions and lines in the left panel
of Figure 1. Specifically, the blue regions (with or without dots) correspond
to the conditions ${c\over 3}+\mu>{1\over 2}$ and $c+\mu\geq 1$ in part (a) of
Corollary 5, while our results do not hold in the pink region which violates
the conditions in part (a). Furthermore, under conditions ${c\over
3}+\mu>{1\over 2}$ and $c+\mu\geq 1$, that the desired bound in part (a) can
be achieved by choosing $m\asymp(\eta T)^{\frac{3}{2c}}$ for any $\eta T$
satisfying $\eta T\gtrsim n^{\frac{c}{6\mu+2c-3}}$ if $c\geq 3/4$ and
$n^{\frac{c}{3-4c}}\gtrsim\eta T\gtrsim n^{\frac{c}{6\mu+2c-3}}$ if
$c\in[1/2,3/4)$, which further implies that GD with any width $m\gtrsim
n^{\frac{3}{2(6\mu+2c-3)}}$ if $c\in[3/4,1]$ and $n^{\frac{3}{2(3-4c)}}\gtrsim
m\gtrsim n^{\frac{3}{2(6\mu+2c-3)}}$ if $c\in[1/2,3/4)$ with suitable
iterations can achieve the error rate $\mathcal{O}(1/\sqrt{n})$. This
observation tells us that the smallest width for guaranteeing our results in
part (a) is $m\asymp n^{\frac{3}{2(6\mu+2c-3)}}$ for any $c\in[1/2,1]$. The
dotted line $\mu=3/4-c/3$ in the figure corresponds to the setting $m\asymp
n$, i.e., $\frac{3}{2(6\mu+2c-3)}=1$. Correspondingly, we use the dotted blue
region above the dotted line to indicate the under-parameterization region and
the blue region without dots below the dotted line for the over-
parameterization region. With the above explanations, we can interpret the
left panel of Figure 1 as follows.

$\bullet$ Firstly, from the figure, we know that, if values of $c$ and $\mu$
are located above the dotted line $\mu\geq 3/4-c/3$, i.e., the blue region
with dots, under-parameterization is sufficient for GD to achieve the error
rate $\mathcal{O}(1/\sqrt{n})$. It implies that the sufficient condition for
under-parameterized NNs trained by GD achieving the desired rate is $\mu\geq
3/4-c/3$. The potential reason is that the population risk minimizer
$\mathbf{W}^{*}$ is well-behaved in terms of its norm being relatively small
with $\mu$ being relatively large there. In particular, when $\mu>1/2$,
$\|\mathbf{W}^{*}\|_{2}\leq m^{1/2-\mu}$ tends to $0$ as $m$ tends to
infinity. Hence, it is expected that under-parameterized NNs can learn this
relatively simple $\mathbf{W}^{*}$ well. However, it is worthy of mentioning
that over-parameterization can also achieve the rate $\mathcal{O}(1/\sqrt{n})$
since the dotted line only indicates the smallest width required for achieving
such an error rate.

$\bullet$ Secondly, from the figure, we see that, if $c$ and $\mu$ belong to
the blue region without dots which is between the solid lines and the dotted
line, then over-parameterization is necessary for achieving the error rate
$\mathcal{O}(1/\sqrt{n}).$ This is because, in the blue region without dots,
that the conditions of choosing $m\gtrsim n^{\frac{3}{2(6\mu+2c-3)}}$ in part
(a) of Corollary 5 which will always indicate the over-parameterization
region, i.e., $m\gtrsim n.$ Furthermore, from the above discussions, our
theoretical results indicate that the over-parameterization does bring benefit
for GD to achieve good generalization in the sense that GD can achieve excess
risk rate $\mathcal{O}(1/\sqrt{n})$ when $c$ and $\mu$ is in the whole blue
region (with or without dots) while under-parameterization can only do so for
the blue region with dots where the network complexity is relatively simple,
i.e., $\mu$ is relatively large.

$\bullet$ Thirdly, our results do not hold for GD when values of $c$ and $\mu$
are in the pink region in the figure. In particular, when $\mu<1/6$, our
bounds do not hold for any $c\in[1/2,1]$. We suspect that this is due to the
artifacts of our analysis tools and it remains an open question to us whether
we can get a generalization error bound $\mathcal{O}(1/\sqrt{n})$ when
$\mu<1/6.$ In addition, our results in Corollary 5 also indicate that the
requirement on $m$ becomes weaker as $c$ and $\mu$ become larger. It implies
that networks with larger scaling and simpler network complexity are biased to
weaken the over-parameterization for GD to achieve the desired error rates for
two-layer NNs.

######  Remark 3.

In Lemma A.2, we show that $f_{\mathbf{W}}$ is
$B_{\sigma^{\prime}}c_{\mathbf{x}}m^{\frac{1}{2}-c}$-Lipschitz. Combining this
result with Assumption 3 we know
$|f_{\mathbf{W}^{*}}(\mathbf{x})-f_{\mathbf{0}}(\mathbf{x})|^{2}=\mathcal{O}(m^{2(1-c-\mu)})$.
In order for $|f_{\mathbf{W}{*}}(\mathbf{x})-f_{\mathbf{0}}(\mathbf{x})|^{2}$
to not vanish as $m$ tends to infinity, one needs $c+\mu\leq 1$. In Corollary
5, we also need $\frac{c}{3}+\mu>\frac{1}{2}$ to ensure the excess risk bounds
vanish. Combining these two conditions together implies that $c$ can not be
larger than $3/4$. That is, for the range $c\in(3/4,1]$, the conditions in
Corollary 5 restrict the class of functions the networks can represent as $m$
tends to infinity. However, we want to emphasize that even for the simplest
case that $|f_{\mathbf{W}^{*}}(\mathbf{x})-f_{\mathbf{0}}(\mathbf{x})|^{2}$
tends to $0$ as $m$ tends to infinity, our results still imply that over-
parameterization does bring benefit for GD to achieve optimal excess risk rate
$\mathcal{O}(1/\sqrt{n})$. Besides, our corollary mainly discusses the
conditions for achieving the excess risk rate $\mathcal{O}(1/\sqrt{n})$ and
$\mathcal{O}(1/n)$. The above-mentioned conditions will be milder if we
consider the slower excess risk rates. Then the restriction on $c$ will be
weaker. Furthermore, our main result (i.e., Theorem 4) does not rely on
Assumption 3, and it holds for any setting.

Comparison with the Existing Work: Part (b) in Corollary 5 shows fast rate
$\mathcal{O}(1/n)$ can be derived under a low-noise condition
$L(\mathbf{W}^{*})=0$ which is equivalent to the fact that there is a true
network such that $y=f_{\mathbf{W}^{*}}(\mathbf{x})$ almost surely. Similar to
part (a), large $c$ and large $\mu$ also help weaken the requirement on the
width $m$ in this case. For a special case $\mu=1/2$ and $c=1/2$, [23] proved
that GD for two-layer NNs achieves the excess risk rate
$\mathcal{O}(1/\sqrt{n})$ with $m\asymp n^{3/2}$ and $\eta T\asymp\sqrt{n}$ in
the general case, which is further improved to $\mathcal{O}(1/n)$ with
$m\asymp n^{3}$ and $\eta T\asymp n$ in a low-noise case. Corollary 5 recovers
their results with the same conditions on $m$ and $\eta T$ for this setting.

[35] studied GD with weakly convex losses and showed that the excess
population risk is controlled by $\mathcal{O}\big{(}\frac{\eta
TL^{2}}{n}+\frac{\|\mathbf{W}_{\epsilon}-\mathbf{W}_{0}\|_{2}^{2}}{\eta
T}+\epsilon(\eta T+\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2})\big{)}$ if
$2\eta\epsilon<1/T$ when the empirical risk is $\epsilon$-weakly convex and
$L$-Lipschitz continuous, where
$\mathbf{W}_{\epsilon}=\arg\min_{\mathbf{W}}L_{S}(\mathbf{W})+\epsilon\|\mathbf{W}-\mathbf{W}_{0}\|_{2}^{2}$.
If the approximation error is small enough, then the $\mathcal{O}(1/\sqrt{n})$
bound can be achieved by choosing $\eta T=\sqrt{n}$ if
$\|\mathbf{W}_{\epsilon}\|_{2}=\mathcal{O}(1)$. Indeed, their excess risk
bound will not converge for the general case. Specifically, note that
$L_{S}(\mathbf{W}_{\epsilon})+\epsilon\|\mathbf{W}_{\epsilon}-\mathbf{W}_{0}\|_{2}^{2}\leq
L_{S}(0)+\epsilon\|\mathbf{W}_{0}\|_{2}^{2}$, then there holds
$\|\mathbf{W}_{\epsilon}-\mathbf{W}_{0}\|_{2}^{2}=\mathcal{O}(1/\epsilon)$.
The simultaneous appearance of $\frac{1}{\eta T\epsilon}$ and $\eta T\epsilon$
causes the non-vanishing error bound. [35] also investigated the weak
convexity of two-layer NNs with a smooth activation function. Under the
assumption that the derivative of the loss function is uniformly bounded by a
constant, they proved that the weak convexity parameter is controlled by
$\mathcal{O}(d/m^{c})$. We provide a dimension-independent weak convexity
parameter which further yields a dimension-independent excess risk rate
$\mathcal{O}(1/\sqrt{n})$. More discussion can be found in Appendix A.3.

###  3.2 Three-layer Neural Networks with Scaling Parameters

Now, we present our results for three-layer NNs. Let
$\hat{\rho}=4B_{2}(1+2B_{1})$, where $B_{1},B_{2}>0$ are constants depending
on $c_{\mathbf{x}},B_{\sigma^{\prime}},B_{\sigma^{\prime\prime}}$ and $c_{0}$,
whose specific forms are given in Appendix B.1. Let
$\mathcal{B}_{T}=\sqrt{\eta T}+\|\mathbf{W}_{0}\|_{2}$. We first present the
generalization bounds for three-layer NNs.

######  Theorem 6 (Generalization error).

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta_{t}\equiv\eta\leq 1/(8\hat{\rho})$ based on $S$. Assume

$\displaystyle m\gtrsim(\eta T)^{4}+(\eta
T)^{\frac{1}{4c-2}}+\|\mathbf{W}_{0}\|_{2}^{\frac{4}{8c-3}}+\|\mathbf{W}_{0}\|_{2}^{\frac{1}{6c-3}}+\big{(}(\eta
T\mathcal{B}_{T})^{2}+\frac{(\eta
T)^{\frac{7}{2}}\mathcal{B}_{T}}{n}\big{)}^{\frac{1}{5c-\frac{1}{2}}}$
$\displaystyle+\big{(}(\eta T)^{\frac{3}{2}}\mathcal{B}_{T}^{2}+\frac{(\eta
T)^{3}\mathcal{B}_{T}}{n}\big{)}^{\frac{1}{4c-1}}+\big{(}(\eta
T)^{2}\mathcal{B}_{T}+\frac{(\eta
T)^{\frac{7}{2}}}{n}\big{)}^{\frac{1}{5c-1}}+\big{(}(\eta
T)^{\frac{3}{2}}\mathcal{B}_{T}+\frac{(\eta
T)^{3}}{n}\big{)}^{\frac{1}{4c-\frac{3}{2}}}.$ (6)

Then, for any $t\in[T]$,

$\mathbb{E}[L(\mathbf{W}_{t})-L_{S}(\mathbf{W}_{t})]\leq\Big{(}\frac{4e^{2}\eta^{2}\hat{\rho}^{2}t}{n^{2}}+\frac{4e\eta\hat{\rho}}{n}\Big{)}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}.$

Similar to Theorem 2, Theorem 6 also implies that a larger scaling $c$ relaxes
the requirement on $m$.

######  Remark 4.

As compared to two-layer NNs, the analysis of three-layer NNs is more
challenging since we can only show that
$\lambda_{\max}\big{(}\nabla^{2}\ell(\mathbf{W};z)\big{)}\leq\rho_{\mathbf{W}}$
where $\rho_{\mathbf{W}}$ depends on $\|\mathbf{W}\|_{2}$, i.e., the
smoothness parameter of $\ell$ relies on the upper bound of $\mathbf{W}$,
while that of two-layer NNs is uniformly bounded. In this way, three-layer NNs
do not enjoy the almost co-coercivity, which is the key step to control the
stability of GD. To handle this problem, we first establish a crude estimate
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$ for any $c>1/2$ by
induction strategy. By using this estimate, we can further show that
$\rho_{\mathbf{W}}\leq\hat{\rho}$ with $\hat{\rho}=\mathcal{O}(1)$ for any
$\mathbf{W}$ produced by GD iterates if $m$ satisfies (6). Finally, by
assuming $\eta\leq 1/(2\hat{\rho})$ we build the upper bound
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2c_{0}\eta t}$. However, for
the case $c=1/2$, we cannot get a similar bound due to the condition
$m^{2-4c}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}^{2}=\mathcal{O}(m^{2c-1})$.
Specifically, the upper bound of $\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}$ in
this case contains a worse term $2^{t}$, which is not easy to control.
Therefore, we only consider $c\in(1/2,1]$ for three-layer NNs. The estimate of
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}$ when $c=1/2$ remains an open problem.
The detailed proof of the theorem is given in Appendix B.1.

Let
$\hat{C}_{\mathbf{W}}=4B_{1}\big{(}m^{-3c}(\|\mathbf{W}\|_{2}^{2}+2c_{0}\eta
T)+m^{\frac{1}{2}-2c}(\|\mathbf{W}\|_{2}+\sqrt{2c_{0}\eta T})\big{)}$ and
$\hat{B}_{\mathbf{W}}=\big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-1/2}}(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{)}(2\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}\|_{2})+\sqrt{2c_{0}}$ . The following theorem gives
optimization error bounds for three-layer NNs. The proof is given in Appendix
B.2.

######  Theorem 7 (Optimization error).

Let Assumptions 1, 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by (2) with
$\eta_{t}\equiv\eta\leq 1/(8\hat{\rho})$. Let $\mathcal{C}_{T,n}=\eta
T+\eta^{3}T^{2}/n^{2}$. Assume (6) and

$\displaystyle m\gtrsim$
$\displaystyle(\mathcal{C}_{T,n}(\mathcal{B}_{T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\|_{2})^{4})^{\frac{1}{5c-\frac{1}{2}}}\\!+\\!(\mathcal{C}_{T,n}(\mathcal{B}_{T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\|_{2})^{3})^{\frac{1}{4c-1}}\\!+\\!(\mathcal{C}_{T,n}(\mathcal{B}_{T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\|_{2})^{2})^{\frac{1}{4c-\frac{3}{2}}}$
$\displaystyle+(\mathcal{C}_{T,n}(\mathcal{B}_{T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\|_{2}))^{\frac{1}{2c-\frac{1}{2}}}.$ (7)

Then we have

$\displaystyle\mathbb{E}\big{[}L_{S}(\mathbf{W}_{T})]-L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}\big{]}$
$\displaystyle\leq\hat{C}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\hat{B}_{\mathbf{W}^{*}_{\frac{1}{\eta
T}}}\big{(}\big{(}\frac{4e^{2}\eta^{3}T^{2}\hat{\rho}^{2}}{n^{2}}+\frac{4e\eta^{2}T\hat{\rho}}{n}\big{)}\sum_{s=0}^{T-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}+\eta T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}\big{)}.$

Now, we develop excess risk bounds of GD for three-layer NNs by combining
Theorem 6 and Theorem 7 together. The proof is given in Appendix B.3.

######  Theorem 8 (Excess population risk).

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta\leq 1/(8\hat{\rho})$. Assume (6) and (7) hold. For any
$c\in(1/2,1]$, if $n\gtrsim\eta T$, then there holds

$\mathbb{E}[L(\mathbf{W}_{T})\\!-\\!L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T}{n}L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

Finally, we establish excess risk bounds of GD for three-layer NNs by assuming
Assumption 3 holds.

######  Corollary 9.

Let assumptions in Theorem 8 and Assumption 3 hold. The following statements
hold.

  1. (a)

Assume $\mu\geq 1/2$. If $c\in[9/16,1]$, we can choose $m\asymp(\eta T)^{4}$
and $\eta T$ such that $n^{\frac{1}{2(8\mu-3)}}\lesssim\eta
T\lesssim\sqrt{n}$. If $c\in(1/2,9/16)$, we can choose $m\asymp(\eta
T)^{\frac{1}{4c-2}}$ and $\eta T$ such that
$n^{\frac{2c-1}{2\mu+4c-3}}\lesssim\eta T\lesssim\sqrt{n}$. Then

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{\sqrt{n}}\big{)}.$

  2. (b)

Assume $L(\mathbf{W}^{*})=0$ and $\mu\geq 1/2$. If $c\in[9/16,1]$, we can
choose $m\asymp(\eta T)^{4}$ and $\eta T\gtrsim n^{\frac{1}{8\mu-3}}$. If
$c\in(1/2,9/16)$, we can choose $m\asymp(\eta T)^{\frac{1}{4c-2}}$ and $\eta
T$ such that $\eta T\gtrsim n^{\frac{4c-2}{4c+2\mu-3}}$. Then

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{n}\big{)}.$

Discussion of the Results:  Part (a) in Corollary 9 shows GD for three-layer
NNs can achieve the excess risk rate $\mathcal{O}(1/\sqrt{n})$ with
$m\asymp(\eta T)^{4}$ and $n^{\frac{1}{2(8\mu-3)}}\lesssim\eta
T\lesssim\sqrt{n}$ for the case $c\in[9/16,1]$ and $m\asymp(\eta
T)^{\frac{1}{4c-2}}$ and $n^{\frac{2c-1}{2\mu+4c-3}}\lesssim\eta
T\lesssim\sqrt{n}$ for the case $c\in(1/2,9/16)$, respectively. Note that
there is an additional assumption $\mu\geq 1/2$ in part (a). Combining this
assumption with $\|\mathbf{W}^{*}\|_{2}\leq m^{\frac{1}{2}-\mu}$ together, we
know that the population risk minimizer $\mathbf{W}^{*}$ cannot be too large
to reach the power of the exponent of $m$. The potential reason is that we use
a constant to bound the smoothness parameter in the analysis for three-layer
NNs. Part (a) also indicates a quantitative condition in terms of $m$ and $c$
where GD for three-layer NNs can achieve the excess risk rate
$\mathcal{O}(1/\sqrt{n})$ in under-parameterization and over-parameterization
regimes, which is interpreted in the right panel of Figure 1. The results in
part (a) tell us that the smallest width for guaranteeing the desired bounds
are $m\asymp n^{\frac{2}{8\mu-3}}$ for $c\in[9/16,1]$ and $m\asymp
n^{\frac{1}{2(2\mu+4c-3)}}$ for $c\in(1/2,9/16)$. Similar to the left panel of
Figure 1, the dotted lines $\mu=\frac{5}{8}$ and $\mu=\frac{7}{4}-2c$ in the
right panel of Figure 1 correspond to the setting $m\asymp n$, i.e.,
$\frac{2}{8\mu-3}=1$ and $\frac{1}{2(2\mu+4c-3)}=1$. Hence, when $c$ and $\mu$
belong to the blue region with dots, under-parameterization is sufficient to
achieve the desired rate. When $c$ and $\mu$ are located in the blue region
without dots which is between the solid lines and the dotted line, over-
parameterization is necessary for GD to achieve the rate
$\mathcal{O}(1/\sqrt{n})$. Our results for three-layer NNs also imply that the
over-parameterization does bring benefit for GD to achieve good generalization
in the sense that GD can achieve excess risk rate $\mathcal{O}(1/\sqrt{n})$.
Under a low-noise condition, part (b) implies that the excess risk rate can be
improved to $\mathcal{O}(1/n)$ with suitable choices of $m$ and $\eta T$.
These results imply that the larger the scaling parameter is, the less over-
parameterization is needed for GD to achieve the desired error rate for both
the general case and low-noise case.

Comparison with the Existing Work: [35] studied the minimal eigenvalue of the
empirical risk Hessian for a three-layer NN with a linear activation in the
first layer for Lipschitz and convex losses (e.g., logistic loss), while we
focus on NNs with more general activation functions for least square loss. See
more detailed discussion in Appendix B.4. [20] studied the generalization
performance of overparameterized three-layer NTK models with the absolute loss
and ReLU activation. They showed that the generalization error is in the order
of $\mathcal{O}(1/\sqrt{n})$ when there are infinitely many neurons. They only
trained the middle-layer weights of the networks. To the best of our
knowledge, our work is the first study on the stability and generalization of
GD to train both the first and the second layers of the network in the kernel-
free regime.

##  4 Main Idea of the Proof

In this section, we present the main ideas for proving the main results in
Section 3.

Two-layer Neural Networks. (2) decomposes the excess population risk into
three terms: generalization error, optimization error and approximation error.
We estimate these three terms separately.

Generalization error. From Lemma 1 we know the generalization error can be
upper bounded by the on-average argument stability of GD. Hence, it remains to
figure out the on-average argument stability of GD. A key step in our
stability analysis is to show that the loss is strongly smooth and weakly
convex, which can be obtained by the following results given in Lemma A.2:

$\lambda_{\max}\\!\big{(}\nabla^{2}\ell(\mathbf{W};z)\big{)}\\!\leq\\!\rho\text{
and
}\lambda_{\min}\\!\big{(}\nabla^{2}\ell(\mathbf{W};z)\big{)}\\!\geq\\!-\big{(}c_{\mathbf{x}}^{3}B_{\sigma^{\prime}}\\!B_{\sigma^{\prime\prime}}m^{\frac{1}{2}-2c}\|\mathbf{W}\\!-\\!\mathbf{W}_{\\!0}\|_{2}+c_{\mathbf{x}}^{2}B_{\sigma}\\!\sqrt{2c_{0}}m^{-c}\\!\big{)}.$

Here $\rho=\mathcal{O}(m^{1-2c})$, $\lambda_{\max}(A)$ and $\lambda_{\min}(A)$
denote the largest and the smallest eigenvalue of $A$, respectively. The lower
bound of $\lambda_{\min}\\!(\nabla^{2}\ell(\mathbf{W};z))$ is related to
$\|\mathbf{W}-\mathbf{W}_{0}\|_{2}$, we further show it is uniformly bounded
(see the proof of Theorem A.5). Then the smoothness and weak convexity of the
loss scale with $m^{1-2c}$ and $m^{c}$, which implies that the loss becomes
more smooth and more convex for wider networks with a larger scaling.

Based on the above results, we derive the following uniform stability bounds
$\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}\leq\frac{2\eta
eT\sqrt{2c_{0}\rho(\rho\eta T+2)}}{n}.$ Here, the weak convexity of the loss
plays an important role in presenting the almost co-coercivity of the gradient
operator, which helps us establish the recursive relationship of
$\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}$. Note
$\rho=\mathcal{O}(m^{1-2c})=\mathcal{O}(1)$. Then we know
$\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}=\mathcal{O}(\frac{m^{1-2c}}{n}(\eta
T)^{3/2})$, which implies that GD is more stable for a wider neural network
with a large scaling. For a specific case $c=1/2$, our stability bound is in
the order of $\mathcal{O}((\eta T)^{3/2}/n)$, and matches the result in [23].

Optimization error. A key step in optimization error analysis is to use the
smoothness and weak convexity to control

$\mathbb{E}[\|\mathbf{W}_{\\!\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{t}\|_{2}^{2}]\\!\leq\\!\big{(}\frac{8e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}\\!+\\!\frac{8e\eta^{2}t\rho}{n}\big{)}\\!\sum_{s=0}^{t-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\\!+\\!2\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}\\!+\\!2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})\\!-\\!L(\mathbf{W}^{*})\big{]}$

in Lemma A.2. Here, to remove the condition $\mathbb{E}[L(\mathbf{W}_{s})]\geq
L(\mathbf{W}^{*}_{\frac{1}{\eta T}})$ for any $s\in[T]$ in [23], we use
$L(\mathbf{W}^{*}_{\frac{1}{\eta T}})-L(\mathbf{W}_{s})\leq
L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}^{*})\leq\Lambda_{\frac{1}{\eta T}},$ where the first
inequality is due to $L(\mathbf{W}_{s})\geq L(\mathbf{W}^{*})$ for any
$s\in[T]$. Then the optimization error can be controlled by the monotonically
decreasing property of $\\{L_{S}(\mathbf{W}_{t})\\}$. The proofs are given in
Appendix A.2.

Excess population risk. Combining stability bounds, optimization bounds and
approximation error together, and noting that $L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}\leq L(\mathbf{W}^{*})+\frac{1}{2\eta
T}\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}^{2}$, one can get the final error
bound. The detailed proof can be found in Appendix A.3.

Three-layer Neural Networks. The basic idea to study the generalization
behavior of GD for three-layer NNs is similar to that of two-layer NNs. We
develop stability bounds and control the generalization error by figuring out
the smoothness and curvature of the loss function:
$\lambda_{\max}(\nabla^{2}\ell(\mathbf{W};z))\leq\rho_{\mathbf{W}}$ and
$\lambda_{\min}(\nabla^{2}\ell(\mathbf{W};z))\\!\geq\\!-C_{\mathbf{W}}(\frac{2B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\|\mathbf{W}^{(2)}\|_{2}+\sqrt{2c_{0}}),$
where $\rho_{\mathbf{W}}$ and $C_{\mathbf{W}}$ depend on $\|\mathbf{W}\|_{2}$.
The specific forms of $\rho_{\mathbf{W}}$ and $C_{\mathbf{W}}$ are given in
Appendix B.1. As mentioned in Remark 4, it is not easy to estimate
$\|\mathbf{W}_{t}\|_{2}$ since the smoothness of the loss relies on the norm
of $\mathbf{W}$ in this case. We address this difficulty by first giving a
rough bound of $\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}$ by induction, i.e.,
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$. Then, for any
$\mathbf{W}$ produced by GD iterates, we can control $\rho_{\mathbf{W}}$ by a
constant $\hat{\rho}$ if $m$ is large enough. Finally, by assuming
$\eta\hat{\rho}\leq 1/2$, we prove that
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2c_{0}\eta t}$ and further get
$\|\mathbf{W}_{t}\|_{2}\leq\|\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}\eta t}$.

After estimating $\|\mathbf{W}_{t}\|_{2}$, we can develop the following almost
co-coercivity of the gradient operator:

$\displaystyle\langle\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\rangle\geq$ $\displaystyle
2\eta\big{(}1-4\eta\hat{\rho}\big{)}\big{\|}\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\big{\|}_{2}^{2}$
$\displaystyle-\tilde{\epsilon}_{t}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}.$

It helps to establish the uniform stability bound
$\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}\leq 2e\eta
T\sqrt{2c_{0}\hat{\rho}(\hat{\rho}\eta T+2)}/n.$ Based on stability bounds, we
get generalization bounds by Lemma 1. The proofs are given in Appendix B.1.

Similar to two-layer NNs, to estimate the optimization error for three-layer
NNs, we first control $\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{t}\|_{2}^{2}]$ by using the smoothness and weak convexity of
the loss. Then the desired bound can be obtained by the monotonically
decreasing property of $\\{L_{S}(\mathbf{W}_{t})\\}$. The final error bounds
(Theorem 8 and Corollary 9) can be derived by plugging generalization and
optimization bounds back into (2). The detailed proof can be found in Appendix
B.3.

##  5 Conclusion

We present stability and generalization analysis of GD for multi-layer NNs
with generic network scaling factors. Under some qualitative conditions on the
network scaling and the network complexity, we establish excess risk bounds of
the order $\mathcal{O}(1/\sqrt{n})$ for GD on both two-layer and three-layer
NNs, which are improved to $\mathcal{O}(1/n)$ with an additional low-noise
condition. Our results describe a quantitative condition related to the
scaling factor and the network complexity under which GD on two-layer and
three-layer NNs can achieve the desired excess risk rate.

There remain several questions for further study. The first question is
whether our analysis of GD for multi-layer NNs can be extended to SGD with
less computation cost. The key challenge here is that the analysis for GD
relies critically on the monotonicity of the objective functions along the
optimization process, which does not hold for SGD. Second, our analysis for
three-layer NNs does not hold for $c=1/2$. It would be interesting to develop
a result for this setting. Finally, the results in Corollaries 5 and 9 hold
true for $\mu\geq 1/6$ or $\mu\geq 1/2$. It remains an open question to us
whether we can get a generalization error bound $\mathcal{O}(1/\sqrt{n})$ when
$\mu$ is small.

Acknowledgement. The work of Ding-Xuan Zhou was partially supported by the
Laboratory for AI-Powered Financial Technologies under the InnoHK scheme. The
corresponding author is Yiming Ying whose work was supported by NSF research
grants (DMS-2110836, IIS-2103450, and IIS-2110546). Di Wang was supported in
part by BAS/1/1689-01-01, URF/1/4663-01-01, FCC/1/1976-49-01 of KAUST, and a
funding of the SDAIA-KAUST AI center.

Appendix for “Generalization Guarantees of Gradient Descent for Multi-Layer
Neural Networks”

##  Appendix A Proofs of Two-layer Neural Networks

###  A.1 Proofs of Generalization Bounds

We first introduce the self-bounding property of smooth functions [37].

######  Lemma A.1 (Self-bounding property).

Suppose for all $z\in\mathcal{Z}$, the function
$\mathbf{W}\mapsto\ell(\mathbf{W};z)$ is nonnegative and $\rho$-smooth. Then
$\|\nabla\ell(\mathbf{W};z)\|_{2}^{2}\leq 2\rho\ell(\mathbf{W};z)$.

We work with vectorized quantities so $\mathbf{W}\in\mathbb{R}^{md}$. Then
$\nabla f_{\mathbf{W}}(\mathbf{x})\in\mathbb{R}^{md}$ and
$\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\in\mathbb{R}^{md\times md}.$ Denote by
$\|\mathbf{W}\|_{op}$ the spectral norm of a matrix $\mathbf{W}$. We first
introduce the following lemma, which shows that the loss function is smooth
and weakly convex.

######  Lemma A.2 (Smoothness and Curvature).

Suppose Assumptions 1 and 2 hold. Let $\mathbf{W}_{0}$ be the initial point of
GD. For any fixed $\mathbf{W}\in\mathbb{R}^{m\times d}$ and any
$z\in\mathcal{Z}$, there holds

$\lambda_{\max}\\!\big{(}\nabla^{2}\\!\ell(\mathbf{W};z)\big{)}\\!\leq\\!\rho\text{
with
}\rho\\!=\\!c_{\mathbf{x}}^{2}\Big{(}\frac{\\!B_{\sigma^{\prime}}^{2}\\!+\\!B_{\sigma}\\!B_{\sigma^{\prime\prime}}\\!}{m^{2c-1}}\\!+\\!\frac{\\!B_{\sigma^{\prime\prime}}c_{y}}{m^{c}}\\!\Big{)}.$
$\lambda_{\min}\\!\big{(}\nabla^{2}\\!\ell(\mathbf{W};z)\big{)}\\!\geq\\!-\\!\Big{(}\\!\frac{c_{\mathbf{x}}^{3}B_{\sigma^{\prime}}\\!B_{\sigma^{\prime\prime}}\\!}{m^{2c-\frac{1}{2}}}\\!\|\mathbf{W}\\!-\\!\mathbf{W}_{0}\|_{2}\\!+\\!\frac{\\!c_{\mathbf{x}}^{2}B_{\sigma}\\!\sqrt{2c_{0}}\\!}{m^{c}}\Big{)}.$

###### Proof.

Recall that
$f_{\mathbf{W}}(\mathbf{x})=\frac{1}{m^{c}}\sum_{k=1}^{m}a_{k}\sigma(\mathbf{w}_{k}\mathbf{x})$.
Let $\mathbf{v}=(\mathbf{v}_{1},\ldots,\mathbf{v}_{m})\in\mathbb{R}^{dm}$ with
$\mathbf{v}_{k}\in\mathbb{R}^{d}$ where $k\in[m]$. According to Assumption 1,2
and noting that $|a_{k}|=1$, we can give the following estimations:

$\displaystyle\|\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\|_{op}$
$\displaystyle=\max_{\mathbf{v}:\|\mathbf{v}\|_{2}\leq
1}\sum_{k=1}^{m}\frac{a_{k}}{m^{c}}\langle\mathbf{v}_{k},\mathbf{x}\rangle^{2}\sigma^{\prime\prime}(\mathbf{w}_{k}\mathbf{x})$
$\displaystyle\leq\frac{\|\mathbf{x}\|_{2}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\max_{\mathbf{v}:\|\mathbf{v}\|_{2}\leq
1}\sum_{k=1}^{m}\|\mathbf{v}_{k}\|_{2}^{2}$
$\displaystyle\leq\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}},$
(A.1) $\|\nabla
f_{\mathbf{W}}(\mathbf{x})\|_{2}^{2}=\sum_{k=1}^{m}\big{\|}\frac{a_{k}}{m^{c}}\mathbf{x}\sigma^{\prime}(\mathbf{w}_{k}\mathbf{x})\big{\|}_{2}^{2}\leq\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}^{2}}{m^{2c-1}}$
(A.2)

and

$\big{|}f_{\mathbf{W}}(\mathbf{x})-y\big{|}\leq\big{|}f_{\mathbf{W}}(\mathbf{x})\big{|}+c_{y}\leq
m^{1-c}B_{\sigma}+c_{y}.$ (A.3)

Note

$\nabla^{2}\ell(\mathbf{W};z)=\nabla f_{\mathbf{W}}(\mathbf{x})\nabla
f_{\mathbf{W}}(\mathbf{x})^{\top}+\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\big{(}f_{\mathbf{W}}(\mathbf{x})-y\big{)}.$
(A.4)

Then for any $\mathbf{W}\in\mathbb{R}^{md}$, we can upper bound the maximum
eigenvalue of the Hessian as

$\displaystyle\lambda_{\max}(\nabla^{2}\ell(\mathbf{W};z))$
$\displaystyle\leq\|\nabla
f_{\mathbf{W}}(\mathbf{x})\|_{2}^{2}+\|\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\|_{op}|f_{\mathbf{W}}(\mathbf{x})-y|$
$\displaystyle\leq\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}^{2}}{m^{2c-1}}+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\big{(}m^{1-c}B_{\sigma}+c_{y}\big{)}$
$\displaystyle=c_{\mathbf{x}}^{2}\Big{(}\frac{B_{\sigma^{\prime}}^{2}+B_{\sigma}B_{\sigma^{\prime\prime}}}{m^{2c-1}}+\frac{B_{\sigma^{\prime\prime}}c_{y}}{m^{c}}\Big{)},$

which implies that the loss function is $\rho$-smooth with
$\rho=c_{\mathbf{x}}^{2}\big{(}\frac{B_{\sigma^{\prime}}^{2}+B_{\sigma}B_{\sigma^{\prime\prime}}}{m^{2c-1}}+\frac{B_{\sigma^{\prime\prime}}c_{y}}{m^{c}}\big{)}$.

For any $\mathbf{W},\mathbf{W}^{\prime}\in\mathbb{R}^{md}$, from Assumption 1
we know

$\big{|}f_{\mathbf{W}}(\mathbf{x})-f_{\mathbf{W}^{\prime}}(\mathbf{x})\big{|}\leq\frac{1}{m^{c}}\sum_{k=1}^{m}\big{|}\sigma(\mathbf{w}_{k}\mathbf{x})-\sigma(\mathbf{w}_{k}^{\prime}\mathbf{x})\big{|}\leq\frac{B_{\sigma^{\prime}}}{m^{c}}\sum_{k=1}^{m}\big{|}(\mathbf{w}_{k}-\mathbf{w}_{k}^{\prime})\mathbf{x}\big{|}\leq\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}^{\prime}\|_{2}.$
(A.5)

Combining (A.4) with the fact that $\nabla f_{\mathbf{W}}(\mathbf{x})\nabla
f_{\mathbf{W}}(\mathbf{x})^{\top}$ is positive semi-definite together, we
obtain

$\displaystyle\lambda_{\min}(\nabla^{2}\ell(\mathbf{W};z))$
$\displaystyle\geq-\|\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\|_{op}\big{|}f_{\mathbf{W}}(\mathbf{x})-y\big{|}$
$\displaystyle\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\big{|}f_{\mathbf{W}}(\mathbf{x})-f_{\mathbf{W}_{0}}(\mathbf{x})\big{|}+\big{|}f_{\mathbf{W}_{0}}(\mathbf{x})-y\big{|}\Big{)}$
$\displaystyle\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{{}^{\prime\prime}}}}{m^{c}}\Big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{0}\|_{2}+\sqrt{2\ell(\mathbf{W}_{0};z)}\Big{)}$
$\displaystyle\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{{}^{\prime\prime}}}}{m^{c}}\Big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)},$
(A.6)

where in the third inequality we used (A.5) with
$\mathbf{W}^{\prime}=\mathbf{W}_{0}$ and in the last inequality we used
Assumption 2. The proof is completed. ∎

To give an upper bound of the uniform stability, we need the following lemma
which shows how the GD iterate will deviate from the initial point.

######  Lemma A.3 ([34]).

Suppose the loss is $\rho$-smooth and $\eta\leq 1/(2\rho)$. Then for any
$t\geq 0$, $i\in[n]$,

$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2\eta
tL_{S}(\mathbf{W}_{0})},$
$\|\mathbf{W}_{t}^{(i)}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2\eta
tL_{S^{(i)}}(\mathbf{W}_{0})}.$

The following lemma shows an almost co-coercivity of the gradient operator
associated with shallow neural networks. For any $i\in[n]$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z^{\prime}_{i},z_{i+1},\ldots,z_{n}\\}$ as
the set formed from $S$ by replacing the $i$-th element with $z_{i}^{\prime}$.
For any $\mathbf{W}\in\mathcal{W}$,

$L_{S^{\setminus
i}}(\mathbf{W})=L_{S}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i})=L_{S^{(i)}}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i}^{\prime}).$

Let $\\{\mathbf{W}_{t}\\}$ and $\\{\mathbf{W}_{t}^{(i)}\\}$ be the sequence
produced by GD based on $S$ and $S^{(i)}$, respectively.

######  Lemma A.4 (Almost Co-coercivity of the Gradient Operator).

Suppose the loss is $\rho$-smooth and $\eta\leq 1/(2\rho)$. Then

$\displaystyle\langle\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus i}}$
$\displaystyle(\mathbf{W}^{(i)}_{t})\rangle\geq
2\eta\Big{(}1-\frac{\eta\rho}{2}\Big{)}\big{\|}\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\big{\|}_{2}^{2}$
$\displaystyle-\epsilon_{t}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2},$

where
$\epsilon_{t}=\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}(1+\eta\rho)\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}$.

###### Proof.

This lemma can be proved in a similar way as Lemma 5 in [34] except the
estimation of the eigenvalue of Hessian matrix. Specifically, for
$\alpha\in[0,1]$, let
$\mathbf{W}(\alpha)=\alpha\mathbf{W}_{t}+(1-\alpha)\mathbf{W}_{t}^{(i)}-\alpha\eta\big{(}\nabla\ell(\mathbf{W}_{t};z)-\nabla\ell(\mathbf{W}_{t}^{(i)};z)\big{)}$.
According to (A.1) and (A.4) , for any $\mathbf{W}\in\mathcal{W}$, we know

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S^{\setminus
i}}(\mathbf{W})\big{)}\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{1}{n}\sum_{j\in[n],j\neq
i}|f_{\mathbf{W}}(\mathbf{x}_{j})-y_{j}|\Big{)}.$

Let $\mathbf{W}=\mathbf{W}(\alpha)$. Note Lemma A.2 shows that the loss is
$\rho$-smooth with
$\rho=c_{\mathbf{x}}^{2}\big{(}\frac{B_{\sigma^{\prime}}^{2}+B_{\sigma}B_{\sigma^{\prime\prime}}}{m^{2c-1}}+\frac{B_{\sigma^{\prime\prime}}c_{y}}{m^{c}}\big{)}$.
Then from (A.5) and the smoothness of $\ell$ we can get

$\displaystyle\frac{1}{n}\sum_{j\in[n],j\neq
i}|f_{\mathbf{W}(\alpha)}(\mathbf{x}_{j})-y_{j}|$
$\displaystyle\leq\frac{1}{n}\sum_{j\in[n],j\neq
i}|(f_{\mathbf{W}(\alpha)}(\mathbf{x}_{j})-f_{\mathbf{W}_{t}^{(i)}}(\mathbf{x}_{j}))+(f_{\mathbf{W}_{t}^{(i)}}(\mathbf{x}_{j})-f_{\mathbf{W}_{0}}(\mathbf{x}_{j}))+(f_{\mathbf{W}_{0}}(\mathbf{x}_{j})-y_{j})|$
$\displaystyle\leq\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}\|\mathbf{W}(\alpha)-\mathbf{W}_{t}^{(i)}\|_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}\|\mathbf{W}_{t}^{(i)}-\mathbf{W}_{0}\|_{2}+\sqrt{2L_{S^{\setminus
i}}(\mathbf{W}_{0})}$
$\displaystyle\leq\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\alpha}{m^{c-1/2}}\big{(}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+\eta\|\nabla\ell(\mathbf{W}_{t};z)-\nabla\ell(\mathbf{W}_{t}^{(i)};z)\|_{2}\big{)}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}$
$\displaystyle\leq\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}(1+\eta\rho)}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}},$

where in the third inequality we used Lemma A.3 and
$\ell(\mathbf{W}_{0};z)\leq c_{0}$.

Combining the above two inequalities together, we get

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S^{\setminus
i}}(\mathbf{W}(\alpha))\big{)}$
$\displaystyle\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}(1+\eta\rho)}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}.$

Similarly, let
$\widetilde{\mathbf{W}}(\alpha)=\alpha\mathbf{W}_{t}^{(i)}+(1-\alpha)\mathbf{W}_{t}-\alpha\eta\big{(}\nabla\ell(\mathbf{W}_{t}^{(i)};z))-\nabla\ell(\mathbf{W}_{t};z)\big{)}$,
we can prove that

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S^{\setminus
i}}(\widetilde{\mathbf{W}}(\alpha))\big{)}$
$\displaystyle\geq-\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}(1+\eta\rho)}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}.$

The remaining arguments in proving the lemma are the same as Lemma 5 in [34].
We omit the proof for simplicity. ∎

Based on the almost co-coercivity property of the gradient operator, we give
the following uniform stability theorem.

######  Theorem A.5 (Uniform Stability).

Suppose Assumptions 1 and 2 hold. Let $S,S^{(i)}$ be constructed in Definition
2. Let $\\{\mathbf{W}_{t}\\}$ and $\\{\mathbf{W}_{t}^{(i)}\\}$ be produced by
(2) with $\eta\leq 1/(2\rho)$ based on $S$ and $S^{(i)}$, respectively. Assume
(4) holds. For any $t\in[T]$, there holds

$\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}\leq\frac{2\eta
eT\sqrt{2c_{0}\rho(\rho\eta T+2)}}{n}.$

###### Proof.

Recall that

$L_{S^{\setminus
i}}(\mathbf{W})=L_{S}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i})=L_{S^{(i)}}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i}^{\prime}).$

Note $\mathcal{W}=\mathbb{R}^{m\times d}$. Then by the update rule
$\mathbf{W}_{t+1}=\mathbf{W}_{t}-\eta\nabla L_{S}(\mathbf{W}_{t})$, there
holds

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle=\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}-\frac{\eta}{n}\big{(}\nabla\ell(\mathbf{W}_{t};z_{i})-\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{)}\big{\|}_{2}^{2}$
$\displaystyle\leq(1+p)\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle\quad+\frac{\eta^{2}(1+1/p)}{n^{2}}\big{\|}\nabla\ell(\mathbf{W}_{t};z_{i})-\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}$
$\displaystyle\leq(1+p)\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle\quad+\frac{2\eta^{2}(1+1/p)}{n^{2}}\Big{(}\big{\|}\nabla\ell(\mathbf{W}_{t};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\Big{)},$
(A.7)

where in the first inequality we used $(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$.

According to Lemma A.4 we can get

$\displaystyle\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle=\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\eta^{2}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}^{2}$
$\displaystyle\quad-2\eta\Big{\langle}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\Big{\rangle}$
$\displaystyle\leq\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\eta^{2}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}^{2}$
$\displaystyle\quad-4\eta^{2}\Big{(}1-\frac{\eta\rho}{2}\Big{)}\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\big{\|}_{2}^{2}$
$\displaystyle\quad+2\eta\epsilon_{t}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2},$

where
$\epsilon_{t}=\frac{c_{\mathbf{x}}B_{\sigma^{\prime\prime}}}{m^{c}}\big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}(1+\eta\rho)\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\big{)}$.

Rearranging the above inequality and noting that $\eta\rho\leq 1/2$, we obtain

$\displaystyle(1-2\eta\epsilon_{t})\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2}$
$\displaystyle\leq\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\eta^{2}(2\eta\rho-3)\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}^{2}\leq\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}.$

We can choose $m$ large enough to ensure $2\eta\epsilon_{t}<1$ holds for any
$t\in[T]$. Indeed, $2\eta\epsilon_{t}<1$ holds as long as condition (4) holds.
We will discuss it at the end of the proof. Now, plugging the above inequality
back into (A.1) yields

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{1+p}{1-2\eta\epsilon_{t}}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}^{2}+\frac{2\eta^{2}(1+1/p)}{n^{2}}\Big{(}\big{\|}\nabla\ell(\mathbf{W}_{t};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{t}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\Big{)}.$
(A.8)

We can apply (A.1) recursively and derive

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}\leq$
$\displaystyle\frac{2\eta^{2}(1+1/p)}{n^{2}}\sum_{j=0}^{t}\Big{(}\big{\|}\nabla\ell(\mathbf{W}_{j};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\Big{)}\prod_{\tilde{j}=j+1}^{t}\frac{1+p}{1-2\eta\epsilon_{\tilde{j}}},$
(A.9)

where we used $\mathbf{W}_{0}=\mathbf{W}_{0}^{(i)}$.

According to Lemma A.1 and Lemma A.3, we know

$\displaystyle\|\nabla\ell(\mathbf{W}_{j};z)\|_{2}^{2}$ $\displaystyle\leq
2\|\nabla\ell(\mathbf{W}_{j};z)-\nabla\ell(\mathbf{W}_{0};z)\|_{2}^{2}+2\|\nabla\ell(\mathbf{W}_{0};z)\|_{2}^{2}$
$\displaystyle\leq
2\rho^{2}\|\mathbf{W}_{j}-\mathbf{W}_{0}\|_{2}^{2}+4\rho\ell(\mathbf{W}_{0};z)\leq
4\rho^{2}\eta jL_{S}(\mathbf{W}_{0})+4\rho\ell(\mathbf{W}_{0};z).$

Similarly, we can show that

$\displaystyle\|\nabla\ell(\mathbf{W}_{j}^{(i)};z)\|_{2}^{2}\leq 4\rho^{2}\eta
jL_{S^{(i)}}(\mathbf{W}_{0})+4\rho\ell(\mathbf{W}_{0};z).$

Combining the above three inequalities together, we get

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{8\rho\eta^{2}(1+1/p)}{n^{2}}\sum_{j=0}^{t}\Big{(}\rho\eta
jL_{S}(\mathbf{W}_{0})+\ell(\mathbf{W}_{0};z_{i})+\rho\eta
jL_{S^{(i)}}(\mathbf{W}_{0})+\ell(\mathbf{W}_{0};z_{i}^{\prime})\Big{)}\prod_{\tilde{j}=j+1}^{t}\frac{1+p}{1-2\eta\epsilon_{\tilde{j}}}$
$\displaystyle\leq\frac{8\rho\eta^{2}(1+1/p)}{n^{2}}\prod_{\tilde{j}=1}^{t}\frac{1+p}{1-2\eta\epsilon_{\tilde{j}}}\sum_{j=0}^{t}\Big{(}\rho\eta
jL_{S}(\mathbf{W}_{0})+\ell(\mathbf{W}_{0};z_{i})+\rho\eta
jL_{S^{(i)}}(\mathbf{W}_{0})+\ell(\mathbf{W}_{0};z_{i}^{\prime})\Big{)}$
$\displaystyle=\frac{4\rho\eta^{2}(1+1/p)}{n^{2}}\prod_{\tilde{j}=1}^{t}\frac{1+p}{1-2\eta\epsilon_{\tilde{j}}}\Big{(}\rho\eta
t(t+1)\big{(}L_{S}(\mathbf{W}_{0})+L_{S^{(i)}}(\mathbf{W}_{0})\big{)}+2(t+1)\big{(}\ell(\mathbf{W}_{0};z_{i})$
$\displaystyle\quad+\ell(\mathbf{W}_{0};z_{i}^{\prime})\big{)}\Big{)}$
$\displaystyle\leq\frac{8\rho\eta^{2}c_{0}(1+1/p)(1+t)\big{(}\rho\eta
t+2\big{)}}{n^{2}}\prod_{\tilde{j}=1}^{t}\frac{1+p}{1-2\eta\epsilon_{\tilde{j}}},$

where we used $\ell(\mathbf{W}_{0};z)\leq c_{0}$ for any $z\in\mathcal{Z}$. If
we further choose $p=1/t$, then there holds

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{8\rho\eta^{2}c_{0}e(1+t)^{2}(\rho\eta
t+2)}{n^{2}}\prod_{\tilde{j}=1}^{t}\frac{1}{1-2\eta\epsilon_{\tilde{j}}},$
(A.10)

where we used $(1+1/t)^{t}\leq e$.

Now, we prove by induction to show

$\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}\leq\frac{2\eta
eT\sqrt{2c_{0}\rho(\rho\eta T+2)}}{n}.$ (A.11)

(A.11) with $k=0$ holds trivially. Assume (A.11) holds with all $k\leq t$,
i.e., for all $k\leq t$

$\big{\|}\mathbf{W}_{k}-\mathbf{W}_{k}^{(i)}\big{\|}_{2}\leq\frac{2\eta
eT\sqrt{2c_{0}\rho(\rho\eta T+2)}}{n}.$ (A.12)

and we want to show it holds with $k=t+1\leq T$. Recall that
$\epsilon_{k}=\frac{c_{\mathbf{x}}B_{\sigma^{\prime\prime}}}{m^{c}}\big{(}\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}}{m^{c-1/2}}(1+\eta\rho)\big{\|}\mathbf{W}_{k}-\mathbf{W}_{k}^{(i)}\big{\|}_{2}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\big{)}$. From (A.12), for any $\tilde{j}\leq
t$, we know

$\epsilon_{\tilde{j}}\leq\epsilon^{\prime}:=\frac{c_{\mathbf{x}}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{2\sqrt{2c_{0}\rho(\rho\eta
T+2)}\eta
eT(1+\eta\rho)c_{\mathbf{x}}B_{\sigma^{\prime}}}{nm^{c-1/2}}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}.$

Putting the above inequality back into (A.10), we get

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{8\rho\eta^{2}c_{0}e(1+t)^{2}(\rho\eta
t+2)}{n^{2}}\Big{(}\frac{1}{1-2\eta\epsilon^{\prime}}\Big{)}^{t}.$

If $m$ is large enough such that $2\eta\epsilon^{\prime}\leq 1/(t+1)$, then we
can show

$\Big{(}\frac{1}{1-2\eta\epsilon^{\prime}}\Big{)}^{t}\leq\Big{(}\frac{1}{1-1/(t+1)}\Big{)}^{t}\leq
e.$ (A.13)

Then there holds

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}$
$\displaystyle\leq\frac{2\eta e(1+t)\sqrt{2\rho c_{0}(\rho\eta
t+2)}}{n}\leq\frac{2\eta eT\sqrt{2\rho c_{0}(\rho\eta T+2)}}{n}.$ (A.14)

Now, we discuss the conditions on $m$. Suppose $m$ satisfies the following
conditions

$m\geq C_{1}\Big{(}\frac{(\eta T)^{2}(1+\eta\rho)\sqrt{\rho(\rho\eta
T+2)}}{n}\Big{)}^{\frac{2}{4c-1}},m\geq C_{2}(\eta T)^{\frac{3}{4c-1}}\text{
and }m\geq C_{3}\Big{(}\eta T\Big{)}^{\frac{1}{c}},$

where
$C_{1}=(8ec_{\mathbf{x}}^{2}B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}\sqrt{2c_{0}})^{\frac{2}{4c-1}}$,
$C_{2}=\big{(}4\sqrt{2c_{0}}c_{\mathbf{x}}^{2}B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}\big{)}^{\frac{3}{4c-1}}$
and $C_{3}=(8\sqrt{2c_{0}}c_{\mathbf{x}}B_{\sigma^{\prime\prime}})^{1/c}$.
Then it is easy to verify that

$\frac{2\eta
c_{\mathbf{x}}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{2\sqrt{2c_{0}\rho(\rho\eta
T+2)}\eta
eT(1+\eta\rho)c_{\mathbf{x}}B_{\sigma^{\prime}}}{nm^{c-1/2}}+\frac{c_{\mathbf{x}}B_{\sigma^{\prime}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}\leq\frac{1}{T}\leq\frac{1}{1+t},$

which ensures that $2\eta\epsilon^{\prime}\leq 1/(t+1)$, and then (A.14)
holds. The proof is completed. ∎

We can combine Theorem A.5 and Lemma 1 together to get the upper bound of the
generalization error.

###### Proof of Theorem 2.

Eq.(A.9) with $p=1/t$ and Eq.(A.13) implies

$\displaystyle\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{2e^{2}\eta^{2}(1+t)}{n^{2}}\sum_{j=0}^{t}\Big{(}\big{\|}\nabla\ell(\mathbf{W}_{j};z_{i})\big{\|}_{2}^{2}+\big{\|}\nabla\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{\|}_{2}^{2}\Big{)}$
$\displaystyle\leq\frac{4e^{2}\eta^{2}\rho(1+t)}{n^{2}}\sum_{j=0}^{t}\Big{(}\ell(\mathbf{W}_{j};z_{i})+\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\Big{)},$

where in the last inequality we used self-bounding property of the smooth loss
(Lemma A.1). Now, taking an average over $i\in[n]$ and using
$\mathbb{E}\big{[}\ell(\mathbf{W}_{j};z_{i})\big{]}=\mathbb{E}\big{[}\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{]}$,
we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{\|}\mathbf{W}_{t+1}-\mathbf{W}_{t+1}^{(i)}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{4e^{2}\eta^{2}\rho(1+t)}{n^{3}}\sum_{j=0}^{t}\Big{(}\sum_{i=1}^{n}\mathbb{E}\big{[}\ell(\mathbf{W}_{j};z_{i})\big{]}+\mathbb{E}[\ell(\mathbf{W}_{j}^{(i)};z_{i}^{\prime})\big{]}\Big{)}$
$\displaystyle=\frac{8e^{2}\eta^{2}\rho(1+t)}{n^{3}}\sum_{j=0}^{t}\sum_{i=1}^{n}\mathbb{E}\big{[}\ell(\mathbf{W}_{j};z_{i})\big{]}$
$\displaystyle=\frac{8e^{2}\eta^{2}\rho(1+t)}{n^{2}}\sum_{j=0}^{t}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}.$

Combining the above stability bounds with Lemma 1 together, we get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{t})\\!-\\!L_{S}(\mathbf{W}_{t})]$
$\displaystyle\leq\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}\\!+\\!\Big{(}\frac{16e^{2}\eta^{2}\rho^{2}t\mathbb{E}[L_{S}(\mathbf{W}_{t})]}{n^{2}}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]}+\frac{4e\eta\rho}{n}\sum_{j=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{j})\big{]},$

where in the last inequality we used
$L_{S}(\mathbf{W}_{t})\leq\frac{1}{t}\sum_{j=1}^{t-1}L_{S}(\mathbf{W}_{j})$
[34]. The proof is completed. ∎

###  A.2 Proofs of Optimization Bounds

Before giving the proofs of optimization error bound, we first introduce the
following lemma on the bound of GD iterates.

######  Lemma A.6.

Suppose Assumptions 1 and 2 hold, and $\eta\leq 1/(2\rho)$. Assume (4) and (5)
hold. Then for any $t\in[T]$, there holds

$\displaystyle 1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{t}\|_{2}^{2}]\leq\Big{(}\frac{8e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}+\frac{8e\eta^{2}t\rho}{n}\\!\Big{)}\\!\sum_{s=0}^{t-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}\big{]}}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

###### Proof.

For any $\mathbf{W},\widetilde{\mathbf{W}}\in\mathbb{R}^{md}$ and
$\alpha\in[0,1]$, define
$\mathbf{W}(\alpha):=\widetilde{\mathbf{W}}+\alpha(\mathbf{W}-\widetilde{\mathbf{W}})$.
Note that

$\displaystyle\lambda_{\min}\big{(}\nabla^{2}L_{S}(\mathbf{W}(\alpha))\big{)}$
$\displaystyle\geq-\max_{i}\\{\|\nabla^{2}f(\mathbf{x}_{i})\|_{2}\\}\Big{(}\frac{1}{n}\sum_{i=1}^{n}|f_{\mathbf{W}(\alpha)}(\mathbf{x}_{i})-y_{i}|\Big{)}$
$\displaystyle\geq-\frac{c_{x}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\frac{1}{n}\Big{(}\sum_{i=1}^{n}\big{(}|f_{\mathbf{W}(\alpha)}(\mathbf{x}_{i})-f_{\widetilde{\mathbf{W}}}(\mathbf{x}_{i})|+|f_{\widetilde{\mathbf{W}}}(\mathbf{x}_{i})-f_{\mathbf{W}_{0}}(\mathbf{x}_{i})|+|f_{\mathbf{W}_{0}}(\mathbf{x}_{i})-y_{i}|\big{)}\Big{)}$
$\displaystyle\geq-\frac{c_{x}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}(\alpha)-\widetilde{\mathbf{W}}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\widetilde{\mathbf{W}}-\mathbf{W}_{0}\|_{2}+\sqrt{2L_{S}(\mathbf{W}_{0})}\Big{)}$
$\displaystyle\geq-\frac{c_{x}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\widetilde{\mathbf{W}}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\widetilde{\mathbf{W}}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)}.$

Then for any $t\in[T]$, let $\widetilde{\mathbf{W}}=\mathbf{W}_{t}$, and
define

$\displaystyle g(\alpha):=$ $\displaystyle
L_{S}(\mathbf{W}(\alpha))+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{m^{c}}\frac{\alpha^{2}}{2}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}]).$

It is obvious that $g^{\prime\prime}(\alpha)\geq 0$. Then $g(\alpha)$ is
convex in $\alpha\in[0,1]$. Now, by convexity we know

$\displaystyle g(1)-g(0)$
$\displaystyle=L_{S}(\mathbf{W})+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\quad\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}])-L_{S}(\mathbf{W}_{t})$
$\displaystyle\geq\langle\mathbf{W}-\mathbf{W}_{t},\nabla
L_{S}(\mathbf{W}_{t})\rangle=g^{\prime}(0).$

Rearranging the above inequality we get

$\displaystyle L_{S}(\mathbf{W}_{t})$ $\displaystyle\leq
L_{S}(\mathbf{W})+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\quad\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}])-\langle\mathbf{W}-\mathbf{W}_{t},\nabla
L_{S}(\mathbf{W}_{t})\rangle.$ (A.15)

Combining (A.2) with the smoothness of the loss we can get

$\displaystyle L_{S}(\mathbf{W}_{t+1})$ $\displaystyle\leq
L_{S}(\mathbf{W}_{t})+\langle\nabla
L_{S}(\mathbf{W}_{t}),\mathbf{W}_{t+1}-\mathbf{W}_{t}\rangle+\frac{\rho}{2}\|\mathbf{W}_{t+1}-\mathbf{W}_{t}\|_{2}^{2}$
$\displaystyle\leq L_{S}(\mathbf{W}_{t})-\eta\langle\nabla
L_{S}(\mathbf{W}_{t}),\nabla
L_{S}(\mathbf{W}_{t})\rangle+\frac{\rho}{2}\|\mathbf{W}_{t+1}-\mathbf{W}_{t}\|_{2}^{2}$
$\displaystyle\leq L_{S}(\mathbf{W}_{t})-\eta(1-\frac{\eta\rho}{2})\|\nabla
L_{S}(\mathbf{W}_{t})\|_{2}^{2}$ $\displaystyle\leq
L_{S}(\mathbf{W}_{t})-\frac{\eta}{2}\|\nabla L_{S}(\mathbf{W}_{t})\|_{2}^{2}$
$\displaystyle\leq
L_{S}(\mathbf{W})+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\quad\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}])-\langle\mathbf{W}-\mathbf{W}_{t},\nabla
L_{S}(\mathbf{W}_{t})\rangle-\frac{\eta}{2}\|\nabla
L_{S}(\mathbf{W}_{t})\|_{2}^{2},$

where in the third inequality we used the update rule (2) and $\eta\rho\leq
1$.

According to the equality $2\langle
x-y,x-z\rangle=\|x-y\|_{2}^{2}+\|x-z\|_{2}^{2}-\|y-z\|_{2}^{2}$, we know

$\displaystyle\\!-\langle\mathbf{W}-\mathbf{W}_{t},\nabla
L_{S}(\mathbf{W}_{t})\rangle-\frac{\eta}{2}\|\nabla
L_{S}(\mathbf{W}_{t})\|_{2}^{2}$
$\displaystyle=\frac{1}{\eta}\langle\mathbf{W}-\mathbf{W}_{t},\mathbf{W}_{t+1}-\mathbf{W}_{t}\rangle-\frac{1}{2\eta}\|\mathbf{W}_{t+1}-\mathbf{W}_{t}\|_{2}^{2}$
$\displaystyle=\frac{1}{2\eta}\big{(}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}\\!-\\!\|\mathbf{W}_{t+1}-\mathbf{W}\|_{2}^{2}\big{)}.$

Then there holds

$\displaystyle L_{S}(\mathbf{W}_{t+1})$ $\displaystyle\leq
L_{S}(\mathbf{W})+\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}}\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}+\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}+\sqrt{2c_{0}}\Big{)}$
$\displaystyle\quad\times(1\vee\mathbb{E}[\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}])+\frac{1}{2\eta}\Big{(}\|\mathbf{W}-\mathbf{W}_{t}\|_{2}^{2}-\|\mathbf{W}_{t+1}-\mathbf{W}\|_{2}^{2}\Big{)}.$
(A.16)

The above inequality with $\mathbf{W}=\mathbf{W}^{*}_{\frac{1}{\eta T}}$
implies

$\displaystyle\frac{1}{t}\sum_{s=0}^{t-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]+\frac{\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}}{2\eta t}$
$\displaystyle\\!\leq\\!\mathbb{E}[L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})]\\!+\\!\frac{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!\\!-\\!\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}{2\eta
t}\\!+\\!\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}t}\\!\\!\sum_{s=0}^{t-1}\\!\Big{(}\\!\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!\\!-\\!\\!\mathbf{W}_{s}\|_{2}]\\!+\\!\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\\!\vee\\!\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!\\!-\\!\\!\mathbf{W}_{s}\|_{2}^{2}]).$

Combined the above inequality with Theorem 2 implies

$\displaystyle\frac{\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}}{2\eta t}$
$\displaystyle\leq\frac{1}{t}\sum_{s=0}^{t-1}\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})\\!-\\!\mathbb{E}[L(\mathbf{W}_{s})]\big{]}\\!+\\!\frac{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}{2\eta
t}\\!+\\!\Big{(}\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}\\!+\\!\frac{4e\eta\rho}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+\\!\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}t}\\!\sum_{s=0}^{t-1}\\!\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{s}\|_{2}]\\!+\\!\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{s}\|_{2}^{2}])$ $\displaystyle\leq
L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})\\!-\\!L(\mathbf{W}^{*})\\!+\\!\frac{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}{2\eta
t}\\!+\\!\Big{(}\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}\\!+\\!\frac{4e\eta\rho}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+\\!\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2m^{c}t}\\!\sum_{s=0}^{t}\\!\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{s}\|_{2}]\\!+\\!\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{s}\|_{2}^{2}]),$ (A.17)

where in the second inequality we used $L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}_{s})\leq L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})$ since $L(\mathbf{W}_{s})\geq L(\mathbf{W}^{*})$
for any $s\in[t-1]$.

On the other hand, using Lemma A.3 we can obtain

$\displaystyle\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}\leq\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{s}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta T}}^{*}-\mathbf{W}_{0}\|_{2}.$ (A.18)

Then we know

$\displaystyle\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{s}\|_{2}]\\!+\\!\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}\sqrt{2\eta
Tc_{0}}}{m^{c-1/2}}\\!+\\!\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}])$
$\displaystyle\leq\Big{(}\frac{B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}(2\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})+\sqrt{2c_{0}}\Big{)}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}]).$

Plugging the above inequality back into (A.2) yields

$\displaystyle\frac{\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}}{2\eta t}$
$\displaystyle\leq\frac{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}{2\eta
t}\\!+\\!\frac{\tilde{b}(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}t}\sum_{s=0}^{t}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{s}\|_{2}^{2}])\\!+\\!\Big{(}\frac{4e^{2}\eta^{2}\rho^{2}t}{n^{2}}\\!+\\!\frac{4e\eta\rho}{n}\Big{)}\\!\sum_{s=0}^{t-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*}),$

where
$\tilde{b}=\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2}\big{(}\frac{2B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}+\sqrt{2c_{0}}\big{)}$.

Multiplying both sides by $2\eta t$ yields

$\displaystyle\mathbb{E}\big{[}\|\mathbf{W}_{t}-\mathbf{W}_{\frac{1}{\eta
T}}^{*}\|_{2}^{2}\big{]}$
$\displaystyle\leq{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}\big{]}}+\frac{2\tilde{b}\eta(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\sum_{s=0}^{t}(1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}])$
$\displaystyle\quad+\Big{(}\frac{8e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}+\frac{8e\eta^{2}\rho
t}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

Let $x=\max_{s\in[T]}\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{s}\|_{2}^{2}]\vee 1$. Then the above inequality implies

$\displaystyle x$
$\displaystyle\leq{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}\big{]}}+\frac{2\tilde{b}\eta T(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}x$
$\displaystyle\quad+\Big{(}\frac{8e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}+\frac{8e\eta^{2}\rho
t}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

Without loss of generality, we assume $\eta\leq 1$. Condition (5) implies
$m\geq\big{(}4\tilde{b}\eta T(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})\big{)}^{\frac{1}{c}}$, then there holds
$\frac{2\tilde{b}\eta T(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\leq\frac{1}{2}$. Hence

$x\leq\Big{(}\frac{16e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}+\frac{16e\eta^{2}t\rho}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+2{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}\big{]}}+2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})-L(\mathbf{W}^{*})\big{]}.$

It then follows that

$\displaystyle 1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{t}\|_{2}^{2}]\leq\Big{(}\frac{16e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}\\!+\\!\frac{16e\eta^{2}t\rho}{n}\Big{)}\sum_{s=0}^{t-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}\\!+\\!2{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}\\!+\\!2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})\\!-\\!L(\mathbf{W}^{*})\big{]}.$

This completes the proof. ∎

Now, we can give the proof of Theorem 3.

###### Proof of Theorem 3.

Recall that
$\tilde{b}=\frac{c_{\mathbf{x}}^{2}B_{\sigma^{\prime\prime}}}{2}\big{(}\frac{2B_{\sigma^{\prime}}c_{\mathbf{x}}}{m^{c-1/2}}+\sqrt{2c_{0}}\big{)}$.
Eq.(A.2) with $\mathbf{W}=\mathbf{W}^{*}_{\frac{1}{\eta T}}$ implies

$\displaystyle\frac{1}{T}\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]\\!+\\!\frac{\tilde{b}(\sqrt{2\eta
Tc_{0}}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}T}\sum_{s=0}^{T-1}1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{s}\|_{2}^{2}]\\!+\\!\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}}{2\eta T},$ (A.19)

where in the last inequality we used (A.18).

Further, by monotonically decreasing of $\\{L_{S}(\mathbf{W}_{t})\\}$, we know

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})]\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]\\!+\\!\frac{\tilde{b}(\sqrt{2\eta
Tc_{0}}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}T}\sum_{s=0}^{T-1}1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!-\\!\mathbf{W}_{s}\|_{2}^{2}]+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}}{2\eta T}.$

Note that Lemma A.6 shows

$\displaystyle 1\vee\mathbb{E}[\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{t}\|_{2}^{2}]\leq\\!\Big{(}\frac{16e^{2}\eta^{3}\rho^{2}t^{2}}{n^{2}}\\!+\\!\frac{16e\eta^{2}t\rho}{n}\Big{)}\\!\sum_{s=0}^{t-1}\\!\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}\\!+\\!2{\mathbb{E}\big{[}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\big{]}}\\!+\\!2\eta
T\big{[}L(\mathbf{W}_{\frac{1}{\eta T}}^{*})\\!-\\!L(\mathbf{W}^{*})\big{]}.$

Combining the above two inequalities together, we get

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})]$
$\displaystyle\leq\mathbb{E}[L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})]+\frac{2\tilde{b}(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{(}\Big{(}\frac{8e^{2}\eta^{3}\rho^{2}T^{2}}{n^{2}}+\frac{8e\eta^{2}T\rho}{n}\Big{)}\sum_{s=0}^{T-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}}+\eta T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}\Big{)}+\frac{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta T}.$

The theorem is proved. ∎

######  Lemma A.7.

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ be produced by
(2) with $\eta\leq 1/(2\rho)$. Assume (4) and (5) hold. Then

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\leq
4TL(\mathbf{W}^{*}_{\frac{1}{\eta T}})-2\eta
TL(\mathbf{W}^{*})+\Big{(}\frac{2\tilde{b}T(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}+\frac{1}{2\eta}\Big{)}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}.$

###### Proof.

Multiplying $T$ over both sides of (A.2) and using Lemma A.6 we get

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]$
$\displaystyle\leq TL(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{\tilde{b}(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\sum_{s=0}^{T-1}1\vee\mathbb{E}[\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{s}\|_{2}^{2}]+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta}$ $\displaystyle\leq
TL(\mathbf{W}^{*}_{\frac{1}{\eta T}})\\!+\\!\frac{\tilde{b}T(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{(}\big{(}\frac{16e^{2}\eta^{3}\rho^{2}T^{2}}{n^{2}}\\!+\\!\frac{16e\eta^{2}T\rho}{n}\big{)}\sum_{s=0}^{T-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}$
$\displaystyle\quad+2{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}}+2\eta T\big{[}L(\mathbf{W}_{\frac{1}{\eta
T}}^{*})-L(\mathbf{W}^{*})\big{]}\Big{)}+\frac{\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}}{2\eta}.$

Condition (5) implies $m\geq\big{(}2\tilde{b}T(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})\big{(}\frac{16e^{2}\eta^{3}\rho^{2}T^{2}}{n^{2}}+\frac{16e\eta^{2}T\rho}{n}\big{)}\big{)}^{1/c}$
and $m\geq\big{(}2\tilde{b}T(\sqrt{2\eta Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})\big{)}^{1/c}$, there holds

$\displaystyle\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\leq
4TL(\mathbf{W}^{*}_{\frac{1}{\eta T}})-2\eta
TL(\mathbf{W}^{*})+\Big{(}\frac{2\tilde{b}T(\sqrt{2\eta
Tc_{0}}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}+\frac{1}{2\eta}\Big{)}\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2},$

which completes the proof. ∎

###  A.3 Proofs of Excess Risk Bounds

###### Proof of Theorem 4.

According to Lemma A.7 and noting that $\tilde{b}=\mathcal{O}(1)$, we know

$\displaystyle\\!\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\\!=\\!\mathcal{O}\Big{(}TL(\mathbf{W}^{*}_{\frac{1}{\eta
T}})\\!+\\!\Big{(}\frac{T(\sqrt{\eta T}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}}\\!+\\!\frac{1}{\eta}\Big{)}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\Big{)}.$ (A.20)

The upper bound of the generalization error can be controlled by plugging
(A.20) back into Theorem 2

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L_{S}(\mathbf{W}_{T})]$
$\displaystyle=\mathcal{O}\Big{(}\big{(}\frac{\eta^{2}\rho^{2}T}{n^{2}}+\frac{\eta\rho}{n}\big{)}\sum_{s=0}^{T-1}\mathbb{E}[L_{S}(\mathbf{W}_{s})]\Big{)}$
$\displaystyle=\mathcal{O}\Big{(}\Big{(}\frac{\eta^{2}\rho^{2}T^{2}}{n^{2}}+\frac{\eta
T\rho}{n}\Big{)}\Big{(}L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\Big{(}\frac{\sqrt{\eta T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}}{m^{c}}+\frac{1}{\eta
T}\Big{)}\|\mathbf{W}^{*}_{\frac{1}{\eta T}}-\mathbf{W}_{0}\|_{2}^{2}\Big{)}.$
(A.21)

The estimation of the optimization error is given by plugging (A.20) back into
Theorem 3

$\displaystyle\mathbb{E}[L_{S}(\mathbf{W}_{T})-L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{2\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}]$
$\displaystyle\\!=\mathcal{O}\Big{(}\frac{(\sqrt{\eta
T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{[}\Big{(}\frac{\eta^{3}\rho^{2}T^{2}}{n^{2}}+\frac{\eta^{2}T\rho}{n}\Big{)}\sum_{s=0}^{T-1}\mathbb{E}\big{[}L_{S}(\mathbf{W}_{s})\big{]}+{\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2}^{2}}$ $\displaystyle\quad+\eta
T\big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}^{*})\big{]}\Big{]}\Big{)}$
$\displaystyle\\!=\mathcal{O}\Big{(}\\!\frac{(\sqrt{\eta
T}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{(}\frac{\eta^{3}\rho^{2}T^{2}}{n^{2}}\\!+\\!\frac{\eta^{2}T\rho}{n}\Big{)}\Big{(}\frac{T(\sqrt{\eta
T}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}}\\!+\\!\frac{1}{\eta}\Big{)}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!-\\!\mathbf{W}_{0}\|_{2}^{2}$ $\displaystyle\qquad+\frac{\eta
T(\sqrt{\eta T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{(}\frac{\eta^{2}\rho^{2}T^{2}}{n^{2}}+\frac{\eta
T\rho}{n}\Big{)}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})$
$\displaystyle\qquad+\frac{(\sqrt{\eta T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\big{(}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}+\eta T\Lambda_{\frac{1}{\eta T}}\big{)}\Big{)},$
(A.22)

where we used the fact that $L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})-L(\mathbf{W}^{*})\leq\Lambda_{\frac{1}{\eta T}}$.

Combining (A.3) and (A.3) together and noting that the approximation error
$\Lambda_{\frac{1}{\eta T}}=L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})$ we get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle\\!=\\!\Big{[}\mathbb{E}[L(\mathbf{W}_{T})-L_{S}(\mathbf{W}_{T})\Big{]}+\mathbb{E}\Big{[}L_{S}(\mathbf{W}_{T})-\big{(}L_{S}(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}\big{)}\Big{]}$
$\displaystyle\quad+\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})+\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}-L(\mathbf{W}^{*})\Big{]}$
$\displaystyle\\!=\\!\mathcal{O}\Big{(}\frac{\eta
T\rho}{n}\Big{(}\frac{\\!\eta\rho
T}{n}\\!+\\!1\Big{)}\Big{(}1\\!+\\!\frac{\\!\eta T(\sqrt{\eta
T}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2})}{m^{c}}\Big{)}\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!)\\!+\\!\Big{(}\frac{1}{2\eta T}\\!+\\!\frac{\\!\\!\sqrt{\eta
T}\\!+\\!\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}\\!\\!-\\!\mathbf{W}_{0}\|_{2}}{m^{c}}\Big{)}$
$\displaystyle\quad\times\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\Big{]}+\frac{(\sqrt{\eta
T}+\|\mathbf{W}_{\frac{1}{\eta
T}}^{*}-\mathbf{W}_{0}\|_{2})}{m^{c}}\big{(}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}+\eta T\Lambda_{\frac{1}{\eta
T}}\big{)}+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

Recalling that $\rho=\mathcal{O}(m^{1-2c})$. If $\eta
Tm^{1-2c}=\mathcal{O}(n)$ and $\eta T(\sqrt{\eta
T}+\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2})=\mathcal{O}(m^{c})$, there holds
$\eta T\rho=\mathcal{O}(n)$ and $\eta T(\sqrt{\eta
T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2})/m^{c}=\mathcal{O}(1)$. Then from the above bound we
can get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T\rho}{n}\Big{[}L(\mathbf{W}^{*}_{\frac{1}{\eta T}})+\frac{1}{2\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}\Big{]}+\frac{1}{\eta
T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}\\!\\!-\\!\mathbf{W}_{0}\|_{2}^{2}+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

Combining the above bound with the facts $L(\mathbf{W}^{*}_{\frac{1}{\eta
T}})+\frac{1}{2\eta T}\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2}^{2}=L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}$ and
$\|\mathbf{W}^{*}_{\frac{1}{\eta T}}-\mathbf{W}_{0}\|_{2}\leq\sqrt{\eta
T\Lambda_{\frac{1}{\eta T}}}$ together we get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T\rho}{n}L(\mathbf{W}^{*})+\Lambda_{\frac{1}{\eta T}}\Big{)}.$

The proof is completed. ∎

###### Proof of Corollary 5.

Part (a). Case 1. From the definition of the approximation error
$\Lambda_{\frac{1}{\eta T}}$, we know that $\Lambda_{\frac{1}{\eta
T}}\leq\frac{1}{2\eta T}\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}^{2}$. Combining
this with Theorem 4, we have

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\Big{(}\frac{\eta
T\rho}{n}L(\mathbf{W}^{*})+\frac{1}{\eta
T}\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}^{2}\Big{)}.$

Without loss of generality, we consider $\|\mathbf{W}_{0}\|_{2}$ as a
constant. To obtain the excess risk rate, we discuss the following two cases:
$2c+6\mu-3>0$ and $2c+6\mu-3\leq 0$.

For the case $2c+6\mu-3>0$, to ensure conditions (4), (5) and $\eta
T(\sqrt{\eta T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2})=\mathcal{O}(m^{c})$ hold, we set $m\asymp(\eta
T)^{\frac{3}{2c}}$ for this case. Then according to Theorem 4 and Assumption 3
we know

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle=\mathcal{O}\Big{(}(\eta T)^{\frac{3-4c}{2c}}n^{-1}+(\eta
T)^{\frac{3-6\mu-2c}{2c}}\Big{)}.$

If $c<3/4$, under the condition $\eta T\lesssim n^{\frac{c}{3-4c}}$ and
$n^{\frac{c}{6\mu+2c-3}}\lesssim\eta T$, there holds $(\eta
T)^{\frac{3-4c}{2c}}n^{-1}+(\eta
T)^{\frac{3-6\mu-2c}{2c}}=\mathcal{O}(1/\sqrt{n})$. To ensure the above-
mentioned conditions hold simultaneously, we further require $c+\mu\geq 1$
such that $n^{\frac{c}{3-4c}}\gtrsim n^{\frac{c}{6\mu+2c-3}}$. Therefore, if
$c\in[1-\mu,3/4)$ and $c+3\mu>3/2$, we can obtain

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle=\mathcal{O}\Big{(}\frac{1}{\sqrt{n}}\Big{)}$

with $m\asymp(\eta T)^{\frac{3}{2c}}$ and $n^{\frac{c}{6\mu+2c-3}}\lesssim\eta
T\lesssim n^{\frac{c}{3-4c}}$.

If $c\geq 3/4$, for any $\eta T\geq 1$ and $n\geq 1$, there holds $(\eta
T)^{\frac{3-4c}{2c}}n^{-1}=\mathcal{O}(1/\sqrt{n})$. Similar to before, if
$\eta T\gtrsim n^{\frac{c}{6\mu+2c-3}}$, there holds $(\eta
T)^{\frac{3-6\mu-2c}{2c}}=\mathcal{O}(1/\sqrt{n})$. Then we can obtain the
excess population bound $\mathcal{O}(1/\sqrt{n})$ with $m\asymp(\eta
T)^{\frac{3}{2c}}$ and $\eta T\gtrsim n^{\frac{c}{6\mu+2c-3}}$ .

Case 2. For the case $2c+6\mu-3\leq 0$, we can choose $m\asymp(\eta
T)^{\frac{1}{c+\mu-1/2}}$ to ensure conditions (4), (5) and $\eta T(\sqrt{\eta
T}+\|\mathbf{W}^{*}_{\frac{1}{\eta
T}}-\mathbf{W}_{0}\|_{2})=\mathcal{O}(m^{c})$ hold. From Theorem 4 we know

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle=\mathcal{O}\big{(}(\eta
T)^{\frac{1-2c+2\mu}{2c+2\mu-1}}n^{-1}+(\eta
T)^{\frac{3-6\mu-2c}{2c+2\mu-1}}\big{)}.$

Note $3-6\mu-2c\geq 0$ and $2c+2\mu-1>0$. Then the term $(\eta
T)^{\frac{3-6\mu-2c}{2c+2\mu-1}}$ will not converge for any choice of $\eta T$
in this case. The proof of Part (a) is completed.

Part (b). Now, we consider the low noise case, i.e., $L(\mathbf{W}^{*})=0$.
Combining the fact $\Lambda_{\frac{1}{\eta T}}\leq\frac{1}{2\eta
T}\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}^{2}$, Assumption 3 and Theorem 4 with
$L(\mathbf{W}^{*})=0$, we can get

$\displaystyle\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]$
$\displaystyle=\mathcal{O}\Big{(}\frac{m^{1-2\mu}}{\eta T}\Big{)}.$

Similar to part (a), we can set $m\asymp(\eta T)^{\frac{3}{2c}}$, $\eta
T\gtrsim n^{\frac{2c}{6\mu+2c-3}}$ and obtain

$\mathbb{E}[L(\mathbf{W}_{T})-L(\mathbf{W}^{*})]=\mathcal{O}\big{(}\frac{1}{n}\big{)}.$

We can check that this choice of $m$ and $\eta T$ satisfies conditions (4) and
(5). The proof is completed. ∎

######  Remark A.1.

Several works [11, 17, 25, 40, 30] studied the stability behavior of
stochastic gradient methods for non-convex losses, which can be applied to
two-layer networks. Specifically, to obtain meaningful stability bounds, [17]
required a time-dependent step size $\eta_{t}=1/t$, which is insufficient to
get a good convergence rate for optimization error. [11, 25, 40] established
generalization bounds by introducing the Polyak-Łojasiewicz condition, which
depends on a problem-dependent number. This number might be large in practice
and results in a worse generalization bound. It is hard to provide a direct
comparison with their results since the learning settings are different.

##  Appendix B Proofs of Three-layer Neural Networks

###  B.1 Proofs of Generalization Bounds

For a matrix $\mathbf{W}$, let $\mathbf{W}_{s;\cdot}$ and $\mathbf{W}_{is}$
denote the $s$-th row and the $(i,s)$-th entry of $\mathbf{W}$, respectively.

######  Lemma B.1 (Smoothness and Curvature).

Suppose Assumptions 1 and 2 hold. For any fixed
$\mathbf{W}=(\mathbf{W}^{(1)},\mathbf{W}^{(2)})\in\mathbb{R}^{m\times
d}\times\mathbb{R}^{m\times m}$ and any $z\in\mathcal{Z}$, there holds

$\lambda_{\max}\big{(}\nabla^{2}\ell(\mathbf{W};z)\big{)}\leq\rho_{\mathbf{W}}\text{
with }$
$\rho_{\mathbf{W}}=\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}+C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2c_{0}}\Big{)},$
$\lambda_{\min}\big{(}\nabla^{2}\ell(\mathbf{W};z)\big{)}\\!\geq\\!-C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2c_{0}}\Big{)},$

where
$C_{\mathbf{W}}=\frac{B^{2}_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{3c}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{2c-\frac{1}{2}}}+\frac{2B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}c_{\mathbf{x}}}{m^{3c-\frac{1}{2}}}\Big{)}\|\mathbf{W}^{(2)}\|_{2}+\frac{B_{\sigma^{\prime\prime}}B_{\sigma}^{2}}{m^{3c-1}}+\frac{2B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}$.

###### Proof.

Let
$A_{\mathbf{W}^{(1)}}=[\sigma(\mathbf{W}_{1;\cdot}^{(1)}\mathbf{x}),\ldots,\sigma(\mathbf{W}_{m;\cdot}^{(1)}\mathbf{x})]^{\top}\in\mathbb{R}^{m}$.
Let $\tilde{\mathbf{w}}=\mathbf{w}^{\top}$. We first estimate the upper bound
of $\|\nabla f_{\mathbf{W}}(\mathbf{x})\|_{2}$. Note that for any
$k=1,\ldots,m$

$\nabla_{\tilde{\mathbf{w}}^{(1)}_{k}}f_{\mathbf{W}}(\mathbf{x})=\frac{\partial
f_{\mathbf{W}}(\mathbf{x})}{\partial\tilde{\mathbf{w}}^{(1)}_{k}}=\frac{1}{m^{2c}}\sum_{i=1}^{m}a_{i}\sigma^{\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}_{is}^{(2)}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})\Big{)}\mathbf{W}^{(2)}_{ik}\sigma^{\prime}(\mathbf{W}_{k;\cdot}^{(1)}\mathbf{x})\mathbf{x}$

and

$\nabla_{\tilde{\mathbf{w}}^{(2)}_{k}}f_{\mathbf{W}}(\mathbf{x})=\frac{\partial
f_{\mathbf{W}}(\mathbf{x})}{\partial\tilde{\mathbf{w}}^{(2)}_{k}}=\frac{a_{k}}{m^{2c}}\sigma^{\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}_{ks}^{(2)}\sigma(\mathbf{W}^{(1)}_{s;\cdot}\mathbf{x})\Big{)}A_{\mathbf{W}^{(1)}}.$

According to Assumptions 1 and 2, the upper bound of the gradient can be
controlled as follows

$\displaystyle\|\nabla f_{\mathbf{W}}(\mathbf{x})\|_{2}^{2}$
$\displaystyle=\sum_{k=1}^{m}\Big{(}\big{\|}\nabla_{\tilde{\mathbf{w}}^{(1)}_{k}}f_{\mathbf{W}}(\mathbf{x})\big{\|}_{2}^{2}+\big{\|}\nabla_{\tilde{\mathbf{w}}^{(2)}_{k}}f_{\mathbf{W}}(\mathbf{x})\big{\|}_{2}^{2}\Big{)}$
$\displaystyle\leq\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\sum_{k=1}^{m}\sum_{i=1}^{m}\big{|}\mathbf{W}_{ik}^{(2)}\big{|}^{2}+\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}$
$\displaystyle\leq\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}.$
(B.1)

For any $k,j\in[m]$, we know

$\displaystyle\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}^{(1)}_{k}\big{)}^{2}}=$
$\displaystyle\frac{1}{m^{3c}}\sum_{i=1}^{m}a_{i}\sigma^{\prime\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{w}^{2}_{is}\sigma(\mathbf{W}^{(1)}_{s;\cdot}\mathbf{x})\Big{)}\big{(}\mathbf{W}^{(2)}_{ik}\big{)}^{2}\big{(}\sigma^{\prime}(\mathbf{W}^{(1)}_{k;\cdot}\mathbf{x})\big{)}^{2}\mathbf{x}\mathbf{x}^{\top}$
$\displaystyle+\frac{1}{m^{2c}}\sum_{i=1}^{m}a_{i}\sigma^{\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}^{2}_{is}\sigma(\mathbf{W}^{(1)}_{s;\cdot}\mathbf{x})\Big{)}\mathbf{W}^{(2)}_{ik}\sigma^{\prime\prime}(\mathbf{W}^{(1)}_{k;\cdot}\mathbf{x})\mathbf{x}\mathbf{x}^{\top},$
$\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}^{(2)}_{k}\big{)}^{2}}=\frac{a_{k}}{m^{3c}}\sigma^{\prime\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}^{(2)}_{ks}\sigma(\mathbf{W}^{(1)}_{s;\cdot}\mathbf{x})\Big{)}A_{\mathbf{W}^{(1)}}A_{\mathbf{W}^{(1)}}^{\top}$

and

$\displaystyle\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\partial\tilde{\mathbf{w}}^{(1)}_{k}\partial\tilde{\mathbf{w}}^{(2)}_{j}}=$
$\displaystyle\frac{1}{m^{3c}}a_{j}\sigma^{\prime\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}^{(2)}_{js}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})\Big{)}\mathbf{W}^{(2)}_{jk}\sigma^{\prime}(\mathbf{W}^{(1)}_{k;\cdot}\mathbf{x})\mathbf{x}A^{\top}_{\mathbf{W}^{(1)}}$
$\displaystyle+\frac{1}{m^{2c}}a_{j}\sigma^{\prime}\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}^{(2)}_{js}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})\Big{)}\sigma^{\prime}(\mathbf{W}^{(1)}_{k;\cdot}\mathbf{x})\mathbf{x}B_{k}$

where $B_{k}\in\mathbb{R}^{1\times m}$ with $k$-th element is 1 and others are
0. Let the vector $\mathbf{u}\in\mathbb{R}^{md+m^{2}}$ have unit norm
$\|\mathbf{u}\|_{2}=1$ and be composed in a manner matching the parameter
$\mathbf{W}=(\mathbf{W}^{(1)},\mathbf{W}^{(2)})$ so that
$\mathbf{u}=(\mathbf{u}^{(1)},\mathbf{u}^{(2)})$ where
$\mathbf{u}^{(1)}\in\mathbb{R}^{m\times d}$ and
$\mathbf{u}^{(2)}\in\mathbb{R}^{m\times m}$ have been vectorised in a row-
major manner with $\mathbf{u}_{k}^{(1)}\in\mathbb{R}^{1\times d}$ and
$\mathbf{u}_{k}^{(2)}\in\mathbb{R}^{1\times m}$. Then

$\displaystyle\mathbf{u}^{\top}\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\mathbf{u}$
$\displaystyle\\!=\\!\sum_{k=1}^{m}\Big{(}\mathbf{u}^{(1)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}_{k}^{(1)}\big{)}^{2}}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}\\!+\\!\mathbf{u}^{(2)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}_{k}^{(2)}\big{)}^{2}}\big{(}\mathbf{u}^{(2)}_{k}\big{)}^{\top}\\!+\\!2\sum_{j=1}^{m}\mathbf{u}^{(1)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\partial\tilde{\mathbf{w}}_{k}^{(1)}\partial\tilde{\mathbf{w}}_{j}^{(2)}}\big{(}\mathbf{u}^{(2)}_{j}\big{)}^{\top}\Big{)}.$
(B.2)

We estimate the above three terms separately. Let $\mathbf{W}_{\cdot k}^{(2)}$
denote the $k$-th column of $\mathbf{W}^{(2)}$.

$\displaystyle\sum_{k=1}^{m}\mathbf{u}^{(1)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}_{k}^{(1)}\big{)}^{2}}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B^{2}_{\sigma^{\prime}}}{m^{3c}}\sum_{k=1}^{m}\mathbf{u}^{(1)}_{k}\sum_{i=1}^{m}\big{(}\mathbf{W}^{(2)}_{ik}\big{)}^{2}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}+\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}}{m^{2c}}\sum_{k=1}^{m}\mathbf{u}^{(1)}_{k}\sum_{i=1}^{m}\mathbf{W}^{(2)}_{ik}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B^{2}_{\sigma^{\prime}}}{m^{3c}}\sum_{i=1}^{m}\sum_{k=1}^{m}\big{(}\mathbf{W}^{(2)}_{ik}\big{)}^{2}\big{(}\mathbf{u}^{(1)}_{k}\mathbf{x}\big{)}^{2}+\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}}{m^{2c}}\sqrt{\sum_{k=1}^{m}\big{(}\sum_{i=1}^{m}\mathbf{W}^{(2)}_{ik}\big{)}^{2}}\sqrt{\sum_{k=1}^{m}\big{(}\mathbf{u}^{(1)}_{k}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}\big{)}^{2}}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B^{2}_{\sigma^{\prime}}c_{\mathbf{x}}^{2}}{m^{3c}}\sum_{k=1}^{m}\sum_{i=1}^{m}\big{(}\mathbf{W}^{(2)}_{ik}\big{)}^{2}\big{\|}\mathbf{u}_{k}^{(1)}\big{\|}_{2}^{2}+\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}}{m^{2c}}\sqrt{m\sum_{k=1}^{m}\sum_{i=1}^{m}\big{(}\mathbf{W}_{ik}^{(2)}\big{)}^{2}}\sum_{k=1}^{m}\big{(}\mathbf{u}^{(1)}_{k}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}\big{)}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B^{2}_{\sigma^{\prime}}c_{\mathbf{x}}^{2}}{m^{3c}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{2c-\frac{1}{2}}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2},$
(B.3)

where we used $\big{(}\sum_{i=1}^{m}\mathbf{W}_{ik}^{(2)}\big{)}^{2}\leq
m\sum_{i=1}^{m}\big{(}\mathbf{W}_{ik}^{(2)}\big{)}^{2}$ and
$\sum_{k=1}^{m}\big{(}\mathbf{u}^{(1)}_{k}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}\big{)}^{2}\leq\big{(}\sum_{k=1}^{m}\mathbf{u}^{(1)}_{k}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}\big{)}^{2}$
in the third inequality, and the last inequality follows from
$\mathbf{u}^{(1)}_{k}\mathbf{x}\mathbf{x}^{\top}\big{(}\mathbf{u}^{(1)}_{k}\big{)}^{\top}=\big{(}\mathbf{u}_{k}^{(1)}\mathbf{x}\big{)}^{2}\leq
c_{\mathbf{x}}^{2}\|\mathbf{u}_{k}^{(1)}\|_{2}^{2}$ and
$\|\mathbf{u}_{k}^{(1)}\|_{2}^{2}\leq 1$.

For the second term in (B.1), we control it by

$\displaystyle\sum_{k=1}^{m}\mathbf{u}^{(2)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\big{(}\partial\tilde{\mathbf{w}}_{k}^{(2)}\big{)}^{2}}\big{(}\mathbf{u}_{k}^{(2)}\big{)}^{\top}\leq\frac{B_{\sigma^{\prime\prime}}}{m^{3c}}\sum_{k=1}^{m}\big{(}\mathbf{u}^{(2)}_{k}A_{\mathbf{W}^{(1)}}\big{)}^{2}\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma}}{m^{3c-1}}\big{\|}\mathbf{u}^{(2)}\big{\|}_{2}^{2}\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma}}{m^{3c-1}}.$
(B.4)

Further, according to Cauchy-Schwarz inequality, we can get

$\displaystyle\sum_{k=1}^{m}\sum_{j=1}^{m}\mathbf{u}^{(1)}_{k}\frac{\partial^{2}f_{\mathbf{W}}(\mathbf{x})}{\partial\tilde{\mathbf{w}}_{k}^{(1)}\partial\tilde{\mathbf{w}}_{j}^{(2)}}\big{(}\mathbf{u}^{(2)}_{j}\big{)}^{\top}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}}{m^{3c}}\sum_{j=1}^{m}\mathbf{W}_{j;\cdot}^{(2)}\mathbf{u}^{(1)}\mathbf{x}\big{\|}\mathbf{u}^{(2)}_{j}\big{\|}_{1}+\frac{B_{\sigma^{\prime}}^{2}}{m^{2c}}\sum_{k=1}^{m}\mathbf{u}_{k}^{(1)}\mathbf{x}\Big{(}\sum_{j=1}^{m}\mathbf{u}_{jk}^{(2)}\Big{)}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}}{m^{3c}}\sqrt{\sum_{j=1}^{m}\big{\|}\mathbf{u}^{(2)}_{\ell}\big{\|}_{1}^{2}}\sqrt{\sum_{j=1}^{m}\Big{(}\mathbf{W}_{j;\cdot}^{(2)}\mathbf{u}^{(1)}\mathbf{x}\Big{)}^{2}}+\frac{B_{\sigma^{\prime}}^{2}}{m^{2c}}\sqrt{\sum_{k=1}^{m}\big{(}\mathbf{u}_{k}^{(1)}\mathbf{x}\big{)}^{2}}\sqrt{\sum_{k=1}^{m}\big{\|}\mathbf{u}_{\cdot
k}^{(2)}\big{\|}_{1}^{2}}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}}{m^{3c}}\sqrt{m\sum_{j=1}^{m}\big{\|}\mathbf{u}^{(2)}_{j}\big{\|}_{2}^{2}}\sqrt{\sum_{j=1}^{m}\big{\|}\mathbf{W}_{j;\cdot}^{(2)}\big{\|}_{2}^{2}\big{\|}\mathbf{u}^{(1)}\mathbf{x}\big{\|}_{2}^{2}}+\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c}}\sqrt{\sum_{k=1}^{m}\big{\|}\mathbf{u}_{k}^{(1)}\big{\|}_{2}^{2}}\sqrt{m\sum_{k=1}^{m}\big{\|}\mathbf{u}_{\cdot
k}^{(2)}\big{\|}_{2}^{2}}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}c_{\mathbf{x}}}{m^{3c-\frac{1}{2}}}\big{\|}\mathbf{u}^{(1)}\big{\|}_{2}\big{\|}\mathbf{u}^{(2)}\big{\|}_{2}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}\big{\|}\mathbf{u}^{(1)}\big{\|}_{2}\big{\|}\mathbf{u}^{(2)}\big{\|}_{2}$
$\displaystyle\leq\frac{B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}c_{\mathbf{x}}}{m^{3c-\frac{1}{2}}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}},$
(B.5)

where in the first equality we used
$\sum_{k=1}^{m}\mathbf{u}^{(1)}_{k}\mathbf{W}_{jk}^{(2)}\mathbf{x}=\mathbf{W}_{j;\cdot}^{(2)}\mathbf{u}^{(1)}\mathbf{x}$,
the second inequality follows from
$\Big{(}\sum_{j=1}^{m}\mathbf{u}_{jk}^{(2)}\Big{)}\leq\big{\|}\mathbf{u}_{\cdot
k}^{(2)}\big{\|}_{1}$, here $\mathbf{u}_{\cdot k}^{(2)}$ denotes the $k$-th
column of $\mathbf{u}^{(2)}$.

Plugging (B.1), (B.4) and (B.1) back into (B.1) we can get

$\displaystyle\big{\|}\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\big{\|}_{op}$
$\displaystyle\leq\frac{B^{2}_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{3c}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}\\!+\\!\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2}}{m^{2c-\frac{1}{2}}}\\!+\\!\frac{2B_{\sigma^{\prime\prime}}B_{\sigma^{\prime}}B_{\sigma}c_{\mathbf{x}}}{m^{3c-\frac{1}{2}}}\Big{)}\|\mathbf{W}^{(2)}\|_{2}\\!+\\!\frac{B_{\sigma^{\prime\prime}}B_{\sigma}^{2}}{m^{3c-1}}\\!+\\!\frac{2B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}:=C_{\mathbf{W}}.$
(B.6)

For any $\mathbf{W},\widetilde{\mathbf{W}}$, according to Assumptions 1 ans 2
we can get

$\displaystyle\big{|}f_{\mathbf{W}}(\mathbf{x})-f_{\widetilde{\mathbf{W}}}(\mathbf{x})\big{|}$
$\displaystyle\leq\frac{1}{m^{c}}\sum_{k=1}^{m}\big{|}\sigma\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\mathbf{W}_{ks}^{(2)}\sigma(\mathbf{W}_{s}^{(1)}\mathbf{x})\Big{)}-\sigma\Big{(}\frac{1}{m^{c}}\sum_{s=1}^{m}\widetilde{\mathbf{W}}_{ks}^{(2)}\sigma(\widetilde{\mathbf{W}}_{s;\cdot}^{(1)}\mathbf{x})\Big{)}\big{|}$
$\displaystyle\leq\frac{B_{\sigma^{\prime}}}{m^{2c}}\sum_{k=1}^{m}\sum_{s=1}^{m}\big{|}\mathbf{W}_{ks}^{(2)}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})-\widetilde{\mathbf{W}}_{ks}^{(2)}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})+\widetilde{\mathbf{W}}_{ks}^{(2)}\sigma(\mathbf{W}_{s;\cdot}^{(1)}\mathbf{x})-\widetilde{\mathbf{W}}_{ks}^{(2)}\sigma(\widetilde{\mathbf{W}}_{s;\cdot}^{(1)}\mathbf{x})\big{|}$
$\displaystyle\leq\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c}}\sum_{k=1}^{m}\sum_{s=1}^{m}\big{|}\mathbf{W}_{ks}^{(2)}-\widetilde{\mathbf{W}}_{ks}^{(2)}\big{|}+\frac{B^{2}_{\sigma^{\prime}}}{m^{2c}}\sum_{k=1}^{m}\sum_{s=1}^{m}\big{|}\widetilde{\mathbf{W}}_{ks}^{(2)}\big{|}\cdot\big{|}\big{(}\mathbf{W}_{s;\cdot}^{(1)}-\widetilde{\mathbf{W}}_{s;\cdot}^{(1)}\big{)}\mathbf{x}\big{|}$
$\displaystyle\leq\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}-\widetilde{\mathbf{W}}^{(2)}\big{\|}_{2}+\frac{B^{2}_{\sigma^{\prime}}c_{\mathbf{x}}\|\widetilde{\mathbf{W}}^{(2)}\|_{\infty}}{m^{2c-\frac{3}{2}}}\big{\|}\mathbf{W}^{(1)}-\widetilde{\mathbf{W}}^{(1)}\big{\|}_{2}.$
(B.7)

Since

$\nabla^{2}\ell(\mathbf{W};z)=\nabla f_{\mathbf{W}}(\mathbf{x})\nabla
f_{\mathbf{W}}(\mathbf{x})^{\top}+\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\big{(}f_{\mathbf{W}}(\mathbf{x})-y\big{)}.$
(B.8)

Then for any $\mathbf{W}\in\mathbb{R}^{md+m^{2}}$, we can upper bound the
maximum eigenvalue of the Hessian by combining (B.1), (B.1) and (B.1) with
$\widetilde{\mathbf{W}}=\mathbf{0}$ together

$\displaystyle\lambda_{\max}(\nabla^{2}\ell(\mathbf{W};z))$
$\displaystyle\leq\|\nabla
f_{\mathbf{W}}(\mathbf{x})\|_{2}^{2}+\|\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\|_{op}|f_{\mathbf{W}}(\mathbf{x})-y|$
$\displaystyle\leq\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}+C_{\mathbf{W}}\big{(}\big{|}f_{\mathbf{W}}(\mathbf{x})-f_{\mathbf{0}}(\mathbf{x})\big{|}+\big{|}f_{\mathbf{0}}(\mathbf{x})-y\big{|}\big{)}$
$\displaystyle\leq\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}\\!+\\!\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}\\!+\\!C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2\ell(\mathbf{0};z)}\Big{)}$
$\displaystyle\leq\frac{B^{4}_{\sigma^{\prime}}c^{2}_{\mathbf{x}}}{m^{4c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\frac{B^{2}_{\sigma^{\prime}}B^{2}_{\sigma}}{m^{4c-2}}+C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2c_{0}}\Big{)}.$

Note that $\nabla f_{\mathbf{W}}(\mathbf{x})\nabla
f_{\mathbf{W}}(\mathbf{x})^{\top}$ is positive semi-definite, then from (B.1),
(B.8) and (B.1) with $\widetilde{\mathbf{W}}=\mathbf{0}$ we can get

$\displaystyle\lambda_{\min}(\nabla^{2}\ell(\mathbf{W};z))$
$\displaystyle\geq-\|\nabla^{2}f_{\mathbf{W}}(\mathbf{x})\|_{op}\big{|}f_{\mathbf{W}}(\mathbf{x})-y\big{|}$
$\displaystyle\geq-
C_{\mathbf{W}}\Big{(}\big{|}f_{\mathbf{W}}(\mathbf{x})-f_{\mathbf{0}}(\mathbf{x})\big{|}+\big{|}f_{\mathbf{0}}(\mathbf{x})-y\big{|}\Big{)}$
$\displaystyle\geq-
C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2\ell(\mathbf{W}_{0};z)}\Big{)}$
$\displaystyle\geq-
C_{\mathbf{W}}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}+\sqrt{2c_{0}}\Big{)}.$

The proof is completed. ∎

Let
$B_{1}=\max\big{\\{}B_{\sigma^{\prime}}^{2}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2},B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2},2B_{\sigma^{\prime\prime}}B_{\sigma}c_{\mathbf{x}},B_{\sigma^{\prime\prime}}B_{\sigma}^{2},2B_{\sigma^{\prime\prime}}^{2}c_{\mathbf{x}}\big{\\}}$
and
$B_{2}=\max\big{\\{}B_{\sigma^{\prime}}^{4}c_{\mathbf{x}}^{2},B_{\sigma^{\prime}}^{2}B_{\sigma^{\prime\prime}}^{2},B_{\sigma^{\prime\prime}}B_{\sigma},\sqrt{2c_{0}}\big{\\}}.$

######  Lemma B.2.

Suppose Assumptions 1 and 2 hold. Let $\\{\mathbf{W}_{t}\\}$ and
$\\{\mathbf{W}^{\prime}_{t}\\}$ be produced by GD iterates with $T$ iterations
based on $S$ and $S^{\prime}$, respectively. Let $\hat{\rho}=4B_{2}(1+2B_{1})$
and $C>0$ be a constant. Assume $\eta\leq 1/(2\hat{\rho})$ and (6) hold. Then
for any $c\in(1/2,1]$ and any $t=0,\ldots,T$ there holds

$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2c_{0}\eta t}$

and

$\|\nabla\ell(\mathbf{W}_{t};z)-\nabla\ell(\mathbf{W}^{\prime}_{t};z)\|_{2}\leq\hat{\rho}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{\prime}\|_{2}.$

###### Proof.

We will prove by induction to show
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$. Further, we can
show that $\rho_{\mathbf{W}}=\mathcal{O}(1)$ for any $\mathbf{W}$ produced by
GD iterates if $m$ satisfies (6). Then by assuming $\eta\leq 1/(2\hat{\rho})$
we can prove that $\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\sqrt{2c_{0}\eta
t}$.

It’s obvious that $\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$
with $t=0$ holds trivially. Assume
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$, according to the
update rule (2) we know

$\displaystyle\|\mathbf{W}_{t+1}-\mathbf{W}_{0}\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\eta\|\nabla
L_{S}(\mathbf{W}_{t})\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\eta\max_{i\in[n]}\|\nabla
f_{\mathbf{W}_{t}}(\mathbf{x}_{i})\|_{2}\big{|}f_{\mathbf{W}_{t}}(\mathbf{x}_{i})-y_{i}\big{|}$
$\displaystyle\leq\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\eta\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}(\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}\Big{(}\big{|}f_{\mathbf{W}_{t}}(\mathbf{x}_{i})-f_{\mathbf{0}}(\mathbf{W}_{t})\big{|}$
$\displaystyle\quad+\big{|}f_{\mathbf{0}}(\mathbf{W}_{t})-y_{i}\big{|}\Big{)}$
$\displaystyle\leq\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\eta\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}(\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{(}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}$
$\displaystyle\quad+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}\Big{)},$ (B.9)

where in the third inequality we used (B.1), the last inequality used (B.1)
with $\widetilde{\mathbf{W}}=\mathbf{0}$. If $m$ is large enough such that

$\displaystyle\Big{(}\frac{B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}(\|\mathbf{W}_{t}\\!-\\!\mathbf{W}_{0}\|_{2}\\!+\\!\|\mathbf{W}_{0}\|_{2})+\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\Big{)}\Big{(}\frac{B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\big{(}\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{0}\|_{2}\big{)}\\!+\\!\sqrt{2c_{0}}\Big{)}$
$\displaystyle\leq m^{2c-1},$ (B.10)

then from (B.1) we know that
$\|\mathbf{W}_{t+1}-\mathbf{W}_{0}\|_{2}\leq\eta(t+1)m^{2c-1}$. The first part
of the lemma can be proved. Now, we discuss the conditions on $m$ such that
(B.1) holds. Let
$x=\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}+\|\mathbf{W}_{0}\|_{2}$. To guarantee
(B.1), it suffices that the following three inequalities hold

$\frac{B_{\sigma^{\prime}}^{3}B_{\sigma}c_{\mathbf{x}}}{m^{4c-\frac{3}{2}}}x^{2}\leq\frac{m^{2c-1}}{3},\big{(}\frac{B_{\sigma^{\prime}}^{2}B_{\sigma}^{2}}{m^{4c-2}}+\frac{\sqrt{2c_{0}}B_{\sigma^{\prime}}^{2}c_{\mathbf{x}}}{m^{2c-\frac{1}{2}}}\big{)}x\leq\\!\frac{m^{2c-1}}{3},\frac{\sqrt{2c_{0}}B_{\sigma^{\prime}}B_{\sigma}}{m^{2c-1}}\leq\frac{m^{2c-1}}{3}.$
(B.11)

It’s easy to verify that (B.11) holds if $m\gtrsim\max\\{(\eta
T)^{\frac{4}{4c-1}},(\eta
T)^{\frac{1}{4c-2}},\|\mathbf{W}_{0}\|_{2}^{\frac{1}{3c-\frac{5}{4}}},\|\mathbf{W}_{0}\|_{2}^{\frac{1}{6c-3}}\\}$
, which can be ensured by (6). Hence, if $c\in(1/2,1]$ and (6) holds, we have
$\|\mathbf{W}_{t}-\mathbf{W}_{0}\|_{2}\leq\eta tm^{2c-1}$ for all
$t=0,1,\ldots,T$.

Recall that

$B_{1}=\max\big{\\{}B_{\sigma^{\prime}}^{2}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2},B_{\sigma^{\prime}}B_{\sigma^{\prime\prime}}c_{\mathbf{x}}^{2},2B_{\sigma^{\prime\prime}}B_{\sigma}c_{\mathbf{x}},B_{s\sigma^{\prime\prime}}B_{\sigma}^{2},2B_{s\sigma^{\prime\prime}}^{2}c_{\mathbf{x}}\big{\\}}$

and

$B_{2}=\max\big{\\{}B_{\sigma^{\prime}}^{4}c_{\mathbf{x}}^{2},B_{\sigma^{\prime}}^{2}B_{\sigma^{\prime\prime}}^{2},B_{s\sigma^{\prime\prime}}B_{\sigma},\sqrt{2c_{0}}\big{\\}}.$

Then from Lemma B.1 we know

$C_{\mathbf{W}}\leq
B_{1}\Big{(}{m^{-3c}}\big{\|}\mathbf{W}^{(2)}\big{\|}_{2}^{2}+\big{(}{m^{\frac{1}{2}-2c}}+{m^{\frac{1}{2}-3c}}\big{)}\|\mathbf{W}^{(2)}\|_{2}+{m^{1-3c}}+{m^{\frac{1}{2}-2c}}\Big{)}$

and

$\rho_{\mathbf{W}}\leq
B_{2}\Big{(}m^{1-4c}\big{\|}\mathbf{W}\big{\|}_{2}^{2}+{m^{2-4c}}+C_{\mathbf{W}}\big{(}{m^{1-2c}}\big{\|}\mathbf{W}\big{\|}_{2}+1\big{)}\Big{)}.$

Note that (6) implies $m\gtrsim(\eta
T)^{4}+\|\mathbf{W}_{0}\|_{2}^{\frac{4}{8c-3}}$. By using
$\|\mathbf{W}_{t}\|_{2}\leq\eta tm^{2c-1}+\|\mathbf{W}_{0}\|_{2}$ we can
verify that

$\rho_{\mathbf{W}_{t}}\leq 4B_{2}(1+2B_{1}):=\hat{\rho}\quad\text{ for any
}\quad t=0,\ldots,T.$

Hence, we know that $\ell$ is $\hat{\rho}$-smooth when the parameter space is
the trajectory of GD. Then for any $t=0,\ldots,T$ and any
$\mathbf{W}_{t},\mathbf{W}_{t}^{\prime}$ produced by GD iterates, there holds

$\|\nabla\ell(\mathbf{W}_{t};z)-\nabla\ell(\mathbf{W}^{\prime}_{t};z)\|_{2}\leq\hat{\rho}\|\mathbf{W}_{t}-\mathbf{W}_{t}^{\prime}\|_{2}.$
(B.12)

In addition, by the smoothness of $\ell$ we can get for any $j=0,\ldots,T-1$

$L_{S}(\mathbf{W}_{j+1})\leq
L_{S}(\mathbf{W}_{j})-\eta\Big{(}1-\frac{\eta\hat{\rho}}{2}\Big{)}\|\nabla
L_{S}(\mathbf{W}_{j})\|_{2}^{2}.$

Rearranging and summing over $j$ yields

$\eta\Big{(}1-\frac{\eta\hat{\rho}}{2}\Big{)}\sum_{j=0}^{t}\|\nabla
L_{S}(\mathbf{W}_{j})\|_{2}^{2}\leq\sum_{j=0}^{t}L_{S}(\mathbf{W}_{j})-L_{S}(\mathbf{W}_{j+1})\leq
L_{S}(\mathbf{W}_{0}).$

Note that the update rule of GD (2) implies

$\mathbf{W}_{t+1}=\mathbf{W}_{0}-\eta\sum_{j=0}^{t}\nabla
L_{S}(\mathbf{W}_{j}).$

Combining the above two equations together and noting that $\eta\hat{\rho}\leq
1/2$, we obtain

$\|\mathbf{W}_{t+1}-\mathbf{W}_{0}\|_{2}^{2}=\eta^{2}\big{\|}\sum_{j=0}^{t}\nabla
L_{S}(\mathbf{W}_{j})\big{\|}^{2}_{2}\leq\eta^{2}t\sum_{j=0}^{t}\big{\|}\nabla
L_{S}(\mathbf{W}_{j})\big{\|}^{2}_{2}\leq 2\eta tL_{S}(\mathbf{W}_{0})\leq
2c_{0}\eta t.$

The proof is completed. ∎

The almost co-coercivity of the gradient operator for three-layer neural
networks is given as follows. Recall that
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z^{\prime}_{i},z_{i+1},z_{n}\\}$ is the set
formed from $S$ by replacing the $i$-th element with $z_{i}^{\prime}$ and for
any $\mathbf{W}$,

$L_{S^{\setminus
i}}(\mathbf{W})=L_{S}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i})=L_{S^{(i)}}(\mathbf{W})-\frac{1}{n}\ell(\mathbf{W};z_{i}^{\prime}).$

Let $\\{\mathbf{W}_{t}\\}$ and $\\{\mathbf{W}_{t}^{(i)}\\}$ be the sequence
produced by GD based on $S$ and $S^{(i)}$, respectively. Let
$C_{3,T}=4B_{1}\big{(}2c_{0}\eta
T{m^{-3c}}+\big{(}{m^{\frac{1}{2}-2c}}+{m^{\frac{1}{2}-3c}}\big{)}\sqrt{2c_{0}\eta
T}+{m^{1-3c}}+{m^{\frac{1}{2}-2c}}\big{)}$.

######  Lemma B.3.

Suppose $\eta\leq 1/(8\hat{\rho})$ where $\hat{\rho}=4B_{2}(1+2B_{1})$. Assume
(6) holds. Then

$\displaystyle\langle\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus i}}$
$\displaystyle(\mathbf{W}^{(i)}_{t})\rangle\geq
2\eta\Big{(}1-4\eta\hat{\rho}\Big{)}\big{\|}\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\big{\|}_{2}^{2}$
$\displaystyle-\tilde{\epsilon}_{t}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}-\eta\big{(}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{)}\big{\|}_{2}^{2},$

where $\tilde{\epsilon}_{t}=C_{3,T}\big{(}B_{3}\big{(}\frac{\sqrt{\eta
T}+\|\mathbf{W}_{0}\|_{2}}{m^{2c-\frac{1}{2}}}+m^{1-2c}\big{)}\big{(}(1+\eta\hat{\rho})\|\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\|_{2}+2\big{(}\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2}\big{)}+\sqrt{2c_{0}}\big{)}$.

###### Proof.

For any $\mathbf{W}\in\mathcal{B}\big{(}0,2(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})\big{)}$, defining the following two functions

$G_{1}(\mathbf{W})=L_{S^{\setminus i}}(\mathbf{W})-\langle\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t}^{(i)}),\mathbf{W}\rangle,\qquad
G_{2}(\mathbf{W})=L_{S^{\setminus i}}(\mathbf{W})-\langle\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t}),\mathbf{W}\rangle.$

Note that

$\displaystyle\\!\langle\mathbf{W}_{t}\\!-\\!\mathbf{W}_{t}^{(i)},\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})\\!-\\!\nabla L_{S^{\setminus
i}}(\mathbf{W}^{(i)}_{t})\rangle\\!=\\!\big{(}G_{1}\big{(}\mathbf{W}_{t}\big{)}\\!-\\!G_{1}\big{(}\mathbf{W}^{(i)}_{t}\big{)}\big{)}\\!+\\!\big{(}G_{2}\big{(}\mathbf{W}^{(i)}_{t}\big{)}\\!-\\!G_{2}\big{(}\mathbf{W}_{t}\big{)}\big{)}.$
(B.13)

Hence, it is enough to lower bound
$G_{1}\big{(}\mathbf{W}_{t}\big{)}-G_{1}\big{(}\mathbf{W}^{(i)}_{t}\big{)}$
and
$G_{2}\big{(}\mathbf{W}^{(i)}_{t}\big{)}-G_{2}\big{(}\mathbf{W}_{t}\big{)}$.

Note that for any $\mathbf{W}_{t}$, Lemma B.1 implies that
$\|\mathbf{W}_{t}\|_{2}\leq\sqrt{2c_{0}\eta t}+\|\mathbf{W}_{0}\|_{2}$. Then
there holds

$\displaystyle\big{\|}\mathbf{W}_{t}-\eta\nabla
G_{1}(\mathbf{W}_{t})\big{\|}_{2}$
$\displaystyle\leq\big{\|}\mathbf{W}_{t}\big{\|}_{2}+\eta\big{\|}\nabla
L_{S^{\setminus i}}(\mathbf{W}_{t})-\nabla L_{S^{\setminus
i}}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}$
$\displaystyle\leq\big{\|}\mathbf{W}_{t}\big{\|}_{2}+\eta\hat{\rho}\big{\|}\mathbf{W}_{t}-\mathbf{W}_{t}^{(i)}\big{\|}_{2}$
$\displaystyle\leq\sqrt{2c_{0}\eta
t}+\|\mathbf{W}_{0}\|_{2}+2\eta\hat{\rho}\big{(}\sqrt{2c_{0}\eta
t}+\|\mathbf{W}_{0}\|_{2}\big{)}$ $\displaystyle\leq 2\big{(}\sqrt{2c_{0}\eta
t}+\|\mathbf{W}_{0}\|_{2}\big{)},$

where in the last inequality we used $\eta\hat{\rho}\leq 1/8$. Similarly, we
can show that $\big{\|}\mathbf{W}_{t}^{(i)}-\eta\nabla
G_{2}(\mathbf{W}_{t}^{(i)})\big{\|}_{2}\leq 2(\sqrt{2c_{0}\eta
T}+\|\mathbf{W}_{0}\|_{2})$. Hence, we know $\mathbf{W}_{t}-\eta\nabla