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

François Malgouyres
email: francois.malgouyres@math.univ-toulouse.fr

François Bachoc
email: francois.bachoc@math.univ-toulouse.fr

Geometry-induced Implicit Regularization in Deep ReLU Neural Networks

Keywords: D eep learning, implicit regularization, geometry of neural networks, functional dimension of neural networks, flat minima, identifiability

It is well known that neural networks with many more parameters than training examples do not overfit. Implicit regularization phenomena, which are still not well understood, occur during optimization and 'good' networks are favored. Thus the number of parameters is not an adequate measure of complexity if we do not consider all possible networks but only the 'good' ones.

To better understand which networks are favored during optimization, we study the geometry of the output set as parameters vary. When the inputs are fixed, we prove that the dimension of this set changes and that the local dimension, called batch functional dimension, is almost surely determined by the activation patterns in the hidden layers. We prove that the batch functional dimension is invariant to the symmetries of the network parameterization: neuron permutations and positive rescalings. Empirically, we establish that the batch functional dimension decreases during optimization. As a consequence, optimization leads to parameters with low batch functional dimensions. We call this phenomenon geometry-induced implicit regularization.

The batch functional dimension depends on both the network parameters and inputs. To understand the impact of the inputs, we study, for fixed parameters, the largest attainable batch functional dimension when the inputs vary. We prove that this quantity, called computable full functional dimension, is also invariant to the symmetries of the network's parameterization, and is determined by the achievable activation patterns. We also provide a sampling theorem, showing a fast convergence of the estimation of the computable full functional dimension for a random input of increasing size. Empirically we find that the computable full functional dimension remains close to the number of parameters, which is related to the notion of local identifiability. This differs from the observed values for the batch functional dimension computed on training inputs and test inputs. The latter are influenced by geometry-induced implicit regularization.

Introduction

We introduce the context of the present article in Section 1.1, and we give a first glimpse of the objects of study in Section 1.2. We then outline the article in Section 1.3, and we present the related works in Section 1.4.

On the Importance of Local Complexity Measures for Neural Networks

