CS Paper Radar

The Geometry of Limits in ReLU Function Spaces

Kathryn A. Lindsey

cs.LG math.FAmath.GNmath.MG ·submitted 2026-10-24 16:32 UTC · v1
theory

Abstract

We study the geometry and closure of spaces of functions realized by ReLU neural networks of fixed architecture. We first establish a general result about limits of continuous piecewise-linear (CPWL) functions: the minimum number of convex sets on which a function is affine is lower semicontinuous under pointwise convergence. The proof uses a connection to hypergraph coloring and a compactness principle, and yields quantitative bounds on the polyhedral complexity of continuous limits. We then characterize the functions realizable by shallow ReLU networks with vector-valued outputs, extending a known scalar-valued characterization. Using this and the geometry of limiting hyperplane arrangements, we prove that fixed-width shallow scalar ReLU realization spaces are closed in the weighted supremum norm on the whole input space. In contrast, we construct an explicit sequence of networks with architecture $(2,3,2\mid1)$ whose limit is not realizable by that architecture. Non-closedness holds both globally in weighted supremum norm and under uniform convergence on compact sets with nonempty interior, disproving a conjecture of Petersen, Raslan, and Voigtlaender. Finally, we show that non-closedness for a fixed scalar-output ReLU architecture necessarily involves a \emph{blow-up residue}, in which diverging output coefficients amplify an emerging linear dependence among hidden features. Together, these results provide geometric and functional-analytic tools for studying the boundaries and degenerations of ReLU realization spaces.

Comment
37 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Two hidden layer suffice: the caterpillar net

cs.LG ·2026-10-19 ·Jakob Paul Zimmermann
code/data similarity 0.71
Abstract · 17 pages. Lean formalization and paper sources: https://github.com/JayPiZimmermann/Max_Caterpillar

Every continuous piecewise linear (CPWL) function is a finite signed sum of maxima of affine functions, making maximum representation a central problem in the study of the expressiveness of ReLU networks. A now-disproved conjecture predicted logarithmic depth for maxima. Inspired by the proof by Brunck et al. (2026) that two hidden layers suffice for general CPWL functions, we give the Caterpillar Net, a nonrecursive construction for the maximum of $N$ inputs with two hidden layers of widths $O(N^2)$ and $2^{O(N\log N)}$. The construction has a direct geometric interpretation.

0.31

NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks

cs.LG ·2026-10-08 ·Sangrock Lee
top venuetheory similarity 0.69
Abstract

A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an $L^p(\mathbb{R}^d,\mathbb{R}^m)$ approximation constraint. For every fixed $d \ge 1$, $m \ge 1$, and $1 \le p < \infty$, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least $d+2$. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the $L^p$-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.

0.64

Constructive Bounds for the Topological Expressivity of Neural Networks

cs.LG math.AT ·2026-10-09 ·Kosio Beshkov
similarity 0.68
Abstract

