Minimizing neurons in two-layer ReLU networks is computationally hard
NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
Machine Learning
Summary
Finding the smallest number of hidden neurons needed to approximate a function with certain neural networks is a key problem. The authors show that for networks with two hidden layers using ReLU activation, this problem is NP-hard, meaning it’s very unlikely to have an efficient exact solution. They prove this even when the function to approximate has nice properties like piecewise linearity and compact support. This result explains why people use heuristic methods instead of exact algorithms to design these networks.
What this means in practice
- •For neural network designers: Avoid seeking exact minimal neuron counts in two-hidden-layer ReLU networks due to computational impracticality, guiding the use of heuristic methods instead.
- •For machine learning practitioners: Understand limitations in network size optimization to better justify heuristic architecture search and regularization techniques.
A theory result. No direct application yet.
Authors
Sangrock Lee
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.