Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets

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 outperform brute-force search in the average case, building a new connection between Deep Learning and Meta-Complexity.