\section{\label{sec:intro}Introduction}
\vspace{-5pt}
The dramatic increase in mobile applications and the number of devices demanding for wireless connectivity poses a challenge in today's wireless networks \cite{cisco_index, ericsson_report}, and calls for new networking mechanisms.

One of the promising solutions to address the increasing data and connectivity demand is Device-to-Device (D2D) networking. As illustrated in Fig.~\ref{fig:intro_example_new}(a), the default operation in current wireless networks is to  connect each device to the Internet via its cellular or Wi-Fi interface. The D2D connectivity idea, which is illustrated in Fig.~\ref{fig:intro_example_new}(b), breaks this assumption: it advocates that two or more devices in close proximity can be directly connected, {\em i.e., } without  traversing through auxiliary devices such as a base station or access point. D2D networking, that can be formed by exploiting D2D connections such as Wi-Fi Direct \cite{WiFiDirect}, is a promising solution to the ever increasing number and diversity of applications and devices. In this context, it is crucial to identify scarce resources and effectively utilize them to fully exploit the potential of D2D networking.

Although bandwidth is traditionally considered as the primary scarce resource in wireless networks, in D2D networks, thanks to close proximity among devices and the developments in communication theory, the main bottleneck shifts from bandwidth to other scarce resources including processing power and energy. Next, we present our pilot study demonstrating that processing power can be more pronounced as a bottleneck than bandwidth in D2D networks.

\begin{figure}[t!]
\centering
\vspace{-2pt}
\subfigure[The default operation]{ {\includegraphics[height=21mm]{example_fig_a_2.eps}} }
\subfigure[D2D connectivity]{ {\includegraphics[height=21mm]{example_fig_b_2.eps}} }
\vspace{-5pt}
\caption{(a) The default operation for the Internet connection. (b) D2D connectivity: two or more mobile devices can be connected directly, {\em i.e., } without traversing through the  core network, if they are in close proximity by exploiting local area connections such as Wi-Fi Direct.
}
\vspace{-18pt}
\label{fig:intro_example_new}
\end{figure}

\underline{\textit{Pilot Study:}} We developed a prototype for this pilot study as shown in Fig. \ref{fig:complexityVsRate_new}(a), where a mobile device $D_2$ receives data from another device $D_1$ over a Wi-Fi Direct link. We use Android operating system \cite{AndroidDeveloper}  based Nexus 7 tablets \cite{NexusTechSpecs} as mobile devices. In this experiment, after receiving the packets, the mobile device $D_2$ performs operations with complexities of $\mathcal{O}(1)$, $\mathcal{O}(n)$, and $\mathcal{O}(n^2)$ above the transport layer (TCP), where $n$ is the packet size, and the operations we perform are counting the bytes in the packets. In particular, $\mathcal{O}(1)$, $\mathcal{O}(n)$, and $\mathcal{O}(n^2)$ correspond to (i) no counting, (ii) counting every byte in a packet once, and (iii) counting every byte in a packet $n$ times, respectively. We demonstrate in Fig.~\ref{fig:complexityVsRate_new}(c) the received rate at the mobile device $D_2$ (note that this is the rate we measure at the mobile device $D_2$ after performing computations) versus time. This figure demonstrates that the received rate decreases significantly when the complexity increases. \hfill $\Box$

Our pilot study shows that even if actual bandwidth is high and not a bottleneck, processing power could become a bottleneck in D2D networks. Similar observations are made for the energy bottleneck as detailed in Appendix A. Furthermore, with the advances in communication theory, {\em e.g., } millimeter wave communication \cite{mmWave_rap}, it is expected that  data rates among devices in close proximity will increase significantly, which will make processing power and energy more pronounced as bottlenecks. However, existing applications, algorithms, and protocols are mainly designed by assuming that bandwidth is the main bottleneck. Thus, it is crucial to develop new networking mechanisms when bandwidth is not the primary bottleneck, but processing power and energy are.

\begin{figure}[t!]
\centering
\vspace{-3pt}
\subfigure[Setup] { {\includegraphics[width = 35mm]{ap_and_mobile_device.eps}} }
\subfigure[Rate vs Time]{{\includegraphics[width = 38mm]{hs_rate_vs_complexity_3.eps}} }
\vspace{-8pt}
\caption{\textbf{Pilot Study:} (a) Setup: Data is transmitted from mobile device $D_1$ to another mobile device $D_2$. In this setup,
the mobile devices are Android operating system (OS) \cite{AndroidDeveloper} based Nexus 7 tablets \cite{NexusTechSpecs}. The specific version of the Anroid OS is Android Lollipop 5.1.1. The devices have 16GB storage, 2GB RAM, Qualcomm Snapdragon S4 Pro, 1.5GHz CPU, and Adreno 320, 400MHz GPU. Packet size is $500B$. (b) Transmission rate versus time for different computational complexities at the receiver side. Note that we present the rate that we measure at the mobile device after performing the computations. The presented rates are the average rate of 10 seeds.}
\vspace{-18pt}
\label{fig:complexityVsRate_new}
\end{figure}

Thus, in this paper, our goal is to create group of devices that help each other cooperatively by exploiting high rate D2D connections to overcome the processing power and energy bottlenecks. The next example demonstrates our approach.

\begin{example} \label{ex1} Let us consider Fig.~\ref{fig:intro_example_new}(a) again, where device $D_1$ would like to receive a file from a remote resource via using its cellular or Wi-Fi connection. Assume that the cellular (or Wi-Fi) rates of all devices are 1Mbps, but device $D_1$ can receive data with 500kbps rate due to processing power bottleneck, {\em i.e., } device $D_1$ has limited processing power (similar to our pilot study we presented earlier). In a traditional system, $D_1$ will behave as a single end point, so its receiving rate will be limited to 500kbps. On the other hand, if devices $D_1$, $D_2$, and $D_3$ will behave as a group and cooperate, then devices $D_2$ and $D_3$ can also receive and process 500kbps portions of data, and transmit the processed data to device $D_1$ over D2D connections. This increases the receiving rate of device $D_1$ to 1.5Mbps from 500kbps, which is a significant improvement.

This example could be extended for scenarios when energy (battery of mobile devices) is limited.  For example, if device $D_2$'s battery level is too low, its participation to the group activity  should be limited. \hfill $\Box$
\end{example}

\underline{{\em Application Areas.}}  The scenario in the above motivating example could arise in different practical applications from health, education, entertainment, and transportation systems. The following are some example applications. {\em Health:} A person may own a number of health monitoring devices (activity monitoring, hearth monitoring, etc.) which may need updates from the core network. These updates - potentially coded for error correction, compression, and security reasons - should be processed (decoded) by these devices. Processing takes time, which may lead to late reaction to the update (which may require timely response) and energy consumption. On the other hand, by grouping mobile devices, the person's smartphone or tablet could receive the update, process, and pass the processed data to the health monitoring devices via high rate D2D links. {\em Education \& Entertainment:} A group of students may want to watch the video of a lecture from an online education system (or an entertainment video) while sitting together and using several mobile devices. In this setup, one of the devices can download a base layer of a video and decode, while the other devices could download enhancement layers and decode. The decoded video layers could be exchanged among these mobile devices via high rate D2D links. As in the motivating example, if one device's download and decoding rate is limited to 500kbps, it could be improved to 1.5Mbps with the help of other devices.

Note that the processing overhead in these applications could be due to any computationally intensive task related to data transmission. For example, for video transmission applications, H.264/AVC decoders introduce higher computational complexity when higher quality guarantees are needed \cite{1286980,1218201}. Another example could be network coding; for example, data could be network coded at the source to improve throughput, error correction, packet randomization potential of network coding \cite{NC_meets_TCP}. However, most of the network coding schemes introduce high computational complexity at the receiver side; $\mathcal{O}(n^3)$,  \cite{5357971, 5061951}, which limits the transmission rate. Encryption could be another example that introduces processing overhead \cite{modern_complexity}.

Thus, there exists several applications and scenarios where bandwidth and energy could be bottlenecks, while bandwidth is not the bottleneck. This makes our approach demonstrated in Example~\ref{ex1} crucial. In particular, in this paper, we develop an {\em energy-aware cooperative computation} framework for mobile devices. In this setup, a group of cooperative mobile devices, within proximity of each other, (i) use their cellular or Wi-Fi (802.11) links as their primary networking interfaces, and (ii) exploit their D2D connections (Wi-Fi Direct) for cooperative computation. Our approach is grounded on a network utility maximization (NUM) formulation of the problem and its solution \cite{tutorial_doyle}. The solution decomposes into several parts with an intuitive interpretation, such as flow control, computation control, energy control, and cooperation \& scheduling. Based on the structure of the decomposed solution, we develop a stochastic algorithm; {\em energy-aware cooperative computation}.\footnote{Note that our work focuses on cooperative resource utilization in mobile devices. In this sense, our work is complementary to and synergistic with: (i) creating incentive mechanisms in D2D networks, and (ii) providing privacy and security for D2D users \cite{bits_and_coins, survey_d2d}. Looking into the future, it is very likely that our proposed work on the design, analysis, and implementation of cooperative resource utilization is gracefully combined with the work on creating incentives and providing privacy and security.}
The following are the key contributions of this work:
\begin{itemize}
  \item We consider a group of cooperative mobile devices within proximity of each other. In this scenario, we first investigate the impact of processing power to transmission rate. Then, we develop an energy-aware cooperative computation  model, where devices depending on their energy constraints could cooperate to get benefit of aggregate processing power in a group of cooperative devices.
  \item We characterize our problem in a NUM framework by taking into account processing power, energy, and bandwidth constraints. We solve the NUM problem, and use the solution to develop our stochastic algorithm; {\em energy-aware cooperative computation (EaCC)}. We show that EaCC provides stability and optimality guarantees.
  \item An integral part of our work is to understand the performance of EaCC in practice. Towards this goal, we develop a testbed consisting of  Nexus 5 smartphones and  Nexus 7 tablets. All devices uses Android 5.1.1 as their operation systems. We implement  {\em EaCC} in this testbed, and evaluate it. The experimental results show that our algorithm brings significant performance benefits.
\end{itemize}

The structure of the rest of the paper is as follows. Section~\ref{sec:related} presents related work. Section~\ref{sec:system} gives an overview of the system model. Section~\ref{sec:NUM} presents the NUM formulation of our cooperative computation scheme. Section~\ref{sec:CoopComp} presents our stochastic algorithm; {\em EaCC}. Section~\ref{sec:performance} evaluates the performance of our scheme in a real testbed. Section~\ref{sec:conclusion} concludes the paper.

\vspace{-5pt}
\section{\label{sec:related} Related Work}
\vspace{-5pt}
This work combines ideas from D2D networking, network utility maximization, and stochastic network control.

The idea of D2D networking is very promising to efficiently utilize resources, so it has found several applications in the literature. In particular, D2D connections are often used to form cooperative groups for data streaming applications, and for the purpose of (i) content dissemination among mobile devices \cite{micro4,micro5}, (ii) cooperative video streaming over mobile devices \cite{microcast, microcast_allerton, micro6, micro7}, and (iii) creating multiple paths and providing better connectivity by using multiple interfaces simultaneously \cite{chesterfield_micro, stiemerling_micro}. As compared to this line of work, we investigate the impact of processing power and energy in D2D networks, and develop mechanisms to effectively utilize these scarce resources.

D2D networking is often used for the purpose of offloading cellular networks. For example, previous work \cite{micro1, micro2, micro4} disseminate the content to mobile devices by taking advantage of D2D connections to relive the load on cellular networks. Instead of offloading cellular networks, our goal is to create energy-aware cooperation framework to overcome the processing power and energy bottlenecks of mobile devices.

There is an increasing interest in computing using mobile devices by exploiting connectivity among mobile devices \cite{survey_mobile_to_ubiq}. This approach suggests that if devices in close proximity are capable of processing tasks cooperatively, then these devices could be used together to process a task as it is a cheaper alternative to remote clouds. This approach, sparking a lot of interest, led to some very interesting work in the area \cite{trans_clouds1}, \cite{cloud_down_to_earth}, \cite{mclouds}. As compared to this line of work, we focus on processing power and energy bottlenecks in mobile devices and address the problem by developing energy-aware cooperative computation mechanism.

An integral part of our proposed work in this task is to develop efficient resource allocation mechanisms. In that sense, our approach is similar to the line of work emerged after the pioneering work in \cite{tass1}, \cite{tass2}, \cite{neelymoli}. However, our focus is on energy-aware cooperative computation.

\vspace{-5pt}
\section{\label{sec:system}System Model}
\vspace{-5pt}
We consider a cooperative system setup with  $N$ mobile devices, where $\mathcal{N}$ is the set of the mobile devices. Our system model for three nodes are illustrated in Fig.~\ref{fig:systemModel}(a). The source in Fig.~\ref{fig:systemModel}(a) represents the core network and base stations (access points). This kind of abstraction helps us focus on the bottlenecks of the system; processing power, energy of mobile devices, and downlink/uplink data rates. In this setup, mobile devices communicate via D2D connections such as Wi-Fi Direct, while the source communicates with mobile devices via cellular or Wi-Fi links. We consider in our analysis that time is slotted and $t$ refers to the beginning of slot $t$.

