# An embedding of ReLU networks
and an analysis of their identifiability

Pierre Stock and Rémi Gribonval

###### Abstract.

Neural networks with the Rectified Linear Unit (ReLU) nonlinearity are
described by a vector of parameters $\theta$, and realized as a piecewise
linear continuous function
$\boldsymbol{R}_{\theta}:x\in\mathbb{R}^{d}\mapsto\boldsymbol{R}_{\theta}(x)\in\mathbb{R}^{k}$.
Natural scalings and permutations operations on the parameters $\theta$ leave
the realization unchanged, leading to equivalence classes of parameters that
yield the same realization. These considerations in turn lead to the notion of
identifiability – the ability to recover (the equivalence class of) $\theta$
from the sole knowledge of its realization $\boldsymbol{R}_{\theta}$. The
overall objective of this paper is to introduce an embedding for ReLU neural
networks of any depth, $\boldsymbol{\Phi}(\theta)$, that is invariant to
scalings and that provides a locally linear parameterization of the
realization of the network. Leveraging these two key properties, we derive
some conditions under which a deep ReLU network is indeed locally identifiable
from the knowledge of the realization on a finite set of samples
$x_{i}\in\mathbb{R}^{d}$. We study the shallow case in more depth,
establishing necessary and sufficient conditions for the network to be
identifiable from a bounded subset $\mathcal{X}\subseteq\mathbb{R}^{d}$.

###### Contents

  1. 1 Introduction
  2. 2 General setting and main results
    1. 2.1 Network architectures
    2. 2.2 Realization of a network
    3. 2.3 Invariance to permutation and scaling
    4. 2.4 An invariant embedding of ReLU networks
    5. 2.5 Some consequences of PS-identifiability
    6. 2.6 Identifiability conditions in the shallow case
    7. 2.7 A glimpse at the analysis of local identifiability
    8. 2.8 Non-degeneracy and irreducibility in shallow _vs_ deeper architectures
    9. 2.9 Discussion
  3. 3 Rescaling invariance of the embedding
  4. 4 Analyzing local identifiability
    1. 4.1 Activation status of neurons and paths, and activation spaces
    2. 4.2 “Algebraic” expressions of the realization
    3. 4.3 Non-degeneracy and local S-identifiability
  5. 5 Identifiability for shallow neural networks
    1. 5.1 Activation spaces and twin neurons
    2. 5.2 Proof of Lemma 5: no twins implies non-degeneracy
    3. 5.3 Proof of Theorem 3: irreducibility and no twins implies PS-identifiability
    4. 5.4 Local S-identifiability despite the presence of twins
    5. 5.5 Discussion of the role of activation spaces
  6. A Proof of Lemma 7
  7. B Proof of Theorem 2
  8. C Proof of Lemma 3
  9. D Proof of Lemma 4
  10. E Proof of Lemma 9 and Lemma 10
  11. F Proof of Lemma 11
  12. G Proof of Lemma 13
  13. H Proof of Lemma 16
  14. I Details on Example 4
  15. J Details on Example 5

##  1\. Introduction

The empirical success of Deep Neural Networks (DNNs) for traditional machine
learning tasks such as image classification is a well-known fact for the
research community [1]. While this empirical success percolates to areas
ranging from protein folding to symbolic mathematics, a second well-known fact
is that the theoretical tools to grasp DNNs and uncover the reasons of their
success are still lagging behind the fast-paced experimental results. We argue
that a deeper understanding of the expressivity and stability properties of
such networks could lead to practical improvements [2, 3]. In this paper, we
introduce an embedding, $\boldsymbol{\Phi}(\theta)$, of the vector $\theta$ of
network parameters (weights and biases) that exhibits interesting properties
for networks based on the popular Rectified Linear Unit (ReLU): in particular,
$\boldsymbol{\Phi}(\theta)$ is invariant to natural rescalings of the
parameters that leave unchanged the function implemented by the network. To
showcase the potential of this tool, we leverage it to study the expressivity
of DNNs from the perspective of their functional equivalence classes.

In the remainder of this section, we first list the papers tackling
identifiability of neural networks with a given non-linearity function. We
next present some related work that construct an embedding for ReLU networks.
Finally, we list applications directly or indirectly derived from the two
previous theoretical considerations.

### Around Functional Identifiability

First, various results dating back from the 90’s identify conditions that
allow to identify neural networks _with one hidden layer_ equipped with
various non-linearities111It should be noted that the functional equivalence
class generally depends on the considered non-linearity. For instance, with
the hyperbolic tangent, the authors only consider permutations and sign flips.
like the hyperbolic tangent [4, 5, 6, 7]. Such results _do not_ encompass the
ReLU case. Simultaneously, Fefferman derived identifiability conditions for
deep networks equipped with the $\tanh$ nonlinearity using complex analysis
[8]. More recently, the work of Rolnick and Kording [9] reflects a renewed
interest for this subject and its application to ReLU networks. The authors
propose to reverse-engineer deep ReLU networks and present a constructive
algorithm that samples network realizations $\boldsymbol{R}_{\theta}(x)$ for
carefully chosen input points $x$ to deduce the architecture of the network
and its parameters, up to rescalings and permutations. The authors prove that
their algorithm terminates, except for a measure-zero set of parameters222This
measure-zero set of parameters is not explicitly described by the authors..
Similarly, Fornasier et al. [10] propose to recover the parameters of a _two-
hidden-layer_ neural network with smooth nonlinearity by actively sampling
finite difference approximations to Hessians of the network, and by combining
the insights gained from the sampling with a heuristic for precise attribution
of the parameters to the architecture. The authors demonstrate the empirical
effectiveness of their approach and claim that the proposed method can be
generalized to networks with any depth. Finally, Phuong and Lampert provide a
result related to identifiability for ReLU networks under some more
restrictive assumptions [11].

### Embeddings Zoology

We list here the neural network embeddings in the literature that are the
closest to our own embedding, $\boldsymbol{\Phi}(\theta)$, which is introduced
in Definition 6. Its main property is that it is invariant under the action of
rescalings, as stated more formally in Theorem 1. Schematically,
$\boldsymbol{\Phi}(\theta)$ lives in the linear space indexed by network
_paths_ and each coordinate is a product of weights and/or biases along a
particular network path. In a similar fashion, Malgouyres and Landsberg [12]
consider a particular class of _linear_ structured networks called _Deep
Structured Neural Networks_ , without biases, and consider only layer-wise
rescalings. In [12, Section 6], the authors provide sufficient and necessary
conditions for local identifiability by studying complex algebraic varieties
leveraging the _Segre embedding_ of such networks. The Segre embedding bears a
resemblance with $\boldsymbol{\Phi}(\theta)$ since it is also made of product
of network parameters, but it does not encompass the biases. Moreover, we
consider neuron-wise rescalings in this paper as opposed to less general
layer-wise rescalings considered by the authors, and also emcompass the ReLU
non-linearity in our approach. Malgouyres later leverages the Segre embedding
to study local stability properties of sparse neural networks [13]. Finally,
Neyshabur _et al._ introduce a family of _path regularizers_ to derive an
optimization procedure that takes the invariance of the realization
$\boldsymbol{R}_{\theta}$ under the action of the rescalings into account and
called Path-SGD [14, 15]. Such path regularizers are scalars – as opposed to
vectorial embeddings – that are obtained by summing, for any network path, the
norm of the product of all weights along this paths. Moreover, this approach
does not take the biases into account, as opposed to our embedding,
$\boldsymbol{\Phi}(\theta)$.

### Applications

As illustrated with Path-SGD [15], several papers attempt to perform the
optimization in the space of network parameters _quotiented_ by the rescaling
operation. Several work follow and perform the optimization by alternating
between a standard SGD step and a projection step that modifies the rescaling
coefficients without changing the function implemented by the network [16, 17,
18, 19]. The main difference between these papers is the projection step, that
is performed either implicitly (with a regularizer) or explicitly (by
computing the optimal333In the sense that such coefficients globally minimize
a given objective function. rescaling coefficients). In the latter case, the
proposed empirical methods may not yield the optimal rescaling coefficients
but rather more or less stable and good approximations. Another advantage of
rescalings is to improve post-training scalar quantization of neural networks
by carefully selecting the rescaling coefficients such that the dynamic range
of the weights within a layer is relatively small, with as few outliers as
possible [20, 21]. More related to the concept of (local) identifiability,
Carlini _et al._ [22] design a differential attack to efficiently recover the
parameters of remote model up to floating point precision, by sending
carefully designed queries $x$ to the remote network and receiving only its
output.

After introducing the main notations, we define $\boldsymbol{\Phi}(\theta)$
and state the main results of the paper in Section 2. Then, we formally state
and prove the main properties of the embedding $\boldsymbol{\Phi}(\theta)$ in
Section 3. In particular, we prove that $\boldsymbol{\Phi}(\theta)$ is
invariant under the action of the rescalings. Next, we leverage this embedding
to derive partial and local identifiability results for ReLU neural networks
of any depth in Section 4. To further demonstrate the validity of our
approach, we fully study the shallow case in Section 5 and provide conditions
under which a ReLU neural network with one hidden layer is identifiable.
Finally, we argue that $\boldsymbol{\Phi}(\theta)$ may be leveraged to tackle
other open problems in the Machine Learning community.

##  2\. General setting and main results

We consider fully-connected feedforward ReLU neural networks with $L\geq 2$
affine layers. Each network is supported on a graph $G=(E,V)$ with vertex set
$V$ composed of neurons $\nu$ and edge set $E$ composed of connections. The
set of neurons $V$ is partitioned into the input layer $N_{0}$, $L-1$ hidden
layers $N_{\ell}$, $1\leq\ell\leq L-1$, and the output layer $N_{L}$. Hidden
neurons compose the set $H=\cup_{\ell=1}^{L-1}N_{\ell}$. Since we focus on
fully-connected networks, the set of connections $E$ is made of all oriented
edges $e=\nu\to\nu^{\prime}$ between neurons belonging to consecutive layers,
$\nu\in N_{\ell-1}$, $\nu^{\prime}\in N_{\ell}$ for some $1\leq\ell\leq L$.
The subset of incoming edges of neuron $\nu$ is denoted $\bullet\to\nu$, while
$\nu\to\bullet$ denotes its set of outgoing edges.

Each edge $e\in E$ is equipped with a weight $w_{e}$ and each hidden neuron
$\nu\in H$ with a bias $b_{\nu}$. Output neurons, i.e. neurons from the last
layer $\eta\in N_{L}$, are also equipped with a bias $b_{\eta}$, which is
sometimes constrained to be zero. The set of all neurons equipped with biases
is $\bar{H}:=H\cup N_{L}$. Parameters (weights and biases) are gathered in a
parameter vector $\theta\in\mathbb{R}^{E\cup\bar{H}}$ where $E\cup\bar{H}$
indexes all possible weights and biases including biases on the output layer.
For brevity we may denote $\theta_{e}$ for weights and $\theta_{\nu}$ for
biases. When needed we also write $\theta=(\theta_{i})_{i\in E\cup\bar{H}}$.
Since we consider a fully connected architecture (this does not prevent some
weights to possibly vanish on some edges), $\theta$ can also be represented as
a set of $L$ matrices
$\boldsymbol{W}_{\ell}=(w_{\nu\to\nu^{\prime}})_{\nu^{\prime}\in
N_{\ell},\nu\in N_{\ell-1}}\in\mathbb{R}^{N_{\ell}\times N_{\ell-1}}$,
$1\leq\ell\leq L$ and $L$ vectors $\boldsymbol{b}_{\ell}=(b_{\nu})_{\nu\in
N_{\ell}}\in\mathbb{R}^{N_{\ell}}$, $1\leq\ell\leq L$.

###  2.1. Network architectures

Many of the notions of parameter identifiability or non-degeneracy that will
be considered are relative to a choice of network “architecture”. This is
represented both by the graph $G$ (which determines how many layers there are,
and how wide they are) but also by a possibly restricted set
$\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ of network parameters, which may
for example account for the following type of constraints:

  * •

restricting to a convolutional structure;

  * •

restricting to sparse networks, possibly with structured sparsity patterns;

  * •

restricting to networks without output biases ($b_{\eta}=0$ for every $\eta\in
N_{L}$);

  * •

restricting to networks without biases ($b_{\nu}=0$ for every $\nu\in H\cup
N_{L}$).

###  2.2. Realization of a network

Given a parameter $\theta$ and an input vector $x\in\mathbb{R}^{N_{0}}$, we
sequentially define $\boldsymbol{y}_{0}(\theta,x)=x$ and for each
$1\leq\ell\leq L-1$ the pre-activation
$\boldsymbol{z}_{\ell}(\theta,x)=\boldsymbol{W}_{\ell}\boldsymbol{y}_{\ell-1}(\theta,x)+\boldsymbol{b}_{\ell}\in\mathbb{R}^{N_{\ell}}$,
the post-activation
$\boldsymbol{y}_{\ell}(\theta,x)=\mathtt{ReLU}(\boldsymbol{z}_{\ell}(\theta,x))\in\mathbb{R}^{N_{\ell}}$
where the rectified linear unit (ReLU) activation function,
$\mathtt{ReLU}(t)=\max(t,0)$, is applied entrywise. Finally we define the
realization of the network as the function
$\boldsymbol{R}_{\theta}:x\mapsto\boldsymbol{R}_{\theta}(x):=\boldsymbol{z}_{L}(\theta,x)=\boldsymbol{W}_{L}\boldsymbol{y}_{L-1}(\theta,x)+\boldsymbol{b}_{L}\in\mathbb{R}^{N_{L}}$.
When needed we will use neuron-wise versions of these notations, e.g.
$y_{\nu}(\theta,x)=(\boldsymbol{y}_{\ell}(\theta,x))_{\nu}$ where $\nu\in
N_{\ell}$. Note the general convention to denote scalar-valued quantities in
plain font to distinguish them from quantities that can be vector-valued,
which are generally denoted in bold.

###  2.3. Invariance to permutation and scaling

A well known fact [23] is that the realization of any ReLU-network is
invariant to permutations and scalings of the parameter $\theta$. The
invariance to permutations is not specific to ReLU-networks, while the
scaling-invariance is due to the homogeneity of the ReLU:
$\mathtt{ReLU}(\lambda\cdot)=\lambda\mathtt{ReLU}(\cdot)$ for every
$\lambda>0$ and is also valid for other variants such as the leaky-ReLU. While
various definitions coexist in the literature [24, 25, 26], it is convenient
to focus first on the practical _per-neuron_ rescaling equivalence [23] as
stated below.

##### Rescaling equivalence

Let $\nu\in H$ and $\lambda_{\nu}>0$. A neuron-wise scaling multiplies the
incoming weights and the bias of $\nu$ by $\lambda_{\nu}$, and divides the
outgoing weights by $\lambda_{\nu}$. It is formally defined as
$s_{\nu,\lambda_{\nu}}:\theta=(w,b)\mapsto\theta^{\prime}=(w^{\prime},b^{\prime})$
where for every connection $e\in E$,

(1) $\forall e\in E,\quad
w^{\prime}_{e}=\begin{cases}w_{e}\lambda_{\nu}&\mbox{if }e\in\bullet\to\nu\\\
\frac{1}{\lambda_{\nu}}w_{e}&\mbox{if }e\in\nu\to\bullet\\\
w_{e}&\mbox{otherwise},\end{cases}\qquad\forall\nu\in H,\quad
b^{\prime}_{\nu}=b_{\nu}\lambda_{\nu}.$

Let $\mathcal{S}$ be the set of neuron-wise scalings. We observe that neuron-
wise rescalings commute and are invertible, the inverse of
$s_{\nu,\lambda_{\nu}}$ being $s_{\nu,1/\lambda_{\nu}}$. Let
$\langle\mathcal{S}\rangle$ be the commutative group generated by
$\mathcal{S}$. Every $s\in\langle\mathcal{S}\rangle$ can be uniquely
represented as the composition

$s=\operatorname*{\bigcirc}_{\nu\in H}s_{\nu,\lambda_{\nu}}$

where the $\lambda_{\nu}$ are strictly positive. Note that in this
representation, every hidden neuron $\nu$ is associated to exactly one neuron-
wise rescaling $\lambda_{\nu}$.

######  Definition 1.

$\theta$ and $\theta^{\prime}$ are rescaling equivalent if there exists
$s\in\langle\mathcal{S}\rangle$ such that $\theta^{\prime}=s(\theta)$. We then
denote $\theta\sim_{S}\theta^{\prime}$.

Notice that if $\theta^{\prime}\sim_{S}\theta$, then the output biases are
equal: $\theta^{\prime}_{\eta}=\theta_{\eta}$ for all $\eta\in N_{L}$.

######  Fact 1.

$\theta^{\prime}\sim_{S}\theta$ if, and only if, there exists diagonal
matrices $\boldsymbol{\Lambda}_{\ell}\in\mathbb{R}^{N_{\ell}\times N_{\ell}}$
with positive entries, $0\leq\ell\leq L$ such that
$\boldsymbol{\Lambda}_{0}=\boldsymbol{I}_{N_{0}}$,
$\boldsymbol{\Lambda}_{L}=\boldsymbol{I}_{N_{L}}$, and for every layer
$1\leq\ell\leq L$

(2)
$\boldsymbol{W}^{\prime}_{\ell}=\boldsymbol{\Lambda}_{\ell}\boldsymbol{W}_{\ell}\boldsymbol{\Lambda}_{\ell-1}^{-1}\
\text{and}\
\boldsymbol{b}^{\prime}_{\ell}=\boldsymbol{\Lambda}_{\ell}\boldsymbol{b}_{\ell}.$

##### Permutation equivalence

Consider $\pi:=(\pi_{1},\ldots,\pi_{\ell})$ where
$\pi_{\ell}\in\mathfrak{S}_{N_{\ell}}$ is a permutation of the $\ell$-th
hidden layer (input and output layers are never permuted), $1\leq\ell\leq
L-1$. Denote
$\mathfrak{S}_{G}=\mathfrak{S}_{N_{1}}\times\ldots\times\mathfrak{S}_{N_{L-1}}$
the group of all such tuples of permutations. One can define a natural action
of the group $\mathfrak{S}_{G}$ on parameterizations via
$\theta\mapsto\pi\circ\theta:=\theta^{\prime}$ where each weight matrix
$\boldsymbol{W}^{\prime}_{\ell}$ is obtained from $\boldsymbol{W}_{\ell}$ by
permuting rows according to $\pi_{\ell}$ and columns according to
$\pi_{\ell-1}$, while bias vector $\boldsymbol{b}^{\prime}_{\ell}$ is a
permuted version of $\boldsymbol{b}_{\ell}$ according to $\pi_{\ell}$.

######  Definition 2.

Two parameters $\theta,\theta^{\prime}$ are _permutation-equivalent_ if, and
only if, there exists $\pi\in\mathfrak{S}_{G}$ such that
$\theta^{\prime}=\pi\circ\theta$. This is denoted
$\theta\sim_{P}\theta^{\prime}$.
The parameters are _permutation-scaling equivalent_ if, and only if, there
exists $\theta^{\prime\prime}$ such that
$\theta\sim_{S}\theta^{\prime\prime}\sim_{P}\theta^{\prime}$. This is denoted
$\theta\sim_{PS}\theta^{\prime}$.
The parameters are _scaling-permutation equivalent_ if, and only if, there
exists $\theta^{\prime\prime}$ such that
$\theta\sim_{P}\theta^{\prime\prime}\sim_{S}\theta^{\prime}$. This is denoted
$\theta\sim_{SP}\theta^{\prime}$.

