Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks

Introduction

Residual networks (He et al., 2016) are deep neural networks in which, roughly, subnetworks determine how a feature transformation should differ from the identity, rather than how it should differ from zero. After enabling the winning entry in the ILSVRC 2015 classification task, they have become established as a central idea in deep networks.

Hardt & Ma (2017) provided a theoretical analysis that shed light on residual networks. They showed that (a) any linear transformation with a positive determinant and a bounded condition number can be approximated by a “deep linear network” of the form $f(x)=\Theta_{L}\Theta_{L-1}...\Theta_{1}x$, where, for large $L$, each layer $\Theta_{i}$ is close to the identity, and (b) for networks that compose near-identity transformations this way, if the excess loss is large, then the gradient is steep. Bartlett et al. (2018) extended both results to the nonlinear case, showing that any smooth, bi-Lipschitz map can be represented as a composition of near-identity functions, and that a suboptimal loss in a composition of near-identity functions implies that the functional gradient of the loss with respect to a function in the composition cannot be small. These results are interesting because they suggest that, in many cases, this non-convex objective may be efficiently optimized through gradient descent if the layers stay close to the identity, possibly with the help of a regularizer.

This paper describes and analyzes such algorithms for linear regression with $d$ input variables and $d$ response variables with respect to the quadratic loss, the same setting analyzed by Hardt and Ma. We abstract away sampling issues by analyzing an algorithm that performs gradient descent with respect to the population loss. We focus on the case that the distribution on the input patterns is isotropic. (The data may be transformed through a preprocessing step to satisfy this constraint.)

The traditional analysis of convex optimization algorithms (see Boyd & Vandenberghe, 2004) provides a bound in terms of the quality of the initial solution, together with bounds on the eigenvalues of the Hessian of the loss. For the non-convex problem of this paper, we show that if gradient descent starts at the identity in each layer, and if the excess loss of that initial solution is bounded by a constant, then the Hessian remains well-conditioned enough throughout training for successful learning. Specifically, there is a constant $c_{0}$ such that, if the excess loss of the identity (over the least squares linear map) is at most $c_{0}$, then back-propagation initialized at the identity in each layer achieves loss within at most $\epsilon$ of optimal in time polynomial in $\log(1/\epsilon)$, $d$, and $L$ (Section 3). On the other hand, we show that there is a constant $c_{1}$ and a least squares matrix $\Phi$ such that the identity has excess loss $c_{1}$ with respect to $\Phi$, but backpropagation with identity initialization fails to learn $\Phi$ (Section 6).

We also show that if the least squares matrix $\Phi$ is symmetric positive definite then gradient descent with identity initialization achieves excess loss at most $\epsilon$ in a number of steps bounded by a polynomial in $\log(d/\epsilon)$, $L$ and the condition number of $\Phi$ (Section 4).

In contrast, for any least squares matrix $\Phi$ that is symmetric but has a negative eigenvalue, we show that no such guarantee is possible for a wide variety of algorithms of this type: the excess loss is forever bounded below by the square of this negative eigenvalue. This holds for step-and-project algorithms, and also algorithms that initialize to the identity and regularize by early stopping or penalizing $\sum_{i}||\Theta_{i}-I||_{F}^{2}$ (Section 6). Both this and the previous impossibility result can be proved using a least squares matrix $\Phi$ with a positive determinant and a good condition number. Recall that such $\Phi$ were proved by Hardt and Ma to have a good approximation as a product of near-identity matrices – we prove that gradient descent cannot learn them, even with the help of regularizers that reward near-identity representations.

In Section 5 we provide a convergence guarantee for a least squares matrix $\Phi$ that may not be symmetric, but satisfies the positivity condition $u^{\top}\Phi u>\gamma$ for some $\gamma>0$ that appears in the bounds. We call such matrices $\gamma$-positive. Such $\Phi$ include rotations by acute angles. In this case, we consider an algorithm that regularizes in addition to a near-identity initialization. After the gradient update, the algorithm performs what we call power projection, projecting its hypothesis $\Theta_{L}\Theta_{L-1}...\Theta_{1}$ onto the set of $\gamma$-positive matrices. Second, it “balances” $\Theta_{1},...,\Theta_{L}$ so that, informally, they contribute equally to $\Theta_{L}\Theta_{L-1}...\Theta_{1}$. (See Section 5 for the details.) We view this regularizer as a theoretically tractable proxy for regularizers that promote positivity and balance between layers by adding penalties.