\begin{figure*}[t!]
\centering
\subfigure[System Model]{ {\includegraphics[height = 34mm]{system_model.eps}} }   \hspace{2mm}
\subfigure[Building blocks of the source.]{{\includegraphics[height = 25mm]{source_block_diagram.eps}} } \hspace{2mm}
\subfigure[Building blocks of mobile device $n$]{{\includegraphics[height = 33mm]{example_fig_c.eps}} }
\vspace{-8pt}
\caption{(a) System model for the scenario of three devices; $n$, $m$, $k$. The source in this model represents the core network and base stations (access points). (b) Building blocks of the source. File$_n$, $\forall n$ is read and inserted in the buffer $S_n(t)$, and packets are transmitted from $S_n(t)$. $x_{n,k}(t)$ is the transmission rate of the packets from the source towards device $n$, and these packets will be processed by device $n$ and forwarded to device $k$.
(c) Building blocks of mobile device $n$. If packets are received from the source via cellular and WiFi interfaces, then they go to the computation and energy control blocks. If packets are received from other mobile devices via D2D interface, they are directly passed to the application.
}
\vspace{-15pt}
\label{fig:systemModel}
\end{figure*}

{\bf Connecting Devices Together:}
The total flow rate towards device $n$ in  Fig.~\ref{fig:systemModel}(a) (and also explained in Fig.~\ref{fig:systemModel}(b)) is $\sum_{k \in \mathcal{N}} x_{n,k}(t) $, where $x_{n,n}(t)$ is the transmission rate of the packets from the source towards device $n$, and these packets will be used by device $n$. Note that $x_{n,k}(t)$ is the transmission rate of the packets from the source towards device $n$, and these packets will be processed by device $n$ and forwarded to device $k$. On the other hand, $y_n(t)$ is the total flow rates targeting device $n$ as demonstrated in Fig.~\ref{fig:systemModel}(b). The source constructs a queue $S_{n}(t)$ for the packets that will be transmitted to the mobile device $n$. The evolution of $S_n(t)$ based on $y_n(t)$ and $x_{k,n}(t)$ is expressed as
\begin{align} \label{eq:queueS}
S_{n}(t+1) \leq \max [S_n(t) - \sum_{k \in \mathcal{N}} x_{k,n}(t), 0] + y_{n}(t),
\end{align} where the inequality comes from the fact that there may be less than $y_{n}(t)$ packets arriving into $S_{n}(t)$ at time $t$ in practice ({\em e.g., } in real time applications, the number of available packets for transmission could be limited).

The flow rate $y_n(t)$ is coupled with a utility function $g_n(y_n(t))$, which we assume to be strictly concave function of $y_n(t)$. This requirement is necessary to ensure stability and utility optimality of our algorithms. The ultimate goal in our resource allocation problem is to determine the flow rates; $y_n(t)$ which maximize the sum utility $\sum_{n \in \mathcal{N}} g_n(y_n(t))$.

Finally, flow rate over D2D connection between device $n$ and $k$ is $h_{n,k}(t)$, $k\neq n$. Note that $h_{n,k}(t)$ is to help node $k$ using node $n$ as a processing device.

{\bf Inside a Mobile Device:} In each device, we develop different modules depending on where data is arriving from (as shown in Fig.~\ref{fig:systemModel}(c)); {\em i.e., } from the source via cellular or WiFi interface, or other mobile devices via D2D interfaces.

When data is arriving from a D2D interface, it is directly passed to the application layer, as this data is already processed by another device. On the other hand, when data is arriving from the source via cellular or WiFi interfaces, packets go through multiple queues as shown in Fig.~\ref{fig:systemModel}(c), where $U_{n,k}$, $Q_{n,k}$, and $Z_{n,k}$ represent three different queues constructed at mobile device $n$ for the purpose of helping node $k$. Incoming packets via cellular or WiFi links are stored in $U_{n,k}$, which then forwards the packets to {\em computation} block with rate $d_{n,k}(t)$. The computation block processes the packets, and pass them to queue $Q_{n,k}$. Note that the output rate from computation block is $d_{n,k}(t) \alpha_{n,k}(t)$, where $\alpha_{n,k}(t)$ is a positive real value. This value captures any possible rate changes at the computation block, {\em i.e., } $\alpha_{n,k}(t)$ is a rate shaper. For example, if the computation block is H.264/AVC decoder or transcoder, we expect that the rate at the output of the computation block should be higher than the input. Thus, $\alpha_{n,k}(t)$ captures this fact for any $n,k,t$. On the other hand, if there is no rate change after the processing, then $\alpha_{n,k}(t) = 1$.

The processed (and possibly rate shaped) packets are queued at $Q_{n,k}(t)$ and passed to {\em energy filter}. The energy filter is coupled to the energy source, which determines the amount of energy that can be spent to support the tasks at each slot. The amount of energy is determined according to {\em  energy credits}. In particular, the energy source, depending on the battery level as well as the estimate on the expected battery consumption in the near future, calculates the number of packets that can be supported by the mobile device, and the same number of energy credits enter the energy filter. (Note that both energy filter, energy source, and energy credits are not real, but virtual entities, so they can be modeled by using a few counters in practice.) Thus, at each transmission slot, packets are transmitted from $Q_{n,k}(t)$ to $Z_{n,k}(t)$ if there are energy credits in the energy filter. Finally, packets from $Z_{n,k}(t)$ are transmitted to application if device $n$ is the destination of the data ({\em i.e., } $n=k$), or they are transmitted to the original destination via D2D interface with rate $h_{n,k}(t)$.

The computation and energy filter blocks in Fig.~\ref{fig:systemModel}(c) model the processing and energy bottlenecks of the mobile device, respectively. If packets in $U_{n,k}$ increases too much, this means that the computation block, hence processing power, is the bottleneck, so node $n$ should not receive much packets from the source. Similarly, if $Q_{n,k}$ increases too much, this means that energy filter is the bottleneck, so again node $n$ should not receive much packets. Note that there could be also some buildup in $Z_{n,k}$ if the link between node $n$ and $k$ is the bottleneck of the system, and it should be taken into account when the energy-aware cooperative computation framework is developed.

Also, it is crucial in our system model to put energy filter after the computation block, because if device $n$ will help device $k$, the actual amount of packets that are supposed to be transmitted are the processed packets, which will cause energy consumption ({\em i.e., } not the packets before processing).

Based on the above intuitions and observations, we will develop our resource allocation problem and algorithm in the next sections. The evolution of the queues $U_{n,k}(t)$, $Q_{n,k}(t)$, and $Z_{n,k}(t)$ are provided in Table~\ref{table:queueEvolution}.

\begin{table}[t!]
\vspace{-5pt}
\caption{Evolution of queues $U_{n,k}(t)$, $Q_{n,k}(t)$, and $Z_{n,k}(t)$.}
\centering
\begin{tabular}{  | c | }
    \hline  $U_{n,k}(t+1) \leq \max [U_{n,k}(t) - d_{n,k}(t), 0] + x_{n,k}(t)$  \\
    \hline  $Q_{n,k}(t+1) \leq \max [Q_{n,k}(t) - e_{n,k}(t), 0] + d_{n,k}(t) \alpha_{n,k}(t)$    \\
    \hline  $Z_{n,k}(t+1) \leq \max [Z_{n,k}(t) - h_{n,k}(t), 0] + e_{n,k}(t)$   \\
    \hline
\end{tabular}
\label{table:queueEvolution}
\vspace{-5pt}
\end{table}

{\bf Links:}
In our system model, we consider two scenarios: (i) cellular + Wi-Fi Direct, and (ii) Wi-Fi + Wi-Fi Direct.  In both cases, the D2D links between mobile devices are Wi-Direct. In the first case, {\em i.e., } in cellular + Wi-Fi Direct, the links between the source and mobile devices are cellular, while they are Wi-Fi in the second case, {\em i.e., } in  Wi-Fi + Wi-Fi Direct. These two scenarios are different from each other, because in the first scenario, cellular and Wi-Fi Direct links could operate simultaneously as they use different parts of the spectrum. On the other hand, in the second scenario, both Wi-Fi and Wi-Fi Direct use the same spectrum, so they time share the available resources. Our model and energy-aware cooperative computation framework are designed to operate in both scenarios. Next, we provide details about our link models.\footnote{Note that the link models described in this section provide a guideline in our algorithm development and basis in our theoretical analysis. However, in Section~\ref{sec:performance}, we relax the link model assumptions we made in this section, and evaluate our algorithms on real devices and using real links.}

In the system model in Fig.~\ref{fig:systemModel}(a), each mobile device $n \in \mathcal{N}$ is connected to the Internet via its cellular or Wi-Fi link. At slot $t$, $\boldsymbol C^{s}(t)$ is the channel state vector of these links, where $\boldsymbol C^{s}(t) = \{C_{1}^{s}(t),$ $...,$ $C_{n}^{s}(t),$ $...,$ $C_{N}^{s}(t)\}$. We assume that $C_{n}^{s}(t)$ is the state of the link between the source and mobile device $n$, and it takes ``ON'' and ``OFF'' values depending on the state of the channel. Without loss of generality, if mobile device $n$ does not have Internet connection, then $C_{n}^{s}(t)$ is always at ``OFF'' state, which means there is no cellular or Wi-Fi connection.

Since we consider that mobile devices are in close proximity and transmission range, they form a fully connected clique topology. At slot $t$, $\boldsymbol C^{w}(t)$ is the channel state vector of the D2D links, where $\boldsymbol C^{w}(t)$ $=$ $\{C_{1,2}^{w}(t),$ $...,$ $C_{n,k}^{w}(t),$ $...,$ $C_{N-1,N}^{w}(t)\}$. We assume that $C_{n,k}^{w}(t)$ is the state of the D2D link between node $n$ and $k$.

We consider protocol model in our formulations \cite{gupta_interference_model}, where each mobile device can either transmit or receive at the same time at the same frequency. Assuming that $\boldsymbol C(t) = \{\boldsymbol C^{s}(t), \boldsymbol C^{w}(t)\}$ is the channel state vector of the system including both the links between the source and mobile devices as well as among mobile devices, $\Gamma_{\boldsymbol C(t)}$ denotes the set of the link transmission rates feasible at time slot $t$ depending on our protocol model. In particular, for cellular + Wi-Fi Direct setup, $\Gamma_{\boldsymbol C(t)}$ is the set that allows more links to be operated at the same time, while for the Wi-Fi + Wi-Fi Direct setup, $\Gamma_{\boldsymbol C(t)}$ is more limited set to take into account the interference among the links.

\vspace{-5pt}
\section{\label{sec:NUM} Problem Formulation}
\vspace{-5pt}
In this section, we characterize the stability region of the energy-aware cooperative computation problem, and formulate network utility maximization (NUM) framework. The solution of the NUM framework provides us insights for developing the stochastic control algorithms in the next section.\footnote{Note that NUM optimizes the average values of the parameters that are defined in Section~\ref{sec:system}. By abuse of notation, we use a variable, {\em e.g., } $\phi$ as the average value of $\phi(t)$  in our NUM formulation if both $\phi$ and $\phi(t)$ refers to the same parameter.}

\subsection{\label{sec:stabRegion} Stability Region}
We provide the stability region of the cooperative computation system for both cellular + Wi-Fi Direct and W-Fi + Wi-Fi Direct setups. First, the flow conservation constraint at the source should be $y_n \leq \sum_{k \in \mathcal{N}} x_{k,n}$ to stabilize the system. This constraint requires that the total outgoing rate from the source, {\em i.e., } $\sum_{k \in \mathcal{N}} x_{k,n}$ should be larger than the generated rate $y_n$.

Furthermore, the following flow conservation constraints inside a mobile device should be satisfied for stability; $x_{n,k} \leq d_{n,k}$, $d_{n,k} \alpha_{n,k} \leq e_{n,k}$, and $e_{n,k} \leq h_{n,k}$. These constraints are necessary for the stability of queues $U_{n,k}$,  $Q_{n,k}$, and  $Z_{n,k}$, respectively. Finally, the transmission rates over the links should be feasible, {\em i.e., } $\{ x_{n,k}, h_{n,k} \}_{\forall n \in \mathcal{N}, k \in \mathcal{N}} \in \Gamma_{\boldsymbol C}$.

Thus, we define the stability region as $\Lambda = \{ \{y_n, x_{n,k}, d_{n,k}, e_{n,k}, h_{n,k}\}_{\forall n \in \mathcal{N}, k \in \mathcal{N}}$ $|$ $y_n$, $x_{n,k}$, $d_{n,k}$, $e_{n,k}$, $h_{n,k}$ $\geq 0$, $\forall n \in \mathcal{N}, k \in \mathcal{N}$, $y_n \leq \sum_{k \in \mathcal{N}} x_{k,n}$, $x_{n,k} \leq d_{n,k}$, $d_{n,k} \alpha_{n,k} \leq e_{n,k}$, $e_{n,k} \leq h_{n,k}$, $\{ x_{n,k}, h_{n,k} \}_{\forall n \in \mathcal{N}, k \in \mathcal{N}} \in \Gamma_{\boldsymbol C}\}$.

