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

arXiv: https://arxiv.org/abs/2607.01266 · HTML: https://mlsanity.com/paper/2607.01266/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 29 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Fast convergence rates of deep neural networks for classification](https://mlsanity.com/paper/1812.03599/) (2018)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [Neural network approximation and estimation of classifiers with classification boundary in a Barron class](https://mlsanity.com/paper/2011.09363/) (2020)
- [Mathematical theory of deep learning](https://mlsanity.com/paper/2407.18384/) (2024)
- [Optimal learning of high-dimensional classification problems using deep neural networks](https://mlsanity.com/paper/2112.12555/) (2021)
- [Measurability in the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2410.10243/) (2024)
- [Deep Learning as the Disciplined Construction of Tame Objects](https://mlsanity.com/paper/2509.18025/) (2025)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [High-dimensional classification problems with Barron regular boundaries under margin conditions](https://mlsanity.com/paper/2412.07312/) (2024)

## Abstract (arXiv)

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.