




\subsection{Properties of Local Learning}
One of the key features of LP is the locality in the gradient computations. Before going into further details, we remark that, in the context of this paper, the term \textit{locality} refers to those gradient computations with respect to a certain variable of layer $\ell$ that only involve units belonging (at most) to neighbouring layers. 
This is largely different from the usual case of the BackPropagation (BP) algorithm, where the gradient of the cost function with respect to a certain weight in layer $\ell$ is computed only after a forward and a backward steps that involve all the neural units of all layers (see Fig.~\ref{local} (a))
\begin{figure*}
\centering
\includegraphics[width=0.42\textwidth]{fig/local.pdf} \hskip 0.5cm {\unskip\ \vrule\ } \hskip 0.5cm \includegraphics[width=0.39\textwidth]{fig/figres.pdf}\\
$\ \ \ $ \hskip -0.9cm (a) \hskip 2.6cm (b) \hskip 0.22\textwidth (c) \hskip 2.0cm (d)
\caption{Left: the neurons and weights that are involved in the computations to update the red-dotted weight $w$ are highlighted in yellow. (a) Backpropagation; (b) Local Propagation -- the computations required to update the variables $x,\lambda$ (associated to the red neuron) are also considered. Right: (c) ResNet in the case of $H=3$, and (d) after the change of variables ($x_{\ell} \rightarrow \tilde{x}_{\ell}$) described in Sec.~\ref{sec:popular}. Greenish circles are sums, and the notation $\texttt{in}_{\ell}$ inside a rectangular block indicates the block input.}
\label{local}
\end{figure*}
Differently, in the case of LP we have
\begin{eqnarray}
\label{w}\hskip-5mm \frac{\partial \mathcal{L}}{\partial W_{\ell}} &\hskip-3mm=\hskip-3mm& -\sum_{i=1}^{N} \left(\lambda_{\ell+1,i} \odot  \mathcal{G}'_{\ell+1,i} \odot \sigma'(W_{\ell}x_{\ell,i}) \right) x^{T}_{\ell,i}  \\
\label{uff}\hskip-5mm \frac{\partial \mathcal{L}}{\partial x_{\ell,i}} &\hskip-3mm=\hskip-3mm& \lambda_{\ell,i}\odot \mathcal{G}'_{\ell,i} \hskip-0.5mm - \hskip-0.5mm W_{\ell}^T \hskip -1mm \left(  \lambda_{\ell+1,i}\odot \hskip -0.5mm \mathcal{G}'_{\ell+1,i}  \odot \hskip -0.5mm \sigma'(W_{\ell}x_{\ell,i}) \right) \\
\label{x}\hskip-5mm \frac{\partial \mathcal{L}}{\partial x_{H,i}} &\hskip-3mm=\hskip-3mm& \lambda_{H,i}\odot \mathcal{G}'_{H,i} +  W_{H}^T \left( V'(W_{H}x_{H,i},y_i) \right)\\
\label{l}\hskip-5mm \frac{\partial \mathcal{L}}{\partial \lambda_{\ell,i}} &\hskip-3mm=\hskip-3mm& \mathcal{G}_{\ell,i}
\end{eqnarray}
where $\mathcal{G}'$, $\sigma'$ and $V'$ are the first derivatives of the respective functions, and $\odot$ denotes the Hadamard product. The  equations above  hold for all $i\in[1,n]$ and $\ell\in[1,H]$, with the exception of Eq. (\ref{uff}) that holds for $\ell\in[1,H-1]$.
It is evident that each partial derivative with respect to a variable associated to layer $\ell$ only involves terms that belong to the same layer (e.g., $\partial \mathcal{L} / \partial \lambda_{\ell,i}$) and also to either layer $\ell-1$ (as in $\partial \mathcal{L} / \partial W_{\ell}$) or layer $\ell+1$ (the case of $\partial \mathcal{L} / \partial x_{\ell,i}$), that is, gradient computations are \textit{local} (see Fig.~\ref{local} (b)).