\subsection{\label{sec:NUM_Formulation} NUM Formulation}
Now, we characterize our NUM problem.
\begin{align} \label{opt:eq1}
\max_{\boldsymbol y} \mbox{ } & \sum_{n \in \mathcal{N}} g_n(y_n)  \nonumber \\
\mbox{s.t.} \mbox{ }  & y_n, x_{n,k}, d_{n,k}, e_{n,k}, h_{n,k} \in \Lambda,  \mbox{ } \forall n \in \mathcal{N}, k \in \mathcal{N}
\end{align}
The objective of the NUM problem in (\ref{opt:eq1}) is to determine  $y_n, x_{n,k}, d_{n,k}, e_{n,k}, h_{n,k}$ for $\forall n \in \mathcal{N}, k \in \mathcal{N}$ which maximize the total utility $\sum_{n \in \mathcal{N}} g_n(y_n)$.

\subsection{\label{sec:NUM_Solution} NUM Solution}
Lagrangian relaxation of the flow conservation constraints that characterize the stability region $\Lambda$ gives the following Lagrange function:

\begin{align} \label{relax:eq1}
L & = \sum_{n \in \mathcal{N}} g_{n}(y_{n}) - \sum_{n \in \mathcal{N}} s_n (y_n - \sum_{k \in \mathcal{N}} x_{k,n}) - \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} u_{n,k} \nonumber \\
&  (x_{n,k} - d_{n,k}) - \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} q_{n,k}(d_{n,k}\alpha_{n,k} - e_{n,k}) - \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} \nonumber \\
& z_{n,k} (e_{n,k} - h_{n,k})
\end{align} where $s_n$, $u_{n,k}$, $q_{n,k}$, and $z_{n,k}$ are the Lagrange multipliers. Note that we will convert these Lagrange multipliers to queues $S_n$, $U_{n,k}$, $Q_{n,k}$, and $Z_{n,k}$ when we design our stochastic algorithm in the next section.

The Lagrange function in (\ref{relax:eq1}) is decomposed into sub-problems such as flow, computation, and energy controls as well as cooperation and scheduling. The solutions of  (\ref{relax:eq1}) for $y_n$, $d_{n,k}$, $e_{n,k}$, $x_{n,k}$, and $h_{n,k}$ are expressed as:
\begin{align}
\label{eq:decSol1} & \mbox{\underline {Flow control:} } \max_{\boldsymbol y} \mbox{ }   \sum_{n \in \mathcal{N}} (g_{n}(y_n) - y_n s_n)  \\
\label{eq:decSol2} & \mbox{\underline {Computation control:} }\max_{\boldsymbol d} \mbox{ }  \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} d_{n,k} (u_{n,k} - q_{n,k} \alpha_{n,k})   \\
\label{eq:decSol3}  & \mbox{\underline {Energy control:} } \max_{\boldsymbol e} \mbox{ }  \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} e_{n,k} (q_{n,k} - z_{n,k})  \\
\label{eq:decSol4} & \mbox{\underline {Cooperation \& Scheduling:} } \nonumber \\
& \max_{\boldsymbol x, h} \mbox{ }  \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} [x_{n,k} (s_k - u_{n,k}) + z_{n,k} h_{n,k}] \nonumber \\
& \mbox{s.t. } \mbox{ } \{ x_{n,k}, h_{n,k} \}_{\forall n \in \mathcal{N}, k \in \mathcal{N}} \in \Gamma_{\boldsymbol C}
\end{align}

Next, we design a stochastic algorithm; energy-aware cooperative computation inspired by the NUM solutions in (\ref{eq:decSol1}), (\ref{eq:decSol2}), (\ref{eq:decSol3}), (\ref{eq:decSol4}).

\section{\label{sec:CoopComp} Energy-Aware Cooperative Computation }
Now, we provide our energy-aware cooperative computation algorithm  which includes {\em flow control}, {\em computation control}, {\em energy control}, and  {\em cooperation \& scheduling}.

\underline{Energy-Aware Cooperative Computation (EaCC):}
\begin{itemize}
 \item {\em Flow Control:} At every time slot $t$, ${y}_n(t)$ is determined by maximizing $\max_{\boldsymbol {{y}}}$  $[M g_{n}({y}_n(t)) -  {S}_{n}(t) {y}_{n}(t) ]$ subject to  ${y}_n(t) \leq R_{n}^{\max}$, where $R_{n}^{\max}$ is a positive constant larger than the transmission rate from the source, and $M$ is a large positive constant. Note that ${S}_{n}(t)$ is the queue size at the source of flow and stores packets that are supposed to be transmitted to mobile device $n$. After ${y}_n(t)$ is determined, ${y}_n(t)$ packets are inserted in queue $S_n(t)$ (as illustrated in Fig.~\ref{fig:systemModel}(a)).

\item {\em Computation Control:}  At every time slot $t$, the computation control algorithm at device $n$ determines $d_{n,k}(t)$ by optimizing
\begin{align} \label{eq:decoder}
\max_{\boldsymbol d} & \mbox{  } \sum_{k \in \mathcal{N}} d_{n,k}(t) [U_{n,k}(t) - Q_{n,k}(t)\alpha_{n,k}(t)] \nonumber \\
\mbox{s.t. } & \sum_{k \in \mathcal{N}} d_{n,k}(t) \leq D_{n}^{\max}
\end{align} where $D_{n}^{\max}$ is a positive constant larger than the processing rate of the computation block in device $n$ dedicated to help device $k$. The interpretation of (\ref{eq:decoder}) is that at every time slot $t$, $d_{n,k^{*}}= D_{n}^{\max}$ packets are passed to the computation block (in Fig.~\ref{fig:systemModel}(b)) if $U_{n,k^{*}}(t) - Q_{n,k^{*}}(t) > 0$, where $k^{*}$ is the mobile device that maximizes (\ref{eq:decoder}).  Otherwise, no packets are sent to the computation block. The packets that are being processed by the computation block are passed to $Q_{n,k}(t)$. Note that some computation blocks may require to receive a group of packets to be able to process them. In that case, $D_{n}^{\max}$ is arranged accordingly ({\em i.e., } it can be increased to transfer a group of packets).

\item {\em Energy Control:}
At every time slot $t$, the energy control algorithm at device $n$ determines $e_{n,k}(t)$ by optimizing
\begin{align} \label{eq:energy}
\max_{\boldsymbol e} & \mbox{  } \sum_{k \in \mathcal{N}} e_{n,k}(t) [Q_{n,k}(t) - Z_{n,k}(t)] \nonumber \\
\mbox{s.t. } & \sum_{k \in \mathcal{N}} e_{n,k}(t) \leq E_{n,k}^{\max}
\end{align} where $E_{n}^{\max}$ is a positive constant larger than the energy capacity of device $n$ dedicated to help device $k$. The interpretation of (\ref{eq:energy}) is that at every time slot $t$, $e_{n,k^{*}}= E_{n}^{\max}$ packets are passed to the energy filter (as illustrated in Fig.~\ref{fig:systemModel}(b)) if $Q_{n,k^{*}}(t) - Z_{n,k^{*}}(t) > 0$, where $k^{*}$ is the mobile device that maximizes (\ref{eq:energy}). Otherwise, no packets are sent to the energy filter. The packets passing through the energy filter are inserted in $Z_{n,k}(t)$.

\item {\em Scheduling \& Cooperation:}  At every time slot $t$, the scheduling and cooperation algorithm determines transmission rates over links, {\em i.e., } $x_{n,k}(t)$ and $h_{n,k}(t)$ by maximizing
\begin{align} \label{eq:schedulingCoop}
\max_{\boldsymbol x, \boldsymbol h} & \mbox{  } \sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}} [x_{n,k}(t) (S_{k}(t) - U_{n,k}(t)) + h_{n,k}(t) Z_{n,k}(t) ] \nonumber \\
\mbox{s.t. } & {\boldsymbol x, \boldsymbol h} \in \Gamma_{\boldsymbol C(t)}
\end{align} For cellular + Wi-Fi Direct system, (\ref{eq:schedulingCoop}) is decomposed into two terms: maximizing $\sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}}$ $x_{n,k}(t) (S_{k}(t)$ $-$ $U_{n,k}(t))$ and $\sum_{n \in \mathcal{N}} \sum_{k \in \mathcal{N}}$ $h_{n,k}(t) Z_{n,k}(t)$, because cellular and Wi-Fi Direct transmissions operate simultaneously and transmission over one link does not affect the other. On the other hand, for Wi-Fi + Wi-Fi Direct setup, the joint optimization in (\ref{eq:schedulingCoop}) should be solved.

Note that transmissions over all links are unicast transmissions in our work, where unicast is dominantly used in practice over cellular, Wi-Fi, and Wi-Fi Direct links. Also, it is straightforward to extend our framework for broadcast transmissions.

\end{itemize}

\begin{theorem}\label{eec_theorem1}
If channel states are i.i.d. over time slots, and the arrival rates $E[y_{n}(t)] = A_n, \forall n \in \mathcal{N}$ are interior of the stability region $\Lambda$, then energy-aware cooperative computation stabilizes the network and the total average queue sizes are bounded.

Furthermore, if the channel states are i.i.d. over time slots, and the traffic arrival rates are controlled by the flow control algorithm of energy-aware cooperative computation, then the admitted flow rates converge to the utility optimal operating point with increasing $M$.
\end{theorem}
{\em Proof:} The proof is provided in Appendix B. $\blacksquare$

Our energy-aware cooperative computation framework has several advantages: (i) distributed, (ii) takes into account scarce resources such as processing power and energy in addition to bandwidth to make control decisions, and (iii) utilizes available resources; processing power, energy, and bandwidth in a utility optimal manner. Theorem~\ref{eec_theorem1} shows the theoretical performance guarantees of our framework, while we focus on its performance in a practical setup in the next section.

\vspace{-5pt}
\section{\label{sec:performance} Performance Evaluation}
\vspace{-5pt}
In this section, we evaluate our {\em energy-aware cooperative computation} (EaCC) scheme using a tested that consists of Android based smartphones and tablets. The evaluation results show that our scheme significantly improves throughput as compared to (i) no-cooperation, where each device receives its content from the source without cooperating with other devices,  and (ii) cooperation, where multiple mobile devices cooperate, but the cooperating devices do not do computation and energy control for other devices (mobile devices just receive packets from the source, and relay them to other mobile devices without processing and energy control). Next, we present testbed setup and results in detail.

\begin{figure*}[t!]
\centering
\vspace{-5pt}
\subfigure[System Model]{ {\includegraphics[height = 32mm]{two_device_coop_v2.eps}} }
\subfigure[Rate vs. Time]{ {\includegraphics[height = 32mm]{hs_edited_fig.eps}} }
\subfigure[Rate vs. Energy]{ {\includegraphics[height = 32mm]{BatteryAndComplexityON2.eps}} }
\vspace{-5pt}
\caption{(a) System model consisting of a source device, one receiver, and one helper. Wi-Fi is used between the source and the receiver device ($R_1$) and the helper device ($H_1$), while Wi-Fi Direct is used to connect $R_1$ to $H_1$. (b) Average rate versus time for the setup shown in (a) for the case that all the devices are Android  based Nexus 7 tablets. (c) Average rate versus energy level at receiver device $R_1$. In this setup, all devices are Android based Nexus 5 smartphones. In both (b) and (c), the average rate is calculated as the average over 10 trials (with different seeds). The computation under consideration in this experiment is $O(n^2)$, which basically counts the number of bytes in a packet for each byte in the packet ({\em i.e., } recursive counting).
}
\vspace{-15pt}
\label{fig:Rate_vs_time_results}
\end{figure*}

\subsection{Setup \& Implementation Details}
\vspace{-5pt}
{\em Devices:} We implemented a testbed of the setup shown in Fig.~\ref{fig:systemModel}(a) using real mobile devices, specifically Android 5.1.1 based Nexus 5 smartphones and Nexus 7 tablets.

We classify devices as (i) a source device, which acts as the source in Fig.~\ref{fig:systemModel}(a), (ii) helper devices, which receive data from the source, process it, and transmit to other devices (receivers) to help them, and (iii) receiver devices, which receive data from both the source device and the helpers. A receiver device processes data arriving from the source, but it does not process the data arriving from helpers as the helpers send already processed data. Note that a device could be both receiver and a helper device depending on the configuration.

{\em Integration to the Protocol Stack:} We implemented our energy-aware cooperative computation (EaCC) framework as a slim layer between transport and application layers. In other words, we implemented our framework on top of TCP. This kind of implementation is advantageous, because (i) mobile devices do not need rooting, and (ii) our framework and codes could be easily transferred to mobile devices using other operating systems such as iOS.\footnote{We note that we will make our codes and applications publicly available, which we believe will contribute to the research community.}

