On Alignment in Deep Linear Neural Networks
We study the properties of alignment, a form of implicit regularization, in linear neural networks under gradient descent. We define alignment for fully connected networks with multidimensional outputs and show that it is a natural extension of alignment in networks with 1-dimensional outputs as defined by Ji and Telgarsky, 2018. While in fully connected networks, there always exists a global minimum corresponding to an aligned solution, we analyze alignment as it relates to the training process. Namely, we characterize when alignment is an invariant of training under gradient descent by providing necessary and sufficient conditions for this invariant to hold. In such settings, the dynamics of gradient descent simplify, thereby allowing us to provide an explicit learning rate under which the network converges linearly to a global minimum. We then analyze networks with layer constraints such as convolutional networks. In this setting, we prove that gradient descent is equivalent to projected gradient descent, and that alignment is impossible with sufficiently large datasets.
\section{Introduction}
\label{sec: Introduction}


Although overparameterized deep networks can interpolate randomly labeled training data \cite{DuOptimizesOverparameterizedNetworks, DuAdaptiveMethods}, training overparameterized networks with modern optimizers often leads to solutions that generalize well. This suggests that there is a form of \textit{implicit regularization} occurring through training \cite{RethinkingGeneralization}.  


As an example of implicit regularization, the authors in \cite{LogisticAlignment} proved that the layers of linear neural networks used for binary classification on linearly separable datasets become aligned in the limit of training.  That is, for a linear network parameterized by the matrix product $W_d, W_{d-1}, \ldots W_1$, the top left/right singular vectors $u_i$ and $v_i$ of layer $W_i$ satisfy $|v_{i+1}^T u_i| \rightarrow 1$ as the number of gradient descent steps goes to infinity.

Alignment of singular vector spaces between adjacent layers allows for the network representation to be drastically simplified  (see Equation \eqref{eq: aligned_network});  namely, the product of all layers becomes a product of diagonal matrices with the exception of the outermost unitary matrices.  If alignment is an invariant of training, then optimization over the set of weight matrices reduces to optimization over the set of singular values of weight matrices. Thus, importantly, alignment of singular vector spaces allows for the gradient descent update rule to be simplified significantly, which was used in \cite{LogisticAlignment} to show convergence to a max-margin solution.




In this work, we generalize the definition of \emph{alignment} to the multidimensional setting. We study when alignment can occur and moreover, under which conditions it is an invariant of training in linear neural networks under gradient descent. Our main contributions are as follows:

\begin{enumerate}
\item We extend the definition of alignment from the 1-dimensional classification setting to the multi-dimensional setting (Definition~\ref{def: Alignment for 2 matrices}) and characterize when alignment is an invariant of training in linear fully connected networks with multi-dimensional outputs (Theorem~\ref{thm: Alignment for fully connected networks with multi-dimensional output}). 

\item  We demonstrate that alignment is an invariant for fully connected networks with multidimensional outputs only in special problem classes including autoencoding, matrix factorization and matrix sensing. This is in contrast to networks with 1-dimensional outputs, where there exists an initialization such that adjacent layers remain aligned throughout training under \textit{any} real-valued loss function and any training dataset (Proposition~\ref{prop: Alignment for 1 dimensional outputs}).

\item Alignment largely simplifies the analysis of training linear networks: We provide an explicit learning rate under which gradient descent converges linearly to a global minimum under alignment in the squared loss setting (Proposition~\ref{prop: linear convergence}). 

\item We prove that alignment cannot occur, let alone be invariant, in networks with constrained layer structure (such as convolutional networks), when the amount of training data dominates the dimension of the layer structure (Theorem  \ref{thm: No Alignment in constrained layers}). 

\item We support our theoretical findings via experiments in Section \ref{sec: Experiments}.
\end{enumerate}

As a consequence, our characterization of the invariance properties of alignment 
provides settings under which the gradient descent dynamics can be simplified and the implicit regularization properties can be fully understood, yet also shows that further results are required to explain implicit regularization in linear neural networks more generally. 








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


Implicit regularization in overparameterized networks has become a subject of significant interest \cite{ImplictRegularizationBach, GunasekarImplicitBiasOptimizationGeometry, GunasekarImplicitRegularizationLinearConvNetworks, ImplicitSelfRegularization, neyshabur2014search}.  In order to characterize the specific form of implicit regularization, several works have focused on analyzing deep \emph{linear} networks \cite{DeepMatrixFactorization, GunasekarImplicitRegularizationLinearConvNetworks, MatrixFactorizationNIPS2017, GunasekarLinearlySeparableData}.  Even though such networks can only express linear maps, parameter optimization in linear networks is non-convex and is studied in order to obtain intuition about optimization of deep networks more generally.  

One such form of implicit regularization is \emph{alignment}, identified by \cite{LogisticAlignment} in their analysis of linear fully connected networks with 1-dimensional outputs trained on linearly separable data.  They proved that in the limit of training, each layer, after normalization, approaches a rank $1$ matrix, i.e. 
\begin{align*}
    \lim_{t\rightarrow \infty} \frac{W_i^{(t)}} { \|W_i^{(t)}\|_F} = u_i v_i^T
