lβ
β∈[1,2]
1. Introduction
Neural networks have become an interesting subject in a variety of areas, including pattern recognition [Reference Albanese, Alemanno, Alessandrelli and Barra1, Reference Krotov and Hopfield19], autonomous vehicles [Reference Serban, Poll and Visser33, Reference Tian, Pei, Jana and Ray40], image segmentation [Reference Badrinarayanan, Kendall and Cipolla3, Reference Li, Ma, Xu, Tang, He and Guo24], and other fields. In recent years, extensive research on optimization and statistical guarantees has been conducted in [Reference Bartlett, Montanari and Rakhlin7], [Reference Sun36], [Reference Taheri, Xie and Lederer38], and the references therein. Substantial effort and contributions have been devoted to the algorithmic and computational aspects, while theoretical problems still remain to be solved urgently. One can refer to [Reference Bartlett, Montanari and Rakhlin7] and references therein for reviews. The challenges exist mainly due to the activation function and the complex structure of neural networks [Reference Xiang, Tran and Johnson44].
We begin by introducing the basic regression framework adopted throughout this paper. Consider independent observations
$(\mathbf{x}_1,y_1),\ldots,(\mathbf{x}_n,y_n)\in \mathbb{R}^{d}\times \mathbb{R}$
generated from the following non-parametric regression model:
\begin{align}y_i=g_*(\mathbf{x}_i)+\epsilon_i, \quad i\in \{1,\ldots,n\},\end{align}
where
$g_*\colon \mathbb{R}^{d}\rightarrow\mathbb{R}$
denotes the unknown underlying regression function, and
$\epsilon_1,\ldots,\epsilon_n\in\mathbb{R}$
represent independent random noise variables. Our objective is to approximate the target function
$g_*$
via feedforward neural networks. For a given input
$\mathbf{x}\in\mathbb{R}^{d}$
, the network output is formulated as
\begin{align}g_\Theta(\mathbf{x}) \, :\!= \, W^L \mathbf{f}^{\, L}(\!\cdots W^1 \mathbf{f}^1(W^0 \mathbf{x})\cdots \!),\end{align}
where the network parameter set is defined by
\[\mathcal{A}\, :\!= \, \{\Theta= (W^L, \ldots, W^0)\colon W^l \in \mathbb{R}^{p_{l+1}\times p_{l}}, \ l=0,1,\ldots,L\}.\]
Here
$\mathbf{x}_i$
and
$y_i$
correspond to network inputs and outputs, respectively; the
$W^l$
stand for layer-wise weight matrices; L denotes the number of hidden layers; and
$p_0,\dots,p_{L+1}$
denote the neuron number of each layer. The mapping
$\mathbf{f}^{\, l}\colon \mathbb{R}^{p_l}\rightarrow\mathbb{R}^{p_{l}}$
refers to the activation function of the lth layer.
As the depth of the neural network increases, the complexity of the model and the number of parameters in the untrained network continue to expand; thus the model becomes prone to overfitting (see [Reference Srivastava, Hinton, Krizhevsky, Sutskever and Salakhutdinov35] and [Reference Zhang, Song, Gao, Chen, Bao and Ma46]). To avoid overfitting and reduce generalization errors, a common approach is to apply regularization techniques. Regularization theory has developed accordingly, and much work has been done to improve the robustness and generalization ability of neural networks. Works such as that of Wu et al. [Reference Wu, Li, Wang, Meng, Qin, Chen and Liu43] introduce a simple consistency training strategy (R-Drop) to regularize dropout, compensating for the non-negligible inconsistency between training and inference. Yildirim and Özkale [Reference Yildirim and Özkale45] conclude that biased estimators may be powerful tools in extreme learning machine studies and that ridge-based regression estimators may outperform extreme machine learning. In [Reference Taheri, Xie and Lederer38], Taheri et al. investigate the scale property of 1-degree neural networks by applying the idea of scale regularization. In [Reference Taheri, Xie and Lederer39], they consider statistical guarantees for approximating stationary points using the strategy of scale regularization. Subsequently, the idea of scale regularization has been widely applied in many ways, such as connection- and node-sparse deep learning [Reference Lederer22], and reducing computational and statistical complexity in machine learning [Reference Mohades and Lederer27].
Among existing regularization strategies, scale regularization has attracted increasing attention for homogeneous network analysis. In [Reference Taheri, Xie and Lederer38], Taheri et al. explore scale regularization for classical 1-degree neural networks, while in [Reference Taheri, Xie and Lederer39] they further establish statistical guarantees for approximate stationary points under the same framework. Subsequently, the scale regularization idea has been extended to sparse deep learning [Reference Lederer22] and complexity reduction in machine learning [Reference Mohades and Lederer27].
Notably, scale regularization inherently requires activation functions to satisfy non-negative homogeneity. For theoretical analysis and statistical guarantee derivation, existing studies commonly impose the standard global Lipschitz condition on activations, with typical examples including ReLU [Reference Lederer21] and ELU [Reference Clevert, Unterthiner and Hochreiter10]. Nevertheless, most existing results are confined to 1-degree networks with globally Lipschitz activations. For general k-degree neural networks and activation functions that only satisfy local Lipschitz continuity, polynomial growth considerably elevates analytical complexity, leading to a scarcity of rigorous statistical theories in this setting.
Motivation and definition of
k
-degree neural networks. To provide a self-contained presentation, we first clarify the conceptual connotation and research motivation of k-degree neural networks. Conceptually, a k-degree neural network adopts activation functions with k-degree non-negative homogeneity: scaling the input vector by a non-negative constant c yields an output scaled by
$c^k$
. The case
$k=1$
recovers conventional homogeneous networks such as ReLU-based structures, whereas
$k>1$
enables the network to naturally characterize high-order polynomial interactions among input features. Such modeling flexibility is particularly useful in physical system simulation, high-dimensional non-parametric regression, and geometric deep learning, where homogeneous structures and polynomial feature interactions widely exist; see more details in [Reference Diaa, Fenaux, Humphries, Dietz, Ebrahimianghazani, Kacsmar and Kerschbaum12], [Reference Feng and Yang14], [Reference Klusowski and Barron18], [Reference Krotov and Hopfield19], [Reference Kubjas, Li and Wiesmann20], and [Reference Pusztaházi, Eigner and Csiszár29]. From a theoretical perspective, the k-degree homogeneous structure facilitates the application of scale regularization and enables us to derive sharper statistical guarantees that are unattainable in standard network frameworks.
We now formalize the relevant mathematical definition.
Definition 1.1. (Non-negative homogeneity and positive definiteness.) For any
$d_1,d_2\in \mathbb{N}$
, we say that a function
$\mathbf{f}\colon {\mathbb R}^{d_1}\rightarrow\mathbb{R}^{d_{2}}$
is non-negative homogeneous of degree
$k \in (0,\infty)$
if, for any
$c\in [0,\infty)$
and
$\mathbf{z}\in \mathbb{R}^{d_1}$
, we have
\begin{align*}\mathbf{f}(c\mathbf{z})=c^k\mathbf{f}(\mathbf{z}),\end{align*}
and we say that a function
$\mathbf{f}\colon \mathbb{R}^{d_1}\rightarrow [0,\infty)$
is positive definite if
\begin{align*}\mathbf{f}(\mathbf{z})=0 \quad \Leftrightarrow \quad \mathbf{z}={\mathbf{0}_{d_1}}.\end{align*}
Novelties and contributions. Compared with [Reference Taheri, Xie and Lederer38], our contributions are non-trivial and threefold.
-
(i) Our framework covers general k-degree neural networks, which substantially generalize the standard networks studied in [Reference Taheri, Xie and Lederer38]. Their layered polynomial structure requires entirely new analytical tools and theoretical arguments.
-
(ii) The extension to general
$\ell_{\beta}$
-regularization entails non-trivial refinements to concentration inequalities and to the decomposition of approximation and estimation errors under general convex penalties. -
(iii) We establish new statistical guarantees tailored to k-degree architectures that cannot be directly inferred from
$\ell_1$
-based theory, providing fresh theoretical insights into regularized deep networks.
Our analysis employs novel techniques to bound approximation errors and derive oracle inequalities under polynomial homogeneity. We further develop iterative constructions to handle the additional complexity caused by polynomial growth and to establish Lipschitz continuity of network mappings under locally Lipschitz activation functions.
The remainder of this paper is organized as follows. In Section 2 we establish the framework of scale regularization for k-degree neural networks and give a general prediction error for regularized least-squares estimators. In Section 3 we consider an example with
$l_{\beta}$
-regularization for
$\beta\in[1,2]$
and a sequence of sub-Gaussian noise vectors, showing that the corresponding prediction error decreases by the second root of the number of samples. In Section 4 we conclude our paper and give some discussions. In Appendix A we provide the proof of proposition and theorems in Sections 2 and 3.
2. Framework and statistical guarantee
2.1. Scale regularization for k-degree neural networks
In this subsection we conduct the theoretical analysis of the proposed network architecture. Specifically, the 0th layer corresponds to the input layer with dimension
$p_0 = d$
, and the
$(L+1)$
th layer serves as the output layer with
$p_{L+1} = 1$
. The total number of network parameters is defined as
\begin{align*}P \, :\!= \, \sum_{l=0}^L p_{l+1} p_l.\end{align*}
Based on the properties of k-degree non-negative homogeneous functions and positive definite functions introduced earlier, we present the following proposition that characterizes an alternative parametrization. The proof is provided in Appendix A.1.
Proposition 2.1. Suppose that the activation functions
$\mathbf{f}^1,\ldots,\mathbf{f}^{\, L}$
are non-negative homogeneous of degree k. Let the function
$h \colon \mathcal{A} \rightarrow [0,\infty)$
be non-negative homogeneous of degree
$\alpha \in (0,\infty)$
and positive definite. Denote the unit ball by
\[\mathcal{A}_h\, :\!= \, \{\Theta \in \mathcal{A}\colon h(\Theta)\leq 1\}.\]
Then, for any
$\Theta \in \mathcal{A}$
and
$\mathbf{x} \in \mathbb{R}^{d}$
, there exists a pair of
$\kappa \in (0,\infty)$
and
$\Omega\in \mathcal{A}_h$
such that
\begin{align}g_\Theta(\mathbf{x}) = \kappa g_\Omega (\mathbf{x}).\end{align}
Inversely, for every pair of
$\kappa \in (0,\infty)$
and
$\Omega\in \mathcal{A}_h$
, there exists a
$\Theta \in \mathcal{A}$
such that the equality (2.1) holds.
Motivated by the idea of scale regularization developed in [Reference Taheri, Xie and Lederer38] and Proposition 2.1 above, we estimate the true data generating function
$g_*$
to
$[0,\infty)\times \mathcal{A}_h$
with the help of a parameter space of networks corresponding to
$\{\kappa g_\Omega\colon \kappa\in[0,\infty), \Omega\in \mathcal{A}_h\}$
. Hence we study the following neural networks: for any
$\mathbf{x}\in\mathbb{R}^{d}$
,
\begin{align*} \kappa g_\Omega(\mathbf{x}) \, :\!= \, \kappa U^L \mathbf{f}^{\, L}(\!\cdots U^1 \mathbf{f}^1 (U^0 \mathbf{x})),\end{align*}
which is indexed by the scale parameters
$\kappa\in[0,\infty)$
and
$\Omega= (U^L, \ldots , U^0) \in \mathcal{A}_h$
.
2.2. Statistical prediction guarantee
In deep learning, taking the high-dimensionality of the parameter space
$\mathcal{A}$
into consideration, the usual approach to estimate the network parameters in model (1.1) is the least-squares estimator complemented by some type of regularization, and the concrete form can be written as follows:
\[\hat{\Theta}_{\mathrm{reg},h}\in \operatorname*{arg\,min}_{\Theta\in\mathcal{A}} \Biggl\{ \dfrac{1}{n}\sum_{i=1}^n(y_i-g_\Theta(\mathbf{x}_i))^2+\lambda h(\Theta) \Biggr\},\]
where
$\lambda \in[0,\infty)$
is a tuning parameter and
$h \colon \mathcal{A} \rightarrow [0,\infty)$
is a regularizer.
However, it seems to be difficult to analyze such estimators in network frameworks; for more detail on analyzing the estimators, we refer to [Reference Wei, Lee, Liu and Ma42] and [Reference Wu, Li, Wang, Meng, Qin, Chen and Liu43] and the references therein. In this section we employ the alternative parametrization to incorporate regularizers. Based on the equality
$g_{\hat{\Theta}_{LS}}=\hat{\kappa}_{LS} g_{\hat{\Omega}_{LS}}$
obtained by Proposition 2.1, we adopt the approach of scale regularization to transform the above estimation problem into the following framework:
\begin{align}(\hat{\kappa}_{h},\hat{\Omega}_{h})\in \operatorname*{arg\,min}_{\substack{ \kappa\in[0,\infty)\\[3pt] \Omega\in\mathcal{A}_h } } \Biggl\{ \dfrac{1}{n}\sum_{i=1}^n(y_i-\kappa g_\Omega(\mathbf{x}_i))^2+\lambda \kappa \Biggr\}.\end{align}
Thus we turn to solving the regularization on the scale parameter
$\kappa$
.
Now we focus on the statistical guarantees for the parameter estimator described above. On the one hand, we consider the prediction error
\[\mathrm{ err}(\kappa g_\Omega)\, :\!= \, \sqrt{ \dfrac{1}{n}\sum_{i=1}^n(\kappa g_\Omega(\mathbf{x}_i)-g_*(\mathbf{x}_i))^2 }\quad \text{for $\kappa\in[0,\infty),\ \Omega\in\mathcal{A}_h$,}\]
which measures the accuracy of the network
$\kappa g_\Omega$
fitting the unknown function
$g_{*}$
on the data. On the other hand, for a new sample
$(\mathbf{x},y) \in \mathbb{R}^{d}\times \mathbb{R}$
, we measure the generalization error or prediction risk by
\[\mathrm{risk}(\kappa g_\Omega)\, :\!= \, \mathbb{E}_{(\mathbf{x},y)} [ (\kappa g_\Omega(\mathbf{x})-y)^2 ]\quad \text{for $\kappa\in[0,\infty),\ \Omega\in\mathcal{A}_h $.}\]
Similar to high-dimensional linear regression, the core quantity of prediction guarantees is the effective noise [Reference Lederer and Vogt23], and thus we define the quantile
$\lambda_{h,t}$
of the effective noise for given level
$t \in [0, 1]$
through
\begin{align*} \lambda_{h,t} = \min \{ \delta \in[0,\infty) \colon \mathbb{P}(z_h\leq \delta)\geq 1-t \},\end{align*}
where
\begin{align*} z_h \, :\!= \, \sup\nolimits_{ \Omega\in\mathcal{A}_h } \Biggl\{ \dfrac{2}{n}\sum_{i=1}^n g_\Omega(\mathbf{x}_i) \epsilon_i \Biggr\},\end{align*}
which plays an important role in exploring the properties of the function class
$\{g_{\Omega}\colon \Omega\in\mathcal{A}_{h}\}$
, such as the Gaussian complexity and Rademacher complexity [Reference Bartlett and Mendelson5].
By the same argument as the proof of [Reference Taheri, Xie and Lederer38, Theorem 2], we can immediately obtain the following prediction guarantee in terms of the prediction error.
Theorem 2.1. Assume that
$\lambda \geq \lambda_{h,t}$
for
$t \in [0, 1]$
. Then
\[\mathrm{err}^2(\hat{\kappa}_h g_{{\hat\Omega}_h}) \leq \inf_{\substack{ \kappa\in[0,\infty)\\[3pt] \Omega\in\mathcal{A}_h } }\{ \mathrm{err}^2( \kappa g_\Omega) +2 \lambda \kappa \}, \]
with probability at least
$1-t$
.
The error bound suggests that the squared prediction error of the regularized estimator is bounded by the squared bias term
$\mathrm{err}^2( \kappa g_\Omega)$
and the variance term
$2 \lambda \kappa$
. A small prediction error can be achieved with relatively small quantile
$\lambda_{h,t}$
and scale
$\kappa$
.
3. Example:
$l_\beta$
-regularization for
$\beta\in[1,2]$
In this section we consider the case
$k>1$
and illustrate a concrete example of
$l_\beta$
-regularization to present an explicit bound. Specifically, we consider a weak regularizer proposed in [Reference Wei, Lee, Liu and Ma42], which has proved that the sample efficiency can indeed depend on the presence of the regularizer, and the weak regularizer often makes the optimization problem achieve the best results (the maximum normalized margin solution; see more details in [Reference Wei, Lee, Liu and Ma42, Section 4]). Recently, the weak regularizer has been widely used in [Reference Bartlett, Foster and Telgarsky6], [Reference McCulloch, Pierre, Linka and Kuhl26], and the references therein. Hence, similar to [Reference Wei, Lee, Liu and Ma42, (4.1)], for any
$\beta\in[1,2]$
, we define the regularizer h as
\begin{align*}h(\Omega)\, :\!= \, |\!|\!| \Omega |\!|\!|_F^{\beta} \, :\!= \, \Biggl(\sum_{l=0}^{L}\sum_{k=1}^{p_{l+1}}\sum_{j=1}^{p_{l}}|U^l_{kj}|^{2} \Biggr)^{{{\beta}/{2}}}.\end{align*}
Then h is non-negative homogeneous of degree
$\beta$
.
Before stating our main conclusions, we first give the definition of the Euclidean norm: for any
$d\geq 1$
and
$v\in\mathbb{R}^{d}$
,
\[|\mathbf{v}| \, :\!= \, \sqrt{\sum_{i=1}^d \vert v_i \vert^2 }.\]
Then we suppose that the activation functions
$\mathbf{f}^1,\ldots,\mathbf{f}^{\, L}$
satisfy the following assumption.
Assumption 3.1. For all
$l\in\{1,\ldots,L\}$
, let the activation functions
$\mathbf{f}^{\, l}$
be non-negative homogeneous of degree
$k\in(1,\infty)$
and positive definite. We further suppose that the activation functions satisfy
$\mathbf{f}^{\, l}(\mathbf{0}_{p_l})=\mathbf{0}_{p_l}$
and are locally Lipschitz-continuous for a constant
$M_k \in (1,\infty)$
and with respect to the Euclidean norms on their input and output spaces:
\begin{align}\vert \mathbf{f}^{\, l}(\mathbf{z})-\mathbf{f}^{\, l}(\mathbf{z'}) \vert \leq M_k (\vert \mathbf{z} \vert^{k-1}+ \vert \mathbf{z}' \vert^{k-1}+1 )\vert \mathbf{z}-\mathbf{z'} \vert\quad \text{for all $\mathbf{z},\mathbf{z'}\in \mathbb{R}^{p_l}$.}\end{align}
Assumption 3.1 is satisfied by many nonlinear activation functions. For example, the square ReLU function
$z\mapsto \max\{z,0\}^{2}$
[Reference Klusowski and Barron18] satisfies Assumption 3.1 with
$M_{2}=2$
, and when
$k\geq2$
, the
$\mathrm{Re}P_{k}$
function
$z\mapsto \max\{z,0\}^{k}$
[Reference Krotov and Hopfield19] satisfies Assumption 3.1 with
$M_{k}=k\times2^{k-2}$
. For more details on the activation functions, we refer the readers to [Reference Apicella, Donnarumma, Isgrò and Prevete2], [Reference Chung, Lee and Park9], [Reference Dubey, Singh and Chaudhuri13], [Reference Janjua, Zulfiqar, Khan and Ramay17], [Reference Lederer21], [Reference Rasamoelina, Adjailia and Sinčák31], [Reference So, Mańke, Liu, Dai, Shazeer and Le34], [Reference Szandala37], and the references therein.
Furthermore, we assume the noise variables
$\epsilon_i$
in model (1.1) satisfy the uniformly sub-Gaussian assumption [Reference Geer15, Chapter 8].
Assumption 3.2. For
$i=1,\ldots,n$
, let the noise variables
$\epsilon_i$
be independent, centered, and uniformly sub-Gaussian for constants
$K_1,\gamma_1 \in(0,\infty)$
:
\[\max_{i\in \{1,\ldots,n\}} K_1^2\bigl(\mathbb{E} {\mathrm{e}}^{{{|\epsilon_i|^2}/{K_1^2}}}-1 \bigr)\leq \gamma_1^2. \]
For any
$\mathbf{x}\in \mathbb{R}^{d}$
, we define
\begin{align*}B(\mathbf{x})&=2^{L-1+\frac{(L+6)k^{L+3}}{(k-1)^{2}}}{M_k^{\frac{(L+7)k^{L+3}}{k-1}}}\biggl(\dfrac{2}{L}\biggr)^{{{L}/{2}}} \bigl(1 +\big( \vert \mathbf{x}\vert^{k-1} + \vert \mathbf{x} \vert^{(k-1)k^{L+1}} \big) ^{2}\bigr)\\[3pt] &\quad \times\Bigl(1+2^{\frac{L^{2}(L+10)k^{L+2}}{(k-1)^{2}}}M_k^{\frac{(3L^{2}+1)Lk^{L+2}}{k-1}}\big(|\mathbf{x}|+|\mathbf{x}|^{Lk^{L+1}}\big)^{L}\Bigr)\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr).\end{align*}
With the shorthand
\[\mathcal{A}_{\beta} \, :\!= \, \bigl\{\Theta \in \mathcal{A}\colon \|\Omega\|_F^{\beta} \leq 1\bigr\}\quad\text{and}\quad\|\mathbf{x}\|_n \, :\!= \, \sqrt{\frac{1}{n}\sum_{i=1}^n |\mathbf{x}_i|^2},\]
we extend our analysis to general
$\ell_{\beta}$
-regularization. This generalization necessitates non-trivial refinements of concentration inequalities as well as the decomposition of approximation and estimation errors under general convex penalties. The following prediction guarantee for the estimator in (2.2) is then established, and its proof is provided in Appendix A.2.
Theorem 3.1. Assume Assumptions 3.1 and 3.2 hold. Suppose that
\[\lambda\geq a M_k^L \sqrt{ \dfrac{1}{n}\sum_{i=1}^n (B(\mathbf{x}_i))^2 } \sqrt{L\log(2P)} \dfrac{\log(2n)}{\sqrt{n}}, \]
where
$a \in (0,\infty)$
is a constant that depends only on the noise parameters
$K_1$
and
$\gamma_1$
. Then, for n large enough,
\[\mathrm{err}^2(\hat{\kappa}_h g_{{\hat\Omega}_h}) \leq \inf_{\substack{ \kappa\in[0,\infty)\\ \Omega\in\mathcal{A}_1 } } \{ \mathrm{err}^2( \kappa g_\Omega) +2 \lambda \kappa \} , \]
with probability at least
$1-\tfrac{1}{n}$
.
Remark 3.1. From the locally Lipschitz-continuous condition, we know the activation function has polynomial growth. As a result, the complexity of neural networks is greatly increased, which makes it very difficult to derive the continuity and boundary properties of the neural networks in
$\mathcal{A}_{\beta}$
. To address this issue, we construct some iterative sequences during the proof of Theorem 3.1, then utilize some common techniques for handling locally Lipschitz-continuous functions. Finally, we obtain the Lipschitz-continuous property of the neural networks, and thus Theorem 3.1 is derived. However, when the input
$|\mathbf{x}|>1$
, the polynomial growth of the activation function leads to the bound obtained in Theorem 3.1 being exponentially increasing with respect to the number of layers L, and it seems difficult to improve this result by using the iterative method in this paper.
As an illustration, we can simplify Theorem 3.1 in a parametric setting.
Corollary 3.1. Assume that Assumptions 3.1 and 3.2 hold. Suppose that
\begin{align*}\lambda =a M_k^L \sqrt{ \dfrac{1}{n}\sum_{i=1}^n (B(\mathbf{x}_i))^2 } \sqrt{L\log(2P)} \dfrac{\log(2n)}{\sqrt{n}},\end{align*}
and there exist parameters
$(\kappa_*, \Omega_*) \in [0,\infty) \times \mathcal{A}_1$
such that
$\kappa_* g_{\Omega_*}(\mathbf{x}_i)=g_{*}(\mathbf{x}_i)$
for all
$i \in \{1, \ldots, n\}$
. Then, for n large enough,
\begin{align*}\mathrm{err}^2(\hat{\kappa}_h g_{{\hat\Omega}_h}) \leq 2a \kappa_* M_k^L \sqrt{ \dfrac{1}{n}\sum_{i=1}^n (B(\mathbf{x}_i))^2 }\sqrt{L\log(2P)} \dfrac{\log(2n)}{\sqrt{n}}\end{align*}
with probability at least
$1-{{1}/{(2n)}}$
.
Remark 3.2. For the k-degree neural networks with
$l_{\beta}$
-regularization, Theorem 3.1 and Corollary 3.1 establish essentially an
$n^{-{{1}/{2}}}$
-decrease of the error in the sample size n; this conclusion validates the conjecture in [Reference Taheri, Xie and Lederer38, Corollary 4], and it is further verified that the method of scale regularization is still applicable to the case of k-degree neural networks.
Moreover, based on Theorem 3.1 and Corollary 3.1 above, and similar to the proof of [Reference Taheri, Xie and Lederer38, Theorem 5], we can immediately obtain the following bound for the prediction risk.
Theorem 3.2. Keep the same assumptions and notation as in Corollary 3.1. Suppose that the inputs
$\mathbf{x}_1,\ldots,\mathbf{x}_n$
are i.i.d. random vectors. Then, for n large enough,
\begin{align*}\mathrm{risk}(\hat{\kappa}_h g_{{\hat\Omega}_h}) &\leq 1.01 \mathrm{risk}(\kappa_*g_{\Omega_*}) + a \kappa_* M_k^L \sqrt{ \dfrac{1}{n}\sum_{i=1}^n ({ B(\mathbf{x}_{i})})^2 } \sqrt{L\log(2P)} \dfrac{\log(2P)}{\sqrt{n}} \\[3pt] & \quad + a (\kappa_*)^2 M_k^{2L} \sqrt{ L^2 \log(2p) \sum_{i=1}^n (B(\mathbf{x}_i))^4 } \dfrac{\log(2n)}{n} ,\end{align*}
with probability at least
$1-{{1}/{n}}$
, where
$a \in (0,\infty)$
is a constant that depends only on the sub-Gaussian parameters
$K _1$
and
$\gamma_1$
of the noise.
Theorem 3.2 proves the fact that for properly chosen tuning parameter
$\lambda$
and large enough sample size n, any reasonable optimal point of (2.2) generalizes essentially as well as
$(\kappa_*, \Omega_*) $
. Our result generalizes [Reference Taheri, Xie and Lederer38, Theorem 5] in the context of k-degree neural networks, and is applicable to the global optimum of the objective function.
4. Discussion
This paper establishes statistical guarantees for k-degree neural networks via scale regularization. Our theoretical results show that the prediction error decrease is of the order of
$n^{-{{1}/{2}}}$
in the sample size n. We also illustrate an explicit bound in the case of
$l_\beta$
-regularization, locally Lipschitz activation functions, and sub-Gaussian noise. Indeed, our new statistical guarantees might be useful in deriving bounds for other regularizers [Reference Dai, Karzand and Srebro11, Reference McCulloch, Pierre, Linka and Kuhl26, Reference Neyshabur, Tomioka and Srebro28, Reference Wei, Lee, Liu and Ma42], activation functions [Reference Castaneda, Morris and Khoshgoftaar8, Reference Lederer21, Reference Lyu and Li25, Reference Ramachandran, Zoph and Le30], and noise distributions [Reference Bakhshizadeh, Maleki and de la Pena4, Reference Gorbunov, Danilova, Dobre, Dvurechenskii, Gasnikov and Gidel16, Reference Rigollet and Hütter32, Reference Vershynin41] with different rates. Theoretical properties still merit further research within the framework of neural networks.
Appendix A. Proofs in Sections 2 and 3
A.1. Proof of Proposition 2.1
We first prove the sufficiency of the proposition. For any fixed
$\Theta= (W^L, \ldots, W^0)\in \mathcal{A}$
, we assume that
$W^l = \mathbf{0}_{p_{l+1}\times p_l}$
for an
$l \in \{0,\ldots, L\}$
. By (1.2) and the fact that the activation functions are non-negative homogeneous, we have
\begin{align*}g_\Theta(\mathbf{x})&=W^L \mathbf{f}^{\, L}(\!\cdots \mathbf{0}_{p_{l+1}\times p_l} \mathbf{f}^{\, l}(\!\cdots W^1 \mathbf{f}^1(W^0 \mathbf{x})))\\[3pt] &=W^L \mathbf{f}^{\, L}(\!\cdots 0\cdot \mathbf{0}_{p_{l+1}\times p_l} \mathbf{f}^{\, l}(\!\cdots W^1 \mathbf{f}^1(W^0 \mathbf{x})))\\[3pt] &=0 \quad \text{for all $\mathbf{x} \in \mathbb{R}^{d}$.}\end{align*}
Therefore, when
$W^l = \mathbf{0}_{p_{l+1}\times p_l}$
for
$l \in \{0,\ldots, L\}$
, let
$\kappa \, :\!= \, 0$
, and the equality
$\kappa g_\Omega = g_\Theta$
holds for all
$\Omega\in \mathcal{A}_h$
.
When
$W^l \neq \mathbf{0}_{p_{l+1}\times p_l}$
for all
$l \in \{0, \ldots, L\}$
, denote
\[\kappa\, :\!= \, (h(\Theta))^{{(k^L+k^{L-1}\cdots +1)}/{\alpha}}.\]
Notice that h is positive definite; we have
$h(\Theta)\in(0,\infty)$
, which implies
$\kappa\in(0,\infty)$
. Let
\[\Omega\, :\!= \, \Theta/\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}=\bigl(W^L/\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}, \ldots, W^0/\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}\bigr).\]
Since h is non-negative homogeneous of degree
$\alpha$
, it is straightforward to calculate that
\[h(\Omega)=h\bigl(\Theta/\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}\bigr)=\kappa^{{-\alpha}/{(k^L+k^{L-1}\cdots +1)}}h(\Theta)=(h(\Theta))^{-1}h(\Theta)=1,\]
that is,
$\Omega\in\mathcal{A}_{h}$
. Now we only need to prove the equality (2.1). Since
$\mathbf{f}^1,\ldots,\mathbf{f}^{\, L}$
are non-negative homogeneous of degree k, for any
$\mathbf{x} \in\mathbb{R}^d$
, one can derive that
\begin{align*} \kappa g_{\Omega}(\mathbf{x}) &= \kappa \dfrac{W^L}{\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}} \mathbf{f}^{\, L}\biggl(\!\cdots \dfrac{W^1}{\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}}\mathbf{f}^1\biggl(\dfrac{W^0}{\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}} \mathbf{x}\biggr)\biggr)\\[3pt] &= \kappa \dfrac{W^L}{\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}}} \mathbf{f}^{\, L} \biggl(\!\cdots \dfrac{W^1}{\kappa^{{k+1}/{(k^L+k^{L-1}\cdots +1)}}} \mathbf{f}^1\bigl({W^0} \mathbf{x}\bigr)\biggr)\end{align*}
\begin{align*} &= \cdots \\[3pt] &= \dfrac{\kappa}{\kappa^{{(k^L+k^{L-1}\cdots +1)}/{(k^L+k^{L-1}\cdots +1)}}} W^L\mathbf{f}^{\, L}(\!\cdots {W^1}\mathbf{f}^1({W^0} \mathbf{x}))\\[3pt] &= W^L\mathbf{f}^{\, L}(\!\cdots {W^1}\mathbf{f}^1({W^0} \mathbf{x}))\\[3pt] & = g_\Theta(\mathbf{x}),\end{align*}
and thus (2.1) is proved.
Inversely, for a fixed
$\kappa\in[0,\infty)$
and a
$\Omega = (U^L, \ldots , U^0) \in \mathcal{A}_h$
, let
\[\Theta \, :\!= \, \kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} \Omega = \bigl(\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^L, \ldots , \kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^0\bigr).\]
Then, for any
$\mathbf{x} \in \mathbb{R}^{d}$
, one can derive from the non-negative homogeneity of degree k of the activation functions that
\begin{align*} g_\Theta(\mathbf{x}) &= \kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^L {\mathbf{f}^{\, L}} \bigl( \cdots \kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^1 \mathbf{f}^1 \bigl(\kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^0 \mathbf{x}\bigr) \bigr) \\[3pt] &= \kappa^{{1}/{(k^L+k^{L-1}\cdots +1)}} U^L \mathbf{f}^{\, L} \bigl( \cdots \kappa^{{(k+1)}/{(k^L+k^{L-1}\cdots +1)}} U^1 \mathbf{f}^1 ( U^0 \mathbf{x}) \bigr) \\[3pt] &= \cdots \\[3pt] &= \kappa^{{(k^L+k^{L-1}\cdots +1)}/{(k^L+k^{L-1}\cdots +1)}} U^L \mathbf{f}^{\, L} ( \cdots U^1 \mathbf{f}^1 ( U^0 \mathbf{x}) )\\[3pt] & = \kappa g_{\Omega}(\mathbf{x}),\end{align*}
and the desired result follows.
A.2. Proof of Theorem 3.1
We first introduce some notations. Define the Frobenius norms of the parameter and weight matrices by
\[|\!|\!|\Theta|\!|\!|_F \, :\!= \, \sqrt{\sum_{l=0}^L \Vert W^l \Vert_F^2 } \quad\text{and}\quad \Vert W^l \Vert_F \, :\!= \, \sqrt{\sum_{k=1}^{p_{l+1}} \sum_{j=1}^{p_{l}} \bigl( W_{kj}^l \bigr)^2 }.\]
For any networks
$g_\Theta$
and
$g_\Gamma$
with
$\Theta, \Gamma \in\mathcal{A}$
, the prediction distance is defined as
\[ \Vert g_\Theta- g_\Gamma \Vert_n \, :\!= \, \sqrt{ \dfrac{1}{n}\sum_{i=1}^n(g_\Theta(\mathbf{x}_i)- g_\Gamma(\mathbf{x}_i) )^2 }, \]
and similarly
\[ \Vert g_\Theta \Vert_n \, :\!= \, \sqrt{ \dfrac{1}{n}\sum_{i=1}^n(g_\Theta(\mathbf{x}_i) )^2 }. \]
We divide the networks into inner and outer subnetworks and then obtain the locally Lipschitz property of neural networks on
$\mathcal{A}$
.
The inner subnetworks of a network
$g_\Theta \in \mathcal{G} \, :\!= \, \{ g_\Theta \colon \Theta \in\mathcal{A} \}$
are vector-valued functions defined by
\begin{align*}S_0 g_\Theta(\mathbf{x}) \, :\!= \, \mathbf{x} \quad \text{for all $\mathbf{x}\in\mathbb{R}^{d}$,}\end{align*}
and
\begin{align*}S_l g_\Theta(\mathbf{x}) \, :\!= \, \mathbf{f}^{\, l} (W^{l-1}\mathbf{f}^{\, l-1} ( \cdots W^1 \mathbf{f}^1(W^0 \mathbf{x})))\in\mathbb{R}^{p_l} \quad \text{for all $\mathbf{x}\in\mathbb{R}^{d}$,}\end{align*}
for
$l\in \{1,\ldots,L\}$
. Similarly, the outer subnetworks of
$g_\Theta$
are real-valued functions defined by
\begin{align*}S^l g_\Theta(\mathbf{z}) \, :\!= \, W^{L}\mathbf{f}^{L} ( \cdots W^l \mathbf{f}^{\, l}(W^{l-1} \mathbf{z}))\in\mathbb{R} \quad \text{for all $\mathbf{z}\in\mathbb{R}^{p_{l-1}}$,}\end{align*}
for
$l\in \{1,\ldots,L\}$
, and
\begin{align*}S^{L+1} g_\Theta(\mathbf{z}) \, :\!= \, W^{L}\mathbf{z}\in\mathbb{R} \quad \text{for all $\mathbf{z}\in\mathbb{R}^{p_{L}}$.}\end{align*}
The initial network can be split into an inner and outer network along every layer
$l\in \{1,\ldots, L+1\}$
:
\[g_\Theta(\mathbf{x})=S^l g_\Theta({S_{l-1}} g_\Theta(\mathbf{x})). \]
Since the locally Lipschitz property of neural networks is much more complicated than the global Lipschitz (
$k=1$
) case, we need to define some iterative sequences.
For any
$r\geq0$
and
$\Theta = (W^L,\ldots, W^0)\in\mathcal{A}$
, let
$c_{0}(r,\Theta)=r+ \Vert W^{0} \Vert^{k-1}_{F}r^{k}$
and
\[c_{l}(r,\Theta)=c_{l-1}(r,\Theta)+ M_k^{l(k-1)} \prod_{j=0}^{l} \Vert W^{j} \Vert^{k-1}_{F} c_{l-1}(r,\Theta)^k\quad \text{for $ 1\leq l\leq L$.}\]
Based on the above sequence, for any fixed
$l\in\{1,\ldots,L\}$
, we define
\begin{align*}\, \tilde{\kern-2pt c}_{j}(r,\Theta) &= 0 \quad\text{for $ 0\leq j< l$,}\\[3pt]\, \tilde{\kern-2pt c}_{l}(r,\Theta) &= r + \Vert W^{l} \Vert^{k-1}_{F}r^k, \\[3pt]\, \tilde{\kern-2pt c}_{j}(r,\Theta) &= \, \tilde{\kern-2pt c}_{j-1}(r,\Theta) + M_k^{(j-l)(k-1)} \prod_{q=l}^{j} \Vert W^{q} \Vert^{k-1}_{F} \, \tilde{\kern-2pt c}_{j-1}^k (r,\Theta) \quad\text{for $ l+1\leq j\leq L$.}\end{align*}
In addition, for any
$\Gamma = (V^L,\ldots, V^0)\in\mathcal{A}$
, we define
\begin{align*}d_l(r,\Theta,\Gamma)\, :\!= \, M_k^{l} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} \Vert W^{l-1} \Vert_{F} c_{l-2}(r,\Gamma) + M_k^{1+(l-1)k} \prod_{j=0}^{l-2} \Vert V^{j} \Vert^{k}_{F} \Vert W^{l-1} \Vert_{F}^{k}c_{l-2}^k(r,\Gamma),\end{align*}
where we set (note the unusual indexes of the product)
$\prod_{j=0}^{-1}b_{j} \, :\!= \, 1 $
for any sequence
$b_{j}$
.
According to the above definition, we first show an upper bound for the inner subnetworks and a Lipschitz property for the outer subnetworks.
Lemma A.1. Suppose that the activation functions
$\mathbf{f}^{\, l}\colon \mathbb{R}^{p_l}\rightarrow \mathbb{R}^{p_l}$
satisfy Assumption 3.1. Then it holds for every
$\mathbf{x}\in \mathbb{R}^{d}$
and
$\Theta = (W^L,\ldots, W^0)$
that
\begin{align*}|S_{l-1} g_\Theta(\mathbf{x})|\leq\Biggl(M_k^{l-1} \prod_{j=0}^{l-2} \Vert W^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Theta)\Biggr)\vee |\mathbf{x}|,\end{align*}
where
$a\vee b=\max\{a,b\}$
for any
$a,b\in\mathbb{R}$
.
Proof. Using the assumption that
$\mathbf{z} \mapsto \mathbf{f}^{\, l-1}(\mathbf{z})$
is locally Lipschitz, we get for every
$\Theta = (W^L,\ldots, W^0)$
and
$\mathbf{x} \in \mathbb{R}^{d}$
that
\begin{align*} \vert S_{l-1} g_\Theta(\mathbf{x}) \vert &= \vert \mathbf{f}^{\, l-1} \bigl(W^{l-2} S_{l-2} g_\Theta(\mathbf{x}) \bigr) \vert \\[3pt] &\leq M_k \big(1+ \vert W^{l-2} S_{l-2} g_\Theta(\mathbf{x}) \vert^{k-1} \big) \vert W^{l-2} S_{l-2} g_\Theta(\mathbf{x}) \vert \\[-30pt] \end{align*}
\begin{align*} &= M_k \vert W^{l-2} S_{l-2} g_\Theta(\mathbf{x}) \vert + M_k \vert W^{l-2} S_{l-2} g_\Theta(\mathbf{x}) \vert^{k} \\[3pt] &\leq M_k \Vert W^{l-2} \Vert_{F} \vert S_{l-2} g_\Theta(\mathbf{x}) \vert + M_k \Vert W^{l-2} \Vert^k_{F} \vert S_{l-2} g_\Theta(\mathbf{x}) \vert^{k}.\end{align*}
Then, when
$l=2$
,
\begin{align*} \vert S_{1} g_\Theta(\mathbf{x}) \vert&\leq M_k \Vert W^{0} \Vert_{F} \vert S_{0} g_\Theta(\mathbf{x}) \vert + M_k \Vert W^{0} \Vert^k_{F} \vert S_{0} g_\Theta(\mathbf{x}) \vert^{k}\\[3pt] &\leq M_k \Vert W^{0} \Vert_{F} \vert \mathbf{x} \vert + M_k \Vert W^{0} \Vert^k_{F} \vert \mathbf{x} \vert^{k}\\[3pt] &= M_k \Vert W^{0} \Vert_{F} \bigl(\vert \mathbf{x} \vert + \Vert W^{0} \Vert^{k-1}_{F} \vert \mathbf{x} \vert^{k}\bigr)\\[3pt] & = M_k \Vert W^{0} \Vert_{F} c_0(|\mathbf{x}|,\Theta),\end{align*}
when
$l=3$
,
\begin{align*} \vert S_{2} g_\Theta(\mathbf{x}) \vert&\leq M_k \Vert W^{1} \Vert_{F} \vert S_{1} g_\Theta(\mathbf{x}) \vert + M_k \Vert W^{1} \Vert^k_{F} \vert S_{1} g_\Theta(\mathbf{x}) \vert^{k}\\[3pt] &\leq M_k \Vert W^{1} \Vert_{F}M_k \Vert W^{0} \Vert_{F} c_0(|\mathbf{x}|,\Theta) + M_k \Vert W^{1} \Vert^k_{F} M_k^k {c_0(|\mathbf{x}|,\Theta)^k} \Vert W^{0} \Vert^{k}_{F}\\[3pt] &= M_k^2 \Vert W^{1} \Vert_{F} \Vert W^{0} \Vert_{F} \bigl( c_0(|\mathbf{x}|,\Theta) + M_k^{k-1} \Vert W^{1} \Vert^{k-1}_{F} \Vert W^{0} \Vert^{k-1}_{F} c_0(|\mathbf{x}|,\Theta)^k \bigr)\\[3pt] &= M_k^2 \Vert W^{1} \Vert_{F} \Vert W^{0} \Vert_{F}c_1(|\mathbf{x}|,\Theta).\end{align*}
Inductively, for any
$l\geq 2$
,
\[ \vert S_{l-1} g_\Theta(\mathbf{x}) \vert \leq M_k^{l-1} \prod_{j=0}^{l-2} \Vert W^{j} \Vert_{F}c_{l-2}(|\mathbf{x}|,\Theta).\]
In addition, notice that
$ \vert S_{0} g_\Theta(\mathbf{x}) \vert=\vert \mathbf{x} \vert$
, so one can verify readily that
$\mathbf{x} \mapsto S_{l-1} g_\Theta(\mathbf{x})$
and
$\mathbf{x} \mapsto S_{0} g_\Theta(\mathbf{x})$
are bounded by
\[M_k^{l-1} \prod_{j=0}^{l-2} \Vert W^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Theta) \quad\text{and}\quad |\mathbf{x}|,\]
respectively.
Lemma A.2. Assume that the activation functions
$\mathbf{f}^{\, l}\colon \mathbb{R}^{p_l}\rightarrow \mathbb{R}^{p_l}$
satisfy Assumption 3.1. Then it holds for every
$\mathbf{x}\in \mathbb{R}^{d}$
and
$\Theta = (W^L,\ldots, W^0)$
that
\begin{align} &\vert S^{l+1} g_\Theta(\mathbf{z}_1)- S^{l+1} g_\Theta(\mathbf{z}_2) \vert \nonumber\\[3pt] &\quad \leq M_k^{L-l} \vert \mathbf{z}_1-\mathbf{z}_2 \vert \bigl( 1+ \Vert W^{l} \Vert^{k-1}_{F} \vert \mathbf{z}_1\vert^{k-1} + \Vert W^{l} \Vert^{k-1}_{F} \vert \mathbf{z}_2\vert^{k-1} \bigr) \Vert W^{l+1} \Vert_{F}\Vert W^{l} \Vert_{F} \nonumber\\[3pt] &\quad\quad \times \prod_{j=l+1}^{L-1}\Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} ( \, \tilde{\kern-2pt c}_{j-1}(|\mathbf{z}_1|,\Theta)+ \, \tilde{\kern-2pt c}_{j-1}(|\mathbf{z}_2|,\Theta)) \Biggr) \Vert W^{j+1} \Vert_{F}.\end{align}
Proof. For every
$\mathbf{z}_1,\mathbf{z}_2 \in \mathbb{R}^{p_l}$
and
$l\in \{0,\ldots,L\}$
, we have
\begin{align*} &\vert S^{l+1} g_\Theta(\mathbf{z}_1)- S^{l+1} g_\Theta(\mathbf{z}_2) \vert \\[3pt] &\quad = \bigl\vert W^{L}\mathbf{f}^{L} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_1\big)\bigr) -W^{L}\mathbf{f}^{L} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_2\big)\bigr) \bigr\vert \\[3pt] &\quad \leq \Vert W^{L} \Vert_{F} \bigl\vert \mathbf{f}^{L} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_1\big)\bigr) - \mathbf{f}^{L} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_2\big)\bigr)\bigr\vert.\end{align*}
Then Assumption 3.1 implies that
\begin{align*} &\vert S^{l+1} g_\Theta(\mathbf{z}_1)- S^{l+1} g_\Theta(\mathbf{z}_2) \vert \\[3pt] &\quad \leq \Vert W^{L} \Vert_{F} M_k \bigl\vert W^{L-1}\mathbf{f}^{L-1} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_1\big)\bigr)- W^{L-1}\mathbf{f}^{L-1} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_2\big)\bigr)\bigr\vert\\[3pt] &\quad\quad \times \bigl( 1+ \bigl\vert W^{L-1}\mathbf{f}^{L-1} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_1\big)\bigr)\bigr\vert^{k-1}+ \bigl\vert W^{L-1}\mathbf{f}^{L-1} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_2\big)\bigr)\bigr\vert^{k-1} \bigr).\end{align*}
Hence it can be inferred by induction that
\begin{align*} &\vert S^{l+1} g_\Theta(\mathbf{z}_1)- S^{l+1} g_\Theta(\mathbf{z}_2) \vert \\[3pt] &\quad \leq M_k^{L-l} \vert \mathbf{z}_1-\mathbf{z}_2 \vert\bigl( 1+ \vert W^{l} \mathbf{z}_1 \vert^{k-1} + \vert W^{l} \mathbf{z}_2 \vert^{k-1} \bigr) \Vert W^{l+1} \Vert_{F}\Vert W^{l} \Vert_{F} \\[3pt] &\quad \quad \times \prod_{j=l+1}^{L-1}\bigl( 1+ \bigl\vert W^{j}\mathbf{f}^{\, j} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_1\big)\bigr)\bigr\vert^{k-1}+ \bigl\vert W^{j}\mathbf{f}^{\, j} \bigl( \cdots W^{l+1} \mathbf{f}^{\, l+1}\big(W^{l} \mathbf{z}_2\big)\bigr)\bigr\vert^{k-1} \bigr) \Vert W^{j+1} \Vert_{F}.\end{align*}
Then we need to bound
$ \vert \mathbf{f}^{\, j} (\! \cdots W^{l+1} \mathbf{f}^{\, l+1}(W^{l} \mathbf{z})) \vert $
for any
$l+1\leq j \leq L-1$
. Similar to the proof of Lemma A.1, we have
\[ \vert \mathbf{f}^{\, j} ( \cdots W^{l+1} \mathbf{f}^{\, l+1}(W^{l} \mathbf{z})) \vert\leq M_k^{j-l} \prod_{q=l}^{j-1} \Vert W^{q} \Vert_{F} \, \tilde{\kern-2pt c}_{j-1}(|\mathbf{z}|,\Theta).\]
Hence we obtain
\begin{align*}\bigl\vert W^{j} \mathbf{f}^{\, j} ( \cdots W^{l+1} \mathbf{f}^{\, l+1}(W^{l} \mathbf{z})) \bigr\vert\leq M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} \, \tilde{\kern-2pt c}_{j-1}(|\mathbf{z}|,\Theta)\quad\text{for any $ l+1 \leq j \leq L-1$,}\end{align*}
and the desired result follows.
Now we define
\begin{align} & B_{1}(r,\Theta,\Gamma)\nonumber\\[3pt] & = \max_{l\in \{1,\ldots,L+1\}} \Biggl\{ \Biggl( 1+ \Vert W^{l} \Vert^{k-1}_{F}{{ d_l(r,\Theta,\Gamma)} }^{k-1}+ \Vert W^{l} \Vert^{k-1}_{F}{{ \prod_{j=0}^{l-1} \Vert V^{j} \Vert^{k-1}_{F} c_{l-1}^{k-1}(r,\Gamma) } } \Biggr) c_{l-2}(r,\Gamma) \nonumber\\[3pt] & \times \Biggl( 1 + \bigl(\Vert W^{l-1} \Vert^{k-1}_{F}+\Vert V^{l-1} \Vert^{k-1}_{F}\bigr)M_k^{(l-1)(k-1)} \prod_{q=0}^{l-2} \Vert V^{q} \Vert^{k-1}_{F} c_{l-2}^{k-1}(r,\Gamma) \Biggr) \nonumber\\[3pt] & \times\prod^L_{\substack{ j=0\\[3pt] j\neq l-1 } } \Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} \Biggl({ \, \tilde{\kern-2pt c}_{j-1} ( d_l(r,\Theta,\Gamma), \Theta) }+{ \, \tilde{\kern-2pt c}_{j-1} \Biggl( M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F} c_{l-1}(r,\Gamma), \Theta\Biggr) } \Biggr) \Biggr)\nonumber \\[3pt] & \times ( \Vert W^{j} \Vert_{F} \vee \Vert V^{j} \Vert_{F} ) \Biggr\} ,\end{align}
and give the following locally Lipschitz property of neural networks.
Lemma A.3. Assume that the activation functions
$\mathbf{f}^{\, l}\colon \mathbb{R}^{p_l}\rightarrow \mathbb{R}^{p_l}$
satisfy Assumption 3.1. Then it holds for every
$\mathbf{x}\in \mathbb{R}^{d}$
and
$\Theta = (W^L,\ldots, W^0)$
,
$\Gamma = (V^L,\ldots, V^0)\in\mathcal{A}$
that
\[ \vert g_\Theta(\mathbf{x})-g_\Gamma(\mathbf{x}) \vert \leq 2 M_k^L \sqrt{L} B_{1}(|\mathbf{x}|,\Theta,\Gamma) |\!|\!|\Theta-\Gamma|\!|\!|_F.\]
Similarly, it holds that
\[ \Vert g_\Theta -g_\Gamma \Vert_n \leq 2 M_k^L \sqrt{L} \sqrt{ \dfrac{1}{n}\sum_{i=1}^n (B_{1}(|\mathbf{x}_i|,\Theta,\Gamma))^2 } |\!|\!|\Theta-\Gamma|\!|\!|_F. \]
Proof. We consider two networks
$g_\Theta$
and
$g_\Gamma$
with parameters
$\Theta=(W^L,\ldots,W^0)\in \mathcal{A}$
and
$\Gamma=(V^L,\ldots,V^0)\in \mathcal{A}$
, respectively. Then, similar to the proof of Proposition 6 in [Reference Taheri, Xie and Lederer38], we have
\begin{align*}\vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert&\leq \sum_{l=1}^{L} \bigl\vert \bigl( S^{l+1} g_\Theta\bigl( \mathbf{f}^{\, l} \bigl( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \bigr) - S^{l+1} g_\Theta \bigl( \mathbf{f}^{\, l} \bigl( V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \bigr) \bigr) \bigr\vert \\[3pt] &\quad + \vert ( W^L- V^L) S_{L} g_\Gamma(\mathbf{x}) \vert .\end{align*}
\begin{align*}& \vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert \\[3pt] & \leq \sum_{l=1}^{L} M_k^{L-l}\Biggl( 1+ \Vert W^{l} \Vert^{k-1}_{F}{\underbrace{ \vert \mathbf{f}^{l} ( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )\vert }_{\unicode{x2460}} }^{k-1}+ \Vert W^{l} \Vert^{k-1}_{F}{\underbrace{ \vert \mathbf{f}^{l} ( V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )\vert }_{\unicode{x2461}} }^{k-1} \Biggr)\\[3pt] & \times \prod_{j=l+1}^{L-1} \Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} \Biggl(\underbrace{ \tilde{c}_{j-1} (|\mathbf{f}^{l} ( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )|,\Theta) }_{\unicode{x2462}}+\underbrace{ \tilde{c}_{j-1} ( |\mathbf{f}^{l} ( V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )|,\Gamma) }_{\unicode{x2463}} \Biggr) \Biggr)\\[3pt] & \times \Vert W^{j+1} \Vert_{F}\Vert W^{l+1} \Vert_{F} \Vert W^{l} \Vert_{F} \\[3pt] & \times M_k \Biggl( 1 +{\underbrace{ \vert W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \vert }_{\unicode{x2464}} }^{k-1}+{\underbrace{ \vert V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \vert }_{\unicode{x2465}} }^{k-1}\Biggr)\Vert W^{l-1}- V^{l-1} \Vert_{F}\underbrace{ \vert S_{l-1} g_\Gamma(\mathbf{x}) \vert }_{\unicode{x2466}} \\[3pt] & + \Vert ( W^L- V^L) \Vert\underbrace{ \vert S_{L} g_\Gamma(\mathbf{x}) \vert }_{\unicode{x2467}} .\end{align*}
Then we need to bound the above eight terms. For terms
$\unicode{x2460}$
and
$\unicode{x2461}$
, similar to the proof of Lemma A.1, one can write, by (3.1),
\begin{align*} &\vert \mathbf{f}^{\, l} ( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )\vert\\[3pt] &\quad = \vert \mathbf{f}^{\, l} ( W^{l-1} \mathbf{f}^{\, l-1} ( V^{l-2} \mathbf{f}^{\, l-2} (\! \cdots V^{1} \mathbf{f}^{1} (V^0 \mathbf{x}) ) ) )\vert \\[3pt] &\quad \leq M_k^{l} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} \Vert W^{l-1} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma) + M_k^{1+(l-1)k} \prod_{j=0}^{l-2} \Vert V^{j} \Vert^{k}_{F} \Vert W^{l-1} \Vert_{F}^{k}c_{l-2}^k(|\mathbf{x}|,\Gamma)\\[3pt] &\quad = d_l(|\mathbf{x}|,\Theta,\Gamma)\end{align*}
and
\begin{align*} \vert \mathbf{f}^{\, l} ( V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )\vert&= \vert S_{l} g_\Gamma(\mathbf{x}) \vert\leq M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F} c_{l-1}(|\mathbf{x}|,\Gamma).\end{align*}
For terms
$\unicode{x2462}$
and
$\unicode{x2463}$
, according to the definition of
$\, \tilde{\kern-2pt c}_j(|\mathbf{z}|,\Theta)$
, we know the function is increasing in
$\vert \mathbf{z} \vert$
, so we only need to bound
$ \vert \mathbf{f}^{\, l} ( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) ) \vert $
. One can derive from terms
$\unicode{x2460}$
and
$\unicode{x2461}$
that
\begin{align*}\, \tilde{\kern-2pt c}_{j-1} ( |\mathbf{f}^{\, l} ( W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )|,\Theta )\leq & \, \tilde{\kern-2pt c}_{j-1} ( d_l(|\mathbf{x}|,\Theta,\Gamma), \Theta)\end{align*}
and
\begin{align*}\, \tilde{\kern-2pt c}_{j-1} ( |\mathbf{f}^{\, l} ( V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) )|,\Theta )\leq & \, \tilde{\kern-2pt c}_{j-1} \Biggl( M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F} c_{l-1}(|\mathbf{x}|,\Gamma), \Theta \Biggr).\end{align*}
For the last four terms, it is easy to imply from Lemmas A.1 and A.2 that
\begin{align*} \vert W^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \vert& \leq \Vert W^{l-1} \Vert_{F} \vert S_{l-1} g_\Gamma(\mathbf{x}) \vert\leq \Vert W^{l-1} \Vert_{F} M_k^{l-1} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma),\\[2pt] \vert V^{l-1} S_{l-1} g_\Gamma(\mathbf{x}) \vert& \leq M_k^{l-1} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma),\\[2pt] \vert S_{l-1} g_\Gamma(\mathbf{x}) \vert& \leq M_k^{l-1} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma),\\[2pt] \vert S_{L} g_\Gamma(\mathbf{x}) \vert& \leq M_k^{L} \prod_{j=0}^{L-1} \Vert V^{j} \Vert_{F}c_{L-1}(|\mathbf{x}|,\Gamma).\end{align*}
Therefore we have
\begin{align*}& \vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert \\[3pt] & \leq M_k^{L} \sum_{l=1}^{L} \Biggl( 1+ \Vert W^{l} \Vert^{k-1}_{F}d_l(|\mathbf{x}|,\Theta,\Gamma)^{k-1}+ \Vert W^{l} \Vert^{k-1}_{F} M_k^{l(k-1)} \prod_{j=0}^{l-1} \Vert V^{j} \Vert^{k-1}_{F} c_{l-1}^{k-1}(|\mathbf{x}|,\Gamma) \Biggr) \Vert W^{l+1} \Vert_{F} \\[2pt] & \times \prod_{j=l+1}^{L-1} \Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} \Biggl( \, \tilde{\kern-2pt c}_{j-1}( d_l(|\mathbf{x}|,\Theta,\Gamma),\Theta)+ \, \tilde{\kern-2pt c}_{j-1} \Biggl( M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert c_{l-1}(|\mathbf{x}|,\Gamma), \Theta \Biggr) \Biggr) \Biggr) \\[2pt] & \times \Vert W^{j+1} \Vert_{F} \Vert W^{l} \Vert_{F}\Biggl( 1 + (\Vert W^{l-1} \Vert^{k-1}_{F}+\Vert V^{l-1} \Vert^{k-1}_{F})M_k^{(l-1)(k-1)} \prod_{q=0}^{l-2} \Vert V^{q} \Vert^{k-1}_{F} c_{l-2}^{k-1}(|\mathbf{x}|,\Gamma) \Biggr) \\[2pt] & \times \Vert W^{l-1}- V^{l-1} \Vert_{F} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma) + \Vert ( W^L- V^L) \Vert_{F} M_k^{L} \prod_{j=0}^{L-1} \Vert V^{j} \Vert_{F} c_{L-1}(|\mathbf{x}|,\Gamma).\end{align*}
Then we obtain
\begin{align*}& \vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert \\[2pt] & \leq M_k^{L} \sum_{l=1}^{L} \Biggl( 1+ \Vert W^{l} \Vert^{k-1}_{F}{{ d_l(|\mathbf{x}|,\Theta,\Gamma)} }^{k-1}+ \Vert W^{l} \Vert^{k-1}_{F}{{ \prod_{j=0}^{l-1} \Vert V^{j} \Vert^{k-1}_{F} c_{l-1}^{k-1}(|\mathbf{x}|,\Gamma) } } \Biggr) c_{l-2}(|\mathbf{x}|,\Gamma) \\[2pt] &\quad \times \Biggl( 1 + (\Vert W^{l-1} \Vert^{k-1}_{F}+\Vert V^{l-1} \Vert^{k-1}_{F})M_k^{(l-1)(k-1)} \prod_{q=0}^{l-2} \Vert V^{q} \Vert^{k-1}_{F} c_{l-2}^{k-1}(|\mathbf{x}|,\Gamma) \Biggr) \\[-20pt] \end{align*}
\begin{align*} & \times\prod^L_{\substack{ j =0 \\[3pt] j\neq l-1 } } \Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F}\Biggl({ \, \tilde{\kern-2pt c}_{j-1} ( d_l(|\mathbf{x}|,\Theta,\Gamma), \Theta) }+{ \, \tilde{\kern-2pt c}_{j-1} \Biggl( M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F}c_{l-1}(|\mathbf{x}|,\Gamma), \Theta\Biggr) } \Biggr) \Biggr) \\[3pt] & \times ( \Vert W^{j} \Vert_{F} \vee \Vert V^{j} \Vert_{F} ) \times \Vert W^{l-1}- V^{l-1} \Vert_{F}+ M_k^{L} c_{L-1}(|\mathbf{x}|,\Gamma) \prod_{j=0}^{L-1} ( \Vert W^{j} \Vert_{F}\vee \Vert V^{j} \Vert_{F} ) \Vert W^{L}- V^{L} \Vert_{F}.\end{align*}
Furthermore, recall (A.2).Then, consolidating and rearranging yields
\begin{align*}& \vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert \\[3pt] & \leq M_k^{L} \sum_{l=1}^{L+1} \Biggl( 1+ \Vert W^{l} \Vert^{k-1}_{F}{{ d_l(|\mathbf{x}|,\Theta,\Gamma)} }^{k-1}+ \Vert W^{l} \Vert^{k-1}_{F}{{ \prod_{j=0}^{l-1} \Vert V^{j} \Vert^{k-1}_{F} c_{l-1}^{k-1}(|\mathbf{x}|,\Gamma) } } \Biggr) c_{l-2}(|\mathbf{x}|,\Gamma) \\[3pt] & \times \Biggl( 1 + \big(\Vert W^{l-1} \Vert^{k-1}_{F}+\Vert V^{l-1} \Vert^{k-1}_{F}\big)M_k^{(l-1)(k-1)} \prod_{q=0}^{l-2} \Vert V^{q} \Vert^{k-1}_{F} c_{l-2}^{k-1}(|\mathbf{x}|,\Gamma) \Biggr) \\[3pt] & \times\prod^L_{\substack{ j=0 \\[3pt] j\neq l-1 } } \Biggl( 1+ M_k^{j-l} \prod_{q=l}^{j} \Vert W^{q} \Vert_{F} \Biggl({ \, \tilde{\kern-2pt c}_{j-1} ( d_l(|\mathbf{x}|,\Theta,\Gamma), \Theta) }+{ \, \tilde{\kern-2pt c}_{j-1} \Biggl( M_k^{l} \prod_{j=0}^{l-1} \Vert V^{j} \Vert_{F}c_{l-1}(|\mathbf{x}|,\Gamma), \Theta\Biggr) } \Biggr) \Biggr) \\[3pt] & \times ( \Vert W^{j} \Vert_{F}\vee\Vert V^{j} \Vert_{F} ) \times \Vert W^{l-1}- V^{l-1} \Vert_{F}\\[3pt] & \leq M_k^{L}B_{1}(|\mathbf{x}|,\Theta,\Gamma) \sum_{m=0}^{L} \Vert W^{m}- V^{m} \Vert_{F}.\end{align*}
For the last sum in the above bound, similar to the proof of Proposition 6 in [Reference Taheri, Xie and Lederer38], we obtain
\begin{align*}\sum_{m=0}^{L} \Vert W^{m}- V^{m} \Vert_{F} \leq 2 \sqrt{L} |\!|\!|\Theta-\Gamma|\!|\!|_2 \leq 2 \sqrt{L} |\!|\!|\Theta-\Gamma|\!|\!|_F.\end{align*}
Combining all of the above, we have
\begin{align*}\vert g_\Theta(\mathbf{x})- g_\Gamma(\mathbf{x}) \vert&\leq 2 \sqrt{L} M_k^{L} B_{1}(|\mathbf{x}|,\Theta,\Gamma) |\!|\!|\Theta-\Gamma|\!|\!|_F,\end{align*}
and the first claim is proved. The second claim then follows readily:
\begin{align*} \Vert g_\Theta - g_\Gamma \Vert_n&= \sqrt{ \dfrac{1}{n}\sum_{i=1}^{n} ( g_\Theta(\mathbf{x}_i)- g_\Gamma(\mathbf{x}_i) )^2 }\\[3pt] &\leq \sqrt{ \dfrac{1}{n}\sum_{i=1}^{n} ( 2 \sqrt{L} M_k^{L} B_{1}(|\mathbf{x}_i|,\Theta,\Gamma) )^2 } |\!|\!|\Theta-\Gamma|\!|\!|_F \\[3pt] &= 2 \sqrt{L} M_k^{L} \sqrt{ \dfrac{1}{n}\sum_{i=1}^{n} ( B_{1}(|\mathbf{x}_i|,\Theta,\Gamma) )^2 } |\!|\!|\Theta-\Gamma|\!|\!|_F . \\[-40pt] \end{align*}
Now we give the following Lipschitz property and boundary on
$\mathcal{A}_{\beta}$
.
Lemma A.4. Assume that the activation functions
$\mathbf{f}^{\, l}\colon \mathbb{R}^{p_l}\rightarrow \mathbb{R}^{p_l}$
satisfy Assumption 3.1. Then it holds for every
$\mathbf{x}\in \mathbb{R}^{d}$
and
$\Theta = (W^L,\ldots, W^0)$
,
$\Gamma = (V^L,\ldots, V^0)\in\mathcal{A}_{\beta}$
that
\begin{align*} \Vert g_\Theta - g_\Gamma \Vert_n\leq2 M_k^L \sqrt{L} \sqrt{ \dfrac{1}{n}\sum_{i=1}^n (B(|\mathbf{x}_i|))^2 } |\!|\!|\Theta-\Gamma|\!|\!|_F\end{align*}
and
\begin{align*} \Vert g_\Theta \Vert_n\leq 2 M_k^{L}\sqrt{L} \sqrt{ \dfrac{1}{n}\sum_{i=1}^{n} (B(\mathbf{x}_i))^2}.\end{align*}
Proof. The proof follows from Lemma A.3 and we need to bound
$B_{1}(|\mathbf{x}|,\Theta,\Gamma)$
in Lemma A.3 in the case
$h(\Theta)\leq 1$
and
$h(\Gamma)\leq 1$
. Recalling (A.2), we have
\begin{align}&B_{1}(|\mathbf{x}|,\Theta,\Gamma)\\[3pt] &\quad \leq M_k^{2} \max_{l\in \{1,\ldots,L+1\}}\bigl\{ \bigl( 1+ d_l(|\mathbf{x}|,\Theta,\Gamma)^{k-1} + c_{l-1}(|\mathbf{x}|,\Gamma)^{k-1}\bigr) c_{l-2}(|\mathbf{x}|,\Gamma) \nonumber\\[3pt] &\quad\quad \times \bigl( 1+2 M_k^{(l-1)(k-1)} c_{l-2}(|\mathbf{x}|,\Gamma)^{k-1} \bigr) \bigr\} \max_{l\in \{1,\ldots,L+1\}}\left\{\prod^L_{\substack{ j=0 \\ j\neq l-1 } } \Vert W^{j} \Vert_{F} \vee \Vert V^{j} \Vert_{F}\right\} \nonumber\\[3pt] &\quad\quad \times \max_{l\in \{1,\ldots,L+1\}}\left\{\prod^L_{\substack{ j=0 \\ j\neq l-1 } } \bigl( 1+ M_k^{j-l} \bigl(\, \tilde{\kern-2pt c}_{j-1}(d_l(|\mathbf{x}|,\Theta,\Gamma),\Theta) + \, \tilde{\kern-2pt c}_{j-1}\big( M_k^{l} {c}_{l-1}(|\mathbf{x}|,\Gamma),\Theta\big) \bigr) \bigr) \right\}\nonumber\\[3pt] &\quad \, :\!= \, \mathcal{K}_{1}+\mathcal{K}_{2},\nonumber\end{align}
so we need to bound the three sequences
$c_{l}(|\mathbf{x}|,\Gamma)$
,
$d_l(|\mathbf{x}|,\Theta,\Gamma)$
and
$\, \tilde{\kern-2pt c}_{j-1}(u,\Theta)$
appearing in the above inequality.
We first derive the upper bound of the sequence
$c_{l}(|\mathbf{x}|,\Gamma)$
. For any
$l\geq1$
, by the inequality of the arithmetic and geometric means, we have
\begin{align*}c_l(|\mathbf{x}|,\Gamma) &= c_{l-1}(|\mathbf{x}|,\Gamma) + M_k^{l(k-1)} \prod_{j=0}^{l} \Vert V^{j} \Vert_{F}^{k-1} c_{l-1}(|\mathbf{x}|,\Gamma)^k \\[3pt] &\leq c_{l-1}(|\mathbf{x}|,\Gamma) + M_k^{l(k-1)} \Biggl( \dfrac{1}{l+1}\sum_{j=0}^{l} \Vert V^{j} \Vert_{F}^{2} \Biggr)^{{{(l+1)(k-1)}/{2}}} c_{l-1}(|\mathbf{x}|,\Gamma)^k \\[3pt] &\leq c_{l-1}(|\mathbf{x}|,\Gamma) + M_k^{l(k-1)} (l+1)^{-{{(l+1)(k-1)}/{2}}} c_{l-1}(|\mathbf{x}|,\Gamma)^k \\[3pt] &\leq c_{l-1}(|\mathbf{x}|,\Gamma) + \biggl( \dfrac{M_k}{2} \biggr)^{l(k-1)} c_{l-1}(|\mathbf{x}|,\Gamma)^k.\end{align*}
Then
\begin{align*}c_0(|\mathbf{x}|,\Gamma)&= |\mathbf{x}| + \Vert V^{0} \Vert_{F}^{k-1}|\mathbf{x}|^{k}\leq |\mathbf{x}| + |\mathbf{x}|^{k},\\[3pt]c_1(|\mathbf{x}|,\Gamma) &= c_{0}(|\mathbf{x}|,\Gamma) + \biggl( \dfrac{M_k}{2} \biggr)^{k-1} c_{0}(|\mathbf{x}|,\Gamma)^k \\[3pt]&\leq |\mathbf{x}| + |\mathbf{x}|^{k} + \biggl( \dfrac{M_k}{2} \biggr)^{k-1} (|\mathbf{x}| +|\mathbf{x}|^{k})^k \\[3pt]&\leq |\mathbf{x}| + |\mathbf{x}|^{k} + \biggl( \dfrac{M_k}{2} \biggr)^{k-1} 2^{k-1}\big(|\mathbf{x}| +|\mathbf{x}|^{k^{2}}\big) \\[3pt]&=|\mathbf{x}| + |\mathbf{x}|^{k} + {M_k}^{k-1}\big(|\mathbf{x}| +|\mathbf{x}|^{k^{2}}\big) \\[3pt] &\leq 2\bigl(1+{M_k}^{k-1}\bigr) \big(\vert \mathbf{x} \vert +\vert\mathbf{x}\vert^{k^{2}}\big).\end{align*}
By the method of induction, we have
\begin{align*}c_l(|\mathbf{x}|,\Gamma)&\leq 2\bigl(1+M_k^{k-1}\bigr)^{k^l+2k^{l-1}+\cdots+lk+l+1} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{l+1}}\bigr) .\end{align*}
Hence, for any
$0\leq m\leq L+1$
,
\begin{align}\max_{l\in \{1,\ldots,L+1\}} c_{l-m}(|\mathbf{x}|,\Gamma)&\leq 2\bigl(1+M_k^{k-1}\bigr)^{k^{L+1-m}+2k^{L-m}+\cdots+(L+1-m)k+{L+2-m}} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+2-m}}\bigr)\nonumber \\[3pt] & \, :\!= \, I_1(m) \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+2-m}}\bigr) .\end{align}
Next we bound
$d_l(|\mathbf{x}|,\Theta,\Gamma)$
. By (A.4), we have
\begin{align*}& d_l(|\mathbf{x}|,\Theta,\Gamma) \\[3pt] & \quad = M_k^{l} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} \Vert W^{l-1} \Vert_{F} c_{l-2}(|\mathbf{x}|,\Gamma) + M_k^{1+(l-1)k} \prod_{j=0}^{l-2} \Vert V^{j} \Vert^{k}_{F} \Vert W^{l-1} \Vert_{F}^{k}c_{l-2}^k(|\mathbf{x}|,\Gamma) \\[3pt] & \quad\leq M_k^{l} \prod_{j=0}^{l-2} \Vert V^{j} \Vert_{F} \Vert W^{l-1} \Vert_{F} I_1(2) \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}}\bigr) \\[3pt] & \quad \quad + M_k^{1+(l-1)k} \prod_{j=0}^{l-2} \Vert V^{j} \Vert^{k}_{F} \Vert W^{l-1} \Vert_{F}^{k}I_1(2)^{k} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}}\bigr)^k.\end{align*}
Since
$\Theta,\Gamma\in\mathcal{A}_{\beta}$
, we have
$\Vert V^{j} \Vert_{F}\leq 1$
and
$\Vert W^{l-1} \Vert_{F}\leq 1$
, so that
\begin{align}d_l(|\mathbf{x}|,\Theta,\Gamma)&\leq M_k^{l} \bigl(I_1(2) \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}}\bigr) + M_k^{(l-1)(k-1)} I_1(2)^k 2^{k-1} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}}\bigr) \bigr) \nonumber \\[3pt] &\leq M_k^{l} I_1(2) \bigl( 2+ M_k^{(l-1)(k-1)} I_1(2)^{k-1} 2^{k-1} \bigr) \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}}\bigr)\nonumber \\[3pt] &\leq M_k^{L+1} I_1(2) \bigl( 2+ M_k^{L(k-1)} I_1(2)^{k-1} 2^{k-1} \bigr) \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}}\bigr)\nonumber \\[3pt] &\, :\!= \, I_{k,L} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}}\bigr) .\end{align}
Denoting
$d_l(|\mathbf{x}|,\Theta,\Gamma)\, :\!= \, u$
, for
$\, \tilde{\kern-2pt c}_{j-1}(u,\Theta)$
, we have
\begin{align*}\, \tilde{\kern-2pt c}_{l}(u,\Theta)=u+ \Vert W^{l} \Vert^{k-1}_{F} u^k \leq u+u^k,\end{align*}
and, for any
$j\geq l+2$
, the inequality of the arithmetic and geometric means implies that
\begin{align*}\, \tilde{\kern-2pt c}_{j-1}(u,\Theta)&= \, \tilde{\kern-2pt c}_{j-2}(u,\Theta) + M_k^{(j-1-l)(k-1)} \prod_{q=l}^{j-1} \Vert W^{q} \Vert^{k-1} \, \tilde{\kern-2pt c}_{j-2}^k(u,\Theta) \\[3pt] &\leq \, \tilde{\kern-2pt c}_{j-2}(u,\Theta) + \biggl(\dfrac{M_k}{2}\biggr)^{(j-1-l)(k-1)} \, \tilde{\kern-2pt c}_{j-2}(u,\Theta)^{k} ,\end{align*}
which implies from (A.4) that
\begin{align}\, \tilde{\kern-2pt c}_{j-1}(u,\Theta)&\leq I_1(l+1)\bigl(u+u^{k^{L+1-l}}\bigr) .\end{align}
Hence one can derive from (A.4) and (A.5) that
\begin{align*}\mathcal{K}_{1}&\leq M_k^{2} \bigl(1 + I_{k,L}^{k-1}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}} \bigr)^{k-1} + I_1(1)^{k-1}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}} \bigr)^{k-1} \bigr)I_1(2)\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr) \\[3pt] &\quad \times\bigl( 1+2 M_k^{L(k-1)} I_1(2)^{k-1} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr)^{k-1}\bigr) \max_{l\in \{1,\ldots,L+1\}}\left\{\prod^L_{\substack{ j= 0 \\ j\neq l-1 } } \Vert W^{j} \Vert_{F}\vee\Vert V^{j} \Vert_{F}\right\}\!,\end{align*}
whereas by (A.3), (A.4), (A.5), and (A.6),
\begin{align*}\mathcal{K}_{2}&\leq \max_{l\in \{1,\ldots,L\}}\bigl\{1+2M_{k}^{L-l}I_{1}(l+1)\bigl(I_{k,L}+M_{k}^{l}I_{1}(1)+2^{L-l}\big(I_{k,L}^{L+1-l}+M_{k}^{l(L+1-l)}I_{1}(1)^{L+1-l}\bigr)\bigr) \\[3pt] & \quad\times \bigl(|\mathbf{x}|+|\mathbf{x}|^{(L+1-l)k^{L+1}}\bigr)\bigr\}^{L-l+1}\\[3pt] &\leq \max_{l\in \{1,\ldots,L\}}\bigl\{1+4M_{k}^{L-1}I_{1}(l+1)\bigl(I_{k,L}+M_{k}^{L}I_{1}(1)+2^{L-1}\bigl(I_{k,L}^{L}+M_{k}^{L^{2}}I_{1}(1)^{L}\bigr)\bigr) \\[3pt] & \quad\times\bigl(|\mathbf{x}|+|\mathbf{x}|^{Lk^{L+1}}\bigr)\bigr\}^{L}.\end{align*}
Notice that for any positive integer r, we have
\[k^{r}+2k^{r-1}+\cdots+rk+r+1\leq\dfrac{k^{r+2}}{(k-1)^{2}}.\]
We therefore have
\begin{align}I_{1}(m)\leq2\bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+3-m}}{(k-1)^{2}}},\end{align}
and by the inequality of the arithmetic and geometric means,
\begin{align*}\max_{l\in \{1,\ldots,L+1\}}\left\{\prod^L_{\substack{ j= 0 \\ j\neq l-1 } } \Vert W^{j} \Vert_{F}\vee\Vert V^{j} \Vert_{F}\right\} & \leq \max_{l\in \{1,\ldots,L+1\}}\Biggl\{\dfrac{1}{L}\sum_{j=0,j\neq l}^{L}\Vert W^{j} \Vert_{F}^{2}\vee\Vert V^{j} \Vert_{F}^{2}\Biggr\}^{{{L}/{2}}}\\[3pt] & \leq \Biggl(\dfrac{1}{L}\sum_{j=0}^{L}\Vert W^{j} \Vert_{F}^{2}\vee\Vert V^{j} \Vert_{F}^{2}\Biggr)^{{{L}/{2}}}\end{align*}
\begin{align*}& \leq \Biggl(\dfrac{1}{L}\sum_{j=0}^{L} \bigl(\Vert W^{j} \Vert_{F}^{2}+\Vert V^{j} \Vert_{F}^{2} \bigr)\Biggr)^{{{L}/{2}}}\\[3pt] & \leq \biggl(\dfrac{2}{L}\biggr)^{{{L}/{2}}}.\end{align*}
These imply
\begin{align*}\mathcal{K}_{1}&\leq 2 M_k^{2}\biggl(\dfrac{2}{L}\biggr)^{{{L}/{2}}} \Bigl(1 + I_{k,L}^{k-1}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}} \bigr)^{k-1} + 2^{k-1}\bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+2}}{k-1}}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L+1}} \bigr)^{k-1} \Bigr) \\[3pt] &\quad\times \bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+1}}{(k-1)^{2}}}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr)\Bigl( 1+2^{k} M_k^{L(k-1)} \bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+1}}{k-1}} \bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr)^{k-1} \Bigr)\\[3pt] &\leq 2 M_k^{2}\biggl(\dfrac{2}{L}\biggr)^{{{L}/{2}}} \Bigl(1 + \Bigl(2^{k-1}I_{k,L}^{k-1}+4^{k-1}\bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+2}}{k-1}}\Bigr)\bigl( \vert \mathbf{x}\vert^{k-1} + \vert \mathbf{x} \vert^{(k-1)k^{L+1}} \bigr) \Bigr) \\[3pt] &\quad\times \bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+1}}{(k-1)^{2}}}\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr)\Bigl( 1+2^{2k-1} M_k^{L(k-1)} \bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+1}}{k-1}} \bigl( \vert \mathbf{x}\vert^{k-1} + \vert \mathbf{x} \vert^{(k-1)k^{L}} \bigr) \Bigr)\end{align*}
and
\begin{align*}\mathcal{K}_{2}&\leq \Bigl(1+8M_{k}^{L-1}\bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+1}}{(k-1)^{2}}} \bigl(|\mathbf{x}|+|\mathbf{x}|^{Lk^{L+1}} \bigr) \\[3pt] &\quad \times \Bigl(I_{k,L}+M_{k}^{L}2\bigl(1+M_k^{k-1}\bigr)^{\frac{k^{L+2}}{(k-1)^{2}}}+2^{L-1}\Bigl(I_{k,L}^{L}+M_{k}^{L^{2}}2^{L}\bigl(1+M_k^{k-1}\bigr)^{\frac{Lk^{L+2}}{(k-1)^{2}}}\Bigr)\Bigr)\Bigr)^{L}.\end{align*}
In addition, (A.7) and
$M_{k}\geq 1$
imply that
\begin{align}I_{k,L}&\leq 2M_{k}^{L+1}\bigl(1+M_{k}^{k-1}\bigr)^{\frac{L+1}{(k-1)^{2}}}\Bigl(2+4^{k-1}M_{k}^{L(k-1)}\bigl(1+M_{k}^{k-1}\bigr)^{\frac{L+1}{k-1}}\Bigr)\nonumber\\[3pt] &\leq 2^{1+\frac{L+1}{(k-1)^{2}}}M_{k}^{\frac{k(L+1)}{k-1}}2^{1+\frac{2(k-1)^{2}+L+1}{k-1}}M_{k}^{Lk+1} \notag \\[3pt] &\leq 2^{2k+\frac{k(L+1)}{(k-1)^{2}}}M_{k}^{\frac{Lk^{2}+2k-1}{k-1}}.\end{align}
Therefore, by the same argument as the proof of (A.8), estimating, consolidating, and rearranging yields
\begin{align*}B_{1}(|\mathbf{x}|,\Theta,\Gamma)&\leq 2^{\frac{(L+6)k^{L+3}}{(k-1)^{2}}}{M_k^{\frac{(L+7)k^{L+3}}{k-1}}}\biggl(\dfrac{2}{L}\biggr)^{{{L}/{2}}} \bigl(1 + \bigl( \vert \mathbf{x}\vert^{k-1} + \vert \mathbf{x} \vert^{(k-1)k^{L+1}} \bigr) ^{2}\bigr)\bigl( \vert \mathbf{x}\vert + \vert \mathbf{x} \vert^{k^{L}} \bigr)\\[3pt] &\quad \times \Bigl(1+2^{\frac{L(L+10)k^{L+2}}{(k-1)^{2}}}M_k^{\frac{(3L^{2}+1)k^{L+2}}{k-1}} \bigl(|\mathbf{x}|+|\mathbf{x}|^{Lk^{L+1}} \bigr)\Bigr)^{L}\\[3pt] &\leq B(\mathbf{x}).\end{align*}
Then the first inequality follows from Lemma A.3 and the second inequality can be derived from setting
$\Gamma$
equal to the all-zeros parameter in the first inequality. The proof is complete.
Finally, we move towards the proof of Theorem 3.1.
Proof of Theorem 3.1. Combining with Lemmas A.3 and A.4, and applying the same arguments discussed in the proof of Theorem 3 of [Reference Taheri, Xie and Lederer38], yields the desired result.
Acknowledgements
We wish to thank the editor and two referees for their insightful comments and suggestions on this article, which have led to significant improvements.
Funding information
Peng Chen’s research was supported by the National Natural Science Foundation of China (12301176) and the International (Regional) Cooperation and Exchange Program of NSFC under NSFC-RS Joint Program (W2521122). Ting Zhang’s research was supported by the National Natural Science Foundation of China (12301342).
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
