🤖 machine learning

Most ReLU Networks Admit Identifiable Parameters

This paper establishes that deep ReLU networks with input and hidden layer widths of at least two possess an open set of identifiable parameters, revealing that their functional dimension equals the parameter count minus the number of hidden neurons while also demonstrating a generic depth hierarchy where shallower networks cannot represent these functions.

Original authors: Moritz Grillo, Guido Montúfar

Published 2026-05-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Moritz Grillo, Guido Montúfar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Black Box" Mystery

Imagine you have a complex machine (a neural network) that takes an input (like a picture of a cat) and gives you an output (the label "cat"). Inside this machine are thousands of tiny knobs and dials (the parameters or weights) that you can turn to change how the machine works.

The big question this paper asks is: If you see the machine's output, can you figure out exactly how the knobs were set?

Usually, the answer is "No, not uniquely." There are two obvious reasons for this:

Swapping: If you have two identical workers in a factory, swapping their jobs doesn't change the final product. In a network, swapping two neurons in a layer is like this.
Scaling: If you turn a volume knob up by 2x but turn the next volume knob down by 2x, the sound stays the same. In a network, you can multiply a weight by a number and divide the next weight by the same number without changing the result.

The authors call these "trivial symmetries." They are easy to ignore. The real mystery is: Are there any hidden ways to change the knobs that still produce the exact same result, even after we ignore the obvious swaps and scales?

The Main Discovery: Most Networks Are "Identifiable"

The paper proves that for almost all deep neural networks (specifically, those where every layer has at least 2 neurons), the answer is no.

If you pick a random set of knobs for a sufficiently wide network, and you see the function it produces, you can uniquely reverse-engineer the knobs (up to the trivial swaps and scales). There are no "hidden" tricks left.

The Analogy:
Imagine a recipe for a cake.

Trivial Symmetries: You can swap the order of mixing the eggs and sugar, or use a slightly different brand of flour that tastes the same.
Hidden Redundancy: This would be like having a secret ingredient that you could add or remove, or change the amount of, and the cake would taste exactly the same.
The Paper's Claim: For most cake recipes (networks) with enough ingredients (width $\ge$ 2), there are no secret ingredients. If you taste the cake, you know exactly what was in it.

How They Proved It: The "Bent" Map

To prove this, the authors looked at how these networks "fold" space. A ReLU network acts like a piece of paper that gets folded and bent many times.

The Paper: They used a mathematical tool called a Weighted Polyhedral Complex. Think of this as a map of all the folds in the paper.
The Breakpoints: Where the paper bends is called a "breakpoint." The authors showed that for most networks, these bends are arranged in a very specific, rigid way.
The Dependency Graph: They built a "family tree" of these bends. They proved that for most networks, you can look at the final shape of the paper and trace the bends back to exactly which layer of the network made them. Because the layers are distinct and the bends don't cancel each other out, you can't hide a change in the knobs.

The Surprising Twist: "Minimal" Doesn't Mean "Unique"

One of the most interesting findings is about minimality.

Minimal Network: A network is "minimal" if you can't remove any neurons without changing the function. It's the smallest possible machine that can do the job.
The Expectation: You might think, "If the machine is the smallest possible size, there's no room for hidden tricks, so it must be identifiable."
The Reality: The authors found a case where a network is minimal (you can't remove any neurons) but still not identifiable.

The Analogy:
Imagine a machine with two gears that are always spinning together.

You can't remove either gear because the machine stops if you take one out (it's minimal).
However, you can change the size of the first gear and the second gear in a specific, linked way, and the machine still works exactly the same.
The paper shows that even in the "smallest" networks, you can sometimes have this kind of "linked gear" redundancy where the knobs can wiggle without changing the output.

The "Depth" Hierarchy: You Can't Fake Depth

The paper also tackles the question of depth. Can a shallow network (few layers) mimic a deep network (many layers) if we just make the shallow one wider?

The Finding: For most random settings, no.
The Analogy: Imagine a deep network is like a multi-story building where you have to walk up stairs to get to the top. A shallow network is like a single-story building with a giant ramp.
The authors proved that for most deep networks, the "staircase" structure is so specific and rigid that you cannot flatten it into a ramp, no matter how wide you make the ramp. The "depth" is a real, structural feature that cannot be traded for width.

What About Narrow Networks?

The paper explicitly states that their results apply to networks where every layer has at least 2 neurons.

If a layer has only 1 neuron, the math gets tricky. The "folding" becomes too simple (like folding a piece of string instead of a sheet of paper), and the authors suspect that in these narrow cases, you cannot uniquely identify the parameters. They leave this as an open question for future research.

Summary of Key Takeaways

Most Networks are Unique: If you have a deep network with at least 2 neurons per layer, the function it produces usually tells you exactly how the network is built (ignoring obvious swaps and scales).
No Hidden Tricks: There are no "hidden symmetries" in these wide networks. The geometry of the function is rigid enough to lock the parameters in place.
Smallest $\neq$ Unique: Even if a network is the smallest possible size (minimal), it might still have hidden ways to change the knobs without changing the result.
Depth Matters: You generally cannot replace a deep network with a shallow one, even if the shallow one is huge. The depth is structurally necessary for the function.
The Tool: They solved this by mapping the network's behavior to a geometric shape (a polyhedral complex) and proving that the "bends" in this shape reveal the network's internal structure.

