stat.MLNov 3, 2026

Two-Layer Random ReLU Networks Can Separate Disjoint Classes

Authors: Yichen Liu, Jianbin Yang

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

Explore similar work

Aug 24, 2026

Every Layer Counts: An Exponential L2L_2 Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all k≥2k\geq2, we construct a globally [0,1][0,1]-valued, 11-Lipschitz function realized by a depth-(k+1)(k+1) network of width O(d4)\mathcal{O}(d^4), whereas any depth-kk network with unrestricted weights and width at most 2d2d(k−1)\frac{2^d}{2d(k-1)} has squared L2L_2 error at least 1/241/24 under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least 33. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case k=2k=2 gives a compactly supported separation between depths 33 and 22 with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally [0,1][0,1]-valued and O(d)\mathcal{O}(\sqrt d)-Lipschitz and maps the unit hypercube onto [0,1][0,1]. It is computed by a polynomial-width depth-44 network, whereas any depth-33 network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.
Oct 18, 2026

A Distribution-Free Separation Between Learned and Fixed Features

The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.
Apr 25, 2026

Explicit integral representations and quantitative bounds for two-layer ReLU networks

An approach to construct explicit integral representations for two-layer ReLU networks is presented, which provides relatively simple representations for any multivariate polynomial. Quantitative bounds are provided for a particular, sharpened ReLU integral representation, which involves a harmonic extension and a projection. The bounds demonstrate that functions can be approximated with L2(D)L^{2}(\mathcal{D}) errors that do not depend explicitly on dimension or degree, but rather the coefficients of their monomial expansions and the distribution D\mathcal{D}. We also present a connection to the RKHS of the exponential kernel K(x,y)=exp⁡(⟨x,y⟩)K(x,y)=\exp\left(\left\langle x,y\right\rangle \right), and a very simple integral representation involving additionally multiplication via a fixed function which has better quantitative bounds.