Neural Network Expressivity

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 40% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 92

Sep 28, 2026cs.LG

Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity

We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Hölder-continuous functions on

[0,1]^d

and the associated encoding complexity. For

d\geq 2

, we construct a fixed, explicitly defined activation function for which a closed-form network with two hidden layers of widths

d

and

1

achieves arbitrary accuracy in the uniform norm. We prove that

d+1

is the exact minimum total number of hidden neurons among standard feedforward networks with locally integrable activations and affine outputs. We further give a simpler construction using a single elementary activation that combines the floor and exponential functions. This construction requires three hidden layers of widths

d

,

1

, and

2

, only two neurons above the minimum. If a skip connection is allowed, widths

d

,

1

, and

1

suffice. These constructions use explicit grid addressing and integer encoding of quantized function values. For a bounded

α

-Hölder class, they require

O(\varepsilon^{-d/α}\log(1/\varepsilon))

bits, matching the metric-entropy lower bound up to a logarithmic factor.

Zilan Cheng, Li-Lian Wang, Zhongjian Wang

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore.

Neural Network Approximation Theory Feedforward Neural Networks Neural Network Expressivity

Sep 22, 2026cs.NE

The Computational Value of Sensory-Aligned Receptive Fields Depends on Neuronal Expressivity

Biological sensory neurons have selective receptive fields organized along meaningful stimulus coordinates, such as frequency, motion direction, or retinotopic position. Such structure may arise from efficient coding and biological constraints on activity, connectivity, and wiring, as computational studies of simple neurons have shown across modalities. This raises a question: do structured receptive fields confer a computational advantage beyond resource efficiency itself, and does this advantage persist when individual neurons are highly expressive? We address this question in recurrent networks of Expressive Leaky Memory neurons, where we can independently vary neuronal complexity and the organization of feed-forward receptive fields. Across auditory and event-based visual classification tasks, receptive fields aligned with a task-relevant sensory coordinate improve test accuracy relative to budget-matched random receptive fields. This advantage disappears when sensory coordinates are scrambled, or when receptive fields follow task-irrelevant coordinates, showing that the benefit comes from alignment with task geometry rather than restricted connectivity alone. Increasing neuronal complexity reduces the performance advantage of structured receptive fields. Finally, generic synaptic sparsity regularization induces input selectivity and partially recovers performance, but remains substantially below explicitly structured receptive fields, suggesting that sparsity alone is insufficient to recover the full computational benefit of task-aligned receptive fields. Together, our results show that appropriate receptive fields can serve as a computational prior beyond sparsity itself, and that their value depends on the computational expressivity of individual neurons.

Agnese Adorante, Aaron Spieler, Anna Levina

Department of Computer Science, University of Tübingen, Tübingen, Germany · Max Planck Institute for Biological Cybernetics, Tübingen, Germany

Recurrent Neural Networks Neural Network Expressivity

Sep 22, 2026cs.LG

Neural Approximation by Function Composition: Rigidity and Doubly Exponential Convergence

Deep neural networks approximate functions by composing affine maps with nonlinear activations, but how composition itself creates approximation power is not yet fully understood. We investigate a fundamental mechanism: geometrically weighted sums of iterates of a single scalar generator function. This mechanism underpins the classical tent-map construction of the function

x - x^2

and related recursive representations used by Yarotsky, W. E, et al., to analyze the approximation powers of deep neural networks. First, we establish a rigidity theorem: for continuous piecewise linear generators with a finite number of segments, any

C^3

function that can be represented in this way is at most quadratic. For non-affine quadratic functions, the geometric factor is at least

1/4

. This result both reveals limitations of the tent-map approach and complements existing methods based on hierarchical bases and recursive polynomial constructions. Second, using an exact remainder identity as guidance, we construct a smooth generator whose iterates yield doubly exponential error decay in total depth for square approximation and, through multiplication modules, for each fixed polynomial. For power series with absolutely summable coefficients on

[-1,1]^d

, distributing depth according to monomial degree yields a uniform approximation error of order

O(e^{-cL^{1/d}})

on each interior cube. These findings demonstrate how generator dynamics and remainder estimates govern depth allocation and approximation rates of deep neural networks.

Wentao Huang, Haizhang Zhang

Department of Mathematics, The University of Hong Kong, Hong Kong, P.R. China. · School of Mathematics, Sun Yat-sen University, Guangzhou, P.R. China.

Neural Network Approximation Theory Neural Network Expressivity

Sep 22, 2026math.RT

Graded Representation Theory of Equivariant Neural Networks

