text:
\section{Introduction} \label{sec:introduction}

How do humans come to understand their world? Consider the learning of mathematics - we learn basic mathematics before proceeding to advanced mathematics, the understanding of basic math serving as the foundation on which to develop an understanding of advanced math. Once an advanced understanding of math is acquired, it in turn is used to better understand basic math, reinforcing an understanding of mathematics as a whole. Similarly in perception - higher levels of abstraction within our perceptual hierarchies are built upon the lower levels of abstraction. Additionally, using higher level interpretations to reinforce lower level interpretations can provide benefits to perception as a whole, in the same way that using a more expansive understanding of mathematics to understand elementary mathematics reinforces an understanding of mathematics as a whole.

Disregarding the interplay between levels of abstraction in perception, the recent trend in deep neural networks is to simply make networks deeper.
Since networks have become so deep, researchers have developed a now standard design that divides network layers into blocks of layers~\cite{krizhevsky2012imagenet,VGG,he2016deep,Huang2016Densely}. Each block consists of layers of transforms that produce feature maps of the same shape. Cross-block transforms recombine the previous features and incorporate strided convolutions or pooling operations to reshape the feature maps. This strategy is an extension of the traditional design of the multilayer perceptron or fully-connected network~\cite{Rumelhart:1986:LIR:104279.104293}. The introduction of blocks has allowed a better organization of the evolving layers of abstraction within those networks. Overall, more high level features are abstracted through these transforms (Fig.~\ref{fig:CasNet},~\ref{fig:Multilevel}). However, the unstructured recombination of features in existing networks has made the investigation of deep neural networks nontrivial~\cite{DBLP:journals/corr/ZeilerF13,UnderstandingCNN_Mallat}.

Aside from deviating from basic intuitions about learning and perception, the now standard design has other apparent shortcomings. Since strided convolution or pooling are used to resize the feature maps by integer scales, researchers are compelled to create ad hoc network shapes, ones which are subject to awkward constraints of integer pooling and strides. Some networks assign more layers in later stages, where the feature maps are very small~\cite{he2016deep}. Some other networks are wider but have fewer layers~\cite{WideResNet}. The specification of feature map dimensions or distribution of computational resources is highly engineered and uneven in these designs. It is difficult to determine which designs outperform others, given that the overall shape is different. To make things worse, when the task changes, the network shape needs to be handcrafted again.

Arguably the biggest shortcoming of existing designs is that they afford little intuition on the training process, and consequently make deep networks notoriously hard to train. Researchers have expended significant effort in developing better methods to train these networks.

In this work we introduce an architecture more closely in line with intuitions of biological learning and perception: Evenly Cascaded convolutional Network (ECN). ECN is 1) easier than existing architectures to adapt to new tasks, 2) produces internal representations which are more humanly interpretable, 3) performs robustly as parameter count is restricted, and 4) produces competitive performance when compared to other state-of-the-art methods.

\begin{figure}
\centering
\subfigure[]{\includegraphics[height=.6 in]{figs/maps_layer1.png}}
\subfigure[]{\includegraphics[height=.8 in]{figs/maps_layer2.png}}
\subfigure[]{\includegraphics[height=.8 in]{figs/maps_layer3.png}}
\subfigure[]{\includegraphics[height=.8 in]{figs/maps_layer4.png}}
\subfigure[]{\includegraphics[height=.8 in]{figs/maps_layer5.png}}
\subfigure[]{\includegraphics[height=.8 in]{figs/maps_layer6.png}}

\caption{Visualizations of feature maps in ECN. The underlying network has $8$ feature maps in the first hidden layer. The feature channel growth rate is set to $8$. In this $6$-hidden-layer network there are $8,16,24,32,40,48$ feature maps in layers 1-6 respectively. In each deeper layer the newly generated higher level feature maps are appended as a new row. (a) Level 1 feature maps in the first hidden layer. (b) Level 1 features are adapted and tiled in the first row, level 2 features are newly generated using level 1 features, and are appended in the second row. (c) Both level 1 and level 2 features are adapted and tiled in the first two rows. Level 3 features are newly generated from level 1 and level 2 features, and are appended as the third row. (d) Level 4 features. (e) Level 5 features. (f) Level 6 features are used for recognition. The feature maps have been rescaled for better visualization.}
\label{fig:Maps}
\end{figure}
ECN is structured around the  insights that 1) maintaining low-level features through to the upper layers of a network is beneficial, 2) allowing multiple levels of features to interact with each other within the network is beneficial, 3) abrupt changes in feature map dimension could be less ideal than gradual changes, and 4) the manner in which features are conventionally combined within network blocks hampers the preservation of low-level features. Our architecture instantiates the first two of these insights through a ``cascade'' architecture - a two stream architecture, one stream for low-level features, one stream for successively higher level features, where these two streams interact at every layer. This differs from the existing method of using skip connections to introduce low-level features into upper level network layers in that low level features are maintained, and modulated appropriately, rather than simply jumping layers~\cite{Huang2016Densely}. This approach differs from a conventional two-stream approach~\cite{WaveletPackets} in that both streams interact with each other. For the third insight, in both streams of our cascade architecture bilinear interpolation is employed for fractional pooling, allowing a gradual rather than abrupt decrease of feature map dimensions. Different from existing architectures, in ECN a scaling factor is introduced which simplifies the design of the shape of the network removing the need for handcrafting network shape. For the fourth insight we remove the conventional combination of features across blocks in neural networks in order to preserve the low-level signal in ECN's two-stream cascade architecture. We demonstrate that preserving multilevel features enhances training by providing easy-to-train shortcuts.

Our evaluation of ECN resulted in several intriguing results: 1) With ECN's principled structuring, shallow networks (Fig. \ref{fig:CasNet}) seem to perform competitively well when compared to extremely deep networks. 2) Complex high level tasks such as image classification can be approached through evenly downsampling and adapting a set of highly structured features (Fig. \ref{fig:Maps}). 3) Low level features may be of critical importance in high level tasks such as image classification: not only do these features remain similar in the deeper adaptation process, but they may have provided major convenience for the training of high level features.

Finally, we evaluate ECN using multiple convolution block designs and find that recurrent and recursive designs lead to improved efficiency and accuracy. Without additional treatment, a standard convolution block design combined with recurrent connections leads to state-of-the-art accuracy in benchmark image classification tasks. Another block design using a recursive filter gives rise to state-of-the-art efficiency. Our 6-cascading-layer design with under 500k parameters achieves 95.24\% and 78.99\% accuracy on CIFAR-10 and CIFAR-100 datasets, respectively, outperforming the current state-of-the-art on small parameter networks, and our 3 million parameter version is competitive to the state-of-the-art.

\section{Related Work} \label{sec:related_work}

Even though convolutional networks have led to many exciting breakthroughs in visual and language learning tasks \cite{krizhevsky2012imagenet}, the mathematical understanding of convolutional networks is severely underdeveloped. It is intuitively clear that convolutional networks can be understood in part within the context of scale-space theory or multiresolution analysis \cite{Mallat:2008:WTS:1525499}. While an excellent attempt has been made \cite{UnderstandingCNN_Mallat} to explain convolutional networks in wavelet terms, it remains unclear how the techniques in wavelet theory can be explicitly used to simplify the construction and training of convolutional networks.

Skip connections or identity maps in the networks \cite{hochreiter1997long,he2016deep,Huang2016Densely,DPN} are a popular method for improving network performance. One intuitive understanding of the function of skip connections is that they pass lower level representations to deeper levels. In LSTM \cite{hochreiter1997long} and ResNet~\cite{he2016deep} networks the representations are adapted during this process.  Whereas in DenseNet~\cite{Huang2016Densely} shallow features are passed to the deeper levels without modification. One recent work, termed Dual Path Networks(DPN) \cite{DPN}, connects the two approaches using a high order recurrent neural network, and horizontally concatenates ResNet \cite{he2016deep} and DensNet \cite{Huang2016Densely}, and shows improved performance.

Presently, the best performing networks are typically 50 to 100 layers deep~\cite{he2016deep,Huang2016Densely,DBLP:journals/corr/SrivastavaGS15}. Translating an existing backbone architecture to a new application with different input and output sizes is a nontrivial task. The structuring of these standard designs are constrained by integer resizing operations such as pooling and strided convolution. Fractional pooling and strides have been explored previously, e.g. \cite{graham2014fractional}. In our implementation of fractional pooling we employ bilinear interpolation, as is done in \cite{SpatialTransformer}. Furthermore, existing architectures merge different levels of features at the end of each block such that low- and high-level features become entangled and in-differentiable.  ECN safely removes these limitations.

