Two-Layer Random ReLU Networks Can Separate Disjoint Classes

Yichen Liu, Jianbin Yang

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…