Nonlinear activations can create equivariant interactions between irreducible representations that linear maps cannot. We use the Gaussian degree decomposition to extend ordinary polynomial degree to such nonlinear maps, and prove that for a fixed coordinatewise equivariant layer each degree factors into a polynomial determined by the linear maps and a scalar determined by the activation. This separates three distinct obstructions, coming from symmetry, coordinates, and activation.

Mani Shayestehfar

Equivariant Neural Networks Equivariant Representation Learning Neural Network Expressivity

Sep 21, 2026cs.LG

Complex KDA: Understanding and Enhancing the Expressivity of Kimi Delta Attention

Linear RNNs based on the delta-rule enable efficient sequence modeling, but their linear updates with a low-rank correction constrain their expressivity. Prior work has shown that composing two delta-rule transitions in a single recurrent update can model a 2D rotation, but this increases the rank and the cost of the updates compared to a single transition. We show that Kimi Delta Attention (KDA) can realize 2D rotations by combining a single delta-rule transformation with a second reflection supplied by its channel-wise gate. This requires extending the parameter ranges of KDA by combining two existing range extensions: allowing gates in

[-1,1]

and the delta-rule coefficient

β

in

[0,2]

. We call the resulting model Complex KDA (CKDA). It preserves KDA's stability and efficiency, with transitions that remain diagonal-plus-rank-one and non-expansive, while reaching the state-tracking expressivity of DeltaProduct

_2

. We characterize the expressivity of CKDA and prove that every orthogonal diagonal-plus-rank-one matrix is exactly a CKDA transition matrix. A single CKDA layer can track every finite group isomorphic to a subgroup of

\mathrm{SO}(3)

, and many state-tracking results use one fewer layer for CKDA compared to other diagonal-plus-rank-one Linear RNNs. Empirically, combining both extensions yields the strongest length extrapolation among tested KDA range settings on

S_3

,

S_4

, and periodic audio continuation. In language modeling, CKDA outperforms Transformers and other linear RNNs, obtains similar results to a KDA baseline, and shows promising scaling behavior. Our code is open source at https://github.com/OpenEuroLLM/ComplexKDA and our models are available at https://huggingface.co/collections/openeurollm/complexkda.

Julien Siems, Riccardo Grazzi, Korbinian Pöppel +8

Length Generalization Delta-Rule Linear Attention State Tracking Gated Delta Networks Neural Network Expressivity

Sep 11, 2026cs.LG

Polyhedral Geometry of Time-to-First-Spike Neural Networks

We study the expressivity of spiking neural networks, which provide a natural framework for asynchronous, event-driven computation complementary to conventional feedforward neural networks. We consider the time-to-first-spike model in a setting for which the input-output map is continuous and piecewise linear, with affine pieces governed by causal feasibility constraints that determine which presynaptic spikes occur before a neuron fires. We first show that each neuron's firing time admits a maxout-like representation with exponentially many, highly constrained affine pieces. We then formalize causal regions as polyhedral regions with fixed causal sets and derive upper and lower bounds on the maximal number of causal regions in both shallow and multilayer feedforward spiking networks. Our theoretical and experimental results show that spiking networks can generate richer partitions of the input space than conventional feedforward ReLU networks.

Manjot Singh, Guido Montúfar, Gitta Kutyniok

Department of Mathematics, Ludwig-Maximilians-Universität München · Munich Center for Machine Learning · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles +2

Spiking Neural Networks Feedforward Neural Networks Neural Network Expressivity

Sep 10, 2026cs.SC

Diversity of EML-type operators

The discovery of the EML operator, sufficient to evaluate the standard explicit purely transcendental elementary functions, has led to considerable interest and discussion across multiple scientific disciplines. However, most authors have focused on the binary EML itself, while numerous similar variants with slightly different properties are now known. This article attempts to close this gap by enumerating and classifying them. We also take this opportunity to clarify common misconceptions related to the EML operator. The principal goal, symbolic regression within an architecture as close as possible to proven neural networks which combine matrix multiplication with a single univariate non-linear activation function, remains beyond reach. Instead, we propose a Möbius layer, with rational functions replacing matrix operations, and showcase the recently discovered activation function eml(x,1/x), which allows exp(x) and ln(x) to be recovered separately, and hence all elementary functions to be evaluated within a rational generalization of the neural network.

Andrzej Odrzywołek

Institute of Theoretical Physics, Jagiellonian University, Łojasiewicza 11, 30-348 Kraków, Poland

Neural Network Activation Functions Neural Network Expressivity

Aug 31, 2026cs.LG

Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Many parameter-efficient methods generate the parameters of a large neural network from a low-dimensional latent representation. Given an architecture

