Exploring the Complexity of Deep Neural Networks through Functional
  Equivalence
We investigate the complexity of deep neural networks through the lens of
functional equivalence, which posits that different parameterizations can yield
the same network function. Leveraging the equivalence property, we present a
novel bound on the covering number for deep neural networks, which reveals that
the complexity of neural networks can be reduced. Additionally, we demonstrate
that functional equivalence benefits optimization, as overparameterized
networks tend to be easier to train since increasing network width leads to a
diminishing volume of the effective parameter space. These findings can offer
valuable insights into the phenomenon of overparameterization and have
implications for understanding generalization and optimization in deep
learning.
Guohao Shen
# Complexity of Feed-Forward Neural Networks from the Perspective of Functional Equivalence

###### Abstract

In this paper, we investigate the complexity of feed-forward neural networks by examining the concept of functional equivalence, which suggests that different network parameterizations can lead to the same function. We utilize the permutation invariance property to derive a novel covering number bound for the class of feed-forward neural networks, which reveals that the complexity of a neural network can be reduced by exploiting this property. Furthermore, based on the symmetric structure of parameter space, we demonstrate that an appropriate strategy of random parameter initialization can increase the probability of convergence for optimization. We found that overparameterized networks tend to be easier to train in the sense that increasing the width of neural networks leads to a vanishing volume of the effective parameter space. Our findings offer new insights into overparameterization and have significant implications for understanding generalization and optimization in deep learning.

## 1 Introduction

Feed-forward neural networks, particularly deep and wide ones, have demonstrated remarkable success in various applications widely in the fields of machine learning and artificial intelligence. However, one of the major challenges in understanding the success is to explain their ability to generalize well, even if they are very large and have the potential to overfit the training data(Neyshabur et al., 2014, 2017; Razin and Cohen, 2020).

Theoretical studies have suggested that the generalization error can be related to the complexity, approximation power, and optimization properties of deep neural networks. Larger neural networks are proved to possess better approximation power (Yarotsky, 2017; Lu et al., 2021; Zhou, 2020), but may exhibit larger complexity and generalization gaps (Bartlett et al., 2017; Mohri et al., 2018; Bartlett et al., 2019), and can be more challenging to optimize (Glorot et al., 2011). However, some aspects of deep learning initially appeared to contradict common sense: overparameterized networks tend to be easier to train (Frankle and Carbin, 2019; Allen-Zhu et al., 2019; Du et al., 2019) and exhibit better generalization (Belkin et al., 2019; Neyshabur et al., 2019; Novak et al., 2018). Although the model class's capacity was immense, deep networks did not tend to overfit (Zhang et al., 2017).

Recent studies have highlighted that the functional form of neural networks may be less complex than their parametric form Bui Thi Mai and Lampert (2020); Stock and Gribonval (2022); Grigsby et al. (2022). In other words, the parameterization of neural networks is redundant, as networks with different parameters may implement the same function. This insight provides us with a fresh perspective for reconsidering how overparameterization truly affects the generalization and optimization.
In this work, we quantitatively characterize the redundancy in the parameterization of feedforward neural networks and derive a complexity measure for these networks based on functional equivalence. We analyze the results to gain insights into generalization and optimization in deep learning.

### Related work

