Joachim Bona-Pellissier Ab
email: joachim.bona-pellissier@univ-toulouse.fr

François Malgouyres

François Bachoc

Local Identifiability of Deep ReLU Neural Networks: the Theory

Is a sample rich enough to determine, at least locally, the parameters of a neural network? To answer this question, we introduce a new local parameterization of a given deep ReLU neural network by fixing the values of some of its weights. This allows us to define local lifting operators whose inverses are charts of a smooth manifold of a high dimensional space. The function implemented by the deep ReLU neural network composes the local lifting with a linear operator which depends on the sample. We derive from this convenient representation a geometric necessary and sufficient condition of local identifiability. Looking at tangent spaces, the geometric condition provides: 1/ a sharp and testable necessary condition of identifiability and 2/ a sharp and testable sufficient condition of local identifiability. The validity of the conditions can be tested numerically using backpropagation and matrix rank computations.

 consider a general class of networks amongst which ReLU networks, but the result only holds for one-hidden-layer neural networks. Furthermore this result also requires the knowledge of f θ on a whole domain.

, as well as ReLU in the fully-connected case

Introduction 1.Context and motivations

Neural networks are famous for their capacity to perform complex tasks in a wide variety of domains such as image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], object recognition [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF][START_REF] Shaoqing Ren | Faster R-CNN: Towards real-time object detection with region proposal networks[END_REF], speech recognition [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF][START_REF] Sak | Long short-term memory recurrent neural network architectures for large scale acoustic modeling[END_REF][START_REF] Hannun | Deep speech: Scaling up end-to-end speech recognition[END_REF], natural language processing [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF][START_REF] Mikolov | Recurrent neural network based language model[END_REF][START_REF] Kalchbrenner | Recurrent continuous translation models[END_REF], anomaly detection [START_REF] José | Deep learning and multivariate time series for cheat detection in video games[END_REF] or climate sciences [START_REF] Rilwan A Adewoyin | Tru-net: a deep learning approach to high resolution prediction of rainfall[END_REF].

The following properties of the parameters of neural networks have recently drawn attention: identifiability, inverse stability and stable recovery; from weaker to stronger. Let f θ (X) be the outputs of a network parameterized by the parameters θ, for given inputs X. Global identifiability means that if f θ (X) = f θ (X) then θ = θ, up to identified invariances, for instance neuron permutation and rescaling for ReLU networks. Local identifiability restricts this analysis for θ and θ sufficiently close. Then, inverse stability means that the distance between θ and θ (up to invariances) is bounded by a function of the distance between f θ (X) and f θ (X). Finally, stable recovery consists in obtaining an algorithm to approximately recover θ from a noisy version of f θ (X), with quantitative guarantees. In all cases, we must distinguish between statements for X being a finite list of inputs, in which case we would like X to be small, and for infinite X (for instance determining θ from the entire function f θ ). Identifiability from finite X, which is the focus of this paper, is important for different reasons. In the first place, model extraction attacks for neural networks have been a growing topic over the last years. Indeed, some algorithms are able to recover in practice the parameters of a neural network 36th Conference on Neural Information Processing Systems (NeurIPS 2022).

from queries [START_REF] Carlini | Cryptanalytic extraction of neural network models[END_REF][START_REF] Rolnick | Reverse-engineering deep ReLU networks[END_REF]. This can be a concern since neural network providers may wish to keep these parameters secret, for security [START_REF] Kurakin | Adversarial examples in the physical world[END_REF], for privacy [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF][START_REF] Carlini | The secret sharer: Evaluating and testing unintended memorization in neural networks[END_REF], or for intellectual property [START_REF] Zhang | Protecting intellectual property of deep neural networks with watermarking[END_REF].

A way of preventing such a recovery can be by guaranteeing that identifiability does not hold, that is to check that a necessary condition of identifiability is not met. On the opposite side, guaranteeing that identifiability holds is interesting in the position of an attacker. If the attacker has access to X, to f θ (X), and is able to compute a θ such that f θ (X) = f θ (X), the question then becomes: does this guarantee that θ = θ or shall the attacker expand X with new queries? The attacker needs a sufficient condition of identifiability.

Another important motivation for identifiability is having a better understanding and control of neural networks. Indeed, if the learning sample has the form (X, f θ (X)), with θ the parameters of a teaching network, global identifiability from X means that the global minimizer of the empirical risk is unique. In this case, if the global minimizer is reached, there will typically be no variability due to the optimization parameters (choice of the algorithm, number of epochs,...) and to stochasticity (for stochastic optimizers). Even if very recent works on double descent phenomena, e.g. [START_REF] Belkin | Two models of double descent for weak features[END_REF], highlight a benefit of overparameterization (thus absence of identifiability) for increasing prediction performances, a user may be interested in a small enough number of parameters to retain identifiability, if the loss of performance is mild compared to overparameterization.

Note that, of course, global identifiability is more relevant than local identifiability to the above motivations. This work nevertheless focuses on local identifiability, which is a necessary condition for global identifiability, and which analysis can be a first step to analyzing global identifiability. Local identifiability is also arguably insightful on the geometry of the relationship between the parameter space of θ and its image {f θ (X), θ varies}. Note that most existing identifiability, inverse stability and stable recovery results (see the next section) are also local.

Existing work on identifiability, inverse stability, stable recovery and attacks

Identifiability: Even though it has regained interest recently, the question of identifiability for neural networks is not new. Indeed, in the 1990s, some positive results of identifiability for networks with smooth activation functions (tanh, logistic sigmoid or Gaussian for instance) have been established [START_REF] Héctor | Uniqueness of the weights for minimal feedforward nets with a given input-output map[END_REF][START_REF] Albertini | Uniqueness of weights for neural networks[END_REF][START_REF] Kůrková | Functionally equivalent feedforward neural networks[END_REF][START_REF] Paul C Kainen | Uniqueness of network parametrization and faster learning[END_REF][START_REF] Fefferman | Reconstructing a neural net from its output[END_REF]. These results are mainly theoretical, they concern activation functions which are not the most used nowadays (in particular, they do not apply to ReLU networks), and assume full knowledge of the function f θ implemented by the network, which is impossible in practice.

When it comes to ReLU, for shallow [START_REF] Petzka | Notes on the symmetries of 2-layer ReLU-networks[END_REF][START_REF] Stock | Efficiency and Redundancy in Deep Learning Models : Theoretical Considerations and Practical Applications[END_REF] as well as deep [START_REF] Phuong | Functional vs. parametric equivalence of ReLU networks[END_REF][START_REF] Bona-Pellissier | Parameter identifiability of a deep feedforward ReLU neural network[END_REF] neural networks, some positive results of identifiability have been recently established. They show that under some conditions on the architecture and parameters of the network, the function implemented by the network uniquely characterizes its parameters, up to neuron permutation and rescaling operations. Although they apply to ReLU networks, these results share a limitation with those of previous paragraph: they assume the function implemented by the network to be known on the whole input space, or at least on an open subset of it.

As far as we know, there exists only one identifiability result for deep ReLU networks assuming the knowledge of f θ on a finite sample only. Stock and Gribonval [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF] give a theoretical condition for the existence of a finite set which locally identifies the parameters of a deep neural network. It is an existence result: it does not concretely provide such a finite set, nor does it allow to test local identifiability for any finite sample, as we propose in this work. The construction in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF] shares similarities with previous works on deep structured matrix factorization [START_REF] Malgouyres | On the identifiability and stable recovery of deep/multi-layer structured matrix factorization[END_REF][START_REF] Malgouyres | Multilinear compressive sensing and an application to convolutional linear networks[END_REF][START_REF] Malgouyres | On the stable recovery of deep structured linear networks under sparsity constraints[END_REF]. The present article also lies in this line of research.

Σ * 1 • ϕ(θ) N (X, θ) ϕ(θ) • Σ * 1 N (X, θ)
Figure 1: The local intersection between the affine space N (X, θ) (in green) and the smooth manifold Σ * 1 (color gradient). We also represent in red the tangent space to Σ * 1 at ϕ(θ). Left: The identifiable case. The intersection is reduced to {ϕ(θ)}. Right: The non identifiable case. The intersection, represented with a dashed white line, is not reduced to {ϕ(θ)}. [START_REF] Ge | Learning one-hidden-layer neural networks with landscape design[END_REF][START_REF] Zhang | Learning one-hidden-layer ReLU networks via gradient descent[END_REF][START_REF] Zhong | Recovery guarantees for one-hidden-layer neural networks[END_REF][START_REF] Zhou | A local convergence theory for mildly over-parameterized two-layer neural network[END_REF] or in the convolutional case [START_REF] Brutzkus | Globally optimal gradient descent for a ConvNet with Gaussian inputs[END_REF][START_REF] Zhang | Improved linear convergence of training CNNs with generalizability guarantees: A one-hidden-layer case[END_REF]. These references consider a finite X but provide a large sample complexity under which a smartly constructed initialization followed by a first order algorithm allows to stably recover the parameters of the network.

For deep networks, some stable recovery algorithms also exist, for instance for Heavyside activation function [START_REF] Arora | Provable bounds for learning some deep representations[END_REF], or for only recovering the first layer with sparsity assumptions [START_REF] Sedghi | Provable methods for training neural networks with sparse connectivity[END_REF] in the ReLU case, but to the best of our knowledge there does not exist any algorithm recovering fully a deep ReLU network from a finite sample.

Model inversion attacks:

For deep ReLU networks, when one has full access to the function implemented by the network, a practical algorithm [START_REF] Rolnick | Reverse-engineering deep ReLU networks[END_REF] sequentially constructs a sample X and approximately recovers the architecture and the parameters modulo permutation and rescaling. Similarly, formulating the problem as a cryptanalytic problem, [START_REF] Carlini | Cryptanalytic extraction of neural network models[END_REF] reconstructs a functionally equivalent network with fewer requests. As mentioned in Section 1.1, these two references are related to identifiability, but consider a different setting. In this article we consider an arbitrary given X, while they work mostly on its construction.

Contributions

1/ We establish a necessary and sufficient geometric condition of local identifiability from a finite sample X for deep fully-connected ReLU networks. The condition is that the intersection between an affine space and a smooth manifold is reduced to a single point. See Figure 1 for an illustration.

2/ Considering tangent spaces, we then provide a computable necessary condition of local identifiability from a finite sample X. Since global identifiability implies local identifiability, it is also a computable necessary condition of global identifiability.

3/

We also establish a computable sufficient condition of local identifiability, which is close to the necessary condition. To the best of our knowledge, these are the first testable conditions of local identifiability for any finite input sample. In particular, [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF] provides a theoretical condition equivalent to the existence of a finite sample for which local identifiability holds, but does not provide the sample explicitly, nor does it characterize local identifiability for any arbitrary sample.

4/

To prove these results, we develop geometric tools which can be of independent interest for theoretically understanding deep ReLU networks as well as for possible applications. Namely, we introduce local reparameterizations ρ θ of the network by fixing some weight values as constants. Building on these local parameterizations, we introduce local lifting operators ψ θ and we decompose the function implemented by the network f θ (x) as a composition of ψ θ , which only depends on the parameters, and a piecewise constant operator α which depends on θ and the inputs x i . For almost any parameterization θ, the operator α is constant in a neighborhood of θ and consists in applying a linear function to ψ θ . We show that in fact, the operators ψ θ are the inverses of coordinate charts of a smooth manifold Σ * 1 , contained in a high dimensional space. We find Σ * 1 to be of particular interest 3 in representing geometrically some properties of the network parameters (in particular to establish 1/, 2/ and 3/ above).

Overview of the article

This work is structured as follows. We start by introducing basic tools and already known results, and we state the definition of local identifiability in Section 2. We then introduce the local parameterizations ρ θ and the set Σ * 1 , and we show that the latter is a smooth manifold in Section 3. This allows us to state our main results in Section 4, that is the geometric and the numerically testable conditions of local identifiability. Finally we discuss in Section 5 the numerical computations needed to test the latter conditions. All the proofs are provided in the appendices.

2 ReLU networks, lifting operator and rescaling of the parameters

ReLU networks

Let us introduce our notations for deep fully-connected ReLU networks. In this paper, a network is a graph (E, V ) of the following form.

• V is a set of neurons, which is divided in L + 1 layers, with L ≥ 2: V = (V l ) l∈ 0,L .
V 0 is the input layer, V L the output layer and the layers V l with 1 ≤ l ≤ L -1 are the hidden layers. Using the notation |C| for the cardinal of a finite set C, we denote, for all l ∈ 0, L , N l = |V l | the size of the layer V l .

• E is the set of all oriented edges v → v ′ between neurons in consecutive layers, that is

E = {v → v ′ , v ∈ V l , v ′ ∈ V l+1 , for l ∈ 0, L -1 }.
A network is parameterized by weights and biases, gathered in its parameterization θ, with

θ = ((w v→v ′ ) v→v ′ ∈E , (b v ) v∈B ) ∈ R E × R B ,
where B = L l=1 V l . It is also convenient to consider the weights and biases in matrix/vector form: for a given θ, we denote, for l ∈ 1, L ,

W l = (w v→v ′ ) v ′ ∈V l ,v∈V l-1 ∈ R N l ×N l-1 and b l = (b v ) v∈V l ∈ R N l .
When dealing with two parameterizations θ and θ ∈ R E × R B , we take as a convention that w v→v ′ and b v as well as W l and b l denote the weights and biases associated to θ, and wv→v ′ and bv as well as W l and bl denote those associated to θ.

The activation function, denoted σ, is always ReLU: for any p ∈ N * and any vector x = (x 1 , . . . , x p ) T ∈ R p , it is defined as σ(x) = (max(x 1 , 0), . . . , max(x p , 0)) T .

For a given θ, we define recursively f l : R V0 → R V l (we omit the dependency in θ in the notation for simplicity), for l ∈ 0, L , by

