Training Neural Networks is ER-complete

• URL: http://arxiv.org/abs/2102.09798v1
• Date: Fri, 19 Feb 2021 08:28:37 GMT
• Title: Training Neural Networks is ER-complete
• Authors: Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
• Abstract summary: Given a neural network, training data, and a threshold, it was known that it is NP-hard for the neural network such that the total error is below the threshold. We determine this fundamental problem precisely, by showing that it is ER-complete. This means that it is equivalent to deciding whether a system of ER equations and inequalities with integer coefficients and real unknowns has a solution.
• Score: 0.7251305766151019
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold. We determine the algorithmic complexity of this fundamental problem precisely, by showing that it is ER-complete. This means that the problem is equivalent, up to polynomial-time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, ER is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP.

Related papers

• Verified Neural Compressed Sensing [58.98637799432153]
  We develop the first (to the best of our knowledge) provably correct neural networks for a precise computational task. We show that for modest problem dimensions (up to 50), we can train neural networks that provably recover a sparse vector from linear and binarized linear measurements. We show that the complexity of the network can be adapted to the problem difficulty and solve problems where traditional compressed sensing methods are not known to provably work.
  arXiv  Detail & Related papers  (2024-05-07T12:20:12Z)
• SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization [5.982922468400901]
  We show that it is possible to achieve error bounds equivalent to that obtained in the order of the weights of a neural layer. We prove that it is possible to achieve full-network bounds under an infinite alphabet and minimal assumptions on the input data.
  arXiv  Detail & Related papers  (2023-09-20T00:35:16Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems [25.641418039598587]
  The A* algorithm is commonly used to solve NP-hard optimization problems. We show that accurate approximation for many such problems is also NP-hard.
  arXiv  Detail & Related papers  (2022-09-07T18:02:02Z)
• Reachability In Simple Neural Networks [2.7195102129095003]
  We show that NP-hardness already holds for restricted classes of simple specifications and neural networks. We give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.
  arXiv  Detail & Related papers  (2022-03-15T14:25:44Z)
• Reachability Is NP-Complete Even for the Simplest Neural Networks [0.0]
  It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer.
  arXiv  Detail & Related papers  (2021-08-30T12:38:57Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Redundant representations help generalization in wide neural networks [71.38860635025907]
  We study the last hidden layer representations of various state-of-the-art convolutional neural networks. We find that if the last hidden representation is wide enough, its neurons tend to split into groups that carry identical information, and differ from each other only by statistically independent noise.
  arXiv  Detail & Related papers  (2021-06-07T10:18:54Z)
• Conditional physics informed neural networks [85.48030573849712]
  We introduce conditional PINNs (physics informed neural networks) for estimating the solution of classes of eigenvalue problems. We show that a single deep neural network can learn the solution of partial differential equations for an entire class of problems.
  arXiv  Detail & Related papers  (2021-04-06T18:29:14Z)
• Abstraction based Output Range Analysis for Neural Networks [10.051309746913512]
  We consider the problem of output range analysis for feed-forward neural networks with ReLU activation functions. Existing approaches reduce the output range analysis problem to satisfiability and optimization solving. We present a novel abstraction technique that constructs a simpler neural network with fewer neurons.
  arXiv  Detail & Related papers  (2020-07-18T22:24:54Z)
• Self-Organized Operational Neural Networks with Generative Neurons [87.32169414230822]
  ONNs are heterogenous networks with a generalized neuron model that can encapsulate any set of non-linear operators. We propose Self-organized ONNs (Self-ONNs) with generative neurons that have the ability to adapt (optimize) the nodal operator of each connection.
  arXiv  Detail & Related papers  (2020-04-24T14:37:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.