Complexity of training ReLU neural network

Digvijay Boob, Santanu S. Dey, Guanghui Lan

TL;DR

This paper tackles the fundamental question of how computationally expensive it is to train neural networks that use the Rectified Linear Unit (ReLU) activation function. The authors prove that training a specific type of two-hidden-layer ReLU network is NP-hard, meaning it's likely impossible to find a fast, general algorithm for it. However, they also show that under certain conditions, like fixed input dimensions or over-parameterization, training can be done efficiently in polynomial time.

What Problem Does This Paper Address?

Neural networks have revolutionized many fields, but understanding the theoretical limits of their training process is crucial. While the ReLU activation function is now ubiquitous in deep learning due to its efficiency and effectiveness, its computational complexity for training has remained an open question. Previous work had established NP-hardness for networks with threshold activation functions, but the ReLU's unique properties (like its non-differentiability at zero) made it unclear if similar hardness results would apply. This paper aims to bridge this gap by investigating the complexity of training ReLU networks, specifically focusing on two-hidden-layer architectures.

Methods

The core of the paper's contribution lies in its theoretical analysis.

  • NP-Hardness Proof: The authors establish NP-hardness for a specific two-hidden-layer, fully-connected ReLU network by reducing it from the "2-Hyperplane Separability Problem." This reduction is novel because it adapts techniques used for threshold activation functions to the ReLU setting, which requires different combinatorial interpretations.
  • Polynomial-Time Solvable Cases:
    • Fixed Input Dimension: They prove that if the input dimension (d) and the number of nodes in the first hidden layer (k) are fixed, the training problem can be solved in polynomial time with respect to the number of data points (N). This relies on the Hyperplane Arrangement Theorem.
  • Over-parameterization: A key insight is that if the first hidden layer has as many nodes as there are data points (an "over-parameterized" scenario), the problem can be reduced to training a single-hidden-layer network, for which polynomial-time algorithms already exist.

Datasets

The paper is primarily theoretical and does not present empirical results on specific datasets. Instead, it defines a generic training problem with input data points $(x^i, y^i)$ and focuses on the computational complexity of finding network weights that satisfy these data points.

Key Insights and Ideas

  • ReLU's Unique Complexity: The NP-hardness result for ReLU networks is significant because it shows that even with a seemingly simpler activation function than threshold units, training can still be computationally intractable in the general case. The proof techniques had to be adapted, highlighting the distinct nature of ReLU.
  • The Power of Over-parameterization: The finding that over-parameterization (specifically, matching the number of hidden units to data points) makes the problem tractable is a crucial insight. It suggests that practical deep learning success might be partly due to the inherent over-parameterization in many modern architectures.
  • Fixed Dimension as a Tractability Lever: The result that fixed input dimension leads to polynomial-time solvability is a classic theme in computational geometry and complexity theory, showing how dimensionality can drastically alter problem hardness.

Key Results

  • NP-Hardness: Training a 2-ReLU Neural Network (two hidden layers, one node in the second layer) is proven to be NP-hard. This extends to (2,j)-ReLU networks for any j > 1.
  • Polynomial-Time Solvability:
    • Training a k-ReLU neural network is solvable in polynomial time if the input dimension d and the number of nodes in the first hidden layer k are fixed constants.
  • Training an N-ReLU neural network with N data points (over-parameterized) can be solved in polynomial time.

Limitations and Future Work

  • Specific Architecture: The NP-hardness result is for a specific architecture (2-hidden layer, fully-connected). The authors acknowledge that other architectures or variations might have different complexity profiles.
  • Generalizing Gadgets: A natural next step suggested is to generalize the "gadget" construction used for the 2-ReLU network to k-ReLU networks to better understand the complexity landscape for deeper or wider networks.
  • Intermediate Complexity: The paper leaves open the question of the complexity status for networks with more than two hidden layers but fewer nodes than data points, which is a significant area 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},
}
Figure