\section{Proof of Convergence}\label{appsect}
























\subsection{Notation and conventions}




In what follows, we will need some notation for  tensor manipulation.   First, we recall  the matrix inner product, which for two matrices $A = (a_{i,j})_{n\times m}, B = (b_{i,j})_{n\times
m}$, is defined as $A:B = \sum_{i,j} a_{i,j}b_{i,j}$. Also, a matrix gradient
of a real (vector) valued function is matrix (tensor) valued, with an element-wise
representation as  $\frac{\partial f }{\partial v_{(i,j)}^k} = \left(\frac{\partial
f }{\partial v_{(i,j)}^{a,b;k}}\right)_{l_i\times l_j}$ and $\frac{\partial
H_m^k }{\partial v_{(i,j)}^k}= \left(\frac{\partial H_m^{c;k} }{\partial
v_{(i,j)}^{a,b;k}}\right)_{l_i\times l_j\times l_m}$.  

In all future estimates, we look at backpropagation over a single input, meaning $J = 1$. This allows us to suppress the variable $p$, which is essentially done for the sake of presentation.  The proofs of Theorem \ref{bigtheo} and Lemma \ref{simplem} generalize immediately to the case of multiple inputs by taking sums over all inputs. Finally, in our estimates, we will use the constant $C>0$ which depends solely on fixed parameters in the network, such as the input value $x$, uniform bounds of node outputs $H_j$ and inputs $S_j$, and for generalizing to multiple inputs, the size of the dataset $J$. The constant $C$ is used in multiple estimates, and may increase for each time it appears.

 \subsection{Estimates on node output increments}

Our  major technical theorem shows that the increment of outputs $\Delta H^{k+1}$   is
similar, up to first order, to $Q^k(H^k)$, where  $Q^k$ denotes the differential operator
\begin{equation}\label{qeqn}
Q^k =\sum_{i<j\le L}  \Delta v_{(i,j)}^{k+1}:\frac{\partial }{\partial v_{(i,j)}^{k}}.
\end{equation}  
Note that when $Q^k$ acts on a  length $l_m$ vector, the matrix inner product in (\ref{qeqn})
is between a $l_i \times l_j$-sized matrix and a $l_i\times l_j \times l_m$-sized tensor, and is vector of size $l_m$.

The major utility of introducing $Q^k$ is that it provides a simple bound
when acting on $E^k$.  Specifically, using (\ref{defq}) , (\ref{itdef}),
and (\ref{taudef}), it is straightforward to show
\begin{equation}
Q^k(E^k)\le (-\eta+\tau)\sum_{i<j \le L}\|q_{(i,j)} ^k\|^2. \label{midest}
\end{equation}
     
    
\begin{theorem}\label{bigtheo}

There exists a universal constant $C>0$ such that

\begin{equation}
|Q^k(E^k)-\Delta E^{k+1}| \le C\left(\sum_{n\le L}\|\Delta H_n^k\|^2 + \sum_{m<n\le
L}\|\Delta v_{(m,n)}^k\|^2\right). \label{th1bnd}
\end{equation}
\end{theorem}

\begin{proof} We show (\ref{th1bnd}) follows through three steps: (1) finding a recurrence relation, with respect to the ordering of hidden layers, for $Q^k(H^k_n)$, (2) finding a similar relation for $\Delta H^{k+1}$, and (3) comparing the two relations.
 
 \textit{(1) (A recurrence for $Q^k(H_n^k)$).} Applying the  chain rule to the total error (\ref{edef}), using (\ref{nodeeqn}),
 and rearranging sums, \begin{align}\label{crule1}
Q^k(E^{k}) = g'(S_L)\sum_{i<j\le L} \Delta v_{(i,j)}^{k+1}:
\frac{\partial }{\partial v_{(i,j)}^k}\left(\sum_{m<L}H_m^{k}v_{(m,L)}^k
 \right)\\\\  =   g'(S_L)\sum_{m<L}\sum_{i<j\le L} \Delta v_{(i,j)}^{k+1}:
\frac{\partial }{\partial v_{(i,j)}^k}\left(H_m^{k}v_{(m,L)}^k \right) \label{qeform}.
\end{align}

We now focus on expressing (\ref{qeform}) in a more compact form. We begin with considering the terms in (\ref{qeform}) with $j = L$. We first work elementwise by differentiating with respect to  the $(a,b)$ entry of the matrix derivative for the tensor $\frac{\partial }{\partial v_{(i,j)}^k}\left(H_m^{k}v_{(m,L)}^k of \right)$. From the product rule,  this can be written as a sum of vectors, with
\begin{align} \label{msplit}
&\frac{\partial }{\partial v_{(i,L)}^{a,b;k}}\left( H_m^{k}v_{(m,L)}^k \right)
= \frac{\partial  H_m^{k} }{\partial v_{(i,L)}^{a,b;k}}v_{(m,L)}^k + H_m^{k}
\frac{\partial v_{(m,L)}^k }{\partial v_{(i,L)}^{a,b;k}}\\
  &=  \frac{\partial  H_m^{k} }{\partial v_{(i,L)}^{a,b;k}}v_{(m,L)}^k +
(0, \dots,\underbrace{ \delta_{i,m}H_m^{a;k}}_{\hbox{ $b^{th}$ entry}}, \dots,
0)\\
&:=A_{i,m}^{a,b;k}+B_{i,m}^{a,b;k}.  \label{msplit2}
\end{align} 
 
Each of these terms is handled in turn.  First, summing the matrix inner product of the matrix $\Delta v_{(i,L)}^{k+1}$ and the tensor $A_{i,m}^k$  may be rewritten as
\begin{align}
\sum_{m<L}\sum_{i< L} \Delta v_{(i,L)}^{k+1}:A_{i,m}^k 
  &= \sum_{m<L} \sum_{i<L} \sum_{\substack{a<l_i\\b<l_L}}\Delta v_{(i,L)}^{a,b;k+1}\frac{\partial
 H_m^{k} }{\partial v_{(i,L)}^{a,b;k}}v_{(m,L)}^k\\
&= \sum_{m<L} \sum_{i< L} \left(\Delta v_{(i,L)}^{k+1}:\frac{\partial H_m^k }{\partial
v_{(i,L)}^k}\right)v^k_{(m,L)}.
 \label{nondiag}
\end{align}