{\em Source Configuration and EaCC Implementation:} We implemented the source node in Fig.~\ref{fig:systemModel} using a Nexus 5 smartphone.
Basically, multiple files; File$_n$, File$_k$ requested by devices $n$ and $k$ are read by using the public java class {\em BufferedInputStream} according to the flow control algorithm described in Section~\ref{sec:CoopComp} and shown in Fig.~\ref{fig:systemModel}(b). The bytestream is packetized by setting each packet to $500B$, and packets are inserted into source buffers; $S_n(t)$, $S_k(t)$.  We set the flow control parameters as; $M=500$, $R_n^{\max} = 100$, and slot duration is $20msec$. We used $\log$ function as our utility function. In this setup, reading files, converting bytestream into packets, and inserting packets into the input queues are done by multiple threads, {\em i.e., } a thread runs for each file; File$_n$ in Fig.~\ref{fig:systemModel}(b).

The other set of threads at the source device make packet transmission decisions from the source device to receiver and helper devices. In particular, the source node collects $U_{n,k}(t)$ information from all mobile devices.  At each time slot, the source node checks $S_k(t) - U_{n,k}(t)$, and if $S_k(t) - U_{n,k}(t) > 0$, then $100$ packets are transmitted from $S_k(t)$ to the TCP socket at the source device for transmission to mobile device $n$.

{\em EaCC Operation on Mobile Devices:} All mobile devices (including helper or receiver+helper devices) implement all the building blocks illustrated Fig.~\ref{fig:systemModel}(c). Multiple threads are used to make these blocks operating simultaneously.

The first thread at mobile device $n$ receives packets that are transmitted by the source node, and inserts these packets in $U_{n,k}$.

The second thread has two tasks. First, it transfers packets from $U_{n,k}$ to $Q_{n,k}$ according to the computation control algorithm in (\ref{eq:decoder}), where $D_{n}^{\max} = 100$ packets and the slot duration is $20msec$. We set $\alpha_{n,k}(t)=1$ in our experiments as our applications do not change the rate as explained later in this section.  The second task of this thread to actually do the computation tasks related to the application. In our experiments, the computation block counts the bytes in the packets. In particular, similar to the pilot study in the introduction, $\mathcal{O}(1)$, $\mathcal{O}(n)$, and $\mathcal{O}(n^2)$ correspond to (i) no counting, (ii) counting every byte in a packet once, and (iii) counting every byte in a packet $n$ times, respectively.

The third thread transfers packets from $Q_{n,k}$ to $Z_{n,k}$ using the energy control algorithm in (\ref{eq:energy}), where we set $E_{n,k}^{\max}$ depending on the battery level of the device. For example, if the battery level is below some threshold $E_{n,k}^{\max}$ is limited. We evaluated different configurations in our experiments as we explain layer. The slot duration is again set to $20msec$.

The final thread transfers packets from $Z_{n,k}$ to application layer if $n=k$, or transmits to node $k$ if $n \neq k$. In the second case, {\em i.e., } if $n \neq k$, the number of packets in TCP socket is checked at every time slot, where the time slot duration is $20msec$. If it is below a threshold of $500$ packets, then $100$ packets are removed from $Z_{n,k}$ and inserted to the TCP socket to be transmitted to node $k$.

When node $n$ receives packets from node $k$, it directly passes the packets to the application layer as illustrated in Fig.~\ref{fig:systemModel}(c), because these packets are the ones that are already processed by node $k$. If node $n$ is both a helper and a receiver device, it runs all the threads explained above in addition to the receiving thread from node $k$ (illustrated in Fig.~\ref{fig:systemModel}(c)).

{\em Information Exchange:} Our implementation is lightweight in the sense that it limits control information exchange among mobile devices. The only control information that is transmitted in the system is $U_{n,k}$ from each mobile device to the source node. Each mobile device $n$ collects $U_{n,k}$, $\forall k \in \mathcal{N}$, and transmits this information to the source node periodically, where we set the periods $100msec$.

{\em Connections:} All the devices in the system including the source device, helpers, receivers, and helper+receiver devices are connected to each other using Wi-Fi Direct connections in our testbed. The source node is configured as the group owner of the Wi-Fi Direct group. We note that cooperation in this setup does not bring any benefit in terms of bandwidth utilization as all the links use the same transmission channel in a Wi-Fi Direct group. However, as we demonstrate later in this section, it brings benefit due to cooperative processing power and energy utilization, which is our main focus in this paper. Therefore, this setup (where all the devices are connected to each other using Wi-Fi Direct links) well suits to our evaluation purposes.

{\em Test Environment:} We conducted our experiments using our testbed in a lab environment where several other Wi-Fi networks were operating in the  background. We located all the devices in close proximity of each other, and we have evaluated EaCC for varying levels of computational complexity, number of receivers, and number of helpers. Next, we present our evaluation results.

\begin{figure*}[t!]
\centering
\vspace{-5pt}
\subfigure[System Model]{ {\includegraphics[height = 32mm]{multiple_helper_one_receiver.eps}} }
\subfigure[Rate vs. Number of Helpers]{ {\includegraphics[height = 32mm]{CombinedResultsCompexity10seeds.eps}} }
\subfigure[Rate vs. Number of Helpers]{ {\includegraphics[height = 32mm]{CombinedResultsCompexity10seeds_compare_coop_wo_process.eps}} }
\vspace{-5pt}
\caption{(a) System model consisting of a source device, one receiver, and multiple helpers. Wi-Fi is used between the source and the receiver device ($R_1$) and the helper devices ($H_1, \ldots$), while Wi-Fi Direct is used to connect the receiver devices with the helper devices. (b) EaCC: Average rate measured at receiver $R_1$ versus the number of helpers. (c) Average rate measured at receiver $R_1$ versus the number of helpers for EaCC and cooperation, when the complexity is $O(n^2)$.
}
\vspace{-15pt}
\label{fig:Rate_vs_helpers_one_receiver_results}
\end{figure*}

\subsection{Results}
\vspace{-5pt}
We first consider a setup as shown in Fig.~\ref{fig:Rate_vs_time_results}(a) which consists of a source device, one receiver ($R_1$), and one helper ($H_1$). Fig.~\ref{fig:Rate_vs_time_results}(b) shows the average rate versus time graph for the setup shown in Fig.~\ref{fig:Rate_vs_time_results}(a) when all three devices are Android based Nexus 7 tablets. The average rate is calculated as the average over 10 trials (with different seeds). The computation under consideration in this experiment is $O(n^2)$, which basically counts the number of bytes in a packet $n$ times, $n$ is the packet size. As can be seen, if there is no cooperation, the rate measured at $R_1$ is on the order of 1.5Mbps. On the other hand, EaCC increases the rate to almost 3Mbps. This means that helper device $H_1$ helps the receiver device $R_1$ to process the packets in EaCC. In this setup, EaCC doubles the rate as compared to no-cooperation, which is a significant improvement.

For the same setup in Fig.~\ref{fig:Rate_vs_time_results}(a), we also evaluate the effect of energy control part of EaCC on the average rate performance. In particular, Fig.~\ref{fig:Rate_vs_time_results}(c) shows the average rate versus battery level at the receiver device $R_1$. In these results, we used Android based Nexus 5 smartphones. The average rate is calculated as the average over 10 trials (with different seeds). The computation under consideration in this experiment is $O(n^2)$, which basically counts the number of bytes in a packet for each byte in the packet. We consider that if the battery level of a device reduces below 40\% threshold, then energy credits are not generated for the processing of the received packets. This makes $Q_{n,k}$ large over time, and after some point no packets are transmitted to that device for the processing task. In Fig.~\ref{fig:Rate_vs_time_results}(c), when the battery level of $R_1$ reduces below 40\%, then it stops receiving packets for processing. If there is no cooperation, then the rate towards $R_1$ reduces to 0. On the other hand, with EaCC, the rate is still higher than 0 thanks to having helper. The helper device with larger energy level (for the sake of this experiment), receives packets from the source, process them, and forwards them to $R_1$, which receives already processed data. After 40\% threshold, both EaCC and no-cooperation improve, because $R_1$ starts processing packets. This result shows the importance of energy-awareness in our cooperative computation setup.

Now, we consider the effect of the number of helpers to overall rate performance. In particular, we develop a setup shown in Fig.~\ref{fig:Rate_vs_helpers_one_receiver_results}(a), where there is one source, one receiver, and varying number of helpers. In this setup, the source device, receiver, and the first two helper devices are Nexus 5 smartphones, while the other helpers are Nexus 7 tablets. Fig.~\ref{fig:Rate_vs_helpers_one_receiver_results}(b) shows the average rate (averaged over 10 seeds) when EaCC is employed versus the number of helpers for different computational complexities such as $O(1)$, $O(n)$, and $O(n^2)$, where the processing task is counting the number of bytes in a packet. As expected, when complexity increases, the rate decreases. More interestingly, the increasing number of helpers increases the rates of all complexity levels. There are two reasons for this behavior. First, even if complexity level is low, {\em e.g., } $O(1)$, processing power is still a bottleneck, and it can be solved by increasing the number of helpers. Note that after the number of helpers exceeds a value, the achievable rates saturate, which means that processing power is not a bottleneck anymore, but bandwidth is. The second reason is that receiving data over multiple interfaces increases diversity. In other words, when the channel condition over one interface ({\em e.g., } between source and the mobile device) degrades, the other interface ({\em e.g., } between two mobile devices) can still have a better channel condition.

In order to understand the real impact of processing power in a cooperative system, we tested both EaCC and cooperation (without computation and energy control) in the setup shown in Fig.~\ref{fig:Rate_vs_helpers_one_receiver_results}(a). The results are provided in Fig.~\ref{fig:Rate_vs_helpers_one_receiver_results}(c) when the complexity is $O(n^2)$. As can be seen, while EaCC significantly increases the rate with increasing number of helpers, cooperation slightly increases the rate (due to diversity). The improvement of EaCC over cooperation is as high as 83\%, which is significant.

\begin{figure*}[t!]
\centering
\vspace{-5pt}
\subfigure[System Model]{ {\includegraphics[height = 32mm]{multiple_helper_two_receiver.eps}} }
\subfigure[Rate at $R_1$ vs. Number of Helpers]{ {\includegraphics[height = 32mm]{Receiver1NumberOfHelpersVSRate_v2.eps}} }
\subfigure[Rate at $R_2$ vs. Number of Helpers]{ {\includegraphics[height = 32mm]{Receiver2NumberOfHelpersVSRate_v2.eps}} }
\vspace{-5pt}
\caption{(a) System model consisting of a source device, two receivers, and multiple helpers. Wi-Fi is used between the source and the receiver devices ($R_1$, $R_2$) and the helper devices ($H_1, \ldots$), while Wi-Fi Direct is used to connect the receiver devices with the helper devices. (b) EaCC: Average rate measured at receiver $R_1$ versus the number of helpers. (c)  EaCC: Average rate measured at receiver $R_2$ versus the number of helpers.}
\vspace{-15pt}
\label{fig:Rate_vs_helpers_two_receiver_results}
\end{figure*}

Finally, we consider a scenario that there are multiple receivers interested in different files. Fig.~\ref{fig:Rate_vs_helpers_two_receiver_results}(a) shows the system model with one source, two receivers, and multiple helpers. In this setup, the source, two receivers, and the first helper is Android based Nexus 5 smartphone, while the rest of the helpers are Nexus 7 tablets. Fig.~\ref{fig:Rate_vs_helpers_two_receiver_results}(b) and (c) show the average rate (averaged over 10 seeds) measured at $R_1$ and $R_2$ when EaCC is employed with respect to the increasing number of helpers, respectively. Similar to previous setups, $O(1)$, $O(n)$, and $O(n^2)$ correspond to different computational complexities, where the processing task is counting the number of bytes in a packet. As can be seen, the measured rate at both $R_1$ and $R_2$ increases with increasing number of helpers. This shows that our EaCC algorithm successfully accommodates multiple flows and receivers.

\vspace{-5pt}
\section{\label{sec:conclusion}Conclusion}
\vspace{-5pt}
We considered that a group of cooperative mobile devices, within proximity of each other, (i) use their cellular or Wi-Fi (802.11) links as their primary networking interfaces, and (ii) exploit their D2D connections (Wi-Fi Direct) for cooperative computation. We showed that if mobile devices cooperate to utilize their aggregate processing power, it significantly improves transmission rates. Thus, for this scenario, we developed an {\em energy-aware cooperative computation} framework to effectively utilize processing power and energy. This framework provides a set of algorithms including flow, computation and energy controls as well as cooperation and scheduling. We implemented these algorithms in a testbed which consists of real mobile devices. The experiments in the testbed show that our {\em energy-aware cooperative computation} framework brings significant performance benefits.

\bibliographystyle{IEEEtran}


\section{Setting and main results}
\label{sec:intro}

