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

本文认为，深度神经网络（DNN）实现了一种计算意义上的奥卡姆剃刀原则——即寻找能够拟合数据的“最简单”算法——这或许可以解释为何DNN在众多任务中远胜于传统的统计方法。我们首先发现，当满足 γ > 2 时，在“比蒙特卡洛更难”（HTMC）的条件下，所有可用大小不超过 cε⁻ᵞ 的二进制电路 ε-逼近的实值函数 f 构成的集合是凸的，从而允许我们在函数上定义一个HTMC范数。与此同时，我们可以在残差网络（ResNet）的参数上定义一种复杂度度量（即参数的加权ℓ₁范数），由此诱导出一个“ResNet范数”。随后，HTMC范数与ResNet范数可通过一个几乎匹配的夹逼不等式相互关联。因此，最小化该ResNet范数等价于寻找一个能拟合数据且节点数几乎最少（在相差一个2的幂次范围内达到最优）的电路。由此可见，ResNet似乎提供了一种用于计算实值函数的替代性计算模型，更契合HTMC区域及其所具有的凸性特征。

论文试图解释为什么深度神经网络（DNNs）在各种任务中远超传统统计方法，其核心假设是：DNNs隐式地实现了一种‘计算版奥卡姆剃刀’——在拟合数据的同时倾向于选择最简单的算法。这个问题虽然长期被讨论（如泛化能力之谜），但从电路复杂性和函数空间凸性的角度建模‘简单性’是一个较新的视角。

提出在‘Harder than Monte Carlo’（HTMC）极限下（即当近似误差ε→0时电路规模增长快于ε^{-2}），可由大小受限的二值电路逼近的实函数集合趋于凸集，从而可定义HTMC范数；同时在ResNet参数上构造加权ℓ₁范数，诱导出ResNet函数范数，并证明两者之间存在几乎匹配的夹逼界。因此，最小化ResNet范数等价于寻找近乎最优（节点数最少）的电路实现，揭示了ResNet本质上是在实现一种适应HTMC机制的高效计算模型。这一将深度网络训练与电路复杂性理论通过范数联系起来的思路具有高度原创性。

理论贡献为主，无实验或数据集。亮点在于首次将函数逼近的电路复杂性与深度网络参数正则化联系起来，建立了ResNet与最优电路之间的近似等价性。提出了HTMC范数这一新概念，并展示了其在小误差极限下的凸性，为理解DNN的归纳偏置提供了全新数学框架。值得深入的方向包括：将该理论扩展到其他网络架构（如Transformer）、探索HTMC范数在实际正则化中的应用、以及与PAC-Bayes等泛化理论的结合。目前未提及开源代码。

1. Deep Learning and the Information Bottleneck Principle 2. On the Inductive Bias of Neural Networks 3. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 4. Towards Understanding Generalization in Deep Learning via Tensor Methods 5. Circuit Complexity Meets Deep Learning: A Framework for Understanding Neural Network Expressivity