• ∀x ∈ R V0 , f 0 (x) = x ; • ∀l ∈ 1, L -1 , ∀x ∈ R V0 , f l (x) = σ (W l f l-1 (x) + b l ); • ∀x ∈ R V0 , f L (x) = W L f L-1 (x) + b L .
We define the function f θ : R V0 → R V L implemented by the network of parameter θ as f θ = f L .

The lifting operator ϕ and the activation operator α

For a fixed x ∈ R V0 , the value of f θ (x) is a non-linear function of θ. The goal of this section is to obtain a higher-dimensional representation of θ, that will be written ϕ(θ), and such that f θ (x) is locally a linear function of ϕ(θ). This will be achieved with Proposition 1. The function ϕ is called a lifting operator, a wording borrowed from category theory and commonly used in compressed sensing and dictionary learning, for instance in [START_REF] Emmanuel | Phase retrieval via matrix completion[END_REF]. The components of ϕ(θ) will be associated to paths in the neural network. Linearity in Proposition 1 will correspond to summing over these paths.

We now introduce the paths notations. For all l ∈ 0, L -1 , we define

P l = V l × • • • × V L-1 ,
which is the set of all paths in the network starting from layer l and ending in layer L -1. We consider an additional element β which can be interpreted as an empty path and whose role will be clear once ϕ has been defined and Proposition 1 stated. We define

P = L-1 l=0 P l ∪ {β}.
In a similar way to [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF], we can now define the above-mentioned 'lifting operator'

ϕ : R E × R B -→ R P×V L θ -→ (ϕ p,v (θ)) p∈P,v∈V L (1) by:
• for all l ∈ 0, L -1 and all p = (v l , . . . , v L-1 ) ∈ P l , and for all v L ∈ V L ,

ϕ p,v L (θ) = ® L-1 l ′ =0 w v l ′ →v l ′ +1 if l = 0 b v l L-1 l ′ =l w v l ′ →v l ′ +1 if l ≥ 1; • for p = β and v L ∈ V L , ϕ β,v L (θ) = b v L .
To define the activation operator, we first define, for all l ∈ 1,

L -1 , all v ∈ V l , all θ ∈ R E × R B and x ∈ R V0 , a v (x, θ) = ® 1 if (W l f l-1 (x) + b l ) v ≥ 0 0 otherwise,
which is the activation indicator of neuron v. We then define the 'activation operator'

α : R V0 × R E × R B -→ R 1×P (x, θ) -→ (α p (x, θ)) p∈P (2) by:
• for all l ∈ 0, L -1 and all p = (v l , . . . , v L-1 ) ∈ P l :

α p (x, θ) = ® x v0 L-1 l ′ =1 a v l ′ (x, θ) if l = 0 L-1 l ′ =l a v l ′ (x, θ) if l ≥ 1; • for p = β, α β (x, θ) = 1.
We then have the announced linear representation of the function f θ implemented by the network.

Proposition 1. For all θ ∈ R E × R B and all x ∈ R V0 , f θ (x) T = α(x, θ)ϕ(θ).
This result, which is proven in Appendix B, is for instance also stated in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF]Sec. 4] with slightly different notations. Note that each component of the vector f θ (x) above is written as a sum over a (very large) number of paths.

Let us reformulate Proposition 1 with several inputs. We consider, for some n ∈ N * , some given inputs x i ∈ R V0 , with i ∈ 1, n . We denote by X ∈ R n×V0 the matrix whose lines are the transpose (x i ) T of the inputs. For all θ ∈ R E × R B , we denote by f θ (X) ∈ R n×V L the matrix whose lines are the transpose f θ (x i ) T of the corresponding outputs. We also denote by α(X, θ) ∈ R n×P the matrix whose lines are the line vectors α(x i , θ). Using Proposition 1 for all the x i , we have the relation

f θ (X) = α(X, θ)ϕ(θ). (3)
We prove in Appendix B the next proposition, which states that θ → α(X, θ) is piecewise constant.

Proposition 2. For all n ∈ N * , for all X ∈ R n×V0 , the mapping

α X : R E × R B -→ R n×P θ -→ α(X, θ)
is piecewise-constant, with a finite number of pieces. Furthermore, the boundary of each piece has Lebesgue measure zero. We call ∆ X the union of all these boundaries. The set ∆ X ⊂ R E × R B is closed and has Lebesgue measure zero.

As discussed before, for a given X ∈ R n×V0 , when studying the function θ → f θ (X), Proposition 2 alongside (3) shows that on a piece over which α X is constant, f θ (X) depends linearly on ϕ(θ).

Since ∆ X is closed with measure zero, for almost all θ ∈ R E × R B , there exists a neighborhood of θ over which α X is constant. As noted for instance by Stock and Gribonval [39,Sec. 2], for any θ in such a neighborhood, we thus have

f θ (X) -f θ (X) = α(X, θ) Ä ϕ(θ) -ϕ( θ) ä . (4)
Hence, studying ϕ will allow us to understand better how f θ (X) locally depends on θ.

Invariant rescaling operations on θ

Some well-known rescaling operations on the parameters θ do not affect the value of ϕ(θ). Before detailing them, let us define, for all t ∈ R, the sign indicator sign(t) as 1, 0 or -1 depending on whether t > 0, t = 0 or t < 0 respectively. For any θ ∈ R E × R B , we then define

sign(θ) = (sign(w v→v ′ ) v→v ′ ∈E , (sign(b v )) v∈B ∈ {-1, 0, 1} E × {-1, 0, 1} B .
We can now describe the rescaling operations.

Definition 3. Let θ ∈ R E × R B and θ ∈ R E × R B .
• We say that θ is equivalent to θ modulo rescaling, and we write θ R ∼ θ iff there exists a family of vectors (λ 0 , . . . , λ

L ) ∈ (R * ) V0 × • • • × (R * ) V L , with λ 0 = 1 V0 and λ L = 1 V L , such that, for all l ∈ 1, L , ® W l = Diag(λ l ) W l Diag(λ l-1 ) -1 b l = Diag(λ l ) bl . (5)
• We say that θ is equivalent to θ modulo positive rescaling, and we write θ ∼ θ iff θ R ∼ θ and sign(θ) = sign( θ).

For all l ∈ 1, L , to satisfy ( 5) is equivalent to satisfy, for all

(v l-1 , v l ) ∈ V l-1 × V l ,    w v l-1 →v l = λ l v l λ l-1 v l-1 wv l-1 →v l b v l = λ l v l bv l . (6)
The relations R ∼ and ∼ are equivalence relations on the set of parameters R E × R B . The equivalence modulo positive rescaling ∼ is a well-known invariant for ReLU networks [START_REF] Stock | Efficiency and Redundancy in Deep Learning Models : Theoretical Considerations and Practical Applications[END_REF][START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF][START_REF] Bona-Pellissier | Parameter identifiability of a deep feedforward ReLU neural network[END_REF][START_REF] Behnam Neyshabur | Path-SGD: Path-normalized optimization in deep neural networks[END_REF][START_REF] Yi | Positively scale-invariant flatness of ReLU neural networks[END_REF]. We have indeed the following property: if θ ∼ θ, for all x ∈ R V0 ,

f θ (x) = f θ (x). (7)
One of the interests of the operator ϕ is that it captures this invariant, as described by Stock and Gribonval [39,Sec. 2.4]. Propositions 4 and 5 are similar to their results and are restated here and proven in Appendix B for completeness. Indeed, combining the definition of ϕ with (6), we have the following property.

Proposition 4. For all θ, θ ∈ R E × R B , we have θ R ∼ θ =⇒ ϕ(θ) = ϕ( θ),
and thus in particular θ ∼ θ =⇒ ϕ(θ) = ϕ( θ).

The reciprocal of Proposition 4 holds provided we exclude some degenerate cases. Let us denote, for any l ∈ 1, L -1 and any v ∈ V l , by w •→v the vector

(w v ′ →v ) v ′ ∈V l-1 ∈ R V l-1
and by w v→• the vector (w v→v ′ ) v ′ ∈V l+1 ∈ R V l+1 . We define the following set, which is close to the notion of 'non admissible parameter' in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF]:

S = {θ ∈ R E × R B , ∃v ∈ V 1 ∪ • • • ∪ V L-1 , w v→• = 0 or (w •→v , b v ) = (0, 0)}.
When w v→• = 0, all the outward weights of v are zero. When (w •→v , b v ) = (0, 0), all the inward weights as well as the bias of v are zero, so for any input the information flowing through neuron v is always zero. In both cases, the neuron v does not contribute to the output and could be removed from the network without changing the function f θ . Since the set S is a finite union of linear subspaces of codimension larger than 1, it is closed and has Lebesgue measure zero. We can thus exclude the degenerate cases in S without loss of generality. Proposition 5 states that the reciprocal of Proposition 4 holds over R E × R B \S.

Proposition 5. For all θ ∈ R E × R B \S, for all θ ∈ R E × R B , ϕ(θ) = ϕ( θ) =⇒ θ R ∼ θ.

Local identifiability

We have now introduced all the concepts used in the formal definition of 'local identifiability'. Definition 6. Let X ∈ R n×V0 and θ ∈ R E × R B . We say that θ is locally identifiable from X if there exists ϵ > 0 such that for all

θ ∈ R E × R B , if ∥θ -θ∥ ∞ < ϵ, f θ (X) = f θ (X) =⇒ θ ∼ θ.
3 The smooth manifold Σ * 1

We explained in the previous section that studying ϕ allows to better understand how the output f θ (X) locally depends on θ. The image of ϕ is of particular interest in this study and is the subject of this section. We define

Σ * 1 = {ϕ(θ), θ ∈ R E × R B \S}.
The main result of this section, Theorem 7, states that Σ * 1 is a smooth manifold. This result is a key element of the article. Indeed, it allows to consider tangent spaces to Σ * 1 , and by doing so, to linearize the geometric characterization of Theorem 8 illustrated in Figure 1. Instead of considering the intersection between a smooth manifold and an affine space as in Theorem 8, this indeed allows to consider the intersection between two affine spaces, which can be characterized with rank computations as in Theorems 9 and 10.

To show this result, we need local injectivity. In this aim, let us consider a fixed θ and analyze the functions u → f θ+u (X) and u → ϕ(θ + u) for u around 0. We can select N 1 + • • • + N L-1 scalar scaling parameters (each in a neighborhood of 1), and use them to "rescale" θ + u as in Definition 3, leaving f θ+u (X) and ϕ(θ + u) unchanged ((7) and Proposition 4). Locally, at first order, this means that there are N 1 + • • • + N L-1 linear combinations of u which leave f θ+u (X) and ϕ(θ + u) invariant. In order to obtain injectivity with respect to u, locally around 0, we will fix

N 1 +• • •+N L-1 components of u as follows.
For each neuron v in a hidden layer, we choose the outward edge v → v ′ whose weight w v→v ′ has largest (absolute) value (if there are several such edges, we choose one arbitrarily). We denote by s θ max (v) such a neuron v ′ . For each neuron v in a hidden layer V l , there is exactly one neuron s θ max (v) in the layer V l+1 , and one corresponding edge v → s θ max (v). See Figure 2 for an illustration. We will set to 0 the components of u corresponding to all the edges of the form v → s θ max (v). Intuitively, The outward edges of a hidden neuron v and their weights. In this example,

❼ ❼ ❼ ❼ wv→v 1 τv→v 2 τv→v 3 v v 1 v 2 v 3 ❼ ❼ ❼ ❼ ❼ ❼ ❼ ❼ ❼ ❼ ❼ ❼ ■♥♣✉t ❍✐❞❞❡♥ •❛②❡rs ❖✉t♣✉t
v 1 = s θ max (v)
, so the weight of the edge in red, v → v 1 , has its value fixed as w v→v1 . The weights of the remaining edges, τ v→v2 and τ v→v3 , are free to vary. Right: In red, all the edges whose weights are fixed. The remaining edges, in black, constitute the set F θ . it will not limit the set of functions f θ , in the vicinity of f θ ; but will permit to obtain a one-to-one correspondence between u and f θ+u .

More precisely, let us denote by F θ ⊂ E the set of remaining edges, which is formally defined as1

F θ = E \ L-1 l=1 (v, s θ max (v)), v ∈ V l . ( 8
)
The mapping from the space of restricted parameters R F θ × R B to the parameter space R E × R B locally around θ is simply given by the following application

ρ θ : R F θ × R B -→ R E × R B τ -→ θ such that    ∀(v, v ′ ) ∈ F θ , wv→v ′ = τ v→v ′ ∀(v, v ′ ) ∈ E\F θ , wv→v ′ = w v→v ′ ∀v ∈ B, bv = τ v . (9)
In particular, if we define

τ θ ∈ R F θ ×R B by (τ θ ) v→v ′ = w v→v ′ and (τ θ ) v = b v , we have ρ θ (τ θ ) = θ.
The function ρ θ is affine and injective. We define

U θ = ρ -1 θ R E × R B \S , (10)
which is an open set of R F θ × R B . We define, for all θ ∈ R E × R B \S, the local lifting operator

ψ θ : U θ -→ R P×V L τ -→ ϕ • ρ θ (τ ). (11)
One can show that ψ θ is C ∞ and that it is a homeomorphism from U θ onto its image (see the proofs in Appendix C), which we denote V θ and is thus an open subset of Σ * 1 (with the topology induced on Σ * 1 by the standard topology on R P×V L ). In particular, since

ρ θ (τ θ ) = θ, we have ϕ(θ) = ψ θ (τ θ ) ∈ V θ .
We have the following fundamental result that will allow us to consider and make use the tangent spaces of

