A Complete Symmetry Classification of Shallow ReLU Networks

1. Problem Statement

The paper addresses the fundamental issue of parameter identifiability in neural networks. Specifically, it investigates the symmetry group of shallow ReLU (Rectified Linear Unit) neural networks.

• The Core Question: Given a specific function $f$ realized by a shallow ReLU network, what is the set of all distinct parameter configurations (weights and biases) that produce this exact same function?
• Context: While the "standard" symmetries of neural networks are well understood (permutations of hidden neurons and positive scaling of weights), it was an open question whether hidden symmetries exist—parameters outside the standard orbit that still realize the same function.
• The Gap: Previous complete classification results relied on the analyticity of activation functions (e.g., sigmoid, polynomial). These techniques fail for ReLU because ReLU is non-differentiable at zero. Consequently, a complete symmetry classification for shallow ReLU networks had remained elusive.

2. Methodology

The author employs an algebraic approach rather than the probabilistic or geometric techniques common in deep learning literature. The methodology proceeds through several key steps:

A. Formalization of Parameter Space

The paper defines the parameter space $\Omega(m,n,k)$ for a shallow network with input dimension $m$, hidden layer size $n$, and output dimension $k$. A parameter is denoted as $\theta = (M, A, b, c)$, representing the output weights, hidden weights, hidden biases, and output bias.
The realization map $\rho$ maps these parameters to the function space $C^0(\mathbb{R}^m, \mathbb{R}^k)$.

B. Identification of Standard Symmetries ($H_n$)

The paper identifies the subgroup $H_n \leq GL_n(\mathbb{R})$, generated by:

1. Permutations ($S_n$): Swapping hidden neurons.
2. Positive Diagonal Scaling ($D^+_n$): Scaling weights and biases by positive constants.
   It is known that $H_n$ acts on the parameter space such that $\rho$ is invariant under this action. The goal is to determine if the fiber $\rho^{-1}(\theta)$ (the set of all parameters realizing the same function) is exactly the orbit $H_n \cdot \theta$ or if it is larger.

C. The "Minimal Form" and Equivalence Relations

To classify the fibers, the author introduces a canonical "minimal form" for parameters. This involves defining an equivalence relation $\sim$ generated by three specific algebraic operations:

1. Zeroing out: If a neuron has zero output weight ($v_i=0$), its internal weights and biases can be set to zero without changing the function.
2. Merging: If two neurons have proportional weights and biases ($\lambda(a_i, b_i) = (a_j, b_j)$), their contributions can be merged into a single neuron.
3. Bias shifting: If a neuron has zero internal weights ($a_i=0$), its bias can be absorbed into the output bias.

By reducing any parameter to its minimal form ($\theta_{min}$), the author creates a unique representative for equivalence classes under these operations.

D. Exploiting Non-Differentiability

The core technical breakthrough relies on the specific property of ReLU: $\sigma(x) - \sigma(-x) = x$.
The author proves (Proposition 14) that for a minimal parameter with no "zero factors" (no redundant neurons), the realized function is smooth (affine linear) if and only if the parameters satisfy a specific "anti-symmetric" structure:
$$\sum \sigma(a_i^T x + b_i) - \sum \sigma(-a_i^T x - b_i) = \text{Linear Function}$$
This identity is the only source of "hidden symmetry" in shallow ReLU networks. It implies that a neuron with weights $(a, b)$ and weight $v$ can be swapped with a neuron with weights $(-a, -b)$ and weight $-v$ without changing the function, provided they cancel out to form a linear term.

3. Key Contributions and Results

Theorem 1: Generic Identifiability

Statement: The set of parameters $\theta$ where the fiber $\rho^{-1}(\theta)$ is diffeomorphic to the Lie group $H_n$ (i.e., the only symmetries are the standard permutations and scalings) is dense in the parameter space.
Significance: For "almost all" shallow ReLU networks, there are no hidden symmetries. The standard group $H_n$ fully describes the symmetry.

Theorem 2: Stabilizer Classification

Statement: The paper classifies the stabilizer subgroup $Stab_{H_n}(\theta)$ (parameters fixed by the group action). It shows that the stabilizer is isomorphic to $S \times H_{n'}$, where $S$ is a finite group generated by at most $\binom{n-n'}{2}$ transpositions (swaps of identical neurons) and $n'$ is the number of zeroed-out neurons.
Significance: This provides a precise algebraic characterization of when a network has redundant symmetries due to identical neurons or zeroed components.

Theorem 3 & 4: Complete Symmetry Classification

Statement: The paper provides a complete classification of the quotient space (the space of realizable functions). Two parameters $\theta_1$ and $\theta_2$ realize the same function if and only if:

1. They are related by the standard $H_n$ action, OR
2. Their "difference" (defined via a specific subtraction operation $\ominus$) reduces to a form representing the identity $\sigma(x) - \sigma(-x) = x$.
   Significance: This is the first complete classification for ReLU. It proves that beyond the standard symmetries, the only additional symmetry arises from the specific linear cancellation property of ReLU.

Corollary 9: Non-Identifiability Conditions

The paper establishes a hierarchy showing that if the stabilizer of the internal weights/biases is non-trivial ($Stab_{H_n}(A, b) \neq 1$), the fiber is strictly larger than the $H_n$ orbit. This helps identify when local identifiability fails.

4. Significance and Impact

1. Resolution of the ReLU Case: The paper successfully bridges the gap left by previous works that required analytic activation functions. It demonstrates that the non-differentiability of ReLU is not a hindrance but a feature that allows for an algebraic classification.
2. Optimization Dynamics: Understanding the geometry of the "neuromanifold" (the quotient space of parameters) is crucial for understanding optimization landscapes (e.g., why gradient descent converges, the nature of saddle points). This work provides the rigorous geometric foundation for shallow ReLU networks.
3. Algorithmic Implications: The construction of the "minimal form" is computable (Section 6 of the paper implies an algorithm). This suggests a method to canonicalize neural network parameters, potentially aiding in model compression, pruning, and comparing different trained models.
4. Limitations and Future Work: The author notes that while the algebraic classification is complete, a full geometric interpretation of the equivalence conditions (specifically the "bent hyperplane arrangements") remains an open area for future research. The results are currently restricted to shallow (one hidden layer) networks, though the methodology hints at potential extensions.

In summary, Ramakrishnan provides a rigorous algebraic framework proving that shallow ReLU networks are generically identifiable up to permutation and positive scaling, with the sole exception of a specific symmetry derived from the linear cancellation property of the ReLU function.