PaperlayerView exact revision on arXiv

Source-linked AI summary

Representing MAX functions using two-hidden-layer ReLU networks

Zhimao Wang, Amitabh Basu

arXiv:2608.25221v1cs.LGmath.OCstat.ML

TL;DR

The paper addresses whether MAX_N can be represented with two hidden ReLU layers, a question tied to the hidden-layer complexity of continuous piecewise linear functions. It uses exact linear systems over symmetric atom combinations and obtains representations for MAX5 through MAX8, while its methods do not reach MAX9 or MAX10.

  • Problem

    The central gap is whether MAX_N admits two-hidden-layer ReLU representations beyond the previously established cases, within a problem whose general lower bound is 2 and upper bound is logarithmic.

  • Method

    The paper uses computer-assisted exact linear algebra on rational linear combinations of atoms, exploiting coordinate permutations and additional functional symmetries.

  • Results

    Two-hidden-layer ReLU representations are obtained for MAX5, MAX6, MAX7, and MAX8.

  • Takeaways & Limitations

    The results extend exact two-hidden-layer representations beyond MAX5, although the paper's approach does not provide a complete characterization of such representations.

  • Takeaways & Limitations

    The methods remain computationally inaccessible for MAX9 and MAX10, and the MAX8 representation uses degree k = 4 rather than Rueß et al.'s k = 3.

Abstract

from arXiv · show

