🔢 mathematics

Piecewise linear functions and neural network expressivity via discriminantal arrangements

This paper extends the hyperplane arrangement framework for analyzing neural network expressivity from braid to discriminantal arrangements, characterizing compatible piecewise linear functions through circuit relations and a matroidal description based on Mobius inversion.

Original authors: Pragnya Das

Published 2026-04-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pragnya Das

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: Building with Lego Bricks

Imagine you are trying to build a complex structure (a Neural Network) using Lego bricks. In the world of math and AI, these "bricks" are simple straight lines and flat planes. When you stack them together, you can create shapes that bend and twist, but they always stay "piecewise linear" (made of flat pieces).

For a long time, mathematicians studied these structures using a very specific, highly organized set of rules called the Braid Arrangement. Think of this like a perfectly symmetrical grid where every brick can connect to every other brick in any way you want. It's the "freedom" model.

This paper asks a new question: What happens if we put rules on how the bricks can connect? What if some bricks are "incompatible" and cannot touch each other directly?

The author, Pragnya Das, introduces a new framework called Discriminantal Arrangements. Instead of total freedom, this framework forces the network to follow specific "dependency rules."

The Core Concept: The "Gossip" Rule (Circuits)

To understand the new rules, imagine a group of friends (the variables in your neural network).

The Old Way (Braid Arrangement): Everyone can gossip with everyone. If Alice, Bob, and Charlie are friends, Alice can talk to Bob, Bob to Charlie, and Alice to Charlie. They can also form a "group chat" where all three interact at once. In math terms, any combination of friends can create a new, complex idea.
The New Way (Discriminantal Arrangement): There is a rule called a Circuit.
- Imagine a rule that says: "If Alice, Bob, and Charlie are all in the same room, they cannot form a unique 'triple' conversation. Their conversation is just a sum of their pairwise chats."
- In this paper, a "Circuit" is a specific group of variables (say, 3 people) that are dependent. If you know how Alice talks to Bob, and Bob to Charlie, and Alice to Charlie, you automatically know everything about the "triple" conversation. You don't need a special "triple" setting; it's already determined by the pairs.

The Metaphor:
Think of a Circuit as a "redundant" group. If you have a team of 3 people, and the rule is that the 3rd person is just a mix of the first two, then the 3rd person adds no new information. The paper shows that if you enforce these "redundancy rules" (circuits) on a neural network, the network loses the ability to create complex, high-level "group thoughts" involving 3, 4, or 5 people at once.

The Magic Tool: The "Invisible Filter" (Möbius Inversion)

How do we prove that these rules actually limit the network? The author uses a mathematical tool called Möbius Inversion.

The Analogy:
Imagine you have a photo of a complex scene.

The Function (F): This is the final photo you see.
The Möbius Transform (bF): This is a special filter that breaks the photo down into its "ingredients." It separates the photo into:
- The background (Constant)
- Individual objects (Linear/Single variables)
- Pairs of objects interacting (Pairwise)
- Groups of three interacting (Triple)
- Groups of four, five, etc.

The Discovery:
The paper proves that if you follow the "Circuit Rules" (the dependency constraints), the filter zaps out (makes zero) all the ingredients involving groups larger than a certain size.

If your rule says "groups of 3 are redundant," the filter deletes all "Triple interactions."
If your rule says "groups of 4 are redundant," the filter deletes all "Quadruple interactions."

The result? The final photo (the function the network can create) is built only from the background, single objects, and pairs. The complex "group scenes" simply cannot exist.

Why Does This Matter? (The "Quadratic" vs. "Exponential" Gap)

This is the most exciting part for understanding Neural Networks.

