Year: 2020

Abstract:
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.

heading: 1 INTRODUCTION
text: Although overparameterized deep networks can interpolate randomly labeled training data (Du et al., 2019; Wu et al., 2019), training overparameterized networks with modern optimizers often leads to solutions that generalize well. This suggests that there is a form of implicit regularization occurring through training (Zhang et al., 2017).
As an example of implicit regularization, the authors in Ji & Telgarsky (2018) 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 WdWd−1 . . .W1, the top left/right singular vectors ui and vi of layer Wi satisfy |vTi+1ui| → 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 3); 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 Ji & Telgarsky (2018) to show convergence to a max-margin solution.
In this work, we generalize the definition of 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. Prior works (Gidel et al., 2019; Saxe et al., 2014; 2019) have implicitly relied on invariance of alignment as an assumption on initialization to simplify training dynamics for 2 layer networks. In this work, we provide necessary and sufficient conditions for when alignment is an invariant for networks of arbitrary depth. Our main contributions are as follows:
1. We extend the definition of alignment from the 1-dimensional classification setting to the multi-dimensional setting (Definition 2) and characterize when alignment is an invariant of training in linear fully connected networks with multi-dimensional outputs (Theorem 1).
2. 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 any real-valued loss function and any training dataset.
3. 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 1).
4. 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 3).
5. We support our theoretical findings via experiments in Section 6.
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.

heading: 2 RELATED WORK
text: Implicit regularization in overparameterized networks has become a subject of significant interest (Gunasekar et al., 2018a;b; Martin & Mahoney, 2018; Neyshabur et al., 2014). In order to characterize the specific form of implicit regularization, several works have focused on analyzing deep linear networks (Arora et al., 2019b; Gunasekar et al., 2018b; 2017; Soudry et al., 2018). 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 alignment, identified by Ji & Telgarsky (2018) to analyze 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.
lim t→∞
W (t) i
‖W (t)i ‖F = uiv
T i
and that adjacent layers, Wi+1 and Wi become aligned, i.e. |vTi+1ui| → 1. In addition, Ji & Telgarsky (2018) 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 (Arora et al., 2019c; Zou et al., 2018).
Our definition of invariance of alignment extends assumptions on initialization appearing in various prior works (Gidel et al., 2019; Saxe et al., 2014; 2019). While the connection to alignment was not mentioned in their work, the authors in Gidel et al. (2019) begin to generalize alignment to multidimensional outputs by considering two-layer networks initialized so that layers are aligned with each other and to the data. We generalize this to networks of any depth, showing that our definition of alignment corresponds to the initialization considered in Gidel et al. (2019). Moreover, we establish necessary and sufficient conditions for when alignment is an invariant of training in Theorem 1 instead of assuming these conditions. Furthermore, their result on sequential learning of components can be derived via our singular value update rule in Corollary 1.
Balancedness is another closely related form of implicit regularization in linear neural networks. It was introduced in Arora et al. (2018) and defined as the property that if WTi Wi = Wi+1W T i+1 for all i at initialization, then this property is invariant under gradient flow. Du et al. (2018) present a more general form, that WTi Wi −Wi+1WTi+1 is constant under gradient flow. In practice, analyses rely on this quantity being close to or exactly zero. In this exact setting, balancedness indeed implies alignment of singular vector spaces between consecutive layers. To study gradient descent, slightly more general notions such as approximate balancedness (Arora et al., 2019a) and -balancedness have been introduced. Du et al. (2018) 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.