######  Fact 2.

$\theta^{\prime}\sim_{PS}\theta$ if, and only if,
$\theta^{\prime}\sim_{SP}\theta$, if and only if there exists diagonal
matrices $\boldsymbol{\Lambda}_{\ell}\in\mathbb{R}^{N_{\ell}\times N_{\ell}}$
with positive entries and permutation matrices
$\boldsymbol{\Pi}_{\ell}\in\mathbb{R}^{N_{\ell}\times N_{\ell}}$,
$0\leq\ell\leq L$, such that
$\boldsymbol{\Pi}_{0}=\boldsymbol{\Lambda}_{0}=\boldsymbol{I}_{N_{0}}$,
$\boldsymbol{\Pi}_{L}=\boldsymbol{\Lambda}_{L}=\boldsymbol{I}_{N_{L}}$, and
for every layer $1\leq\ell\leq L$

(3)
$\boldsymbol{W}^{\prime}_{\ell}=\boldsymbol{\Pi}_{\ell}\boldsymbol{\Lambda}_{\ell}\boldsymbol{W}_{\ell}\boldsymbol{\Lambda}_{\ell-1}^{-1}\boldsymbol{\Pi}_{\ell-1}^{-1}\
\text{and}\
\boldsymbol{b}^{\prime}_{\ell}=\boldsymbol{\Pi}_{\ell}\boldsymbol{\Lambda}_{\ell}\boldsymbol{b}_{\ell}.$

As widely documented [23, 24, 25, 26], PS-equivalent parameters share their
realization as proven, e.g., in [9][Lemma 1].

######  Lemma 1.

For any $\theta,\theta^{\prime}\in\mathbb{R}^{E\cup\bar{H}}$, if
$\theta^{\prime}\sim_{PS}\theta$ then
$\boldsymbol{R}_{\theta^{\prime}}=\boldsymbol{R}_{\theta}$.

A natural question is to determine conditions for the identifiability of (the
equivalence class up to scaling and permutation of) $\theta$ from
$\boldsymbol{R}_{\theta}$. To be more specific, we consider identifiability
with respect to a family of parameters $\Theta$, from a set $\mathcal{X}$. A
case of particular interest will be when $\mathcal{X}$ is finite, in order to
characterize whether $\theta$ can be recovered (up to scaling and
permutations) from finitely many samples of the network realization
$\boldsymbol{R}_{\theta}$.

######  Definition 3 (PS-identifiability).

A parameter $\theta\in\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ is PS-
identifiable with respect to $\Theta$ from
$\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ if for every
$\theta^{\prime}\in\Theta$, the equality
$\boldsymbol{R}_{\theta}=\boldsymbol{R}_{\theta^{\prime}}$ on $\mathcal{X}$
implies $\theta^{\prime}\sim_{PS}\theta$. When considering
$\mathcal{X}=\mathbb{R}^{N_{0}}$, $\theta$ is simply said to be PS-
identifiable with respect to $\Theta$. When considering
$\Theta=\mathbb{R}^{E\cup\bar{H}}$, $\theta$ is simply said to be PS-
identifiable (from $\mathcal{X}$).

A trivial observation is that if all outgoing weights of a hidden neuron are
zero, then the realization of the network is unchanged under arbitrary
modifications of the incoming weights and of the bias of this neuron, hence
the corresponding parameter $\theta$ cannot be PS-identifiable with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$. A similar phenomenon occurs if all
incoming weights to a hidden neuron are zero. This motivates the definition of
admissible parameters and proves Lemma 2 below.

######  Definition 4.

$\theta$ is admissible if for each hidden neuron $\nu\in H$ we have
$\boldsymbol{w}_{\bullet\to\nu}\neq 0$ and $\boldsymbol{w}_{\nu\to\bullet}\neq
0$. Equivalently, every hidden neuron belongs to a full path with nonzero
weights.

######  Lemma 2.

If $\theta$ is PS-identifiable from $\mathcal{X}$ with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$, then it is admissible.

###  2.4. An invariant embedding of ReLU networks

The invariance with respect to (permutations and) scalings (Lemma 1) calls for
an invariant representation of equivalence classes of network parameters. A
central tool is a representation $\boldsymbol{\Phi}(\theta)$ mapping a network
parameter $\theta\in\mathbb{R}^{E\cup\bar{H}}$ to a vector
$\boldsymbol{\Phi}(\theta)$ in a space indexed by paths of the network,
$\mathbb{R}^{\mathcal{P}}$.

Before going further let us formally introduce paths, as illustrated in Figure
1

######  Definition 5.

The set $\mathcal{P}_{\ell}$, $0\leq\ell\leq L$ (resp. $\mathcal{Q}_{\ell}$,
$1\leq\ell\leq L-1$) consists of all partial paths from any neuron
$\nu_{\ell}\in N_{\ell}$ to a neuron of the last (resp. penultimate) layer
$\nu_{L}\in N_{L}$ (resp. $\nu_{L-1}\in N_{L-1}$). Any path
$p\in\mathcal{P}_{\ell}$ is written as a tuple $p=(p_{\ell},\dots,p_{L})$
where each $p_{i}\in V$ is a neuron. We say that $p$ is a full path if
$\ell=0$, that is, if $p$ connects the input and the output layers. We may
write $p=p_{\ell}\to p_{\ell+1}\to\dots\to p_{L}$, as well as $p=\mu\to
q\to\nu$ where $\mu=p_{\ell}\in N_{\ell}$, $\nu=p_{L}\in N_{L}$ and
$q=(p_{\ell+1},\ldots,p_{L-1})\in\mathcal{Q}_{\ell+1}$.

Figure 1. We consider a particular network architecture with $L=4$ layers
(equivalently, with two hidden layers). Left: A particular path belonging to
$\mathcal{P}_{0}$. Right: A particular path belonging to $\mathcal{Q}_{1}$.

######  Remark 1.

To streamline notations we say that an edge $e=\mu\to\nu\in E$ belongs to $p$
and also write $e\in p$ if there exists $\ell\leq i\leq L-1$ such that
$\mu=p_{i}$ and $\nu=p_{i+1}$. Similarly, we choose to denote $\nu\in p$ if
(and only if) the path $p$ _starts_ from neuron $\nu$, i.e., when
$p=(p_{\ell},\ldots,p_{L})\in\mathcal{P}_{\ell}$, if $p_{\ell}=\nu$.

We next introduce the representation $\boldsymbol{\Phi}(\cdot)$, which
presents some connections with previous work [12, 13, 23] while being more
generic as detailed in the introduction.

######  Definition 6.

Given $\theta\in\mathbb{R}^{E\cup\bar{H}}$, the value of a path is

(4) $\displaystyle{\Phi}_{p}(\theta)$ $\displaystyle=\Pi_{e\in p}\theta_{e},\
\text{for each full path}\ p\in\mathcal{P}_{0},$ (5)
$\displaystyle{\Phi}_{p}(\theta)$ $\displaystyle=\theta_{p_{\ell}}\Pi_{e\in
p}\theta_{e},\text{for}\
p=(p_{\ell},\ldots,p_{L})\in\mathcal{P}_{\ell},1\leq\ell\leq L.$

For $p\in\mathcal{P}_{L}$, $p=(\eta)$ with $\eta\in N_{L}$,
${\Phi}_{p}(\theta)=\theta_{p_{L}}=b_{\eta}$ is the corresponding output bias.
Define $\mathcal{P}:=\cup_{\ell=0}^{L}\mathcal{P}_{\ell}$. For any
$\theta\in\mathbb{R}^{E\cup\bar{H}}$ we define

(6)
$\boldsymbol{\Phi}(\theta):=({\Phi}_{p}(\theta))_{p\in\mathcal{P}}\in\mathbb{R}^{\mathcal{P}}$

This representation, combined with the entrywise sign of $\theta$ (with the
convention $\mathtt{sign}(0)=0$), characterizes the classes of scaling-
equivalent admissible parameters.

######  Theorem 1.

Consider any $\theta^{\prime},\theta\in\mathbb{R}^{E\cup\bar{H}}$.

  1. a)

Assume that $\theta\sim_{S}\theta^{\prime}$. Then
$\boldsymbol{\Phi}(\theta)=\boldsymbol{\Phi}(\theta^{\prime})$ and
$\mathtt{sign}(\theta^{\prime})=\mathtt{sign}(\theta)$.

  2. b)

Assume that $\theta$ is admissible, that
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$, and that
$\mathtt{sign}(\theta^{\prime}_{E})=\mathtt{sign}(\theta_{E})$.
Then $\theta\sim_{S}\theta^{\prime}$ and $\theta^{\prime}$ is also admissible.

The proof is in Section 3. A similar result is proven in [27, Theorem 3.3]
without considering the biases and by replacing the condition on the signs by
a condition on the activation statuses of all partial paths, which depend on
the input variable $x$ besides $\theta$.

######  Remark 2.

The map $\theta\mapsto\boldsymbol{\Phi}(\theta)$ will be referred to as an
_embedding_ of network parameters. Stricto-sensu, as this map is not an
injective function of network parameters, it does not match the definition of
an embedding. However, since it characterizes equivalence classes of
rescaling-equivalent admissible parameters, it can be used to define without
ambiguity an embedding of these equivalence classes in
$\mathbb{R}^{\mathcal{P}}$.

###  2.5. Some consequences of PS-identifiability

Using the embedding $\boldsymbol{\Phi}(\cdot)$, we show that if $\theta$ is
PS-identifiable then it is locally identifiable up to scaling only. Locality
is measured in the sense of open balls
$B(\boldsymbol{c},r)=\\{\boldsymbol{c}^{\prime}:\|\boldsymbol{c}^{\prime}-\boldsymbol{c}\|_{\infty}<r\\}$,
where the ambient linear space, equipped with the sup-norm, should always be
clear from context.

######  Definition 7 (local S-identifiability).

Given $\epsilon>0$, a parameter
$\theta\in\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ is $\epsilon$-locally
S-identifiable from $\mathcal{X}\subset\mathbb{R}^{N_{0}}$ with respect to
$\Theta$, if for every $\theta^{\prime}\in\Theta\cap B(\theta,\epsilon)$, the
identity $\boldsymbol{R}_{\theta}=\boldsymbol{R}_{\theta^{\prime}}$ on
$\mathcal{X}$ implies $\theta^{\prime}\sim_{S}\theta$. If there exists
$\epsilon>0$ such that $\theta$ is $\epsilon$-locally S-identifiable from
$\mathcal{X}$ then $\theta$ is locally S-identifiable from $\mathcal{X}$. When
$\mathcal{X}=\mathbb{R}^{N_{0}}$ and/or $\Theta=\mathbb{R}^{E\cup\bar{H}}$ we
adopt the same simplified terminology as with the notion of PS-
identifiability.

######  Remark 3.

If $\theta$ is PS-identifiable (resp. locally S-identifiable) from
$\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ with respect to
$\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ then the same holds from any
$\mathcal{X}^{\prime}\supseteq\mathcal{X}$ with respect to any
$\Theta^{\prime}\subseteq\Theta$.

Our first result is the following theorem.

######  Theorem 2.

Consider $\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ and
$\mathcal{X}\subset\mathbb{R}^{N_{0}}$. If $\theta\in\Theta$ is admissible and
PS-identifiable from $\mathcal{X}$ with respect to $\Theta$ then it is locally
S-identifiable from $\mathcal{X}$ with respect to $\Theta$.

The proof is in Appendix B and uses the embedding $\boldsymbol{\Phi}(\cdot)$.
By Lemma 2, PS-identifiability with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$ implies admissibility. Considering any
$\Theta$ with a similar property, a direct corollary of Theorem 2 is that PS-
identifiability with respect to $\Theta$ implies local S-identifiability with
respect to $\Theta$. Note however that the assumption that $\theta$ is
admissible cannot simply be skipped in Theorem 2.

Figure 2. Realizations of networks from (a) Example 1; (b) Example 2 ; (c)
Example 4

An example shows that indeed, local S-identifiability depends on the
constraint set $\Theta$.

######  Example 1 (see Figure 2-(a)).

On a shallow network architecture with two hidden neurons $\nu_{1},\nu_{2}$,
the identity $\mathtt{id}:\mathbb{R}\to\mathbb{R},x\mapsto x$ can be written
as $x=\mathtt{ReLU}(x-t)-\mathtt{ReLU}(-(x-t))+t=\boldsymbol{R}_{\theta_{t}}$
with
$\theta_{t}=(w_{\mu\to\nu_{1}}=1,w_{\mu\to\nu_{2}}=-1,b_{\nu_{1}}=-t,b_{\nu_{2}}=t,w_{\nu_{1}\to\eta}=1,w_{\nu_{2}\to\eta}=-1,b_{\eta}=t$)
for every $t\in\mathbb{R}$ ($\mu$ is the input neuron, $\eta$ the output
neuron). Since $\theta_{t}$ and $\theta_{t^{\prime}}$, $t\neq t^{\prime}$ have
different output bias, they are not PS-equivalent. This shows that, e.g.,
$\theta_{0}$ is not locally S-identifiable with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$. With respect to the set $\Theta$ of
networks without output bias $(b_{\eta}=0)$, as detailed in Example 5,
$\theta_{0}$ becomes PS-identifiable from $\mathcal{X}=\mathbb{R}$.

The above example includes two neurons which are _twins_ in the following
sense.

######  Definition 8 (Twin neurons).

Consider a parameter $\theta$ on a network architecture of any depth. Two
hidden neurons $\nu\neq\nu^{\prime}$ from the same layer are said to be twins
if there exists $\lambda\in\mathbb{R}$ such that
$(\boldsymbol{w}_{\bullet\to\nu},b_{\nu})=\lambda(\boldsymbol{w}_{\bullet\to\nu^{\prime}},b_{\nu^{\prime}})$.
If $\theta$ is admissible then necessarily $\lambda\neq 0$, and
$\nu,\nu^{\prime}$ are said to be positive twins if $\lambda>0$, negative
twins otherwise.
NB: Even though each hidden neuron $\nu\in H$ is (positive) twin to itself,
such a neuron is abusively said to have “no twin” if it is not twin with any
$\nu^{\prime}\neq\nu$ from the same layer. We also say that $\theta$ has no
twins if none of its neurons have any twin.

Intuitively, if $\nu,\nu^{\prime}$ are twins then the corresponding pre-
activation functions $z_{\nu}(\theta,\cdot)$ $z_{\nu^{\prime}}(\theta,\cdot)$
are collinear, and the resulting post-activation functions,
$y_{\nu}(\theta,\cdot)$ $y_{\nu^{\prime}}(\theta,\cdot)$ are also collinear
for positive twins. For negative twins, there exists linear combinations of
the post-activations that are simply proportional to the pre-activations,
somehow bypassing the effect of the ReLU nonlinearity. As proved in Appendix
C, twins _always_ prevent identifiability with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$.

######  Lemma 3.

Consider $\theta\in\Theta=\mathbb{R}^{E\cup\bar{H}}$.

  1. a)

Assume that $\theta$ is locally S-identifiable with respect to $\Theta$.
Then $\theta$ has no positive twins.

  2. b)

Assume that $\theta$ is PS-identifiable from some bounded set
$\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ with respect to $\Theta$.
Then $\theta$ has no twins.

We will see in Example 4 (in section 5) that the absolute value function (see
Figure 2-(c)) is the realization of a shallow network with two hidden neurons
that are negative twins, yet it is PS-identifiable (hence locally
S-identifiable) with respect to $\Theta=\mathbb{R}^{E\cup\bar{H}}$. It is even
locally S-identifiable from some finite set $F\subseteq\mathbb{R}$. Of course,
by Lemma 3 such a network cannot be PS-identifiable from any bounded set with
respect to $\Theta=\mathbb{R}^{E\cup\bar{H}}$.

Twins are a form of local degeneracy. For shallow networks, we will show that
this is the only form of local degeneracy (see the upcoming Lemma 5 and
Theorem 3), but we will see other forms for deeper networks (see Example 3).
As illustrated next, there are also non-local degeneracies that can prevent
identifiability.

######  Example 2 (see Figure 2-(b)).

The function

$f(x)=\begin{cases}-x,&\text{if}\ x\leq 0\\\ 0,&\text{if}\ 0\leq x\leq 1\\\
x-1,&\text{if}\ x\geq 1\end{cases}$

satisfies
$f(x)=\mathtt{ReLU}(-x)+\mathtt{ReLU}(x-1)=\mathtt{ReLU}(x)+\mathtt{ReLU}(-(x-1))-1$.
It is thus the realization of
$\theta=(w_{\mu\to\nu_{1}}=-1,w_{\mu\to\nu_{2}}=1,b_{\nu_{1}}=0,b_{\nu_{2}}=-1,w_{\nu_{1}\to\eta}=w_{\nu_{2}\to\eta}=1,b_{\eta}=0$,
but also of
$\theta^{\prime}=(w^{\prime}_{\mu\to\nu_{1}}=1,w^{\prime}_{\mu\to\nu_{2}}=-1,b^{\prime}_{\nu_{1}}=0,b^{\prime}_{\nu_{2}}=1,w^{\prime}_{\nu_{1}\to\eta}=w^{\prime}_{\nu_{2}\to\eta}=1,b^{\prime}_{\eta}=-1$,
which are not PS-equivalent since $b_{\eta}\neq b^{\prime}_{\eta}$. Yet the
theory we establish (see Lemma 5) shows that $\theta$ and $\theta^{\prime}$
are both locally S-identifiable from some finite set $F\subset\mathbb{R}$.

It turns out that the above example fails to be _irreducible_ as we formalize
next.

######  Definition 9 (Irreducibility).

A parameter $\theta$ is irreducible if for each hidden layer $1\leq\ell\leq
L-1$ and non-empty subset $T\subset N_{\ell}$ we have

(7) $\boldsymbol{W}_{\ell+1}\boldsymbol{I}_{T}\boldsymbol{W}_{\ell}\neq
0,\quad\text{with}\ \boldsymbol{I}_{T}=\mathtt{diag}(\boldsymbol{\chi}_{T}),$

with $\boldsymbol{\chi}_{T}\in\\{0,1\\}^{N_{\ell}}$ the indicator function of
$T$: $(\boldsymbol{\chi}_{T})_{\nu}=1$ if, and only if, $\nu\in T$. We denote
${\Theta_{\mathtt{irr}}}\subset\mathbb{R}^{E\cup\bar{H}}$ the set of all
irreducible parameters.

######  Fact 3.

Each irreducible parameter is also admissible.

In fact, as established in Appendix D, any PS-identifiable parameter with no
twins must be irreducible.

######  Lemma 4.

If $\theta$ is PS-identifiable from $\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$
with respect to $\Theta=\mathbb{R}^{E\cup\bar{H}}$ and has no twin, then it is
irreducible.

In particular, in light of Lemma 3, every parameter that is PS-identifiable
from a bounded $\mathcal{X}$ is irreducible. In the shallow case, a direct
consequence of irreducibility can be obtained using an “algebraic” expression
of the realization $\boldsymbol{R}_{\theta}$ (Lemma 9 in section 4): for every
input vector $x$ where $\boldsymbol{R}_{\theta}$ is differentiable, the
Jacobian of $\boldsymbol{R}_{\theta}$ is given by
$\boldsymbol{W}_{2}\boldsymbol{I}_{1}\boldsymbol{W}_{1}$ with
$\boldsymbol{I}_{1}=\mathtt{diag}(\boldsymbol{a}_{1}(\theta,x))$ (see section
4 for the introduction of notation $\boldsymbol{a}_{1}(\theta,x)$).
Irreducibility thus implies that this Jacobian can only vanish if
$\boldsymbol{a}_{1}(\theta,x)=\boldsymbol{0}$, i.e., if all neurons are
inactive. As illustrated on Example 2 (see Figure 2-(b)) this however does not
_characterize_ irreducibility, and an intuitive characterization of
irreducibility in terms of simple properties of $\boldsymbol{R}_{\theta}$ is
left to future work.

###  2.6. Identifiability conditions in the shallow case

For shallow neural networks, we prove that admissible parameters with no twins
are locally S-identifiable from a _finite_ set. Such results resonate with
previous work on the identifiability of shallow networks equipped with various
activation functions other than the ReLU [4, 5, 6, 7].

######  Lemma 5.

Consider a shallow architecture. If $\theta$ is admissible with no twins, then
there is a finite $\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ with
$\mathtt{card}(\mathcal{X})\leq(|N_{0}|+1)(|N_{1}|+1)$ from which $\theta$ is
locally S-identifiable with respect to $\Theta=\mathbb{R}^{E\cup\bar{H}}$.

The proof is in Section 5.2. Combined with irreducibility, the absence of
twins is further shown to be equivalent to PS-identifiability from a _bounded_
set. Whether this is also equivalent to PS-identifiability from a _finite_ set
is left to future work, as well as a possible explicit control of the
cardinality of such a finite set.

######  Theorem 3.

Consider a shallow network architecture. The following are equivalent:

  1. a)

there is a bounded $\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ from which
$\theta$ is PS-identifiable with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$;

  2. b)

