Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

技术摘要：利用 ReLU 神经网络对 o-minimal 结构中二分类任务进行快速逼近与学习

问题陈述
本文研究了决策集 $A \subseteq [-1/2, 1/2]^n$ 定义在实域的 o-minimal 扩张中的二分类问题。尽管深度神经网络在经验上取得了成功，但对其逼近能力和统计可学习性的理论理解通常依赖于对目标集的特定结构假设，例如边界的平滑性或 Barron 型函数类。作者旨在为一类更广泛的、由 o-minimality 定义的“驯 tame”集合建立定量逼近与学习率，这些集合包括半代数集及各种解析结构，且无需依赖可能在复杂决策边界处并不成立的全局平滑性假设。

方法论
作者引入了一类被称为**可追踪集（traceable sets）**的概念，作为 o-minimal 结构中可定义集的经典代理。这一概念的动机源于 o-minimal 几何中固有的细胞分解定理。

1. 可追踪集： 一个集合 $A$ 被定义为 $m$-可追踪的，如果它可以通过在纤维方向上定义边界的有界 $C^m$ 映射 $f_i, g_i$ 归纳地构建而成。具体而言，该集合是通过一系列“地平线（horizon）”函数构建的，其中每一层都由平滑函数限定。作者将 $(m, \ell)$-可追踪集定义为此类集合的有限不交并。
2. 扩展性质： 为了便于逼近，论文施加了一个 $(m, B)$-扩展性质，要求边界函数 $f_i, g_i$ 可以扩展为整个定义域上的 $C^m$ 函数，且具有有界的 Sobolev 范数。
3. 逼近策略： 核心逼近技术包括：
   • 使用 ReLU 神经网络逼近“地平线函数”（即由平滑图限定的区域的特征函数）。这利用了现有关于逼近平滑函数及其复合函数的结论。
   • 通过使用基于 ReLU 的最小化和最大化操作来构造可追踪集的特征函数（因为 $\chi_{\cap} = \min$ 且 $\chi_{\cup} = \max$）。
   • 利用集合的前沿（边界）在扩展假设下勒贝格测度为零这一事实，确保逼近集合的闭包对于 $L^p$ 逼近是充分的。
4. 学习框架： 统计学习分析结合了推导出的逼近率与 ReLU 神经网络类的熵估计（覆盖数）。作者在这些特定的网络类上应用经验风险最小化（ERM）与合页损失（hinge loss），以推导出泛化界限。

主要贡献与结果

• 定量逼近率： 论文证明了任何 $(m, \ell)$-可追踪集 $\Omega \subseteq [-1/2, 1/2]^n$ 的特征函数 $\chi_\Omega$ 都可以被 ReLU 神经网络 $\Phi_\epsilon$ 以精度 $\epsilon$ 在 $L^p$ 范数下逼近。

  • 网络规模： 所需的非零权重数量（规模）为 $O(\epsilon^{-p(n-1)/m})$。
  • 深度： 网络的深度与 $\epsilon$ 无关，具体为 $O(\log(\ell n) + \log(m))$。
  • 权重： 权重随 $1/\epsilon$ 至多呈多项式增长。
  • 该结果扩展到了定义在可追踪域上的可定义映射 $f: [-1/2, 1/2]^n \to \mathbb{R}$ 的子类。

• 统计学习率： 对于从定义域中均匀抽取的 $N$ 个独立样本，作者推导了在所构建的 ReLU 网络类上进行经验风险最小化的学习率。

  • 所得分类器的期望误分类误差被界定为 $O(N^{-m/(m+pn-p)})$，至多包含一个极小的多项式损失因子 $N^\kappa$。
  • 该速率是通过结合逼近误差界限与假设空间的覆盖熵推导而出的。

• 在 o-minimal 结构中的应用： 作者证明了 o-minimal 结构中“m-容许（m-admissible）”的可定义集合（即具有统一细胞分解界限的可定义集合的纤维集合）满足可追踪集的性质。因此，推导出的逼近率与学习率可以直接应用于这些可定义的集合与映射。

意义与主张
本文声称提供了一种基于 o-minimal 结构中可定义性的、具有数学鲁棒性的分类理论正则性概念。通过分离出实现快速逼近所需的解析特征（可追踪性与平滑扩展），作者表明 o-minimality 捕捉了广泛的实际决策集，同时能够实现强大的定量逼近与估计率。

其意义在于架起了模型论（o-minimality）与现代深度学习理论之间的桥梁。作者认为，o-minimal 结构提供了一个自然的统一框架，使得可以在其中同时研究逼近理论、统计学习与优化。与可能在函数复合方面存在困难的 Barron 型设置不同，o-minimal 框架自然地适应了深度神经网络中仿射映射与非线性激活的重复复合，因为可定义映射的复合仍然是可定义的。

结果表明，对于决策边界是“驯 tame”（可定义于 o-minimal 结构）的情况，ReLU 神经网络可以实现最优或近优的速率（取决于平滑参数 $m$ 和维度 $n$），而无需要求边界具有全局平滑性。论文明确指出，这些速率是针对特定的可定义集合与映射的子类推导出的，且学习率取决于 o-minimal 结构中可定义集合所固有的统一有限性质（关于连通分量与 VC 维的统一界限）。