The strict depth hierarchy conjecture for ReLU networks

For n\boxinNn\boxin\mathbb{N}, let

k=log2(n+1).k^* = \left\lceil \log_2(n+1)\right\rceil.

Here, ReLUn(k)\operatorname{ReLU}_n(k) denotes the class of functions representable by ReLU neural networks with nn input variables and kk hidden layers, and CPWLn\operatorname{CPWL}_n denotes the class of continuous piecewise-linear functions on Rn\mathbb{R}^n. The strict depth hierarchy conjecture. For every nNn\in\mathbb{N},

ReLUn(0)ReLUn(1)ReLUn(k1)ReLUn(k)=CPWLn.\operatorname{ReLU}_n(0)\subsetneq\operatorname{ReLU}_n(1)\subsetneq\dots\subsetneq\operatorname{ReLU}_n(k^*-1)\subsetneq\operatorname{ReLU}_n(k^*)=\operatorname{CPWL}_n.

The conjecture asserts that the logarithmic-depth construction representing every continuous piecewise-linear function is depth-minimal, with every additional hidden layer up to kk^* strictly increasing the representable class. Its status is not resolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Christoph Hertrich, Amitabh Basu, Marco Di Summa and Martin Skutella, “Towards Lower Bounds on the Depth of ReLU Neural Networks”, arXiv:2105.14835 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.