While, in practice, deep networks are non-linear, analysis of the linear case can provide a tractable way to gain insight through rigorous theoretical analysis (Saxe et al., 2013; Kawaguchi, 2016; Hardt & Ma, 2017). We might view back-propagation in the non-linear case as an approximation to a procedure that locally modifies the function computed by each layer in a manner that reduces the loss as fast as possible. If a non-linear network is obtained by composing transformations, each of which is chosen from a Hilbert space of functions (as in Daniely et al. (2016)), then a step in “function space” corresponds to a step in an (infinite-dimensional) linear space of functions.

Related work. The motivation for this work comes from the papers of Hardt & Ma (2017) and Bartlett et al. (2018). Saxe et al. (2013) studied the dynamics of a continuous-time process obtained by taking the step size of backpropagation applied to deep linear neural networks to zero. Kawaguchi (2016) showed that deep linear neural networks have no suboptimal local minima. In the case that $L=2$, the problem studied here has a similar structure as problems arising from low-rank approximation of matrices, especially as regards algorithms that approximate a matrix $A$ by iteratively improving an approximation of the form $UV$. For an interesting survey on the rich literature on these algorithms, please see Ge et al. (2017a); successful algorithms have included a regularizer that promotes balance in the sizes of $U$ and $V$. Taghvaei et al. (2017) studied the properties of critical points on the loss when learning deep linear neural networks in the presence of a weight decay regularizer; they studied networks that transform the input to the output through a process indexed by a continuous variable, instead of through discrete layers. Lee et al. (2016) showed that, given regularity conditions, for a random initialization, gradient descent converges to a local minimizer almost surely; while their paper yields useful insights, their regularity condition does not hold for our problem. Many papers have analyzed learning of neural networks with non-linearities. The papers most closely related to this work analyze algorithms based on gradient descent. Some of these (Andoni et al., 2014; Brutzkus & Globerson, 2017; Ge et al., 2017b; Li & Yuan, 2017; Zhong et al., 2017; Zhang et al., 2018; Brutzkus et al., 2018; Ge et al., 2018) analyze constant-depth networks. Daniely (2017) showed that stochastic gradient descent learns a subclass of functions computed by log-depth networks in polynomial time; this class includes constant-degree polynomials with polynomially bounded coefficients. Other theoretical treatments of neural network learning algorithms include Lee et al. (1996); Arora et al. (2014); Livni et al. (2014); Janzamin et al. (2015); Safran & Shamir (2016); Zhang et al. (2016); Nguyen & Hein (2017); Zhang et al. (2017); Orhan & Pitkow (2018), although these are less closely related.

Our three upper bound analyses combine a new upper bound on the operator norm of the Hessian of a deep linear network with the result of Hardt and Ma that gradients are lower bounded in terms of the loss for near-identity matrices. They otherwise have different outlines. The bound in terms of the loss of the initial solution proceeds by showing that the distance from each layer to the identity grows slowly enough that the loss is reduced before the layers stray far enough to harm the conditioning of the Hessian. The bound for symmetric positive definite matrices proceeds by showing that, in this case, all of the layers are the same, and each of their eigenvalues converges to the $L$th root of a corresponding eigenvalue of $\Phi$. As mentioned above, the bound for $\gamma$-positive matrices $\Phi$ is for an algorithm that achieves favorable conditioning through regularization.

We expect that the theoretical analysis reported here will inform the design of practical algorithms for learning non-linear deep networks. One potential avenue for this arises from the fact that the leverage provided by regularizing toward the identity appears to already be provided by a weaker policy of promoting the property that the composition of layers is (potentially asymmetric) positive definite. Also, balancing singular values of the layers of the network aided our analysis; an analogous balancing of Jacobians associated with various layers may improve conditioning in practice in the non-linear case.

Preliminaries

