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 Cm extensions for the boundary functions, we prove that characteristic functions of traceable subsets of [-1/2,1/2]n can be approximated in Lp 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 → ℝ. 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.