For $B_{i,m}^k$, we again work elementwise, and write the inner product as
\begin{align}
&\sum_{m<L}\sum_{i< L} \Delta v_{(i,L)}^{k+1}:B_{i,m}^k
  = \sum_{m<L} \sum_{\substack{a\le l_i\\b\le l_L}}\Delta v_{(m,L)}^{a,b;k+1}B_{m,m}^{a,b;k}\\
     &=\sum_{m<L}\left(\sum_{b<l_L}H_m^{1,k}\Delta v_{(m,L)}^{1,b;k+1}, \dots,
\sum_{b<l_L}H_m^{l_m,k}\Delta v_{(m,L)}^{l_m,b;k+1}\right)\\&=\sum_{m<L}H_m^k\Delta
v_{(m,L)}^{k+1}.\label{diag}
\end{align}

Calculations for double sum in (\ref{qeform}) for the remaining terms with $j<L$ are similar to the case $j = L$, except that there is
no corresponding $B_{i,m}^k$ term. Indeed, we can show
\begin{align} 
\sum_{m<L}\sum_{i<j< L} \Delta v_{(i,j)}^{k+1}:
\frac{\partial }{\partial v_{(i,j)}^k}\left(H_m^{k}v_{(m,L)}^k \right) 
 = \sum_{m<L}\sum_{i<j< L}\Delta v_{(i,j)}^{k+1}:\left(\frac{\partial H_m^k}{\partial
v_{(i,j)}^k}v_{(m,L)}^k\right). \label{lessj} \end{align}
Combining (\ref{nondiag}), (\ref{diag}) and (\ref{lessj}),

  \begin{align}
 &\sum_{m<L}\sum_{i<j\le L} \Delta v_{(i,j)}^{k+1}:
\frac{\partial }{\partial v_{(i,j)}^k}\left( H_m^{k}v_{(m,L)}^k \right) \label{bigsumrewrite}\\
&= \sum_{m<L}H_m^k\Delta v_{(m,L)}^{k+1} 
+\sum_{m<L}\sum_{i<j\le m}\Delta v_{(i,j)}^{k+1}:\left(\frac{\partial H_m^k}{\partial
v_{(i,j)}^k}v_{(m,L)}^k  
 \right) \label{firstrep}\\
 &= \sum_{m<L}\left(H_m^k\Delta v_{(m,L)}^{k+1} +Q^k(H^k_m)v^k_{(m,L)}  
\right).
\end{align}
Note that \ref{firstrep} uses the fact that since $H_m^k$ only depends on layers $1$ through $m-1$, we may truncate the sum of $Q^k$ and write\begin{equation}
Q^k(H_m^k) =\sum_{i<j\le m}  \Delta v_{(i,j)}^{k+1}:\frac{\partial H_m^k
}{\partial v_{(i,j)}^k}.
\end{equation}
We may now substitute (\ref{bigsumrewrite}) into (\ref{qeform}) to yield the recursive formula
\begin{align}
Q^k(E^k)=  g'\left(S_L^k \right)\sum_{m<L}\left( H_m^k\Delta v_{(m,L)}^{k+1}+Q^k(H^k_m)v^k_{(m,L)}
  \right).
\end{align}
From similar calculations, the formula over a node $H^k_n$, with $n<L$, is
\begin{align}
Q^k(H^k_n)= g'\left(S_n^k\right)\sum_{m<n}\left( H_m^k\Delta v_{(m,n)}^{k+1}+Q^k(H^k_m)v^k_{(m,n)}
  \right).\label{qrec}
\end{align}

\textit{(2) (A recurrence for $\Delta H_n^{k+1}$).} A recursive formula for   $\Delta H^{k+1}_n$ is found through a Taylor expansion of $E(S_L^{k+1})$ centered at $S_L^k$. Specifically, there exists $t_{k}$ between $E^{k}$
and $E^{k+1}$ with
\begin{align}
\Delta E^{k+1} &=  g'\left(S_L^{k} \right)\Big(\sum_{m < L} \Delta( v_{(m,L)}^{k+1}\cdot H_m^{k+1}) \Big)+g''(t_{k})\left(\sum_{m < L}\Delta( v_{(m,L)}^{k+1}\cdot H_m^{k+1})\right)^2\\
 &=  g'\left(S_L^{k} \right)\Big(\sum_{m < L} \Delta H_m^{k+1}
v_{(m,L)}^k +H^k_m\Delta v_{(m,L)}^{k+1}
+\sum_{m < L}\Delta v_{(m,L)}^{k+1}\cdot \Delta H_m^{k+1} \Big)
\\&+g''(t_{k})\left(\sum_{m < L}\Delta( v_{(m,L)}^{k+1}\cdot H_m^{k+1})\right)^2.
\end{align} 
Similarly,there exist $t_{n,k} = (t_{n,k}^{1}, \dots, t_{n,k}^{l_l})$ where each
$t_{n,k}^r, r = 1, \dots l_n$ lies between $H_n^k$ and $H_n^{k+1}$ and
\begin{align}
&\Delta H_n^{k+1} = g'\left(S_n^k \right)\Big(\sum_{m < n}\Delta H_m^{k+1}v_{(m,n)}^k
 +H^k_m\cdot\Delta v_{(m,n)}^{k+1}
+\sum_{m < n}\Delta H_m^{k+1}\Delta v_{(m,n)}^{k+1}  \Big)
\\+&\frac 12g''(t_{n,k})\left(\sum_{m < n}H_m^{k+1}\Delta v_{(m,n)}^{k+1}
\right)^2\label{diffrec}. 
\end{align}


\textit{(3) (Comparing recurrences).}
From (1) and (2) of Assumptions \ref{assumes}, we may derive the simple bound
\begin{equation}
\|\Delta H_m^{k+1}\Delta v_{(m,n)}^{k+1}\| \le C( \|\Delta v_{(m,n)}^{k+1}\|^2+\|\Delta
H_m^{k+1}\|^2)
\end{equation}
for some constant $C>0$. 
Taking differences of (\ref{diffrec}) and (\ref{qrec}),
for any $n<L$,  we then obtain the recurrence inequality
\begin{align}
&\|Q^k(H_n^{k})-\Delta H_n^{k+1} \|\le C\left(\sum_{m < n}\|Q^k(
H_m^{k})-\Delta H_m^{k+1} \|  \right)  \label{rec1}\\&+ C\sum_{m<n} ( \|\Delta v_{(m,n)}^{k+1}\|^2+\|\Delta
H_m^{k+1}\|^2) \label{mainrec1}.
\end{align}
Replacing $H_n^k$ with $E^k$ in (\ref{rec1}) produces the same type of inequality,
with the sum in (\ref{mainrec1}) now ranging from $m = 1, \dots, L-1$. Repeated
applications of (\ref{mainrec1}) to  $E^k$ and subsequently to $H_n^k$,
for $n = 1, \dots, L-1$, result in   
\begin{align}
&|Q^k(E^k)-\Delta E^{k+1}|\le C\left(\|Q^k( H_0^{k})-\Delta H_0^{k+1} \|  \right)
\\&+ C\left(\sum_{n< L}\|\Delta H_n^k\|^2 + \sum_{m<n< L}\|\Delta v_{(m,n)}^k\|^2\right)
\label{mainrec}.
\end{align}
To complete the proof, we note that
 the input data $x$ does not change under iterations, so \begin{equation}