Σ * 1 . Theorem 7. Σ * 1 is a smooth manifold of R P×V L of dimension |F θ | + |B| = N 0 N 1 + N 1 N 2 + • • • + N L-1 N L + N L ,
and the family (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is an atlas.

Theorem 7 is proven in Appendix C. Besides being key in Section 4, Theorem 7 (both the smooth manifold nature of Σ * 1 and the explicit atlas (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S ) may also be considered of more general independent interest. To our knowledge, such a result has not been established elsewhere in the literature. Notice that, as announced, despite the use of restricted parameters in R F θ × R B , we can represent the whole tangent space at any point of Σ * 1 . The only consequence of the restriction is the uniqueness of the representation of the elements of tangent spaces.

Main results: necessary and sufficient conditions for local identifiability

The main results of this paper rely on the decomposition (4) introduced in Section 2. To reformulate (4), let us introduce the linear operator A(X, θ), which simply corresponds to the matrix product with α(X, θ):

A(X, θ) :

R P×V L -→ R n×V L η -→ α(X, θ)η,
where α(X, θ)η is the matrix product between α(X, θ) ∈ R n×P and η ∈ R P×V L . The operator A(X, θ) inherits the properties of α(X, θ), in particular those stated in Proposition 2. Using A(X, θ), the relation (4) satisfied by θ in the neighborhood of θ becomes

f θ (X) -f θ (X) = A(X, θ) • Ä ϕ(θ) -ϕ( θ) ä . ( 12
)
Let us also define the affine space (set-sum of a fixed point and a vector space)

N (X, θ) = ϕ(θ) + Ker A(X, θ). If a parameterization θ ∈ R E × R B is such that f θ (X) = f θ (X)
and ( 12) holds, then ϕ(θ)ϕ( θ) ∈ Ker A(X, θ), so by definition ϕ( θ) ∈ N (X, θ). Since for θ in the neighborhood of θ, we also have ϕ( θ) ∈ Σ * 1 , we see that local identifiability is closely related to the nature of the intersection between the smooth manifold Σ * 1 and the affine subspace N (X, θ).

Indeed, let us denote by B ∞ (ϕ(θ), ϵ) = {η ∈ R P×V L , ∥ϕ(θ) -η∥ ∞ < ϵ} the ball of center ϕ(θ)
and of radius ϵ > 0. We have the following geometric necessary and sufficient condition of local identifiability, which states that local identifiability of θ holds if and only if the intersection between Σ * 1 and N (X, θ) is locally reduced to the single point {ϕ(θ)}. Theorem 8. For any

X ∈ R n×V0 and θ ∈ R E × R B \(S ∪ ∆ X ), the two following statements are equivalent. i) θ is locally identifiable from X. ii) There exists ϵ > 0 such that B ∞ (ϕ(θ), ϵ) ∩ Σ * 1 ∩ N (X, θ) = {ϕ(θ)}.
Theorem 8 is proven in Appendix D, and is illustrated in Figure 1. This geometric condition is crucial for showing the next two results which give testable conditions of identifiability. Theorems 9 and 10 rely on the rank of A(X, θ) and of another linear operator Γ(X, θ), which we now define. Since, as we said, the function ψ θ is C ∞ , let us denote by Dψ θ (τ ) : R F θ × R B → R P×V L its differential at the point τ , for any τ ∈ U θ . We define the linear operator Γ(X, θ) : R

F θ × R B → R n×V L by Γ(X, θ) = A(X, θ) • Dψ θ (τ θ ). (13)
We denote

R A = rank(A(X, θ)) and R Γ = rank(Γ(X, θ)). Since Γ(X, θ) is defined on R F θ × R B , we have 0 ≤ R Γ ≤ |F θ | + |B|,
and the expression [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF] shows that we also have 0 ≤ R Γ ≤ R A . We can now define the two following conditions.

Condition C N . Condition C N is satisfied by (θ, X) iif R Γ < R A or R Γ = |F θ | + |B|. Condition C S . Condition C S is satisfied by (θ, X) iif R Γ = |F θ | + |B|.
The following result states that C N is necessary for local and therefore global identifiability. Theorem 9 (Necessary condition of identifiability).

Let X ∈ R n×V0 and θ ∈ R E × R B \(S∪∆ X ).
If C N is not satisfied, then θ is not locally identifiable from X (thus not globally identifiable).

The following result states that C S is a sufficient condition of local identifiability. Theorem 10 (Sufficient condition of local identifiability).

Let X ∈ R n×V0 and θ ∈ R E × R B \(S ∪ ∆ X ). If C S is satisfied, then θ is locally identifiable from X.
Both theorems are proven in Appendix D. To discuss these two results, let us point out that the output spaces of Γ(X, θ) and A(X, θ) have the same dimension, equal to nN L . Each new input adds N L to this dimension. One can verify that R A -R Γ is initially 0 and cannot decrease when new inputs are added. If a new input leads to R A > R Γ , it can be discarded to preserve R A = R Γ . Moreover, such an input seems unlikely when

R A < |F θ | + |B|. If the equality R Γ = R A is enforced, the condition R Γ = |F θ | + |B|

Checking the conditions numerically

The key benefit of the conditions C N and C S , compared to the existing literature, is that they can be numerically tested for any fixed finite sample. They need the computation of the rank of two linear operators, namely Γ(X, θ) and A(X, θ). The operator Γ(X, θ) satisfies the following:

Proposition 11. Let X ∈ R n×V0 and θ ∈ R E × R B \(S ∪ ∆ X ). The function τ → f ρ θ (τ ) (X), for τ ∈ U θ is differentiable in a neighborhood of τ θ ,

and we denote by

D τ f ρ θ (τ θ ) (X) its differential at τ θ . We have D τ f ρ θ (τ θ ) (X) = Γ(X, θ). ( 14
)
The proof of Proposition 11 is in Appendix E. Since the reparameterization with ρ θ simply consists in fixing the weights of the edges v → s θ max (v) to the value w v→s θ max (v) , (59) shows that the coefficients of Γ(X, θ) can be computed by a classic backpropagation algorithm N L times for each input x i , simply omitting the derivatives with respect to the edges of the form v → s θ max (v). An explicit expression of the coefficients of Γ(X, θ) is given in the Appendix E.

To be satisfied, C S needs the dimensions of Γ(X, θ) to satisfy nN L ≥ |F θ | + |B|. One then needs to compute the rank R Γ of Γ(X, θ), which means computing the rank of a nN L × (|F θ | + |B|) matrix. Existing algorithms allow to do this with a complexity O(nN L (|F θ | + |B|) ω-1 ) (up to polylog terms), where ω is the matrix multiplication exponent and satisfies ω < 2.38 [START_REF] Ho | Fast matrix rank algorithms and applications[END_REF].

When it comes to C N , one needs in addition to know the rank R A of A(X, θ), which, as Proposition 12 states, requires to compute the rank of α(X, θ).

Proposition 12. Let X ∈ R n×V0 and θ ∈ R E × R B . We have R A = N L rank (α(X, θ)).
The dimensions of α(X, θ) are sensibly larger, with |P| columns and n lines, and typically |P| >> n. However it may have some sparsity properties, as its entries consist in products of activation indicators (with possibly one input x i v0 ), any one of them being zero causing many entries to vanish. The question of the efficient computation of R A still needs to be explored and is left as open for future work.

Conclusion

This paper is the first to characterize local identifiability for deep ReLU networks for any given finite sample, with testable conditions. The practical use of these conditions deserves follow-up research, and so does an extension of our approach to inverse stability. The role of ReLU is crucial in our approach, especially for the necessary condition of local identifiability and with the linear representation (Proposition 1). In the end, from Theorem 10 and Proposition 11, the sufficient condition for local indentifiability is expressed from the Jacobian matrix of the neural network function with respect to its parameters. Extending this to other activation functions than ReLU is an interesting perspective. As for any such contributions, the positive or negative societal impact will depend on the application case. We do not promote any harmful use of this theory, but we expand on the existing knowledge.

A Notations

In this section, we define notations, many of which are standard, that are useful in the proofs.

We denote by N the set of all natural numbers, including 0, and by N * the set N without 0. We denote by Z the set of all integers. For any a, b ∈ Z, we denote by a, b the set of all integers k ∈ Z satisfying a ≤ k ≤ b. For any finite set A, we denote by |A| the cardinal of A.

For n, N ∈ N * , we denote by R N the N -dimensional real vector space and by R n×N the vector space of real matrices with n lines and N columns. For a vector x = (x 1 , . . . , x N ) T ∈ R N , we use the norm ∥x∥ ∞ = max i∈ 1,N |x i |. For x ∈ R N and r > 0, we denote B ∞ (x, r) = {y ∈ R N , ∥y -x∥ ∞ < r}.

For any vector x = (x 1 , . . . , x N ) T ∈ R N , we define sign(x) = (sign(x 1 ), . . . , sign(x N )) T ∈ {-1, 0, 1} N as the vector whose i th component is equal to

sign(x i ) =    1 if x i > 0 0 if x i = 0 -1 if x i < 0.
For any matrix M ∈ R n×N , for all i ∈ 1, n , we denote by M i,: the i th line of M . The vector M i,: is a line vector whose j th component is M i,j . Similarly, for j ∈ 1, N , we denote by M :,j the j th column of M , which is the column vector whose i th component is M i,j . For any matrix M ∈ R n×N , we denote by M T ∈ R N ×n the transpose matrix of M .

We denote by Id N the N × N identity matrix and by 1 N the vector (1, 1, . . . , 1) T ∈ R N . If λ ∈ R N is a vector of size N , for some N ∈ N * , we denote by Diag(λ) the N × N matrix defined by:

Diag(λ) i,j = ® λ i if i = j 0 otherwise.
If X and Y are two sets and h : X → Y is a function, for a subset A ⊂ Y , we denote by h -1 (A) the preimage of A under f , that is

h -1 (A) = {x ∈ X, h(x) ∈ A}.
Note that this does not require the function h to be injective.

For any n, N ∈ N * and any differentiable function f : R n → R N , for all x ∈ R n , we denote by Df (x) its differential at the point x, i.e. the linear application Df (x) :

R n → R N satisfying, for all h ∈ R n , f (x + h) = f (x) + Df (x) • h + o(h).
If we denote by x j and h j the components of x and h, for j ∈ 1, n , we have

Df (x) • h = n j=1 ∂f ∂x j (x)h j ,
where for all j, ∂f ∂xj (x) ∈ R N . If f : R n → R N is a linear application, we denote by Ker f the set {x ∈ R n , f (x) = 0}, which is a linear subset of R n .

B The lifting operator ϕ

Let us introduce the notion of 'path', extending the definition in Section 2.2. A path is a sequence of neurons

(v k , v k+1 , . . . , v l ) ∈ V k × V k+1 × • • • × V l , for integers k, l satisfying 0 ≤ k ≤ l ≤ L.
In particular, for all l ∈ 0, L -1 , the set P l defined in Section 2.2 contains all the paths starting from layer l and ending in layer L -1. We recall

P = L-1 l=0 P l ∪ {β}. If k, l, m ∈ N are three integers satisfying 0 ≤ k < l ≤ m ≤ L, and p = (v k , . . . , v l-1 ) ∈ V k × • • • × V l-1 and p ′ = (v l , . . . , v m ) ∈ V l × • • • × V m are
two paths such that p ends in the layer preceding the starting layer of p ′ , we define the union of the paths by

p ∪ p ′ = (v k , . . . , v l-1 , v l , . . . v m ) ∈ V k × • • • × V m .
Before proving Proposition 1, let us compare briefly our construction to [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF]. The lifting operator ϕ introduced in Section 2.2 is similar to the operator Φ in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF], except that Φ does not take a matrix form. The operator α(x, θ) introduced in Section 2.2 corresponds partly to the object α(θ, x) in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF]. One of the differences is that α(θ, x) does not include any product with x v0 in its entries, as does α(x, θ). Finally, a similar statement to Proposition 1 and a similar proof can be found in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF]. However, one of the present contributions is to simplify the construction.

Let us now prove Proposition 1, which we restate here. Proposition 13. For all θ ∈ R E × R B and all x ∈ R V0 ,

f θ (x) T = α(x, θ)ϕ(θ).
Proof. Let us prove first the following expression, for all v L ∈ V L :

f θ (x) v L = v0∈V0 . . . v L-1 ∈V L-1 x v0 w v0→v1 L-1 l=1 a v l (x, θ)w v l →v l+1 + L-1 l=1 v l ∈V l . . . v L-1 ∈V L-1 b v l L-1 l ′ =l a v l ′ (x, θ)w v l ′ →v l ′ +1 + b v L . (15)
We prove this by induction on the number L of layers of the network.

Initialization (L = 2). Let v 2 ∈ V 2 . f θ (x) v2 = (W 2 ) v2,: σ (W 1 x + b 1 ) + b v2 = v1∈V1 w v1→v2 [σ (W 1 x + b 1 )] v1 + b v2 = v1∈V1 w v1→v2 σ ((W 1 ) v1,: x + b v1 ) + b v2 = v1∈V1 w v1→v2 a v1 (x, θ) v0∈V0 w v0→v1 x v0 + b v1 + b v2 = Ö v0∈V0 v1∈V1 w v1→v2 a v1 (x, θ)w v0→v1 x v0 è + v1∈V1 w v1→v2 a v1 (x, θ)b v1 + b v2 = Ö v0∈V0 v1∈V1 x v0 w v0→v1 a v1 (x, θ)w v1→v2 è + v1∈V1 b v1 a v1 (x, θ)w v1→v2 + b v2
which proves [START_REF] Ge | Learning one-hidden-layer neural networks with landscape design[END_REF], when L = 2. Now let L ≥ 3 and suppose [START_REF] Ge | Learning one-hidden-layer neural networks with landscape design[END_REF] holds for all ReLU networks with L -1 layers. Let us consider a network with L layers.

Let us denote by g θ (x) the output of the L -1 first layers of the network pre-activation (before applying the ReLUs of the layer L -1). The function g θ is that of a ReLU network with L -1 layers, and we have

f θ (x) = W L σ(g θ (x)) + b L .
Let v L ∈ V L . We thus have