The issue of redundancy or identification of parameterization of neural networks has been noted since 1990 in Hecht-Nielsen (1990). Subsequent studies for neural networks with Tanh and sigmoid activation functions(Chen et al., 1993; Fefferman and Markel, 1993; Kurkov'a and Kainen, 1994) have proved that given the input-output mapping of a Tanh neural network, its architecture can be determined and weights are identified up to permutations and sign flips. In recent years, the identifiability of parameterization in deep neural networks, particularly ReLU neural networks, has received considerable attention (Elbrachter et al., 2019; Bui Thi Mai and Lampert, 2020; Bona-Pellissier et al., 2021; Dereich and Kassing, 2022; Stock and Gribonval, 2022; Grigsby et al., 2022, 2022). Most recently, Bui Thi Mai and Lampert (2020) demonstrated that ReLU networks with non-increasing widths are identifiable up to permutation and scaling of weight matrices. With redundant parameterization, the weight space of deep neural networks can exhibit symmetries structures, which leads to implications for optimization(Neyshabur et al., 2015; Badrinarayanan et al., 2015; Stock et al., 2019). These studies suggest that naive loss gradient is sensitive to reparameterization by scaling, and proposed alternative, scaling-invariant optimization procedures. In addition, the redundancy or identification properties of neural networks are also closely related to the study of inverse stability (Elbrachter et al., 2019; Rolnick and Kording, 2020; Bona-Pellissier et al., 2021; Petersen et al., 2021; Stock and Gribonval, 2022), which investigates the possibility for one to recover the parameters (weights and biases) of a neural network.

The complexity of neural networks as input-output functions based on their parameterization redundancy has received relatively little attention. To the best of our knowledge, most relevant studies are Grigsby et al. (2022, 2022). Grigsby et al. (2022) studied the their newly defined local and global notions of topological complexity for fully-connected feedforward ReLU neural network functions. Grigsby et al. (2022) defined the functional dimension of ReLU neural networks based on perturbations in parameter space, and studied the their functional redundancy and when the functional dimension achieves its theoretical maximum. However, these results on functional dimension are not applicable to convert into generalization error bounds for deep learning algorithms.

The complexity of a class of functions characterizes how rich it is and is a core quantity closely related to generalization error, where larger complexities lead to larger generalization error (Bartlett et al., 2017; Mohri et al., 2018). Complexity upper bounds for deep neural networks in different measurements have been studied, including Rademacher complexity (Neyshabur et al., 2015; Golowich et al., 2018; Li et al., 2018), VC-dimension and Pseudo dimension (Baum and Haussler, 1988; Goldberg and Jerrum, 1993; Anthony et al., 1999; Bartlett et al., 2019), and covering number (Anthony et al., 1999; Neyshabur et al., 2017; Bartlett et al., 2017; Lin and Zhang, 2019). These measurements characterize how complex the class of neural networks (as functions) is and are expressed in terms of and increasing in the hyperparameters of the neural architecture, such as network depth, width, number of weights and bias vectors, and corresponding norm bounds. These bounds are not directly comparable to each other in magnitude, though they are closely related and can be converted to make a comparison (Anthony et al., 1999; Mohri et al., 2018).

### Our contributions

In this work, we quantitatively characterize the redundancy in the parameterization of feedforward neural networks, and derive new covering number upper bounds for these networks based on functional equivalence. We summarize our contributions as following aspects:

1. We make use of the permutation equivalence property to firstly obtain a tighter upper bound on the covering number. Surprisingly, we found that bias vectors are "for free" in the sense that the increased complexity that comes with adding bias vectors to neural networks is canceled by taking permutation invariance into account.
2. We improve existing covering number bounds in the sense that our results hold for neural networks with bias vectors and general activation functions. Since bias terms are indispensable for the approximation power of neural networks, our results are useful in both theory
and practice. Additionally, we express our bound explicitly in terms of the width, depth, size of the network, and the norm of the parameters, instead of the spectral norm of the weight matrices, which is usually unknown in practice.
3. We discuss the implications of our findings for understanding generalization and optimization. In particular, we found that using the same strategy of random initialization for weights and biases within a layer can reduce the complexity of optimizations. And we found that overparameterized networks tend to be easier to train in the sense that increasing the width of neural networks leads to a vanishing volume of the effective parameter space.

The remainder of the paper is organized as follows. In section 2, we introduce the concept of functional equivalence and investigate the permutation invariance property of general feedforward neural networks. In section 3, we derive novel covering number bounds for shallow and deep feedforward neural networks by exploiting the permutation invariance property and compare our results with existing ones. In section 4, we demonstrate that permutation invariance can help theoretically reduce the optimization complexity in deep learning and discuss the implications of our results on generalization and optimization under the framework of empirical risk minimization. Finally, we discuss the limitations of this study and future research directions in section 5. All technical proofs are included in the supplementary materials.

## 2 Functionally equivalent Feedforward Neural Networks

A feedforward neural network is a fully connected artificial neural network consisting of multiple layers of interconnected neurons. The network's architecture can be expressed as a composition of linear transformations and activations. The functional form of an \(L\)-layer feedforward neural network is determined by its weight matrices, bias vectors, and activation functions:

\[f(x;\theta)=\mathcal{A}_{L+1}\circ\sigma_{L}\circ\mathcal{A}_{L}\circ\cdots \circ\sigma_{2}\circ\mathcal{A}_{2}\circ\sigma_{1}\circ\mathcal{A}_{1}(x). \tag{1}\]

Here, \(\mathcal{A}_{l}(x)=W^{(l)}x+b^{(l)}\) is the linear transformation for layer \(l\), where \(W^{(l)}\) and \(b^{(l)}\) are the weight matrix and bias vector respectively. The activation function \(\sigma_{l}\) is applied element-wise to the output of \(\mathcal{A}_{l}\), and can be different across layers. The collection of weight matrices and bias vectors is denoted by \(\theta=(W^{(1)},b^{(1)},\ldots,W^{(L+1)},b^{(L+1)})\). The input \(x\) is propagated through each layer of the network to produce the output \(f(x;\theta)\).

The parameterization of a feedforward neural network can be redundant, with different parameter sets producing identical function outputs. This redundancy arises due to the non-identifiability of certain weight matrices or activation functions.

\begin{table}
\begin{tabular}{c c c c} \hline \hline Perspective & Estimation Error & Optimization Error & Approximation Error \\ \hline Improve & & & **?** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Suggested improvement by this study in understanding generalization errors from different perspectives under empirical risk minimization framework.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Paper & Complexity & Explicit & \begin{tabular}{c} Allow Bias \\ Vectors \\ \end{tabular} & \begin{tabular}{c} General \\ Activations \\ \end{tabular} & 
\begin{tabular}{c} Permutation \\ Invariance \\ \end{tabular} \\ \hline Bartlett et al. (2017) & \(B_{x}^{2}(\bar{\rho}\bar{s})^{2}\mathcal{U}\log(W)/\epsilon^{2}\) & & & \\ Neyshabur et al. (2017b) & \(B_{x}^{2}(\bar{\rho}\bar{s})^{2}\mathcal{S}^{2}\log(WL)/\epsilon^{2}\) & & & \\ Lin and Zhang (2019) & \(B_{x}(\bar{\rho}\bar{s})\mathcal{S}^{2}L/\epsilon\) & & & \\ Bartlett et al. (2019) & \(L\mathcal{S}\log(\mathcal{S})\log(B_{x}/\epsilon)\) & & & \\ This paper & \(L\mathcal{S}\log(\bar{\rho}\bar{s}B_{x}^{1/L}/(d_{1}\cdots d_{L}\epsilon)^{1/L})\) & & & \\ \hline \hline \end{tabular}

* Notations: \(\mathcal{S}\), total number of parameters; \(\mathcal{U}\), number of hidden neurons; \(L\) number of hidden layers; \(W\), maximum width of hidden layers; \(B_{x}\), L2 norm of input; \(\bar{\rho}=\Pi_{j=1}^{L}\rho_{j}\), products of Lipschitz constants of activation functions; \(\bar{s}=\Pi_{j=1}^{L}s_{j}\), products of spectral norms of hidden layer weight matrices; \(\epsilon\), radius for covering number.

\end{table}
Table 2: A comparison of recent results on the complexity of feedforward neural networks.
**Definition 1** (Functionally-Equivalent Neural Networks).: _Two neural networks \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) are said to be functionally-equivalent if they produce the same input-output function for all possible inputs, i.e.,_

