📊 statistics

Identifiability of Deep Polynomial Neural Networks

This paper establishes the identifiability of deep polynomial neural networks by leveraging connections to low-rank tensor decompositions and Kruskal-type theorems to reveal how activation degrees and layer widths govern unique representation, while also resolving an open conjecture regarding the dimension of their neurovarieties.

Original authors: Konstantin Usevich, Ricardo Borsoi, Clara Dérand, Marianne Clausel

Published 2026-02-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Konstantin Usevich, Ricardo Borsoi, Clara Dérand, Marianne Clausel

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

Imagine you are trying to reverse-engineer a complex machine, like a high-end coffee maker. You can see the beans going in and the coffee coming out, but the machine has many internal gears, levers, and filters. The big question is: If I see the coffee, can I figure out exactly how the machine was built? Or, could there be two completely different sets of gears that produce the exact same cup of coffee?

In the world of Artificial Intelligence, this question is called identifiability. If a neural network is "identifiable," it means its internal settings (parameters) are unique to the function it performs. If it's not identifiable, the model is a bit of a black box where we can't be sure what the "true" settings are, making it hard to understand or trust.

This paper focuses on a specific type of AI called Polynomial Neural Networks (PNNs). Unlike standard AI that uses simple "on/off" switches or smooth curves, PNNs use polynomials (mathematical expressions like $x^2$ , $x^3$ , or $x \cdot y$ ) as their activation functions. This makes them very good at spotting complex patterns, but it also makes their internal math much more complicated to analyze.

Here is a breakdown of what the authors discovered, using simple analogies:

1. The "Lego Tower" Problem

Think of a deep neural network as a tall tower made of Lego blocks. Each layer of the tower is a block.

The Old Way: Previously, researchers could only prove that the tower was "identifiable" (unique) if the tower was very short (2 layers) or if every single block was exactly the same size.
The New Discovery: The authors found a clever shortcut. They proved that if every pair of connected blocks (a 2-layer section) is unique, then the entire tower is unique.

Imagine you are checking a long chain of dominoes. Instead of checking the whole chain at once, you just check every pair of dominoes next to each other. If every pair is locked in a unique way, the whole chain is locked in a unique way. This allows them to solve the problem for very deep networks by breaking them down into tiny, manageable 2-layer puzzles.

2. The "Pyramid" vs. The "Hourglass"

The paper looks at different shapes of these Lego towers:

Pyramid Networks: These start wide at the bottom and get narrower as they go up (like a real pyramid). The authors found that these are almost always identifiable. It's like a funnel; as the path gets narrower, there are fewer ways to arrange the pieces, so the arrangement becomes unique.
Hourglass (Encoder-Decoder) Networks: These start wide, squeeze into a tiny middle (the bottleneck), and then get wide again. The authors found these are also identifiable, but with a catch: the top half (the decoder) cannot get too wide too quickly. If the top expands too fast compared to the math power (activation degree) of the layers, the uniqueness breaks. It's like trying to pour a huge bucket of water through a tiny straw; if the top is too big, the system gets confused.

3. The "Homogenization" Trick (Handling Biases)

Most real-world AI models have a "bias" term—a little nudge or offset added to the data. Mathematically, this makes things messy because the equations aren't perfectly symmetrical.

The Analogy: Imagine trying to balance a scale with a wobbly weight on one side. It's hard to calculate.
The Solution: The authors used a mathematical trick called homogenization. They essentially added an "invisible extra dimension" (like adding a dummy variable) to the math. This turns the messy, wobbly equation into a perfectly symmetrical one (a homogeneous polynomial).
The Result: By solving the symmetrical version, they could prove that the original, messy version with biases is also unique. It's like solving a puzzle by temporarily adding a piece to make the picture symmetrical, solving it, and then removing the extra piece to see the original solution holds.

4. The Connection to "Tensor Decompositions"

The authors didn't just look at the neural network as a computer program; they looked at it as a tensor (a multi-dimensional array of numbers, like a 3D cube of data).

The Metaphor: They realized that a 2-layer polynomial network is mathematically identical to breaking a complex 3D cube of data into a sum of simpler, flat slices (a "low-rank tensor decomposition").
Why it matters: Mathematicians have already spent decades studying how to uniquely break down these 3D cubes. The authors borrowed these old, proven rules (called Kruskal-type theorems) and applied them to neural networks. This allowed them to say, "Because we know how to uniquely slice this 3D cube, we know this neural network is unique."

5. The "Activation Degree" Rule

The paper also figured out exactly how "complex" the math needs to be for the network to be unique.

The Rule: They found that the complexity of the math (the power of the polynomial, like $x^2$ vs $x^{10}$ ) only needs to grow linearly with the size of the network.
Why it's a big deal: Previous theories suggested the complexity needed to grow quadratically (much faster). The authors proved that you don't need super-complex math to get a unique solution; you just need a little bit more complexity as the network gets wider. This is a much more efficient rule.

Summary

In short, this paper acts as a translator between two worlds: the world of deep neural networks and the world of algebraic geometry (specifically tensor decompositions).

They proved that:

Deep networks are unique if their small 2-layer parts are unique.
Pyramid shapes are naturally unique.
Hourglass shapes are unique as long as the top doesn't expand too wildly.
Biases (offsets) don't break uniqueness if you use a specific mathematical trick to handle them.
You don't need overly complex math to ensure the network is identifiable; the requirements are much lower than previously thought.

This gives us a solid mathematical foundation to understand why certain AI architectures work and ensures that when we train these specific types of networks, we aren't just finding a random solution, but the correct unique solution.