Learning deep neural networks has a huge impact on many practical aspects of our lives. This requires optimizing a non-convex function, in a large dimensional space. Surprisingly, in many cases, although the number of parameters defining the neural network exceeds by far the amount of training data, the learned neural network generalizes and performs well with unseen data [START_REF] Zhang U. A | [END_REF]. This is surprising because in this setting the set of global minimizers is large (Cooper, 2021;[START_REF][END_REF] and contains elements that generalize poorly (Wu u. a., 2017;[START_REF] Neyshabur U. A ; Neyshabur | Nati: Exploring generalization in deep learning[END_REF]. In accordance with this empirical observation, the good generalization behavior is not explained by the classical statistical learning theory (e.g., Anthony und Bartlett, 2009;[START_REF] Grohs | [END_REF] that considers the worst possible parameters in the parameter set. For instance, the Vapnik-Chervonenkis dimension of feedforward neural networks of depth L, with W parameters, with the ReLU activation function is 1‹ O(LW ) (Bartlett u. a., 2019(Bartlett u. a., , 1998;;[START_REF][END_REF]Maass, 1994), leading to an upper bound on the generalization gap of order 1 ‹ O( » LW n ), where n is the sample size. This worst-case analysis is not accurate enough to explain the success of deep learning, when W ≫ n.

This leads to the conclusion that a global analysis, that applies to all global minima and the worst possible neural network that fits the data, will not permit to explain the success of deep learning. A local analysis is needed.

Despite tremendous research efforts in this direction (see, e.g., Grohs und Kutyniok, 2022 and references below) a complete explanation for the good generalization behavior in deep learning is still lacking. The attempts of explanation suggest that optimization algorithms and notably stochastic algorithms discover 'good minima' . These are minima having special properties that authors would like to model using local complexity measures that are pivotal in the mathematical explanation. Authors aim to establish that stochastic algorithms prioritize outputs (parameterizations at convergence) with low local complexity and to demonstrate that low local complexity explains the good generalization to unseen data (Bartlett u. a., 2020;Chaudhari u. a., 2019;Camuto u. a., 2021;Keskar u. a., 2017). This is sometimes also expressed as some form of implicit regularization (Imaizumi und [START_REF] Imaizumi Und Schmidt-Hieber ; Imaizumi | On generalization bounds for deep networks based on loss surface implicit regularization[END_REF]Belkin, 2021;[START_REF] Neyshabur U. A ; Neyshabur | Nati: Exploring generalization in deep learning[END_REF].

In this spirit, many authors contend that the excellent generalization behavior can be attributed to the fulfillment of conditions regarding the flatness of the landscape in the proximity of the algorithm's output (Keskar u. a., 2017;Foret u. a., 2021;[START_REF] Cha U | SWAD: Domain generalization by seeking flat minima[END_REF][START_REF] Hochreiter | [END_REF]. This is known however not to fully capture the good generalization phenomenon (Dinh u. a., 2017). Other studies explain the good generalization performances by constraints involving norms of the neural network parameters (Bartlett u. a., 2020;Neyshabur u. a., 2015b;[START_REF] Golowich | Sizeindependent sample complexity of neural networks[END_REF][START_REF][END_REF]. Despite being supported by partial arguments, none of the aforementioned local complexity measures fully explain the experimentally observed behaviors. This is in sharp contrast with linear networks for which implicit regularization is better understood. The consensus is that implicit regularization constrains the rank of the prediction matrix, the matrix obtained when multiplying all the factors of the linear network [START_REF] Arora U. A | [END_REF][START_REF] Razin Und Cohen | [END_REF][START_REF][END_REF][START_REF][END_REF][START_REF][END_REF]Achour u. a., 2022).

Local Dimensions of the Image and Pre-image Sets

This article investigates properties and computational aspects of local geometrical complexity measures of deep ReLU neural networks, recently introduced by Grigsby u. a. ( 2022). The considered complexity measures relate to the local geometry of the image set as defined by {f θ (X) | θ varies} and the pre-image set {θ ′ | f θ ′ (X) = f θ (X)}, where f θ (X) is the prediction made by the neural network of parameter θ, for an input sample X = (x (i) ) i∈ 1,n ∈ R N 0 ×n , where x (i) is the i-th column of X and the i-th input of the sample. When the differential Df θ (X) of θ -→ f θ (X) is appropriately defined, these concepts of complexity are associated with the local dimension of these sets, see Corollary 3, and related to the rank of the aforementioned differential, denoted rank(Df θ (X)) and called batch functional dimension by Grigsby u. a. (2022). Notice that, before Grigsby u. a., the batch functional dimension already appeared in an identifiability condition introduced by Bona-Pellissier u. a. (2022).

Main Contributions and Organization of the Paper

• In Theorem 1 (Section 3), up to a negligible set, we decompose the parameter space as a finite union of open sets. On each set, the batch functional dimension rank(Df θ (X))

is well defined and constant. The construction of the sets shows that almost everywhere, the activation pattern (defined in Section 2) determines the batch functional dimension. We also establish in Proposition 2 (Section 3) that the batch functional dimension is invariant under the symmetries of a ReLU neural network's parameterization, positive rescaling and neuron permutation, as defined in Section 2. We also provide examples in Sections 3 and 4.

• In Section 4, we illustrate the consequences of the statements of Section 3 when learning a deep ReLU network. In particular, we explain the links between the batch functional dimension, and the local dimensions of the image and pre-image sets, see Corollary 3 and Figure 2. We also illustrate in this figure how the described geometry impacts the iterates trajectory for small learning rates and we describe the geometry-induced implicit regularization.

• In Section 5, we study the computable full functional dimension1 defined by

r * (θ) = max X rank(Df θ (X)).
The first result of the section states that the achievable activation patterns for θ determine r * (θ), see Theorem 6. It also shows that when more activation patterns can be achieved, r * increases. As for the batch functional dimension, we establish that the computable full functional dimension is invariant under positive rescalings and neuron permutations. We finish the section with a connection between the computable full functional dimension and the fat-shattering dimension of neural networks.

• In Section 6 we provide the details on the practical computation of rank(Df θ (X)), for given X and θ. We also establish in Theorem 11 that, for a given θ, a random X of sufficient size can be used to compute r * (θ). Indeed, we upper bound the probability of not reaching r * (θ), as a vanishing function of the number n of columns of X. The upper bound depends on two natural quantities p and n * (θ) (see Theorem 11 for details).

• Finally, we provide experiments on the MNIST data set in Section 7. In Section 7.2, we analyze the behavior of the local complexity measures when the width of the network increases. We also describe their behavior during the learning phase in Section 7.3. We also show in Sections 7.4 and 7.5 how they behave when the distribution of (X, Y ) is artificially complexified, Y denoting the outputs. The experiments highlight the geometry-induced implicit regularization described in Section 4 both at the learning and test stages. The experiments also highlight the correlation between the batch functional dimension computed using the learning and test samples and the complexity of the learning task. Our experiments also indicate that for corrupted or highly random inputs, the batch functional dimension may be maximal, corresponding almost surely to local identifiability, see Bona-Pellissier u. a. (2022).

All the proofs are in the Appendices and the codes are available at (Bona-Pellissier u. a., 2023b).

Related Works

To the best of our knowledge, the functional dimensions of deep ReLU neural networks has only been explicitly studied by Grigsby u. a. (2022[START_REF] Grigsby U. A | [END_REF]. The article Grigsby u. a. ( 2022) is very rich and it is difficult to summarize it in a few lines2 . The authors establish sufficient conditions guaranteeing that θ -→ f θ (X) is differentiable. The conditions are comparable to but weaker than the one presented here. The benefit of the difference is that our conditions guarantee the value of the batch functional dimension, allowing us to make the connection between the activation patterns and the batch functional dimension. Furthermore, Grigsby u. a. define and provide examples to illustrate that the batch functional dimension and the full functional dimension vary in the parameter space. They also prove that for all narrowing architectures3 , the functional dimension as defined by max θ max X rank(Df θ (X)) reaches its upper-bound W -W ′ where W ′ is the number of positive rescalings. They finish their article with several examples showing that the global structure of the pre-image set {θ ′ | f θ ′ (X) = f θ (X)} can vary in several regards. Grigsby u. a. prove that when the input size lower-bounds the other widths there exist parameters for which the batch functional dimension reaches the upper-bound W -W ′ . They also numerically estimate, for several neural network architectures, the size of the sets of parameters that reach this upper bound.

Geometric properties of the pre-image set of a global minimizer have been studied by Cooper (2021). Topological properties of a variant of the image set included in function spaces, {f θ | θ varies}, have been established by [START_REF] Petersen U | [END_REF].

There are many articles devoted to the identifiability of neural networks (Petzka u. a., 2020;Carlini u. a., 2020;Rolnick und Kording, 2020;[START_REF] Stock | Rémi: An embedding of ReLU networks and an analysis of their identifiability[END_REF]Bona-Pellissier u. a., 2022, 2023a). For a given θ, they study conditions guaranteeing that the pre-image set4 of f θ (X) coincides with the set obtained when considering all the positive rescalings of θ. Of particular interest in our context, Bona-Pellissier u. a. (2022) establish that the condition rank(Df θ (X)) = W -W ′ is sufficient to guarantee local identifiability. The same condition is also involved in a necessary condition of local identifiability.

Other local complexity measures, not related to the geometry of neural networks, have been considered. There are complexity measures using the number of achievable activation patterns Montufar u. a. (2014);[START_REF] Raghu U | On the expressive power of deep neural networks[END_REF]; Hanin und [START_REF] Hanin Und Rolnick ; Hanin | Complexity of linear regions in deep networks[END_REF]. Those based on norms and the flatness are already mentioned in Section 1.1.

The objects studied in this article are also related to the properties of the landscape of the empirical risk, which have been investigated in the literature. Studies of these properties for instance permit to guarantee that first-order algorithms find a global minimizer [START_REF] Soudry | [END_REF][START_REF] Nguyen Und Hein | [END_REF][START_REF][END_REF][START_REF][END_REF], focus on the shape at the bottom of the empirical risk [START_REF] Ghorbani U | [END_REF][START_REF] Sagun U | [END_REF][START_REF] Gur- | [END_REF] and (again) on flatness.

The local properties studied in the present article also have an impact on the iterates trajectory of minimization algorithms and therefore the biases induced by the optimization as studied in (Bartlett u. a., 2020;Chaudhari u. a., 2019;Camuto u. a., 2021;Keskar u. a., 2017). Finally, Arora u. a. ( 2018) and Suzuki u. a. (2020) establish generalization bounds of compressed neural networks. This might provide hints for the construction of upper-bounds of the generalization gap based on the local geometric complexity measures considered in this article.

ReLU Networks and Notations

This section is devoted to introducing the formalism and notations that we use throughout the article. In Section 2.1, we present the graph formalism that we use for neural networks, and we specify the architectures that we study, and in Section 2.2, we construct the prediction function implemented by a network, and we define the differential Df θ (X) that is central in this work. In Section 2.3, we recall the two classical symmetries of ReLU networks, namely positive rescalings and permutations. Finally, we introduce the activation patterns in Section 2.4 and some additional notations in Section 2.5.

ReLU Network Architecture

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

• V is a set of neurons, which is divided into L + 1 layers, with L ≥ 2: V = L ℓ=0 V ℓ .
The layer V 0 is the input layer, V L is the output layer and the layers V ℓ with 1 ≤ ℓ ≤ L -1 are the hidden layers. Using the notation |C| for the cardinality of a finite set C, we denote, for all5 ℓ ∈ 0, L , N ℓ = |V ℓ | the size of the layer V ℓ .

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

E = {v ′ → v | v ′ ∈ V ℓ-1 , v ∈ V ℓ , for ℓ ∈ 1, L }.
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 ℓ=1 V ℓ . We let W = |E| + |B|.
The activation function used in the hidden layers, and denoted σ, is always ReLU: for any p ∈ N * and any vector

x = (x 1 , . . . , x p ) T ∈ R p , we set σ(x) = (max(x 1 , 0), . . . , max(x p , 0)) T .
Here and in the sequel, the symbol N * denotes the set of natural numbers without 0. We allow the use of a specific activation σ L : R N L -→ R N L for the output layer, which we only require to be analytic. For instance, σ L can be the identity, as is generally the case in regression, or the softmax, as is generally the case in classification. The ReLU neural network architectures considered in this article are fully characterized by a triplet (E, V, σ L ).

ReLU Network Prediction

For a given θ, we define recursively

f ℓ θ : R V 0 -→ R V ℓ , for ℓ ∈ 0, L and x ∈ R V 0 , by          (f 0 θ (x)) v = x v for v ∈ V 0 , (f ℓ θ (x)) v = σ Ä v ′ ∈V ℓ-1 w v ′ →v (f ℓ-1 θ (x)) v ′ + b v ä for v ∈ V ℓ , when ℓ ∈ 1, L -1 , (y L θ (x)) v = v ′ ∈V L-1 w v ′ →v (f L-1 θ (x)) v ′ + b v for v ∈ V L , f L θ (x) = σ L (y L θ (x)), (1)
where the definition of f L θ (x) takes into account that σ L : R V L -→ R V L may require the whole pre-activation output. This is for instance the case for the softmax activation function. We define the function f θ : R V 0 -→ R V L implemented by the network of parameter θ as

f θ = f L θ .
We call it the prediction. For all n ∈ N * , we concatenate a set of n inputs in a matrix X = (x (i) ) i∈ 1,n ∈ R N 0 ×n , where x (i) is the i-th column of X and the i-th input of the network. We also allow to write f θ as operating on an input set X. In this case, we write f θ : R N 0 ×n -→ R N L ×n and we define f θ (X) as the matrix gathering the outputs (f θ (x (i) )) i∈ 1,n .

Among other quantities, we study in this article the set

{f θ (X) | θ ∈ R E × R B },
for X ∈ R N 0 ×n fixed, which we call an image set. When it is differentiable at θ, we denote by Df θ (X) the differential, at the point θ, of the mapping

R E × R B -→ R N L ×n θ ′ -→ f θ ′ (X).
We recall that the differential at θ is the linear map

Df θ (X) : R E × R B -→ R N L ×n (2) such that, for θ ′ ∈ R E × R B in a neighborhood of zero, f θ+θ ′ (X) = f θ (X) + Df θ (X)(θ ′ ) + o(∥θ ′ ∥).
(3)

Positive rescaling and neuron permutations symmetries

Consider two parameters θ, θ ∈ R E×B , with θ = Ä ( w v ′ →v ) v ′ →v∈E , ( b v ) v∈B ä
. We say that θ and θ are equivalent modulo positive rescaling, and we write θ ∼ s θ, when the following holds. There are

(λ v ) v∈V 0 ∪•••∪V L ∈ (0, ∞) V 0 ∪•••∪V L such that λ v = 1 for v ∈ V 0 ∪ V L and for ℓ ∈ 1, L , v ′ ∈ V ℓ-1 , v ∈ V ℓ , w v ′ →v = λ v λ v ′ w v ′ →v , ( 4
) b v = λ v b v . ( 5
)
Then it is a well-known property of ReLU networks (Bona-Pellissier u. a., 2023a, 2022;Neyshabur u. a., 2015a;[START_REF] Stock | Efficiency and Redundancy in Deep Learning Models : Theoretical Considerations and Practical Applications[END_REF][START_REF] Stock | Rémi: An embedding of ReLU networks and an analysis of their identifiability[END_REF][START_REF][END_REF] that if θ ∼ s θ then f θ = f θ , that is, positive rescalings are a symmetry of the network parameterization.

Another classic symmetry consists in swapping neurons, and their corresponding weights, within each hidden layer. If θ stands for the permuted weights, we denote the corresponding equivalence relation θ ∼ p θ. Again, when θ ∼ p θ, we have f θ = f θ .

We say that θ ∼ θ if there exists θ ′ such that θ ∼ p θ ′ and θ ′ ∼ s θ. Again, if θ ∼ θ, then f θ = f θ .

Activation Patterns

For any ℓ ∈ 1, L -1 , v ∈ V ℓ , θ ∈ R E × R B and x ∈ R N 0 , we define the activation indicator at neuron v by a v (x, θ) = ® 1 if v ′ ∈V ℓ-1 w v ′ →v (f ℓ-1 θ (x)) v ′ + b v ≥ 0 0 otherwise.
Using (1), we have for the ReLU activation function σ,

any ℓ ∈ 1, L -1 and v ∈ V ℓ , (f ℓ θ (x)) v = a v (x, θ) v ′ ∈V ℓ-1 w v ′ →v (f ℓ-1 θ (x)) v ′ + b v . ( 6
)
We then define the activation pattern as the mapping

a : R N 0 × Ä R E × R B ä -→ {0, 1} N 1 +•••+N L-1 (x, θ) -→ (a v (x, θ)) v∈V 1 ∪•••∪V L-1 .
For X ∈ R N 0 ×n as considered above, we let a(X, θ) ∈ {0, 1} (N +N L-1 )×n be defined by,

for i ∈ 1, n and v ∈ V 1 ∪ • • • ∪ V L-1 , a v,i (X, θ) = a v (x (i) , θ).
By extension, we also call activation patterns the elements of {0,

1} N 1 +•••+N L-1 or {0, 1} (N 1 +•••+N L-1 )×n .

Further Notation

We use the notation rank(•) for the rank of linear maps and matrices. The determinant of a square matrix M is denoted det(M ). If the matrix M ∈ R a×b for a, b ∈ N * , then for i ∈ 1, a , we write M i,: for the row i of M . All considered vector spaces are finite dimensional and they are endowed with the standard Euclidean topology. For a subset C ⊂ T of a topological space, we denote Int(C) the topological interior of C, ∂C its boundary and C c = T \ C the complement of C (the ambient topological space T should always be clear from context). For all Euclidean space V , all element x ∈ V , and all real number r ≥ 0, the open Euclidean ball of radius r centered at x is denoted by B(x, r).

Rank Properties

In this section, we give the key technical theorem, namely Theorem 1, on which the remaining of the article relies. We then illustrate the theorem with examples showing the diversity of situations that might occur. The theorem is composed of two parts. In the first one, we study (X, θ) -→ f θ (X) over R N 0 ×n × (R E × R B ), and in the second one, we study θ -→ f θ (X) over R E × R B , for X fixed. We must first introduce a few definitions.

For n ∈ N * , the function

R N 0 ×n × (R E × R B ) -→ {0, 1} (N 1 +•••+N L-1 )×n (X, θ) -→ a(X, θ)
takes a finite set of values, that we write ∆ n 1 , . . . , ∆ n q . Let us write, for j ∈ 1, q ,

‹ O n j = Int{(X, θ) ∈ R N 0 ×n × (R E × R B ) | a(X, θ) = ∆ n j }, (7)
and let us only keep the non-empty ‹ O n j . If m n ∈ 1, q is the number of such non-empty sets, up to a re-ordering, we can assume that we keep ‹ O n 1 , . . . , ‹ O n mn . As will be formally established in Lemma 13, (i), third item, for all j ∈ 1, m n , the function

θ -→ f θ (X) is differentiable at θ when (X, θ) ∈ ‹ O n j .
We can therefore define, for n ∈ N * and j ∈ 1, m n ,

r n j = max (X,θ)∈ ‹ O n j rank(Df θ (X)). (8)
We then define the subset of ‹ O n j on which the rank is maximal. For n ∈ N * and j ∈ 1, m n ,

O n j = {(X, θ) ∈ ‹ O n j | rank(Df θ (X)) = r n j }. (9)
Similarly, for n ∈ N * and X ∈ R N 0 ×n , the function θ -→ a(X, θ) takes a finite number of values ∆ X 1 , . . . , ∆ X q X , and we define, for j ∈ 1, q X ,

U X j = Int{θ ∈ R E × R B | a(X, θ) = ∆ X j }. (10)
Similarly, we keep only the nonempty such sets, and if p X ∈ 1, q X is the number of such sets, we can assume up to a re-ordering that we keep U X 1 , . . . , U X p X . Again, as we will establish in Lemma 13, (ii), third item, for all j ∈ 1, p X , the function θ -→ f θ (X) is differentiable at θ when θ ∈ U X j . We can therefore define, for n ∈ N * , X ∈ R N 0 ×n and j ∈ 1, p X ,

r X j = max θ∈ U X j rank(Df θ (X)). ( 11
)
We finally define the subset of U X j on which the rank is maximal.

For n ∈ N * , X ∈ R N 0 ×n and j ∈ 1, p X , U X j = {θ ∈ U X j | rank(Df θ (X)) = r X j }. ( 12
)
The following theorem is composed of two parts, named (i) and (ii). In (i), we study (X, θ) -→ f θ (X) over R N 0 ×n ×(R E ×R B ), and we provide properties of the sets O n 1 , . . . , O n mn . In (ii), we study θ -→ f θ (X) over R E × R B , for X fixed, and we provide properties of the sets U X 1 , . . . , U X p X . Note that for both parts (i) and (ii), Items 1, 2 and 3 hold trivially by definition, while Items 4, 5 and 6 require detailed proofs.

-for all j ∈ 1, m n , (X, θ) -→ f θ (X) is an analytic function on O n j .
(ii) For all n ∈ N * , for all X ∈ R N 0 ×n , by definition, -the sets U X 1 , . . . , U X p X are non-empty and disjoint, -for all j ∈ 1, p X , the function θ -→ a(X, θ) is constant on each U X j and takes p X distinct values on ∪ p X j=1 U X j ; -for all j ∈ 1, p X , θ -→ rank(Df θ (X)) is constant on U X j and equal to r X j .

Furthermore,

-the sets U X 1 , . . . , U X p X are open, - Ä ∪ p X j=1 U X j ä c is a closed set with Lebesgue measure zero; -for all j ∈ 1, p X , θ -→ f θ (X) is an analytic function on U X j .
The proof of the theorem is in Appendix A.1. This theorem formalizes that the sets (O n j ) j∈ 1,mn (resp. (U

X j ) j∈ 1,p X ) almost cover the spaces R N 0 ×n × (R E × R B ) (resp. R E × R B ). Moreover, on each set O n j (resp. U X j
) the activation pattern is constant, and the function (X, θ) -→ f θ (X) (resp. θ -→ f θ (X)) is analytic. We only state that it is analytic, but when the output activation σ L is the identity, it is in fact polynomial, and we would like to emphasize here that the structure of the polynomial is very particular. For instance, every variable appears with a degree at most one, and all monomials have the same degree. A more complete description of the polynomial structure is, for instance, given by Bona-Pellissier u. a. (2022); [START_REF] Stock | Rémi: An embedding of ReLU networks and an analysis of their identifiability[END_REF].

Looking at the definition of ‹ O n j (resp U X j ) and O n j (resp U X j ), using that In other words, modulo negligible sets, the activation pattern determines rank(Df θ (X)).

Ä ∪ mn j=1 O n j ä c (resp Ä ∪ p X j=1 U X j ä c )
Finally, the conclusions concerning rank(Df θ (X)) have direct consequences on the dimensions of the image

{f θ ′ (X) | θ ′ ∈ B(θ, ε)} and the pre-image {θ ′ ∈ B(θ, ε) | f θ ′ (X) = f θ (X)},
where ε > 0 is small enough. The consequences and their implications in machine learning applications are described in greater detail in the next sections.

When compared to existing similar statements [START_REF] Stock | Rémi: An embedding of ReLU networks and an analysis of their identifiability[END_REF]Grigsby u. a., 2022;Bona-Pellissier u. a., 2022;[START_REF] Grigsby | [END_REF], the particularity of Theorem 1 is that the construction of the sets O n j and U X j permits to include, in the third item of (i) and (ii), a statement on rank(Df θ (X)). To the best of our knowledge, this quantity appears for the first time in conditions of local parameter identifiability introduced by Bona-Pellissier u. a. ( 2022). It appears independently a few months later, as the core quantity of a study dedicated to the geometric analysis of neural networks carried out by Grigsby u. a. (2022). In the latter article, this quantity is called the 'batch functional dimension' and we will use this name in this article.

Because the input space of Df θ (X) is always R E × R B , the quantity rank(Df θ (X)) is upper bounded by the number of parameters |E|+|B|. Furthermore, as formalized by Grigsby u. a. (2022), because of the invariance by positive rescaling, see the definition and discussion of the relation ∼ s in Section 2, we even have rank(Df θ (X))

≤ |E| + |B| -N 1 -• • • -N L-1 . In fact, when rank(Df θ (X)) = |E| + |B| -N 1 -• • • -N L-1
, under mild conditions on θ, the network function is locally identifiable around θ. That is, f θ (X) = f θ ′ (X) and ∥θ -θ ′ ∥ small enough imply θ ∼ s θ ′ (see Bona-Pellissier u. a., 2022).

Beyond the case of maximal rank value, rank(Df θ (X)

) = |E| + |B| -N 1 -• • • -N L-
∈ R E × R B such that b v < 0 and w v ′ →v < 0, for all v ′ ∈ V ℓ-1 . ( 13
)
Because of the ReLU activation function, for all x ∈ R N 0 and all v ′ ∈ V ℓ-1 , we have (f ℓ-1 θ (x)) v ′ ≥ 0, and (1) and ( 13) guarantee that (f ℓ θ (x)) v = 0. This holds for all θ in the open set defined by (13). In this set, the parameters (w v ′ →v ) v ′ ∈V ℓ-1 and b v have no impact on f θ (X), which leads to a rank deficiency of Df θ (X). Going further, consider any θ ∈ R E × R B . According to the above remark, to diminish rank(Df θ (X)), we can change the weights arriving to a given neuron v, and assign them negative values so that (13) holds. We can redo this operation to many neurons to diminish the rank further. As a conclusion to the example, many values of rank(Df θ (X)) are reached at different places in the parameter/input space.

Let us conclude the section by showing that the quantity rank(Df θ (X)) is invariant with respect to the positive rescaling and/or neuron permutation symmetries defined in Section 2.

Proposition 2. Consider any deep fully-connected ReLU network architecture (E, V, σ L ). Let θ, θ ∈ R E × R B such that θ ∼ θ. Then, for any n ∈ N * and X ∈ R N 0 ×n , Df θ (X) is defined if and only if Df θ (X) is defined, and in that case we have

rank Df θ (X) = rank(Df θ (X)).
The proof of the proposition is in Appendix A.2. In this appendix, we provide Proposition 14, which includes Proposition 2 as its first statement. Keskar u. a. (2017). This leads to undesired behaviors (Dinh u. a., 2017). Similarly, complexity measures defined by norms [START_REF][END_REF](Bartlett u. a., , 2020;;[START_REF] Golowich | Sizeindependent sample complexity of neural networks[END_REF]Neyshabur u. a., 2015b) are not invariant to positive rescalings6 .

Geometric Interpretation when X is Fixed

The statement of Theorem 1, (i) is used in Section 5. In this section, we mostly describe the consequences of Theorem 1, (ii). The next corollary is a straightforward consequence of the constant rank theorem and Theorem 1, (ii).

Corollary 3. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

For any n ∈ N * , X ∈ R N 0 ×n , j ∈ 1, p X and θ ∈ U X j , there exists ε X,θ > 0 such that

• the local image set {f θ ′ (X) ∈ R N L ×n | ∥θ ′ -θ∥ < ε X,θ }
is a smooth manifold of dimension rank(Df θ (X));

• the local pre-image set

{θ ′ ∈ R E × R B | f θ ′ (X) = f θ (X) and ∥θ ′ -θ∥ < ε X,θ } is a smooth manifold of dimension |E| + |B| -rank(Df θ (X)).

Example

We show on Figure 1 the sets U X j (left) and their image f U X j (X) = {f θ (X) | θ ∈ U X j } (right), for j ∈ 1, 6 , for a one-hidden-layer neural network of widths (1, 1, 1), with the identity activation function on the last layer. To simplify notations, we denote the weights and biases θ = (a, b, c, d)

∈ R 4 so that f θ (x) = bσ(ax + c) + d, for all x ∈ R. We consider X = (0, 1, 2) ∈ R 1×3 and f θ (X) T = Ñ bσ(c) + d bσ(a + c) + d bσ(2a + c) + d é .
For any j ∈ 1, 6 , the sets U X j depend on the activations in the hidden layer. They are separated by the hyperplanes c = 0, a + c = 0, 2a + c = 0. The conditions only depend on a and c. We represent the projection of the sets U X j and the lines c = 0, a + c = 0, 2a + c = 0 in the plane (a, c), on the left of Figure 1.

Similarly, for any j ∈ 1, 6 , the image set f U X j (X) ⊆ R 3 is invariant to translations by a vector (d, d, d), for d ∈ R. On the right of Figure 1, we represent for all j the intersection V j = f U X j (X) ∩ P between the image set f U X j (X) and the linear plane P orthogonal to

(1, 1, 1), generated by the vectors 1 √ 6 (1, 1, -2) and 1 √ 2 (-1, 1, 0). The calculations leading to the construction of the figure are in Appendix B.

Geometry-induced Implicit Regularization

Corollary 3 is illustrated in Figure 2. There we consider a regression problem with a fixed target data matrix Y ∈ R N L ×n corresponding to the input matrix X ∈ R N 0 ×n . We consider the square loss ∥Y -f θ (X)∥ 2 , for θ ∈ R E × R B , where ∥ • ∥ is the Euclidean (Frobenius) norm. We also consider θ * minimizing the square loss.

In Figure 2, we display a (fictive) illustrative case, that can be considered as representative of the practice of deep neural networks, and of our numerical experiments in Section 7.

We consider here that in Corollary 3, p X = 7. Hence, there are 7 sets

U X 1 , . . . , U X 7 forming a partition of R E × R B . On Figure 2, for j ∈ 1, 7 , the image of U X j , {f θ (X) | θ ∈ U X j }
, is drawn with the same color as U X j . Locally, it has the structure of a smooth manifold of dimension r X j . The rank values are r

X 1 = 1, r X 2 = 2, r X 3 = 1, r X 4 = 0, r X 5 = 1, r X 6 = 1, r X 7 = 1 and thus the full image set {f θ (X) | θ ∈ R E × R B } is a two-dimensional object. In the figure, this full image set is mainly covered by the two-dimensional image set {f θ (X) | θ ∈ U X 2 }, and the six other image sets {f θ (X) | θ ∈ U X j }, j ∈ 1, 7 \ {2}, of dimension one or zero, are at the boundary of {f θ (X) | θ ∈ R E × R B }.
Hence, intuitively they are 'exposed', meaning in particular that if Y does not belong to the full image set, then the optimal prediction

f θ * (X) is in one of the smaller dimensional {f θ (X) | θ ∈ U X j }, j ∈ 1, 7 \ {2}.
This is an illustration of the geometry-induced implicit regularization phenomenon put to evidence in this article. In practice, parameters found by minimizing the empirical risk numerically tend to have a small complexity as measured by rank(Df θ (X)), where X is the learning sample.

c a a + c = 0 2a + c = 0 c = 0 U X 1 U X 2 U X 3 U X 4 U X 5 U X 6 θ = (a, b, c, d) ∈ R 4 f θ (X) R 1×3 restrict to P R 2 y x x + √ 3y = 0 √ 3x + y = 0 y = 0 • Figure 1: Representation of the sets U X j in the space (a, c) (left) and restriction to P of the corresponding image sets {f θ (X) | θ ∈ U X j }, j ∈ 1, 6 (right). We have r X 1 = 1, r X 2 = 2, r X 3 = 3, r X 4 = 2, r X 5 = 3, r X 6 = 2. The image of U X 1 such that r X 1 = 1 is reduced to (0, 0) (right).
The images of the sets U X j with r X j = 2 (i.e. j = 2, 4, 6) are represented with thick lines of their respective colors (right). The images of U X 3 , with r X 3 = 3, and U X 5 , with r X 5 = 3, are represented by dashed areas, with the corresponding colors (right).

θ ∈ R E × R B U X 1 U X 2 U X 3 U X 4 U X 5 U X 6 θ * × U X 7 f θ (X) R N L ×n Y × ×f θ * (X)
•

(X) | θ ∈ U X j }, j ∈ 1, 7 (right). We have r X 1 = 1, r X 2 = 2, r X 3 = 1, r X 4 = 0, r X 5 = 1, r X 6 = 1, r X 7 = 1. The image of U X
2 is the curved diamond-shaped area, hatched in cyan (right). The images of the sets U X j with r X j = 1 are represented with lines of their respective colors (right). The image of U X 4 with r X 4 = 0 is represented by a magenta bullet point (right). We consider the square loss in R N L ×n . The target Y ∈ R N L ×n and the global solution f θ * (X) of the regression problem are represented (right). The pre-image of f θ * (X) is displayed in brown (left). A minimizing sequence is represented by gray stars, in the parameter space (left) and the image space (right).

The illustrative situation in Figure 2 corresponds to the empirical observations made in Section 7.2 for the MNIST classification problem. In this section, we even observe that, consistently in our experiments, a larger optimal loss leads to a smaller batch functional dimension. We will also see empirically in Section 7.2 that for large parameter complexities (W large), the batch functional dimension computed on the learning sample remains moderate. There are two complementary explanations. First, even though the predictions are correct for all training examples, because of the soft-max activation on the last layer, the cross-entropy loss slightly differs from zero. Secondly, although there may exist θ for which the loss is exactly zero, this θ is apparently not in the convergence basin in which the local search algorithm optimizes.

Influence of the Geometry on the Optimization Trajectory

In Figure 2, we also display a (fictive) minimizing sequence, that is a set of pairs (θ n , f θn (X)) n∈N obtained by a numerical gradient-descent-based optimization procedure. This sequence is initialized in U X 2 , then passes in U X 5 and then U X 6 , where the optimal solution lies. This illustrative example is an illustration of the experimental results of Section 7.3. There, during the learning phase, the sequence (rank(Df θn (X))) n∈N typically decreases. According to Corollary 3, this corresponds to an objective landscape that becomes flatter and flatter, in the sense that the local dimension of the pre-image of f θn (X) increases. Locally in the parameter space, the objective function is constant along a smooth manifold of a larger dimension. This new notion of flatness resembles but slightly differs from the notion of 'flat minima' usually considered to explain the good generalization properties of deep learning (Keskar u. a., 2017;Dinh u. a., 2017;Foret u. a., 2021;[START_REF] Cha U | SWAD: Domain generalization by seeking flat minima[END_REF][START_REF] Hochreiter | [END_REF].

Rank Saturating X, when θ is Fixed

In this section, we define a dense subset of R E × R B , and for θ in this subset, we analyze the maximum value of rank(Df θ (X)), for any X of any size, in a dense set. This is a natural notion of complexity, that we call 'computable full functional dimension'. In particular, it is independent of X and measures the expressive potential of the neural network defined by θ. It is linked to the full functional dimension defined by Grigsby u. a. ( 2022), but can be computed (see Section 6.2), thus the name. After giving the main definitions and establishing the first properties of the considered mathematical objects, we give the main result of this section (Theorem 6), which states that the computable full functional dimension depends only on the attainable activation patterns for the considered θ, when X varies. We also show the invariance of the computable full functional dimension with respect to neuron permutations and positive rescalings. We finally establish a simple link with the (local and global) fat-shattering dimensions of the ReLU neural networks of architecture (E, V, σ L ).

For a fixed θ ∈ R E × R B and any activation pattern δ ∈ {0,

1} N 1 +•••+N L-1 , we denote D δ (θ) = {x ∈ R N 0 | a(x, θ) = δ}. ( 14
)
It is well known (among many others, see Bona-Pellissier u. a., 2023a) that the restriction of the function

x -→ f θ (x) to D δ (θ) is affine. It is therefore smooth in Int(D δ (θ)) but,
generically, the function is not differentiable at the boundary of D δ (θ). For any θ ∈ R E × R B , following [START_REF] Stock | Rémi: An embedding of ReLU networks and an analysis of their identifiability[END_REF], we also define the achievable activation patterns

A(θ) = {δ ∈ {0, 1} N 1 +•••+N L-1 | Int(D δ (θ)) ̸ = ∅} (15)
and

X θ = δ∈A(θ) Int(D δ (θ)).
It is well known that the pieces D δ (θ) are polyhedral (see for instance Bona-Pellissier u. a. 2023a). Hence the complement set X c θ is included in a finite union of hyperplanes. Hence, the set X θ is dense (and open) in R N 0 .

We extend this definition to samples and set, for

n ∈ N * and θ ∈ R E × R B , X n θ = {X ∈ R N 0 ×n | ∀i ∈ 1, n , x (i) ∈ X θ }. (16)
The set X n θ is the nth order tensor product of the set X θ with itself. By construction, the set X n θ is open and dense in R N 0 ×n , for all n and θ. The results of this section will apply to all θ ∈ R E × R B except those in a subset Z, which will turn out to be of Lebesgue measure zero -see Proposition 4. To define the set Z, we first define, for all n ∈ N * and all

θ ∈ R E × R B , z n (θ) = ¶ X ∈ R N 0 ×n | (X, θ) ∈ Ä ∪ mn j=1 O n j ä c © , ( 17
)
where O n 1 , . . . , O n mn are defined in (9) and described in Theorem 1. The set z n (θ) is closed and therefore Lebesgue measurable. We write, for all n ∈ N * ,

Z n = ¶ θ ∈ R E × R B | z n (θ) has positive Lebesgue measure in R N 0 ×n © (18)
and Z = ∪ n∈N * Z n . We state in the following proposition the most important properties of Z, used in the remaining of the article.

Proposition 4. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

(i) For all n ∈ N * , the set Z n is Lebesgue measurable and has Lebesgue measure zero on

R E × R B .
(ii) The set Z is Lebesgue measurable and has Lebesgue measure zero on

R E × R B . (iii) For all θ ∈ (R E × R B ) \ Z, all n ∈ N * , and all X ∈ X n θ , the function θ ′ -→ f θ ′ (X)
is analytic in a neighborhood of θ and it is therefore differentiable at the point θ.

The proof of the proposition is in Appendix C.1. Using Proposition 4, (iii), we can define, for all n ∈ N * and all θ ∈ (R E × R B ) \ Z, the main objects studied in this section

r * n (θ) = max X∈X n θ rank(Df θ (X)), (19)
and the computable full functional dimension

r * (θ) = max n∈N * r * n (θ). (20)
Notice that, although X n θ is open and dense in R N 0 ×n and the rank is lower semicontinuous, the existence of X ∈ R N 0 ×n \ X n θ such that Df θ (X) is well defined and rank(Df θ (X)) > r * n (θ) is not excluded. The computable full functional dimension r * (θ) therefore may slightly differ from the full functional dimension defined by Grigsby u. a. ( 2022). It lower bounds the full functional dimension. We will see in Section 6.2 that its advantage is that it can be computed with a random X. Notice finally that in Examples 1 the rank deficiency caused by negative weights is independent of X. Therefore, r * (θ) achieves several values, as θ varies.

Notice also that, although we take the maximum over all n ∈ N * , we know that since, for all n ∈ N * and all X ∈ R N 0 ×n , θ -→ Df θ (X) always has the same input dimension |E| + |B|, see (2), the maximum is reached for n ≤ |E| + |B| (see also Proposition 9 below).

The following proposition states that r * n (θ) equals the largest of all the r n j , as defined in (8), that are reachable when X varies, for the given θ.

Proposition 5. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

For any θ

∈ (R E × R B ) \ Z and n ∈ N * , r * n (θ) = max j∈In(θ) r n j ,
where

I n (θ) = {j ∈ 1, m n | ∃X ∈ R N 0 ×n , (X, θ) ∈ O n j }. ( 21
)
The proposition is proved in Appendix C.2.

The following theorem states that the achievable activation patterns A(θ), as defined in (15), determine r * (θ). It also states that when the prediction has more affine areas, that is for a fixed θ, X -→ f θ (X) is piece-wise affine with more pieces, then this prediction is more complex, in the sense of r * . Theorem 6. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

For any θ and

θ ′ in (R E × R B ) \ Z, if A(θ) ⊆ A(θ ′ ) then r * (θ) ≤ r * (θ ′ ); as a consequence, if A(θ) = A(θ ′ ) then r * (θ) = r * (θ ′ ).
The proof of the theorem is in Appendix C.3. Next, we show that r * n (θ), r * (θ) and Z are invariant by neuron permutation and positive rescaling (recall the relations ∼, ∼ s and ∼ p presented in Section 2).

Proposition 7. Let θ ∈ R E × R B and θ ∼ θ. Then θ ∈ Z ⇐⇒ θ ∈ Z. Also, if θ ∈ (R E × R B ) \ Z, r * n (θ) = r * n ( θ) for all n ∈ N * and r * (θ) = r * ( θ).
The proof of the proposition is in Appendix C.4. Let us conclude this section by showing that r * (θ) provides lower-bounds on various fat-shattering dimensions for neural networks. The fat-shattering dimension of a family of regression functions is a well-known measure of complexity (see for instance Anthony und Bartlett 2009, Chapter 11). In the rest of the section, we let N L = 1 and, for a subset A ⊆ R E × R B , for γ > 0, the fat-shattering dimension of the family {f θ | θ ∈ A}, that we write fS A,γ , is defined as follows. It is the largest n ∈ N * such that there exist

x (1) , . . . , x (n) ∈ R N 0 and t 1 , . . . , t n ∈ R such that for all I ⊆ 1, n , there is θ ∈ A such that for i ∈ I, f θ (x (i) ) ≥ t i + γ and for i ∈ 1, n \ I, f θ (x (i) ) ≤ t i -γ. If this property holds for all n then we let fS A,γ = ∞.
The intuition is that fS A,γ is the largest number n of input points for which all 2 n combinations of being above or below the threshold t i by a margin γ, i ∈ 1, n , can be reached by the functions in {f θ | θ ∈ A} (see Anthony und Bartlett 2009). When A is a small ball centered at a parameter of interest we shall call fS A,γ a local fat-shattering dimension, and when A = R E × R B , we shall call fS A,γ a global fat-shattering dimension. We also consider the case where A is the set of parameters yielding a given computable full functional dimension, where we refer to fS A,γ as the fixed-rank fat-shattering dimension. The next proposition shows the announced lower bounds.

Proposition 8. Consider any deep fully-connected ReLU network architecture

(E, V, σ L ) such that N L = 1. Let θ ∈ (R E × R B ) \ Z.
Then for any ε > 0, there is γ > 0 such that we have the following lower bound on the local fat-shattering dimension,

fS B(θ,ε),γ ≥ r * (θ). ( 22
)
As a first consequence, there is γ ′ > 0 such that the global fat-shattering dimension is lower bounded as follows,

fS R E ×R B ,γ ′ ≥ max θ∈(R E ×R B )\Z r * (θ).
As a second consequence, the fixed-rank fat-shattering dimension is lower bounded as follows.

Consider

r ∈ 1, |E| + |B| -N 1 -• • • -N L-1 . Let A r = {θ ∈ (R E × R B ) \ Z | r * (θ) = r}. If A r has non-empty interior, there is γ ′′ > 0 such that fS Ar,γ ′′ ≥ r.
The proof of the proposition is in Appendix C.5.

It consists first in obtaining local continuous differentiability, with an invertible square Jacobian matrix and second in applying the inverse function theorem. Variations of this second step were already carried out in the literature, in particular by [START_REF][END_REF].

Remark that the same proof would also apply to other measures of complexity, for instance the Vapnik-Chervonenkis (VC) dimension (Anthony und Bartlett, 2009, Chapter 3) of the binary classifiers indexed by θ and obtained by taking the sign of f θ -f θ 0 for any fixed θ 0 ∈ (R E × R B ) \ Z (with σ L as the identity).

Our motivation, for studying the fat-shattering dimension (or the VC-dimension), is their relationships with notions of generalization errors in machine learning, and with uniform convergence in probability and statistics, (see in particular Alon u. a. 1997; Bartlett und Long 1998;Colomboni u. a. 2023;Vapnik und Chervonenkis 1971 and references therein). In particular, Proposition 8 indicates that the computable full functional dimension r * (θ) can be seen as relevant for studying the generalization error of neural networks in machine learning.

Finally, remark that Bartlett u. a. (2019Bartlett u. a. ( , 1998)); Harvey u. a. (2017); Maass (1994) relate the global VC dimension of neural networks to their number of parameters (and their depths) while in Proposition 8 we consider local or global dimensions and relate them to the (smaller) computable full functional dimension.

Computational Considerations

In this section, we describe how to compute the quantities of this article in practice. In Section 6.1, we describe how one can efficiently compute rank(Df θ (X)) for a given X, and in Section 6.2 we explain how this allows to compute r * (θ) by sampling, for a sufficient number of samples.

How to Compute rank(Df θ (X))

For a given X ∈ R N 0 ×n and a given θ ∈ R E × R B , rank(Df θ (X)) is computed using the backpropagation and numerical linear algebra tools computing the rank of a matrix. To justify the computations, let us first recall the classical backpropagation algorithm for computing the gradients with respect to the parameters of the network, for a given loss Lo : R N L × R N L -→ R. We will then describe how to use the backpropagation to compute rank(Df θ (X)). We conclude with implementation recommendations.

For a given input x ∈ R N 0 and a given output y ∈ R N L , backpropagation computes the gradient ∇Lo(f θ (x), y) of the function θ -→ Lo(f θ (x), y). To do so, it first computes f θ (x) and stores the intermediate pre-activation values (y ℓ θ

) v = v ′ ∈V ℓ-1 w v ′ →v (f ℓ-1 θ (x)) v ′ + b v , for ℓ ∈ 1, L and v ∈ V ℓ .
This is known as the 'forward pass'. Then, backpropagation computes the vector of errors η L θ defined by

η L θ = Ä Jσ L (y L θ ) ä T ∂Lo ∂y 1 (f θ (x), y),
where ∂Lo ∂y 1 (f θ (x), y) ∈ R N L is the gradient of y 1 -→ Lo(y 1 , y), at the point (f θ (x), y), and Jσ L (y L θ ) is the Jacobian matrix of y L → σ L (y L ), at y L θ . This vector is then backpropagated, from ℓ = L to ℓ = 1 thanks to the equation

∀v ′ ∈ V ℓ-1 Ä η ℓ-1 θ ä v ′ = σ ′ ÄÄ y ℓ-1 θ ä v ′ ä v∈V ℓ w v ′ →v Ä η ℓ θ ä v ( 23
)
where σ ′ (t) = 1 if t > 0 and σ ′ (t) = 0 if7 t ≤ 0. This allows to recursively obtain the error vectors η ℓ θ ∈ R N ℓ , for all ℓ ∈ 1, L . We deduce the partial derivatives thanks to the formulas

∀ℓ ∈ 1, L , ∀v ′ ∈ V ℓ-1 , ∀v ∈ V ℓ , ∂Lo(f θ (x), y) ∂w v ′ →v = σ ÄÄ y ℓ-1 θ ä v ′ ä Ä η ℓ θ ä v and ∀ℓ ∈ 1, L , ∀v ∈ V ℓ , ∂Lo(f θ (x), y) ∂b v = Ä η ℓ θ ä v .
This allows computing the gradients for one example (x, y). For a batch, the algorithm is repeated for each example (x (i) , y (i) ), and the average of the so obtained gradients is computed.

Let us now make the connection between backpropagation and the computation of rank(Df θ (X)). Vectorizing both the input and output spaces of θ -→ f θ (X), we first notice that rank(Df θ (X)) = rank(Jf θ (X)), where the Jacobian matrix Jf ) is the Jacobian matrix of θ -→ f θ (x (i) ). We construct the matrix Jf θ (X) by successively computing each of its lines, i.e. computing each line of Jf θ (x (i) ) for all i ∈ 1, n . For a given i ∈ 1, n and v ∈ V L , the line corresponding to v of Jf θ (x (i) ) is indeed simply obtained as the transpose of ∇Lo v (f θ (x (i) ), y (i) ) for the function

θ (X) ∈ R nN L ×(|E|+|B|) takes the form Jf θ (X) = Ö Jf θ (x (1) ) . . . Jf θ (x (n) ) è and, for all i ∈ 1, n , Jf θ (x (i) ) ∈ R N L ×(|E|+|B|
Lo v : R N L × R N L -→ R defined by Lo v (y 1 , y 2 ) = (y 1 ) v , for all (y 1 , y 2 ) ∈ R N L × R N L . We indeed have Lo v (f θ ′ (x (i) ), y (i) ) = f θ ′ (x (i) ) v for all θ ′ . The gradient ∇Lo v (f θ (x (i) ), y (i)
) is obtained using the backpropagation algorithm described above. Notice that when σ L is the identity, for a given v ∈ V L , using the definition of Lo v , we always have (η

L θ ) v = 1 and (η L θ ) v ′ = 0 for all v ′ ̸ = v.
We need however to compute the forward pass in order to compute the vectors y ℓ θ , for ℓ ∈ 0, L -1 . Finally, once Jf θ (X) is computed its rank is obtained using standard linear algebra algorithms.

Our implementation uses the existing automatic differentiation of Tensorflow. It is possible to call the method GradientTape.gradients, which computes Jf θ (x) for a single example x, and to repeat it for each example x (i) . However, it is more efficient to use GradientTape.jacobian which allows to compute directly Jf θ (X). We do not report the details of the experiments here but we found even more efficient to cut X in sub-batches and repeatedly call GradientTape.jacobian, when appropriately choosing the size of the sub-batches.

Once Jf θ (X) built, the value of rank(Jf θ (X)) can be computed with the np.linalg.rank function of Numpy, or using the accelerated rank computation of Pytorch with a GPU, which improves the speed by some factors. Note that the limiting factor when computing rank(Jf θ (X)) for large networks and/or n large is the computation of the rank and not the construction of Jf θ (X).

The codes are available at (Bona-Pellissier u. a., 2023b).

How to Compute r * (θ)

In this section, our goal is to estimate the maximal rank r * (θ), see ( 20), from rank(Df θ (X)), where X ∈ R N 0 ×n is a random data set composed of n i.i.d samples. Such an estimate is already considered by Grigsby u. a. ( 2023). Intuitively, the bigger n is, the better the estimation. Indeed, we provide an upper bound on the probability that rank(Df θ (X)) < r * (θ) as a function of n, see Theorem 11. This probability also depends on the probability of generating an example in the least probable linear region of x -→ f θ (x). This result can be compared to the smallest possible sample size n * (θ) obtained if an optimal X ∈ R N 0 ×n * (θ) was provided by an oracle, see Proposition 9. This proposition proves that this smallest possible sample size n * (θ) has the order of magnitude of r * (θ). Before stating the proposition, we remind that, since the input space of Df θ (X) is always R E × R B , we always have8 r * (θ) ≤ |E| + |B|. Proposition 9. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

Let θ ∈ (R E × R B ) \ Z. Consider the sequence (r * n (θ)) n∈N * . There exists (a unique) n * (θ) ∈ N * such that this sequence is increasing for 1 ≤ n ≤ n * (θ) and stationary (constant) for n * (θ) ≤ n. Furthermore, if r * (θ) ̸ = 0, we also have

r * (θ) N L ≤ n * (θ) ≤ r * (θ).
The proof of the proposition is in Appendix D.1. As its proof shows, the following proposition is a direct consequence of Proposition 5. It already guarantees that, without any knowledge of the problem, a random X following a sufficiently spread distribution can be used to calculate r * n (θ) and therefore r * (θ). Its purpose is to illustrate how the statements in the previous sections can be used to calculate r * (θ). A better statement is given in Theorem 11.

Proposition 10. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

Let θ ∈ (R E × R B ) \ Z. Let n ∈ N * . The set {X ∈ X n θ | rank(Df θ (X)) = r * n (θ)} has non-zero Lebesgue measure (on R N 0 ×n ).
Proof of Proposition 10. From Proposition 5, there exists j ∈ I n (θ) such that r n j = r * n (θ). We then have the inclusion

{X ∈ X n θ | (X, θ) ∈ O n j } ⊆ {X ∈ X n θ | rank(Df θ (X)) = r * n (θ)}.
Since O n j is open, the left-hand set above is an open set, which is non-empty by definition of I n (θ), in (21). Hence, the right-hand set above has a non-zero Lebesgue measure.

Theorem 11. Consider any deep fully-connected ReLU network architecture (E, V, σ L ).

Let us consider a distribution G over R N 0 , that is absolutely continuous with respect to Lebesgue measure, with (strictly) positive density. Assume we sample randomly and independently the vectors

x (i) ∈ R N 0 , i ∈ 1, n , following the distribution G, for some n ∈ N * . Let θ ∈ (R E × R B ) \ Z and p = min δ∈A(θ) P Ä x (1) ∈ Int D δ (θ) ä ,
where A(θ) and D δ (θ) are defined in (15) and ( 14). Note that we have p > 0, because A(θ) is finite and, for all δ ∈ A(θ), D δ (θ) has nonempty interior.

Then the following holds.

1. Consider i.i.d. Bernoulli random variables B 1 , . . . , B n , with P(B 1 = 1) = p and P(B 1 = 0) = 1 -p. We have

P Ä rank Ä Df θ Ä (x (i) ) 1≤i≤n ää < r * (θ) ä ≤ P(B 1 + • • • + B n < n * (θ)).
2. As a consequence, if n ≥ 2n * (θ)/p,

P Ä rank Ä Df θ Ä (x (i) ) 1≤i≤n ää < r * (θ) ä ≤ 4 np .
The proof of the theorem is in Appendix D.2. A first consequence of the theorem is that if one simply adds columns to an input matrix X randomly and independently, the corresponding value of rank(Df θ (X)) will reach the computable full functional dimension, almost surely (this consequence alone could be seen/proved more simply). This can for instance help understand the experimental results of Grigsby u. a. ( 2023).

The theorem then provides two upper bounds (Items 1 and 2) on the probability of not reaching the computable full functional dimension, as a vanishing function of the number of columns n. A beneficial feature of these upper bounds is that they are based on p, the smallest probability of reaching a given region Int D δ (θ), relative to a given activation pattern δ, for a single column sample. Importantly, the probabilities of reaching several given activation patterns simultaneously over multiple samplings of the columns, which would be typically much smaller than p, are not involved.

Also, the upper bounds are based on n * (θ), the smallest number of columns for X such that we can have rank(Df θ (X)) = r * (θ). This is natural since the larger n * (θ), the more samples we need to have a non-zero probability of reaching the computable full functional dimension. Typically, for n of the order of magnitude of n * (θ) (for instance such that np ≳ 2n * (θ)), since n * (θ) is usually large, we already have a high probability that the lower-bound rank Ä Df θ Ä (x (i) ) 1≤i≤n ää coincides with r * (θ). The first upper bound (Item 1) is the tightest and most general. The second one (Item 2) simply follows from Chebyshev's inequality and is provided for the sake of obtaining a straightforward compact bound. Other upper bounds could be obtained simply from Item 1, using for instance the Hoeffding inequality.

Experiments

The experiments emphasize several aspects of the geometry-induced implicit regularization illustrated in Figure 2. The setting of the experiments is described in Section 7.1. In Section 7.2, we describe the results of an experiment in which we compute the functional dimensions as the number of parameters of the network grows. In Section 7.3, we compute functional dimensions throughout the learning phase. In Section 7.4, we investigate the impact of the corruption of the inputs of the learning sample on the functional dimensions. In Section 7.5, we perform the same experiment but corrupt the outputs of the learning sample.

The Python codes implementing the experiments described in this section are available at (Bona-Pellissier u. a., 2023b).

Experiments Description

In the experiments of Section 7.2, 7.3, 7.4 and 7.5, we evaluate the behavior of different complexity measures for the classification of a subpart of the MNIST data set.

We consider a fully-connected feed-forward ReLU network of depth L = 4, of widths (N 0 , N 1 , N 2 , N 3 , N 4 ) = (784, w, w, w, 10), for different values of w ∈ 1, 60 . The tested values of w depend on the experiment/section. The hidden layers (1, 2, 3) include a ReLU activation function. The last layer includes a soft-max activation function. We randomly extract a training sample (X train , Y train ), containing 6 000 images and a test sample (X test , Y test ) containing 20 000 images from MNIST.

For given w and (X train , Y train ), we tune the parameters of the network to minimize the cross-entropy. This is achieved using the Glorot uniform initialization for the weights while initializing the biases to 0, and using the stochastic gradient descent 'sgd' as optimizer with a learning rate of 0.1 and a batch size of 256. The number of epochs depends on the experiment/section.

In the figures presenting the results of the experiments, we display the following quantities:

• Max rank: the maximal theoretically possible value of rank(Df θ (X)) for any sample X and parameter θ. 2022), Theorem 7.1). With the architecture described above, for a given w, the Max_rank is equal to 2w 2 + 794w + 10. This is very close to the number of parameters 2w 2 + 797w + 10. Furthermore, with the values of w considered in the forthcoming experiments, the predominant term is 794w.

It is equal to |E| + |B| -N 1 -• • • -N L-1 = N 0 N 1 + N 1 N 2 + • • • + N L-1 N L +N L (
• Rank X_random: an estimation of the computable full functional dimension, according to the statement of Section 6.2, by computing rank(Df θ (X random )) with a random i.i.d. sample X random , where each example of the sample is a Gaussian random vector. The number of examples is equal to 20 000 or 40 000 depending on the experiment/section.

• Rank X_test: It corresponds to rank(Df θ (X test )), where X test is the test sample of size 20 000 introduced above. Note that the test set is bigger than the train set, in contrast to classical settings. Indeed, the test set serves two purposes here: it is classically used to compute the classification accuracy, but it is also meant to provide an estimation of the functional dimension over the distribution of the inputs (the MNIST images). The latter estimation differs from the estimation with X random which samples images outside the distribution of the inputs.

• Rank X_train: It corresponds to rank(Df θ (X train )), where X train is the training sample of size 6 000 mentioned above. This quantity is the batch functional dimension.

• Train loss: the value of the training loss at the end of the training (resp. at the current epoch) in Sections 7.2, 7.4 and 7.5 (resp. in Section 7.3).

• Test error: the proportion of images of X test that are misclassified by the network.

• Train error: the proportion of images of X train that are misclassified by the network.

Behavior of the Functional Dimensions as the Network Width Increases

In this experiment, we evaluate the functional dimensions when the width w varies between 1 and 85. More precisely, we test all w between 1 and 9, then all w between 10 and 18 with an increment of 2, and then all w between 20 and 85 with an increment of 5. Overall, the number of parameters of the network varies between 809 and 82 205 As described in Section 7.1, we randomly extract a training sample (X train , Y train ) of size 6 000 and a test sample (X test , Y test ) of size 20 000 from MNIST. The size of the i.i.d Gaussian sample X random is 40 000. We optimize the network parameters during 1 000 epochs.

The results of the experiment are in Figure 3. When increasing the number of parameters, the train loss, the train error and the test error decrease. For w ≥ 12, i.e. when the number of parameters is superior or equal to 9 862, the train error is equal to 0: the network is able to fit perfectly the training images. However, the test error continues to decrease even after the train error reaches 0: from 0.101 when w = 12 to 0.058 when w = 85.

As we can see, the quantity rank(Df θ (X random )) in the case of the 40 000 inputs generated as Gaussian vectors, X random , is nearly always equal to its maximum theoretical value Max_rank. This indicates first that r * (θ) is equal to its maximal theoretical value, and second that rank(Df θ (X random )) provides here a good estimation of r * (θ). Furthermore, according to Bona-Pellissier u. a. ( 2022), the networks parameters are locally identifiable from X random in this case.

The ranks rank(Df θ (X train )) and rank(Df θ (X test )) are nearly equal when the number of parameters is smaller than 21 185 (w = 25). For these sizes, it seems to indicate that rank(Df θ (X test )) is indeed equal to the functional dimension over the distribution of inputs, and that rank(Df θ (X train )) already attains it, which means that adding MNIST images to X train would not increase rank(Df θ (X train )). It thus also suggests that the functional dimension over the distribution of inputs (the MNIST images) is smaller than r * (θ) which consider all X inside but also outside of this distribution, and which, as we have seen in the previous paragraph, is maximal here. In the light of Bona-Pellissier u. a. ( 2022), this also shows that θ is not locally identifiable from X train nor X test . This suggests that for these networks and the MNIST dataset, using only samples of the input distribution does not allow to identify the parameters of a network, and one needs to add examples outside the input distribution.

Then, for more than 21 185 parameters, a gap appears between the two ranks rank(Df θ (X train )) and rank(Df θ (X test )), i.e. rank(Df θ (X train )) is smaller than the functional dimension over the distribution of the inputs. Furthermore, while both ranks are not far from the maximum rank for small numbers of parameters, the gap increases with the number of parameters, to the point where the shape of the curves seem to diverge: while the maximum rank is nearly proportional to the number of parameters, the ranks rank(Df θ (X train )) and rank(Df θ (X test )) seem to increase less and less with the number of parameters. This is the consequence of the geometry-induced implicit regularization described in Section 4.2 and Figure 2. The regularization on the training sample seems to also concern the input distribution in general as the curve rank(Df θ (X test )) indicates.

Behavior of the Functional Dimensions During Training

We consider the setting described in Section 7.1, where we fix the value of w to 30. For this experiment, we keep the original MNIST images and labels in (X train , Y train ) and (X test , Y test ) and we set the size of the random set X random to 20 000. The architecture is (784,30,30,30,10), which corresponds to a total number of parameters equal to 25 720. The quantities plotted in the previous experiment (see Figure 3) are computed after the training is done. In contrast, here, we fix a total number of epoch to 3 000 and we compute the same quantities during training, throughout the epochs.

More precisely, we study the quantities Max rank, Rank X_random, Rank X_test, Rank X_train, Train loss, Test error and Train error, as described in Section 7.1. They are computed at the epochs {40, 80, 120, 160, 200, 240, 280, 320, 360, 400}∪{600, 800, 1000, 1200, 1400}∪ {1800, 2200, 2600, 3000}. We plot these quantities in Figure 4.

We plot the train loss (on the left), which decreases throughout the epochs, and the train error (on the right), which decreases and reaches 0 at epoch 120, after which all training images are always correctly classified. The test error decreases the most in the first 80 epochs, after which it continues to decrease, although at a slower pace.

At the beginning of the training, the quantity rank(Df θ (X random )) is equal to the 2022), when rank(Df θ (X random )) is maximal, the parameterization θ is locally identifiable from the sample X random . On the contrary, the gap observed here at the end of the training indicates some lack of identifiability from X random . We observe that the value of rank(Df θ (X train )) consistently decreases during training. Such a behavior is consistent with the geometric interpretation of Section 4.2 and 4.3, and Figure 2. The value of rank(Df θ (X test )) also decreases, with a more gentle slope. This indicates that the geometry-induced implicit regularization occurring on the training sample is 'communicated' to the test sample.

Behavior of the Functional Dimensions when X is Corrupted

We consider the same setting as the experiments of Section 7.1, with w = 30, which corresponds to a total number of parameters equal to 25 720.

The network is trained, during 3 000 epochs, repeatedly over different train sets of size 6 000 made of MNIST images. We add to the train images a Gaussian noise, before clipping the values of the pixels between 0 and 1, to stay consistent with black and white images. We do the same for the test images. This blurs the input distribution. For each training, we use a different noise variance, which overall varies between 10 -3 and 1. We represent visually an image with different levels of noise in Figure 5. The network is trained to the point it is able to interpolate the training examples: for all the settings, the final train error is equal to 0.

Once the training is done, we compute the quantities Max rank, Rank X_random, Rank X_test, Rank X_train, Test error, and Train error described in Section 7.1, for the different noise levels. The size of X random is 20 000. We plot these quantities in Figure 6.

As already said, the expressiveness of the network permits to fit the learning data perfectly. The training error is zero for all noise levels. However, the noise has two effects: an effect on the distribution of inputs which becomes more complex, and an effect on the difficulty of the problem. Indeed, as is reflected by the increase in the test error, the problem becomes more difficult. The curve representing rank(Df θ (X train )) also increases, and gets close to the maximum rank for a noise amplitude getting close to 1. This phenomenon is coherent with the fact that the batch functional dimension is linked to activation patterns, which are linked to the distribution of the inputs, which -as already said-are made more complex by the noise. The quantity rank(Df θ (X test )) also increases, but for smaller noises than X train . It oscillates close to the maximum rank.

Behavior of the Functional Dimensions when Y is Corrupted

We consider the setting described in Section 7.1, for three different values of w, equal to 30, 50 and 60 respectively. The first experiment carried out was the one with the width w = 30, in harmony with the experiments of Sections 7.3 and 7.4, and we then added the cases w = 50 and w = 60 to see the impact of the width on this experiment. Following Neyshabur u. a. (2017); Zhang u. a. ( 2021), we study what happens when part of the labels of the training set are corrupted with random labels. The network is trained repeatedly over different train sets of size 6 000 made of MNIST images. A varying number of the labels associated with the training images are set to a random value, according to the uniform distribution over {0, 1, . . . , 9}. The quantity of images with random labels varies from 0 to 4 500. Each time, the network is trained to the point where it interpolates the training set, even with the random labels.

Intuitively, the more corrupted labels there are, the more complex the function interpo-lating the training data should be. The distribution of the inputs is however the same and it is not clear if the linear regions, defined by the activation patterns, and used to describe the interpolating function need to change much when corruption increases. Another interpretation is that depending on the level of corruption, we select different global minimizers of the empirical risk with respect to the 1500 images that always remain clean. The purpose of this experiment is to see if the functional dimension increases with the proportion of corrupted labels and the test error, when w is such that implicit regularization occurs. The quantities Max_rank, Rank_X_random, Rank_X_test, Rank_X_train, Train loss, Test error and Train error are described in Section 7.1. We plot these quantities as a function of the number of corrupted labels in Figure 7 for three different values of w. The case w = 30, is described in Section 7.5.1, and the case w = 50 is described in Section 7.5.2.

Observations when w = 30

Consistently with Sections 7.3 and 7.4, we take w = 30, which corresponds to a number of parameters equal to 25 720. The size of the test set X test and of the random Gaussian inputs X random are both equal to 20 000. The learning performs 3 000 epochs. The plots associated to this experiment correspond to the left side of Figure 7.

As expected, the test error (the proportion of images in X test that are misclassified) increases with the number of corrupted labels: from 0.08 when no label is corrupted to 0.73 when 4500 images out of 6000 have random labels.

In this experiment, again, we observe that rank(Df θ (X random )) is often equal to the maximum rank, which is here equal to 25630. For numbers of corrupted labels equal to 500 and 1500, we observe that the value is slightly lower.

Although we can observe a clear increase of the ranks rank(Df θ (X train )) and rank(Df θ (X test )) between 0 and 500 corrupted labels, for a greater number of corrupted labels these quantities are relatively stable and do not seem to be much affected by the corruption of the labels. We try to clarify this observation by performing two other experiments with a bigger width w in the following section.

Observations when w = 50 and w = 60

To better understand the impact of label corruption on the functional dimension, we repeat the previous experiment twice, this time with widths w set to 50 and 60, corresponding to a number of parameters equal to 44860 and 55030 respectively. This corresponds to points on the right of curve on fig. 3, where implicit regularization occurs the most. We keep the sizes of X train and X test to 6000 and 20000 respectively, and we increase the size of X random to 40000. The plots associated with this experiment correspond to the right side of Figure 7.

We observe similar train and test errors as in 7.5.1. We also observe similarly that rank(Df θ (X random )) is often equal to the maximum rank (but note that we increase the size of X random here).

For these two widths, the increase of both quantities rank(Df θ (X train )) and rank(Df θ (X test )) is clearer, in particular in the case of X train . Overall, the experiments 7.5.1 and 7.5.2 indicate that there is a positive correlation between the functional dimensions and the complexity of the function learned by the neural network.

Conclusion and perspectives

In this article, we describe the local geometry of deep ReLU neural networks. The study shows that the image of a sample X by deep ReLU neural networks of a fixed architecture is a set whose local dimension varies. The local dimension is called the batch functional dimension by Grigsby u. a. (2022). We show that the parameter space is divided into pieces where the batch functional dimension is fixed. Empirically, the pieces of small dimensions are on the outside of the ones of large dimensions. They are favored by the optimization. We call this phenomenon geometry-induced implicit regularization. When X is allowed to vary, we also study the maximal dimension over all possible X. We call it the computable full functional dimension. Both notions of local complexity are determined by the activation patterns. We investigate the practical computation of the functional dimensions and provide experiments emphasizing the geometry-induced implicit regularization and the link between functional dimensions and the complexity of the learning task.

This opens up many perspectives in deep learning theory. The formal connection between the notions of local complexity and the generalization gap is still missing. It would permit us to obtain a theory that explains the good performance of deep learning. It would be interesting to study more systematically how the functional dimensions of the learned parameters depend on the distribution of the learned phenomenon. To do so, it would be interesting to study instances in larger dimensions. Algorithms of a better complexity for computing the functional dimensions are needed. In particular, since we have proved that the batch functional dimension is almost-surely determined by the activation patterns, it would be interesting to compute the former using the activation patterns instead of the gradients.

A Proofs of Section 3

This appendix is devoted to the proofs of Section 3. In Section A.1, we prove Theorem 1, and in Section A.2 we prove Proposition 2.

A.1 Proof of Theorem 1

Let us define, for ℓ ∈ 1, L -1 and v ∈ V ℓ the set

T v = (x, θ) ∈ R N 0 × (R E × R B ) | v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v = 0 , ( 24
)
and let

T = ∪ L-1 ℓ=1 ∪ v∈V ℓ T v . ( 25
)
Similarly, for any x ∈ R N 0 , ℓ ∈ 1, L -1 and v ∈ V ℓ , we define the set

T x v = θ ∈ R E × R B | v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v = 0 ,
and let

T x = ∪ L-1 ℓ=1 ∪ v∈V ℓ T x v . Lemma 12. (i) -Over R N 0 ×(R E ×R B ), the function (x, θ) -→ a(x, θ) ∈ {0, 1} N 1 +•••+N L-1 takes exactly 2 N 1 +•••+N L-1 distinct values. -For any δ ∈ {0, 1} N 1 +•••+N L-1 , we write A δ = {(x, θ) ∈ R N 0 × (R E × R B ) | a(x, θ) = δ}, ( 26
)
which is thus nonempty. Then: On A δ , the function (x, θ) -→ f θ (x) is analytic.

-The set T has Lebesgue measure zero and ∪ δ∈{0,

1} N 1 +•••+N L-1 ∂A δ = T . Therefore, for any δ ∈ {0, 1} N 1 +•••+N L-1 , ∂A δ is a closed set of Lebesgue measure zero in R N 0 × (R E × R B ).
(ii) -For any fixed x ∈ R N 0 , the function θ -→ a(x, θ) exactly takes 2

N 1 +•••+N L-1 distinct values. -For x ∈ R N 0 and δ ∈ {0, 1} N 1 +•••+N L-1 , we write A x δ = {θ ∈ R E × R B | a(x, θ) = δ}. Then: On A x δ , the function θ -→ f θ (x) is analytic. -The set T x has Lebesgue measure zero and ∪ δ∈{0,1} N 1 +•••+N L-1 ∂A x δ = T x . There- fore, for any δ ∈ {0, 1} N 1 +•••+N L-1 , ∂A x δ is a closed set with Lebesgue measure zero in R E × R B .
Proof of Lemma 12. To avoid repetitions, we only detail the proof of (i). The proof of (ii) is very similar, considering functions of θ only (with x fixed) rather than (x, θ).

We first prove the first item, i.e. we prove that all activation patterns are reached. The set {0,

1} N 1 +•••+N L-1 is finite and its cardinal is 2 N 1 +•••+N L-1 . Observe that for any δ ∈ {0, 1} N 1 +•••+N L-1 , by taking θ ∈ R E × R B such that w v→v ′ = 0 for any (v → v ′ ) ∈ E, b v = 0 for v ∈ V L and b v = (-1) 1+δv for any v ∈ V 1 ∪ • • • ∪ V L-1 , then, for any x ∈ R N 0 and any v ∈ V 1 ∪ • • • ∪ V L-1 , we have a v (x, θ) = δ v , i.e. a(x, θ) = δ.
In order to prove the second item, i.e. that the function (x, θ) -→ f θ (x) is analytic, we remind the definition of f ℓ θ , in (1), and we define

a ≤ℓ (x, θ) = ® (a v (x, θ)) v∈V 1 ∪•••∪V ℓ if ℓ ≥ 1, 1 if ℓ = 0.
We prove by induction that the assertion

H ℓ : ß ∀D ⊆ R N 0 × (R E × R B ), if (x, θ) -→ a ≤ℓ (x, θ) is constant on D, then (x, θ) -→ f ℓ θ (x) is polynomial on D holds, for all ℓ ∈ 0, L -1 . The assertion H 0 indeed holds because f 0 θ (x) = x is polynomial in (x, θ) (of degree 1) on any subset of R N 0 × (R E × R B ). Assume now that for some ℓ ∈ 1, L -1 , H ℓ-1 holds, and let us prove H ℓ . Let D ⊆ R N 0 × (R E × R B ) such that a ≤ℓ (x, θ) is constant on D. For (x, θ) ∈ D and v ∈ V ℓ , using (6), we have Ä f ℓ θ (x) ä v =a v (x, θ) Ñ v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v é .
The quantity a ≤ℓ-1 (x, θ) is constant on D and thus from , θ). This concludes the proof by induction that H ℓ holds for all ℓ ∈ 0, L -1 .

H ℓ-1 , for all v ′ ∈ V ℓ-1 , (x, θ) -→ (f ℓ-1 θ (x)) v ′ is a polynomial function of (x, θ) on D. Since a v (x, θ) is constant on D, f ℓ θ (x) v is a polynomial function of (x
If we recall from (1) that y

L θ (x) ∈ R N L is the vector satisfying, for all v ∈ V L , (y L θ (x)) v = v ′ ∈V L-1 w v ′ →v (f L-1 θ (x)) v ′ + b v , we have f θ (x) = σ L (y L θ (x)). We recall the notations A δ , δ ∈ {0, 1} N 1 +•••+N L-1 , in (26). For δ ∈ {0, 1} N 1 +•••+N L-1 , a ≤L-1 (x, θ) = a(x, θ) is constant on A δ and thus from H L-1 , (x, θ) -→ f L-1 θ (x) is poly- nomial on A δ . As a consequence, (x, θ) -→ y L θ (x) is polynomial on A δ ,
and since σ L is analytic, (x, θ) -→ f θ (x) is analytic on A δ . This proves the second item of Lemma 12, (i).

Let us now show the third item, which states that T has Lebesgue measure zero. For that, let us show that for all ℓ ∈ 1, L -1 and v ∈ V ℓ , T v has Lebesgue measure zero. To do so, since

∪ δ A δ = R N 0 × (R E × R B ), we consider ℓ ∈ 1, L -1 and v ∈ V ℓ , and prove that, for all δ ∈ {0, 1} N 1 +•••+N L-1 , T v ∩ A δ has Lebesgue measure zero. For δ ∈ {0, 1} N 1 +•••+N L-1 , a ≤ℓ-1 (x, θ) is constant on A δ and thus from H ℓ-1 , (x, θ) -→ f ℓ-1 θ (x) is a polynomial function of (x, θ) on A δ and thus v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v also is. Since the variable (x, θ) → b v is not present in the expression of f ℓ-1 θ (x)
, it only appears in a single monomial of degree and coefficient 1 of

v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v .
The latter polynomial function is therefore non-constant. Hence the set T v ∩ A δ , constituted by the zeros of this polynomial function, has Lebesgue measure zero. Since

∪ δ A δ = R N 0 × (R E × R B ), we finally conclude that, for any ℓ ∈ 1, L -1 and v ∈ V ℓ , T v has Lebesgue measure zero.
The set

T = ∪ L-1 ℓ=1 ∪ v∈V ℓ T v is thus also of Lebesgue measure zero.
Let us now prove the set equality:

δ ∂A δ = T . ( 27
)
We first show the inclusion

δ ∂A δ ⊆ T . Consider δ ∈ {0, 1} N 1 +•••+N L-1 and let us now show that ∂A δ ⊆ T . To do so, consider (x, θ) ∈ ∂A δ . Since (x, θ) ̸ ∈ Int(A δ ), for any ε there exists δ ε ̸ = δ such that B((x, θ), ε) ∩ A δε ̸ = ∅.
Since the set of all possible δ ε is finite, we are sure that there exists

δ ′ ̸ = δ such that (x, θ) ∈ A δ ′ . Let ℓ ∈ 1, L -1 and v ∈ V ℓ such that δ v ̸ = δ ′ v .
We assume without loss of generality that δ v = 0. The proof is indeed similar when

δ v = 1. There exists (x n , θ n ) ∈ A N * δ such that (x n , θ n ) → (x, θ) as n → ∞ and there exists (x ′ n , θ ′ n ) ∈ A N * δ ′ such that (x ′ n , θ ′ n ) → (x, θ) as n → ∞. We have a v (x n , θ n ) = 0 and a v (x ′ n , θ ′ n ) = 1 for all n. Using that (x, θ) -→ v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v
is continuous and taking the limit of this function at (x n , θ n ), as n goes to infinity, we obtain that

v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v ≤ 0. Reasoning similarly with the sequence (x ′ n , θ ′ n ) n∈N * we obtain the reverse inequality and conclude that v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v = 0. This shows that (x, θ) ∈ T v ⊆ T . This finishes the proof of ∂A δ ⊆ T . Let us now show the reciprocal inclusion T ⊆ δ ∂A δ . Indeed, let (x, θ) ∈ T . There exist ℓ ∈ 1, L -1 and v ∈ V ℓ such that (x, θ) ∈ T v . There also exists δ ∈ {0, 1} N 1 +•••+N L-1 such that (x, θ) ∈ A δ . In particular, since v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v = 0, we have δ v = a v (x, θ) = 1. For any ε > 0, by replacing b v by b v -ε, we obtain a θ ε satisfying ∥θ -θ ε ∥ ≤ ε and a v (x, θ ε ) = 0 ̸ = δ v , which shows (x, θ ε ) ̸ ∈ A δ . This shows (x, θ) ∈ ∂A δ ⊆ δ ∂A δ .
This shows the desired inclusion, and thus the equality (27).

For all δ ∈ {0,

1} N 1 +•••+N L-1
, ∂A δ is closed by definition of a boundary. Since T has been shown to have Lebesgue measure zero, then ∂A δ has Lebesgue measure zero and thus the proof of the part (i) is concluded.

We state and prove another lemma before proving Theorem 1. The lemma resembles Theorem 1 but does not include the statements on rank(Df θ (X)).

For n ∈ N * , recalling the definition T in (25), let us now define

T n = ∪ n i=1 (X, θ) ∈ R N 0 ×n × (R E × R B ) (x (i) , θ) ∈ T . ( 28
)
Similarly, for n ∈ N * and X ∈ R N 0 ×n , we define

T X = ∪ n i=1 ¶ θ ∈ R E × R B | (x (i) , θ) ∈ T © . Lemma 13. (i) For all n ∈ N * , the sets ‹ O n 1 , . . . , ‹ O n mn defined
-for all j ∈ 1, m n , the function (X, θ) -→ a(X, θ) is constant on each ‹ O n j and takes m n distinct values on ∪ mn j=1 ‹ O n j ; -for all j ∈ 1, m n , (X, θ) -→ f θ (X) is an analytic function on ‹ O n j .
(ii) For all n ∈ N * , for all X ∈ R N 0 ×n , the sets U X 1 , . . . , U X p X defined in (10) are non-empty, open and disjoint, and they satisfy

- Ä ∪ p X j=1 U X j ä c = T X , and in particular the complement Ä ∪ p X j=1 U X j ä c is a closed set with Lebesgue measure zero;
for all j ∈ 1, p X , the function θ -→ a(X, θ) is constant on each U X j and takes p X distinct values on ∪ p X j=1 U X j ; -for all j ∈ 1, p X , θ -→ f θ (X) is an analytic function on U X j .

Proof of Lemma 13. As in the proof of Lemma 12, the proofs of (i) and (ii) are very similar.

To avoid repetitions, we only detail the proof of (i). By definition, see (7), the sets ‹ O n 1 , . . . , ‹ O n mn are non-empty, open and disjoint. Before proving the first point of (i), let us notice that T n is of Lebesgue measure zero. Indeed, the third item of Lemma 12 states that T has Lebesgue measure zero, and therefore, we see in the definition (28) that T n is a finite union of zero-measured sets, which shows that it itself has Lebesgue measure zero. Let us also write the following useful characterization: thanks to the characterization of T in the third item of Lemma 12 (i), we have

T n = ∪ n i=1 ∪ δ∈{0,1} N 1 +•••+N L-1 ¶ (X, θ) ∈ R N 0 ×n × (R E × R B ) | (x (i) , θ) ∈ ∂A δ © . ( 29
)
Let us now show the first point of (i). Let us prove that (∪ mn j=1

‹ O n j ) c = T n . To do so, let us first show that (∪ mn j=1 ‹ O n j ) c ⊆ T n . Let (X, θ) ∈ (∪ mn j=1 ‹ O n j ) c . Consider the ∆ n 1 , . . . , ∆ n q defined just before (7). There exists j ∈ 1, q such that a(X, θ) = ∆ n j . Since (X, θ) ̸ ∈ ‹ O n j , there exists a sequence (X k , θ k ) k∈N * such that (X k , θ k ) → (X, θ), as k → ∞ and a(X k , θ k ) ̸ = ∆ n j , for all k.
Modulo the extraction of a sub-sequence, we can assume that there exist i ∈ 1, n such that for all k ∈ N * , a(x

(i) k , θ k ) ̸ = δ, where x (i)
k is the i th column of X k , and where we denote δ = (∆ n j ) i . Thus, we have (x

(i) k , θ k ) ̸ ∈ A δ ,
for all k, and since (x (i) , θ) ∈ A δ , we conclude (x (i) , θ) ∈ ∂A δ . The characterization (29) thus shows (X, θ) ∈ T n . This shows (∪ mn j=1 The second point of (i) holds by definition of 7) and the latter is of the form (δ 1 , . . . , δ n ) with

‹ O n j ) c ⊆ T n . Let us now show that T n ⊆ (∪ mn j=1 ‹ O n j ) c . If (X, θ) ∈ T n , there exists i ∈ 1, n and δ ∈ {0, 1} N 1 +•••+N L-1 such that (x (i) , θ) ∈ ∂A δ . Thus, for any ε > 0, (x, θ ′ ) -→ a(x, θ ′ ) is not constant over B((x (i) , θ), ε).
‹ O n 1 , . . . , ‹ O n mn . Let us now show the third point of (i). Let j ∈ 1, m n . The function (X, θ) -→ a(X, θ) is constant on ‹ O n j . The set ‹ O n j is associated to ∆ n j in (
δ i ∈ {0, 1} N 1 +•••+N L-1 for i ∈ 1, n . Fix i ′ ∈ 1, n . Then for X = (x (i) ) i∈ 1,n with (X, θ) ∈ ‹ O n j , (x (i ′ ) , θ) ∈ A δ i ′ . Hence, Lemma 12 (i) shows that f θ (x (i ′ )
) is an analytic function of (x (i ′ ) , θ) and thus of (X, θ). The quantity f θ (X) is a matrix whose columns are

f θ (x (i) ), i ∈ 1, n . Hence (X, θ) -→ f θ (X) is an analytic function on ‹
O n j , which concludes the proof of (i).

Proof of Theorem 1. Again, the proofs of (i) and (ii) are very similar and we only detail the proof of (i).

Consider

X, θ) -→ f θ (X) is analytic over ‹ O n j (by Lemma 13 (i)), the function (X, θ) -→ Df θ (X) is continuous over ‹ O n j .
Since the rank is lower semicontinuous, if rank(Df θ (X)) = r n j , then there exists ϵ > 0 such that for any (X ′ , θ ′ ) ∈ B((X, θ), ϵ), we have rank(Df θ ′ (X ′ )) ≥ r n j , which by maximality of r n j , is equivalent to rank(Df θ ′ (X ′ )) = r n j and to (X ′ , θ ′ ) ∈ O n j . This shows that O n j is open. Hence Item 4 holds. Item 6 comes directly from Lemma 13 and from the inclusion O n j ⊆ ‹ O n j . To finish the proof, we need to prove Item 5, stating that

Ä ∪ mn j=1 O n j ä c is a closed set with
Lebesgue measure zero. Let us consider a basis (e 1 , . . . , e |E|+|B| ) of R E × R B and a basis (ε 1 , . . . , ε nN L ) of R N L ×n . For all X, let us write M θ (X) for the matrix of the differential Df θ (X) of the function θ -→ f θ (X) in these two bases. Then (X, θ) -→ M θ (X) is an

analytic function on ‹ O n j . Recall the notation r n j = max (X,θ)∈ ‹ O n j rank(Df θ (X)), and let (X ′ , θ ′ ) ∈ ‹ O n j such that rank(Df θ ′ (X ′ )) = r n j .
We thus have rank(M θ ′ (X ′ )) = r n j , and thus there exists a sub-matrix

N θ ′ (X ′ ) of M θ ′ (X ′ ), of size r n j × r n j , such that det N θ ′ (X ′ ) ̸ = 0. The function (X, θ) -→ M θ (X) is an analytic function on ‹
O n j and thus (X, θ) -→ det(N θ (X)) also is. This latter function is not uniformly zero on ‹ O n j and thus the set of its zeros, that we write Y j , is a closed set of Lebesgue measure zero (Mityagin, 2020).

For all (X, θ) ∈ ‹ O n j \ Y j , we have det N θ (X) ̸ = 0 and thus rank(N θ (X)) = r n j and thus rank(M θ (X)) ≥ r n j . We also have rank

(M θ (X)) = rank(Df θ (X)) ≤ r n j by definition of r n j . Hence rank(Df θ (X)) = r n j . This shows ‹ O n j \ Y j ⊆ O n j . Finally, Ä ∪ mn j=1 O n j ä c = ∩ mn j=1 O n j c ⊆ ∩ mn j=1 Ä ‹ O n j \ Y j ä c = ∩ mn j=1 ÄÄ ‹ O n j ä c ∪ Y j ä ⊆ ∩ mn j=1 ÄÄ ‹ O n j ä c ∪ Ä ∪ mn j ′ =1 Y j ′ ää = Ä ∩ mn j=1 Ä ‹ O n j ä c ä ∪ Ä ∪ mn j=1 Y j ä = Ä ∪ mn j=1 ‹ O n j ä c ∪ Ä ∪ mn j=1 Y j ä .
We know from Lemma 13 that

Ä ∪ mn j=1 ‹ O n j ä c has Lebesgue measure Also each Y j has
Lebesgue measure zero, thus ∪ mn j=1 Y j has Lebesgue measure zero. Hence,

Ä ∪ mn j=1 O n j ä c has
Lebesgue measure zero, which concludes the proof of (i) in the theorem.

A.2 Proof of Proposition 2

Let us prove more than Proposition 2. We in fact prove the following proposition. Proposition 2 simply corresponds to the first item, but it is convenient to prove the others items at the same time, which will be useful in the proofs of other results.

Proposition 14. Consider any deep fully

-connected ReLU network architecture (E, V, σ L ). Let θ, θ ∈ R E × R B . Assume θ ∼ θ.
Then for any n ∈ N * and X ∈ R N 0 ×n :

1. if the differential Df θ (X) is well-defined, then the differential Df θ (X) is well-defined, and in that case we have

rank Df θ (X) = rank(Df θ (X)); 2. if there exists j ∈ 1, m n , such that (X, θ) ∈ ‹ O n j , then there exists j ′ ∈ 1, m n such that (X, θ) ∈ ‹ O n j ′ ;
3. if there exists j ∈ 1, m n , such that (X, θ) ∈ O n j , then there exists j ′ ∈ 1, m n such that (X, θ) ∈ O n j ′ .

Proof. Let θ ∼ θ, let n ∈ N * and let X ∈ R N 0 ×n . Let us prove the three items of the proposition.

Let us prove the first item. By definition of the relation ∼, in Section 2, there is an invertible linear map M : R E × R B -→ R E × R B such that θ = M θ. Note that when expressed in the canonical basis of R E × R B , the matrix corresponding to M is the product of a permutation matrix and a diagonal matrix, with strictly positive diagonal components whose values are given by ( 4) and ( 5). Notice that since M corresponds to positive and neuron permutations, as discussed after (5), we have,

for any θ ′ ∈ R E × R B , f θ ′ (X) = f M θ ′ (X). ( 30
)
Assume that Df θ (X) is well-defined, i.e. the map θ ′ → f θ ′ (X) is differentiable at θ. Then, for all u ∈ R E × R B , the following calculation holds, using the fact that M is invertible, using (30) and using (3),

f θ+u (X) = f M θ+u (X) =f M (θ+M -1 u) (X) =f θ+M -1 u (X) =f θ (X) + Df θ (X)(M -1 u) + o(∥M -1 u∥) =f θ (X) + Df θ (X)(M -1 u) + o(∥u∥). Hence, θ ′ -→ f θ ′ (X) is differentiable at θ and for all u ∈ R E × R B , Df θ (X)(u) = Df θ (X)(M -1 u).
Since M -1 is invertible, it follows that rank Df θ (X) = rank(Df θ (X)). This concludes the proof of the first item.

Let us now prove the second and the third items. Let j ∈ 1, m n such that (X, θ) ∈ ‹ O n j . Again, let us consider the map M defined above. For any θ ′ ∈ R E × R B , it is well-known (see for instance Bona-Pellissier u. a. 2023a, Proposition 39, Item 2) that since θ ′ and M θ ′ are equivalent modulo permutation and positive rescaling, for any x ∈ R N 0 , we have a(x, M θ ′ ) = P a(x, θ ′ ), for some permutation matrix P ∈ {0,

1} (N 1 +•••+N L-1 )×(N 1 +•••+N L-1 )
that only depends on M and not on x.

Since (X, θ) ∈ ‹ O n j , recalling the definition (7), there exists an open neighborhood ‹ U of (X, θ) such that for any (X , θ). This shows that there exists j ′ ∈ 1, m n such that ∆ n j ′ = P ∆ n j and (X, θ) ∈ ‹ V ⊆ ‹ O n j ′ . This proves the second item. Finally, if we furthermore assume (X, θ) ∈ O n j , applying Theorem 1, we see that the function (X ′ , θ ′ ) -→ rank(Df θ ′ (X ′ )) is locally constant at (X, θ): there exists an open neighborhood of (X, θ), U ⊆ ‹ U , such that U ⊆ O n j and thus, for all (X ′ , θ ′ ) ∈ U , we have rank(Df θ ′ (X ′ )) = r n j . Thus, applying the invertible map M , which preserves the rank as shown in the first item, this shows that (X ′ , θ ′ ) -→ rank(Df θ ′ (X ′ )) is also constant on

′ , θ ′ ) ∈ ‹ U , we have a(X ′ , θ ′ ) = ∆ n j . For any (X ′ , θ ′ ) ∈ ‹ U , we have a(X ′ , M θ ′ ) = P a(X ′ , θ ′ ) = P ∆ n j . Furthermore, since M is invertible, the map M defined by (X ′ , θ ′ ) → (X ′ , M θ ′ ) is invertible, and the image ‹ V of ‹ U by M is thus an open neighborhood of (X
V = M (U ) (note that V ⊆ ‹ V ),
which is an open set and which contains (X, θ) = M (X, θ). Since V ⊆ ‹ O n j ′ , this shows that rank Df θ (X) = r n j ′ because r n j ′ is the only value that can be taken on a subset of ‹ O n j ′ of non-zero Lebesgue measure. In other words, we have (X, θ) ∈ O n j ′

(and in particular we have shown r n j = r n j ′ ).

B Calculations for the Example in Section 4.1

We provide in this appendix, the calculations permitting to construct Figure 1. We consider a one-hidden-layer neural network of widths (1, 1, 1), with the identity activation function on the last layer. To simplify notations, we denote the weights and biases θ = (a, b, c, d) ∈ R 4 so that f θ (x) = bσ(ax + c) + d, for all x ∈ R. We consider X = (0, 1, 2) ∈ R 1×3 and

f θ (X) T = Ñ bσ(c) + d bσ(a + c) + d bσ(2a + c) + d é .
The boundaries of the sets U X j , corresponding to the parameters having the same activation pattern, are defined by the equation c = 0, a + c = 0 and 2a + c = 0. There are 6 possible activation patterns corresponding to the zones represented, in the (a, c) plane, on the left of Figure 1.

Since the sets f U X j (X) = {f θ (X) | θ ∈ U X j }, for j ∈ 1, 6 , are invariant to translations by vectors (d, d, d), for d ∈ R, we consider the plane P orthogonal to the vector (1, 1, 1) and parameterize its elements using the mapping p : R 2 -→ P

(x, y) -→ x √ 6 (1, 1, -2) + y √ 2 (-1, 1, 0).
Instead of representing f U X j (X), we represent on the right of Figure 1 its intersection with P, formally defined as the set

V j ⊆ R 2 such that f U X j (X) = p(x, y) + (z, z, z) ∈ R 1×3 | (x, y) ∈ V j and z ∈ R .
Below, we construct the sets V j , for j ∈ 1, 6 .

Case j = 1: We have c ≤ 0, 2a + c ≤ 0 and therefore a + c ≤ 0. This leads to f (a,b,c,d) (X) = (d, d, d) and V 1 = {(0, 0)}.

Case j = 2: We have c ≥ 0, a + c ≤ 0 and therefore 2a + c ≤ 0. This leads to f (a,b,c,d) (X) = (bc + d, d, d) and d, d, d) .

V 2 = (x, y) ∈ R 2 | ∃(a, b, c, d) ∈ U X 2 , p(x, y) = (bc +
Solving      (1) : bc + d = x √ 6 -y √ 2
(2) :

d = x √ 6 + y √ 2 (3) : d = -2 x √ 6 ⇐⇒      (1) -(2) : - √ 2y = bc √ 2((2) -(3)) : y = - √ 3x (3) : d = -2 x √ 6
and we obtain

V 2 = (x, y) ∈ R 2 | √ 3x + y = 0 .
Case j = 3: We have c ≥ 0, a + c ≥ 0 and 2a + c ≤ 0. This leads to f (a,b,c,d) d) and

(X) = (bc + d, b(a + c) + d,
V 3 = (x, y) ∈ R 2 | ∃(a, b, c, d) ∈ U X 3 , p(x, y) = (bc + d, b(a + c) + d, d) .
We have

     (1) : bc + d = x √ 6 -y √ 2 (2) : b(a + c) + d = x √ 6 + y √ 2 (3) : d = -2 x √ 6 ⇐⇒      √ 2((1) -(3)) : √ 3x = y + √ 2bc (2) -(1) : √ 2y = ba (3) : d = -2 x √ 6
.

Using (a, b, c, d) ∈ U X 3 , we obtain c ∈ [-a, -2a], where we recall that a ≤ 0.

• Taking, for simplicity, b = 1 and choosing the value of a, the second equation shows that we can reach any y = a Finally, the set V 2 is the set in between the two lines x + √ 3y = 0 and √ 3x + y = 0, as on the right of Figure 1.

Case j = 4: We have c ≥ 0, a + c ≥ 0 and 2a + c ≥ 0. This leads to f (a,b,c,d)

(X) = (bc + d, b(a + c) + d, b(2a + c) + d) and V 4 = (x, y) ∈ R 2 | ∃(a, b, c, d) ∈ U X 4 , p(x, y) = (bc + d, b(a + c) + d, b(2a + c) + d) .
We have

     (1) : bc + d = x √ 6 -y √ 2 (2) : b(a + c) + d = x √ 6 + y √ 2 (3) : b(2a + c) + d = -2 x √ 6 ⇐⇒      (2) -(1) : √ 2y = ba (3) -(2) : -3 x √ 6 -y √ 2 = ba (3) : b(2a + c) + d = -2 x √ 6
which is equivalent to

     (1) : √ 2y = ba √ 2((2) -(1)) : 3y = - √ 3x (3) : b(2a + c) + d = -2 x √ 6
This leads to

V 4 = (x, y) ∈ R 2 | x + √ 3y = 0 .
Case j = 5: We have c ≤ 0, a + c ≥ 0 and therefore 2a + c ≥ 0. This leads to f (a,b,c,d)

(X) = (d, b(a + c) + d, b(2a + c) + d) and V 5 = (x, y) ∈ R 2 | ∃(a, b, c, d) ∈ U X 5 , p(x, y) = (d, b(a + c) + d, b(2a + c) + d) .
We have

    
(1) : Finally, the set V 5 is the set in between the two lines x + √ 3y = 0 and y = 0, as on the right of Figure 1.

d = x √ 6 -y √ 2 (
Case j = 6: We have c ≤ 0, a + c ≤ 0 and 2a + c ≥ 0. This leads to f (a,b,c,d)

(X) = (d, d, b(2a + c) + d) and V 6 = (x, y) ∈ R 2 | ∃(a, b, c, d) ∈ U X 6 , p(x, y) = (d, d, b(2a + c) + d) .
We have

    
(1) :

d = x √ 6 -y √ 2
(2) :

d = x √ 6 + y √ 2 (3) : b(2a + c) + d = -2 x √ 6 ⇐⇒     
(1) :

x √ 6 -y √ 2 = d ((2) -(1))/ √ 2 : y = 0 (3) -(1) : -3 x √ 6 + y √ 2 = b(2a + c) .
Using either d or b(2a + c), x can take any value in R and

V 6 = (x, y) ∈ R 2 | y = 0 .

C Proofs of Section 5

This appendix is devoted to proving the results of Section 5: in Section C.1 we prove Proposition 4, in Section C.2 we prove Proposition 5, in Section C.3 we prove Theorem 6, in Section C.4 we prove Proposition 7, and in Section C.5 we prove Proposition 8.

C.1 Proof of Proposition 4

Before proving Proposition 4, we state and prove a lemma connecting the sets ‹ O n j , defined in (7), and X n θ , defined in (16).

Lemma 15. Let θ ∈ (R E × R B ) \ Z, and let n ∈ N * . We have

X n θ = {X ∈ R N 0 ×n | (X, θ) ∈ mn j=1 ‹ O n j }. Proof. Consider θ ∈ (R E × R B ) \ Z and n ∈ N * and let us first prove that {X ∈ R N 0 ×n | (X, θ) ∈ mn j=1 ‹ O n j } ⊆ X n θ . Let X = (x (i) ) i∈ 1,n ∈ R N 0 ×n and let j ∈ 1, m n such that (X, θ) ∈ ‹ O n j . Denote δ 1 , . . . , δ n ∈ {0, 1} N 1 +•••+N L-1 such that X ∈ n i=1 D δ i (θ). Using Lemma 13, (i), Item 2, we have X ∈ {X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ ‹ O n j } ⊆ n i=1 D δ i (θ). Moreover, {X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ ‹ O n j } is open, since ‹ O n j is open, and therefore X ∈ Int Ç n i=1 D δ i (θ) å = n i=1 Int(D δ i (θ)).
Using the definition of X n θ , in (16), we conclude that X ∈ X n θ . This concludes the proof of the first inclusion.

Before

T n = (∪ mn j=1 ‹ O n j ) c . Hence T n = mn j=1 ‹ O n j c ⊆ mn j=1 O n j c . ( 31
)
Let us now prove the inclusion

X n θ ⊆ {X ∈ R N 0 ×n | (X, θ) ∈ mn j=1 ‹ O n j }. Let X = (x (i) ) i∈ 1,n ∈ X n θ .
Since, as written above,

Ä mn j=1 ‹ O n j ä c = T n , proving that (X, θ) ∈ mn j=1 ‹ O n j is equivalent to proving that (X, θ) ̸ ∈ T n . Assume by contradiction that (X, θ) ∈ T n . There exist i ∈ 1, n , ℓ ∈ 1, L -1 and v ∈ V ℓ such that (x (i) , θ) ∈ T v , which means that v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x (i) ) ä v ′ + b v = 0.
Since X ∈ X n θ , we have x (i) ∈ X θ , and there exists δ ∈ A(θ) such that

x (i) ∈ Int(D δ (θ)). Let us show that this implies Int(D δ (θ)) × {θ} ⊆ T v . Indeed, the function x -→ v ′ ∈V ℓ-1 w v ′ →v Ä f ℓ-1 θ (x) ä v ′ + b v
is affine over the open set Int(D δ (θ)). If it is not constantly equal to zero over this set, then since its value at x (i) is zero, it takes both positive and negative values over Int(D δ (θ)), and thus a v (x, θ) is not constant over Int(D δ (θ)). This contradicts the definition of D δ (θ). Thus, the function is constantly equal to zero on Int(D δ (θ)) and, using the definition of T v , in (24), Int(D δ (θ)) × {θ} ⊆ T v . Therefore, Int(D δ (θ)) × {θ} ⊆ T and, using the definition of T n in ( 28) and ( 31)

Ä ¶ X ′ ∈ R N 0 ×n | (x ′ ) (i) ∈ Int(D δ (θ)) © × {θ} ä ⊆ T n ⊆ mn j=1 O n j c . Therefore, ¶ X ′ ∈ R N 0 ×n | (x ′ ) (i) ∈ Int(D δ (θ)) © ⊆ z n (θ), where z n (θ) is defined in (17). Since Int(D δ (θ)) is non-empty, the Lebesgue measure of ¶ X ′ ∈ R N 0 ×n | (x ′ ) (i) ∈ Int(D δ (θ))
© is not zero and therefore θ ∈ Z n , as defined in (18). This contradicts the hypothesis on θ and finishes the proof of the statement (X, θ) ̸ ∈ T n .

This concludes the proof of the inclusion

X n θ ⊆ {X ∈ R N 0 ×n | (X, θ) ∈ mn j=1 ‹
O n j } and finishes the proof of Lemma 15.

Proof of Proposition 4. We remind that for all n ∈ N * and all θ Let us write λ for Lebesgue measure on R N 0 ×n ×(R E ×R B ), and λ 1 for Lebesgue measure on R N 0 ×n . Note that

∈ R E × R B , z n (θ) = X ∈ R N 0 ×n (X, θ) ∈ Ä ∪ mn j=1 O n j ä c , Z n = θ ∈ R E × R B z n (θ)
Ä ∪ mn j=1 O n j ä c is measurable in R N 0 ×n × (R E × R B ), as a closed set,
and thus for all

θ ∈ R E × R B , z n (θ) is measurable in R N 0 ×n . With similar arguments, the function θ -→ λ 1 (z n (θ)) is measurable on R E × R B as
(θ) × {θ} ⊆ Ä ∪ m j=1 O n j ä c , and thus C ⊆ Ä ∪ m j=1 O n j ä c . We have λ(C) = R E ×R B R N 0 ×n 1 C (X, θ)dXdθ = Zn zn(θ) 1dXdθ = Zn λ 1 (z n (θ))dθ >0,
as the integral of the strictly positive function λ 1 (z n (θ)), on the set Z n with non-zero Lebesgue measure, is strictly positive (note that since all the functions in the above display are non-negative and measurable, their integrability is guaranteed). This is in contradiction with the fact that C

⊆ Ä ∪ m j=1 O n j ä c , since Ä ∪ m j=1 O n j ä c has Lebesgue measure zero from Theorem 1 (i).
This concludes the proof of the statement that Z n has Lebesgue measure zero on R E ×R B and concludes the proof of (i).

The item (ii) is an immediate consequence of (i), since Z is a countable union of measurable sets of measure 0.

Let us now prove (iii).

For any θ ∈

(R E × R B ) \ Z, n ∈ N * , and X ∈ X n θ , Lemma 15 shows that there exists j ∈ 1, m n such that (X, θ) ∈ ‹ O n j . Lemma 13 (i) Item 3 shows that (X ′ , θ ′ ) -→ f θ ′ (X ′ ) is an analytic function on the open set ‹ O n j . Its restriction to the open neighborhood {θ ′ ∈ R E × R B | (X, θ ′ ) ∈ ‹ O n j } of θ is also an analytic function. In particular, θ ′ -→ f θ ′ (X) is differentiable at θ.

C.3 Proof of Theorem 6

We begin the proof with a lemma. To state the lemma, let us recall first that for any n ∈ N * and any j ∈ 1, m n , the mapping (X, θ) -→ a(X, θ), is constant on ‹ O n j and that we denote by ∆ n j ∈ {0, 1} (N 1 +•••+N L-1 )×n its constant value, see ( 7). Since by definition we have O n j ⊆ ‹ O n j , in particular the mapping (X, θ) -→ a(X, θ), is also constant equal to ∆ n j over O n j . Let us write ∆ n j = (δ j,n 1 , . . . , δ j,n n ). We therefore have, for all (X, θ) = ((

x (i) ) i∈ 1,n , θ) ∈ O n j , a(x (i) , θ) = δ j,n i ∈ {0, 1} N 1 +•••+N L-1 , for all i ∈ 1, n . ( 33
)
For the next lemma, note that I n (θ) in ( 21) can in fact be defined for any

θ ∈ R E × R B .
Lemma 16. For any n ∈ N * , θ ∈ R E × R B , and j ∈ 1, m n , we have

j ∈ I n (θ) =⇒ ∀i ∈ 1, n , δ j,n i ∈ A(θ).
Conversely, for any n ∈ N * , θ ∈ (R E × R B ) \ Z, and j ∈ 1, m n , we have

j ∈ I n (θ) ⇐= ∀i ∈ 1, n , δ j,n i ∈ A(θ). Proof. Consider n ∈ N * , θ ∈ R E × R B and j ∈ 1, m n . Let us first prove that if j ∈ I n (θ) then, for all i ∈ 1, n , δ j,n i ∈ A(θ). Indeed, let j ∈ I n (θ). For any i ∈ 1, n , given the definition of A(θ) in (15), in order to prove that δ j,n i ∈ A(θ), it is sufficient to prove Int(D δ j,n i (θ)) ̸ = ∅, where the notation D δ (θ) is defined in (14).
Since j ∈ I n (θ), there exists X such that (X, θ) = ((

x (i) ) i∈ 1,n , θ) ∈ O n j . Moreover, since O n j is open {X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ O n j
} is open and, since it contains X, non-empty. We also have using ( 33)

{X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ O n j } ⊆ n i=1 D δ j,n i (θ)
and thus

{X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ O n j } ⊆ n i=1 Int(D δ j,n i (θ)), which shows that, for i ∈ 1, n , Int(D δ j,n i (θ)) ̸ = ∅ and therefore δ j,n i ∈ A(θ).
This finishes the proof of the first implication.

Consider n ∈ N * , θ ∈ (R E × R B ) \ Z and j ∈ 1, m n .
Let us now prove that if, for all i ∈ 1, n , δ j,n i ∈ A(θ), then j ∈ I n (θ). To do so, assume that for all i ∈ 1, n , δ j,n i ∈ A(θ). Considering the definition of I n (θ), in (21), it suffices to put to evidence X ∈ R N 0 ×n such that (X, θ) ∈ O n j to prove that j ∈ I n (θ).

Since, for all i ∈ 1, n , δ j,n i ∈ A(θ), using the definition of

A(θ) in (15), Int(D δ j,n i (θ)) ̸ = ∅. Therefore, Π n i=1 Int(D δ j,n i (θ)) ⊆ R N 0 ×n is a non-empty open set. Moreover, since θ ̸ ∈ Z, {X ∈ R N 0 ×n | (X, θ) ∈ (∪ mn j=1 O n j ) c } has Lebesgue measure zero in R N 0 ×n . Therefore, since Π n i=1 Int(D δ j,n i (θ)) is a non-empty open set, there exists j ′ ∈ 1, m n such that Π n i=1 Int(D δ j,n i (θ)) ∩ {X ∈ R N 0 ×n | (X, θ) ∈ O n j ′ } ̸ = ∅.
Consider X in this set, we have

a(X, θ) = δ j,n = δ j ′ ,n .
Using Theorem 1, (i), second item, we conclude that j = j ′ . Finally, (X, θ) ∈ O n j and j ∈ I n (θ). This concludes the proof.

Proof of Theorem 6. Consider θ and θ ′ in (R E × R B ) \ Z and assume A(θ) ⊆ A(θ ′ ).

Let n ∈ N * and j ∈ I n (θ). Using Lemma 16, we know that for all i ∈ 1, n , δ j,n i ∈ A(θ), and therefore for all i ∈ 1, n , δ j,n i ∈ A(θ ′ ). Using Lemma 16 again, we obtain that j ∈ I n (θ ′ ). As a conclusion, for all n ∈ N * , I n (θ) ⊆ I n (θ ′ ).

Using Proposition 5, we obtain that for all n ∈ N * , r * n (θ) ≤ r * n (θ ′ ). We conclude, using the definition of r * , in (19), that r * (θ) ≤ r * (θ ′ ).

This concludes the proof of the first statement of Theorem 6. The second statement follows by applying the first statement twice. Once with the hypothesis A(θ) ⊆ A(θ ′ ) and a second time with the hypothesis A(θ ′ ) ⊆ A(θ). This concludes the proof of the theorem.

C.4 Proof of Proposition 7

Let θ ∈ R E × R B and let θ ∼ θ. The first statement is immediate: for n ∈ N * , the third item of Proposition 14 shows that

(X, θ) ∈ mn j=1 O n j ⇐⇒ (X, θ) ∈ mn j=1 O n j , i.e. z n (θ) = z n ( θ). This immediately yields θ ∈ Z ⇐⇒ θ ∈ Z. Let us now show the second statement. Consider θ ∈ (R E × R B ) \ Z and θ ∼ θ. The first statement shows that θ ∈ (R E × R B ) \ Z. Let us fix n ∈ N * and show that r * n (θ) = r * n ( θ).
Since, as discussed in Section 3, the rank is bounded by |E| + |B|, there is a finite number of possibles values, and thus there exists X ∈ X n θ that realizes the maximum in the definition (19), i.e. satisfying rank(Df θ (

X)) = r * n (θ). Since θ ∈ (R E × R B ) \ Z, by Lemma 15 there exists j ∈ 1, m n such that (X, θ) ∈ ‹ O n j .
The first item of Proposition 14 shows that

The second part of the proposition is a consequence of the first part. Indeed, let us fix some ε > 0, let us take θ ∈ (R E × R B ) \ Z such that r * (θ) = max θ∈(R E ×R B )\Z r * ( θ), and let us take γ ′ > 0 such that (22) holds with γ there replaced by γ ′ here. Then we have fS R E ×R B ,γ ′ ≥ fS B(θ,ε),γ ′ ≥ r * (θ).

Finally, the third part of the proposition is also a consequence of the first part. Consider r such that A r = {θ ∈ (R E × R B ) \ Z | r * (θ) = r} has non-empty interior. Consider θ in the interior of A r . There is ϵ > 0 such that B(θ, ϵ) ⊆ A r . Hence for any γ ′′ > 0 such that (22) holds, with γ replaced by γ ′′ , fS Ar,γ ′′ ≥ fS B(θ,ϵ),γ ′′ ≥ r * (θ).

Since r * (θ) = r, we obtain fS Ar,γ ′′ ≥ r for some γ ′′ > 0. Hence the third part is proved.

This concludes the proof.

Consider then the case where P (Y 1 = x 1 , . . . , Y k = x k ) > 0. We have

P (Y 1 =
P k (ω) P(X k+1 = 1|X 1 = x 1 , . . . , X k = x k ) = P (X 1 = x 1 , . . . , X k = x k ) P(X k+1 = 1|X 1 = x 1 , . . . , X k = x k ) = P (X 1 = x 1 , . . . , X k = x k , X k+1 = 1) .
We treat the case Y k+1 = 0 similarly, writing the details for the sake of completeness. We have P (Y 1 = x 1 , . . . , Y k = x k , Y k+1 = 0) = P (X 1 = x 1 , . . . , X k = x k ) 1

P (Y 1 = x 1 , . . . , Y k = x k ) ω∈Ω k s.t.
Y i (ω)=x i for i∈ 1,k P k+1 (ω, 3) = P (X 1 = x 1 , . . . , X k = x k ) 1

P (Y 1 = x 1 , . . . , Y k = x k ) ω∈Ω k s.t. Y i (ω)=x i for i∈ 1,k P k (ω)(1 -P ω ) = P (X 1 = x 1 , . . . , X k = x k ) 1 P (Y 1 = x 1 , . . . , Y k = x k ) ω∈Ω k s.t.
Y i (ω)=x i for i∈ 1,k P k (ω) P(X k+1 = 0|X 1 = x 1 , . . . , X k = x k ) = P (X 1 = x 1 , . . . , X k = x k ) P(X k+1 = 0|X 1 = x 1 , . . . , X k = x k ) = P (X 1 = x 1 , . . . , X k = x k , X k+1 = 0) . Hence Item (2) of L k+1 holds.

Let us now show Item (3) of L k+1 . The method is similar as above, but we give the details for completeness. Consider c 1 , . . . , c k , c k+1 ∈ {0, 1}. Using the definition of C 1 , . . . , C k+1 , we have

P (C 1 = c 1 , . . . , C k = c k , C k+1 = c k+1 ) =P k+1 A c 1 × • • • × A c k+1 ,
where for i ∈ 1, k + 1 , A c i = {1} if c i = 1 and A c i = {2, 3} if c i = 0. Note that this holds by constructing P 1 , . . . , P k+1 , Ω 1 , . . . , Ω k+1 and C 1 , . . . , C k+1 as above, by induction, with in particular Ω k+1 = {1, 2, 3} k+1 . If c k+1 = 1, then

P k+1 A c 1 × • • • × A c k+1 = P k+1 (A c 1 × • • • × A c k × {1}) = i 1 ∈Ac 1 ••• i k ∈Ac k P k+1 ((i 1 , . . . , i k , 1)) = i 1 ∈Ac 1 ••• i k ∈Ac k P k ((i 1 , . . . , i k )) p = P k (C 1 = c 1 , . . . , C k = c k )p = P k (B 1 = c 1 , . . . , B k = c k )p = P k (B 1 = c 1 , . . . , B k = c k , B k+1 = c k+1 ),
where we have used Item 3 of L k for the second equality before last above and the definition of B 1 , . . . , B k+1 , in the lemma statement, for the last equality. Similarly, we have, if c k+1 = 0,

P k+1 A c 1 × • • • × A c k+1 =P k+1 (A c 1 × • • • × A c k × {2, 3}) = i 1 ∈Ac 1 ••• i k ∈Ac k
P k+1 ((i 1 , . . . , i k , 2)) + P k+1 ((i 1 , . . . , i k , 3)) Let us now show (38). We have from Items (2) and (3) of L k ,

= i 1 ∈Ac 1 ••• i k ∈Ac k P k ((i 1 , . . . , i k )) (1 -p) =P k (C 1 = c 1 , . . . , C k = c k )(1 -p) =P k (B 1 = c 1 , . . . , B k = c k )(1 -p) =P k (B 1 = c 1 , . . . , B k = c k , B k+1 = c k+1 ).
P (X 1 + • • • + X k ≤ t) -P (B 1 + • • • + B k ≤ t) =P (Y 1 + • • • + Y k ≤ t) -P (C 1 + • • • + C k ≤ t) =E 1 {Y 1 +•••+Y k ≤t} -1 {C 1 +•••+C k ≤t} ≤0,
because from Item (1) of L k , the random variable

1 {Y 1 +•••+Y k ≤t} -1 {C 1 +•••+C k ≤t}
takes the values -1 or 0.

Proof of Theorem 11. Let us consider random vectors x (1) , . . . , x (n) ∈ R N 0 , sampled as described in the statement of the theorem. Let us first show that, almost surely, for all ℓ ∈ 1, n , there exists j ∈ 1, m ℓ such that ((x (i) ) 1≤i≤ℓ , θ) ∈ O ℓ j . Indeed, for any ℓ ∈ 1, n , since θ ̸ ∈ Z, the set {X ∈ R N 0 ×ℓ | (X, θ) ∈ (∪ m ℓ j=1 O ℓ j ) c } has Lebesgue measure zero. Since the vectors x (i) are independent, the matrix (x (i) ) 1≤i≤ℓ ∈ R N 0 ×ℓ follows the product distribution G ℓ , which is absolutely continuous with respect to Lebesgue measure of R N 0 ×ℓ . Therefore, we have

P Ä ((x (i) ) 1≤i≤ℓ , θ) ∈ (∪ m ℓ j=1 O ℓ j ) c ä = 0,
and since this is true for all ℓ ∈ 1, n , we thus have

P Ä ∃ℓ ∈ 1, n such that ((x (i) ) 1≤i≤ℓ , θ) ∈ (∪ m ℓ j=1 O ℓ j ) c ä = 0.
As a consequence, for the rest of the proof, up to intersecting with an event of probability one, we will assume that for all ℓ ∈ 1, n , there exists j ∈ 1, m ℓ such that ((x (i) ) 1≤i≤ℓ , θ) ∈ O ℓ j . To ease the reading, let us denote N = n * (θ) in this proof. By definition of N , we have r * N (θ) = r * (θ), and Proposition 5 shows that there exists j ∈ I N (θ) such that r * N (θ) = r N j .

Consequently, there exist deterministic x (1) , . . . , x (N ) ∈ R N 0 such that if ‹ X = ( x (i) ) 1≤i≤N , we have ( ‹ X, θ) ∈ O N j and rank Ä Df θ ( ‹ X) ä = r * (θ).

For δ ∈ A(θ), let us define the deterministic integer

c * δ = Card {i ∈ 1, N | x (i) ∈ Int D δ (θ)}.
We have We have c δ (ℓ) ≤ c * δ , for all δ ∈ A(θ), thus c(ℓ) ≤ N . The sequence c(ℓ) is nondecreasing, and at each step, the increment c(ℓ + 1) -c(ℓ) is either 0 or 1.

Let us first show that, almost surely, for ℓ ∈ 1, n ,

{c(ℓ) = N } =⇒ ¶ rank Ä Df θ Ä (x (i) ) 1≤i≤ℓ ää = r * (θ) © . ( 39
)
Suppose indeed that, for some ℓ ∈ 1, n , c(ℓ) = N . Then for all δ ∈ A(θ), we have c δ (ℓ) = c * δ . Up to a re-ordering, we can assume that for all i ∈ 1, N , a(x (i) , θ) = a( x (i) , θ).

(40)

As assumed earlier, there exists j ′ ∈ 1, m N such that ((x (i) ) 1≤i≤N , θ) ∈ O N j ′ . The equality (40) and Item 2 of Theorem 1 (i) show that j ′ = j. Item 3 of Theorem 1 (i) shows that the rank is constant over O N j , and thus rank Define X 1 = c(1) and X k = c(k)-c(k -1) for k ∈ 2, n . Notice that X 1 +• • •+X k = c(k) for all k ≥ 2. Consider also the i.i.d. Bernoulli variables B 1 , . . . , B n from the first item of the theorem statement. We will apply Lemma 19 to p, as defined in Theorem 11, (X 1 , . . . , X n ) and (B 1 , . . . , B n ). To do so we need to prove that (X 1 , . . . , X n ) satisfies the hypotheses of Lemma 19. First, P(X 1 = 1) is the probability that x (1) falls into one of the sets Int D δ (θ) for any δ such that c * δ ≥ 1. Since there exists at least one such δ, and since the probability of falling into Int D δ (θ) is lower bounded by p, by definition of p, we thus have P(X 1 = 1) ≥ p. Now let us show that, for k ∈ 1, n -1 , x 1 , . . . , x k ∈ {0, 1}, P(X k+1 = 1|X 1 = x 1 , . . . , X k = x k ) ≥ p.

Ä Df θ ((x (i) ) 1≤i≤N ) ä = rank Ä Df θ (( x (i) ) 1≤i≤N ) ä =

Let us work conditionnally to X

1 = x 1 , . . . , X k = x k . If x 1 + • • • + x k ≥ N , then c(k) = x 1 + • • • + x k ≥ N
and thus, by definition of c(k + 1) and X k+1 , X k+1 = 1. So P(X k+1 = 1|X 1 = x 1 , . . . , X k = x k ) = 1 ≥ p.

Consider now the case x 1 + • • • + x k < N , i.e. c(k) < N . Conditionally to x (1) , . . . , x (k) for which X 1 = x 1 , . . . , X k = x k with x 1 + • • • + x k < N , there is at least one δ ∈ A(θ) such that c δ (k) < c * δ , and if x (k+1) falls into Int D δ (θ), then X k+1 = 1 because c(k + 1) = c(k) + 1 and thus c(k + 1) = c(k) + 1. Hence P Ä X k+1 = 1|x (1) , . . . , x (k) ä ≥ p and thus

P (X k+1 = 1|X 1 = x 1 , . . . , X k = x k ) = 1 P(X 1 = x 1 , . . . , X k = x k ) P (X 1 = x 1 , . . . , X k = x k , X k+1 = 1) = 1 P(X 1 = x 1 , . . . , X k = x k ) E E 1 {X 1 =x 1 ,...,X k =x k } 1 {X k+1 =1}
x (1) , . . . , x (k) = 1 1) , . . . , x (k) äó ≥p.

P(X 1 = x 1 , . . . , X k = x k ) E î 1 {X 1 =x 1 ,...,X k =x k } P Ä X k+1 = 1|x (
Hence we can apply Lemma 19. From this lemma and ( 41), for all n ∈ N,

P rank Ä Df θ Ä (x (i) ) 1≤i≤n ää < r * (θ) ≤P(c(n) < N ) =P(X 1 + • • • + X n < N ) ≤P(B 1 + • • • + B n < N ).
Hence

+ • • • + B n < N ) =P(B 1 + • • • + B n -np < N -np) ≤ np (np -N ) 2 ≤ 4 np .
This concludes the proof.

  1 , leading to local identifiability, examples of non-identifiable neural networks and rank deficient parameters are in Grigsby u. a. (2022); Bona-Pellissier u. a. (2023a); Grigsby u. a. (2023); Sonoda u. a. (2021). Let us emphasize a simple example illustrating that several rank values can be achieved. Examples 1. Consider L ≥ 3, any neuron v ∈ V ℓ , for ℓ ∈ {2, . . . , L -1}, and θ

Figure 2 :

 2 Figure 2: Schematic representation of the sets U X j (left) and the corresponding local image sets {f θ(X) | θ ∈ U X j }, j ∈ 1, 7 (right). We have r X 1 = 1, r X 2 = 2, r X 3 = 1, r X 4 = 0, r X 5 = 1, r X 6 = 1, r X 7 = 1. The image of U X2 is the curved diamond-shaped area, hatched in cyan (right). The images of the sets U X j with r X j = 1 are represented with lines of their respective colors (right). The image of U X 4 with r X 4 = 0 is represented by a magenta bullet point (right). We consider the square loss in R N L ×n . The target Y ∈ R N L ×n and the global solution f θ * (X) of the regression problem are represented (right). The pre-image of f θ * (X) is displayed in brown (left). A minimizing sequence is represented by gray stars, in the parameter space (left) and the image space (right).

  see the bound provided by Grigsby u. a. (

Figure 3 :

 3 Figure 3: Behavior of different complexity measures as the size of the network increases. The values of the several ranks are to be read on the left axis, titled 'functional dimension'. The values for the test and train errors and the train loss are to be read on the right axis.

Figure 4 :

 4 Figure 4: Behavior of different complexity measures during training. The values of the different ranks are to be read on the left axis, titled 'functional dimension'. The values of the train loss (on the left figure), and the values of the test and train errors (on the right figure) are to be read on the right axis.

Figure 5 :

 5 Figure 5: Effect of the noise on a MNIST image for different amplitudes. From left to right, a MNIST image to which has been added a Gaussian noise, of amplitude 10 -2 , 10 -1 , 5 × 10 -1 and 10 0 respectively.

Figure 6 :

 6 Figure 6: Behavior of different complexity measures when noise is added to the input images. The values of rank(Df θ (X train )) are to be read on the left axis, titled 'functional dimension'. The values of the test and train errors are to be read on the right axis.

Figure 7 :

 7 Figure 7: Behavior of different complexity measures as some corrupted labels are introduced in the training set, tested for three network widths. The values of the different ranks are to be read on the left axis, titled 'functional dimension'. The values of the test and train errors are to be read on the right axis. Width of the network from left to right: w = 30, w = 50 and w = 60.

  in (7) are non-empty, open and disjoint, and they satisfy -

  As a consequence, (X, θ) does not belong to any of the open sets ‹ O n j ′ . This shows (∪ mn j=1 ‹ O n j ) c = T n , and thus, since T n is of Lebesgue measure zero, (∪ mn j=1 ‹ O n j ) c has Lebesgue measure zero. Adding that the complement of an open set is closed, (∪ mn j=1 ‹ O n j ) c is closed, which ends the proof of the first point of (i).

√ 2 ≤

 2 0. Moreover, as c goes through[-a, -2a],[-2y, -4y]. Therefore, we see with the first equation that √ 3x goes through [-y, -3y], that isx goes through [-y √ 3 , -√3y]. It is not possible to reach other values for other values of b ≥ 0. • Similarly, taking b = -1 and choosing the value of a, the second equation shows that we can reach any y = -a √ 2 ≥ 0. Moreover, as c goes through [-a, [-4y, -2y]. Therefore, we see with the first equation that √ 3x goes through [-3y, -y], that is x goes through [-√ 3y, -y √ 3 ]. Again, it is not possible to reach other values for other values of b ≤ 0.

.

  2) : b(a + c) + d = x √ Using b and a + c ≥ 0, we see with the second equation that y can take any value in R. Let us consider an arbitrary fixed y ∈ R. In fact, there are infinitely many choices for b, a and c corresponding to this value. Taking b = sign(y), we have a + c = sign(y) √ 2y = √ 2|y| and, since c ≤ 0, a can take any value in [ √ 2|y|, +∞). Therefore, 2a + c = a + (a + c) can take any value in [

  has strictly positive Lebesgue measure and Z = ∪ n∈N * Z n .Let us first prove (i).

  Hence in all cases,P (C 1 = c 1 , . . . , C k = c k , C k+1 = c k+1 ) = P (B 1 = c 1 , . . . , B k = c k , B k+1 = c k+1 )and L k+1 is proved. This finishes the proof by induction that L k holds for all k ∈ N * .

  intersecting with an event of probability one, since∪ δ∈A(θ) Int D δ (θ) c = X cθ is included in a finite union of hyperplanes, as observed after (15), and thus has Lebesgue measure zero. Let us also define, for ℓ ∈ 1, n and δ ∈ A(θ), the random integersc δ (ℓ) = min Ä Card {i ∈ 1, ℓ | x (i) ∈ Int D δ (θ)} , c *

  r * (θ). This shows (39) as desired.Define now c(ℓ) by c(ℓ) = c(ℓ) if c(ℓ) < N and by c(ℓ) = N + (ℓ -M ) if c(ℓ) = N , where M is the smallest index i such that c(i) = N . Then, for all ℓ ∈ 1, n , c(ℓ) = N ⇐⇒ c(ℓ) ≥ N . Hencei) ) 1≤i≤n ää < r * (θ) ä ≤ P (c(n) < N ) . (41)

  is a closed set with Lebesgue measure zero, we find that,

	O n j is open and dense in ‹ O n j	and	U X j is open and dense in U X j .

  proving the converse inclusion, let us establish that T n ⊆ Ä

		mn j=1 O n j	ä c , where the
	open sets O n 1 , . . . , O n mn are as in Theorem 1 and T n is defined in (28). By definition, we
	have O n j ⊆ ‹ O n j for j ∈ 1, m n . Thus ∪ mn j=1 O n j ⊆ ∪ mn j=1	‹ O n j . Also from Lemma 13, (i), Item 1,

  the integral with respect to X of a measurable function of X and θ. Hence, Z n , as the set where this function is strictly positive, is indeed measurable.Let n ∈ N * . We first prove that Z n has Lebesgue measure zero on R E × R B . Let us assume by contradiction that Z n has strictly positive Lebesgue measure.Let us write C = ∪ θ∈Zn (z

	Ä	∪ m j=1 O n j	ä c .

n (θ) × {θ}). For all θ, for all X ∈ z n (θ), (X, θ) ∈ Hence, we have, for all θ, z n

  x 1 , . . . , Y k = x k , Y k+1 = 1) = Using now Item (2) of L k , and then using the definition of P w , we haveP (Y 1 = x 1 , . . . , Y k = x k , Y k+1 = 1) = ω∈Ω k s.t. Y i (ω)=x i for i∈ 1,k P k (ω)P ω = P (X 1 = x 1 , . . . , X k = x k ) 1 P (Y 1 = x 1 , . . . , Y k = x k ) ω∈Ω k s.t. Y i (ω)=x i for i∈ 1,k P k (ω)P ω = P (X 1 = x 1 , . . . , X k = x k ) 1 P (Y 1 = x 1 , . . . , Y k = x k ) ω∈Ω k s.t.

	2
	P k+1 (ω, j) =	P k (ω)P ω .
	j=1 ω∈Ω k s.t.	ω∈Ω k s.t.
	Y i (ω)=x i	Y i (ω)=x i
	for i∈ 1,k	for i∈ 1,k

Y i (ω)=x i for i∈ 1,k

  Item 1 of Theorem 11 holds. Let us now consider Item 2. The expectation of B 1 + • • • + B n is np and the variance is np(1 -p) ≤ np. Hence using Chebyshev's inequality, for np ≥ 2N

	P	Ä rank	Ä	Df θ	Ä	(x (i) ) 1≤i≤n	ää	< r * (θ) ä	≤P(B 1

The notation ‹ O(•) ignores logarithmic factors.

As its name indicates, the computable full functional dimension is a variant of the full functional dimension defined in(Grigsby u. a.,

2022), that we can compute. The informal definition below does not take into account restrictions guaranteeing that θ -→ f θ (X) is differentiable at θ.

A weakness of it is that it considers neural networks whose last layer undergoes a ReLU activation.

Narrowing architectures are such that widths decrease.

In these articles X sometimes contains infinitely many examples, in which case we let f θ (X) denote the function f θ restricted to X.

Throughout the paper, for a, b ∈ N, a ≤ b, a, b is the set of consecutive integers {a, a + 1, . . . , b}.

For both flatness and norms, it is, of course, possible to consider the minimum of the complexity criterion over the equivalence class of a θ element. However, this is an additional burden that is not necessary for criteria based on the functional dimension.

Neural networks libraries such as Tensorflow set σ ′ (0) = 0 and we adopt this convention in this calculus. Due to numerical imprecision, we rarely have y ℓ-1 θv = 0 in practice. In the theoretical sections of this article, the situation σ ′ (0) never occurs for the cases where Df θ (X) is considered.

A tighter upper-bound taking into account the positive rescaling invariance of ReLU networks is given by Grigsby u. a. (2022), as discussed in Section 3.

https://www.deel.ai/

Acknowledgement

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. 9

C.2 Proof of Proposition 5

Consider θ ∈ (R E × R B ) \ Z and n ∈ N * and let us first prove that r * n (θ) ≥ max j∈In(θ) r n j . Consider j ∈ I n (θ) such that r n j = max j ′ ∈In(θ) r n j ′ . Because of the definition of I n (θ), in (21), there exists X ∈ R N 0 ×n such that (X, θ) ∈ O n j . As a first consequence, using Theorem 1, (i) third item, we know that r n j = rank(Df θ (X)). As a second consequence, since θ ∈ (R E × R B ) \ Z and O n j ⊆ ‹ O n j we can use Lemma 15, at the beginning of Section C.1, and we have X ∈ X n θ . This leads to the conclusion that max j ′ ∈In(θ)

Let us now prove that r * n (θ) ≤ max j∈In(θ) r n j . Because the rank can only take a finite number of values and considering the definition of r * n (θ) in ( 19), we know there exists X = (x (i) ) i∈ 1,n ∈ X n θ such that rank(Df θ (X)) = r * n (θ).

Since θ ̸ ∈ Z and X ∈ X n θ , we know thanks to Lemma 15 that there exists j ∈ 1, m n such that (X, θ) ∈ ‹ O n j . Thus, by definition of r n j , see (8), we have

To conclude the proof, we only need to show that j ∈ I n (θ).

Since by definition we have O n j ⊆ ‹ O n j , we have the inclusion

Let us show that the set on the left of this inclusion is non-empty, which, by definition of I n (θ), will show that j ∈ I n (θ). First, both sets are open since O n j and ‹ O n j are open, and the set on the right is non-empty since it contains X. Assume by contradiction that the set on the left is empty. Since for all j ′ ∈ 1, m n \{j}, we have O n j ′ ∩ ‹ O n j = ∅, this means, recalling the definition of z n (θ) in ( 17), that we have

Since, as we have just shown, the set

} is open and non-empty, this means that z n (θ) has positive Lebesgue measure, and thus, using (18), that θ ∈ Z n ⊆ Z. This contradicts the hypothesis θ ∈ (R E × R B ) \ Z. This concludes the proof establishing that the open set {X ′ ∈ R N 0 ×n | (X ′ , θ) ∈ O n j } is non-empty, and thus that j ∈ I n (θ). This proves the desired inequality r * n (θ) ≤ max j∈In(θ) r n j .

rank Df θ (X) = rank(Df θ (X)), and the second item shows that there exists j ′ ∈ 1, m n such that (X, θ) ∈ ‹ O n j ′ . Using again Lemma 15 and the fact that θ ∈ (R E × R B ) \ Z, we find that X ∈ X n θ , and we thus have, using the definition (19):

We have shown r * n (θ) ≤ r * n ( θ), and by swapping the roles of θ and θ, we obtain r * n (θ) = r * n ( θ).

Finally, since r * n (θ) = r * n ( θ) for all n ∈ N * , then (20) guarantees that r * (θ) = r * ( θ). This concludes the proof of Proposition 7.

C.5 Proof of Proposition 8

Similarly to what was done in the proof of Theorem 1, all along the proof of Proposition 8, we consider the canonical basis (e 1 , . . . , e |E|+|B| ) of R E × R B and the canonical basis (ε 1 , . . . , ε n ) of R n , where this time we have

Hence we can extract r * (θ) rows from Jf θ ( X) such that, up to reordering, we have, with X = (x (1) , . . . , x (r * (θ)) ), rank(Df θ (X)) = r * (θ). Furthermore, still, θ ′ -→ f θ ′ (X) is continuously differentiable on B(θ, ϵ ′ ).

Then, we can extract r * (θ) columns from Jf θ (X) for which the resulting r * (θ) × r * (θ) matrix is invertible. These r * (θ) columns are associated to a subset of E ∪ B, that we write S. For ϕ ∈ S, we define θ(ϕ) ∈ R E × R B by θ(ϕ) w = θ w for w ∈ (E ∪ B) \ S and by θ(ϕ) w = ϕ w for w ∈ S. We also let θ |S = (θ w ) w∈S . Then we consider the function g : R S -→ R r * (θ) defined by the row vector g(ϕ) = f θ(ϕ) (X).

The differential of g at θ |S is defined by the invertible r * (θ) × r * (θ) matrix extracted from Jf θ (X), discussed above, in the canonical bases of R S and R r * (θ) . In addition, g is continuously differentiable on B(θ |S , ϵ ′ ).

Hence we can apply the inverse function theorem. There is an open set

such that g is bijective from U to V . We let g -1 be the inverse of g. Then, there is γ > 0 small enough such that f θ (X) + γ{-1, 1} r * (θ) ⊆ V , where "+" denotes the Minkowski sum.

Let

By definition, this implies that fS B(θ,ε),γ ≥ r * (θ). This shows the first part of the proposition. guaranteed by definition of r * (θ)). Let X ′′ ∈ X n+n ′ θ be obtained by concatenating the columns of X and X ′ . From Lemma 17, we have rank Df θ (X ′′ ) ≥ rank Df θ (X ′ ) = r * (θ) ≥ rank(Df θ (X)) + 1.

Using the matrix notations defined in the proof of Lemma 17, there exists a row of Jf θ (X ′ ),

to the range of Jf θ (X). Recall that for x ∈ X θ , we write X x for the matrix of X n+1 θ obtained by concatenating X and x. From the above, we have rank Df θ (X x ′ (i) ) ≥ rank(Df θ (X)) + 1.

This proves the first statement of the lemma and we still need to prove that the set of such x's has non-zero Lebesgue measure on R N 0 . Consider x ′ (i) ∈ X θ as constructed in the first part of the proof. By continuity of

x -→ Df θ (X x ) at x ′ (i) , and since the rank is a lower semi-continuous function and X θ is open, then there exists ε > 0 such that B(x ′ (i) , ε) ⊆ X θ and for all x ∈ B(x

The ball B(x ′ (i) , ε) has a non-zero Lebesgue measure, which concludes the proof.

We can now prove Proposition 9.

Proof of Proposition 9. Let us first show that the sequence (r * n (θ)) n∈N * is non-decreasing. Let n ∈ N * and X ∈ X n θ such that rank(Df θ (X)) = r * n (θ). For any x ∈ X θ , using the notation X x of Lemma 18, Lemma 17 shows that r * n (θ) = rank(Df θ (X)) ≤ rank(Df θ (X x )), and thus r * n (θ) ≤ r * n+1 (θ). Hence, the sequence (r * n (θ)) n∈N * is non-decreasing. Since the input space of Df θ (X) is R E ×R B for all X, the sequence is also upper bounded by r * (θ) ≤ |E| + |B|. Therefore, since it only takes integer values, there exists n such that r * n (θ) = r * (θ) and we can write n * (θ) ∈ N * for the smallest of these n. Let n ∈ 1, n * (θ) -1 and X ∈ X n θ such that rank(Df θ (X)) = r * n (θ). We have r * n (θ) < r * (θ) and using Lemma 18, there exists x ∈ X θ such that rank(Df θ (X x )) ≥ rank(Df θ (X)) + 1. Hence we have

The sequence is therefore increasing for 1 ≤ n ≤ n * (θ). Because of the definition n * (θ), it is also stationary (constant) for n * (θ) ≤ n.

Let us now prove the upper and lower bounds on n * (θ). Now, consider n ∈ 1, n * (θ) -1 and X ∈ X n+1 θ such that rank(Df θ (X)) = r * n+1 (θ). Let us write X n ∈ X n θ for the matrix obtained by removing the last column x (n+1) from X.

Furthermore, for x ∈ X θ , because of the size of Df θ (x), we have

Hence

Grouping ( 34) and (36), we have

This allows an induction argument. Recall that for this part of the proposition we assume here r * (θ) ≥ 1 (in the case r * (θ) = 0, the sequence r * n (θ) is constantly zero and n * (θ) = 1). Then, there exists n ∈ N * and X ∈ X n θ such that rank(Df θ (X)) ≥ 1, and by extracting x (k) from X such that rank Ä Df θ (x (k) ) ä ≥ 1, we find that 1 ≤ r * 1 (θ). Adding the inequality (35), we have 1 ≤ r * 1 (θ) ≤ N L . Using (37) we can then show that for all n ∈ 1, n * (θ) , we have n ≤ r * n (θ) ≤ nN L . Applying these latter inequalities to n = n * (θ) yields

and the proof is concluded.

D.2 Proof of Theorem 11

Before proving Theorem 11, we state and prove a lemma.

Lemma 19. Fix p ∈ (0, 1) and k ∈ N * . Consider random variables X 1 , . . . , X k valued in {0, 1} such that P(X 1 = 1) ≥ p and for any i ∈ 2, k , for any x 1 , . . . , x i-1 ∈ {0, 1},

Consider B 1 , . . . , B k independent Bernoulli random variables such that for i ∈ 1, k , P(B i = 1) = p and P(B i = 0) = 1 -p.

Then there exists a finite probability space (Ω k , P k ) and random variables

(2) (X 1 , . . . , X k ) and (Y 1 , . . . , Y k ) have the same distribution;

(3) (B 1 , . . . , B k ) and (C 1 , . . . , C k ) have the same distribution.

As a consequence, for each t ≥ 0,

Proof of Lemma 19. We prove the first part of the lemma by induction. Let L k correspond to the statements (1) to (3) for a given k ∈ N * . Let us first show that L 1 is true. Let Ω 1 = {1, 2, 3} and P 1 (1) = p, P 1 (2) = P(X 1 = 1) -p and P 1

Assume now that L k holds for some k ∈ N * and let us show that L k+1 holds. We thus consider Ω k , P k , Y 1 , . . . , Y k and C 1 , . . . , C k as in the statements (1) to (3). We define Ω k+1 = Ω k × {1, 2, 3}. Since Ω k is finite by L k , Ω k+1 is also finite. For ω ∈ Ω k , i ∈ 1, k and j ∈ {1, 2, 3}, let us define Y i (ω, j) = Y i (ω) and C i (ω, j) = C i (ω). Note that we use the convenient abuse of notation of defining Y 1 , . . . , Y k and C 1 , . . . , C k as both functions on Ω k and Ω k+1 . For ω ∈ Ω k , let us define Y k+1 (ω, 1) = Y k+1 (ω, 2) = 1, Y k+1 (ω, 3) = 0, C k+1 (ω, 1) = 1 and C k+1 (ω, 2) = C k+1 (ω, 3) = 0. Then Item (1) of L k+1 is satisfied.

In order to define P k+1 , we denote, for ω ∈ Ω k ,

Then, for ω ∈ Ω k , we define P k+1 (ω, 1) = P k (ω)p, P k+1 (ω, 2) = P k (ω)(P ω -p) and P k+1 (ω, 3) = P k (ω)(1 -P ω ). Using that P k is a probability measure on Ω k , it is simple to see that P k+1 is a probability measure on Ω k+1 . Consider now x 1 , . . . , x k ∈ {0, 1}. If P (Y 1 = x 1 , . . . , Y k = x k ) = 0 then, from Item (2) of L k , P (X 1 = x 1 , . . . , X k = x k ) = 0. In this case, for all x k+1 ∈ {0, 1}, we have