Complexity of Training ReLU Neural Network

Digvijay Boob, Santanu S. Dey, Guanghui Lan

TL;DR

This paper proves that training even a simple, two-hidden-layer fully connected ReLU neural network is NP-hard, resolving a significant gap in our theoretical understanding of deep learning. However, the authors also show that the problem becomes computationally tractable (solvable in polynomial time) if the input dimension is fixed or if the network is sufficiently over-parameterized.

What Problem Does This Paper Address?

The Rectified Linear Unit (ReLU) is the workhorse activation function of modern deep learning. While practitioners have seen immense success using gradient-based heuristics to train these networks, the theoretical community has long grappled with a fundamental question: How hard is it, in the worst case, to find the optimal weights for a ReLU network?

Previous research had established that training networks with "threshold" (step) functions is NP-hard. However, ReLU behaves differently—it is continuous and provides gradient information, which is why it works so well with backpropagation. Earlier hardness results for ReLU were limited to restricted, non-fully connected architectures. This paper addresses the complexity of training the standard, fully connected ReLU networks that are actually used in practice.

Methods

The authors employ three distinct approaches to map out the complexity landscape of ReLU training:

  1. NP-Hardness Reduction: To prove hardness, they reduce the "2-hyperplane separability problem" (a known NP-complete problem) to the problem of training a 2-ReLU network (a network with two nodes in the first hidden layer and one in the second). They introduce a specific set of 18 "gadget points" to force the network to behave in a way that mimics hyperplane separation.
  2. Hyperplane Arrangement Theorem: For cases where the input dimension ($d$) and the number of hidden nodes ($k$) are fixed, the authors use this theorem to enumerate all possible ways the data can be partitioned by the ReLU activations. This allows them to turn a non-convex training problem into a finite collection of convex programs.
  3. Over-parameterization Analysis: They explore the "highly over-parameterized" setting, where the number of nodes in the first hidden layer equals the number of data points. They show this specific configuration allows the training problem to be reduced to a single-hidden-layer interpolation problem, which is solvable in polynomial time.
Figure 1: Difference between ReLU model studied in [11, 12] and typical fully connected counterpart

Datasets

As a theoretical paper, it does not use standard empirical benchmarks like ImageNet or CIFAR-10. Instead, the authors construct a synthetic "gadget" dataset consisting of 18 specific points in 2D space (labeled $p_1$ through $p_{18}$) to prove their NP-hardness result.

Figure 3: The 18 "gadget points" used in the reduction. Blue points represent one class (label 1), and red points represent the other (label 0).

Key Insights and Ideas

  • The "Hard-Sorting" Requirement: The authors define a concept called "hard-sorting." For a network to achieve zero loss, the first layer must transform the data such that the second layer's ReLU can perfectly separate the classes. The proof shows that for certain data distributions, this is only possible if the first layer effectively solves an NP-hard geometric separation problem.
  • Architecture Matters: The paper highlights that allowing non-diagonal entries in the weight matrices (full connectivity) makes the problem fundamentally different from earlier studies. While more parameters might seem to make the problem "easier" to solve, it actually makes the search space for the optimal solution much more complex.
  • The Tractability of Over-parameterization: A fascinating "aha moment" is the confirmation that over-parameterization—often viewed as a way to improve generalization—also fundamentally changes the computational complexity of the optimization problem itself, shifting it from NP-hard to Polynomial-time.

Key Results

  • Theorem 3.1: Training a fully connected 2-ReLU neural network (two nodes in the first hidden layer, one in the second) is NP-hard.
  • Theorem 3.3: If the input dimension $d$ and the number of nodes $k$ are constant, there exists an algorithm to find the optimal weights in polynomial time relative to the number of data points $N$.
  • Proposition 3.4: In the highly over-parameterized setting (where the first layer has $N$ nodes), there is a randomized polynomial-time algorithm to achieve zero training error.
Figure 2: (2,1)-ReLU Neural Network. Also called 2-ReLU NN after dropping ‘1’. Here ReLU function is

Limitations and Future Work

  • The "Complexity Gap": The authors identify a significant gap in our knowledge: we know the problem is NP-hard for 2 nodes and P for $N$ nodes. What happens when we have 10, 100, or $\sqrt{N}$ nodes? The exact transition point of complexity remains unknown.
  • Exact vs. Approximate: The NP-hardness result applies to finding the global optimum (zero loss). The paper does not address the complexity of finding an "approximate" solution that is "good enough," which is what most practitioners actually do.
  • Gadget Generalization: The current proof uses a specific 2D gadget. Generalizing this gadget to prove hardness for deeper or wider networks ($k$-ReLU networks) is a suggested path for future research.

Summary updated

Abstract

In this paper, we explore some basic questions on the complexity of training neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension of the input data and the network topology is fixed, then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network, then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.
BibTeX
@article{boob2022complexity,
  author = {Digvijay Boob and Santanu S. Dey and Guanghui Lan},
  title = {{Complexity of Training ReLU Neural Network}},
  journal = {Discret. Optim},
  year = {2022},
  doi = {10.1016/j.disopt.2020.100620},
}

Loading related content...

Figure