We study algorithms that learn linear mappings parameterized by deep networks. The network with $L$ layers and parameters $\Theta=(\Theta_{1},\ldots,\Theta_{L})$ computes the parameterized function $f_{\Theta}(x)=\Theta_{L}\Theta_{L-1}\cdots\Theta_{1}x,$ where $x\in\Re^{d}$ and $\Theta_{i}\in\Re^{d\times d}$.

We use the notation $\Theta_{i:j}=\Theta_{j}\Theta_{j-1}\cdots\Theta_{i}$ for $i\leq j$, so that we can write $f_{\Theta}(x)=\Theta_{1:L}x=\Theta_{i+1:L}\Theta_{i}\Theta_{1:i-1}x.$

For $\gamma>0$, a matrix $A\in\Re^{d\times d}$ is $\gamma$-positive if, for all unit length $u$, we have $u^{\top}Au>\gamma$.

2 Tools and background

We use $||A||_{F}$ for the Frobenius norm of matrix $A$, $||A||_{2}$ for its operator norm, and $\sigma_{\min}(A)$ for its least singular value. For vector $v$, we use $||v||$ for its Euclidian norm.

For a matrix $A$ and a matrix-valued function $B$, define $D_{A}B(A)$ to be the matrix with

where $G$ is the $d\times d$ matrix given by

Targets near the identity

In this section, we prove an upper bound for gradient descent in terms of the loss of the initial solution.

First, set $\Theta^{(0)}=(I,I,...,I)$, and then iteratively update

2 Proof of Theorem 1

The following lemma, which is implicit in the proof of Theorem 2.2 in Hardt & Ma (2017), shows that the gradient is steep if the loss is large and the singular values of the layers are not too small.

Next, we show that, if $\Theta^{(t)}$ and $\Theta^{(t+1)}$ are both close to the identity, then the gradient is not changing very fast between them, so that rapid progress continues to be made. We prove this through an upper bound on the operator norm of the Hessian that holds uniformly over members of a ball around the identity, which in turn can be obtained through a bound on the Frobenius norm. The proof is in Appendix B.

Armed with Lemmas 2 and 3, let us now analyze gradient descent. Very roughly, our strategy will be to show that the distance from the identity to the various layers grows slowly enough for the leverage from Lemmas 2 and 3 to enable successful learning. Let ${\cal R}(\Theta)=\max_{i}||\Theta_{i}-I||_{2}$. From the update, we have

By Lemma 3, for all $\Theta$ on the line segment from $\Theta^{(t)}$ to $\Theta^{(t+1)}$, we have

Before starting the inductive step, notice that for any $t\geq 0$,

Since ${\cal R}(t+1)\leq\frac{\ln c}{L}$, the choice of $\eta$ satisfies (3), so

Symmetric positive definite targets

In this section, we analyze the procedure of Section 3.1 when the least squares matrix $\Phi$ is symmetric and positive definite.

Note that a symmetric matrix is $\gamma$-positive when its minimum eigenvalue is at least $\gamma$.

Let $\Phi$ be a symmetric, real, $\gamma$-positive matrix with $\gamma>0$, and let $\Theta^{(0)},\Theta^{(1)},...$ be the iterates of gradient descent with a step size $0<\eta\leq\frac{1}{L(1+||\Phi||_{2}^{2})}$.

Symmetric matrices ${\cal A}\subseteq\Re^{d\times d}$ are commuting normal matrices if there is a single unitary matrix $U$ such that for all $A\in{\cal A}$, $U^{\top}AU$ is diagonal.

We will use the following well-known facts about commuting normal matrices.

If ${\cal A}\subseteq\Re^{d\times d}$ is a set of symmetric commuting normal matrices and $A,B\in{\cal A}$, the following hold:

for all scalars $\alpha$ and $\beta$, ${\cal A}\cup\{\alpha A+\beta B,AB\}$ are commuting normal;

there is a unitary matrix $U$ such that $U^{\top}AU$ and $U^{\top}BU$ are real and diagonal;

the multiset of singular values of $A$ is the same as the multiset of magnitudes of its eigenvalues;

$||A-I||_{2}$ is the largest value of $|z-1|$ for an eigenvalue $z$ of $A$.