As the networks become wider and deeper, methods such as pruning~\cite{DBLP:journals/corr/HanMD15,PruningHao,PruningICCV}, quantizing~\cite{DBLP:journals/corr/CourbariauxB16}, and knowledge distillation~\cite{DBLP:journals/corr/HintonVD15} have been introduced to reduce the size of these networks. ECN uses recursion\cite{RecurrentCNN,socher2012convolutional} to re-use parameters across layers, allowing for greater compactness of network design.
In the other direction, significant efforts have been spent on discovering more efficient network layers or overall architectures~\cite{DBLP:journals/corr/IandolaMAHDK16,MobileNet,DBLP:journals/corr/ZhangZLS17,Condensenet,Huang2016Densely,DBLP:journals/corr/ZhangQ0W17}.

\section{Methods} \label{sec:methods}

ECN is based on a simple cascading layer design. Intuitively, a cascading layer incorporates multilevel features and gradually resizes those features before providing them to the next layer. ECN consists of iteratively stacked cascading layers. This iterative construction process ends when a stopping condition is met - e.g., when feature map dimensions fall below a predefined size.

\subsection{Utilization of Multilevel Features}

\begin{figure}
\centering
\includegraphics[width=4.5 in]{figs/layers.png}
\caption{Multilevel feature representations within ECN. For the $i$-th layer ($i$-th row in the figure), fractional scaling is used to downsample the features from layer $i-1$ (row $i-1$ in the figure). A convolution block is applied over these downsampled features to generate the modulation signal, and the level $i$ features (red block). The modulation signal is then added to the features downsampled from the  previous layer. The superscripts in each block represent the number of modulations the features have undergone.}
\label{fig:Multilevel}
\end{figure}

We now follow the intuition
that allowing an interplay between level of abstraction within perception can give rise to greater perceptual synergy
  at the beginning of Section \ref{sec:introduction} in introducing ECN's usage of multilevel features. To illustrate ECN's relation to work in the literature we also provide three additional viewpoints of our utilization of multilevel features: one from the network architecture, one from wavelet analysis, and one from optimization of neural networks.

\subsubsection{From a Network Architectural Point of View}

Our cascading design can be viewed as evolving from the designs of several well-performing networks~\cite{he2016deep,Huang2016Densely,DPN}. Our first design can be viewed as a ResNet-inspired DenseNet, or a DenseNet-inspired ResNet. We make an extension to DenseNet~\cite{Huang2016Densely} when passing low level features to deeper layers by allowing them to be modulated by higher level features. The modulation of low level features can be viewed as a \textit{feedback} mechanism, where high level knowledge is providing ``advanced viewpoints'' to improve the low level knowledge, effected through a link from the higher level stream to the lower level stream of the network. The modulation signal is generated using a convolution block, and is added to the original features as in residual learning~\cite{he2016deep}. The generation of high level features is also achieved using the convolution block - however, the results are appended to the existing channels (Figs.~\ref{fig:CasNet},~\ref{fig:Multilevel}).  Similar to our design, but more costly, Dual Path Network~\cite{DPN} concatenates ResNet and DenseNet layers. By not passing low-level features through a $1\times1$ convolution, such as is done in DPN, ECN better preserves low-level features, making them more directly available at higher layers.

As a consequence of this ECN is able to pass features throughout the \textit{whole network}, rather than only within each \textit{block}. With this design we explicitly enforce that the shallowest level features be preserved throughout the whole network, with adaptations made only if they improve the final task (Figs.~\ref{fig:CasNet},~\ref{fig:Maps}).

\subsubsection{From a Wavelet Point of View}
It is noteworthy that the cascading layer is a more general form of the cascade algorithm used in wavelet packet decomposition~\cite{WaveletPackets,Mallat:2008:WTS:1525499}, where previous level signals are decomposed into a low frequency branch and a high frequency branch, usually followed by downsampling by a factor of $2$. In wavelet packet decomposition, the original signal is decomposed into a binary tree. The difference between this and ECN is that in ECN the two siblings are merged before the next level of decomposition, deviating from a tree structure. The extensions we made in our cascading design derive from the adaptations and downsampling of features which we introduce later.  Due to the cascading design, the evolution of feature maps within ECN closely resembles the evolution of modulus maxima in scale-space theory~\cite{Mallat:2008:WTS:1525499}. This relation suggests a path for further mathematical investigation of neural networks.

\subsubsection{From an Optimization Point of View}

ECN's construction facilitates training by providing easily trainable shortcuts to the optimization: we speculate that as a consequence of the two stream architecture, ECN allows the decomposition of $f$, the mapping from network input to output, into a series of progressively hierarchically deeper, and therefore harder to train, functions: $f=f_1+f_2+...+f_N$. See figure \ref{fig:Multilevel} for a visualization of function decomposition within and across layers. In figure \ref{fig:Multilevel} layer N contains features of levels $1$ through $N$ - this provides a direct link from the training (gradient) signal not only to higher level features, as is the case in other architectures, but to mid- and low-level features as well. This relaxes the interdependence in training between $f_i$ (low $f_i$ can be trained with less dependence on high $f_i$), and has the potential to facilitate training by allowing a training of $f$ component-wise. The result of this is the capability to train a complex function, $f$, by training the simpler functions of which it is composed, $f_i$.

Decompositions analogous to this kind have been proven to be helpful in multiscale signal analysis. Complex operations are simplified by conducting them at multiple scales, either (1) from coarse-to-fine or (2) in parallel. Here, we take the second approach to train different levels in parallel: the easier to train, or coarse, components can serve as a backbone model for the harder components, where the harder-to-train layers have only to compensate for the residuals of the learning problem.  We conjecture that ECN's construction facilitates the progressive training of neural networks. Note that ECN's construction is a revival of the layer-wise pretraining technique~\cite{Layer-wise-training} which triggered the era of deep learning. This classic approach followed the correct intuition of progressively developing high level representations. But the layer-wise training, which belongs to the first approach, lacks proper supervision signal.

\subsection{Fractional Scaling}

To facilitate the passing of low level features throughout the whole network, and to evenly resize the feature maps in a network, we propose to use fractional scaling, performed using bilinear interpolation, replacing the classic integer pooling and striding operations. Bilinear interpolation was first introduced in Spatial Transformer Networks~\cite{SpatialTransformer} to continuously deform feature maps for recognition tasks. Here we use bilinear interpolation to replace all the size change operations in the network.

Using bilinear interpolation, the outputs of the previous layer are fractionally scaled to the desired shape, and then serve as inputs to the next layer. Since bilinear interpolation is a locally smooth operation, subgradients can be calculated for backpropagation. In a network with a decreasing feature map dimension, having a constant scaling factor close to $1$ leads to a deep network. Similarly, having a constant scaling factor close to $0$ leads to a shallow network.

We adopt a simple uniform sampling when scaling the feature maps for obtaining the sample grid for bilinear interpolation. Non-uniform sampling is a natural extension~\cite{DeformableCNN} and we leave it for future work. Here, the output feature map dimension can be either calculated from the scaling factor or manually specified. The uniformly spaced sampling grid is then calculated to sample from the previous feature map.

\subsection{Convolution Block Design}

Many researchers have proposed different convolution block designs for use within layers of convolutional networks. However, in most cases different block designs are associated with different network architectures. As a consequence, it is difficult to draw conclusions about the relative merits of different block designs. However, with ECN's evenly cascaded design, it is straightforward to incorporate different block designs. In this work we propose and evaluate multiple block designs. More advanced block designs than are presented here can be evaluated in subsequent works and potentially result in improved performance. In this paper we include six basic blocks:

Block 1:  Single convolution (Fig.~\ref{fig:ConvBlocks}(a)). The convolutional layer has one single convolution operation, combined with standard techniques such as batch normalization~\cite{DBLP:journals/corr/IoffeS15} and the ReLU activation function~\cite{krizhevsky2012imagenet}. We order these operations as $BN \rightarrow ReLU \rightarrow Conv$.

Block 2: Double convolution (Fig.~\ref{fig:ConvBlocks}(b)). Two single convolution layers are chained together, the number of intermediate output channels is set to be the larger of the input and output channels.