Technical Summary: Identifiability of Deep Polynomial Neural Networks

Problem Statement

Polynomial Neural Networks (PNNs), which utilize monomial activation functions, offer a unique intersection of competitive experimental performance and rigorous theoretical analysis via algebraic geometry. A critical property for the interpretability and theoretical understanding of these networks is identifiability: the ability to uniquely determine the network's parameters (and thus its hidden representations) from its input-output behavior, up to trivial ambiguities like neuron permutations and rescalings.

While identifiability for shallow (2-layer) PNNs and specific deep architectures (e.g., self-attention, convolutional) has been studied, a general theory for deep feedforward PNNs remains missing. Existing results for deep networks are limited to cases with uniform layer widths or very high activation degrees. Furthermore, previous theoretical studies largely overlooked PNNs with bias terms. The paper addresses the open question of under what conditions deep PNNs (with and without biases) are finitely or globally identifiable, and how layer widths and activation degrees interact to satisfy these conditions.

Methodology

The authors employ a constructive approach grounded in algebraic geometry and tensor decomposition theory. The core methodology involves:

Connection to Tensor Decompositions: The authors establish a correspondence between deep PNNs and partially symmetric Canonical Polyadic Decompositions (CPD) of tensors. Specifically, 2-layer homogeneous PNNs (hPNNs) are shown to be equivalent to partially symmetric tensors.
Kruskal-Type Uniqueness Theorems: Leveraging classical results on the uniqueness of tensor decompositions (specifically Kruskal rank conditions), the authors derive sufficient conditions for the identifiability of 2-layer hPNNs.
Inductive Localization: The central theoretical mechanism is a localization theorem. The authors prove that the identifiability of a deep network can be reduced to the identifiability of its constituent 2-layer subnetworks. If every 2-layer block in a deep network is identifiable for a specific subset of inputs, the entire deep network is identifiable.
Homogenization for Biases: To handle PNNs with bias terms, the authors utilize a homogenization procedure. This transforms a PNN with biases into an equivalent homogeneous PNN (hPNN) with increased input dimensions and structured weight matrices. This allows the application of hPNN identifiability results to general PNNs.

Key Contributions and Results

1. Localization Theorem for Deep hPNNs

The paper presents a Localization Theorem (Theorem 11), which states that an $L$ -layer homogeneous PNN is finitely identifiable if every 2-layer subnetwork (composed of two successive layers) is finitely identifiable for a specific subset of inputs. This establishes a strict equivalence between the identifiability of shallow and deep hPNNs, provided the input dimension to each subnetwork is accounted for.

2. Sufficient Conditions for Identifiability

Using the link to tensor decompositions, the authors derive explicit bounds on activation degrees ( $r$ ) required for identifiability based on layer widths ( $d$ ):

2-Layer Condition (Proposition 12): A 2-layer hPNN is globally identifiable if the activation degree $r$ satisfies:
$r \geq \frac{2d_1 - \min(d_2, d_1)}{\min(d_1, d_0) - 1}$
where $d_0, d_1, d_2$ are the input, hidden, and output widths, respectively.
Pyramidal Architectures (Corollary 16): PNNs with non-increasing layer widths (pyramidal nets) are generically identifiable under mild degree conditions (e.g., $r \geq 2$ ).
Bottleneck/Encoder-Decoder Architectures (Corollary 19): Encoder-decoder networks are identifiable if the decoder widths do not grow too rapidly relative to the activation degrees. Specifically, for a bottleneck of width $d_b$ , the decoder layers must satisfy $d_\ell^{r_\ell} \leq d_b - 1$ .

3. Activation Thresholds and Neurovariety Dimensions

The paper resolves a standing conjecture regarding the activation thresholds (the minimal degrees required for identifiability):

The authors prove that the minimal activation degree required is linear in the layer widths ( $r_\ell \geq 2d_\ell - 1$ ), improving upon previous quadratic bounds found in literature [11].
These results confirm that for identifiable architectures, the associated neurovariety (the algebraic variety of functions representable by the network) is non-defective, meaning its dimension equals the effective number of parameters.

4. Extension to PNNs with Biases

By utilizing the homogenization technique, the authors extend their identifiability results to PNNs with bias terms. They demonstrate that if the corresponding homogenized hPNN is identifiable, the original PNN with biases is also identifiable. This provides the first general theoretical guarantees for deep PNNs with biases.

Significance and Claims

The paper claims to provide the first comprehensive theory for the identifiability of deep polynomial neural networks. Its significance lies in:

Bridging Shallow and Deep Theory: It tightly links the identifiability of deep networks to shallow subnetworks, a key challenge in general neural network theory.
Generalizing Conjectures: It settles and generalizes conjectures from prior work [11] regarding pyramidal networks and activation thresholds, moving from quadratic to linear bounds.
Handling Biases: It addresses a gap in theoretical studies by explicitly handling bias terms through homogenization.
Constructive Proofs: Unlike non-constructive existence proofs, the results are constructive, implying that standard polynomial-time tensor algorithms can be used to recover parameters for identifiable 2-layer blocks, which serves as the building block for deep networks.
Implications for Pruning and Compression: The results offer criteria for determining which architectures are "reducible" (non-identifiable) and which are structurally necessary, aiding in network compression and pruning strategies.

The authors note that while they prove finite identifiability (a finite number of non-equivalent representations), the question of global identifiability (a unique representation) for deep networks remains a conjecture, as the composition of unique shallow networks does not necessarily yield a unique deep network. However, the established conditions provide a robust framework for understanding the geometric properties of deep PNNs.