神经网络不仅是函数逼近器，更是计算模型，其复杂度由算法结构决定。
Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation
- 从计算电路视角建模神经网络，用门电路数量控制网络参数
- 证明含非线性激活的网络必为通用逼近器，且可高效模拟牛顿法等算法
- 在最短路径问题上实现指数级参数压缩，优于传统方法千倍以上
前馈神经网络的表达能力通常通过模拟最优基展开方案来研究。然而，这一视角不完整：它主要依赖光滑性衡量复杂度，无法区分具有相似光滑性但直观差异大的对象，如平方根函数与典型布朗路径。核心观点是，神经网络应被视为计算模型而非仅是灵活的基函数。若某函数可被实值电路在特定基础门语言下计算，则其可被深度、宽度、非零参数受限的神经网络以相近精度实现，其中各参数受电路深度、宽度、门数及结构约束。因此，神经网络复杂度不仅由光滑性决定，更由算法复杂性决定。我们进一步证明，任何满足自然并行化条件且允许多变量非线性（如注意力或层归一化）的可定义神经网络模型，当且仅当包含非仿射非线性时，才具备通用逼近能力。理论应用于连续函数的通用逼近、Besov类的极小极大最优逼近、解析函数的对数误差复杂度，并展示神经网络可无需特殊架构设计地模拟牛顿迭代与幂迭代等数值算法。精确性体现在对 $k$-顶点图的最短路径计算：将热带动态规划电路编译为神经网络，得到非零参数量为 $O(\log(1/\varepsilon))$，相比通用 $O(\varepsilon^{-c k^2})$ 的利普希茨逼近尺度（$c>0$），在 $1/\varepsilon$ 上呈指数级提升。
原文摘要 · Abstract (English)
Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary gate language, then it can be computed to comparable accuracy by an NN with explicit depth, width, and non-zero-parameter bounds controlled by the depth, width, gate count, and gate structure. Thus, neural-network complexity is not governed by regularity alone, but also by algorithmic complexity. We then show that any definable NN model satisfying a natural parallelization condition, allowing possibly multivariate non-linearities such as attention or layer normalization, is a universal approximator if and only if it contains a non-affine nonlinearity. The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power iteration without architecture-specific arguments. Its precision is illustrated by shortest-path computation on $k$-vertex graphs: compiling the tropical dynamic-programming circuit yields NNs with O(log(1/ε)) non-zero parameters, exponentially improving in 1/ε over the generic $O(ε^{-c k^2})$ Lipschitz-approximation scale, for a constant c>0.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。