A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
arXiv:2604.14037v1 [cs.LG] 15 Apr 2026
PRANAVKRISHNAN RAMAKRISHNAN
Abstract. Parameter space is not function space for neural network architectures. This fact, investigated as early as the 1990s under terms such as “reverse engineering,” or “parameter identifiability”, has led to the natural question of parameter space symmetries—the study of distinct parameters in neural architectures which realize the same function. Indeed, the quotient space obtained by identifying parameters giving rise to the same function, called the neuromanifold, has been shown in some cases to have rich geometric properties, impacting optimization dynamics. Thus far, techniques towards complete classifications have required the analyticity of the activation function, notably excising the important case of ReLU. Here, in contrast, we exploit the non-differentiability of the ReLU activation to provide a complete classification of the symmetries in the shallow case.
1. Introduction Let Hn ≤ GLn (R) denote the subgroup generated by permutations and diagonal matrices with positive coefficients. This subgroup constitutes the well understood symmetries on the parameter space of a shallow feed forward ReLU neural network, cf. [18, 7]. That is to say, given parameter space Ω(m,n,k) = Mk×n (R) × Mn×m (R) × Rn+k of architecture (m, n, k), we may define the realization map as follows1 ρ(m,n,k) : Ω(m,n,k)
C 0 (Rm , Rk )
(M, A, b, c)
M σ(Ax + b) + c
where σ denotes the ReLU activation function, which is defined as x1 max{0, x1 } .. σ ... = . . xn max{0, xn } We see that Hn acts on Ω(m,n,k) by h · (M, A, b, c) = (M h−1 , hA, hb, c) such that ρ(m,n,k) is a Hn -invariant map. Here by symmetry, we mean not only a group action which preserves the value of a given loss function as in [18, Def. 3.1], but any equivalence of parameters which is invariant under the realization map; this is notably a stronger condition than the one just mentioned, and to distinguish the terms functional loss symmetry [17, Def. 2.6] and functional Date: April 2026. 1The notation used for the parameters in Ω (m,n,1) is, of course, non-standard. A more typical notation in the literature would be taking a parameter θ as (A2 , b2 , A1 , b1 ), where ρ(m,n,k) (θ) = A2 σ(A1 x + b1 ) + b2 . Though this notation is expedient in view of deeper neural networks, since we are considering just the shallow case we opt for the non-standard notation which better visually aligns with realized function. 1
2
PRANAVKRISHNAN RAMAKRISHNAN
neural symmetry [17, Def. 2.4] may be used.2 In particular, this means that for any θ ∈ Ω(m,n,k) , −1 the fibre ρ−1 (m,n,k) (ρ(m,n,k) (θ)), which by abuse of notation we shall now denote ρ(m,n,k) (θ), admits a map from Hn by h 7→ h · θ. We may naturally ask if ρ−1 (m,n,k) (θ) is “larger” than Hn . In fact, as shown in Lemmas 10 and 11, the fibre ρ−1 (m,n,k) (θ) is indeed not merely Hn · θ for certain choices of θ, but contains additional parameters not in the orbit. Called “hidden symmetries” in [8, Def. F.4], the study of such additional symmetries has been a topic of interest in the mathematics of machine learning. Even as early as the 1993, this question was investigated in [5] and [1], though with sigmoidal activations in mind, and a number of works in the past years study the case of polynomial activations, as in [6, 9]. As for the case of ReLU activations, there has been progress in restricting the picture to a neighbourhood to a given parameter [4, 15, 3] or in considering certain types of symmetries [12, 18]. There has also been particular progress in the case of deep ReLU neural networks, as in [8, 13, 2]. Perhaps the most general statements thus far are in [14, 16], which provides general statements for parameters of deep neural networks. The condition of high depth or polynomial activation belies a certain reliance of probabilistic or geometric techniques in the methodology, even epistemology, of the work, with a notable exception of [16], which uses techniques from Lukasiewicz logic. Here, however, we take an ostensibly algebraic approach to the case of shallow ReLU neural networks, which proves itself fruitful in the following main result: Theorem 1. The set of parameters θ ∈ Ω(m,n,k) where the fibre ρ−1 (m,n,k) (θ) is diffeomorphic to the Lie group Hn is dense. Our method is to look at the case when k = 1 and build up to the general case in a natural way. The proof in the k = 1 requires the definition of a certain minimal form (Definition 3) associated to certain equivalence classes of our parameters, through which we are given sufficient data about the symmetries of our parameters to determine the behaviour of their fibres, and which is also computable via a program as given in Section 6. Indeed, this formation of a minimal form gives us not only information on a dense subset of Ω(m,n,1) (namely the one prescribed in Theorem 1,) but also gives us its full symmetry classification, by which we also get the full symmetry classification of Ω(m,n,k) —this is the content of Theorems 3 and 4. The heart of this classification is Proposition 14, which aims to provide conditions for when a certain type of parameter, minimal parameters with no 0-factors (Definition 4), realize a smooth function, that is to say an affine linear function, with an eye towards the 0 function. The proof of this proposition, which relies on checking everywhere differentiability on the domain, speaks to the utility of considering ReLU, which contains a point of non-differentiability at 0. We get as a result that beyond any of the immediate symmetries listed in Definition 3, there remains only one class of symmetries in the case of shallow ReLU networks, which derives from the relationship that σ(x) − σ(−x) = x (note that this is essentially the only nontrivial relation with the ReLU activation function which produces a smooth function.) In fact, the aforementioned immediate symmetries are not unique to the ReLU case, but are one example of symmetries prevalent for a broad class of neural networks. There is likely much to be said about this and the applications of these methods to a more general neural network, but for now we shall resign ourselves to Remark 1. We also prove a somewhat tangential result in classifying the possible stabilizers of a parameter under the Hn action, which we call StabHn θ. Specifically, we get the following result: Theorem 2. For any given parameter θ ∈ Ω(m,n,k) StabHn θ ≃ S × Hn′ 2With the caveat that symmetry to us does not mean that the equivalence derives from a group action. In the
language of [7], such symmetries which derive from a group action as called symmetry via intertwiner group.
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
(a) Bent hyperplane arrangement of θ1
3
(b) Bent hyperplane arrangement of θ2
Figure 1. The bent hyperplane arrangements of θ1 and θ2 . The section in red represents the domain where the first hidden neuron is activated, blue the second, and green the third. Finally the set ρ(2,3,1) (θi )(x, y) = 0 is denoted in black. where n′ ≤ n and S ⊆ Sn−n′ is a subgroup generated by at most
n − n′ 2
two cycles.
The details of this result and its exact form is given in Proposition 2. It is natural to ask if the structure of the stabilizer of θ determines whether its fibre is diffeomorphic to Hn . To this extent, the utility of this theorem within the context of this work is showing that StabHn θ ̸= 1 is a sufficient yet not necessary condition for ρ−1 (m,n,k) (θ) ̸≃ Hn . As a result, we are given the following hierarchy of parameters: {θ : StabHn θ ̸= 1}
Definition
⊂
{θ = (M, A, b, c) : StabHn (A, b) ̸= 1}
Corollary 9
⊂
{θ : ρ−1 (m,n,k) (θ) ̸≃ Hn }.
That being said, however, Corollary 9 itself becomes useful by allowing our method of reduction in Proposition 20, which leads to Theorem 1. On account of this and their otherwise tangential nature, the stabilizer results shall form the contents of Section 3. We see that these classifications and results are given firmly in the language of (linear) algebra. It is natural to ask how these conditions might be interpreted geometrically. While one might with relative ease make geometric sense of the equivalences given in Definition 3, a complete geometric interpretation of the last condition of ≡ in Theorem 3 is not by any means immediate, and it is possible that this one algebraic equivalence encapsulates many different types of geometric equivalences. Alas, any substantive discussion of this are beyond the scope of the work. But to whet our appetites, let us consider the following seemingly innocuous parameter in Ω(2,3,1) : 1 1 1 −2 θ1 = 1 , −1 0 , −1 , −6 0 −1 −1 1 (Here, as indicated in the Notation section, we shall denote the matrix Rn → R as a vector which acts by its transpose on Rn .) Indeed, this parameter satisfies the conditions of [8, Lem. D15]: it is generic in that all k-fold intersections are affine linear subspaces of dimension n − k[8, Sec. B], and it is supertransversal [11, Def. 11] in that the bent hyperplane arrangement on Rm is transverse on cells[11, Def. 4] to the complex of the second layer map, in addition to satisfying both the LRA and TPIC conditions (See Figure 1a.) Yet, in contrast to the statement of [8, Lem. D15], the fibre ρ−1 (2,3,1) (θ1 ) is not determined by positive scalings and permutations of θ1 as ρ(2,3,1) (θ1 ) = ρ(2,3,1) (θ2 ) where 1 −1 −1 2 0 , 1 , −10 . θ2 = 1 , 1 1 0 1 1
4
PRANAVKRISHNAN RAMAKRISHNAN
This equality derives from the identity σ(x) − σ(−x) = x by the following ρ(2,3,1) (θ1 ) − ρ(2,3,1) (θ2 ) = σ(x1 + x2 − 2) + σ(−x1 − 1) + σ(−x2 − 1) − 6 − (σ(−x1 − x2 + 2) + σ(x1 + 1) + σ(x2 + 1) − 10) = x1 + x2 − 2 − x1 − 1 − x2 − 1 − 6 + 10 =0 (symmetries from the identity σ(x) − σ(−x) = x is further discussed in Section 4.) This shows that for a given parameter θ ∈ Ω(m,n,k) , it satisfying the conditions of the aforementioned Lemma is not strong enough to show that ρ−1 (m,n,k) (θ) ≃ Hn . And so at best such conditions at best show local identifiability [3, Def. 6]. Whether it is sufficient to show local identifiability shall remain as conjecture for this work. Acknowledgements: The core of this works stems from discussions with and attending the class of Kathryn Lindsey during the spring and fall of 2025, which extended into a research project with Eli Grigsby starting in earnest in spring of 2025. For this, I would be remiss not to express here my immense gratitude. I would also like to express my thanks in particular for the discussions I was able to have Joe Boninger, Qile Chen, Yaoying Fu, Spencer Leslie, and Ming-Hong Tee, from which this paper has immensely benefitted. This work was partially supported by the Institute for Foundations of Machine Learning (IFML). 2. Notation and Preliminaries 2.1. Notation. To recall the notation used in the introduction, Hn ≤ GLn (R) denotes the subgroup generated by permutations, which we shall denote Sn and diagonal matrices with positive coefficients, which we shall denote Dn+ . Likewise, Ω(m,n,k) = Mk×n (R) × Mn×m (R) × Rn+k denotes parameter space of architecture (m, n, k), and the ReLU activation function σ : Rl → Rl is the function given by x1 max{0, x1 } .. σ ... = , . xl max{0, xl } where the domain, and thereby codomain, is clear from context. A parameter in Ω(m,n,k) is denoted by θ = (M, A, b, c), where M ∈ Mk×n (R), A ∈ Mn×m (R), b ∈ Rn , c ∈ Rk , and admits an Hn -action denoted by · and given by h · (M, A, b, c) = (M h−1 , hA, hb, c). When k = 1, in place of M we shall write v and in place of c we shall write the capital C. Moreover, in the case where a parameter has no bias, that is to say is of the form (M, A, 0, 0), we may forego stating the bias and just write (M, A) (likewise (v, A) in place of (v, A, 0, 0).) The realization map ρ(m,n,k) : Ω(m,n,k) → C 0 (Rm , Rk ) is the Hn -invariant map given by ρ(m,n,k) (M, A, b, c) = M σ(Ax + b) + c, or if k = 1, ρ(m,n,1) (v, A, b, C) = v T σ(Ax + b) + C = ⟨v, σ(Ax + b)⟩ + C. −1 The fibre of θ, denoted by ρ−1 (m,n,k) (θ), is the set ρ(m,n,k) (ρ(m,n,k) (θ)). In addition, we also make use of a projection map πi : Ω(m,n,k) → Ω(m,n,1) throughout the work: for m1 c1 .. .. (M, A, b, c) = . , A, b, . ∈ Ω(m,n,k) , ck mk we define πi (M, A, b, c) = (mi , A, b, ci ).
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
5
Throughout Section 3, for some G-set X, StabG x denotes the stabilizer of x ∈ X under the G-action (We usually take X = Ω(m,n,k) and G = Hn , Sn , Dn+ .) Moreover, when used to denote an element of GLn (R), we let (i, j) denote the permutation of the i-th and j-th coordinate, and let λ1 .. diag(λ1 , . . . , λn ) = . λn and denote diag(λi1 , . . . , λim ) the matrix with λij on the ij -th entry and 1 otherwise. Finally, in Section 4, in accordance with notation from Commutative Algebra and Algebraic Geometry, we shall denote V (f ) = {x : f (x) = 0} 2.2. Preliminaries from the theory of Lie groups. Here we shall recall some relevant results from the theory of Lie groups that shall be relevant to this work, particularly in Section 5. We follow in the theory as described in [10, Ch. 7, 21]. Definition 1. Let G be a smooth manifold admitting the structure of a group where the maps G × G → G, (g1 , g2 ) 7→ g1 g2 G → G, g1 7→ g1−1 are smooth. Then we call G a (real) Lie group. What is relevant to us of course is to describe the group action of a Lie group on a smooth manifold, and the relationship between its structure and the manifold on which it acts. We shall start by definition the group action of a Lie group: Definition 2. Let G be a Lie group, and M a smooth manifold. A (left) Lie group action of G on M is a group action in which the map θg : M → M defined by x 7→ g · x is a smooth map for all g ∈ G. This action is free if g · x = x for some x ∈ M implies g is identity element in G, and is transitive if for all x, y ∈ M there exists some g ∈ G such that g · x = y. Finally, if the action is both free and transitive, we call it simply transitive. An important map which relates the structure of a Lie group to a manifold it acts on is the orbit map on a point x ∈ M given by g 7→ g · x
(1)
If G acts on M transitively, we call M a homogeneous G-space, and this map is surjective. Moreover, we are given the following result: Lemma 1 ([10], Th. 21.18). Let M be a homogeneous G-space. Then we get an (equivariant) diffeomorphism G/StabG x ≃ M given by (1) 3. Stabilizers of Parameter Space The goal of this section is to classify the possible stabilizers of a parameter θ ∈ Ω(m,n,k) under the group action of Hn , which we shall denote StabHn θ. Let diag(λ1 , . . . , λn ) denote the diagonal matrix with λi as the i-th diagonal entry, and denote diag(λi1 , . . . , λim ) the matrix with λij on the ij -th entry and 1 otherwise. Our main result of the section is the following: Proposition 2. Let θ ∈ Ω(m,n,k) be of the form θ = v1
T a b1 .1 . . . . vn , .. , .. , c bn aTn
6
PRANAVKRISHNAN RAMAKRISHNAN
where vi ∈ Rk , ai ∈ Rm , bi , c ∈ Rk . Let #{i : (vi , ai , bi ) = (0, 0, 0)} = n′ . Then StabHn θ = ⟨S⟩ × Hn′ where S is a finite set with elements of the form diag(λi , λj )(i, j), where λi λj = 1, with #S ≤ In particular, there is a bijection i = ̸ j S −→
n−n′ . 2
{i, j} : (vi , ai , bi ), (vj , aj , bj ) ̸= (0, 0, 0) ∃λ > 0, λ(v , a , b ) = (v , a , b ) i
We first note that Hn acts similarly to Mn×m term Rk . And so in particular:
i
i
j
j
j
(R) and Rn , while acting trivially on the constant
StabHn (M, A, b, c) = StabHn (M, A b , 0, 0)
(2)
Moreover, we note the following: Lemma 3. Let us denote πi : Ω(m,n,k) → Ω(m,n,1) to be the projection as before. Then k \
StabG πi (θ) = StabG θ
i=1
for any G ≤ Hn Proof. This follows from the definition of the stabilizer.
□
So we may just consider k = 1, and take all our parameters θ ∈ Ω(m,n,1) to be without bias. To this extent, we shall denote all our parameters with (v, A) in place of (v, A, 0, 0) ∈ Ω(m,n,1) Lemma 4. For any θ ∈ Ω, StabSn θ ≃ where
Y
Sνi
P
i νi ≤ n
Q Proof. Let p = pi ∈ StabSn θ such that pi are disjoint cycles. As they are disjoint permutation actions, it follows immediately that pi ∈ StabSn θ. Now if p is a k-cycle we see by the definition of permutation that (vi , aTi ) = (vp−1 (i) , aTp(i) ) for all i. And so, for any i, j such that p(i) ̸= i, p(j) ̸= j, (vi , aTi ) = (vj , aTj ). And so the 2-cycle (i, j) also stabilizes θ, proving our statement. □ Lemma 5. For any θ ∈ Ω(m,n,1) ,
StabDn+ θ ≃ Rµ>0
where µ ≤ n Proof. We see that if diag(λ1 , . . . , λn ) is in StabDn+ θ then as diag(λ1 , . . . , λn ) =
n Y
diag(λi )
i=1
with each diag(λi ) acting disjointly, we see that diag(λi ) also stabilizes θ. Moreover, we see that T T T −1 T T (vi λ−1 i , λi ai ) = (vi , ai ) for λi ̸= 1 if and only if (vi , ai ) = 0 and so (vi λ , λai ) = (vi , ai ) for all λ > 0, proving our statement. □ Proposition 6. For any θ ∈ Ω(m,n,1) , StabHn θ has the following properties: (1) Any h ∈ StabHn θ can be written of the form lp where l ∈ Dn+ and p ∈ Sn . (2) StabHn θ is generated by elements of the form l′ p′ where p′ is a k-cycle and l′ = diag(λ1 , . . . , λn ) ∈ Dn+ is a diagonal matrix where λi ̸= 1 only if p′ (i) ̸= i. In particular, a stabilizing element of the form l′ p′ acting non-trivially on a pair (vi , aTi ), (vj , aTj ) exists if and only if they are linearly dependent by some λ > 0.
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
7
(3) Say p′ is a k-cycle is such that p′ (i) ̸= i for some (vi , aTi ) ̸= 0. Then there is at most one l′ as defined above such that l′ p′ ∈ StabHn θ (4) Finally, in fact, StabHn θ is generated by elements of the form diag(λi , λj )(i, j), where λi λj = 1, and diag(λi ) Proof. We see that (i, j)diag(λ1 , . . . , λi , λj , . . . , λn ) = diag(λ1 , . . . , λj , λi , . . . , λn )(i, j) and so Dn+ Sn = Hn . This gives us (1). Now let l ∈ Dn+ and p ∈ Sn such that lp ∈ StabHn θ. We may write p as a product of disjoint cycles p1 . . . pk and so correspondingly write lp = l1 p1 . . . lk pk where l1 . . . lk = l and li acts nontrivially on a coordinate only if pi acts non-trivially on it. Each of these li pi act disjointly and so li pi ∈ StabHn θ. As such, let is take p to be a k-cycle now, and l = diag(λ1 , . . . , λn ) to be a diagonal matrix where T T λi ̸= 1 only if p(i) ̸= i. We then see that if lp ∈ StabHn θ then (vi λ−1 i , λp(i) mi ) = (vp−1 (i) , mp(i) ). This implies vp(i) = λp(i) vi and λp(i) aTi = aTp(i) , and so λp(i) (vi , aTi ) = (vp(i) , aTp(i) ). This implies that λ′pl (i) (vi , aTi ) = (vpl (i) , aTpl (i) ) λ′pl (i) =
l Y
λpj (i) .
j=1
Finally, let λ(vi , aTi ) = (vj , aTj ). Then the action diag(λi , λj )(i, j) where λi = λ, λj = λ−1 stabilizes θ, proving (2) The statement of (3) comes as a natural consequence of the work above, as assuming otherwise gives us two different λ, λ′ such that λ(vi , aTi ) = (vj , aTj ) = λ′ (vi , aTi ) for some (vi , aTi ) ̸= 0. To prove (4), we see by (2) that it suffices to prove it for p being a k-cycle, and l = diag(λ1 , . . . , λn ) being a diagonal matrix where λi ̸= 1 only if p(i) ̸= i. If lp acts non-trivially only on rows of the form (0, 0) then this follows immediately, so we shall assume it acts on at least one row, (vi , aTi ) ̸= 0, non-trivially. We see that (i, pk−1 (i)) . . . (i, p(i)) = p and also that λ′pl (i) (vi , aTi ) = (vpl (i) , aTpl (i) ) (l)
(l)
(l) (l)
(l)
from the work before. Then we see that diag(λi , λpl (i) )(i, pl (i)), where λi λpl (i) = 1 and λi
=
λ′pl (i) stabilizes θ. Moreover, there exists some l† ∈ Dn+ such that (k−1)
diag(λi
(k−1)
(1)
(1)
(1)
(1)
, λpl (k−1) )(i, pl (k − 1)) . . . diag(λi , λp(i) )(i, p(i)) = l† p
also stabilizes θ. This means by (3) that (k−1)
diag(λi
(k−1)
, λpl (k−1) )(i, pl (k − 1)) . . . diag(λi , λp(i) )(i, p(i)) = lp
proving (4).
□
Corollary 7. Let θ be a parameter with n′ rows of the form (0, 0). Then StabHn θ = ⟨S⟩ × Hn′
8
PRANAVKRISHNAN RAMAKRISHNAN
where S is a finite set with elements of the form diag(λi , λj )(i, j), where λi λj = 1, with #S ≤ In particular, there is a bijection i ̸= j (vi , aTi ), (vj , aTj ) ̸= (0, 0)} S −→ {i, j} : ∃λ > 0, λ(vi , aTi ) = (vj , aTj )
n−n′ . 2
Proof of Theorem 2. This follows from Corollary 7 and Lemma 3: By Corollary 7 we see that StabHn πi (θ) = ⟨Si ⟩ × Hn′i . And so by Lemma 3, k \
⟨Si ⟩ × Hn′i = StabHn θ.
i=1
It follows that StabHn θ = ⟨S⟩ × Hn′ ′ where S and n are given as in the Theorem.
□
Finally, we see applying the steps similar as above the following result: Lemma 8. Let A ∈ Mn×m (R), b ∈ Rn be of the form T a1 b1 .. .. A = . ,b = . bn aTn Let #{i : (ai , bi ) = 0} = n′ . Then StabHn (A, b) = ⟨S⟩ × Hn′ where S is a finite set with elements of the form diag(λi , λj )(i, j), where λi λj = 1, with #S ≤ In particular, there is a bijection i = ̸ j S −→
n−n′ . 2
(ai , bi ), (aj , bj ) ̸= (0, 0) {i, j} : ∃λ > 0, λ(a , b ) = (a , b ) i
i
j
j
Corollary 9. Let θ = (M, A, b, c) be a parameter such that StabHn (A, b) ̸= 1. Then ρ−1 (m,n,k) (θ) ̸≃ Hn Proof. By our hypothesis and Lemma 8, we know that there exist i, j such that (ai , bi ) = (0, 0) or there exists some λ > 0 such that λ(ai , bi ) = (aj , bj ). This gives us two cases to consider: When (ai , bi ) = (0, 0), we see that ρ(m,n,k) (M, A, b, c) = ρ(m,n,k) (M † , A, b, c) where ( h i vl l ̸= i † M † = v1† . . . vn† , vl = . 0 l=i So ρ−1 (m,n,k) (θ) ̸≃ Hn . When there exists some λ > 0 such that λ(ai , bi ) = (aj , bj ), we see that ρ(m,n,k) (M, A, b, c) = ρ(m,n,k) (M ′ , A, b, c) where v l ̸= i, j ′ ′ l ′ ′ M = v1 . . . vn , vl = 0 l=i vl + λvi l = j. So ρ−1 (m,n,k) (θ) ̸≃ Hn .
□
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
9
4. Structure of im ρ(m,n,k) In order to derive some statement on the structure of fibres, diffeomorphic to Hn , we shall first describe the structure of im ρ(m,n,k) as a quotient space of parameter space Ω(m,n,k) . To this extent, it is expedient to first understand the structure of im ρ(m,n,1) as a quotient space of Ω(m,n,1) in order to build up to the construction of im ρ(m,n,k) . As such, let us consider functions in the architecture Rm → Rn → R. We see that for any such f , it is of the form f (x) = v T σ(Ax + b) + C, for some A ∈ Mm×n (R), v, b ∈ Rn , and C ∈ R. We know that there is a diagonal Hn action which preserves the function and so f (x) = v T h−1 σh(Ax + b) + C for all h ∈ Hn . One might hope to regard the space Hn \Ω(m,n,1) , being the equivalence classes of Ω(m,n,1) under the Hn -action prescribed above, as the space of functions f ∈ C 0 (Rm , R) realizable via ReLU on 2 layers: that is to say for any f ∈ im ρ(m,n,1) , there is a unique class C ∈ Hn \Ω(n,m,1) such that ρ(n,m,1) (θ) = f for θ ∈ C. Indeed this is not true by considering the following obvious case: Lemma 10. Let
T v1 a1 b1 .. .. .. (v, A, b, C) = . , . , . , C . vn
aTn
bn
such that vi = 0 for some i. We see that ρ(m,n,1) (v, A, b, C) = ρ(m,n,1) (v, Aw , bλ , C) for all w ∈ Rm , λ ∈ R where
aT1 b1 .. .. . . T a bi−1 i−1 λ . Aw = Tw , bλ = a bi+1 i+1 .. ... . aTn
bn
Moreover, even if we require vi ̸= 0 for all i in our parameter, we still ourselves short of our hope as we can find the following two relations by direct calculation3: Lemma 11. (1) Suppose there exists some λ > 0 such that λ(aj , bj ) = (ai , bi ) for some i ̸= j. Then ρ(m,n,1) (v, A, b, C) = ρ(m,n,1) (v ′ , A, b, C) where l ̸= i, j vl ′ vl = vi + λvj l = i 0 l=j (2) Suppose ai = 0 for some i. Then ρ(m,n,1) (v, A, b, C) = ρ(m,n,1) (v † , A, b, C + vi σ(bi )) where ( vl l ̸= i † vl = 0 l=i 3It is in fact easy to see that there more than these two relations. However, for the sake of narrative we shall
forego their mention for now.
10
PRANAVKRISHNAN RAMAKRISHNAN
It then follows that the space im ρ(n,m,1) is a quotient of the space Hn \Ω(n,m,1) / ∼ where the equivalence ∼ is generated4 by T 0 a1 0 b1 0 0 v2 aT b1 v2 aT b1 1 1 v3 , aT , b3 , C ∼ v3 , aT , b3 , C 3 3 .. .. .. .. .. .. . . . . . . T T a1 a1 v1 b1 v1 + v 2 b1 v2 aT b1 0 aT b1 1 1 v3 , aT , b3 , C ∼ v3 , aT , b3 , C 3 3 .. .. .. .. .. .. . . . . . . 0 0 v1 b1 0 0 v2 aT b2 v2 aT b2 , 2 , , C ∼ , 2 , , C + v1 σ(b1 ) .. .. .. .. .. .. . . . . . . While this space, as we shall learn, does not have a one-to-one correspondence with im ρ(m,n,1) , it gives us enough information to define a strong enough canonical form, which we shall call the minimal form, to understand the structure of im ρ(n,m,1) : Definition 3. For a given parameter θ = (v, A, b, C), consider it’s equivalence class, denoted as Cθ , in Hn \Ω(n,m,1) / ∼ where the equivalence ∼ is generated by (1) T 0 a1 0 b1 0 0 v2 aT b1 v2 aT b1 1 1 v3 , aT , b3 , C ∼ v3 , aT , b3 , C 3 3 .. .. .. .. .. .. . . . . . . (2) T T a1 a1 b1 v1 + v 2 v1 b1 v2 aT b1 0 aT b1 1 1 v3 , aT , b3 , C ∼ v3 , aT , b3 , C 3 3 .. .. .. .. .. .. . . . . . . (3) 0 0 0 v1 b1 0 v2 aT b2 v2 aT b2 , 2 , , C ∼ , 2 , , C + v1 σ(b1 ) .. .. .. .. .. .. . . . . . . 4As this equivalence acts simultaneously on the space Ω
(n,m,1) may rely on the permutation equivalence given by the Hn -action to extend the equivalence to all cases covered by Lemmas 10 and 11
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
11
Now, let f be any function such that f (1) > f (−1) > f (0) and consider the following subset of Cθ : u ∈ {0, ±1}n , ′ ′ u = 0 ⇔ (a , b ) = (0, 0), i i i ′ ′ ′ (u, A , b , C ) ∈ Cθ : f (ui ) ≥ f (ui+1 ), f (ui ) = f (ui+1 ) ⇒ (ai , bi ) ≥l (ai+1 , bi+1 ) where >l denotes the lexical ordering. This set is endowed with an ordering by taking ⟨u, u⟩, and we shall denote the minimum of this set with respect to this ordering as θmin = (vmin , Amin , bmin , Cmin ), ′ calling it the minimal form of (v, A, b, C). Moreover, θmin = θmin if and only if Cθ = Cθ′ . Finally, if θ = θmin then we shall call θ minimal. Remark 1. The equivalence ∼ does not represent a set of functional symmetries unique to ReLU but rather is applicable almost universally to shallow ReLU networks. In place of σ, let us take f = (f1 , . . . , fn ) to be a function where fi = fj for all choices of i, j, and consider a general k. For any parameter T b1 a .1 . . θ = (M, A, b, c) = v1 . . . vn , . , .. , c bn aTn (f )
in Ω(m,n,k) , we may define a realization with respect to f , denoted as ρ(m,n,k) , like so: (f )
ρ(m,n,k) (θ) = M f (Ax + b) + c. Moreover, there is an Sn action on Ω(m,n,k) given by s · θ = (M s−1 , sA, sb, c), s ∈ Sn (f )
(f )
such that ρ(m,n,k) is an Sn -invariant map. Then im ρ(m,n,k) is a quotient space of Sn \Ω(m,n,k) / ∼f where the equivalence ∼f is generated by T 0 a1 b1 0 aT b1 aT b1 1 1 0 v2 v3 . . . , aT , b3 , c ∼ 0 v2 v3 . . . , aT , b3 , c 3 3 .. .. .. .. . . . . T T a1 a1 b1 b1 T T a1 b1 a1 b1 v1 v2 v3 . . . , aT , b3 , c ∼ v1 + v2 0 v3 . . . , aT , b3 , c 3 3 .. .. .. .. . . . . 0 0 b1 0 T T v1 v2 . . . , a2 , b2 , c ∼ 0 v2 . . . , a2 , b2 , c + f (b1 )v1 . .. .. .. .. . . . . This forms a general theory of quotients for neural networks with activation function of the form of f . Definition 4. We shall say a parameter (v, A, b, C) has 0-factors of rank k if k = #{ei | ⟨vmin , ei ⟩ = 0}. Likewise if a parameter (v, A, b, C) has 0-factors of rank 0, we shall say it has no 0-factors. Example 1. Given below are some examples of minimal forms of parameters
12
PRANAVKRISHNAN RAMAKRISHNAN
Form 0-factor Rank Parameter Minimal 0 0 0 0 0 0 0 , A, b, C 0 , 0 0 0 , 0 , C 3 0 0 0 0 0 0 2 1 4 4 4 11 11 11 0 0 3 , 1 1 1 , 0 , C −1 , 5 2 1 , 0 , C 1 −1 5 2 1 0 0 0 0 0 0 1 1 2 4 0 2 4 0 7 7 1 , 1 1 3 , 2 , 7 1 , 1 1 3 , 2 , 4 1 3 −1 0 0 0 0 0 0 0 0 1 0 36 0 63 9 0 4 0 7 1 , 1 7 3 , 2 , 8 1 , 1 7 3 , 2 , 8 0 −1 10 5 15 45 −5 2 1 3 9 T Lemma 12. If v1T σ(A1 + b1 ) + C1 = v2T σ(A2 + b2 ) + C2 then v1,min σ(A1,min + b1,min ) + C1,min = T v2,min σ(A2,min + b2,min ) + C2,min .
Definition-Lemma 5. Given a parameter θ = (v, A, b, C) with zero factors of rank k < n, we see that there exist unique vectors vr ∈ Rn−k , br ∈ Rm−k , and a unique matrix Ar ∈ M(n−k)×m (R) such that θr = (vr , Ar , br , Cr ) is minimal with no 0-factors and v T σA = vrT σAr . We shall call θr the 0-factor reduction of θ in codimension k. Moreover, if θ has zero factors of rank n, by convention we shall say θr = (0, 0, 0, Cr ) ∈ R4 . Finally, θ = θr if and only if θ is minimal with no zero factors, and for θi ∈ Ω(m,n,1) , θ1,r = θ2,r if and only if θ1,min = θ2,min . Definition 6. Any two vectors v, w are linearly semi-independent if there exists no λ ≥ 0 such that λv = w, and linearly semi-dependent if there is such a λ ≥ 0. Now let v1 , . . . , vn be an indexed set of vectors. We call them pairwise linearly semi-independent if all distinct pairs vi , vj are linearly semi-independent. Likewise, this set is called pairwise linearly independent if instead of λ ≥ 0 we allows λ to be any real number. Lemma 13. Let (v, A, b, C) be minimal with no 0-factors. Then the vectors formed by the rows of A and the corresponding coordinates of b are pairwise linearly semi-independent. Proof. This follows from the minimality of (v, A, b, C)
□
Proposition 14. Let (v, A, b, C) be minimal with no 0-factors, and A ̸= 0. Then v T σ(Ax+b)+C = T x + D for some linear transformation T : Rn → R and D ∈ R if and only if v = e1 + . . . + el − el+1 − . . . − e2l and T a1 b1 .. .. . . T a bl l ,b = A= −aT −b1 1 . .. .. . −aTl
with
−bl
l X ⟨ai , x⟩ + bi + C = T x + D i=1
Proof. We see that to show this is equivalent to showing that k X i=1
σ(⟨vi , x⟩ + αi ) =
l X i=1
σ(⟨wi , x⟩ + βi ) + T x + D
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
13
for (v1 , α1 ), . . . , (vk , αk ), (w1 , β1 ), . . . , (wl , βl ) pairwise linearly semi-independent can only occur when k = l and (vi , αi ) = −(wi , βi ) for all i (by reordering the terms.) Let us say either k > l with vl+1 ̸= 0 (this follows from minimality) or (vi , αi ) ̸= −(wj , βj ) for all j with vi ̸= 0. Our assumption then gives that there is a vector x1 such that αi /⟨vi , x1 ⟩ ̸= βj /⟨wj , x1 ⟩ for all choices of j. Without loss of generality let us say (v1 , α1 ) satisfies this condition. And so restricting our function to tx1 for t ∈ R we reduce to one of two cases, denoting c1 = ⟨v1 , x1 ⟩: ′
λ1 σ(c1 t + α1 ) +
′
k X
λi σ(ci t + αi′ ) =
i=2
l X
σ(di t + βi′ ) + Λt + D
i=1
or
′
λ1 σ(c1 t + α1 ) + λ′1 σ(−c1 t − α1 ) +
k X
′
λi σ(ci t + αi′ ) =
l X
µi σ(di t + βi′ ) + Λt + D
i=2 i=1 ′ ′ ′ for λi , µj , λ1 > 0 and (ci , αi ), (di , βi ) pairwise linearly semi-independent, and (c1 , α1 ) pairiwse linearly independent with (ci , αi′ ), (di , βi′ ), i ̸= 1. We see the equations above is equivalent to writing ′
λ1 σ(c1 t + α1 ) =
l X
′
σ(di t + βi′ ) −
i=1
k X
λi σ(ci t + αi′ ) + Λt + D
i=2
or
′
λ1 σ(c1 t + α1 ) + λ′1 σ(−c1 t − α1 ) =
l X
′
σ(di t + βi′ ) −
i=1
k X
λi σ(ci t + αi′ ) + Λt + D
i=2
By assumption, we see that α1 /c1 ̸= αi′ /ci , βj′ /dj , i ̸= 1 and so we can pick some neighbourhood U of −α1 /c1 such that for all t ∈ U , ′
l X
′
σ(di t + βi′ ) −
i=1
k X
λi σ(ci t + αi′ ) + Λt + D
i=2
is a linear function, and so in particular is differentiable at −α1 /c1 . However we see clearly that neither λ1 σ(c1 t + α1 ) nor λ1 σ(c1 t + α1 ) + λ′1 σ(−c1 t − α1 ) is differentiable at −α1 /c1 , giving us a contradiction. □ Corollary 15. Let (v, A, b, C) be an arbitrary parameter, and denote T v1 a1 b1 .. .. .. v = . ,A = . ,b = . vn
aTn
bn
with vi ̸= 0 and the property that there exists no λ < 0 such that λ(ai , bi ) = (aj , bj ). Then if (v ′ , A′ , b′ , C ′ ) = (v, A, b, C) and (v, A, b, C) has zero factors of rank l, then (v ′ , A′ , b′ , C ′ ) has zero factors of at most rank l. Proof. By considering the 0-factor reductions of (v, A, b, C) and (v ′ , A′ , b′ , C ′ ) we reduce this problem: For λi , λ′j ∈ {±1}, ai , a′j ̸= 0, (a1 , b1 ), . . . , (ak , bk ) pairwise linearly independent and (a′1 , b′1 ), . . . , (a′k′ , b′k′ ) pairwise linearly semi-independent, ′
k X j=1
λ′j σ(⟨a′j , x⟩ + b′j ) + C ′ =
k X
λi σ(⟨ai , x⟩ + bi ) + C
i=1
is impossible if k ′ < k. Moreover, if (a′j , b′j ) = (ai , bi ) we may add both sides by −λ′j σ(⟨a′i , x⟩+b′i ) and reduce, by which we may assume without loss of generality that (a1 , b1 ), . . . , (ak , bk ), (a′1 , b′1 ), . . . , (a′k′ , b′k′ ) are pairwise linearly semi-independent. This is equivalent to producing a minimal parameter
14
PRANAVKRISHNAN RAMAKRISHNAN
(v † , A† , b† , C † ) with no 0-factors in M1×(k+k′ ) (R)×M(k+k′ )×m (R)×R(k+k )+1 such that (a†1 , b†1 ), . . . , (a†k+k′ , b†k+k′ ) are pairwise linearly independent and ′
v †T σ(A† x + b† ) + C † = 0. However as k > k ′ , this is impossible by Proposition 14.
□
Corollary 16. Let (v, A, b, C) be a minimal parameter with no 0-factors such that (a1 , b1 ), . . . , (an , bn ) are pairwise linearly independent. Suppose that there exists a minimal parameter (v ′ , A′ , b′ , C ′ ) such that v ′T σ(A′ x + b′ ) + C ′ = v T σ(Ax + b) + C, and that there exists some i such that vi′ ̸= 0 and there exists a λ > 0 with (a′i , b′i ) = λ(a1 , b1 ). Then v1 − λvi′ = 0. Proof. Supposing towards contradiction by letting v1 −λvi′ ̸= 0 , subtracting both sides by λvi′ σ(⟨ai , x⟩+ bi ) gives a counterexample to Corollary 15, and so cannot be true. □ Definition 7. For parameters θi = (vi , Ai , bi , Ci ) ∈ Ω(m,ni ,1) we define θ1 ⊖ θ2 ∈ Ω(m,n1 +n2 ,1) to be v1 A b θ1 ⊖ θ 2 = , 1 , 1 , C1 − C2 −v2 A2 b2 Lemma 17. (θ1 ⊖ θ2 )r = (0, 0, 0, 0) if and only if θ1,r = θ2,r Proof. We see that (θ1 ⊖θ2 )r = (θ1,r ⊖θ2,r )r as the 0-factor reduction depends only on the equivalence class of θ1 ⊖ θ2 in Hn \Ω(m,n1 +n2 ,1) / ∼, with θ1 ⊖ θ2 and θ1,min ⊖ θ2,min lying in the same equivalence class. As such, let us assume θ1 , θ2 are reduced, and denote T ai,1 vi,1 bi,1 θi = ... , ... , ... , Ci vi,ni bi,ni aTi,ni We see that the first and third generating equivalence of ∼ in the definition of the minimal form act trivially on the parameter θr ⊖ θr′ . Then n1 = n2 = n and for all rows (a1,i , b1,i ) there exist (a2,j , b2,j ) and λi > 0 such that λi (a1,i , b1,i ) = (a2,j , b2,j ). This means that θ1 ⊖ θ2 are in the same equivalence class of Hn \Ω(m,2n,1) / ∼ as T a1,1 v1,1 − λ1 v2,p(1) b1,1 .. .. .. . . . T v1,n − λn v2,p(n) a b1,n , 1,n , , C1 − C2 0 0 0 .. . .. . . . . 0 0 0 for some permutation p ∈ Sn . As we assume θi are reduced, we know that vi,j = ±1 for all i, j, which means that λi = 1 for all i. This means that v1,j = v2,p(j) and (aT1,j , b1,j ) = (aT2,p(j) , b2,p(j) ), and since θ2 is reduced means that p = e ∈ Sn and so θ1 = θ2 when θi are reduced, proving our statement. □ Corollary 18. For θ1 , θ2 ∈ Hn \Ω(m,n,1) / ∼, (θ1 ⊖ θ2 )r = (0, 0, 0, 0) if and only if θ1,min = θ2,min Theorem 3. The quotient space im ρ(m,n,1) is given by Hn \Ω(m,n,1) / ≡
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
15
where θ1 ≡ θ2 if and only if θ1 ∼ θ2 or T a1 1 b1 .. .. .. . . . T 1 a bl l (θ1 ⊖ θ2 )r = T , , C −b −1 −a 1 1 .. .. . . . .. −1 −aTl −bl where
P
ai = 0 and
P
bi + C = 0
Proof. We see that if ρ(m,n,1) (θ1 ) = ρ(m,n,1) (θ2 ) that ρ(m,2n,1) (θ1 ⊖ θ2 ) = 0. We see by Corollary 18 that (θ1 ⊖θ2 )r = (0, 0, 0, 0) if and only if θ1 and θ2 lie in the same equivalence class of Hn \Ω(m,n,1) / ∼. On the other hand, if (θ1 ⊖ θ2 )r ̸= (0, 0, 0, 0) we see by Proposition 14 that (θ1 ⊖ θ2 )r must be of the form T a1 1 b1 .. .. .. . . . T 1 a bl l , (θ1 ⊖ θ2 )r = , C T −1 −a1 −b1 .. . . . .. .. where
P
P
ai = 0 and
−1 bi + C = 0, as desired.
−aTl
−bl
□
Theorem 4. The quotient space im ρ(m,n,k) is given by Ω(m,n,k) / ≡k where θ1 ≡k θ2 if and only if πi (θ1 ) ≡ πi (θ2 ) ∈ Hn \Ω(m,n,1) for all projections πi : Ω(m,2n,k) → Ω(m,2n,1) . Proof. We see that ρ(m,n,k) (θ1 ) = ρ(m,n,k) (θ2 ) if and only if ρ(m,n,1) (πi (θ1 )) = ρ(m,n,1) (πi (θ2 )) for all i, which is equivalent to the condition that πi (θ1 ) ≡ πi (θ2 ) in Ω(m,n,1) □ 5. Proof of Theorem 1 Our goal this section is to prove the following theorem, which essentially gives the statement of Theorem 1: (1)
Theorem 5. Let Ω(m,n,k) ⊂ Ω(m,n,k) be the set of parameters θ such that the action of Hn on (1)
ρ−1 (m,n,k) (θ) is simply transitive. Then Ω(m,n,k) contains a Zariski open set. With our previous work in Section 4, we have essentially approached the solution. All that (1) remains is to prove some additional results and explicitly construct a Zariski open set in Ω(m,n,k) . (1)
In order to do this, we shall first start by reducing the problem to the Ω(m,n,1) : Lemma 19. The projection map πi : Ω(m,n,k) → Ω(m,n,1) is Zariski continuous. Proof. Let us denote
m1 c1 .. .. (M, A, b, c) = . , A, b, . ∈ Ω(m,n,k) . mk
ck
Let f (v, A, b, C) : Ω(m,n,1) → R be some polynomial function. We see then that πi−1 (V (f )) = V (fi ) where fi (M, A, b, c) = f (mi , A, b, ci ) □
16
PRANAVKRISHNAN RAMAKRISHNAN (1)
(1)
Proposition 20. If Ω(m,n,1) contains a Zariski open set then Ω(m,n,k) contains a Zariski open set. Namely, denoting proji : Rn → R as the projection to the i-th coordinate, proji (ρ(m,n,k) (θ)) = ρ(m,n,1) (πi (θ)) which in particular gives us that (3)
−1 πi (ρ−1 (m,n,k) (θ)) ⊆ ρ(m,n,1) (πi (θ))
Moreover, recalling the definition of the fibre product, for any given subsets S1 ⊆ A × C, S2 ⊆ A × C, we see that S1 ×C S2 can be interpreted like so: {(a, b, c) ∈ A × B × C : (a, c) ∈ S1 , (b, c) ∈ S2 }. Given this, we see there is the obvious inclusion, denoting Ω′ = {(A, b) : (v, A, b, C) ∈ Ω(m,n,1) } = {(A, b) : (v, A, b, C) ∈ Ω(m,n,k) }: k
×ρ
−1 (π (θ)) ⊆ ρ−1 (m,n,k) (θ). Ω′ (m,n,1) i i=1
However by Equation 3 we see that in fact k
(4)
×ρ
−1 (π (θ)) = ρ−1 (m,n,k) (θ). Ω′ (m,n,1) i i=1
With this, we shall prove this abstract result in category theory applicable to our case: Lemma 21. Let A, B, C, D be objects in some category such that we have the diagram f1
D f
e1
A ×C B f2
B g1
e2 g2
A C with f1 , f2 isomorphisms, and g1 , g2 monomorphisms. Then f is an isomorphism. Proof. We see that A ×C B ≃ D ×C D where D ×C D
f1−1 ◦e1
f2−1 ◦e2
D
D g1 ◦f1
g2 ◦f2
C
We see that g2 ◦ f2 = g1 ◦ f1 and are monomorphisms and so D ×C D ≃ D, which implies f2−1 ◦ e2 is an isomorphism. This therefore means that f = (f2−1 ◦ e2 )−1 is an isomorphism. □ Proof of Proposition 20. To prove this statement, we see by Lemma 19 and Equation 4 that it −1 suffices to show ρ−1 (m,n,1) (πi (θ)) ≃ Hn for all i implies ρ(m,n,k) (θ) ≃ Hn . By Lemma 21, This −1 −1 ′ reduces to showing ρ−1 (m,n,k) (θ) ≃ Hn implies ρ(m,n,k) (θ) → Ω is injective. Suppose ρ(m,n,k) (θ) ≃ Hn ′ and ρ−1 (m,n,k) (θ) → Ω is not injective. Then StabHn (A, b) ̸= 1, which implies by Corollary 9 that
ρ−1 (m,n,k) (θ) ̸≃ Hn , giving us a contradiction.
□
A COMPLETE SYMMETRY CLASSIFICATION OF SHALLOW RELU NETWORKS
17
Now that we have reduced this problem to that of Ω(m,n,1) , we shall explicitly construct a Zariski (1)
open set U∼ of Ω(m,n,1) . First, we shall construct a Zariski open set of Ω(m,n,1) in which the equivalence ∼ acts trivially in Hn \Ω(m,n,1) . From this we shall construct an open set of U∼ in which the equivalence ≡ acts trivially in Hn \Ω(m,n,1) : Lemma 22. Let
u1 w1 .. .. u = . ,w = . .
un Then u and w are linearly dependent if and only if
wn
ui wj − wi uj = 0 for all i, j, i ̸= j. Definition 8. For u ∈ An , w ∈ An , let V dep (u, w) =
\
V (ui wj − wi uj ) ⊂ A2n
i̸=j n denote the Zariski closed set of ordered pairs of linearly dependent vectors in A . Likewise for u1 .. u = . let un V (u) = V (u1 , . . . , un )
Lemma 23. Denote
T v1 a1 b1 .. .. .. θ = . , . , . , C . vn
aTn
bn
Then U∼ = (V1 ∪ V2 ∪ V3 )c , where V1 =
n [
V (vi )
i=1
V2 =
[
V dep ((ai , bi ), (aj , bj )).
i̸=j
V3 =
[
V (ai )
i
Proof. Let us denote by S(i) the set of parameters θ ∈ Ω(m,n,1) such that the equivalence (i) as in Definition 3 acts nontrivially on θ in Hn \Ω(m,n,1) . By their definition, we see that Vi contains S(i). □ It follows immediately that the minimal form of any parameter in U∼ has no 0-factors. With this in mind we prove the following statement: Proposition 24. Let θ = (v, A, b, C) be an arbitrary parameter, and denote T v1 a1 b1 .. .. .. v = . ,A = . ,b = . . vn bn aTn
18
PRANAVKRISHNAN RAMAKRISHNAN
Let us assume the following conditions: vi ̸= 0, (a1 , b1 ), . . . , (an , bn ) pairwise linearly independent, and n X β(i)vi ai ̸= 0. i=1
for all functions β : {1, . . . , n} → {0, ±1}, β ̸= 0. Then the only other parameters in Ω(m,n,1) which realize v T σ(Ax + b) + C are of the form (vh−1 , hA, hb, C) where h ∈ Hn . Proof. We see by our hypothesis that (v, A, b, C) has no 0-factors, and so it follows that n X
β(i)ai,min ̸= 0,
i=1
for all functions β : {1, . . . , n} → {0, ±1}, β ̸= 0. So we may assume without loss of generality that (v, A, b, C) is minimal with no 0-factors. Now if θ′ = (v ′ , A′ , b′ , C ′ ) is another minimal parameter such that v ′T σ(A′ x+b′ )+C ′ = v T σ(Ax+b)+C, we see by Corollary 15 that it must have no 0-factors. Moreover, by definition ρ(m,2n,1) (θ ⊖ θ′ ) = 0, which implies ρ(m,n,1) ((θ ⊖ θ′ )r ) = 0. By Corollary 16, A b we see that the rows of , ′ are pairwise linearly semi-independent. By Proposition 14 ′ A r b r implies that there exists some indices {i1 , . . . , in′ } and a morphism of sets γ : {1, . . . , r} → {±1} such that γ(1)aTi1 γ(1)bi1 1 .. .. .. . . . ′ )aT ′ γ(n γ(n )b 1 i i ′ ′ ′ ′ n , n (θ ⊖ θ )r = , ,C − C T or (0, 0, 0, 0). −1 −γ(1)ai1 −γ(1)bi1 . .. .. .. . . ′ ′ T −1 −γ(n )bin′ −γ(n )ai ′ n
And so ′
′
ρ(m,n,1) ((θ ⊖ θ )r ) =
n X
γ(l)(σ(aTil x + bil ) − σ(−aTil x − bil ))
l=1 ′
=
n X
γ(l)(aTil x + bil )
l=1 ′ This means there exists some β : {1, . . . , n} → {0, ±1} such that
0=
n X
β ′ (i)(aTi x + bi )
i=1
However by assumption n X
β(i)ai ̸= 0,
i=1
for all β : {1, . . . , n} → {0, ±1}, β ̸= 0 and so β ′ = 0. This means that there cannot exist any such indices {i1 , . . . , in′ }, and so (θ ⊖ θ′ )r = (0, 0, 0, 0). This means by Lemma 17 that θ and θ′ must lie in the same Hn -orbit. □ Definition 9. For β ∈ Hom({1, . . . , n}, {0, ±1}), define V a (β) = V
n X i=1
! β(i)ai
REFERENCES
19
Proof of Theorem 5. Let H = Hom({1, . . . , n}, {0, ±1}) − {0} Define the following Zariski open set: U = U4 ∩ U∼ where
c
U4 =
[
V (β) .
β∈H
We see that all parameters in U satisfy the conditions of Proposition 24 and so for all θ ∈ U, ρ−1 (θ) (1) admits the group structure of Hn . Thus U ⊂ Ω(m,n,1) , as desired. □ Proof of Theorem 1. By Theorem 5, it just remains to show that Hn is diffeomorphic to ρ−1 (m,n,k) (θ) if the action of Hn is simply transitive. However, supposing Hn acts simply transitively on ρ−1 (m,n,k) (θ), we see that ρ−1 (m,n,k) (θ) is a homogeneous Hn -space, and that StabHn θ ≃ 1. So by Lemma 1, ρ−1 (m,n,k) (θ) ≃ Hn , as desired.
□ References
[1] Francesca Albertini and Eduardo D. Sontag. “For neural networks, function determines form”. In: Neural Networks 6.7 (1993), pp. 975–990. issn: 0893-6080. doi: https : / / doi . org / 10.1016/S0893- 6080(09)80007- 5. url: https://www.sciencedirect.com/science/ article/pii/S0893608009800075. [2] Joachim Bona-Pellissier, François Malgouyres, and François Bachoc. Geometry-induced Regularization in Deep ReLU Neural Networks. 2026. arXiv: 2402.08269 [cs.AI]. url: https: //arxiv.org/abs/2402.08269. [3] Joachim Bona-Pellissier, François Malgouyres, and François Bachoc. Local Identifiability of Deep ReLU Neural Networks: the Theory. 2022. arXiv: 2206.07424 [math.ST]. url: https: //arxiv.org/abs/2206.07424. [4] J. Elisenda Grigsby et al. “Functional dimension of feedforward ReLU neural networks”. In: Advances in Mathematics 482 (Dec. 2025), p. 110636. issn: 0001-8708. doi: 10.1016/j.aim. 2025.110636. url: http://dx.doi.org/10.1016/j.aim.2025.110636. [5] Charles Fefferman and Scott Markel. “Recovering a Feed-Forward Net From Its Output”. In: Advances in Neural Information Processing Systems. Ed. by J. Cowan, G. Tesauro, and J. Alspector. Vol. 6. Morgan-Kaufmann, 1993. url: https://proceedings.neurips.cc/ paper_files/paper/1993/file/e49b8b4053df9505e1f48c3a701c0682-Paper.pdf. [6] Bella Finkel et al. “Activation degree thresholds and expressiveness of polynomial neural networks”. In: Algebraic Statistics 16.2 (Sept. 2025), pp. 113–130. issn: 2693-2997. doi: 10. 2140/astat.2025.16.113. url: http://dx.doi.org/10.2140/astat.2025.16.113. [7] Charles Godfrey et al. On the Symmetries of Deep Learning Models and their Internal Representations. 2023. arXiv: 2205.14258 [cs.LG]. url: https://arxiv.org/abs/2205.14258. [8] Elisenda Grigsby, Kathryn Lindsey, and David Rolnick. “Hidden Symmetries of ReLU Networks”. In: Proceedings of the 40th International Conference on Machine Learning. Ed. by Andreas Krause et al. Vol. 202. Proceedings of Machine Learning Research. PMLR, 23–29 Jul 2023, pp. 11734–11760. url: https://proceedings.mlr.press/v202/grigsby23a.html. [9] Joe Kileel, Matthew Trager, and Joan Bruna. On the Expressive Power of Deep Polynomial Neural Networks. 2019. arXiv: 1905.12207 [cs.LG]. url: https://arxiv.org/abs/1905. 12207. [10] John M. Lee. Introduction to Smooth Manifolds. Springer, 2013. [11] Marissa Masden. Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks. 2022. arXiv: 2207.07696 [cs.LG]. url: https://arxiv. org/abs/2207.07696.
20
REFERENCES
[12] Henning Petzka, Martin Trimmel, and Cristian Sminchisescu. “Notes on the Symmetries of 2-Layer ReLU-Networks”. In: Proceedings of the Northern Lights Deep Learning Workshop 1 (Feb. 2020), p. 6. doi: 10.7557/18.5150. [13] Mary Phuong and Christoph H. Lampert. “Functional vs. parametric equivalence of Re{LU} networks”. In: International Conference on Learning Representations. 2020. url: https : //openreview.net/forum?id=Bylx-TNKvH. [14] David Rolnick and Konrad Kording. “Reverse-engineering deep ReLU networks”. In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, 13–18 Jul 2020, pp. 8178–8187. url: https://proceedings.mlr.press/v119/rolnick20a.html. [15] Pierre Stock and Rémi Gribonval. “An Embedding of ReLU Networks and an Analysis of Their Identifiability”. In: Constructive Approximation 57.2 (July 2022), pp. 853–899. issn: 14320940. doi: 10.1007/s00365-022-09578-1. url: http://dx.doi.org/10.1007/s00365022-09578-1. [16] Yani Zhang and Helmut Bölcskei. Complete Identification of Deep ReLU Neural Networks by Many-Valued Logic. 2026. arXiv: 2602.00266 [cs.AI]. url: https://arxiv.org/abs/ 2602.00266. [17] Bo Zhao, Robin Walters, and Rose Yu. Symmetry in Neural Network Parameter Spaces. 2025. arXiv: 2506.13018 [cs.LG]. url: https://arxiv.org/abs/2506.13018. [18] Bo Zhao et al. Symmetries, flat minima, and the conserved quantities of gradient flow. 2023. arXiv: 2210.17216 [cs.LG]. url: https://arxiv.org/abs/2210.17216. 6. Code to Compute Minimal Form 1 2
3 4 5 6
from math import sqrt # Notably this sign function returns 0 for 0 instead of 1 as might be more standard . def sign ( x ) : if x > 0: return 1 elif x < 0: return -1 else : return 0
7 8 9 10 11 12 13 14 15
def isLinDep (x , y ) : PseudoOutput = 0 l = len ( x ) for i in range ( l ) : for j in range (i , l ) : PseudoOutput += abs ( x [ i ]* y [ j ] - x [ j ]* y [ i ]) if PseudoOutput == 0: return True else : return False
16 17 18 19 20 21
def isSemiLinDep (x , y ) : xsign = [ sign ( a ) for a in x ] ysign = [ sign ( a ) for a in y ] if isLinDep (x , y ) and xsign == ysign : return True else : return False
22 23 24 25 26 27 28
def inner ( x ) : y = 0 for a in x : y += a * a return y
REFERENCES 29
30 31 32 33 34 35
36 37 38 39 40 41 42 43
# This takes 4 different inputs but returns one input as a list in the form [ v_min , A_min , b_min , c_min ]. Notably there is no test for whether the parameter is actually a valid parameter which bears caution . def minimalForm (v , A , b , c ) : c_final = c n = len ( v ) Az = [0]* len ( A [0]) partitionRange = set ( range ( n ) ) # This loop takes care of equivalences (1) and (3) in in the definition of the minimal form for i in range ( len ( b ) ) : if A [ i ] == Az : c_final += v [ i ]* max (0 , b [ i ]) partitionRange . remove ( i ) if v [ i ] == 0: partitionRange . remove ( i ) combinedAb = [ A [ i ]+ [ b [ i ]] for i in range ( n ) ] n onZ eroS emiDe pInd ices = []
44 45 46 47 48 49
50 51 52
# This loop determines linearly semi - dependent rows in A for i in partitionRange : if partitionRange == {}: break if i not in partitionRange : continue l = [ j for j in partitionRange if isSemiLinDep ( combinedAb [ i ] , combinedAb [ j ]) ] nonZ eroSe miDe pInd ices . append ( l ) partitionRange = partitionRange - set ( l ) r_pos , r_neg , r_zero = [] , [] , n - len ( nonZe roSe miDe pIndi ces )
53
# This loop takes care of equivalence (2) in the definition of the minimal
54
form 55 56 57 58
59 60 61 62 63 64 65 66 67 68 69 70
for I in nonZ eroSe miDe pIndi ces : if len ( I ) > 1: w = inner ( combinedAb [ I [0]]) s = 1+ sum ([( v [ I [ i ]]/ v [ I [0]]) * sqrt ( inner ( combinedAb [ I [ i ]]) / w ) for i in range (1 , len ( I ) ) ]) if v [ I [0]]* s > 0: r_pos . append ([ a * abs ( s ) for a in combinedAb [ I [0]]]) if v [ I [0]]* s < 0: r_neg . append ([ a * abs ( s ) for a in combinedAb [ I [0]]]) if s == 0: r_zero += 1 else : if v [ I [0]] > 0: r_pos . append ([ a * abs ( v [ I [0]]) for a in combinedAb [ I [0]]]) if v [ I [0]] < 0: r_neg . append ([ a * abs ( v [ I [0]]) for a in combinedAb [ I [0]]]) A_pos , A_neg , b_pos , b_neg = [] , [] ,[] ,[]
71 72
73 74 75
21
# These loops piece together everything to build the minimal form of the parameter for r in sorted ( r_pos , reverse = True ) : b_pos . append ( r . pop () ) A_pos . append ( r )
22 76 77 78 79 80 81
REFERENCES
for r in sorted ( r_neg , reverse = True ) : b_neg . append ( r . pop () ) A_neg . append ( r ) v_final = [1]* len ( r_pos ) + [ -1]* len ( r_neg ) + [0]* r_zero A_final = A_pos + A_neg + [ Az ]* r_zero b_final = b_pos + b_neg + [0]* r_zero
82 83
return [ v_final , A_final , b_final , c_final ]