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

원문 초록

We study binary classification tasks whose decision sets are given by definable sets in o-minimal expansions of the real field. Motivated by the cell decomposition theory of definable sets, we introduce traceable sets that isolate the analytical properties of definable sets used for fast approximation by ReLU neural networks. Under uniform bounds on the number of cells and a suitable extension assumption for the boundary functions, we prove that classifiers can be approximated in $L^p$ up 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 suitable definable collections in o-minimal structures using ReLU neural networks. Furthermore, the stated approximation rates are also derived for definable maps under similar geometric assumptions on their smoothness domains. We then obtain statistical learning rates for empirical risk minimization with hinge loss over the approximating ReLU neural network classes. For $N$ uniformly distributed samples, the predicted classifiers achieve expected misclassification error of order $N^{-m/(m+n-1)}$ up to an arbitrarily small polynomial loss.