证明了多数前馈神经网络在任意参数下都有有限样本复杂度。
Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity
- 基于o-极小结构的网络架构具备可学习性
- 涵盖标准MLP/CNN/GNN/Transformer等主流模型
- 为现代模型学习能力提供统一理论基础
我们证明，在精确意义下，一大类前馈神经网络在PAC模型中具有有限样本复杂度：任何固定大小的前馈架构，其层若可定义于o-极小结构，则即使参数无界，在抗干扰的PAC设定下也具有有限样本复杂度。该结论涵盖标准的固定尺寸MLP、CNN、GNN、Transformer（固定序列长度），以及通常使用的操作与层，包括线性投影、残差连接、注意力机制、池化层、归一化层和允许的位置编码。因此，现代非循环架构的无分布学习能力并非特定激活函数或架构特异性VC论证的例外，而是温和前馈计算的结果。我们的结果将有限样本PAC可学习性重新定位为基线而非区分特征：推动架构比较的重点转向归纳偏置、对称性、几何先验、可扩展性及优化行为。
原文摘要 · Abstract (English)
We show that, in a precise sense, a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model: every fixed finite feedforward architecture whose layers are definable in an o-minimal structure has finite sample complexity in the agnostic PAC setting, even with unbounded parameters. This covers standard fixed-size MLPs, CNNs, GNNs, and transformers with fixed sequence length, together with the operations and layers typically used in such architectures, including linear projections, residual connections, attention mechanisms, pooling layers, normalization layers, and admissible positional encodings. Hence, distribution-free learnability for modern non-recurrent architectures is not an exceptional property of particular activations or architecture-specific VC arguments, but a consequence of tame feedforward computation. Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator: they shift the focus of architectural comparison toward inductive biases, symmetries and geometric priors, scalability, and optimization behaviour.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。