Yaoyu Zhang111Corresponding author<EMAIL_ADDRESS>
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC and
Qing Yuan Research Institute, Shanghai Jiao Tong University, Shanghai Center
for Brain Science and Brain-Inspired Technology, Shanghai, 200240, China and
Yuqing Li liyuqing<EMAIL_ADDRESS>
School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai,
200240, China and Zhongwang Zhang<EMAIL_ADDRESS>
School of Mathematical Sciences, Institute of Natural Sciences, Shanghai Jiao
Tong University, Shanghai, 200240, China and Tao Luo<EMAIL_ADDRESS>
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC and
Qing Yuan Research Institute, Shanghai Jiao Tong University, Shanghai, 200240,
China and Zhi-Qin John Xu222Corresponding author<EMAIL_ADDRESS>
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC and
Qing Yuan Research Institute, Shanghai Jiao Tong University, Shanghai, 200240,
China

# Embedding Principle: a hierarchical structure of loss landscape of deep
neural networks

###### Abstract

We prove a general Embedding Principle of loss landscape of deep neural
networks (NNs) that unravels a hierarchical structure of the loss landscape of
NNs, i.e., loss landscape of an NN _contains_ all critical points of all the
narrower NNs. This result is obtained by constructing a class of critical
embeddings which map any critical point of a narrower NN to a critical point
of the target NN with the same output function. By discovering a wide class of
general compatible critical embeddings, we provide a gross estimate of the
dimension of critical submanifolds embedded from critical points of narrower
NNs. We further prove an irreversiblility property of any critical embedding
that the number of negative/zero/positive eigenvalues of the Hessian matrix of
a critical point may increase but never decrease as an NN becomes wider
through the embedding. Using a special realization of general compatible
critical embedding, we prove a stringent necessary condition for being a
“truly-bad” critical point that never becomes a strict-saddle point through
any critical embedding. This result implies the commonplace of strict-saddle
points in wide NNs, which may be an important reason underlying the easy
optimization of wide NNs widely observed in practice.

###### keywords:

neural network, loss landscape, critical point, embedding principle

##  1 Introduction

The loss landscape of a deep neural network (NN) is important to both its
optimization dynamics and generalization performance, hence is a key issue in
deep learning theory. It has been realized for a long time that it is
important to quantify exactly how the loss landscape looks like (E et al.,
2020; Sun et al., 2020). This problem is difficult since various visualization
methods show that the NN loss landscape is very complicated (Li et al., 2018;
Skorokhodov and Burtsev, 2019). Moreover, its non-convexity, high
dimensionality and the dependence on data, model and the specific form of loss
function make it very difficult to obtain a general understanding through
empirical study. Therefore, though it has been extensively studied over the
years, it remains an open problem to provide a clear picture about the general
structure of a DNN loss landscape, e.g., critical points/submanifolds, their
output functions and other properties.

Our work is inspired by the following empirical observations. From the aspect
of optimization, it is often observed that wider NNs are easier for training.
This phenomenon not only holds in a neural tangent kernel (NTK) regime (Jacot
et al., 2018), where the gradient descent training can find the global minimum
with a linear convergence rate (Du et al., 2019; Chizat and Bach, 2018; Arora
et al., 2019; Zou et al., 2018), but also happens in highly nonlinear regimes
far beyond NTK (Luo et al., 2021b). From the aspect of generalization, the
puzzle that over-parameterized NNs often generalize well seems to contradict
the conventional learning theory (Breiman, 1995; Zhang et al., ). The
frequency principle (Xu et al., 2019, 2020; Rahaman et al., 2019; Zhang et
al., 2021a; Luo et al., 2021a) shows that NNs, over-parameterized or not, tend
to fit the training data by a low-frequency function, which suggests that the
learned function by an NN is often of much lower complexity than the NN’s
capacity. Specifically, with small initialization, e.g., in a condensed
regime, weights of an NN are empirically found to condense on isolated
directions resulting in an output function mimicking that of a narrower NN
(Luo et al., 2021b; Maennel et al., 2018). These observations raise a question
that in which sense learning of a wide NN is not drastically different from a
narrower NN despite potentially huge difference in their numbers of
parameters. From the aspect of pruning, empirical works propose a “lottery
ticket hypothesis” that a substantially smaller sub-network can achieve the
same accuracy as the original large network (Frankle and Carbin, 2018).
However, it is not yet clear about the mechanism of redundancy in a learned
wide NN, which makes a drastic pruning possible in practice.

All above empirical observations, though relevant to different aspects of NN,
are in essence pointing towards an intrinsic similarity between narrow and
wide NNs. In this work, focusing on the loss landscape, we address the
following problem: What are the relations of critical points and the
corresponding output functions of loss landscape among NNs with different
widths. The significance of studying the critical points and their output
functions of the NN loss landscape is as follows. From the optimization
perspective, NN parameters trained by gradient descent provably converge to a
critical point, which in general is not necessarily a global minimum or local
minimum. Moreover, even for these saddle points which can be escaped, e.g.,
strict-saddle points (Lee et al., 2019), they may still attract the training
trajectory, contributing to the implicit regularization of NNs. We are
specifically interested in output functions corresponding to critical points,
named as _critical functions_ for convenience. Studying these critical
functions that potentially attract the learning of NN is clearly important for
a deeper understanding of the learning process of an NN.

Our key finding in this work is the following general principle about critical
points/functions of NN loss landscape intuitively stated as follows:

_Embedding principle : the loss landscape of an NN _contains_ all critical
points/functions of all the narrower NNs._

The Embedding Principle shows that any NN loss landscape contains a
hierarchical structure of critical points/functions with different
complexities from NNs of different widths. Specifically, it ensures existence
of “simple” critical functions that can be represented by narrow NNs.
Therefore, combining with the phenomenon of Frequency Principle and
condensation, we conjecture that nonlinear training of NNs may be implicitly
biased towards these “simple” critical functions. We will carefully look into
this conjecture in our future works.

To prove the Embedding Principle, we first construct one-step critical
embeddings which map any parameters of a narrow network to that of an one-
neuron wider NN preserving the output function and criticality. With these
embeddings, critical points of a narrow network loss landscape is mapped to
$1$-d critical affine subspaces of an one-neuron wider network loss landscape
with the same output function. These one-step critical embeddings are
constructed by adding a null neuron or splitting an existing neuron. By
composition of one-step embeddings, any critical point of a narrow network
loss landscape can be mapped to a critical point of any wider network loss
landscape preserving the output function. Importantly, we further propose a
wide class of general compatible critical embeddings, where one-step
embeddings or their composition are its special cases. Note that, all critical
points of a wide NN embedded from a critical point of a narrower NN by all
possible general compatible critical embeddings, form high-dimensional
critical submanifolds which in general are not affine subspaces for three-
layer or deeper NNs.

The critical embeddings naturally link critical points of NNs of different
widths, thus providing a means to track how properties of these critical
points may change as the width of the NN increases. Using these critical
embeddings as a tool, we obtain rich information about the general structure
of an NN loss landscape.

We show that the degeneracy of a critical point substantially increases when
it is embedded to a wider network, due to the fact that a critical point can
be mapped to a high-dimensional critical submanifold through a class of
critical embeddings. This degeneracy of critical points arises from the neuron
redundancy of the wide NN in representing certain simple critical functions
from narrower NNs, which is different from over-parameterization induced
degeneracy studied in Cooper (2021). We also study the property of Hessian of
critical points through critical embedding, e.g., the number of its negative
eigenvalues, which determines whether the corresponding critical point is a
strict-saddle that enables easy optimization (Lee et al., 2019). We prove an
irreversiblility of critical embedding that the number of negative eigenvalues
of Hessian matrix may increase but never decrease as an NN becomes wider
through critical embedding. Moreover, we introduce a notion of “truly-bad”
critical point which never becomes a strict-saddle point through any critical
embedding. We prove a stringent necessary condition for being a “truly-bad”
critical point that requires an important ingredient of its Hessian matrix
being a zero matrix. This result implies the commonplace of strict-saddle
points in the high-dimensional critical submanifolds of wide NNs, which may be
an important reason underlying the easy optimization of wide NNs widely
observed in practice.

In summary, the following general understanding of an NN loss landscape is
obtained by the embedding principle in this work:
(i) It contains a hierarchical structure of critical points/functions with
different complexities from that of all narrower NNs;
(ii) Critical functions from narrower NNs in general forms a high-dimensional
critical submanifold with a gross estimate of the dimension:
$K+\sum_{k\in[L]}K_{l}K_{l-1}$, where $K_{l}$ is the difference in neuron
number in layer $l$ between the target NN and the narrower NN.
(iii) If it has critical points other than the global minima that are not
strict-saddle points, they mostly can become strict-saddle points in wider NNs
through critical embedding, which means the optimization difficulty results
from these critical points can be alleviated by simply using a wider NN.

##  2 Related works

This work is an comprehensive extension of our previous conference paper Zhang
et al. (2021b), in which we study one-step embeddings and their multi-step
composition. Similar results on composition embedding are studied in other
works (Fukumizu and Amari, 2000; Fukumizu et al., 2019; Simsek et al., 2021).

Simple gradient-descent-based optimization on the complex loss landscape of NN
(Skorokhodov and Burtsev, 2019; E et al., 2020) often finds solutions that
generalize well. Many works study the geometry of the NN loss landscape at
critical points in relation to its generalization ability. For example,
empirical works show that SGD (Keskar et al., 2017) and dropout (Zhang et al.,
2021c) training can find a flat minimizer, which may explain why such
stochastic training can find solution that generalize better. Wu et al. (2017)
further suggest that the volume of basin of attraction of good (flat) minima
may dominate over that of poor (sharp) minima in practical problems. He et al.
(2019) show that at a local minimum there exist many asymmetric directions
such that the loss increases abruptly along one side, and slowly along the
opposite side. Ding et al. (2019) prove that for any multi-layer network with
generic input data and non-linear activation functions, sub-optimal local
minima can exist, no matter how wide the network is. When the network width
increases towards infinity, the loss landscape may become simpler and the
training can avoid spurious valleys with high probability in an over-
parameterized regime (Venturi et al., 2019). In an extremely over-
parameterized regime with a large initialization, i.e., the linear regime
identified in Luo et al. (2021b) with the NTK regime as its special case
(Jacot et al., 2018), the gradient descent training can find the global
minimum with a linear convergence rate (Luo et al., 2021b; Du et al., 2019;
Chizat and Bach, 2018; Arora et al., 2019; Zou et al., 2018).

The starting point of this work originates from our work in Luo et al.
(2021b), where we identify a highly nonlinear condensed regime far beyond the
NTK regime that weights condense in isolated directions during the training.
Moreover, neural networks of different width often exhibit similar condensed
behavior, e.g., stagnating at similar loss with almost the same output
function, which is illustrated in experiments in our conference paper Zhang et
al. (2021b). The condensation is a highly nonlinear feature learning process
important to implicit regularization and generalization of NNs. The
condensation transforms a large network to a network of only a few effective
neurons, leading to an output function with low complexity. Such learning
process is consistent with another line of research, that is, the complexity
of NN output gradually increases during the training (Arpit et al., 2017; Xu
et al., 2019, 2020; Rahaman et al., 2019; Zhang et al., 2021a; Luo et al.,
2021a; Kalimeris et al., 2019; Goldt et al., 2020; He et al., 2020; Mingard et
al., 2019; Jin et al., 2020). For example, the Frequency Principle (Xu et al.,
2019, 2020) states that NNs often fit target functions from low to high
frequencies during the training. A series of works study the mechanism of
condensation at an initial training stage, such as for ReLU network (Maennel
et al., 2018; Pellegrini and Biroli, 2020) and network with continuously
differentiable activation functions (Xu et al., 2021).

This work in some sense serves as our attempt to uncover the theoretical
structure underlying the condensation phenomenon from the perspective of loss
function by proving a general Embedding Principle. In another aspect, the
condensation phenomenon also confirms the value of Embedding Principle in
understanding the highly nonlinear training behavior in practice.

The Embedding Principle provides a structural mechanism underlying the
degeneracy as a very common property for critical points (Choromanska et al.,
2015; Sagun et al., 2016). Thus it complements the understanding that global
minima of NNs typically form a high dimensional manifold due to over-
parameterization (Cooper, 2021).

##  3 Preliminary

###  3.1 Deep neural networks

Consider $L$-layer ($L\geq 2$) fully-connected NNs with a general
differentiable activation function. We regard the input as the $0$-th layer
and the output as the $L$-th layer. Let $m_{l}$ be the number of neurons in
the $l$-th layer. In particular, we also set $m_{0}=d$ and $m_{L}=d^{\prime}$.
For any $i,k\in\mathbb{N}$ and $i<k$, we denote $[i:k]=\\{i,i+1,\ldots,k\\}$.
In particular, we denote $[k]:=\\{1,2,\ldots,k\\}$. For a matrix $\bm{A}$, we
use $(\bm{A})_{i,j}$ to denote its $(i,j)$-th entry. We will also define
$(\bm{A})_{i,[j:k]}:=\left((\bm{A})_{i,j},(\bm{A})_{i,j+1},\cdots,(\bm{A})_{i,k}\right)$
as part of the $i$-th row vector. Similarly, $(\bm{A})_{[j:k],i}$ is a part of
the $i$-th column vector. For a vector $\bm{a}$, we use $(\bm{a})_{i}$ to
denote its $i$-th entry, we also define
$(\bm{a})_{[j:k]}:=\left((\bm{a})_{j},(\bm{a})_{j+1},\cdots,(\bm{a})_{k}\right)$
as part of the vector. Given weights $\bm{W}^{[l]}\in\mathbb{R}^{m_{l}\times
m_{l-1}}$ and bias $\bm{b}^{[l]}\in\mathbb{R}^{m_{l}}$ for $l\in[L]$, we
define the collection of parameters $\bm{\theta}$ as a $2L$-tuple (an ordered
list of $2L$ elements) whose elements are matrices or vectors

$\bm{\theta}:=\Big{(}\bm{\theta}|_{1},\cdots,\bm{\theta}|_{L}\Big{)}:=\Big{(}\bm{W}^{[1]},\bm{b}^{[1]},\ldots,\bm{W}^{[L]},\bm{b}^{[L]}\Big{)}.$
(1)

where the $l$-th layer parameters of $\bm{\theta}$ is the ordered pair
$\bm{\theta}|_{l}:=\Big{(}\bm{W}^{[l]},\bm{b}^{[l]}\Big{)},\quad l\in[L]$. We
may misuse our notations and do not distinguish $\bm{\theta}$ from its
vectorization $\mathrm{vec}(\bm{\theta})\in\mathbb{R}^{M}$ with
$M:=\sum_{l=0}^{L-1}(m_{l}+1)m_{l+1}$. Moreover, we call the collection of
tuples of length $2L$ the tuple class, whose elements are matrices
$\\{\bm{W}^{[l]}\\}_{l=1}^{L}$ with $\bm{W}^{[l]}\in\mathbb{R}^{m_{l}\times
m_{l-1}}$, or vectors $\\{\bm{b}^{[l]}\\}_{l=1}^{L}$ with
$\bm{b}^{[l]}\in\mathbb{R}^{m_{l}}$, and denoted by
$\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$, i.e.,

$\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}:=\left\\{\bm{\theta}|\bm{\theta}=\Big{(}\bm{W}^{[1]},\bm{b}^{[1]},\ldots,\bm{W}^{[L]},\bm{b}^{[L]}\Big{)},~{}~{}\bm{W}^{[l]}\in\mathbb{R}^{m_{l}\times
m_{l-1}},~{}\bm{b}^{[l]}\in\mathbb{R}^{m_{l}},~{}l\in[L]\right\\}.$

Since the tuple class inherits the structure of Euclidean spaces, obviously it
is a linear space. We set $\bm{0}$ as the zero element in the tuple class,
i.e.

$\bm{0}=\Big{(}\bm{0}_{m_{1}\times m_{0}},\bm{0}_{m_{1}\times
1},\ldots,\bm{0}_{m_{L}\times m_{L-1}},\bm{0}_{m_{L}\times
1}\Big{)}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}},$

and we abuse the notation $\bm{0}$ from time to time to denote zero elements
belonging to different tuple classes.

We further define the upper bracket $[L-1]$ by limiting ourselves to the first
$2L-2$ element of the tuple, i.e.,

$\bm{\theta}^{[L-1]}:=(\bm{W}^{[1]},\bm{b}^{[1]},\cdots,\bm{W}^{[L-2]},\bm{b}^{[L-2]},\bm{W}^{[L-1]},\bm{b}^{[L-1]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L-2},m_{L-1}\\}}.$
(2)