$\theta$ has no twins and is irreducible.

###### Proof.

The implication a $\Rightarrow$ b is a consequence of Lemma 3 and Lemma 4. The
converse b $\Rightarrow$ a follows by Theorem 6-b in Section 5.3. ∎

As established with Theorem 6-a in Section 5.3, the shallow architecture
itself is identifiable in the following sense for irreducible parameters with
no twins.

######  Theorem 4.

Consider two shallow network architectures with the same input and output
layers, $N_{0}$ and $N_{2}$, and potentially distinct hidden layer $H=N_{1}$,
$H^{\prime}=N^{\prime}_{1}$. Let $\theta$, $\theta^{\prime}$ be parameters on
each architecture. Assume that $\theta$ is irreducible with no twins, and that
$\theta^{\prime}$ is admissible with no twins. If
$\boldsymbol{R}_{\theta}=\boldsymbol{R}_{\theta^{\prime}}$ on
$\mathbb{R}^{N_{0}}$ then $\mathtt{card}(N_{1})=\mathtt{card}(N^{\prime}_{1})$
and $\theta^{\prime}\sim_{PS}\theta$.

As illustrated by Example 4 in section 5, there are also shallow networks that
are PS-identifiable from $\mathcal{X}=\mathbb{R}^{N_{0}}$ but not from any
bounded set. They are of course irreducible by Lemma 4, and have no positive
twin by Lemma 3, but they have one or more pairs of negative twins.

###  2.7. A glimpse at the analysis of local identifiability

Much of the local identifiability analysis, which is conducted in detail in
section 4, relies on an important property of the embedding
$\boldsymbol{\Phi}$ (besides its ability to characterize scaling equivalence,
see Theorem 1): it provides a _locally linear parameterization_ of the
realization of the network, in the sense that given $\theta$ and for “most”
$x\in\mathbb{R}^{N_{0}}$ we have, for every $\theta^{\prime}$ in a (small
enough) neighborhood $\theta$

(8)
$\boldsymbol{R}_{\theta^{\prime}}(x)-\boldsymbol{R}_{\theta}(x)=\boldsymbol{C}_{\theta,x}\cdot\left(\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\right)$

with $\boldsymbol{C}_{\theta,x}\in\mathbb{R}^{N_{L}\times\mathcal{P}}$ some
linear operator that is _independent of $\theta^{\prime}$_, see Corrolary 3
for a precise statement. This property holds provided $x$ is a point where the
gradient of $\boldsymbol{R}_{\theta}$ (and of all pre-activations at
intermediate hidden layers) is well-defined and continuous, which motivates
the following definition.

######  Definition 10.

Consider any network architecture. Given a parameter $\theta$ we define for
each hidden neuron $\nu\in H$ the set $\Gamma_{\nu}(\theta)$ of input vectors
where $z_{\nu}(\theta,x)=0$ and the gradient $\nabla z_{\nu}(\theta,x)$ is
_well-defined_ and nonzero,

(9) $\displaystyle\Gamma_{\nu}(\theta)$
$\displaystyle:=\\{x\in\mathbb{R}^{N_{0}}:z_{\nu}(\theta,x)=0\ \text{and}\
\nabla z_{\nu}(\theta,x)\neq 0\\}.$

We define $\mathcal{X}_{\theta}\subseteq\mathbb{R}^{N_{0}}$ as the complement
to $\cup_{\nu\in H}\Gamma_{\nu}(\theta)$.

Definition 10 is extremely close to the definition of _Bent Hyperplanes_ [28]
(except that we add the non-nullity condition on the gradient). Informally,
and as previously stated [29, 30, 31], bent hyperplanes separate the input
space into _linear regions_ where the realization of the network
$x\mapsto\boldsymbol{R}_{\theta}(x)$ is affine, see Figure 3 for an
illustration.

Figure 3. We consider a network architecture with $|N_{1}|=2$ neurons on the
first hidden layer and $|N_{2}|=1$ neuron on the second hidden layer. The
input $x$ is two-dimensional: $|N_{0}|=2$ and the output is scalar:
$|N_{4}|=1$. Left: bent hyperplanes for the first hidden layer,
$\Gamma_{\nu}(\theta)$, $\nu\in N_{1}$ (blue) and second hidden layer
$\Gamma_{\nu}(\theta)$, $\nu\in N_{2}$ (red). Right: linear regions. All the
weights and biases were initialized randomly. The figures are generated with a
PyTorch script available at https://github.com/pierrestock/linear-
regions/blob/main/partition.ipynb.

For our needs, we will provide in Lemma 11 an alternate characterization of
$\mathcal{X}_{\theta}$ which we have not found elsewhere in the literature. It
will be used in Corollary 3 to formalize Property (8) for
$x\in\mathcal{X}_{\theta}$, which motivates the definition of non-degenerate
parameters.

######  Definition 11 (Non-degeneracy).

Consider the finite dimensional linear space

(10)
$\mathtt{V}(\theta):=\cap_{x\in\mathcal{X}_{\theta}}\mathtt{ker}(\boldsymbol{C}_{\theta,x})\subseteq\mathbb{R}^{\mathcal{P}},$

where $\boldsymbol{C}_{\theta,x}$ is introduced formally in Corrolary 3. A
parameter $\theta\in\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ is _$\epsilon$
-non-degenerate_ with respect to $\Theta$, where $\epsilon>0$, if it is
admissible and for every $\theta^{\prime}\in\Theta\cap B(\theta,\epsilon)$ we
have

(11)
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)\Rightarrow\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta).$

It is _non-degenerate_ with respect to $\Theta$ if there exists $\epsilon>0$
such that it is $\epsilon$-non-degenerate with respect to $\Theta$.

Exploiting the fact that all considered spaces are finite dimensional, we
characterize the space $\mathtt{V}(\theta)$ in terms of certain _activation
spaces_ (Definition 14) and prove that non-degeneracy is equivalent (see
Theorem 5, the main result of section 4) to the existence of some _finite set_
$F\subset\mathcal{X}_{\theta}$ such that $\theta$ is locally S-identifiable
from $F$ (hence also locally S-identifiable from
$\mathcal{X}=\mathbb{R}^{N_{0}}$). The cardinality of $F$ is bounded from
above using the dimension of activation spaces.

###  2.8. Non-degeneracy and irreducibility in shallow _vs_ deeper
architectures

An easy sufficient condition for non-degeneracy is to have a trivial space
$\mathtt{V}(\theta)=\\{0\\}$. For _scalar-valued_ shallow networks
($L=2,|N_{L}|=1$), we prove (cf Lemma 17 and Corollary 2 that non-degeneracy
with respect to $\Theta=\mathbb{R}^{E\cup\bar{H}}$ is in fact _equivalent_ to
$\mathtt{V}(\theta)=\\{0\\}$, and for shallow (possibly vector-valued)
networks, the latter is proved to hold if, and only if, there are no twins (by
Corollary 2 and Lemma 15). In light of Theorem 3, when combined with
irreducibility, the fact that $\mathtt{V}(\theta)=\\{0\\}$ thus becomes
equivalent (for shallow networks) to the PS-identifiability of $\theta$ from
some bounded set.

For networks of depth $L\geq 3$, any parameter such that
$\mathtt{V}(\theta)=\\{0\\}$ is of course still non-degenerate (hence locally
S-identifiable from a finite set, by Theorem 5), but this property is no
longer equivalent to the absence of twins: further conditions between layers
are required, as illustrated by the following example.

######  Example 3.

In Figure 4, we exhibit a two-hidden-layer architecture valued with a
parameter $\theta$ that presents no twin neurons (see Definition 8) but such
that $\theta$ is not locally S-identifiable (see Definition 7).

Figure 4.  A network with two hidden layers that is not locally
S-identifiable, while having no twin hidden neurons. Weights $w_{e}$ and
$w^{\prime}_{e}$, $e\in E$ are set to one on the displayed edges and to zero
on other edges, and are not depicted here for readability. Left:
parameterization $\theta$ valuing the architecture. Center: alternative
parameterization $\theta^{\prime}$ such that $\theta$ and $\theta^{\prime}$
are _not_ rescaling equivalent. Right: the two realizations $R_{\theta}$ and
$R_{\theta^{\prime}}$ coincide: for every input point
$x=(x_{\mu_{1}},x_{\mu_{2}})\in\mathbb{R}^{2},R_{\theta}(x)=R_{\theta^{\prime}}(x)$.
The construction is valid for arbitrary $\varepsilon>0$.

Characterizing concrete conditions ensuring $\mathtt{V}(\theta)=\\{0\\}$ is
left to future work. A particular challenge is to understand whether the
condition $\mathtt{V}(\theta)=\\{0\\}$, combined with (a possibly strengthened
version of) irreducibility remains equivalent to PS-identifiability from a
bounded set. We note that irreducibility in the shallow case is reminiscent of
[32, Equation (8)], a condition used to define so-called “general ReLU
networks” to provide sufficient identifiability conditions in deeper settings.
This may serve as a guide to identify stronger notions of irreducibility for
deep networks. Preliminary investigations suggest that certain tensor products
of activation vectors play a role when analyzing non-degeneracy. This is
reminiscent of the tools studied by Fornasier et al. [10] with two hidden
layers $L=3$ in a smooth context that cannot cover ReLU networks.

###  2.9. Discussion

Before diving into the technical contributions in the next Sections, we
discuss some topics of interest for the reader that are mostly out of the
scope of this work. We refer the reader to Figure 5 for a brief summary of the
results proven in this paper.

#### Local identifiability and optimization.

First, we argue that studying _local_ (instead of global) S-identifiability is
of practical interest, as discussed e.g. in [12, 13]. Indeed, neural networks
are traditionally optimized with a variant of stochastic gradient descent, or
SGD [33]. Hence, (1) during training, the optimization yields parameters that
are close to the previous ones and (2) the parameters obtained after
convergence can be expected to be locally optimal up to natural permutation
and rescaling equivalences.

#### Identifiability from a _finite_ set.

Since we are mainly interested in the problem of recovering (the equivalence
class of) $\theta$ from the knowledge of its realization
$\boldsymbol{R}_{\theta}$, we list below some questions calling for extensions
of Theorem 3. Indeed, it is not always possible to recover $\theta$ from its
realization. Even when such a recovery is theoretically possible, it may
involve having full access to the function $\boldsymbol{R}_{\theta}$, which is
not a concrete input to provide to any reconstruction algorithm. A more
practical question is: when can we recover (the equivalence class of) $\theta$
from the knowledge of finitely many samples
$\boldsymbol{R}_{\theta}(x_{i}),1\leq i\leq n$ ? When there exists a choice
(that may depend on $\theta$) of $n$ and $x_{i}$, $1\leq i\leq n$ such that
this is feasible, we also get as a byproduct a reconstruction of
$\boldsymbol{R}_{\theta}$ from the sole knowledge of its samples at these
points. Hence, another question of interest is: when can the function
$\boldsymbol{R}_{\theta}$ be identified from the knowledge of finitely many of
its samples ? This is possibly less demanding, as here it is not required to
be able to reconstruct (the equivalence class of) $\theta$ from its
realization. In both cases, since $\theta$ is not known beforehand, it is
important to ensure that the choice of the sampling set is algorithmically
feasible, for example if it is done iteratively at least the first sample must
be chosen without any knowledge on $\theta$ or $\boldsymbol{R}_{\theta}$. Of
course, answers to these questions lead to further ones, that we do not touch
upon: if $\theta$ can be identified from finitely many samples, how many
samples are sufficient444Lemma 5 partly answers this question regarding local
S-identifiability for shallow networks. (resp. necessary) ? Can we explicit a
scheme (possibly randomized) to choose these samples ? Can we explicit an
algorithm to perform reconstruction ? How stable is it to inaccuracies in the
evaluation of $\boldsymbol{R}_{\theta}(x_{i})$ or to the knowledge of $x_{i}$?

#### Reverse-engineering ReLU networks.

Here, we dicuss the work of Rolnick and Kording [9] more extensively than what
was done in the Introduction. The goal is to position our work with respect to
this interesting work. The authors present a sampling algorithm to recover a
ReLU network’s architecture and parameters, up to permutations and rescalings.
The authors prove that their algorithm terminates except for a measure-zero
set of networks and do not provide the complexity of their method in terms of
number of the samples needed to recover $\boldsymbol{R}_{\theta}$, except for
recovering the first layer’s parameters. They reason in terms of so-called
_activation_ and _linear_ regions [28] and make the following assumptions.
Recall that the sets $\Gamma_{\nu}(\theta)$ are introduced in Definition 9 for
every hidden neuron $\nu$. $\Gamma_{\nu}(\theta)$ is often called the
_separating_ or _bent_ hyperplane for neuron $\nu$.

  1. (1)

Linear Regions assumption as stated by the authors: Each [activation]555What
the authors denote as linear regions are in fact known as activation regions,
see [28].region represents a maximal connected component of input space on
which the [realization $\boldsymbol{R}_{\theta}$] is given by a single linear
function. In other words, the authors assume that activation regions and
linear regions coincide (Section 3.2 in the original paper).

  2. (2)

All the sets $\Gamma_{\nu}(\theta)$ for $\nu\in H$ have codimension 1666This
prevents the case where $\nabla R_{\theta}(x)=0$ for $x\in B(x_{0},r)$. hence
the name _separating hyperplane_ (implicitly assumed, see in particular the
first paragraph of Section 3.3).

  3. (3)

For every hidden neuron $\nu$ in layer $1\leq\ell\leq L-1$,
$\Gamma_{\nu}(\theta)$ intersects _all_ the sets
$\Gamma_{\nu^{\prime}}(\theta)$ for all neurons $\nu^{\prime}$ in a previous
layer $1\leq\ell^{\prime}<\ell\leq L-1$ (Section 5.2 in the original paper).

  4. (4)

For $\nu\neq\nu^{\prime}$ such that $\nu$ belong to layer $\ell$ and
$\nu^{\prime}$ belongs to layer $\ell^{\prime}<\ell$, $\Gamma_{\nu}(\theta)$
bends on $\Gamma_{\nu^{\prime}}(\theta)$, but $\Gamma_{\nu}(\theta)$ and
$\Gamma_{\nu^{\prime}}(\theta)$ cannot both bend at their intersection
(implicitly assumed, see in particular the first paragraph of Section 3.3).

  5. (5)

For every hidden neuron $\nu\in H$, $\Gamma_{\nu}(\theta)$ is _not bounded_
and _not disconnected_ (Section 5.2 in the original paper).

According to the authors, parameters $\theta$ that do not satisfy at least one
of these assumptions constitute a measure-zero set of networks, hence the
authors discard these cases from their analysis. In the remainder of this
paper, we aim at more precisely characterizing this measure-null zero set.
This is fully done in the shallow case, and the developed tools should be
instrumental when pursuing this mathematical study in deeper settings.

Figure 5.  Summary of the various results proven in the paper. Theorem 3
further establishes that irreducibility and the absence of twins imply PS-
identifiability from a bounded set in the shallow case.

##  3\. Rescaling invariance of the embedding

The proof of the main property of the embedding $\boldsymbol{\Phi}(\cdot)$,
Theorem 1, exploits linear operators related to $\boldsymbol{\Phi}(\cdot)$.
The following definition is motivated by the obvious observation that, if
$\theta$ has positive entries $\theta_{i}=e^{\alpha_{i}}$, $i\in
E\cup\bar{H}$, then $\boldsymbol{\Phi}(\theta)=e^{\boldsymbol{P}\alpha}$ where
the exponential is taken componentwise. This is related to the idea of
updating weights _multiplicatively_ , which is exploited in particular by
Bernstein [34] to investigate learning stability.

######  Definition 12.

Consider $\boldsymbol{P}:\mathbb{R}^{E\cup\bar{H}}\to\mathbb{R}^{\mathcal{P}}$
the linear operator defined for $\boldsymbol{u}\in\mathbb{R}^{E\cup\bar{H}}$
as

(12) $(\boldsymbol{P}\boldsymbol{u})_{p}:=\begin{cases}\sum_{e\in
p}u_{e},&\text{for each full path}\ p\in\mathcal{P}_{0};\\\
u_{p_{\ell}}+\sum_{e\in p}u_{e},&\text{for each partial path}\
p=(p_{\ell},\ldots,p_{L})\in\mathcal{P}_{\ell},\ 1\leq\ell\leq L.\end{cases}$

With the notations from Remark 1 we can also write
$(\boldsymbol{P}\boldsymbol{u})_{p}=\sum_{i\in p}u_{i}$.

Before proving Theorem 1 we express a few technical lemmas.

######  Lemma 6.

For every $\theta\in\mathbb{R}^{E\cup\bar{H}}$, with
$\mathtt{supp}(\boldsymbol{\Phi}(\theta))=\\{p\in\mathcal{P}:{\Phi}_{p}(\theta)\neq
0\\}$ we have

(13) $\\{i\in E\cup\bar{H}:\exists
p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta)),p\ni i\\}\subseteq\\{i\in
E\cup\bar{H}:\theta_{i}\neq 0\\}=\mathtt{supp}(\theta).$

If $\theta\in\mathbb{R}^{E\cup\bar{H}}$ is admissible then we further have

(14) $\mathtt{supp}(\theta)=\\{i\in E\cup\bar{H}:\exists
p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta)),p\ni i\\}.$

###### Proof.

For each path $p\in\mathcal{P}$ denote $I_{p}=\\{i\in E\cup\bar{H}:i\in p\\}$
and observe first that the left hand side in (13) is
$\cup_{p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta))}I_{p}$. Consider
$p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta))$. Since
${\Phi}_{p}(\theta)=\Pi_{i\in p}\theta_{i}$, we have $\theta_{i}\neq 0$ for
each $i\in I_{p}$, i.e., $I_{p}\subseteq\mathtt{supp}(\theta)$. As this holds
for every $p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta))$ we obtain
$\cup_{p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta))}I_{p}\subseteq\mathtt{supp}(\theta)$.
This establishes (13).