heading: 3 DEFINITION OF ALIGNMENT IN THE MULTI-DIMENSIONAL SETTING
text: 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 linear neural networks. Let f : Rk0 → Rkd denote such a d-layer network, i.e. f(x) = WdWd−1 . . .W1x, (1) where Wi ∈ Rki×ki−1 for i ∈ [d], where we follow the convention that [d] = {1, 2, . . . d}. Let (X,Y ) ∈ Rk0×n × Rkd×n denote the set of training data pairs {(x(i), y(i))} for i ∈ [n]. Gradient descent with learning rate γ is used to find a solution to the following optimization problem:
arg min f∈F
1
2n n∑ i=1 `(f(x(i)), y(i)), (2)
where F is the set of linear functions represented by f and ` is a real-valued loss function. When not stated otherwise, we assume `(f(x(i)), y(i)) = ‖y(i) − f(x(i))‖22, which is the squared loss (MSE). In addition, we denote by W (t)i for t ∈ Z≥0 the weight matrix Wi after t steps of gradient descent. When there are no additional constraints on the matrices Wi, then f is a fully connected network.
We next introduce a generalized form of the singular value decomposition: Definition 1. An unsorted, signed singular value decomposition (usSVD) of a matrix A ∈ Rm×n is a triple U ∈ Rm×m,Σ ∈ Rm×n, V ∈ Rn×n such that U, V are orthonormal matrices, Σ is diagonal, and A = UΣV T .
In contrast to the usual definition of singular value decomposition (SVD) of a matrix, the diagonal entries of Σ may be in any order and take negative values. Throughout, we will refer to the entries of Σ 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 Ji & Telgarsky (2018) to the multi-dimensional setting. Definition 2. Let f = WdWd−1 . . .W1 be a linear network. We say that f is aligned if there exists a usSVD Wi = UiΣiV Ti with Ui = Vi+1 for all i ∈ [d− 1]. (We also say that a matrix A is aligned with another matrix B if there exist usSVD’s A = UAΣAV TA , B = UBΣBV T B such that VA = UB .)
Note that if Wi and Wi+1 are rank 1 matrices in an aligned network f , then the inner product of the first columns of Vi+1 and Ui is 1 in absolute value. Hence Definition 2 is consistent with alignment in the 1-dimensional setting from Ji & Telgarsky (2018).
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. Definition 3. Alignment is an invariant of training for a linear neural network f if there exists an initialization {W (0)j }dj=1 such that W (∞) 1 ,W (∞) 2 , . . . ,W (∞) d achieves zero training error
1 and for all gradient descent steps t ∈ Z≥0
(a) the network f is aligned;
(b) W (t)i = UiΣ (t) i V T i for all i ∈ {2, . . . d− 1}, that is, Ui, Vi are not updated;
(c) W (t)1 = U1Σ (t) 1 V (t) 1 T and W (t)d = U (t) d Σ (t) d V T d , that is, U1 and Vd are not updated.
If additionally, V1 and Ud are not updated for any t ∈ Z≥0, then we say that strong alignment is an invariant of training.
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 Wi = UiΣiV Ti for all 1 ≤ i ≤ d, then
f(x) = Wd · · ·W1x = Ud ( d−1∏ i=0 Σd−i ) V T1 x. (3)
1The 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.
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 V1 and Ud.
Remarks. For the remainder of the paper, we assume that the gradient of the loss function at initialization {W (0)i }di=1 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 Ji & Telgarsky (2018).

heading: 4 ALIGNMENT IN FULLY CONNECTED NETWORKS
text: In this section, we first characterize when alignment is an invariant of training for fully connected networks (Theorem 1). 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 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.

heading: 4.1 CHARACTERIZATION OF ALIGNMENT WITH MULTI-DIMENSIONAL OUTPUTS
text: Theorem 1 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. ki = kj for all 0 ≤ i, j ≤ d. The general result for non-square matrices is provided in Appendix D.
Theorem 1. Let f : Rk → Rk be a linear fully connected network with d ≥ 3 square layers of size k > 1. Alignment is an invariant of training under the squared loss on a dataset (X,Y ) ∈ Rk×n × Rk×n if and only if there exist orthonormal matrices U, V ∈ Rk×k such that UTY XTV and V TXXTV are diagonal.
The full proof of this result is presented in Appendices A-E; here, we provide a proof sketch.
Proof Sketch. The proof essentially follows by induction. For the base case, we initialize the layers {Wi}di=1 to satisfy the conditions for alignment given in Definition 3. 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
U (t) d T n∑ k=1 (y(k) − f(x(k)))x(k) T V (t) 1 (4)
is a diagonal matrix. By considering the update for W (t)1 and W (t) d , one sees that alignment implies strong alignment and so Ud, V1 are also invariant across updates. Thus, let Ud = U and V1 = V . By expanding f(x(k)) using equation 3, and considering the update across multiple timesteps, we obtain that the matrix in equation 4 is diagonal if and only if UTY XTV and V TXXTV 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.
Theorem 1 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 = 0 data condition with the initialization considered in Gidel et al. (2019). In Section 6, 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.

heading: 4.2 CLASSES OF PROBLEMS WITH ALIGNMENT
text: We next discuss classes of problems for which alignment is an invariant of training.
Autoencoding: In the case when X = Y , it holds that UTY XTV = UTXXTV . Taking U = V to be the left singular vectors of X satisfies the conditions of Theorem 1.
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 1. For matrix inversion, we have that Y = I and we proceed analogously.
Matrix Sensing. Given pairs of observations {(Mi, yi)}ni=1 with Mi ∈ Rk×k and yi = Tr(MTi X∗) for some unobserved matrix X∗ ∈ Rk×k, gradient descent on {Wi}ni=1 is used to solve
arg min {Wi}
1
2n n∑ i=1 ‖yi − Tr(MTi WdWd−1 . . .W1)‖22.
Implicit regularization in the matrix sensing setting has been analyzed extensively (Arora et al., 2019b; Du et al., 2018; Gunasekar et al., 2017; Li et al., 2018). Theorem 1 shows that alignment is an invariant of training in this setting if and only if Mi = UΛiV T for all i ∈ [n], and Ud = U, V1 = V .
1-dimensional Outputs. In Appendix F, 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.

heading: 4.3 CONSEQUENCES OF ALIGNMENT
text: 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 B) follows from the proof of Theorem 1, and shows that under alignment the gradient descent update rule is simplified significantly.
Corollary 1. Let r = min(k0, k1, . . . , kd) > 1 and let the top left r × r submatrix of UTY XTV be Λ′ and that of V TXXTV be Λ. Under the invariance of strong alignment (i.e., when Λ′ and Λ are diagonal), we can express the partial derivative with respect to Wi as follows:
∂L ∂Wi = − 1 n Ui  d∏ j=i+1 Σj T (UTY XTV1 − Σd · · ·Σ1V TXXTV ) i−1∏ j=1 Σj T V Ti . (5) As a result, gradient descent only updates the first r values of Σi. Let Σ′ (t) i be the top left r× r matrix of Σ(t)i . The updates are then given by:
Σ′ (t+1) i = Σ ′ i (t)
+ γ
n d∏ j=1 Σ′ (t) j (Λ ′ − d∏ j=1 Σ′ (t) j Λ). (6)
The other entries of Σ(t+1)i are not updated.
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 C.
Proposition 1. For k ∈ [r], let σk(Wi) denote the kth entry of Σi in the usSVD of Wi, and let λk, λ′k denote the kth entries of Λ, Λ ′ respectively. Under the conditions of Corollary 1 and
assuming that σk(W (0) i ) > 0 and d∏ i=1 σk(W (0) i ) < λ′k λk for all k ∈ [r], if the learning rate satisfies
γ ≤ n ln 2d ·mink σk(W
(0) i ) 2λk λ′2k
then gradient descent only updates the top r singular values of the solution and converges linearly to the global minimum.
Remarks. Shamir (2018) shows that for linear neural networks with one-dimensional outputs, the rate of convergence can be exponentially slow in the depth. Proposition 1 shows that for a fixed depth, gradient descent converges linearly. Our analysis in Appendix C shows that our upper bound on the rate of convergence can also grow exponentially in the depth.
Alignment in the Limit of Training. We briefly comment on understanding whether alignment will occur in the limit of training. The following proposition, which states that for a 2-layer network, an aligned solution achieves the minimum `2-norm. The proof is given in Appendix G. Proposition 2. Let W1,W2 be matrices such that W2W1 = P , for a fixed matrix P . Then, ‖W1‖2F + ‖W2‖2F achieves a minimum at the solution where W1 and W2 are aligned and 0-balanced, i.e. there exist usSVD’s W1 = WΣV T ,W2 = UΣWT .
It has been shown that SGD in the overparameterized setting for a network initialized close to zero will converge to a solution close in `2-norm to the minimum `2-norm solution (Azizan et al., 2019). Therefore we expect such networks to converge to a solution which is close to an aligned solution.

heading: 5 ALIGNMENT UNDER GENERAL LAYER STRUCTURE
text: 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.

heading: 5.1 LINEAR NEURAL NETWORKS WITH LAYER STRUCTURE
text: We start by setting up mathematical terminology to describe different layer structures. Definition 4. Let S ⊂ Rm×n be a linear subspace of matrices and let {Ai}ri=1 be an orthogonal2 basis for S . Layer Wi has layer structure S if Wi ∈ S , i.e., there exist coefficients {cij}rj=1 ⊂ R such that Wi = ∑r j=1 c i jAj , and gradient descent operates on the {cij}ri,j=1.
Definition 4 encompasses layer structures commonly used in practice, such as:
Convolutional layers: Treating a p× p image as a vector in Rp2 , a single s× s convolutional filter with stride 1 and padding (s−1)/2 maps the image to another p×p image; this linear transformation is a matrix in Rp2×p2 and the set of all such transformations forms an s2-dimensional subspace. The parameters of the filter are coefficients of an orthogonal basis of this subspace; see Appendix I.
Layers with Sparse Connections: Consider a fixed connection pattern between layers such that the jth hidden unit in layer i depends only on a subset of units in layer i − 1. In this case, the subspace S consists of matrices where particular entries are forced to be zero corresponding to missing connections between features in consecutive layers.
The following theorem provides, in closed-form, the gradient descent update rules for linear networks with layer structure. The proof is provided in Appendix H.
Theorem 2. Performing gradient descent on the basis coefficients {cij}rj=1 leads to the following weight matrix updates:
W (t+1) i = W (t) i − η · πS
( ∂l
∂W (t) i
) ,
where πS denotes the projection operator onto S.
Theorem 2 shows that gradient descent in networks with layer structure is equivalent to projected gradient descent3. 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.
2Orthogonality is w.r.t the inner product 〈A,B〉 = Tr(ATB), or equivalently the dot product in Rmn 3πS is a projection in the traditional sense if and only if the Aj form an orthonormal basis; otherwise, πS is
a projection onto S followed by an appropriate scaling in each basis direction.