Given parameters $\bm{\theta}$, the neural network function
$\bm{f}_{\bm{\theta}}(\cdot)$ can be defined in a recursive way. First, we
write $\bm{f}^{[0]}_{\bm{\theta}}(\bm{x}):=\bm{x}$ for the input
$\bm{x}\in\mathbb{R}^{d}$, then for $l\in[L-1]$, $\bm{f}^{[l]}_{\bm{\theta}}$
is defined recursively as

$\bm{f}^{[l]}_{\bm{\theta}}(\bm{x}):=\sigma(\bm{W}^{[l]}\bm{f}^{[l-1]}_{\bm{\theta}}(\bm{x})+\bm{b}^{[l]}),$

where $\sigma(\cdot):\mathbb{R}\to\mathbb{R}$ is the activation function
applied coordinate-wisely, with slight abuse of notation. Finally, we denote

$\bm{f}_{\bm{\theta}}(\bm{x}):=\bm{f}(\bm{x},\bm{\theta}):=\bm{f}^{[L]}_{\bm{\theta}}(\bm{x}):=\bm{W}^{[L]}\bm{f}^{[L-1]}_{\bm{\theta}}(\bm{x})+\bm{b}^{[L]},$
(3)

and for simplicity, sometimes we may drop the subscript $\bm{\theta}$ in
$\bm{f}^{[l]}_{\bm{\theta}}$ for $l\in[0:L]$.

###  3.2 Loss function

The set of training data is denoted by
$S:=\left\\{(\bm{x}_{i},\bm{y}_{i})\right\\}_{i=1}^{n}$, where
$\bm{x}_{i}\in\mathbb{R}^{d}$, $\bm{y}_{i}\in\mathbb{R}^{d^{\prime}}$. Here we
assume that there exists an unknown function
$\bm{f}^{*}(\cdot):\mathbb{R}^{d}\to\mathbb{R}^{d^{\prime}}$ satisfying
$\bm{f}^{*}(\bm{x}_{i})=\bm{y}_{i}$ for $i\in[n]$. The empirical risk reads as

$R_{S}(\bm{\theta}):=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{f}(\bm{x}_{i},\bm{\theta}),\bm{y}_{i}):=\mathbb{E}_{S}\ell(\bm{f}(\bm{x},\bm{\theta}),\bm{f}^{*}(\bm{x})).$
(4)

where the expectation $\mathbb{E}_{S}$ is defined for any function
$h(\cdot):\mathbb{R}^{d}\to\mathbb{R}$ as

$\mathbb{E}_{S}h(\bm{x}):=\frac{1}{n}\sum_{i=1}^{n}h(\bm{x}_{i}),$

and the loss function
$\ell(\cdot,\cdot):\mathbb{R}^{d^{\prime}}\times\mathbb{R}^{d^{\prime}}\to\mathbb{R}$
in (4) is differentiable in both variables, and the derivative of
$\ell(\cdot,\cdot)$ with respect to its first argument is denoted by
$\nabla\ell(\bm{y},\bm{y}^{*})$. In this paper, we always take
derivatives/gradients of $\ell(\cdot,\cdot)$ in its first argument with
respect to any possible parameter.

For each $l\in[L]$, we define the error vectors as

$\bm{z}_{\bm{\theta}}^{[l]}:=\nabla_{\bm{f}^{[l]}}\ell,$

and the feature gradients as

$\bm{g}_{\bm{\theta}}^{[L]}:=\mathbf{1},~{}\text{and}~{}~{}\bm{g}^{[l]}_{\bm{\theta}}:=\sigma^{(1)}\left(\bm{W}^{[l]}\bm{f}^{[l-1]}_{\bm{\theta}}+\bm{b}^{[l]}\right)~{}\text{for}~{}l\in[L-1],$

where we use $\sigma^{(1)}(\cdot)$ for the first derivative of
$\sigma(\cdot)$. Moreover, we call $\bm{f}^{[l]}_{\bm{\theta}}$ the feature
vectors, and we denote the collections of feature vectors, feature gradients,
and error vectors $\\{\bm{z}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L}$ respectively by

$\bm{F}_{\bm{\theta}}:=\\{\bm{f}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L},~{}\bm{G}_{\bm{\theta}}:=\\{\bm{g}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L},~{}\bm{Z}_{\bm{\theta}}:=\\{\bm{z}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L}.$

Moreover, using backpropagation, we can derive the following relations
concerning the above quantities

$\displaystyle\bm{z}_{\bm{\theta}}^{[L]}$ $\displaystyle=\nabla\ell,$ (5)
$\displaystyle\bm{z}_{\bm{\theta}}^{[l]}$
$\displaystyle=(\bm{W}^{[l+1]})^{\intercal}\left(\bm{z}_{\bm{\theta}}^{[l+1]}\circ\bm{g}_{\bm{\theta}}^{[l+1]}\right),\quad
l\in[L-1],$ $\displaystyle\nabla_{\bm{W}^{[l]}}\ell$
$\displaystyle=\left(\bm{z}_{\bm{\theta}}^{[l]}\circ\bm{g}_{\bm{\theta}}^{[l]}\right)(\bm{f}_{\bm{\theta}}^{[l-1]})^{\intercal},\quad
l\in[L],$ $\displaystyle\nabla_{\bm{b}^{[l]}}\ell$
$\displaystyle=\bm{z}_{\bm{\theta}}^{[l]}\circ\bm{g}_{\bm{\theta}}^{[l]},\quad
l\in[L],$

where we use $\circ$ for the Hadamard product (Horn and Johnson, 2012) of two
matrices of the same dimension.

Specifically, for simplicity of gradient computation, we define another group
of error vectors for $l\in[L]$

$\bm{e}^{[l]}_{\bm{\theta}}:=\bm{z}_{\bm{\theta}}^{[l]}\circ\bm{g}_{\bm{\theta}}^{[l]},$

and we denote $\\{\bm{e}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L}$ by
$\bm{E}_{\bm{\theta}}:=\\{\bm{e}^{[l]}_{\bm{\theta}}\\}_{l=1}^{L}$.

Directly from relation (5), we obtain that

$\bm{e}^{[l]}_{\bm{\theta}}=\bm{z}_{\bm{\theta}}^{[l]}\circ\bm{g}_{\bm{\theta}}^{[l]}=\left((\bm{W}^{[l+1]})^{\intercal}\left(\bm{z}_{\bm{\theta}}^{[l+1]}\circ\bm{g}_{\bm{\theta}}^{[l+1]}\right)\right)\circ\bm{g}_{\bm{\theta}}^{[l]}=\left((\bm{W}^{[l+1]})^{\intercal}\bm{e}^{[l+1]}_{\bm{\theta}}\right)\circ\bm{g}_{\bm{\theta}}^{[l]}.$
(6)

###  3.3 Hessian

Given a scalar loss function
$\ell(\cdot,\cdot):\mathbb{R}^{d^{\prime}}\times\mathbb{R}^{d^{\prime}}\to\mathbb{R}$,
twice differentiable in both variables, and an activation function
$\sigma(\cdot):\mathbb{R}\to\mathbb{R}$, also twice differentiable, we denote
that

$\displaystyle R_{S}(\bm{\theta})$
$\displaystyle=\mathbb{E}_{S}\ell(f(\bm{x},\bm{\theta}),f^{*}(\bm{x})).$ (7)
$\displaystyle\bm{v}_{S}(\bm{\theta})$
$\displaystyle:=\nabla_{\bm{\theta}}R_{S}(\bm{\theta})=\mathbb{E}_{S}\nabla\ell(\bm{f}(\bm{x},\bm{\theta}),\bm{f}^{*}(\bm{x}))^{\intercal}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x})=\sum_{i=1}^{m_{L}}\mathbb{E}_{S}\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{i},$
(8)

where $\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})$ is the $i$-th
element of $\nabla\ell(\bm{f}(\bm{x},\bm{\theta}),\bm{f}^{*}(\bm{x}))$, and
$(\bm{f}_{\bm{\theta}})_{i}$ is the $i$-th element of vector
$\bm{f}_{\bm{\theta}}$. Then for the Hessian matrix $\bm{H}_{S}(\bm{\theta})$,
we have

$\displaystyle\bm{H}_{S}(\bm{\theta})$
$\displaystyle:=\nabla_{\bm{\theta}}\nabla_{\bm{\theta}}R_{S}(\bm{\theta})=\sum_{i=1}^{m_{L}}\mathbb{E}_{S}\nabla_{\bm{\theta}}\left(\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\right)\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{i}+\sum_{i=1}^{m_{L}}\mathbb{E}_{S}\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}\nabla_{\bm{\theta}}\left((\bm{f}_{\bm{\theta}})_{i}\right)$
$\displaystyle=\sum_{i,j=1}^{m_{L}}\mathbb{E}_{S}\partial_{ij}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{i}\left(\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{j}\right)^{\intercal}+\sum_{i=1}^{m_{L}}\mathbb{E}_{S}\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}\nabla_{\bm{\theta}}\left((\bm{f}_{\bm{\theta}})_{i}\right),$

where $\partial_{ij}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})$ is the $(i,j)$-th
element of $\nabla\nabla\ell(\bm{f}(\bm{x},\bm{\theta}),\bm{f}^{*}(\bm{x}))$.

We define matrices $\bm{H}^{(1)}_{S}(\bm{\theta})$ and
$\bm{H}^{(2)}_{S}(\bm{\theta})$ as follows:

$\displaystyle\bm{H}^{(1)}_{S}(\bm{\theta})$
$\displaystyle:=\sum_{i,j=1}^{m_{L}}\mathbb{E}_{S}\partial_{ij}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{i}\left(\nabla_{\bm{\theta}}(\bm{f}_{\bm{\theta}})_{j}\right)^{\intercal},$
(9) $\displaystyle\bm{H}^{(2)}_{S}(\bm{\theta})$
$\displaystyle:=\sum_{i=1}^{m_{L}}\mathbb{E}_{S}\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}}\nabla_{\bm{\theta}}\left((\bm{f}_{\bm{\theta}})_{i}\right),$
(10)

and

$\bm{H}_{S}(\bm{\theta})=\bm{H}^{(1)}_{S}(\bm{\theta})+\bm{H}^{(2)}_{S}(\bm{\theta}).$

###  3.4 Assumptions and conventions of notations

We begin this part by introducing several assumptions that will be used
throughout this paper:

###### Assumption

(i) We choose the $L$-layer ($L\geq 2$) fully-connected deep neural networks
(NNs) as our model.
(ii) Our training data is $S=\\{(\bm{x}_{i},\bm{y}_{i})\\}_{i=1}^{n}$,
$n\in\mathbb{Z}^{+}\cup\\{+\infty\\}$.
(iii) We use the empirical loss
$R_{S}(\bm{\theta})=\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})$.
(iv) Loss function $\ell(\cdot,\cdot)$ and activation function $\sigma(\cdot)$
are (weakly) differentiable. (Remark: twice differentiable is required for the
computation of Hessian)

After stating out the assumptions, we would also like to introduce some
conventions of notations that are frequently used in this paper in the
following.

We write $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ for a fully-connected $L$-layer
network with width $(m_{0},\ldots,m_{L})$, by which the tuple class of its
parameters $\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$ is
determined whereas its activation $\sigma(\cdot)$ is not provided. When
$\sigma(\cdot)$ is given, the output of $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$
is denoted by $\bm{f}_{\bm{\theta}}(\bm{x})$ with
$\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$.

Note that, if given two NNs, $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, their corresponding parameters
belong to different tuple classes except when $m^{\prime}_{l}=m_{l}$ for all
$l\in[0:L]$. Therefore, in this work, $\bm{f}_{\bm{\theta}}(\bm{x})$ and
$R_{S}({\bm{\theta}})$ may correspond to output and loss landscape of
different NNs distinguished by $\bm{\theta}$ of different tuple classes.

Given two NNs, $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ with $m^{\prime}_{0}=m_{0}$,
$m^{\prime}_{L}=m_{L}$, and $m^{\prime}_{l}\geq m_{l}$ for any $l\in[L-1]$,
then for $K=\sum_{l=1}^{L-1}(m^{\prime}_{l}-m_{l})\in\mathbb{Z}^{+}$, we say
that $\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ is $K$-neuron wider than
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$, and conversely,
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ is $K$-neuron narrower than
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$.

As long as we have two NNs, $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, given in the context of
Definitions, Theorems, Propositions, Lemmas etc, we always assume that
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ is wider than
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$, i.e., $m^{\prime}_{0}=m_{0}$,
$m^{\prime}_{L}=m_{L}$, and $m^{\prime}_{l}\geq m_{l}$ for any $l\in[L-1]$. We
also denote $M=\sum_{l=0}^{L-1}(m_{l}+1)m_{l+1}$ and
$M^{\prime}=\sum_{l=0}^{L-1}(m^{\prime}_{l}+1)m^{\prime}_{l+1}$, and
consequently, $M^{\prime}\geq M$. We denote the parameters of a narrower
network by $\bm{\theta}_{\textnormal{narr}}$, and the counterpart of a wider
network by $\bm{\theta}_{\textnormal{wide}}$. Then, given the data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, the collection of critical
points of narrower NN and wider NN can be found respectively and denoted by
$\bm{\Theta}_{\textnormal{narr}}^{\textnormal{c}}:=\\{\bm{\theta}|\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}\\}$
and
$\bm{\Theta}_{\textnormal{wide}}^{\textnormal{c}}:=\\{\bm{\theta}|\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}\\}$.
Furthermore,
$\mathcal{F}_{\textnormal{narr}}^{\textnormal{c}}:=\\{\bm{f}_{\bm{\theta}}|\bm{\theta}\in\bm{\Theta}_{\textnormal{narr}}^{\textnormal{c}}\\}$
and
$\mathcal{F}_{\textnormal{wide}}^{\textnormal{c}}:=\\{\bm{f}_{\bm{\theta}}|\bm{\theta}\in\bm{\Theta}_{\textnormal{wide}}^{\textnormal{c}}\\}$
are denoted for the function spaces induced by critical points accordingly.

Finally, a neuron, say the $i$-th neuron in layer $l$, is termed a null neuron
if its output is a constant independent of input $\bm{x}$ for any activation,
i.e., $(\bm{f}^{[l]})_{i}(\cdot)\equiv\mathrm{Const}$ for any $\sigma(\cdot)$.
Otherwise, we call this neuron an effective neuron.

##  4 Embedding Principle

In this section, we prove the Embedding Principle by constructing critical
embeddings. First, we define a critical embedding operation. Then, by
constructing one-step critical embeddings and their composition, we prove the
Embedding Principle that critical points of the loss landscape of a narrow
network can be embedded to critical affine subspaces of the loss landscape of
any wider network while preserving the output function. Finally, we emphasize
the importance of Embedding Principle in understanding the implicit
regularization and generalization of NNs.

We begin with the concepts of embedding, affine embedding and critical
embedding.

######  Definition 4.1 (Embedding and affine embedding).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, an embedding is an injective
operator
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$,
i.e., $\mathcal{T}(\bm{\theta}_{1})\neq\mathcal{T}(\bm{\theta}_{2})$ for
$\bm{\theta}_{1},\bm{\theta}_{2}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
and $\bm{\theta}_{1}\neq\bm{\theta}_{2}$. In addition, $\mathcal{T}$ is an
affine embedding if
$\tilde{\mathcal{T}}(\bm{\theta}):=\mathcal{T}(\bm{\theta})-\mathcal{T}(\bm{0})$
is a linear operator, i.e.,
$\tilde{\mathcal{T}}(\bm{\theta}_{1})+\tilde{\mathcal{T}}(\bm{\theta}_{2})=\tilde{\mathcal{T}}(\bm{\theta}_{1}+\bm{\theta}_{2})$
and
$\tilde{\mathcal{T}}(\beta\bm{\theta})=\beta\tilde{\mathcal{T}}(\bm{\theta})$
for any
$\bm{\theta},\bm{\theta}_{1},\bm{\theta}_{2}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
and $\beta\in\mathbb{R}$.

###### Remark 1

For any given affine embedding $\mathcal{T}$, it is associated with a matrix
$\bm{A}\in\mathbb{R}^{M^{\prime}\times M}$ and a vector
$\bm{c}\in\mathbb{R}^{M^{\prime}}$ such that
$\mathrm{vec}(\mathcal{T}(\bm{\theta}))=\bm{A}\mathrm{vec}(\bm{\theta})+\bm{c}$,
where $M=\sum_{l=0}^{L-1}(m_{l}+1)m_{l+1}$ and
$M^{\prime}=\sum_{l=0}^{L-1}(m^{\prime}_{l}+1)m^{\prime}_{l+1}$. As noted
before, we do not distinguish tuple $\bm{\theta}$ from its vectorization
$\mathrm{vec}(\bm{\theta})$ in the following. Hence,
$\mathcal{T}(\bm{\theta})=\bm{A}\bm{\theta}+\bm{c}$.