The proof is by induction. The base case follows from the fact that $\Phi$ and $I$ are commuting normal.

are commuting normal follows from Lemma 4. The update formula now reveals that $\Theta_{1}^{(t+1)}=...=\Theta_{L}^{(t+1)}.$ ∎

Now we are ready to analyze the dynamics of the learning process. Let $\Phi=U^{\top}D^{L}U$ be a diagonalization of $\Phi$. Let $\Gamma=\max\{1,||\Phi||_{2}\}$. We next describe a sense in which gradient descent learns each eigenvalue independently.

For each $t$, there is a real diagonal matrix $\hat{D}^{(t)}$ such that, for all $i$, $\Theta_{i}^{(t)}=U^{\top}\hat{D}^{(t)}U$ and

Lemma 5 implies that there is a single real $U$ such that $\Theta_{i}^{(t)}=U^{\top}\hat{D}^{(t)}U$ for all $i$. Applying Lemma 1, recalling that $\Theta_{1}^{(t)}=...=\Theta_{L}^{(t)}$, and applying the fact that $\Theta_{i}^{(t)}$ and $\Phi$ commute, we get

Replacing each matrix by its diagonalization, we get

and left-multiplying by $U$ and right-multiplying by $U^{\top}$ gives (5). ∎

We will now analyze the convergence of each $\hat{D}_{kk}^{(t)}$ to $D_{kk}$ separately. Let us focus for now on an arbitrary single index $k$, let $\lambda=D_{kk}$ and $\hat{\lambda}^{(t)}=\hat{D}_{kk}^{(t)}$.

Recalling that $||\Phi||_{2}\leq\Gamma$, we have $\gamma^{1/L}\leq\lambda\leq\Gamma^{1/L}.$ Also, $\Gamma^{1/L}=e^{\frac{1}{L}\ln\Gamma}\leq e^{1/a}\leq 1+2/a$ whenever $a\geq 1$ and $L\geq a\ln\Gamma$. Similarly, $\gamma^{1/L}\geq 1-a$ whenever $L\geq a\ln(1/\gamma)$. Thus, there are absolute constants $c_{3}$ and $c_{4}$ such that $|1-\lambda|\leq\frac{c_{4}\ln(\Gamma/\gamma)}{L}<1$ for all $L\geq c_{3}\ln(\Gamma/\gamma)$.

We claim that, for all $t$, $\hat{\lambda}^{(t)}$ lies between $1$ and $\lambda$ inclusive, so that $|\hat{\lambda}^{(t)}-\lambda|\leq\frac{c_{4}\ln(\Gamma/\gamma)}{L}$. The base case holds because $\hat{\lambda}^{(t)}=1$ and $|1-\lambda|\leq\frac{c_{4}\ln(\Gamma/\gamma)}{L}$. Now let us work on the induction step. Applying (5) together with Lemma 1, we get

We have proved that each $\hat{\lambda}^{(t)}$ lies between $\lambda$ and $1$, so that $|1-\hat{\lambda}^{(t)}|\leq|1-\lambda|\leq c_{4}\ln(\Gamma/\gamma)$.

Now, since the step is in the right direction, and does not overshoot,

since the fact that $\hat{\lambda}^{(t)}$ lies between $1$ and $\lambda$ implies that $\hat{\lambda}^{(t)}\geq\gamma^{1/L}$. Thus, $|\hat{\lambda}^{(t)}-\lambda|\leq\left(1-\eta L\gamma^{2}\right)^{t}c_{4}\ln(\Gamma/\gamma)$. This implies that, for any $\epsilon\in(0,1)$, for any absolute constant $c_{5}$, there is a constant $c_{6}$ such that, after $c_{6}\frac{1}{\eta L\gamma^{2}}\ln\left(\frac{dL\ln\Gamma}{\gamma\epsilon}\right)$ steps, we have $|\hat{\lambda}^{(t)}-\lambda|\leq\frac{c_{5}\gamma\sqrt{\epsilon}}{L\Gamma\sqrt{d}}.$ Writing $r=\hat{\lambda}^{(t)}-\lambda$, this implies, if $c_{5}$ is small enough, that

Asymmetric positive definite matrices