\[f_{1}(x;\theta_{1})=f_{2}(x;\theta_{2})\quad\forall x\in\mathcal{X}, \tag{2}\]

_where \(\mathcal{X}\) is the input space and \(\theta_{1}\) and \(\theta_{2}\) denote the sets of parameters of the two networks, respectively._

Neural networks with a fixed architecture can have functionally-equivalent versions through weight scaling, sign flips, and permutations. This can even occur across networks with different architectures. In this paper, we focus on the complexity of a specific class of neural networks with fixed architecture but varying parameterizations. We provide examples of functionally-equivalent shallow neural networks to illustrate this concept.

**Example 1** (Scaling).: _Consider two shallow neural networks parameterized by \(\theta_{1}=(W_{1}^{(1)},b_{1}^{(1)},W_{1}^{(2)},b_{1}^{(2)})\) and \(\theta_{2}=(W_{2}^{(1)},b_{2}^{(1)},W_{2}^{(2)},b_{2}^{(2)})\), defined as:_

\[f(x;\theta_{1})=W_{1}^{(2)}\sigma(W_{1}^{(1)}x+b_{1}^{(1)})+b_{1}^{(2)}\quad \mathrm{and}\quad f(x;\theta_{2})=W_{2}^{(2)}\sigma(W_{2}^{(1)}x+b_{2}^{(1)}) +b_{2}^{(2)}\]

_respectively, where \(x\in\mathbb{R}^{n}\) is the input to the network and \(\sigma\) satisfies_

\[\sigma(\lambda x)=\lambda\sigma(x)\]

_for all \(x\in\mathbb{R}^{n}\) and \(\lambda>0\). If there exists a scalar value \(\alpha>0\) such that:_

\[(W_{2}^{(1)},b_{2}^{(1)})=(\alpha W_{1}^{(1)},\alpha b_{1}^{(1)})\qquad \mathrm{and}\qquad W_{2}^{(2)}=\frac{1}{\alpha}W_{1}^{(2)},\]

_then the neural networks \(f(\cdot;\theta_{1})\) and \(f(\cdot;\theta_{2})\) are functionally equivalent._

Scaling invariance property is applicable to ReLU, Leaky ReLU, and piecewise-linear activated neural networks. Specifically, for all \(x\in\mathbb{R}^{n}\) and \(\lambda\geq 0\), we have \(\sigma(\lambda x)=\lambda\sigma(x)\) for \(\sigma\) being the ReLU or Leaky ReLU function. It is worth noting that the above example is presented for shallow neural networks, but the scaling invariance property can be extended to deep neural networks across any two consecutive layers.

**Example 2** (Sign Flipping).: _Consider two shallow neural networks \(f(\cdot;\theta_{1})\) and \(f(\cdot;\theta_{2})\) defined in Example 1 with \(\sigma\) being an odd function, that is \(\sigma(-x)=-\sigma(x)\) for all \(x\in\mathbb{R}^{n}\). If_

\[(W_{2}^{(1)},b_{2}^{(1)})=(-W_{1}^{(1)},-b_{1}^{(1)})\qquad\mathrm{and} \qquad W_{2}^{(2)}=-W_{1}^{(2)},\]

_then the neural networks \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) are functionally equivalent._

Sign flipping invariance property can happen for neural networks activated by Tanh, Sin and odd functions. The sign flipping invariance property can also be generalized to deep neural networks across any two consecutive layers.

**Example 3** (Permutation).: _Consider two shallow neural networks \(f(\cdot;\theta_{1})\) and \(f(\cdot;\theta_{2})\) defined in Example 1 with \(\sigma\) being a general activation function. Let the dimension of the hidden layer of \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) be denoted by \(m\). If there exists an \(m\times m\) permutation matrix \(P\) such that_

\[(PW_{2}^{(1)},Pb_{2}^{(1)})=(W_{1}^{(1)},b_{1}^{(1)})\qquad\mathrm{and}\qquad W _{2}^{(2)}P=W_{1}^{(2)},\]

_then the neural networks \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) are functionally equivalent._

The feedforward neural networks are built of linear transformations and activations, and it is intuitive that simply re-indexing neurons in a hidden layer and the corresponding rows of the weights matrix and bias vector will lead to a functionally equivalent neural network. The permutation invariance is the most basic type of equivalence for feedforward neural networks since it does not rely on any specific properties of activation functions, while scaling and sign flipping invariance are activation-dependent properties. A comparison on the functional equivalence properties on neural network with commonly-used activation functions is presented in Table 3.
Next, we derive sufficient conditions for deep feed-forward neural networks (FNNs) to be permutation-equivalent.

**Theorem 1** (Permutation equivalence for deep FNNs).: _Consider two neural networks \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) with the same activations \(\sigma_{1},\ldots,\sigma_{L}\) and architecture_

\[f(x;\theta)=W^{(L+1)}\sigma_{L}(W^{(L)}\cdots\sigma_{1}(W^{(1)}_{1}x+b^{(1)}_{ 1})\cdots)+b^{(L)}_{1})+b^{(L+1)}\]

_but parameterized by different parameters_

\[\theta_{1}=(W^{(1)}_{1},b^{(1)}_{1},\ldots,W^{(L+1)}_{1},b^{(L+1)}_{1}),\qquad \theta_{2}=(W^{(1)}_{2},b^{(1)}_{2},\ldots,W^{(L+1)}_{2},b^{(L+1)}_{2})\]

_respectively, where \(x\in\mathbb{R}^{n}\) is the input to the network. Let \(P^{\top}\) denote the transpose of matrix \(P\). If there exists permutation matrices \(P_{1},\ldots,P_{L}\) such that_