######  Definition 4.2 (Critical embedding).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, a critical embedding is an
affine embedding
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$,
which maps any set of its network parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
to that of a wider NN
$\bm{\theta}_{\textnormal{wide}}=\mathcal{T}(\bm{\theta}_{\textnormal{narr}})\in\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
satisfying that: For any given data $S$, loss function $\ell(\cdot,\cdot)$,
activation function $\sigma(\cdot)$,
(i) output preserving:
$\bm{f}_{\bm{\theta}_{\textnormal{narr}}}(\bm{x})=\bm{f}_{\bm{\theta}_{\textnormal{wide}}}(\bm{x})$
for any $\bm{x}\in\mathbb{R}^{d}$;
(ii) representation preserving:

$\mathrm{span}\left\\{\left\\{\left(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}(\cdot)\right)_{j}\right\\}_{j\in[m_{l}]}\cup\\{1\\}\right\\}=\mathrm{span}\left\\{\left\\{\left(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}(\cdot)\right)_{j^{\prime}}\right\\}_{j^{\prime}\in[m^{\prime}_{l}]}\cup\\{1\\}\right\\},~{}~{}\text{for
any}~{}l\in[L],$

where $\\{\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\}_{l=1}^{L}$ and
$\\{\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}\\}_{l=1}^{L}$ are feature
vectors of $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, and
$1:\mathbb{R}^{d}\to\mathbb{R}$ is the constant function, i.e.,
$1(\cdot)\equiv 1$;
(iii) criticality preserving: If $\bm{\theta}_{\textnormal{narr}}$ is a
critical point of $R_{S}({\bm{\theta}})$, i.e.,
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}$, then
$\bm{\theta}_{\textnormal{wide}}$ is also a critical point of
$R_{S}({\bm{\theta}})$, i.e.,
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.
Specifically, if an embedding is a critical embedding with
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ one-neuron wider than
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$, we call it one-step critical embedding.

###  4.1 One-step critical embedding

In this subsection, we introduce two types of one-step critical embeddings. we
start with the definition of one-step null embedding. Intuitively, a one-step
null embedding adds a null neuron to the NN, whose output is a constant
independent of input $\bm{x}$ for any activation.

######  Definition 4.3 (One-step null embedding).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameter
$\bm{\theta}=(\bm{W}^{[1]},\bm{b}^{[1]},\cdots,\bm{W}^{[L]},\bm{b}^{[L]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,
then for any $l\in[L-1]$, we define the operators $\mathcal{T}_{l,0}$ and
$\mathcal{V}_{l,0}$ applying on $\bm{\theta}$ as follows

$\displaystyle\mathcal{T}_{l,0}(\bm{\theta})|_{k}$
$\displaystyle=\bm{\theta}|_{k},\quad k\neq l,~{}l+1,$
$\displaystyle\mathcal{T}_{l,0}(\bm{\theta})|_{l}$
$\displaystyle=\left(\left[{\begin{array}[]{cc}\bm{W}^{[l]}\\\ \bm{0}_{1\times
m_{l-1}}\\\ \end{array}}\right],\left[{\begin{array}[]{cc}\bm{b}^{[l]}\\\ 0\\\
\end{array}}\right]\right),$
$\displaystyle\mathcal{T}_{l,0}(\bm{\theta})|_{l+1}$
$\displaystyle=\left(\left[\bm{W}^{[l+1]},\bm{0}_{m_{l+1}\times
1}\right],\bm{b}^{[l+1]}\right),$
$\displaystyle\mathcal{V}_{l,0}(\bm{\theta})|_{k}$
$\displaystyle=\left(\bm{0}_{m_{k}\times m_{k-1}},\bm{0}_{m_{k}\times
1}\right),\quad k\neq l,~{}l+1$
$\displaystyle\mathcal{V}_{l,0}(\bm{\theta})|_{l}$
$\displaystyle=\left(\bm{0}_{(m_{l}+1)\times
m_{l-1}},\left[{\begin{array}[]{cc}\bm{0}_{m_{l}\times 1}\\\ 1\\\
\end{array}}\right]\right),$
$\displaystyle\mathcal{V}_{l,0}(\bm{\theta})|_{l+1}$
$\displaystyle=\left(\bm{0}_{m_{l+1}\times{(m_{l}+1)}},\bm{0}_{m_{l+1}\times
1}\right).$

We define one-step null embedding $\mathcal{T}_{l,0}^{\alpha}$ as: For any
$\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,

$\mathcal{T}_{l,0}^{\alpha}(\bm{\theta})=(\mathcal{T}_{l,0}+\alpha\mathcal{V}_{l,0})(\bm{\theta}).$

Note that the neuron added by the above one-step null embedding has zero
output weights, zero input weights and an arbitrary bias. An illustration is
shown in Fig. 1.

Figure 1: Illustration of one-step null embedding. The purple neuron is added
with both input and output weights as zero and an arbitrary bias.

We proceed to the definition of one-step splitting embedding.

######  Definition 4.4 (One-step splitting embedding).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameter
$\bm{\theta}=(\bm{W}^{[1]},\bm{b}^{[1]},\cdots,\bm{W}^{[L]},\bm{b}^{[L]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,
then for any $l\in[L-1]$ and $s\in[m_{l}]$, we define the operators
$\mathcal{T}_{l,s}$ and $\mathcal{V}_{l,s}$ applying on $\bm{\theta}$ as
follows

$\displaystyle\mathcal{T}_{l,s}(\bm{\theta})|_{k}$
$\displaystyle=\bm{\theta}|_{k},\quad k\neq l,l+1,$
$\displaystyle\mathcal{T}_{l,s}(\bm{\theta})|_{l}$
$\displaystyle=\left(\left[{\begin{array}[]{cc}\bm{W}^{[l]}\\\
\bm{W}^{[l]}_{s,[1:m_{l-1}]}\\\
\end{array}}\right],\left[{\begin{array}[]{cc}\bm{b}^{[l]}\\\
\bm{b}^{[l]}_{s}\\\ \end{array}}\right]\right),$
$\displaystyle\mathcal{T}_{l,s}(\bm{\theta})|_{l+1}$
$\displaystyle=\left(\left[\bm{W}^{[l+1]},\bm{0}_{m_{l+1}\times
1}\right],\bm{b}^{[l+1]}\right),$
$\displaystyle\mathcal{V}_{l,s}(\bm{\theta})|_{k}$
$\displaystyle=\left(\bm{0}_{m_{k}\times m_{k-1}},\bm{0}_{m_{k}\times
1}\right),k\neq l,l+1,$ $\displaystyle\mathcal{V}_{l,s}(\bm{\theta})|_{l}$
$\displaystyle=\left(\bm{0}_{(m_{l}+1)\times m_{l-1}},\bm{0}_{(m_{l}+1)\times
1}\right),$ $\displaystyle\mathcal{V}_{l,s}(\bm{\theta})|_{l+1}$
$\displaystyle=\left(\left[\bm{0}_{m_{l+1}\times(s-1)},-\bm{W}^{[l+1]}_{[1:m_{l+1}],s},\bm{0}_{m_{l+1}\times(m_{l}-s)},\bm{W}^{[l+1]}_{[1:m_{l+1}],s}\right],\bm{0}_{m_{l+1}\times
1}\right).$

We define one-step splitting embedding $\mathcal{T}_{l,s}^{\alpha}$ as: For
any $\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,

$\mathcal{T}_{l,s}^{\alpha}(\bm{\theta})=(\mathcal{T}_{l,s}+\alpha\mathcal{V}_{l,s})(\bm{\theta}).$

An illustration of one-step splitting method is shown in Fig. 2.

Figure 2: Illustration of one-step splitting embedding. The black neuron in
the left network is split into the blue and purple neurons in the right
network. The red (green) output weight of the black neuron in the left net is
split into two red (green) weights in the right net with ratio $(1-\alpha)$
and $\alpha$, respectively. This is also illustrated in Zhang et al. (2021b).

###### Remark 2

The parameters $\mathcal{T}_{l,0}^{\alpha}(\bm{\theta})$ and
$\mathcal{T}_{l,s}^{\alpha}(\bm{\theta})$ correspond to a $L$-layer NN with
width $(m_{0},\ldots,m_{l-1},m_{l}+1,m_{l+1},\ldots,m_{L})$ since
$\mathcal{T}_{l,0}^{\alpha}$ and $\mathcal{T}_{l,s}^{\alpha}$ are one-step
embeddings.

###### Remark 3

We observe that $\mathcal{T}_{l,0}^{\alpha}$ and $\mathcal{T}_{l,s}^{\alpha}$
can be applied on the neural network parameter $\bm{\theta}$ of any given
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ of proper depth and width, hence the
domain of $\mathcal{T}_{l,0}^{\alpha}$ and $\mathcal{T}_{l,s}^{\alpha}$ is not
limited to a specific $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$. Instead,
the extended domain of $\mathcal{T}_{l,0}^{\alpha}$ and
$\mathcal{T}_{l,s}^{\alpha}$ assembles all possible tuple class, i.e., if we
denote the extended domain of $\mathcal{T}_{l,0}^{\alpha}$ by
$\mathcal{D}_{l,0}$, then

$\mathcal{D}_{l,0}:=\bigsqcup_{l<L}\mathrm{Tuple}_{\\{n_{0},\cdots,n_{L}\\}},$
(11)

and if we denote the extended domain of $\mathcal{T}_{l,s}^{\alpha}$ by
$\mathcal{D}_{l,s}$, then

$\mathcal{D}_{l,s}:=\bigsqcup_{l<L,s\leq
n_{l}}\mathrm{Tuple}_{\\{n_{0},\cdots,n_{L}\\}},$ (12)

where $\bigsqcup$ refers to the disjoint union of different tuple classes.

By the above remark, we may extend $\mathcal{T}_{l,0}^{\alpha}$ and
$\mathcal{T}_{l,s}^{\alpha}$ to their extended domains, and we identify

$\mathcal{T}_{l,0}^{\alpha}:\mathcal{D}_{l,0}\to\mathcal{D}_{l,0},~{}~{}\mathcal{T}_{l,s}^{\alpha}:\mathcal{D}_{l,s}\to\mathcal{D}_{l,s},$

with their restrictions on $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$ for
some given $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$.

######  Theorem 1.

One-step null embedding and one-step splitting embedding are critical
embeddings.

In order to prove Theorem 1, we need several lemmas.

######  Lemma 4.5.

For any one-step null embedding $\mathcal{T}_{l,0}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,0}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, for any $l\in[L-1]$,
(i) feature vectors in $\bm{F}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal},\sigma(\alpha)\right]^{\intercal}$;
(ii) feature gradients in $\bm{G}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})^{\intercal},\sigma^{(1)}(\alpha)\right]^{\intercal}$;
(iii) error vectors in $\bm{Z}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]},0\right]^{\intercal}$;
(iv) $\mathcal{T}_{l,0}^{\alpha}$ is injective for all $\alpha$;
(v) $\mathcal{T}_{l,0}^{\alpha}$ is an affine embedding for all $\alpha$.

######  Lemma 4.6.

For any one-step splitting embedding $\mathcal{T}_{l,s}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,s}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, for any $l\in[L-1]$,
(i) feature vectors in $\bm{F}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal},(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(ii) feature gradients in $\bm{G}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})^{\intercal},(\bm{g}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(iii) error vectors in $\bm{Z}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[\left(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]}\right)^{\intercal}_{[1:s-1]},(1-\alpha)(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s},\left(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]}\right)^{\intercal}_{[s+1:m_{l}]},\alpha(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(iv) $\mathcal{T}_{l,s}^{\alpha}$ is injective for all $\alpha$.
(v) $\mathcal{T}_{l,s}^{\alpha}$ is an affine embedding for all $\alpha$.

Directly from Lemma 4.5 and Lemma 4.6, we obtain that both one-step null
embedding and one-step splitting embedding satisfy the property of output
preserving and representation preserving, and all we need is to check the
property of criticality preserving.

######  Proposition 2.

For any one-step null embedding $\mathcal{T}_{l,0}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,0}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, if
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}$, then
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

######  Proposition 3.

For any one-step splitting embedding $\mathcal{T}_{l,s}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,s}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, if
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}$, then
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

Combining altogether Lemma 4.5, Lemma 4.6, Proposition 2 and Proposition 3, we
finish our proof for Theorem 1.

###  4.2 Composition of one-step embeddings and the Embedding Principle

We first define the composition of two embeddings, which would naturally leads
to the composition of arbitrary embeddings.

######  Definition 4.7 (Composition of two embeddings).

Suppose we have an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$, and we have two
embeddings $\mathcal{T}$ and $\mathcal{T}^{\prime}$ satisfying
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$,
$\mathcal{T}^{\prime}:\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime\prime}_{0},\cdots,m^{\prime\prime}_{L}\\}}$,
with $\mathcal{T}^{\prime}$ maps the range of $\mathcal{T}$ into
$\mathrm{Tuple}_{\\{m^{\prime\prime}_{0},\cdots,m^{\prime\prime}_{L}\\}}$,
where $m^{\prime\prime}_{0}=m^{\prime}_{0}=m_{0}$,
$m^{\prime\prime}_{L}=m^{\prime}_{L}=m_{L}$, and for any $l\in[L-1]$,
$m^{\prime\prime}_{l}\geq m^{\prime}_{l}\geq m_{l}$. Since
$\mathcal{T}^{\prime}\mathcal{T}$ is obviously an injective operator, then
$\mathcal{T}^{\prime}\mathcal{T}$ is an embedding
$\mathcal{T}^{\prime}\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime\prime}_{0},\cdots,m^{\prime\prime}_{L}\\}}$,
and we term $\mathcal{T}^{\prime}\mathcal{T}$ the composition of
$\mathcal{T}^{\prime}$ and $\mathcal{T}$,i.e., for any
$\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,

$\mathcal{T}^{\prime}\mathcal{T}(\bm{\theta}):=\mathcal{T}^{\prime}(\mathcal{T}(\bm{\theta})).$

For simplicity, for any $K\in\mathbb{Z}^{+},K\geq 2$, we denote hereafter
$\prod_{l=1}^{K}\mathcal{T}_{l}:=\mathcal{T}_{K}\cdots\mathcal{T}_{1}$ as the
composition of $K$ individual embeddings
$\left\\{\mathcal{T}_{l}\right\\}_{l=1}^{K}$. For $K=1$,
$\prod_{l=1}^{1}\mathcal{T}_{l}:=\mathcal{T}_{1}$.

######  Definition 4.8 ($K$-step (Multi-step) composition embedding).

Suppose we have two vectors $\bm{l}=(l_{k})_{k=1}^{K},~{}l_{k}\in[L-1]$,
$\bm{\alpha}=(\alpha_{k})_{k=1}^{K}\subset\mathbb{R}^{K}$, and a sequence
$\\{m^{(0)}_{l}\\}_{l=1}^{L}$ with $m^{(0)}_{l}:=m_{l}$ for $l\in[L]$. Then
given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}$, a $K$-step composition embedding,
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
with $K=\sum_{l=1}^{L-1}m^{\prime}_{j}-\sum_{l=1}^{L-1}m_{l}$, is defined
recursively by the composition of $K$ one-step null embeddings or one-step
splitting embeddings.
Formally speaking, a $K$-step composition embedding
$\mathcal{T}^{\bm{\alpha}}_{\bm{l},\bm{s}}$ is defined recursively as follows:
For $n=1$, choose $s_{1}\in[m^{(0)}_{l_{1}}]\cup\\{0\\}$, then

$\mathcal{T}^{\bm{\alpha},(1)}_{\bm{l},\bm{s}}:=\mathcal{T}_{l_{1},s_{1}}^{\alpha_{1}}=\mathcal{T}_{l_{1},s_{1}}+\alpha_{1}\mathcal{V}_{l_{1},s_{1}}.$

Update the sequence from $\\{m^{(0)}_{l}\\}_{l=1}^{L}$ to
$\\{m^{(1)}_{l}\\}_{l=1}^{L}$ following: $m^{(1)}_{l}=m^{(0)}_{l}$ for
$l\in[L-1]\backslash\\{l_{1}\\}$, and $m^{(1)}_{l_{1}}=m^{(0)}_{l_{1}}+1$;
Then inductively, for $n=k$, choose $s_{k}\in[m^{(k-1)}_{l_{k}}]\cup\\{0\\}$,
then

$\mathcal{T}^{\bm{\alpha},(k)}_{\bm{l},\bm{s}}:=\mathcal{T}_{l_{k},s_{k}}^{\alpha_{k}}\mathcal{T}^{\bm{\alpha},(k-1)}_{\bm{l},\bm{s}}.$