We have seen that if the least squares matrix is symmetric, $\gamma$-positivity is sufficient for convergence of gradient descent. We shall see in Section 6 that positivity is also necessary for a broad family of gradient-based algorithms to converge to the optimal solution when the least squares matrix is symmetric. Thus, in the symmetric case, positivity characterizes the success of gradient methods. In this section, we show that positivity suffices for the convergence of a gradient method even without the assumption that the least squares matrix is symmetric.

Note that the set of $\gamma$-positive (but not necessarily symmetric) matrices includes both rotations by an acute angle and “partial reflections” of the form $ax+b\text{ refl}(x)$ where $\text{refl}(\cdot)$ is a length-preserving reflection and $0\leq|b|<a$. Since $\left(u^{\top}Au\right)^{\top}=u^{\top}A^{\top}u$, a matrix $A$ is $\gamma$-positive if and only if $u^{\top}(A+A^{\top})u\geq 2\gamma$ for all unit length $u$, i.e. $A+A^{\top}$ is positive definite with eigenvalues at least $2\gamma$.

The algorithm analyzed in this section uses a construction that is new, as far as we know, that we call a balanced factorization. This factorization may be of independent interest.

Recall that a polar decomposition of a matrix $A$ consists of a unitary matrix $R$ and a positive semidefinite matrix $P$ such that $A=RP$. The principal $L$th root of a complex number whose expression in polar coordinates is $re^{\theta i}$ is $r^{1/L}e^{\theta i/L}$. The principal $L$th root of a matrix $A$ is the matrix $B$ such that $B^{L}=A$, and each eigenvalue of $B$ is the principal $L$th root of the corresponding eigenvalue of $A$.

If $A$ be a matrix with polar decomposition $RP$, then $A$ has the balanced factorization $A=A_{1},...,A_{L}$ where for each $i$,

and each of the $L$th roots is the principal $L$th root.

The motivation for balanced factorization is as follows. We want each factor to do a $1/L$ fraction of the total amount of rotation, and a $1/L$ fraction of the total amount of scaling. However, the scaling done by the $i$th factor should be done in directions that take account of the partial rotations done by the other factors. The following is the key property of the balanced factorization; its proof is in Appendix C.

If $\sigma_{1},...,\sigma_{d}$ are the singular values of $A$, and $A_{1},...,A_{L}$ is a balanced factorization of $A$, then the following hold: (a) $A=\prod_{i=1}^{L}A_{i}$; (b) for each $i\in\{1,...,L\}$, $\sigma_{1}^{1/L},...,\sigma_{d}^{1/L}$ are the singular values of $A_{i}$.

2 Procedure and upper bound

The following is the power projection algorithm. It has a positivity parameter $\gamma>0$, and uses ${\cal H}=\{A:\forall u\mbox{ s.t. }||u||=1,\;u^{\top}Au\geq\gamma\}$ as its “hypothesis space”. First, it initializes $\Theta_{i}^{(0)}=\gamma^{1/L}I$ for all $i\in\{1,...,L\}$. Then, for each $t$, it does the following.

Gradient Step. For each $i\in\{1,...,L\}$, update:

Power Project. Compute the projection $\Psi^{(t+1/2)}$ (w.r.t. the Frobenius norm) of $\Theta_{1:L}^{(t+1/2)}$ onto ${\cal H}$.

Factor. Let $\Theta_{1}^{(t+1)},...,\Theta_{L}^{(t+1)}$ be the balanced factorization of $\Psi^{(t+1/2)}$, so that $\Psi^{(t+1/2)}=\Theta_{1:L}^{(t+1)}$.

3 Proof of Theorem 3

For all $t$, $\Theta_{1:L}^{(t)}\in{\cal H}$.

$\Theta_{1:L}^{(0)}=\gamma I\in{\cal H}$, and, for all $t$, $\Psi^{(t+1/2)}$ is obtained by projection onto ${\cal H}$, and $\Theta_{1:L}^{(t+1)}=\Psi^{(t+1/2)}$. ∎

The exponential of a matrix $A$ is $\exp(A)\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{k=0}^{\infty}\frac{1}{k!}A^{k}$, and $B$ is a logarithm of $A$ if $A=\exp(B)$.

