Distribution-specific hardness of learning neural networks

MaRDI QIDQ4558174zbMATH OpenFDO

Authors Ohad Shamir

Publication date 21 November 2018

Full work available at URL https://arxiv.org/abs/1609.01037, http://jmlr.csail.mit.edu/papers/v19/17-537.html

zbMATH Keywords

computational hardnessdistributional assumptionsgradient-based methodsneural networks

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Neural nets and related approaches to inference from stochastic processes (62M45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Hardness results for neural network approximation problems
• An unfeasibility view of neural network learning
• Estimates of Data Complexity in Neural-Network Learning
• scientific article; zbMATH DE number 774005
• scientific article; zbMATH DE number 2080651

Cites work

• Adaptive subgradient methods for online learning and stochastic optimization
• Applied analysis
• Concentration inequalities. A nonasymptotic theory of independence
• Cryptographic hardness for learning intersections of halfspaces
• Efficient noise-tolerant learning from statistical queries
• Embedding hard learning problems into Gaussian space
• From average case complexity to improper learning complexity
• scientific article; zbMATH DE number 3910150 (Why is no real title available?)
• scientific article; zbMATH DE number 47310 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Matrix completion with the trace norm: learning, bounding, and transducing
• Projection-based approximation and a duality with kernel methods
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Cited in

(11)

• Neural learning for distributions on categorical data
• Depth separations in neural networks: what is actually being separated?
• Discussion of: ``Nonparametric regression using deep neural networks with ReLU activation function
• Complexity of training ReLU neural network
• Polynomial‐time universality and limitations of deep learning
• A mathematical perspective of machine learning
• Hardness of learning AES with gradient-based methods
• Towards a mathematical understanding of neural network-based machine learning: what we know and what we don't
• The informativeness of the gradient revisited
• Gradient descent fails to learn high-frequency functions and modular arithmetic
• Almost pairwise independence and resilience to deep learning attacks

Describes a project that uses

Uses Software

• AdaGrad

This page was built for publication: Distribution-specific hardness of learning neural networks

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