heading: 5.2 NECESSARY CONDITION FOR ALIGNMENT
text: 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 4). 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 J.
Proposition 3. Let (X,Y ) ∈ Rk0×n × Rkd×n such that n ≥ k0 and X is full-rank (ensuring that XXT is invertible). If an aligned network f = WdWd−1 . . .W1 achieves zero error under squared loss (i.e. if Y = f(X)), then WTd aligns with Y X T (XXT )−1, which in turn aligns with WT1 .
The following result tells us that when a linear space S of matrices is sufficiently low-dimensional, the set of matrices that align with an element of S has measure zero. While we are mainly interested in the setting where n ≥ k, we state it in full generality using ( m 2 ) = 0, when m < 2.
Proposition 4. Let S be an r-dimensional linear subspace of k × k matrices. If r < k − 1− ( k−n 2 ) then the set of matrices of size k × n that can align with an element of S , excluding scalar multiples of the identity, has Lebesgue measure zero.
The proof of Proposition 4 is provided in Appendix K. Taken together, Propositions 3 and 4 imply Theorem 3, which states that alignment does not occur in linear networks with constrained layer structures given enough training samples. We assume k = k0 = · · · = kd and that all layers have the same structure, S. The statement can trivially be extended to the general setting. Theorem 3. Let n ≥ k, let X,Y ∈ Rk×n be generic, let S ⊂ Rk×k be a linear subspace of dimension r < k − 1, and let W1, . . . ,Wd ∈ S such that at least one Wi is not a scalar multiple of the identity4. If the network f = Wd · · ·W1 satisfies Y = f(X), then f is not aligned.
Theorem 3 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 3, is discussed next.
Example. If m ≥ 4, then a generic dataset consisting of n ≥ m2 m×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 = m2, r = 9 in Proposition 4.

heading: 6 EMPIRICAL SUPPORT
text: In this section, we provide experimental results to validate our findings5. 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 (t)i and U (0)i , as well as V (t) i and V (0) i . Alignment is measured by the average dot product between corresponding columns of U (t)i and V (t) i+1. For both, a value of 1 is perfect alignment / invariance.
We begin by demonstrating that alignment is not an invariant of training for fully connected networks when the data conditions of Theorem 1 are violated. Figure 1a 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 ∈ R9×9 and targets Y ∈ R9×9, and a 2-hidden layer network initialized so that alignment holds at the start of training. SinceX and Y do not have the same right singular vectors, the conditions of Theorem 1 are violated, and hence alignment is not an invariant of training. In Figures 1b and c, we show that alignment is also not an invariant in standard classification settings. 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 1b is consistent with the generalization of
4This 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.
5Hyperparameter settings are detailed in Appendix M
Theorem 1 (Appendix D). Interestingly, this result empirically transfers to the case of cross entropy loss, suggesting that our theoretical results may also be relevant for other loss functions.
In networks with constrained layer structure, Theorem 3 shows that given sufficient 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 that of the output. In the setting of matrix factorization (Y ∈ Rk×k, X = I), k = n, so Theorem 3 states that alignment is impossible when the linear structure has dimension r < k − 1. In Figure 2a, we observe that alignment is not invariant also even when r ≥ k − 1, by training a 2-hidden layer Toeplitz network to factorize a 4× 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 2b, 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). In Appendix L, we provide empirical validation that alignment is indeed an invariant of training when the data conditions of Theorem 1 are satisfied.

heading: 7 DISCUSSION
text: 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 simplify 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 (Savarese et al., 2019; Zhang et al., 2020; Radhakrishnan et al., 2019).