A real matrix has a real logarithm if and only if it is invertible and each Jordan block belonging to a negative eigenvalue occurs an even number of times.

For all $t$, $\Theta_{1:L}^{(t)}$ has a real $L$th root.

Since $\Theta_{1:L}^{(t)}\in{\cal H}$ implies $u^{\top}\Theta_{1:L}^{(t)}u>0$ for all $u$, $\Theta_{1:L}^{(t)}$ does not have a negative eigenvalue and is invertible. By Lemma 9, $\Theta_{1:L}^{(t)}$ has a real logarithm. Thus, its real $L$th root can be constructed via $\exp(\log(\Theta_{1:L}^{(t)})/L)$. ∎

The preceding lemma implies that the algorithm is well-defined, since all of the required roots can be calculated.

Suppose $A$ and $B$ are in $H$ and $\lambda\in(0,1)$. We have

For all $A\in{\cal H}$, $\sigma_{\min}(A)\geq\gamma$.

Let $u$ and $v$ be singular vectors such that $u^{\top}Av=\sigma_{\min}(A)$.

For all $t$, $\sigma_{\min}(\Theta_{i}^{(t)})\geq\gamma^{1/L}.$

First, $\sigma_{\min}(\Theta_{i}^{(0)})=\gamma^{1/L}\geq\gamma^{1/L}$.

Now consider $t>0$. Since $\Psi^{(t-1/2)}$ was projected into ${\cal H}$, we have $\sigma_{\min}(\Psi^{(t-1/2)})\geq\gamma$. Lemma 7 then completes the proof. ∎

Arguing as in the initial portion of Section 3.2, as long as

Failure

In this section, we show that positive definite $\Phi$ are necessary for several gradient descent algorithms with different kinds of regularization to minimize the loss. One family of algorithms that we will analyze is parameterized by a function $\psi$ mapping the number of inputs $d$ and the number of layers $L$ to a radius $\psi(d,L)$, step sizes $\eta_{t}$ and initialization parameter $\gamma\geq 0$. In particular, a $\psi$-step-and-project algorithm is any instantiation of the following algorithmic template.

Initialize each $\Theta_{i}^{(0)}=\gamma^{1/L}I$ for some $\gamma\geq 0$ and iterate:

Gradient Step. For each $i\in\{1,...,L\}$, update:

Project. Set each $\Theta_{i}^{t+1}$ to the projection of $\Theta_{i}^{t+1/2}$ onto $\{A:||A-I||_{2}\leq\psi(d,L)\}$.

Both results use the simple observation that when $\Theta_{1:L}$ and $\Phi$ are mutually diagonalizable then

where the $D_{ii}$ are the eigenvalues of $\Phi$.

If the least squares matrix $\Phi$ is symmetric then Penalty Regularized Gradient Descent produces hypotheses $\Theta^{(t)}_{1:L}$ that are commuting normal with $\Phi$.

To analyze step-and-project algorithms, it is helpful to first characterize the project step (see also (Lefkimmiatis et al., 2013)).

Let $X$ be a symmetric matrix and let $U^{\top}DU$ be its diagonalization.

Thus $\{X,Y\}$ are symmetric commuting normal matrices.

First, if $X\in{\cal B}_{a}$, then $Y=X$ and we are done.

Let $Z$ be an arbitrary member of ${\cal B}_{a}$. We would like to show that $||Z-X||_{F}^{2}\geq\sum_{\lambda\in\Lambda}e_{\lambda}^{2}.$ Since $Z\in{\cal B}_{a}$, we have $||Z-I||_{2}\leq a$. $||Z-I||_{2}$ is the largest singular value of $Z-I$ so, for any unit length vector, in particular some $u_{\lambda}$ for $\lambda\in\Lambda$, $|u_{\lambda}^{\top}(Z-I)u_{\lambda}|=|u_{\lambda}^{\top}Zu_{\lambda}-1|\leq a$, which implies $u_{\lambda}^{\top}Zu_{\lambda}\in[1-a,1+a]$. Since $U$ is unitary $U^{\top}(X-Z)U$ has the same eigenvalues as $X-Z$, and, since the Frobenius norm is a function of the eigenvalues, $||U^{\top}(X-Z)U||_{F}=||X-Z||_{F}$. But since $u_{\lambda}^{\top}Zu_{\lambda}\in[1-a,1+a]$ for all $\lambda\in\Lambda$, just summing over the diagonal elements, we get $||U^{\top}(X-Z)U||_{F}^{2}\geq\sum_{\lambda\in\Lambda}e_{\lambda}^{2}$, completing the proof. ∎