Φ

with

P_Φ

parameter slots, we write

\boldsymbolθ_f=\mathcal{G}(\boldsymbolξ_f)

, where

\mathcal{G}\colon\mathbb{R}^M\to\mathbb{R}^{P_Φ}

is a parameter generator and

\boldsymbolξ_f\in\mathbb{R}^M

is a latent representation of the target function

f

. The architecture

Φ

and the generator

\mathcal{G}

are shared across the entire target class, while each target

f

is represented by its own latent vector

\boldsymbolξ_f

, with

Φ_{\mathcal{G}(\boldsymbolξ_f)}

approximating

f

. This framework encompasses hypernetworks, low-dimensional parameterizations, parameter-efficient adaptation, and model compression. Understanding the tradeoff between the latent dimension

M

and the network budget

P

is therefore fundamental to characterizing the expressive efficiency of these methods. We study this tradeoff for affine generators and fully connected ReLU architectures. More precisely, optimizing jointly over architectures

Φ

satisfying

P_Φ\leq P

and affine generators

\mathcal{G}:\mathbb{R}^M\to \mathbb{R}^{P_Φ}

, we prove that the optimal worst-case uniform approximation error over the unit ball of

α

-Hölder functions on

[0,1]^d

, where

0<α\leq1

, has the sharp order

\bigl(P\min\{M,P\}\bigr)^{-α/d}.

In particular, our result shows that even a fixed-dimensional latent space suffices to achieve vanishing approximation error as the network budget increases.

Shijun Zhang

Department of Applied Mathematics Hong Kong Polytechnic University

Hypernetworks Neural Network Approximation Theory Neural Network Expressivity Neural Network Compression

Aug 24, 2026cs.LG

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all

k\geq2

, we construct a globally

[0,1]

-valued,

1

-Lipschitz function realized by a depth-

(k+1)

network of width

\mathcal{O}(d^4)

, whereas any depth-

k

network with unrestricted weights and width at most

\frac{2^d}{2d(k-1)}

has squared

L_2

error at least

1/24

under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least

3

. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case

k=2

gives a compactly supported separation between depths

3

and

2

with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally

[0,1]

-valued and

\mathcal{O}(\sqrt d)

-Lipschitz and maps the unit hypercube onto

[0,1]

. It is computed by a polynomial-width depth-

4

network, whereas any depth-

3

network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.

Itay Safran

Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Aug 12, 2026cs.LG

The Boolean Power of ReLU

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in

Σ

-MPLang, for any collection

Σ

of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than {TrReLU,id}-GNNs with respect to Boolean queries on Boolean-featured graphs.

Pablo Barceló, Floris Geerts, Matthias Lanzinger +2

Pontifical Catholic University · IMFD & CENIA, Chile · University of Antwerp +4

ReLU Neural Networks GNN Expressivity Neural Network Expressivity

Aug 12, 2026cs.LG

Reducing Symmetry Increase in Equivariant Neural Networks

Equivariant Neural Networks (ENNs) have empowered numerous applications in scientific fields. Despite their remarkable capacity for representing geometric structures, ENNs suffer from degraded expressivity when processing symmetric inputs: the output representations are invariant to transformations that extend beyond the input's symmetries. The mathematical essence of this phenomenon is that a symmetric input, after being processed by an equivariant map, experiences an increase in symmetry. While prior research has documented symmetry increase in specific cases, a rigorous understanding of its underlying causes and general reduction strategies remains lacking. In this paper, we provide a detailed and in-depth characterization of symmetry increase together with a principled framework for its reduction: (i) For any given feature space and input symmetry group, we prove that the increased symmetry admits an infimum determined by the structure of the feature space; (ii) Building on this foundation, we develop a computable algorithm to derive this infimum, and propose practical guidelines for feature design to prevent harmful symmetry increases. (iii) Under standard regularity assumptions, we demonstrate that for most equivariant maps, our guidelines effectively reduce symmetry increase. To complement our theoretical findings, we provide visualizations and experiments on both synthetic datasets and the real-world QM9 dataset. The results validate our theoretical predictions.

Ning Lin, Jiacheng Cen, Anyi Li +2

Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China

Equivariant Neural Networks Equivariant Representation Learning Neural Network Expressivity

Aug 11, 2026cs.LG

Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

How much feature rank does comparison require in kernel attention? On Min-IP over

m

-bit tokens, rank one solves every sequence of length at most two exactly. At length three, the minimum feature rank of one normalized nonnegative kernel-attention head is

2^{Θ(m)}

for error strictly below

1/2

on every input, even with arbitrary finite-dimensional tokenwise values and query-dependent affine readouts. Dense softmax solves this three-token task with

