Hardness results for neural network approximation problems

Recommendations

scientific article; zbMATH DE number 2080651
On approximate learning by multi-layered feedforward circuits
On the infeasibility of training neural networks with small mean-squared error
scientific article; zbMATH DE number 5957227
The computational intractability of training sigmoidal neural networks

Cites work

Cryptographic limitations on learning Boolean formulae and finite automata
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Efficient agnostic learning of neural networks with bounded fan-in
scientific article; zbMATH DE number 3960854 (Why is no real title available?)
scientific article; zbMATH DE number 1332666 (Why is no real title available?)
On the complexity of polyhedral separability
On the difficulty of approximately maximizing agreements.
Optimization, approximation, and complexity classes
Robust trainability of single neurons
Strong universal consistency of neural network classifiers
The computational intractability of training sigmoidal neural networks
The hardness of approximate optima in lattices, codes, and systems of linear equations
The hardness of approximation: Gap location

Cited in

(26)

Finding approximate solutions to NP-hard problems by neural networks is hard
Some connections between learning and optimization
Topological properties of the set of functions generated by neural networks of fixed size
Best \(k\)-layer neural network approximations
Neural networks with linear threshold activations: structure and algorithms
Approximation by neural networks and learning theory
On approximate learning by multi-layered feedforward circuits
Complexity of training ReLU neural network
Theory of Classification: a Survey of Some Recent Advances
Efficient agnostic learning of neural networks with bounded fan-in
Training a Single Sigmoidal Neuron Is Hard
scientific article; zbMATH DE number 2080455 (Why is no real title available?)
scientific article; zbMATH DE number 2080651 (Why is no real title available?)
Rank correlation estimators and their limiting distributions
Distribution-specific hardness of learning neural networks
On the infeasibility of training neural networks with small mean-squared error
scientific article; zbMATH DE number 7626778 (Why is no real title available?)
Loading Deep Networks Is Hard: The Pyramidal Case
The committee machine: computational to statistical gaps in learning a two-layers neural network
Deep learning: a statistical viewpoint
Reachability in Simple Neural Networks
Complexity of network training for classes of Neural Networks
Convolution hierarchical deep-learning neural networks (C-HiDeNN): finite elements, isogeometric analysis, tensor decomposition, and beyond
Proof of the theory-to-practice gap in deep learning via sampling complexity bounds for neural network approximation spaces
On the performance guarantee of neural networks for NP-hard optimization problems
Boolean autoencoders and hypercube clustering complexity

This page was built for publication: Hardness results for neural network approximation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1603592)