\[W^{(1)}_{1}=P_{1}W^{(1)}_{2}, b^{(1)}_{1}=P_{1}b^{(1)}_{2},\] \[W^{(1)}_{1}=PW^{(1)}_{2}P^{\top}_{l-1}, b^{(l)}_{1}=P_{l}b^{(1)}_{2}, l=2,\ldots,L\] \[W^{(L+1)}_{1}=W^{(L+1)}_{2}P^{\top}_{L}, b^{(L)}_{1}=b^{(L)}_{2},\]

_then the neural networks \(f(x;\theta_{1})\) and \(f(x;\theta_{2})\) are functionally equivalent._

Theorem 1 describes the relationship between the parameters of two permutation-equivalent deep feedforward neural networks. This relationship can be used to create functionally equivalent networks with fixed architectures. It's important to note that although permutation invariance is sufficient for functional equivalence of some feedforward neural networks with general activation functions, it's not always necessary. To fully characterize the necessary and sufficient conditions for functional equivalence, certain restrictions on the network's architecture or activation function are required (Kurkov'a and Kainen, 1994; Bui Thi Mai and Lampert, 2020). However, this study focuses only on utilizing permutation invariance to investigate neural network complexity.

## 3 Complexity of Feedforward Neural Networks

In this section, we analyze the complexity of a class of feedforward neural networks by examining the redundancy that arises from permutation invariance. Specifically, we study the covering number of real-valued, deep feedforward neural networks that share the same architecture but have different parameterization.

Let the vector \((d_{0},d_{1},\ldots,d_{L})\) represent the dimensions of the layers of the neural network \(f(x;\theta)\) defined in (1), where \(d_{L+1}=1\) as the output is real-valued. Note that the bias vectors in hidden layers contain \(\mathcal{U}:=\sum_{i=1}^{L}d_{i}\) entries, and the weight matrices together with bias vectors contain \(\mathcal{S}:=\sum_{i=0}^{L}d_{i}\times d_{i+1}+d_{i+1}\) entries in total. We define the parameter space of \(\theta\) as \(\Theta=[-B,B]^{S}\) for some \(B\geq 1\), which is closed for permutation operations and ensures the absolute value of the weight matrix and bias vector entries are bounded by \(B\). We set \(\Theta=[-B,B]^{S}\) for some \(B\geq 1\). The setting is in line with complexity studies as in (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al., 2018) with norm controls. It also takes into account the implicit regularization phenomenon in optimization (Gunasekar et al., 2018, 2018). We do not specify any activation functions \(\sigma_{1},\ldots,\sigma_{L}\) since we consider general deep feedforward neural networks. Finally, the class of feedforward neural networks we consider is denoted as

\[\mathcal{F}(L,d_{0},d_{1},\ldots,d_{L},B)=\{f(\cdot;\theta):\mathbb{R}^{d_{0} }\rightarrow\mathbb{R}\text{ is defined in }(1):\theta\in[-B,B]^{S}\}. \tag{3}\]

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Activations & Formula & Sign flipping & Scaling & Permutation \\ \hline Sigmoid & \([1+\exp(-x)]^{-1}\) & ✗ & ✗ & ✓ \\ Tanh & \([1-\exp(-2x)]/[1+\exp(-2x)]\) & ✓ & ✗ & ✓ \\ ReLU & max\{0,\(x\}\) & ✗ & ✓ & ✓ \\ Leaky ReLU & max\{ax,x\} for \(a>0\) & ✗ & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 3: Functional equivalence property for networks with different activation functions.
### Shallow Feed-Forward Neural Networks

It is well-known that a shallow neural network with a single hidden layer has universal approximation properties (Cybenko, 1989; Hornik, 1991) and is sufficient for many learning tasks (Hanin and Rolnick, 2019; Hertrich et al., 2021). We begin our investigation by considering shallow neural networks of the form

\[\mathcal{F}(1,d_{0},d_{1},B)=\{f(x;\theta)=W^{(2)}\sigma_{1}(W^{(1)}x+b^{(1)})+ b^{(2)}:\theta\in[-B,B]^{\mathcal{S}}\} \tag{4}\]

where the total number of parameters is given by \(\mathcal{S}=(d_{0}+2)\times d_{1}+1\). By Theorem 1, for any \(\theta=(W^{(1)},b^{(1)},W^{(2)},b^{(2)})\in\Theta\) and any permutation matrix \(P\), \(\hat{\theta}=(PW^{(1)},Pb^{(1)},W^{(2)}P^{\top},b^{(2)})\in\Theta\) will produce the same input-out function. Actually, permutation invariance leads to equivalence classes of parameters that yield the same realization, and we can obtain a set of representatives from equivalence classes. A canonical choice can be

\[\Theta_{0}:=\{\theta\in[-B,B]^{\mathcal{S}}:b_{1}^{(1)}\geq b_{2}^{(1)}\geq \cdots\geq b_{d_{1}}^{(1)}\},\]

where the set of representatives is by restricting the bias vector \(b^{(1)}=(b_{1}^{(1)},\ldots,b_{d_{1}}^{(1)})^{\top}\) to have descending components. Alternatively, we can sort the first component of the rows of \(W^{(1)}\) to obtain a set of representatives. The set of representatives \(\Theta_{0}\) has two important properties

* The neural networks \(\{f(\cdot;\theta):\theta\in\Theta_{0}\}\) parameterized by \(\Theta_{0}\) contains all the functions in \(\{f(\cdot;\theta):\theta\in\Theta\}\), which we denote as \[\{f(\cdot;\theta):\theta\in\Theta_{0}\}=\{f(\cdot;\theta):\theta\in\Theta\}.\]
* The volume of the set of representatives \(\Theta_{0}\) is \((1/d_{1}!)\) times smaller that that of the parameter space \(\Theta\), which we express as \[\mathrm{Volume}(\Theta)=d_{1}!\times\mathrm{Volume}(\Theta_{0}).\]

These properties suggest that \(\Theta_{0}\) can be a light and effective parameterization of neural networks when they are viewed only as input-output functions. In light of these observations, we derive improved complexities of the class of neural networks in terms of its covering number.