m

-dimensional scores and temperature constant in

m

. For every fixed number of heads

H

, the minimum total feature rank is

2^{Θ_H(m)}

for the same error guarantee at exact length

H+2

in one attention layer with affine mixing. These bounds also hold with position-dependent maps and a final causal query. For one head with polynomial readout of fixed degree at most

D

, rank one suffices at exact length

D+1

, while exact length

D+2

requires exponential feature rank. With unrestricted exact-real decoding, a scalar rank-one construction solves the task at every finite length. This motivates a separate bound on total communication for deterministic models with finite-alphabet cross-token channels and any number of heads and layers. In this setting, correctness up to length

n

requires

Ω(n\log m)

bits over a range of lengths that grows exponentially with

m

.

Vicente Opazo

CENIA

Low-Rank Attention Attention Mechanisms Neural Network Expressivity

Aug 8, 2026stat.ML

The Spectral Neuron

As machine learned models increase in complexity and expressive power, features of simpler models, such as interpretability and control over the shape of the modeled function are lost. On the one edge of the spectrum we have simple linear models are transparent and possess good interpretability and explainability properties, but have a limited expressive power. On the other edge we have neural networks, that have expressive power that improves with scaling, but are mostly opaque. In this work we develop the \emph{spectral neuron} concept: a scalar model given by

f(\vx)=λ_k \left(A_0+\sum_{i=1}^n x_i A_i\right)

, with learned real symmetric matrices

A_0,\ldots,A_n

. The input enters the model through an affine matrix function, but the prediction is obtained by reading one of its eigenvalues. Thus, the model is nonlinear, but the source of nonlinearity is still mathematically explicit. This gives us a useful middle ground: the model can become more expressive as the matrix dimension grows, while retaining a degree of structural interpretability through the learned matrices. For example, extremal eigenvalues yield convex or concave functions, semidefinite constraints on the coefficient matrices impose monotonicity, and the associated eigenspaces characterize local feature sensitivity. We study the robustness, structural interpretability, and shape-control properties of this model family, and then test whether it can be learned and scaled in practice. We develop a systematic study of this model family, bringing together spectral results from several mathematical literatures to characterize its expressivity, robustness, interpretability, and shape-control properties.

Alex Shtoff

Technology Innovation Institute

Neural Network Robustness Neural Network Interpretability Neural Network Expressivity

Jul 21, 2026math.NA

Neural network realization of binary refinement iterates via a two-chart atlas selector

Refinement operators generate many functions used in wavelet constructions, subdivision schemes, and geometric modeling. Their finite iterates can develop rapidly increasing numbers of linear pieces, making them a natural test case for the expressive power of deep neural networks. Earlier work showed that, for scalar binary refinement with a finitely supported mask, every compactly supported continuous piecewise linear seed has finite refinement iterates that admit exact ReLU realizations of fixed width and depth growing linearly with the number of refinement steps. The present paper gives a new construction of this known theorem. The difficulty is that the refinement cascade is driven by discontinuous binary digit choices, whereas ReLU networks produce continuous piecewise linear maps. We represent the residual dynamics on a polygonal model of the circle and describe each residual position in two overlapping coordinate systems, one ordinary and one shifted by one half. Their discontinuities occur at different points. The network switches between the two descriptions only where both are valid and the corresponding fixed linear cascade updates agree, so the switch is exact and requires no multiplication by a variable selector. The construction also gives exact readout of every continuous piecewise linear circle function satisfying the natural endpoint compatibility condition. Localized seeds are handled by a two-pass network, and translation covariance, finite decomposition, and gluing extend the result to arbitrary compactly supported continuous piecewise linear seeds in a preserved support window.

Tsogtgerel Gantumur

McGill University, Montr´eal, QC, Canada · National University of Mongolia, Ulaanbaatar, Mongolia · Mongolian Academy of Sciences, Institute of Mathematics and Digital Technology

ReLU Neural Networks Neural Network Approximation Theory Iterative Refinement Neural Network Expressivity

Jul 21, 2026cs.LG

Spectral Higher-Order Neural Networks Have Sharp Expressivity Bounds

Neural hypergraphs are a natural generalization of neural networks, the reference models in modern machine learning. Yet, their deployment has proven demanding: the number of weighted hyperedges required leads to an intractable parameter explosion. However, a novel parametrization that leverages spectral attributes for neural hypergraphs has been recently proposed, that enables to recycle parameters via a weight sharing scheme and consequently yields a significant reduction of the associated computational cost. Preliminary tests carried out on spectral higher-order architectures pointed to meaningful improvements in both performance and interpretability. Building on these results, we advance the benchmarking efforts by evaluating the spectral higher order framework on N-bit parity tasks, a well-established testbed known to be particularly challenging. As we will convincingly argue, Spectral Higher-Order Neural Networks (SHONNs) possess a versatile and highly tunable hypothesis space.

