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 th...

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical mechanics 2024-10, Vol.2024 (10), p.104008
Main Authors: Barak, Boaz, Carrell, Annabelle, Favero, Alessandro, Li, Weiyu, Stephan, Ludovic, Zlokapa, Alexander
Format: Article
Language:English
Subjects:
machine learning
typical-case computational complexity
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1742-5468
1742-5468
DOI:10.1088/1742-5468/ad3a5b