Q^k( H_0^{k})-\Delta H_0^{k+1} \equiv 0.
\end{equation}
\end{proof}


 We now bound the quadratic terms in (\ref{th1bnd}).

\begin{lemma}\label{simplem}
For some constant $C>0$,

\begin{enumerate}
\item
\begin{equation}
\|\Delta v^k_{(m,n)}\| \le (\eta+\tau)\|q_{(m,n)}^k\| \label{fstpart}
\end{equation}
\item 
\begin{equation}
\|\Delta H^k_n\| \le C(\eta+\tau)\sum_{m<n}\|q_{(m,n)}^k\|
\end{equation}
\end{enumerate}
\end{lemma}
\begin{proof}
We may show (\ref{fstpart}) immediately from (\ref{itdef}) and (\ref{taudef}).
For the next inequality, note that from Taylor's theorem, and the boundedness
of $g'$ and  $g''$:

\begin{align}
\|\Delta H^{k+1}_n\| \le |g'(S_n^k)|\left \|\Delta\left(\sum_{m < n} H_m^{k+1}v_{(m,n)}^k
 \right)\right \|\\ +\frac 12|g''(t_{n}^k)|\left \|\Delta\left(\sum_{m <
n}H_m^{k+1}v_{(m,n)}^k \right)^2\right \|.
\end{align}
From the boundedness Assumptions (1) and (2), we may use (\ref{fstpart}) to rewrite this as 
\begin{align}
&\|\Delta H^{k+1}_n\| \le C \sum_{m < n}\|\Delta v^k_{(m,n)}\|+\|\Delta v^k_{(m,n)}\|^2\\
&\le C(\tau+\eta)(\sum_{m< n}\|q_{(m,n)}^k\|+\|q_{(m,n)}^k\|^2) \le C(\tau+\eta)\sum_{m
< n}\|q_{(m,n)}^k\| .
\end{align}
 The last inequality uses the fact that from Assumption (2), we may uniformly
bound gradients. 
\end{proof}


Now, combining Theorem \ref{bigtheo}, (\ref{midest}), and Lemma \ref{simplem},
the iteration of error may then be estimated as 
\begin{align}
\Delta E^{k+1} &\le  C\left(\sum_{n\le L}\|\Delta H_n^k\|^2 + \sum_{m<n\le
L}\|\Delta v_{(m,n)}^k\|^2\right)+Q^k(E^k)
\\&\le \left(-\eta+\tau+C(\tau^2+\eta^2)\right) \sum_{m<n \le L} \|q_{(m,n)}^k\|^2.
\label{graddif}
\end{align}

\subsubsection{Proof of convergence}

We now use a Lemma found in  \cite{sun2006}:

\begin{lemma}\label{canned}
Let $f \in C^1( \mathbb R^n, \mathbb R)$, and suppose that  $\nabla f$ vanishes
at a finite set of points.  Then, for a sequence $\{x_k\}$ if $\|\Delta x^k\|
\rightarrow 0$ and $\|\nabla f(x^k)\|\rightarrow 0$, then for some $x^* \in
\mathbb R^n$,  $x^k \rightarrow x^*$ and $\nabla f(x^*) = 0$.
\end{lemma}

For some $s \in (0,1)$, assume $\eta = s\tau $.  It is straightforward to show that the term in
front of the norms in \ref{graddif} is negative when

\begin{align}
\eta < \frac{1-s}{C(s^2+1)}.
\end{align}
Under this constraint, $E^k$ is decreasing under each iteration. The summability
for $\|q_{2}^k\|^2$ also follows, since
\begin{align}
\sum_{k = 1}^\infty \|q_{(i,j)}^k\|^2 \le\frac 1{\left(\eta-\tau- C(\tau^2+\eta^2)\right)}
\sum_{k = 1}^\infty \Delta E^k <\infty.   
\end{align}
Thus  $\|q_{1}^k\|\rightarrow 0$ and, from (\ref{fstpart}),  $ \|\Delta v_{(i,j)}^k\|\rightarrow 0.$
Lemma \ref{canned}
and part (3) of Assumption 2 imply a set of minimum weights $v^*_{1}, v_2^*, z^*, w^*$,
which determine a local minimum of $E$. This shows Theorem \ref{maint2}.

\section{ARCHITECTURE FOR A FEED-FORWARD NETWORK
WITH CROSS-LAYER CONNECTIVITY}
\label{sec:architecture}

In this section, we formally explain  DAG architectures, and the associated backpropagation algorithm with momentum.  We then state a theorem for the convergence of error for backpropagation whose proof is presented in Section \ref{appsect}.






\subsection{DAG architecture and backpropagation}
We now present the architecture for neural networks on DAGs. Nodes of a  DAG can always be ordered into layers $0, \dots, L$, in which directed edges always point to layers labeled with higher indices.  Layer 0, having $l_0$ nodes,  accepts the input training values $x^p \in \mathbb R^{l_0}$, over $ p = 1, \dots, J$.  For each layer $i$  from 1 through $L$, there are $l_i$ nodes. Under this ordering, define $v_{(i,j)}^{l,m}$ as the weight between node $l$ in layer $i$ and node $m$ in layer $j$, where $i<j$. Let $v_{(i,j)}$ denote the matrix of weights from layer $i$ to $j$. Over all nodes, we use a single (possibly nonlinear) activation function $g:\mathbb R\rightarrow \mathbb R$  for the determination of output values. 

The explicit output values of the $l_j$ nodes in layer $j$ are denoted as
\begin{equation}
H_j = (H_j^1, \dots, H_j^{l_j}), \quad 0 \le j \le L.
\end{equation}
These are defined recursively from forward propagation, where the $j$ layer receives input from all layers $H_i$ with $i<j$. Explicitly,
\begin{align}
&H_0 = x,  &&H_1 = g\left(H_0 v_{(0,1)} \right),\\
&H_j = g\left(\sum_{i < j} H_iv_{(i,j)} \right),  &&H_L = y = g\left(\sum_{i <L } H_iv_{(i,L)} \right).\label{nodeeqn}
\end{align}  
 Note that here, and in the future, for
