Approximating Maxima And Minima With ReLU Networks

Why Maxima and Minima Fit ReLU Networks

Many targets in approximation theory are assembled by choosing the largest or smallest among several simpler functions. A maximum of affine functions, for example, is a convex piecewise-affine function. ReLU networks are well suited to these constructions because the ReLU activation itself can express a maximum exactly. This gives both a direct representation and a way to combine approximations without losing control of their error.

Here, a ReLU network means a feedforward network whose hidden units apply \(\rho(t)=\max\{t,0\}\) to affine combinations, with an affine output layer. We count ReLU units, not affine operations. For size statements, depth means the number of hidden layers. Exact identities for real-valued quantities will first be derived; we then connect those identities to network size and approximation error.

Exact ReLU Identities

For any real numbers \(a\) and \(b\), the difference \(a-b\) determines which is larger. If \(a\geq b\), then \(\rho(a-b)=a-b\), and if \(a<b\), then \(\rho(a-b)=0\). Thus

The corresponding minimum follows by subtracting the positive part of the same difference from \(a\):

These identities are exact, including at \(a=b\). Applied pointwise, they show that the maximum or minimum of two functions can be formed with one ReLU of their difference and affine combinations of the results. The two-function maximum is convex as a function of the pair \((a,b)\), but the identity itself requires no convexity assumption on the functions being combined.

Finite Maxima, Minima, and Network Size

A finite maximum can be computed by repeatedly applying the two-input identity. For \(m\) inputs, a binary tree combines pairs, then combines the resulting values, until one remains. If the tree is balanced, it has at most \(\lceil\log_2 m\rceil\) levels. A binary tree with \(m\) leaves has exactly \(m-1\) internal nodes, so the construction uses \(m-1\) max operations. Each operation uses one ReLU of a difference. Replacing every maximum by the minimum identity gives the analogous result for minima.

When the inputs are affine functions of \(x\), the computation can be implemented as a ReLU network. More generally, the binary-tree identities can be applied to outputs of networks. In a standard layered network, a value passed between hidden layers can be represented by the pair \((\rho(z),\rho(-z))\), since their difference is \(z\). This may add a constant number of units per intermediate value, but does not change the order of the size bound. Consequently, for \(m\) affine inputs, a balanced construction has \(O(m)\) ReLU units and \(O(\log m)\) depth. These are upper bounds; a particular collection of functions may admit a smaller network.

Proof. For \(m=1\), the function is affine and can be represented by the output layer. For \(m\geq2\), arrange the \(\ell_i\) as leaves of a binary tree, padding with repeated leaves if necessary to reach a power of two. At each internal node, apply \(\max\{u,v\}=v+\rho(u-v)\) to the functions at its two children. Induction up the tree shows that the value at each node is the maximum of the affine functions among its descendant leaves. Therefore, the root is \(f\). The tree has fewer than \(2m\) leaves after padding and hence fewer than \(2m\) internal nodes. It has at most \(\lceil\log_2 m\rceil\) levels. Each node requires one ReLU in the computation, and passing values between layers in a standard network uses at most a constant number of additional units per intermediate value through the positive-negative representation above. Thus the total number of ReLU units is \(O(m)\), and the depth is \(O(\log m)\). \(\square\)

The theorem also describes an important class of piecewise-affine functions. Each \(\ell_i\) is affine, so their maximum is continuous and piecewise affine: at a point where a particular \(\ell_i\) is largest, the maximum agrees with that affine function, and the regions are determined by the inequalities \(\ell_i(x)\geq\ell_j(x)\). The regions may be empty, and multiple pieces may tie on their boundaries. The theorem is a representation result for maxima of affine functions; it does not assert that every piecewise-affine function is a maximum of affine functions.

Uniform Approximation Error Through Maxima and Minima

Maxima and minima are also stable under uniform approximation. This matters when the functions being combined cannot themselves be represented exactly, or when they have already been approximated by networks. The key fact is that changing every candidate value by at most \(\varepsilon\) can change the largest or smallest value by no more than \(\varepsilon\).

Proof. Fix \(x\in\Omega\). For each \(i\), \(f_i(x)\leq g_i(x)+\varepsilon\), so taking the maximum over \(i\) gives \(\max_i f_i(x)\leq\max_i g_i(x)+\varepsilon\). Interchanging \(f_i\) and \(g_i\) gives \(\max_i g_i(x)\leq\max_i f_i(x)+\varepsilon\). Together these inequalities imply \(\left|\max_i f_i(x)-\max_i g_i(x)\right|\leq\varepsilon\). Taking the supremum over \(x\) proves the maximum bound. For minima, \(f_i(x)\leq g_i(x)+\varepsilon\) for every \(i\) implies \(\min_i f_i(x)\leq\min_i g_i(x)+\varepsilon\); interchanging the functions gives the reverse bound. Taking the supremum proves the minimum bound. \(\square\)

In particular, if each \(g_i\) is a network approximation to \(f_i\) with uniform error at most \(\varepsilon\), then an exact ReLU maximum of the \(g_i\) approximates the maximum of the \(f_i\) with error at most \(\varepsilon\). The number of candidates does not multiply this error. A larger number of components may increase network size, but the uniform error bound remains unchanged.

Minima, Envelopes, and a Common Pitfall

Minima need no separate approximation machinery: for any functions \(g_i\), \(\min_i g_i=-\max_i(-g_i)\). Negating the affine output of a network therefore converts a maximum construction into a minimum construction. More generally, a finite envelope formed by taking maxima or minima of network outputs can be represented by composing the pairwise identities. If the component networks each have a uniform approximation guarantee, the stability result gives a corresponding guarantee for the combined envelope.

Common pitfall: It is tempting to argue that if each of \(m\) component functions has error at most \(\varepsilon\), then the maximum has error at most \(m\varepsilon\), on the grounds that errors accumulate across the \(m\) candidates. That reasoning treats a maximum like a sum. At a fixed input, every candidate lies between its approximation minus \(\varepsilon\) and its approximation plus \(\varepsilon\); taking a maximum preserves those two bounds. The correct uniform error is at most \(\varepsilon\), independent of \(m\). Network size can grow with \(m\), but this particular error bound does not.

A second point to keep distinct is exact representation versus approximation. The maximum of finitely many affine functions is represented exactly by a ReLU network. If the candidates are nonlinear functions, the maximum identity is still exact as an operation, but the candidate functions may require approximation. In that case, the quality of the final result depends on the component approximation errors, while the maximum operation itself adds no further uniform error.