'Agnostic learning' is a learning paradigm that is central to both the theory and applications of machine learning. Much of the activity within this framework focuses on learning with neural networks. The absence of provably efficient algorithms for many of the neural networks learning tasks raises the suspicion that they may be inherently hard.

Using the breakthrough results that have emerged in the area of hardness-of-approximation in the past 5 years, we are able to show that, assuming $P \neq NP$, some of the basic neural networks learning tasks are indeed computationally infeasible. In this talk I shall provide a brief introduction to agnostic learning and a survey of the existing results and major open questions related to the computational hardness of neural network learning. If time permits, I shall also sketch the ideas behind the proofs of the new results.

The talk covers joint work with Peter Bartlett and with Phil Long.