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

The gist: Computing OPTp,d,m(S, ε) exactly is NP-hard.

Introduction and Motivation

O PTIMIZING the number of neurons in deep learning architectures is critical for balancing computational efficiency and model performance. Given the extensive use of feedforward neural networks in applications such as image classification [2], [3], natural language processing [4], [5], and scientific computing [6], [7], there is a need for methods to design minimal yet effective models [8], [9]. Our research examines the fundamental computational hurdles in optimizing ReLU network structures and provides a complexity-theoretic rationale for approximation-based methods in network design by proving a worst-case NP-hardness result for exact hidden-neuron minimization.

Key Findings on Complexity

The paper establishes that exact minimization of the hidden-neuron count in two-hidden-layer ReLU networks is NP-hard for every fixed input dimension d ≥ 1, output dimension m ≥ 1, and every 1 ≤ p < ∞. The result holds even for rational target networks whose realizations are nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. This result identifies a worst-case computational obstruction to exact architecture selection and provides a complexity-theoretic basis for heuristic, approximate, or restricted architectureselection methods for ReLU neural networks.

Construction of Target Functions

The paper constructs compactly supported polyhedral frustum functions from bounded polytopes and shows that these functions are realized by two-hidden-layer ReLU networks. The construction involves defining violation variables ui(x) = σ(−cili(x)) and the total violation VP,c(x) = Xq i=1 σ(−cili(x)). The transition region is defined as the intermediate set where 0 < VP,c < ρo, and this function is called a frustum function.

Approximation via Frustum Functions

The paper proves that finite linear combinations of compactly supported box-frustum functions are dense in L p(Rd) and extends this approximation result to vector-valued functions. Lemma 4 demonstrates that for every ε > 0, there exists a scalar valued two-hidden-layer ReLU network ϕ from R d to R such that ϕ ∈ L p(R d) and∥f − ϕ∥Lp(Rd) < ε. Corollary 5 shows that for vector-valued functions f = (f1,..., fm) ∈ L p(Rd,Rm), there exists a two-hidden-layer ReLU network Φ from R d to R m such that∥f − Φ∥Lp(Rd,Rm) < ε.

NP-Hardness Reduction

The proof reduces the problem from 3-SAT to formulas having at least one variable and one clause. Lemma 9 provides a construction of a rational ReLU network whose realization fΨ,d: R d → R m is nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. Theorem 10 establishes that for every fixed input dimension d ≥ 1 and output dimension m ≥ 1, one can construct in polynomial time a rational ReLU target network SΨ,d,m: R d → R m and a positive rational tolerance εΨ,d satisfying Ψ ∈/ 3-SAT =⇒ OPTp,d,m (SΨ,d,m, εΨ d) = 0 and Ψ ∈ 3-SAT =⇒ OPTp,d m (SΨ d m, εΨ d) ≥ d + 2. This reduction proves that the language LARGEp,d,m is NP-hard.

Conclusion

The paper concludes that minimizing the total number of hidden neurons in two-hidden-layer ReLU networks under an L p approximation constraint is NP-hard for every fixed input dimension d ≥ 1, output dimension m ≥ 1, and every 1 ≤ p < ∞. The proof gives a polynomial-time reduction from 3-SAT using rational ReLU target networks whose realizations are nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. For an unsatisfiable formula, the zero network satisfies the approximation constraint and the optimum is zero. For a satisfiable formula, every feasible two-hiddenlayer ReLU network has at least d + 2 hidden neurons. This gap establishes a worst-case computational barrier to exact architecture selection and motivates the use of heuristic, approximate, or structurally restricted methods for ReLU network design.

--- Page 1 ---

The gist: Computing OPTp,d,m(S, ε) exactly is NP-hard.

How it works

The paper establishes that exact minimization of the hidden-neuron count in two-hidden-layer ReLU networks is NP-hard for every fixed input dimension d ≥ 1, output dimension m ≥ 1, and every 1 ≤ p < ∞. The result holds even for rational target networks whose realizations are nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine.

NP-Hardness Reduction

The proof reduces the problem from 3-SAT to formulas having at least one variable and one clause. Lemma 9 provides a construction of a rational ReLU network whose realization fΨ,d: R d → R m is nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. Theorem 10 establishes that for every fixed input dimension d ≥ 1 and output dimension m ≥ 1, one can construct in polynomial time a rational ReLU target network SΨ d m: R d → R m and a positive rational tolerance εΨ d satisfying Ψ ∈/ 3-SAT =⇒ OPTp,d m (SΨ d m, εΨ d) = 0 and Ψ ∈ 3-SAT =⇒ OPTp,d m (SΨ d m, εΨ d) ≥ d + 2. This reduction proves that the language LARGEp,d,m is NP-hard.

--- Page 2 ---

The gist: Computing OPTp,d,m(S, ε) exactly is NP-hard.

How it works

Extensive work has sought analytical descriptions of neural network architectures that achieve universal function approximation. In addressing the challenge of determining the optimal configuration of neural networks, heuristic approaches have played a vital role, as evidenced by Neural Architecture Search (NAS).

Key Findings on Complexity

Different aspects of neural networks are examined through the lens of computational complexity, using networks with various widths and depths. Blum and Rivest [28] demonstrate that the process of training a neural network, characterized by a single hidden layer with merely two nodes employing a step activation function and a single-node output, is classified as an NP-complete problem.

1. Improving network design by using NP-hard minimization constraints to guide heuristic searches is now theoretically justified; specifically, "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." This suggests that instead of exhaustive search for the absolute minimum neuron count, systems can focus on finding near-optimal solutions using efficient approximation methods.

2. Implementing architecture selection via a satisfiability-dependent target allows for the construction of networks with provable performance guarantees; specifically, For an unsatisfiable formula, OPTp,d,m (SΨ,d,m, εΨ,d) = 0, and For a satisfiable formula, every feasible two-hiddenlayer ReLU network has at least d + 2 hidden neurons. This enables the creation of networks whose performance bounds are directly tied to the satisfiability of a hard problem like 3-SAT.

3. Developing approximation techniques for function representation allows for better modeling capabilities; specifically, "For every fixed d ≥ 1, m ≥ 1, and 1 ≤ p < ∞, we prove that computing the optimum exactly is NP-hard, and finite linear combinations of compactly supported box-frustum functions are dense in L p(R d)." This means AI systems can approximate complex target functions using a finite combination of simpler, geometrically defined ReLU networks.

4. Leveraging the density result for function approximation enables robust learning; specifically, "For every ε > 0, there exists a scalarvalued two-hidden-layer ReLU network ϕ from R d to R such that ϕ ∈ L p(R d) and f − ϕLp(Rd) < ε." This allows systems to approximate any desired function in an Lp norm using a network whose structure is constrained by the density of box-frustum functions.

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(R d, R m) approximation constraint. For every fixed d 1, m 1, and 1 p < infinity, 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.