A neural network is a model of real-valued computation defined by a connected directed graph as follows.
Nodes await real numbers on their incoming edges,
thereafter computing a function of these reals and transmitting it along their outgoing edges.
Root nodes apply their computation to a vector provided as input to the network,
whereas internal nodes apply their computation to the output of other nodes.
Different nodes may compute different functions, two common choices being
the maximization gate $v\mapsto \max_i v_i$ (where $v$ is the vector of values on incoming edges),
and the \emph{standard ReLU gate} $v\mapsto \sigma_{\textsc{r}}(\ip{a}{v} + b)$
where $\sigma_{\textsc{r}}(z) := \max\{0,z\}$ is called the ReLU
(rectified linear unit), and the parameters $a$ and $b$ may vary from node to node.
Graphs in the present work are acyclic,
and there is exactly one node with no outgoing edges
whose computation is the output of the network.

Neural networks distinguish themselves from many other function classes used in machine learning by
possessing multiple \emph{layers}, meaning the output is the result of composing together an arbitrary
number of (potentially complicated) nonlinear operations;
by contrast, the functions computed by boosted decision stumps and SVMs can be written
as neural networks with a constant number of layers.

The purpose of the present work is to show that standard types of networks always gain in representation
power with the addition of layers.
Concretely: it is shown that for every positive integer $k$,
there exist neural networks
with $\Theta(k^3)$ layers,
$\Theta(1)$ nodes per layer,
and $\Theta(1)$ distinct parameters
which can not be approximated by networks with $\cO(k)$ layers
and $o(2^k)$ nodes.

\subsection{Main result}
\label{sec:intro:main}

Before stating the main result, a few choices and pieces of notation deserve explanation.
First, the target many-layered function uses standard ReLU gates;
this is by no means necessary, and a more general statement can be found in \Cref{fact:main:gen}.
Secondly, the notion of approximation is the $L^1$ distance: given two functions $f$ and $g$,
their pointwise disagreement $|f(x) - g(x)|$ is averaged over the cube $[0,1]^d$.
Here as well, the same proofs allow flexibility (cf. \Cref{fact:main:gen}).
Lastly, the shallower networks used for approximation use \emph{semi-algebraic gates},
which generalize the earlier maximization and standard ReLU gates,
and allow for analysis of not just standard networks with ReLU gates,
but convolutional networks with ReLU and maximization gates \citep{imagenet_sutskever},
sum-product networks (where nodes compute polynomials) \citep{poon_domingos_spn},
and boosted decision trees;
the full definition of semi-algebraic gates appears in \Cref{sec:sa}.

\begin{theorem}  \label{fact:main}
  Let any integer $k \geq 1$ and any dimension $d\geq 1$ be given.
  There exists $f:\mathbb R^d \to \mathbb R$ computed by a neural network with standard ReLU gates
  in $2k^3+8$ layers, $3k^3 + 12$ total nodes, and $4+d$ distinct parameters
  so that
  \[
    \inf_{g \in \cC} \int_{[0,1]^d} |f(x)-g(x)|dx \geq \frac 1 {64},
  \]
  where $\cC$ is the union of the following two sets of functions.
  \begin{itemize}
    \item
      Functions computed by networks of $(t,\alpha,\beta)$-semi-algebraic gates
      in $\leq k$ layers and $\leq 2^{k}/(t\alpha\beta)$ nodes.
      (E.g., as with standard ReLU networks
      or with convolutional neural networks with standard ReLU and maximization gates; cf. \Cref{sec:sa}.)
    \item
      Functions
      computed by linear combinations of $\leq t$ decision trees
      each with $\leq 2^{k^3}/t$ nodes.
      (E.g., the function class used by boosted decision trees;
      cf. \Cref{sec:sa}.)
  \end{itemize}
\end{theorem}

Analogs to \Cref{fact:main} for boolean circuits --- which have boolean inputs
routed through $\{\textup{and},\textup{or},\textup{not}\}$ gates --- have been studied extensively
by the circuit complexity community, where they are called \emph{depth hierarchy theorems}.
The seminal result, due to \citet{hastad_thesis}, establishes the inapproximability
of the parity function by shallow circuits (unless their size is exponential).
Standard neural networks appear to have received less study;
closest to the present work is an investigation by
\citet{ohad_nn_apx} analyzing the case $k=2$ when the dimension $d$ is large,
showing an exponential separation between 2- and 3-layer networks, a regime not handled by \Cref{fact:main}.
Further bibliographic notes and open problems may be found in \Cref{sec:bib}.

The proof of \Cref{fact:main} (and of the more general \Cref{fact:main:gen}) occupies \Cref{sec:apx}.
The key idea is that just a few function compositions (layers) suffice to construct a highly oscillatory function,
whereas function addition (adding nodes but keeping depth fixed) gives a function with few oscillations.
Thereafter, an elementary counting argument suffices to show that low-oscillation functions can not approximate
high-oscillation functions.

\subsection{Companion results}
\label{sec:intro:companion}

\Cref{fact:main} only provides the existence of \emph{one}
network (for each $k$) which can not be approximated by
a network with many fewer layers.  It is natural to wonder if there are \emph{many} such
special functions.  The following bound indicates their population is in fact quite modest.

Specifically, the construction behind \Cref{fact:main}, as elaborated in \Cref{fact:main:gen},
can be seen as exhibiting $\cO(2^{k^3})$ points, and a fixed labeling of these points, upon which a shallow network hardly improves
upon random guessing.  The forthcoming \Cref{fact:sa_fit_few} similarly shows that even on the more simpler task of fitting $\cO(k^9)$ points,
the earlier class of networks is useless on most random labellings.

In order to state the result, a few more definitions are in order.
Firstly, for this result, the notion of neural network is more restrictive.
Let a \emph{neural net graph $\mathfrak G$} denote not only the graph structure (nodes and edges),
but also an assignment of gate functions to nodes, of edges to the inputs of gates,
and an assignment of free parameters $w\in\mathbb R^p$ to the parameters of the gates.
Let $\cN(\mathfrak G)$ denote the class of functions obtained by varying the free parameters;
this definition is fairly standard, and is discussed in more detail in \Cref{sec:sa}.
As a final piece of notation, given a function $f:\mathbb R^d\to\mathbb R$, let $\tilde f : \mathbb R^d \to \{0,1\}$ denote
the corresponding classifier $\tilde f(x) := \mathbf 1[f(x) \geq 1/2]$.

\begin{theorem}
  \label{fact:sa_fit_few}
  Let any neural net graph $\mathfrak G$ be given with $\leq p$ parameters in $\leq l$ layers and $\leq m$ total
  $(t,\alpha,\beta)$-semi-algebraic nodes.
  Then for any $\delta > 0$
  and any
  $n \geq 8pl^2 \ln(8emt \alpha\beta p(l+1)) + 4\ln(1/\delta)$ points $(x_i)_{i=1}^n$,
  with probability $\geq 1-\delta$ over uniform random labels $(y_i)_{i=1}^n$,
  \[
    \inf_{f\in\cN(\mathfrak G)}  \frac 1 n \sum_{i=1}^n \mathbf 1[\tilde f(x_i) \neq y_i]
    \geq \frac 1 4.
  \]
\end{theorem}

This proof is a direct corollary of the VC dimension of semi-algebraic networks,
which in turn can be proved by a small modification of the VC dimension proof for
piecewise polynomial networks \citep[Theorem 8.8]{anthony_bartlett_nn}.
Moreover, the core methodology for VC
dimension bounds of neural networks is due to \citeauthor{warren},
whose goal was an analog of \Cref{fact:sa_fit_few} for polynomials \citep[Theorem 7]{warren}.

\ifarxiv
\begin{lemma}[name={Simplification of \Cref{fact:pp_vc}}]
\else
\begin{lemma}[Simplification of \Cref{fact:pp_vc}]
\fi
  \label[lemma]{fact:vc_sa}
  Let any neural net graph $\mathfrak G$ be given with $\leq p$ parameters in $\leq l$ layers and $\leq m$ total nodes,
  each of which is $(t,\alpha,\beta)$-semi-algebraic.
  Then
  \[
    \textup{VC}(\cN(\mathfrak G)) \leq
    6p(l+1)\big(
      \ln(2p(l+1)) + \ln(8emt\alpha) + l\ln(\beta)
    \big).
  \]
\end{lemma}

The proof of \Cref{fact:sa_fit_few} and \Cref{fact:vc_sa} may be found in \Cref{sec:vc}.
The argument for the VC dimension is very close to the argument for \Cref{fact:main}
that a network with few layers has few oscillations; see \Cref{sec:vc} for further discussion
of this relationship.

\section{Semi-algebraic gates and assorted network notation}
\label{sec:sa}

The definition of a semi-algebraic gate is unfortunately complicated;
it is designed to capture a few standard nodes in a single abstraction
without degrading the bounds.
Note that the name \emph{semi-algebraic set} is standard \citep[Definition 2.1.4]{bochnak_coste_roy},
and refers to a set defined by unions and intersections of polynomial inequalities
(and thus the name is somewhat abused here).

\begin{definition}
  A function $f:\mathbb R^k\to\mathbb R$ is \emph{$(t,\alpha,\beta)$-sa ($(t,\alpha,\beta)$-semi-algebraic)}
  if there exist $t$ polynomials $(q_i)_{i=1}^t$ of degree $\leq\alpha$,
  and $m$ triples $(U_j,L_j,p_j)_{j=1}^m$ where $U_j$ and $L_j$ are subsets
  of $[t]$ (where $[t] := \{1,\ldots,t\}$) and $p_j$ is a polynomial of degree $\leq\beta$, such that
  \[
    f(v) = \sum_{j=1}^m p_j(v)
    \left(\prod_{i \in L_j} \mathbf 1[q_i(v) < 0]\right)
    \left(\prod_{i \in U_j} \mathbf 1[q_i(v) \geq 0]\right).
  \]
\end{definition}

A notable trait of the definition is that the number of terms $m$ does not need to enter
the name as it does not affect any of the complexity estimates herein (e.g., \Cref{fact:main} or \Cref{fact:sa_fit_few}).

Distinguished special cases of semi-algebraic gates are as follows in \Cref{fact:sa:ex}.
The standard piecewise polynomial gates generalize the ReLU and have received a fair bit of attention
in the theoretical community \citep[Chapter 8]{anthony_bartlett_nn};
here a function $\sigma:\mathbb R\to\mathbb R$ is \emph{$(t,\alpha)$-poly}
if $\mathbb R$ can be partitioned into $\leq t$ intervals
so that $\sigma$ is a polynomial of degree $\leq \alpha$ within each piece.
The maximization and minimization gates have become popular due to their use in convolutional
networks \citep{imagenet_sutskever}, which will be discussed more in \Cref{sec:sa:nn}.
Lastly, decision trees and boosted decision trees are practically successful classes usually viewed as competitors
to neural networks \citep{caruana_empirical}, and have the following structure.

\begin{definition}
  A \emph{$k$-dt (decision tree with $k$ nodes)} is defined recursively as follows.
  If $k=1$, it is a constant function.
  If $k > 1$, it first evaluates $x\mapsto \mathbf 1[\ip{a}{x} - b \geq 0]$,
  and thereafter conditionally evaluates either
  a left $l$-dt or a right $r$-dt where $l+r<k$.
  A \emph{$(t,k)$-bdt} (boosted decision tree)
  evaluates $x\mapsto \sum_{i=1}^t c_i g_i(x)$ where each $c_i\in \mathbb R$ and each $g_i$ is a $k$-dt.
\end{definition}

\begin{lemma}[Example semi-algebraic gates]
  \label[lemma]{fact:sa:ex}
  \begin{enumerate}
    \item
      If $\sigma :\mathbb R\to\mathbb R$ is $(t,\beta)$-poly and $q:\mathbb R^d\to\mathbb R$ is a polynomial of degree $\alpha$,
      then the standard piecewise polynomial gate $\sigma\circ q$ is $(t,\alpha,\alpha\beta)$-sa.
      In particular, the standard ReLU gate $v\mapsto \sigma_{\textsc{r}}(\ip{a}{v} + b)$ is $(1,1,1)$-sa.
    \item
      Given polynomials $(p_i)_{i=1}^r$ of degree $\leq\alpha$,
      the standard $(r,\alpha)$-min and -max gates $\phi_{\min}(v) := \min_{i\in[r]} p_i(v)$
      and $\phi_{\max}(v) := \max_{i\in[r]} q_i(v)$
      are $(r(r-1), \alpha, \alpha)$-sa.
    \item
      Every $k$-dt is $(k,1,0)$-sa,
      and every $(t,k)$-bdt is $(tk,1,0)$.
  \end{enumerate}
\end{lemma}
The proof of \Cref{fact:sa:ex} is mostly a matter of unwrapping definitions, and is deferred to
\Cref{sec:proofs}.
Perhaps the only interesting encoding is for the maximization gate (and similarly the minimization gate),
which uses $\max_{i} v_i = \sum_i v_i (\prod_{j < i} \mathbf 1[v_i > v_j])(\prod_{j > i} \mathbf 1[v_i \geq v_j])$.

\subsection{Notation for neural networks}
\label{sec:sa:nn}

