Neural Network Expressivity

Overview

It asks what mappings a model can represent exactly or approximate, and how the needed width, depth, parameters, precision, and activation choices scale with the task. Common approaches include universal-approximation results and lower bounds, counting linear regions or polynomial features, circuit-complexity and logic characterizations, and geometric analyses of MLPs, recurrent models, transformers, and graph networks. These tools reveal when depth, recurrence, multiplicative gates, or higher-order interactions add capabilities, often using tasks such as parity, memorization, graph distinguishing, and smooth-function approximation. A central tension is that theoretical capacity does not ensure training will find or use it, and results under idealized assumptions about precision or weights may not transfer directly to practical models.

Latest papers

123 papers5 papers in the last four weeks, down 50% on the four weeks before. 0.0% of all new papers.

Nov 10, 2024

Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach

Why can neural networks struggle to learn optimal play in a game with a simple, efficient solution algorithm? Motivated by empirical difficulties with parity in impartial games, we use NIM to study a representational bottleneck and three ways around it. We show that a restricted model of shallow, fixed-scale quantised networks lies in AC0\mathrm{AC}^0, a circuit class unable to compute parity on arbitrarily large inputs. This prevents optimal single-position play across all board sizes within the model. The obstruction also guides architectural design: two-frame inputs allow restoration from a known zero-nim-sum position; complementary rollout policies reveal the missing invariant; and persistent recurrence accumulates it row by row. Each route retains shallow network components while supplying additional information or processing time. Supervised experiments illustrate the benefits of two-frame restoration and multiple rollout heads; recurrence is a theoretical construction. These results establish representational possibilities, not guarantees of successful training: AC0\mathrm{AC}^0 does not characterise practical learnability. Core mathematical results and constructions have been checked in Lean, with classical complexity results as explicit external inputs. The interactive edition and complete Lean sources are available online at https://sr123.github.io/impartial-games-learning-lean/.
May 30, 2024

A Computational Tropical Geometry Framework for Neural Networks

We propose a computational tropical geometry framework for the symbolic analysis of neural networks with tropical activations. The number of linear regions of a neural network has been actively studied as a measure of the expressivity of a given architecture. To study these, we work in the setting of tropical geometry---a combinatorial and polyhedral variant of algebraic geometry---where there are known connections between tropical rational maps and feedforward neural networks. We expand this connection by developing concrete computational tools for studying the linear regions of neural networks. We present an algorithm, together with a proof of correctness, which computes the linear regions of a neural network as explicit unions of polyhedra. We further relate the computation of the number of linear regions of a tropical expression to the number of monomials that appear in it, and show how tropical expressions can often be pruned to remove redundant monomials. We introduce the Hoffman constant of a neural network's tropical expression, a geometric quantity that controls the distance from any point in the input space to the farthest linear region. We provide the open source Julia library TropicalNN.jl, which is built on top of the OSCAR computer algebra system and implements the algorithms mentioned above to analyze neural networks symbolically using their tropical representations. We present a set of proof-of-concept computational examples to demonstrate how our tropical geometric theory can be applied to reveal insights on the expressivity of a network architecture.
Jul 13, 2023

Deep Network Approximation: Beyond ReLU to Diverse Activation Functions

This paper explores the expressive power of deep neural networks for a diverse range of activation functions. An activation function set A\mathscr{A} is defined to encompass the majority of commonly used activation functions, such as ReLU\mathtt{ReLU}, LeakyReLU\mathtt{LeakyReLU}, ReLU2\mathtt{ReLU}^2, ELU\mathtt{ELU}, CELU\mathtt{CELU}, SELU\mathtt{SELU}, Softplus\mathtt{Softplus}, GELU\mathtt{GELU}, SiLU\mathtt{SiLU}, Swish\mathtt{Swish}, Mish\mathtt{Mish}, Sigmoid\mathtt{Sigmoid}, Tanh\mathtt{Tanh}, Arctan\mathtt{Arctan}, Softsign\mathtt{Softsign}, dSiLU\mathtt{dSiLU}, and SRS\mathtt{SRS}. We demonstrate that for any activation function ϱ∈A\varrho\in \mathscr{A}, a ReLU\mathtt{ReLU} network of width NN and depth LL can be approximated to arbitrary precision by a ϱ\varrho-activated network of width 3N3N and depth 2L2L on any bounded set. This finding enables the extension of most approximation results achieved with ReLU\mathtt{ReLU} networks to a wide variety of other activation functions, albeit with slightly increased constants. Significantly, we establish that the (width, \,depth) scaling factors can be further reduced from (3,2)(3,2) to (1,1)(1,1) if ϱ\varrho falls within a specific subset of A\mathscr{A}. This subset includes activation functions such as ELU\mathtt{ELU}, CELU\mathtt{CELU}, SELU\mathtt{SELU}, Softplus\mathtt{Softplus}, GELU\mathtt{GELU}, SiLU\mathtt{SiLU}, Swish\mathtt{Swish}, and Mish\mathtt{Mish}.