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

2025/11/25 by Arthur Paul Jacot, Jacot, Arthur
Computer Science · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2511.20888

openalex publication_date 2025/11/25 · openalex created_date 2025/11/28 · openalex updated_date 2026/07/28

Abstract

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ε<sup>-γ</sup> becomes convex in the `Harder than Monte Carlo' (HTMC) regime, when γ&gt;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 ℓ₁ 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.

Citations

• Position: A Theory of Deep Learning Must Include Compositional Sparsity
• How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning
• Auto-Regressive Next-Token Predictors are Universal Learners
• Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff
• Diffusion Models are Minimax Optimal Distribution Estimators
• Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data
• Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions
• Governance Architecture for Neural Network Superposition: A Structural Solution to Hallucination via Routing and Interference Filtering
• Generalization bounds via distillation
• Scaling Laws for Neural Language Models
• Fantastic Generalization Measures and Where to Find Them
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• The Barron Space and the Flow-induced Function Spaces for Neural Network Models
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• How do infinite width bounded norm networks look in function space?
• Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation
• On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport
• Spectrally-normalized margin bounds for neural networks
• Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review
• Norm-Based Capacity Control in Neural Networks
• Breaking the Curse of Dimensionality with Convex Neural Networks

Related

• A Study of the Mathematics of Deep Learning
• Are deep ResNets provably better than linear predictors?
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Deep Online Convex Optimization with Gated Games