Assuming now that $\theta$ is admissible, consider $i\in\mathtt{supp}(\theta)$
and distinguish three cases. If $i=\eta\in N_{L}$ is an output neuron, then
$p=(\eta)\ni i$ yields ${\Phi}_{p}(\theta)=\theta_{\eta}\neq 0$. If $i=\nu\in
H$ is a hidden neuron, then since $\theta$ is admissible there is a path $p\ni
i$ with nonzero weights connecting $\nu$ to an output neuron. This path
satisfies ${\Phi}_{p}(\theta)\neq 0$. Finally, if $i=\nu\to\nu^{\prime}$ is an
edge, then since $\theta$ is admissible there is a path connecting the input
layer to $\nu$ and a path connecting $\nu^{\prime}$ to the output layer, both
with nonzero weights. Concatenating them yields a path $p\ni i$ such that
${\Phi}_{p}(\theta)\neq 0$. In all cases, we obtain the existence of a path
$p\in\mathtt{supp}(\boldsymbol{\Phi}(\theta))$ such that $p\ni i$. This
establishes (14). ∎

######  Corollary 1.

Consider $\theta,\theta^{\prime}\in\mathbb{R}^{E\cup\bar{H}}$ such that
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$. If $\theta$ is
admissible then $\mathtt{supp}(\theta^{\prime})=\mathtt{supp}(\theta)$ and
$\theta^{\prime}$ is also admissible.

###### Proof.

By Lemma 6 and the equality
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$ we have

$\displaystyle\mathtt{supp}(\theta)$ $\displaystyle=\\{i\in
E\cup\bar{H}:\exists p\in\mathcal{P},{\Phi}_{p}(\theta)\neq 0,i\in p\\}$
$\displaystyle=\\{i\in E\cup\bar{H}:\exists
p\in\mathcal{P},{\Phi}_{p}(\theta^{\prime})\neq 0,i\in
p\\}\subseteq\mathtt{supp}(\theta^{\prime}).$

The fact that $\theta$ is admissible is a property of its support, and the
inclusion $\mathtt{supp}(\theta)\subseteq\mathtt{supp}(\theta^{\prime})$
implies that $\theta^{\prime}$ is also admissible. It follows using Lemma 6
again that the rightmost inclusion above is an equality. ∎

######  Lemma 7.

Given $\theta\in\mathbb{R}^{E\cup\bar{H}}$ an admissible parameter, consider
the spaces

(15) $\displaystyle W_{\theta}$
$\displaystyle:=\\{\alpha\in\mathbb{R}^{E\cup\bar{H}},[\boldsymbol{\Phi}(\theta)\odot\boldsymbol{P}\alpha]_{\mathcal{P}_{0}}=0\\}$
(16) $\displaystyle V_{\theta}$ $\displaystyle:=\\{\alpha\in
W_{\theta},\alpha_{\bar{H}}=0,\mathtt{supp}(\alpha)\subseteq\mathtt{supp}(\theta)\\}.$

Given $\alpha\in W_{\theta}$, define for each hidden neuron $\nu\in H$

(17) $\displaystyle(\boldsymbol{S}_{\theta}\alpha)_{\nu}\triangleq-\sum_{e\in
p}\alpha_{e}$

with $p$ any path with edges $e\in E\cap\mathtt{supp}(\theta)$ joining $\nu$
to an output neuron $\eta$.

  1. a)

The linear map $\boldsymbol{S}_{\theta}\colon W_{\theta}\to\mathbb{R}^{H}$ is
well-defined and independent of the choice of $p$ and $\eta$;

  2. b)

Its restriction $\boldsymbol{S}_{\theta}:V_{\theta}\to\mathbb{R}^{H}$ is an
isomorphism. Its inverse $\boldsymbol{S}_{\theta}^{-1}:\mathbb{R}^{H}\to
V_{\theta}$ is such that for any $\beta\in\mathbb{R}^{H}$,
$\boldsymbol{S}_{\theta}^{-1}\beta=\alpha$ where $\alpha_{\bar{H}}=0$ and for
each edge $e=\mu\to\nu\in E\cap\mathtt{supp}(\theta)$,

(18) $\displaystyle\alpha_{e}\triangleq\begin{cases}-\beta_{\mu}&\text{if}\
\mu\in N_{L-1}\ (\text{and}\ \nu\in N_{L})\\\
\beta_{\nu}-\beta_{\mu}&\text{if}\ \mu\in N_{\ell},1\leq\ell\leq L-2\\\
\beta_{\nu}&\text{if}\ \mu\in N_{0}.\end{cases}$

while $\alpha_{e}=0$ for each $e\in E\backslash\mathtt{supp}(\theta)$.

The proof is postponed to Appendix A to keep the reading flow.

###### Proof of Theorem 1.

By Definition 1, $\theta\sim_{S}\theta^{\prime}$ if, and only if, there are
$\\{\lambda_{\nu}\\}_{\nu\in H\cup N_{0}\cup N_{L}}$ such that

(19) $\displaystyle\lambda_{\nu}$ $\displaystyle>0,\quad\forall\nu\in
H,\quad\text{and}\ \lambda_{\nu}=1,\quad\forall\nu\in N_{0}\cup N_{L}$ (20)
$\displaystyle\theta^{\prime}_{e}$
$\displaystyle=\lambda_{\mu}^{-1}\theta_{e}\lambda_{\nu},\quad\forall
e=\mu\to\nu\in E\quad\text{and}\
\theta^{\prime}_{\nu}=\theta_{\nu}\lambda_{\nu},\quad\forall\nu\in\bar{H}.$

Thus, if $\theta^{\prime}\sim_{S}\theta$ then
$\mathtt{sign}(\theta^{\prime})=\mathtt{sign}(\theta)$, and for every path
$p=(p_{0},\ldots,p_{L})\in\mathcal{P}_{0}$ we get

$\displaystyle{\Phi}_{p}(\theta^{\prime})$
$\displaystyle=\Pi_{k=0}^{L-1}\theta^{\prime}_{p_{k}\to
p_{k+1}}=\Pi_{k=0}^{L-1}(\lambda_{p_{k}}^{-1}\theta_{p_{k}\to
p_{k+1}}\lambda_{p_{k+1}})=\Pi_{k=0}^{L-1}\theta_{p_{k}\to
p_{k+1}}={\Phi}_{p}(\theta),$ while for
$p=(p_{\ell},\ldots,p_{L})\in\mathcal{P}_{\ell}$, $1\leq\ell\leq L$
$\displaystyle{\Phi}_{p}(\theta^{\prime})$
$\displaystyle=\theta^{\prime}_{p_{\ell}}\Pi_{k=\ell}^{L-1}\theta^{\prime}_{p_{k}\to
p_{k+1}}=\theta_{p_{\ell}}\lambda_{p_{\ell}}\Pi_{k=\ell}^{L-1}(\lambda_{p_{k}}^{-1}\theta_{p_{k}\to
p_{k+1}}\lambda_{p_{k+1}})=\theta_{p_{\ell}}\Pi_{k=0}^{L-1}\theta_{p_{k}\to
p_{k+1}}={\Phi}_{p}(\theta).$

This shows $\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$.

Conversely, assume that $\theta$ is admissible and that
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$ and
$\mathtt{sign}(\theta^{\prime}_{E})=\mathtt{sign}(\theta_{E})$. By Corollary
1, since $\theta$ is admissible and
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$, we have
$\mathtt{supp}(\theta^{\prime})=\mathtt{supp}(\theta)$ hence there are
$\gamma_{i}\neq 0,i\in\mathtt{supp}(\theta)$ such that
$\theta^{\prime}_{i}=\gamma_{i}\theta_{i}$ for each
$i\in\mathtt{supp}(\theta)$. Since
$\mathtt{sign}(\theta^{\prime}_{E})=\mathtt{sign}(\theta_{E})$, we have
$\gamma_{e}>0$ for every $e\in E\cap\mathtt{supp}(\theta)$. Consider
$\alpha\in\mathbb{R}^{E\cup\bar{H}}$ such that $\alpha_{\bar{H}}=0$,
$e^{\alpha_{e}}=\gamma_{e}$ for $e\in E\cap\mathtt{supp}(\theta)$, and
$\alpha_{e}=0$ for $e\in E\backslash\mathtt{supp}(\theta)$. For each
$p\in\mathcal{P}_{0}$

${\Phi}_{p}(\theta^{\prime})=\Pi_{e\in p}\theta^{\prime}_{e}=\Pi_{e\in
p}(\theta_{e}e^{\alpha_{e}})={\Phi}_{p}(\theta)e^{\sum_{e\in
p}\alpha_{e}}={\Phi}_{p}(\theta)\odot e^{(\boldsymbol{P}\alpha)_{p}}.$

Since $\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$, it
follows that for each $p\in\mathcal{P}_{0}$ such that ${\Phi}_{p}(\theta)\neq
0$ we have $e^{(\boldsymbol{P}\gamma)_{p}}=1$, i.e.,
$(\boldsymbol{P}\alpha)_{p}=0$. Thus,
${\Phi}_{p}(\theta)(\boldsymbol{P}\alpha)_{p}=0$ for all
$p\in\mathcal{P}_{0}$, i.e.,
$[\boldsymbol{\Phi}(\theta)\odot\boldsymbol{P}\alpha]_{\mathcal{P}_{0}}=0$.
Since $\alpha_{\bar{H}}=0$, we get that $\alpha$ belongs to the space
$V_{\theta}$ defined in (16) in Lemma 7. Since $\theta$ is admissible, the
linear operator $\boldsymbol{S}_{\theta}$ defined in Lemma 7 is a well-defined
bijection from $V_{\theta}$ to $\mathbb{R}^{H}$, hence $\alpha$ is related to
$\beta:=\boldsymbol{S}_{\theta}\alpha\in\mathbb{R}^{H}$ through the relation
(18). Considering $\delta\in\mathbb{R}^{N_{0}\cup H\cup N_{L}}$ with
$\delta_{\nu}:=\beta_{\nu}$ for $\nu\in H$, $\delta_{\nu}=0$ for $\nu\in
N_{0}\cup N_{L}$, relation (18) implies

$\alpha_{e}=\delta_{\nu}-\delta_{\mu},\quad\forall e=\mu\to\nu\in
E\cap\mathtt{supp}(\theta).$

Setting $\lambda_{\nu}:=e^{\delta_{\nu}}$ for each $\nu\in N_{0}\cup H\cup
N_{L}$, it follows that for each $e=\mu\to\nu\in E$ we have
$\theta^{\prime}_{e}=\lambda_{\mu}^{-1}\theta_{e}\lambda_{\nu}$. Since
$\mathtt{supp}(\theta)=\mathtt{supp}(\theta)$, this also trivially holds for
$e\in E\backslash\mathtt{supp}(\theta)$.

To conclude, we show that $\theta^{\prime}_{\nu}=\theta_{\nu}\lambda_{\nu}$
for each $\nu\in\bar{H}$. As this holds trivially for
$\nu\in\bar{H}\cap\mathtt{supp}(\theta)$, we focus on
$\nu\in\bar{H}\cap\mathtt{supp}(\theta)$. First, we treat the case of $\eta\in
N_{L}\cap\mathtt{supp}(\theta)$ by observing that, with
$p=(\eta)\in\mathcal{P}_{L}$ we have
$\theta^{\prime}_{\eta}={\Phi}_{p}(\theta^{\prime})={\Phi}_{p}(\theta)=\theta_{\eta}=\theta_{\eta}\lambda_{\eta}$
since $\lambda_{\eta}=e^{\delta_{\eta}}=1$ by definition of
$\delta_{\eta}:=0$. Now consider $\nu\in H\cap\mathtt{supp}(\theta)$. Since
$\theta$ is admissible, there is a partial path $p$ connecting $\nu$ to some
output neuron $\eta$ with edges in $\mathtt{supp}(\theta)$. Since $-\sum_{e\in
p}\alpha_{e}=(\boldsymbol{S}_{\theta}\alpha)_{\nu}=\beta_{\nu}=\delta_{\nu}$
we have

$\displaystyle\theta^{\prime}_{\nu}\Pi_{e\in
p}\theta^{\prime}_{e}={\Phi}_{p}(\theta^{\prime})={\Phi}_{p}(\theta)=\theta_{\nu}\Pi_{e\in
p}\theta_{e}=\theta_{\nu}\Pi_{e\in p}\theta^{\prime}_{e}e^{-\alpha_{e}}$
$\displaystyle=\theta_{\nu}(\Pi_{e\in p}\theta^{\prime}_{e})e^{-\sum_{e\in
p}\alpha_{e}}$ $\displaystyle=\theta_{\nu}(\Pi_{e\in
p}\theta^{\prime}_{e})e^{\delta_{\nu}}=\theta_{\nu}(\Pi_{e\in
p}\theta^{\prime}_{e})\lambda_{\nu}.$

We conclude using that $\Pi_{e\in p}\theta^{\prime}_{e}\neq 0$ since all edges
$e\in p$ belong to $\mathtt{supp}(\theta^{\prime})=\mathtt{supp}(\theta)$. ∎

##  4\. Analyzing local identifiability

Equipped with the rescaling-invariant embedding $\boldsymbol{\Phi}(\cdot)$ we
now establish the claimed local identifiability results. First, we need to
introduce notations for the activation status of neurons and paths and use
them to provide several expressions of the realization
$\boldsymbol{R}_{\theta}$ before providing the main result of the section,
Theorem 5.

###  4.1. Activation status of neurons and paths, and activation spaces

The forthcoming analysis heavily involves the activation status of each hidden
neuron $\nu\in H$,
$a_{\nu}(\theta,x)=\mathtt{1}_{z_{\nu}(\theta,x)>0}\in\\{0,1\\},$ which gives
rise to the activation status of each hidden layer
$\boldsymbol{a}_{\ell}(\theta,x)=(a_{\nu}(\theta,x))_{\nu\in N_{\ell}}$,
$1\leq\ell\leq L-1$, and the global activation status
$\boldsymbol{a}(\theta,x)=(a_{\nu}(\theta,x))_{\nu\in
H}=(\boldsymbol{a}_{\ell}(\theta,x))_{1\leq\ell\leq L-1}$.

######  Definition 13.

The activation of a path $p$ (full or partial) is defined as

$\alpha_{p}(\theta,x):=\Pi_{\nu\in H\cap p}a_{\nu}(\theta,x)\in\\{0,1\\}$

where for $p=(p_{\ell},\ldots,p_{L})\in\mathcal{P}_{\ell}$ we denote the set
of _hidden_ neurons visited by the path $p$ using the shorthand $H\cap
p:=\\{\nu\in H,\exists
i\in\llbracket\max(\ell,1),L-1\rrbracket,\nu=p_{i}\\}\subset H$.

######  Remark 4.

By convention, a product over an empty set is $1$. If $p$ contains no hidden
neuron (e.g. , if $p=(\eta)\in\mathcal{P}_{L}$, $L\geq 1$) its activation is
$\alpha_{p}(\theta,x)=1$ for every $x$.

With $\mathcal{Q}:=\cup_{\ell=1}^{L-1}\mathcal{Q}_{\ell}$ the set of all
“partial” paths $q\in(q_{\ell},\ldots,q_{L-1})$ from a hidden layer
$1\leq\ell\leq L-1$ to the penultimate layer $L-1$ (cf Definition 5 for the
formal definition of $\mathcal{Q}_{\ell}$), we define the binary-vector-valued
function
$\boldsymbol{\alpha}(\theta,x):=(\alpha_{q}(\theta,x))_{q\in\mathcal{Q}}\in\\{0,1\\}^{\mathcal{Q}}$.
We also define variants that are notably useful to account for output biases

$\bar{\boldsymbol{a}}_{\ell}(\theta,x)=\left(\begin{matrix}\boldsymbol{a}_{\ell}(\theta,x)\\\
1\end{matrix}\right)\in\\{0,1\\}^{N_{\ell}+1}\ \text{and}\
\bar{\boldsymbol{\alpha}}(\theta,x):=\left(\begin{matrix}\boldsymbol{\alpha}(\theta,x)\\\
1\end{matrix}\right)\in\\{0,1\\}^{\mathcal{Q}+1}$

where for any set $A,B$ we use the shorthand $A^{B+1}=A^{B}\times A$.

To state the connections between non-degeneracy and local S-identifiability
from finite sets, it is convenient to observe that the linear space
$\mathtt{V}(\theta)$ from Definition 11 can be characterized using simpler
linear spaces called _activation spaces_.

######  Definition 14 (Activation spaces, activation dimension).

The activation spaces associated to $\theta\in\mathbb{R}^{E\cup\bar{H}}$ are

(21) $\displaystyle\mathtt{\bar{A}}(\theta)$
$\displaystyle:=\mathtt{span}\left\\{\bar{\boldsymbol{\alpha}}(\theta,x),x\in\mathcal{X}_{\theta}\right\\}\subseteq\mathbb{R}^{\mathcal{Q}+1}.$
(22) $\displaystyle\mathtt{A}(\theta)$
$\displaystyle=\mathtt{span}\left\\{\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x),x\in\mathcal{X}_{\theta}\right\\}=\boldsymbol{Q}\mathtt{\bar{A}}(\theta)\subseteq\mathbb{R}^{\mathcal{Q}_{1}}$

with $\boldsymbol{Q}$ as in Lemma 10. We define its _activation dimension_ as
$\mathtt{actdim}(\theta)=\mathtt{dim}\left(\mathtt{\bar{A}}(\theta)\right)$.

######  Remark 5.

Observe that if $\theta$ and $\tilde{\theta}$ share the same $L-1$ first
affine layers
$(\boldsymbol{W}_{\ell},\boldsymbol{b}_{\ell})=(\widetilde{\boldsymbol{W}}_{\ell},\widetilde{b}_{\ell})_{\ell=0}^{L-1}$
then their activation spaces are identical. This holds _even if the dimension
of the output layers of $\tilde{\theta}$ and $\theta$ differ_.

######  Lemma 8.

Viewing $\mathbb{R}^{\mathcal{P}}$ as the product of $N_{L}\times N_{0}$
copies of $\mathbb{R}^{\mathcal{Q}_{1}}$ and $N_{L}$ copies of
$\mathbb{R}^{\mathcal{Q}+1}$,
$\mathtt{V}(\theta)\subset\mathbb{R}^{\mathcal{P}}$ is the product of
$N_{L}\times N_{0}$ copies of
$\mathtt{A}^{\perp}(\theta)\subseteq\mathbb{R}^{\mathcal{Q}_{1}}$ and $N_{L}$
copies of $\mathtt{\bar{A}}^{\perp}(\theta)$.

The proof is postponed to after Corollary 3 as it uses notations introduced
there.

######  Corollary 2.

$\mathtt{V}(\theta)=\\{0\\}$ if, and only if,
$\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$.

###### Proof.

If $\mathtt{V}(\theta)=\\{0\\}$ then by Lemma 8 we have
$\mathtt{\bar{A}}^{\perp}(\theta)=\\{0\\}$ hence
$\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$. Vice-versa if
$\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$ then
$\mathtt{A}(\theta)=\boldsymbol{Q}\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}_{1}}$.
By Lemma 8 it follows that $\mathtt{V}(\theta)=\\{0\\}$, ∎

###  4.2. “Algebraic” expressions of the realization

We can express the realization using weight matrices, bias vectors and
layerwise binary activation vectors. A similar formula is stated without
taking the biases into account in [16][Lemma A.2] whereas [35] performs
analogous computations for gradient computations, still without biases.

######  Lemma 9.