\end{align*}
and that adjacent layers, $W_{i+1}$ and $W_i$ become \textit{aligned}, i.e. $|v_{i+1}^T u_i| \rightarrow 1.$

In addition, \cite{LogisticAlignment} proved that alignment in this setting occurs concurrently with convergence to the max-margin solution. Follow-up work mainly focused on this convergence phenomenon and gave explicit convergence rates for overparameterized networks trained with gradient descent \cite{AroraTwoLayerNetwork, SGDOptimization}.

While the connection to alignment was not mentioned in their work, the authors in ~\cite{ImplictRegularizationBach} begin to generalize alignment to the case of multidimensional outputs. In particular, they consider two-layer networks initialized so that the two layers are aligned with each other and where both of the layers are aligned with the data. We generalize this to networks of any depth, showing that our definition of alignment corresponds to the initialization considered in \cite{ImplictRegularizationBach}.  Moreover, we establish necessary and sufficient conditions for when alignment is an invariant of training in Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output} instead of assuming these conditions as in \cite{ImplictRegularizationBach}. Furthermore, their result on sequential learning of components is one of a variety of results which can be derived via our singular value update rule presented in Corollary \ref{cor:singular-update}.


Balancedness is another closely related form of implicit regularization in linear neural networks. It was introduced in~\cite{Balancedness} and defined as the property that if $W_i^TW_i = W_{i+1}W_{i+1}^T$ for all $i$ at initialization, then this property is \emph{invariant} through gradient flow. \cite{BalancednessJasonLee} presented a more general form, which is that the difference $W_i^TW_i - W_{i+1}W_{i+1}^T$ is constant through gradient flow. In practice, however, analyses are based on this quantity being close to or exactly zero (in Frobenius norm). In this exact setting, the connection between balancedness and alignment becomes clear since balancedness implies alignment of singular vector spaces between consecutive layers.  
To study gradient descent, slightly more general notions such as approximate balancedness \cite{ApproximateBalancedness} and $\epsilon$-balancedness have been introduced. \cite{BalancednessJasonLee} also defined balancedness with respect to convolutional networks, showing that under gradient flow, the difference in the norm of the weights of consecutive layers is an invariant. Generally, the goal of identifying invariants of training such as balancedness or alignment is to help understand both the dynamics of training and properties of solutions at the end of training.





\section{Definition of Alignment in the Multi-dimensional Setting}
\label{sec: Definition of alignment in multi-dimensional setting}
In this section, we first define alignment for linear neural networks with multi-dimensional outputs.  We then define when alignment is an invariant of training.

We consider \emph{linear} neural networks. Let $f: \mathbb{R}^{k_0} \rightarrow{} \mathbb{R}^{k_{d}}$ denote such a $d$-layer network, i.e.
\begin{align}
    \label{eq: Network Representation}
    f(x) &= W_d W_{d-1}\ldots W_1 x,
\end{align}
where $W_i \in \mathbb{R}^{k_{i} \times k_{i-1}}$ for $i \in [d]$, where we follow the convention that $[d]=\{1, 2, \ldots d \}$.  Let $(X, Y) \in \mathbb{R}^{k_0 \times n} \times \mathbb{R}^{k_{d} \times n}$ denote the set of training data pairs $\{(x^{(i)}, y^{(i)})\}$ for $i \in [n]$. Gradient descent with learning rate $\gamma$ is used to find a solution to the following optimization problem:
\begin{align}
    \arg\min_{f \in \mathcal{F}} \; \frac{1}{2n} \displaystyle\sum\limits_{i=1}^{n} \ell(f(x^{(i)}), y^{(i)}),
\end{align}
where $\mathcal{F}$ is the set of linear functions represented by $f$ and $\ell$ is a real-valued loss function.  When not stated otherwise,  we assume $\ell(f(x^{(i)}), y^{(i)}) =  \|y^{(i)} -  f(x^{(i)})\|^2_2$, which is the squared loss (MSE). In addition, we denote by $W_i^{(t)}$ for ${t \in \mathbb{Z}_{\geq 0}}$ the weight matrix $W_i$ after $t$ steps of gradient descent.  When there are no additional constraints on the matrices $W_i$, then $f$ is a fully connected network.

We next introduce a generalized form of the singular value decomposition:

\begin{definition}
An \textbf{unsorted, signed singular value decomposition (usSVD)} of a matrix $A \in \mathbb{R}^{m \times n}$ is a triple $U \in \mathbb{R}^{m \times m},\Sigma \in \mathbb{R}^{m \times n}, V \in \mathbb{R}^{n \times n}$ such that $U, V$ are orthonormal matrices,
$\Sigma$ is diagonal, and $A = U \Sigma V^T$.  
\end{definition}

In contrast to the usual definition of singular value decomposition (SVD) of a matrix, the diagonal entries of $\Sigma$ may be in any order and take negative values. Throughout, we will refer to the entries of $\Sigma$ in a usSVD as singular values and the vectors in $U, V$ as singular vectors. Using the usSVD, we now generalize the notion of alignment from~\cite{LogisticAlignment} to the multi-dimensional setting. 