Update the sequence from $\\{m^{(k-1)}_{l}\\}_{l=1}^{L}$ to
$\\{m^{(k)}_{l}\\}_{l=1}^{L}$ following: $m^{(k)}_{l}=m^{(k-1)}_{l}$ for
$l\in[L-1]\backslash\\{l_{k}\\}$, and $m^{(k)}_{l_{k}}=m^{(k-1)}_{l_{k}}+1$.
Finally,
$\mathcal{T}:=\mathcal{T}^{\bm{\alpha}}_{\bm{l},\bm{s}}:=\mathcal{T}^{\bm{\alpha},(K)}_{\bm{l},\bm{s}}$.

###### Remark 4

For each $i\in[K]$, $\mathcal{T}_{l_{i},s_{i}}^{\alpha_{i}}$ is regarded as
its restriction on the tuple class
$\mathrm{Tuple}_{\\{m_{0}^{(i-1)},\cdots,m_{L}^{(i-1)}\\}}\in\mathcal{D}_{l_{i},s_{i}}$,
hence

$\mathcal{T}_{l_{i},s_{i}}^{\alpha_{i}}:\mathrm{Tuple}_{\\{m_{0}^{(i-1)},\cdots,m_{L}^{(i-1)}\\}}\to\mathrm{Tuple}_{\\{m_{0}^{(i)},\cdots,m_{L}^{(i)}\\}}.$

######  Theorem 4.9.

A $K$-step composition embedding is a critical embedding.

The composition of one-step embeddings renders a feasible method to embedding
any critical point of the loss landscape of a narrow NN to a critical point
with the same output function of any wider NN, therefore, we have the
following Embedding Principle.

######  Theorem 4.10 (Embedding Principle).

Given any NN and any $K$-neuron wider NN, there exists a $K$-step composition
embedding $\mathcal{T}$ satisfying that: For any given data $S$, loss function
$\ell(\cdot,\cdot)$, activation function $\sigma(\cdot)$, given any critical
point $\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}$ of the narrower NN,
$\bm{\theta}^{\textnormal{c}}_{\textnormal{wide}}:=\mathcal{T}(\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}})$
is still a critical point of the $K$-neuron wider NN with the same output
function, i.e.,
$\bm{f}_{\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}}=\bm{f}_{\bm{\theta}^{\textnormal{c}}_{\textnormal{wide}}}$.

######  Proof 4.11.

Existence of a $K$-step composition embedding $\mathcal{T}$ can be seen from
the $K$-step construction given in Definition 4.8, and we finish the proof.

Moreover, we obtain a corollary from Theorem 4.10 stating the Embedding
Principle for the critical functions.

######  Corollary 4.12 (Embedding Principle of critical functions).

Given any NN and any wider NN, for any given data $S$, loss function
$\ell(\cdot,\cdot)$ and activation function $\sigma(\cdot)$,

$\mathcal{F}^{\textnormal{c}}_{\textnormal{narr}}\subset\mathcal{F}^{\textnormal{c}}_{\textnormal{wide}}$
(13)

where
$\mathcal{F}_{\textnormal{narr}}^{\textnormal{c}}=\\{\bm{f}_{\bm{\theta}}|\bm{\theta}\in\bm{\Theta}_{\textnormal{narr}}^{\textnormal{c}}\\}$
and
$\mathcal{F}_{\textnormal{wide}}^{\textnormal{c}}=\\{\bm{f}_{\bm{\theta}}|\bm{\theta}\in\bm{\Theta}_{\textnormal{wide}}^{\textnormal{c}}\\}$
are the sets of critical functions.

###  4.3 Importance of Embedding Principle

Mathematically speaking, Embedding Principle is a natural result of an
embedding operation that preserves output function and criticality. However,
we must emphasize the importance of stating and proving it explicitly in this
work. For a long time, researchers study the loss landscape of NN from an
optimization perspective focusing specifically on its property in the
parameter space. Lots of works make effort in tackling problems like whether
bad local minima exist, whether local minima are also global minima and
whether all saddle points are strict-saddle points, etc. However, because the
loss landscape of NN also has profound impact on its implicit regularization
and generalization performance, it is important to look into the loss
landscape from the perspective of function spaces.

Motivated by the phenomena of Frequency Principle (Xu et al., 2019, 2020;
Rahaman et al., 2019; Zhang et al., 2021a; Luo et al., 2021a) and condensation
(Luo et al., 2021b), we are very interested in the question of what are the
critical functions of an NN loss landscape that may attract the training
trajectory in the function space. Specifically, we care about whether there
are “simple” critical functions in wide NNs that may implicitly regularize the
training to help avoid overfitting. For example, in our experiments shown in
Fig. 3, we clearly observe that the training of a width-$500$ two-layer tanh-
NN in fitting $50$ data points experiences two stages. At the first stage, it
learns an output function close to the best fitting of the width-$1$ tanh-NN
and stays for a while, seemingly that it encounters a saddle point. At the
second stage, it converges to an output function close to the best fitting of
the width-$3$ tanh-NN, which interpolates all the data points. Clearly, the
complexity of the output function of the width-$500$ NN gradually increases
during the training, leading to a non-overfitting interpolation of data
despite of possessing overfitting capability. However, before studying the
universality of such training behavior clearly relevant to generalization, it
is important to have a theoretical answer to whether such “simple” critical
functions always exist even in very wide NNs.

[] [] []

Figure 3: (a) The training loss of a two-layer tanh neural network with $500$
hidden neurons. (b, c) Red solid: the DNN output at a training step, where the
blue dot and the orange dot in (a) corresponds to (b) and (c), respectively;
Black dashed: the output of the global minimum of the width-$1$ NN in (b) and
the width-$3$ NN in (c), respectively; Blue dots: training data. This is also
illustrated in Zhang et al. (2021b)

By stating and proving the Embedding Principle explicitly, we provide a clear
answer of “YES” to above question. Moreover, we unravel the exact meaning of
“simple” critical functions—critical functions of narrower networks. An
illustration of critical functions of a two-layer width-$m$ NN and a three-
layer width-$\\{m_{1},m_{2}\\}$ NN predicted by the Embedding Principle are
shown in Fig. 4(a), (b), respectively. Critical functions of the width-$500$
tanh-NN for experiments in Fig. 3 are illustrated in Fig. 4(c). Note that, by
Frequency Principle (Xu et al., 2019, 2020; Rahaman et al., 2019; Zhang et
al., 2021a; Luo et al., 2021a), we consider functions dominated by low
frequency components as “simple” functions that training of an NN is
implicitly biased to. Here, by Embedding Principle, “simple” functions are
those critical functions of narrow NNs, which signify a hierarchical structure
of fittings of training data with different complexities indicated by the
narrowerest NN a critical function belongs to. Combining with empirical
observations of Frequency Principle and condensation, we conjecture that
nonlinear training of an NN is implicitly biased towards these “simple”
critical functions. It is clearly important to look further into this
conjecture in the future works.

[] []
[]

Figure 4: Illustration of the Embedding Principle for the critical functions
of (a) two-layer width-$m$ NN and (b) three-layer width-$\\{m_{1},m_{2}\\}$
NN. (c) Some critical functions of width-$500$ tanh-NN predicted by the
Embedding Principle for experiments in Fig. 3.

##  5 General compatible critical embedding

Although the Embedding Principle has been proven above, discovering as many
critical embeddings as possible remains an important task because the more
critical embeddings we discover, the more we understand about the critical
submanifolds of an NN, e.g., their dimension and geometry, corresponding to
these critical functions of narrower NNs. In the following, we propose a much
wider class of general compatible embeddings with above class of one-step and
multi-step composition embeddings as its special cases.

To define a general compatible embedding from a narrow NN to a wide NN, we
first define mappings that establish the relation between neuron indices of
the narrow NN and neuron indices of the wide NN.

######  Definition 5.1 (Pull-back index mapping and total index mapping ).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and a wider
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, a pull-back index mapping
$\mathcal{I}:=\\{\mathcal{I}_{l}\\}_{l=0}^{L}$ from the wider NN to the
narrower NN is defined as follows: For any fixed $l\in[L-1]$,
$\mathcal{I}_{l}$ maps a neuron index $s^{\prime}\in[m^{\prime}_{l}]$ of the
wider $\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ in layer $l$ to a neuron
index $s\in[m_{l}]\sqcup\\{0\\}$ in the same layer of the narrower
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$. As for the case of $l=0$ and $l=L$,
$\mathcal{I}_{0}$ and $\mathcal{I}_{L}$ are always the identity maps since
their indices are fixed once data is given with $m^{\prime}_{0}=m_{0}=d$ and
$m^{\prime}_{L}=m_{L}=d^{\prime}$. To sum up

$\mathcal{I}_{0}:[m^{\prime}_{0}]\to[m_{0}],~{}\mathcal{I}_{l}:[m^{\prime}_{l}]\to[m_{l}]\sqcup\\{0\\}~{}\text{for}~{}l\in[L-1],~{}\mathcal{I}_{L}:[m^{\prime}_{L}]\to[m_{L}].$
(14)

Moreover, for any nonzero index $s\neq 0$, if the push-forward
$\mathcal{I}^{-1}_{l}(s)\neq\emptyset$ for all $l\in[0:L]$, we say that
$\mathcal{I}=\\{\mathcal{I}_{l}\\}_{l=0}^{L}$ is a total (pull-back) index
mapping.

######  Lemma 5.2.

