arXiv:2607.01266math.LOcs.LG2026-07

用ReLU神经网络高效逼近可定义分类问题,给出精确误差率。

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

  • 基于o-极小结构的可定义集构造可追踪集,作为分类区域代理。
  • 在边界函数光滑条件下,神经网络大小为O(ε^{-p(n-1)/m}),误差达ε。
  • 适用于高维可定义分类任务,尤其适合理论分析与学习率推导。

我们研究决策集由实数域o-极小扩张中可定义集构成的二分类问题。受可定义集细胞分解启发,引入可追踪集作为可定义决策区域的经典近似,并分析其被ReLU神经网络逼近的性质。在连通分支数量有界且边界函数具有合适C^m扩展的条件下,证明了[-1/2,1/2]^n上可追踪子集的特征函数可在L^p范数下以精度ε被大小为O(ε^{-p(n-1)/m})的ReLU神经网络逼近,深度与ε无关,权重多项式有界。该结果建立了对某些o-极小结构中可定义集合的量化逼近率。相同方法也适用于一类可定义映射[-1/2,1/2]^n → ℝ。进一步结合ReLU神经网络类的熵估计,获得使用铰链损失的经验风险最小化统计学习率:对于N个均匀采样样本,所得分类器的期望误分误差为N^{-m/(m+pn-p)}量级,至多存在任意小的多项式损失。

原文摘要 · Abstract (English)

We study binary classification problems whose decision sets are given by definable sets in o-minimal expansions of the real field. Motivated by cell decomposition of definable sets, we introduce traceable sets as a classical proxy for definable decision regions and analyze their approximation by ReLU neural networks. Under uniform bounds on the number of connected components and suitable $C^m$ extensions for the boundary functions, we prove that characteristic functions of traceable subsets of $[-1/2,1/2]^n$ can be approximated in $L^p$ to accuracy $\varepsilon>0$ by ReLU neural networks of size $\mathcal{O}(\varepsilon^{-p(n-1)/m})$, with depth independent of $\varepsilon$ and polynomially bounded weights. This establishes quantitative approximation rates for certain definable collections in o-minimal structures using ReLU neural networks. The same approach also yields the stated approximation rates for a subclass of definable maps $[-1/2,1/2]^n \to \mathbb{R}$. We then combine the approximation capabilities with entropy estimates for ReLU neural network classes to obtain statistical learning rates for empirical risk minimization with hinge loss. For $N$ uniformly distributed samples, the resulting classifiers achieve expected misclassification error of order $N^{-m/(m+pn-p)}$ up to an arbitrarily small polynomial loss.

神经网络分类可定义集学习率

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。