**Definition 2** (Covering Number).: _Let \(\mathcal{F}=f:\mathcal{X}\to\mathbb{R}\) be a class of functions. We define the supremum norm of \(f\in\mathcal{F}\) as \(\|f\|_{\infty}:=\sup_{x\in\mathcal{X}}|f(x)|\). For a given \(\epsilon>0\), we define the covering number of \(\mathcal{F}\) with radius \(\epsilon\) under the norm \(\|\cdot\|_{\infty}\) as the least cardinality of a subset \(\mathcal{G}\subseteq\mathcal{F}\) satisfying_

\[\sup_{f\in\mathcal{F}}\min_{g\in\mathcal{G}}\|f-g\|_{\infty}\leq\epsilon.\]

_Denoted by \(\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty})\), the covering number measures the minimum number of functions in \(\mathcal{F}\) needed to cover the set of functions within a distance of \(\epsilon\) under the supremum norm._

The covering number \(\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty})\) provides a quantitative measure of the complexity of the class of functions \(\mathcal{F}\) under the supremum norm, with smaller values indicating simpler classes. Covering numbers, along with Rademacher complexity, VC dimension, and Pseudo dimension, are essential complexity measures in the analysis of learning theories and in estimating generalization errors. Although these measures are different, they are correlated with each other, and we introduce the detailed correlations in Appendix.

**Remark 1**.: _We define the covering number of a class of functions in the uniform sense. This is an extension of the canonical definition of covering numbers, which was originally developed for subsets in Euclidean space. While most existing studies of covering numbers for function spaces consider the image of the functions on a finite sample (Anthony et al., 1999; Bartlett et al., 2017), our definition is formulated directly in terms of the function space itself, without requiring a finite sample or any other auxiliary construction._

**Theorem 2** (Covering number of shallow neural networks).: _Consider the class of single hidden layer neural networks \(\mathcal{F}:=\mathcal{F}(1,d_{0},d_{1},B)\) defined in (4) parameterized by \(\theta\in\Theta=[-B,B]^{\mathcal{S}}\) where \(\mathcal{S}\) is the total number of parameters in the network. Suppose the radius of the domain \(\mathcal{X}\) of \(f\in\mathcal{F}\) is bounded by some \(B_{x}>0\), and the activation \(\sigma_{1}\) is continuous. Then for any \(\epsilon>0\), the covering number_

\[\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty})\leq(16B^{2}(B_{x}+1) \sqrt{d_{0}}d_{1}/\epsilon)^{d_{0}d_{1}+2d_{1}+1}\times\rho^{d_{0}d_{1}+d_{1} }/d_{1}!,\]
_or simply_

\[\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty})\leq(16B^{2}(B_{x}+1) \sqrt{d_{0}}d_{1}/\epsilon)^{\mathcal{S}}\times\rho^{\mathcal{S}_{h}}/d_{1}!, \tag{5}\]

_where \(\rho\) denotes the Lipschitz constant of \(\sigma_{1}\) on the range of the hidden layer (i.e., \([-\sqrt{d_{0}}B(B_{x})+1),\sqrt{d_{0}}B(B_{x}+1)]\)), and \(\mathcal{S}_{h}=d_{0}d_{1}+d_{1}\) is the total number of parameters in the linear transformation form input to the hidden layer, and \(\mathcal{S}=d_{0}\times d_{1}+2d_{1}+1\)._

Our upper bound on the covering number takes advantage of permutation invariance and includes a factorial term \(d_{1}!\) in the denominator, resulting in reduced complexity compared to existing studies (Neyshabur et al., 2015b; Bartlett et al., 2017; Neyshabur et al., 2017b; Neyshabur, 2017; Lin and Zhang, 2019). Stirling's formula can be used to approximate the factorial term as \(\sqrt{2\pi d_{1}}(d_{1}/e)^{d_{1}}\exp(1/(12d_{1}+1))<d_{1}!<\sqrt{2\pi d_{1}} (d_{1}/e)^{d_{1}}\exp(1/12d_{1})\) when \(d_{1}\geq 1\). This reduces the covering number approximately by a factor of \((d_{1}/e)^{d_{1}}\). Notably, the bound in (5) reduces to \((C_{B,B_{x},d_{0},\rho}/\epsilon)^{\mathcal{S}}\times d_{1}^{\mathcal{S}- \mathcal{U}}\), where \(\mathcal{U}=d_{1}\) denotes the number of hidden neurons and \(C_{B,B_{x},d_{0},\rho}>0\) is a constant depending only on \(B,B_{x},d_{0}\) and \(\rho\). Surprisingly, \(\mathcal{S}-\mathcal{U}\) is the number of weights, and the reduced bound is basically that for a single neural network without bias vectors and considering permutation invariance. Bias vectors are "for free" in the sense that including them does not increase the covering number if we take into account permutation invariance. It's worth noting that our bounds allow for bias vectors, which is an improvement over previous studies that didn't consider bias vectors in neural networks (Neyshabur et al., 2015b; Bartlett et al., 2017; Neyshabur et al., 2017b; Neyshabur, 2017; Lin and Zhang, 2019), since bias terms are crucial for the approximation power of neural networks (Yarosky, 2017; Lu et al., 2021b; Shen et al., 2022). Lastly, we note that increasing the number of neurons in a shallow neural network enlarges its approximation power (Lu et al., 2017; Ongie et al., 2019), but at a smaller increase in complexity according to our results

**Remark 2**.: _Theorem 2 applies to any activation function that is continuous and Lipschitz on bounded sets, and does not require any specific choice of activation function, such as Hinge or ReLU as in Neyshabur et al. (2015b, 2017b), or to be universal Lipschitz and \(\sigma(0)=0\) as in Bartlett et al. (2017); Lin and Zhang (2019). Instead, we only require the activation function to be continuous, which implies that it is Lipschitz on bounded sets (range of the hidden layer), which is a technical condition. In the case of the ReLU or Leaky ReLU activation, our bound simplifies to \(\rho=1\) without any condition, leading to the disappearance of the term \(\rho^{\mathcal{S}_{h}}\) in our bound._

