The strict depth hierarchy conjecture for ReLU networks

At least 4 years old · documented by

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

k∗=⌈log⁡2(n+1)⌉.k^* = \left\lceil \log_2(n+1)\right\rceil.

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

ReLU⁡n(0)⊊ReLU⁡n(1)⊊⋯⊊ReLU⁡n(k∗−1)⊊ReLU⁡n(k∗)=CPWL⁡n.\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 k∗k^* strictly increasing the representable class. Its status is not resolved in the supplied source context.

References

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.