Unrestricted Networks (The Old Way):
- If you have 10 variables, a standard network can potentially create interactions between any combination of them.
- The number of possible interactions grows exponentially (like $2^{10}$ ). It's a massive, chaotic library of possibilities.
Restricted Networks (This Paper's Way):
- If you force the network to follow these "Circuit Rules" (specifically for $k=2$ $k = 2$ , meaning no groups larger than 2), the network can only model:
  - Single variables.
  - Pairs of variables (like "Alice and Bob").
- It cannot model "Alice, Bob, and Charlie together."
- The number of possible interactions grows polynomially (like $n^2$ ).

The Takeaway:
By choosing a specific geometric structure (a Discriminantal Arrangement) for your neural network, you are essentially pruning the tree. You are forcing the network to be "simple" and "sparse."

Benefit: The network becomes much easier to understand (interpretable). You know it only looks for pairs of connections, not wild, complex 10-way interactions.
Cost: It loses the ability to learn very complex patterns that require those high-order interactions.

Summary in One Sentence

This paper shows that if you design a neural network to follow specific geometric "dependency rules" (where groups of 3 or more are redundant), you mathematically prove that the network cannot learn complex interactions involving more than 2 variables at a time, effectively turning a chaotic, high-dimensional brain into a simpler, pairwise-focused one.

1. Problem Statement

The paper addresses the central problem of understanding the expressive power of neural networks, specifically those using ReLU (or maxout) activations. It is well-established that such networks represent the class of Continuous Piecewise Linear (CPWL) functions.

While previous research successfully modeled this expressivity using the braid arrangement (where all subsets of inputs contribute independently), the braid arrangement represents a highly symmetric and simple case. Many natural geometric and combinatorial structures involve more complex dependency relations not captured by the braid setting. The paper seeks to generalize the framework to discriminantal arrangements, which encode minimal dependencies via circuits (related to matroid theory). The core question is: How do these circuit-induced dependencies constrain the space of representable CPWL functions and, consequently, the expressivity of neural networks?

2. Methodology

The author employs a multidisciplinary approach combining combinatorics, geometry, and algebra:

Hyperplane Arrangements & Polyhedral Complexes: The paper models the domains of CPWL functions as polyhedral fans induced by hyperplane arrangements. A function is "compatible" with an arrangement if it is affine on each full-dimensional cone of the induced fan.
Set Function Encoding: CPWL functions $f: \mathbb{R}^n \to \mathbb{R}$ are encoded as set functions $F: 2^{[n]} \to \mathbb{R}$ via evaluation on indicator vectors ( $F(S) = f(\mathbf{1}_S)$ ). This maps the geometric problem to the Boolean lattice.
Discriminantal Arrangements: The study focuses on arrangements defined by a uniform matroid $M_{n,k}$ , where every subset of size $k+1$ is a circuit (a minimal dependent set), and all subsets of size $\le k$ are independent.
Circuit Constraints: The author defines linear functionals $\alpha_C$ based on inclusion-exclusion principles over circuits $C$ . A function is admissible if $\alpha_C(F) = 0$ for all circuits.
Möbius Inversion: The paper utilizes the Möbius transform on the Boolean lattice to analyze the support of these functions. It establishes a direct link between the vanishing of the Möbius transform on circuits and the constraints imposed by the arrangement.

3. Key Contributions

The paper makes several theoretical advances:

Extension to Discriminantal Arrangements: It generalizes the combinatorial framework from the braid arrangement to a broader class of discriminantal arrangements governed by circuit structures.
Circuit-Constrained Function Spaces: It defines a space of set functions ( $F_A$ ) constrained by linear relations induced by circuits. It proves that these functions correspond to CPWL functions compatible with the arrangement.
Matroidal Characterization: Using Möbius inversion, the paper characterizes the function space entirely in terms of the underlying matroid. It shows that the Möbius transform of an admissible function must vanish on all dependent sets (circuits and their supersets).
Dimensional Reduction: It derives a precise dimension formula for the function space, showing it equals the number of independent sets of the matroid.
Explicit Characterization for $k=2$ : For the case where circuits have size 3 (order $k=2$ ), the paper provides a complete characterization: functions are uniquely determined by values on subsets of size at most 2.

4. Key Results

A. Structural Characterization

Theorem 4.6 & 4.7: The dimension of the space of arrangement-compatible CPWL functions is exactly the number of independent sets in the associated matroid ( $|I(M)|$ ).
Canonical Basis: The space admits a canonical basis indexed by independent sets. Any function $F$ in the space can be uniquely represented as a linear combination of basis functions $\phi_T(S) = \mathbb{1}_{T \subseteq S}$ where $T$ is an independent set.

B. The Case $k=2$ (Triple Circuits)

Reduction of Higher-Order Terms: For arrangements where all circuits have size 3 (e.g., $A(n,2)$ ), the paper proves that all higher-order interactions vanish.
Theorem 5.3: Any function $F \in F_{A(n,2)}$ is uniquely determined by its values on subsets of size $\le 2$ . Specifically, for any triple $\{i, j, k\}$ , the value $F(\{i,j,k\})$ is a linear combination of values on subsets of size 2, 1, and 0 (constant).
Dimension Bound: The dimension of this space is bounded by $\sum_{i=0}^k \binom{n}{i}$ . For $k=2$ , this is $1 + n + \binom{n}{2}$ (quadratic in $n$ ), compared to $2^n$ for the unrestricted case.

C. Neural Network Expressivity Implications

Theorem 6.3 (Expressivity Limitation): Functions computed by neural networks conforming to a discriminantal arrangement $A(n,k)$ are restricted to interactions of order at most $k$ .
Strict Expressivity Reduction: The class of functions representable by such networks is a strict subclass of all CPWL functions.
- Braid Arrangement ( $k=n$ ): No circuit constraints; full expressive power ( $2^n$ dimensions).
- Discriminantal Arrangement ( $k < n$ ): Circuit constraints eliminate higher-order degrees of freedom. The expressive capacity grows polynomially in $n$ (specifically $O(n^k)$ ) rather than exponentially.
Implicit Regularization: The architecture enforces sparsity in higher-order interactions, acting as an implicit structural regularizer that reduces model complexity.

5. Significance

This work provides a rigorous mathematical bridge between combinatorial geometry and neural network theory:

Refined Understanding of Expressivity: It moves beyond the "black box" view of neural networks, showing that the geometric arrangement of activation boundaries (hyperplanes) fundamentally dictates the types of interactions (linear, pairwise, higher-order) the network can model.
Controlled Complexity: It demonstrates that by imposing specific geometric constraints (via discriminantal arrangements), one can systematically control the complexity of the function space, reducing it from exponential to polynomial.
Theoretical Foundation for Architectures: The results suggest that designing neural networks with specific "circuit structures" could be a viable strategy for creating models that are inherently interpretable (limited to low-order interactions) and less prone to overfitting, without explicit regularization terms.
Generalization of Prior Work: It successfully generalizes the successful braid arrangement framework to a much richer class of dependencies, opening new avenues for studying neural networks through the lens of matroid theory.

In summary, the paper proves that the combinatorial structure of the underlying hyperplane arrangement governs the expressive capacity of neural networks, with discriminantal arrangements imposing strict limits on high-order interactions, effectively collapsing the function space dimension from exponential to polynomial.