heading: A OUTLINE OF PROOF FOR THEOREM 1, COROLLARY 1, AND PROPOSITION 1
text: We now provide an outline of our results and proofs.
1. In Appendix A, we introduce Lemmas 1, 2, which will be used to prove Theorem 1.
2. In Appendix B, we provide the proof of Corollary 1 - the simplification of gradient descent under alignment - which relies on Lemma 2.
3. In Appendix C, we provide the proof of Proposition 1 - linear convergence under strong alignment - which relies on Corollary 1.
4. In Appendix D, we introduce Theorem 4, which is a generalization of Theorem 1 to fully connected networks with rectangular layers. We use Lemma 2 and Proposition 1 to prove Theorem 4.
5. In Appendix E, we finally prove Theorem 1, which follows from Theorem 4.
Here, we present two lemmas that will be used extensively in our proofs.
Clearly strong alignment being an invariant implies that alignment is an invariant. Now we show that alignment implies strong alignment in the case of networks with square matrix layers.
Lemma 1. Let {Wi}di=1 ⊂ Rk×k, where d ≥ 3. If alignment is an invariant of training under the squared loss for network f = WdWd−1 . . .W1 on data (X,Y ) ∈ Rk×n × Rk×n, then strong alignment is also invariant.
Proof. Assume that alignment is an invariant of training. Gradient descent on the objective
arg min f∈F
1
2n n∑ i=1 ‖y(i) − f(x(i))‖22 (7)
proceeds via the following update rule:
W (t+1) i = W (t) i +
γ n (W (t) d . . .W (t) i+1) T n∑ l=1 (y(l) − f(x(l)))(W (t)i−1 . . .W (t) 1 x (l))T , ∀i ∈ [d]. (8)
Since alignment is an invariant, the initialization satisfies W (t)i = UiΣ (t) i V T i for 2 ≤ i ≤ d − 1, W (t) 1 = U1Σ (t) 1 V (t) 1 T , andW (t)d = U (t) d Σ (t) d V T d , where Ui = Vi+1 for i ∈ [d−1]. For 2 ≤ i ≤ d−1, substituting into Equation (8) yields
W (t+1) i = UiΣ (t) i V T i +
γ n (U (t) d Σ (t) d · · ·Σ (t) i+1V T i+1) T n∑ l=1 (y(l) − f(x(l)))(Ui−1Σ(t)i−1 · · ·Σ (t) 1 V (t) 1 T x(l))T
= Ui Σ(t)i + γn d∏
j=i+1
Σ (t) j
T U
(t) d T n∑ l=1 (y(l) − f(x(l)))x(l) T V (t) 1 i−1∏ j=1 Σ (t) j T V Ti = Ui Σ(t)i + γn d∏
j=i+1
Σ (t) j
T (U
(t) d
T Y XTV
(t) 1 − Σ (t) d · · ·Σ (t) 1 V (t) 1
T XXTV
(t) 1 ) i−1∏ j=1 Σ (t) j T V Ti . Since alignment is an invariant, the quantity
d∏ j=i+1 Σ (t) j T (U (t) d T Y XTV (t) 1 − Σ (t) d · · ·Σ (t) 1 V (t) 1 T XXTV (t) 1 ) i−1∏ j=1 Σ (t) j T (9)
is a diagonal matrix for all t. Since each of the Σj are square, full rank matrices, the quantity
U (t) d
T Y XTV
(t) 1 − Σ (t) d · · ·Σ (t) 1 V (t) 1
T XXTV
(t) 1
must be diagonal for all t.
The update rule for W1 is given by
W (t+1) 1 = W (t) 1 +
γ n (W (t) d · · ·W (t) 2 ) T n∑ l=1 (y(l) − f(x(l)))x(l) T
U1Σ (t+1) 1 V (t+1) 1 T = U1Σ (t) 1 V (t) 1 T + V2 d∏ j=2 Σ (t) j T U (t) d T (Y XT − UdΣ(t)d · · ·Σ (t) 1 V (t) 1 T XXT )
=⇒ Σ(t+1)1 V (t+1) 1
T V
(t) 1 = Σ (t) 1 + d∏ j=2 Σ (t) j T (U (t) d T Y XTV (t) 1 − Σ (t) d · · ·Σ (t) 1 V (t) 1 T XXTV (t) 1 ),
which is diagonal. Therefore V (t+1)1 T V (t) 1 is diagonal, and since this is also an orthogonal matrix we must have that V (t+1)1 = V (t) 1 .
Similarly, the update rule for Wd is given by:
W (t+1) d = W (t) d +
γ
n n∑ l=1 (y(l) − f(x(l)))x(l) T (W (t) d−1 · · ·W (t) 1 ) T
U (t+1) d Σ (t+1) d V T d = U (t) d Σ (t) 1 V T d + (Y X T − U (t)d Σ (t) d · · ·Σ (t) 1 V (t) 1
T XXT )V
(t) 1 d−1∏ j=1 Σ (t) j T U (t) d−1 T
=⇒ U (t)d T U (t+1) d Σ (t+1) d = Σ (t) d + (U (t) d T Y XTV (t) 1 − Σ (t) d · · ·Σ (t) 1 V (t) 1 T XXTV (t) 1 ) d−1∏ j=1 Σ (t) j T U (t) d−1 T ,
which is diagonal. Therefore U (t)d T U (t+1) d is also diagonal, implying that U (t) d = U (t+1) d . Therefore strong alignment is also an invariant. This means that alignment being an invariant and strong alignment being an invariant are equivalent in the setting where all the ki are equal.
Now that we have shown the equivalence of alignment being an invariant and strong alignment being an invariant in the setting where all the layers are square, we prove the following lemma for the general case where the ki are not necessarily all equal.
Lemma 2. Let f : Rk0 → Rkd be a linear fully connected network as in Equation equation 1, and let r = min(k0, . . . , kn). For training under the squared loss on the dataset (X,Y ), there exists an aligned initialization f(x) = W (0)d · · ·W (0) 1 x such that W (t) i = UiΣ (t) i V T i for all i ∈ [d] (that is, Ui, Vi are not updated) if and only if there exist orthonormal matrices U ∈ Rkd×kd , V ∈ Rk0×k0 such that
UTY XTV = [ Λ′ 0 0 A1 ] , and V TXXTV = [ Λ 0 0 A2 ] for diagonal r × r matrices Λ,Λ′ and arbitrary A1 ∈ R(k0−r)×(kd−r), A2 ∈ R(k0−r)×(k0−r).
Proof. Gradient descent on the objective
arg min f∈F
1
2n n∑ i=1 ‖y(i) − f(x(i))‖22
proceeds via the following update rule:
W (t+1) i = W (t) i +
γ n (W (t) d . . .W (t) i+1) T n∑ l=1 (y(l) − f(x(l)))(W (t)i−1 . . .W (t) 1 x (l))T , ∀i ∈ [d],
(10)
where γ is the learning rate and superscript (t) denotes the gradient descent step. Assume that the network is initialized to be aligned, that is, there exist orthonormal Ui, Vi and diagonal matrices Σi such that Wi = UiΣiV Ti and Ui = Vi+1 for i ∈ [d− 1]. Substituting into Equation (10) yields
W (t+1) i = UiΣ (t) i V T i +
γ n (UdΣ (t) d · · ·Σ (t) i+1V T i+1) T n∑ l=1 (y(l) − f(x(l)))(Ui−1Σ(t)i−1 · · ·Σ (t) 1 V T 1 x (l)) T
= Ui Σ(t)i + γn d∏
j=i+1
Σ (t) j T UTd n∑ l=1 (y(l) − f(x(l)))x(l) T V1 i−1∏ j=1 Σ (t) j T V Ti = Ui Σ(t)i + γn d∏
j=i+1
Σ (t) j T (UTd Y X TV1 − Σ(t)d · · ·Σ (t) 1 V T 1 XX TV1) i−1∏ j=1 Σ (t) j T V Ti . Thus strong alignment is an invariant if and only if for all i, the quantity
d∏ j=i+1 Σ (t) j T (UTd Y X TV1 − Σ(t)d · · ·Σ (t) 1 V T 1 XX TV1) i−1∏ j=1 Σ (t) j T
is an ki × ki−1 diagonal matrix for all t. At initialization each of the Σj have rank at least r. Considering i = 1 and i = d, the above quantity is diagonal if and only if the matrix
UTd Y X TV1 − Σ(t)d · · ·Σ (t) 1 V T 1 XX TV1 (11) has its top r rows and top r columns all diagonal; i.e. we can write this expression as[
D 0 0 A
] (12)
for an r × r diagonal matrix D and an arbitrary (kd − r)× (k0 − r) matrix A. For the first direction, assume that strong alignment is an invariant, i.e. that Equation (11) can be written in the above block diagonal form. Define Σ(t)tot = Σ (t) d · · ·Σ (t) 1 – this is a diagonal matrix whose only nonzero entries are the first r on the diagonal. We know that
UTd Y X TV1 − Σ(t)totV T1 XXTV1
is of the form of Equation (12) for all gradient descent steps t, and thus the quantity( Σ
(t) tot − Σ (0) tot ) V T1 XX TV1
is of this form as well. Assuming that we’ve not initialized any of the singular values to be their optimal value (which is satisfied with probability 1), the top r diagonal entries of Σ(t)tot − Σ (0) tot are nonzero, which means that the top left r × r submatrix of V T1 XXTV1 is diagonal, and that the top right submatrix consists of all zeros. But since V T1 XX
TV1 is symmetric, the bottom left submatrix must also consist of all zeros, and thus we have
V T1 XX TV1 = [ D2 0 0 A2 ] for an r × r diagonal matrix D2 and arbitrary (k0 − r) × (k0 − r) matrix A2. Plugging this into Equation (11) implies that UTd Y X TV1 must be of this form as well.
We next show the other direction. Assume that for some orthonormal matrices U and V , it holds that V TXXTV is diagonal and UTY XTV can be written in the block matrix form given by Equation (12). Initializing the layers such that Ud = U, V1 = V, and Ui = Vi+1 for i ∈ [d − 1] implies that Equation (11) is also of this block diagonal form, as desired.