a real valued function $f$, and a vector $v= (v_1, \dots, v_n)$, we will use
the notation $f(v) = (f(v_1), \dots, f(v_n))$. Node inputs are defined as 
 \begin{equation}
 S_j= \sum_{i < j} H_iv_{(i,j)}.
 \end{equation}
 
We seek to minimize the difference between a set of  $J$ desired outputs $d^1, \dots, d^J \in \mathbb{R}^{l_L}$, and corresponding actual outputs  $y^1, \dots, y^J \in \mathbb{R}^{l_L}$. We measure the distances between desired and actual output with the total quadratic error
\begin{equation}
E = \sum_{j = 1}^J \|d^j-y^j\|/2. \label{generrordef}
\end{equation}
Gradients of the error with respect to weights are then defined as
\begin{equation}\label{defq}
\frac{\partial E}{\partial v_{(i,j)}^{l,m}} =  q_{(i,j)}^{l,m}.
\end{equation}

The iteration of weights by backpropagation is done through gradient descent with momentum. Here and in the future, a superscript $k$ is used as an iteration variable, and $\Delta x^k = x^k - x^{k-1}$ for any quantity $x$.   Weights are updated as

\begin{equation}\label{itdef}
\Delta v^{m,l;k+1}_{(i,j)}= \tau^{m,l;k}_{(i,j)}\Delta v^{m,l;k}_{(i,j)}
- \eta q^{m,l;k}_{(i,j)}.
\end{equation}
The second term is (\ref{itdef}) corresponds to traditional backpropagation through gradient descent, while first term, for a predetermined $\tau \in (0,1)$, is the contribution from adaptive momentum, where
\begin{equation}\label{taudef}
\tau^{m,l;k}_{(i,j)} = \begin{cases}\frac{\tau\|q^{m,l;k}_{(i,j)}\|}{\|\Delta
v^{m,l;k}_{(i,j)}\|} &  \|\Delta v^{m;k}_{(i,j)}\| \neq 0,\\
0  & \mathrm{otherwise}. \\
\end{cases}
\end{equation}
The norm $\|v\|$ denotes the usual Euclidean norm for a vector $v$. When the norm acts on a matrix $A = (a_{i,j})_{n\times m}$, it is treated as a
length $n\cdot m$ vector, with $\|A\|^2 = \sum_{i,j} a_{i,j}^2$. This choice of momentum was also used in \cite{zhang2006}. Note that  we sometimes place a variable denoting iteration after a semicolon to distinguish it from node indices.  

\subsection{Convergence of backpropagation}

Our major theorem is a statement of convergence under backpropagation with momentum.   Specifically, for some input $x^j \in l_0$, we will use a generic desired output of $d^j \in \mathbb{R}$. We use a 1-d output for clarity in exposition.  The proof of convergence for output in multiple dimensions is essentially the same as the one presented here. The error in this case is then
\begin{equation}
E = \sum_{j = 1}^J |d^j-y^j|/2: =  \sum_{j = 1}^J g_j(y_j). \label{edef}
\end{equation}


We will need some regularity and boundedness assumptions.  These assumptions are similar to those used in \cite{wu2008convergence}, and may also be found in other nonlinear optimization problems such as \cite{gori1996}. 
\begin{ass} \label{assumes}
\hspace{0.5em}
\begin{enumerate} 
\item The function $g$, and its first two derivatives $g'$ and $g''$ are bounded in $\mathbb R$.
\item The weights $v_{(i,j)}^k$ are uniformly bounded over layers $1 \le i<j \le L$ and iterations $k = 1, 2, \dots.$
\item The gradient $\nabla E$ vanishes only at a finite set of points.
\end{enumerate}
\end{ass}

It readily follows from these two assumptions that we may also uniformly bound  $q_{(i,j)}^k, H_i^k,g_p, g_p',$ and  $g_p''$.  Note that we do not assume boundedness of weights connected to the input layer.

\begin{theorem}\label{maint2}
Under assumptions (1) and (2), for any $s \in (0,1)$ and  $\tau = s\eta$, there exists $C>0$ such that if 
\begin{equation}
\eta < \frac{1-s}{C(s^2+1)},
\end{equation}
then for $k = 1,2,\dots$, 
\begin{align}
&E^k = E(v_{(i,j)}^k ) \rightarrow E^* \quad 1\le i<j\le L,\\
&q^k_{(i,j)} \rightarrow 0.
\end{align}

If part (3) of the Assumptions is satisfied, weights $v_{(i,j)}^k\rightarrow v_{(i,j)}^*$, and $E^* = E(v_{(i,j)}^*)$ is a local  minimum.
\end{theorem}

The constant $C$ used is solely dependent on fixed parameters form the network, and the uniform bounds from the Assumptions. A complete proof for Theorem \ref{maint2} is provided in Section \ref{appsect}.



\section{Experiments}
\label{experiment}
We evaluate the effectiveness of our proposed architecture by implementing the cross-connections on different MLP and CNN frameworks. The main purpose of the following experiments was not to design the architecture which gives state-of-the-art performance, but to introduce the idea of using cross-connections to existing sequential architectures. We compare the result of  cross-connected architectures with their sequential counterparts, and with other previously proposed architectures for both image classification and compression tasks.

\begin{figure*}[!ht]
\centering
\begin{center}
\begin{tabular}{cc}
  \includegraphics[width=65mm,height=50mm]{graph1.eps} &   \includegraphics[width=65mm,height=50mm]{graph2.eps} \\   (a) & (b) \\[6pt]
 \includegraphics[width=65mm,height=50mm]{graph3.eps} &   \includegraphics[width=65mm,height=50mm]{graph4.eps} \\    (c) & (d) \\[6pt]
\end{tabular}
\end{center}•
\caption{Comparison of the cross-entropy training loss between various architectures and their CrossNet counterparts. The different architectures experimented with are (a) 2-layer-25-neurons, (b) 2-layer-50-neurons, (c) 2-layer-800-neurons, and (d) 3-layer-1024-neurons.}
\label{figure3}
\end{figure*}