If the least squares matrix $\Phi$ is symmetric then $\psi$-step-and-project algorithms produce hypotheses $\Theta^{(t)}_{1:L}$ that are commuting normal with $\Phi$.

Our proof of failure to minimize the loss exploits the fact that the layers are initialized to multiples of the identity. Since the training process is a continuous function of the initial solution, this implies that any convergence to a good solution will be very slow if the initializations are sufficiently close to the identity.

Acknowledgements

We thank Yair Carmon, Nigel Duffy, Matt Feiszli, Roy Frostig, Vineet Gupta, Moritz Hardt, Tomer Koren, Antoine Saliou, Hanie Sedghi, Yoram Singer and Kunal Talwar for valuable conversations.

Peter Bartlett gratefully acknowledges the support of the NSF through grant IIS-1619362 and of the Australian Research Council through an Australian Laureate Fellowship (FL110100281) and through the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS).

References

Appendix A Proof of Lemma 1

We rely on the following facts (Horn, 1986; Harville, 1997).

For compatible matrices (and, where $m,n,p,q,r,s$ are mentioned, $A\in\Re^{m\times n}$, $B\in\Re^{p\times q}$, $X\in\Re^{r\times s}$):

Armed with Lemma 16, we now prove Lemma 1. We have

Define $P=\Theta_{1:j-1}x$ and $Q=\Theta_{j+1:L}$, so that $P\in\Re^{d\times 1}$ and $Q\in\Re^{d\times d}$. We have

The product rule in Lemma 16 gives, for each $i$,

Appendix B Proof of Lemma 3

Let’s start with the easier term. Choose $\Theta$ such that $||\Theta_{i}-I||_{2}\leq z$ for all $i$. We have

Putting these together with (10), we get $||\nabla^{2}||_{F}^{2}\leq L^{2}9d^{10}(1+z)^{4L},$ so that

Appendix C Proof of Lemma 7

Recall that a polar decomposition of a matrix $A$ consists of a unitary matrix $R$ and a positive semidefinite matrix $P$ such that $A=RP$.

$A$ is a unitary matrix if and only if all of the (complex) eigenvalues $z$ of $A$ have magnitude $1$.

If $A$ is normal with eigenvalues $\lambda_{1},...,\lambda_{d}$, the singular values of $A$ are $|\lambda_{1}|,...,|\lambda_{d}|$.

If $A$ is unitary, then $A^{1/L}$ is unitary, and thus $A^{i/L}$ is unitary for any non-negative integer $i$.

If $A$ is invertible and normal with singular values $\sigma_{1},...,\sigma_{d}$, then, for any positive integer $L$, the singular values of $A^{1/L}$ are $\sigma_{1}^{1/L},...,\sigma_{d}^{1/L}$.

Follows from Lemma 19 together with the fact that raising a non-singular matrix to a power results in raising its eigenvalues to the same power. ∎

If $A=RP$ is the polar decomposition of $A$, then the singular values of $A$ are the same as the singular values of $P$.

If $\sigma_{1},...,\sigma_{d}$ are the principal components of $A$, and $A=\prod_{i=1}^{L}A_{i}$ is a balanced factorization of $A$, then then $\sigma_{1}^{1/L},...,\sigma_{d}^{1/L}$ are the principal components of $A_{i}$, for each $i\in\{1,...,L\}$.

The singular values of $A_{i}=R_{i}P_{i}$ are the same as the singular values of $P_{i}$, which is similar to $P^{1/L}$, whose singular values are the $L$th roots of the singular values of $P$, which are the same as the singular values of $A$. ∎

If $A_{1},...,A_{L}$ is a balanced factorization of $A$, then