The general intelligence properties of deep neural networks (DNNs) could stem from their ability to implement a computational Occam’s razor: searching over data-fitting programs to select the simplest one. However, minimizing algorithmic complexity is notoriously difficult; how could a local search algorithm such as gradient descent recover the optimal program? For example, there currently exists no algorithm for the Minimum Circuit Size Problem (MCSP) that improves upon brute-force search. I recently discovered a regime of computation, the Harder than Monte Carlo (HTMC) regime, where circuit size becomes convex, allowing the definition of a norm whose minimization is equivalent to the MCSP. Furthermore, one can define a complexity measure $R(\theta)$ on the parameters of a ResNet that is within a power of two of the HTMC norm, thus proving a near-equivalence between ResNet training and the MCSP. Starting from this discovery, I will present a research program to understand DNNs as algorithmic complexity optimizers that could outperform brute-force search in the average case, building a new connection between Deep Learning and Meta-Complexity.

Bio:
Arthur Jacot is an Assistant Professor at New York University’s Courant Institute of Mathematical Sciences and earned his PhD at EPFL under Clément Hongler. His research develops mathematical foundations for deep learning, focusing on training dynamics, feature learning, and implicit regularization. He co-introduced the neural tangent kernel and is currently investigating how a preference for simple computational circuits can explain neural networks’ ability to generalize.