Gianluca Peri, Diego Febbe, Duccio Fanelli

Department of Physics, University of Florence & INFN, Italy

Hypergraph Neural Networks Neural Network Expressivity

Jul 20, 2026nlin.CD

Beyond the Edge of Chaos: Stability-Expressivity Transfer in Reservoir Forecasting

The edge-of-chaos heuristic has long served as a guiding principle for designing reservoir computers, yet its relevance to machine performance remains elusive. Here, taking the spectral radius of the reservoir network as the control parameter, we show that the radius yielding the best forecasting performance does not coincide with the Lyapunov edge of the isolated, teacher-forced, or closed-loop generative reservoir. By analyzing the collective dynamics of the teacher-forced reservoir, we find that the target dynamics are represented mainly by stable Lyapunov modes whose finite-time stability is strongly modulated by the input. This finding motivates a stability-expressivity transfer index, which balances the stability of these modes against their expressivity in representing the target. Across chaotic and quasiperiodic targets, and for both asymmetric and symmetric reservoirs, this index accurately identifies the optimal spectral radius for autonomous forecasting.

Yao Du, Xingang Wang

School of Physics and Information Technology, Shaanxi Normal University, Xi’an 710062, China

Lyapunov Stability Reservoir Computing Neural Network Expressivity Chaotic Time-Series Prediction

Jul 19, 2026math.AG

Expressivity of Shallow Neural Networks Over Finite Fields

We study the expressivity of shallow polynomial neural networks (PNNs) with monomial activation functions over finite fields. For a given architecture, we define a neuromanifold as the image of the map from all possible network weights into the product of polynomial rings. We quantify the expressivity by the cardinality of the neuromanifold, and derive a natural lower and upper bound. This leads to counting rational points over finite fields, a problem closely linked to the Weil conjectures. Finally, we present an architecture that exhibits a striking difference in the neuromanifolds when considered over a characteristic zero versus a finite-characteristic field, illustrating the critical role of field characteristic in the notion of expressivity.

Maksym Zubkov, Carol Wu, Shiwei Yang +2

Department of Mathematics, University of British Columbia, 1984 Mathematics Rd, Vancouver, V6T 1Z2, BC, Canada

Shallow Neural Networks Polynomial Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Jul 15, 2026cs.LG

Algebraic Representability as the Limiting Regime of Grokking: An Exactly Solvable Model with Holomorphic Activations

Neural networks trained on modular arithmetic exhibit grokking, a delayed transition from memorisation to generalisation known to depend on model capacity: too little and the network memorises slowly or not at all, too much and it generalises almost immediately. What happens at the extreme of this spectrum, when the architecture's expressible function class collapses to a finite-dimensional algebraic variety? We study two-layer networks with a holomorphic monomial activation sigma(z)=z^k, trained on modular tasks encoded via roots of unity. Here the network output, regardless of hidden width, is confined to a (k+1)-dimensional subspace of characters of (Z_p)^2, an O(k/p^2) slice of the full function space. We give a complete algebraic characterisation of this subspace: a task is representable if and only if its discrete Fourier support lies on the diagonal u+v = k (mod p), which for linear-phase targets reduces to the arithmetic criterion m+n=k. This is not merely a constraint on eventual generalisation but on memorisation itself: because the outputs are algebraically confined, a non-representable target cannot be fit even on the training set, and we prove a positive lower bound on the training loss, independent of width. Across 585 runs the algebraic prediction matches the observed outcome with 99.8% accuracy, with no memorisation regime and no grokking; outcomes split cleanly into instant success and outright failure. This binary behaviour is the limiting case of the capacity-grokking relationship: when the expressible class shrinks to a fixed algebraic object, the question of when a network will grok dissolves into whether it can represent the target at all. A bottleneck ablation connects this extreme to standard networks, tracing a continuous path from representational failure, through memorisation without generalisation, to grokking with a shrinking gap as capacity grows.

Chon-Fai Kam, Xavier Cadet, Miloud Bessafi +1

University Paris City & University of Reunion, Paris, France · Dipartimento di Fisica e Chimica Emilio Segrè, Università degli Studi di Palermo, Palermo, Italy · Thayer School of Engineering, Dartmouth College, Hanover, NH 03755, USA +2

Feedforward Neural Networks Neural Network Expressivity Modular Arithmetic Grokking