f θ (x) v L = v L-1 ∈V L-1 w v L-1 →v L σ(g θ (x) v L-1 ) + b v L . ( 16
)
By the induction hypothesis, for all v L-1 ∈ V L-1 , g θ (x) v L-1 can be expressed with [START_REF] Ge | Learning one-hidden-layer neural networks with landscape design[END_REF]. Considering that σ(g θ (x) v L-1 ) = a v L-1 (x, θ)g θ (x) v L-1 and replacing g θ (x) v L-1 by its expression using ( 15), ( 16) becomes

f θ (x) v L = v L-1 ∈V L-1 w v L-1 →v L a v L-1 (x, θ) v0∈V0 . . . v L-2 ∈V L-2 x v0 w v0→v1 L-2 l=1 a v l (x, θ)w v l →v l+1 + L-2 l=1 v l ∈V l . . . v L-2 ∈V L-2 b v l L-2 l ′ =l a v l ′ (x, θ)w v l ′ →v l ′ +1 + b v L-1 + b v L = v0∈V0 . . . v L-1 ∈V L-1 w v L-1 →v L a v L-1 (x, θ)x v0 w v0→v1 L-2 l=1 a v l (x, θ)w v l →v l+1 + L-2 l=1 v l ∈V l . . . v L-1 ∈V L-1 w v L-1 →v L a v L-1 (x, θ)b v l L-2 l ′ =l a v l ′ (x, θ)w v l ′ →v l ′ +1 + v L-1 ∈V L-1 w v L-1 →v L a v L-1 (x, θ)b v L-1 + b v L = v0∈V0 . . . v L-1 ∈V L-1 x v0 w v0→v1 L-1 l=1 a v l (x, θ)w v l →v l+1 + L-1 l=1 v l ∈V l . . . v L-1 ∈V L-1 b v l L-1 l ′ =l a v l ′ (x, θ)w v l ′ →v l ′ +1 + b v L ,
which proves (15) holds for ReLU networks with L layers. This ends the induction, and we conclude that (15) holds for all ReLU networks.

We can now use this expression to prove Proposition 13. The first sum in [START_REF] Ge | Learning one-hidden-layer neural networks with landscape design[END_REF] is taken over all the paths p = (v 0 , . . . , v L-1 ) ∈ P 0 , and each summand can be written as

x v0 w v0→v1 L-1 l=1 a v l (x, θ)w v l →v l+1 = x v0 L-1 l=1 a v l (x, θ) L-1 l=0 w v l →v l+1 = α p (x, θ)ϕ p,v L (θ).
For all l ∈ 1, L -1 , the inner sum of the double sum in ( 15) is taken over all the paths p = (v l , . . . , v L-1 ) ∈ P l , and each summand can be written as

b v l L-1 l ′ =l a v l ′ (x, θ)w v l ′ →v l ′ +1 = L-1 l ′ =l a v l ′ (x, θ) b v l L-1 l ′ =l w v l ′ →v l ′ +1 = α p (x, θ)ϕ p,v L (θ).
And finally, we can also write

b v L = α β (x, θ)ϕ β,v L (θ).
Joining all these sums and denoting ϕ :,v L (θ) = (ϕ p,v L (θ)) p∈P ∈ R P , we have

f θ (x) v L = p∈P α p (x, θ)ϕ p,v L (θ) = α(x, θ)ϕ :,v L (θ),
so in other words,

f θ (x) T = α(x, θ)ϕ(θ).
We restate here and prove Proposition 2. Proposition 14. For all n ∈ N * , for all X ∈ R n×V0 , the mapping

α X : R E × R B -→ R n×P θ -→ α(X, θ)
appearing in (3) is piecewise-constant, with a finite number of pieces. Furthermore, the boundary of each piece has Lebesgue measure zero. We call ∆ X the union of all the boundaries. The set ∆ X is closed and has Lebesgue measure zero.

Proof. Let us first notice that for any i ∈ 1, n , for any l ∈ 1, L -1 ,

a v (x i , θ) v∈V1∪•••∪V l-1 ∈ {0, 1} V1∪•••∪V l-1 takes at most 2 N1+•••+N l-1 distinct values, so the mapping θ → a v (x i , θ) v∈V1∪•••∪V l-1
is piecewise constant, with a finite number of pieces.

Let i ∈ 1, n . Let l ∈ 1, L -1 and v ∈ V l . Recall the definition of f l-1 , as given in Section 2.1.

The function θ → a v (x i , θ) takes only two values, 1 or 0, and its values are determined by the sign of

v ′ ∈V l-1 w v ′ →v f l-1 (x i ) v ′ + b v . (17)
For all v ′ ∈ V l-1 , the value of f l-1 (x i ) v ′ depends on θ. On a piece

P ⊂ R E × R B such that a v ′′ (x i , θ) v ′′ ∈V1∪•••∪V l-1
is constant, this dependence is polynomial. Thus, on P , the value of ( 17) is a polynomial function of θ, and since the coefficient applied to b v is equal to 1, the corresponding polynomial is non constant. Since the values of a v (x i , θ) are determined by the sign of (17), inside P , the boundary between [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF] equals 0. This piece of boundary is thus contained in a level set of a non constant polynomial, whose Lebesgue measure is zero.

{θ ∈ R E × R B , a v (x i , θ) = 0} and {θ ∈ R E × R B , a v (x i , θ) = 1} is included in the set of θ for which
Since there is a finite number of pieces P , the Lebesgue measure of the boundary between {θ ∈

R E × R B , a v (x i , θ) = 0} and {θ ∈ R E × R B , a v (x i , θ) = 1}
, which is contained in the union of the boundaries on all the pieces P , is thus equal to 0.

Since this is true for all l ∈ 1, L -1 and all v ∈ V l , the boundary of a piece over which a v (x i , θ) v∈V1∪•••∪V L-1 is constant also has Lebesgue measure zero. Now since, for all x i , the value of α(x i , θ) only depends on a v (x i , θ) v∈V1∪•••∪V L-1 and since α X (θ) is a matrix whose lines are the vectors α(x i , θ), we can conclude that α X : R E × R B -→ R n×P θ -→ α(X, θ) is piecewise-constant, with a finite number of pieces, and that the boundary of each piece has Lebesgue measure zero.

A boundary is, by definition, closed. Finally, a finite union of closed sets with Lebesgue measure 0, as ∆ X is, is closed and has Lebesgue measure 0.

For convenience, we introduce the two following notations. Let l ∈ 0, L . For any l ′ ∈ 0, l and any path

p i = (v l ′ , . . . , v l ) ∈ V l ′ × • • • × V l , we denote θ pi = ® l-1 k=0 w v k →v k+1 if l ′ = 0 b l ′ l-1 k=l ′ w v k →v k+1 if l ′ ≥ 1, (18)
where as a classic convention, an empty product is equal to 1. In particular, if l = 0, for any

p i = (v 0 ) ∈ V 0 , we have θ pi = 1. For any path p o = (v l , . . . , v L ) ∈ V l × • • • × V L , we denote θ po = L-1 k=l w v k →v k+1 , (19)
with again the convention that an empty product is equal to 1, so if l = L, θ po = 1.

Some attention must be paid to the fact that for any l ′ ∈ 1, L , if we take p i in the case l = L and p o in the case l = l ′ , it is possible to have

p i = (v l ′ , . . . , v L ) = p o ,
but in that case we DO NOT have

θ pi = θ po , since θ pi = b l ′ L-1 k=l ′ w v k →v k+1 and θ po = L-1
k=l ′ w v k →v k+1 . We will always denote the paths p i and p o with an i (as in 'input') or an o (as in 'output') to clarify which definition is used.

When considering another parameterization θ ∈ R E × R B , we denote by θpi and θpo the corresponding objects.

We establish different characterizations of the set S defined in Section 2.3 that will be useful in the proofs. As mentioned in Section 2.3, the subset of parameters R E × R B \S is close to the notion of 'admissible' parameter in [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF], but is slightly larger since the condition w •→v ̸ = 0 is replaced by

(w •→v , b v ) ̸ = (0, 0), for each hidden neuron v. Proposition 15. Let θ ∈ R E × R B . The following statements are equivalent. i) θ ∈ R E × R B \S.
ii) For all l ∈ 1, L-1 and all v l ∈ V l , there exist l ′ ∈ 0, l , a path

p i = (v l ′ , . . . , v l ) ∈ V l ′ ו • •×V l and a path p o = (v l , . . . , v L ) ∈ V l × • • • × V L such that θ pi ̸ = 0 and θ po ̸ = 0.
iii) For all l ∈ 1, L -1 and all v l ∈ V l , there exist l ′ ∈ 0, l , a path p = (v l ′ , . . . , v l , . . . , v L-1 ) ∈ P l ′ and v L ∈ V L such that ϕ p,v L (θ) ̸ = 0.

Proof. Let us show successively that

i) ⇒ ii), ii) ⇒ iii) and iii) ⇒ i). i) → ii) Let θ ∈ R E × R B \S. Let us show ii) holds.
Let l ∈ 1, L and v l ∈ V l . To form a path p i satisfying the condition, we follow the procedure:

p i ← (v l ) k ← l while k ≥ 1 and b k = 0 do ∃v k-1 ∈ V k-1 , w v k-1 →v k ̸ = 0 p i ← (v k-1 , p i ) k ← k -1 end while l ′ ← k
The existence of v k-1 in the loop is guaranteed by the fact that θ ̸ ∈ S and b k = 0 in the condition of the while loop. In the end, we obtain a path p i = (v l ′ , . . . , v l ) with either l ′ > 0 and b l ′ ̸ = 0, or l ′ = 0. In both cases, we have by construction

θ pi ̸ = 0.
We do similarly the other way to form a path p o = (v l , . . . , v L ). We follow the procedure:

p o ← (v l ) k ← l while k ≤ L -1 do ∃v k+1 ∈ V k+1 , w v k →v k+1 ̸ = 0 p o ← (p o , v k+1 ) k ← k + 1 end while
The existence of v k+1 in the loop is guaranteed by the fact that θ ̸ ∈ S. In the end, we obtain a path p o = (v l , . . . , v L ) satisfying by construction

θ po ̸ = 0. ii) → iii) Let l ∈ 1, L -1 and v l ∈ V l . There exist l ′ ∈ 0, l , a path p i = (v l ′ , . . . , v l ) ∈ V l ′ × • • • × V l and a path p o = (v l , . . . , v L ) ∈ V l × • • • × V L such that θ pi ̸ = 0 and θ po ̸ = 0. Denoting p = (v l ′ , . . . , v l , . . . , v L-1 ), we have ϕ p,v L (θ) = θ pi θ po ̸ = 0.
iii) → i) Let us show the contrapositive: let θ ∈ S, and let us show the statement iii) is not true. Indeed, if θ ∈ S, there exist l ∈ 1, L -1 and v l ∈ V l such that (w

•→v l , b v l ) = (0, 0) or w v l →• = 0.
Consider a path p = (v l ′ , . . . , v l , . . . , v L-1 ) and v L ∈ V L . We have

ϕ p,v L (θ) = ® b v l ′ w v l ′ →v l ′ +1 . . . w v l-1 →v l w v l →v l+1 . . . w v L-1 →v L if l ′ ≥ 1 w v0→v1 . . . w v l-1 →v l w v l →v l+1 . . . w v L-1 →v L if l ′ = 0. If (w •→v l , b v l ) = (0, 0), either l ′ = l and b v l ′ = 0 so ϕ p,v L (θ) = 0, or l ′ < l and since w v l-1 →v l = 0, we have ϕ p,v L (θ) = 0. If w v l →• = 0, w v l →v l+1 = 0 so ϕ p,v L (θ) = 0. Thus iii) is not satisfied.
We restate and prove Proposition 4. Proposition 16. For all θ, θ ∈ R E × R B , we have

θ R ∼ θ =⇒ ϕ(θ) = ϕ( θ),
and thus in particular θ ∼ θ =⇒ ϕ(θ) = ϕ( θ). 6) holds. We consider first a path p = (v 0 , . . . , v L-1 ) ∈ P 0 and v L ∈ V L . Using [START_REF] Brutzkus | Globally optimal gradient descent for a ConvNet with Gaussian inputs[END_REF] and the fact that