Consider $\theta$ a network parameter of depth $L\geq 1$. Denote
$\boldsymbol{I}_{0}=\boldsymbol{Id}_{\mathbb{R}^{N_{0}}}$ and for each $x$ and
$1\leq\ell\leq L-1$,
$\boldsymbol{I}_{\ell}=\mathtt{diag}(\boldsymbol{a}_{\ell}(\theta,x))$. The
realization of $\theta$ satisfies

(23)
$\boldsymbol{R}_{\theta}(x)=\left(\Pi_{\ell=1}^{L}\boldsymbol{W_{\ell}}\boldsymbol{I}_{\ell-1}\right)x+\sum_{\ell^{\prime}=1}^{L}\left(\Pi_{\ell=\ell^{\prime}+1}^{L}\boldsymbol{W}_{\ell}\boldsymbol{I}_{\ell-1}\right)\boldsymbol{b}_{\ell^{\prime}}$

with the convention that a product over an empty set is the identity matrix.

The proof is in Appendix E. To conduct an analysis of the local
S-identifiability of a parameter, another expression of
$\boldsymbol{R}_{\theta}$ where the embedding $\boldsymbol{\Phi}(\theta)$
appears more explicitly will be useful. We rewrite (23) using
$\boldsymbol{\Phi}(\theta)$ and the activation vector
$\bar{\boldsymbol{\alpha}}(\theta,x)$.

######  Lemma 10.

Consider $\theta$ a network parameter of depth $L\geq 2$. For each $\eta\in
N_{L}$, denote777Superscripts $\mathtt{i}$ and $\mathtt{h}$ stand for “input”
and “hidden”, as $\boldsymbol{\Phi}^{\mathtt{i}}$ is associated to full paths
starting from the input layer, while $\boldsymbol{\Phi}^{\mathtt{h}}$
corresponds to partial paths starting from a hidden (or the output) layer.

(24) $\displaystyle\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)$
$\displaystyle:=\left({\Phi}_{\mu\to
q\to\eta}(\theta)\right)_{q\in\mathcal{Q}_{1},\mu\in
N_{0}}\in\mathbb{R}^{\mathcal{Q}_{1}\times N_{0}}$ (25)
$\displaystyle\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)$
$\displaystyle:=\left(\begin{matrix}({\Phi}_{q\to\eta}(\theta))_{q\in\mathcal{Q}}\\\
\theta_{\eta}\end{matrix}\right)\in\mathbb{R}^{\mathcal{Q}+1}$

Up to reshaping, $\boldsymbol{\Phi}(\theta)\in\mathbb{R}^{\mathcal{P}}$ is the
concatenation of matrices
$\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)\in\mathbb{R}^{\mathcal{Q}_{1}\times
N_{0}}$ and vectors
$\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)\in\mathbb{R}^{\mathcal{Q}+1}$
over all output neurons $\eta\in N_{L}$. For each output neuron $\eta\in
N_{L}$ we have

(26) $\displaystyle\boldsymbol{R}_{\theta}(x)_{\eta}$
$\displaystyle=\langle\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)x\rangle+\langle\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)\rangle$

where
$\boldsymbol{Q}:\mathbb{R}^{\mathcal{Q}+1}\to\mathbb{R}^{\mathcal{Q}_{1}}$ is
the canonical restriction to $\mathcal{Q}_{1}\subset\mathcal{Q}$.

The proof of Lemma 10 is in Appendix E. It yields an expression of
$\boldsymbol{R}_{\theta}$ that perfectly fits the upcoming analysis of local
S-identifiability. A more abstract (but probably somewhat more digestible)
version of the same result implies Property (8) as claimed.

######  Corollary 3.

Consider $\theta$ a network parameter of depth $L\geq 2$. For each
$x\in\mathbb{R}^{N_{0}}$ let $\boldsymbol{L}_{\theta,x}$ be the linear form on
$\mathbb{R}^{\mathcal{Q}_{1}\times N_{0}}\times\mathbb{R}^{\mathcal{Q}+1}$
defined as

$\boldsymbol{L}_{\theta,x}\\{(\boldsymbol{M},\boldsymbol{v})\\}:=\langle\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{M}x\rangle+\langle\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{v}\rangle,\quad\boldsymbol{M}\in\mathbb{R}^{\mathcal{Q}_{1}\times
N_{0}},\quad\boldsymbol{v}\in\mathbb{R}^{\mathcal{Q}+1}$

Define $\boldsymbol{C}_{\theta,x}\in\mathbb{R}^{N_{L}\times\mathcal{P}}$ the
matrix associated to the linear operator mapping each
$\boldsymbol{\phi}\in\mathbb{R}^{\mathcal{P}}$, seen as a reshaped
concatenation of matrices
$\boldsymbol{\phi}_{\eta}^{\mathtt{i}}\in\mathbb{R}^{\mathcal{Q}_{1}\times
N_{0}}$ and vectors
$\boldsymbol{\phi}_{\eta}^{\mathtt{h}}\in\mathbb{R}^{\mathcal{Q}+1}$ as in
Lemma 10, to $\boldsymbol{r}:=(r_{\eta})_{\eta\in N_{L}}$, with
$r_{\eta}=\boldsymbol{L}_{\theta,x}\\{(\boldsymbol{\phi}_{\eta}^{\mathtt{i}},\boldsymbol{\phi}_{\eta}^{\mathtt{h}})\\}.$
We have

(27)
$\boldsymbol{R}_{\theta}(x)=\boldsymbol{C}_{\theta,x}\cdot\boldsymbol{\Phi}(\theta)$

We are now equipped with the notations needed to prove Lemma 8. The proof also
relies on the following alternative characterization of the set
$\mathcal{X}_{\theta}$ from Definition 10 that we did not find elsewhere. It
is proved in Appendix F.

######  Lemma 11.

Given a parameter $\theta$, consider the open set of input variables $x$ such
that $(\theta^{\prime},z)\mapsto\boldsymbol{a}(\theta^{\prime},z)$ is locally
constant in some neighborhood of $(\theta,x)$.

(28)
$\displaystyle\mathcal{X}_{\theta}^{\prime}:=\\{x\in\mathbb{R}^{N_{0}}:\exists\epsilon,r>0,\
\forall(\theta,z)\in B(\theta,\epsilon)\times B(x,r),\
\boldsymbol{a}(\theta^{\prime},z)=\boldsymbol{a}(\theta,x)\\}.$

with the convention that $\mathcal{X}_{\theta}^{\prime}=\mathbb{R}^{N_{0}}$ if
the network depth is $L=1$. This set coincides exactly with the set
$\mathcal{X}_{\theta}$ from Definition 10.

###### Proof of Lemma 8.

Consider a vector $\boldsymbol{\phi}\in\mathbb{R}^{\mathcal{P}}$ and its
representation as
$\boldsymbol{\phi}_{\eta}^{\mathtt{i}}\in\mathbb{R}^{\mathcal{Q}_{1}\times
N_{0}}$, $\boldsymbol{\phi}_{\eta}^{\mathtt{h}}\in\mathbb{R}^{\mathcal{Q}}$,
$\eta\in N_{L}$. By definition $\boldsymbol{\phi}\in\mathtt{V}(\theta)$ if,
and only if, $\boldsymbol{C}_{\theta,x}\boldsymbol{\phi}=0,\ \forall
x\in\mathcal{X}_{\theta}$, i.e., for each $\eta\in N_{L}$ we have

(29)
$\displaystyle\langle\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{\phi}^{\mathtt{i}}_{\eta}x\rangle+\langle\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{\phi}^{\mathtt{h}}_{\eta}\rangle=0,\
\forall x\in\mathcal{X}_{\theta}.$

By Lemma 11, $x^{\prime}\mapsto\bar{\boldsymbol{\alpha}}(\theta,x^{\prime})$
is locally constant in the neighborhood of each $x\in\mathcal{X}_{\theta}$,
hence the left-hand-side in (29) is locally affine with respect to $x$, and
(29) is thus equivalent to

(30)
$\displaystyle\begin{cases}[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x)]^{\top}\boldsymbol{\phi}^{\mathtt{i}}_{\eta}&=\boldsymbol{0}_{1\times
N_{0}}\\\
\langle\bar{\boldsymbol{\alpha}}(\theta,x),\boldsymbol{\phi}^{\mathtt{h}}_{\eta}\rangle&=0\end{cases},\
\forall x\in\mathcal{X}_{\theta},$

that is to say each column of $\boldsymbol{\phi}^{\mathtt{i}}_{\eta}$, is
orthogonal to $\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x)$, and
$\boldsymbol{\phi}^{\mathtt{h}}_{\eta}$ is orthogonal to
$\bar{\boldsymbol{\alpha}}(\theta,x)$ for every $x\in\mathcal{X}_{\theta}$. We
conclude using the definition of
$\mathtt{A}(\theta),\mathtt{\bar{A}}(\theta)$. ∎

###  4.3. Non-degeneracy and local S-identifiability

We can now state the main result of this section.

######  Theorem 5.

Consider $\theta\in\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$. The following
are equivalent:

  1. i)

$\theta$ is non-degenerate with respect to $\Theta$;

  2. ii)

there is a finite $F\subset\mathcal{X}_{\theta}$ such that $\theta$ is locally
S-identifiable from $F$ with respect to $\Theta$.

  3. iii)

there is a compact $K\subset\mathcal{X}_{\theta}$ such that $\theta$ is
locally S-identifiable from $K$ wrt $\Theta$.

When they hold, the finite set $F$ can be chosen such that

(31)
${\color[rgb]{0,0,0}\mathtt{card}(F)\leq(|N_{0}|+1)\mathtt{actdim}(\theta)}.$

######  Remark 6.

We exhibit in Example 4 a PS-identifiable (hence locally S-identifiable)
parameter $\theta$ that is degenerate, i.e., not locally S-identifiable from
any compact $K\subseteq\mathcal{X}_{\theta}$.

###### Proof.

i) $\Rightarrow$ ii) Consider $\epsilon>0$ such that $\theta$ is
$\epsilon$-non-degenerate with respect to $\Theta$. To establish the existence
of $F$ such that $\theta$ is locally S-identifiable from $F$ with respect to
$\Theta$, we use a Lemma which proof is postponed.

######  Lemma 12.

Consider $\theta\in\mathbb{R}^{E\cup\bar{H}}$.

  1. a)

There exists $\epsilon>0$ and a set $F\subset\mathcal{X}_{\theta}$ of
cardinality at most $(N_{0}+1)\mathtt{actdim}(\theta)$ such that: for each
$\theta^{\prime}\in B(\theta,\epsilon)$, if
$\boldsymbol{R}_{\theta^{\prime}}=\boldsymbol{R}_{\theta}$ on $F$, then
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$.

  2. b)

For every compact set $K\subset\mathcal{X}_{\theta}$, there exists
$\epsilon^{\prime}>0$ such that: for each $\theta^{\prime}\in
B(\theta,\epsilon^{\prime})$, if
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$,
then $\boldsymbol{R}_{\theta^{\prime}}(x)=\boldsymbol{R}_{\theta}(x)$ for all
$x\in K$.

Let $\epsilon_{0}$, $F$ be given by Lemma 12-a and set
$\epsilon_{1}:=\min(\epsilon_{0},\epsilon,\eta/2)$ where
$\eta:=\min_{i\in\mathtt{supp}(\theta)}|\theta_{i}|$. We will show that
$\theta$ is $\epsilon_{1}$-locally S-identifiable from $F$. For this, consider
$\theta^{\prime}\in\Theta\cap B(\theta,\epsilon_{1})$ and assume that
$\boldsymbol{R}_{\theta^{\prime}}=\boldsymbol{R}_{\theta}$ on $K$. By Lemma
12-a, since $\theta^{\prime}\in B(\theta,\epsilon_{0})$, we have
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$.
Since $\theta^{\prime}\in B(\theta,\epsilon)$ and $\theta$ is $\epsilon$-non-
degenerate, this implies
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$ hence (recall
that, since $\theta$ is non-degenerate, it is admissible by definition) by
Lemma 6 we have $\mathtt{supp}(\theta^{\prime})=\mathtt{supp}(\theta)$. Since
$\theta^{\prime}\in B(\theta,\eta/2)$ we further have
$\mathtt{sign}(\theta^{\prime}_{i})=\mathtt{sign}(\theta_{i})$ for every
$i\in\mathtt{supp}(\theta)$, hence
$\mathtt{sign}(\theta^{\prime})=\mathtt{sign}(\theta)$. By Theorem 1 we obtain
$\theta^{\prime}\sim_{S}\theta$.

ii) $\Rightarrow$ iii) Simply observe that a finite set is compact.

iii) $\Rightarrow$ i) Consider $\epsilon>0$ such that $\theta$ is
$\epsilon$-locally identifiable from $K$ with respect to $\Theta$. By Lemma
12-b for the compact set $K$, there is $\epsilon_{0}>0$ such that: for each
$\theta^{\prime}\in B(\theta,\epsilon_{0})$,
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)\Rightarrow(\boldsymbol{R}_{\theta^{\prime}}(x)=\boldsymbol{R}_{\theta}(x),\forall
x\in K)$. Set $\epsilon_{1}:=\min(\epsilon,\epsilon_{0})$. We will show that
$\theta$ is $\epsilon_{1}$-non-degenerate with respect to $\Theta$.
Considering $\theta^{\prime}\in\Theta\cap B(\theta,\epsilon_{1})$ such that
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$
we now show that
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$. Since
$\theta^{\prime}\in B(\theta,\epsilon_{0})$ and
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$,
we have $\boldsymbol{R}_{\theta^{\prime}}(x)=\boldsymbol{R}_{\theta}(x)$ for
all $x\in K$. Since $\theta^{\prime}\in\Theta\cap B(\theta,\epsilon)$ and
$\theta$ is locally S-identifiable from $K$ with respect to $\Theta$ this
implies $\theta^{\prime}\sim_{S}\theta$, hence by Theorem 1 we have
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$. ∎

###### Proof of Lemma 12.

We begin with some preliminaries. Since
$\mathtt{\bar{A}}(\theta)\subseteq\mathbb{R}^{\mathcal{Q}+1}$, it is finite
dimensional hence there is a finite set
$\mathcal{Z}_{\theta}\subset\mathcal{X}_{\theta}$ such that
$\mathtt{card}(\mathcal{Z}_{\theta})=\mathtt{actdim}(\theta)$ and

(32)
$\displaystyle\mathtt{\bar{A}}(\theta)=\mathtt{span}\left\\{\bar{\boldsymbol{\alpha}}(\theta,z),z\in\mathcal{Z}_{\theta}\right\\}.$

By Lemma 11, for each $z\in\mathcal{Z}_{\theta}$ there exists
$\epsilon(z),r(z)>0$ such that, for every $\theta^{\prime}\in
B(\theta,\epsilon(z))$ and $x\in B(z,r(z))$, we have
$\boldsymbol{a}(\theta^{\prime},x)=\boldsymbol{a}(\theta,z)$, hence
$\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)=\bar{\boldsymbol{\alpha}}(\theta,z)$.
Since $\mathcal{Z}_{\theta}$ is finite,

$\epsilon:=\min_{z\in\mathcal{Z}_{\theta}}\epsilon(z)>0.$

Consider $\theta^{\prime}\in B(\theta,\epsilon)$, $z\in\mathcal{Z}_{\theta}$,
$x\in B(z,r(z))$. Since
$\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)=\bar{\boldsymbol{\alpha}}(\theta,z)$,
we have for each output neuron $\eta\in N_{L}$

$\displaystyle\begin{cases}[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)]^{\top}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})&=[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta^{\prime},z)]^{\top}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})\\\
\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)^{\top}\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})&=\bar{\boldsymbol{\alpha}}(\theta^{\prime},z)^{\top}\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})\end{cases}$

hence using (26) we get

(33)
$\displaystyle\boldsymbol{R}_{\theta^{\prime}}(x)_{\eta}-\boldsymbol{R}_{\theta}(x)_{\eta}=$
$\displaystyle[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,z)]^{\top}\left(\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)\right)x+\bar{\boldsymbol{\alpha}}^{\top}(\theta,z)\left(\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)\right).$

Considering $z\in\mathcal{Z}_{\theta}$, define
$F_{z}:=\\{x_{i}\\}_{i=0}^{N_{0}}\subset B(z,r(z))\subset\mathbb{R}^{N_{0}}$
where $x_{0}=z$ and for $1\leq i\leq N_{0}$,
$x_{i}=z+\tfrac{r(z)}{2}\delta_{i}$ with $\delta_{i}$ the $i$-th vector of the
canonical basis. Observe that if
$\boldsymbol{u}\in\mathbb{R}^{N_{0}},b\in\mathbb{R}$ are such that
$\boldsymbol{u}^{\top}x+b=0$ for every $x\in F_{z}$, then
$\boldsymbol{u}=\boldsymbol{0}$ (since
$r(z)\boldsymbol{u}^{\top}\delta_{i}=\boldsymbol{u}^{\top}(x_{i}-x_{0})=\boldsymbol{u}^{\top}x_{i}+b-(\boldsymbol{u}^{\top}x_{0}+b)=0$
for every $i$), and therefore $b=0$ too.

a) The finite set $F:=\cup_{z\in\mathcal{Z}_{\theta}}F_{z}$ satisfies
$F\subset\cup_{z\in\mathcal{Z}_{\theta}}B(z,r(z))\subset\mathcal{X}_{\theta}$.
Assume that $\boldsymbol{R}_{\theta^{\prime}}=\boldsymbol{R}_{\theta}$ on $F$
where $\theta^{\prime}\in B(\theta,\epsilon)$. By the preliminaries, this
implies that the right hand side in (33) is zero for each $\eta\in N_{L}$,
$z\in\mathcal{Z}_{\theta}$, $x\in F_{z}$, hence

$\displaystyle\begin{cases}[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,z)]^{\top}\left(\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)\right)=\boldsymbol{0}_{1\times
N_{0}}\\\
\bar{\boldsymbol{\alpha}}^{\top}(\theta,z)\left(\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)\right)=0.\end{cases}$

Since this holds for every $\eta\in N_{L}$, $z\in\mathcal{Z}_{\theta}$, in
light of (32) this establishes that

(34) $\displaystyle\forall\eta\in
N_{L},\begin{cases}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)&\in\underbrace{\mathtt{A}^{\perp}(\theta)\times\ldots\times\mathtt{A}^{\perp}(\theta)}_{N_{0}\
\text{times}}\\\
\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)&\in\mathtt{\bar{A}}^{\perp}(\theta)\end{cases}$

and we conclude using Lemma 8 and the fact that
$\mathtt{card}(F)\leq\mathtt{card}(\mathcal{Z}_{\theta})\times(N_{0}+1)$.

b) Since $K\subset\mathcal{X}_{\theta}$, for each $z\in K$ there are
$\epsilon(z),r(z)>0$ such that: for each $\theta^{\prime}\in
B(\theta,\epsilon(z))$, $x\in B(z,r(z))$,
$\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)=\bar{\boldsymbol{\alpha}}(\theta,z)$.
Since $K$ is compact and $K\subset\cup_{z\in K}B(z,r(z))$, there is a finite
set $\mathcal{Z}\subset K$ such that
$K\subset\cup_{z\in\mathcal{Z}}B(z,r(z))$. Denote
$\epsilon^{\prime}:=\min_{z\in\mathcal{Z}}\epsilon(z)>0$. Considering
$\theta^{\prime}\in B(\theta,\epsilon^{\prime})$ such that
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$,
we now show that
$\boldsymbol{R}_{\theta^{\prime}}(x)=\boldsymbol{R}_{\theta}(x)$ for each
$x\in K$. Given $x\in K$, since there is $z\in\mathcal{Z}_{\theta}$ such that
$x\in B(z,r(z))$, we have

