CS Paper Radar

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

Sangrock Lee

cs.LG ·submitted 2026-10-08 06:19 UTC · v1
top venuetheory

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.

Journal ref
Lee, S., NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 48, no. 11, 2026
DOI
10.1109/TPAMI.2026.3711513

Closest papers

Nearest neighbours by meaning across the whole index.

The Complexity of ReLU Network Synthesis from a Parameter Multiset

cs.CC cs.LG ·2026-11-02 ·Dimitrios Myrisiotis
similarity 0.70
Abstract · 110 pages, 1 table

We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, and a bound on the number of neurons (output included). The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture. Matching two labeled examples exactly is already $\mathsf{NP}$-complete, so we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is $Σ_2^{\mathsf P}$-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in $\mathsf{DP}$ for every fixed neuron bound and is $\mathsf{DP}$-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is $Σ_2^{\mathsf P}$-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is $\mathsf{NP}^{\mathsf{PP}}$-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess.

0.20

The Geometry of Limits in ReLU Function Spaces

cs.LG math.FAmath.GNmath.MG ·2026-10-24 ·Kathryn A. Lindsey
theory similarity 0.69
Abstract · 37 pages

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.

0.21

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

Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes

cs.CC cs.DMcs.LGcs.NE ·2026-08-25 ·Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich +4 more
theory similarity 0.66
Abstract · 26 pages, 3 figures

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$-Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_\infty$-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$-norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$, maximizing the $L_p$-norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$. Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$-Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$-norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

0.37

Two hidden layer suffice: the caterpillar net

cs.LG ·2026-10-19 ·Jakob Paul Zimmermann
code/data similarity 0.65
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

$(\text{DNN})^2$: Doubly Non-Negative Relaxations for Deep Neural Networks

cs.LG cs.ROeess.SY ·2026-08-25 ·Hanna Jiamei Zhang, Alan Papalia, Michael Everett, David M. Rosen
published similarity 0.64
Abstract · 6 pages, 3 figures, accepted and to be presented at 64th IEEE Conference on Decision and Control: CDC 2026

Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach $(\text{DNN})^2$ produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.

0.37

Optimal approximation of smooth functions by ReLU neural networks

cs.LG stat.MLmath.NA ·2026-10-15 ·Thomas Nagler
similarity 0.64
Abstract

We study uniform approximation of the Hölder ball $\mathcal H_1^s([0,1]^D)$ by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every $s>0$ and $D\ge1$: networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ attain uniform approximation error of order $(N^2L^2\log N)^{-s/D}$. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate $n^{-2s/(2s+D)}$ without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.

0.19

Representing MAX functions using two-hidden-layer ReLU networks

cs.LG math.OCstat.ML ·2026-08-25 ·Zhimao Wang, Amitabh Basu
theory similarity 0.63
Abstract

We study exact representations of $\mathrm{MAX}_N(x)=\max{x_1,\ldots,x_N}$ using two-hidden-layer ReLU neural networks. This problem has been studied in recent years in an attempt to characterize the exact number of hidden layers required to represent continuous piecewise linear functions. The best lower bound is 2, while the current upper bound is logarithmic in $N$. It remains completely open if the right answer is a constant number of hidden layers (possibly even 2!) or not. In fact, a recent breakthrough was the representation of $\mathrm{MAX}_5$ as a two-hidden-layer ReLU function obtained in [Bakaev et al., 2026], and the case of $\mathrm{MAX}_N$ was stated as open for $N\geq 6$ in that paper. Using a careful computer assisted search, we obtain two-hidden-layer ReLU representations of $\mathrm{MAX}_5, \mathrm{MAX}_6, \mathrm{MAX}_7$, and $\mathrm{MAX}_8$. We obtain these by considering rational linear combinations of terms of the form $\max\{\sum_{r=1}^{s}\max(x_{a_r},x_{b_r}),\sum_{r=1}^{s}\max(x_{c_r},x_{d_r})\}$, where $a_r,b_r,c_r,d_r\in\{1,\ldots,N\}$. Each inner maximum of two coordinates can be computed in a first hidden layer, and the outer maximum of the two side-sums can be computed in a second hidden layer. Consequently, every finite linear combination of these terms has a two-hidden-layer ReLU realization. An identity for $\mathrm{MAX}_N$ in this form therefore gives an exact two-hidden-layer ReLU representation of $\mathrm{MAX}_N$. Very recently, two-hidden-layer representations of $\mathrm{MAX}_N$ of the above form were obtained for all $N\leq 10$ in [Ruess et al., 2026]. Our representations are different and were developed independently. While our techniques share most of the high-level ideas presented in [Ruess et al., 2026], there are also some minor differences which may be of interest for future research on this problem.

0.56