\subsection{Image Classification}
\subsubsection{Dataset 1: MNIST}
\label{MNIST}
We performed experiments on hand-written digit classification problem \cite{lecun1998mnist} where input patterns are  digits. The samples are $28\times28$ binary pixel images. The train and test sets contain 60k and 10k images respectively, and we hold out 10k training images as a validation set. The task is to classify the images into 10 digit classes. Table \ref{table1} compares the performance of adding cross-connections to different MLP and convolutional architectures. The best performing neural networks for the permutation invariant setting achieved an error of about 1.60\% \cite{simard2003best}. With the addition of two cross-connections, one between the input and later hidden layer and the second between the early hidden layer and the output, we achieve an error of about 1.26\%. A neural net (3 layers and 1024 neurons without max-constraints) with cross-connections achieves an error of about 1.10\% as compared to a 1.25\% error for a sequential network with same architecture using dropouts \cite{srivastava2014dropout}. A 2-Convolutional layer network gave an error rate of 1.41\%, whereas a CrossNet version of the same achieved a large improvement by reducing the error to 1.15\%.

Table \ref{table2} illustrates a comprehensive result on the MNIST dataset without data augmentation. In Table \ref{table1}, our main focus was to analyze the performance of adding cross-connections to various sequential feed-forward architectures, whereas in Table \ref{table2}, we designed a CrossNet architecture in order to achieve state-of-the-art performances. Training such big networks with MNIST commonly gives generalization error. An error rate of 0.53\% was achieved in \cite{jarrett2009best} using a 2-layer CNN+2-layer NN configuration (0.11M trainable parameters). Network in Network \cite{lin2013network} surpassed this result by achieving an error of 0.47\%. By using maxout activation function \cite{goodfellow2013maxout} reduced the error to 0.45\%. As per our knowledge the current state-of-the-art result for MNIST classification without data augmentation is 0.39\% achieved by \cite{lee2015deeply}. We used a 12-layer ($\approx{0.12M}$ trainable parameters) CrossNet to reach an error rate of 0.36\%.
\\
\begin{table}[ht]
\caption{Misclassification rates, for the general MNIST dataset without data augmentation, for different architectures.}
\begin{center}
\begin{tabular}{c c}
 \hline
\\
 Methods & Misclassification Error \\ 
 \hline
& \\
2-Layer 25 Neurons & {9.12\%} \\ [0.5ex]
2-Layer 50 Neurons & {4.39\%} \\ [0.5ex]
2-Layer 800 Neurons & {1.60\%} \\ [0.5ex]
3-Layer 1024 Neurons & {1.25\%} \\ [0.5ex]
2-Layer CNN & {1.41\%} \\ [0.5ex]
CrossNet\_2-Layer 25 Neurons & {\textbf{3.70\%}} \\ [0.5ex]
CrossNet\_2-Layer 50 Neurons & {\textbf{2.38\%}} \\ [0.5ex]
CrossNet\_2-Layer 800 Neurons & {\textbf{1.26\%}} \\ [0.5ex]
CrossNet\_3-Layer 1024 Neurons & {\textbf{1.10\%}} \\ [0.5ex]
CrossNet\_2-Layer CNN & {\textbf{1.15\%}} \\ [0.5ex]
 \hline
 \end{tabular} 
\end{center}•
\vspace{-2em}
\label{table1}
\end{table}

\vspace{-1em}
\begin{table}[ht]
\vspace{2em}
\caption{MNIST classification result without data augmentation and model averaging}
 \begin{tabular}{c c}
 \hline
\\
 Methods & Misclassification Error \\ 
 \hline
& \\
2-Layer CNN + 2-Layer NN & {0.53\%} \\ [0.5ex]
Network in Network & {0.47\%} \\ [0.5ex]
Maxout Network & {0.45\%} \\ [0.5ex]
Deeply Supervised Nets & {0.39\%} \\ [0.5ex]
CrossNet (12 Layers, 0.12M parameters) & {\textbf{0.36\%}} \\ [0.5ex]
 \hline
 \end{tabular} 
\vspace{-1em}
\label{table2}
\end{table}
\noindent
\textbf{Experimental details:}\\
All the different networks were tuned on the validation dataset. This tuned network was then used to evaluate the performance on the test images. The performance of our proposed architecture was evaluated using an overall of six architectures. Stochastic Gradient Descent (SGD) with momentum of 0.95 was used for training all the architectures. For the shallow networks (25 and 50 neurons case), we used a learning rate of 0.1. For all other MLP architectures we used an initial learning rate of 0.01. In regards to CrossNet version of the MLP network, the input layer was connected to all the subsequent hidden layers (excluding the output layer), and the hidden layers were connected to all the subsequent hidden layers (including the output layer). For the 2-layer CNN architecture we used a standard network. Both convolutional layers use $5\times5$ filter size with 16 and 32 channels, respectively. A dropout of 0.5 is used after the second convolutional layer. All the layers used ReLU activations. For the CrossNet version of this architecture the activated outputs of both the convolutional layers were stacked together and fed to the output softmax classifier. 

The 2-CNN-2-fully connected architecture was designed as per \cite{jarrett2009best}. The first convolutional produces 32 feature maps, and the second convolutional layer produces 64 feature maps, each using $5\times5$ filters followed by $2\times2$ pooling. The classifier comprises of 2-layer fully-connected neural network with 200 hidden units, and 10 outputs. A 12-layer CrossNet was designed for the experiment, consisting of 12 composite units (defined in Section \ref{composite}). A $2\times2$ average pooling layer was used after every 4 composite units. The number of kernels used in each convolution layer was 12. We used a step wise learning rate for training, starting from an initial learning rate of 0.1. We trained the network for 30 epochs.

These experiments were mainly to demonstrate the effectiveness of cross-connections. Exhaustive exploration using common tricks, such as weight constraints, hidden unit sparsity, and adding noise, were not done. All the experiments on

\begin{table*}
\caption{CrossNet architectures for CIFAR datasets. The number of kernels in each layer was fixed to 12 for computational issues. Each "conv" is a composite unit comprising the sequence of BN-RELU-Convolution layer.}

\centering
\scalebox{0.8}{
\begin{tabular}
{c|c|c|c|c}
\hline
  & & & &\\
Layers & Output Size & CrossNet\_v1 & CrossNet\_v2 & CrossNet\_v3\\[0.5ex]
\hline
\makecell{Pre-Activation\\Convolution} & $32\times32$ & \multicolumn{3}{c}{$3\times3$ convolution layer} \\ [0.5ex]
\hline

& & & &\\
\multirow{3}{*}{Composite block (1)} & \multirow{3}{*}{$32\times32$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       \textrm{12 kernels}
     \end{bmatrix}\times 8$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv}\\
       12\textrm{ kernels}
     \end{bmatrix}\times 16$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       \textrm{12 kernels}
     \end{bmatrix}\times 16$} \\[0.5ex] 
  & & & &\\[0.5ex]
  & & & &\\[0.5ex]
\hline

\makecell{Transition Layer\\(1)} & $16\times16$ & \multicolumn{3}{c}{$1\times1$ conv, $2\times2$ average pool, stride 2}\\ [0.5ex]
\hline