We study exact representations of $\mathrm{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 $\mathrm{MAX}_5$ as a two-hidden-layer ReLU function obtained in [Bakaev et al., 2026], and the case of $\mathrm{MAX}_N$ was stated as open for $N\geq 6$ in that paper. Using a careful computer assisted search, we obtain two-hidden-layer ReLU representations of $\mathrm{MAX}_5, \mathrm{MAX}_6, \mathrm{MAX}_7$, and $\mathrm{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_r\in\{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 $\mathrm{MAX}_N$ in this form therefore gives an exact two-hidden-layer ReLU representation of $\mathrm{MAX}_N$. Very recently, two-hidden-layer representations of $\mathrm{MAX}_N$ of the above form were obtained for all $N\leq 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.

1 Introduction

The section frames ReLU expressivity through exact MAX_N representations and introduces symmetric atom combinations as a route to two-hidden-layer networks.

  • 1 Introduction: ReLU networks alternate affine maps with coordinatewise activations, and the number of activation applications defines the hidden-layer count.Their outputs are continuous and piecewise linear.
  • 1 Introduction: The best known general lower bound is 2 hidden layers, while arbitrary continuous piecewise linear functions have logarithmic upper bounds in the input dimension.The cited upper bound is ⌈log2(n + 1)⌉ hidden layers.
  • 1 Introduction: MAX_N is central because continuous piecewise linear functions can be expressed using affine compositions with MAX_{n+1}.Setting N = n + 1 transfers hidden-layer results for MAX_N to arbitrary continuous piecewise linear functions on R^n.
  • 1 Introduction: Atoms combine sums of pairwise coordinate maxima inside an outer maximum, with degree k counting the number of pair maxima on each side.Each atom pattern lists k ordered pairs for each of two sides, allowing repetition.
  • 1 Introduction: Each atom has a two-hidden-layer ReLU realization because pair maxima form the first layer and the outer maximum forms the second.Finite signed linear combinations therefore retain a two-hidden-layer realization.
  • 1 Introduction: The atom construction also has a convex-geometric interpretation through zonotopes and their convex hulls.After clearing denominators, an identity becomes an equality of Minkowski sums of polytopes.
  • 1 Introduction: Permutation symmetry preserves MAX_N and maps atoms to atoms, enabling orbit-based coefficient constraints and reduction to the sorted chamber.Equality on the sorted chamber extends globally by coordinate-permutation symmetry.

1.1 The approach in Rueß et al [RAB+26]

Rueß et al. impose orbit-wise coefficient symmetry and solve an explicit linear system on the sorted chamber to obtain MAX_N identities.

  • 1.1 The approach in Rueß et al [RAB+26]: Rueß et al. assign one coefficient λ_O to each orbit of degree-k atom patterns under the symmetric-group action.The resulting linear combination is permutation-invariant.
  • 1.1 The approach in Rueß et al [RAB+26]: Permutation invariance allows the search to restrict to the sorted chamber, where MAX_N(x) equals x_1.The atom-derived functions are invariant under coordinate permutations as well.
  • 1.1 The approach in Rueß et al [RAB+26]: On that chamber, the representation condition becomes equations involving atom-derived linear functions and vectors.The coefficients a_ℓ and b_d are explicit linear combinations of the orbit coefficients λ_O.
  • 1.1 The approach in Rueß et al [RAB+26]: Solving the resulting explicit linear system yields the desired representation of MAX_N.The target system sets the linear-function coefficients to represent x_1 and the vector terms to zero.

1.2 Our approach

The paper constructs permutation-invariant linear systems for representing MAX_N with degree-k atoms, incorporating functional symmetries and handling nondifferentiable terms on the sorted chamber.

  • Symmetry reduction: The approach first quotients atom patterns by reversals, within-side permutations, and left-right switching before forming coordinate-permutation orbits.These transformations preserve the represented atom function, so equivalence classes support a well-defined symmetric-group action.
  • Symmetry reduction: Orbit sums are invariant under coordinate permutations, allowing the MAX_N identity to be checked on the sorted chamber where MAX_N(x)=x_1.Equality on this chamber extends to all of R^N by permutation symmetry.
  • Linear-system formulation: The resulting coefficients are related through an explicit matrix linear system, although distinct atom orbits can produce identical vector pairs.This duplication means the chosen symmetries do not capture every functional equivalence among atoms.
  • Chamber analysis: Atoms are partitioned into ambiguous and unambiguous terms according to whether the two arguments of the outer maximum exchange dominance within the sorted chamber.Unambiguous terms are linear on the chamber, while ambiguous terms account for possible internal breakpoints.
  • Computational outcome: Solving the induced linear equations yields two-hidden-layer representations of MAX_5, MAX_6, MAX_7, and MAX_8.The dimensions of the corresponding systems are reported in Table 1.

1.3 Comparison of this paper to [RAB+26]

The paper’s method reaches MAX_8 but remains computationally inaccessible for MAX_9 and MAX_10, while Rueß et al. obtain those cases and a more compact MAX_8 representation.

  • Computational boundary: MAX_9 systems have 51,984 constraints and 210,540 variables, while MAX_10 systems have 112,837 constraints and 216,428 variables.The authors could not solve these systems with exact rational arithmetic within the available compute time.
  • Comparison with prior work: Rueß et al. obtain identities for MAX_9 and MAX_10, whereas these cases remain inaccessible to the paper’s methods and resources.The stated obstacle is the size of the exact rational linear systems.
  • Representation compactness: For MAX_8, Rueß et al. use degree k=3, while this paper uses degree k=4.Their representation therefore sums three two-term coordinate maxima rather than four.
  • Methodological differences: The paper’s linear system incorporates additional functional symmetries beyond the left-right switching symmetry also used by Rueß et al.These additional symmetries arise from the atom-pattern transformations introduced earlier.

2 An exact seven-class identity for MAX5

For MAX_5, the paper reports an exact identity found after symmetry reduction and orbit computation, with the theorem statement presenting a representation supported on selected atom orbits.

  • Search construction: The MAX_5 search uses degree k=2 atom patterns and reduces them to 131 orbits of equivalence classes under coordinate permutations.Canonical representatives P_1, …, P_131 are selected for these orbits.
  • Exact identity: Theorem 2.1 states an exact MAX_5 identity supported on selected atom orbits.The supplied theorem passage introduces the identity but does not reproduce its formula.
  • Representation support: The seven-class representation is one exact representation obtained from the selected seven orbits.The supplied passages identify its support size but do not provide the coefficients.

2 MAX5 = −2 5GO[P0] + 1 30GO[P3] + 1 120GO[P16] + 1 60GO[P22] + 1

The MAX5 identity is presented as an exact representation supported on selected atom orbits. Its coefficients are unique within those seven orbits, although other representations exist.

  • The displayed atom patterns include P81 = [11, 23 | 12, 45].
  • The alternative representation is supported on only five orbits.
  • Theorem 2.3 presents a second exact MAX5 identity.

2 MAX5 = −2 5GO[P0] + 1 15GO[P3] −1 40GO[P69] + 1 20GO[P95] −1 30GO[P97]. (7)

This section gives another exact MAX5 identity, expressed through a different collection of atom patterns and coefficients.

  • The identity includes the atom pattern P97 = [11, 23 | 25, 34].
  • The displayed representation uses P97 among its atom-pattern terms.

3 An exact seven-class identity for MAX6

The MAX6 search found representations with degree parameter k = 2 and organized the resulting atom patterns into symmetric-group orbits.

  • The search obtained representations of MAX6 with k = 2.
  • After quotienting by the stated symmetries and computing symmetric-group orbits, 144 atom-pattern orbits remained.
  • Theorem 3.1 presents an exact MAX6 identity.

2 MAX6 = −1 3GO[P0] + 1 90GO[P22] + 1 180GO[P51] − 1 360GO[P71]

A second exact MAX6 identity is presented, alongside a description of its nonuniqueness and the atom patterns used in one representation.

  • Theorem 3.3 gives a different exact MAX6 identity supported on nine orbits.
  • The displayed linear combination uses coefficients including −2, 1/90, 1/15, 1/180, and 1/720.
  • The listed patterns include P15, P44, P47, P56, P69, P118, P130, P135, and P142.

4 An exact 109-class identity for MAX7

The paper gives an exact three-summand representation of MAX7 using 109 atom patterns with rational coefficients listed in Table 2.

  • k = 3 yields an exact representation of MAX7.
  • Theorem 4.1 states the exact three-summand MAX7 identity.
  • 109 atom patterns and their rational coefficients are listed in Table 2 of Appendix A.

5 An exact 1,290-class identity for MAX8

The paper gives an exact four-summand representation of MAX8 using 1,290 atom patterns with rational coefficients listed in Table 3.

  • k = 4 yields an exact representation of MAX8.
  • Theorem 5.1 states the exact four-summand MAX8 identity.
  • 1,290 atom patterns and their rational coefficients are listed in Table 3 of Appendix B.

6 Conclusion

The method certifies two-hidden-layer representations through finite exact linear algebra, but its search reaches only MAX8 and is less efficient for MAX8 than the independent approach of Ruess et al.

  • Finite exact linear algebra certifies global piecewise-linear identities sufficient for two-hidden-layer ReLU representations.
  • The certificate is sufficient but not a complete characterization, so a failed linear-system search does not prove nonexistence of a representation.
  • MAX5, MAX6, MAX7, and MAX8 are represented, whereas Ruess et al. also obtain representations for MAX9 and MAX10.
  • The approach is computationally inaccessible for MAX9 and MAX10, and its MAX8 representation uses k = 4 instead of Ruess et al.'s k = 3.

A The complete MAX7 coefficient list

Appendix A records the complete coefficient data for the exact MAX7 identity, including 109 nonzero coefficients and their atom patterns, with abstract-letter orbit notation.

  • 109 nonzero coefficients and corresponding atom patterns comprise the complete MAX7 identity list.
  • Table 2 lists each index, coefficient c_j, and atom pattern Q_j = [left | right].
  • Abstract letters denote patterns, and coefficients apply to sums over all assignments of those letters to values in {1, ..., 7}.
  • The listed entries include rational coefficients attached to degree-three atom patterns such as aa aa aa aa | aa aa aa aa and aa aa aa aa | aa aa aa bc.
  • The coefficient list continues with numerous signed entries for patterns involving repeated and distinct abstract letters.
Loading 2608.25221v1…