\begin{definition}
    \label{def: Alignment for 2 matrices}
    Let $f= W_d W_{d-1} \ldots W_1$ be a linear network. We say that $f$ is \textbf{aligned} if there exists a usSVD $W_i = U_i\Sigma_iV^T_i$ with $U_i = V_{i+1}$ for all $i \in [d-1]$. (We also say that a matrix $A$ is aligned with another matrix $B$ if there exist usSVD's $A = U_A\Sigma_Av_A^T, B = U_B\Sigma_BV_B^T$ such that $V_A = U_B$.)
\end{definition}

Note that if $W_i$ and $W_{i+1}$ are rank $1$ matrices in an aligned network $f$, then the inner product of the first columns of $V_{i+1}$ and $U_i$ is $1$ in absolute value. Hence Definition~\ref{def: Alignment for 2 matrices} is consistent with alignment in the 1-dimensional setting from \cite{LogisticAlignment}.




We next define when alignment is an invariant of training for deep linear networks. Again, such invariants are of interest since they may provide insights into properties of trained networks and significantly simplify the dynamics of gradient descent.

\begin{definition}
    \label{def: Invariance of Alignment} 
    \textbf{Alignment is an invariant of training} for a linear neural network $f$ if there exists an initialization $\{W_j^{(0)}\}_{j=1}^{d}$ such that $W_1^{(\infty)}, W_{2}^{(\infty)}, \ldots , W_d^{(\infty)}$ achieves zero training error \footnote{The interpolation condition in this definition (i.e., achieving zero training error) is important in ruling out several architectures where the layers are trivially aligned.  For example, if all layers are constrained to be diagonal matrices throughout training, then the layers are all trivially aligned, but cannot interpolate datasets where the target is not the product of a diagonal matrix with the input.} and for all gradient descent steps $t \in \mathbb{Z}_{\geq 0}
    \vspace{-0.2cm}
    \begin{enumerate}
        \item[(a)] the network $f$ is aligned; 
          
        \item[(b)] $W_i^{(t)} = U_i \Sigma_i^{(t)} V_i^T$ for all $i \in \{2, \ldots d-1\}$, that is, $U_i, V_i$ are not updated;
            \vspace{-0.2cm}
        \item[(c)] $W_1^{(t)} = U_1 \Sigma_1^{(t)} {V_1^{(t)}}^T$ and $W_d^{(t)} = U_d^{(t)} \Sigma_d^{(t)} V_d^T$, that is, $U_1$ and $V_d$ are not updated.
    \end{enumerate}
    \vspace{-0.2cm}
     If additionally, $V_1$  and $U_d$ are not updated for any $t\in\mathbb{Z}_{\geq 0}$, then we say that \textbf{strong alignment is an invariant of training}. 
\end{definition}
When alignment is an invariant of training, there are important consequences for training. In particular, note that when the network $f$ is aligned with usSVDs $W_i = U_i \Sigma_i V_i^T$ for all $1\leq i \leq d$, then 
\begin{align}
    \label{eq: aligned_network}
     f(x) = W_d\cdots W_1x = U_d 
    \left(\prod\limits_{i=0}^{d-1}\Sigma_{d-i}\right) V_1^Tx.
\end{align}
Hence if alignment is an invariant of training, then the singular vectors of layers $2$ through $d-1$ are never updated and the analysis of gradient descent can be limited to the singular values of the layers and the matrices $V_1$ and $U_d$. 





\textbf{Remarks.} For the remainder of the paper, we assume that the gradient of the loss function at initialization $\{W_i^{(0)}\}_{i=1}^{d}$ is non-zero.  Otherwise, training with gradient descent would not proceed. We also only consider datasets $(X,Y)$ for which there is a linear network that achieves loss zero. This is consistent with the assumptions in~\cite{LogisticAlignment}.  



\section{Alignment in Fully Connected Networks}
\label{sec:Alignment in Fully Connected Networks}

In this section, we first characterize when alignment is an invariant of training for  fully connected networks (Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output}). In particular, we show that this is not the case in general. We then present special classes of problems for which alignment is an invariant of training, namely autoencoding, matrix factorization, and matrix sensing.  In contrast, for a linear neural network with 1-dimensional outputs, we demonstrate that there exists an initialization for which the layers remain aligned throughout training given any dataset and any real-valued loss function.  Finally, we discuss various consequences of alignment, including a proof of linear convergence of gradient descent to an interpolating solution.

 \subsection{Characterization of Alignment with Multi-dimensional Outputs}
\label{subsec: Data Conditions for Alignment in FC Networks}

Theorem~\ref{thm: Alignment for fully connected networks with multi-dimensional output} is one of our main results and characterizes when alignment is an invariant of training in a fully connected network with multi-dimensional outputs. To simplify notation, we consider the case when the layers are square matrices, i.e. $k_i = k_j$ for all $0\leq i,j \leq d$. The general result for non-square matrices is provided in Appendix~\ref{proof strong alignment non square}.


