\section{Comparison to Neural Networks}

A shallow neural network with one hidden layer consists of an $n$-dimensional input layer $x$, a hidden layer $h$ of dimension $m$, and an output layer $o$. It can be expressed as:

\begin{align*}
    h_i(x) &= \sigma(w^i \cdot x + b_i), \qquad i = 1,\ldots,m \\
    o(x) &= a(h)
\end{align*}
 
Each neuron in the hidden layer computes an affine transformation of the input $x$ followed by a nonlinear activation function $\sigma$. The output layer aggregates the hidden layer outputs $h$ using an aggregation function $a$. In theory, any non-polynomial function can serve as an activation, but in practice, common choices include the ReLU, sigmoid, and tanh functions. The output layer may implement a simple sum or a more complex operation such as max pooling.

\begin{figure*}[!htbp]
\centering

\begin{adjustwidth}{\globalshift}{0cm} % negative left, zero right
\noindent
\begin{tikzpicture}[
    neuron1/.style={rectangle, rounded corners, draw, minimum width=.8cm, minimum height=0.4cm, fill=green!10, drop shadow, font=\scriptsize},
    neuron2/.style={rectangle, rounded corners, draw, minimum width=4cm, minimum height=0.4cm, fill=green!10, drop shadow, font=\scriptsize},
    layerlabel/.style={align=center, text width=1.5cm, font=\scriptsize},
    arrowstyle/.style={->, gray, line width=0.3pt, >=stealth, scale=0.6, shorten <=3pt, shorten >=6pt},
    every node/.style={font=\scriptsize}
  ]

\begin{scope}[xshift=\globalshift] % This moves the *whole drawing* left!
    
\foreach \copy in {0,1} {
  \begin{scope}[xshift=\copy*\diagramsep]

    % Input layer nodes
    \node[neuron1] (I-1) at (0,0) {$x_1$};
    \node[neuron1] (I-2) at (0,-\nodesep) {$x_2$};
    \node at (0, { -2*\nodesep + 0.1cm }) {\tiny$\vdots$};
    \node[neuron1] (I-n1) at (0,-3*\nodesep) {$x_{n-1}$};
    \node[neuron1] (I-n) at (0,-4*\nodesep) {$x_n$};

    % Hidden layer nodes, conditionally change formula for right graph
    \ifnum\copy=0
      \node[neuron2] (H-1) at (\layersep,0) {$h_1=\sigma(w^1\!\cdot\!x+b_1)$};
      \node[neuron2] (H-2) at (\layersep,-\nodesep) {$h_2=\sigma(w^2\!\cdot\!x+b_2)$};
      \node at (\layersep, { -2*\nodesep + 0.1cm }) {\tiny$\vdots$};
      \node[neuron2] (H-m1) at (\layersep,-3*\nodesep) {$h_{m-1}=\sigma(w^{m-1}\!\cdot\!x+b_{m-1})$};
      \node[neuron2] (H-m) at (\layersep,-4*\nodesep) {$h_{m}=\sigma(w^{m}\!\cdot\!x+b_{m})$};
    \else
      \node[neuron2] (H-1) at (\layersep,0) {$h_1 = \Phi(x, y^1) + r(y^1)$};
      \node[neuron2] (H-2) at (\layersep,-\nodesep) {$h_2 = \Phi(x, y^2) + r(y^2)$};
      \node at (\layersep, { -2*\nodesep + 0.1cm }) {\tiny$\vdots$};
      \node[neuron2] (H-m1) at (\layersep,-3*\nodesep) {$h_{m-1} = \Phi(x, y^{m-1}) + r(y^{m-1})$};
      \node[neuron2] (H-m) at (\layersep,-4*\nodesep) {$h_{m} = \Phi(x, y^{m}) + r(y^{m})$};
    \fi

    % Output node, conditionally sum or max
    \ifnum\copy=0
      \node[neuron2, minimum width=2.0cm] (O) at ($(2*\layersep, -2*\nodesep) + (\outputshift, 0)$) {$o = a(h)$};
    \else
      \node[neuron2, minimum width=2.0cm] (O) at ($(2*\layersep, -2*\nodesep) + (\outputshift, 0)$) {$o = \max_i h_i$};
    \fi

    % Connections input-hidden (straight)
    \foreach \i in {1,2,n1,n} {
      \foreach \h in {1,2,m1,m} {
        \draw[arrowstyle] (I-\i.east) -- (H-\h.west);
      }
    }
    % Connections hidden-output (straight)
    \foreach \h in {1,2,m1,m} {
      \draw[arrowstyle] (H-\h.east) -- (O.west);
    }

    % Layer labels
    \node[layerlabel] at ($(I-1)+(0, \labsep)$) {Input\\layer};
    \node[layerlabel] at ($(H-1)+(0, \labsep)$) {Hidden\\layer};
    \node[layerlabel] at ($(O)+(0, \labsep)$) {Output\\layer};

    % ===== Top Labels (above network) =====
    % x position: halfway between input and output node, y position above hidden layer
    \ifnum\copy=0
      \node[font=\bfseries, yshift=3.2cm] at ($(H-1)!0.5!(H-m)$) {Shallow Neural Network};
    \else
      \node[font=\bfseries, yshift=3.2cm] at ($(H-1)!0.5!(H-m)$) {Finitely Convex};
    \fi


  \end{scope}
    }
\end{scope}

\end{tikzpicture}

\end{adjustwidth}

\caption{Comparison between finitely convex functions and neural networks: The left side shows a shallow neural network with an $n$-dimensional input layer, a single $m$-dimensional hidden layer, and a one-dimensional output layer. $\sigma$ is an arbitrary nonlinear activation function, $w^i$ is the weight vector for the $i$-th neuron in the hidden layer, and $b_i$ is the bias for the $i$-th neuron. The right side shows a $\tilde{Y}$-convex function $r^{\tilde{Y}}$with $\tilde{Y} = \{y^1, y^2, \dots, y^m\}$.}
\label{fig:neural-ot}
\end{figure*}

As Figure~\ref{fig:neural-ot} shows, this structure is similar to our definition of finitely convex functions. The key differences are: (1) the inner product is replaced by the surplus function $\Phi(\cdot,\cdot)$; (2) the activation function $\sigma$ is the identity function; and (3) the aggregation function $a$ is $\max$. It is not surprising that no additional nonlinear activation is needed in the hidden layer, since the surplus function itself may be highly nonlinear.

Therefore, the results presented in this paper can be seen from the perspective of shallow neural networks. Although in theory a sufficiently wide shallow network can approximate any function that a deep network can, in practice deep networks are often more effective. Beyond empirical evidence, theoretical work suggests reasons for this: shallow, wide networks are more prone to memorizing training data, while deep networks are more likely to extract underlying structure.

This suggests that there may be more powerful alternatives to our finitely convex functions, which could perform better in practice by trading network width for depth.
