Implicit Hypersurface Approximation Capacity in Deep ReLU Networks

We develop a geometric approximation theory for deep feed-forward neural networks with ReLU activations. Given a d-dimensional hypersurface in Rᵈ⁺¹ represented as the graph of a C²-function φ, we show that a deep fully-connected ReLU network of width $d+1$ can implicitly construct an approximation as its zero contour with a precision bound depending on the number of layers. This result is directly applicable to the binary classification setting where the sign of the network is trained as a classifier, with the network's zero contour as a decision boundary. Our proof is constructive and relies on the geometrical structure of ReLU layers provided in [doi:10.48550/arXiv.2310.03482]. Inspired by this geometrical description, we define a new equivalent network architecture that is easier to interpret geometrically, where the action of each hidden layer is a projection onto a polyhedral cone derived from the layer's parameters. By repeatedly adding such layers, with parameters chosen such that we project small parts of the graph of φ from the outside in, we, in a controlled way, construct a network that implicitly approximates the graph over a ball of radius R. The accuracy of this construction is controlled by a discretization parameter δ and we show that the tolerance in the resulting error bound scales as (d-1)R3/2δ1/2 and the required number of layers is of order d(32R/δ)d+1/2.