heading: B PROOF OF COROLLARY 1
text: Proof. The conditions of strong alignment imply the conditions of Lemma 2, which in turn implies that there exist orthonormal matrices U, V such that
UTY XTV = [ Λ′ 0 0 A1 ] , and
V TXXTV = [ Λ 0 0 A2 ] ,
where Λ,Λ′ are r × r diagonal matrices. Furthermore, from the proof of Theorem 1, if the layers are initialized to be aligned, with Ud = U and V1 = V , then the gradient descent updates are as follows:
W (t+1) i = Ui Σ(t)i + γn d∏
j=i+1
Σ (t) j T (UTY XTV1 − Σ(t)d · · ·Σ (t) 1 V TXXTV ) i−1∏ j=1 Σ (t) j T V Ti . Since the minimum of the ranks of the Σ(t)i is r, only the top r singular values of Wi are updated. Plugging in the expressions for UTY XTV and V TXXTV and restricting to the top r singular values (which we denote by Σ′i), we obtain the statement of Corollary 1, with the singular values of each layer being updated as:
Σ′i (t+1) = Σ′i (t)
+ γ
n ∏ j 6=i Σ′j (t) (Λ′ − d∏ j=1 Σ′j (t) Λ).
This completes the proof.

heading: C PROOF OF PROPOSITION 1
text: Proof. By Corollary 1, under strong alignment, each singular value is updated independently of each other. Thus we can focus on how the kth singular value for each layer is updated. Recall that σk(W (t) i ) denotes the kth diagonal entry of Σ (t) i . Since we’re focusing on a fixed k, we drop the subscript k for convenience and let σ(t)i equal σk(W (t) i ). The σ are updated by the following update rule:
σ (t+1) i = σ (t) i +
γ
n ∏ j 6=i σ (t) j (λ ′ k − λk d∏ j=1 σ (t) j ),
where λ′k, λk are the kth diagonal elements of Λ ′,Λ. We assume that Λ′ and Λ have the same zero pattern. Therefore λk = 0 if and only if λ′k = 0. If both of these values are zero, then σi is not updated.
Otherwise, assume λk, λ′k 6= 0. Note that λk > 0, since XXT is positive semidefinite. We can also negate columns of U to ensure that λ′k > 0 as well. Let η = γλk n , and define S (t) = ∏d j=1 σ (t) j . This yields
σ (t+1) i = σ (t) i + η
S(t)
σ (t) i
( λ′k λk − S(t)). (13)
Therefore (dropping the superscript to let S = S(t)),
S(t+1) = d∏ i=1 σ (t+1) i = d∏ i=1 ( σ (t) i + ηS 1 σ (t) i ( λ′k λk − S) )
= S + ∑
T⊂[d]:|T |≥1
η|T |S|T |( λ′k λk − S)|T | ∏ i∈T 1 σ (t) i ∏ i 6∈T σ (t) i
= S + ∑
T⊂[d]:|T |≥1
η|T |S|T |+1( λ′k λk − S)|T | ∏ i∈T 1 (σ (t) i ) 2 ,
and hence
λ′k λk − S(t+1) = λ ′ k λk − S − ∑ T⊂[d]:|T |≥1 η|T |S|T |+1( λ′k λk − S)|T | ∏ i∈T 1 (σ (t) i ) 2 (14)
= ( λ′k λk − S) 1− ∑ T⊂[d]:|T |≥1 η|T |S|T |+1( λ′k λk − S)|T |−1 ∏ i∈T 1 (σ (t) i ) 2  . (15)
Thus we obtain
λ′k λk − S(t+1) = ( λ′k λk − S(t) ) · r(t)k , (16)
where
r (t) k = 1− ∑ T⊂[d]:|T |≥1 η|T |S|T |+1( λ′k λk − S)|T |−1 ∏ i∈T 1 (σ (t) i ) 2 . (17)
We aim to bound r(t)k from both above and below. First, we show that r (t) k is nonnegative in order to prove the following lemma:
Lemma 3. 0 < S(j) ≤ λ ′ k
λk for all j ≥ 0.
Proof. We proceed by induction. By the original assumptions in Proposition 1, 0 < S(0) ≤ λ ′ k
λk . Now
assume that 0 < S(j) ≤ λ ′ k
λk for all j ≤ t. By the update rule in Equation (13), σ(j+1)i ≥ σ (j) i . Since
σ (0) i > 0, σ (j) i > 0, so S (j) > 0. We also have that∏ i∈T 1 (σ (t) i ) 2 ≤ ∏ i∈T 1 (σ (0) i ) 2 ≤ 1 (mini σ (0) i ) 2|T | .
Next, note that we can bound
S|T |+1( λ′k λk − S)|T |−1 ≤ (λ ′ k λk )2|T |.
This means that we can upper bound the sum in Equation (17) as∑ T⊂[d]:|T |≥1 η|T |S|T |+1( λ′k λk − S)|T |−1 ∏ i∈T 1 (σ (t) i ) 2 ≤ ∑ T⊂[d]:|T |≥1 η|T |(min i σ (0) i ) −2|T |( λ′k λk )2|T |
= ( 1 + η · (min
i σ (0) i ) −2( λ′k λk
)2 )d − 1.
Since γ ≤ n ln 2d · mini (σ
(0) i ) 2 λk
λ′2k , we have that η ≤ ln 2 · mini (σ
(0) i )
2
d · λ2k λ′k
2 , and thus the right-hand side of the above expression can be upper bounded by(
1 + η · (min i σ (0) i ) −2 )d − 1 ≤ edη(mini σ (0) i ) −2 − 1 ≤ eln 2 − 1 = 1.
Therefore r(t)k ≥ 0. Plugging into Equation (16), since S(t) = S ≤ λ′k λk , we get that S(t+1) ≤ λ ′ k λk , which completes the inductive step.
Next, we would like to upper bound r(t)k by a term independent of t in order to obtain linear convergence. We can lower bound the sum in Equation (17) by the sets with size 1, so∑
T⊂[d]:|T |≥1
η|T |S|T |+1( λ′k λk − S)|T |−1 ∏ i∈T 1 (σ (t) i ) 2 ≥ d∑ i=1 ηS2 1 (σ (t) i ) 2 ≥ ηS2 · dS−2/d,
where the last inequality is due to AM-GM . Lemma 3 implies that S(j+1) ≥ S(j), which means that the above sum is at least ηd(S(0))2−2/d, which means that we can upper bound r(t)k by
r (t) k ≤ 1− ηd(S (0))2−2/d.
This implies that S(t+1) is closer to λ ′ k
λk than S is, and in particular
λ′k λk − S(t+1) ≤ (λ ′ k λk − S)(1− dη(S(0))2−2/d);
hence λ′k λk − S(t) ≤ (λ ′ k λk − S(0))(1− dη(S(0))2−2/d)t.
Since the initialization is fixed, the quantity 1 − dη(S(0))2−2/d is fixed, and thus S(t) converges linearly to λ ′ k
λk . Therefore each of the top k singular values converge linearly to their optimal value
λ′k λk , which means that the loss converges linearly as well.
To complete the proof, it suffices to show that this limit solution achieves a training loss of zero. This is proven in a more general setting at the end of Appendix E.