Proof. Let θ, θ ∈ R E × R B such that θ R ∼ θ. There exists a family (λ 0 , . . . , λ L ) ∈ (R * ) V0 × • • • × (R * ) V L , with λ 0 = 1 V0 and λ L = 1 V L , such that for all l ∈ 1, L , for all (v l-1 , v l ) ∈ V l-1 × V l , (
λ 0 v0 = λ L v L = 1, we have ϕ p,v L (θ) = L l=1 w v l-1 →v l = L l=1 λ l v l λ l-1 v l-1 wv l-1 →v l = λ L v L λ 0 v0 L l=1 wv l-1 →v l = ϕ p,v L ( θ).
Similarly, for l ∈ 1, L -1 and a path p = (v l , . . . , v L-1 ) ∈ P l , and for all v L ∈ V L , we have, using ( 6) and the fact that

λ L v L = 1, ϕ p,v L (θ) = b v l L l ′ =l+1 w v l ′ -1 →v l ′ = λ l v l bv l L l ′ =l+1 λ l ′ v l ′ λ l ′ -1 v l ′ -1 wv l ′ -1 →v l ′ = λ L v L bv l L l ′ =l+1 wv l ′ -1 →v l ′ = ϕ p,v L ( θ).
Finally, for p = β and v L ∈ V L , we have

ϕ p,v L (θ) = b v L = λ L v L bv L = bv L = ϕ p,v L ( θ).
This shows ϕ(θ) = ϕ( θ).

For the second implication, we simply use the fact that if θ ∼ θ, in particular, θ R ∼ θ.

so combining both equalities, we have

λ l v l θpi wv l-1 →v l = λ l-1 v l-1 θpi w v l-1 →v l .
Using the fact that θpi ̸ = 0 and λ l-1 v l-1 ̸ = 0, we finally obtain, for all l ∈ 1, L and all

(v l-1 , v l ) ∈ V l-1 × V l : w v l-1 →v l = λ l v l λ l-1 v l-1 wv l-1 →v l .
For all l ∈ 1, L and all v l ∈ V l , using [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] with p i = (v l ), we obtain

b v l = λ l v l bv l .
This shows that ( 6) is satisfied for all

(v l-1 , v l ) ∈ V l-1 × V l , and thus θ R ∼ θ.
The following proposition is useful in the proof of Theorem 26 and allows to improve identifiability modulo rescaling into identifiability modulo positive rescaling.

Proposition 19. For all θ ∈ R E × R B \S, there exists ϵ > 0 such that for all θ ∈ R E × R B , ∥θ -θ∥ ∞ < ϵ and θ R ∼ θ =⇒ θ ∼ θ. Proof. Let θ ∈ R E × R B \S. We define ϵ = min |w v→v ′ |, v → v ′ ∈ E and w v→v ′ ̸ = 0 ∪ |b v |, v ∈ B and b v ̸ = 0 . Let θ ∈ R E × R B such that ∥θ -θ∥ ∞ < ϵ and θ R ∼ θ.
To prove θ ∼ θ, we simply have to prove sign(θ) = sign( θ). There exists (λ 0 , . . . , λ 6) holds. Let us show that sign(θ) = sign( θ).

L ) ∈ (R * ) V0 × • • • × (R * ) V L , with λ 0 = 1 V0 and λ L = 1 V L , such that, for all l ∈ 1, L , for all (v l-1 , v l ) ∈ V l-1 × V l , (
Indeed, let l ∈ 1, L , and let (v, v ′ ) ∈ V l-1 × V l . If w v→v ′ ̸ = 0, then since |w v→v ′ -wv→v ′ | < ϵ and by definition ϵ ≤ |w v→v ′ |, we have sign(w v→v ′ ) = sign( wv→v ′ ). Otherwise, if w v→v ′ = 0, [START_REF] Brutzkus | Globally optimal gradient descent for a ConvNet with Gaussian inputs[END_REF] shows that we have

wv→v ′ = λ l-1 v λ l v ′
w v→v ′ = 0, so we still have sign(w v→v ′ ) = sign( wv→v ′ ).

Now let l ∈ 1, L and let v ∈ V l . Similarly, if b v ̸ = 0, we have |b v -bv | < ϵ ≤ |b v |, so sign(b v ) = sign( bv ), and if b v = 0, we have bv = b v λ l v = 0, so again sign(b v ) = sign( bv ).
This shows sign(θ) = sign( θ), so θ ∼ θ.

C The smooth manifold structure of Σ * 1

In this section, we prove Theorem 7, which is restated as Theorem 25. Before doing so, we establish intermediary results, some of which are evoked in Section 3.

Let us discuss the cardinal of F θ defined in Section 3. The set F θ is obtained by removing the edges of the form

v → s θ max (v) for v ∈ V 1 ∪ • • • ∪ V L-1
. Note that we do not remove the edges of the form v → s θ max (v) for v ∈ V 0 . For all l ∈ 1, L -1 , there are precisely N l edges of the form (v,

s θ max (v)) with v ∈ V l , so |F θ | = |E| -(N 1 + • • • + N L-1 ) = N 0 N 1 + • • • + N L-1 N L -N 1 -• • • -N L-1 .
As a consequence, since

|B| = N 1 + • • • + N L , we have in particular |F θ | + |B| = N 0 N 1 + • • • + N L-1 N L -N 1 -• • • -N L-1 + N 1 + • • • + N L = N 0 N 1 + • • • + N L-1 N L + N L . (21)
The following proposition is a first step towards Proposition 21, which states that ψ θ is a homeomorphism. Proposition 20. For all θ ∈ R E × R B \S, the function

ψ θ : U θ → R P×V L is injective. Proof. Let τ, τ ∈ U θ such that ψ θ (τ ) = ψ θ (τ ). Let us show τ = τ . We have ϕ(ρ θ (τ )) = ϕ(ρ θ (τ ))
and by definition of U θ , ρ θ (τ ) ∈ R E × R B \S, so by Proposition 18 we have the rescaling equivalence

ρ θ (τ ) R ∼ ρ θ (τ ).
By definition of the rescaling equivalence, in its formulation [START_REF] Brutzkus | Globally optimal gradient descent for a ConvNet with Gaussian inputs[END_REF], there exists (λ 0 , . . . , λ

L ) ∈ (R * ) V0 × • • •×(R * ) V L , with λ 0 = 1 V0 and λ L = 1 V L , such that, for all l ∈ 1, L , for all (v l-1 , v l ) ∈ V l-1 ×V l , ρ θ (τ ) v l-1 →v l = (λ l )v l (λ l-1 )v l-1 ρ θ (τ ) v l-1 →v l b v l = λ l v l bv l . (22)
Let l ∈ 2, L and let

v l-1 ∈ V l-1 . Let v l = s θ max (v l-1
). According to [START_REF] Kůrková | Functionally equivalent feedforward neural networks[END_REF] we have

ρ θ (τ ) v l-1 →v l = (λ l ) v l (λ l-1 ) v l-1 ρ θ (τ ) v l-1 →v l . But since v l = s θ max (v l-1 ) and v l-1 ∈ V l-1 with l -1 ∈ 1, L -1 , we have v l-1 → v l ∈ E\F θ , so by definition of ρ θ in (9), ρ θ (τ ) v l-1 →v l = w v l-1 →v l = ρ θ (τ ) v l-1 →v l ̸ = 0, so (λ l )v l (λ l-1 )v l-1 = 1.
We have shown that for all l ∈ 2, L , for all v l-1 ∈ V l-1 , there exists v l ∈ V l such that

(λ l-1 ) v l-1 = (λ l ) v l . As a consequence, if l is such that λ l = 1 V l , then λ l-1 = 1 V l-1 .
Starting from λ L = 1 V L , this shows by induction that for all l ∈ 1, L ,

λ l = 1 V l .
By hypothesis we also have λ 0 = 1 V0 . Using [START_REF] Kůrková | Functionally equivalent feedforward neural networks[END_REF], this shows that

ρ θ (τ ) = ρ θ (τ ).
The injectivity of ρ θ allows us to conclude that τ = τ .

The following proposition shows, as mentioned in Section 3, that ψ θ is a homeomorphism. This is a necessary step to prove that

(V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is an atlas of Σ * 1 . Proposition 21. For all θ ∈ R E × R B \S, ψ θ is a homeomorphism from U θ onto its image V θ .
Proof. We already know from Proposition 20 that ψ θ is injective, so we need to prove that ψ θ is continuous and its inverse is continuous. The function ρ θ is affine and ϕ is a polynomial function, so the function ψ θ = ϕ • ρ θ is a polynomial function, and in particular it is continuous.

To prove that (ψ θ ) -1 is continuous, we consider a sequence (τ n ) taking values in U θ and τ ∈ U θ such that ψ θ (τ n ) → ψ θ (τ ), and we want to show that τ n → τ .

Let us first show that for all

v ∈ B, (τ n ) v → τ v . Indeed, let l ∈ 1, L and let v l ∈ V l , so that v l is an arbitrary element of B. Let us define v l+1 = s θ max (v l ), then v l+2 = s θ max (v l+1
) and so on up to

v L = s θ max (v L-1 ). Since for all l ′ ∈ l, L -1 , v l ′ +1 = s θ max (v l ′ )
, by definition of F θ and ρ θ (see ( 8) and ( 9)), we have

ρ θ (τ n ) v l ′ →v l ′ +1 = w v l ′ →v l ′ +1 , (23)
and

ρ θ (τ ) v l ′ →v l ′ +1 = w v l ′ →v l ′ +1 . (24)
In particular, since θ ̸ ∈ S, for all l ′ ∈ l, L -1 we have w v l ′ →• ̸ = 0, so by definition of s θ max , w v l ′ →v l ′ +1 ̸ = 0. We thus have

w v l →v l+1 . . . w v L-1 →v L ̸ = 0. (25)
If we denote p = (v l , . . . , v L-1 ), we have, using the definition of ϕ and ( 23), 25) and the fact that

ψ θ p,v L (τ n ) = (τ n ) v l w v l →v l+1 . . . w v L-1 →v L and using (24), ψ θ p,v L (τ ) = (τ ) v l w v l →v l+1 . . . w v L-1 →v L . Using (
ψ θ (τ n ) → ψ θ (τ ),
we conclude that

(τ n ) v l → τ v l .
Let us now prove that for all

(v, v ′ ) ∈ E, (τ n ) v→v ′ → τ v→v ′ .
Let us show by induction on l ∈ 1, L the following hypothesis

∀l ′ ∈ 1, l , ∀(v, v ′ ) ∈ (V l ′ -1 × V l ′ ) ∩ F θ , (τ n ) v→v ′ -→ τ v→v ′ . (H l ) Initialization. Let (v 0 , v 1 ) ∈ (V 0 × V 1 ) ∩ F θ . We define v 2 = s θ max (v 1 ), then we define v 3 = s θ max (v 2 )
, and so on up to v L = s θ max (v L-1 ). Let p = (v 0 , . . . , v L-1 ) ∈ P. As above, using the definition of ρ θ , F θ and ϕ, we have

ψ θ p,v L (τ n ) = (τ n ) v0→v1 w v1→v2 . . . w v L-1 →v L and ψ θ p,v L (τ ) = (τ ) v0→v1 w v1→v2 . . . w v L-1
→v L , and since θ ̸ ∈ S, we also have , as above,

w v1→v2 . . . w v L-1 →v L ̸ = 0. (26)
Since

ψ θ (τ n ) -→ ψ θ (τ )
we conclude using ( 26) that

(τ n ) v0→v1 -→ τ v0→v1 .
We have shown H 1 .

Induction step. Let l ∈ 2, L and let us assume that H l-1 holds.

Let (v l-1 , v l ) ∈ (V l-1 × V l ) ∩ F θ . We define v l+1 = s θ max (v l ), v l+2 = s θ max (v l+1
), and so on up to v L = s θ max (v L-1 ). Let us denote p o = (v l , . . . , v L ). Recalling the notation defined in [START_REF] Kalchbrenner | Recurrent continuous translation models[END_REF], we have

ρ θ (τ n ) po = w v l →v l+1 . . . w v L-1 →v L = ρ θ (τ ) po ̸ = 0. (27)
At the same time, since τ ∈ U θ , Proposition 15 shows there exist l ′ ∈ 0, l -1 and a path

p i = (v l ′ , . . . , v l-2 , v l-1 ) such that ρ θ (τ ) pi ̸ = 0. ( 28
) If l ′ ≥ 1, we have shown in the first part of the proof that (τ n ) v l ′ -→ τ v l ′ . Moreover, whatever the value of l ′ is, for k ∈ l ′ , l -2 , if (v k , v k+1 ) ∈ E\F θ , ρ θ (τ n ) v k →v k+1 = w v k →v k+1 = ρ θ (τ ) v k →v k+1 , and if (v k , v k+1 ) ∈ F θ , according to H l-1 , ρ θ (τ n ) v k →v k+1 = (τ n ) v k →v k+1 -→ τ v k →v k+1 = ρ θ (τ ) v k →v k+1 . We therefore have ρ θ (τ n ) pi -→ ρ θ (τ ) pi , (29)
and in particular, since ρ θ (τ ) pi ̸ = 0, there exists n 0 ∈ N such that for all n ≥ n 0 ,

ρ θ (τ n ) pi ̸ = 0. (30)
We can write 27), ( 30) and ( 29), we have

ψ θ p,v L (τ n ) = ρ θ (τ n ) pi (τ n ) v l-1 →v l ρ θ (τ n ) po and ψ θ p,v L (τ ) = ρ θ (τ ) pi (τ ) v l-1 →v l ρ θ (τ ) po , so using (
(τ n ) v l-1 →v l = ψ θ p,v L (τ n ) ρ θ (τ n ) pi ρ θ (τ n ) po -→ ψ θ p,v L (τ ) ρ θ (τ ) pi ρ θ (τ ) po = τ v l-1 →v l .
We have shown H l , which concludes the induction step.

In particular, H L is satisfied, and finally τ n → τ .

This shows that ψ θ is a homeomophism.

The following lemma is necessary for the proof of Proposition 23.

Lemma 22. Let θ ∈ R E × R B \S. Let (v, v ′ ) ∈ E (resp. v ∈ B). If w v→v ′ ̸ = 0 (resp. b v ̸ = 0), then there exists ϵ > 0 such that for all θ ∈ R E × R B , if ∥ϕ(θ) -ϕ( θ)∥ ∞ < ϵ, then wv→v ′ ̸ = 0 (resp. bv ̸ = 0). Proof. Let θ ∈ R E × R B \S and (v, v ′ ) ∈ E such that w v→v ′ ̸ = 0. Denote l ∈ 0, L -1 such that v ∈ V l .
If l = 0, we take p i = (v) so that by convention θ pi = 1 ̸ = 0, and if l ≥ 1, we use Proposition 15 which states that there exists l ′ ∈ 0, l -1 and a path p i = (v l ′ , . . . , v l-2 , v) such that θ pi ̸ = 0. Similarly, if l = L -1, we take p o = (v ′ ) so that by convention θ po = 1 ̸ = 0 and if l < L -1, we use Proposition 15 which states that there exists a path

p o = (v ′ , v l+1 , . . . , v L ) such that θ po ̸ = 0. If we denote p =    (v, v ′ , v l+2 , . . . , v L-1 ) if l = 0 (v l ′ , . . . , v l-1 , v, v ′ ) if l = L -1 (v l ′ , . . . , v l-1 , v, v ′ , v l+2 , . . . , v L-1 ) otherwise, we have ϕ p,v L (θ) = θ pi w v→v ′ θ po ̸ = 0. We define ϵ = |ϕ p,v L (θ)| > 0. For all θ ∈ R E × R B such that ∥ϕ( θ) -ϕ(θ)∥ ∞ < ϵ we have ϕ p,v L ( θ) ̸ = 0.
Since ϕ p,v L ( θ) = θpi wv→v ′ θpo , this implies in particular that

wv→v ′ ̸ = 0.
The proof is similar in the case v ∈ B and b v ̸ = 0.

The following proposition, which states that for any

θ ∈ R E × R B \S, V θ = ψ θ (U θ
) is open with respect to the topology induced on Σ * 1 by the standard topology of R P×V L , is necessary to show that (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is an atlas of Σ * 1 . Proposition 23. For any θ ∈ R E × R B \S, for any τ ∈ U θ , there exists ϵ > 0 such that

Σ * 1 ∩ B ∞ (ψ θ (τ ), ϵ) ⊂ V θ .
Proof. Let us first construct ϵ and then consider an element of the set on the left of the inclusion and prove it belongs to V θ . Let θ ∈ R E × R B \S and τ ∈ U θ . For all l ∈ 1, L -1 , for all v ∈ V l , by definition of F θ and ρ θ , we have ρ θ (τ ) v→s θ max (v) = w v→s θ max (v) , and since θ ̸ ∈ S, by definition of s θ max , w v→s θ max (v) ̸ = 0, so according to Lemma 22 there exists ϵ v > 0 such that for all θ

∈ R E × R B , ∥ϕ(ρ θ (τ )) -ϕ( θ)∥ ∞ < ϵ v =⇒ wv→s θ max (v) ̸ = 0. Let ϵ = min v∈V1∪•••∪V L-1 ϵ v .
Let us now show the inclusion: let θ ∈ R E × R B \S such that ∥ϕ(ρ θ (τ ))ϕ( θ)∥ ∞ < ϵ, and let us show that ϕ( θ) ∈ V θ . Notice first that for all l ∈ 1, L -1 and v ∈ V l , by definition of ϵ, w v→s θ max (v) ̸ = 0 and wv→s θ max (v) ̸ = 0. We are going to define τ ∈ U θ such that ρ θ (τ ) R ∼ θ, so that using Proposition 16, ψ θ (τ ) = ϕ( θ).

Let us define recursively a family (λ 0 , . . . , λ

L ) ∈ (R * ) V0 × • • • × (R * ) V L as follows:
• we define λ L = 1 V L ;

• for all l ∈ 1, L -1 , for all v ∈ V l , we define

λ l v = wv→s θ max (v) w v→s θ max (v) λ l+1 s θ max (v) . (31)
• we define finally λ 0 = 1 V0 .

Note that for all l ∈ 0, L and for all v ∈ V l , λ l v ̸ = 0. Also note that for all l ∈ 2, L , for all v ∈ V l-1 , reformulating [START_REF] Phuong | Functional vs. parametric equivalence of ReLU networks[END_REF] in a way that will be useful later, we have

λ l s θ max (v) λ l-1 v = w v→s θ max (v) wv→s θ max (v) . (32)
We then define τ ∈ R F θ × R B by:

• for all l ∈ 1, L , for all

(v, v ′ ) ∈ (V l-1 × V l ) ∩ F θ , τv→v ′ = λ l v ′ λ l-1 v wv→v ′ ; (33)
• for all l ∈ 1, L , for all v ∈ V l , τv = λ l v bv .

Let us show ρ θ (τ )

R ∼ θ. Indeed, let l ∈ 1, L and let (v, v ′ ) ∈ V l-1 × V l . If v ∈ V 0 or v ∈ V 1 ∪ • • • ∪ V L-1 and v ′ ̸ = s θ max (v)
, then by definition (8) of F θ , we have v → v ′ ∈ F θ , so using ( 9) and [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF] we have

ρ θ (τ ) v→v ′ = τv→v ′ = λ l v ′ λ l-1 v wv→v ′ . ( 35
) If v ∈ V 1 ∪ • • • ∪ V L-1 and v ′ = s θ max (v)
, then by definition (8) of F θ , we have v → v ′ ∈ E\F θ , and since in that case, l ≥ 2, using ( 9) and (32), we see that

ρ θ (τ ) v→v ′ = w v→v ′ = λ l v ′ λ l-1 v wv→v ′ . (36)
If v ∈ B, using ( 9) and (34), we have

ρ θ (τ ) v = τv = λ l v bv . (37)
Equations ( 35), [START_REF] Sak | Long short-term memory recurrent neural network architectures for large scale acoustic modeling[END_REF] and [START_REF] Sedghi | Provable methods for training neural networks with sparse connectivity[END_REF] prove that

ρ θ (τ ) R ∼ θ. Using Corollary 17, since θ ∈ R E × R B \S and ρ θ (τ ) R ∼ θ, we also have ρ θ (τ ) ∈ R E × R B \S. Since, by definition, U θ = ρ -1 θ R E × R B \S , we have τ ∈ U θ . We have shown Σ * 1 ∩ B ∞ (ψ θ (τ ), ϵ) ⊂ V θ .
The following proposition is necessary in order to show that (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is an atlas of Σ * 1 . Proposition 24. For all θ ∈ R E × R B \S, the function ψ θ is C ∞ and its differential Dψ θ (τ ) is injective for all τ ∈ U θ .

Proof. Let θ ∈ R E × R B \S. First of all, ψ θ is a polynomial function as a composition of ϕ and ρ θ which are both polynomial functions. So, ψ θ is C ∞ .

In order to show the injectivity of the differential Dψ θ (τ ) for all τ ∈ U θ , let us compute the partial derivatives of ψ θ p,v L (τ ). Let p ∈ P and v L ∈ V L . Using the definition of ψ θ and ϕ, three cases are possible.

Case 1. The path p is of the form (v 0 , v 1 , . . . , v L-1 ). We have

ψ θ p,v L (τ ) = ρ θ (τ ) v0→v1 . . . ρ θ (τ ) v L-1 →v L .
Case 2. The path p is of the form (v l , . . . , v L-1 ) with l ∈ 1, L -1 . We have, for all τ ∈ U θ ,

ψ θ p,v L (τ ) = τ v l ρ θ (τ ) v l →v l+1 . . . ρ θ (τ ) v L-1 →v L .
Case 3. For p = β, we have, for all τ ∈ U θ ,

ψ θ p,v L (τ ) = τ v L .
Let (v, v ′ ) ∈ F θ , and let us compute

∂ψ θ p,v L
∂τ v→v ′ (τ ).

Case 1. We have p = (v 0 , . . . , v L-1 ) ∈ P 0 . If {v, v ′ } ⊂ {v 0 , . . . , v L }, there exists l ∈ 0, L -

1 such that (v, v ′ ) = (v l , v l+1 ), in which case, since (v, v ′ ) ∈ F θ , ρ θ (τ ) v l →v l+1 = τ v l →v l+1 and ∂ψ θ p,v L ∂τ v→v ′ (τ ) = k∈ 0,L-1 k̸ =l ρ θ (τ ) v k →v k+1 . ( 38
) Otherwise if {v, v ′ } ̸ ⊂ {v 0 , . . . , v L }, ∂ψ θ p,v L ∂τ v→v ′ (τ ) = 0. Case 2. We have p = (v l , . . . , v L-1 ) ∈ P l , for l ∈ 1, L -1 . If {v, v ′ } ⊂ {v l , . . . , v L }, there exists l ′ ∈ l, L -1 such that (v, v ′ ) = (v l ′ , v l ′ +1 ), in which case, since (v, v ′ ) ∈ F θ , ρ θ (τ ) v l ′ →v l ′ +1 = τ v l ′ →v l ′ +1 and ∂ψ θ p,v L ∂τ v→v ′ (τ ) = τ v l k∈ l,L-1 k̸ =l ′ ρ θ (τ ) v k →v k+1 . (39)
Otherwise if {v, v ′ } ̸ ⊂ {v l , . . . , v L },

∂ψ θ p,v L ∂τ v→v ′ (τ ) = 0.
Case 3. We have p = β. In that case, we have

∂ψ θ p,v L ∂τ v→v ′ (τ ) = 0.
Now let v ∈ B, and let us compute

∂ψ θ p,v L ∂τv (τ ).
Case 1. We have p = (v 0 , . . . , v L-1 ) ∈ P 0 and

∂ψ θ p,v L ∂τ v (τ ) = 0.
Case 2. We have p = (v l , . . . , v L-1

) ∈ P l for l ∈ 1, L -1 . If v = v l , then ∂ψ θ p,v L ∂τ v (τ ) = k∈ l,L-1 ρ θ (τ ) v k →v k+1 . If v ̸ = v l , ∂ψ θ p,v L ∂τ v (τ ) = 0.
Case 3. We have p = β and

∂ψ θ p,v L ∂τ v (τ ) = ® 1 if v = v L 0 if v ̸ = v L .

Now that we know the partial derivatives, let us show

Dψ θ (τ ) is injective for all τ ∈ U θ . Let τ ∈ U θ and let h ∈ R F θ × R B such that Dψ θ (τ ) • h = 0.
We need to prove that h = 0.

Let us show first that for all v ∈ B, h v = 0. Let l ∈ 1, L -1 , and let v l ∈ V l so that v l is arbitrary in B\V L . Let us define v l+1 = s θ max (v l ), then v l+2 = s θ max (v l+1 ), and so on up to v L = s θ max (v L-1 ). Let us denote p = (v l , . . . , v L-1 ). We have

ψ θ p,v L (τ ) = τ v l w v l →v l+1 . . . w v L-1 →v L , so Dψ θ (τ ) • h p,v L = ∂ψ θ p,v L ∂τ v l (τ )h v l = w v l →v l+1 . . . w v L-1 →v L h v l . Since Dψ θ (τ ) • h p,v L = 0 and w v l →v l+1 . . . w v L-1 →v L ̸ = 0, we conclude that h v l = 0. Now let v L ∈ V L .
We consider p = β and we have

Dψ θ (τ ) • h p,v L = h v L .
Since Dψ θ (τ ) • h p,v L = 0, we also conclude in that case that h v L = 0.

Let us now show that for all

(v, v ′ ) ∈ F θ , h v→v ′ = 0. Let l ∈ 1, L and let (v l-1 , v l ) ∈ (V l-1 × V l ) ∩ F θ so that (v l-1 , v l ) is arbitrary in F θ . If l = 1, we define p i = (v l-1
) and we have by convention θ pi = 1 ̸ = 0. If l > 1, using Proposition 15 there exist l ′ ∈ 0, l -1 and a path p i = (v l ′ , . . . , v l-1 ) such that ρ θ (τ ) pi ̸ = 0. If l < L, we define v l+1 = s θ max (v l ), then v l+2 = s θ max (v l+1 ), and so on up to v L = s θ max (v L-1 ), and we denote p = p i ∪ (v l-1 , v l , . . . , v L-1 ). If l = L, we denote p = p i . Let us show the following expression.

Dψ θ (τ ) • h p,v L = k∈ l ′ ,l-1 (v k ,v k+1 )∈F θ ∂ψ θ p,v L ∂τ v k →v k+1 (τ )h v k →v k+1 (40)
Indeed, if l ′ ≥ 1, we have

ψ θ p,v L (τ ) = τ v l ′ l-1 k=l ′ ρ θ (τ ) v k →v k+1 L-1 k=l w v k →v k+1 ,
with the classical convention that if l = L, the product on the right is empty thus equal to 1. We thus have

Dψ θ (τ ) • h p,v L = ∂ψ θ p,v L ∂τ v l ′ (τ )h v l ′ + k∈ l ′ ,l-1 (v k ,v k+1 )∈F θ ∂ψ θ p,v L ∂τ v k →v k+1 (τ )h v k →v k+1 = k∈ l ′ ,l-1 (v k ,v k+1 )∈F θ ∂ψ θ p,v L ∂τ v k →v k+1 (τ )h v k →v k+1 ,
since we have already shown that h v l ′ = 0.

If l ′ = 0, we have

ψ θ p,v L (τ ) = l-1 k=0 ρ θ (τ ) v k →v k+1 L-1 k=l w v k →v k+1 ,
with the same convention that when l = L the product on the right is equal to 1, so again

Dψ θ (τ ) • h p,v L = k∈ 0,l-1 (v k ,v k+1 )∈F θ ∂ψ θ p,v L ∂τ v k →v k+1 (τ )h v k →v k+1 .
This concludes the proof of [START_REF] Héctor | Uniqueness of the weights for minimal feedforward nets with a given input-output map[END_REF].

We can now show by induction the following statement, for l ∈ 0, L .

∀l ′ ∈ 1, l , ∀(v, v ′ ) ∈ (V l ′ -1 × V l ′ ) ∩ F θ , h v→v ′ = 0. (H l )
Since 1, 0 = ∅, H 0 is trivially true. Now let l ∈ 1, L and suppose H l-1 is true. We consider (v l-1 , v l ) ∈ (V l-1 × V l ) ∩ F θ , and l ′ ∈ 0, l , p i and p just as before. Since for all k ∈ 0, l -2 , the induction hypothesis guarantees that h v k →v k+1 = 0, (40) becomes

Dψ θ (τ ) • h p,v L = ∂ψ θ p,v L ∂τ v l-1 →v l (τ )h v l-1 →v l .
Using [START_REF] Stock | Efficiency and Redundancy in Deep Learning Models : Theoretical Considerations and Practical Applications[END_REF] and [START_REF] Stock | An Embedding of ReLU Networks and an Analysis of their Identifiability[END_REF], we obtain

Dψ θ (τ ) • h p,v L = ® ρ θ (τ ) pi w v l →v l+1 . . . w v L-1 →v L h v l-1 →v l if l < L ρ θ (τ ) pi h v l-1 →v l if l = L.
Since ρ θ (τ ) pi ̸ = 0, and for l < L, w v l →v l+1 . . . w v L-1 →v L ̸ = 0, we conclude that h v l-1 →v l = 0 and that H l holds.

This induction leads to the conclusion that h = 0 and Dψ θ (τ ) is injective.

We are now equipped to prove Theorem 7, which we restate here.

Theorem 25. Σ 1 * is a smooth manifold of R P×V L of dimension |F θ | + |B| = N 0 N 1 + N 1 N 2 + • • • + N L-1 N L + N L ,
and the family (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is an atlas.

Proof. Our goal is to show that the family (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is a smooth atlas, which will show that Σ * 1 is a smooth manifold. We already know from Proposition 23 that for any θ ∈ R E × R B \S, V θ is an open subset of Σ * 1 and from Proposition 21 that (ψ θ ) -1 is a homeomorphism from V θ onto U θ . Since for any Figure 3: The points η 0 , τ 0 , τ 1 and the inverse charts ψ θ and ψ θ .

θ ∈ R E × R B \S, τ θ ∈ U θ , we have ϕ(θ) = ψ θ (τ θ ) ∈ V θ which shows that (V θ ) θ∈(R E ×R B )\S covers Σ * 1 . Let θ, θ ∈ R E × R B \S, let us show that the transition map (ψ θ ) -1 • ψ θ : (ψ θ ) -1 (V θ ∩ V θ ) → (ψ θ ) -1 (V θ ∩ V θ ) is smooth. Let τ 0 ∈ U θ such that τ 0 ∈ (ψ θ ) -1 (V θ ∩ V θ ).
We are going to show that the function

(ψ θ ) -1 • ψ θ is C ∞ in a neighborhood of τ 0 .
For ease of reading, let us denote ψ θ (τ 0 ) by η 0 . By definition, η 0 ∈ V θ ∩ V θ . In particular, since η 0 ∈ V θ , we can define τ 1 = (ψ θ ) -1 (η 0 ). See Figure 3

θ : U θ × R N C -→ R P×V L (τ, x) -→ ψ θ (τ ) + i(x).
We are going to show that there exist an open neighborhood Ũ of (τ

1 , 0) in (R F θ × R B ) × R N C and an open neighborhood Ṽ of η 0 in R P×V L such that φ θ is a C ∞ diffeomorphism from Ũ onto Ṽ satisfying φ θ Å (R F θ × R B ) × {0} N C ∩ Ũ ã = Σ * 1 ∩ Ṽ . Let us first show that φ θ is a C ∞ -diffeomorphism from a neighborhood of (τ 1 , 0) in (R F θ × R B ) × R N C onto a neighborhood of η 0 in R P×V L . As shown in Proposition 24, ψ θ is C ∞ and i is a linear function, so φ θ is C ∞ . Let us prove that the differential Dφ θ (τ 1 , 0) is injective. For all (τ, x) ∈ R F θ × R B × R N C , Dφ θ (τ 1 , 0) • (τ, x) = Dψ θ (τ 1 ) • τ + i(x). Since Dψ θ (τ 1 ) • τ ∈ T , i(x) ∈ G, and T and G are in direct sum, if Dφ θ (τ 1 , 0) • (τ, g) = 0, then we have ® Dψ θ (τ 1 ) • τ = 0 i(x) = 0.
Since as shown in Proposition 24 Dψ θ (τ 1 ) is injective, and since i is invertible, we have (τ, x) = (0, 0).

Hence, Dφ

θ (τ 1 , 0) is injective. Since dim( R F θ × R B × R N C ) = |F θ | + |B| + N C = |P|N L , the differential Dφ θ (τ 1 , 0) is bijective. Using the inverse function theorem, there exists an open set U ⊂ U θ × R N C containing (τ 1 , 0), an open set V ⊂ R P×V L containing η 0 such that φ θ is a C ∞ -diffeomorphism from U onto V . We have φ θ Å (R F θ × R B ) × {0} N C ∩ U ã ⊂ V θ ∩ V.
In fact, if V is small enough, this inclusion is an equality. We are going to construct open subsets Ũ ⊂ U and Ṽ ⊂ V so that it is the case. Let us define

O = {τ ∈ U θ , (τ, 0) ∈ U }. Since U is an open set containing (τ 1 , 0), O is an open set containing τ 1 = (ψ θ ) -1 (η 0 ). Since, according to Proposition 21, ψ θ is a homeomorphism, ψ θ (O) is an open subset of V θ so there exists ϵ > 0 such that V θ ∩ B ∞ (η 0 , ϵ) ⊂ ψ θ (O). (41)
We can now define Ṽ = V ∩ B ∞ (η 0 , ϵ), and

Ũ = {(τ, x) ∈ U, φ θ (τ, x) ∈ Ṽ }, which are open sets such that (τ 1 , 0) ∈ Ũ , η 0 ∈ Ṽ , and φ θ is a C ∞ -diffeomorphism from Ũ onto Ṽ . Let us show that φ θ Å (R F θ × R B ) × {0} N C ∩ Ũ ã = V θ ∩ Ṽ . (42)
The direct inclusion is immediate: Let us now define

if (τ, 0) ∈ (R F θ × R B ) × {0} N C ∩ Ũ , then φ θ (τ, 0) = ψ θ (τ ) ∈ V θ ∩ Ṽ . For the reciprocal inclusion, if τ ∈ U θ is such that ψ θ (τ ) ∈ V θ ∩ Ṽ ,
P θ : R F θ × R B × R N C -→ R F θ × R B (τ, x) -→ τ
the restriction to the first component, and let us observe that over V θ ∩ Ṽ , we have

P θ • (φ θ ) -1 = (ψ θ ) -1 . (43)
Indeed, if η ∈ V θ ∩ Ṽ , then by [START_REF] Zhang | Protecting intellectual property of deep neural networks with watermarking[END_REF] there exists τ ∈ U θ such that (τ, 0) ∈ Ũ and φ θ (τ, 0) = η. Since φ θ (τ, 0) = ψ θ (τ ), this shows that τ = (ψ θ ) -1 (η) and thus

(ψ θ ) -1 (η) = P θ (τ, 0) = P θ • (φ θ ) -1 (η). Now recall that η 0 = ψ θ (τ 0 ). By continuity of ψ θ , there exists ϵ ′ > 0 such that B ∞ (τ 0 , ϵ ′ ) ⊂ (ψ θ ) -1 (V θ ∩ V θ ) and ψ θ (B ∞ (τ 0 , ϵ ′ )) ⊂ Ṽ .
For any τ ∈ B ∞ (τ 0 , ϵ ′ ), we have ψ θ (τ ) ∈ V θ ∩ Ṽ so, as we just proved with [START_REF] Zhang | Improved linear convergence of training CNNs with generalizability guarantees: A one-hidden-layer case[END_REF],

(ψ θ ) -1 • ψ θ (τ ) = P θ • (φ θ ) -1 • ψ θ (τ ).
Since the functions ψ θ , (φ θ ) -1 and P θ are all C ∞ , we conclude that the transition map (ψ θ ) -1 • ψ θ is C ∞ over B ∞ (τ 0 , ϵ ′ ), for all τ 0 ∈ (ψ θ ) -1 (V θ ∩ V θ ). We conclude that

(ψ θ ) -1 • ψ θ is C ∞ over (ψ θ ) -1 (V θ ∩ V θ ).
We have showed that (V θ , (ψ θ ) -1 ) θ∈(R E ×R B )\S is a smooth atlas, and thus that Σ * 1 is a smooth submanifold of R P×V L . As computed in [START_REF] Kurakin | Adversarial examples in the physical world[END_REF], its dimension is

|F θ | + |B| = N 0 N 1 + N 1 N 2 + • • • + N L-1 N L + N L .
More precisely, we suppose that for all n ∈ N * , there exists ϕ n ∈ N (X, θ) ∩ Σ * 1 such that ϕ n ̸ = ϕ(θ) and ∥ϕ(θ)ϕ n ∥ ∞ < 1 n and prove that it leads to T ∩ Ker A(X, θ) ̸ = {0}, which contradicts (56). Using Proposition 23, there exists n 0 ∈ N * such that for all n ≥ n 0 , there exists τ n ∈ U θ such that ϕ n = ψ θ (τ n ). Since ψ θ is a homeomorphism and ψ θ (τ θ ) = ϕ(θ), ϕ n → ϕ(θ) implies that τ n → τ θ .

Moreover, for all n ≥ n 0 , τ n ̸ = τ θ .

When n tends to infinity, we can thus write

ϕ n -ϕ(θ) = ψ θ (τ n ) -ψ θ (τ θ ) = Dψ θ (τ θ ) • (τ n -τ θ ) + o(τ n -τ θ ).
Let us apply A(X, θ) and divide by ∥τ nτ θ ∥.

1 ∥τ n -τ θ ∥ A(X, θ)•(ϕ n -ϕ(θ)) = A(X, θ)•Dψ θ (τ θ )• Å τ n -τ θ ∥τ n -τ θ ∥ ã + 1 ∥τ n -τ θ ∥
A(X, θ)o (τ nτ θ ) .

(58) Since ϕ n ∈ N (X, θ) for all n ∈ N * ,

1 ∥τ n -τ θ ∥ A(X, θ) • (ϕ n -ϕ(θ)) = 0.
Since τn-τ θ ∥τn-τ θ ∥ belongs to the unit sphere, we can extract a subsequence that converges to a limit h with norm equal to 1. Taking the limit in (58) according to this subsequence, we obtain 0 = A(X, θ) • Dψ θ (τ θ ) • h, which shows that Dψ θ (τ θ ) • h ∈ Ker A(X, θ). Since h ̸ = 0 and Dψ θ (τ θ ) is injective, Dψ θ (τ θ )h ̸ = 0 and T ∩ Ker A(X, θ) ̸ = {0}.

This is in contradiction with (56).

We have proven (57). We can now conclude thanks to Lemma 26: there exists ϵ ′ > 0 such that for any θ ∈ R E × R B , if ∥θ -θ∥ < ϵ ′ , then f θ (X) = f θ (X) =⇒ θ ∼ θ.

E Checking the conditions numerically

We restate and prove Proposition 12. Proposition 31. Let X ∈ R n×V0 and θ ∈ R E × R B . We have

R A = N L rank (α(X, θ)) .
Proof. Let η ∈ R P×V L . We have A(X, θ) • η = α(X, θ)η.

If we denote by η 1 , . . . , η N L ∈ R P the N L columns of η, the columns of A(X, θ) • η are α(X, θ)η 1 , . . . , α(X, θ)η N L . If we consider the matrix η as a family of N L vectors of R P and the matrix A(X, θ) • η as a family of N L vectors of R n , the operator A(X, θ) can then be equivalently described as A(X, θ) : (R P ) N L -→ (R n ) N L (η 1 , . . . , η N L ) -→ (α(X, θ)η 1 , . . . , α(X, θ)η N L ).

The rank of such an operator is N L rank(α(X, θ)).

Proof. Let (i, v L ) ∈ 1, n × V L .

Let us compute γ i,v L v l →v l+1 , for l ∈ 0, L -1 and (v l , v l+1 ) ∈ V l × V l+1 such that v l → v l+1 ∈ F θ . γ i,v L v l →v l+1 is the coefficient corresponding to the line (i, v L ) and the column (v l → v l+1 ) of Γ(X, θ). Let us denote by h v l →v l+1 ∈ R F θ × R B the vector whose component indexed by v l → v l+1 is equal to 1 and whose other components are zero. Let us denote by d i,v L ∈ R n×V L the element whose component indexed by (i, v L ) is equal to 1 and whose other components are zero. Let us denote by ⟨•, •⟩ R n×V L the scalar product of the euclidean space R n×V L . We have (τ θ ). Let us remind the dimensions in this product. For the left factor, recalling the definition given in the beginning of Section D, we have α(X, θ) ∈ R n×P . Concerning the right factor, since for any τ ∈ U θ , we have ψ θ (τ ) ∈ R P×V L , the partial derivative satisfies ∂ψ θ ∂τv l →v l+1 (τ θ ) ∈ R P×V L . Hence, the dimension of the product is α(X, θ) ∂ψ θ ∂τ v l →v l+1 (τ θ ) ∈ R n×V L .

γ i,v L v l →v l+1 = d i,v L , Γ(X, θ) • h v l →v l+1 R n×V L = d i,v L , A(X, θ) • Dψ θ (τ θ ) • h v l →v l+1 R n×V L = AE d i,v L , A(X, θ) • ∂ψ θ ∂τ v l →v l+1 (τ θ ) ∏ R n×V L = AE d i,v L ,
To obtain the coefficient (i, v L ) of this product, we keep the i th line of the left factor, which is equal to α(x i , θ), and the column v L of the right factor, which is equal to Recalling the definition of α p (x i , θ) in the case p ∈ P 0 , given in (2), we also have Recalling the definition of α p (x i , θ) in the case p ∈ P l ′ , given in (2), we also have which can be reformulated, getting rid of the zero sums when v l → v l+1 ̸ ∈ p, as

α p (x i , θ) = x i v0 L-1 k=1 a v k (x i , θ),
α p (x i , θ) = L-1 k=l ′ a v k (x i , θ),
γ i,v L v l+1 →v l = v0∈V0 . . . v l-1 ∈V l-1 v l+2 ∈V l+2 . . . v L-1 ∈V L-1
x i v0 w v0→v1 a v l (x i , θ)

k∈ 1,L-1 k̸ =l a v k (x i , θ)w v k →v k+1 + L l ′ =1 v l ′ ∈V l ′ . . . v l-1 ∈V l-1 v l+2 ∈V l+2 . . . v L-1 ∈V L-1 a v l (x i , θ)b v ′ l k∈ l ′ ,L-1 k̸ =l a v k (x i , θ)w v k →v k+1 ,
which shows (60).

The proof of (61) is similar to the one of (60).

Figure 2 :

 2 Figure2: Left: The outward edges of a hidden neuron v and their weights. In this example, v 1 = s θ max (v), so the weight of the edge in red, v → v 1 , has its value fixed as w v→v1 . The weights of the remaining edges, τ v→v2 and τ v→v3 , are free to vary. Right: In red, all the edges whose weights are fixed. The remaining edges, in black, constitute the set F θ .

Checklist 1 .

 1 For all authors... (a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The outline in Section 1.4 ("Overview of the article") provides pointers to where the claimed contributions of the paper are provided. (b) Did you describe the limitations of your work? [Yes] Section 5 acknowledges the open problem of an efficient computation of the rank of α(X, θ) and Section 6 describes other remaining open questions. (c) Did you discuss any potential negative societal impacts of your work? [N/A] This is a theoretical/foundation work that adds to the theory and methodology of deep learning.

  (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] See previous question. 2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] All our results explicitly refer to their required assumptions. Some general assumptions that hold throughout the paper are also stated at the beginning. (b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are provided in the supplement. 3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] We did not run experiments. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a) If your work uses existing assets, did you cite the creators? [N/A] We did not use existing assets (code, data or models) nor cure/release new assets (code, data or models). (b) Did you mention the license of the assets? [N/A] (c) Did you include any new assets either in the supplemental material or as a URL? [N/A] (d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] 5. If you used crowdsourcing or conducted research with human subjects... (a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use crowdsourcing nor conducted research with human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

  for a representation. Let T = Im Dψ θ (τ 1 ), and let us consider a linear subspace G such that T ⊕ G = R P×V L . Let N C = |P|N L -|F θ | -|B| = dim(G). Let i : R N C → G be linear and invertible. Let us consider the function φ

  then by definition of ϵ and Ṽ , (41) guarantees, since ψ θ is injective, that τ ∈ O. By definition of O, we have (τ, 0) ∈ U , and since φ θ (τ, 0) = ψ θ (τ ) ∈ Ṽ , this shows (τ, 0) ∈ Ũ . This shows the reciprocal inclusion, and thus (42) holds.

  l+1(τ θ ). We thus haveñ α(X, θ) ∂ψ θ ∂τ v l →v l+1 (τ θ ) ô i,v L = α(x i , θ) ∂ψ θ v L ∂τ v l →v l+1 (τ θ ) = p∈P α p (x i , θ) ∂ψ θ p,v L ∂τ v l →v l+1 (τ θ ).Let p ∈ P. If p = (v 0 , . . . , v L ) ∈ P 0 , looking at the case 1 in the proof of Proposition 24, we have∂ψ θ p,v L ∂τ v l →v l+1 (τ θ ) = 1 {v l →v l+1 ∈p} k∈ 0,L-1 k̸ =l w v k →v k+1 .

- 1 k=1a

 1 ∂τ v l →v l+1 (τ θ ) = 1 {v l →v l+1 ∈p} x i v0 Lv k (x i , θ) k∈ 0,L-1 k̸ =l w v k →v k+1 .(62)Now if p = (v l ′ , . . . , v L ) ∈ P l ′ , for l ′ ∈ 1, . . . , L -1}, looking at the case 2 in the proof of Proposition 24, we have∂ψ θ p,v L ∂τ v l →v l+1 (τ θ ) = 1 {v l →v l+1 ∈p} b v l ′ k∈ l ′ ,L-1 k̸ =l w v k →v k+1 .

  ∂τ v l →v l+1 (τ θ ) = 1 {v l →v l+1 ∈p} b v l ′ L-1 k=l ′ a v k (x i , θ) k∈ l ′ ,L-1 k̸ =l w v k →v k+1 .(63)Finally, if p = β, looking at the case 3 in the proof of Proposition 24, we have∂ψ θ p,v L ∂τ v l →v l+1 (τ θ ) = 0,and thusα p (x i , θ) ∂ψ θ p,v L ∂τ v l →v l+1 (τ θ ) = 0.(64)Assembling (62), (63) and (64), we can sum over all p ∈ P, and obtainγ i,v L v l+1 →v l = p∈P0 p=(v0,...,v L-1 ) 1 {v l →v l+1 ∈p} x i v0 L-1 k=1 a v k (x i , θ) k∈ 0,L-1 k̸ =l w v k →v k+1 + L l ′ =1 p∈P l ′ p=(v l ′ ,...,v L-1 ) 1 {v l →v l+1 ∈p} b v l ′ L-1 k=l ′ a v k (x i , θ) k∈ l ′ ,L-1 k̸ =l w v k →v k+1

  is both necessary and sufficient. Finally, to satisfy R Γ = |F θ | + |B|, the dimensions must satisfy nN L ≥ |F θ | + |B|. The general belief is that the latter is the condition of identifiability since nN L is the number of scalar measurements and |F θ | + |B| is the number of independent free parameters, see Theorem 7.

Note, in the definition of F θ , the index l starting at l = 1 and not l = 0.

https://www.deel.ai/

Acknowledgments and Disclosure of Funding

The authors would like to thank Pierre Stock and Rémi Gribonval for the fruitful discussions around this work, notably regarding the construction of ϕ and its link to the question of local identifiability. This work has benefited from the AI Interdisciplinary Institute ANITI. ANITI is funded by the French "Investing for the Future -PIA3" program under the Grant agreement n°ANR-19-PI3A-0004.

The authors gratefully acknowledge the support of the DEEL project. 2

Corollary 17. The set R E × R B \S is stable by rescaling equivalence: if θ ∈ R E × R B \S, Proposition 16 shows that ϕ( θ) = ϕ(θ).

Let l ∈ 1, L and v ∈ V l . Since θ ∈ R E × R B \S, according to Proposition 15 there exists l ′ ∈ 0, l , a path p = (v l ′ , . . . , v l , . . . , v L-1 ) and v L ∈ V L such that ϕ p,v L (θ) ̸ = 0. We have ϕ p,v L ( θ) = ϕ p,v L (θ) ̸ = 0, and since this is true for any l ∈ 1, L and v ∈ V l , Proposition 15 shows that θ ∈ R E × R B \S.

We restate and prove Proposition 5.

Proof. Let us choose (λ 0 , . . . , λ L ) ∈ (R * ) V0 × • • • × (R * ) V L as follows. For all l ∈ 1, L -1 and all v l ∈ V l , since θ ∈ R E × R B \S, Proposition 15 shows that there exists a path

The value of λ l v l a priori depends on the choice of the path p o (v l ), but the first of the two following facts, that we are going to prove, shows it only depends on v l , since in [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], p i does not depend on p o (v l ).

• For all l ∈ 0, L , for all v l ∈ V l , for any l ′ ∈ 0, l and any

• For all l ∈ 0, L , for all v l ∈ V l , λ l v l ̸ = 0.

Indeed, let l ∈ 0, L and let us consider l ′ ∈ 0, l and a path

We have by hypothesis

which proves the first point. To prove the second point, we simply use Proposition 15 to consider a path p i such that θ pi ̸ = 0, and [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] shows that λ l v l ̸ = 0. Let us now prove the rescaling equivalence. Let l ∈ 1, L , and let (v l-1 , v l ) ∈ V l-1 × V l . Let us consider, thanks to Proposition 15, l ′ ∈ 0, l -1 and a path [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] shows we also have θpi

At the same time, using [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] with θ pi we have,

D Conditions of local identifiability

Let us restate (using Definition 6) and prove Theorem 8.

Theorem 26. For any X ∈ R n×V0 and θ ∈ R E × R B \(S ∪ ∆ X ), the two following statements are equivalent.

i) θ is locally identifiable from X.

ii) There exists ϵ > 0 such that

A(X, θ) = A(X, θ).

Let us prove that η = ϕ(θ). Using [START_REF] Zhong | Recovery guarantees for one-hidden-layer neural networks[END_REF], there exists τ ∈ U θ such that η = ψ θ (τ ). Since ∥ϕ(θ) -η∥ ∞ < ϵ ′ , we have using [START_REF] Zhang | Learning one-hidden-layer ReLU networks via gradient descent[END_REF]

Since ϵ < ϵ 2 , we have

Since

Using successively (3), (47), ( 48) and (3) again, we have

Since the hypothesis i) holds for ϵ 1 , using [START_REF] Zhou | A local convergence theory for mildly over-parameterized two-layer neural network[END_REF] and the fact that ϵ < ϵ 1 , we have

We conclude using Proposition 16 that

The converse inclusion trivially holds and therefore ii) holds.

ii) ⇒ i) Suppose ii) is satisfied for some ϵ ′ > 0.