\begin{theorem}
\label{thm: Alignment for fully connected networks with multi-dimensional output}
    Let $f: \mathbb{R}^{k} \rightarrow \mathbb{R}^{k}$ be a linear fully connected network with $d \geq 3$  square layers of size $k>1$.  Alignment is an invariant of training under the squared loss on a dataset $(X, Y)\in\mathbb{R}^{k\times n}\times \mathbb{R}^{k\times n}$ if and only if there exist orthonormal matrices $U, V \in \mathbb{R}^{k \times k}$ such that $U^TYX^TV$ and $V^TXX^TV$ are diagonal.
\end{theorem}

The full proof of this result is presented in Appendices \ref{sec: appendix outline}-\ref{sec: completing the proof};  here, we provide a proof sketch.  
\vspace{-0.2cm}
\begin{proof}[Proof Sketch]
The proof essentially follows by induction.  For the base case, we initialize the layers $\{W_i\}_{i=1}^{n}$ to satisfy the  conditions for alignment given in Definition \ref{def: Invariance of Alignment}.  Assuming that these conditions hold at gradient descent step $t$, we prove that they hold at step $t + 1$.

After substituting the alignment conditions into the gradient descent update equation for the squared loss at step $t+1$ and cancelling terms, we obtain that alignment is an invariant of training~if~and~only~if
\begin{equation}
    \label{eq: Condition for alignment in fully connected matrices}
    {U_d^{(t)}}^T \displaystyle\sum\limits_{k=1}^{n} (y^{(k)} -  f(x^{(k)})) {x^{(k)}}^T V_{1}^{(t)}
\end{equation}
is a diagonal matrix.  By considering the update for $W_1^{(t)}$ and $W_d^{(t)}$, one sees that alignment implies strong alignment and so $U_d, V_1$ are also invariant across updates.  Thus, let $U_d = U$ and $V_1 = V$.  By expanding $f(x^{(k)})$ using \eqref{eq: aligned_network}, and considering the update across multiple timesteps, we obtain that the matrix in \eqref{eq: Condition for alignment in fully connected matrices} is diagonal if and only if $U^TYX^TV$ and $V^TXX^TV$ are diagonal. To complete the proof, we show in Appendix D that under strong alignment, gradient descent converges to a solution~with~zero~training~error. 
\end{proof}


Theorem~\ref{thm: Alignment for fully connected networks with multi-dimensional output} implies that invariance of alignment throughout training holds only for special classes of problems. In particular, the above implies that alignment is an invariant of training when $X$ and $Y$ have the same right singular vectors, a very special condition on the data. Note that this corresponds to the $\epsilon=0$ data condition with the initialization considered in \cite{ImplictRegularizationBach}.
In Section \ref{sec: Experiments}, we also provide empirical support showing that alignment is not an invariant of training for important tasks that violate the data condition presented here, such as multi-class classification.

\subsection{Classes of Problems with Alignment}

We next discuss classes of problems for which alignment is an invariant of training.\\\\
\textbf{Autoencoding:}  In the case when $X = Y$, it holds that  $U^TYX^TV = U^TXX^TV$.  Taking $U = V$ to be the left singular vectors of $X$ satisfies the conditions of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output}.\\\\
\textbf{Matrix Factorization and Inversion}: In the case of matrix factorization, we have that $X = I$. Hence taking $U$ and $V$ to be the left and right singular vectors of $Y$ respectively satisfies the conditions of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output}.  For matrix inversion, we have that $Y = I$ and we proceed analogously. \\\\
\textbf{Matrix Sensing.}  Given pairs of observations $\{(M_i, y_i)\}_{i=1}^{n}$ with $M_i\in \mathbb{R}^{k \times k}$ and $y_i = \text{Tr}(M_i^T X^*)$ for some unobserved matrix $X^* \in \mathbb{R}^{k \times k}$,  gradient descent on $\{W_i\}_{i=1}^n$ is used to solve
\begin{align*}
    \arg\min_{\{W_i\} }\frac{1}{2n} \sum\limits_{i=1}^{n}\| y_i - \text{Tr}(M_i^T W_d W_{d-1} \ldots W_1) \|_2^2.
\end{align*}
Implicit regularization of linear networks in the matrix sensing setting has been analyzed extensively~\cite{DeepMatrixFactorization, BalancednessJasonLee, MatrixFactorizationNIPS2017,  MatrixSensing}. Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output} shows that alignment is an invariant of training for this problem if and only if $M_i = U \Lambda_i V^T$ for all $i \in [n]$, and $U_d = U, V_1 = V$. \\\\
\textbf{1-dimensional Outputs.}  In the following proposition, we show that alignment is an invariant of training for fully connected networks with 1-dimensional outputs for any real-valued loss function provided that gradient descent converges to zero training error. The proof is given in Appendix \ref{alignment 1d proof}.

\begin{prop}
    \label{prop: Alignment for 1 dimensional outputs}
    Alignment is an invariant of training for any linear fully connected network $f: \mathbb{R}^{k_0} \rightarrow \mathbb{R}$, any real-valued loss function, and data $(X,Y)\in \mathbb{R}^{k_0 \times n} \times \mathbb{R}^{1 \times n}$ for which gradient descent minimizes the loss to zero.