Technical Summary: Most ReLU Networks Admit Identifiable Parameters

Problem Statement
The central question addressed is the relationship between the parameter space and the function space of deep ReLU networks. Specifically, the paper investigates parameter identifiability: whether a function realized by a network uniquely determines its parameters, up to trivial symmetries (permutations of neurons within a layer and positive scalings of weights across layers). While previous work established identifiability for specific architectures (e.g., pyramidal networks or those with hidden layer widths exceeding the input dimension), a general structural understanding for arbitrary deep ReLU architectures was lacking. Furthermore, it was unclear whether non-identifiability arises solely from the non-minimality of the architecture (redundancy via overparameterization) or if intrinsic redundancies persist even in minimal realizations.

Methodology
The authors develop a unified framework based on weighted polyhedral complexes to analyze the realization map $\mu_A: \Theta_A \to \mathcal{F}_A$ . Key methodological components include:

Canonical Polyhedral Complex and Bent Hyperplanes: The input space is partitioned into polyhedra based on activation patterns. The authors define "bent hyperplanes" as the loci where neurons change their linear behavior. Unlike previous definitions that include regions where preactivations vanish identically, this definition focuses on the locus of nonlinearity.
Tropical Weights: Using Lemma 2.1, the authors describe the continuous piecewise-linear (CPWL) function via a weight function on the facets of the polyhedral complex. These weights record the change in the affine linear part of the function when crossing a facet.
Genericity Conditions: The paper introduces a set of "generic" parameters satisfying:
- Supertransversality: Every face of codimension $k$ in the complex is contained in exactly $k$ bent hyperplanes.
- Cancellation-freeness: Tropical weights are non-zero unless a layer is entirely inactive on a facet.
- Transparency: Every input in a region activates at least one neuron in the layer.
- Transverse Pairwise Intersection Condition (TPIC): Bent hyperplanes from adjacent layers intersect transversely.
Breakpoint Complex and Dependency Graph: The authors define the breakpoint complex as the support of the function's non-linearities. They construct a dependency graph where vertices represent candidate bent hyperplanes and edges represent "bending" relationships (where a hyperplane from a later layer bends along one from an earlier layer). This graph serves as a functional invariant that encodes the layer hierarchy.

Key Contributions and Results

Existence of Identifiable Parameters in Almost All Architectures:
The paper proves that for any architecture where the input and all hidden layers have a width of at least 2, there exists a non-empty open set of identifiable parameters (Theorem 4.10, 4.11). This generalizes prior results that required hidden layer widths to be at least the input dimension or to follow a pyramidal structure.
Functional Dimension:
As a consequence of the existence of identifiable parameters, the paper settles the functional dimension for these architectures. It is shown to be exactly the number of parameters minus the number of hidden neurons (Theorem 4.11). This implies that the realization map is locally an embedding modulo trivial symmetries.
Minimality Does Not Imply Identifiability:
The authors construct an open set of minimal parameters (where no neurons can be removed without changing the function) that are not identifiable (Proposition 5.23). This demonstrates that redundancy can persist even in minimal realizations, refuting a conjecture that minimality implies identifiability for ReLU networks. The non-identifiability arises from a continuous symmetry in the output layer of a minimal subnetwork that does not affect the realized function.
Generic Depth Hierarchy:
The paper establishes a generic depth hierarchy (Proposition 5.24). For an open set of parameters, the realized function cannot be represented by any shallower network, regardless of width. This is proven by showing that the dependency graph of a generic parameter contains a chain of length equal to the network depth, which cannot be mapped injectively into a shallower architecture while preserving the layer ordering.
The Breakpoint Complex as a Functional Invariant:
The authors show that for generic parameters, the breakpoint complex and its associated dependency graph depend only on the realized function, not the specific parameter. This allows for the algebraic characterization of the parameter fiber (the set of all parameters realizing a function) via configuration varieties defined by geometric alignment and tropical weight matching.

Significance and Claims
The paper claims to provide a general structural understanding of identifiability for deep ReLU networks, moving beyond specific architectural constraints. By introducing the weighted polyhedral framework and the dependency graph, the authors separate the "visible" geometry of the function from the "latent" geometry of the parameters.

The work highlights that:

Identifiability is generic for wide enough networks (width $\ge 2$ ), but not universal (width 1 layers pose challenges).
Non-identifiability is not solely a symptom of overparameterization; intrinsic redundancies exist even in minimal networks.
Depth is structurally rigid for generic parameters; depth cannot be traded for width in the generic regime, contrasting with non-generic regimes where shallower networks might represent the same functions.

The authors conclude that while they have established the existence of identifiable parameters and described the local functional invariants, several questions remain open, including the precise measure of the identifiable set, the semi-algebraic characterization of the fiber, and the behavior of architectures containing layers of width 1.