\subsection{Proof of \cref{claim:convex}} \label{sub:pf min-ReLU}


We prove that the FNN $\hat{f}_\theta$ from \cref{sub:monotonicity constraint} 
is convex if it only uses the max-ReLU neurons from~\eqref{eq:ReLU}.

First, the activation function of max-ReLU neurons from \eqref{eq:ReLU} 
is convex and monotonically non-decreasing, when $\theta_1, \ldots \theta_n \geq 0$.


\paragraph*{Claim 2:} 
The composition of such convex and monotonically non-decreasing functions is  still convex and monotonically non-decreasing.

This is because, for convex and monotonically non-decreasing functions
$\psi, \varphi_1, \ldots, \varphi_m$ of proper dimensions,
it holds that for any $x_1$ and $x_2$
\[
\begin{split}
    & \psi \big( \varphi_1 \big( \frac{x_1 + x_2}{2} \big), \ldots, \varphi_m \big( \frac{x_1 + x_2}{2} \big) \big) 
    \\ & \quad \leq \psi \big( \frac{\varphi_1(x_1) + \varphi_1(x_2)}{2}, \ldots, \frac{\varphi_m(x_1) + \varphi_m(x_2)}{2} \big)
    \\ & \quad \leq \frac{ \psi ( \varphi_1(x_1), \ldots, \varphi_m(x_1) ) + \psi ( \varphi_1(x_2), \ldots, \varphi_m(x_2) )}{2},
\end{split}
\]
where the first inequality holds due to the monotonicity of $\psi$
and the convexity of $\varphi_1, \ldots, \varphi_m$,
and the second inequality holds due to the convexity of $\psi$.

Thus, the composition $\psi ( \varphi_1(x), \ldots, \varphi_m(x) )$
is convex for $x$.

The function $\psi ( \varphi_1(x), \ldots, \varphi_m(x) )$
is also monotonically non-decreasing, due to the monotonicity of 
$\psi, \varphi_1, \ldots, \varphi_m$.


Now, for an FNN $\hat{f}_\theta$ composed of only max-ReLU neurons, 
we can inductively apply \textbf{Claim~2} over the layers
of the FNN (as in the proof in \cref{sub:pf postive}) to show that 
$\hat{f}_\theta$ is convex (as well as monotonically non-decreasing). \qed


\subsection{Proof of \cref{thm:postive to monotone}} \label{sub:pf postive}

From \eqref{eq:ReLU}, since the weights satisfy $\theta_1, \ldots \theta_d \geq 0$, it follows that the activation function $\varphi$ of each neuron is monotonically non-decreasing. 

For an FNN $\hat{f}_\theta$ that is composed of such neurons, we can inductively proof  the output of the first layer is monotonically non-decreasing with the inputs; the output of the second layer is monotonically non-decreasing for the inputs; and so on.

Hence, $\hat{f}_\theta$ is~monotone. \qed
{"config": "arxiv", "file": "2006.06417/appendix_a2.tex"}