This analysis reveals the full local structure of the algorithm for the discovery of saddle points.
The role of the local updates is twofold: first, they project the variables onto the feasible region defined by the $\mathcal{G}_{\ell,i}$ constraints; second, they allow the information attached to the supervised pairs to flow from the loss function $V(\cdot,\cdot)$ through the network. The latter consideration is critical, since the information can flow through a large number of paths, and many iterations could be required to keep the model projected onto the feasible region and efficiently learn the network weights. In Section~\ref{sec:exp} we will also explore the possibility of enforcing a $L_1$-norm regularizer (weighted by $\alpha > 0$) on each $x_{\ell,i}$, in order to help the model to focus on a smaller number of paths from input to output units, reducing the search space.

\paragraph{Parallel Computations over Layers.}
It is well known that in Backpropagation we have to perform a set of \textit{sequential} computations over layers to complete the forward stage, and only afterwards we can start to \textit{sequentially} compute the gradients, moving from the top layer down to the currently considered one (backward computations). 
Modern hardware (GPUs) can benefit by the parallelization of the matrix operations within each layer,
while in the case of LP, the locality in the gradient computation allows us to go beyond that. We can promptly see from Eq.~(\ref{w}-\ref{l}) that we can trivially distribute all the computations associated to each layer $\ell$ in a different computational unit. Of course, the $\ell$-th computational unit needs to share the memory where some variables are stored with the $(\ell+1)$-th and $(\ell-1)$-th units (see Eq.~(\ref{w}-\ref{l})).

\paragraph{Deep Learning in the Adjoint Space.}
Learning in the space to which the variables $\mathcal{W}, \mathcal{X}, \Lambda$ belong introduces a particular information flow through the network. If, during the optimization stage, the architectural constraints of Eq.~(\ref{con}) are strongly violated, then the updates applied to the network weights are not related to the ground truths that are attached to the loss function $V(\cdot)$, and we can imagine that the gradients are just noise. Differently, when the constraints are fulfilled, the information traverses the network in a similar way to what happens in Backpropagation, i.e., in a noise-free manner. When the optimization proceeds, we progressively get closer to the fulfilment of the constraints, so that the noisy information is reduced. It is the learning algorithm itself that decides how to reduce the noise, in conjunction with the reduction of the loss on the supervised pairs. It has been shown that introducing a progressively reduced noise contribution to the gradient helps the Backpropagation algorithm to improve the quality of the solution, allowing very deep networks to be trained also when selecting low quality initialization of the weights \cite{neelakantan2015adding}. The LP natively embeds this property so that, differently from \cite{neelakantan2015adding}, the noise reduction scheme is not a hand-designed procedure. Moreover, the local gradient computations of LP naturally offer a setting that is more robust to the problem of vanishing gradients, which afflicts Backpropagation when training deep neural networks.

\paragraph{Recovering Backpropagation.}
The connections between the LP algorithm and Backpropagation become evident when imposing the stationary condition on the Lagrangian $\partial \mathcal{L} / \partial \lambda_{\ell,i}=0$ and $\partial \mathcal{L} / \partial x_{\ell,i} = 0$. For the purpose of this description, let $\mathcal{G}(\cdot)$ be the identity function. From Eq.~(\ref{l}), we can immediately see that the stationary condition $\partial \mathcal{L} / \partial \lambda_{\ell,i} = 0$ leads to the classic expression to compute the outputs of the neural units, $x_{\ell,i} = \sigma(W_{\ell-1}x_{\ell-1,i})$, that is associated to the forward step of Backpropagation. Differently, when imposing $\partial \mathcal{L} / \partial \lambda_{\ell,i}=0$ and defining $\delta_{\ell,i}=\lambda_{\ell,i} \odot \sigma'(W_{\ell-1}x_{\ell-1,i})$, Eq.~(\ref{w}) and Eq.~(\ref{uff}) can be respectively rewritten as
\begin{align*}
\frac{\partial \mathcal{L}}{\partial W_{\ell}} & = -\sum_{i=1}^N \delta_{\ell,i} \cdot x_{\ell-1,i}^T,\\ \delta_{\ell,i} & =\sigma'(W_{\ell-1}x_{\ell-1,i}) \odot \left( W_{\ell}^{T} \delta_{\ell+1,i} \right),
\end{align*}
that are the popular equations for updating weights and the Backpropagation deltas. 