& & & &\\
\multirow{3}{*}{Composite block (2)} & \multirow{3}{*}{$16\times16$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       \textrm{12 kernels}
     \end{bmatrix}\times 8$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv}\\
       12 \textrm{ kernels}
     \end{bmatrix}\times 16$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       12 \textrm{ kernels}
     \end{bmatrix}\times 16$}\\[0.5ex]  
  & & & &\\[0.5ex]
  & & & &\\[0.5ex]
\hline

\makecell{Transition Layer\\(2)} & $8\times8$ & \multicolumn{3}{c}{$1\times1$ conv, $2\times2$ average pool, stride 2} \\ [0.5ex]
\hline

& & & &\\
\multirow{3}{*}{Composite block (3)} & \multirow{3}{*}{$8\times8$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       \textrm{12 kernels}
     \end{bmatrix}\times 8$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv}\\
       12 \textrm{ kernels}
     \end{bmatrix}\times 16$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       12 \textrm{ kernels}
     \end{bmatrix}\times 16$}\\[0.5ex] 
  & & & &\\[0.5ex]
  & & & &\\[0.5ex]
\hline

\makecell{Transition Layer\\(3)} & $4\times4$ & \multicolumn{2}{c|}{$1\times1$ conv, $2\times2$ average pool, stride 2}
											  & {-}\\ [0.5ex]
\hline

& & & &\\
\multirow{3}{*}{Composite block (4)} & \multirow{3}{*}{$4\times4$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv} \\
       \textrm{12 kernels}
     \end{bmatrix}\times 8$} & \multirow{3}{*}{$\begin{bmatrix}
       3\times3 \textrm{ conv}\\
       12 \textrm{ kernels}
     \end{bmatrix}\times 16$} & \multirow{3}{*}{-}\\[0.5ex] 
  & & & &\\[0.5ex]
  & & & &\\[0.5ex]
\hline

\makecell{Classification\\ Layer} & $1\times1$ & \multicolumn{2}{c|}{$4\times4$ global average pool, 10D fully-connected, Softmax} 
& {$8\times8$ global average pool, 10D fully-connected, Softmax}\\ [0.5ex]
\hline

\end{tabular}}
\vspace{-1em}
\label{table4}
\end{table*}

\noindent MNIST were performed without data augmentation. In Figure \ref{figure3}, we see the superior training performance of CrossNet MLP architectures as compared to a sequential MLP architectures.\\


\subsubsection{Dataset 2: CIFAR-10 and CIFAR-100}

The CIFAR datasets \cite{krizhevsky2009learning} consist of $32\times32$ RGB color images taken from various classes. CIFAR-10 and CIFAR-100 comprise of images taken from 10 and 100 classes respectively. Both the dataset consists of 60k images split into 50k training and 10k testing images. Of the 50k training images,  5k were kept for cross-validation to optimize hyper-parameters. As we see, each class has 6000 and 600 images in CIFAR-10 and CIFAR-100 datasets respectively. The input images were normalized and experiments were performed with and without augmentation.

Table \ref{table3} shows the classification error of different methods on the CIFAR-10 and CIFAR-100 datasets. We see that CrossNets performance is superior to most of the previously proposed architectures. It is clearly observed that CrossNets\_v2 (64  layers) (6.59\%) outperforms both ResNet (13.63\%) and Stochastic depth (11.66\%) \cite{huang2016deep} without any data augmentation by a large margin for CIFAR-10 dataset. A similar performance was observed for CIFAR-100 dataset where CrossNets\_v2 (28.10\%) outperformed both ResNets(44.76\%) and Stochastic depth (37.80\%). With data augmentation we see similar performances for the above architectures. Results from other notable methods are also mentioned in Table \ref{table3}. 
CrossNet\_v3 outperforms the earlier versions. The primary difference between CrossNet\_v3 with the prior versions are that it preserves the global structure more. Due to computational limitations, we were not able to test with larger architectures, and hence, we experimented with relatively shallow CrossNets to showcase the effectiveness of the architecture. It is to be noted that networks like FractalNets use 22.9M and 38.6M trainable parameters for achieving low misclassification rates, whereas CrossNets only use 1.2M, 4.9M, and 2.7M trainable parameters for achieving the results stated in Table \ref{table3}. Architectural details for the different versions of CrossNets are described in the following section and in Table \ref{table4}.\\

\noindent
\textbf{Experimental details:}\\
Both CIFAR-10 and CIFAR-100 consists of images belonging to 10 and 100 classes respectively. The raw input images pre-processed using global contrast normalization and ZCA whitening. ZCA whitening means that we center the data around its mean, rotate it onto its principle components, normalize individual components and then rotate them back. We held out 5,000 random training images for validation. The network was tuned to give the best performance on this validation dataset. The presented results are obtained from this tuned network. We use three different versions of CrossNets in our experiments. In Table \ref{table4}, further details are provided with respect to each version. CrossNet\_v1, CrossNet\_v2, and CrossNet\_v3 consisted of 32, 64, and 48 composite units respectively. The pre-processed images were pre-activated using a convolutional layer with 16 filters of $3\times3$ kernel size each. A $2\times2$ average pooling layer was used after every 8, 16, and 16 composite units in each of the above mentioned CrossNets respectively. Finally, a global averaging pooling layer and a softmax classifier was used at the end. We use a step wise learning rate schedule for training, where we start with an initial learning rate of 0.1 and reduced 10 times after each quarter of the total number of epochs. We train the network for 300 epochs. No dropouts or drop-connects were used in the training. Standard data augmentation scheme in the form of translation and horizontal flips were used.