Block 3: Recurrent convolution (Fig.~\ref{fig:ConvBlocks}(c)). We iteratively reuse the weights in Block 1 through recurrent connections. We made alterations to the previously reported approach~\cite{RecurrentCNN}. Firstly, the number of input channels do not usually match the number of output channels. Here we propose a simple solution: when the output channels ($OUT$) are more than the input channels ($IN$), we \textit{slice} the matching channels from the output (e.g. the first $IN$ channels) to reuse as input. Similar to an $LSTM$~\cite{hochreiter1997long} we add the outputs of the later iterations to the initial outputs. It is important to point out that our implementations of this recurrent design lead to worse results in ECN. The output signals usually have very different statistical properties from the input signals, and this inconsistency interfered with training. Our solution to this is that we insert an individual batch normalization operation for each iteration, leaving the convolution kernel weights shared in all iterations. This design significantly improves performance with very little increase in number of parameters (Tables~\ref{tab:CIFAR-10},~\ref{tab:CIFAR-100}, Fig.~\ref{fig:SizePerformance}).

Block 4: Recurrent double convolution (Fig. \ref{fig:ConvBlocks}(d)). Similar to Block 3 we iteratively reuse Block 2.

Block 5: Recursive convolution (Fig. \ref{fig:ConvBlocks}(e)). To make the convolutions more efficient we adopt separable convolution operations~\cite{MobileNet} to replace standard convolution. Cross-channel $1 \times 1$ convolution is applied in the first stage to change the number of input channels to match the number of output channels, followed by the channel-wise convolution in the second stage. Compared to standard convolution which involves more parameters, separable convolutions are usually more efficient but are weaker than directly applying standard convolutions. One fix for this weakness is to iteratively apply the filtering as in Blocks 3 and 4. Traditionally this technique is called recursive filtering. We adopt this name and include this class of filtering in our comparison.

Block 6: Recursive quadruple convolution (Fig. \ref{fig:ConvBlocks}(f)). Each recurrent double convolution (Block 4) is replaced by four separable convolutions.

\begin{figure}
\centering
\subfigure[]{\includegraphics[height=.75 in]{figs/SingleConv.png}}
\subfigure[]{\includegraphics[height=.75 in]{figs/DoubleConv.png}}
\subfigure[]{\includegraphics[height=.75 in]{figs/RecurrentConv.png}}
\subfigure[]{\includegraphics[height=.75 in]{figs/RecurrentDoubleConv.png}}
\subfigure[]{\includegraphics[height=.75 in]{figs/RecursiveConv.png}}
\subfigure[]{\includegraphics[height=.75 in]{figs/RecursiveQuadConv.png}}

\caption{Convolution blocks that we evaluate: (a) Single convolution, (b) Double convolution, (c) Recurrent convolution, (d) Recurrent double convolution, (e) Recursive convolution. $Conv\_C$ stands for cross-channel $1\times 1$ convolution, $Conv\_S$ stands for channel-wise spatial convolution. (f) Recursive quadruple convolution.}
\label{fig:ConvBlocks}
\end{figure}

\section{Experiments} \label{sec:experiments}

\def \hspace*{-\textwidth} \hfill {\hspace*{-\textwidth} \hfill}

\begin{table}[t]
\begin{minipage}{0.7\textwidth}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{@{}l|rrrrrr@{}}
\toprule
\textbf{Conv Block} & \textbf{\begin{tabular}[c]{@{}r@{}}Initial \\ Channels\end{tabular}} & \textbf{Scaling} & \textbf{CIFAR-10} & \textbf{Parameters} & \textbf{CIFAR-100} & \textbf{Parameters} \\ \midrule
type 4              & 16                                                                   & 3/4              & 93.49\%           & 214330              & 68.15\%            & 220180              \\
type 4              & 32                                                                   & 3/4              & 95.47\%           & 849130              & 76.05\%            & 860740              \\
type 4              & 64                                                                   & 3/4              & 96.20\%           & 3380170             & 79.80\%            & 3403300             \\
type 4              & 128                                                                  & 3/4              & 96.68\%           & 13488010            & 81.75\%            & 13534180            \\ \midrule
type 6              & 64                                                                   & 3/4              & 95.24\%           & 421770              & 78.99\%            & 444900              \\ \bottomrule
\end{tabular}
}
\caption{CIFAR accuracies for ECN-6}
\label{tab:Results}
\end{minipage}
\hspace*{-\textwidth} \hfill
\begin{minipage}{0.3\textwidth}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{c}
\hline
\textbf{ECN-6}                                                                          \\ \hline
3x3 Conv                                                                        \\ \hline
\begin{tabular}[c]{@{}c@{}}
$\begin{bmatrix}Cascaded ConvBlock\\ Fractional Scaling
 \end{bmatrix}\times 6$
\end{tabular} \\ \hline
global average pooling                                                          \\ \hline
Softmax                                                                         \\ \hline
\end{tabular}
}
\caption{ECN-6 architecture}
\label{tab:CasNet-6}
\end{minipage}
\end{table}

\subsection{Datasets}
We evaluate ECN over three datasets: CIFAR-10, CIFAR-100~\cite{krizhevsky2009learning}, and ImageNet-32~\cite{DBLP:journals/corr/ChrabaszczLH17}. These datasets consist of 32x32 pixel images. CIFAR-10 has 10 classes, CIFAR-100 has 100 classes, and ImageNet-32 has 1000 classes. We employ standard methods of data augmentation, including horizontal image flips, and random 32x32 crops of zero padded images, with 4 pixel padding. CIFAR-10 and CIFAR-100 each contains 50,000 training samples, and 10,000 testing samples. ImageNet-32 contains images of ImageNet~\cite{ImageNet}, downsampled to 32x32 pixels; it contains 1.2 million training samples, and 50 thousand validation samples.

\subsection{Results}

The ECN network we use has a shape where feature map dimensions consistently decrease in size; it is constructed by iteratively stacking cascading layers until the feature map size is below a preset threshold (4 pixels). In our experiments we fix the number of iterations in Blocks 3, 4, 5, and 6 to $3$.

In table \ref{tab:Results} we employed a scaling factor of $\frac{3}{4}$, resulting in an evenly cascaded structure with 6 cascading layers (ECN-6). We report results for differently scaled structures using block 4, and one more result using a more efficient design using block 6. At the beginning of the network, a convolution is used to transform the channel count of the input to $init\_channels$, which takes the value 16, 32, 64, or 128. In each consecutive layer, we generate channels of high level features with a growth rate of $init\_channels \times 2\times (1-scaling\_factor)$, corresponding to 8, 16, 32, 64 respectively in the four networks. The overall network architecture can be found in table \ref{tab:CasNet-6}. Here a cascaded convolution block~\cite{Mallat:2008:WTS:1525499} represents using one convolution block and grouping the results into a low level branch and a high level branch. Global average pooling is used to convert the final feature map into a vector for classification. To avoid overfitting we also insert dropout after ReLU activations for the 3 largest networks in table \ref{tab:Results}. The dropout rates range from 0.03-0.25. We use stochastic gradient descent to train the network for 2000 epochs with a batch size of 512, for CIFAR10 and CIFAR100, and for 50 epochs and a batch size of 512 for ImageNet-32. The training is scheduled with an initial learning rate of 0.1 and followed by cosine annealing learning rates. The results can be found in table \ref{tab:Results}.

\begin{table}
\begin{center}
\begin{tabular}{l|r|r|r}
\hline
\textbf{ImageNet32}  & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c|}{\textbf{Top-1 error}} & \multicolumn{1}{c}{\textbf{Top-5 error}} \\ \hline
WRN-28-1 \cite{WideResNet}             & 0.44M                                & 67.97\%                                   & 42.49\%                                  \\
WRN-28-2 \cite{WideResNet}            & 1.6M                                 & 56.92\%                                   & 30.92\%                                  \\
WRN-28-5 \cite{WideResNet}            & 9.5M                                 & 45.36\%                                   & 21.36\%                                  \\
WRN-28-10 \cite{WideResNet}            & 37.1M                                & 40.96\%                                   & 18.87\%                                  \\ \hline
ECN-6, block 6 (32)  & 0.24M                                & 63.91\%                                   & 38.50\%                                  \\
ECN-3, block 6 (64)  & 0.48M                                 & 59.05\%                                   & 33.68\%                                  \\
ECN-6, block 6 (64)  & 0.68M                                & 55.51\%                                   & 30.26\%                                  \\
ECN-6, block 6 (128) & 2.1M                                 & 46.29\%                                   & 21.92\%                                  \\
ECN-3, block 4 (128) & 7.8M                                 & 45.10\%                                   & 21.06\%                                  \\
ECN-6, block 4 (128) & 14.0M                                & 41.87\%                                   & 18.61\%                                  \\ \hline
\end{tabular}
\end{center}
\caption{Results on the ImageNet-32 dataset, for WideResNet \cite{WideResNet}, and ECN (channel count)}
\label{tab:ImageNet32}
\end{table}

