Research
Representing MAX functions using two-hidden-layer ReLU networks
arXiv:2608.25221v1 Announce Type: new Abstract: We study exact representations of MAX_N(x)=max{x_1,ldots,x_N} using two-hidden-layer ReLU neural networks. This problem has been studied in recent years
arXiv:2608.25221v1 Announce Type: new Abstract: We study exact representations of MAX_N(x)=max{x_1,ldots,x_N} using two-hidden-layer ReLU neural networks. This problem has been studied in recent years in an attempt to characterize the exact number of hidden layers required to represent continuous piecewise linear functions. The best lower bound is 2, while the current upper bound is logarithmic in N. It remains completely open if the right answer is a constant number of hidden layers (possibly even 2!) or not. In fact, a recent breakthrough was the representation of MAX_5 as a two-hidden-layer ReLU function obtained in [Bakaev et al., 2026], and the case of MAX_N was stated as open for Ngeq 6 in that paper. Using a careful computer assisted search, we obtain two-hidden-layer ReLU representations of MAX_5, MAX_6, MAX_7, and MAX_8. We obtain these by considering rational linear combinations of terms of the form max{sum_{r=1}^{s}max(x_{a_r},x_{b_r}),sum_{r=1}^{s}max(x_{c_r},x_{d_r})}, where a_r,b_r,c_r,d_rin{1,ldots,N}. Each inner maximum of two coordinates can be computed in a first hidden layer, and the outer maximum of the two side-sums can be computed in a second hidden layer. Consequently, every finite linear combination of these terms has a two-hidden-layer ReLU realization. An identity for MAX_N in this form therefore gives an exact two-hidden-layer ReLU representation of MAX_N. Very recently, two-hidden-layer representations of MAX_N of the above form were obtained for all Nleq 10 in [Ruess et al., 2026]. Our representations are different and were developed independently. While our techniques share most of the high-level ideas presented in [Ruess et al., 2026], there are also some minor differences which may be of interest for future research on this problem.
Related
- Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks
- Explicit integral representations and quantitative bounds for two-layer ReLU networks
- Every Layer Counts: An Exponential L_2 Depth Hierarchy for ReLU Networks
Source: arXiv cs.LG | 2026-08-27