For any affine embedding
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
satisfying the output preserving property, if there exist a total index
mapping $\mathcal{I}=\\{\mathcal{I}_{l}\\}_{l=0}^{L}$ from
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ to
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and auxiliary variables
$\bm{\beta}=\left\\{\bm{\beta}^{[l]}_{j}\in\mathbb{R}|~{}l\in[L],j\in[m^{\prime}_{l}]\backslash\mathcal{I}_{l}^{-1}(0)\right\\}$,
such that for any given neuron belonging to
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, located in layer $l$ with index
$j$, the following two statements hold:
(i) If $\mathcal{I}_{l}(j)\neq 0$,
$(\bm{f}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{\mathcal{I}_{l}(j)}$
and
$(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=\bm{\beta}_{j}^{[l]}(\bm{e}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{\mathcal{I}_{l}(j)}$,
(ii) If $\mathcal{I}_{l}(j)=0$,
$(\bm{f}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=\mathrm{Const}$ and
$(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=0$,
then $\mathcal{T}$ is a critical embedding.

Next, we propose a general compatible embedding method, where above embedding
methods including one-step embedding and K-step composition embedding are its
special cases.

######  Definition 5.3 (General compatible embedding).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and a wider
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, then for any total index
mapping $\mathcal{I}=\\{\mathcal{I}_{l}\\}_{l=0}^{L}$ from
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ to
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$, and for any tuple
$\bm{\alpha}:=\\{\bm{\alpha}^{[1]},\bm{\alpha}^{[1]}_{\textnormal{b}},\cdots,\bm{\alpha}^{[L]},\bm{\alpha}^{[L]}_{\textnormal{b}}\\}\in\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
satisfying some compatibility conditions (see Condition 1 and Condition 2), we
define a general embedding
$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
as: For any parameters
${\bm{\theta}_{\textnormal{narr}}}=(\bm{W}_{{\textnormal{narr}}}^{[1]},\bm{b}_{{\textnormal{narr}}}^{[1]},\cdots,\bm{W}_{{\textnormal{narr}}}^{[L]},\bm{b}_{{\textnormal{narr}}}^{[L]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,

$\displaystyle\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}(\bm{\theta}_{\textnormal{narr}}):=\Big{(}$
$\displaystyle\bm{\alpha}^{[1]}\circ\bm{W}^{[1]}_{\textnormal{inter}},\bm{\alpha}^{[1]}_{\textnormal{b}}+\bm{b}^{[1]}_{\textnormal{inter}},\cdots,$
$\displaystyle\bm{\alpha}^{[l]}\circ\bm{W}^{[l]}_{\textnormal{inter}},\bm{\alpha}^{[l]}_{\textnormal{b}}+\bm{b}^{[l]}_{\textnormal{inter}},\cdots,$
$\displaystyle\bm{\alpha}^{[L]}\circ\bm{W}^{[L]}_{\textnormal{inter}},\bm{\alpha}^{[L]}_{\textnormal{b}}+\bm{b}^{[L]}_{\textnormal{inter}}\Big{)},$

where
$\bm{W}^{[l]}_{\textnormal{inter}}:=\left[\left(\bm{W}^{[l]}_{\textnormal{narr}}\right)_{\mathcal{I}_{l}(i),\mathcal{I}_{l-1}(j)}\right]$,
$\bm{b}^{[l]}_{\textnormal{inter}}:=\left(\left(\bm{b}^{[l]}_{\textnormal{narr}}\right)_{\mathcal{I}_{l}(k)}\right)$
for $l\in[L]$ with $i,~{}k\in[m_{l}^{\prime}]$, $j\in[m^{\prime}_{l-1}]$, and
$\circ$ is the the Hadamard product.

###### Remark 5

Since $\mathcal{I}_{l}:[m^{\prime}_{l}]\to[m_{l}]\sqcup\\{0\\}$ for
$l\in[L-1]$, and the components in $\bm{W}^{[l]}_{\textnormal{narr}}$ and
$\bm{b}^{[l]}_{\textnormal{narr}}$ are not defined for zero indices, i.e., no
definitions can be found for $(\bm{W}^{[l]}_{\textnormal{narr}})_{0j}$,
$(\bm{W}^{[l]}_{\textnormal{narr}})_{i0}$,
$(\bm{b}^{[l]}_{\textnormal{narr}})_{0}$, for any $l\in[L-1]$ with
$i\in[m_{l}]$ and $j\in[m_{l-1}]\sqcup\\{0\\}$, for convenience of expression,
we set $(\bm{W}^{[l]}_{\textnormal{narr}})_{0j}=1$,
$(\bm{W}^{[l]}_{\textnormal{narr}})_{i0}=1$, and
$(\bm{b}^{[1]}_{\textnormal{narr}})_{0}=0$, with $i\in[m_{l}]$ and
$j\in[m_{l-1}]\sqcup\\{0\\}$.

Now we proceed to state out the certain conditions for the tuple

$\bm{\alpha}=\\{\bm{\alpha}^{[1]},\bm{\alpha}^{[1]}_{\textnormal{b}},\cdots,\bm{\alpha}^{[L]},\bm{\alpha}^{[L]}_{\textnormal{b}}\\}\in\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
(15)

in Definition 5.3.

######  Condition 1 (Compatibility conditions I (see Fig. 5 for illustration))

The elements $\\{\bm{\alpha}^{[l]}\\}_{l=1}^{L}$ in (15) satisfy that:
There exist a collection of auxiliary variables
$\bm{\beta}:=\left\\{\bm{\beta}^{[l]}_{j}\in\mathbb{R}|~{}l\in[0:L],~{}j\in[m^{\prime}_{l}]\backslash\mathcal{I}_{l}^{-1}(0)\right\\}$
such that

  * •

$\bm{\beta}^{[L]}_{k}=1$ for $k\in[m^{\prime}_{L}]$. (Since $\mathcal{I}_{L}$
is the identity map, $\mathcal{I}_{L}^{-1}(0)=\emptyset$).

  * •

Forward conditions:

    * –

Effective neurons forward to an effective neurons: For
$i\notin\mathcal{I}^{-1}_{l}(0)$, $s\in[m_{l-1}]$, we have
$\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\bm{\alpha}^{[l]}_{ij}=1$;

    * –

Effective neurons forward to a null neuron: For $i\in\mathcal{I}^{-1}_{l}(0)$,
$s\in[m_{l-1}]$, we have
$\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\bm{\alpha}^{[l]}_{ij}=0$.

  * •

Backward conditions:

    * –

Effective neurons backpropagate to an effective neuron: For
$j\notin\mathcal{I}^{-1}_{l-1}(0)$, $k\in[m_{l}]$, we have
$\sum_{i\in\mathcal{I}^{-1}_{l}(k)}\bm{\beta}^{[l]}_{i}\bm{\alpha}^{[l]}_{ij}=\bm{\beta}^{[l-1]}_{j}$;

    * –

Effective neurons backpropagate to a null neuron: For
$j\in\mathcal{I}^{-1}_{l-1}(0)$, $k\in[m_{l}]$, we have
$\sum_{i\in\mathcal{I}^{-1}_{l}(k)}\bm{\beta}^{[l]}_{i}\bm{\alpha}^{[l]}_{ij}=0$.

Figure 5: Illustration of forward and backward compatibility conditions I for
$\bm{\alpha}^{[l]}$.

The compatibility conditions for
$\\{\bm{\alpha}^{[l]}_{\textnormal{b}}\\}_{l=1}^{L}$ is stated in the
following. In order for that, we need another collection of auxiliary
variables
$\bm{B}_{*}:=\left\\{(\bm{b}^{[l]}_{*})_{i}\in\mathbb{R}|~{}l\in[0:L],~{}i\in\mathcal{I}_{l}^{-1}(0)\right\\}$.
We term $\bm{B}_{*}$ _the effective biases for null neurons._

######  Condition 2 (Compatiblity conditions II (see Fig. 6 for illustration))

The rest of the elements in $\bm{\alpha}$, i.e.,
$\\{\bm{\alpha}^{[l]}_{\textnormal{b}}\\}_{l=1}^{L}$ satisfy that:
For any effective biases of null neurons
$\bm{B}_{*}:=\left\\{(\bm{b}^{[l]}_{*})_{i}\in\mathbb{R}|~{}l\in[0:L],~{}i\in\mathcal{I}_{l}^{-1}(0)\right\\}$,
we have

  * •

Effective neurons: $(\bm{\alpha}_{\textnormal{b}}^{[l]})_{i}=0$ for any
$l\in[L]$ with $i\notin\mathcal{I}_{l}^{-1}(0)$;

  * •

Null neurons to a null neuron: for $i\in\mathcal{I}^{-1}_{l}(0)$, $s=0$, we
have
$\sum_{j\in\mathcal{I}^{-1}_{l-1}(0)}\bm{\alpha}^{[l]}_{ij}\sigma((\bm{b}^{[l-1]}_{*})_{j})+(\bm{\alpha}_{\textnormal{b}}^{[l]})_{i}=(\bm{b}^{[l]}_{*})_{i}$;

  * •

Null neurons to an effective neuron: for $i\notin\mathcal{I}^{-1}_{l}(0)$,
$s=0$, we have
$\sum_{j\in\mathcal{I}^{-1}_{l-1}(0)}\bm{\alpha}^{[l]}_{ij}\sigma((\bm{b}^{[l-1]}_{*})_{j})+(\bm{\alpha}_{\textnormal{b}}^{[l]})_{i}=0$;

Figure 6: Illustration of compatibility conditions II for
$\bm{\alpha}^{[l]}_{\textnormal{b}}$.

We then illustrate the general compatible embedding as follows. First, we
illustrate an example of the general compatible embedding without null neurons
through the forward conditions in Fig. 7 and the backward conditions in Fig.
8. Second, we illustrate the conditions related to null neurons in Fig. 9.

Figure 7: Illustration of the forward conditions for split neurons in
compatibility conditions I. The sum of the input weights from neurons that are
split from the same previous neuron to a post neuron should be equal to the
weight from the previous to the post neuron.  Figure 8: Illustration of the
backward conditions for split neurons in compatibility conditions I. The
gradient of the loss w.r.t. to the neuron output of the wide network is
proportional to the gradient of the loss w.r.t. the corresponding neuron in
the narrow network.  Figure 9: Illustration of compatibility conditions for
null neurons. Red: The input from effective neurons split from the same neuron
should cancel out. Yellow: the effective bias of a null neuron is the sum of
its bias (can be any value) and its input from other null neurons. Purple: The
added null neurons have constant input to the effective neuron, which would be
added a bias correction to cancel the constant input. Purple+Green: the
backward condition of a null neuron leads to the zero gradient.

######  Theorem 5.4.

General compatible embedding is a critical embedding.

Remark that we later name it as general compatible critical embedding in this
work.

###  5.1 Special cases of general compatible critical embedding

In the following, we present some special cases of general compatible critical
embedding. Specifically, the three-fold global splitting embedding is the key
to the proof of a necessary condition of a “truly-bad” critical point in
Section 6.

######  Definition 5.5 (Splitting embedding).

For a general compatible critical embedding
$\mathcal{T}_{\mathcal{I}}^{\bm{\alpha}}$, if there is no null neuron in the
embedded NN, i.e., $\mathcal{I}^{-1}_{l}(0)=\emptyset$ for any $l\in[L-1]$,
then we call $\mathcal{T}_{\mathcal{I}}^{\bm{\alpha}}$ a splitting embedding.

######  Definition 5.6 (Null embedding).

For a general compatible critical embedding
$\mathcal{T}_{\mathcal{I}}^{\bm{\alpha}}$, if only null neurons are added,
i.e., $\\#\mathcal{I}^{-1}_{l}(0)=m^{\prime}_{l}-m_{l}$ for any $l\in[L-1]$,
hence there is no neuron splitting, i.e., $\\#\mathcal{I}^{-1}_{l}(s)=1$ for
any $l\in[L-1]$, $s\in[m_{l}]$, then we call
$\mathcal{T}_{\mathcal{I}}^{\bm{\alpha}}$ a null embedding.

###### Remark 6

One-step null embedding and its multi-step composition are special cases of
null embedding. Similarly, one-step splitting embedding and its multi-step
composition are special cases of splitting embedding. Multi-step embedding
composed by a mixture of one-step null and splitting embedding is a special
case of general compatible critical embedding.

######  Example 5.7 (A three-fold global splitting embedding).

For any $l\in[L-1]$, we define the operator $\mathcal{T}_{\mathrm{global}}$
applying on $\bm{\theta}$ as follows

$\displaystyle\mathcal{T}_{\mathrm{global}}(\bm{\theta})|_{l}$
$\displaystyle=\left({\begin{bmatrix}\bm{W}^{[l]}&\bm{0}&\bm{0}\\\
\bm{0}&\bm{W}^{[l]}&\bm{0}\\\ \bm{0}&\bm{0}&\bm{W}^{[l]}\\\
\end{bmatrix}},\left[{\begin{array}[]{cc}\bm{b}^{[l]}\\\ \bm{b}^{[l]}\\\
\bm{b}^{[l]}\\\ \end{array}}\right]\right),$
$\displaystyle\mathcal{T}_{\mathrm{global}}(\bm{\theta})|_{L}$
$\displaystyle=\left(\left[\bm{W}^{[L]},\bm{W}^{[L]},-\bm{W}^{[L]}\right],\bm{b}^{[L]}\right),$

######  Remark 5.8.

For this global splitting embedding, $m^{\prime}_{l}=3m_{l}$ and
$\mathcal{I}^{-1}_{l}(s)=\\{s,s+m_{l},s+2m_{l}\\}$ for any $l\in[L-1]$ and
$s\in[m_{l}]$. For any $l\in[L-1]$,

$\bm{\alpha}^{[l]}=\begin{bmatrix}\mathbf{1}_{m_{l}\times
m_{l-1}}&\bm{0}_{m_{l}\times m_{l-1}}&\bm{0}_{m_{l}\times m_{l-1}}\\\
\bm{0}_{m_{l}\times m_{l-1}}&\mathbf{1}_{m_{l}\times
m_{l-1}}&\bm{0}_{m_{l}\times m_{l-1}}\\\ \bm{0}_{m_{l}\times
m_{l-1}}&\bm{0}_{m_{l}\times m_{l-1}}&\mathbf{1}_{m_{l}\times m_{l-1}}\\\
\end{bmatrix},$ $\bm{\alpha}_{\textnormal{b}}^{[l]}=\bm{0}_{3m_{l}\times 1},$

and

$\bm{\alpha}^{[L]}=\begin{bmatrix}\mathbf{1}_{m_{l}\times
m_{l-1}}&\mathbf{1}_{m_{l}\times m_{l-1}}&-\mathbf{1}_{m_{l}\times m_{l-1}}\\\
\end{bmatrix},$ $\bm{\alpha}_{\textnormal{b}}^{[l]}=\bm{0}_{m_{L}\times 1}.$

Moreover, for any $l\in[L-1]$, $\bm{\beta}^{[l]}_{j}=1$ when $j\in[2m_{l}]$
and $\bm{\beta}^{[l]}_{j}=-1$ when $j\in[2m_{l}+1:3m_{l}]$. It is a special
case of splitting embedding.

##  6 Analysis of critical points/submanifolds by critical embeddings

###  6.1 Degeneracy of critical points/submanifolds

A key observation to the critical embeddings proposed above is that it is not
unique. Actually, given any NN and a wider NN, there is a class of critical
embeddings. Therefore, any critical point can be embedded to a set of critical
points in a wider NN. By a $K$-step composition embedding, because embedding
$\mathcal{T}_{l_{i},s_{i}}^{\alpha_{i}}$ at each step $i$ has one degree of
freedom parameterized by $\alpha_{i}$ given $l_{i}$ and $s_{i}$, one critical
point in general can be embedded to a $K$-dimensional critical affine
subspace, which provides a lower bound to the degeneracy of embedded critical
points. Precisely, in Zhang et al. (2021b), we prove the following theorem
using composition of one-step splitting embeddings.

######  Theorem 6.1 (Theorem 2 in Zhang et al. (2021b)).

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and a $K$-neuron wider
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, then for any critical point
$\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}=\left(\bm{W}^{[1]},\bm{b}^{[1]},\cdots,\bm{W}^{[L]},\bm{b}^{[L]}\right)$
satisfying $\bm{W}^{[l]}\neq\bm{0}$ for each $l\in[L]$,
$\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}$ can be critically embedded
to a $K$-dimensional critical affine subspace
$\mathcal{M}_{\textnormal{wide}}=\\{\bm{\theta}_{\textnormal{wide}}+\sum_{i=1}^{K}\alpha_{i}\bm{\mu}_{i}|\alpha_{i}\in\mathbb{R}\\}$
of loss landscape of $\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$. Here
$\bm{\theta}_{\textnormal{wide}}:=(\prod_{l=1}^{K}\mathcal{T}_{l_{l},s_{l}})(\bm{\theta}_{\textnormal{narr}})$
and
$\bm{\mu}_{i}:=\mathcal{T}_{l_{K},s_{K}}\cdots\mathcal{V}_{l_{i},s_{i}}\cdots\mathcal{T}_{l_{1},s_{1}}(\bm{\theta}_{\textnormal{narr}})$,
where $s_{l}\neq 0$ for all $l\in[K]$. (The definitions of
$\mathcal{V}_{l_{l},s_{l}}$ and $\mathcal{T}_{l_{l},s_{l}}$ can be found in
Definition 4.4).

In addition, in this work, as we propose above a wider class of general
compatible critical embeddings, we attempt to obtain a better estimate of the
dimension of critical submanifolds corresponding to any given critical
function $\bm{f}_{\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}}$ of a
narrow NN. A gross estimate yields the following heuristic argument.

###### Heuristic argument

Given any total index mapping $\mathcal{I}$, the degree of freedom of all
possible $\bm{\alpha}$ for general compatible critical embedding
$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ to a $K$-neuron wider NN is
$K+\sum_{l\in[L]}K_{l}K_{l-1}$, where $K_{l}:=m^{\prime}_{l}-m_{l}$, and
$K:=\sum_{l\in[L-1]}K_{l}$.

###### Justification

By the definition of general compatible critical embedding,
$\\{\bm{\alpha}^{[l]}\\}_{l=1}^{L}$ and auxiliary variables
$\bm{\beta}=\left\\{\bm{\beta}^{[l]}_{j}\in\mathbb{R}|~{}l\in[L],j\in[m^{\prime}_{l}]\backslash\mathcal{I}_{l}^{-1}(0)\right\\}$
with $\bm{\beta}^{[L]}_{k}=\bm{1}$ satisfy forward and backward compatibility
conditions.

Step 1: We first observe that
$\sum_{i\in\mathcal{I}^{-1}_{l}(s)}\bm{\beta}_{i}^{[l]}=1$ for any
$s\in[m_{l}]$. Thus, $\bm{\beta}$ has $K-m_{\mathrm{null}}$ degrees of
freedom, where $m_{\mathrm{null}}$ is the number of null neurons.

Step 2: Given any such $\bm{\beta}$, we now consider the degrees of freedom
for $\\{\bm{\alpha}^{[l]}\\}_{l=1}^{L}$. Note that forward and backward
conditions are not independent of one another because

$\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\sum_{i\in\mathcal{I}^{-1}_{l}(k)}\bm{\beta}^{[l]}_{i}\bm{\alpha}^{[l]}_{ij}=\sum_{i\in\mathcal{I}^{-1}_{l}(k)}\bm{\beta}^{[l]}_{i}=1=\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\bm{\beta}^{[l-1]}_{j}$

automatically holds for the given $\bm{\beta}$. Therefore, there are
$m^{\prime}_{l}m_{l-1}+m_{l}m^{\prime}_{l-1}-m_{l}m_{l-1}$ independent linear
equations for $m^{\prime}_{l}m^{\prime}_{l-1}$ parameters in
$\bm{\alpha}^{[l]}$ for each layer $l$, resulting in
$\sum_{l\in[L]}K_{l}K_{l-1}$ degrees of freedom in total.

Step 3: Given any effective biases $\bm{B}_{*}$ as auxiliary variables for all
null neurons and any $\bm{\alpha}^{[l]}$ satisfying forward and backward
conditions, $(\bm{\alpha}_{\textnormal{b}}^{[l]})_{i}$ is uniquely determined
for all neurons in the wide NN. Therefore, there are $m_{\mathrm{null}}$
degrees of freedom in $\bm{B}_{*}$.

In the end, the degrees of freedom in $\bm{\alpha}$ is the summation of
degrees of freedom in auxiliary variables $\bm{\beta}$, degrees of freedom in
$\\{\bm{\alpha}^{[l]}\\}_{l=1}^{L}$ given $\bm{\beta}$ and additional degrees
of freedom in $\bm{B}_{*}$ for all null neurons, which add up to
$K+\sum_{l\in[L]}K_{l}K_{l-1}$ degrees of freedom.

Intuitively, degrees of freedom in critical embedding $\mathcal{T}$ transform
into dimensions of critical submanifolds, resulting in a higher estimate of
degrees of degeneracy $K+\sum_{l\in[L]}K_{l}K_{l-1}$ in comparision to $K$
obtained by multi-step composition embedding in Zhang et al. (2021b). We note
that the nonlinear coupling between $\bm{\alpha}$ and $\bm{\beta}$ in general
results in non-affine curved critical submanifolds for three-layer or deeper
NNs containing the corresponding $K$-dimensional critical affine subspaces
identified in Theorem 6.1. A more rigorous estimate requires careful handling
of the nonlinear coupling. We leave it to later works.

###  6.2 Irreversible transition to strict-saddle point

In this subsection, we look further into the transition between different
types of critical points, e.g., local minima, saddle points, through critical
embeddings. We are specifically interested in the transition of a critical
point to a strict-saddle point due to its good optimization guarantee detailed
in Lee et al. (2019). We prove the following irreversibility property for any
critical embedding, which guarantees that a strict-saddle point always embedds
to strict-saddle points.

######  Theorem 6.2.

Given an $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and any of its parameters
$\bm{\theta}\in\mathbb{R}^{M}$, for any critical embedding
$\mathcal{T}:\mathbb{R}^{M}\to\mathbb{R}^{M^{\prime}}$ to any wider
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, the number of positive, zero,
negative eigenvalues of $\bm{H}_{S}(\mathcal{T}(\bm{\theta}))$ is no less than
the counterparts of $\bm{H}_{S}(\bm{\theta})$.

###  6.3 “Truly-bad” critical point

The above irreversibility property of any critical embedding provokes the
following thought about a conventional bad local minimum: for any bad local
minimum of a given NN, if it can become a strict-saddle point in wider NNs,
then it should not be a problem as we can simply use a wider NN in practice.
However, there is still a “truly-bad” situation in which a critical point may
never become a strict-saddle point through any critical embedding. In the
following, through proving a stringent necessary condition for such a “truly-
bad” critical point defined below, we justify its rarity, hence providing a
reasonable conjecture for the easy optimization of wide NNs widely observed in
practice.

We denote hereafter that $\bm{A}\succeq\bm{B}$ if and only if $\bm{A}-\bm{B}$
is a semi-positive definite matrix, and $\bm{A}\succ\bm{B}$ if and only if
$\bm{A}-\bm{B}$ is a strictly positive definite matrix.

######  Definition 6.3 ("Truly-bad" critical point).

Given any data $S$, loss $\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$,
for any NN, if there exists a critical point
$\bm{\theta}^{\textnormal{c}}\in\bm{\Theta}^{\textnormal{c}}$ satisfying that:
(i) $\bm{\theta}^{\textnormal{c}}$ is not a strict-saddle point (Lee et al.,
2019, Definition 1);
(ii) For any critical embedding $\mathcal{T}$,
$\mathcal{T}(\bm{\theta}^{\textnormal{c}})$ is also not a strict-saddle point,
then we term this critical point a "truly-bad" critical point.

We would like to introduce some additional notations in order to state Lemma
6.4 and Lemma 6.5. We denote

$\bm{H}^{(1),[L-1]}_{S}(\bm{\theta}):=\sum_{i,j=1}^{m_{L}}\mathbb{E}_{S}\partial_{ij}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\nabla_{\bm{\theta}^{[L-1]}}(\bm{f}_{\bm{\theta}})_{i}\left(\nabla_{\bm{\theta}^{[L-1]}}(\bm{f}_{\bm{\theta}})_{j}\right)^{\intercal},$

and

$\bm{H}^{(2),[L-1]}_{S}(\bm{\theta}):=\sum_{i,j=1}^{m_{L}}\mathbb{E}_{S}\partial_{i}\ell(\bm{f}_{\bm{\theta}},\bm{f}^{*})\bm{W}_{i,j}^{[L]}\nabla_{\bm{\theta}^{[L-1]}}\nabla_{\bm{\theta}^{[L-1]}}\left(\bm{f}_{\bm{\theta}}^{[L-1]}\right)_{j}.$

We denote further that
$\bm{H}^{[L-1]}_{S}(\bm{\theta}):=\bm{H}^{(1),[L-1]}_{S}(\bm{\theta})+\bm{H}^{(2),[L-1]}_{S}(\bm{\theta})$.

We state Lemma 6.4 and Lemma 6.5 as follows.

######  Lemma 6.4.

Given any data $S$, loss $\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$,
for any NN, if a critical point
$\bm{\theta}^{\textnormal{c}}\in\bm{\Theta}^{\textnormal{c}}$ satisfies:
(i) $\bm{H}_{S}(\bm{\theta}^{\textnormal{c}})\succeq 0$;
(ii) $\bm{H}^{(2),[L-1]}_{S}(\bm{\theta}^{\textnormal{c}})\neq\mathbf{0}$,
then there exists a general compatible critical embedding $\mathcal{T}$, such
that $\mathcal{T}(\bm{\theta}^{\textnormal{c}})$ is a strict-saddle point.

######  Lemma 6.5.

Given any data $S$, loss $\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$,
for any NN, if a critical point
$\bm{\theta}^{\textnormal{c}}\in\bm{\Theta}^{\textnormal{c}}$ satisfies:
(i) $\bm{H}_{S}(\bm{\theta}^{\textnormal{c}})\succeq 0$;
(ii) $\bm{H}^{(2),[L-1]}_{S}(\bm{\theta}^{\textnormal{c}})=\mathbf{0}$;
(iii) $\bm{H}^{(2)}_{S}(\bm{\theta}^{\textnormal{c}})\neq\mathbf{0}$.
Then there exist a general compatible critical embedding $\mathcal{T}$, such
that $\mathcal{T}(\bm{\theta})$ is a strict-saddle point.

######  Theorem 6.6.

Given any data $S$, loss $\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$,
for any NN, if a critical point $\bm{\theta}^{\textnormal{c}}$ with
$\bm{H}_{S}(\bm{\theta}^{\textnormal{c}})\succeq 0$ satisfies
$\bm{H}^{(2)}_{S}(\bm{\theta}^{\textnormal{c}})\neq\mathbf{0}$, then there
exist a general compatible critical embedding $\mathcal{T}$ such that
$\mathcal{T}(\bm{\theta}^{\textnormal{c}})$ is a strict-saddle point, i.e.,
$\bm{H}_{S}(\mathcal{T}(\bm{\theta}^{\textnormal{c}}))$ has at least one
negative eigenvalue.

######  Proof 6.7.

This can be directly obtained by Lemma 6.4 and 6.5.

######  Theorem (short version of Theorem 6.6)

$\bm{H}^{(2)}_{S}(\bm{\theta}^{\textnormal{c}})=\bm{0}$ is a necessary
condition for a critical point $\bm{\theta}^{\textnormal{c}}$ being a "truly-
bad" critical point.

##  7 Conclusion and discussion

In this work, we prove the Embedding Principle that loss landscape of an NN
_contains_ all critical points/functions of all the narrower NNs. We define
the critical embedding, which serves as the key tool not only to the proof of
Embedding Principle but also to the study of the general geometry of loss
landscape. Importantly, we discover a wide class of general compatible
embedding, by which we obtain rich understanding about the critical
points/submanifolds, e.g., their degree of degeneracy, their easy and
irreversible transition to strict-saddle points.

The general compatible embedding proposed in this work unravels that the
embedding relation from a critical point of the loss landscape of a narrow NN
to critical points of the loss landscape of any wide NN is not limited by the
composition of adding neurons one by one, but can be a collective operation.
As a consequence, all critical points of a wide NN embedded from a critical
point of a narrower NN by all possible general compatible critical embeddings,
form high-dimensional critical submanifolds which in general are not affine
subspaces for three-layer or deeper NNs. It is interesting and important.
However, it remains a problem for the future study about whether the general
compatible embeddings in certain sense are all the critical embeddings.

Embedding Principle provides an integrated view about loss landscapes of NNs
with different widths. Specifically, it informs us that the existence of bad
local minimum in a NN with a fixed width may not be a big deal for
optimization as long as it can become a strict-saddle point in wider NNs,
i.e., not a “truly-bad” critical point. In this work, we prove a stringent
necessary condition for a “truly-bad” critical point. Still, it remains a
problem about whether non-trivial “truly-bad” critical points indeed exist,
and whether they are indeed a headache for optimization.

We emphasize that Embedding Principle provides a function space view on the
critical points /submanifolds of loss landscape, which is of great importance
for studying the implicit regularization and generalization of NNs. In recent
years, it has been more and more clear that optimization and generalization
are heavily intertwined with one another for deep learning. Therefore, one can
not expect to develop a deep learning theory with optimization theory and
generalization theory established separately. Yet, for a long time, the study
of loss landscape focuses mainly on the parameter space in pursuit of an
optimization guarantee. On the other hand, the study of generalization focuses
mainly on the function space, failing to incorporate the geometry of loss
landscape in parameter space which is key to the training. Now, by the
Embedding Principle, we see a hierarchical structure of critical functions of
different complexities of the loss landscape, which originate from loss
landscape with clear optimization implication while being amenable to the
analysis of complexity with clear generalization implication. Such a critical
function hierarchy reflects the degree of matching between the NN architecture
and data, i.e., if critical functions of narrow NNs attain low training error,
then the NN architecture well matches the target function and may obtain a
well generalized solution through training like in Fig. 3. Though, more works
need to be done to unravel the full details and implication of this critical
function hierarchy, we believe it is an important piece and may be a key to
the deep learning theory.

## Acknowledgments

This work is sponsored by the National Key R&D Program of China Grant No.
2019YFA0709503 (Z. X.), the Shanghai Sailing Program, the Natural Science
Foundation of Shanghai Grant No. 20ZR1429000 (Z. X.), the National Natural
Science Foundation of China Grant No. 62002221 (Z. X.), the National Natural
Science Foundation of China Grant No. 12101401 (T. L.), the National Natural
Science Foundation of China Grant No. 12101402 (Y. Z.), Shanghai Municipal of
Science and Technology Project Grant No. 20JC1419500 (Y.Z.), Shanghai
Municipal of Science and Technology Major Project No. 2021SHZDZX0102, and the
HPC of School of Mathematical Sciences and the Student Innovation Center at
Shanghai Jiao Tong University.

##  Appendix A Theoretical details

######  Lemma (Lemma 4.5 in main text.)

For any one-step null embedding $\mathcal{T}_{l,0}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,0}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, for any $l\in[L-1]$,
(i) feature vectors in $\bm{F}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal},\sigma(\alpha)\right]^{\intercal}$;
(ii) feature gradients in $\bm{G}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})^{\intercal},\sigma^{(1)}(\alpha)\right]^{\intercal}$;
(iii) error vectors in $\bm{Z}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]},0\right]^{\intercal}$;
(iv) $\mathcal{T}_{l,0}^{\alpha}$ is injective for all $\alpha$;
(v) $\mathcal{T}_{l,0}^{\alpha}$ is an affine embedding for all $\alpha$.