### Deep Feed-Forward Neural Networks

For deep neural networks, we can also analyze its effective parameter space based on permutation invariance properties. By Theorem 1, a set of representatives \(\Theta_{0}=\Theta_{0}^{(1)}\times\Theta_{0}^{(2)}\times\cdots\times\Theta_{0}^ {(L)}\times\Theta_{0}^{(L+1)}\) can be constructed where

\[\Theta_{0}^{(l)}=\{(W^{(l)},b^{(l)}) \in[-B,B]^{\mathcal{S}_{l}}:b_{1}^{(l)}\geq b_{2}^{(l)}\geq\cdots \geq b_{d_{l}}^{(l)}\}\text{ for }l=1,\ldots,L,\] \[\Theta_{0}^{(L+1)}=\{(W^{(L+1)},b^{(L+1)})\in[-B,B]^{\mathcal{S}_{ L+1}}\}.\]

Then we can obtain an upper bound of the covering number of deep feedforward neural networks.

**Theorem 3** (Covering number of deep neural networks).: _Consider the class of deep neural networks \(\mathcal{F}:=\mathcal{F}(1,d_{0},d_{1},\ldots,d_{L},B)\) defined in (3) parameterized by \(\theta\in\Theta=[-B,B]^{\mathcal{S}}\) where \(\mathcal{S}\) is the total number of parameters in the neural network. Suppose the radius of the domain \(\mathcal{X}\) of \(f\in\mathcal{F}\) is bounded by \(B_{x}\) for some \(B_{x}>0\), and the activations \(\sigma_{1},\ldots,\sigma_{L}\) are continuous. Then for any \(\epsilon>0\), the covering number_

\[\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty})\leq\frac{ \left(4(L+1)(B_{x}+1)(2B)^{L+2}(\Pi_{j=1}^{L}\rho_{j})(\Pi_{j=0}^{L}d_{j}) \cdot\epsilon^{-1}\right)^{\mathcal{S}}}{d_{1}!\times d_{2}!\times\cdots \times d_{L}!}, \tag{6}\]

_where \(\mathcal{S}=\sum_{i=0}^{L}d_{i}d_{i+1}+d_{i+1}\) and \(\rho_{i}\) denotes the Lipschitz constant of \(\sigma_{i}\) on the range of \((i-1)\)-th hidden layer, especially the range of \((i-1)\)-th hidden layer is bounded by \([-B^{(i)},B^{(i)}]\) with \(B^{(i)}\leq(2B)^{i}\Pi_{j=1}^{i-1}\rho_{j}d_{j}\) for \(i=1,\ldots,L\)._
Theorem 3 provides a novel upper bound for the covering number of deep neural networks based on permutation invariance, which reduces the complexity compared to previous results (Neyshabur et al., 2015, 2017; Bartlett et al., 2017; Lin and Zhang, 2019) by approximately a factor of \((d_{1}!d_{2}!\cdots d_{L}!)\). According to Theorem 3, increasing the depth of a neural network does increase its complexity. However, it is interesting to note that the increased hidden layer \(l\) will have a \((d_{l}!)\) discount on the complexity. If the hidden layers have equal width (\(d=d_{1}=\cdots=d_{L}\)), the bound in (6) reduces to \((C_{B,B_{x},d_{0},\rho}/\epsilon)^{\mathcal{S}}\times d^{\mathcal{S}-\mathcal{ U}}\), where \(\mathcal{U}=Ld\) denotes the number of hidden neurons and \(C_{B,B_{x},d_{0},\rho}>0\) is a constant depending only on \(B,B_{x},d_{0}\) and \(\rho_{i},i=1,\ldots,L\). As with shallow neural networks, bias vectors here are also "for free" when taking into account permutation invariance.

**Remark 3**.: _As discussed in Remark 2, our results take into account the permutation invariance and have looser requirements on activation functions compared to existing results (Neyshabur et al., 2015, 2017; Bartlett et al., 2017; Lin and Zhang, 2019). In addition, our upper bound is explicitly expressed in parameters which are known and can be specified in practice, e.g., network depth \(L\), width \((d_{0},d_{1},\ldots,d_{L})\), size \(\mathcal{S}\) and uniform bound \(B\) for weights and biases. While most existing bounds in (Neyshabur et al., 2015, 2017; Bartlett et al., 2017; Lin and Zhang, 2019) are in terms of the spectral norm of weight matrices and some measurement on externally introduced reference matrices, which are usually unknown in practice._

### Comparing to existing results

The complexity upper bounds in terms of covering number on the class of deep neural networks have been studied in Anthony et al. (1999); Neyshabur et al. (2017); Bartlett et al. (2017); Lin and Zhang (2019). These results are proved by using similar approaches of mathematical induction (e.g. Lemma A.7 in Bartlett et al. (2017), Lemma 2 in Neyshabur et al. (2017) and Lemma 14 of Lin and Zhang (2019)). Compared with these results, we improve upon their results in three ways.

* First, we consider the generally defined neural networks where the bias vector is allowed to appear. Bias terms are indispensable for the approximation power of neural networks (Yarotsky, 2017; Lu et al., 2021; Shen et al., 2022). Neural networks without bias vectors may be disqualified in theory and practice.
* Second, we express our bound in terms of the width, depth, and size of the neural network, as well as the infinity norm of the parameters, instead of the spectral norm of the weight matrices, which is usually unknown in practice.
* Third, we make use of the permutation equivalence property to obtain a tighter upper bound on the covering number. We found that bias vectors are "for free" in the sense that the increased complexity that comes with adding bias vectors to neural networks is canceled by taking permutation invariance into account.