(35) $\displaystyle\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)$
$\displaystyle=\bar{\boldsymbol{\alpha}}(\theta,z)=\bar{\boldsymbol{\alpha}}(\theta,x).$

For each $\eta\in N_{L}$, since by Lemma 8
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$
is equivalent to (34), we get

$\displaystyle[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta^{\prime},x)]^{\top}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:activequal}}}{{=}}[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x)]^{\top}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})\stackrel{{\scriptstyle\eqref{eq:orthoexplicit}}}{{=}}[\boldsymbol{Q}\bar{\boldsymbol{\alpha}}(\theta,x)]^{\top}\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)$
$\displaystyle\bar{\boldsymbol{\alpha}}^{\top}(\theta^{\prime},x)\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:activequal}}}{{=}}\bar{\boldsymbol{\alpha}}^{\top}(\theta,x)\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})\stackrel{{\scriptstyle\eqref{eq:orthoexplicit}}}{{=}}\bar{\boldsymbol{\alpha}}^{\top}(\theta,x)\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta).$

Using (26) we conclude that
$\boldsymbol{R}_{\theta^{\prime}}(x)_{\eta}=\boldsymbol{R}_{\theta}(x)_{\eta}$
for all $\eta\in N_{L}$, i.e.,
$\boldsymbol{R}_{\theta^{\prime}}(x)=\boldsymbol{R}_{\theta}(x)$. ∎

##  5\. Identifiability for shallow neural networks

In this section we focus on shallow networks, for which the set
$\mathcal{Q}=\mathcal{Q}_{1}$ of paths is in bijection with the set $H=N_{1}$
of hidden neurons. Identifying these sets the activation vectors also coincide
$\boldsymbol{\alpha}(\theta,x)=\boldsymbol{a}_{1}(\theta,x)\in\mathbb{R}^{\mathcal{Q}}=\mathbb{R}^{N_{1}}=\mathbb{R}^{H}$.
After giving a complete characterization of the activation space
$\mathtt{\bar{A}}(\theta)$ using the notion of twin neurons, we show that the
absence of twin neurons implies non-degeneracy (hence local
S-identifiability), and that its combination with irreducibility implies PS-
identifiability. Finally, we discuss what happens in the presence of twin
neurons.

###  5.1. Activation spaces and twin neurons

Whenever $\theta$ is admissible, each hidden neuron $\nu\in H$ is not dead,
i.e. $\boldsymbol{w}_{\bullet\to\nu}\neq 0$ and
$\boldsymbol{w}_{\nu\to\bullet}\neq 0$. According to Definition 8, neurons are
twins if their extended vectors $(\boldsymbol{w}_{\bullet\to\nu},b_{\nu})$ are
colinear. This defines an equivalence relation, and the hidden layer $H=N_{1}$
can be partitioned into _equivalence classes of twin neurons_ , denoted

$T_{c}\subset H,1\leq c\leq C.$

Each equivalence class $T_{c}$ is partitioned into $I_{c},J_{c}$, where all
neurons in $I_{c}$ are positive twins, all neurons in $J_{c}$ are positive
twins, and $\nu\in I_{c},\nu^{\prime}\in J_{c}$ are negative twins. By
convention $I_{c}$ is always non-empty, while $J_{c}$ may be empty if there
are no negative twins in $T_{c}$. For each class, we can define a class
signature vector

$\mathtt{s}_{c}=\mathtt{1}_{I_{c}}-\mathtt{1}_{J_{c}}\in\mathbb{R}^{H},$

which is zero out of $T_{c}$, with $\pm 1$ entries on $T_{c}$, and has at
least one $+1$ entry. When $T_{c}$ contains both positive and negative twins,
$\mathtt{s}_{c}$ is only defined up to a global sign. An equivalence class is
said to be nontrivial if its cardinal is at least two. Equipped with these
notions, we prove in Appendix G the following characterization of activation
spaces.

######  Lemma 13.

Consider an admissible parameter $\theta$ on a shallow network architecture.
Using the notations introduced above, its activation spaces are

(36)
$\displaystyle\mathtt{A}(\theta)=\mathtt{span}\left\\{\mathtt{1}_{H},\mathtt{s}_{c},1\leq
c\leq C\right\\}$ $\displaystyle\subseteq\mathbb{R}^{H}$ (37)
$\displaystyle\mathtt{\bar{A}}(\theta)=\mathtt{span}\left\\{(\mathtt{1}_{H},2),(\mathtt{s}_{c},0),1\leq
c\leq C\right\\}$ $\displaystyle\subseteq\mathbb{R}^{H+1}.$

###  5.2. Proof of Lemma 5: no twins implies non-degeneracy

Lemma 5 is a direct consequence of the combination of Theorem 5 with the
following two results.

######  Lemma 14.

On any network architecture, if $\theta\in\mathbb{R}^{E\cup\bar{H}}$ is
admissible and $\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$
then888The converse does not hold: there are non-degenerate parameters with
$\mathtt{\bar{A}}(\theta)\neq\mathbb{R}^{\mathcal{Q}+1}$, see Lemma 16.
$\theta$ is non-degenerate with respect to any
$\Theta\subset\mathbb{R}^{E\cup\bar{H}}$ that contains it.

###### Proof.

Since $\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$, by Corollary 2
$\mathtt{V}(\theta)=\\{0\\}$, hence
$\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$
is equivalent to
$\boldsymbol{\Phi}(\theta^{\prime})=\boldsymbol{\Phi}(\theta)$. Since $\theta$
is admissible, this shows that $\theta$ is non-degenerate. ∎

######  Lemma 15.

Consider a shallow architecture and $\theta\in\mathbb{R}^{E\cup\bar{H}}$. The
equality $\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$ holds if, and
only if, there is no twin. When this holds,
$\mathtt{actdim}(\theta)=|H|+1=|N_{1}|+1$.

###### Proof.

Equivalence classes of twin neurons form a partition of $H$, hence
$|C|\leq|H|=|\mathcal{Q}|$. By Lemma 13, $\mathtt{\bar{A}}(\theta)$ is the
span of $|C|+1$ vectors, hence its dimension is at most $|C|+1$. In the
presence of twins we get $|C|<|H|$ hence
$\mathtt{\bar{A}}(\theta)\neq\mathbb{R}^{\mathcal{Q}+1}$. In the absence of
twins, each equivalence class $T_{c}$ is trivial, i.e. $|T_{c}|=1$. We obtain
that $|C|=|H|$, that each signature vector $\mathtt{s}_{c}$ is a distinct
canonical vector $\delta_{c}$, and obtain
$\mathtt{\bar{A}}(\theta)=\mathbb{R}^{\mathcal{Q}+1}$ by Lemma 13. ∎

###  5.3. Proof of Theorem 3: irreducibility and no twins implies PS-
identifiability

By Lemma 3, PS-identifiability from a bounded set with respect to
$\Theta=\mathbb{R}^{E\cup\bar{H}}$ implies that $\theta$ has no twins, hence
by Lemma 4), it is irreducible (hence admissible), and local S-identifiable,
by Theorem 2. For shallow networks, we show that conversely, irreducibility
and the absence of twins imply PS-identifiability from a bounded set.

######  Theorem 6.

Consider $N_{1}$, $N^{\prime}_{1}$ two finite sets of indices, empty or
not999We use the convention: $\sum_{\emptyset}=0$., and integers $d,k\geq 1$.
Consider $\boldsymbol{c}\in\mathbb{R}^{k}$ and for each $\nu\in N_{1}$, let
$\boldsymbol{v}_{\nu}\in\mathbb{R}^{k}$,
$\boldsymbol{w}_{\nu}\in\mathbb{R}^{d}$ and $b_{\nu}\in\mathbb{R}$. Define

$\boldsymbol{\varphi}(x)=\sum_{\nu\in{N_{1}}}\boldsymbol{v}_{\nu}\mathtt{ReLU}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})+\boldsymbol{c},\qquad
x\in\mathbb{R}^{d}.$

Similarly define $\boldsymbol{\psi}(x)$ with
$\boldsymbol{v}^{\prime}_{\nu}\in\mathbb{R}^{k}$,
$\boldsymbol{w}^{\prime}_{\nu}\in\mathbb{R}^{d}$,
$b^{\prime}_{\nu}\in\mathbb{R}$ for $\nu\in N^{\prime}_{1}$, and
$\boldsymbol{c}^{\prime}\in\mathbb{R}^{k}$.

  1. a)

Assume that

     * •

$\\{(\boldsymbol{w}_{\nu},b_{\nu})\\}_{\nu\in N_{1}}$ are pairwise not
collinear, and $\boldsymbol{v}_{\nu},\boldsymbol{w}_{\nu}\neq 0$;

     * •

$\\{(\boldsymbol{w}^{\prime}_{\nu},b^{\prime}_{\nu})\\}_{\nu\in
N^{\prime}_{1}}$ are pairwise not collinear, and
$\boldsymbol{v}^{\prime}_{\nu},\boldsymbol{w}^{\prime}_{\nu}\neq 0$.

If $\boldsymbol{\varphi}(x)=\boldsymbol{\psi}(x)$ for every
$x\in\mathbb{R}^{d}$ then
$\mathtt{card}(N_{1})=\mathtt{card}(N^{\prime}_{1})$.

  2. b)

Assume that $\\{(\boldsymbol{w}_{\nu},b_{\nu})\\}_{i\in N_{1}}$ are pairwise
not collinear, and

(38) $\sum_{\nu\in{T}}\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}\neq
0,\quad\text{for all non-empty}\ {T}\subset N_{1}.$

There exists a bounded set $\mathcal{X}\subseteq\mathbb{R}^{N_{0}}$ (which
depends on $\theta$) such that: if $N^{\prime}_{1}=N_{1}$ and
$\boldsymbol{\varphi}(x)=\boldsymbol{\psi}(x)$ for every $x\in\mathcal{X}$,
then101010Let us emphasize that here no further assumption is made on
$\boldsymbol{w}^{\prime}_{\nu},b^{\prime}_{\nu},\boldsymbol{v}^{\prime}_{\nu}$,
$\nu\in N_{1}$. $\boldsymbol{c}=\boldsymbol{c}^{\prime}$ and there exists a
permutation $\pi$ of $N_{1}$ and $\lambda_{\nu}>0$, $\nu\in N_{1}$ such that

(39) $\displaystyle\forall\nu\in
N_{1}:\boldsymbol{v}^{\prime}_{\pi(\nu)}=\lambda_{\nu}^{-1}\boldsymbol{v}_{\nu};\
\boldsymbol{w}^{\prime}_{\pi(\nu)}=\lambda_{\nu}\boldsymbol{w}_{\nu}\
\text{and}\ b^{\prime}_{\pi(\nu)}=\lambda_{\nu}b_{\nu}.$

###### Proof.

As a preliminary, consider $\nu\in N_{1}$ and denote
$\mathcal{V}_{\nu}:=\\{x\in\mathbb{R}^{N_{0}}:\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu}=0\\}$.
Since $\boldsymbol{w}_{\nu}\neq 0$, the set $\mathcal{V}_{\nu}$ is a
hyperplane which matches the set $\Gamma_{\nu}(\theta)$ from Definition 10
when considering $\theta$ such that
$\boldsymbol{\varphi}=\boldsymbol{R}_{\theta}$. As none of the
$(\boldsymbol{w}_{\nu},b_{\nu})$ is collinear to another, the hyperplanes
associated to $\nu\neq\nu^{\prime}\in N_{1}$ are distinct. As
$\boldsymbol{v}_{\nu}\neq 0$ for every $\nu\in N_{1}$ and
$\boldsymbol{\varphi}$ is continuous and piecewise affine, this function is
differentiable exactly on the complement of
$\mathcal{T}:=\cup_{\nu\in{N_{1}}}\mathcal{V}_{\nu}$, which is a union of
$\mathtt{card}(N_{1})$ distinct hyperplanes.

a) Similarly, since none of the
$(\boldsymbol{w}^{\prime}_{\nu},b^{\prime}_{\nu})$ is collinear to another and
$\boldsymbol{v}^{\prime}_{\nu}\neq 0,\boldsymbol{w}^{\prime}_{\nu}\neq 0$ for
each $\nu\in N^{\prime}_{1}$, the function $\boldsymbol{\psi}$ is
differentiable exactly on the complement of a union of
$\mathtt{card}(N^{\prime}_{1})$ distinct hyperplanes,
$\mathcal{T}^{\prime}=\cup_{\nu\in{N}^{\prime}}\mathcal{V}^{\prime}_{\nu}$,
where
$\mathcal{V}^{\prime}_{\nu}:=\\{x\in\mathbb{R}^{N_{0}}:\langle\boldsymbol{w}^{\prime}_{\nu},x\rangle+b^{\prime}_{\nu}=0\\}$.
Note that $\mathcal{T}$ may be empty since $N_{1}$ may be empty, and similarly
for $\mathcal{T}^{\prime}$. Since $\boldsymbol{\varphi}=\boldsymbol{\psi}$, we
have $\mathcal{T}=\mathcal{T}^{\prime}$ hence $\mathtt{card}(N_{1})$ =
$\mathtt{card}(N^{\prime}_{1})$, otherwise there would exist one point
$x\in\mathbb{R}^{d}$ where one function would be differentiable and the other
not.

b) We now assume $N^{\prime}_{1}$ = $N_{1}$, but make no specific assumption
on $\boldsymbol{v}^{\prime}_{\nu}\in\mathbb{R}^{k}$,
$\boldsymbol{w}^{\prime}_{\nu}\in\mathbb{R}^{d}$,
$b^{\prime}_{\nu}\in\mathbb{R}$ for $\nu\in N_{1}$ or on
$\boldsymbol{c}^{\prime}\in\mathbb{R}^{k}$. By (38) with $T=\\{\nu\\}$ we have
$\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}\neq 0$ hence, as in the
preliminary, $\mathcal{V}_{\nu}$, $\nu\in N_{1}$ are pairwise distinct
hyperplanes. Consider an arbitrary hidden neuron $\nu\in N_{1}$. As the
hyperplanes $\\{\mathcal{V}_{\mu}\\}_{\mu\in N_{1}}$ are pairwise distinct,
there exist $x_{\nu}\in\mathcal{V}_{\nu}$ and $\epsilon_{\nu}>0$ such that
$\Omega_{\nu}:=B(x_{\nu},\epsilon_{\nu})$ satisfies
$\Omega_{\nu}\cap\mathcal{T}=\Omega_{\nu}\cap\mathcal{V}_{\nu}$. We will show
that the result holds with $\mathcal{X}:=\cup_{\nu\in N_{1}}\Omega_{\nu}$,
which is easily seen to be bounded.

From now, assume that $\boldsymbol{\psi}(x)=\boldsymbol{\varphi}(x)$ for every
$x\in\mathcal{X}$.

For each $\nu\in\widehat{N}_{1}:=\\{\nu\in
N_{1}:\boldsymbol{v}^{\prime}_{\nu}\neq 0,\boldsymbol{w}^{\prime}_{\nu}\neq
0\\}$, since $\boldsymbol{w}^{\prime}_{\nu}\neq 0$, the set
$\mathcal{V}^{\prime}_{\nu}$ is a hyperplane. Consider the equivalence
relation on $\widehat{N}_{1}$ defined by:
$\nu\sim\mu\Leftrightarrow\mathcal{V}^{\prime}_{\nu}=\mathcal{V}^{\prime}_{\mu}$,
and the resulting quotient set $\bar{N_{1}}=\widehat{N}_{1}/\\!\\!\\!\sim$.
For each equivalence class $\bar{\nu}\in\bar{N_{1}}$, denote
$\mathcal{V}^{\prime}_{\bar{\nu}}$ the common hyperplane associated to every
$\nu\in\bar{\nu}$, and set
$\bar{\mathcal{T}}=\cup_{\bar{\nu}\in\bar{N}_{1}}\mathcal{V}^{\prime}_{\bar{\nu}}$.
We will prove below that there exists an injective map
$\pi:N_{1}\to\bar{N}_{1}$ such that
$\mathcal{V}_{\nu}=\mathcal{V}^{\prime}_{\pi(\nu)}$ for every $\nu\in N_{1}$.
This will imply that $\mathtt{card}(\bar{N}_{1})\geq\mathtt{card}(N_{1})$, and
since
$\mathtt{card}(\bar{N}_{1})\leq\mathtt{card}(\widehat{N}_{1})\leq\mathtt{card}(N_{1})$,
it will follow that $\widehat{N}_{1}=N_{1}$ (hence
$\boldsymbol{v}^{\prime}_{\nu}\neq 0$, $\boldsymbol{w}^{\prime}_{\nu}\neq 0$
for every $\nu\in N_{1}$) and that each equivalence class $\bar{\nu}$ is a
singleton. In other words, $\pi$ is indeed a permutation of $N_{1}$, and the
hyperplanes $\mathcal{V}^{\prime}_{\\{\nu\\}}$, $\nu\in N_{1}$ are pairwise
distinct.

To build $\pi$, consider a hidden neuron $\nu\in N_{1}$. For the sake of
contradiction, assume that
$\mathcal{V}^{\prime}_{\bar{\mu}}\neq\mathcal{V}_{\nu}$ for every
$\bar{\mu}\in\bar{N}_{1}$. This implies the existence of
$x^{\prime}_{\nu}\in\Omega_{\nu}\cap\mathcal{V}_{\nu}$ and of
$\epsilon^{\prime}_{\nu}>0$ such that
$\Omega^{\prime}_{\nu}:=B(x^{\prime}_{\nu},\epsilon^{\prime}_{\nu})\subseteq\Omega_{\nu}$
and $\Omega^{\prime}_{\nu}\cap\bar{\mathcal{T}^{\prime}}=\emptyset$ and
$\Omega^{\prime}_{\nu}\cap\mathcal{V}_{\nu}=\mathcal{V}_{\nu}$. Since
$\Omega^{\prime}_{\nu}\cap\bar{\mathcal{T}}=\emptyset$, the function
$\boldsymbol{\psi}$ is affine linear on $\Omega^{\prime}_{\nu}$, hence it has
constant Jacobian on $\Omega^{\prime}_{\nu}$. Denote
$\Omega_{\nu}^{+}:=\\{x\in\Omega^{\prime}_{\nu}:\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu}>0\\}$,
$\Omega_{\nu}^{-}:=\\{x\in\Omega^{\prime}_{\nu}:\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu}<0\\}$,
and observe that both sets are non-empty. For any
$x\in\Omega^{\prime}_{\nu}\backslash\mathcal{V}_{\nu}=\Omega_{\nu}^{+}\cup\Omega_{\nu}^{-}$,
the function $\boldsymbol{\varphi}$ is differentiable and its Jacobian is
$\boldsymbol{\varphi}^{\prime}(x)=\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}H(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})+\boldsymbol{d}$
where $\boldsymbol{d}\in\mathbb{R}^{k}$ and

$\displaystyle H(t):=\begin{cases}1,&\text{if}\ t>0\\\
0,&\text{otherwise}.\end{cases}$