######  Proof A.1.

(i) By the construction of $\bm{\theta}_{\textnormal{wide}}$, it is clear that
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for all $l^{\prime}\in[l-1]$. Then

$\displaystyle\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\sigma\left(\left[{\begin{array}[]{cc}\bm{W}^{[l]}\\\
\bm{0}_{1\times m_{l-1}}\\\
\end{array}}\right]\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}}+\left[{\begin{array}[]{cc}\bm{b}^{[l]}\\\
\alpha\\\
\end{array}}\right]\right)=\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
\sigma(\alpha)\\\ \end{array}}\right].$ (22)

Note that since

$\alpha\left[\bm{0}_{m_{l+1}\times{(m_{l}+1)}}\right]\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
\sigma(\alpha)\\\ \end{array}}\right]=\bm{0}_{m_{l+1}\times 1}$

Thus

$\displaystyle\bm{f}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\sigma\left(\left[\bm{W}^{[{l+1}]},\bm{0}_{m_{l+1}\times
1}\right]\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
\sigma(\alpha)\\\ \end{array}}\right]+\bm{0}_{m_{l+1}\times
1}+\bm{b}^{[l+1]}+\alpha~{}\bm{0}_{m_{l+1}\times
1}\right)=\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l+1]}.$ (25)

Next, by the construction of $\bm{\theta}_{\textnormal{wide}}$, it is clear
that
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for any $l^{\prime}\in[l+1:L]$.

(ii) The results for feature gradients
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for $l^{\prime}\in[L]$ can be calculated in a similar way except by replacing
$\sigma(\cdot)$ with $\sigma^{(1)}(\cdot)$.

(iii) By the backpropagation and the above facts in (i), we have

$\bm{z}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\nabla\ell(\bm{f}^{[L]}_{\bm{\theta}_{\textnormal{wide}}},\bm{y})=\nabla\ell(\bm{f}^{[L]}_{\bm{\theta}_{\textnormal{narr}}},\bm{y})=\bm{z}^{[L]}_{\bm{\theta}_{\textnormal{narr}}}.$

Recall the recurrence relation for $l^{\prime}\in[l+1:L-1]$, then we
recursively obtain the following equality for $l^{\prime}$ from $L-1$ down to
$l+1$:

$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=(\bm{W}^{[l^{\prime}+1]})^{\intercal}\left(\bm{z}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{wide}}}\circ\bm{g}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{wide}}}\right)=(\bm{W}^{[l^{\prime}+1]})^{\intercal}\left(\bm{z}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{narr}}}\circ\bm{g}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{narr}}}\right)=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l^{\prime}]}.$
(26)

Next,

$\displaystyle\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\left(\left[\bm{W}^{[{l+1}]},\bm{0}_{m_{l+1}\times
1}\right]+\alpha\left[\bm{0}_{m_{l+1}\times{(m_{l}+1)}}\right]\right)^{\intercal}\left(\bm{z}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}\circ\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}\right)$
$\displaystyle=\left[{\begin{array}[]{cc}\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
0\\\ \end{array}}\right]+\left[\bm{0}_{{(m_{l}+1)\times
1}}\right]=\left[\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]},0\right]^{\intercal}.$
(29)

Finally,

$\displaystyle\bm{z}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\left[{\begin{array}[]{cc}{\bm{W}^{[l]}}^{\intercal},\bm{0}_{m_{l-1}\times
1}\\\
\end{array}}\right]\left(\left[{\begin{array}[]{cc}\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
0\\\
\end{array}}\right]\circ\left[{\begin{array}[]{cc}\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
\sigma^{(1)}(\alpha)\\\ \end{array}}\right]\right)$ (35)
$\displaystyle=(\bm{W}^{[l]})^{\intercal}\left(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\circ\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\right)+\bm{0}_{m_{l-1}\times
1}=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l-1]}.$ (36)

This with the recurrence relation once again leads to
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l^{\prime}]}$
for all $l^{\prime}\in[l-1]$.

(iv) If for
$\bm{\theta}_{1},\bm{\theta}_{2}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
and $\bm{\theta}_{1}\neq\bm{\theta}_{2}$, since
$\mathcal{T}_{l,0}^{\alpha}|_{k}$ for $k\neq l,l+1$ is the identity map, then
if there exists some $k_{0}\neq l,l+1$, such that
$\bm{W}_{1}^{[k_{0}]}\neq\bm{W}_{2}^{[k_{0}]}$ or
$\bm{b}_{1}^{[k_{0}]}\neq\bm{b}_{2}^{[k_{0}]}$, then obviously
$\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{1})\neq\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{2})$.
If $k_{0}=l$ or $k_{0}=l+1$, by similar reasoning,
$\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{1})\neq\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{2})$.

(v) For
$\bm{\theta}_{0}=(\bm{W}_{0}^{[1]},\bm{b}_{0}^{[1]},\cdots,\bm{W}_{0}^{[L]},\bm{b}_{0}^{[L]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,
we have

$\tilde{\mathcal{T}}_{l,0}^{\alpha}(\bm{\theta}_{0})=\left(\bm{W}_{0}^{[1]},\bm{b}_{0}^{[1]},\cdots,\left[{\begin{array}[]{cc}\bm{W}_{0}^{[l]}\\\
\bm{0}_{1\times m_{l-1}}\\\
\end{array}}\right],\left[{\begin{array}[]{cc}\bm{b}_{0}^{[l]}\\\ 0\\\
\end{array}}\right],\left[\bm{W}_{0}^{[l+1]},\bm{0}_{m_{l+1}\times
1}\right],\bm{b}_{0}^{[l+1]},\cdots,\bm{W}_{0}^{[L]},\bm{b}_{0}^{[L]}\right),$

obviously $\tilde{\mathcal{T}}_{l,0}^{\alpha}$ is a linear operator, thus
$\mathcal{T}_{l,0}^{\alpha}$ is an affine operator.

######  Lemma (Lemma 4.6 in main text)

For any one-step splitting embedding $\mathcal{T}_{l,s}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,s}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, for any $l\in[L-1]$,
(i) feature vectors in $\bm{F}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal},(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(ii) feature gradients in $\bm{G}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})^{\intercal},(\bm{g}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(iii) error vectors in $\bm{Z}_{\bm{\theta}_{\textnormal{wide}}}$:
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$,
for $l^{\prime}\in[L]$ and $l^{\prime}\neq l$,
$\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}=\left[\left(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]}\right)^{\intercal}_{[1:s-1]},(1-\alpha)(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s},\left(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]}\right)^{\intercal}_{[s+1:m_{l}]},\alpha(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}$;
(iv) $\mathcal{T}_{l,s}^{\alpha}$ is injective for all $\alpha$.
(v) $\mathcal{T}_{l,s}^{\alpha}$ is an affine embedding for all $\alpha$.

######  Proof A.2.

(i) By the construction of $\bm{\theta}_{\textnormal{wide}}$, it is clear that
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for all $l^{\prime}\in[l-1]$. Then

$\displaystyle\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\sigma\left(\left[{\begin{array}[]{cc}\bm{W}^{[l]}\\\
\bm{W}^{[l]}_{s,[1:m_{l-1}]}\\\
\end{array}}\right]\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}}+\left[{\begin{array}[]{cc}\bm{b}^{[l]}\\\
\bm{b}^{[l]}_{s}\\\
\end{array}}\right]\right)=\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\\\ \end{array}}\right].$
(43)

Note that

$\alpha\left[\bm{0}_{m_{l+1}\times(s-1)},-\bm{W}^{[l+1]}_{[1:m_{l+1}],s},\bm{0}_{m_{l+1}\times(m_{l}-s)},\bm{W}^{[l+1]}_{[1:m_{l+1}],s}\right]\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\\\
\end{array}}\right]=\bm{0}_{m_{l+1}\times 1}.$

Thus

$\displaystyle\bm{f}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\sigma\left(\left[\bm{W}^{[{l+1}]},\bm{0}_{m_{l+1}\times
1}\right]\left[{\begin{array}[]{cc}\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\\\
\end{array}}\right]+\bm{0}_{m_{l+1}\times
1}+\bm{b}^{[l+1]}+\alpha~{}\bm{0}_{m_{l+1}\times
1}\right)=\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l+1]}.$ (46)

Next, by the construction of $\bm{\theta}_{\textnormal{wide}}$, it is clear
that
$\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for any $l^{\prime}\in[l+1:L]$.

(ii) The results for feature gradients
$\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{g}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{narr}}}$
for $l^{\prime}\in[L]$ can be calculated in a similar way except by replacing
$\sigma(\cdot)$ with $\sigma^{(1)}(\cdot)$.

(iii) By the backpropagation and the above facts in (i), we have

$\bm{z}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\nabla\ell(\bm{f}^{[L]}_{\bm{\theta}_{\textnormal{wide}}},\bm{y})=\nabla\ell(\bm{f}^{[L]}_{\bm{\theta}_{\textnormal{narr}}},\bm{y})=\bm{z}^{[L]}_{\bm{\theta}_{\textnormal{narr}}}.$