Our studies on ImageNet-32 demonstrate ECN's potential to generalize to larger scale datasets. We evaluate ECN-3 and ECN-6, corresponding to scaling rates of $\frac{1}{2}$ and $\frac{3}{4}$, over ImageNet-32. We use initial channel counts of 32, 64, and 128, and report results in table \ref{tab:ImageNet32}, with channel counts given in parentheses. ECN-6 is more efficient than the strong baseline results reported in WideResNet~\cite{WideResNet}. An ECN-6 network using only 2 million parameters shows comparable results to a WideResNet architecture using 9.5 million parameters. ECN with block 4 produces competitive results using smaller number of parameters than WideResNet. ECN-3, which has 3 cascading layers and 7 million parameters outperforms the 9.5 million parameter WRN-28-5 result. A larger ECN-6 network using block 4 with 14 million parameters achieves accuracy that is comparable to WRN-28-10, which contains 37.1 million parameters.

\begin{table}[t]
\begin{minipage}{0.49\textwidth}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{l|r|r|r}
\hline
\textbf{Model}      & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c|}{\textbf{CIFAR-10}} & \multicolumn{1}{c}{\textbf{CIFAR-100}} \\ \hline
VGG-16 pruned\cite{PruningHao}       & 5.4M                                 & 6.60                                   & 25.28                                  \\
VGG-19 pruned\cite{PruningICCV}       & 2.3M                                 & 6.20                                   & -                                      \\
VGG-19 pruned\cite{PruningICCV}       & 5M                                   & -                                      & 26.52                                  \\
Resnet-56 pruned\cite{PruningHao}    & .73M                                 & 6.94                                   & -                                      \\
Resnet-110 pruned\cite{PruningHao}   & 1.68M                                & 6.45                                   & -                                      \\
Resnet 164-B pruned\cite{PruningICCV} & 1.21M                                & 5.27                                   & 23.91                                  \\
DenseNet-40-pruned\cite{PruningICCV}  & .66M                                 & 5.19                                   & 25.28                                  \\
CondenseNet-94\cite{Condensenet}      & .33M                                 & 5.00                                   & 24.08                                  \\
CondenseNet-86 \cite{Condensenet}     & .52M                                 & 5.00                                   & 23.64                                  \\ \hline
ECN, Block 6   & .42M                                 & 4.76                                   & 21.01                                  \\ \hline
\end{tabular}
}
\caption{Error rate comparison with state-of-the-art efficient architectures}
\label{tab:EfficientArchitectures}
\end{minipage}
\hspace*{-\textwidth} \hfill
\begin{minipage}{0.49\textwidth}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{lrrrlll}
\cline{1-4}
\multicolumn{1}{l|}{\textbf{Model}}        & \multicolumn{1}{r|}{\textbf{Params}} & \multicolumn{1}{r|}{\textbf{CIFAR-10}} & \textbf{CIFAR-100}   \\ \hline
\multicolumn{1}{l|}{ResNet-1001\cite{DBLP:journals/corr/HeZR016}}           & \multicolumn{1}{r|}{16.1M}           & \multicolumn{1}{r|}{4.62}              & 22.71                \\
\multicolumn{1}{l|}{Stochastic-Depth-1202\cite{DBLP:journals/corr/HuangSLSW16}} & \multicolumn{1}{r|}{19.4M}           & \multicolumn{1}{r|}{4.91}              & -                    \\
\multicolumn{1}{l|}{Wide-ResNet-28\cite{WideResNet}}        & \multicolumn{1}{r|}{36.5M}           & \multicolumn{1}{r|}{4}                 & 19.25                \\
\multicolumn{1}{l|}{ResNeXt-29\cite{DBLP:journals/corr/XieGDTH16}}            & \multicolumn{1}{r|}{68.1M}           & \multicolumn{1}{r|}{3.58}              & 19.25                \\
\multicolumn{1}{l|}{DenseNet-BC-190\cite{Huang2016Densely}}          & \multicolumn{1}{r|}{25.6M}           & \multicolumn{1}{r|}{3.46}              & 17.18                \\
\multicolumn{1}{l|}{NASNet-A*\cite{Condensenet}}             & \multicolumn{1}{r|}{3.3M}            & \multicolumn{1}{r|}{3.41}              & -                    \\
\multicolumn{1}{l|}{CondenseNet*light-160\cite{Condensenet}} & \multicolumn{1}{r|}{3.1M}            & \multicolumn{1}{r|}{3.46}              & 17.55                \\
\multicolumn{1}{l|}{CondenseNet-182\cite{Condensenet}}       & \multicolumn{1}{r|}{4.2M}            & \multicolumn{1}{r|}{3.76}              & 18.47                \\ \hline
\multicolumn{1}{l|}{ECN, Block4}         & \multicolumn{1}{r|}{3.3M}            & \multicolumn{1}{r|}{3.8}               & 20.2                 \\ \hline
\multicolumn{1}{l|}{ECN, Block4}         & \multicolumn{1}{r|}{13.3M}           & \multicolumn{1}{r|}{3.32}              & 18.25                \\ \hline
                                           & \multicolumn{1}{l}{}                 & \multicolumn{1}{l}{}                   & \multicolumn{1}{l}{}
\end{tabular}

}
\caption{Error rate comparison with state-of-the-art architectures}
\label{State of art architecture}
\end{minipage}
\end{table}

\subsection{Comparison of Convolution Blocks over CIFAR10 and CIFAR100}

We have compared the six block designs over CIFAR10 and CIFAR100 using various sized networks. The networks are trained for 500 epochs.
We tested scaling factors $\frac{1}{2}, \frac{3}{4},$ and $\frac{7}{8}$, and the corresponding networks have $3, 6,$ and $12$ cascading layers. The growth rates are calculated using the same strategy as explained above. For these experiments we use 3-stage learning rate scheduling, decreasing the learning rate at $40\%$ and $80\%$ total epoch count by a factor of 10. We set batch size to 512 for CIFAR-10. For CIFAR-100 a batch size of 128 usually leads to better performance, and we report the better of size 128 and size 512 batches. The results over CIFAR-10 and CIFAR-100 can be found in tables \ref{tab:CIFAR-10} and \ref{tab:CIFAR-100}, respectively.

By comparing Blocks 1 and Blocks 3 in tables~\ref{tab:CIFAR-10} and \ref{tab:CIFAR-100}, and Fig.~\ref{fig:SizePerformance}, we found that reusing the convolution weights via recurrent connections significantly improves performance, while maintaining a small network size. When the convolution block becomes powerful, and especially when the model gets large, the improvement due to recurrent connections becomes smaller (Blocks 2 vs Blocks 4). Still, we find a surprise here that through recurrent connections even the single convolution can perform competitively with the widely used double convolution, using the same number of parameters (Fig.~\ref{fig:SizePerformance}). The optimal balance between depth and width varies from block to block. Our most efficient convolution block is block 6, which uses recursive quadruple convolutions. We reach state-of-the-art efficiency and the best results are reported in the last row of table~\ref{tab:Results}. It is noteworthy that although using separable convolution~\cite{MobileNet} reduces the number of parameters, the gain in efficiency also comes with a decrease in accuracy. The effective reduction in parameters enabled by using separable convolutions in ECN blocks $5$ and $6$ is around 2 fold to 4 fold.

When compared to other state-of-the-art efficient architecture designs, listed in table~\ref{tab:EfficientArchitectures}, ECN using block 6 achieves the lowest error rate without using any pruning methods. This is significant, as a simple and principled architecture design is proving to be better than sophisticated methods such as pruning described in~\cite{PruningICCV},~\cite{PruningHao} and even better than \cite{Condensenet} with smaller parameter count (Figs.~\ref{fig:sizeperformancecifar10_4_6}, ~\ref{fig:sizeperformancecifar100_4_6}). On the other hand, ECN block 4 does relatively well compared to other architectures listed in table~\ref{State of art architecture} that are using more advanced designs than ours.

We have shown that there are avenues for improving the performance of convolutional networks by using principled designs like ECN. Even the simplest designs can reach state-of-the-art performance. Due to limitations in space and computational resources, only the 6 basic block designs are evaluated. More advanced block designs can modularly replace our basic block designs and potentially produce even better numbers.

\begin{table}
\centering