We first construct ϵ and prove i) holds. Since θ ∈ R E × R B \(S ∪ ∆ X ), using Proposition 14, there exists ϵ 1 > 0 such that for all θ ∈ B ∞ (θ, ϵ 1 ),

Since ϕ is continuous, there exists

Using Proposition 19, there exists

Since θ ̸ ∈ S and S is closed, there exists

Let ϵ = min(ϵ 1 , ϵ 2 , ϵ 3 , ϵ 4 ). Let θ ∈ B ∞ (θ, ϵ), and suppose

Let us prove that θ ∼ θ. Reformulating the above equality using (3) for both sides, and using the definition of A given in the beginning of Section 4, we have

Since ∥θ -θ∥ ∞ < ϵ ≤ ϵ 1 , we have the equality (49) and thus

In other words, ϕ( θ)ϕ(θ) ∈ Ker A(X, θ).

1 ∩ N (X, θ), and using the hypothesis ii), we conclude that ϕ( θ) = ϕ(θ).

By Proposition 18, we have θ R ∼ θ, and since ϵ < ϵ 3 , we conclude that θ ∼ θ.

We are now going to prove Theorems 9 and 10, which we restate as Theorems 27 and 28 respectively (using Definition 6). Theorem 27 (Necessary condition). Let X ∈ R n×V0 and θ ∈ R E × R B \(S ∪ ∆ X ). If C N is not satisfied, then θ is not locally identifiable from X (thus not globally identifiable).

