Two hidden layers in ReLU networks compute maximum of six numbers
A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
Machine LearningComputational Complexity
Summary
Finding the maximum number from a list is a common test for certain types of AI models called ReLU networks. The authors show that just two layers of these networks can exactly find the maximum of six real numbers. They discovered a neat mathematical identity, which they verified by hand without relying on computers. This proof also gives a detailed way to build such a network using only simple numbers and no biases.
What this means in practice
- •For neural network designers: Develop exact ReLU networks with two hidden layers that compute maximum of six inputs using fully specified weights and zero biases.
- •For optimization software developers: Incorporate rigorously proven small ReLU networks to improve numerical stability when computing max functions in optimization algorithms.
A theory result. No direct application yet.
Authors
Dimitrios Myrisiotis
Abstract
Exactly computing the maximum function is a standard test case for studying depth in ReLU networks. Two hidden layers are known to suffice for up to twelve inputs through computer-assisted constructions. For six real inputs, we give an explicit hexagon identity whose local structure yields a self-contained analytical proof of this depth bound. The identity was found by computer-assisted search; we prove it through explicit cancellations that can be checked entirely by hand, without executing a verification program. The identity also yields an explicit network with hidden widths $17$ and $41$, zero biases, and rational weights.