heading: D PROOF OF THEOREM 4
text: We can finally state the generalization of Theorem 1 to the non-square setting:
Theorem 4. Let f : Rk0 → Rkd be a linear fully connected network as in Equation equation 1, and let r = min(k0, . . . , kn). Strong alignment is an invariant of training under the squared loss on the dataset (X,Y ) if and only if there exist orthonormal matrices U ∈ Rkd×kd , V ∈ Rk0×k0 such that
UTY XTV = [ Λ′ 0 0 A1 ] , and V TXXTV = [ Λ 0 0 A2 ] for diagonal r × r matrices Λ,Λ′ and arbitrary A1 ∈ R(k0−r)×(kd−r), A2 ∈ R(k0−r)×(k0−r).
Proof. By Lemma 2 we know that under strong alignment there exist U and V satisfying the above conditions. In the other direction, Lemma 2 also tells us that given U and V satisfying the data conditions, all the conditions of strong alignment hold except for convergence to a global minimum.
To conclude, we must show that regardless of the zero pattern of Λ or Λ′, under a strongly aligned initialization the network converges to a solution with a loss of zero.
Using the convenient notation that σ(t)i = σk(W (t) i ), we again focus on how the kth singular values of each layer are updated, for some k ∈ [r]. Recall that the σ’s are updated as
σ (t+1) i = σ (t) i +
γ
n ∏ j 6=i σ (t) j (λ ′ k − λk d∏ j=1 σ (t) j ).
The rank ofX must be at least the rank of Y in order for the data to be linearly interpolated. Therefore we can choosen U, V (via permuting columns) to ensure that whenever λk = 0, λ′k = 0 as well. This ensures that σk(W (t) i ) is never updated. If λk, λ ′ k 6= 0, then we showed in Proposition 1 that S(t) converges to λ′k/λk in the limit.
Finally, we consider the case where λ′k = 0, λk 6= 0. Assume that σ (t) i < 1 and γ < n λk
. Then, the σi’s update as
σ (t+1) i = σ (t) i +
γ
n ∏ j 6=i σ (t) j −λk d∏ j=1 σ (t) j  = σi 1− η∏ j 6=i (σ (t) j ) 2  , where η = γλkn . We observe that 0 ≤ σ (t+1) i ≤ σ (t) i . Therefore 0 ≤ S(t+1) = S(t) d∏ i=1 1− η∏ j 6=i (σ (t) j ) 2  ≤ S(t) exp −η d∑ i=1 ∏ j 6=i (σ (t) j ) 2
 ≤ S(t) exp(−ηdS(t)2−2/d) . Since S(0) is positive, we see that 0 ≤ S(t+1) ≤ S(t), and therefore S(t) must converge to some constant c. Assume that c 6= 0. For all > 0, there exists some t such that S(T ) < c+ . Then,
S(T+1) ≤ S(T ) exp ( −ηdS(T ) 2−2/d) < (c+ ) exp ( −ηc2−2/d ) ,
where exp ( −ηc2−2/d ) is a constant which is less than 1. Hence if we choose such that
exp ( −ηc2−2/d ) < c+ c , then S
(T+1) < c, a contradiction. Therefore c = 0, and hence S(t) → 0 = λ′k/λk. In general, we have shown that if λk 6= 0, then σk(W1(t)) · · ·σk(Wd(t))→ λ′k/λk. This solution is given by f(x) = UdΛ′Λ−1V T1 x, which is the solution given by the pseudoinverse which obviously has a loss of zero.

heading: E COMPLETING THE PROOF OF THEOREM 1
text: Proof. In Lemma 1, we showed that in the setting where all layers are square, alignment is equivalent to strong alignment. Theorem 4 states that in general, strong alignment is an invariant if and only if there exist U, V satisfying particular data conditions. Since in the square setting r = k, by Theorem 4 we have that strong alignment is an invariant if and only if there exist U, V such that UTY XTV and V TXXTV are diagonal, as desired.