To prove the theorems, we need to prove first the following lemmas. Lemma 29. Let us denote by T = Im Dψ θ (τ θ ) the direction of the tangent plane to Σ * 1 at ϕ(θ). Let us denote by H the intersection Ker A(X, θ) ∩ T . We have

This shows that Dψ θ (τ θ ) -1 (Ker A(X, θ

Since Dψ θ (τ θ ) is injective, we thus have

Lemma 30. Let G be a supplementary subspace of Ker A(X, θ) such that

Let us show that dim(G) = dim(R P×V L )dim(T ). First note that we have

Using ( 51) and (54), we have

Using (50) and the hypothesis R Γ = R A we thus have

where the last equality comes from the injectivity of Dψ θ (τ θ ), shown in Proposition 24. Together with (53), this proves (52).

Let us now consider the function

then since Dψ θ (τ θ )h ∈ T and g ∈ G, we have

and since Dψ θ (τ θ ) is injective, h = 0 and Dξ(τ θ , 0) is injective. Since, using (52),

We can thus apply the inverse function theorem: there exists an open set

We can now prove the theorems.

Proof of Theorem 27.

We can thus apply Lemma 30:

Using the computation of dim(H) shown in Lemma 29, we have

Let us denote θ = ρ θ (τ ) and let us show that Theorem 26.ii) does not hold. By definition, ϕ( θ) = ψ θ (τ ) and since (τ, g) ∈ Õ, ∥ϕ(θ)ϕ( θ)∥ ∞ < ϵ. Since H ∩ G = {0}, w ∈ H, g ∈ G and w ̸ = 0, (55) shows that ϕ( θ)ϕ(θ) ̸ = 0.

Furthermore, since w ∈ H ⊂ Ker A(X, θ) and g ∈ G ⊂ Ker A(X, θ), (55) shows that

Summarizing, for any ϵ > 0 there exists

The second item of Theorem 26 does not hold. Since it is equivalent, the first item of Theorem 26 does not hold either. In other words, the conclusion of Theorem 27 holds.

Proof of Theorem 28. Suppose that C S is satisfied. Using Lemma 29 and using C S , we obtain

In order to apply Theorem 26, let us show by contradiction that there exists ϵ > 0 such that

We restate and prove Proposition 11.

is differentiable in a neighborhood of τ θ , and we denote by D τ f ρ θ (τ θ ) (X) its differential at τ θ . We have

Proof. Using (3) at ρ θ (τ ) and the definition of ψ θ in (11), we have

Taking the differential of

X) at τ θ , and using (13), we obtain