\resizebox{\textwidth}{!}{
\begin{tabular}{rr|rr|rr|rr|rr|rr|rr}
\hline
\multicolumn{2}{c}{\textbf{CIFAR-10}}                              & \multicolumn{2}{c|}{\textbf{Block 1}}                                   & \multicolumn{2}{c|}{\textbf{Block 2}}                                   & \multicolumn{2}{c|}{\textbf{Block 3}}                                   & \multicolumn{2}{c|}{\textbf{Block 4}}                                   & \multicolumn{2}{c|}{\textbf{Block 5}}                                   & \multicolumn{2}{c|}{\textbf{Block 6}}                                  \\ \hline
\multicolumn{1}{c}{\textbf{Ch}} & \multicolumn{1}{c|}{\textbf{Sc}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c}{\textbf{Params}} \\ \hline
16                              & 1/2                              & 83.35\%                          & 47482                                & 89.71\%                          & 114586                               & 88.59\%                          & 47866                                & 91.84\%                          & 115546                               & 84.56\%                          & 9066                                 & 88.59\%                          & 19514                               \\
16                              & 3/4                              & 88.58\%                          & 97258                                & 92.04\%                          & 212410                               & 90.96\%                          & 98122                                & 92.57\%                          & 214330                               & 87.90\%                          & 17090                                & 89.92\%                          & 35370                               \\
16                              & 7/8                              & 90.12\%                          & 195082                               & 93.26\%                          & 407194                               & 91.51\%                          & 196906                               & 93.12\%                          & 411034                               & 89.35\%                          & 32946                                & 91.02\%                          & 66986                               \\ \hline
32                              & 1/2                              & 87.88\%                          & 187114                               & 92.40\%                          & 454954                               & 91.66\%                          & 187882                               & 93.86\%                          & 456874                               & 89.78\%                          & 28362                                & 91.47\%                          & 64106                               \\
32                              & 3/4                              & 91.13\%                          & 385738                               & 94.09\%                          & 845290                               & 93.15\%                          & 387466                               & 94.59\%                          & 849130                               & 91.04\%                          & 55418                                & 93.36\%                          & 117450                              \\
32                              & 7/8                              & 92.70\%                          & 776074                               & 94.36\%                          & 1622506                              & 93.93\%                          & 779722                               & 94.67\%                          & 1630186                              & 92.64\%                          & 108762                               & 93.87\%                          & 223754                              \\ \hline
64                              & 1/2                              & 90.41\%                          & 742858                               & 94.41\%                          & 1813066                              & 94.39\%                          & 744394                               & 95.29\%                          & 1816906                              & 92.25\%                          & 97674                                & 93.59\%                          & 228554                              \\
64                              & 3/4                              & 93.53\%                          & 1536394                              & 95.43\%                          & 3372490                              & 95.24\%                          & 1539850                              & 95.66\%                          & 3380170                              & 93.96\%                          & 195818                               & 94.87\%                          & 421770                              \\
64                              & 7/8                              & 94.65\%                          & 3095818                              & 95.75\%                          & 6477514                              & 95.63\%                          & 3103114                              & 95.68\%                          & 6492874                              & 94.54\%                          & 389034                               & 94.82\%                          & 806666                              \\ \hline
\end{tabular}
}
\caption{Comparison of convolution blocks on the CIFAR-10 dataset}
\label{tab:CIFAR-10}

\end{table}

\begin{table}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{rr|rr|rr|rr|rr|rr|rr}
\hline
\multicolumn{2}{c}{\textbf{CIFAR-100}}                             & \multicolumn{2}{c|}{\textbf{Block 1}}                                   & \multicolumn{2}{c|}{\textbf{Block 2}}                                   & \multicolumn{2}{c|}{\textbf{Block 3}}                                   & \multicolumn{2}{c|}{\textbf{Block 4}}                                   & \multicolumn{2}{c|}{\textbf{Block 5}}                                   & \multicolumn{2}{c|}{\textbf{Block 6}}                                  \\ \hline
\multicolumn{1}{c}{\textbf{Ch}} & \multicolumn{1}{c|}{\textbf{Sc}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c|}{\textbf{Params}} & \multicolumn{1}{c}{\textbf{Acc}} & \multicolumn{1}{c}{\textbf{Params}} \\ \hline
16                              & 1/2                              & 53.93\%                          & 53332                                & 64.93\%                          & 120436                               & 59.64\%                          & 53716                                & 66.45\%                          & 121396                               & 54.88\%                          & 14916                                & 61.95\%                          & 25364                               \\
16                              & 3/4                              & 61.50\%                          & 103108                               & 68.45\%                          & 218260                               & 63.62\%                          & 103972                               & 67.95\%                          & 220180                               & 59.96\%                          & 22940                                & 64.86\%                          & 41220                               \\
16                              & 7/8                              & 65.40\%                          & 200932                               & 71.23\%                          & 413044                               & 66.43\%                          & 202756                               & 71.26\%                          & 416884                               & 63.21\%                          & 38796                                & 66.71\%                          & 72836                               \\ \hline
32                              & 1/2                              & 62.17\%                          & 198724                               & 71.12\%                          & 466564                               & 68.19\%                          & 199492                               & 72.72\%                          & 468484                               & 64.85\%                          & 39972                                & 69.44\%                          & 75716                               \\
32                              & 3/4                              & 68.98\%                          & 397348                               & 75.02\%                          & 856900                               & 71.66\%                          & 399076                               & 75.62\%                          & 860740                               & 67.61\%                          & 67028                                & 71.34\%                          & 129060                              \\
32                              & 7/8                              & 71.72\%                          & 787684                               & 76.04\%                          & 1634116                              & 73.16\%                          & 791332                               & 76.42\%                          & 1641796                              & 70.36\%                          & 120372                               & 73.22\%                          & 235364                              \\ \hline
64                              & 1/2                              & 67.02\%                          & 765988                               & 75.47\%                          & 1836196                              & 74.00\%                          & 767524                               & 77.13\%                          & 1840036                              & 70.23\%                          & 120804                               & 74.25\%                          & 251684                              \\
64                              & 3/4                              & 73.79\%                          & 1559524                              & 78.64\%                          & 3395620                              & 76.67\%                          & 1562980                              & 79.03\%                          & 3403300                              & 73.70\%                          & 218948                               & 76.80\%                          & 444900                              \\
64                              & 7/8                              & 74.87\%                          & 3118948                              & 79.57\%                          & 6500644                              & 77.76\%                          & 3126244                              & 80.07\%                          & 6516004                              & 75.38\%                          & 412164                               & 76.93\%                          & 829796                              \\ \hline
\end{tabular}
}
\caption{Comparison of convolution blocks on the CIFAR-100 dataset}
\label{tab:CIFAR-100}

\end{table}

\begin{figure}
\centering
\subfigure[] {\includegraphics[height=1.75in]{figs/out_cifar10.png}}
\subfigure[]{\includegraphics[height=1.75in]{figs/out_cifar100.png}}
\caption{Relationship between network parameter count, block category, and classification accuracy for (a) CIFAR-10 and (b) CIFAR-100 datasets. The results are labeled according to the rows in which they appear in tables~\ref{tab:CIFAR-10} and ~\ref{tab:CIFAR-100}.}
\label{fig:SizePerformance}
\end{figure}

\begin{figure}[ht!]
\centering
\includegraphics[height=2.875 in]{figs/out_cifar10_4_6_labeled_comparison_table3.png}
\caption{Comparison between parameter count and classification accuracy over CIFAR-10 for ECN with blocks 4 and 6 and architectures listed in table ~\ref{tab:EfficientArchitectures}. Additionally, our best result using ECN-6 with block 6, attained through longer training, is plotted as ``ECN-6, block 6''.}
\label{fig:sizeperformancecifar10_4_6}
\end{figure}

\begin{figure}[ht!]
\centering
\includegraphics[height=2.875 in]{figs/out_cifar100_4_6_labeled_comparison_table3.png}
\caption{Comparison between parameter count and classification accuracy over CIFAR-100 for ECN with blocks 4 and 6 and architectures listed in table ~\ref{tab:EfficientArchitectures}. Additionally, our best result using ECN-6 with block 6, attained through longer training, is plotted as ``ECN-6, block 6''.}
\label{fig:sizeperformancecifar100_4_6}
\end{figure}

\section{Acknowledgement}
The support of ONR under grant award  N00014-17-1-2622 and the support of the National Science Foundation under grants SMA 1540916 and CNS 1544787 are greatly acknowledged.

\section{Conclusion} \label{sec:conclusion}

