[Paper] 每个可在 o-Minimal Structure 中定义的 Feedforward Neural Network 具有 Finite Sample Complexity

请提供您希望翻译的具体文本内容（除保留的来源链接外），我将为您翻译成简体中文并保持原有的格式。

概览

一种新的理论突破表明，任何固定规模的前馈神经网络，只要其层由“tame”数学运算（形式上，可在 o‑minimal 结构中定义）构建，就在 agnostic PAC 框架下保证能够从有限的数据中学习。该结果涵盖了最常见的现代架构——MLPs、CNNs、GNNs，甚至是固定序列长度的 transformers——且不需要对网络的权重施加人为的限制。

关键贡献

• 通用 PAC 可学习性定理，适用于所有层是 o‑最小可定义的前馈网络，无论激活函数或参数大小如何。
• 统一处理 多种架构（MLP、CNN、GNN、Transformer）以及典型构建块（线性映射、残差链接、注意力、池化、归一化、位置编码）。
• 证明有限样本可学习性是温和前馈计算的基线属性，而非特定激活函数或 VC 维度技巧的特殊情况。
• 概念转变：将研究焦点从“该架构是否可学习？”转向“它带来了哪些归纳偏置、对称性和优化特性？”

方法论

1. O‑最小结构 – 来自模型论的框架，用于捕获“行为良好”的集合和函数（例如，半代数的、子解析的）。作者表明，实际使用的大多数层都属于此类结构。
2. 无偏 PAC 分析 – 他们在最一般的学习设定下工作，对数据生成分布不作任何假设。
3. 有限样本复杂度界 – 通过利用 O‑最小可定义函数的温和几何性质，他们推导出统一收敛保证，从而得到仅依赖于网络结构（深度、宽度、可定义操作数量）的样本量界，而与参数的大小无关。
4. 层级组合 – 证明过程通过展示 O‑最小可定义层的组合仍保持 O‑最小性，进而在整个网络中保持可学习性属性。

结果与发现

• 有限样本复杂度：对于任意固定的网络结构，存在一个关于 (1/\epsilon) 的多项式以及 (\log(1/\delta)) 的上界，决定实现误差 (\epsilon) 且置信度为 (1-\delta) 所需的训练样本数量。
• 参数无关：即使权重可以任意大，该上界仍然成立，从而在理论保证中不再需要基于范数的正则化。
• 广泛适用性：该定理涵盖了已有针对特定激活函数（例如 ReLU）的 VC 维度结果，并将其扩展到更大类的函数，包括平滑激活函数、有理函数以及工业中使用的许多自定义层。

实际意义

• 设计自由：工程师可以尝试奇特的激活函数或归一化方案，只要这些操作仍然位于 o‑minimal 结构内，就不必担心理论可学习性的丧失。
• 基准转变：既然对任何合理的前馈设计可学习性已成定局，性能比较可以聚焦于 归纳偏置（例如 GNN 中的等变性）、可扩展性 和 优化动态，而不是“该架构是否能学习？”。
• 安全性与验证：温和几何视角与已经依赖半代数推理的形式化验证工具相契合，可能会简化将可证明保证集成到生产流水线中的过程。
• AutoML 课程：自动化架构搜索可以安全地探索更大的搜索空间（任何 o‑minimal 层），而无需嵌入额外的可学习性检查。

限制与未来工作

• Fixed architecture size: 该保证仅适用于具有预先指定层数和神经元数量的网络；它不涉及动态增长的架构（例如，实时添加层的神经架构搜索）。
• Sequence length restriction for transformers: 该结果适用于输入长度有界的 Transformer；将其扩展到无限或可变长度序列仍是一个未解决的问题。
• Optimization not covered: 虽然样本复杂度是有限的，但该定理并不保证随机梯度下降（或任何实际优化器）能够在合理时间内找到良好的解。
• Beyond feedforward: 循环网络、连续时间模型以及其他非前馈结构超出了当前 o‑minimal 框架的范围，计划在未来进行研究。

Bottom line: 对于构建现代深度学习系统的开发者而言，只要你保持在“可控”（tame）的层工具箱内并固定网络规模，这项工作就为你提供了坚实的 PAC‑学习基础。真正的挑战现在转向如何塑造网络的归纳偏置以及如何高效地进行训练。

作者

• Anastasis Kratsios
• Gregory Cousins
• Haitz Sáez de Ocáriz Borde
• Bum Jun Kim
• Simone Brugiapaglia

论文信息

• arXiv ID: 2605.07097v1
• 类别: stat.ML, cs.LG, cs.NE, math.LO, math.ST
• 出版时间: 2026年5月8日
• PDF: 下载 PDF