Recall the recurrence relation for $l^{\prime}\in[l+1:L-1]$, then we
recursively obtain the following equality for $l^{\prime}$ from $L-1$ down to
$l+1$:

$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=(\bm{W}^{[l^{\prime}+1]})^{\intercal}\left(\bm{z}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{wide}}}\circ\bm{g}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{wide}}}\right)=(\bm{W}^{[l^{\prime}+1]})^{\intercal}\left(\bm{z}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{narr}}}\circ\bm{g}^{[l^{\prime}+1]}_{\bm{\theta}_{\textnormal{narr}}}\right)=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l^{\prime}]}.$
(47)

Next,

$\displaystyle\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\left(\left[\bm{W}^{[{l+1}]},\bm{0}_{m_{l+1}\times
1}\right]+\alpha\left[\bm{0}_{m_{l+1}\times(s-1)},-\bm{W}^{[l+1]}_{[1:m_{l+1}],s},\bm{0}_{m_{l+1}\times(m_{l}-s)},\bm{W}^{[l+1]}_{[1:m_{l+1}],s}\right]\right)^{\intercal}\left(\bm{z}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}\circ\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}}\right)$
$\displaystyle=\left[{\begin{array}[]{cc}\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
0\\\ \end{array}}\right]+\left[{\begin{array}[]{cc}\bm{0}_{(s-1)\times 1}\\\
-\alpha(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\\\
\bm{0}_{(m_{l}-s)\times 1}\\\
\alpha(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\end{array}}\right]$
(54)
$\displaystyle=\left[(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal}_{[1:s-1]},(1-\alpha)(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s},(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})^{\intercal}_{[s+1:m_{l}]},\alpha(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s}\right]^{\intercal}.$
(55)

Finally,

$\displaystyle\bm{z}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}}$
$\displaystyle=\left[(\bm{W}^{[l]})^{\intercal},(\bm{W}^{[l]})_{s,[1:m_{l-1}]}^{\intercal}\right]\left(\left(\left[{\begin{array}[]{cc}\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
0\\\ \end{array}}\right]+\left[{\begin{array}[]{cc}\bm{0}_{(s-1)\times 1}\\\
-\alpha(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\\\
\bm{0}_{(m_{l}-s)\times 1}\\\
\alpha(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\end{array}}\right]\right)\circ\left[{\begin{array}[]{cc}\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\\\
(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\\\
\end{array}}\right]\right)$ (64)
$\displaystyle=(\bm{W}^{[l]})^{\intercal}\left(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\circ\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}}\right)+\bm{0}_{m_{l-1}\times
1}=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l-1]}.$ (65)

This with the recurrence relation once again leads to
$\bm{z}^{[l^{\prime}]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l^{\prime}]}$
for all $l^{\prime}\in[l-1]$.

(iv) If for
$\bm{\theta}_{1},\bm{\theta}_{2}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
and $\bm{\theta}_{1}\neq\bm{\theta}_{2}$, since
$\mathcal{T}_{l,s}^{\alpha}|_{k}$ for $k\neq l,l+1$ is the identity map, then
if there exists some $k_{0}\neq l,l+1$, such that
$\bm{W}_{1}^{[k_{0}]}\neq\bm{W}_{2}^{[k_{0}]}$ or
$\bm{b}_{1}^{[k_{0}]}\neq\bm{b}_{2}^{[k_{0}]}$, then obviously
$\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{1})\neq\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{2})$.
If $k_{0}=l$ or $k_{0}=l+1$, by similar reasoning,
$\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{1})\neq\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{2})$.

(v) For
$\bm{\theta}_{0}=(\bm{W}_{0}^{[1]},\bm{b}_{0}^{[1]},\cdots,\bm{W}_{0}^{[L]},\bm{b}_{0}^{[L]})\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,
we have

$\displaystyle\tilde{\mathcal{T}}_{l,s}^{\alpha}(\bm{\theta}_{0})=\Big{(}\bm{W}_{0}^{[1]},\bm{b}_{0}^{[1]},\cdots,\left[{\begin{array}[]{cc}\bm{W}_{0}^{[l]}\\\
({\bm{W}_{0}^{[l]}})_{s,[1:m_{l-1}]}\\\
\end{array}}\right],\left[{\begin{array}[]{cc}\bm{b}_{0}^{[l]}\\\
({\bm{b}_{0}^{[l]}})_{s}\\\ \end{array}}\right],$
$\displaystyle\left[(\bm{W}^{[l+1]}_{0})_{[1:m_{l+1}],[1:s-1]},(1-\alpha)(\bm{W}^{[l+1]}_{0})_{[1:m_{l+1}],s},(\bm{W}^{[l+1]}_{0})_{[1:m_{l+1}],[s+1:m_{l}]},\alpha(\bm{W}_{0}^{[l+1]})_{[1:m_{l+1}],s}\right],$
$\displaystyle~{}~{}\bm{b}_{0}^{[l+1]},\cdots,\bm{W}_{0}^{[L]},\bm{b}_{0}^{[L]}\Big{)},$

obviously $\tilde{\mathcal{T}}_{l,s}^{\alpha}$ is a linear operator, thus
$\mathcal{T}_{l,s}^{\alpha}$ is an affine operator.

Directly from Lemma 4.5 and Lemma 4.6, we obtain that both one-step null
embedding and one-step splitting embedding satisfy the property of output
preserving and representation preserving, and all we need is to check the
property of criticality preserving.

######  Proposition (Proposition 2 in main text)

For any one-step null embedding $\mathcal{T}_{l,0}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,0}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,0}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, if
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}$, then
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

######  Proof A.3.

Gradient of loss with respect to network parameters of each layer can be
computed from $\bm{F}$, $\bm{G}$, and $\bm{Z}$ as follows

$\displaystyle\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{W}^{[l^{\prime}]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right)(\bm{f}_{\bm{\theta}}^{[l^{\prime}-1]})^{\intercal}\right),$
$\displaystyle\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{b}^{[l]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right).$

Then, by Lemma 4.5, we have for $l^{\prime}\neq l,l+1$,

$\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0},$

and

$\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}.$

Also, for any $j\in[m_{l+1}]$, $k\in[m_{l}]$, since
$(\bm{z}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l+1]})_{j}$,
$(\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{narr}}})_{j}$,
$(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{k}=(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{k}$,
and $\bm{W}_{j,(m_{l}+1)}^{[l+1]}\equiv 0$, we obtain that

$\displaystyle\nabla_{\bm{W}^{[l+1]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{W}^{[l+1]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{W}^{[l+1]}_{j,(m_{l}+1)}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=0,$
$\displaystyle\nabla_{\bm{b}^{[l+1]}_{j}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{b}^{[l+1]}_{j}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0.$

Similarly, for any $j\in[m_{l}]$, $k\in[m_{l-1}]$, since
$(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{j}$,
$(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{j}$,
$(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{k}=(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}})_{k}$,
and $\bm{W}_{(m_{l}+1),k}^{[l]}\equiv 0$, we have

$\displaystyle\nabla_{\bm{W}^{[l]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{W}^{[l]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{W}^{[l]}_{(m_{l}+1),k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=0,$
$\displaystyle\nabla_{\bm{b}^{[l]}_{j}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{b}^{[l]}_{j}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0.$

Moreover, by Lemma 4.5, the output function
$\bm{f}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[L]}$
is independent of the hyperparameter $\alpha$, and
$R_{S}(\bm{\theta}_{\textnormal{wide}})=R_{S}(\bm{\theta}_{\textnormal{narr}})$,
then since $\bm{b}^{[l]}_{(m_{l}+1)}=\alpha$, we have

$\nabla_{\bm{b}^{[l]}_{(m_{l}+1)}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\frac{\partial}{\partial\alpha}R_{S}(\bm{\theta}_{\textnormal{narr}})=0.$

Collecting all the above relations, we obtain that
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

######  Proposition (Proposition 3 in main text)

For any one-step splitting embedding $\mathcal{T}_{l,s}^{\alpha}$, given any
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and its parameters
$\bm{\theta}_{\textnormal{narr}}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
with $\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\in\mathcal{D}_{l,s}$, we have
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}_{l,s}^{\alpha}(\bm{\theta}_{\textnormal{narr}})$
satisfies the following conditions: given any data $S$, loss
$\ell(\cdot,\cdot)$ and activation $\sigma(\cdot)$, if
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}$, then
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

######  Proof A.4.

Gradient of loss with respect to network parameters of each layer can be
computed from $\bm{F}$, $\bm{G}$, and $\bm{Z}$ as follows

$\displaystyle\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{W}^{[l^{\prime}]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right)(\bm{f}_{\bm{\theta}}^{[l^{\prime}-1]})^{\intercal}\right),$
$\displaystyle\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{b}^{[l]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right).$

Then, by Lemma 4.6, we have for $l^{\prime}\neq l,l+1$,

$\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0},$

and

$\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta}_{\textnormal{narr}})=\bm{0}.$

Also, for any $j\in[m_{l+1}]$, $k\in[m_{l}]$, since
$(\bm{z}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l+1]})_{j}$,
$(\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{g}^{[l+1]}_{\bm{\theta}_{\textnormal{narr}}})_{j}$,
$(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{k}=(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{k}$,
and and
$(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{m_{l}+1}=(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s}$,
we obtain

$\displaystyle\nabla_{\bm{W}^{[l+1]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{W}^{[l+1]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{W}^{[l+1]}_{j,(m_{l}+1)}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=0,$
$\displaystyle\nabla_{\bm{b}^{[l+1]}_{j}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{b}^{[l+1]}_{j}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0.$

Similarly, for any $j\in[m_{l}]\backslash\\{s\\}$,

$(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{j}=(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{j},~{}(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{s}=(1-\alpha)(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s},~{}(\bm{z}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{(m_{l}+1)}=\alpha(\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{s},$

and for any $i\in[m_{l}]$,

$(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{i},~{}(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{(m_{l}+1)}=(\bm{g}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{s},$

and for $k\in[m_{l-1}]$,

$(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{k}=(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}})_{k},$

hence for any $j\in[m_{l}]\backslash\\{s\\}$, $k\in[m_{l-1}]$:

$\displaystyle\nabla_{\bm{W}^{[l]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{W}^{[l]}_{j,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{b}^{[l]}_{j}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\nabla_{\bm{b}^{[l]}_{j}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{W}^{[l]}_{s,k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=(1-\alpha)\nabla_{\bm{W}^{[l]}_{s,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{W}^{[l]}_{(m_{l}+1),k}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\alpha\nabla_{\bm{W}^{[l]}_{s,k}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{b}^{[l]}_{s}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=(1-\alpha)\nabla_{\bm{b}^{[l]}_{s}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{\bm{b}^{[l]}_{(m_{l}+1)}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\alpha\nabla_{\bm{b}^{[l]}_{s}}R_{S}(\bm{\theta}_{\textnormal{narr}})=0.$

Collecting all the above relations, we obtain that
$\nabla_{\bm{\theta}}R_{S}(\bm{\theta}_{\textnormal{wide}})=\bm{0}$.

Combining altogether Lemma 4.5, Lemma 4.6, Proposition 2 and Proposition 3, we
finish our proof for Theorem 1.

######  Theorem (Theorem 4.9 in main text)

A $K$-step composition embedding is a critical embedding.

######  Proof A.5.

We shall prove it using induction.

For $K=1$, Proposition 4.9 holds since both one-step null embedding and one
step splitting embedding are critical embeddings.

Assume that Proposition 4.9 holds for $K=l-1$, we want to show that it also
holds for $K=l$.

From the induction hypothesis, we only need to show that if given two critical
embeddings $\mathcal{T}_{1}$, $\mathcal{T}_{2}$, then
$\mathcal{T}_{2}\mathcal{T}_{1}$ is also a critical embedding.

(i) $\mathcal{T}_{2}\mathcal{T}_{1}$ is injective:
For $\bm{\theta}_{1}$ and $\bm{\theta}_{2}$ belonging to a same tuple class
but $\bm{\theta}_{1}\neq\bm{\theta}_{2}$, since $\mathcal{T}_{1}$ is
injective, then
$\mathcal{T}_{1}(\bm{\theta}_{1})\neq\mathcal{T}_{1}(\bm{\theta}_{2})$. Since
$\mathcal{T}_{2}$ is injective, then
$\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta}_{1})\neq\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta}_{2})$.

(ii) $\mathcal{T}_{2}\mathcal{T}_{1}$ is an affine embedding:
We have that $\tilde{\mathcal{T}}_{1}$ and $\tilde{\mathcal{T}}_{2}$ are
linear operators, then

$\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}):=\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta})-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0}),$

we need to show that for any $\bm{\theta}_{1},\bm{\theta}_{2}$ and
$c\in\mathbb{R}$,

$\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1}+\bm{\theta}_{2})=\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1})+\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{2}),$

and

$\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(c\bm{\theta}_{1})=c\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1}).$

Since

$\displaystyle\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1}+\bm{\theta}_{2})$
$\displaystyle=\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta}_{1}+\bm{\theta}_{2})-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{\theta}_{1})+\mathcal{T}_{1}(\bm{\theta}_{2})-\mathcal{T}_{1}(\bm{0})\right)-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{\theta}_{1})\right)+\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{\theta}_{2})\right)-\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{0})\right)-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1})+\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{2}),$

and

$\displaystyle\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(c\bm{\theta}_{1})$
$\displaystyle=\mathcal{T}_{2}\mathcal{T}_{1}(c\bm{\theta}_{1})-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=\mathcal{T}_{2}\left(c\mathcal{T}_{1}(\bm{\theta}_{1})+(1-c)\mathcal{T}_{1}(\bm{0})\right)-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=c\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{\theta}_{1})\right)+(1-c)\mathcal{T}_{2}\left(\mathcal{T}_{1}(\bm{0})\right)-\mathcal{T}_{2}\mathcal{T}_{1}(\bm{0})$
$\displaystyle=c\widetilde{\mathcal{T}_{2}\mathcal{T}_{1}}(\bm{\theta}_{1}).$

(iii) $\mathcal{T}_{2}\mathcal{T}_{1}$ satisfies the property of output
preserving:
Since $\mathcal{T}_{1}$ satisfies the property of output preserving, then for
any $\bm{\theta}$,
$\bm{f}_{\mathcal{T}_{1}(\bm{\theta})}=\bm{f}_{\bm{\theta}}$. Similarly for
$\mathcal{T}_{2}$, we have
$\bm{f}_{\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta})}=\bm{f}_{\mathcal{T}_{1}(\bm{\theta})}$,
hence
$\bm{f}_{\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta})}=\bm{f}_{\bm{\theta}}$.

(iv) $\mathcal{T}_{2}\mathcal{T}_{1}$ satisfies the property of representation
preserving:
Similar reasoning in (iii).

(v) $\mathcal{T}_{2}\mathcal{T}_{1}$ satisfies the property of criticality
preserving:
Since $\bm{\theta}$ is a critical point of $R_{S}({\bm{\theta}})$, so is
$\mathcal{T}_{1}(\bm{\theta})$, and
$\mathcal{T}_{2}\mathcal{T}_{1}(\bm{\theta})$ as well, we finish the proof.

######  Lemma (Lemma 5.2 in main text)