Taking inspiration from cascading methods in wavelet packet decomposition, we have developed Evenly Cascaded convolutional Networks (ECN) for image tasks. ECN differs from other networks in the use two interacting streams - a high-level feature stream and a low-level feature stream. ECN's two streams allow for the promulgation of low-level features throughout the entire network, as well as the modulation of those low-level features using advanced perspectives from high-level features. The explicit use of multilevel features not only leads to highly capable networks but provides shortcuts for the training process. Additionally, ECN is structured such that feature map dimensions decrease in a consistent manner, removing burdens of ad hoc architecture design, and potentially improving feature preservation and utility. We have evaluated ECN over CIFAR-10 and CIFAR-100, obtaining state-of-the-art performance, for both datasets, for small network settings; and over ImageNet-32 ECN obtains competitive results.


text:
\section{Introduction}

Social network data can be expensive to collect. A complete network census can be prohibitively costly and, for this reason, often only obtainable for small populations. \cite{breza2017using} propose a simple alternative, which is to collect aggregated relational data (ARD). ARD consists of responses to questions of the form ``How many of your friends have trait $k$?'', which \cite{breza2017using} argue can be substantially cheaper to collect than a full network census. They propose a Bayesian estimation procedure for recovering the structure of the social network from ARD under a specific latent space model of network formation \citep{hrh2002,mccormick2015latent}.