To finish with, the following proposition gives explicit expressions of the coefficients of Γ(X, θ). These expressions are given for the sake of theoretical completeness. Note that when it comes to computing Γ(X, θ) in practice (in order to compute R Γ ), the correct approach is using backpropagation as described in Section 5 rather than evaluating the expressions in Proposition 33 which involve sums with very large numbers of summands. Proposition 33. If we decompose it in the canonical bases of R

For lighter notations, let us drop the dependency in (X, θ) and denote by γ i,v L the lines of Γ(X, θ), for i ∈ 1, n and v L ∈ V L , which satisfy (γ i,v L ) T ∈ R F θ × R B . For any (i, v L ) ∈ 1, n × V L , let us express the coefficients of γ i,v L , i.e. express γ i,v L v l →v l+1 for any v l → v l+1 ∈ F θ and express γ i,v L v l for any v l ∈ B.

• For any l ∈ 0, L -1 and any (v l , v l+1 ) ∈ V l × V l+1 such that v l → v l+1 ∈ F θ ,

x i v0 w v0→v1 a v l (x i , θ)

where w v0→v1 = w v0→v1 and a v l (x i , θ) = a v l (x i , θ) except when l = 0 in which case w v0→v1 = 1 and a v l (x i , θ) = 1.

• For any l ∈ 1, L and any v l ∈ V l ,