{'fraction_non_alphanumeric': 0.03366580795737279, 'fraction_numerical': 0.009621947728824009, 'mean_word_length': 4.181745579007416, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Balancedness and Alignment are Unlikely in Linear Neural Networks

We study the invariance properties of alignment in linear neural networks under gradient descent. Alignment of weight matrices is a form of implicit regularization, and previous works have studied this phenomenon in fully connected networks with 1-dimensional outputs. In such networks, we prove that there exists an initialization such that adjacent layers remain aligned throughout training under any real-valued loss function. We then define alignment for fully connected networks with multidimensional outputs and prove that it generally cannot be an invariant for such networks under the squared loss. Moreover, we characterize the datasets under which alignment is possible. We then analyze networks with layer constraints such as convolutional networks. In particular, we prove that gradient descent is equivalent to projected gradient descent, and show that alignment is impossible given sufficiently large datasets. Importantly, since our definition of alignment is a relaxation of balancedness, our negative results extend to this property.


Introduction
Even though overparameterized deep networks are capable of interpolating randomly labeled training data [6,20], 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 [21].
As an example of implicit regularization, [2] and [5] proved that gradient flow (i.e., gradient descent with infinitesimal step size) balances the layers of linear neural networks throughout training without the need of any explicit regularizer. More precisely, they showed that for adjacent layers with weight matrices W i and W i+1 , the following equation holds throughout gradient flow: W i W T i = W T i+1 W i+1 , i.e., this equality is an invariant of training. Invariants of training for first order methods are useful for understanding properties of the solution after training.
While balancedness constrains the singular values and vectors of adjacent layers, [12] considered a less restrictive condition, known as alignment, which only imposes constraints on the top singular values and vectors of adjacent layers: the layers of a linear neural network become aligned if for all i, the top left/right singular vectors u i and v i of W i satisfy |v T i+1 u i | → 1 as the number of gradient descent steps goes to infinity. They proved that gradient descent aligns the layers of linear fully connected networks with 1-dimensional outputs on linearly separable datasets trained under strictly decreasing loss functions.
In this work, we study the invariance properties of alignment in linear neural networks under gradient descent. This is in contrast to previous work that studied the invariance of balancedness under gradient flow and we will highlight important differences. Our main contributions are as follows: 1. We extend the definition of alignment from the 1-dimensional 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 (Proposition 2).
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 4). 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.

Related Work
Implicit regularization in over-parameterized networks has become a subject of significant interest [16,15,8,9,10]. In order to characterize the specific form of implicit regularization, several works have focused on analyzing deep linear networks [11,3,19,10]. 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. Balancedness is one form of implicit regularization in linear neural networks: Introduced by [2], a matrix A ∈ R ×m is balanced with B ∈ R m×n if While mainly focused on accelerating optimization through depth, [2] studied balancedness of layers in linear networks under a gradient flow analysis. The analysis from this work has been extended to more general notions of balancedness including approximate balancedness [1] and balancing of norms of adjacent layers of homogenous neural networks [5]. Balancedness is a strong condition, as it requires that adjacent layers have the same singular values and aligned singular vector spaces. Instead, [12] identified the less restrictive condition, alignment, in their analysis of linear fully connected networks with 1-dimensional outputs trained on linearly separable data. In particular, [12] proved that in the limit of training, each layer, after normalization, approaches a rank 1 matrix, i.e.
and that adjacent layers, W i+1 and W i become aligned, i.e.
In addition, [12] proved that alignment in this setting occurs concurrently with convergence to the maxmargin solution. Follow-up work mainly focused on this convergence phenomenon and gave explicit convergence rates for overparameterized networks trained with gradient descent [23,4].
We analyze the notion of alignment as a property of neural networks in the multi-dimensional setting and when the layers have constraints (as in convolutional networks), and prove that alignment, let alone balancedness, is highly unlikely in this setting. As a consequence, while these properties may play a role as implicit regularizers for linear neural networks with 1-dimensional outputs, alignment and balancedness are ruled out as candidates to explain implicit regularization in linear neural networks more generally.