For each $x_{\nu}^{+}\in\Omega_{\nu}^{+},x_{\nu}^{-}\in\Omega_{\nu}^{-}$ we
have
$H(\langle\boldsymbol{w}_{\nu},x_{\nu}^{+}\rangle+b_{\nu})-H(\langle\boldsymbol{w}_{\nu},x_{\nu}^{-}\rangle+b_{\nu})=1$,
hence
$\boldsymbol{\varphi}^{\prime}(x_{\nu}^{+})-\boldsymbol{\varphi}^{\prime}(x_{\nu}^{-})=\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}$.
As $\boldsymbol{\psi}=\boldsymbol{\varphi}$ on
$\mathcal{X}\supseteq\Omega_{\nu}\supseteq\Omega^{\prime}_{\nu}$ and
$\boldsymbol{\psi}$ has constant Jacobian on $\Omega^{\prime}_{\nu}$, it
follows that $\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}=0$, which contradicts
our assumptions. Hence, there is $\bar{\mu}\in\bar{N}_{1}$ such that
$\mathcal{V}^{\prime}_{\bar{\mu}}=\mathcal{V}_{\nu}$. Since the hyperplanes
$\\{\mathcal{V}^{\prime}_{\bar{\nu}}\\}_{\bar{\nu}\in\bar{N}_{1}}$ are
pairwise disjoint by construction, such a $\bar{\mu}$ is unique and we define
$\pi(\nu):=\bar{\mu}$. Since this holds for every $\nu\in N_{1}$, we can
define the map $\pi:N_{1}\to\bar{N}_{1}$ with $\pi(\nu):=\bar{\mu}$. For
$\nu\neq\nu^{\prime}$ we have
$\mathcal{V}^{\prime}_{\pi(\nu^{\prime})}=\mathcal{V}_{\nu^{\prime}}\neq\mathcal{V}_{\nu}=\mathcal{V}^{\prime}_{\pi(\nu)}$
since the hyperplanes $\\{\mathcal{V}_{\nu}\\}_{\nu\in N_{1}}$ are pairwise
distinct. This proves the injectivity of $\pi$. As we have seen, this means
that indeed $\pi$ is a permutation of $N_{1}$. Without loss of generality, to
simplify notations, we assume from now on that $\pi$ is the identity.

For each $\nu\in N_{1}$, since
$\mathcal{V}^{\prime}_{\nu}=\mathcal{V}^{\prime}_{\pi(\nu)}=\mathcal{V}_{\nu}$
there is a nonzero $\lambda_{\nu}\in\mathbb{R}$ such that

$(\boldsymbol{w}^{\prime}_{\nu},b^{\prime}_{\nu})=\lambda_{\nu}(\boldsymbol{w}_{\nu},b_{\nu}).$

Reasoning as above, with $\Omega_{\nu}^{\pm}$ defined using
$\Omega^{\prime}_{\nu}:=\Omega_{\nu}$, we obtain that

$\boldsymbol{\varphi}^{\prime}(x_{\nu}^{+})-\boldsymbol{\varphi}^{\prime}(x_{\nu}^{-})=\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}.$

for each $x_{\nu}^{+}\in\Omega_{\nu}^{+},x_{\nu}^{-}\in\Omega_{\nu}^{-}$, and
that for each $x\in\Omega_{\nu}\backslash\mathcal{V}_{\nu}$, the Jacobian of
$\psi$ satisfies
$\boldsymbol{\psi}^{\prime}(x)=\boldsymbol{v}^{\prime}_{\nu}(\boldsymbol{w}^{\prime}_{\nu})^{\top}H(\langle\boldsymbol{w}^{\prime}_{\nu},x\rangle+b^{\prime}_{\nu})+\boldsymbol{d}^{\prime}$
with some $\boldsymbol{d}^{\prime}\in\mathbb{R}^{k}$, hence for each
$x_{\nu}^{+}\in\Omega_{\nu}^{+},x_{\nu}^{-}\in\Omega_{\nu}^{-}$

$\boldsymbol{\psi}^{\prime}(x_{\nu}^{+})-\boldsymbol{\psi}^{\prime}(x_{\nu}^{-})=\boldsymbol{v}^{\prime}_{\nu}(\boldsymbol{w}^{\prime}_{\nu})^{\top}\left(H(\langle\boldsymbol{w}^{\prime}_{\nu},x_{\nu}^{+}\rangle+b^{\prime}_{\nu})-H(\langle\boldsymbol{w}^{\prime}_{\nu},x_{\nu}^{-}\rangle+b^{\prime}_{\nu})\right).$

Since
$(\boldsymbol{w}^{\prime}_{\nu},b^{\prime}_{\nu})=\lambda_{\nu}(\boldsymbol{w}_{\nu},b_{\nu})$
and
$\mathtt{sign}(\langle\boldsymbol{w}_{\nu},x_{\nu}^{\pm}\rangle+b_{\nu})=\pm
1$, we have

$\displaystyle
H(\langle\boldsymbol{w}^{\prime}_{\nu},x_{\nu}^{+}\rangle+b^{\prime}_{\nu})-H(\langle\boldsymbol{w}^{\prime}_{\nu},x_{\nu}^{-}\rangle+b^{\prime}_{\nu})$
$\displaystyle=\mathtt{sign}(\lambda_{\nu}).$

Moreover, as $\boldsymbol{\psi}=\boldsymbol{\varphi}$ on $\mathcal{X}$, we
have
$\boldsymbol{\varphi}^{\prime}(x_{\nu}^{+})-\boldsymbol{\varphi}^{\prime}(x_{\nu}^{-})=\boldsymbol{\psi}^{\prime}(x_{\nu}^{+})-\boldsymbol{\psi}^{\prime}(x_{\nu}^{-})$,
hence

$\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}=\boldsymbol{v}^{\prime}_{\nu}(\boldsymbol{w}^{\prime}_{\nu})^{\top}\mathtt{sign}(\lambda_{\nu}).$

Since $\boldsymbol{w}^{\prime}_{\nu}=\lambda_{\nu}\boldsymbol{w}_{\nu}$, this
simplifies to

(40)
$\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}=\boldsymbol{v}^{\prime}_{\nu}(\boldsymbol{w}^{\prime}_{\nu})^{\top}\mathtt{sign}(\lambda_{\nu})=\boldsymbol{v}^{\prime}_{\nu}\boldsymbol{w}_{\nu}^{\top}\lambda_{\nu}\mathtt{sign}(\lambda_{\nu})=|\lambda_{\nu}|\boldsymbol{v}^{\prime}_{\nu}\boldsymbol{w}_{\nu}^{\top}$

Hence, $\boldsymbol{v}^{\prime}_{\nu}=\boldsymbol{v}_{\nu}/|\lambda_{\nu}|$
for each $\nu\in N_{1}$.

To conclude, it is enough to prove that $\lambda_{\nu}>0$ for every $\nu\in
N_{\nu}$. Using (40), we can re-write the equality
$\boldsymbol{\varphi}(x)=\boldsymbol{\psi}(x)$ for every $x$ as follows:

(41)
$\sum_{\nu\in{N_{1}}}\boldsymbol{v}_{\nu}\Big{[}\mathtt{ReLU}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})-|\lambda_{\nu}|^{-1}\mathtt{ReLU}(\underbrace{\langle\boldsymbol{w}^{\prime}_{\nu},x\rangle+b^{\prime}_{\nu}}_{\lambda_{\nu}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})})\Big{]}+\boldsymbol{c}-\boldsymbol{c}^{\prime}=0.$

Now, we observe that

(42)
$\mathtt{ReLU}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})-|\lambda_{\nu}|^{-1}\mathtt{ReLU}(\lambda_{\nu}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu}))=\begin{cases}0&\text{if
}\mathtt{sign}(\lambda_{\nu})=1\\\
\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu}&\text{if
}\mathtt{sign}(\lambda_{\nu})=-1\end{cases}$

We now show that
${T}:=\\{\nu\in{N_{1}}\mid\mathtt{sign}(\lambda_{\nu})=-1\\}=\emptyset$. Using
(42), we re-write (41) as:

(43)
$\sum_{\nu\in{T}}\boldsymbol{v}_{\nu}(\langle\boldsymbol{w}_{\nu},x\rangle+b_{\nu})+\boldsymbol{c}-\boldsymbol{c}^{\prime}=0.$

Since this is valid for all $x\in\mathbb{R}^{N_{0}}$ we get
$\boldsymbol{c}=\boldsymbol{c}^{\prime}$ and
$\sum_{\nu\in{T}}\boldsymbol{v}_{\nu}\boldsymbol{w}_{\nu}^{\top}=0$. In light
of (38) the latter implies ${T}=\emptyset$, hence
$\mathtt{sign}(\lambda_{\nu})=1$ for all $\nu\in{N_{1}}$. ∎

###  5.4. Local S-identifiability despite the presence of twins

It is natural to wonder if there exists shallow networks with twins that are
nevertheless either non-degenerate, or locally S-identifiable, or PS-
identifiable. Positive twins are excluded (for any network depth) by Lemma 3,
hence we can focus on the case where there are $K\geq 1$ nontrivial classes of
twins, each made of a single pair of (distinct) negative twins (as any
equivalence class with at least three twins necessarily contains two positive
ones). We detail here the case $K=1$ and leave to future work a more detailed
analysis of what happens for $K\geq 2$.

######  Lemma 16 (Single pair of negative twins).

Consider a shallow network architecture. If
$\theta\in\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ is admissible with a
single pair of negative twins, $\\{\nu_{1},\nu_{2}\\}\subseteq H$, then

(44) $\mathtt{A}^{\perp}(\theta)=\\{0\\}\ \text{and}\
\mathtt{\bar{A}}^{\perp}(\theta)=\mathtt{span}\left\\{\delta_{\nu_{1}}+\delta_{\nu_{2}}-\delta_{\star}\right\\}\neq\\{0\\}$

where $\delta_{\nu}\in\mathbb{R}^{H+1},\nu\in H$ is the $\nu$-th canonical
eigenvector, and $\delta_{\star}=(\boldsymbol{0}_{H},1)$.

Moreover, if at least one of the following conditions holds:

  1. i)

$\boldsymbol{w}_{\nu_{1}\to\bullet}$, $\boldsymbol{w}_{\nu_{2}\to\bullet}$ are
linearly independent (which is only possible if $|N_{2}|\geq 2$); or

  2. ii)

$\Theta$ is contained in the set of parameters with zero output bias;

then $\theta$ is non-degenerate with respect to $\Theta$. Conversely, if

  1. iii)

$\boldsymbol{w}_{\nu_{1}\to\bullet}$, $\boldsymbol{w}_{\nu_{2}\to\bullet}$ are
linearly dependent and $\theta$ belongs to the interior of $\Theta$,

then $\theta$ is degenerate with respect to $\Theta$.

######  Remark 7.

Inspecting the proof shows that the assumption in iii) that $\theta$ is in the
interior of $\Theta$ can be relaxed to: for small enough $\epsilon$, each
parameter $\theta^{\prime}\in B(\theta,\epsilon)$ differing from $\theta$ only
in terms of biases belongs to $\Theta\cap B(\theta,\epsilon)$.

The proof is in Appendix H. We are now equipped to show with an example that
non-degeneracy and local-identifiability are distinct concepts.

######  Example 4 (Absolute value).

Consider a shallow architecture with scalar input and output and two hidden
neurons. The absolute value can be written as
$|x|=\mathtt{ReLU}(x)+\mathtt{ReLU}(-x)=\boldsymbol{R}_{\theta}$ where
$\theta=(w_{\mu\to\nu_{1}}=1,w_{\mu\to\nu_{2}}=-1,b_{\nu_{1}}=b_{\nu_{2}}=0,w_{\nu_{1}\to\eta}=w_{\nu_{2}\to\eta}=1,b_{\eta}=0)$
has a single pair of negative twins. This parameter $\theta$ satisfies the
following properties

  1. i)

it is not PS-identifiable from any bounded set $\mathcal{X}\subset\mathbb{R}$
(by Lemma 3);

  2. ii)

it is not locally S-identifiable from any finite
$F\subset\mathcal{X}_{\theta}$ (i.e., it is degenerate, see below);

  3. iii)

it is PS-identifiable (hence locally S-identifiable) _from
$\mathcal{X}=\mathbb{R}$_;

  4. iv)

it is locally S-identifiable from $F\cup\\{0\\}$ for some finite set
$F\subset\mathcal{X}_{\theta}$;

The last two points are detailed in Appendix I. Let us detail ii) here. Since
$|N_{2}|=1$, by Lemma 16-iii) we get that $\theta$ is degenerate with respect
to $\Theta=\mathbb{R}^{E\cup\bar{H}}$, i.e. not locally S-identifiable from
any finite $F\subseteq\mathcal{X}_{\theta}$. Indeed, if
$F\subseteq\mathcal{X}_{\theta}=\mathbb{R}\backslash\\{0\\}$ is finite then
$F\subset(-\infty,-t]\cup[t,+\infty)$ for some $t>0$, and $\mathtt{abs}$
coincides on $F$ with (see Figure 2-(c))

$\mathtt{ReLU}(x-t)+\mathtt{ReLU}(-(x+t))+t=\begin{cases}-x,&x\leq-t\\\
t,&|x|\leq t\\\ x,&x\geq t.\end{cases}=\boldsymbol{R}_{\theta^{\prime}}(x)$

where $\theta^{\prime}$ has nonzero biases, so that
$\theta^{\prime}\not\sim_{PS}\theta$.

######  Example 5 (Revisiting the identity function from Example 1).

The identity function from Example 1 is another example with a single pair of
twin neurons. With $\Theta=\mathbb{R}^{E\cup\bar{H}}$ the parameter
$\theta_{0}$ is not locally S-identifiable (from $\mathcal{X}=\mathbb{R}$) as
already explained in Example 1. With
$\Theta=\Theta_{0}\subsetneq\mathbb{R}^{E\cup\bar{H}}$ the set of parameters
with zero output bias, $\theta_{0}$ is on the contrary PS-identifiable from
$\mathbb{R}$ (see details in Appendix J). It can also be shown that
$\theta_{0}$ is non-degenerate with respect to $\Theta_{0}$, using arguments
similar to those used in Appendix I to prove item iv) of Example 4. This
illustrates the fact that, in the presence of a pair of negative twins, many
things can happen: the parameter can be PS-identifiable and non- degenerate,
or not even locally S-identifiable.

###  5.5. Discussion of the role of activation spaces

For shallow irreducible networks, PS-identifiability from a bounded set is
equivalent (Theorem 3) to the absence of twin neurons, which corresponds
(Lemma 15) to a completeness property of the activation space that reads
$\mathtt{\bar{A}}^{\perp}(\theta)=\\{0\\}$. The property
$\mathtt{\bar{A}}^{\perp}(\theta)=\\{0\\}$ also implies non-degeneracy (Lemma
14), yet a consequence of Lemma 16 is that the converse does not generally
hold (and that the weaker assumption $\mathtt{A}^{\perp}(\theta)=\\{0\\}$ is
no longer sufficient to imply non-degeneracy). An exception occurs for scalar-
valued shallow networks.

######  Lemma 17.

Consider a _scalar-valued_ shallow architecture ($|N_{2}|=1$). If $\theta$
belongs to the interior of $\Theta\subseteq\mathbb{R}^{E\cup\bar{H}}$ and is
non-degenerate with respect to $\Theta$ then
$\mathtt{\bar{A}}^{\perp}(\theta)=\\{0\\}$.

This exception is a consequence of the following result.

######  Lemma 18.

Consider a scalar-valued shallow network architecture. If $\theta$ is
admissible then there is $0<C<\infty$ such that: for each
$\boldsymbol{z}\in\mathbb{R}^{\mathcal{Q}+1}$, there exists
$\theta^{\prime}\in B(\theta,C\|\boldsymbol{z}\|_{\infty})$

(45)
$\displaystyle\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)$
$\displaystyle=\boldsymbol{0}_{\mathcal{Q}_{1}\times N_{0}},$ (46)
$\displaystyle\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta^{\prime})-\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)$
$\displaystyle=\boldsymbol{z}$

where $\eta$ is the single output neuron constituting the output layer
$N_{L}$. The parameters $\theta$ and $\theta^{\prime}$ differ only in terms of
biases.

###### Proof.

Write $\boldsymbol{z}=(\boldsymbol{y},\gamma)$ with
$\boldsymbol{y}\in\mathbb{R}^{\mathcal{Q}}=\mathbb{R}^{H}$ and
$\gamma\in\mathbb{R}$. For each hidden neuron $\nu\in H=N_{1}$, denote
$v_{\nu}=v_{\nu\to\eta}$ the unique weight from neuron $\nu$ to the single
output neuron. For each input neuron $\mu\in N_{0}$, the $\mu$-th column of
$\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)$ is
$\boldsymbol{\Phi}^{\mathtt{i}}_{\mu\to\eta}(\theta):=(w_{\mu\to\nu}v_{\nu})_{\nu\in
H}$, and
$\boldsymbol{\Phi}^{\mathtt{h}}_{\eta}(\theta)=\left((b_{\nu}v_{\nu})_{\nu\in
H},b_{\eta}\right)^{\top}$. To prove the result we define $\theta^{\prime}$
with identical weights as $\theta$, $v^{\prime}_{\nu}:=v_{\nu}$,
$w^{\prime}_{\mu\to\nu}:=w_{\mu\to\nu}$, and set the output bias to
$b^{\prime}_{\eta}:=b_{\eta}+\gamma$. This implies
$w^{\prime}_{\mu\to\nu}v^{\prime}_{\nu}=w_{\mu\to\nu}v_{\nu}$ for every
$\nu\in H,\mu\in N_{0}$, hence
$\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta^{\prime})=\boldsymbol{\Phi}^{\mathtt{i}}_{\eta}(\theta)$.
We now seek $b^{\prime}_{\nu}$ such that
$b^{\prime}_{\nu}v^{\prime}_{\nu}=b_{\nu}v_{\nu}+y_{\nu}$, for each $\nu\in
H$. Since $\theta$ is admissible, $v_{\nu}\neq 0$ for all $\nu\in H$, hence we
can choose $b^{\prime}_{\nu}:=b_{\nu}+y_{\nu}/v_{\nu}$. We conclude with
$C_{\theta}$ driven by $\min_{\nu}1/|v_{\nu}|$. ∎

###### Proof of Lemma 17.

We prove the contraposition. Assume that $\theta$ is admissible, that it
belongs to the interior of $\Theta\subset\mathbb{R}^{E\cup\bar{H}}$, and that
$\mathtt{\bar{A}}^{\perp}(\theta)\neq\\{0\\}$. Since $\theta$ is in the
interior of $\Theta$, there is $\eta>0$ such that
$B(\theta,\eta)\subseteq\Theta$. For each $0<\epsilon<\eta$ there exists
$\boldsymbol{z}\in\mathtt{\bar{A}}^{\perp}(\theta)$ with norm
$\|\boldsymbol{z}\|_{\infty}=\epsilon/C$ where $C$ is the constant from Lemma
18. Since $\theta$ is admissible, by Lemma 18 and the characterization of
$\mathtt{V}(\theta)$ (Lemma 8) there exists $\theta^{\prime}\in
B(\theta,C\|\boldsymbol{z}\|_{\infty})=B(\theta,\epsilon)=\Theta\cap
B(\theta,\epsilon)$ such that
$\boldsymbol{0}\neq\boldsymbol{\Phi}(\theta^{\prime})-\boldsymbol{\Phi}(\theta)\in\mathtt{V}(\theta)$.
This shows that $\theta$ is degenerate with respect to $\Theta$. ∎

######  Remark 8.

The assumption that $\theta$ is in the interior of $\Theta$ can be relaxed to:
each parameter $\theta^{\prime}\in B(\theta,\epsilon)$ differing from $\theta$
only in terms of biases belongs to $\Theta\cap B(\theta,\epsilon)$.

## Acknowledgements