A semi-algebraic gate is simply a function from some domain to $\mathbb R$,
but its role in a neural network is more complicated as the domain of the function must be
partitioned into arguments of three types: the input $x\in\mathbb R^d$ to the network, the parameter vector $w\in\mathbb R^p$,
and a vector of real numbers coming from parent nodes.

As a convention, the input $x\in\mathbb R^d$ is only accessed by the root nodes (otherwise ``layer'' has no meaning).
For convenience, let layer 0 denote the input itself: $d$ nodes where node $i$ is the map $x\mapsto x_i$.
The parameter vector $w\in\mathbb R^p$ will be made available to all nodes in layers above 0, though they might only
use a subset of it.  Specifically,
an internal node computes a function $f:\mathbb R^p\times\mathbb R^d \to \mathbb R$ using parents $(f_1,\ldots,f_k)$
and a semi-algebraic gate $\phi : \mathbb R^p \times \mathbb R^k \to \mathbb R$, meaning
$f(w,x) := \phi(w_1,\ldots,w_p, f_1(w,x), \ldots, f_k(w,x))$.
Another common practice is to have nodes apply a univariate \emph{activation function} to
an affine mapping of their parents (as with piecewise polynomial gates in \Cref{fact:sa:ex}),
where the weights in the affine combination are the parameters to the network, and additionally
correspond to edges in the graph.
It is permitted for the same parameter to appear multiple times in a network, which explains how
the number of parameters in \Cref{fact:main} can be less than the number of edges and nodes.
The entire network computes some function $F_\mathfrak G:\mathbb R^p\times\mathbb R^d\to \mathbb R$, which is equivalent to the
function computed by the single node with no outgoing edges.

As stated previously, $\mathfrak G$ will denote not just the graph (nodes and edges) underlying a network,
but also an assignment of gates to nodes, and how parameters and parent outputs are plugged into
the gates (i.e., in the preceding paragraph, how to write $f$ via $\phi$).
$\cN(\mathfrak G)$ is the set of functions obtained by varying $w\in\mathbb R^p$,
and thus $\cN(\mathfrak G) := \{ F_\mathfrak G(w,\cdot) : w\in\mathbb R^p\}$ where $F_\mathfrak G$ is the function defined as above,
corresponding to computation performed by $\mathfrak G$.
The results related to VC dimension, meaning \Cref{fact:sa_fit_few} and \Cref{fact:vc_sa},
will use the class $\cN(\mathfrak G)$.

Some of the results, for instance \Cref{fact:main} and its generalization \Cref{fact:main:gen},
will let not only the parameters but also network graph $\mathfrak G$ vary.
Let $\cN_d((m_i, t_i,\alpha_i,\beta_i)_{i=1}^l)$ denote a network where layer $i$ has $\leq m_i$ nodes
where each is $(t_i,\alpha_i,\beta_i)$-sa and the input has dimension $d$.
As a simplification, let $\cN_d(m,l, t,\alpha,\beta)$ denote networks of $(t,\alpha,\beta)$-sa gates in $\leq l$ layers (not including layer 0)
each with $\leq m$ nodes.
There are various empirical prescriptions on how to vary the number of nodes per layer;
for instance, convolutional networks typically have an increase between layer 0 and layer 1,
followed by exponential decrease for a few layers, and finally a few layers with the same number of nodes
\citep{fukushima_convnet,lecun_convnet,imagenet_sutskever}.

\section{Benefits of depth}
\label{sec:apx}

The purpose of this section is to prove \Cref{fact:main} and its generalization \Cref{fact:main:gen}
in the following three steps.

\begin{enumerate}
  \item
    Functions with few oscillations poorly approximate functions with many oscillations.

  \item
    Functions computed by networks with few layers must have few oscillations.

  \item
    Functions computed by networks with many layers can have many oscillations.
\end{enumerate}

\subsection{Approximation via oscillation counting}

\begin{wrapfigure}{R}{0.4\textwidth}
  \vspace{-8pt}

  \includegraphics[width=0.4\textwidth]{repr_1_d}

  \vspace{0pt}

    \caption{$f$ crosses more than $g$.}
  \label{fig:apx:1}
  \vspace{-8pt}
\end{wrapfigure}
The idea behind this first step is depicted at right.
Given functions $f:\mathbb R\to\mathbb R$ and $g:\mathbb R\to\mathbb R$ (the multivariate case will come soon),
let $\cI_f$ and $\cI_g$ denote partitions of $\mathbb R$ into intervals so
that the classifiers $\tilde f(x) =\mathbf 1[f(x)\geq 1/2]$ and $\tilde g$ are constant
within each interval.
To formally count oscillations, define
\emph{the crossing number $\textup{Cr}(f)$ of $f$} as $\textup{Cr}(f) = |\cI_f|$ (thus $\textup{Cr}(\sigma_{\textsc{r}}) = 2$).
If $\textup{Cr}(f)$ is much larger than $\textup{Cr}(g)$,
then most piecewise constant regions of $\tilde g$ will exhibit many oscillations of $f$,
and thus $g$ poorly approximates $f$.

\begin{lemma}
  \label[lemma]{fact:mono:crossing_lb:2}
  Let $f:\mathbb R\to\mathbb R$ and $g:\mathbb R\to\mathbb R$ be given,
  and take $\cI_f$ to denote the partition of $\mathbb R$ given by the pieces of $\tilde f$
  (meaning $|\cI_f| = \textup{Cr}(f)$).
  Then
  \[
    \frac 1 {\textup{Cr}(f)} \sum_{U \in \cI_f} \mathbf 1[\forall x \in U \centerdot \tilde f(x) \neq \tilde g(x) ]
    \geq \frac 1 2\left(1 - 2 \left(\frac {\textup{Cr}(g)}{\textup{Cr}(f)}\right)\right).
  \]
\end{lemma}

The arguably strange form of the left hand side of the bound in
\Cref{fact:mono:crossing_lb:2} is to accommodate different notions of distance.
For the $L^1$ distance with the Lebesgue measure as in \Cref{fact:main},
it does not suffice for $f$ to cross 1/2: it must be \emph{regular},
meaning
it must cross by an appreciable distance, and the crossings must be evenly spaced.
(It is worth highlighting that the ReLU easily gives rise to a regular $f$.)
However, to merely show that $f$ and $g$ give very different classifiers $\tilde f$ and $\tilde g$
over an arbitrary measure (as in part of \Cref{fact:main:gen}), no additional regularity is needed.

\begin{proofof}{\Cref{fact:mono:crossing_lb:2}}
  Let $\cI_f$ and $\cI_g$ respectively denote the sets of intervals
  corresponding to $\tilde f$ and $\tilde g$,
  and set $s_f := \textup{Cr}(f) = |\cI_f|$ and $s_g := \textup{Cr}(g) = |\cI_g|$.

  For every $J\in \cI_g$, set $X_J := \{ U \in \cI_f : U \subseteq J \}$.
  Fixing any $J\in \cI_g$,
  since $\tilde g$ is constant on $J$ whereas $\tilde f$ alternates,
  the number of elements in $X_J$ where $\tilde g$ disagrees everywhere with $\tilde f$
  is $|X_J|/2$ when $|X_J|$ is even
  and at least $(|X_J|-1)/2$ when $|X_J|$ is odd,
  thus at least $(|X_J|-1)/2$ in general.
  As such,
  \begin{align}
    \frac 1 {s_f} \sum_{U \in \cI_f} \mathbf 1[\forall x \in U \centerdot \tilde f(x) \neq \tilde g(x) ]
    &
    \geq
    \frac 1 {s_f} \sum_{J \in \cI_{g}} \sum_{U \in X_J}
    \mathbf 1[\forall x \in U \centerdot \tilde f(x) \neq \tilde g(x) ]
   \geq
    \frac 1 {s_f} \sum_{J \in \cI_{g}} \frac {|X_J| - 1} {2}\label{eq:crossing_lb:1}.
  \end{align}
  To control this expression, note that every $X_J$ is disjoint, however $X:=\cup_{J\in\cI_j} X_j$
  can be smaller than $\cI_f$: in particular, it misses intervals $U\in \cI_f$
  whose interior intersects with the boundary of an interval in $\cI_g$.
  Since there are at most $s_g-1$ such boundaries,
  \[
    s_f = |\cI_f| \leq s_g - 1 + |X| \leq s_g + \sum_{J\in\cI_g} |X_J|,
  \]
  which rearranges to gives $\sum_{J\in\cI_g} |X_J| \geq s_f - s_g$.
  Combining this with \cref{eq:crossing_lb:1},
  \[
    \frac 1 {s_f} \sum_{U \in \cI_f} \mathbf 1[\forall x \in U \centerdot \tilde f(x) \neq \tilde g(x) ]
    \geq \frac {1}{2s_f}\left( s_f - s_g - s_g \right)
    = \frac 1 2 \left(1 - \frac {2s_g}{s_f}\right).
  \]
\end{proofof}

\subsection{Few layers, few oscillations}
\label{sec:apx:lb}

As in the preceding section, oscillations of a function $f$ will be counted via the crossing number $\textup{Cr}(f)$.
Since $\textup{Cr}(\cdot)$ only handles univariate functions, the multivariate case is handled by first choosing an affine
map $h : \mathbb R\to\mathbb R^d$ (meaning $h(z) = az + b$) and considering $\textup{Cr}(f\circ h)$.

