neural network designers

Abstract: A depth lower bound for ReLU networks asserts that every shallower network errs on some input; we ask when a weak theory can prove such a bound so that an error can be computed. For the exact computation of $\max(x_1,\ldots,x_n)$, recent work shows two hidden layers suffice with unrestricted rational weights. By contrast, Haase, Hertrich and Loho (ICLR 2023) proved that integer weights require depth logarithmic in $n$, and Averkov, Hojny and Merkert (ICLR 2025) extended the bound to nonbias weights whose denominators are powers of a fixed integer not divisible by a prime $q$. With integer weights the bound is sharp: the classical balanced construction has depth $\lceil\log_2 n\rceil$. For each fixed $q$ and depth cap $K$, we prove this known bound in $\mathbf{VTC}^0$, the bounded-arithmetic theory of uniform constant-depth threshold computation, together with a refuter that is itself such a computation and whose correctness the theory proves. Given a network with at most $K$ hidden layers, nonbias weights whose reduced denominators avoid $q$, arbitrary rational biases and $n>q^K$ inputs, the refuter returns a rational input of polynomial length on which the network errs. The proof makes the obstruction finite: an iterated intersection product of piecewise-linear functions is divisible by $q$ for the network but not for the maximum, so one of finitely many test points exposes the error. By witnessing, provable refutation corresponds to a provably correct refuter, and provable existence of a certified network to a provably correct constructor. On the construction side, we introduce certificates that label each maximum gadget by the inputs it aggregates; with them the theory verifies the balanced construction, which meets the refuter at the sharp threshold $n\le2^K$, and a rational family of polynomial description length and depth $O(\log n/\log\log n)$ built from known depth-two blocks.

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.

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.

Abstract: Exactly computing the maximum function is a standard test case for studying depth in ReLU networks. Two hidden layers are known to suffice for up to twelve inputs through computer-assisted constructions. For six real inputs, we give an explicit hexagon identity whose local structure yields a self-contained analytical proof of this depth bound. The identity was found by computer-assisted search; we prove it through explicit cancellations that can be checked entirely by hand, without executing a verification program. The identity also yields an explicit network with hidden widths $17$ and $41$, zero biases, and rational weights.