heading: F ALIGNMENT FOR 1-DIMENSIONAL OUTPUTS
text: Proposition 5. Assuming gradient descent avoids the point where all parameters are zero, alignment is an invariant of training for any linear fully connected network f : Rk0 → R, any convex, twice continuously differentiable loss function, and data (X,Y ) ∈ Rk0×n × R1×n for which the network can achieve zero training error.
Proof. If we initialize the weight matrices to be rank 1 and aligned, then the matrices {Σ(t)i }di=1 are diagonal with a single non-zero entry. Following the proof of Theorem 1, we obtain that alignment is an invariant if the matrix
d∏ j=i+1 Σ (t) j T ( UTd n∑ k=1 ∂` ∂f ∣∣∣∣ (x(k),y(k)) x(k) T V (t) 1 ) i−1∏ j=1 Σ (t) j T
is diagonal. When i 6= 1, d, this matrix is clearly of rank 1 and diagonal (and has a single nonzero entry). This implies that Ui, Vi are invariant for all i 6= 1, d. If i = d, then since kd = 1, the above quantity is also a rank 1 diagonal matrix, implying that Ud and Vd are invariant. Finally, if i = 1, the above matrix is rank-1 but not necessarily diagonal. However, all but the top row are zeros, which after plugging into the gradient descent update rule implies that U1 is invariant as well. Importantly, layers Wi+1,Wi for i ∈ [d− 1] remain aligned regardless of the loss function used, as the expression above is always a diagonal matrix with a single nonzero entry when the layers are initialized to be rank 1. The final step is to show that training leads to zero error according to Definition 3. To do this, we first characterize the stationary points and then under assumptions, we prove that the loss converges to zero.
We now characterize the stationary points of the above update. Let v(t)1 denote the first column of V
(t) 1 , and let σ1(W (t) j ) denote the top singular value in the usSVD of W (t) j . Then the stationary
points are given by:
1. σ1(W (t) j ) = 0 for j ∈ [d]. 2. v(t)1 ⊥ n∑ k=1 ∂` ∂f ∣∣∣∣ (x(k),y(k)) x(k) T
If we initialize σ1(W (0) 1 ) = 0, then we have that:
σ1(W (t) 1 )v (t) 1
T = n∑ k=1 c (t) k x (k)T
c (t+1) k = n∑ k=1 c(t)k + γ∏ j 6=k σ1(W (t) j ) ∂` ∂f ∣∣∣∣ (x(k),y(k) x(k)T
for c(t)k ∈ R and ∀t ∈ Z≥0. Hence, updates to v (t) 1 are in the span of the data, and so assuming that
{x(k)}nk=1 are linearly independent, v (t) 1 cannot be orthogonal to n∑ k=1 ∂` ∂f ∣∣∣∣ (x(k),y(k)) x(k) T unless the c (t) k are all 0, i.e. σ1(W (t) 1 ) = 0 for t > 0.
Next, if we initialize σ1(W (0) i ) = σ1(W (0) j ), then σ1(W (t) i ) = σ1(W (t) j ) for all i, j ∈ {2, . . . d}, t ≥ 0 since for all i ∈ {2, . . . d}:
σ1(W (t+1) i ) = σ1(W (t) i ) + ∏ j 6=i σ1(W (t) j ) ( n∑ k=1 ∂` ∂f ∣∣∣∣ (x(k),y(k)) x(k) T v (t) 1 )
This initialization corresponds to layers Wi+1,Wi being balanced for i ∈ {2, . . . d}. Thus, under this initialization, the only other stationary point is given by σ1(W (t) i ) = 0 for all i ∈ {2, . . . d}.
Hence, if gradient descent avoids the non-strict saddle points given by σ1(W (t) i ) = 0 for all i ∈ {2, . . . , d} and σ1(W (t)i ) = 0 for all i ∈ [d], then gradient descent converges to a local (and thus global) minimum of the convex loss. The former stationary point can be avoided by re-parameterizing the network such that σ1(W (t) i ) = σ1 for all i ∈ {2, . . . d} (i.e. σ1 = 0 now corresponds to a strict saddle as defined in Lee et al. (2016)), and then taking a random initialization for σ1. This would correspond to gradient descent on the original parameterization with a scaling factor on the learning rate for parameters σ1(W (t) i ) for i ∈ {2, . . . d}. The latter stationary point is avoided by the assumption in the proposition.

heading: G PROOF OF PROPOSITION 2
text: Proof. For any matrices A,B ∈ Cm×n, we have that 2σi(AB∗) ≤ σi(A∗A+B∗B) (Bhatia, 1997). Thus letting A = W2, B = WT1 , we see that
2σi(W2W1) ≤ σi(WT2 W2 +W1WT1 ) =⇒ 2 ∑ i σi(P ) ≤ ∑ i σi(W T 2 W2 +W1W T 1 )
= ‖WT2 W2 +W1WT1 ‖1 ≤ ‖WT2 W2‖1 + ‖W1WT1 ‖1 = ‖W2‖2F + ‖W1‖2F
This lower bound is in fact achieved for an aligned solution. If the SVD of P is P = UΣV T , setting W1 = WΣ 1 2UT and W2 = UΣ 1 2V T yields ‖W1‖2F = ‖W2‖2F = Tr(Σ), so ‖W1‖2F + ‖W2‖2F = 2Tr(Σ).

heading: H PROOF OF THEOREM 2
text: Proof. Given an arbitrary loss function, assume that the ith layer is restricted to some structure given by a subspace S and basis matrices A1, . . . Am, so that at timestep t we have that
W (t) i = m∑ j=1 (cij) (t)Aj
We take the gradient of the loss with respect to the cij . The chain rule yields:
∂l
∂cij = n∑ p,q=1
∂l ∂(Wi)pq · ∂(Wi)pq ∂cij = n∑ p,q=1
∂l
∂(Wi)pq ·Ajpq
The gradient descent update on cij is thus:
(cij) (t+1) = (cij) (t) − η · ∂l ∂cij = (cij) (t) − η n∑ p,q=1
∂l
∂(Wi)pq ·Ajpq
The corresponding update on W i becomes
W (t+1) i = m∑ j=1 (cij) (t+1)Aj
= m∑ j=1 (cij) (t)Aj − η m∑ j=1 n∑ p,q=1
∂l
∂(Wi)pq ·AjpqAj
= W (t) i − η m∑ j=1 n∑ p,q=1
∂l
∂(Wi)pq ·AjpqAj
We calculate the projection operator π of some arbitrary matrix M onto S. We can write
π(M) = m∑ j=1 〈M,Aj〉Aj ‖Aj‖22 = m∑ j=1 m∑ p,q=1 MpqA j pqA j ‖Aj‖22 .
If we define the operator πS as
πS(M) = m∑ j=1 〈M,Aj〉Aj = m∑ j=1 m∑ p,q=1 MpqA j pqA j ,
then gradient descent on the c gives the following update rule on the W i:
W (t+1) i = W (t) i − η · πS
( ∂l
∂Wi
) .
If the Aj all have norm 1, then, π = πS , and this is the same update rule given by projected gradient descent with respect to the subspace S. Otherwise, πS is simply the projection π followed by appropriate scaling in each of the basis directions.

heading: I TREATING A CONVOLUTIONAL LAYER AS A LINEAR SUBSPACE
text: Consider a 3× 3 image. We map it to a 9-dimensional vector as follows[ x1 x2 x3 x4 x5 x6 x7 x8 x9 ] =⇒ [x1 x2 x3 x4 x5 x6 x7 x8 x9]T .
Then, the linear transformation given by applying the 3 × 3 convolutional filter [ c1 c2 c3 c4 c5 c6 c7 c8 c9 ] is given by the matrix
W =  c5 c4 0 c2 c1 0 0 0 0 c6 c5 c4 c3 c2 c1 0 0 0 0 c6 c5 0 c3 c2 0 0 0 c8 c7 0 c5 c4 0 c2 c1 0 c9 c8 c7 c6 c5 c4 c3 c2 c1 0 c9 c8 0 c6 c5 0 c3 c2 0 0 0 c8 c7 0 c5 c4 0 0 0 0 c9 c8 c7 c6 c5 c4 0 0 0 0 c9 c8 0 c6 c5  .
Then S consists of all matrices of the form W . S is a 9-dimensional subspace of R9×9, with an orthonormal basis with coefficients being the ci.

heading: J PROOF OF PROPOSITION 3
text: Proof. For i ∈ [d], let UiΣiV Ti be a usSVD of Wi witnessing alignment of f . We can then rewrite Y = f(X) as Y = Ud ∏d i=1 ΣiV T 1 X , thus proving the desired statement.

heading: K PROOF OF PROPOSITION 4
text: Before we can prove Proposition 4, we require the following definition from combinatorics.
Definition 5. A partition of an integer k is a tuple λ = (λ1, . . . , λs) such that λi ≥ λi+1 for all i and k = λ1 + · · ·+ λs. Each λi is called a part of λ. We let s(λ) denote the number of parts of λ and we write λ ` k to indicate that λ is a partition of k.
Proof of Proposition 4. Given a k × k matrix A, let λ(A) denote the partition λ of k such that λi is the multiplicity of the ith greatest singular value of A. Let U(A) denote the set of matrices U such that UΣV T is a usSVD of A. The dimension of U(A) is
s(λ(A))∑ i=1 ( λi 2 ) .
To see this, note that any orthonormal basis of the eigenspace of AAT corresponding to the multiplicity-λi eigenvalue of AAT can be the corresponding columns in an element of U(A) and that the set of orthonormal bases of an m-dimensional linear space is ( m 2 ) .
For any set Q of matrices, Define U(Q) to be the set of all possible sets of left-singular vectors of elements of S. That is, U(Q) := ⋃ A∈Q U(A).
For each partition λ of k, let Tλ denote the set of matrices A such that λ(A) = λ. The dimension of Tλ ∩ S is at most r and therefore the dimension of U(S ∩ Tλ) is at most
r + s(λ)∑ i=1 ( λi 2 ) .
LetO(k, n) denote the set of k×nmatrices with orthonormal columns. Assume alignment is possible over S for a non-measure-zero set of matrices with n columns. Then there exists B ⊆ O(k, n) with dim(B) = dim(O(k, n)) such that for every U ′ ∈ B, U(S) contains a matrix whose first n columns are U ′. Therefore dim(U(S)) ≥ dim(O(k, n)). Since dim(O(k, n)) = ( k 2 ) − ( k−n 2 ) , the following must be satisfied for some λ ` k
r + s(λ)∑ i=1 ( λi 2 ) ≥ ( k 2 ) − ( k − n 2 ) . (18)
This is attained when λ = (k), but in this case Tλ is simply the set of scalar multiples of the identity. If we forbid λ = (k), then we claim that the maximum value of r + ∑s(λ) i=1 ( λi 2 ) is attained by λ = (k − 1, 1). To see this, note that for all p < q,( q − p
2
) + ( p
2
) = ( q
2
) − p(q − p) < ( q
2
) .
For p > 0, this is maximized when p = 1. This implies that the maximum value of ∑s(λ) i=1 ( λi 2 ) will be obtained in as few summands as possible (which in our case is two), and in particular when λ1 = k − 1 and λ2 = 1. In this case, equation 18 becomes
r +
( k − 1
2
) ≥ ( k
2
) − ( k − n
2
) .
Taking the logical negation of the above inequality and simplifying gives r < k − 1− ( k−n 2 ) .

heading: L ADDITIONAL EXPERIMENTS
text: We provide the following empirical evidence demonstrating that when the conditions of Theorem 1 are satisfied, invariance of alignment can indeed be observed empirically. We use a 2-hidden layer fully connected network with 9 hidden units per layer.

heading: M EXPERIMENTAL SETUP
text: We provide network architectures and hyperparameters used for our experiments below. We trained our networks on an NVIDIA TITAN RTX GPU using the PyTorch library. In all settings, we train using gradient descent with a learning rate of 10−2 until the loss was below 10−4.
1. Figure 1a: We use a 2-hidden layer fully connected network with 9 hidden units per layer. Our data is given by matrices (X,Y ) ∈ R9×9 where each matrix entry is drawn from a standard normal distribution.
2. Figure 1b: We use a 2-hidden layer fully connected network with 1024 hidden units in the first hidden layer and 64 hidden units in the second hidden layer. Our data consists of 256 linearly separable examples from MNIST and is trained using Squared Loss.
3. Figure 1c: We use a 2-hidden layer fully connected network with 1024 hidden units in the first hidden layer and 64 hidden units in the second hidden layer. Our data consists of 256 linearly separable examples from MNIST and is trained using Cross Entropy Loss.
4. Figure 2a: We use a 2-hidden layer network with 4 hidden units per layer, where each layer is constrained to be a Toeplitz matrix. Our input X is equal to the identity, and our output Y is a 4× 4 matrix with each entry sampled from a standard normal distribution.
5. Figure 2b: We use a 2-hidden layer convolutional network with a single 3× 3 filter in each layer, stride of 1, and padding of 1. Our data consists of a single example from MNIST.
Code for the experiments can be found at the following anonymized github link: https:// anonymous.4open.science/r/33277cc0-6074-46c4-8642-7feadd678278/.

Review summaries:
This article extends the notion of alignment [Ji and Telgarsky, 2018] to linear neural networks with multiple output nodes, which requires the consecutive layers (i+1, i) to have the same (right, left) singular spaces. The authors identify necessary and sufficient conditions under which, alignment is an invariant of the gradient descent iterates (Definition 3), which in particular means that the gradient descent iterates only update the singular values of the layers, and not their singular vectors. The authors studied alignment for several shallow and deep linear architectures, and specify learning rates for which gradient descent enjoys exponential convergence.

This paper considers deep linear networks trained by gradient descent with the squared loss, and characterizes when alignment happens, meaning that for any pair of adjacent weight matrices W_{i+1} and W_i, the (unsorted, signed) right singular vectors of W_{i+1} are identical to the (unsorted, signed) left singular vectors of W_i. This paper further gives a few examples where the conditions of alignment hold, and proves a convergence rate for aligned networks. For networks with constrained layer structure, such as convolutional networks, this paper shows that aligned networks in general cannot achieve zero training error with the squared loss. Finally, empirical support of the theory is provided.

The paper presents an extension of the idea of alignment in linear neural networks, that can help in providing convergence analysis of such networks. Such a notion was previously studied for networks with a single output. The current paper extends it to networks with multi-dimensional outputs. The paper offers multiple interesting results: a) conditions on the datasets where alignment can remain invariant b) lack of alignment or invariance for networks with constrained layers