\end{prop}



\subsection{Consequences of Alignment}
\label{subsec: Consequences of Alignment}
\vspace{-0.1cm}
We next discuss various consequences of the invariance of alignment for the analysis of  training. Our explicit characterization of alignment as an invariant is significant as it allows us to greatly simplify the convergence analysis of gradient descent, which is a main goal of defining an invariant of training.

The following corollary (proof in Appendix~\ref{sec: singular update proof}) follows from the proof of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output}, and shows that under alignment the gradient descent update rule is simplified significantly.
\begin{corollary}
    \label{cor:singular-update}
    Let $r = \min(k_0, k_1, \ldots, k_d) > 1$ and let the top left $r \times r$ submatrix of $U^TY X^TV$ be $\Lambda'$ and that of $V^TX X^TV$ be $\Lambda$.  Under the invariance of strong alignment  (i.e., when $\Lambda'$ and $\Lambda$ are diagonal), we can express the partial derivative with respect to $W_i$ as follows:
    \begin{align}
    \label{eq: gradient formula}
        \frac{\partial L}{\partial W_i} = -\frac{1}{n}U_i \left(\prod\limits_{j={i+1}}^{d}{\Sigma_j}^T (U^T YX^TV_1 - \Sigma_d\cdots\Sigma_1V^TXX^T V) \prod\limits_{j={1}}^{i-1}{\Sigma_j}^T\right)V_i^T.
    \end{align}
    As a result, gradient descent only updates the first $r$ values of $\Sigma_i$. Let ${\Sigma'}_i^{(t)}$ be the top left $r \times r$ matrix of $\Sigma_i^{(t)}$. The updates are then given by:
        \vspace{-0.1cm}
    \begin{align}
    \label{eq: Updating diagonal elements under alignment}
    {\Sigma'}_i^{(t+1)} = {\Sigma'_i}^{(t)} + \frac{\gamma}{n} \prod\limits_{j = 1}^d {{\Sigma'}_j^{(t)}} (\Lambda' - \prod_{j=1}^{d}{\Sigma'}_j^{(t)} \Lambda).  
    \vspace{-1.2cm}
    \end{align}
    The other entries of $\Sigma_i^{(t+1)}$ are not updated.   
\end{corollary}

We can use this corollary to provide an explicit learning rate under which gradient descent converges linearly to a global minimum. The proof of the following proposition is given in Appendix \ref{linear convergence proof}.

\begin{prop}
    \label{prop: linear convergence}
    For $k \in [r]$, let $\sigma_k(W_i)$ denote the $k$th entry of $\Sigma_i$ in the usSVD of $W_i$, and let $\lambda_k$, $\lambda'_k$ denote the $k$th entries of $\Lambda$, $\Lambda'$ respectively. Under the conditions of Corollary~\ref{cor:singular-update} and assuming that $\sigma_k(W_i^{(0)}) > 0\,$ and $\prod\limits_{i=1}^{d}\sigma_k(W_i^{(0)})  < \frac{\lambda'_k}{\lambda_k}\,$ for all $k \in [r]$, if the learning rate satisfies $\gamma \le  \frac{n \ln 2}{d} \cdot \min_{k}\frac{ \sigma_k(W_i^{(0)})^2\lambda_k}{\lambda'^2_k}$ then
   
   
   
   
   
   
   
    gradient descent only updates the top $r$ singular values of the solution and converges linearly to the global minimum.
\end{prop}










\subsection{Alignment in the Limit of Training}
\label{sec: Alignment in Limit}

While the previous section was primarily concerned with the invariance properties of alignment, we briefly comment on understanding whether alignment will occur in the limit of training. We first present the following proposition, which states that for a 2-layer network, an aligned solution achieves the minimum $\ell_2$-norm. The proof is given in Appendix \ref{min norm proof}.
\begin{prop}
\label{prop: aligned min norm}
Let $W_1, W_2$ be matrices such that $W_2W_1 = P$, for a fixed matrix $P$. Then, $\|W_1\|^2_F + \|W_2\|^2_F$ achieves a minimum at the solution where $W_1$ and $W_2$ are aligned \emph{and} 0-balanced, i.e. there exist usSVD's $W_1 = W\Sigma V^T, W_2 = U\Sigma W^T$.
\end{prop}

It has also been shown that SGD in the overparameterized setting for a network initialized close to zero will converge to a solution close in $\ell_2$-norm to the minimum $\ell_2$-norm solution~\cite{AzizanMirrorDescent}. Therefore we expect such networks to converge to a solution which is close to an aligned solution.

\section{Alignment Under General Layer Structure}
\label{sec: Alignment in Networks with Layer Structures}
In the previous section, we analyzed fully connected networks, where parameters of each weight matrix are optimized independently.  The most commonly used deep learning models, however, rely on convolutional layers or layers with other forms of constraints.  In this section, we analyze alignment in the setting of linear networks with layer constraints.  In particular, we show that when the dimension of the subspace induced by the layer constraints is small compared to the number of training samples, alignment cannot happen, let alone be an invariant of training.  

\subsection{Linear Neural Networks with Layer Structure}

We start by setting up mathematical terminology to describe different layer structures.


\begin{definition}
\label{def_layer}
Let $\mathcal{S} \subset \mathbb{R}^{m \times n}$ be a linear subspace of matrices and let $\{A_i\}_{i=1}^{r}$ be an orthogonal\footnote{Orthogonality is w.r.t the inner product $\langle A, B \rangle = \text{Tr}(A^TB)$, or equivalently the dot product in $\mathbb{R}^{mn}$} basis for $\mathcal{S}$.
Layer $W_i$ has \textit{layer structure} $\mathcal{S}$ if $W_i\in\mathcal{S}$, i.e., there exist coefficients  $\{c_j^i\}_{j=1}^r \subset \mathbb{R}$ such that $W_i = \sum_{j=1}^{r}c_j^i A_j$,  and gradient descent operates on the $\{c_j^i\}_{i,j=1}^r$.   
\end{definition}
Definition~\ref{def_layer} encompasses layer structures commonly used in practice, such as:

\begin{itemize}
\vspace{-0.1cm}
\item\textit{Convolutional layers:} treating a $p\times p$ image as a vector in $\mathbb{R}^{p^2}$, a single $s \times s$ convolutional filter with stride 1 and padding $\frac{s - 1}{2}$ maps the image to another $p\times p$ image; this linear transformation can be represented as a matrix in $\mathbb{R}^{p^2 \times p^2}$ and the set of all such transformations forms an $s^2$-dimensional subspace. The parameters of the filter are coefficients of an orthogonal basis of this subspace, and hence performing gradient descent on the parameters is equivalent to optimizing over the basis coefficients; see Appendix~\ref{conv example} for an example.  
\vspace{-0.1cm}
\item\textit{Layers with Sparse Connections:} Consider a fixed connection pattern between layers such that the $j^{th}$ hidden unit in layer $i$ depends only on a subset of units in layer $i-1$. In this case, the subspace $\mathcal{S}$ consists of matrices where particular entries are forced to be zero corresponding to missing connections between features in consecutive layers.
\end{itemize}
\vspace{-0.1cm}

The following theorem provides, in closed-form, the gradient descent update rules for linear networks with layer structure. The proof is provided in Appendix~\ref{projected gd proof}.
\vspace{0.1cm}

\begin{theorem}
\label{thm:projected gd}
Performing gradient descent on the basis coefficients $\{c_j^i\}_{j=1}^r$ leads to the following weight matrix updates:
$$W_i^{(t+1)} = W_i^{(t)} - \eta\cdot\pi_\mathcal{S}\left( \frac{\partial l}{\partial W_i^{(t)}} \right),$$
where $\pi_\mathcal{S}$ denotes the projection operator onto $\mathcal{S}$.
\end{theorem}

Theorem \ref{thm:projected gd} shows that gradient descent in networks with layer structure is equivalent to projected gradient descent\footnote{$\pi_\mathcal{S}$ is a projection in the traditional sense if and only if the $A_j$ form an orthonormal basis; otherwise, $\pi_\mathcal{S}$ is a projection onto $\mathcal{S}$ followed by an appropriate scaling in each basis direction.}.  Hence alignment is an invariant of training if and only if it holds throughout the projected gradient descent updates and leads to an aligned solution~with~zero~training~loss.

\subsection{Necessary Condition for Alignment}

Motivated by the above characterization via projected gradient descent, we now show that for layer structures with constrained dimension, aligned networks generally cannot achieve zero training error under the squared loss, given sufficient data (Proposition \ref{prop: No alignment with constrained layers}). This is the case even when there is a solution with the desired layer structure that achieves zero training error.  Hence, if loss is minimized to zero, gradient descent must lead to a non-aligned network. 

We first show that for an aligned network which interpolates the data, the first and last layer must align with the pseudoinverse. The proof of this result is presented in Appendix~\ref{conv alignment lemma}.

\begin{prop}
    \label{prop: Interpolation with layer structure}
    Let $(X,Y) \in \mathbb{R}^{k_0 \times n} \times \mathbb{R}^{k_d \times n}$ such that $n \ge k_0$ and $X$ is full-rank (ensuring that $XX^T$ is invertible).
    If an aligned network $f = W_d W_{d-1} \ldots W_1$ achieves zero error under squared loss (i.e. if $Y = f(X)$),
    then $W_d^T$ aligns with $YX^T(XX^T)^{-1}$, which in turn aligns with $W_1^T$.
\end{prop}

The following result tells us that when a linear space $\mathcal{S}$
of matrices is sufficiently low-dimensional,
the set of matrices that align with an element of $\mathcal{S}$ has measure zero.
While we are mainly interested in the setting where $n\geq k$, we state it in full generality using $\binom{m}{2}=0$, when $m<2$.
\begin{prop}\label{prop: No alignment with constrained layers}
    Let $\mathcal{S}$ be an $r$-dimensional linear subspace of $k\times k$ matrices.
    If $r < k-1-\binom{k-n}{2}$
    then the set of matrices of size $k\times n$
    that can align with an element of $\mathcal{S}$, excluding scalar multiples of the identity,
    has Lebesgue measure zero.
\end{prop}


The proof of Proposition~\ref{prop: No alignment with constrained layers} is provided in Appendix~\ref{conv alignment bound}.
Taken together, Propositions \ref{prop: Interpolation with layer structure} and \ref{prop: No alignment with constrained layers} directly imply Theorem~\ref{thm: No Alignment in constrained layers},
which states that alignment does not occur in linear networks with constrained layer structures given enough training samples.
To simplify notation, we let $k=k_0=\cdots =k_d$ and let all layers have the same structure, $\mathcal{S}$.  The statement can trivially be extended to the general setting without these assumptions.








\begin{theorem}
\label{thm: No Alignment in constrained layers}
    Let $n \ge k$, let $X,Y \in \mathbb{R}^{k\times n}$ be generic,
    let $\mathcal{S} \subset \mathbb{R}^{k \times k}$ be a linear subspace of dimension $r < k-1$,
    and let $W_1,\dots,W_d \in \mathcal{S}$
    such that at least one $W_i$ is not a scalar multiple of the identity\footnote{This is not a serious restriction;
modulo scalar multiplication, the only case in which such a network could achieve zero loss is autoencoding, in which case the latent space would be a scalar multiple of the data itself.}.
    If the network $f = W_d \cdots W_1$ satisfies $Y = f(X)$,
    then $f$ is not aligned.
\end{theorem}



Theorem \ref{thm: No Alignment in constrained layers} is in contrast to fully connected networks (i.e., no layer constraints), where we showed that alignment is possible for particular classes of problems including autoencoders. An explicit example of a convolutional linear autoencoder, where alignment is ruled out by Theorem~\ref{thm: No Alignment in constrained layers}, is discussed next. 




\begin{example}
    If $m \ge 4$, then a generic dataset consisting of $n \ge m^2$ $m\times m$ images cannot be aligned by any convolutional linear autoencoder with filter size $3$, aside from the trivial case where all layers are scalar multiples of the identity.  This follows from letting $k = m^2$, $r = 9$ in Proposition~\ref{prop: No alignment with constrained layers}.
\end{example}










\section{Empirical Support}
\label{sec: Experiments}

In this section, we provide experimental results to validate our theoretical findings in the settings where alignment is not an invariant of training\footnote{Hyperparameter settings are detailed in Appendix~\ref{experimental setup}}. We measure two properties: (1) invariance of alignment from initialization, and (2) alignment between layers.  Invariance of alignment at time $t$ is measured by the average dot product between corresponding columns of $U_i^{(t)}$ and $U_i^{(0)}$, as well as $V_i^{(t)}$ and $V_i^{(0)}$. Alignment is measured by the average dot product between corresponding columns of $U_i^{(t)}$ and $V_{i+1}^{(t)}$. For both, a value of 1 is perfect alignment / invariance. 


\begin{figure*}[!t]
    \centering
    \begin{subfigure}[t]{.33 \textwidth}
        \centering
        \includegraphics[scale=0.3]{Figures/rand_data_final.png}
       
        \caption{\centering Multi-dimensional regression on\newline random data with squared loss.}
    \end{subfigure}%
        \begin{subfigure}[t]{.33 \textwidth}
        \centering
        \includegraphics[scale=0.3]{Figures/mse_multiclass_final.png}
       
        \caption{\centering Multi-class classification on\newline MNIST with squared loss.}
    \end{subfigure}%
    \begin{subfigure}[t]{.33 \textwidth}
        \centering
        \includegraphics[scale=0.3]{Figures/cross_entropy_multiclass_final.png}
      
        \caption{\centering Multi-class classification on\newline MNIST with cross entropy loss.}
    \end{subfigure}%
    \vspace{-0.1cm}
         \caption{Examples of fully connected networks with multi-dimensional outputs where alignment is not an invariant of training.}
         \vspace{-0.3cm}
    \label{fig: Fully connected networks do not align}
\end{figure*}


\begin{figure*}[!t]
    \centering
    \begin{subfigure}[t]{.4 \textwidth}
        \centering
        \includegraphics[scale=0.3]{Figures/toep_final.png}
        \vspace{-0.12cm}
        \caption{\centering Matrix factorization with layers\newline constrained to be Toeplitz matrices.}
    \end{subfigure}%
    \begin{subfigure}[t]{.4 \textwidth}
        \centering
        \includegraphics[scale=0.3]{Figures/conv_1sample_final.png}
        \vspace{-0.12cm}
        \caption{\centering Autoencoding a single MNIST example\newline using a convolutional network.}
    \end{subfigure}
        \vspace{-0.12cm}
        \caption{Examples of layer constrained networks, where alignment is not an invariant of training.}
       
       
    \label{fig: General networks do not align.}
    \vspace{-0.5cm}
\end{figure*}







We begin with examples demonstrating that alignment is not an invariant of training for fully connected networks when the data conditions of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output} are violated. Figure \ref{fig: Fully connected networks do not align}a shows an example where alignment is not an invariant for multi-dimensional regression with random data under squared loss.  We used standard normal inputs $X \in \mathbb{R}^{9\times 9}$ and targets $Y \in \mathbb{R}^{9 \times 9}$, and a 2-hidden layer network initialized so that alignment holds at the start of training.  Since $X$ and $Y$ do not have the same right singular vectors, the conditions of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output} are violated, and hence alignment is not an invariant of training, which is reflected in Figure~\ref{fig: Fully connected networks do not align}a. In Figures \ref{fig: Fully connected networks do not align}b and c, we show that alignment is also not an invariant in standard classification settings.  In particular, we trained a 2-hidden layer fully connected network to classify a linearly separable subset of $256$ MNIST examples under MSE loss and cross entropy loss. Figure \ref{fig: Fully connected networks do not align}b is consistent with the generalization of Theorem \ref{thm: Alignment for fully connected networks with multi-dimensional output} to non-square layers (see Appendix~\ref{proof strong alignment non square}). It is interesting that this result transfers to the case of cross entropy loss, at least empirically, suggesting that our theoretical results may also be relevant for other loss functions.



In networks with constrained layer structure, Theorem~\ref{thm: No Alignment in constrained layers} shows that given a sufficient amount of data, alignment cannot occur. We now present empirical evidence that alignment is not an invariant of training, even when the number of training samples is much smaller than the output dimension of the network or the dimensionality of the layer structure is much larger than the output dimension.


We provide an example from matrix factorization ($Y \in \mathbb{R}^{k \times k}$, $X = I$).  Here, $k = n$, so Theorem~\ref{thm: No Alignment in constrained layers} states that alignment is impossible when the linear structure has dimension $r  < k - 1$.  In Figure \ref{fig: General networks do not align.}a, we show that alignment does not occur also when $r \geq k - 1$.  In particular, alignment is not an invariant when training a 2-hidden layer Toeplitz network to factorize a $4 \times 4$ matrix.  Our network has $4$ hidden units per layer and thus $r = 7, k = 4, n = 4$. Even when $n < r < k$, we observe that alignment is not an invariant.  In Figure \ref{fig: General networks do not align.}b, we show that alignment is not an invariant of training when autoencoding a single MNIST example using a 2-hidden layer linear convolutional network (i.e. $n = 1, r = 9, k = 784$).  



\section{Discussion}
\vspace{-1mm}
We generalized the definition of alignment to linear networks with multi-dimensional outputs. We then analyzed the invariance properties of alignment, showing that under particular data conditions alignment is an invariant for fully connected networks, which allows us to significantly simply the convergence analysis of gradient descent.  We then extended our analysis of alignment to networks with constrained layer structures, such as convolutions, and proved that alignment cannot be an invariant of training in such networks when the dimension of the layer structure $r$ is small compared to the number of training samples $n$. 

While the simplification of gradient descent convergence analysis in the fully connected setting shows that our alignment definition is useful in understanding such networks, the fact that it does not generalize as an invariant to the constrained layer structure setting suggests that other approaches may be necessary to fully understand implicit regularization, such as studying how architecture influences the function classes that can be represented by deep networks~\cite{savarese2019infiniteWidth, IdentityCrisis, RadhaAutoencoders}. 













\section*{Acknowledgements}
A. Radhakrishnan and C. Uhler thank the Simons Institute at UC Berkeley for hosting them during the summer 2019 program on ``Foundations of Deep Learning'', which facilitated this work. A.~Radhakrishnan and C.~Uhler were partially supported by the National Science Foundation (DMS-1651995), Office of Naval Research (N00014-17-1-2147 and N00014-18-1-2765), IBM, and a Simons Investigator Award  to C.~Uhler. Daniel Irving Bernstein was supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship (DMS-1802902).  The Titan Xp used for this research was donated by the NVIDIA Corporation.

\bibliographystyle{plain}

2020-06-18T02:06:32.000
2003
2003.06340
en
https://arxiv.org/abs/2003.06340
We study the properties of alignment, a form of implicit regularization, in linear neural networks under gradient descent. We define alignment for fully connected networks with multidimensional outputs and show that it is a natural extension of alignment in networks with 1-dimensional outputs as defined by Ji and Telgarsky, 2018. While in fully connected networks, there always exists a global minimum corresponding to an aligned solution, we analyze alignment as it relates to the training process. Namely, we characterize when alignment is an invariant of training under gradient descent by providing necessary and sufficient conditions for this invariant to hold. In such settings, the dynamics of gradient descent simplify, thereby allowing us to provide an explicit learning rate under which the network converges linearly to a global minimum. We then analyze networks with layer constraints such as convolutional networks. In this setting, we prove that gradient descent is equivalent to projected gradient descent, and that alignment is impossible with sufficiently large datasets.
Machine Learning (cs.LG); Machine Learning (stat.ML)
On Alignment in Deep Linear Neural Networks
Qwen/Qwen-72B
1. YES
2. YES