The authors are thankful to François Malgouyres for the interesting
discussions on invariant embeddings of linear and ReLU networks we had at
different stages of advancement of this work and Joachim Bona-Pellissier for
his technical comments on early versions of this article. The authors thank
Elisa Riccietti for her feedback that helped a lot improve the readability of
this paper. The authors are thankful to Hervé Jégou and Benjamin Graham for
their continuous support since the genesis of this project a few years ago.
This project was supported in part by the AllegroAssai ANR project
ANR-19-CHIA-0009.

## References

  * [1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in Neural Information Processing Systems, 2012.
  * [2] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova.  Nonlinear approximation and (deep) relu networks, 2019.
  * [3] Ronald DeVore, Boris Hanin, and Guergana Petrova.  Neural network approximation, 2020.
  * [4] Héctor J. Sussmann.  Uniqueness of the weights for minimal feedforward nets with a given input-output map.  Neural Networks, 1992.
  * [5] Paul Kainen, Vera Kurková, Vladik Kreinovich, and Ongard Sirisengtaksin.  Uniqueness of network parameterizations and faster learning.  Preprint, 1994.
  * [6] Věra Kůrková and Paul C. Kainen.  Functionally equivalent feedforward neural networks.  Neural Comput., 1993.
  * [7] Francesca Albertini, Eduardo D. Sontag, and Vincent Maillot.  Uniqueness of weights for neural networks.  In Artificial Neural Networks with Applications in Speech and Vision, 1993.
  * [8] Charles Fefferman.  Reconstructing a neural net from its output.  Revista Matemática Iberoamericana, 1994.
  * [9] David Rolnick and Konrad P. Kording.  Reverse-engineering deep relu networks, 2019.
  * [10] Massimo Fornasier, Timo Klock, and Michael Rauchensteiner.  Robust and resource efficient identification of two hidden layer neural networks, 2019.
  * [11] Mary Phuong and Christoph H Lampert.  Functional vs. parametric equivalence of ReLU networks.  ICLR, 2020.
  * [12] Francois Malgouyres and Joseph Landsberg.  Multilinear compressive sensing and an application to convolutional linear networks.  SIAM, 2018.
  * [13] Francois Malgouyres.  On the stable recovery of deep structured linear networks under sparsity constraints.  Proceedings of Machine Learning Research, 2020.
  * [14] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  Norm-Based Capacity Control in Neural Networks.  Journal of Machine Learning Research, 2015.
  * [15] Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro.  Path-SGD - Path-Normalized Optimization in Deep Neural Networks.  NIPS, 2015.
  * [16] Qi Meng, Shuxin Zheng, Huishuai Zhang, Wei Chen 0034, Qiwei Ye, Zhi-Ming Ma, Nenghai Yu, and Tie-Yan Liu.  G-SGD - Optimizing ReLU Neural Networks in its Positively Scale-Invariant Space.  ICLR, 2019.
  * [17] Mingyang Yi, Qi Meng, Wei Chen, Zhi-ming Ma, and Tie-Yan Liu.  Positively Scale-Invariant Flatness of ReLU Neural Networks.  arXiv:1903.02237 [cs, stat], March 2019.  arXiv: 1903.02237.
  * [18] Pierre Stock, Benjamin Graham, Remi Gribonval, and Hervé Jégou.  Equi-normalization of Neural Networks.  In ICLR 2019 - Seventh International Conference on Learning Representations, pages 1–20, New Orleans, United States, May 2019\.
  * [19] Qunyong Yuan and Nanfeng Xiao.  Scaling-Based Weight Normalization for Deep Neural Networks.  IEEE Access, 7:7286–7295, January 2019.  Publisher: IEEE.
  * [20] Eldad Meller, Alexander Finkelstein, Uri Almog, and Mark Grobman.  Same, Same But Different - Recovering Neural Network Quantization Error Through Weight Factorization.  arXiv:1902.01917 [cs, stat], February 2019.  arXiv: 1902.01917.
  * [21] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling.  Data-Free Quantization Through Weight Equalization and Bias Correction.  arXiv:1906.04721 [cs, stat], November 2019.  arXiv: 1906.04721.
  * [22] Nicholas Carlini, Matthew Jagielski, and Ilya Mironov.  Cryptanalytic extraction of neural network models, 2020.
  * [23] Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro.  Path-sgd: Path-normalized optimization in deep neural networks.  arXiv preprint arXiv:1506.02617, 2015.
  * [24] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling.  Data-free quantization through weight equalization and bias correction, 2019.
  * [25] Eldad Meller, Alexander Finkelstein, Uri Almog, and Mark Grobman.  Same, same but different - recovering neural network quantization error through weight factorization, 2019.
  * [26] Mingyang Yi, Qi Meng, Wei Chen, Zhi ming Ma, and Tie-Yan Liu.  Positively scale-invariant flatness of ReLU neural networks, 2019.
  * [27] Qi Meng, Shuxin Zheng, Huishuai Zhang, Wei Chen, Zhi-Ming Ma, and Tie-Yan Liu.  $\mathcal{G}$-sgd: Optimizing relu neural networks in its positively scale-invariant space, 2018.
  * [28] Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns, 2019.
  * [29] Razvan Pascanu, Guido Montufar, and Yoshua Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations, 2013.
  * [30] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, 2014.
  * [31] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In Proceedings of the 34th International Conference on Machine Learning, 2017.
  * [32] Mary Phuong and Christoph H Lampert.  Functional vs. parametric equivalence of relu networks.  In International Conference on Learning Representations, 2019.
  * [33] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  In Proceedings of the IEEE, volume 86, pages 2278–2324, 1998.
  * [34] Jeremy Bernstein, Jiawei Zhao, Markus Meister, Ming-Yu Liu, Anima Anandkumar, and Yisong Yue.  Learning compositional functions via multiplicative weight updates.  Advances in neural information processing systems, 33, 2020.
  * [35] David Balduzzi, Marcus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams.  The shattered gradients problem: If resnets are the answer, then what is the question?, 2018.

##  Appendix A Proof of Lemma 7

To lighten notations we omit the dependence of $W,V$ and $\boldsymbol{S}$ on
$\theta$. The proof follows three steps.

##### 1) $\boldsymbol{S}$ is well-defined.

Consider $\alpha\in W$ and $\nu\in H$. First, since $\theta$ is admissible,
there exists at least one path $p$ connecting $\nu$ to some output neuron
$\eta$ through edges $e\in E\cap\mathtt{supp}(\theta)$. We wish to show that
if $p$ and $p^{\prime}$ are two such partial paths then $\sum_{e\in
p}\alpha_{e}=\sum_{e\in p^{\prime}}\alpha_{e}.$ Since $\theta$ is admissible,
there exists a partial path $\bar{p}$ going from some input neuron $\mu$ to
$\nu$ through edges $e\in E\cap\mathtt{supp}(\theta)$. Since
$\bar{p}_{\ell}=p_{\ell}=p^{\prime}_{\ell}$, define by concatenation the full
paths $q=(\bar{p}_{0},\ldots,\bar{p}_{\ell},p_{\ell+1},\ldots,p_{L})$ and
$q^{\prime}=(\bar{p}_{0},\ldots,\bar{p}_{\ell},p^{\prime}_{\ell+1},\ldots,p^{\prime}_{L})$.
As $q$ and $q^{\prime}$ have all their edges in $\mathtt{supp}(\theta)$, we
have ${\Phi}_{q}(\theta)\neq 0\neq{\Phi}_{q^{\prime}}(\theta)$. Since
$\alpha\in W$ and $q,q^{\prime}\in\mathcal{P}_{0}$, we have
${\Phi}_{q}(\theta)\cdot(\boldsymbol{P}\alpha)_{q}={\Phi}_{q^{\prime}}(\theta)\cdot(\boldsymbol{P}\alpha)_{q^{\prime}}=0$,
hence $(\boldsymbol{P}\alpha)_{q}=(\boldsymbol{P}\alpha)_{q^{\prime}}=0$ and

$\sum_{e\in\overline{p}}\alpha_{e}+\sum_{e\in p}\alpha_{e}=\sum_{e\in
q}\alpha_{e}=(\boldsymbol{P}\alpha)_{q}=0=(\boldsymbol{P}\alpha)_{q^{\prime}}=\sum_{e\in\overline{p}}\alpha_{e}+\sum_{e\in
p^{\prime}}\alpha_{e}.$

Thus, $\sum_{e\in q}\alpha_{e}=\sum_{e\in q^{\prime}}\alpha_{e}$ and
$\boldsymbol{S}$ is well-defined.

##### 2) $\boldsymbol{S}$ is injective on $V$.

Note that $\boldsymbol{S}$ is linear hence it is sufficient to show that its
kernel is reduced to zero. Let $\alpha\in V$ such that
$\boldsymbol{S}\alpha=0$. Since $\alpha_{\bar{H}}=0$ and
$\mathtt{supp}(\alpha)\subseteq\mathtt{supp}(\theta)$, we have $\alpha_{e}=0$
for each $e\in E\backslash\mathtt{supp}(\theta)$, hence it is sufficient to
show $\alpha_{e}=0$ for any edge $e=\mu\to\nu\in E\cap\mathtt{supp}(\theta)$.
Since $\theta$ is admissible, there is a partial path $\overline{p}$ going
from $\nu$ to some output neuron $\eta$ through edges $e^{\prime}\in
E\cap\mathtt{supp}(\theta)$. Since $e\in E\cap\mathtt{supp}(\theta)$, the
extended path $p:=\mu\to\overline{p}$ also has all its edges in
$E\cap\mathtt{supp}(\theta)$ and joins $\mu$ to an output neuron. We
distinguish three cases: in the first case, $\mu,\nu$ are two hidden neurons,
and

$\alpha_{e}=\sum_{e^{\prime}\in
p}\alpha_{e^{\prime}}-\sum_{e^{\prime}\in\overline{p}}\alpha_{e^{\prime}}=-(\boldsymbol{S}\alpha)_{\mu}+(\boldsymbol{S}\alpha)_{\nu}=0.$

In the second case, $\mu\in N_{0}$ is an input neuron, hence $p$ is a full
path with edges $e^{\prime}\in E\cap\mathtt{supp}(\theta)$, so that
${\Phi}_{p}(\theta)\neq 0$. Since $\alpha\in W$ it follows that
$\sum_{e^{\prime}\in p}\alpha_{e^{\prime}}=(\boldsymbol{P}\alpha)_{p}=0$ and
we also obtain $\alpha_{e}=0$. Finally, in the third case, $\nu\in N_{L}$ is
an output neuron hence $\bar{p}=(\nu)$ contains no edge, so that
$\sum_{e^{\prime}\in\bar{p}}\alpha_{e^{\prime}}=0$ and we get $\alpha_{e}=0$
as well.

##### c) $\boldsymbol{S}$ is surjective.

Consider $\beta\in\mathbb{R}^{H}$, and $\alpha\in\mathbb{R}^{E\cup\bar{H}}$ as
defined around (18). Consider $p=(p_{\ell},\dots,p_{L})\in\mathcal{P}$ (with
$0\leq\ell\leq L-1$) a full or partial path going from some neuron
$\mu=p_{\ell}\in N_{0}\cup H$ to an arbitrary output neuron $\eta=p_{L}\in
N_{L}$ through edges $e\in E\cap\mathtt{supp}(\theta)$. In the case of a full
path, $\mu\in N_{0}$ and

$\displaystyle\sum_{e\in p}\alpha_{e}$
$\displaystyle=-\beta_{p_{L-1}}+\sum_{j=1}^{L-1}(\beta_{p_{j}}-\beta_{p_{j-1}})+\beta_{p_{0}}=0.$

As this holds for any full path with edges $e\in\mathtt{supp}(\theta)$, and
since $\alpha_{\bar{H}}=0$, we get $\alpha\in W$. Since $\alpha_{e}=0$ for
$e\in E\backslash\mathtt{supp}(\theta)$ we have indeed
$\mathtt{supp}(\alpha)\subseteq\mathtt{supp}(\theta)$ hence $\alpha\in V$.

In the case of a partial path ($\ell\geq 1$), we have $\mu\in H$ and similarly

$\displaystyle\sum_{e\in p}\alpha_{e}$
$\displaystyle=-\beta_{p_{L-1}}+\sum_{j=\ell+1}^{L-1}(\beta_{p_{j}}-\beta_{p_{j-1}})=-\beta_{p_{\ell}}=-\beta_{\mu}$

hence $(\boldsymbol{S}\alpha)_{\mu}=\beta_{\mu}$. As this holds for any
$\mu\in H$, this shows that $(\boldsymbol{S}\alpha)=\beta$.

##  Appendix B Proof of Theorem 2

Denote $\eta=\min_{i\in\mathtt{supp}(\theta)}|\theta_{i}|$. Assume by
contradiction that $\theta$ is not locally S-identifiable from $\mathcal{X}$
with respect to $\Theta$. This implies that for each $n\geq 1$ there is
$\theta_{n}\in\Theta\cap B(\theta,\min(\eta,1/n))$ which is not scaling-
equivalent to $\theta$ such that
$\boldsymbol{R}_{\theta_{n}}=\boldsymbol{R}_{\theta}$ on $\mathcal{X}$. For
$n\geq 1/\epsilon$, since $\theta$ is PS-identifiable from $\mathcal{X}$ with
respect to $\Theta$ and since $\theta_{n}\in\Theta$ satisfies
$\boldsymbol{R}_{\theta_{n}}=\boldsymbol{R}_{\theta}$ on $\mathcal{X}$, we
have $\theta_{n}\sim_{PS}\theta$, hence there is a permutation
$\pi_{n}\in\mathfrak{S}_{G}$ such that $\pi_{n}\circ\theta_{n}\sim_{S}\theta$,
hence by Theorem 1

(47)
$\displaystyle\mathtt{sign}(\pi_{n}\circ\theta_{n})=\mathtt{sign}(\theta),\qquad\text{and}\qquad\boldsymbol{\Phi}(\pi_{n}\circ\theta_{n})$
$\displaystyle=\boldsymbol{\Phi}(\theta).$

Since the set of permutations is finite, there exists
$\pi\in\mathfrak{S}_{G}$, and an increasing subsequence $n_{k}$ such that
$\pi_{n_{k}}=\pi$ for each $k\geq 1$. By (47), for every $k$ we have

(48)
$\displaystyle\mathtt{sign}(\pi\circ\theta_{n_{k}})=\mathtt{sign}(\theta)\qquad\text{and}\qquad\boldsymbol{\Phi}(\pi\circ\theta_{n_{k}})=\boldsymbol{\Phi}(\theta).$

There is a permutation matrix
$\boldsymbol{\Pi}\in\mathbb{R}^{\mathcal{P}\times\mathcal{P}}$ such that
$\boldsymbol{\Phi}(\pi\circ\theta^{\prime})=\boldsymbol{\Pi}\boldsymbol{\Phi}(\theta^{\prime})$
for all $\theta^{\prime}\in\mathbb{R}^{E\cup\bar{H}}$. Since
$\lim_{k\to\infty}\theta_{n_{k}}=\theta$, by continuity of $\boldsymbol{\Phi}$
we obtain
$\boldsymbol{\Pi}\boldsymbol{\Phi}(\theta)=\boldsymbol{\Phi}(\pi\circ\theta)=\boldsymbol{\Phi}(\theta)$
hence for every $k\geq 1$

(49)
$\displaystyle\boldsymbol{\Phi}(\theta)=\boldsymbol{\Pi}^{-1}\boldsymbol{\Phi}(\theta)\stackrel{{\scriptstyle\eqref{eq:tmp3}}}{{=}}\boldsymbol{\Pi}^{-1}\boldsymbol{\Pi}\boldsymbol{\Phi}(\theta^{\prime}_{n_{k}})=\boldsymbol{\Phi}(\theta_{n_{k}}).$

Since $\theta$ is admissible, by Corollary 1, the equality
$\boldsymbol{\Phi}(\theta_{n_{k}})=\boldsymbol{\Phi}(\theta)$ implies
$\mathtt{supp}(\theta_{n_{k}})=\mathtt{supp}(\theta)$. This implies that
$\mathtt{sign}((\theta_{n_{k}})_{i})=0=\mathtt{sign}(\theta_{i})$ for each
$i\notin\mathtt{supp}(\theta)$. Since $\theta_{n_{k}}\in B(\theta,\eta)$ for
each $k$, we also have
$\mathtt{sign}((\theta^{\prime}_{n_{k}})_{i})=\mathtt{sign}(\theta_{i})\in\\{-1,1\\}$
for every $i\in\mathtt{supp}(\theta)$, hence
$\mathtt{sign}(\theta_{n_{k}})=\mathtt{sign}(\theta)$ for every $k$. Since
$\theta$ is admissible, by Theorem 1, the fact that
$\mathtt{sign}(\theta_{n_{k}})=\mathtt{sign}(\theta)$ and
$\boldsymbol{\Phi}(\theta_{n_{k}})=\boldsymbol{\Phi}(\theta)$ implies
$\theta^{\prime}_{n}\sim_{S}\theta$. This contradicts our assumption that
$\theta^{\prime}_{n}\not\sim_{S}\theta$ for every $n$.

##  Appendix C Proof of Lemma 3

We will prove the contraposition using the following observation.

######  Fact 4.

Consider $\alpha,\beta\in\mathbb{R}$ and $M>0$. For any $t\in[-M,\infty)$ we
have

$\alpha\mathtt{ReLU}(t)+\beta\mathtt{ReLU}(-t)=\begin{cases}\alpha t,&t\geq
0\\\ -\beta t,&t\leq
0\end{cases}\quad=(\alpha+\beta)\mathtt{ReLU}(t)-\beta\mathtt{ReLU}(t+M)+M.$

Assuming that $\theta$ has twins, consider a hidden layer $1\leq\ell\leq L-1$
and $T\subseteq N_{\ell}$ a pair of twin neurons $T=\\{\nu_{1},\nu_{2}\\}$.
Denote $\boldsymbol{w}_{i}=\boldsymbol{w}_{\bullet\to\nu_{i}}$,
$b_{i}=b_{\nu_{i}}$, $\boldsymbol{v}_{i}=\boldsymbol{w}_{\nu_{i}\to\bullet}$.
As these neurons are twins, there is $\lambda\in\mathbb{R}$ such that for
every $x\in\mathbb{R}^{N_{0}}$,

$z_{\nu_{2}}(\theta,x)=\langle\boldsymbol{w}_{2},y_{\ell-1}(\theta,x)\rangle+b_{2}=\lambda\left(\langle\boldsymbol{w}_{1},y_{\ell-1}(\theta,x)\rangle+b_{1}\right)=\lambda
z_{\nu_{1}}(\theta,x)$

In the case of positive twins we have $\lambda>0$, hence
$y_{\nu_{1}}(\theta,x)=\lambda y_{\nu_{2}}(\theta,x)$ for every $x$. Given
$\epsilon>0$ consider $\theta^{\prime}(\epsilon)$ obtained by keeping
unchanged all weights and biases in $\theta$ except the weights outgoing from
neurons $\nu_{i}$, $i=1,2$:
$\boldsymbol{v}^{\prime}_{1}=\boldsymbol{v}_{1}+\lambda\epsilon\mathtt{1}_{N_{\ell+1}}$,
$\boldsymbol{v}^{\prime}_{2}=\boldsymbol{v}_{2}-\epsilon\mathtt{1}_{N_{\ell+1}}$.
Since the linear layers and biases of hidden neurons up to layer $\ell$ are
unchanged, we have
$\boldsymbol{y}_{\ell}(\theta,x)=\boldsymbol{y}_{\ell}(\theta^{\prime},x)$ for