Training Neural Networks is NP-Hard in Fixed Dimension

Vincent Froese, Christoph Hertrich
3/29/2023
cs.CCcs.DScs.LG

No confident code implementation found for this paper.

Abstract

We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. [ICLR '18] and Khalife and Basu [IPCO '22] showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. [JAIR '22] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

On the Hardness of Training Deep Neural Networks Discretely

87% match2024

Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes

86% match2023

On Size-Independent Sample Complexity of ReLU Networks

84% match2023

Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy

84% match2023

On the Local Complexity of Linear Regions in Deep ReLU Networks

84% match2024

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training

84% match2023

Cite this paper

@article{froese2023training,
  title  = {Training Neural Networks is NP-Hard in Fixed Dimension},
  author = {Vincent Froese and Christoph Hertrich},
  year   = {2023},
  eprint = {2303.17045},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2303.17045v2},
  journal = {NEURIPS 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2303.17045.svg)](https://codeofpaper.com/paper/2303.17045)

Discussion