For any affine embedding
$\mathcal{T}:\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}\to\mathrm{Tuple}_{\\{m^{\prime}_{0},\cdots,m^{\prime}_{L}\\}}$
satisfying the output preserving property, if there exist a total index
mapping $\mathcal{I}=\\{\mathcal{I}_{l}\\}_{l=0}^{L}$ from
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ to
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and auxiliary variables
$\bm{\beta}=\left\\{\bm{\beta}^{[l]}_{j}\in\mathbb{R}|~{}l\in[L],j\in[m^{\prime}_{l}]\backslash\mathcal{I}_{l}^{-1}(0)\right\\}$,
such that for any given neuron belonging to
$\mathrm{NN}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, located in layer $l$ with index
$j$, the following two statements hold:
(i) If $\mathcal{I}_{l}(j)\neq 0$,
$(\bm{f}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=(\bm{f}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{\mathcal{I}_{l}(j)}$
and
$(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=\bm{\beta}_{j}^{[l]}(\bm{e}_{\bm{\theta}_{\textnormal{narr}}}^{[l]})_{\mathcal{I}_{l}(j)}$,
(ii) If $\mathcal{I}_{l}(j)=0$,
$(\bm{f}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=\mathrm{Const}$ and
$(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{j}=0$,
then $\mathcal{T}$ is a critical embedding.

######  Proof A.6.

For any critical point
$\bm{\theta}_{\textnormal{narr}}^{\textnormal{c}}\in\bm{\Theta}_{\textnormal{narr}}^{\textnormal{c}}$,
we set
$\bm{\theta}_{\textnormal{wide}}:=\mathcal{T}(\bm{\theta}_{\textnormal{narr}}^{\textnormal{c}})$.
Then, since we have for any $l^{\prime}\in[L]$

$\displaystyle\nabla_{\bm{W}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{W}^{[l^{\prime}]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right)(\bm{f}_{\bm{\theta}}^{[l^{\prime}-1]})^{\intercal}\right),$
$\displaystyle\nabla_{\bm{b}^{[l^{\prime}]}}R_{S}(\bm{\theta})$
$\displaystyle=\nabla_{\bm{b}^{[l]}}\mathbb{E}_{S}\ell(\bm{f}_{\bm{\theta}}(\bm{x}),\bm{y})=\mathbb{E}_{S}\left(\bm{z}_{\bm{\theta}}^{[l^{\prime}]}\circ\bm{g}^{[l^{\prime}]}_{\bm{\theta}}\right).$

Hence for $\mathcal{I}_{l}(i),\mathcal{I}_{l-1}(j)\neq 0$

$\displaystyle\nabla_{(\bm{W}^{[l]}_{\textnormal{wide}})_{ij}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\mathbb{E}_{S}(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{i}(\bm{f}_{\bm{\theta}_{\textnormal{wide}}}^{[l-1]})_{j}$
$\displaystyle=\mathbb{E}_{S}\bm{\beta}^{[l]}_{i}(\bm{e}_{\bm{\theta}_{\textnormal{narr}}^{\textnormal{c}}}^{[l]})_{\mathcal{I}_{l}(i)}(\bm{f}_{\bm{\theta}_{\textnormal{narr}}^{\textnormal{c}}}^{[l-1]})_{\mathcal{I}_{l-1}(j)}$
$\displaystyle=\bm{\beta}^{[l]}_{i}\nabla_{(\bm{W}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i),\mathcal{I}_{l-1}(j)}}R_{S}(\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}})=0,$
$\displaystyle\nabla_{(\bm{b}^{[l]}_{\textnormal{wide}})_{i}}R_{S}(\bm{\theta}_{\textnormal{wide}})$
$\displaystyle=\mathbb{E}_{S}(\bm{e}_{\bm{\theta}_{\textnormal{wide}}}^{[l]})_{i}$
$\displaystyle=\mathbb{E}_{S}\bm{\beta}^{[l]}_{i}(\bm{e}_{\bm{\theta}_{\textnormal{narr}}^{\textnormal{c}}}^{[l]})_{\mathcal{I}_{l}(i)}$
$\displaystyle=\bm{\beta}^{[l]}_{i}\nabla_{(\bm{b}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i)}}R_{S}(\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}})=0.$

By condition (ii), these gradients are obviously $0$ for
$\mathcal{I}_{l}(i)=0$ or $\mathcal{I}_{l-1}(j)=0$. Therefore,
$\bm{\theta}_{\textnormal{wide}}$ is also a critical point and $\mathcal{T}$
is criticality preserving.

Since $\mathcal{I}$ is a total index mapping, for any feature vector of
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$, the component of which is also the
output function of at least a neuron in the wide NN by condition (i).
Moreover, any neuron output function of a neuron in the wide NN is either
constant or output function of a neuron in the narrow NN by condition (i) and
(ii). Therefore, $\mathcal{T}$ is representation preserving. Then
$\mathcal{T}$ is a critical embedding.

######  Theorem (Theorem 5.4 in main text)

General compatible embedding is a critical embedding.

Remark that we later name it as general compatible critical embedding in this
work.

######  Proof A.7.

We need to prove four properties one by one.

  1. 1.

$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is output preserving and
representation preserving;

  2. 2.

$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is an injective operator;

  3. 3.

$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is an affine embedding;

  4. 4.

$\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is criticality preserving.

(i) We prove output preserving and representation preserving by doing
induction on layers.

For the first layer, i.e., $l=1$, we have for $i\in[m^{\prime}_{1}]$,

$\displaystyle(\bm{f}^{[1]}_{\bm{\theta}_{\textnormal{wide}}})_{i}$
$\displaystyle=\sigma\left(\sum_{j\in[m^{\prime}_{0}]}(\bm{W}^{[1]}_{\textnormal{wide}})_{ij}\bm{x}_{j}+(\bm{b}^{[1]}_{\textnormal{wide}})_{i}\right)$
$\displaystyle=\sigma\left(\sum_{j\in[m_{0}]}\bm{\alpha}^{[1]}_{ij}(\bm{W}^{[1]}_{\textnormal{narr}})_{\mathcal{I}_{1}(i),j}\bm{x}_{j}+(\bm{\alpha}^{[1]}_{\textnormal{b}})_{i}+(\bm{b}^{[1]}_{\textnormal{narr}})_{\mathcal{I}_{1}(i)}\right),$

then for $i\notin\mathcal{I}^{-1}_{l}(0)$, for each $j\in[m_{0}]$, since
$\bm{\alpha}^{[1]}_{ij}=\sum_{s\in\mathcal{I}^{-1}_{0}(j)}\bm{\alpha}_{is}=1$,
$(\bm{\alpha}^{[1]}_{\textnormal{b}})_{i}=0$, hence

$(\bm{f}^{[1]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=(\bm{f}^{[1]}_{\bm{\theta}_{\textnormal{narr}}})_{\mathcal{I}_{1}(i)}.$

Otherwise, for $i\in\mathcal{I}^{-1}_{1}(0)$, we have
$\bm{\alpha}^{[1]}_{ij}=0$ and
$(\bm{\alpha}_{\textnormal{b}}^{[1]})_{i}=(\bm{b}^{[1]}_{*})_{i}$, then

$\displaystyle(\bm{f}^{[1]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=\sigma\left((\bm{b}^{[1]}_{*})_{i}\right),$

which is a constant function playing the same role as the bias term in the
next layer.

Suppose for layer $l-1$, we have for $i\notin\mathcal{I}^{-1}_{l-1}(0)$

$(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}})_{\mathcal{I}_{l-1}(i)},$

and for $i\in\mathcal{I}^{-1}_{l-1}(0)$,

$(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=\sigma\left((\bm{b}^{[l-1]}_{*})_{i}\right).$

Then we want to show that this is also the case for layer $l$.

We obtain that

$\displaystyle(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}$
$\displaystyle=\sigma\left(\sum_{j\in[m^{\prime}_{l-1}]}(\bm{W}^{[l]}_{\textnormal{wide}})_{ij}(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}+(\bm{b}^{[l]}_{\textnormal{wide}})_{i}\right)$
$\displaystyle=\sigma\left(\sum_{s\in[m_{l-1}]\cup\\{0\\}}\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\bm{\alpha}^{[l]}_{ij}(\bm{W}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i),s}(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{wide}}})_{j}+(\bm{\alpha}^{[l]}_{\textnormal{b}})_{i}+(\bm{b}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i)}\right)$
$\displaystyle=\sigma\Bigg{(}\sum_{s\in[m_{l-1}]}(\bm{W}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i),s}(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}})_{s}\sum_{j\in\mathcal{I}^{-1}_{l-1}(s)}\bm{\alpha}^{[l]}_{ij}+\sum_{j\in\mathcal{I}^{-1}_{l-1}(0)}\bm{\alpha}^{[l]}_{ij}\sigma\left((\bm{b}^{[l-1]}_{*})_{j}\right)$
$\displaystyle~{}~{}~{}~{}+(\bm{\alpha}^{[l]}_{\textnormal{b}})_{i}+(\bm{b}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i)}\Bigg{)}.$

For $i\notin\mathcal{I}^{-1}_{l}(0)$, we have

$\displaystyle(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=\sigma\left(\sum_{s\in[m_{l-1}]}(\bm{W}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i),s}(\bm{f}^{[l-1]}_{\bm{\theta}_{\textnormal{narr}}})_{s}+(\bm{b}^{[l]}_{\textnormal{narr}})_{\mathcal{I}_{l}(i)}\right)=(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{narr}}})_{\mathcal{I}_{l}(i)}.$

Otherwise, for $i\in\mathcal{I}^{-1}_{l}(0)$, we have

$\displaystyle(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=\sigma\left((\bm{b}^{[l]}_{*})_{i}\right).$

Then, for any layer $l$, we have for $i\notin\mathcal{I}^{-1}_{l}(0)$,

$(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{\mathcal{I}_{l}(i)},$

and for $i\in\mathcal{I}^{-1}_{l}(0)$,

$(\bm{f}^{[l]}_{\bm{\theta}_{\textnormal{wide}}})_{i}=\sigma\left((\bm{b}^{[l]}_{*})_{i}\right).$

Hence, we have proved already that $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$
is output preserving and representation preserving.

(ii) We prove that $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is injective.

If for
$\bm{\theta}_{\textnormal{narr},1},\bm{\theta}_{\textnormal{narr},2}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$
and $\bm{\theta}_{\textnormal{narr},1}\neq\bm{\theta}_{\textnormal{narr},2}$,
then there exists some $l\in[L]$, such that
$\bm{W}_{\textnormal{narr},1}^{[l]}\neq\bm{W}_{\textnormal{narr},2}^{[l]}$ or
$\bm{b}_{\textnormal{narr},1}^{[l]}\neq\bm{b}_{\textnormal{narr},2}^{[l]}$.

Then, if $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is not injective, there
exists
$\bm{\theta}_{\textnormal{narr},1}\neq\bm{\theta}_{\textnormal{narr},2}$, such
that $\bm{\theta}_{\textnormal{wide},1}=\bm{\theta}_{\textnormal{wide},2}$,
where
$\bm{\theta}_{\textnormal{wide},1}:=\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}(\bm{\theta}_{\textnormal{narr},1})$
and
$\bm{\theta}_{\textnormal{wide},2}:=\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}(\bm{\theta}_{\textnormal{narr},2})$,
and we want to show that this will never happen.

Since there exists $l\in[L]$, such that
$\bm{W}_{\textnormal{narr},1}^{[l]}\neq\bm{W}_{\textnormal{narr},2}^{[l]}$ or
$\bm{b}_{\textnormal{narr},1}^{[l]}\neq\bm{b}_{\textnormal{narr},2}^{[l]}$.
For the case
$\bm{W}_{\textnormal{narr},1}^{[l]}\neq\bm{W}_{\textnormal{narr},2}^{[l]}$, we
obtain that there exists $i\in[m_{l+1}],j\in[m_{l}]$, such that
$\left(\bm{W}_{\textnormal{narr},1}^{[l]}\right)_{i,j}\neq\left(\bm{W}_{\textnormal{narr},2}^{[l]}\right)_{i,j}$.
We observe that
$\bm{W}_{\textnormal{wide},1}^{[l]}=\bm{\alpha}^{[l]}\circ\bm{W}_{\textnormal{inter},1}^{[l]}$,
and
$\bm{W}_{\textnormal{wide},2}^{[l]}=\bm{\alpha}^{[l]}\circ\bm{W}_{\textnormal{inter},2}^{[l]}$.
Then, since $\mathcal{I}$ is a total index mapping, then for $i,j\neq 0$,
$\mathcal{I}^{-1}_{l}(i),\mathcal{I}^{-1}_{l-1}(j)\neq\emptyset$, hence for
any $k\in\mathcal{I}^{-1}_{l}(i)$ and $l\in\mathcal{I}^{-1}_{l-1}(j)$,

$\left(\bm{W}_{\textnormal{wide},1}^{[l]}\right)_{k,l}=\bm{\alpha}^{[l]}_{k,l}\left(\bm{W}_{\textnormal{narr},1}^{[l]}\right)_{i,j},$

and

$\left(\bm{W}_{\textnormal{wide},2}^{[l]}\right)_{k,l}=\bm{\alpha}^{[l]}_{k,l}\left(\bm{W}_{\textnormal{narr},2}^{[l]}\right)_{i,j}.$

If $\bm{W}_{\textnormal{wide},1}^{[l]}=\bm{W}_{\textnormal{wide},2}^{[l]}$,
then

$\sum_{s\in\mathcal{I}^{-1}_{l-1}(j)}\left(\bm{W}_{\textnormal{wide},1}^{[l]}\right)_{k,s}=\sum_{s\in\mathcal{I}^{-1}_{l-1}(j)}\left(\bm{W}_{\textnormal{wide},2}^{[l]}\right)_{k,s},$

hence

$\sum_{s\in\mathcal{I}^{-1}_{l-1}(j)}\bm{\alpha}^{[l]}_{k,s}\left(\bm{W}_{\textnormal{narr},1}^{[l]}\right)_{i,j}=\sum_{s\in\mathcal{I}^{-1}_{l-1}(j)}\bm{\alpha}^{[l]}_{k,s}\left(\bm{W}_{\textnormal{narr},2}^{[l]}\right)_{i,j},$

and since $\sum_{s\in\mathcal{I}^{-1}_{l-1}(j)}\bm{\alpha}^{[l]}_{k,s}=1$, we
obtain that

$\left(\bm{W}_{\textnormal{narr},1}^{[l]}\right)_{i,j}=\left(\bm{W}_{\textnormal{narr},2}^{[l]}\right)_{i,j},$

which contradicts
$\bm{\theta}_{\textnormal{narr},1}\neq\bm{\theta}_{\textnormal{narr},2}$.

For the case where
$\bm{b}_{\textnormal{narr},1}^{[l]}\neq\bm{b}_{\textnormal{narr},2}^{[l]}$,
since $(\bm{\alpha}_{\textnormal{b}}^{[l]})_{i}=0$ for any $l\in[L]$ with
$i\notin\mathcal{I}_{l}^{-1}(0)$. Then for any $k\in\mathcal{I}^{-1}_{l}(j)$,
$j\neq 0$,

$\left(\bm{b}_{\textnormal{wide},1}^{[l]}\right)_{k}=\bm{\alpha}^{[l]}_{\textnormal{b}}+\left(\bm{b}_{\textnormal{narr},1}^{[l]}\right)_{j}=\left(\bm{b}_{\textnormal{narr},1}^{[l]}\right)_{j},$

and

$\left(\bm{b}_{\textnormal{wide},2}^{[l]}\right)_{k}=\bm{\alpha}^{[l]}_{\textnormal{b}}+\left(\bm{b}_{\textnormal{narr},2}^{[l]}\right)_{j}=\left(\bm{b}_{\textnormal{narr},2}^{[l]}\right)_{j},$

hence
$\bm{b}_{\textnormal{wide},1}^{[l]}\neq\bm{b}_{\textnormal{wide},2}^{[l]}$,
and we finish the injection proof.

(iii) We prove that $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is affine.

It is obvious that $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is affine since
for any $\bm{\theta}\in\mathrm{Tuple}_{\\{m_{0},\cdots,m_{L}\\}}$,
$\tilde{\mathcal{T}}^{\bm{\alpha}}_{\mathcal{I}}(\bm{\theta}):={\mathcal{T}}^{\bm{\alpha}}_{\mathcal{I}}(\bm{\theta})-{\mathcal{T}}^{\bm{\alpha}}_{\mathcal{I}}(\bm{0})$
puts the weights and biases of null neuron as zero, and multiplies the weights
and biases of effective by some constant, thus
$\tilde{\mathcal{T}}^{\bm{\alpha}}_{\mathcal{I}}$ is a linear operator.

(iv) We prove that $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is criticality
preserving.

We only need to check whether or not the conditions in Lemma 5.2 are
satisfied, and we show this using induction.

For layer $L$, we have

$\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}_{\bm{\theta}_{\textnormal{wide}}}^{[L]}\circ\bm{g}_{\bm{\theta}_{\textnormal{wide}}}^{[L]},$

since $\mathcal{T}^{\bm{\alpha}}_{\mathcal{I}}$ is output preserving for any
activation, hence

$\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{z}_{\bm{\theta}_{\textnormal{wide}}}^{[L]}\circ\bm{g}_{\bm{\theta}_{\textnormal{wide}}}^{[L]}=\bm{z}_{\bm{\theta}_{\textnormal{narr}}}^{[L]}\circ\bm{g}_{\bm{\theta}_{\textnormal{narr}}}^{[L]}=\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{narr}}},$

hence
$\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}=\bm{\gamma}^{[L]}_{i}\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{narr}}}$,
with $\bm{\gamma}^{[L]}_{i}=1$.

For any $l\in[L]$, then suppose for layer $l$, we have for
$i\notin\mathcal{I}^{-1}_{l}(0)$, there exists
$\bm{\gamma}^{[l]}_{i}\in\mathbb{R}$, such that

$\left(\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{wide}}}\right)_{i}=\bm{\gamma}^{[l]}_{i}\left(\bm{e}^{[L]}_{\bm{\theta}_{\textnormal{narr}}}\right)_{\mathcal{I}_{l}(i)},$

and for $i\in\mathcal{I}^{-1}_{l}(0)$,