We think that the idea of using ARD as a substitute for network data is an important step to reduce financial barriers to empirical research in network economics. The purpose of our paper is to broaden the applicability of ARD. We show that tools from the high-dimensional statistics literature can be employed to recover the network structure using ARD without imposing a particular parametric model of network formation such as the latent space model. Our estimator can be computed in seconds for samples with hundreds of observations using an accelerated gradient descent algorithm due to \cite{ji2009accelerated}. We provide easy-to-use code in Python and R and an example that walks through its use at {\tt \href{https://github.com/mpleung/ARD}{https://github.com/mpleung/ARD}}.

Our estimator is motivated by the observation that the task of recovering a network from ARD can be written as a high-dimensional linear regression problem. Without any assumptions on the network, this problem is ill-posed. Our strategy for network recovery is based on the assumption that the latent social network has a low-dimensional structure, namely that its distribution has low effective rank.\footnote{In this paper, a random network with low effective rank is one in which the ratio of the nuclear norm to the Frobenius norm of the expected adjacency matrix is close to 1. See Section \ref{simp} for a formal motivation.} This assumption is inherent in many models used to describe social networks in the statistics and economics literature. Examples include the latent space models used by \cite{breza2017using}, stochastic blockmodels \citep[]{holland1983stochastic}, and degree heterogeneity models \citep{graham2017econometric}.

When a network has low effective rank, we show that the distribution of network links may be recovered from ARD using a nuclear-norm penalty \citep[see generally][Chapter 10]{wainwright2015high}. We derive a finite-sample bound on the mean squared error of our estimator for the distribution of network links by adapting arguments from \cite{negahban2011estimation}. The bound implies that the mean squared error of the estimator is decreasing in the number of traits used in the ARD and increasing in the effective rank of the network. This result can be found in Section \ref{sMSE} and is, to our knowledge, original.

Our paper makes two main contributions to the empirical literature on network estimation. The first contribution is highlighting this connection between the ARD problem and the nuclear-norm penalization literature. Other recent applications of nuclear-norm penalization in economics include \cite{athey2018matrix}, \cite{beyhum2019square}, and \cite{moon2018nuclear}, although the underlying structure of their estimation problems differ from the ARD network recovery problem in important ways. The second contribution is to demonstrate how to implement the nuclear-norm penalization in practice to a general audience. In service of this second contribution, we have tried to make the exposition of this paper and the supporting materials as nontechnical as possible.

\section{ARD as a Regression Problem}

Following \cite{breza2017using}, we consider a population of $N_2$ agents connected in a network. The ideal but infeasible network census is conducted by interviewing every pair of agents $i, j \in \{1, \ldots, N_2\}$ and asking if they have a social connection, which requires $N_{2}^{2}$ questions.
The innovation of \cite{breza2017using} is to instead collect ARD. To collect ARD, the authors first identify a set of $K$ traits. Traits include characteristics like whether an agent has been arrested, remarried, vaccinated, etc. The authors then conduct two surveys. The first survey is a census of all $N_2$ agents and the authors ask the agents to report their traits. The second survey is conducted with a subsample of $N_{1}$ agents ($N_1 \leq N_2$) and the authors ask the agents to report the number of connections they have to agents in the population with each trait. That is, they ask agents how many friends they have who have been arrested, how many friends they have who have been remarried, how many friends they have who have been vaccinated, etc. This alternative to the full network census only requires $(N_{1}+N_{2})K$ questions where $K < N_{1}$ and is easier to implement logistically.

Let $g_{ij}^{*}$ be an indicator for whether agents $i$ and $j$ would report a link if interviewed. Mathematically, ARD is represented by
\begin{equation}
  y_{ki} = \sum_{j=1}^{N_{2}}g_{ij}^{*}w_{kj} \label{ard}
\end{equation}
where for a collection of $K$ traits, $y_{ki}$ measures the number of agent $i$'s connections that have trait $k$ and $w_{kj}$ is an indicator for whether agent $j$ has trait $k$. The goal is to use the ARD $y_{ki}$ and trait data $w_{kj}$ to learn about the network links, $g^{*}_{ij}$.

A key assumption is that the interviewed agents use precisely the relationships of interest $g_{ij}^*$ to construct their responses to the ARD $y_{ki}$. That is, when asked ``How many of your friends have trait $k$?'' respondents count exactly those connections given by $g^*_{ij}$.

\subsection{Regression Formulation}

Let the matrix $Y$ denote the $K\times N_{1}$ collection of ARD $y_{ki}$, $W$ denote the $K \times N_{2}$ collection of traits $w_{kj}$, and $G^{*}$ denote the  $N_{2} \times N_{1}$ collection of links $g^{*}_{ij}$. Equation \eqref{ard} can be written in matrix form
\begin{equation*}
  Y = WG^*.
\end{equation*}

\noindent The problem of recovering $G^{*}$ from $Y$ and $W$ can be viewed as that of finding an $N_{2} \times N_{1}$ matrix $G$ that minimizes the squared-loss
\begin{equation}
  \frac{1}{2} ||Y - WG||_{F}^2 = \frac{1}{2} \sum_{i=1}^{N_{1}}\sum_{k=1}^{K}\left(y_{ki} - \sum_{j=1}^{N_{2}}w_{kj}g_{ij}\right)^{2}. \label{infreg}
\end{equation}
Since it is not generally possible to learn about the existence of a link between two agents that were both not interviewed about ARD in this setting, we take $G$ to be $N_{2}\times N_{1}$ and not $N_{2}\times N_{2}$. \cite{breza2017using} essentially impute the links of agents not surveyed for ARD, which is also straightforward to do here \citep*[see for instance][]{chatterjee2015matrix}.

If the $N_{2} \times N_{2}$ matrix $W'W$ has full rank, then there exists a unique solution to (\ref{infreg})
\begin{equation*}
  G^{*} = (W'W)^{-1}W'Y
\end{equation*}
and $G^{*}$ can be perfectly recovered.
Of course, the assumption that $W'W$ is full rank requires that the number of traits used in the ARD survey exceeds the size of the population ($K \geq N_{2}$), which defeats the whole point of using ARD as a low-cost alternative to a network census. When $W'W$ is not invertible, (\ref{infreg}) is ill-posed, and $G^{*}$ cannot in general be recovered using $Y$ and $W$ without additional information.

Our idea is to exploit the fact that many network formation models of interest, including the latent space model of \cite{breza2017using}, produce networks that have an underlying low-dimensional structure in the sense that the expected adjacency matrix has {\bf low effective rank}. The next subsection explains this observation. Then in Section \ref{estimator}, we propose a new estimator by adding a penalty to the objective function \eqref{infreg} that allows us to exploit the low-dimensional structure and learn about $G^{*}$.

\subsection{Motivation for the Low Rank Assumption}

Loosely speaking, the premise of the high-dimensional regression literature is that it is often possible to recover the parameters of a model like (\ref{ard}) by solving a version of a problem like (\ref{infreg}) if the minimizer is known to have a certain low-dimensional structure. For instance, if $G^{*}$ is a sparse matrix (i.e. very few pairs of agents would report a connection if interviewed) then the network may be recovered using the LASSO, elastic net, or a related technology. Recent examples in network economics include \cite{barigozzi2018nets,belloni2016quantile,de2018recovering,manresa2013estimating,roseidentification}.

\cite{breza2017using} do not assume $G^{*}$ is sparse. They instead specify the link formation rule
\begin{equation}
  g_{ij}^{*} = \mathbbm{1}\{\eta_{ij} \leq \nu_{i} + \nu_{j} + \zeta z_{i}'z_{j}\}, \label{nfm}
\end{equation}
where $\nu_{i}$ is agent $i$'s random effect and $z_{i}$ is agent $i$'s position on the surface of the $p$-sphere (both distributed iid with von Mises-Fisher marginals on the hypersphere), $\eta_{ij}$ is an iid mean-zero logistic error, and $\zeta$ is a scalar. This model has a low-dimensional structure, as discussed formally below. To see this intuitively, note that the model admits a random utility interpretation in which the expected transferable utility $i$ and $j$ receive from forming a link is given by
\begin{equation*}
  u^{*}_{ij} = \nu_{i} + \nu_{j} + \zeta z_{i}'z_{j}
\end{equation*}

\noindent and two agents only form a link if the realized utility exceeds $1/2$. The expected utility matrix $U^{*}$ formed from the $N_{2}\times N_{1}$ collection of $u_{ij}^{*}$ has rank $p+2$ because $z_i$ is $p$-dimensional, while $\nu_i$ is 1-dimensional. Note that \cite{breza2017using} suggest choosing $p=2$ in practice. The important observation is that this rank is low relative to the sample size $N_1$. It is this low-dimensional structure that our proposed methodology exploits. For a more formal discussion of this low-dimensional structure, see Section \ref{simp}.

\subsection{Adding a Nuclear-Norm Penalty}\label{estimator}

Unfortunately, a low-rank structure does not typically allow us to recover $G^*$ from $Y$ and $W$ exactly. However, it is still possible to learn about the distribution of $G^{*}$ by adding a nuclear-norm penalty to the least-squares objective \eqref{infreg}. Intuitively, the nuclear-norm penalty encourages the solution to have low rank, analogous to how the $\ell_1$ penalty for LASSO encourages sparse solutions \citep[][Example 9.8]{wainwright2015high}. We note that the distribution of network links is exactly what is recovered by \cite{breza2017using}, and we echo their motivation that in many applications recovering the distribution of $G^{*}$ is sufficient to address the research question at hand.

First we define the estimand of interest, the distribution of $G^*$. We assume $G^*$ is realized according to the following nonparametric model of network formation, which substantially generalizes \eqref{nfm}:
\begin{equation}
  g_{ij}^* = \mathbbm{1}\{\eta_{ij} \leq f(\alpha_i, \alpha_j)\} \mathbbm{1}\{i\neq j\}, \label{model}
\end{equation}

\noindent where $\eta_{ij}$ is iid with unknown marginal distribution $F_{\eta}$, $\{\alpha_i\}_{i=1}^n$ are unknown vector-valued agent fixed effects, and $f$ is an unknown function. Let $m_{ij}^{*} = E[g_{ij}^*] = F_{\eta}(f(\alpha_{i},\alpha_{j}))$ and $M^{*}$ be the $N_{2} \times N_{1}$ matrix with $ij$th entry $m_{ij}^{*}$. The entries of the matrix $M^{*}$ describe the conditional probability that two agents would report a link if surveyed in a network census given their fixed effects.  The entries of the matrix $M^{*}$ parametrize the distribution of $G^{*}$ and are our object of interest.

To estimate $M^*$, we propose the followng penalized version of \eqref{infreg}
\begin{align}
  \hat M &= \operatornamewithlimits{argmin}_{M\in \mathcal{M}} \hat Q(M), \quad\text{where} \label{freg}\\
  \hat Q(M) &= \frac{1}{2} ||Y-WM||_{F}^2 + \lambda ||M||_{nuc} \nonumber\\
	    &= \frac{1}{2} \sum_{i=1}^{N_{1}}\sum_{k=1}^{K}\left(y_{ki} - \sum_{j=1}^{N_{2}}m_{ij}w_{kj}\right)^{2} + \lambda \sum_{t=1}^{N_{1}}\sigma_{t}(M), \nonumber
\end{align}

\noindent $\lambda$ is a tuning parameter to be chosen by the researcher, $\sigma_t(M)$ is the $t$th singular value of $M$, and $\mathcal{M}$ is a set of matrices.\footnote{For example, $\mathcal{M}$ might be the set of all matrices, in which case we allow for directed and self-links. Alternatively, it might be the set of symmetric matrices with zeros on the diagonal, in which case $\hat M$ is the distribution of an undirected network with no self-links.} The {\em nuclear norm} $||M||_{nuc}$ is large relative to the Frobenius norm $||M||_F$ when the rank of $M$ is large. Hence, adding the nuclear norm penalty encourages the solution $\hat M$ to have low rank. In practice, we recommend choosing the penalty parameter
\begin{equation}
  \lambda = 2\left(\sqrt{N_1} + \sqrt{N_{2}} + 1\right)\left(\sqrt{N_{2}}+\sqrt{K}\right). \label{penalty}
\end{equation}
Details for computing $\hat M$ are given in the next subsection.

As discussed in Section \ref{simp}, in large samples, $\hat M$ closely approximates $M^*$ under certain conditions. The estimate can therefore be used to simulate the distribution of $G^{*}$, used as an input into a second stage model, or used to estimate various network statistics based on $G^{*}$ such as the degree distribution or clustering coefficient. We refer the reader to \cite{breza2017using} for specific applications in development economics.

\subsection{Implementation Details}\label{simp2}

The nuclear norm penalized problem \eqref{freg} can be rewritten as a semidefinite programming problem and solved using tools that are standard in the optimization literature \citep[see generally][]{boyd2004convex}.\footnote{More precisely, this is the case for the unconstrained problem where $\mathcal{M}$ is the set of all matrices.} In practice this formulation is usually computationally intractable. We instead use a fast accelerated gradient descent (AGD) algorithm due to \cite{ji2009accelerated}, which is also used in the simulations of \cite{negahban2011estimation}. We modify the output of the algorithm to impose the (optional) constraint that the network is undirected with no self-links.\footnote{The approximation guarantees in \cite{ji2009accelerated} are for the unconstrained problem, but our simulations in Section \ref{ssims} show that our modification to impose the constraint performs well in practice.} A complete description of the algorithm can be found in Appendix \ref{AGDalgo}.

In our simulations in Section \ref{ssims}, the algorithm rapidly computes $\hat M$ for populations with hundreds of agents. For example, when $N_1=N_2=500$, it computes an estimate for the latent space model (Example \ref{e1}) in about five seconds on a laptop with a 2.6 GHz processor and 8 GB RAM. The Bayesian estimation procedure of \cite{breza2017using} can be computationally costly if the dimension of the latent space or the number of Markov chain draws required for the convergence of the MCMC algorithm is large. The AGD algorithm proposed here does not depend on these parameters.

\section{Why the Estimator Works}\label{simp}

The basic idea behind our estimator \eqref{freg} is that the nuclear-norm penalty encourages the solution to have a nuclear norm $||\hat M||_{nuc}$ close to its Frobenius norm $||\hat M||_F$, which yields a matrix with small effective rank. Under certain conditions, $\hat M$ will closely approximate $M^*$. This is shown formally in Proposition \ref{mainresult} of Appendix \ref{stheory}, whose proof applies a result due to \cite*{negahban2011estimation}.

Before discussing the proposition, let us define what we mean by effective rank. Recall that the {\em rank} of $M^{*}$ is given by the number of nonzero singular values of $M^{*}$. The {\em effective rank} of $M^{*}$ is the squared ratio of its nuclear norm to its Frobenius norm. Formally, let $\sigma_{t}(M^{*})$ be the $t$th singular value of $M^{*}$ for $t \in \{1, \dots, N_1\}$. Then the effective rank of $M^{*}$ is given by
\begin{equation*}
ER(M^{*}) = \left(\frac{||M^{*}||_{nuc}}{||M^{*}||_{F}}\right)^2 = \frac{\left(\sum_{t=1}^{N_{1}}\sigma_{t}(M^{*})\right)^{2}}{\sum_{t=1}^{N_{1}}\sigma_{t}(M^{*})^{2}}.
\end{equation*}
This ratio gives a measure of matrix rank because the numerator is always larger than the denominator and the two are only similar in magnitude when most of the spectral values of $M^{*}$ are close to zero. That is, $ER(M^{*})$ is only close to $1$ when $M^{*}$ is well-approximated by a low-rank matrix.

For many popular choices of $F_{\eta}$ and $f$, $M^{*}$ has small effective rank when $\alpha_{i}$ is relatively low-dimensional. In such cases, it is possible to estimate $M^*$ using $Y$ and $W$ using our proposed estimator. We next provide three examples popular in practice, which also form the basis of our simulations in Section \ref{ssims}. To simplify the exposition, we take $N_{1} =N_{2} = n$.

\begin{example}[Latent Space Model]\label{e1}
One way to interpret the \cite{breza2017using} model is as a variation on the latent space model of \cite{hrh2002} where
  \begin{equation*}
  m_{ij}^* = F_{\eta}(\nu_i + \nu_j - \norm{z_i-z_j}_{2}),
  \end{equation*}
\noindent  $\norm{\cdot}_{2}$ is the Euclidean norm, $z_i \in \mathbb{R}^p$, and $F_{\eta}$ is the logistic distribution function. Table \ref{effrank} displays the effective rank of this latent space model for $\{\nu_i\}_{i=1}^n \stackrel{iid}\sim \mathcal{N}(0,1)$, $\{z_i\}_{i=1}^n \stackrel{iid}\sim \mathcal{U}([0,1]^2)$, and various values of $n$.
\end{example}
\vspace{5mm}

\begin{example}[Random Dot Product Graph]\label{e2}
The random dot product graph model is a popular class of models in the social networks literature \citep{athreya2017statistical,young2007random}. A simple example is
  \begin{equation*}
    m_{ij}^* = U_i^{1/2}U_j^{1/2}
  \end{equation*}
  \noindent where $\{U_i\}_{i=1}^n \stackrel{iid}\sim \mathcal{U}([0,1])$. Table \ref{effrank} displays the effective rank of this random dot product graph model for various values of $n$.
\end{example}
\vspace{5mm}

\begin{example}[Stochastic Block Model]\label{e3}
  The stochastic block model is widely studied in the statistics literature to evaluate community detection algorithms \citep[see generally][]{abbe2017community,rohe2011spectral}. Agents are assigned one of $L$ possible types. Let $z_{il}$ be an indicator for whether agent $i$ has type $l$. The probability that agents form links is then given by
  \begin{equation*}
  m_{ij}^{*} = \sum_{l_{1}=1}^{L}\sum_{l_{2}=1}^{L}z_{il_{1}}z_{jl_{2}}\theta_{l_{1}l_{2}}
  \end{equation*}
where $\theta_{l_{1}l_{2}}$ is the probability that an agent with type $l_{1}$ forms a link with an agent with type $l_{2}$. Table \ref{effrank} displays the effective rank of this stochastic blockmodel for $\theta_{l_{1}l_{2}} = .3$ if $l_{1} \neq l_{2}$,  $\theta_{l_{1}l_{2}} = .7$ if $l_{1} = l_{2}$, $L = 5$ equally sized groups, and various values of $n$.
\end{example}

Simulation evidence given in Table \ref{effrank} shows that the effective ranks of networks generated from the three examples are small.

\begin{table}[ht]
\centering
\captionsetup{justification=centering}
\caption{Effective Ranks}
\begin{threeparttable}
\begin{tabular}{lrrrrrr}
\toprule
$n$ &  50  &  100 &  200 &  300 &  400 &  500 \\
\midrule
LSM & 2.50 & 2.70 & 2.84 & 2.92 & 2.97 & 3.00 \\
RDP & 1.97 & 1.99 & 1.99 & 2.00 & 2.00 & 2.00 \\
SBM & 3.15 & 3.27 & 3.33 & 3.36 & 3.37 & 3.37 \\
\bottomrule
\end{tabular}
\begin{tablenotes}[para,flushleft]
  \footnotesize $n = N_1 = N_2$. Cells are averages over 500 simulations. LSM $=$ latent space model, RDP $=$ random dot product graph, SBM $=$ stochastic block model.
\end{tablenotes}
\end{threeparttable}
\label{effrank}
\end{table}

\subsection{Mean Squared Error}\label{sMSE}

We adapt arguments from \cite{negahban2011estimation} to derive a finite-sample bound on the mean-squared error of $\hat{M}$. This can be found in Appendix \ref{stheory}. In large samples and under certain assumptions, the bound can be well approximated by the following simple relationship
\begin{equation*}
  \frac{1}{N_{1}N_{2}}\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\left(\hat{m}_{ij} - m_{ij}^{*}\right)^{2} \leq C\times\frac{ER(M^{*})}{K}
\end{equation*}
where $C$ is a constant. That is, the mean squared error is eventually bounded by the ratio of the effective rank of $M^{*}$ over the number of traits used to construct the ARD.

This bound matches the analogous (but fundamentally different) result for the matrix regression of \cite*{negahban2011estimation} (see their discussion after Corollary 3) and their intuition is as follows. If $M^{*}$ has rank $R$ then it can be described with $(N_{1}+N_{2})R$ parameters. To learn these parameters, ARD contains exactly $N_{1}K$ observations. Supposing $N_{2}/N_{1}$ is bounded, the ratio of the two gives our effective sample size which is, intuitively, the number of observations available to estimate each parameter. It is this ratio that fundamentally determines our bound. To be clear, we expect a similar rate of convergence for any procedure that uses the $N_{1}\times K$ dimensional ARD to learn the $N_{2}\times R$ parameters of a latent space model.

We remark that the optimal mean squared error for $\hat{M}$ when $G^*$ is observed (i.e. $K = N_{2}$) is on the order of $\frac{\ln(N_{2})}{N_{2}}$ \citep[see for instance][]{gao2015rate}. It seems reasonable to us that convergence at a $K$ rate instead of a $N_{2}$ rate is the price to pay for using the relatively low-dimensional ARD to substitute for high-dimensional network data.

If the goal of the researcher is to use $\hat{M}$ as a substitute for $M$ in a second-stage estimation procedure (for example, to construct estimates of network statistics to include in a linear regression model), then it may be the case that $K$ need not be taken to be too large for the estimation error of these network statistics around their population analogs to be unimportant. This is the premise of the literature on semiparametric estimation \cite*[see generally][]{powell1994estimation}. In the simulations below we consider $K = \sqrt{N_1}$ which is consistent with choosing an ARD survey with about ten traits to recover the structure of a network with 100 agents. Note that the villages in \cite{banerjee2013diffusion} contain 223 households on average. In the cost savings exercise in section 4 of \cite{breza2017using}, they consider a 30 percent sample, which corresponds to $N_1 \approx 67$. Consequently, we would only survey about $K = 8$ traits in practice in this setting.

\subsection{Simulation Results}\label{ssims}

We compute $\hat{M}$ for the three models for $M^*$ from Examples \ref{e1}--\ref{e3}, which take $N_1=N_2=n$. We construct $W$ as a $K\times n$ matrix of iid Bernoulli$(0.5)$ random variables, where $K$ equals $\sqrt{n}$ rounded to the nearest integer, following the discussion in the previous subsection. Table \ref{simresults} displays the mean-squared error $n^{-2} \sum_{i=1}^n \sum_{j=1}^n (M_{ij}^* - \hat M_{ij})^2$. Even for relatively small values of $n$ and $K$ this error is close to zero and generally decreases with the network size $n$.

\begin{table}[ht]
\centering
\captionsetup{justification=centering}
\caption{Mean-Squared Error}
\begin{threeparttable}
\begin{tabular}{lrrrrrr}
\toprule
$n$  &      50 &     100 &     200 &     300 &     400 &     500 \\
\midrule
LSM & 0.04334 & 0.03209 & 0.02914 & 0.02819 & 0.02718 & 0.02685 \\
RDP & 0.03793 & 0.02436 & 0.02072 & 0.01917 & 0.01757 & 0.01687 \\
SBM & 0.05559 & 0.04255 & 0.03908 & 0.03787 & 0.03677 & 0.03616 \\
\bottomrule
\end{tabular}
\begin{tablenotes}[para,flushleft]
  \footnotesize $n = N_1 = N_2$. Cells are averages over 500 simulations. LSM $=$ latent space model, RDP $=$ random dot product graph, SBM $=$ stochastic block model. The number of traits is $\sqrt{n}$ (rounded). The penalty is \eqref{penalty}.
\end{tablenotes}
\end{threeparttable}
\label{simresults}
\end{table}

\section{Conclusion}

Our purpose in writing this paper is to illustrate how nuclear-norm penalized least squares can be used to recover the structure of a latent network using ARD. We adapt arguments from \cite{negahban2011estimation} and demonstrate how in many cases the distribution of network links can be recovered in a nonparametric frequentist framework. We agree with \cite{breza2017using} that there are many open econometric and practical questions about how ARD ought to be collected and how to formally estimate and make inferences about the underlying parameters of a network formation model. We also think this is an important area for future econometric work.

\footnotesize

\bibliographystyle{aer}

redpajama_set_name: RedPajamaArXiv