RELU representation of $\max(x,y,z)$

Question

Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t_+=\max(0,t)$, so $t_+=t$ if $t\geq 0$ and $t_+=0$ if $t\leq 0$. (This is RELU=rectified linear unit in neural network language.) Note that $t=t_+-(-t)_+$ and $|t|=t_++(-t)_+$.

For the maximum of two variables we have \begin{align*} \max(x,y) &= x + (y-x)_+ \\ &= \left(x+y+(x-y)_++(y-x)_+\right) /2 \\ &= \left((x+y)_+-(-x-y)_++(x-y)_++(y-x)_+\right)/2 \end{align*} Is there a similar expression for $\max(x,y,z)$ as a linear combination of terms $\phi(x,y,z)_+$ with $\phi$ linear? I suspect not, but I have not found a proof. More generally, is there a nice characterisation of the functions of several variables that do admit such a representation?

Answer 1

There's indeed no such way to write $\max(x,y,z)$.

Lemma. Consider on $\mathbf{R}^n$ a function $f(x)=\sum_{i\in I}^m t_iL_i(x)_+$ where the $L_i$ are nonzero, pairwise non-positively-collinear linear forms, $t_i$ are nonzero scalars. Suppose that for some $i$, $f$ is locally linear at $x_0$ with $x_0\in\mathrm{Ker}(L_i)$. Then there exists $j$ (unique) such that $t_iL_i-t_jL_j=0$.

[So $L_j=\frac{t_i}{t_j}L_i$; since these are not positively collinear, necessarily $t_i$ and $t_j$ have distinct signs and in particular $j\neq i$. This also proves uniqueness. Thus the contribution $t_iL_i(x)_++t_jL_j(x)_+$ is linear, namely equal to $t_iL_i(x)$.]

Proof. Induction on $n$. For $n=1$, necessarily $m\le 2$. We can suppose $i=1$. We can rescale to assume $L_1(x)=x$. So $\mathrm{Ker}(L_1)=\{0\}$. So $f(x)=x_++t(ax)_+$ with $a\le 0$, for all $x$. The only possibility to get $f$ smooth at $0$ is to have $a=-1$.

For $n=2$, if no $L_j$, $j\neq i$, is collinear to $L_i$, then all such $L_j$ are smooth at $x_0$, and we get a contradiction. So for some $j$, $L_j$ is collinear to $L_i$, and we see that the only possibility for scalars is $t_iL_i=t_jL_j$.

For $n\ge 3$. Fix $i$ as in the lemma; up to rescale, we can suppose $t_i=1$. Let $P$ be any hyperplane passing through $x_0$. By induction, there exist $j_P$ such that in restriction to $P$ we have $L_i=t_{j_P}L_{j_P}$.

Suppose by contradiction that $L_i-t_jL_j$ is nonzero for all $j\neq i$. Then there exists $x$ such that $L_i(x)-t_jL_j(x)\neq 0$ for all $j$. Let $P$ be a hyperplane passing through $x_0$ and $x$. Then we get a contradiction.

Corollary. There is no function of the form $x\mapsto\sum_j t_jL_j(x)_+$ ($L_j$ linear) on $\mathbf{R}^3$ that equals $f:(x,y,z)\mapsto \max(x,y,z)$.

Proof. Write it as $x\mapsto\sum_k L_k(x)_++a_kL_k(-x)_+$, where the $L_k$ are nonzero and pairwise non-collinear. When $\mathrm{Ker}(L_k)$ is not one of the hyperplanes $x_i=x_j$, there is an element in this kernel at which $f$ is locally linear (namely any point with three distinct coordinates). Then the lemma ensures that $a_k=-1$, so that the contribution $L_k(x)_+-L_k(-x)_+$ is linear. So we can rewrite the given map as $$f(x)(=\max(x_1,x_2,x_3))=L(x)+ \sum_{1\le i\neq j\le 3}a_{ij}(x_i-x_j)_+$$ with $L$ linear. Write $L(x)=\sum_{i=1}^3a_ix_i$.

Since $f$ is symmetric, we have $f(x_1,x_2,x_3)=\frac16\sum_{\sigma\in\mathfrak{S}_3}f(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)})$. Hence we can suppose that the $a_i$ and $a_{ij}$ are symmetric too, which means that $a_i=b$ for some $b$ and $a_{ij}=c$ for some $c$. Thus $$f(x)=b(x_1+x_2+x_3)+c\left(\sum_{1\le i\neq j\le 3}(x_i-x_j)_+\right)$$ for all $x$. Evaluation at $x=(1,1,1)$ yields $b=1/3$. Evaluation at $x=(0,0,1)$ yields $1=b+2c$, so $c=1/3$, and evaluation at $x=(0,0,-1)$ yields $0=-b+4c$, and this is a contradiction.

Answer 2

Here is a simpler proof, inspired by YCor's approach. Fix a finite-dimensional vector space $V$ and let $F$ be the class of functions $V\to\mathbb{R}$ in question. First, by using the rule $t_+=(t+|t|)/2$ and combining terms appropriately, we see that any $f\in F$ can be represented as $$ f(x) = L_0(x) + |L_1(x)| + \dotsb + |L_n(x)| - |L_{n+1}(x)| - \dotsb - |L_{n+m}(x)|, $$ where $L_0,\dotsc,L_{n+m}$ are linear and $L_1,\dotsc,L_{n+m}$ are pairwise linearly independent. As $f(x)-L_0(x)$ is even, it follows that $f$ is differentiable at $x$ iff it is differentiable at $-x$. The $\max$ function is differentiable at $(1,0,0)$ but not at $(-1,0,0)$, so it does not lie in $F$.

For a sharper statement, we can proceed as follows. Let $P$ be the set of piecewise-linear maps $f\colon V\to\mathbb{R}$. For $f\in P$ and $x,v\in V$ put $$ Q(f,x)(v) = \lim_{t\to 0^+} t^{-1}\left(f(x+tv)+f(x-tv)-2f(x))\right). $$ Then $f\in F$ iff there are distinct hyperplanes $W_1,\dotsc,W_p<V$ such that

1. $Q(f,x)=0$ for $x\not\in W_1,\dotsc,W_p$
2. For each $i$ there is a linear map $L_i$ with kernel $W_i$ and $\epsilon_i\in\{1,-1\}$ such that $Q(f,x)(v)=\epsilon_i|L_i(v)|$ for all $x\in W_i\setminus\bigcup_{j\neq i}W_j$ and $v\in V$.