Two-Layer Random ReLU Networks Can Separate Disjoint Classes
Organizations: Department of Mathematics, Hohai University 8 Focheng West Road, Jiangning District Nanjing 211100, China
Abstract
Set separation by continuous linear functionals is fundamental in functional analysis and convex optimization and underlies binary classification in machine learning. Support vector machines provide maximum-margin affine separators for linearly separable data, while kernel methods represent nonlinear decision rules through linear separation in a reproducing-kernel Hilbert space. We study when two classes, not necessarily convex or linearly separable in the input space, can be separated with positive margin by finite ReLU networks and by random ReLU features. At the deterministic level, we prove that positive-margin separation by a finite ReLU network is equivalent to the existence of finite closed convex covers whose opposite-label members have positive pairwise distances, and exactly two hidden layers suffice. For random separation, suppose each class is represented as a finite union of nonempty closed convex cells, possibly unbounded. If every opposite-label cell pair has positive distance and its closed difference cone is pointed, then two independent random ReLU layers yield a common positive-margin affine separator with high probability. The first layer separates the feature image of each negative cell from the feature image of the positive class by a hyperplane through the origin. It also controls all cross-class distances uniformly. The second layer combines cellwise scores through Chebyshev polynomials and realizes the resulting polynomial using Gaussian Hermite features, followed by a uniform finite-width approximation. With the remaining geometric, bias, and confidence parameters fixed, each sufficient width is quadratic in the largest Gaussian width of a spherical difference-cone section, hence at most linear in its span dimension. An example shows that this squared Gaussian-width dependence is sharp for both layers.
Figures & tables
| Work | Sets | Network | Separation and sufficient width |
|---|---|---|---|
| Dirksen et al. [ 7 ] | Two bounded sets at positive distance | Two ReLU layers. | Positive margin. First width: quadratic in Gaussian widths, at most linear in intrinsic dimension. Second: exponential in squared Gaussian widths, at most exponential in dimension. |
| Ghosal et al. [ 8 ] | Two bounded sets at positive distance | One ReLU layer. | Positive margin. Width exponential in squared Gaussian width, at most exponential in intrinsic dimension; additional mutual-complexity dependence (Theorem 1.4). |
| Xu et al. (UoS) [ 31 ] | Two -dimensional linear subspaces intersecting only at . | One quadratic layer; zero bias. | Strict separation off ; no uniform positive margin. Width for fixed minimum principal angle. |
| This work Theorems 2.5 , 2.7 | Finite unions of closed convex sets, possibly unbounded; positive opposite-set gaps and pointed difference cones. | Two ReLU layers. | Positive margin. Each width: quadratic in cone Gaussian widths, at most linear in intrinsic dimension; sharp complexity order (Example 3.2 ). |
| First layer alone | Joint successes | |||
|---|---|---|---|---|
| 0.06219 | 0.05 | 8 | ||
| 0.30414 | 0.50 | 12 | ||
| 0.43946 | 1.00 | 16 | ||
| 0.54280 | 1.50 | 20 | ||
| 0.63007 | 2.00 | 24 | ||
| 0.70724 | 2.50 | 24 |
ReLU Neural Networks
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
See all 133 papers