From this perspective, the Backpropagation algorithm represents the optimum w.r.t. the stationary conditions connected to the $\lambda_{\ell,i}$ and the $x_{\ell,i}$ when compared with Local Propagation. However, by strictly searching only on the hyperplane where the Lagrangian is stationary w.r.t $\lambda_{\ell,i}$ and $x_{\ell,i}$, Backpropagation loses the locality and parallelization properties characterizing our algorithm since the gradients cannot rely anymore on the variables of neighboring layers only but depend on all the variables of the architecture.

\subsection{Epsilon-insensitive Constraints}
\label{sec:eps}
In order to facilitate the convergence of the optimization algorithm or to improve its numerical robustness, we can select different classes of $\mathcal{G}(\cdot)$ functions in Eq.~(\ref{con}). In this paper, we focus on the class of $\epsilon$-insensitive functions, and, in particular, on the following two cases $\mathcal{G} \in \{ \eps, \lineps \}$, 
\begin{eqnarray*}
\eps(a) &=& \max(|a| - \epsilon, 0) \\
\lineps(a) &=& \max(a, \epsilon) - \max(-a, \epsilon) \ .
\end{eqnarray*}
Both the functions are continuous, they are zero in $[-\epsilon, \epsilon]$, and they are linear out of such interval. However, $\eps(\cdot)$ is always positive, while $\lineps(\cdot)$ is negative for arguments smaller than  $-\epsilon$. When plugged into Eq.~(\ref{con}), they allow the architectural constraints to tolerate a bounded mismatch in the values of $x_{\ell,i}$ and $\sigma(W_{\ell-1}x_{\ell,i})$ ($\epsilon$-insensitive constraints). Let us consider two different examples indexed by $i$ and $j$, for which we get two similar valus $\sigma(W_{\ell-1}x_{\ell,i})$ and $\sigma(W_{\ell-1}x_{\ell,j})$ in a certain layer $\ell$. Then, for small values of $\epsilon$, the same value $x_{\ell,i}=x_{\ell,j}$ can be selected by the optimization algorithm, thus propagating the same signal to the units of the layer above. In other words, $\epsilon$-insensitive constraints introduce a simple form of regularization when training the network, that allows the network itself to not be influenced by small changes in the neuron inputs, thus stabilizing the training step. Notice that, at test stage, if we compute the values of $x_{\ell,i}$'s with the classic forward procedure, then the network will not take into account the $\mathcal{G}(\cdot)$ function anymore. If $\epsilon$ is too large, there will be a large discrepancy between the setting in which the weights are learned and the one in which they are used to make new predictions. This could end up in a loss of performances, but it is in line with what happens in the case of the popular Dropout \cite{srivastava2014dropout} when the selected drop-unit factor is too large.

A key difference between $\eps(\cdot)$ and $\lineps(\cdot)$ is the effect they have in the development of the Lagrange multipliers. It is trivial to see that, since $\eps(\cdot)$ is always positive, the multipliers $\lambda_{\ell,i}$ can only increase during the optimization (Eq.~(\ref{l})). In the case of $\lineps(\cdot)$, the multipliers can both increase or decrease. We found that $\eps(\cdot)$ leads to a more stable learning, where the violations of the constraints change more smoothly that in the case of $\lineps(\cdot)$. As suggested in \cite{platt} and as it is also popular in the optimization literature \cite{bertsekas2014constrained}, a way to improve the numerical stability of the algorithm is to introduce the so called Augmented Lagrangian, where $\mathcal{L}$ of Eq.~(\ref{lagrangian}) is augmented with an additive term $\rho \| \mathcal{G}_{\ell,i} \|^2$, for all $i,\ell$. 


\section{Introduction}
\label{sec:intro}
\blfootnote{Accepted for publication at the IEEE International Joint Conference on Neural Networks (IJCNN) 2020 (DOI: TBA).

© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.}
\input introduction.tex

\section{Constraint-based Neural Networks}
\label{sec:constr}
\input constr.tex

\section{Local Propagation}
\label{lp}
\input local.tex

\section{Popular Neural Units}
\label{sec:popular}
\input popular.tex


\section{Experiments}
\label{sec:exp}
\input exp.tex


\section{Conclusions and Future Work}
\label{sec:concl}
\input conclusions.tex


\section*{ Acknowledgments}
This work was partly supported by the PRIN 2017 project RexLearn, funded by the Italian Ministry of Education, University and Research (grant no. 2017TWNMH2). 