Various complexity upper bounds for deep neural networks in other measurements have also been studied, including Rademacher complexity (Neyshabur et al., 2015; Golowich et al., 2018; Li et al., 2018), VC-dimension, and Pseudo dimension (Baum and Haussler, 1988; Goldberg and Jerrum, 1993; Anthony et al., 1999; Bartlett et al., 2019). Our bounds in terms of covering number are not directly comparable with these measurements. To make a comparison with these other measurements, we convert the upper bounds into metric entropy, which is equivalent to the logarithm of the covering number \(\log(\mathcal{N}(\mathcal{F},\epsilon,\|\cdot\|_{\infty}))\). Specially, let \(\bar{\rho}=\Pi_{j=1}^{L}\rho_{j}\) products of Lipschitz constants of activation functions and \(\bar{s}=\Pi_{j=1}^{L}s_{j}\) products of spectral norms of hidden layer weight matrices Bartlett et al. (2017) derived an spectral-norm based bound of metric entropy \(B_{x}^{2}(\bar{\rho}\bar{s})^{2}\mathcal{U}\log(W)/\epsilon^{2}\), following which Neyshabur et al. (2017) obtained \(B_{x}^{2}(\bar{\rho}\bar{s})^{2}\mathcal{S}L^{2}\log(WL)/\epsilon^{2}\) and Lin and Zhang (2019) obtained \(B_{x}(\bar{\rho}\bar{s})\mathcal{S}^{2}L/\epsilon\). Based on Theorem 12.2 in Anthony et al. (1999), the Pseudo dimension bound in Bartlett et al. (2017) leads to \(L\mathcal{S}\log(\mathcal{S})\log(B_{x}/\epsilon)\). Lastly, our results in Theorem 3 can convert to \(L\mathcal{S}\log(\bar{\rho}\bar{s}B_{x}^{1/L}/(d_{1}!\cdots d_{L}!\epsilon)^{1/L})\) by \(s_{i}=B\sqrt{d_{i}d_{i-1}}\) given in our setting. We present a detailed comparison of these results in Table 2.
Applications to generalization and optimization

In this section, we introduce the empirical risk minimization (ERM) framework to highlight the relevance of our study to both generalization and optimization.

The goal of ERM is to find the target function \(f_{0}\), which represents the true relationship between the inputs and outputs. The target \(\bar{f}_{0}\) which represents the true underlying relationship between the inputs and outputs, which is typically defined as the minimizer of the risk \(\mathcal{R}(\cdot)\), i.e.,

\[f_{0}:=\arg\min_{f}\mathcal{R}(f).\]

However, since the target function is unknown, we can only approximate it using a predefined hypothesis space \(\mathcal{F}\), such as the class of neural networks parameterized by \(\theta\) in deep learning, i.e., \(\mathcal{F}=\mathcal{F}\Theta=f\theta(\cdot)=f(\cdot;\theta):\theta\in\Theta\). Then the "best in class" estimator is then defined by

\[f_{\theta^{*}}=\arg\min_{f\in\mathcal{F}_{\Theta}}\mathcal{R}(f).\]

It's worth noting that the risk function \(\mathcal{R}\) is defined with respect to the distribution of the data, which is unknown in practice. Instead, only a sample with size \(n\) is available, and the empirical risk \(\mathcal{R}n\) can be defined and minimized to obtain an empirical risk minimizer, i.e.,

\[f_{\theta_{n}}\in\arg\min_{f\in\mathcal{F}_{\Theta}}\mathcal{R}_{n}(f).\]

Finally, optimization algorithms such as SGD and Adam lead us to the estimator obtained in practice, i.e., \(f_{\hat{\theta}_{n}}\). The generalization error of \(f_{\hat{\theta}_{n}}\) is defined as \(\mathcal{R}(f_{\hat{\theta}_{n}})-\mathcal{R}(f_{0})\), which can be decomposed (Mohri et al., 2018) as follows:

\[\underbrace{\mathcal{R}(f_{\hat{\theta}_{n,opt}})-\mathcal{R}(f_{0})}_{\text {generalization error}}=\underbrace{\mathcal{R}(f_{\hat{\theta}_{n}})-\mathcal{R}(f_ {\theta_{n}})}_{\text{optimization error}}+\underbrace{\mathcal{R}(f_{\theta_{n}})- \mathcal{R}(f_{\theta^{*}})}_{\text{estimation error}}+\underbrace{\mathcal{R}(f_ {\theta^{*}})-\mathcal{R}(f_{0})}_{\text{approximation error}}.\]

The estimation error is closely related to the complexity of the function class \(\mathcal{F}\Theta\) and the sample size \(n\). For a wide range of problems, the estimation error is of the order \(\mathcal{O}((\log\mathcal{N}(\mathcal{F}\Theta),1/n,\|\cdot\|_{\infty})/n)^{1/2}\)(Bartlett et al., 2019; Kohler and Langer, 2021). The approximation error generally depends on the expressive power of neural networks \(\mathcal{F}_{\Theta}\) and the features of the target function \(f_{0}\), such as its input dimension \(d\) and smoothness \(\beta\). Typical results for the bounds of the approximation error are of the order \(\mathcal{O}((L\mathcal{W})^{-\beta/d})\)(Yarotsky, 2017, 2018; Petersen and Voigtlaender, 2018; Lu et al., 2021b). Due to the high non-convexity and complexity of deep learning problems, the optimization error is far from clear based on optimization theories. Even proving convergence (to stationary points) of existing methods is a difficult task (Sun, 2020).