Definition of Alignment in the Multi-dimensional Setting
In this section, we first define alignment for linear neural networks with multi-dimensional outputs and prove that alignment is a relaxation of balancedness. We then define when alignment is an invariant of training.
In this paper, we consider linear neural networks. Let f : R k0 → R k d denote such a d-layer network, i.e. where . Gradient descent with learning rate γ is used to find a solution to the following optimization problem: 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) ) 2 2 , which is the squared loss (MSE). In addition, we denote by W (t) i for t ∈ Z ≥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.
To define alignment in the multi-dimensional setting, we introduce a generalized form of singular value decomposition.
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 [12] to the multi-dimensional setting.
Note that if A and B are rank 1 matrices and A is aligned with B, then the inner product of the first column of V A and U B is 1 in absolute value. Hence Definition 2 is consistent with alignment in the 1dimensional setting from [12]. Note also that the relations "A is aligned with B" and "A is balanced with B" are not symmetric: For example, let U, V, W be distinct generic orthonormal matrices and let Σ be a generic diagonal matrix. Let A = U ΣV T and B = V ΣW T . Then A is both aligned and balanced with B, but B is neither aligned nor balanced with A.
The following result (proof in Appendix A) shows that balancedness is a stronger condition than alignment.
In general, the converse statement does not hold.
It is tempting to assume that a network f = W d . . . W 1 is aligned if and only if W i+1 is aligned with W i for each i ∈ [d − 1]. The following example shows that this is false.
3 and U 1 IU T 1 are both usSVDs of W 2 , W 3 is aligned with W 2 and W 2 is aligned with W 1 . Since Σ 1 and Σ 2 do not have the same nonzero entries, all other usSVDs of W 1 and W 3 are obtained by permuting and negating columns of U 1 , U 3 , V 1 , V 3 . Since V 1 = U 3 , this implies that f is not aligned.
In this paper, we study alignment as an invariant of training for deep linear networks. Such invariants are of interest since they may provide insights into properties of trained networks. We now define alignment as an invariant of training and then discuss its consequences for training. (a) the network f is aligned; d , that is, U 1 and V d are not updated. If additionally, V 1 and U d are not updated for any t ∈ Z ≥0 , then we say that strong alignment is an invariant of training.
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.
When alignment is an invariant of training, there are important consequences for training the network. In particular, note that if the network f is aligned with usSVDs 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 .
Remark. For the remainder of the paper, we assume that the gradient of the loss function at initialization {W 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 [12].

Alignment in Fully Connected Networks
In this section, we first characterize when alignment is an invariant of training for fully connected networks (Theorem 1). We then present various classes of problems for which alignment is an invariant of training including the problems of autoencoding, matrix factorization, matrix sensing. In contrast, for 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 consequences of alignment and draw parallels between aligned solutions and linear regression. In particular, we provide a simple explanation of how depth provides implicit regularization under alignment and establish linear convergence of gradient descent to the minimum Frobenius norm solution when using squared loss under alignment.

Characterization of Alignment with Multi-dimensional Outputs
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. k i = k j for all 0 ≤ i, j ≤ d. The general result for non-square matrices is provided in Appendix E.
Theorem 1. Let f : R k → R k 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 ) ∈ R k×n × R k×n if and only if there exist orthonormal matrices U, V ∈ R k×k such that U T Y X T V and V T XX T V are diagonal.
The full proof of this result is presented in Appendices B-F; in the following, we provide a proof sketch. Proof Sketch. We proceed by induction. For the base case, we initialize the layers {W i } n i=1 to satisfy the following conditions for alignment: Theorem 1 implies that invariance of alignment throughout training holds only for special classes of problems. In particular, note that if we let Hence, for alignment to be an invariant of training, X and Y need to have the same right singular vectors, a very special condition on the data.
Recall from Proposition 1 that balancedness implies alignment. Hence Theorem 1 implies that balancedness is in general not an invariant of training under gradient descent. This is in stark contrast to recent work showing that balancedness is an invariant of training under gradient flow for general linear neural networks. This highlights the importance of studying gradient descent as compared to gradient flow. In Section 6, we provide additional empirical support showing that alignment, and hence balancedness, is not an invariant of training for important tasks such as the problem of multi-class classification.

Classes of Problems with Alignment
We next discuss classes of problems for which alignment is an invariant of training.
Autoencoding: In the case when X = Y , it holds that U T Y X T V = U T XX T V . 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
Implicit regularization of linear networks in the matrix sensing setting has been analyzed extensively [5,14,3,11]. Theorem 1 shows that alignment is an invariant of training for this problem if and only if 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.

