AA3 – Next Generation Networks

Project overview

The project studies the expressivity of neural networks from a mathematical perspective, with a particular focus on ReLU architectures. Neural networks with ReLU activation functions compute continuous piecewise linear (CPWL) functions, which makes them accessible to tools from polyhedral geometry, combinatorics, topology, and computational complexity.

The overarching goal of the project is to understand which functions can be represented by neural networks of a given size and depth, and how difficult it is to verify structural properties of the functions they compute.

Depth lower bounds and size–depth tradeoffs

A central part of the project investigates expressivity questions for ReLU neural networks: how large or how deep must a network be to represent a given function?

Building on the observation that ReLU networks compute CPWL functions, we study lower bounds and tradeoffs between network size and depth using geometric and combinatorial methods. In particular, we establish new lower bounds on the depth required to compute specific functions, including results for the max function under structural assumptions on the network.  These results are closely connected to classical objects such as polytopes and the braid arrangement and provide a combinatorial and geometric explanation for depth limitations in certain network classes [5,6].

For convex CPWL functions, we show that depth and size can be traded off smoothly, allowing for flexible network constructions. This analysis is further extended to classes of nonconvex functions that admit efficient decompositions into differences of convex functions [1].

Polyhedral decompositions of piecewise linear functions

To support the expressivity analysis, the project develops a polyhedral framework for decomposing CPWL functions. While such decompositions always exist, little had previously been known about their structure and complexity.

We introduce the decomposition polyhedron, which parametrizes all decompositions of a CPWL function that are compatible with a fixed polyhedral complex. We show that minimal decompositions correspond to vertices of this polyhedron, yielding a finite method for computing optimal decompositions under compatibility constraints and revealing structural uniqueness in specific cases [1].

Topological expressivity in classification tasks

In the context of classification, the project studies expressivity from a topological point of view. Neural networks were observed empirically to simplify the topology of data as it propagates through layers.

We analyze the topological structure of decision regions of ReLU networks using Betti numbers as quantitative invariants. Upper and lower bounds on these invariants are derived as a function of the network architecture, allowing for a systematic comparison of different depth and size regimes. Using this, we demonstrate a clear separation between shallow and deep networks in their ability to represent topologically complex decision boundaries [2].

Verification and computational complexity

Beyond expressivity, the project addresses the computational complexity of verifying structural properties of neural networks, motivated by safety-critical applications.

We prove that deciding injectivity of a ReLU network is coNP-complete, resolving an open complexity question. At the same time, we present a parameterized algorithm that establishes fixed-parameter tractability with respect to the input dimension. We also initiate a complexity-theoretic study of surjectivity, proving hardness results and revealing connections to problems in computational convexity, such as zonotope containment [3,4].

Summary

By combining geometric, combinatorial, topological, and complexity-theoretic methods, the project advances the mathematical understanding of ReLU neural networks. It provides new insights into their expressive power, structural limitations, and the inherent difficulty of verifying their properties, contributing to a more rigorous foundation for neural network theory.