In this paper, we investigate the functional equivalence, particularly the permutation-invariance property of the parameterization of feedforward neural networks, and demonstrate that this can lead to a reduction in estimation error and a better understanding of optimization error, see Table 1. In section 3, we derived a reduced complexity for feedforward neural networks, which can help to lower the theoretical bounds of the generalization error of the empirical risk minimizer \(f_{\theta_{n}}\). The improvement is due to the consideration of the permutation invariance property when bounding the complexity and estimation error. We also found that the symmetric structure of the parameter space can make optimization easier. For a feedforward neural network in (3), we denote the weight matrix and bias vector in the \(l\)th hidden layer as \(\theta^{(l)}:=(W^{(l)},b^{(l)})\) for \(l=1,\dots,L\). We say two rows in \(\theta^{(l)}\) are identical if the two rows of the concatenated matrix \((W^{(l)};b^{(l)})\) are identical, and we let \(d^{*}_{l}\) denote the number of distinct permutations of rows in \(\theta^{(l)}\). We use a vector \((d^{*}_{1},\dots,d^{*}_{L})\) to collect the number of distinct permutations in the hidden layers of the network parameterization \(\theta=(\theta^{(1)},\dots,\theta^{(L)})\). Let \(\Delta_{min}(\theta)\) denote the minimum of the \(L_{\infty}\) norm of the difference of distinct rows in \(\theta^{(l)}\) over \(l\in{1,\dots,L}\). Let \(\|\theta\|_{\infty}\) denote the maximum absolute value of entries in weight matrices and bias vectors in \(\theta\). Then we have the following result.

**Theorem 4**.: _Suppose we have an empirical risk minimizer \(f_{\theta_{n}}(\cdot)=f(\cdot;\theta_{n})\) with parameter \(\theta_{n}\) having \((d^{*}_{1},\dots,d^{*}_{L})\) distinct permutations and \(\Delta_{min}(\theta_{n})=\delta\). For any optimization algorithm \(\mathcal{A}\), if it guarantees producing a convergent solution of \(\theta_{n}\) when its initialization \(\theta^{(0)}_{n}\) satisfies \(\|\theta^{(0)}_{n}-\theta_{n}\|_{\infty}\leq\delta/2\), then any initialization scheme that uses identical random distributions for the entries of weights and biases within a layer will produce a convergent solution with probability at least \(d^{*}_{1}\times\dots\times d^{*}_{L}\times\mathbb{P}(\|\theta^{(0)}-\theta_{n}\| _{\infty}\leq\delta/2)\). Here, \(\theta^{(0)}\) denotes the random initialization, and \(\mathbb{P}(\cdot)\) denotes the probability with respect to the randomness from initialization._
Theorem 4 can be understood straightforwardly. By Theorem 1, if \(f_{\theta_{n}}\) parameterized by \(\theta_{n}\) is a solution, then \(f_{\tilde{\theta}_{n}}\) is also a solution, where \(\tilde{\theta}_{n}\) is the permutation-implemented version of \(\theta_{n}\). The conditions regarding \(\delta\) in Theorem 1 ensure that the convergent regions for permutation-implemented solutions are disjoint. Initialization schemes that use identical random distributions for the weights and biases within a layer will preserve the distribution of the random initialization \(\theta^{(0)}\), regardless of its permutations. Therefore, if the random initialization \(\theta^{(0)}\) is in the vicinity of any \(\tilde{\theta}_{n}\), then it is sufficient for the algorithm \(\mathcal{A}\) to converge. Thus, the final probability of \(\mathcal{A}\) producing a convergent solution is the probability of the random initialization \(\theta^{(0)}\) being in the union of these disjoint convergence regions.

It is worth noting that when the parameter space is \(\Theta=[-B,B]^{\mathcal{S}}\), based on Theorem 1, the optimization problem is equivalent when restricted to the effective parameter space \(\Theta_{0}\), as defined in section 3.2. The volume of \(\Theta_{0}\) is \((2B)^{\mathcal{S}}/(d_{1}!\cdots d_{L}!)\). Specifically, when \(B\) is fixed, \((2B)^{\mathcal{S}}/(d_{1}!\cdots d_{L}!)\) approaches zero when \(d_{l}\to\infty\) for any \(l=1,\ldots,L\). Remarkably, the observation is counter-intuitive in that increasing the width of neural networks leads to the effective parameter space's volume tending towards zero. As a result, this may explain the observations in Frankle and Carbin (2019); Allen-Zhu et al. (2019); Du et al. (2019) where overparameterized networks tend to be easier to train.

**Remark 4**.: _The popular initialization schemes, including the Xavier and He initialization methods, use normal random numbers to initialize the entries of weight matrices and bias vectors identically within a layer (Glorot and Bengio, 2010; He et al., 2015; Shang et al., 2016; Reddi et al., 2019). By Theorem 4, these initialization schemes reduce the optimization difficulty due to the permutation invariance property._

## 5 Conclusion

In this work, we quantitatively characterized the redundancy in the parameterization of feedforward neural networks and derived a tighter complexity upper bound in terms of the covering number for these networks based on functional equivalence. We found that bias vectors are "for free" in the sense that the increased complexity that comes with adding bias vectors to neural networks is canceled by taking permutation invariance into account. Our improved covering number bound is explicit and holds for neural networks with bias vectors and general activation functions. We discussed the implications of our findings for understanding generalization and optimization. Specifically, we found that using the same strategy of random initialization for weights and biases can reduce the theoretical complexity of optimizations in deep learning. We also observe that increasing the width of neural networks counter-intuitively leads to the effective parameter space's volume tending towards zero, and as a result, the optimization problem seems to become easier.

An important limitation of our work is that we only considered permutation invariance in deriving our complexity bounds for fully-connected feedforward neural networks. It would be interesting to take scale invariance into account and extend the results to other neural networks, such as convolutional neural networks with sparse weight matrices. Additionally, we only considered exactly equivalent functions, while in practice, functional equivalence may be limited to a finite sample, which could lead to further reduced complexity. Lastly, our results only partially explain the benefits of the symmetric structure of neural network parameters for optimization. Further studies may imply advanced optimization algorithms or designs for deep learning. We believe that addressing the above questions carefully can improve both the theoretical bounds and practical algorithms, and we hope to study them in the future.