Jul 13, 2026cs.CC

Tropical Circuits with Scalar Multiplication Gates

We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement

\max

,

+

, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.

Christoph Hertrich, Moritz Stargalla

University of Technology Nuremberg

Neural Network Expressivity

Jul 10, 2026cs.LG

All you need is SAMPAT

The current state of the art in AI/ML rests on deep neural architectures, which, in general, suffer from a lack of interpretability. Interpretability is crucial to gleaning insights while analyzing experimental data, where quantitative predictions may not be adequate for a scientist. We present a three layer neural architecture, SAMPAT (Smooth Approximation via Multivariate Polynomials and Analytic Transformations), that can provably learn a continuous, everywhere differentiable function, that can approximate any smooth function arbitrarily closely. SAMPAT's approximant can be expressed as a closed and compact algebraic, analytic expression, providing complete interpretability. Experiments on synthetic and benchmark datasets indicate that SAMPAT yields competitive performance with simpler representations. For many tasks, a two layer SAMPAT suffices. By imposing restrictions on the connectivity between neurons, SAMPAT may be used to provide a range of approximants, including regular and trigonometric polynomials, rational expressions, Gaussians, mixtures of Gaussians, as well as arbitrary combinations of the same; without restrictions, it learns a suitable structure. SAMPAT may be used to factorize polynomials and model nonlinear systems. With the addition of skip connections, a 4 to 6 layer SAMPAT is adequate to represent a substantive range of methods widely used in AI/ML, allowing the choice of a model's family, not just its parameters, to also be optimized as part of the learning process.

Jayadeva, Madhur Aswani

Department of Electrical Engineering, Indian Institute of Technology, Delhi

Shallow Neural Networks Interpretable ML Neural Network Interpretability Neural Network Approximation Theory Neural Network Expressivity

Jul 8, 2026cs.LG

On the Principles of Deep Feedforward ReLU Networks

The architecture of deep feedforward neural networks is ubiquitous in deep learning, either as a whole system or as a subnetwork of other architectures, and thus its mechanism is a key ingredient of the black box of neural networks. On the basis of the simplest two-layer ReLU network, this paper systematically studies the mechanism of deep feedforward ReLU networks with multiple hidden layers and successfully explains the training solution obtained by the back-propagation algorithm. The concept of a path, especially in terms of the relationships between paths, plays a central role in uncovering the mystery of the black box. It is shown that a unit of a deep ReLU network can form a piecewise linear manifold to divide the input space, instead of a hyperplane of the two-layer case. How to efficiently use the hidden-layer units to produce both linear functions and partitions of the input space is also a central problem. The principles of a two-layer ReLU network can be generalized to the deeper case to a large extent, such as multiple strict partial orders and continuity restriction. The combination of the basic and simple principles proposed can yield complicated instantiations including the training solutions, and in this sense the black box of deep feedforward ReLU networks is revealed.

Changcun Huang

Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C

ReLU Neural Networks Neural Network Interpretability Neural Network Training Dynamics Feedforward Neural Networks Neural Network Expressivity

Jul 7, 2026cs.LG

On Explicit Super-Expressive Approximation for Neural Networks

In this work, we investigate the fixed-architecture neural network approximation with explicit parameter bounds and elementary activations. While prior work demonstrated super-expressive approximation using fixed-size networks, they lack quantitative and non-asymptotic characterizations of parameter magnitude with respect to the approximation error. We resolve this issue by introducing the Chinese Remainder Theorem as a constructive encoding mechanism. For Lipschitz continuous functions on

[0,1]^D

, we construct a width-

\max\{D,4\}

, depth-

5

network with explicit parameter-error trade-offs. For Hölder-smooth functions in

C^{r,γ}_A\left([0,1]^D\right)

, our fixed network of width

\max\{2D,\ D+5N+1\}

and depth

r + 9

achieves the parameter magnitude

\mathcal{P}

bounded by

\log_2 \mathcal{P}=\mathcal{O}\bigl(\varepsilon^{-2D/(r+γ)}\log(1/\varepsilon)\bigr)

. This is the dual result compared to those in the parameter-bounded and architecture-unbounded paradigm.

Feng-Lei Fan, Ze-Yu Li, Chen-Yu Wang +1

Department of Data Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong, Kowloon, Hong Kong. · Department of Mathematics, Chinese University of Hong Kong, University Avenue, Shatin, N.T., Hong Kong. · School of Civil Engineering and Architecture, Guangxi Minzu University, Nanning 530006, China.

Neural Network Approximation Theory Neural Network Expressivity