Before giving the central upper bounds and sketching their proofs, notice by analogy to polynomials how
compositions and additions vary in their impact upon oscillations.  By adding together two polynomials,
the resulting polynomial has at most twice as many terms and does not exceed the maximum degree of either polynomial.
On the other hand, composing polynomials, the result has the product of the degrees and can have more than the product
of the terms.  As both of these can impact the number of
roots or crossings (e.g., by the Bezout Theorem or Descartes' Rule of Signs),
composition wins the race to higher oscillations.

\begin{lemma}
  \label[lemma]{fact:sa_crossing}
  Let $h:\mathbb R\to\mathbb R^d$ be affine.
  \begin{enumerate}
    \item
      Suppose $f \in \cN_d((m_i,t_i,\alpha_i,\beta_i)_{i=1}^l)$
      with $\min_i\min\{\alpha_i,\beta_i\} \geq 1$.
                      Setting $\alpha := \max_i \alpha_i, \beta := \max_i \beta_i$, $t := \max_i t_i$,
      $m := \sum_i m_i$, then
            $\textup{Cr}(f\circ h) \leq 2(2tm\alpha/l)^l \beta^{l^2}$.
    \item
            Let $k$-dt $f:\mathbb R^d\to\mathbb R$ and $(t,k)$-bdt $g:\mathbb R^d\to\mathbb R$ be given.             Then $\textup{Cr}(f\circ h)\leq k$ and $\textup{Cr}(g\circ h) \leq 2tk$.
  \end{enumerate}
\end{lemma}

\Cref{fact:sa_crossing} shows the key tradeoff: the number of layers is in the exponent,
while the number of nodes is in the base.

Rather than directly controlling $\textup{Cr}(f\circ h)$, the proofs will first show $f\circ h$ is $(t,\alpha)$-poly,
which immediately bounds $\textup{Cr}(f\circ h)$ as follows.
\begin{lemma}
  \label[lemma]{fact:poly_cr}
  If $f:\mathbb R\to\mathbb R$ is $(t,\alpha)$-poly,
  then $\textup{Cr}(f) \leq t(1+\alpha)$.
\end{lemma}
\begin{proof}
  The polynomial in each piece has at most $\alpha$ roots,
  which thus divides each piece into $\leq 1+\alpha$ further pieces
  within which $\tilde f$ is constant.
\end{proof}

A second technical lemma is needed to reason about combinations
of partitions defined by $(t,\alpha,\beta)$-sa and $(t,\alpha)$-poly functions.

\begin{lemma}
  \label[lemma]{fact:partition_combination}
  Let $k$ partitions $(A_i)_{i=1}^k$ of $\mathbb R$ each into at most $t$ intervals be given,
  and set $A := \cup_i A_i$.
  Then there exists a partition $B$ of $\mathbb R$ of size at most $kt$
  so that every interval expressible as a union of intersections of elements of $A$
  is a union of elements of $B$.
\end{lemma}

\begin{wrapfigure}{R}{0.3\textwidth}
  \vspace{-8pt}

  \includegraphics[width=0.3\textwidth]{partitions}

  \vspace{0pt}

  \caption{Three partitions.}
  \label{fig:partition:counting}
  \vspace{-8pt}
\end{wrapfigure}
The proof is somewhat painful owing to the fact that there is no convention on the structure
of the intervals in the partitions, namely which ends are closed and which are open,
and is thus deferred to \Cref{sec:proofs}.
The principle of the proof is elementary, and is depicted at right:
given a collection of partitions, an intersection of constituent intervals must share endpoints
with intervals in in the intersection, thus the total number of intervals bounds the total number
of possible intersections.
Arguably, this failure to increase complexity in the face of arbitrary intersections
is why semi-algebraic gates do not care about the number of terms in their definition.

Recall that $(t,\alpha,\beta)$-sa means there is a set of $t$ polynomials of degree at most $\alpha$
which form the regions defining the function by intersecting simpler regions
$x\mapsto \mathbf 1[q(x) \geq 0]$ and $x\mapsto \mathbf 1[q(x) < 0]$.
As such, in order to analyze semi-algebraic gates composed with piecewise polynomial gates,
consider first the behavior of these predicate polynomials.

\begin{lemma}
  \label[lemma]{fact:poly_circ_pp}
  Suppose $f:\mathbb R^k\to\mathbb R$ is polynomial with degree $\leq\alpha$
  and $(g_i)_{i=1}^k$ are each $(t,\gamma)$-poly.
  Then $h(x) := f(g_1(x),\ldots,g_k(x))$ is $(tk,\alpha\gamma)$-poly,
  and the partition defining $h$ is a refinement of the partitions for each $g_i$
  (in particular, each $g_i$ is a fixed polynomial (of degree $\leq\gamma$)
  within the $\leq tk$ pieces defining $h$).
\end{lemma}
\begin{proof}
  By \Cref{fact:partition_combination},
  there exists a partition of $\mathbb R$ into $\leq tk$ intervals
  which refines the partitions defining each $g_i$.
  Since $f$ is a polynomial with degree $\leq \alpha$,
  then within each of these intervals, its composition with $(g_1,\ldots,g_k)$
  gives a polynomial of degree $\leq \alpha\gamma$.
  \end{proof}

This gives the following complexity bound for composing $(s,\alpha,\beta)$-sa and $(t,\gamma)$-poly gates.

\begin{lemma}
  \label[lemma]{fact:sa_to_poly}
  Suppose $f : \mathbb R^k\to\mathbb R$ is $(s,\alpha,\beta)$-sa
  and $(g_1,\ldots,g_k)$ are $(t,\gamma)$-poly.
  Then $h(x) := f(g_1(x),\ldots,g_k(x))$ is $(stk(1 +  \alpha\gamma), \beta\gamma)$-poly.
\end{lemma}
\begin{proof}
  By definition, $f$ is polynomial in regions defined by intersections of the predicates
  $U_i(x) = \mathbf 1[q_i(x) \geq 0]$ and $L_i(x) = \mathbf 1[q_i(x) < 0]$.
  By \Cref{fact:poly_circ_pp}, $q_i(g_1,\ldots,g_k)$ is $(tk,\alpha\gamma)$-poly,
  thus $U_i$ and $L_i$ together define a partition of $\mathbb R$ which has $\textup{Cr}(x\mapsto q_i(g_1(x),\ldots,g_k(x)))$
  pieces, which by \Cref{fact:poly_cr} has cardinality at most $tk(1 + \alpha\gamma)$
  and refines the partitions for each $g_i$.
  By \Cref{fact:partition_combination}, these partitions across all predicate polynomials $(q_i)_{i=1}^s$
  can be refined into a single partition of size
  $\leq stk(1 + \alpha\gamma)$,
  and which thus also refines the partitions defined by $(g_1,\ldots,g_k)$.
  Thanks to these refinements, $h$ over any element $U$ of this final partition
  is a fixed polynomial $p_U(g_1,\ldots,g_k)$ of degree $\leq\beta\gamma$,
  meaning $h$ is $(stk(1 + \alpha\gamma), \beta\gamma)$-poly.
\end{proof}

The proof of \Cref{fact:sa_crossing} now follows by \Cref{fact:sa_to_poly}.
In particular, for semi-algebraic networks, the proof is an induction over layers,
establishing node $j$ is $(t_j,\alpha_j)$-poly (for appropriate $(t_j,\alpha_j)$).

\subsection{Many layers, many oscillations}
\label{sec:triangle}

The idea behind this construction is as follows.  Consider any continuous function $f:[0,1]\to[0,1]$ which is a generalization of
a triangle wave with a single peak: $f(0) = f(1) = 0$,
and there is some $a\in(0,1)$ with $f(a) = 1$, and additionally $f$ strictly increases along $[0,a]$ and strictly decreases along
$[a,1]$.

Now consider the effect of the composition $f\circ f = f^2$. Along $[0,a]$, this is a stretched copy of $f$, since $f(f(a)) = f(1) = 0 = f(0) = f(f(0))$
and moreover $f$ is a bijection between $[0,a]$ and $[0,1]$ (when restricted to $[0,a]$).  The same reasoning applies to $f^2$ along $[a,1]$,
meaning $f^2$ is a function with two peaks.  Iterating this argument implies $f^{k}$ is a function with $2^{k-1}$ peaks; the following
definition and lemmas formalize this reasoning.

\begin{definition}
  $f$ is \emph{$(t,[a,b])$-triangle} when it is continuous along $[a,b]$, and $[a,b]$ may
  be divided into $2t$ intervals $[a_i, a_{i+1}]$ with $a_1 = a$ and $a_{2t+1}=b$,
  $f(a_i) = f(a_{i+2})$ whenever $1 \leq i \leq 2t-1$,
  $f(a_1) = 0$,
  $f(a_2) = 1$,
  $f$ is strictly increasing along odd-numbered intervals (those starting from $a_i$ with $i$ odd),
  and strictly decreasing along even-numbered intervals.
\end{definition}

\begin{lemma}
  \label[lemma]{fact:mono:gen:ub:1}
  If $f$ is $(s,[0,1])$-triangle and $g$ is $(t,[0,1])$-triangle,
  then $f\circ g$ is $(2st, [0,1])$-triangle.
\end{lemma}
\begin{proof}
  \deff_{[a,b]}{f_{[a,b]}}
  Since $g([0,1]) = [0,1]$ and $f$ and $g$ are continuous along $[0,1]$,
  then $f\circ g$ is continuous along $[0,1]$.
  In the remaining analysis,
  let $(a_1,\ldots,a_{2s+1})$ and $(c_1,\ldots,c_{2t+1})$
  respectively denote the interval boundaries for $f$ and $g$.

  Now consider any interval $[c_j, c_{j+1}]$ where $j$ is odd,
  meaning the restriction $g_j : [c_j, c_{j+1}]\to [0,1]$ of $g$ to $[c_j, c_{j+1}]$ is strictly increasing.
  It will be shown that $f\circ g_j$ is $(s,[c_j,c_{j+1}])$-triangle,
  and an analogous proof holds for the strictly decreasing restriction
  $g_{j+1} : [c_{j+1}, c_{j+2}] \to [0,1]$,
  whereby it follows that $f\circ g$ is $(2st,[0,1])$ by considering all choices of $j$.

  To this end, note for any $i \in \{1,\ldots, 2s+1\}$ that $g_{j}^{-1}(a_i)$ exists and is unique,
  thus set $a'_i := g_j^{-1}(a_i)$.
  By this choice,
  for odd $i$ it holds that $f(g_j(a'_i)) = f(g_j(g_j^{-1}(a_i))) = f(a_i) = f(a_1) = 0$
  and $f\circ g_j$ is strictly increasing
  along $[a'_i, a'_{i+1}]$ (since $g_j$ is strictly increasing everywhere
  and $f$ is strictly increasing along $[g_j(a'_i), g_j(a'_{i+1})] = [a_i, a_{i+1}]$),
  and similarly even $i$ has $f(g_j(a'_i)) = f(a_2) = 1$
  and $f\circ g_j$ is strictly decreasing along $[a'_i, a'_{i+1}]$.
\end{proof}

\begin{corollary}
  \label[corollary]{fact:mono:gen:ub:2}
  If $f\in \cN_1(m,l,t,\alpha,\beta)$ is $(t,[0,1])$-triangle with $p$ distinct parameters,
  then $f^k \in\cN_1(m,kl,t,\alpha,\beta)$ is $(2^{k-1}t^{k},[0,1])$-triangle with $p$ distinct parameters
  and $\textup{Cr}(f^k) = (2t)^k+1$.
\end{corollary}
\begin{proof}
  It suffices to perform $k-1$ applications of \Cref{fact:mono:gen:ub:1}.
\end{proof}

Next, note the following examples of triangle functions.

\begin{lemma}
  \label[lemma]{fact:triangles}
  The following functions are $(1,[0,1])$-triangle.
  \begin{enumerate}
    \item
      $f(z) := \sigma_{\textsc{r}}(2\sigma_{\textsc{r}}(z) - 4\sigma_{\textsc{r}}(z-1/2)) \in \cN_1(2,1, 1,1,1)$.

    \item
      $g(z) := \min\{ \sigma_{\textsc{r}}(2z), \sigma_{\textsc{r}}(2-2z) \} \in \cN_1(2,1, 2,1,1)$.
    \item
      $h(z) := 4z(1-z) \in \cN_1(1,1, 0, 2,0)$.
      Cf. \citet{schmitt_4x1x_nn}.
  \end{enumerate}
\end{lemma}

Lastly, consider the first example $f(z) = \sigma_{\textsc{r}}(2\sigma_{\textsc{r}}(z) - 4(\sigma_{\textsc{r}}(z-1/2))) = \min\{\sigma_{\textsc{r}}(2z), \sigma_{\textsc{r}}(2-2z)\}$,
whose graph linearly interpolates (in $\mathbb R^2$) between $(0,0)$, $(1/2,1)$, and $(1,0)$.
Consequently, $f\circ f$ along $[0,1/2]$ linear interpolates between $(0,0)$, $(1/4,1)$, and $(1/2,1)$, and
$f\circ f$ is analogous on $[1/2,1]$, meaning it has produced two copies of $f$ and then shrunken them horizontally
by a factor of 2.  This process repeats, meaning $f^k$ has $2^{k-1}$ copies of $f$, and grants the regularity
needed to use the Lebesgue measure in \Cref{fact:main}.

\begin{lemma}
  \label[lemma]{fact:triangle:relu:shape}
  Set $f(z) := \sigma_{\textsc{r}}(2\sigma_{\textsc{r}}(z) - 4\sigma_{\textsc{r}}(z-1/2)) \in \cN_1(2,1,1,1,1)$ (cf. \Cref{fact:triangles}).
  Let real $z \in [0,1]$ and positive integer $k$ be given,
  and choose the unique nonnegative integer $i_k \in \{0,\ldots,2^{k-1}\}$ and real $z_k \in [0, 1)$
  so that $z = (i_k + z_k)2^{1-k}$.
  Then
  \[
    f^k(z) = \begin{cases}
      2z_k
      &\textup{when $0 \leq z_k \leq 1/2$},
      \\
      2(1 - z_k)
      &\textup{when $1/2 < z_k < 1$}.
    \end{cases}
  \]
\end{lemma}

\subsection{Proof of \Cref{fact:main}}

The proof of \Cref{fact:main} now follows:
\Cref{fact:triangle:relu:shape} shows that a many-layered ReLU network can give rise to
a highly oscillatory and regular function $f^k$,
\Cref{fact:sa_crossing} shows that few-layered networks and (boosted) decision trees
give rise to functions with few oscillations,
and lastly \Cref{fact:mono:crossing_lb:2} shows how to combine these into an inapproximability result.

In this last piece, the proof averages over the possible offsets $y\in\mathbb R^{d-1}$ and considers univariate
problems after composing networks with the affine map $h_y(z) := (z,y)$.  In this way, the result
carries some resemblance to the random projection technique used in depth hierarchy theorems
for boolean functions \citep{hastad_thesis,rocco_apx},
as well as earlier techniques on complexities of multivariate sets \citep{vitushkin_1,vitushkin_2},
albeit in an extremely primitive form (considering variations along only one dimension).

\begin{proofof}{\Cref{fact:main}}
  Set $h(z) := \sigma_{\textsc{r}}(2\sigma_{\textsc{r}}(z) - 4\sigma_{\textsc{r}}(z-1/2))$ (cf. \Cref{fact:triangles}),
  and define $f_0(z) := h^{k^3+4}(z)$ and $f:\mathbb R^d\to\mathbb R$ as $f(x) = f_0(x_1)$.
  Let $\cI_f$ denote the pieces of $\tilde f_0$,
  meaning $|\cI_f| = \textup{Cr}(f_0)$,
  and \Cref{fact:mono:gen:ub:2} grants $\textup{Cr}(f_0) = 2^{k^3+4}+1$.
  Moreover, by \Cref{fact:triangle:relu:shape},
  for any $U\in \cI_f$, $f_0-1/2$ is a triangle with height 1/2
  and base either $2^{-k-1}$ (when $0\in U$ or $1\in U$)
  or $2^{-k}$, whereby
  $\int_U |f_0(x) - 1/2|dx \geq 2^{-k-1}/4 \geq |\cI_f|/16$
  (which has thus made use of the special regularity of $h$).

  Now for any $y\in\mathbb R^{d-1}$ define the map $p_y : \mathbb R\to\mathbb R^d$ as $p_y(z) := (z,y)$.
  If $g$ is a semi-algebraic network with $\leq k$ layers and $m\leq 2^k/(t\alpha\beta)$ total nodes,
  then \Cref{fact:sa_crossing} grants
  $\textup{Cr}(g\circ p_y) \leq 2 (2tm\alpha/k)^k \beta^{k^2} \leq 4(tm\alpha\beta)^{k^2} \leq 2^{k^3+2}$.
  Otherwise, $g$ is $(t,2^{k^3}/t)$-bdt,
  whereby \Cref{fact:sa_crossing} gives $\textup{Cr}(g\circ p_y) \leq 2t2^{k^3}/t \leq 2^{k^3+2}$ once again.

  By \Cref{fact:mono:crossing_lb:2}, for any $y\in\mathbb R^{d-1}$, $\textup{Cr}(f\circ p_y) = \textup{Cr}(f_0)$, and
  \begin{align*}
        \int_{[0,1]} |f(p_y(z)) - g(p_y(z))| dz
    &= \sum_{U \in \cI_f} \int_U |(f\circ p_y)(z) - (g\circ p_y)(z)| dz
    \\
    &\geq \sum_{U \in \cI_f} \int_U |(f\circ p_y)(z) - 1/2|
    \mathbf 1[\forall z\in U\centerdot \widetilde{(f\circ p_y)}(z) \neq \widetilde{(g\circ p_y)}(z)] dz
    \\
    &\geq \frac {1}{16|\cI_f|}\sum_{U \in \cI_f}
    \mathbf 1[\forall z\in U\centerdot \widetilde{(f\circ p_y)}(z) \neq \widetilde{(g\circ p_y)}(z)] dz
    \\
    &\geq \frac 1 {32} \left(1 - \frac {2\textup{Cr}(g\circ p_y)}{\textup{Cr}(f\circ p_y)}\right)
    \geq \frac 1 {32} \left(1 - \frac {2(2^{k^3+2})}{2^{k^3+4}}\right)
    \geq \frac 1 {64}.
  \end{align*}
  To finish,
  \begin{align*}
    \int_{[0,1]^d} |f(x) - g(x)|dx
    &=
    \int_{[0,1]^{d-1}} \int_{[0,1]} |(f\circ p_y)(z) - (g\circ p_y)(z)| dz dy
    \geq
    \frac {1}{64}.
  \end{align*}
\end{proofof}

Using nearly the same proof, but giving up on continuous uniform measure, it is possible
to handle other distances and more flexible target functions.

\begin{theorem}
  \label{fact:main:gen}
  Let integer $k\geq 1$
  and function $f:\mathbb R\to\mathbb R$ be given where $f$ is $(1,[0,1])$-triangle,
  and define $h:\mathbb R^d\to\mathbb R$ as $h(x) := f^k(x_1)$.
       For every $y\in\mathbb R^{d-1}$, define the affine function $p_y(z) := (z,y)$.
  Then there exist Borel probability measures $\mu$ and $\nu$ over $[0,1]^d$
  where $\nu$ is discrete uniform on $2^k+1$ points and $\mu$ is continuous and positive on exactly $[0,1]^d$
  so that
  every $g:\mathbb R^d\to\mathbb R$ with
  $\textup{Cr}(g\circ p_y) \leq 2^{k-2}$ for every $y\in\mathbb R^{d-1}$
  satisfies
  \begin{align*}
    \int |h - g|d\mu \geq \frac 1 {32},
    \qquad
    \int |\tilde h - \tilde g|d\mu \geq \frac 1 {8},
    \qquad
    \int |h - g|d\nu \geq \frac 1 {8},
    \qquad
    \int |\tilde h - \tilde g|d\nu \geq \frac 1 {4}.
  \end{align*}
\end{theorem}

\section{Limitations of depth}
\label{sec:vc}

\Cref{fact:main:gen} can be taken to say: there exists a labeling of $\Theta(2^{k^3})$ points
which is realizable by a network of depth and size $\Theta(k^3)$,
but can not be approximated by networks with depth $k$ and size $o(2^k)$.
On the other hand, this section will sketch the proof of \Cref{fact:sa_fit_few},
which implies that these $\Theta(k^3)$ depth networks realize relatively few different
labellings.
The proof is a quick consequence of the VC dimension of semi-algebraic
networks (cf. \Cref{fact:vc_sa}) and the following fact,
where $\textup{Sh}(\cdot)$ is used to denote the \emph{growth function}
\citep[Chapter 3]{anthony_bartlett_nn}.

\begin{lemma}
  \label[lemma]{fact:vc_lb}
  Let any function class $\cF$
  and any distinct points $(x_i)_{i=1}^n$   be given.
  Then with probability at least $1-\delta$ over a uniform random draw of labels
  $(y_i)_{i=1}^n$ (with $y_i \in \{-1,+1\}$),
     \[
    \inf_{f\in\cF}  \frac 1 n \sum_{i=1}^n \mathbf 1[\tilde f(x_i) \neq y_i]
    \geq \frac 1 2 \left(1 - \sqrt{
        \frac {\ln(\textup{Sh}(\cF;n)) + \ln(1/\delta)}{2n}
    }\right).
              \]
\end{lemma}

The proof of the preceding result is similar to proofs of the Gilbert-Varshamov packing bound via Hoeffding's inequality
\citep[Lemma 13.5]{duchi_info_theory}.  Note that a
similar result was used by \citeauthor{warren} to prove rates of approximation of continuous functions by polynomials,
but without invoking Hoeffding's inequality \citep[Theorem 7]{warren}.

The remaining task is to control the VC dimension of semi-algebraic networks.  To this end, note
the following generalization of \Cref{fact:vc_sa}, which further provides that semi-algebraic networks
compute functions which are polynomial when restricted to certain polynomial regions.

\begin{lemma}
  \label[lemma]{fact:pp_vc}
  Let neural network graph $\mathfrak G$ be given with $\leq p$ parameters, $\leq l$ layers, and $\leq m$ total nodes,
  and suppose every gate is $(t,\alpha,\beta)$-sa.  Then
  \[
    \textup{VC}(\cN(\mathfrak G))
    \leq
        6p(l+1)\big(
      \ln(2p(l+1)) + \ln(8emt\alpha) + l\ln(\beta)
    \big).
  \]
  Additionally, given any $n\geq p$ data points, there exists a partition $\cS$ of
  $\mathbb R^p$ where each $S\in\cS$ is an intersection of predicates $\mathbf 1[q \diamond 0]$ with $\diamond \in \{<,\geq\}$ and
  $q$ has degree $\leq \alpha\beta^{l-1}$, such that $F_\mathfrak G(x_i,\cdot)$ restricted to each $S\in\cS$ is a fixed polynomial of degree $\leq \beta^l$
  for every example $x_i$,
            with
   $|\cS|
   \leq
   \left(8enmt \alpha \beta^{l}\right)^{pl}$
   and
   $
   \textup{Sh}(\cN(\mathfrak G);n)
   \leq
   \left(8enmt \alpha \beta^{l}\right)^{p(l+1)}$
\end{lemma}

The proof follows the same basic structure of the VC bound for networks with piecewise polynomial
activation functions \citep[Theorem 8.8]{anthony_bartlett_nn}.  The slightly modified proof here is also very
similar to the proof of \Cref{fact:sa_crossing}, performing an induction up through the layers of the network,
arguing that each node computes a polynomial after restricting attention to some range of parameters.
The proof of \Cref{fact:pp_vc} manages to be multivariate (unlike \Cref{fact:sa_crossing}), though this requires
arguments due to \citet{warren} which are significantly more complicated than those of \Cref{fact:sa_crossing}
(without leading to a strengthening of \Cref{fact:main}).

One minor departure from the VC dimension proof of piecewise polynomial networks (cf. \citep[Theorem 8.8]{anthony_bartlett_nn})
is the following \namecref{fact:poly_counts}, which is used to track the number of regions
with the more complicated semi-algebraic networks.
Despite this generalization, the VC dimension bound is basically the same as for piecewise polynomial networks.

\begin{lemma}
  \label[lemma]{fact:poly_counts}
  Let a set of polynomials $\cQ$ be given where each $\cQ\ni q:\mathbb R^p\to\mathbb R$
  has degree $\leq \alpha$.
  Define an initial family $\cS_0$ of subsets of $\mathbb R^p$ as
    $
    \cS_0 := \big\{
      \{ a\in\mathbb R^p : q(a) \diamond 0 \}
      \ :\ q\in\cQ, \diamond \in \{ <, \geq \}
    \big\}.
  $
    Then the collection $\cS$ of all nonempty intersections of elements of $\cS_0$ satisfies
  $
        |\cS| \leq 2 \left(\frac {4e|\cQ|\alpha}{p}\right)^p.
  $
\end{lemma}

\section{Bibliographic notes and open problems}
\label{sec:bib}

Arguably the first approximation theorem of a big class by a smaller one is the Weierstrass Approximation Theorem,
which states that polynomials uniformly approximate continuous functions over compact sets \citep{weierstrass_apx}.
Refining this,
\citet{kolmogorov_width} gave a bound on how well subspaces of functions can approximate continuous functions,
and \citet{vitushkin_1,vitushkin_2} showed a similar bound for approximation by polynomials in
terms of
the polynomial degrees, dimension, and modulus of continuity of the target function.
\citet{warren} then gave an alternate proof and generalization of this result, in the process effectively
proving the VC dimension of polynomials
(developing tools still used to prove the VC dimension of neural networks \citep[Chapters 7-8]{anthony_bartlett_nn}),
and producing an analog to \Cref{fact:sa_fit_few} for polynomials.

The preceding results, however, focused on separating large classes (e.g., continuous functions of bounded modulus) from small classes (polynomials
of bounded degree).
Aiming to refine this, depth hierarchy theorems in circuit complexity separated circuits of a certain depth from circuits of a slightly
smaller depth.
As mentioned in \Cref{sec:intro}, the seminal result here is due to \citet{hastad_thesis}.
For architectures closer to neural networks, \emph{sum-product networks} (summation and product nodes) have been analyzed by
\citet{bengio_sumproduct_separation} and more recently \citet{martens_sumproduct},
and networks of linear threshold functions in 2 and 3 layers by \citet{kane_williams_ltf};
note that both polynomial gates (as in sum-product networks)
and linear threshold gates are semi-algebraic gates.
Most closely to the present
work (excluding \citep{mjt_easy_relu}, which is a vastly simplified account),
\citet{ohad_nn_apx} analyze 2- and 3-layer networks with general activation functions composed with affine mappings,
showing separations which are exponential in the input dimension.
Due to this result and also recent advances in circuit complexity \citep{rocco_apx},
it is natural to suppose \Cref{fact:main} can be strengthened to separating $k$ and $k+1$ layer networks when dimension $d$ is large;
however, none of the earlier works give a tight sense of the behavior as $d\downarrow 1$.

The triangle wave target functions considered here (e.g., cf. \Cref{fact:triangles}) have appeared in various forms throughout the literature.
General properties of piecewise affine highly oscillating functions were investigated by
\citet{szymanski_mccane_folding} and \citet{bengio_linear_regions}.
Also, \citet{schmitt_4x1x_nn} investigated the map $z\mapsto 4z(1-z)$ (as in \Cref{fact:triangles}) to show that sigmoidal networks
can not approximate high degree polynomials via an analysis similar to the one here,
however looseness in the VC bounds for sigmoidal networks prevented exponential separations and depth hierarchies.

A tantalizing direction for future work is to characterize not just one difficult function (e.g., triangle functions as in \Cref{fact:triangles}),
but many, or even all functions which are not well-approximated by smaller depths.  Arguably, this direction could have
value in machine learning, as discovery of such underlying structure could lead to algorithms to recover it.
As a trivial example of the sort of structure which could arise,
considering the following \namecref{fact:sym_rep},
stating that any symmetric signal may be repeated by pre-composing it with the ReLU triangle function.

\begin{proposition}
  \label[proposition]{fact:sym_rep}
  Set $f(z) := \sigma_{\textsc{r}}(2\sigma_{\textsc{r}}(z) - 4\sigma_{\textsc{r}}(z-1/2))$ (cf. \Cref{fact:triangles}),
  and let any $g:[0,1]\to[0,1]$ be given with $g(z) = g(1-z)$.
  Then $h := g\circ f^k$ satisfies $h(x) = h(x + i2^k) = g(x2^k)$ for every real $x\in [0,2^{-k}]$ and integer $i\in \{0,\ldots,2^{-k}-1\}$;
  in other words, $h$ is $2^k$ repetitions of $g$ with graph scaled horizontally and uniformly to fit within $[0,1]^2$.
\end{proposition}

\acks{%
  The author is indebted to Joshua Zahl for help navigating semi-algebraic geometry and for a simplification of
  the multivariate case in \Cref{fact:main},
  and to
  Rastislav Telg{\'a}rsky
  for an introduction to this general topic via Kolmogorov's Superposition Theorem \citep{kolmogorov_nn}.
  The author further thanks
  Jacob Abernethy,
  Peter Bartlett,
  S{\'e}bastien Bubeck,
  and Alex Kulesza
  for valuable discussions.
}

\addcontentsline{toc}{section}{References}
\ifarxiv
\bibliographystyle{plainnat}
\fi