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

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks".

Jane: The gist: Computing OPTp,d,m(S, ε) exactly is NP-hard. O PTIMIZING the number of neurons in deep learning architectures is critical for balancing computational efficiency and model performance.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper today titled "NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks." It tackles a really fundamental question about how we design these deep learning architectures, specifically for networks with two hidden layers using the ReLU activation function.

Jane: Exactly, Tom. The authors are Sangrock Lee and others, and they're focusing on whether finding the absolute minimum number of neurons needed to approximate a target function within some error tolerance can actually be done efficiently.

Lu: It's interesting because it moves us from just trying to build bigger networks to figuring out the mathematical limits on how small we can possibly make them while still hitting our performance goals.

Meng: So, if we want the smallest possible network that works, this paper is saying that finding that absolute minimum count exactly is computationally hard.

Lalam: It sets a baseline complexity for architecture search because it shows there's a worst-case scenario where you can't just find the perfect tiny structure in polynomial time.

The paper's summary: Tom: What they found is that this exact minimization problem is NP-hard for every fixed input dimension d, output dimension m, and every approximation parameter p less than infinity. That’s a big statement about the difficulty of the task.

Jane: It means that even with two hidden layers, you can't just run some fast algorithm to find the absolute minimum neuron count required for an Lp approximation.

Lu: The paper shows this holds even when we restrict ourselves to rational target networks—networks whose output is defined by fractions but which are still nonnegative, compactly supported, globally Lipschitz and continuous piecewise affine.

Meng: That means the difficulty isn't just about complicated floating-point numbers; it applies to a very specific class of well-behaved functions that neural networks can model.

Lalam: They show this hardness comes from constructing these polyhedral frustum functions, which they realize using two hidden-layer ReLU networks. This construction gives us a concrete way to see how the hard problem arises in practice.

The paper's improvements: Tom: Now, the paper doesn't just stop at proving it's hard; they show how we can use this hardness to build something useful. They introduce a polynomial-time reduction from three-SAT to problems involving these ReLU networks <ref:2610.11313#pg1,polynomial-time reduction from 3-SAT>.

Jane: This reduction is what really connects the complexity theory to practical network design; it’s not just saying it’s hard, but showing *why* we should probably use different methods.

Lu: Specifically, they prove that for any satisfiable formula in three-SAT, you can construct a rational ReLU target network where the minimum number of neurons is at least d plus two <ref:2610.11313#pg1>.

Meng: That gap—the difference between zero for unsatisfiable and at least d plus two for satisfiable—gives us a provable performance guarantee linked directly to the satisfiability of that hard logic problem.

Lalam: So, it means we can design networks whose size is tied to solving a known hard problem, which gives us a way to steer our architecture selection toward something meaningful instead of just guessing.

Conclusion: Tom: To wrap up, the paper confirms that computing OPTp,d,m for two-hidden-layer ReLU networks under an Lp constraint is NP-hard for every fixed d and m.

Jane: The main implication is that we should move away from trying to find the absolute minimum neuron count via brute force and instead focus on heuristic or approximate methods for network design.

Lu: The construction of the frustum functions and the density result for finite linear combinations of box-frustum functions are key because they show that these simple geometric shapes can approximate any function in Lp norm, which is a strong modeling tool.

Meng: From an engineering standpoint, this justifies using methods that find near-optimal solutions quickly because we know the exact optimum is out of reach for large inputs.

Lalam: The paper on "NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks" provides a theoretical wall showing where exact architecture selection stops and where approximation must begin.