Jul 7, 2026cs.FL

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with

B

bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set

M

at a cost of only

\log_2 |M| + O(1)

additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local

\mathtt{read}

,

\mathtt{write}

, and

\mathtt{move}

commands, makes the system Turing complete: for every single-tape Turing machine with state set

Q

and tape alphabet

Γ

, a controller with

O(\log |Q| + \log |Γ|)

bits of internal memory simulates it, and we exhibit a concrete exponential separation:

\mathrm{EQ}_n

requires

2^n

states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states,

\{0,1\}

transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where

O(\log B)

recurrent bits suffice to simulate any

B

-state Turing machine, and prove a matching impossibility result.

Nikola Zubić, Qian Li, Yuyi Wang +1

Robotics and Perception Group, University of Zurich · Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data · Tengen Intelligence Institute, CRRC Zhuzhou Institute

Recurrent Neural Networks Neural Network Expressivity

Jul 7, 2026stat.ML

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

We aim to identify scattering network architectures that maximize the separation capacity on data with low intrinsic dimension. The networks we consider employ a fixed monomial nonlinearity and no pooling, so that the only design variable is the frame generated by the network filters. For data modeled as rectifiable sets, we first characterize and bound the separation capacity of general feature extractors in terms of the geometry of the dataset. We then particularize to scattering networks and obtain two design criteria: (i) the filters should meet the data on sufficiently many frequencies, and (ii) the matrices coupling the frame to the geometry of the data should be well-conditioned.

Konstantin Häberle, Helmut Bölcskei

ETH Zurich

Neural Network Expressivity

Jul 6, 2026stat.ML

Deep Neural Variation Spaces: A Unifying Perspective on Depth and Complexity

We develop a unified function space theory of deep fully connected neural networks. Functions in our spaces are defined recursively as

\ell^1

-bounded linear combinations of activated functions from preceding layers, with a dictionary of affine functions at the first layer. Unlike existing theories that are largely specialized to homogeneous activations such as the ReLU, our framework provides a meaningful notion of functional complexity for deep networks with a broad range of homogeneous and non-homogeneous activation functions commonly used in practice. This simple construction unites several seemingly disparate ideas from the literature, including norm-based complexity bounds and variational characterizations of depth, and facilitates novel analyses of what kinds of functions deep norm-constrained networks can represent. To this end, we prove a novel representer theorem for our spaces and establish novel function-space complexity bounds showing that the associated function classes remain qualitatively small at arbitrary depth. In the univariate ReLU case, we prove a "depth saturation" result: depth in this setting yields only a small constant rescaling of the function class, with no added functional diversity. As a consequence, we show that deep norm-controlled ReLU functions in any dimension cannot exhibit high frequencies along any direction. This finding reveals that some commonly cited expressivity benefits of depth disappear once network complexity is controlled by an appropriate function space norm, rather than parameter count or other representational costs that permit compounded rescaling across layers. Overall, our results illustrate how a function space perspective yields new structural insights into the relationship between depth and complexity.

Julia Nakhleh, Robert D. Nowak

Department of Computer Science · University of Wisconsin-Madison · Department of Electrical & Computer Engineering

ReLU Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Jul 6, 2026cs.LG

Compressed Computation under $L^4$ Loss is likely Computation in Superposition

Neural networks are thought to represent concepts as directions in their activation space, and superposition lets them encode more concepts than they have dimensions. It is natural to ask whether they can also compute more functions than they have neurons, i.e., perform computation in superposition. In this regime many functions of sparse inputs are evaluated by a layer with fewer neurons than there are functions to compute. Representation in superposition is by now fairly well understood, but computation in superposition is not, and there are few toy models of it arising through training rather than being hand designed. As a toy model of computation in superposition we study the compressed-computation setup: a single-hidden-layer ReLU network with 50 neurons that must compute the ReLU of each of 100 sparse input features. We show that training it under an

L^4

loss (the mean fourth power of the error), rather than the usual

L^2

, elicits a solution that appears to compute all features in superposition. We then reverse-engineer this solution. We find that the network assigns each feature a sparse binary codeword over neurons and decodes it with a pseudoinverse of the encoder. Given these codewords, a description with only three scalars recovers most of the network's performance, and we validate it by building equivalent networks from hand-designed codes.

Francisco Ferreira da Silva, Stefan Heimersheim

ReLU Neural Networks Feedforward Neural Networks Neural Network Expressivity

Jul 6, 2026cs.LG

Minimum Block Width for Universal Approximation by Residual Neural Networks with Inner Width One

In this paper, we study the universal approximation property of residual neural networks, and obtain some new results. For input and output dimensions

