On Alignment in Deep Linear Neural Networks
Authors: Adityanarayanan Radhakrishnan
Eshaan Nichani
Daniel Bernstein
Caroline Uhler
Venue:  (2021)
Keywords: Alignment
Linear Neural Networks
Implicit Regularization

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.  


Under review as a conference paper at ICLR 2021
ON ALIGNMENT IN DEEP LINEAR NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
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 natural extension of alignment in networks with I-dimensional outputs as defined by Ji and Telgarsky, 2018. While in fully connected networks, there always exists 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 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 impossible with sufficiently large datasets.
INTRODUCTION
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 form implicit regularization occurring through training (Zhang 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 linearly separable datasets become aligned in the limit of training. That is, for a linear network parameterized by the matrix product WaWa-1.. ... Wi, the top left/right singular vectors u; and v; of layer W, satisfy |0 u|| + the number gradient descent steps goes to infinity.
Alignment of singular vector spaces between adjacent layers allows for the network representation 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 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 Di & Telgarsky (2018) to show convergence
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 training in linear neural networks under gradient descent. Prior works (Gidel et al.] 2019 Saxe et al. [0044] 2019) have implicitly relied on invariance of alignment as an assumption on initialization to simplify training dynamics for 2 layer networks. In this work, provide necessary and sufficient conditions for when alignment is an invariant for networks arbitrary depth. Our main contributions are as follows:
1. We extend the definition of alignment from the I I-dimensional classification setting to the multi- dilliiidmmesionall setting (Definition 2 and characterize when alignment is an invariant of training in linear fully connected networks with dimensioal outputs (Theorem []]
2. We demonstrate that alignment is an invariant for fully connected networks with multidimen- sional outputs only in special problem classes including autoencoding, matrix factorization

---

Under review as a conference paper at ICLR 2021
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 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 consequence, our characterization of the invariance properties of alignment provides settings under which the gradient descent dynamics can be simplified and the implicit regularization prop- erties can be fully understood, yet also shows that further results are required to explain implicit regularization in linear neural networks more generally.
RELATED WORK
Implicit regularization in overparameterized networks has become subject of significant interest (Gunasekar et al. 2018a 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. (018). 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 Jī & Telgarsky (2018) 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 rank matrix, i.c.
lim
and that adjacent layers, Wi+1 and W; become aligned, i.e. 10 4/ +
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 definition of alignment corresponds to the initialization considered in Gidel et al. (2019). Moreover, we establish necessary and sufficient conditions for when alignment an invariant of training in Theorem instead of assuming these conditions. Furthermore, their result on sequential learning of components can be derived via our singular value update rule in Corollary
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 W.' W. = W++1 W for all i at initialization, then this property is invariant under gradient flow. Du et al. (2018) present more general form, that W W W WT is constant under gradient flow. 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 approximate balancedness (Arora et al. 2019a) and e-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 to help understand both the dynamics of training and properties of solutions the end of training.
2

---

Under review as a conference paper at ICLR 2021
3 DEFINITION OF ALIGNMENT IN THE MULTI-DIMENSIONAL SETTING
In this section, we first define alignment for linear neural networks with multi-dimensional outputs. We then define when alignment is an invariant of training.
We consider linear neural networks. Let f Re + R denote such a dllayer network, i.c.
f(z) W WaWa-1... Waæ
(1)
where W; E R for i E [d], where we follow the convention that [d] = {1, 11,,....d. d.. Let YX E IR x Rax denote the set of training data pairs [(x(), y for E [n]. Gradient descent with learning rate is used to find solution the following optimization problem:
arg min 1 JEF
((f(x())) v())
2n
where F is the set of linear functions represented by f and is real-valued loss functiio. When not stated otherwise, we assume { (x(()))) (0) = |l - f(x())) which is the squared loss (MSE). In addition, denote by w( for E Zzo the weight matrix W, after steps of gradient descent. When there are no additional constraints on the matrices W, then f is a fully connected network.
We next introduce generalized form of the singular value decomposition: Definition 1. An unsorted, signed singular value decomposition (usSVD) of a matrix A E mRxx is triple U E gmxm, L Rmxxn V E g2xx such that U, V are orthonormal matrices, E is diagonal, and = UEVT.
In contrast to the usual definition of singular value decomposition (SVD) of a matrix, the diagonal entries of E may be in any order and take negative values. Throughout, will refer to the entries of E in 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) the multi-dimennsonal setting. Definition 2. Let f = WaWa-1.-. Wi be a linear network. We say that f is aligned if there exists usSVD W, U,,,V? with U, VL+1 for all i [d - 1j. ( (We also say that matrix A is aligned with another matrix B if there exist usSVD's A = UAEAVA VA B UB V such that VA UB.)
Note that if W; and W++1 rank matrices in aligned network f. then the inner product of the first columns of Vi+1 and Ug is in absolute value. Hence Definition 2 is consistent with alignment in the I-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 initialization (w - such that (((os) wr(o) ...., w/(0)) achieves zero training error and for all gradient descent steps E Z2o
(a) the network f is aligned;
(b) w VT for all
all i E (2....d 1}, that Ug, V; are not updated;
(c) (((0) = U, and w-10) = (1( V that is, U1 and Va updated. If additionally, Vi and Ua are not updated any E Zzo, then we say that strong alignment is an invariant of training.
When alignment is an invariant of training, there important consequences for training. In particular, note that when the network f is aligned with usSVDs W, = U.E.V." for all 1 < i & d, then
d-1
f(x) = Wa WI = Ua
II
Ed-i
V x.
(3)
'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 not the product of diagonal matrix with the input.
3

---

Under review as a conference paper at ICLR 2021
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 Vi and Ud-
Remarks. 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 Ji & Telgarsky (2018).
4 ALIGNMENT IN FULLY CONNECTED NETWORKS
In this section, we first characterize when alignment is an invariant of training for fully connected networks (Theorem DT. 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 I-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 proof of linear convergence of gradient descent to an interpolating solution.
4.1 CHARACTERIZATION ALIGNMENT WITH MULTI-DIMENSIONA. OUTPUTS
Theorem D 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 ky for all 0 S í, < d. The general result for non-square matrices is provided in Appendix D
Theorem 1. Let f R* - TR be linear fully connected network with d 2 3 square layers of size h > 1. Alignment is an invariant of training under the squared loss on a dataset (X,Y Y) E Rkxn x Rkx and only if there exist orthonormal matrices U, U.V. Baxk such that UTYX and V X are diagonal.
The full proof of this result is presented in Appendices A here, we provide proof sketch.
Proof Sketch. The proof essentially follows by induction. For the base case, we initialize the layers {W 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 +
After substituting the alignment conditions into the gradient descent update equation for the squared loss at stept +++ 1 and cancelling terms, obtain that alignment is invariant of training if and only if
En - (z)(()))) v(
a diagonal matrix. By considering the update for (((t) and ((()) one sees that alignment implies strong alignment and so Ua, Vı are also invariant across updates. Thus, let U2 = U and V1 V. By expanding (x)( using equation 3 and considering the update across multiple timesteps, we obtain that the matrix in equation is diagonal if and only if UTYX"> and VT XTV are diagonal. To complete the proof, we show in Appendix D that under strong alignment, gradient descent converges to solution with zero training error.
Theorem Saanremmiiiiin Iimplies 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 also provide empirical support showing that alignment not an invariant of training for important tasks that violate the data condition presented here, such as multi-class classification.
4

---

Under review as a conference paper at ICLR 2021
4.2 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 V" U'XVVV. Taking to the left singular vectors of X satisfies the conditions of Thhorem
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 For matrix inversion, we have that Y and we proceed analogously.
Matrix Sensing. Given pairs of observations {(M,, y:) with M, E R and y: = Tr(M X*) for some unobserved matrix X E B gradient descent on {Wi]== is used to solve
n
Σ ll Tr(M, WaWa-1 Wi)ll
arg min (We) 2n
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 shows that alignment an invariant of training in this setting and only if M4 = UAVV" for all [n]. and U2 = U, V1 = V.
1 1-dimensional Outputs. In Appendix [F] we show that alignment is an invariant of training for fully connected networks with I-dimensional outputs for any real-valued loss function provided that gradient descent converges to zero training error.
4.3 CONSEQUENCES ALIGNMENT
We next discuss various consequences of the invariance of aligmment for the analysis of training. Our explicit characterization of alignment as an invariant is significant as 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 Appendix B) follows from the proof of Theorem I and shows that under alignment the gradient descent update rule is simplified significantly.
Corollary 1. Let r = min (ko, ki...., ka) > 1 and let the top left x submatrix of Y be A' and that of X A. Under the invariance of strong alignment (ie., when N and are diagonal), we can express the partial derivative with respect to W; as follows:
0L OW.
-_:
II 1=++1
YX''V' Ea. XXXXX
II Σ3 VT.
(5)
j=1
As result, gradient descent only updates the first values of E.. Let En(() be the top left x matrix of s(()) The updates are then given by:
Ex(++1)
E (1)
(6)
The other entries of x (((+))
(1+1)
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 given Appendix C
Proposition For l [r]. let o (W.) denote the kth entry of Σ, in the usSVD of W,, and let dg. X denote the kth entries of A, N' respectively. Under the conditions of Corollary | and
Nr. for all [r], if the learning rate satisfies assuming that 0 (W O and II (x(w(!)) ==1
7 S ml2 ming
( Ax then gradient descent only updates the top r singular values of the X
d
solution and converges linearly to the global minimum.
5

---

Under review as a conference paper at ICLR 2021
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 shows that for fixed depth, gradient descent converges linearly. Our analysis in Appendix C shows that 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 fg-norm. The proof is given in Appendix [
Proposition 2. Let W1. W2 be matrices such that WyW; = P. for a fixed matrix P. Then, [[ [ + 2|2 achieves minimum at the solution where W1 and W2 are aligned and O-balanced, i.e. there exist SsS'D's s W WEV*, W₂ UEWT.
It has been shown that SGD in the overparameterized setting for network initialized close to will converge to solution close in f2-norm to the minimum 22-norm solution (Azizan et al. 2019). Therefore we expect such networks to converge solution which is close an aligned solution.
5 ALIGNMENT UNDER GENERAL LAYER STRUCTURE
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 aligmment 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, aligoment cannot happen, let alone an invariant of training.
5.1 LINEAR NEURAL NETWORKS WITH LAYER STRUCTURE
We start by setting up mathematical terminology to describe different layer structures.
Definition 4. Let S C Rmxn be linear subspace of matrices and let (Ai) be an orthogona ?
basis for S. Layer Wi has layer structure S if W; E S, i.e., there exist coefficients {c) C IR such that W; Σド= A. and gradient descent operates the [e=
Definition 4 eencompasses layer structures commonly used in practice, such as:
Convolutional layers: Treating a x p image as a vector in Re² a single x s convolutional filter with stride and padding (s 1)/2 maps the image another p X p image; this linear transformation is a matrix in p xp² and the set of all such transformations forms an -dddimensional subspace. The parameters of the filter are coefficients of an orthogonal basis of this subspace; Appendix
Layers with Sparse Connections: Consider a fixed connection pattern between layers such that the jth hidden unit in layer depends only subset of units in layer i 1. In this case, the subspace 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
Theorem 2. Performing gradient descent on the basis coefficients (c) leads to the following weight matrix updates:
(1+1) = w((!) TS
aI ow
where a denotes the projection operator onto S.
Theorem shows that gradient descent in networks with layer structure is equivalent to projected gradient d 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.
2 "Othogonality w.r.t the inner product (A, B) = Tr(A" aT B), or equivalently dot product in Rmn ws is projection in the traditional sense if and only if the A, form orthonormal basis; otherwise, TT projection onto S followed hy appropriate scaling in each basis direction.

---

Under review as a conference paper at ICLR 2021
5.2 NECESSARY CONDITION FOR ALIGNMENT
Motivated by the above characterization via projected gradient descent, we now show that for layer structures with constrained dimension, aligned networks generally cannot achieve zero training error under the squared loss, given sufficient data (Proposition This is the case even when there is solution with the desired layer structure that achieves zero training error. Hence, 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
Proposition 3. Let (X.Y) E R x R such that 2 ko and X is full-rank (ensuring that XX is invertible). If an aligned network f = WaWaa 1... .... W1 achieves zero error under squared loss (i.e. ifY = ((X)) then W aligns with Y Y (XX+)-1 which in turn aligns with W
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 2 k, we state it in full generality using (7) 0, when m < 2.
Proposition 4. Let S be an r-dimensional linear subspace of k x i matrices. Ifr < k- (kar)) then the set of matrices of size of the identity, has Lebesgue measure zero.
that can align with an element of S, excluding sealar mulriples
Taken together, Propositions 3 and 4 Timply Theorem 3. which states that alignment does not occur in linear networks with constrained layer ki and that all layers have the
The proof of Proposition Dis is provided in Appendix K
structures given enough training samples. We assume k = ho same structure, S. The statement can trivially be extended to the general setting.
Theorem 3. Let 2 k, let X, E Re be generic, let C Rixk be a linear subspace of dimension < k - 1, and let W W1.... Wa E S such that at least one W; is not a scalar multiple of the identity q If the network f = Wa a Wi satisfies Y = ((X), then f is not aligned.
Theorem is in contrast to fully connected networks (i.e., no layer constraints), where we showed that aligmment 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. Ifm² 2 4, then a generic dataset consisting of n. 2 m2 m x m images cannot be aligned by any convolutional linear autoencoder with filter size 3, aside from the trivial case where all layers are sealar multiples of the identity. This follows from letting m² r = 9 in Proposition
6 EMPIRICAL SUPPORT
In this section, we provide experimental results to validate our findings We measure two properties: (I) invariance of alignment from initialization, and (2) alignment between layers. Invariance of alignment at time is measured by the average dot product between corresponding columns of t:!!) and U7!0) as well as v,(0) and v-(0). Alignment is measured by the average dot product between corresponding columns of 0,!0) and V+1 For both, value of 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 [ are violated. Figure I shows example where alignment is not an invariant for multi-dimensional regression with random data under squared loss. We used standard normal inputs X E R and targets Y E R9x9 and 2-hidden layer network initialized so that alignment holds at the start of training. Since X and Y do not have the same right singular vectors, the conditions of Theorem [ are violated, and hence alignment is not an invariant of training. In Figures D and c, we show that alignment is also not an invariant in standard classification settings. We trained 2-hidden layer fully connected network classify linearly separable subset of 256 MNIST examples under MSE loss and cross entropy loss. Figure Ip is consistent with the generalization of
*This not a serious restriction; modulo scalar multiplication, the only case in which such network could achieve zero loss is autoencoding, in which case the latent space would be a scalar multiple of the data itself. Hyperparameter settings detailed in Appendix M
7

---

Under review as a conference paper at ICLR 2021
Algnement Inverience
Alommmett invariance Lones
137
Akoementt Invarience non Lowe
Alggmment evatrance
Migmmentt munnemee
Crous Protropy Lokk
MSL
MISE
12
121
26
21t
2004
40003
2004
0003
1300
2000
3000
-000
30.00
0601
Ileration
Eorwton
itoration
(a) Multi-dimensional regression (b) Multi-class classification MNIST with squared loss.
(c) Multi-class classification
random data with squared loss.
MNIST with cross entropy loss.
Figure 1: Examples of fully connected networks with multi-dimennional outputs where alignment is not an invariant of training.
Alignmen: Invanance Losp
Aligmment Invarlance
Loos
6.00
5 F 8.
A0:00
Eoration
(a) Matrix factorization with layers constrained to be Toeplitz matrices.
(b) Autoencoding a single MNIST example
using convolutional network.
Figure 2: Examples of layer constrained networks, where alignment not an invariant of training.
Theorem T (Appendix D
Interestingly, this result empirically transfers 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 the dimensionality of the layer structure is much larger than that of the output. In the setting of matrix factorization (Y E _ X I), k n, so Theorem states that alignment impossible when the linear structure has dimension < k - 1. In Figure 24. we observe that alignment is not invariant 1, by training a 2-hidden layer Toeplitz network to factorize
also even when 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. training when autoencoding a single MNIST example using 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 | are satisfied.
4 matrix.
Figure Pp, we show that alignment not an invariant of
7 DISCUSSION
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 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 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 fully understand implicit regularization, such 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.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning (ICML), 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A converge analysis of gradient descent for deep linear neural networks. International Conference on Learning Representations (ICLR), 2019a.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning (ICML), 2019c.
Navid Azizan, Sahin Lale, and Babak Hassibi. Stochastic mirror descent on overparameterized nonlinear models: Convergence, implicit regularization, and generalization. arXiv preprint arXiv:/906.0m /900000303330 2019.
Rajendra Bhatia.
Matrix Analysis. Springer- Verlag, 1997.
Simon S. Du, Wei Hu, and Jason D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pwer-parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Internation Conference on Machine Learning (ICML), 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018b.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations (ICLR), 2018
Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent converges to minimizers. In Conference on Learning Theory (COLT), 2016.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang, Algorithmic regularization in wer-parameterrized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory (COLT), 2018.
Charles H Martin and Michael W Mahoney. Implicit reff-regularization in deep neural networks:
Evidence from random matrix theory and implications for learning, 2018. arXiv:1810.01075.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning, 2014. 1rXiv:1412.6614
Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Memorization in overpa- rameterized autoencoders. In /CML Workshop on Identifying and Understanding Deep Learning Phenomena, 2019.

---

Under review as a conference paper at ICLR 2021
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? arXiv preprint arXiv:1902.05040. 2019.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In International Conference on Learning Representations (ICLR), 2014.
Andrew M. Saxe, James L.. McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 116 (23):11537-11546, 2019. ISSN 0027-8424. doi: 00.1073/pnas.18222261166 URL https
/www. / htt.a//.orrrgooteee//////////33
Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. arXiv preprint arXiv: 08587, 2018.
Daniel Soudry, Elad Hoffer, Mor S. Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research (JMLR), 19(1): 2822 2878, 2018.
Xiaoxia Wu, Simon S. Du, and Rachel Ward. Global convergence of adaptive gradient methods for over-paramcterized neural network? arXiv preprint 1nXiv:1902.07111 2019,,
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Reprexentations (ICI.R), 2017.
Chiyuan Zhang. Samy Bengio, Moritz Hardt, and Yoram Singer. Identity crisis: Memorization and generalization under extreme overparameterization. In International Conference on Learning Representations (ICLR), 2020.
Difan Zou, Yuan Cao Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes werrparameterized deep relu networks. arXiv preprint arXiv:1811.08885 2018.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
A OUTLINE OF PROOF FOR THEOREM COROLLARY
1 AND PROPOSITION
We now provide an outline of our results and proofs.
1. In Appendix A
introduce Lemmas 2, which will be used to prove Theorem
2. In Appendix B provide the proof of Corollary 1 the simplification of gradient descent under alignment- which relies on Lemma 2.
3. In Appendix we provide the proof of Proposition T- alignment- which relies Corollary [
linear convergence under strong
4. In Appendix D we introduce Theorem which is generalization of Theorem to fully
connected networks with rectangular layers. We use Lemma and Proposition to prove Theorem 4
5. In Appendix we finally prove Theorem which follows from Theorem
Here, we present two lemmas that will be used extensively in our proofs.
Clearly strong alignment being an invariant implies that alignment is invariant. Now show that alignment implies strong alignment in the case of networks with square matrix layers.
Lemma 1. Let (w.) C R where 2 3. If alignment is an invariant of training under the squared loss for network f = WaWa-1... W1 on data (X,Y)= 12xxn x RRk,n, then strong alignment is also invariant.
Proof. Assume that alignment is an invariant of training. Gradient descent on the objective
arg min JEF
(1) (f00-f(xx0 f(x(
(7)
2n i=1
proceeds via the following update rule:
n
w((++ w!! + ((w W )Z
2 y f(a"))( w.. Vie [d]. (8)
n
Since alignment is an invariant, the initialization satisfies wi U. VT for 2 iiid-a w Un ( ('(("))
y(t) and Wh(t= =
=U!">'] xd VT where U, = Vi+1 for i (d - 1]. For 2 <is d-1,
substituting into Equation { yields
= VT + 2U
(0
VT
Σ (n -(=(0) 20000(1)> ~00r
U,
(2)
7
T DJ
> (g)0)) f(x
)2x v-(
(')
Vi7
n
jmit1
U,
(t)
2
(T)
v - 2:1 21(00)
(()) (t)
xxT (2)
II
V.T.
5=1
Since alignment is an invariant, the quantity
II 200 (U) - -E ... 2("1(()) xxx jmit1
II
(9)
a diagonal matrix for all f. Since each of the E, are square, full rank matrices, the quantity
T V x x(9 xxTv(()

---

Under review as a conference paper at ICLR 2021
must be diagonal for all t.
The update rule for W1 is given by
+ 7 (w() ... ...WWl " E00 - f(20)))
w w/
n
U1 U1 (. = U1
( U (YX* - -UDDI .......... 110 -xx7) Xx²)
+ 1
d = 2((t))((t)) 1ith = 21th + II
(
(U
vX - M ...'"""1('''0 X
j=2
which is diagonal. Therefore v((++) 1) must have that v(((+1) = v(() Similarly, the update rule for Wa is given by:
v(( is diagonal, and since this is also an orthogonal matrix
((+1)) d
+ 2
(y
f(x 1(=00)) (W/6)- d-1 -
Th
U 1 (++
V2 = 1 V2 + (YX* -1 ....../ 1() x
(1)
U
T
j=1
TS Uh (ftt)) (++1)
2 +U!! vxTv(1 E V( x
II
U T d-1
which is diagonal. Therefore U (((+1) is also diagonal, implying that US = ((+1) Therefore strong alignment is also invariant. This means that alignment being an invariant and strong alignment being an invariant are equivalent in the setting where all the k; are equal.
d
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, are not necessarily all equal.
Lemma 2. Let ʃ Ro + Ra be a linear fully connected network as in Equation equation | and let min(ko..... ... k.). For training under the squared loss the dataset (X,Y) there exists aligned initialization (x) W ...((%) such that W:(0) U VT for all E [d] (that is, Us, V₁ are not updated) if and only if there exist orthonormal matrices U e Rkaxka V Roo such that
= UTYX"V
A'
0
and V"XX-V =
A 0
0
A
A2
for diagonal r X matrices A, A' and arbitrary A E x A2 E ()(
Proof. Gradient descent on the objective
(-)0 f(x(1))
arg min JEF
2n
i=1
proceeds via the following update rule:
a ((9) 7
w((t+11) w!!!) + 7 ((W(())
[ - f(( - () "/ w/ vi [d].
n
1=1
(10)
12

---

Under review as a conference paper at ICLR 2021
where y is the learning rate and superseript (t) denotes the gradient descent step. Assume that the network is initialized to be aligned, that is, there exist orthonormal U2 V, and diagonal matrices Σ; such that W; = U,E,V? and U, Vi+1 for E [d 1]. Substituting into Equation (10) yields
n
w U. V/ + 2
v
E0 f(x ((=0)))))-112
n
U,
Σ (t)
7
U2
(y
f(x"1)))200)
Vi
Vi7
ni
j=i+1
=
U,
2
2
II
T
( Vf
())))
V??
T j=i+1
Thus strong alignment is an invariant if and only if for all i, the quantity
II D/p (UTYX*V Ef j=++1
II
is h; x - diagonal matrix for all t. At initialization each of the "n have rank at least Considering = and d, the above quantity diagonal if and only if the matrix
Y - x V
(11)
has its top r rows and top columns all diagonal; i.e. we can write this expression as
A [
(12)
for an x r diagonal matrix D and an arbitrary (ka -) X (Ko r) matrix A.
For the first direction, assume that strong alignment an invariant, i.c. that Equation can be written in the above block diagonal form. Define ()t) = x(t) ... ...x(f)) this is a diagonal matrix whose only nonzero entries are the first on the diagonal. We know that
U V si V2 xx
of the form of Equation 12 for all gradient descent steps f, and thus the quantity = V
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) E are nonzero, which means that the top left r submatrix of V/T xx"V,, diagonal, and that the top right submatrix consists of all zeros. But since V," X is symmetric, the bottom left submatrix must also consist of all zeros, and thus we have
VXXX
D2
0
0
A2
for diagonal matrix D2 and arbitrary (kg Equation 11 implies that Y Y x Vi must be of this form as well.
(Au -) matrix Ag. Plugging this into
We next show the other direction. Assume that for VT XVVV is diagonal and U can be written in the block matrix form given by Equation
orthonormal matrices U and V, it holds that
Initializing the layers such that Ua U, V1 V, and U₃ V141 for E [d implies that Equation is also of this block diagonal form, as desired.
12
PROOF OF COROLLARY
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
A'
UTYXTV
and
0
A
VTxXTV-
A
0
0
A2
13

---

Under review as a conference paper at ICLR 2021
where A, A' are diagonal matrices. Furthermore, from the proof of Theorem if the layers initialized to be aligned, with Ud U and V1 = V, then the gradient descent updates are as follows:
d
w((+)= UÚ
( +
DOO (UTYX" - E ... V'V. II -=++1
II
VT.
Since the minimum of the ranks of the (()) is only the top r singular values of W; are updated. Plugging in the expressions for UTYX"V and V V and restricting to the top r singular values (which we denote by ED), we obtain the statement of Corollary ! with the singular values of each layer being updated as:
Ex(+1)
E (t) + 2
II
(4)
(A'
II Σ 10 A). j=1
A).
71 174
This completes the proof.
C PROOF OF PROPOSITION 1
Proof. By Corollary L 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 0x (W denotes the kth diagonal entry of (()) Since we're focusing on a fixed k. we drop the subscript for convenience and let (( equal ox (W.")) The a are updated by the following update rule:
d A
(1+1) = o.
12 (X. 11 J
II 10)) j=1
where Xr As are the kith diagonal elements of A', A. We assume that A' and A have the same zero pattern. Therefore 0 if and only if X/2 0. If both of these values are zero, then o; is updated.
Otherwise, assume Ak. X/e # Note that 0 > since XXx positive semidefinite. We can also
negate columns of U to ensure that X > 0 as well. Let 2Ax, , and define 5(t) = -I1 of This yields
(++1) a( +
S(t)
X
S(t)).
(13)
oi
Therefore (dropping the superscript to let 5 = 5(1))
s(++1)
II
o
(++1
II
(t)
n
1
Ne
-S)
(t)
d
N/
S
Σ
S
TI
0
(4)
d
(4)
T2l411121
iET
0
İT
X
S
Σ
1)
A
(o
(0())
TC44T121
SET
and hence
X/4
X/2
N A
S(t+1)
Σ
1
SSYT
(14)
A
(a
(9)
TC(4/T121
N/2
-)
1-
Σ
17 TI
X
1
(15)
TCM:11121
A
iET
(a
14

---

Under review as a conference paper at ICLR 2021
Thus obtain
X
g((1)
(1z
5(()
(16)
XE
where
K =
(1)
=1
Σ
17
X
(17)
N
ET (a )2
TC(4:17111
(t) We aim to bound (()) from both above and below. First, we show that rk is nonnegative in order to prove the following lemma:
Lemma 3. < (t) s X. X for all j 2 O.
Proof. We proceed by induction. By the original assumptions in Proposition
0 < ((
I X Ag
Now
assume that 0 < 80) S A (0) > 0, o (j) > 0, so s(i) O. We also have that
for all j S t. By the update rule in Equation (13 0;
(j+1)
2 0. Since
(1)
Ae
II eT
II iET
c1) (o;
)2
(0) (o,
(min, oi
(0) )
Next, note that we can bound
X
Ne 2 A
S
T1
sy1 -
d
This means that we can upper bound the sum in Equation 17 as
s
X
1)11111
II
r [T| (min 0 (0)) -212
X / 2//
TC A
(a:
2k
TC(d-1712
1 +++ (min o (0) (0)
-
we have that S In 2 min; (0)) side of the above expression can upper bounded by
Since S uln2 min; (a 5 Ax
2 and thus the right-hand
(1+ + n (min (0)) 1 do(min, (0)) 2 15
e cn2 1
Therefore r/ 2 Plugging into Equation 16 since ((+) = S
A/. A
we get that 5(++1) < X
which completes the inductive step.
Next, we would like to upper bound Th by 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
Ne d
S
iET (o:0)²
(0
TC(
where the last inequality is due to AM-GM Lemma implies that s(++1) 2 Sti, which means that
the above sum is at least ((0) 3 2/d which means that we can upper bound rk by
(0)
< 1 - ()((((0)))))))))) 2-2/d 2/d
This implies that S(++)) is closer to
X X
than S is, and in particular
N/ s((+1)
N
S) (0)
d
15

---

Under review as a conference paper at ICLR 2021
hence
1 5
X ((0)) -
A
Ap
Since the initialization is fixed, the quantity - dn(( is fixed, and thus S converges linearly to X Therefore each of the top k singular values converge linearly to their optimal value which means that the loss converges linearly as well. Ax
N/2
To complete the proof, it suffices to show that this limit solution achieves a training loss of zero. This proven in more general setting at the end of Appendix E
PROOF OF THEOREM
We can finally state the generalization Theorem ! to the non-square setting:
Theorem 4. Let Ro Rk be linear fully connected network in Equation equation ! and let r = min(ko.... ..... 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 Bkaxka ,, V E Rkkoe such that
UTYXTV =
N
and VTXx-v =
0
0
A1
A2
for diagonal r matrices A and arbitrary A1 (k)o--)x((k- A2 Riiko g()o--))((oo-))
Proof. By Lemma 2 we know that under strong alignment there exist U and V satisfying the above conditions. In the other direction, Lemma also tells that given and V satisfying the data conditions, all the conditions of strong alignment hold except for convergence to global minimum.
To conclude, we must show that regardless of the zero pattern of or A', under strongly aligned initialization the network converges to solution with a loss of zero.
Using the convenient notation that o, (t) oh (W! we again focus how the kth singular values of each layer are updated, for some E [r]. Recall that the a's are updated as
((+1) oi (1)
II jæi
(N
II )
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) ensure that whenever 2 0, X well. This ensures that a (W((1) is never updated. If Au, X a 0, then we showed in Proposition that ((t)
converges to / Ay in the limit.
Finally, we consider the case where X 0, Ax * 0. Assume that o.") 1 and 7 n. Then, the a,'s update as
0, (t+1)
-000)
7
A
(0) 0,
j
where 7) Ide We observe that 0 < a (1+1)
Therefore
d II i=1
d II i
0 s g((+1) = s(1) 1 - 1-
S s(t) exp (-ndssd(())2224
< 500 exp
3
Since 5(0) is positive, we see that 0 S S(++1) S S(9, and therefore 5(O) must converge to some constant c. Assume that e + O. For all c > 0, there exists some such that S(T) < <c c c. Then,
S(T+1) < S(T) exp (-1dS(1)3-210) < (c (c+
(-112-21d)
16

---

Under review as a conference paper at ICLR 2021
where exp (-nc2-2//4 is constant which is less than 1. Hence if we choose such that exp (ncc222/// < ctc
then S(T+)) C, a contradiction. Therefore c = 0, and hence
StC) - 0 - - c
In general, have shown that if A + 0, then VVTT -
ox (W) (Wa(()) - Xg/Ax. This solution is which is the solution given by the pseudoinverse which obviously
given by fxx) U&A'
has a loss of zero.
COMPLETING THE PROOF OF THEOREM
Proof. In Lemma I, we showed that in the setting where all layers square, alignment is equivalent to strong alignment. Theorem 4 states that in general, strong alignment is an invariant if and only there exist U, V satisfying particular data conditions. Since in the square setting k. by Theorem 4 we have that strong alignment is an invariant if and only if there exist U, V such that U V and VT X X are diagonal, as desired.
F ALIGNMENT FOR I-DIMENSIONAL OUTPUTS
Proposition 5. Assuming gradient descent avoids the point where all parameters are zero, alignment an invariant of training for any linear fully connected network f :RR + I, any convex, twice continuously differentiable loss function, and data (X, Y) can achieve zero training error.
)) E ko x 1I for which the network
Proof. If we initialize the weight matrices to be rank 1 and aligned, then the matrices (d diagonal with single non-zero entry. Following the proof of Theorem I an invariant if the matrix
===1 are we obtain that alignment is
II j=H+1
UJ
ae
(K) ())
II
I
0f ( (00)
is diagonal. When i # 1,d, this matrix is clearly of rank 1 and diagonal (and has single nonzero entry). This implies that U4, V2 are invariant for all i * 1, d. If ifi=c d. then since ka 1. the above quantity is also rank 1 diagonal matrix, implying that Un and Va are invariant. Finally, if i = 1. the above matrix 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 well. Importantly, layers W;+1, W; for E [d- 1] remain aligned regardless of the loss function used, as the expression above is always diagonal matrix with a single nonzero entry when the layers are initialized to be rank 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 (t) denote the first column of v((t) and let a i (W((t) denote the top singular value in the usSVD w:(() Then the stationary points are given by:
1. (W)( for j E [d].
ae
x (A)
2.
v/t)
1=1 0f
(z(A)
If we initialize 0 (W>(1)) = O, then we have that:
(1(W(() (1) ((()
(0) (A)
c + + II ai (W)!)) de
0f ya)) x(A)T
((+1)
J#k
17

---

Under review as a conference paper at ICLR 2021
for & (1) IR and VI E Z20. Hence, updates vi (t) are in the span of the data, and so assuming that
{> are linearly independent, 2 cannot be orthogonal to Σ al
(0)²² unless the
0f (1(1)
are all O, i.e. (W(")) = 0 for t > 0.
Next, if we initialize 01 (1(W(()) = 01 (W then o1 (W ( for all i, ( .2....dy dj.t 0 since for all E .J::
a de
= =,) + II a (w) (w J
(k)) (1)
Øs
(1(k),
This initialization corresponds layers W W; being balanced for i E {2.... d}. Thus, under this initialization, the only other stationary point is given by 01 (W: O for all i f2....d}.
Hence, if gradient descent avoids the non-strict saddle points given by 0 (W! 0 for all (2.... d) and 01 (W: 0 for all i E [d], then gradient descent converges to local (and thus global) minimum of the convex loss. The former stationary point can be avoided by re- pe-parameterizing
the network such that 01 (W!")) strict saddle 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 scaling factor on the learning rate for parameters 01 (W(()) for (2....d.. The latter stationary point is avoided by the assumption in the proposition.
for all f2....d) d} (i.e. 01 = O now corresponds to
G PROOF OF PROPOSITION 2
Proof. For any matrices A, B E Cm we have that 2o,(AB*) S (, B) Bhatii 1997 Thus letting A = W2, B WT' see that
20, (o, 1 o.WW, W2 + WaW?)
= 2 > (P) S Σ (W3 W2 + WiW?)
= IW3 W2 + W la
S I| W2ll1 WWW
||2111 + ||
This lower bound fact achieved for an aligned solution. the SVD of is UEVT setting
W, = W and Wa = SV v yields |Wil = || Tr(E), so | + || 2Tr(E).
PROOF THEBRRE
Proof. Given an arbitrary loss function, assume that the ith layer is restricted to some structure given by subspace S and basis matrices A!.... Ams so that at timestep we have that
w Σ (
We take the gradient of the loss with respect to the ef. The chain rule yields:
at
al
a(W))
al
Σ
A
0et
a(W.)mg
d
a(W)
1
p.0=1
18

---

Under review as a conference paper at ICLR 2021
The gradient descent update on oj is thus:
01
12
= - 11 dc²
(c))
Σ
A pq
a(W
p.9
p4
The corresponding update on W becomes
W (1++1) 1)
(c)) (+))++)))))) Aj
01
Σ (c)) (1) Aj 17
App
d(W,)
/=1 p:4=1
m
0l
w/
A4 45
a( 0p
j=1 P.g
We calculate the projection operator of some arbitrary matrix M onto S. We can write
(M, A
Mpg Apy A
(MM)
P.g
If we define the operator ss
<s(M) Σ (M, = Σ
Σ
M pq A/ A1
J=1 p.g=1
then gradient descent on the gives the following update rule on the W
w((t+ ((()) 77 -S
aL
aw.
If the Aj all have norm 1, then, Ts. and this is the same update rule given by projected gradient descent with respect to the subspace S. Otherwise, as is simply the projection ' followed by appropriate scaling in each of the basis directions.
I TREATING A CONVOLUTIONAL LAYER AS LINEAR SUBSPACE
Consider 3 x 3 image. We map it to 9-dimensional vector follows
72
33
I4
45
26
[11
32
233
24
25
26
27
28
[g
Cc
C2
C3
Then, the linear transformation given by applying the 3 x 3 convolutional filter
is
C7
C8
Cg.
given by the matrix
C5
0
0
0
C6
C5
C4
C3
C2
C1
0
0
0
Cg
07
C5
64
02
01
W
0g
03
C6
05
03
02
C4
Cg
08
e7
C6
05
C4
0
Cg
C6
C5_
Then S consists of all matrices of the form W. is 9-dimensional subspace of 9x9 with an orthonormal basis with coefficients being the 6;-
19

---

Under review as a conference paper at ICLR 2021
J PROOF OF PROPOSITION 3
Proof. For i E [d]. let V be a usSVD of W; witnessing alignment of f. We can then rewrite
Y = f(X) as Y Ua I E thus proving the desired statement.
K PROOF OF PROPOSITION 4
Before we can prove Proposition 1 we require the following definition from combinatorics.
Definition 5. A partition of an integer is a tuple X = (A1,.... As) such that X Z Xit1 for all i and k A +...+ Ag. Each is called part of X. We let s(X) denote the number of parts of and we write X + to indicate that is a partition of k.
Proof of Proposition 4 Given a x k matrix A, let X(A) denote the partition such that A; is the multiplicity of the 7th greatest singular value of A. Let (A) denote the set of matrices U such that UEVT is usSVD of A. The dimension of U (A) is
(((A)) Σ
2
To see this, note that any orthonormal basis of the eigenspace of AA corresponding to the multiplicity-A; eigenvalue of AA can be corresponding columns in an element of (AA) and that the set of orthonormal bases of an m-dimensional linear space is (?)
For any Q of matrices, Define U(Q) be the of all possible of left-singular vectors of elements of S. That is,
U(Q) = UUU U(A).
AEQ
For each partition À of k let T,, denote the set of matrices A such that X(A) = A. The dimension of T3 nS most and therefore the dimension of U(S n Tx) most
s(A)
A
Let (k, n.) denote the set of k 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 C O n) with dim( B) (im(O n)) such that for every U B, U(S) contains matrix whose first columns are U'. Therefore dim (S) 2 dim(O(k, n)). Since dim dim(O(k n)) must be satisfied for some À +
(5) (R==)) the following
((A)
A 2
k
n2
>
(18)
2
This is attained when À = (k), but in this case T' is simply the set of scalar multiples of the identity. attained by
we forbid (k)), then we claim that the maximum value of r + e()) (As) (k: 1). To see this, note that for all p < g.
iml
p ( 2
q 9--9 p
9 p(q -p) <
9 2
2
For p > O, this is maximized when = This implies that the maximum value of E (2) will be obtained in as few summands possible (which in our case is two), and in particular when
d = k and Xg = In this case, equation [8] becomes
k
n 2
+
2
2
-
Taking the logical negation of the above inequality and simplifying gives < k-1 -((-m))
n
20

---

Under review as a conference paper at ICLR 2021
L ADDITIONAL EXPERIMENTS
We provide the following empirical evidence demonstrating that when the conditions of Theorem | satisfied, invariance of alignment indeed be observed empirically. We use 2-hidden layer fully connected network with 9 hidden units per layer.
0312
Setction
ceratio
Eerattoo
(a) Autoencoding (X (b) Matrix Factorization (X (c) Matrix Inversion (Y [)
Figure 3: As proven in our work, alignment is invariant of training when X, Y satisfy the conditions of Theorem
M EXPERIMENTAL SETUP
We provide network architectures and hyperparameters used for our experiments below. We trained networks on an NVIDIA TITAN RTX GPU using the PyTorch library. In all settings, train using gradient descent with a learning rate of 10 -2 until the loss was below 10
1. Figure 1a: We use a 2-hidden layer fully connected network with 9 hidden units per layer. Our data is given by matrices Y) R where each matrix entry is drawn from standard normal distribution.
2. Figure lb: 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 Ic: We use a 2-hidden layer fully connected network with 1024 hidden units 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 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 4 X matrix with each entry sampled from standard normal distribution.
5. Figure 2b: We use a 2-hidden layer convolutional network with single x 3 filter in each layer, stride of 1, and padding of 1. Our data consists of single example from MNIST.
Code for the experiments can be found at the following anonymized github link: https:// anonymous 4open. httpep/......ae////27/./00004063
21


Reviews:
[{"review_id": "uT18Q9yla7", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces the property of *alignment invariance* of gradient descent for linear networks. Under this definition (Definition 3) the left singular vectors of the linear transform in layer i is aligned with right singular vectors of i+1, and further the definition requires that the singular vectors remain constant throughout the training process (only the singular values are updated along gradient updates). The main theorem derives the necessary and sufficient conditions under which such a notion of alignment invariance is possible. The paper further shows that when such a condition holds, the trajectories of gradient descent are simplified for analysis of convergence speed. \n\nMy main concern with the paper is that the definition of alignment invariance in Def 3 is very restrictive and the motivation for considering such strong conditions is not sufficiently justified.\n1. This definition is significantly different and a much stronger condition compared to similar  properties in prior work: (a) “alignment” in Ji & Telgarsky 2018 (for 1D output) refers to condition where only the final converged solution has aligned singular vectors, but at initialization and throughout training the alignment and invariance need not (and does not) hold, and (b) the balancedness in Arora et al. 2018 and Du et al. 2018 (for gradient flow) are conditions on W_i^TW_i^T-W_{i+1}W_{i+1} being small throughout training. This requires that the singular values be nearly aligned but they need not be constant through the training process. This is a significant difference as for any dataset, the balancedness W_i^TW_i^T-W_{i+1}W_{i+1} can be shown to always be an invariant through gradient flow but that is not true for singular vectors. \n\n2. In practice, this condition almost always never holds without requiring circular computations. For example, in order to initialize an autoencoder to satisfy Def 3, one needs to do know the spectral decomposition of data matrix X, which is in fact the primary computation performed by linear autoencoders! Also, No examples are provided where predictors obtained through such restrictive flows lead to useful models. \n\n3. It is ok to consider restrictive assumptions if such assumptions provide significant new insights and results that are atleast somewhat relevant in practice. However the main use case for this Def 3 in the paper is that these conditions make the analysis of convergence speed of gradient descent simpler. But for linear networks, even though the underlying problem is non-convex, many existing results show convergence of gradient descent under often much less restrictive conditions, e.g., with just balancedness at initialization in Arora et al. 2019a. More specifically, the paper shows Def 3 leads to simplified dynamics, but it is not demonstrated how one can use the simplified dynamics to derive new results/insights that were not previously known. Finally, in terms of pure analysis, although the paper extends for deeper networks, the key proof ideas are similar to those of Gidel et al. 2019. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gMwfR00_963", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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 \n\nThe paper is very clearly written and is offers a coherent explanation of the ideas presented. The presented theoretical results are interesting. However, the constraints on the datasets X and Y in Theorem 1 are pretty stringent. It might be interesting to present a study on how realistic these conditions are in practice.  \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F1l4iKT7Cyv", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nHere are my main comments, mostly about the significance of the results.\nAlignment (Definition 2), itself, is a very restrictive assumption: it requires the left and right singular spaces of all consecutive layers to be aligned, i.e. V_{i+1} = U_{i}. In fact, the authors show in Theorem 3 that alignment cannot occur, for a large class of interesting architectures, including convolutional neural networks. Therefore, studying this notion is not well-motivated to begin with.\nAlignment being an invariant of training (Definition 3), is a far more stringent assumption, particularly because it requires the singular spaces of all hidden layers to remain fixed during the training. As it is shown in Theorem 1, this property holds if and only if the input and the output have the same right singular space. On the other hand, when this condition can be satisfied, e.g. for instances that are given in section 4.2, it is not clear if the analysis provides any additional insights/improvements over the previous works.\n\nSome additional comments:\nDefinition 3 requires interpolation under the linear model, i.e., the data is clean (no noise), and the relationship between the output and the input is completely characterized by a linear map, which makes the result less interesting from a practical view. While this setting is well-studied in the literature, this work does not provide comparisons against the previous works.\nMatrix Sensing in section 4.2: how can matrix sensing be an instance of a deep linear network with a multi-dimensional output? Both the labels y_i and the network predictions Tr(M_i^T W_d...W_1) are scalers, and hence 1-dimensional. \n\nTo sum up, the paper studies an extension of alignment [Ji and Telgarsky, 2018] to linear networks with multi-dimensional output. This notion is too stringent -- as the authors confirm in the paper -- and cannot be satisfied unless in some special cases. On the other hand, when the condition can be satisfied, it is not clear if the results provide any insights/improvements over the previous work. For these reasons, I vote for rejecting this submission.\n\n\n========================\nFinal Recommendation\n\nI have read the rebuttal and decided to keep my score. I think this study needs to be further motivated.\nI also want to clarify a minor issue in authors rebuttal. In contributions, you say: \"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...\". My point is that the matrix sensing problem that you study here has 1-dimensional output.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EVZePnIautM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI think this paper provides a nice necessary and sufficient condition for alignment in deep linear networks, which simplifies the training dynamic and let us prove a linear convergence rate. On the other hand, when the layer structure is constrained, it is shown that aligned networks in general cannot achieve zero training error, which is interesting. \n\nHowever, there are some weaknesses that should be noticed:\n1. As given by Definition 3, if alignment is an invariant of training, it only means that there exists a good initialization. To get a practical algorithm, we need to find such a good initialization, which seems nontrivial. For example, matrix factorization and inversion are mentioned as an example which satisfies the conditions of Theorem 1, but according to the proof of Theorem 1, to factorize or inverse a matrix M, we need to initialize the first and last weight matrices using an unsorted, signed singular value decomposition of M, which does not make sense. \n2. Theorem 1 requires the input dimension to be the same as the output dimension, and it only uses square layers, which I think means that each hidden width is also equal to the input dimension. This setting is pretty restrictive; for example, autoencoding is mentioned as an example of Theorem 1, but if the hidden widths are equal to the input dimension, then there seems to be no point to do such an encoding. On the other hand, Corollary 1 doesn't seem to need the hidden widths to be identical, which is inconsistent.\n\nAdditionally, the appendices should be provided. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The consensus view was that the reviewers were not convinced that the analysis done in the paper was sufficient motivated.
Decision: Reject