Proposition 2.
Alignment is an invariant of training for any linear fully connected network f : R k0 → R, any real-valued loss function, and data (X, Y ) ∈ R k0×n × R 1×n for which gradient descent minimizes the loss to zero.
Proof. If we initialize the weight matrices to be rank 1 and aligned, then the matrices {Σ are diagonal with a single non-zero entry. Following the proof of Theorem 1, we thus obtain that the matrix T is of rank 1 and diagonal. Hence when i = 1, d it has a single nonzero entry. This implies that the weights are aligned throughout training. By assumption, gradient descent achieves zero training error, and thus alignment is an invariant of training. In Appendix G, we extend this proposition to the setting of convex loss functions, where we prove that gradient descent achieves zero training error under less restrictive assumptions.

Consequences of Alignment
We end this section by discussing various consequences of the invariance of alignment for the analysis of training. We will see that using an aligned initialization can greatly simplify the convergence analysis of gradient descent.
The following corollary (proof in Appendix C) follows directly from the proof of Theorem 1 and will allow us to connect training deep linear networks to linear regression, which is a 1-layer linear neural network.
Under the invariance of strong alignment (i.e., when Λ and Λ are diagonal), gradient descent only updates the first r values of i . The updates are then given by: The other entries of Σ This corollary allows us to establish the following connection between training aligned deep linear networks and solving linear regression with gradient descent: It is well-known that using gradient descent to perform linear regression leads to a solution that can be decomposed into the minimum 2 norm solution (Frobenius norm solution in the case of multi-dimensional outputs) and a component orthogonal to the span of the training data [7]. The update rule in (7) shows that a similar phenomenon is present when training aligned deep linear networks. Assuming Λ, Λ have identical 0 patterns, the directions orthogonal to the span of the data do not get updated by gradient descent. Under strong alignment, the matrices V 1 and U d remain unchanged through training, and thus we need only analyze convergence of the product of the singular values The proof follows from the fact that the components orthonormal to the span of the training data are never updated. Hence, the product of matrices Σ (0) i decreases the components orthonormal to the span of the training data provided that the corresponding diagonal entries are less than 1.
Using this connection to linear regression, we provide a bound on the learning rate to guarantee that gradient descent achieves linear convergence to the global minimum.
Proposition 4. For all k ∈ [r], let σ k (W i ) denote the kth entry of Σ i in the usSVD of W i , and let λ k and λ k denote the kth entries of Λ and Λ respectively. Assuming that gradient descent only updates the top r singular values of the solution and converges linearly to the global minimum.
A proof of Proposition 4 is given in Appendix D. It is motivated by the fact that a learning rate of 1 λ1 , given by the inverse of the top eigenvalue of the covariance matrix of the inputs X, is optimal for linear regression and guarantees that gradient descent achieves a linear convergence rate.

Alignment Under General Layer Structure
In Section 4, we characterized when alignment is an invariant of training for fully connected linear networks. In such networks, the parameters of each weight matrix are optimized independently. This is in contrast to the most commonly used deep learning models, which rely on convolutional layers or other layer 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.

Linear Neural Networks with Layer Structure
We start by setting up mathematical terminology to describe different layer structures.
Definition 4. Let S ⊂ R m×n be a linear subspace of matrices and let {A i } r i=1 be an orthogonal basis for S.
In Definition 4, orthogonality is with respect to the inner product A, B = tr(A T B). Equivalently, we can consider A, B as points in R mn and use the standard dot product.
Definition 4 encompasses layer structures commonly used in practice, such as: • Fully connected layers: with S = R m×n and a basis consisting of matrices of the form A pq , where the (p, q) entry is 1 and all other entries are zero.
• Convolutional layers: treating a p × p image as a vector in R p 2 and applying 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 can be represented as a matrix in R p 2 ×p 2 and the set of all possible such linear transformations corresponding to an s × s filter forms an s 2 -dimensional subspace of R p 2 ×p 2 ; the parameters of the filter are coefficients of an orthogonal basis of this subspace, and hence performing gradient descent on the parameters of the filter is equivalent to optimizing over the basis coefficients; see Appendix I for a concrete example.
• 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 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 {c i j } r j=1 leads to the following weight matrix updates: where π S denotes the projection operator onto S.
Theorem 2 shows that gradient descent in networks with layer structure is equivalent to projected gradient descent 1 . 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.

Necessary Condition for Alignment
Motivated by the above characterization via projected gradient descent, we now show that for layer structures with constrained dimension, aligned solutions cannot, in general, achieve zero training error under the squared loss, given sufficient data. 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 solution.
To prove this, we show that alignment after training places certain constraints on the singular vectors of the first and last layers (Proposition 5). We then use a dimension counting argument to show that these constraints cannot be satisfied if the dimension of the layer structure is small (Proposition 6).
and the desired statement follows immediately.
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.
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 6 is provided in Appendix J. The key idea in the proof is that the dimension of the set of possible orthonormal matrices that can appear in a usSVD of a non-identity element W of S can be bounded above in terms of the dimension of S. The main subtlety occurs when singular values of W are repeated. We use this dimension bound to compute an inequality that must be satisfied when every element of some non-measure-zero set of n × k matrices aligns with an element of S. The logical negation of this inequality is what appears in Proposition 6.  Taken together, Propositions 5 and 6 directly imply Theorem 3, 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 = · · · = k d and let all layers have the same structure, S. The statement can trivially be extended to the general setting without these assumptions.
Theorem 3. For n ≥ k and generic input (or output) data, alignment cannot occur for a network f = The caveat included in Theorem 3, that each W i is not a scalar multiple of the identity, is not a serious restriction. Modulo scalar multiplication, the only case in which such a network could achieve zero loss is autoencoding. In this situation, the latent space representation of the data would be a scalar multiple of the data itself.
Theorem 3 is in contrast to fully connected networks (i.e., networks with 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 m 2 or more 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 = m 2 , r = 9, and n ≥ m 2 in Proposition 6.

Empirical Support
In this section, we provide experimental results to validate our theoretical findings and support our finding that alignment is an unlikely property of linear neural networks 2 .
In the experiments, 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 2 Hyperparameter settings are detailed in Appendix K.
(a) Matrix factorization with layers constrained to be Toeplitz matrices.
(b) Autoencoding a single MNIST example using a convolutional network. (a) Multi-dimensional regression on random data with squared loss and randomly initialized weights.
(b) Autoencoding a single MNIST example using a convolutional network with randomly initialized weights. We begin with examples demonstrating that alignment is generally not an invariant of training in fully connected networks with multi-dimensional outputs. 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 ∈ R 9×9 and targets Y ∈ R 9×9 , and a 2-hidden layer network initialized so that alignment holds at the start of training. As X and Y do not have the same right singular vectors, our data violates the conditions of Theorem 1, and alignment is not an invariant of training, which is reflected in Figure 1a.
In Figures 1b and c, we show that alignment is also not an invariant when training fully connected networks 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 1b is consistent with the generalization of Theorem 1 to non-square layers (see Appendix E), which states that strong alignment is not an invariant of training for arbitrary data under squared loss. It is interesting that this result transfers to the case of cross entropy loss, at least empirically, suggesting that this theory may also be relevant for other loss functions.
In networks with constrained layer structure, Theorem 3 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 (i.e. where Y ∈ R k×k and X = I). In this case, k = n, and so the bound in Theorem 3 tells us that alignment is impossible when the linear structure has dimension, r < k −1. In Figure 2a, we show that alignment does not occur even when r ≥ k −1. In particular, alignment is not an invariant when training a 2-hidden layer Toeplitz network to factorize a random matrix in R 4×4 . Our network has 4 hidden units per layer and we have r = 7, k = 4, n = 4.
Even in cases where n < r < k, we observe that alignment is not invariant. In Figure 2c, we see that alignment does not remain invariant when training a 2-hidden layer linear convolutional network to autoencode a single MNIST example (i.e. n = 1, r = 9, k = 784).
Finally, we empirically analyze networks with multi-dimensional outputs whether alignment can happen in the limit even when it is not an invariant of training.
In Figure 3a, we analyzed multi-dimensional regression on standard normal data using a fully connected network. As in 1a, we chose random inputs X ∈ R 9×9 and targets Y ∈ R 9×9 , and used a 2-hidden layer network with 9 hidden units initialized randomly. In Figure 3b, we analyzed the problem of autoencoding a single training example from MNIST using a 2-hidden layer convolutional network, also initialized randomly. In both figures, we observe that the network is far from aligned at the end of training. The experiments presented here corroborate the preceding theory and provide strong evidence that alignment does not occur in a variety of multi-dimensional settings.

Discussion
We generalized the definition of alignment to linear networks with multi-dimensional outputs. We proved that alignment is generally not an invariant of training for fully connected linear networks with multi-dimensional outputs, in contrast to the one-dimensional case [12]. Moreover, we characterized the datasets for which alignment is an invariant for fully connected networks and showed how alignment simplifies 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. Lastly, we provided empirical evidence that alignment does not occur for important problem classes even when n < r.
With regard to implicit regularization in neural networks, our work highlights the importance of studying gradient descent as compared to gradient flow. While balancedness has been shown to be an invariant of training in deep linear fully connected networks under gradient flow [2,5], our results imply that balancedness is generally not an invariant of training in such networks under gradient descent.
Since our work rules out balancedness and alignment as candidates to explain implicit regularization in deep linear networks with layer constraints or multi-dimensional outputs, this suggests other recently initialized approaches such as studying how architecture influences the function classes that can be represented by deep networks [18,22,17].

A Proof of Proposition 1
Proof. Assuming that A is balanced with B, then define M = A T A = BB T and let V and Σ respectively be square orthonormal and diagonal matrices satsifying M = V Σ 2 V T . Then there exist orthonormal matrices U and W such that U ΣV T and V ΣW T are usSVDs of A and B respectively. As a consequence, A is aligned with B.
To see failure of the converse, let A and B have singular value decompositions A = U Σ 1 V T and B = V Σ 2 W T where all diagonal entries of Σ 1 and Σ 2 are distinct with Σ 1 = Σ 2 . Then A is aligned, but not balanced, with B.

B Outline of Proof for Theorem 1, Corollary 1, and Proposition 4
We now provide an outline of our results and proofs.
1. In Appendix B, we introduce Lemmas 1, 2, which will be used to prove Theorem 1.
2. In Appendix C, we provide the proof of Corollary 1, which relies on Lemma 2.
3. In Appendix D, we provide the proof of Proposition 4, which relies on Corollary 1.

4.
In Appendix E, we introduce Theorem 4, which is a generalization of Theorem 1 to fully connected networks with rectangular layers. We use Lemma 2 and Proposition 4 to prove Theorem 4.

5.
In Appendix F, 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.
If alignment is an invariant of training under the squared loss for network f = W d W d−1 . . . W 1 on data (X, Y ) ∈ R k×n ×R k×n , then strong alignment is also invariant.
Proof. Assume that alignment is an invariant of training. Gradient descent on the objective proceeds via the following update rule: Since alignment is an invariant, the initialization satisfies W Since alignment is an invariant, the quantity is a diagonal matrix for all t. Since each of the Σ j are square, full rank matrices, the quantity must be diagonal for all t. The update rule for W 1 is given by is diagonal, and since this is also an orthogonal matrix we must have that V Similarly, the update rule for W d is given by: . 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 k i 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 k i are not necessarily all equal.
Proof. Gradient descent on the objective proceeds via the following update rule: 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 U i , V i and diagonal matrices Σ i such that . Substituting into Equation (11) yields

Thus strong alignment is an invariant if and only if for all
is an k i × k i−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 has its top r rows and top r columns all diagonal; i.e. we can write this expression as for an r × r diagonal matrix D and an arbitrary ( For the first direction, assume that strong alignment is an invariant, i.e. that Equation (12) can be written in the above block diagonal form. Define Σ 1 -this is a diagonal matrix whose only nonzero entries are the first r on the diagonal. We know that is of the form of Equation (13) for all gradient descent steps t, and thus the quantity 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 Σ tot are nonzero, which means that the top left r × r submatrix of V T 1 XX T V 1 is diagonal, and that the top right submatrix consists of all zeros. But since V T 1 XX T V 1 is symmetric, the bottom left submatrix must also consist of all zeros, and thus we have for an r × r diagonal matrix D 2 and arbitrary (k 0 − r) × (k 0 − r) matrix A 2 . Plugging this into Equation (12) implies that U T d Y X T V 1 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 T XX T V is diagonal and U T Y X T V can be written in the block matrix form given by Equation (13).
Initializing the layers such that U d = U, V 1 = V, and U i = V i+1 for i ∈ [d − 1] implies that Equation (12) is also of this block diagonal form, as desired.

C Proof of Corollary 1
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 where Λ, Λ are r×r diagonal matrices. Furthermore, from the proof of Theorem 1, if the layers are initialized to be aligned, with U d = U and V 1 = V , then the gradient descent updates are as follows: Since the minimum of the ranks of the Σ (t) i is r, only the top r singular values of W i are updated. Plugging in the expressions for U T Y X T V and V T XX T V 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: This completes the proof.

D Proof of Proposition 4
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 i . Since we're focusing on a fixed k, we drop the subscript k for convenience and let σ i ). The σ are updated by the following update rule: 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 = 0. Note that λ k > 0, since XX T is positive semidefinite. We can also negate columns of U to ensure that λ k > 0 as well. Let η = γλ k n , and define j . This yields Therefore (dropping the superscript to let S = S (t) ), and hence Thus we obtain where 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: Proof. We proceed by induction. By the original assumptions in Proposition 4, 0 < S (0) ≤ λ k λ k . Now assume that 0 < S (j) ≤ λ k λ k for all j ≤ t. By the update rule in Equation (14), σ Next, note that we can bound This means that we can upper bound the sum in Equation (18) as Since γ ≤ n ln 2 , and thus the right-hand side of the above expression can be upper bounded by Therefore r (t) k ≥ 0. Plugging into Equation (17), 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 (18) by the sets with size 1, so 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 This implies that S (t+1) is closer to λ k λ k than S is, and in particular 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.

E Proof of Theorem 4
We can finally state the generalization of Theorem 1 to the non-square setting: Theorem 4. Let f : R k0 → R k d be a linear fully connected network as in Equation (3), and let r = min(k 0 , . . . , k n ). 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 ∈ R k d ×k d , V ∈ R k0×k0 such that 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 σ 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 The rank of X 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 = 0, then we showed in Proposition 4 that S (t) converges to λ k /λ k in the limit.
Finally, we consider the case where λ k = 0, λ k = 0. Assume that σ (t) i < 1 and γ < n λ k . Then, the σ i 's update as Since S (0) is positive, we see that 0 ≤ S (t+1) ≤ S (t) , and therefore S (t) must converge to some constant c.
In general, we have shown that if λ k = 0, then σ k (W 1 (t)) · · · σ k (W d (t)) → λ k /λ k . This solution is given by which is the solution given by the pseudoinverse which obviously has a loss of zero.

F Completing the Proof of Theorem 1
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 U T Y X T V and V T XX T V are diagonal, as desired.

G Extension of Proposition 2
We extend Proposition 2 to Proposition 7 below. Proposition 7. Assuming gradient descent avoids the point where all parameters are zero, alignment is an invariant of training for any linear fully connected network f : R k0 → R, any convex, twice continuously differentiable loss function, and data (X, Y ) ∈ R k0×n × R 1×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 {Σ are diagonal with a single non-zero entry. Following the proof of Theorem 1, we obtain that alignment is an invariant if the matrix is diagonal. When i = 1, d, this matrix is clearly of rank 1 and diagonal (and has a single nonzero entry). This implies that U i , V i are invariant for all i = 1, d. If i = d, then since k d = 1, the above quantity is also a rank 1 diagonal matrix, implying that U d and V d 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 U 1 is invariant as well. Importantly, layers W i+1 , W i 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 j . Then the stationary points are given by: 1 ) = 0, then we have that: k ∈ R and ∀t ∈ Z ≥0 . Hence, updates to v (t) 1 are in the span of the data, and so assuming that j ) for all i, j ∈ {2, . . . d}, t ≥ 0 since for all i ∈ {2, . . . d}: This initialization corresponds to layers W i+1 , W i being balanced for i ∈ {2, . . . d}. Thus, under this initialization, the only other stationary point is given by i ) = σ 1 for all i ∈ {2, . . . d} (i.e. σ 1 = 0 now corresponds to a strict saddle as defined in [13]), 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

H Proof of Theorem 2
Proof. Given an arbitrary loss function, assume that the ith layer is restricted to some structure given by a subspace S and basis matrices A 1 , . . . A m , so that at timestep t we have that We take the gradient of the loss with respect to the c i j . The chain rule yields: The gradient descent update on c i j is thus: The corresponding update on W i becomes We calculate the projection operator π of some arbitrary matrix M onto S. We can write If we define the operator π S as π S (M ) = M pq A j pq A j , then gradient descent on the c gives the following update rule on the W i : If the A j 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.

I Treating a Convolutional Layer as a Linear Subspace
Consider a 3 × 3 image. We map it to a 9-dimensional vector as follows    x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 Then S consists of all matrices of the form W . S is a 9-dimensional subspace of R 9×9 , with an orthonormal basis with coefficients being the c i .

J Proof of Proposition 6
Before we can prove Proposition 6, 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 6. Given a k × k matrix A, let λ(A) denote the partition λ of k such that λ i is the multiplicity of the i th 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 To see this, note that any orthonormal basis of the eigenspace of AA T corresponding to the multiplicity-λ i eigenvalue of AA T 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 Let O(k, n) denote the set of k × n matrices 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 +