Computational complexity of deep learning: fundamental limitations and empirical phenomena

This manuscript is the lecture notes of B. Barak’s course in the Les Houches ‘Statistical Physics and Machine Learning’ summer school in 2022. It surveys various proxies for computational hardness in random planted problems, from the low-degree likelihood ratio to statistical query complexity and the Franz–Parisi criterion, as well as the various relationships between those criteria. We also present a few aspects of the study of deep learning, from both a theoretical and empirical point of view.