High-dimensional classification problems with Barron regular boundaries under margin conditions

Jonathan García, Philipp Petersen · 2024

Read High-dimensional classification problems with Barron regular boundaries under margin conditions by Jonathan García, Philipp Petersen (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07312.txt.

Introduction

Jonathan Garcia and Philipp Petersen prove results about neural networks for sorting tasks, in a 2024 mathematics paper. Sorting data into classes is hard when the boundary between classes is jagged and the data has many dimensions. Their work covers boundaries with a regularity property named after Barron, under a condition that the classes keep some margin apart.

They show a network with three hidden layers can mimic such a classifier with error shrinking at a high polynomial rate, a speed usually seen only for smooth, low-dimensional problems. Stronger margins make jagged, high-dimensional sorting nearly as easy. Those approximation rates then yield fast learning guarantees, close to the best rate as sample size grows. Computer tests on sorting problems in several dimensions, up to handwritten digit images, back the theory.

Catalog record

CREATORJonathan García, Philipp Petersen
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-07312

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

High-dimensional classification problems with Barron regular boundaries under margin conditions Jonathan García, Philipp Petersen Abstract We prove that a classifier with a Barron-regular decision boundary can be approximated with a rate of high polynomial degree by ReLU neural networks with three hidden layers when a margin condition is assumed. In particular, for strong margin conditions, high-dimensional discontinuous classifiers can be approximated with a rate that is typically only achievable when approximating a low-dimensional smooth function. We demonstrate how these expression rate bounds imply fast-rate learning bounds that are close to n − 1 n^{-1} where n n is the number of samples. In addition, we carry out comprehensive numerical experimentation on binary classification problems with various margins. We study three different dimensions, with the highest dimensional problem corresponding to images from the MNIST data set. Keywords: Neural Networks, Binary classification, Fourier-analytic Barron space, Barron regular boundaries, Margin condition, Hinge loss. Mathematics Subject Classification: 68T05, 62C20, 41A25, 41A46. 1 Introduction Binary classification is one of the oldest problems in machine learning, and it provides a foundation for understanding multiclass classification [ 1 , 2 , 3 ] . This problem can be reduced to interpreting whether an element \bm{x} is inside a set \Omega or not, and this can be represented mathematically by an indicator function \mathbbm{1}_{\Omega}(\bm{x}) . Moreover, we define \Omega as \Omega:=\left\{\bm{x}\in[0,1]^{d}:\eta(\bm{x})\geq 1/2\right\}\penalty\ \text{ where }\penalty\ d\in\mathbb{N}_{\geq 2},\penalty\ \eta(\bm{x}):=\mu\left(Y=1|X=\bm{x}\right) (1) is the posterior probability, and denote the decision boundary of \Omega as \partial\Omega . Our goal is to approximate \mathbbm{1}_{\Omega} using neural networks, which is a complex problem since \mathbbm{1}_{\Omega} is a discontinuous function, can be very high dimensional, and it is known that approximation of high dimensional discontinuous functions is a serious problem in general [ 4 ] . It has also been shown that under classical smoothness assumptions on the decision boundaries \partial\Omega the classification problem admits a curse of dimension [ 5 ] . Probably, the most common classification problem is image classification. In this case the dimension depends on the resolution of the image, i.e. the number of pixels used to create it. Typically this leads to a very high dimensional problem, some well known sample sets to train classification models are for example MNIST with images of 28\times 28 pixels or ImageNet with images of 256\times 256 pixels. A classification method that uses a notion of distance to build the decision functions is expected to learn more easily in regions that are not close to the decision boundary. This suggest that learning should be relatively simple for distributions that do not have a lot of mass in the vicinity of the decision boundary. In order to control the mass in the vicinity of the decision boundary the following margin condition (M) is defined [ 6 ] . Let \mu be a Borel probability measure on [0,1]^{d} and \mathcal{D} a joint distribution induced by \mu of an i.i.d. sample set S=\{(\bm{x}_{i},y_{i})\}_{i=1}^{n},\quad\text{where}\quad(\bm{x}_{i},y_{i})\in[0,1]^{d}\times\{0,1\}\quad\text{and}\quad\mathbbm{1}_{\Omega}(\bm{x}_{i})=y_{i}, (2) for all i\in\{1,\ldots,n\} . Then, the margin condition is as follows. (M) There exist C,\gamma>0 , such that for all \epsilon>0 , \mu\left(B_{\epsilon}^{*}\right)\leq C\epsilon^{\gamma}\quad\text{where}\quad B_{\epsilon}^{*}:=\left\{\bm{x}\in[0,1]^{d}:\mathrm{dist}\left(\bm{x},\partial\Omega\right)\leq\epsilon\right\} is the ball of radius \epsilon>0 around \partial\Omega with respect to Euclidean distance \mathrm{dist}\left(\bm{x},\partial\Omega\right):=\inf_{\bm{x^{\prime}}\in\partial\Omega}\lVert\bm{x}-\bm{x^{\prime}}\rVert_{2}, and \gamma is called the margin exponent. Furthermore, in [ 7 ] it was also shown that by considering the class of measures \mu satisfying the following condition, rates independent of the input dimension and appearing in the form of a polynomial factor can be obtained. It is said that \mu is tube compatible with parameters \alpha\in(0,1] and C>0 if for each measurable function f:[0,1]^{d-1}\to[0,1] , each i\in\{1,\ldots,d\} and each \epsilon\in(0,1] , it is satisfied that \mu(T_{f,\epsilon}^{(i)})\leq C\epsilon^{\alpha}\penalty\ \text{ where }\penalty\ T_{f,\epsilon}^{(i)}:=\left\{\bm{x}=(x_{1},\ldots,x_{d})\in[0,1]^{d}:|x_{i}-f(\bm{x}^{(i)})|\leq\epsilon\right\} (3) and \bm{x}^{(i)}:=(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{d})\in[0,1]^{d-1} . The set T_{f,\epsilon}^{(i)} is called a tube of width \epsilon associated to f . Lastly, it was shown in [ 8 , 9 , 10 ] that for a class of functions with finite Fourier moment, the curse of dimensionality can be overcome when the approximation error is measured in the L^{2} norm. This influenced further research on the approximation in this class of functions (see e.g. [ 11 , 12 ] ) which is nowadays known as the Barron class. Motivated by the qualities of this class of functions, we will use them throughout this paper. To be more precise, we study how complex the classification learning for deep neural networks (NNs) with the rectified linear unit (ReLU) activation function and using the hinge loss (see Section 1.2 ) can be, when the margin condition (M) and the tube compatibility ( 3 ) are met, and \partial\Omega can be described by functions in Barron class (see Subsection 1.3.1 ). Under these conditions we obtained that: (i) Theorems 2 and 3 . It is possible to approximate \mathbbm{1}_{\Omega} using a ReLU-NN \Phi with three hidden layers and a number of neurons O(N) with N\in\mathbb{N} , having an error of \mu\left(\left\{\mathbbm{1}_{\Omega}\neq\Phi\right\}\right)\lesssim N^{-\gamma/2} for all probability measures \mu satisfying the margin condition (M) with margin exponent \gamma , and the tube compatibility ( 3 ). Moreover, when \Phi is trained using the hinge loss \phi (see ( 11 )), we obtain a learning rate (see Subsection 1.2.1 and Remark 4 ) of the order of O(n^{-\gamma/(2+\gamma)}(1+\log n)) , where N\lesssim n^{\gamma/(2+\gamma)} , n=|S| and S is a training set as in ( 2 ). Implying that when \gamma is large, we achieve to approximate \mathbbm{1}_{\Omega} (high-dimensional discontinuous function) by \Phi , at a rate comparable to that of a low-dimensional smooth function, with a fast learning rate of \approx n^{-1}(1+\log n) . (ii) Simulations 2.1 . We produce numerical simulations within the framework of our main theorems: we generate samples in d\in\{3,50,784\} dimensions to simulate the margin condition (M) applied with a margin exponent \gamma and varying the number of elements n in various ranges. Then, we conclude as \gamma and n increase, the test error (see Subsection 1.2.1 ) decreases at a rate close to that stated in our Theorem 3 and Remark 4 , which supports our results. 1.1 Background In [ 6 , Section 8] , the features of SVMs when applied to binary classification were investigated. It was shown that for distributions with noise but low concentration (margin condition (M) ) near the decision boundary, the approximation error for Gaussian kernels was relatively small, leading to favorable learning rates. A data-dependent strategy for selecting the regularization and kernel parameters was also studied, introducing the noise exponent to measure the amount of high noise in the labeling process. The learning rates achieved were sometimes as fast as n^{-1} , where n is the number of data points. Next in [ 13 ] , it was shown that a convergence rate similar to the rates of [ 6 ] can be achieved but using NN classifiers. Particularly, it was proved that the estimated classifier based on NNs with the hinge loss achieves similar fast convergence rates considering the following assumptions on the true classifier: (I) The noise Tsybakov condition is always met [ 14 ] . That is, there exist C>0 and q\in[0,\infty] such that for any \epsilon>0 , \mu\left(\left\{\bm{x}\in[0,1]^{d}:|2\eta(\bm{x})-1|<\epsilon\right\}\right)\leq C\epsilon^{q}. (II) The decision boundary is Hölder smooth, i.e. \partial\Omega can be described by functions in the space

Read the complete text