mlsanityData to 14 Oct 2026

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

arXiv 2511.20888 ↗First posted 25 Nov 2025stat.ML cs.CC cs.LGcited by 5

Not on the map. Why?

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.

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

25 of 44 references.

References · 25

  1. 2020Scaling Laws for Neural Language Modelscited by 6,586
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2022Toy Models of Superpositioncited by 971
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  5. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  6. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  7. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  8. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  9. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  10. 2023Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Datacited by 174
  11. 2023Diffusion Models are Minimax Optimal Distribution Estimatorscited by 165
  12. 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
13 more
  1. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 114
  2. 2019How do infinite width bounded norm networks look in function space?cited by 106
  3. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  4. 2023How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Modelcited by 71
  5. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  6. 2019The Barron Space and the Flow-induced Function Spaces for Neural Network Modelscited by 39
  7. 2022Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functionscited by 38
  8. 2021Generalization bounds via distillationcited by 34
  9. 2023Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoffcited by 17
  10. 2019Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variationcited by 16
  11. 2025Position: A Theory of Deep Learning Must Include Compositional Sparsitycited by 14
  12. 2024How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learningcited by 6
  13. 2023Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Spacecited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026Neural Weight Norm = Kolmogorov Complexitycited by 2
  2. 2026Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Methodcited by 1
  3. 2026Understanding Generalization Requires Universal Inductioncited by 0
  4. 2026Convex Optimization Is Free When Accuracy Is Expensivecited by 0
  5. 2026Barron Optimal Transport I: Generative Modelingcited by 0