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

1 INTRODUCTION

• The paper identifies optimal network sizing as unresolved despite analytical, heuristic, and complexity-theoretic work on neural-network design.It presents its result as a worst-case computational obstruction and a complexity-theoretic rationale for approximation-based design methods.Source: §1 · pp. 1–2
• Prior approximation results establish universality and width bounds across architectures, while studies of neural-network training address a different complexity question from structural optimization.The introduction also surveys NAS approaches, including parameter sharing, continuous optimization, neuron-count regularization, pruning, and evolutionary search.Source: §1 · pp. 1–2
• Exact hidden-neuron minimization for two-hidden-layer ReLU networks is NP-hard for every fixed input dimension d ≥1, output dimension m ≥1, and 1 ≤p < ∞.The result holds even for rational target networks with nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, continuous piecewise affine realizations; the reduction separates optimum zero from at least d + 2.Source: §1 · p. 2
• The paper proceeds from network and polytope notation to frustum construction, Lp-density, and the neuron-minimization hardness proof.Its conclusion discusses implications for exact architecture selection and heuristic design.Source: §1 · p. 2

2 PRELIMINARIES

• A feedforward ReLU network maps inputs x ∈Rd to outputs y ∈Rm, with ReLU applied componentwise.The network description includes hidden layers and an affine output layer.Source: §2 · p. 2
• The width of a hidden layer is its number of components, and total hidden neurons are the sum of the hidden-layer widths.Source: §2 · p. 2
• A bounded polytope in Rd is introduced as a nonempty bounded set of a specified form.Source: §2 · p. 2

3 FORMATION OF FRUSTUM FUNCTIONS

• A frustum function equals one on a bounded polytope, decreases piecewise affinely through a transition region, and vanishes outside a compact set.The construction realizes this compactly supported plateau function with a two-hidden-layer ReLU network.Source: §3 · pp. 2–3
• The first hidden layer computes inequality-violation variables, whose weighted total determines the function value: zero on P, between zero and ρ in the transition region, and at least ρ where the function vanishes.The region with 0 < V_P,c < ρ surrounds the plateau P.Source: §3 · pp. 3–4
• Positive scaling constants c_i leave the defining polytope unchanged but control the magnitudes of the corresponding transition slopes.Increasing a constant increases the magnitude of its associated slope; decreasing it decreases that magnitude.Source: §3 · p. 4, Figure 3 · p. 5
• For an axis-aligned bounded box with all scaling constants equal to one, the resulting frustum function is called a box-frustum function.Source: §3 · p. 5

4 FUNCTION APPROXIMATION BY FRUSTUM FUNCTIONS

• Every scalar Lp(Rd) function can be approximated arbitrarily closely by a two-hidden-layer ReLU network that is a finite linear combination of compactly supported box-frustum functions.The constructed network belongs to Lp(Rd).Source: §4 · p. 5
• Finite linear combinations of compactly supported box-frustum functions are dense in Lp(Rd) for 1 ≤p < ∞.The proof starts from the density of finite linear combinations of bounded-box indicators and replaces each indicator with a box-frustum function having a sufficiently thin transition region.Source: §4 · p. 5
• For d ≥1, m ≥1, and 1 ≤p < ∞, vector-valued Lp functions admit arbitrary-accuracy two-hidden-layer ReLU approximations whose coordinates are finite linear combinations of compactly supported box-frustum functions.The scalar networks are placed in parallel and combined through the affine output layer.Source: §4 · p. 6

Width lower bound

• A nonzero two-hidden-layer ReLU network in Lp(R^d, R^m) requires at least d + 2 hidden neurons.The width-d degeneracy result rules out a nonzero Lp realization when both hidden layers have width at most d.Source: §5 · p. 6

Satisfiability-dependent target

• The target construction uses compactly supported box-frustum functions, with a satisfiable assignment yielding a box on which the constructed function is positive.These functions are realized by two-hidden-layer ReLU networks.Source: §5 · pp. 7–9
• A 3-CNF formula yields a polynomial-time constructible rational target that is nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine.The construction uses polynomially many neurons and coefficients of polynomial bit length.Source: §5 · p. 9

Hardness result

• For every fixed d ≥ 1, m ≥ 1, and 1 ≤ p < ∞, exact two-hidden-layer ReLU neuron minimization is NP-hard.An exact polynomial-time optimizer would decide 3-SAT by testing whether the optimum is at least d + 2.Source: §5 · p. 11

Architecture gap

• The reduction maps satisfiable formulas to instances with optimum at least d + 2 and unsatisfiable formulas to instances with optimum zero.The satisfiable case excludes the zero network, so every feasible approximant is nonzero and meets the d + 2 lower bound.Source: §5 · pp. 10–11

• Exact hidden-neuron minimization is NP-hard for two-hidden-layer ReLU networks under an Lp approximation constraint, for every fixed d ≥ 1, m ≥ 1, and 1 ≤ p < ∞.Source: §6 · p. 11
• The polynomial-time reduction from 3-SAT gives an optimum of zero for unsatisfiable formulas and at least d + 2 for satisfiable formulas.Source: §6 · p. 11
• The hardness holds for rational ReLU target networks whose realizations are nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine.Source: §6 · p. 11
• The result establishes a worst-case barrier to exact architecture selection and motivates heuristic, approximate, or structurally restricted methods for ReLU network design.Source: §6 · p. 11