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

arXiv: https://arxiv.org/abs/2511.20888 · HTML: https://mlsanity.com/paper/2511.20888/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 44 references that are in the map.
- First posted on arXiv 25 Nov 2025.

## Builds on (most cited first, 25 of 25)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [The Barron Space and the Flow-induced Function Spaces for Neural Network Models](https://mlsanity.com/paper/1906.08039/) (2019)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff](https://mlsanity.com/paper/2305.19008/) (2023)
- [Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation](https://mlsanity.com/paper/1902.00800/) (2019)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)

## Built on by (most cited first, 5 of 5)

- [Neural Weight Norm = Kolmogorov Complexity](https://mlsanity.com/paper/2605.10878/) (2026)
- [Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Method](https://mlsanity.com/paper/2603.24594/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)
- [Convex Optimization Is Free When Accuracy Is Expensive](https://mlsanity.com/paper/2609.35418/) (2026)
- [Barron Optimal Transport I: Generative Modeling](https://mlsanity.com/paper/2610.10875/) (2026)

## Abstract (arXiv)

This paper argues that DNNs implement a computational Occam's razor -- finding the `simplest' algorithm that fits the data -- and that this could explain their incredible and wide-ranging success over more traditional statistical methods. We start with the discovery that the set of real-valued function f that can be ε-approximated with a binary circuit of size at most cε-γ becomes convex in the `Harder than Monte Carlo' (HTMC) regime, when γ>2, allowing for the definition of a HTMC norm on functions. In parallel one can define a complexity measure on the parameters of a ResNets (a weighted ℓ1 norm of the parameters), which induce a `ResNet norm' on functions. The HTMC and ResNet norms can then be related by an almost matching sandwich bound. Thus minimizing this ResNet norm is equivalent to finding a circuit that fits the data with an almost minimal number of nodes (within a power of 2 of being optimal). ResNets thus appear as an alternative model for computation of real functions, better adapted to the HTMC regime and its convexity.