Expressivity of Shallow Neural Networks Over Finite Fields

Technical Summary: Expressivity of Shallow Neural Networks Over Finite Fields

Problem Statement
This work investigates the expressivity of shallow polynomial neural networks (PNNs) with monomial activation functions $\sigma(x) = x^r$ over finite fields $\mathbb{F}_q$. While neural network expressivity is traditionally studied via statistical methods or over real/complex fields, this paper addresses the algebraic expressivity in the context of finite fields. This is motivated by the practical advantages of weight quantization (reducing energy and storage) and the theoretical connection between counting rational points over finite fields and the Weil conjectures, which relate to the motivic structure of complex varieties.

The core problem is to quantify the "arithmetic expressive capacity" of a network architecture. Unlike continuous fields where expressivity is often measured by dimension or Zariski density, the authors define expressivity over finite fields via the cardinality of the neuromanifold—the image of the parameter map from network weights to the space of representable polynomial functions.

Methodology
The authors adopt an algebro-geometric approach, treating the network output as elements of a polynomial ring rather than just functions.

1. Formalism: A shallow network with architecture $\mathbf{d}=(n, m, k)$ and activation degree $r$ maps inputs $\mathbf{x} \in \mathbb{F}_q^n$ to outputs in $(\mathbb{F}_q[x_1, \dots, x_n])^k$. The output is a $k$-tuple of homogeneous polynomials of degree $r$.
2. Neuromanifold Definition: The neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ is defined as the image of the parameter map $\Psi_{\mathbf{d}, r}$ from the weight space $\mathbb{F}_q^{m(n+k)}$ to the product of spaces of homogeneous polynomials $(S_r(\mathbb{F}_q^n))^k$.
3. Counting Strategy: Since the ambient space is finite, expressivity is measured by the cardinality $|\mathcal{P}_{\mathbf{d}, r}|$. The authors utilize:
   • Multinomial Congruence Theorems: To determine which monomial coefficients vanish modulo the characteristic $p$ of the field.
   • Tensor Decomposition: Relating network outputs to symmetric tensor decompositions (specifically CP-rank and simultaneous diagonalization).
   • Combinatorial Counting: Using formulas for the number of matrices of a given rank over finite fields (MacWilliams, 1969) and $q$-binomial coefficients.
   • Projective Geometry: Analyzing the structure of the neuromanifold in projective space to handle scaling invariance.

Key Contributions and Results

1. General Upper Bounds
The paper establishes a general upper bound on the cardinality of the neuromanifold based on the base-$p$ expansion of the activation degree $r$. If $r = \sum r_t p^t$, the number of non-vanishing monomial coefficients is $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$. Consequently, the cardinality is bounded by:
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
This bound arises because multinomial coefficients vanish modulo $p$ for certain exponent tuples, reducing the effective dimension of the representable space.

2. Exact Cardinalities for Specific Architectures
The authors derive exact formulas for several architectures:

• Single Output ($k=1$) with Square Activation ($r=2, p \neq 2$): The neuromanifold corresponds to the set of symmetric $n \times n$ matrices of rank $\leq m$. The cardinality is the sum of the number of symmetric matrices of rank $j$ for $0 \leq j \leq m$, utilizing MacWilliams' formula.
• Multiple Outputs ($k>1$) with $r=2$: The authors analyze the case $\mathbf{d}=(n, n, 2)$. They demonstrate a stark contrast between finite and complex fields. Over $\mathbb{C}$, the neuromanifold is Zariski dense (filling the space). Over $\mathbb{F}_q$, the arithmetic expressive capacity approaches $1/2$ as $q \to \infty$. This is linked to the problem of simultaneous diagonalization of symmetric matrices via congruence (SDC), which fails for a non-negligible fraction of pairs over finite fields.
• Architectures with $m=1$ and $m=2$:
  • For $m=1$, the cardinality is derived via a product of projective spaces: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$.
  • For $m=2$, the authors partition the space based on the dimension of the span of the output tensors. They provide distinct formulas for $r > 1$ and $r=1$, noting that for $r=1$, linear combinations of rank-1 tensors remain rank-1, complicating the counting due to non-unique basis pairs.

3. Characteristic Divisibility ($p \mid r$)
A significant theoretical result is the reduction of activation degrees divisible by the characteristic. If $r = i \cdot p$, the cardinality of the neuromanifold is identical to that of the network with activation degree $i$:
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
This is proven using the identity $(a+b)^p \equiv a^p + b^p$ in characteristic $p$ and the fact that finite fields are perfect. This allows the reduction of complex cases to simpler ones.

• Special Case ($r=p$): When $r=p$, the neuromanifold corresponds exactly to the set of $k \times n$ matrices of rank at most $m$.

4. Structural Differences: Finite vs. Complex Fields
The paper highlights that the behavior of neuromanifolds over finite fields can differ drastically from their complex counterparts, even for small architectures.

• Example: For $\mathbf{d}=(2, 2, 2)$ with $r=2$, the neuromanifold over $\mathbb{C}$ is Zariski open (filling the space), whereas over $\mathbb{F}_q$, it occupies only approximately half the ambient space.
• Implication: Properties like "filling" (surjectivity onto the ambient space) are not guaranteed over finite fields even when they hold over $\mathbb{C}$.

Significance and Claims
The authors claim that this work provides a foundational algebraic framework for understanding the expressivity of quantized neural networks. By shifting the focus from function approximation to the cardinality of the image of the parameter map, they reveal structural constraints imposed by the field characteristic.

The paper asserts that:

1. Field Characteristic is Critical: The characteristic of the field plays a decisive role in expressivity, often reducing the capacity of the network compared to characteristic zero fields.
2. Connection to Deep Mathematics: The problem of counting these manifolds is intrinsically linked to the Weil conjectures and the study of rational points, offering a bridge between neural network theory and arithmetic geometry.
3. Limitations of Current Theory: The results suggest that intuition derived from complex or real-valued networks (e.g., regarding Zariski density) may not transfer to finite fields, necessitating specific combinatorial and algebraic tools for quantized architectures.

The paper concludes by identifying open problems, such as finding architectures where the expressive capacity converges to a non-zero fraction $0 < a/b < 1$ and solving the simultaneous diagonalization problem for symmetric tensors over finite fields. It does not propose new training algorithms or experimental benchmarks, focusing instead on the theoretical limits of representability.