\subsubsection{Dataset 3: Street View House Numbers}
The Street View House Numbers (SVHN) dataset \cite{netzer2011reading} consists of $32\times32$ color RGB images. The dataset comes with 73,257 samples for training, 26,032 samples for testing, and an extra 531,131 samples for training. It comprises of 10 digit classes from 0-9. We take out 6000 samples (600 from each class consisting of 400 from the training set and 200 from the extra training set) and used it as validation dataset. Preprocessing was done on the samples in terms of global contrast normalization. As in the CIFAR dataset, we chose the best hyper-parameters by monitoring the validation performance. The performance of DropConnect was a result of their voting scheme. ResNets and FractalNets comparatively did not perform well with SVHN dataset, reaching a 2.01\% and 1.87\% error rate respectively. We trained the same three different versions of CrossNets as used for CIFAR datasets. CrossNet\_v1 (32 layers, 1.2M parameters) did not perform well and achieved an error rate of 2.92\%.
CrossNet\_v2 (64 layers, 4.9M parameters) performed better than CrossNet\_v1 surpassing most of the previous state-of-the-art results by reducing the error to 1.85\%. CrossNet\_v3 (48 layers, 2.7M parameters) achieved an error rate of 1.71\%.
Table \ref{table3} shows recent comparable results using no data augmentation. 
\\
\\
\noindent
\textbf{Experimental details:}\\
As in the case for MNIST and CIFAR datasets, the hyper-parameters for the training were tuned on the validation set, and the tuned network was used to evaluate the performance on the test dataset. The SVHN dataset is a relatively easier task as compared to CIFAR. Pre-processing was only done in terms of global contrast normalization. The same three network architectures for CrossNets were used as that for CIFAR. The only difference is in terms of the total number of epochs. We train the network for 40 epochs. The learning rate schedule starts with an initial learning rate of 0.1 and is reduced 10 times after every 10 epochs.  No dropouts or drop-connects were used in the training. No data augmentation was performed.

\begin{table*}
\caption{Misclassification rates, for the test dataset on the general CIFAR-10, CIFAR-100, and SVHN dataset with(+) and without data augmentation. The results with data augmentation implements translation and mirroring.
}

\begin{center}
 \begin{tabular}{c c c c c c}
 \hline
\\
 Methods & C10 & C10$+$ & C100 & C100$+$ & SVHN \\
 \hline
& \\
DropConnect\cite{wan2013regularization} & {18.7\%} & {9.32\%} & {-} & {-} & 1.94\% \\ [0.5ex]
ResNet\cite{huang2016deep} & {13.63\%} & {6.41\%} & {44.76\%} & {27.22\%} & 2.01\% \\ [0.5ex]
Stochastic Depth\cite{huang2016deep} & {11.66\%} & {5.23\%} & {37.80\%} & {24.58\%} & 1.75\% \\ [0.5ex]
Network in Network & {10.41\%} & {8.81\%} & {35.68\%} & {-} & 2.35\% \\ [0.5ex]
FractalNet (20 layers, 38.6M parameters) & {10.18\%} & {5.22\%} & {35.34\%} & {23.30\%} & 2.01\% \\ [0.5ex]
Deeply Supervised Nets & {9.69\%} & {7.97\%} & {-} & {34.57\%} & 1.92\% \\ [0.5ex]
HighWay Net & {-} & {7.72\%} & {-} & {32.39\%} & {-}\\ [0.5ex]
Generalized Pooling\cite{lee2016generalizing} & {7.62\%} & {6.05\%} & {32.37\%} & {-} & 1.69\% \\ [0.5ex]
ResNet in ResNet \cite{targ2016resnet}  & {-} & {5.01\%} & {-} & {22.90\%} & {-} \\ [0.5ex]
Wide ResNet \cite{zagoruyko2016wide}  & {-} & {4.17\%} & {-} & {20.50\%} & {-} \\ [0.5ex]
FractalNet + drop-path(deepest column alone) & {7.27\%} & {4.68\%} & {29.05\%} & {24.32\%} & 1.87\% \\ [0.5ex]
FractalNet (40 layers, 22.9M params) & {-} & {5.24\%} & {-} & {22.49\%} & {-} \\ [0.5ex]
CrossNet\_v1(32 layers, 1.2M parameters) & {9.02\%} & {6.27\%} & {35.03\%} & {30.66\%} & {2.92\%} \\ [0.5ex]
CrossNet\_v2(64  layers, 4.9M parameters) & {6.59\%} & {5.32\%} & {28.10\%} & {24.72\%} & {1.85\%} \\ [0.5ex]
CrossNet\_v3(48  layers, 2.7M parameters) & {6.21\%} & {4.61\%} & {-} & {23.09\%} & {1.71\%} \\ [0.5ex]
 \hline
 \end{tabular} 
\end{center}•
\vspace{-1em}
\label{table3}
\end{table*}
\section{Experiments} \label{sec:experiment}

\begin{figure}
\centering
\includegraphics[width=.8\textwidth]{crossencoder.eps}
\caption{\textbf{Architecture for CrossEncoders.}A directed edge from a node (circle) in one layer (column of circles) to another node in a different layer represents a connection. Additional edges  between nodes, suppressed for presentation, may also exist. Note, however, that edges may not connect encoding and decoding layers. }\label{autofig}
\end{figure}