The expressivity of a neural network $Φ$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $β(Φ^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $β(Φ(X))$. We formally prove that a ReLU network with architecture $(d,\sum\limits_{k=1}^{d } β_k(3k+2),\sum\limits_{k=1}^{d}β_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($β_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,...,d_N$ we achieve much better bounds $(\sum\limits_{n=1} d_n, 3\sum\limits_{n=1}\limits^N d_n + 2N, \sum\limits_{n=1}\limits^N d_n + N) $ for Betti numbers given by $\prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.

0.35

Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime

cs.CC ·2026-10-05 ·Olivier Bournez, Johanne Cohen, Laura Cohen, Adrian Wurm
published similarity 0.67
Abstract · 30 pages, 8 figures, Accepted at FSTTCS 2026

We study the verification problem for deep narrow ReLU neural networks: given a network of bounded width computing a piecewise-affine map on [0,1], does some input satisfy a prescribed output constraint? Classical NP-hardness proofs for ReLU verification use one neuron per Boolean variable and say nothing about networks of small constant width, while width-1 networks are easy to verify. We show that verification of ReLU networks is NP-complete at width 4 for arbitrary inputs in [0,1]. When inputs are restricted to a natural discrete encoding set, NP-completeness already holds at width 3. Together with polynomial-time decidability at width 1, this leaves open only width 2 on the encoding set, and widths 2 and 3 on [0,1]. The technical core is a fractal preprocessing gadget: a width-2 ReLU subnetwork whose iterate vanishes precisely near a finite Cantor-like subset of [0,1] with 2^n points. It reduces verification of a continuous function on [0,1] to verification on 2^n discrete points without increasing the width, and is the missing ingredient for width-bounded hardness reductions. The same construction yields further results at width 3 on the encoding set: the universal problem is coNP-complete, counting zeros is #P-complete, a majority variant is PP-complete, and approximating the minimum output within a constant gap inherited from Max-3Sat is NP-hard. The NP, coNP and inapproximability results lift to all of [0,1] at width 4; lifting counting and majority, and lifting at width 3, remain open.

0.54

The minimal width of neural networks and immersions of real projective space

cs.LG stat.ML ·2026-10-14 ·BaoZhi Chu, Ben Weinkove
similarity 0.66
Abstract · 12 pages

We investigate the minimal width of deep neural networks that can approximate all continuous functions from $\mathbb{R}^n$ to $\mathbb{R}^m$ in the topology of uniform convergence on compact subsets. We show that whenever the real projective space $\mathbb{RP}^{n-1}$ admits a smooth immersion into $\mathbb{R}^n$, the minimal width is at least $n+\min\{n,m\}$, assuming that the activation function is continuous and monotone. As a consequence, the minimal width of ReLU networks is $n+m$ whenever $n$ is equal to 2, 3, 4, 7 or 8 and $1\le m \le n$, extending results of Hanin-Sellke and Hwang. This suggests an intriguing connection between the approximation theory of neural networks and differential topology.

0.25

On the (non-)closedness of the set of ReLU networks

cs.LG math.CAmath.FAmath.NA+1 ·2026-11-06 ·Eloi Martinet, Leon Bungert
theory similarity 0.66
Abstract · 27 pages, 6 figures

We prove that the set $\mathcal{N}_N$ of ReLU networks with one hidden layer and at most $N\in\mathbb N$ neurons is weakly closed in $W^{1,p}(Ω)$, for a bounded connected open set $Ω\subset\mathbb R^d$. Consequently, every coercive, weakly lower semicontinuous energy on this space attains its minimum over $\mathcal{N}_N$. This covers the Deep Ritz method with convex integrands, Sobolev training and Lipschitz learning. Moreover, as the weight decay parameter tends to zero, minimizers of the regularized problem converge, up to subsequences, to minimizers with minimal parameter norm. We also prove that the set of ReLU networks with two hidden layers of bounded widths is not closed in $W^{1,p}(Ω)$ or in $C(\overlineΩ)$. This disproves a conjecture of Petersen, Raslan and Voigtlaender.

0.16

Neural Approximation by Function Composition: Rigidity and Doubly Exponential Convergence

cs.LG cs.IT ·2026-09-22 ·Wentao Huang, Haizhang Zhang
theory similarity 0.62
Abstract

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.

0.20

Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries

cs.LG math.STstat.ML ·2026-11-11 ·Ruizhi Deng, Guohao Shen, Tangrui Xiong
theory similarity 0.62
Abstract

In neural networks, distinct parameter configurations often realize the same input--output mapping, indicating that nominal parameter counts can overstate functional complexity. In this paper, we characterize the parameter-space symmetries of ReLU and Leaky ReLU networks across fully connected, convolutional, and residual architectures. We prove that every quasianalytic parameter map preserving the network function is a composition of positive channel scaling and channel permutation. By quotienting out both symmetries, we derive uniform covering-number upper bounds in which positive scaling reduces the complexity exponent from the total parameter count $S$ to $S-H$ (with $H$ denoting the number of scalable channels) and permutation symmetry divides the bound by the factorial count $G$ of channel permutations. We establish matching lower bounds showing that the exponent $S-H$ is sharp in general and that the divisor $G$ is attained for one-hidden-layer and generically identifiable networks. We further extend these results to general continuous piecewise-linear activated networks. Finally, we apply our covering-number bounds to derive statistical risk guarantees for empirical risk minimization and capacity control beyond i.i.d.\ settings, and show how the underlying symmetries help explain weight rebalancing in function approximation and flat directions in empirical risk optimization.

0.21