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

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 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.