d_x

and

d_y

, and LeakyReLU, ReLU, ReLU-like activation functions, the upper and lower bounds of the minimum block width are established. To achieve

L^p

approximation

(1\leq p <+\infty)

on any compact domain, we show that the exact minimum block width is

\max\{d_x,d_y\}

when each residual branch has inner width 1. Furthermore, we show that residual neural networks with block width

\min\{d_x+d_y, \max\{2d_x+1,d_y\}\}

can achieve uniform approximation on any compact domain under the constraint that each residual branch has inner width 1. Besides, for any activation function family, we prove that there exist functions that cannot be approximated by residual neural networks with block width less than

\max\{d_x, d_y\}

, both in the

L^p

sense and the uniform sense, regardless of inner width.

Qi Zhou, Xuan Zhou, Xiao-Song Yang

School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan, 430074, Hubei, P.R. China. · Hubei Key Laboratory of Engineering Modeling and Scientific Computing, Huazhong University of Science and Technology, Wuhan, 430074, Hubei, P.R. China.

ReLU Neural Networks Residual Learning Universal Approximation Neural Network Approximation Theory Neural Network Expressivity

Jun 30, 2026cs.LG

Low-dimensional topology of deep neural networks

We study layered models, including feedforward networks, ResNets, and transformers, by limiting each layer to a width of

d = 3

, i.e.,

\mathbb{R}^3

as representation space. This allows us to track how a neural network changes low-dimensional topological invariants through its layers. Just about any topological structure may be simplified or even trivialized by simply increasing dimension; e.g., any knot is equivalent to an unknot in

\mathbb{R}^4

. By restricting to

\mathbb{R}^3

, we not only isolate the effects of activation and depth from that of width, we work in a space that lends itself to easy visualization. We focus on linking number here, deferring other invariants like link groups, Milnor's

\barμ

-invariants, knot types, ambient cobordisms, to a sequel. We provide full proofs and empirical experiments to justify the following insights: When measured by their power to effect changes in linking numbers, the layer-skipping feature in ResNets is as powerful as the attention mechanism in transformers; both ResNets and transformers are strictly more powerful than feedforward neural networks with monotonic activations, which are in turn more powerful than invertible and flow-based models; but replacing monotonic activation with a nonmonotonic one elevates a feedforward network into the same expressivity class as ResNets and transformers. These results suggest that low-dimensional topology can be a useful tool to guide designs of AI architectures. We also generalize our results from

d = 3

to arbitrary

d > 3

.

Junyu Ren, Lek-Heng Lim

University of Chicago, Chicago, IL, USA.

Transformer Feedforward Neural Networks Neural Network Expressivity

Jun 29, 2026stat.ML

Separation Capacity of Scattering Networks

In this paper, we attempt to enhance the theoretical understanding of convolutional neural networks (CNNs) as feature extractors in classification tasks by analyzing them through the lens of Cover's function-counting theory. Specifically, our focus lies on the notion of separation capacity, a combinatorial quantity derived from counting the number of realizable dichotomies (i.e., binary label assignments). Our contributions are threefold. First, we extend Cover's framework by establishing a conceptually insightful and practically useful formulation for the separation capacity. Second, leveraging this formulation, we identify the factors governing the separation capacity of feature extractors that employ a specific CNN architecture, so-called scattering networks, in terms of their network building blocks. Third, we provide practical insights for scattering network design.

Konstantin Häberle, Helmut Bölcskei

ETH Zurich

Convolutional Neural Networks Neural Network Expressivity

Jun 25, 2026cs.LG

Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary gate language, then it can be computed to comparable accuracy by an NN with explicit depth, width, and non-zero-parameter bounds controlled by the depth, width, gate count, and gate structure. Thus, neural-network complexity is not governed by regularity alone, but also by algorithmic complexity. We then show that any definable NN model satisfying a natural parallelization condition, allowing possibly multivariate non-linearities such as attention or layer normalization, is a universal approximator if and only if it contains a non-affine nonlinearity. The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power iteration without architecture-specific arguments. Its precision is illustrated by shortest-path computation on

k

-vertex graphs: compiling the tropical dynamic-programming circuit yields NNs with O(log(1/ε)) non-zero parameters, exponentially improving in 1/ε over the generic

O(ε^{-c k^2})

Lipschitz-approximation scale, for a constant c>0.

Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim +2

McMaster University & Vector Institute, Toronto, ON, Canada · Concordia University, Montréal, QC, Canada · University of Tokyo, Tokyo, Japan +2

Universal Approximation Neural Network Approximation Theory Feedforward Neural Networks Neural Network Expressivity