We examine the efficacy of DAG architectures by  examining a problem of compression through the use of autocoders. The addition of skip connections in autoencoders, entitled CrossEncoders, was studied by Agarwal et al. \cite{agarwal2018crossencoder}.  In this section, we apply CrossEncoders to the Olivetti face dataset\footnote{ The Olivetti faces data set is a public dataset, may be obtained from http://mambo.ucsc.edu/psl/olivetti.html}. 

For the problem of compression, we require a code layer with index $0<\mathbf c<L$ and dimension $l_\mathbf c < l_0$. Since we are now comparing input and output, layer $L$ also contains $l_0$ nodes. In terms of Eqn.  \ref{generrordef}, $d^j = x^j$, and thus
\begin{equation}
E = \sum_{j = 1}^J \|x^j-y^j\|/2. 
\end{equation}
Since decoding should be solely dependent  from the code layer, we also require that skip connections cannot occur between encoding layers and decoding layers.  Thus
 \begin{equation}
 v_{(i,j)}^{l,m} = 0 \quad \hbox{if }  \quad i<\mathbf c < j. \label{encoderequire}
 \end{equation}
 See Fig. \ref{autofig} for a visual representation of the CrossEncoder architecture. 







\subsection{Olivetti faces dataset}
The Olivetti faces dataset \cite{minear2004lifespan} comprises of a set of 400 gray-scale face images consisting of ten different images of 40 distinct subjects. Images for some subjects were taken with varying lighting, facial expressions (e.g. open / closed eyes, smiling / not smiling) and facial details (e.g. glasses / no glasses).
The images are $64\times64$ in size and are quantized to 8-bit [0-255] scale. A $4096-500-500-code-500-500-4096$ MLP network was used for training the face dataset. Both sequential and cross-connected versions of the MLP were trained. 

The original $64\times64$ images were transformed to a $1\times4096$ vector. For training, 350 images were used, and 50 images were used for the testing dataset. Both AutoEncoders and CrossEncoders were trained for 300 epochs using SGD optimizer with a learning rate set to 0.001 and momentum of 0.95. For the given task, we used several lower dimension representations, such as $1\times600$, $1\times300$, and $1\times30$, respectively. Table \ref{table8} illustrates the performance of the respective networks for different code size using peak signal to noise ratio (PSNR), structural similarity index (SSIM), and normalized root mean squared error (NRMSE) metrics. In Table \ref{table8}, we observe improved performance for CrossEncoders across all performance metrics.

\begin{table}[ht]
\caption{PSNR, SSIM, and NRMSE values of CrossEncoder and Autoencoder between reconstructed and the original images for Olivetti face dataset.  Higher PSNR and SSIM values, and lower NRSME values, imply more accurate results.}
\begin{center}
\noindent\begin{tabular}{|c|c|c|c|c|c|c|}
\toprule
& \multicolumn{3}{c|}{\textbf{CrossEncoder}} & \multicolumn{3}{c|}{\textbf{Autoencoder}} \\
\cmidrule(r){2-4}\cmidrule(l){5-7}
\textbf{Code} & \textbf{PSNR} & \textbf{SSIM} & \textbf{NRMSE}  & \textbf{PSNR} & \textbf{SSIM} & \textbf{NRMSE} \\
\midrule
$1\times600$  & \textbf{79.4679} & \textbf{0.9040} &  \textbf{0.1464} & 75.8858 & 0.8554 &  0.2217\\ [0.5ex]
$1\times300$  & \textbf{79.4551} & \textbf{0.9046} &  \textbf{0.1467} & 75.8919 & 0.8555 &  0.2215\\ [0.5ex]
$1\times30$  & \textbf{77.8398} & \textbf{0.8791} & \textbf{0.1764} & 75.9066 & 0.8560 &  0.2211\\ [0.5ex]
\bottomrule
\end{tabular}
\end{center}•
\label{table8}
\vspace{-1em}
\end{table}
















\section{Conclusion}
We have studied a feed-forward network with cross-layer connections. The possible directed graph architectures are the class of directed acyclic graphs.  As shown in \cite{huang2016densely}, introducing skip connections often increases the accuracy of a neural networks. In \cite{agarwal2018crossencoder} and in Section \ref{sec:experiment}, we have demonstrated increased accuracy in the setting of autoencoders. For our main result, we have established the convergence of backpropagation with adaptive momentum of networks with skip connections. This generalizes the result of Wu et al. \cite{wu2008convergence} who established convergence for a feed forward network with one hidden layer. While we have considered general DAG architectures, it remains to investigate, both through theory and experiment, the optimality properties with regards to the number of layers and  skip connections. We hope to address these properties in future works. 
\section{Introduction}
\label{sec:introduction}

Neural networks have recently enjoyed an acceleration in popularity, with new research adding to several decades of foundational work. From multilayer perceptron (MLP) networks to the more prominent recurrent neural networks (RNNs) and convolutional neural networks (CNNs), neural networks have become a dominant force in the fields of computer vision, speech recognition, and machine translation \cite{rosenblatt1961principles}. Increase in computational speed and data collection have legitimized the training of increasingly complex deep networks. The flow of information from input to output is typically performed in a strictly sequential feed-forward fashion, in which for a network consisting of   $L$ layers of neurons,  nodes in the $i^{th}$ layer receive input from the $(i-1)$st layer, compute an output for each neuron, and in turn use this output as an input for the $(i+1)$st  layer. A natural question, then, is how the addition of ``skip connections" between layers affects performance.  Specifically, we are interesting in the class of architectures in which the network of connections form a directed acyclic graph (DAG).  The defining property of a DAG is that it can always be decomposed into a \textit{topological ordering} of $L$ layers, in which nodes in layer $i$ may be connected to layer $j$ where $j>i$.  A skip connection occurs when a node connects layers $i$ and $j$, with $j>i+1$.
There has been an increasing interest in studying networks with skip connection where weights skip a small number of layers, with examples including Deep Residual Networks (ResNet) \cite{he2016deep},  Highway Networks \cite{srivastava2015training}, and FractalNets \cite{larsson2016fractalnet}.  ResNets, for instance,  use ``shortcut connections" in which a copy of previous layers are mapped through an identity mapping to future layers. Kothari and Agyepong \cite{kothari1996lateral} introduced  ``lateral connections" in the form of a chain, where each unit in a hidden layer is connected to the next.
The full generality of neural networks for DAG architectures was considered in \cite{huang2016densely}, which demonstrated superior performance of neural networks, entitled DenseNets, under a large set of skip connections.  

As an example of the efficacy of DAG architectures considered in \cite{huang2016densely}, we consider autoencoders, a class of neural networks which provide a means of compressing data. For an autoencoder, input data, such as a pixelated image, is also considered as the desired output for a neural network.  During an encoding phase, the input is compressed through several hidden layers before arriving at a layer, called the code, with dimension smaller than the input.  The next phase is decoding, in which input from the code is fed through several more hidden layers until arriving at the output, which is of the same dimension as the input.  The goal of compression is to minimize the difference between input data and output.  In \cite{agarwal2018crossencoder}, Agarwal et. al introduced CrossEncoders, which demonstrated superior performance of autoencoders with cross-connections. In Section \ref{sec:experiment}, we extend the previous results to include the Olivetti faces dataset and and compare  CrossEncoders against traditional autoencoders.  While our proof of convergence uses mean square error, we validate our results against several other commonly used compression based performance metrics.

Our main theoretical result is the convergence of backpropagation with DAG architectures using gradient descent with momentum.  It is well known that feed-forward architectures converge to local minima under backpropagation, which is  essentially gradient descent applied to an error function (see \cite{bishop1995neural}, for instance). Updates for weights in backpropagation may be generalized to include a momentum term, which can help with increasing the convergence rate \cite{rumelhart1987parallel}. For a linear activation function, Bhaya \cite{bhaya2004steepest} and Torii \cite{torii2002stability} studied the convergence with backpropagation using momentum. Zhang et al.\cite{zhang2006}  generalized convergence for a class of common nonlinear activation functions, including sigmoids, for the simple case of a zero hidden layer networks. Wu et al. \cite{wu2008convergence} further generalized to one layer, by demonstrating that error is monotonically decreasing under backpropagation iterations for sufficiently small momentum terms. The addition of a hidden layers required  \cite{wu2008convergence} to make the additional assumption of bounded weights during the iteration procedure. 

It is not evident whether applying the methods of \cite{wu2008convergence} would generalize to networks with several hidden layers and skip connections, or if they  would require stronger assumptions on boundedness of weights or the class of activation functions.  We show in Section \ref{appsect}  that convergence indeed does hold, with similar assumptions to the proof of convergence of one hidden layer.  While the general methods of the proof are similar to \cite{wu2008convergence}, the addition of skip connections will require several tensor identities to prove key estimates.





