1

Gradient descent with identity initialization
efficiently learns
positive definite linear transformations
by deep residual networks
Peter L. Bartlett1 , David P. Helmbold2 and Philip M. Long3
1 UC Berkeley 2 UC Santa Cruz 3 Google
Keywords: Residual networks, optimization, deep networks, gradient descent.

Abstract
We analyze algorithms for approximating a function f (x) = Φx mapping <d to <dusing deep linear neural networks, i.e. that learn a function h parameterized by matrices
Θ1 , ..., ΘL and defined by h(x) = ΘL ΘL−1 ...Θ1 x. We focus on algorithms that learn
through gradient descent on the population quadratic loss in the case that the distribution
over the inputs is isotropic. We provide polynomial bounds on the number of iterations
for gradient descent to approximate the least squares matrix Φ, in the case where theinitial hypothesis Θ1 = ... = ΘL = I has excess loss bounded by a small enoughconstant. On the other hand, we show that gradient descent fails to converge for Φ
whose distance from the identity is a larger constant, and we show that some forms ofregularization toward the identity in each layer do not help. If Φ is symmetric positive
definite, we show that an algorithm that initializes Θi = I learns an -approximation off using a number of updates polynomial in L, the condition number of Φ, and log(d/).
In contrast, we show that if the least squares matrix Φ is symmetric and has a negative
eigenvalue, then all members of a class of algorithms that perform gradient descent withidentity initialization, and optionally regularize toward the identity in each layer, fail toconverge. We analyze an algorithm for the case that Φ satisfies u> Φu > 0 for all u,
but may not be symmetric. This algorithm uses two regularizers: one that maintains theinvariant u> ΘL ΘL−1 ...Θ1 u > 0 for all u, and another that “balances” Θ1 , ..., ΘL so thatthey have the same singular values.

1Introduction

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 and 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 theform f (x) = ΘL ΘL−1 ...Θ1 x, where, for large L, each layer Θ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. (2018a) extended both results tothe 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 compositionof 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 helpof 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 casethat 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 and 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 problemof 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 c0 such that, if the excess loss of the identity (over the least squares linear map) is at most c0 , then back-propagation initialized at the identity in each layer
achieves loss within at most  of optimal in time polynomial in log(1/), d, and L (Section 3). On the other hand, we show that there is a constant c1 and a least squares matrix
Φ such that the identity has excess loss c1 with respect to Φ, but backpropagation withidentity initialization fails to learn Φ (Section 6).
We also show that if the least squares matrix Φ is symmetric positive definite thengradient descent with identity initialization achieves excess loss at most  in a number of steps bounded by a polynomial in log(d/), L and the condition number of Φ
(Section 4).
In contrast, for any least squares matrix Φ that is symmetric but has a negative
eigenvalue, we show that no such guarantee is possible for a wide variety of algorithmsof 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 ini2

P
tialize to the identity and regularize by early stopping or penalizing i ||Θi − I||2F(Section 6). Both this and the previous impossibility result can be proved using a leastsquares matrix Φ with a positive determinant and a good condition number. Recall thatsuch Φ were proved by Hardt and Ma to have a good approximation as a product ofnear-identity matrices – we prove that gradient descent cannot learn them, even withthe help of regularizers that reward near-identity representations.
In Section 5 we provide a convergence guarantee for a least squares matrix Φ that
may not be symmetric, but satisfies the positivity condition u> Φu > γ for some γ > 0that appears in the bounds. We call such matrices γ-positive. Such Φ include rotations
by acute angles. In this case, we consider an algorithm that regularizes in addition to anear-identity initialization. After the gradient update, the algorithm performs what wecall power projection, projecting its hypothesis ΘL ΘL−1 ...Θ1 onto the set of γ-positive
matrices. Second, it “balances” Θ1 , ..., ΘL so that, informally, they contribute equally toΘL ΘL−1 ...Θ1 . (See Section 5 for the details.) We view this regularizer as a theoreticallytractable proxy for regularizers that promote positivity and balance between layers byadding penalties.
While, in practice, deep networks are non-linear, analysis of the linear case canprovide a tractable way to gain insight through rigorous theoretical analysis (Saxe et al.,2013; Kawaguchi, 2016; Hardt and 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 nonlinear network is obtained by composing transformations, each of which is chosen froma Hilbert space of functions, 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 andMa (2017) and Bartlett et al. (2018a). After the publication of this work in preliminary form (Bartlett et al., 2018b), Shamir (2018) proved that convergence can be exponentially slow even when the layers of the initial solution are not exactly equal tothe identity, but only close; he also analyzed more general loss functions and otherinitialization schemes. Saxe et al. (2013) studied the dynamics of a continuous-timeprocess obtained by taking the step size of backpropagation applied to deep linear neural networks to zero. Kawaguchi (2016) showed that deep linear neural networks haveno suboptimal local minima. In the case that L = 2, the problem studied here hasa 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 U V . For an interesting survey on the rich literature onthese algorithms, please see Ge et al. (2017a); successful algorithms have included aregularizer that promotes balance in the sizes of U and V . Jain et al. (2017) analyzed
approximation of the matrix square root of a symmetric positive definite matrix A by
gradient descent, providing a simple analysis when the initial solution is a rescaling of
the identity, and a more involved analysis that applies for any well-conditioned initialsolution. Taghvaei et al. (2017) studied the properties of critical points on the loss whenlearning deep linear neural networks in the presence of a weight decay regularizer; theystudied networks that transform the input to the output through a process indexed by acontinuous variable, instead of through discrete layers. Lee et al. (2016) showed that,given regularity conditions, for a random initialization, gradient descent converges to a3

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 neuralnetworks 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 andGloberson, 2017; Ge et al., 2017b; Li and 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 computedby log-depth networks in polynomial time; this class includes constant-degree polynomials with polynomially bounded coefficients. Other theoretical treatments of neuralnetwork learning algorithms include Lee et al. (1996); Arora et al. (2014); Livni et al.
(2014); Janzamin et al. (2015); Safran and Shamir (2016); Zhang et al. (2016); Nguyen
and Hein (2017); Zhang et al. (2017); Orhan and Pitkow (2018), although these are lessclosely related.
Our three upper bound analyses combine a new upper bound on the operator normof the Hessian of a deep linear network with the result of Hardt and Ma that gradientsare lower bounded in terms of the loss for near-identity matrices. They otherwise havedifferent outlines. The bound in terms of the loss of the initial solution proceeds byshowing that the distance from each layer to the identity grows slowly enough thatthe 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 tothe Lth root of a corresponding eigenvalue of Φ. As mentioned above, the bound for
γ-positive matrices Φ is for an algorithm that achieves favorable conditioning throughregularization.
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 thisarises 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 thecomposition 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.

2

Preliminaries

2.1

Setting

For a joint distribution P with support contained in <d × <d and g : <d → <d , define`P (g) = E(X,Y )∼P (||g(X) − Y ||2 /2). We focus on the case that, for (X, Y ) drawn fromP , the marginal on X is isotropic, with EX = 0 and EXX > = Id . For convenience, we
assume that Y = ΦX for Φ ∈ <d×d . This assumption is without loss of generality: if Φis the least squares matrix (so that f defined by f (X) = ΦX minimizes `P (f ) among4

linear functions), for any linear g we have
`P (g) = Ekg(X) − f (X)k2 /2 + Ekf (X) − Y k2 /2+ E ((g(X) − f (X))(f (X) − Y ))= Ekg(X) − f (X)k2 /2 + Ekf (X) − Y k2 /2= Ekg(X) − ΦXk2 /2 + EkΦX − Y k2 /2,
since f is the projection of Y onto the set of linear functions of X. So assuming Y =ΦX corresponds to setting Φ as the least squares matrix and replacing the loss `P (g) by
the excess loss
Ekg(X) − ΦXk2 /2 = Ekg(X) − Y k2 /2 − EkΦX − Y k2 /2.
We study algorithms that learn linear mappings parameterized by deep networks.
The network with L layers and parameters Θ = (Θ1 , . . . , ΘL ) computes the parameterized function fΘ (x) = ΘL ΘL−1 · · · Θ1 x, where x ∈ <d and Θi ∈ <d×d .
We use the notation Θi:j = Θj Θj−1 · · · Θi for i ≤ j, so that we can write fΘ (x) =Θ1:L x = Θi+1:L Θi Θ1:i−1 x.
When there is no possibility of confusion, we will sometimes refer to loss `(fΘ )simply as `(Θ). Because the distribution of X is isotropic, `(Θ) = 21 ||Θ1:L − Φ||2F withrespect to the least squares matrix Φ. When Θ is produced by an iterative algorithm, we
will also refer to the loss of the tth iterate by `(t).
Definition 1. For γ > 0, a matrix A ∈ <d×d is γ-positive if, for all unit length u, wehave u> Au > γ.

2.2

Tools and backgroundWe use ||A||F for the Frobenius norm of matrix A, ||A||2 for its operator norm, andσmin (A) for its least singular value. For vector v, we use ||v|| for its Euclidean norm.
For a matrix A and a matrix-valued function B, define DA B(A) to be the matrix
with∂vec(B(A))i,(DA B(A))i,j =∂vec(A)jwhere vec(A) is the column vector constructed by stacking the columns of A. We use
Td,d to denote the d2 ×d2 permutation matrix mapping vec(A) to vec(A> ) for A ∈ <d×d .
For A ∈ <n×m and B ∈ <p×q , A⊗B denotes the Kronecker product, that is, the np×mq
matrix of n × m blocks, with the i, jth block given by Aij B.
We will need the gradient and Hessian of `. (The gradient, which can be computed
using backpropagation, is of course well known.) The proof is in Appendix A.
Lemma 1.
DΘi ` (fΘ ) = (vec(Id ))>>Θ>1:i−1 ⊗ (Θ1:L −Φ) Θi+1:L= vec(G)> ,5where G is the d × d matrix given bydef>
G = Θ>
i+1:L (Θ1:L − Φ) Θ1:i−1 .

(1)

For i < j,DΘj DΘi ` (fΘ ) = (Id2 ⊗ (vec(Id ))> ) (Id ⊗ Td,d ⊗ Id ) vec(Θ>1:i−1 ) ⊗ Id2



>
>
>
((Θ>
i+1:L Θj+1:L ⊗ Θ1:j−1 )Td,d + (Θi+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L )).

DΘi DΘi ` (fΘ ) = (Id2 ⊗ (vec(Id ))> ) (Id ⊗ Td,d ⊗ Id ) vec(Θ>1:i−1 ) ⊗ Id2

>
Θ
⊗
Θ
Θ>
i+1:L
1:i−1 Td,d .
i+1:L

3

Targets near the identity

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

3.1

Procedure and upper boundFirst, set Θ(0) = (I, I, ..., I), and then iteratively update


(t+1)
(t)
(t)
(t)
(t)
>
Θi
= Θi − η(Θi+1:L ) Θ1:L − Φ (Θ1:i−1 )> .
Theorem 1. There are positive constants c1 and c2 and polynomials p1 and p2 such that,(0)
if `(Θ1:L ) ≤ c1 , L ≥ c2 , and η ≤ 1/p1 (L, d, ||Φ||2 ), then the above gradient descentprocedure achieves `(fΘ(t) ) ≤  within t = p2 (1/η) ln (`(0)/) iterations.

3.2

Proof of Theorem 1

The following lemma, which is implicit in the proof of Theorem 2.2 in Hardt and Ma(2017), shows that the gradient is steep if the loss is large and the singular values of thelayers are not too small.
Lemma 2 (Hardt and Ma 2017). Let ∇Θ `(Θ) be the gradient of `(Θ) with respect
to any flattening of Θ. If, for all layers i, σmin (Θi ) ≥ 1 − a, then ||∇Θ `(Θ)||2 ≥4`(Θ)L(1 − a)2L .
Next, we show that, if Θ(t) and Θ(t+1) are both close to the identity, then the gradientis 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.
Lemma 3. Choose an arbitrary Θ with ||Θi ||2 ≤ 1 + z for all i, and least squares
matrix Φ with ||Φ||2 ≤ (1 + z)L . Let ∇2 be the Hessian of `(fΘ ) with respect to anarbitrary flattening of the parameters of Θ. We have||∇2 ||F ≤ 3Ld5 (1 + z)2L .
6

Armed with Lemmas 2 and 3, let us now analyze gradient descent. Very roughly, ourstrategy 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
R(Θ) = maxi ||Θi − I||2 . From the update, we have


(t+1)
(t)
(t)
(t)
(t)
||Θi
− I||2 ≤ ||Θi − I||2 + η||(Θi+1:L )> Θ1:L − Φ (Θ1:i−1 )> ||2
(t)

(t)

(t)

(t)

≤ ||Θi − I||2 + η(1 + R(Θ(t) ))L ||Θ1:L − Φ||2
≤ ||Θi − I||2 + η(1 + R(Θ(t) ))L ||Θ1:L − Φ||F .
(t)

If R(t) = maxs≤t R(Θ(s) ) (so R(0) = 0) and `(t) = 21 ||Θ1:L − Φ||2F , this impliespR(t + 1) ≤ R(t) + η(1 + R(t))L 2`(t).

(2)

By Lemma 3, for all Θ on the line segment from Θ(t) to Θ(t+1) , we have||∇2Θ ||2 ≤ ||∇2Θ ||F ≤ 3Ld5 max{(1 + R(t + 1))2L , ||Φ||22 },so that3`(t + 1) ≤ `(t) − η||∇Θ(t) ||2 + η 2 Ld5 max{(1 + R(t + 1))2L , ||Φ||22 }||∇Θ(t) ||2 .
2Thus, if we ensureη≤1
3Ld5 max{(1 + R(t + 1))2L , ||Φ||22 },(3)

we have `(t + 1) ≤ `(t) − (η/2)||∇Θ(t) ||2 , which, if R(t) ≤ 1, using Lemma 2, gives`(t + 1) ≤ 1 − 2ηL(1 − R(t))2L `(t).
(4)
(0)

2

Pick any c ≥ 1. Assume that L ≥ (4/3) ln c = c2 , `(Θ1:L ) ≤ ln(c)= c1 and8c101
η ≤ 3Ld5 max{c4 ,||Φ||2 } . We claim that, for all t ≥ 0,2p
P
1. R(t) ≤ ηc 2`(0) 0≤s<t exp − sηL,c4
2. `(t) ≤ exp − 2tηL
`(0).
4
c
The base case holds as R(0) = 0 and `(0) = `(0).
Before starting the inductive step, notice that for any t ≥ 0,


X
p
p
sηL
1

ηc 2`(0)≤ ηc 2`(0) ×
exp − 4c
1 − exp − ηL
c4
0≤s<t
p
2c4
≤ ηc 2`(0) ×ηLp52c 2`(0)ln c=≤≤ 3/4,
LL
7(since ηL≤ 1)c4

where the last two inequalities follow from the constraints on `(0) and L.
Using (2),pR(t + 1) ≤ R(t) + η(1 + R(t))L 2`(t)

L
p
ln c
2`(t)
≤ R(t) + η 1 +Lp≤ R(t) + ηc 2`(t)


p
tηL
≤ R(t) + ηc 2`(0) exp − 4
c


X
p
sηL
≤ ηc 2`(0)
exp − 4 .
c0≤s<t+1
Since R(t + 1) ≤ lnLc < 1, the choice of η satisfies (3), and so`(t + 1) ≤ 1 − 2ηL(1 − R(t))2L `(t).
Now consider (1 − R(t))2L :ln (1 − R(t))2L = 2L ln(1 − R(t))≥ 2L(−2R(t))
ln c≥ 2L −2L(1 − R(t))2L ≥ 1/c4 .

since R(t) ∈ [0, 3/4]
ln csince R(t) ≤L

Using this in the bound on `(t + 1):
`(t + 1) ≤ 1 − 2ηL(1 − R(t))2L `(t)2ηL
≤ 1 − 4 `(t)
c


 


2ηL
2tηL
≤ exp − 4
exp − 4
`(0)
c
c



2(t + 1)ηL`(0).
= exp −c4
Solving `(0) exp − 2tηL≤  for t and recalling that η < 1/c4 completes the proof
4
cof the theorem.

4Symmetric positive definite targets

In this section, we analyze the procedure of Section 3.1 when the least squares matrix
Φ is symmetric and positive definite.
Theorem 2. There is an absolute positive constant c3 such that, if Φ is symmetric and1γ-positive with 0 < γ < 1, and L ≥ c3 ln (||Φ||2 /γ), then for all η ≤ L(1+||Φ||2) ,2
gradient descent achieves `(fΘ(t) ) ≤  in poly(L, ||Φ||2 /γ, 1/η) log(d/) iterations.
Note that a symmetric matrix is γ-positive when its minimum eigenvalue is atleast γ.
8

4.1

Proof of Theorem 2

Let Φ be a symmetric, real, γ-positive matrix with γ > 0, and let Θ(0) , Θ(1) , ... be the1iterates of gradient descent with a step size 0 < η ≤ L(1+||Φ||2) .
2

Definition 2. Symmetric matrices A ⊆ <d×d are commuting normal matrices if there
is a unitary matrix U such that for all A ∈ A, U > AU is diagonal.
We will use the following well-known facts about commuting normal matrices.
Lemma 4 (Horn and Johnson 2013). If A ⊆ <d×d is a set of symmetric commuting
normal matrices and A, B ∈ A, the following hold:• AB = BA;• for all scalars α and β, A ∪ {αA + βB, AB} are commuting normal;• there is a unitary matrix U such that U > AU and U > 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.
(t)

Lemma 5. The matrices {Φ} ∪ {Θi : i ∈ {1, ..., L}, t ∈ Z+ } are commuting normal.
(t)(t)
For all t, Θ1 = ... = ΘL .
Proof. The proof is by induction. The base case follows from the fact that Φ and I arecommuting normal.
For the induction step, the fact that
n
o n
o
(s)
(s+1)
{Φ} ∪ Θi : i ∈ {1, ..., L}, s ≤ t ∪ Θi
: i ∈ {1, ..., L}, s ≤ t
are commuting normal follows from Lemma 4. The update formula now reveals that
(t+1)
(t+1)
Θ1
= ... = ΘL .
Now we are ready to analyze the dynamics of the learning process. Let Φ =U > DL U be a diagonalization of Φ. Let Γ = max{1, ||Φ||2 }. We next describe a sensein which gradient descent learns each eigenvalue independently.
(t)Lemma 6. For each t, there is a real diagonal matrix D̂(t) such that, for all i, Θi =U > D̂(t) U andD̂(t+1) = D̂(t) − η(D̂(t) )L−1 ((D̂(t) )L − DL ).
(5)(t)

Proof. Lemma 5 implies that there is a real unitary matrix U such that for all i, Θi =(t)(t)
U > D̂(t) U . Applying Lemma 1, recalling that Θ1 = ... = ΘL , and applying the fact(t)that Θi and Φ commute, we get


(t+1)
(t)
(t) L−1(t) LΘi= Θi − η(Θi )(Θi ) − Φ .
9Replacing each matrix by its diagonalization, we get
U > D̂(t+1) U = U > D̂(t) U − η(U > (D̂(t) )L−1 U ) U > (D̂(t) )L U − U > DL U


> (t)
>
(t) L−1(t) LL= U D̂ U − ηU (D̂ )(D̂ ) − D U,
and left-multiplying by U and right-multiplying by U > gives (5).
(t)

We will now analyze the convergence of each D̂kk to Dkk separately. Let us focus(t)
for now on an arbitrary single index k, let λ = Dkk and λ̂(t) = D̂kk .
1
Recalling that ||Φ||2 ≤ Γ, we have γ 1/L ≤ λ ≤ Γ1/L . Also, Γ1/L = e L ln Γ ≤ e1/a ≤1 + 2/a whenever a ≥ 1 and L ≥ a ln Γ. Similarly, γ 1/L ≥ 1 − a whenever L ≥a ln(1/γ). Thus, there are absolute constants c3 and c4 such that |1 − λ| ≤ c4 ln(Γ/γ)<1L
for all L ≥ c3 ln(Γ/γ).
We claim that, for all t, λ̂(t) lies between 1 and λ inclusive, so that |λ̂(t) − λ| ≤c4 ln(Γ/γ). The base case holds because λ̂(t) = 1 and |1 − λ| ≤ c4 ln(Γ/γ). Now let us
L
L
work on the induction step. Applying (5) together with Lemma 1, we getλ̂(t+1) = λ̂(t) + η(λ̂(t) )L−1 (λL − (λ̂(t) )L ).

(6)

By the induction hypothesis, we just need to show that sign(λ̂(t+1) − λ̂(t) ) = sign(λ −λ̂(t) ) and |λ̂(t+1) − λ̂(t) | ≤ |λ − λ̂(t) | (i.e., the step is in the correct direction, and does not“overshoot”). First, to see that the step is in the right direction, note that λL ≥ (λ̂(t) )Lif and only if λ ≥ (λ̂(t) ), and the inductive hypothesis implies that λ̂(t) , and therefore(λ̂(t) )L−1 , is non-negative. To show that |λ̂(t+1) − λ̂(t) | ≤ |λ − λ̂(t) |, it suffices toshow that η(λ̂(t) )L−1 λL − (λ̂(t) )L ) ≤ |λ − λ̂(t) |, which, in turn would be implied byP(t) i L−1−iη ≤ (λ̂(t) )L−1 PL−11 (λ̂(t) )i λL−1−i (since λL − (λ̂(t) )L = (λ − λ̂(t) ) L−1),
i=0 (λ̂ ) λ( i=0)
which follows from the inductive hypothesis and η ≤ LΓ1 2 .
We have proved that each λ̂(t) lies between λ and 1, so that |1 − λ̂(t) | ≤ |1 − λ| ≤c4 ln(Γ/γ).
Now, since the step is in the right direction, and does not overshoot,|λ̂(t+1) − λ| ≤ |λ̂(t) − λ| − η(λ̂(t) )L−1 |λL − (λ̂(t) )L |≤ |λ̂(t) − λ| 1 − η(λ̂(t) )L−1

L−1
X
(λ̂(t) )i λL−1−i

!!

i=0

≤ |λ̂

(t)

− λ| 1 − ηLγ

2



,

since the fact that λ̂(t) lies between 1 and λ implies that λ̂(t) ≥ γ 1/L . Thus, |λ̂(t) −tλ| ≤ (1 − ηLγ 2 ) c4 ln(Γ/γ). This implies that, for any  ∈(0, 1),for any absolutedL ln Γ1steps, we haveconstant c5 , there is a constant c6 such that, after c6 ηLγ
2 ln
γ

10

√

5 γ√ 
|λ̂(t) − λ| ≤ cLΓ
. Writing r = λ̂(t) − λ, this implies, if c5 is small enough, thatd((λ̂(t) )L − λL )2 = ((λ+r)L −λL )2

2
r L
2
1+
≤Γ
−1
λ
2

2c5 rL2≤Γλ
2
2c5 rL
2
≤Γ
γ

≤ .
d



(t)
dL ln Γ1steps, (Dkk − D̂kk )2 ≤ /d for all k, and therefore
Thus, after O ηLγ
2 lnγ
`(Θ(t) ) ≤ , completing the proof.

5

Asymmetric positive definite matrices

We have seen that if the least squares matrix is symmetric, γ-positivity is sufficientfor 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 assumptionthat the least squares matrix is symmetric.
Note that the set of γ-positive (but not necessarily symmetric) matrices includes
both rotations by an acute angle and “partial reflections” of the form ax+b refl(x) where>
refl(·) is a length-preserving reflection and 0 ≤ |b| < a. Since u> Au = u> A> u,a matrix A is γ-positive if and only if u> (A + A> )u ≥ 2γ for all unit length u, i.e.
A + A> is positive definite with eigenvalues at least 2γ.

5.1

Balanced factorizations

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 apositive semidefinite matrix P such that A = RP . The principal Lth root of a complex
number whose expression in polar coordinates is reθi is r1/L eθi/L . The principal Lth
root of a matrix A is the matrix B such that B L = A, and each eigenvalue of B is theprincipal Lth root of the corresponding eigenvalue of A.
Definition 3. If A is a matrix with polar decomposition RP , then A has the balanced
factorization A = A1 , ..., AL where for each i,
Ai = R1/L Pi , with Pi = R(L−i)/L P 1/L R−(L−i)/L ,and each of the Lth roots is the principal Lth root.
11

The motivation for balanced factorizations 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 ofscaling. However, the scaling done by the ith factor should be done in directions thattake 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.
Lemma 7. If σ1 , ..., σd are the singular values of Q
A, and A1 , ..., AL is a balanced factorization of A, then the following hold: (a) A = Li=1 Ai ; (b) for each i ∈ {1, ..., L},
1/L
1/L
σ1 , ..., σd are the singular values of Ai .

5.2

Procedure and upper bound

The following is the power projection algorithm. It has a positivity parameter γ > 0,
and uses H = {A : ∀u s.t. ||u|| = 1, u> Au ≥ γ} as its “hypothesis space”. First, it(0)
initializes Θi = γ 1/L I for all i ∈ {1, ..., L}. Then, for each t, it does the following.
• Gradient Step. For each i ∈ {1, ..., L}, update:(t+1/2)
(t)
(t)
(t)
(t)
Θi
= Θi − η(Θi+1:L )> Θ1:L − Φ (Θ1:i−1 )> .
• Power Project. Compute the projection Ψ(t+1/2) (w.r.t. the Frobenius norm) of(t+1/2)
Θ1:L
onto H.
(t+1)

(t+1)

• Factor. Let Θ1 , ..., ΘL(t+1)
Ψ(t+1/2) = Θ1:L .

be the balanced factorization of Ψ(t+1/2) , so that

Theorem 3. For any Φ such that u> Φu > γ for all unit-length u, the power projection
algorithm produces Θ(t) with `(Θ(t) ) ≤  in poly(d, ||Φ||F , 1/γ) log(1/) iterations.

5.3

Proof of Theorem 3(t)Lemma 8. For all t, Θ1:L ∈ H.
(0)

Proof. Θ1:L = γI ∈ H, and, for all t, Ψ(t+1/2) is obtained by projection onto H, and(t+1)
Θ1:L = Ψ(t+1/2) .
def P∞
1 k
Definition 4. The exponential of a matrix A is exp(A) =k=0 k! A , and B is alogarithm of A if A = exp(B).
Lemma 9 (Culver 1966). 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 oftimes.
(t)

Lemma 10. For all t, Θ1:L has a real Lth root.
(t)

(t)

(t)

Proof. Since Θ1:L ∈ H implies u> Θ1:L u > 0 for all u, Θ1:L does not have a negative(t)
eigenvalue and is invertible. By Lemma 9, Θ1:L has a real logarithm. Thus, its real Lth(t)root can be constructed via exp(log(Θ1:L )/L).
12

The preceding lemma implies that the algorithm is well-defined, since all of therequired roots can be calculated.
Lemma 11. H is convex.
Proof. Suppose A and B are in H and λ ∈ (0, 1). We haveu> (λA + (1 − λ)B)u = λu> Au + (1 − λ)u> Bu ≥ γ.

Lemma 12. For all A ∈ H, σmin (A) ≥ γ.
Proof. Let u and v be singular vectors such that u> Av = σmin (A).
γ ≤ v > Av = σmin (A)v > u ≤ σmin (A).

(t)

Lemma 13. For all t, σmin (Θi ) ≥ γ 1/L .
(0)Proof. First, σmin (Θi ) = γ 1/L ≥ γ 1/L .
Now consider t > 0. Since Ψ(t−1/2) was projected into H, we have σmin (Ψ(t−1/2) ) ≥γ. Lemma 7 then completes the proof.
n
o
(s)
1/L
Define U (t)=max maxs≤t maxi ||Θi ||2 , ||Φ||2
,
B(t)
=
(t)

(s)

mins≤t mini σmin (Θi ), and recall that `(t) = ||Θ1:L − Φ||2F .
Arguing as in the initial portion of Section 3.2, as long asη≤1
3Ld5 U (t)2L(7)


we have `(t + 1/2) ≤ 1 − ηLB(t)2L `(t) (see Equation 4). Lemma 13 gives B(t) ≥(t+1/2)γ 1/L , so `(t + 1/2) ≤ (1 − ηLγ 2 ) `(t). Since Ψ(t+1/2) is the projection of Θ1:L
onto
(t+1)
(t+1/2)a convex set H that contains Φ, and Θ1:L = Ψ, (7) implies
`(t + 1) ≤ `(t + 1/2) ≤ 1 − ηLγ 2 `(t).
(8)
Next, we prove an upper bound on U .
p1/L
Lemma 14. For all t, U (t) ≤`(t) + ||Φ||F
.
p
(t)
(t)
Proof. Recall that `(t) = ||Θ1:L −Φ||2F . By the triangle inequality, ||Θ1:L ||F ≤ `(t)+
p
(t)
(t)
||Φ||F . Thus ||Θ1:L ||2 ≤ `(t) + ||Φ||F . By Lemma 7, for all i, we have ||Θi ||2 ≤p1/L`(t) + ||Φ||F. Since ||Φ||2 ≤ ||Φ||F , this completes the proof.

13

(0)

Note that the triangle inequality implies that `(0) ≤ ||Θ1:L ||2F + ||Φ||2F ≤ γ 2 d +||Φ||2F . Since σmin (Φ) ≥ γ, we have ||Φ||2F ≥ γ 2 d, so `(t) ≤ 2||Φ||2F and U (t) ≤(3||Φ||2 )1/L . Now, if we set η = cLd51||Φ||2 , for a large enough absolute constant c, thenF γ2(7) is satisfied, so that (8) gives `(t + 1) ≤ 1 − cd5 ||Φ||2 `(t) and the power projection
F
algorithm achieves `(t + 1) ≤  after
 5

 5



d ||Φ||2F
d ||Φ||2F`(0)||Φ||2F
O
=O
log
log
γ2

γ2

updates.

6

The Necessity of Positive Definite Targets

In this section, we show that positive definite Φ are necessary for several gradient descent algorithms with different kinds of regularization to minimize the loss. One familyof algorithms that we will analyze is parameterized by a function ψ mapping the numberof inputs d and the number of layers L to a radius ψ(d, L), step sizes ηt and initialization
parameter γ ≥ 0. In particular, a ψ-step-and-project algorithm is any instantiation of
the following algorithmic template.
(0)
Initialize each Θi = γ 1/L I for some γ ≥ 0 and iterate:• Gradient Step. For each i ∈ {1, ..., L}, update:


(t)
(t)
(t)
(t)
(t+1/2)= Θi − ηt (Θi+1:L )> Θ1:L − Φ (Θ1:i−1 )> .
Θi
t+1/2

• Project. Set each Θt+1
to the projection of Θiiψ(d, L)}.

onto {A : ||A − I||2 ≤We will also show that Penalty Regularized Gradient Descent which
P uses gradientκ
descent with any step sizes ηt on the regularized objective `(Θ) + 2 i ||I − Θ||2F also
fails to minimize the loss.
Both results use the simple observation that when Θ1:L and Φ are mutually diagonalizable then||Θ1:L − Φ||2F = ||U > D̂U − U > DU ||2F =dX(D̂jj − Djj )2 ,j=1

where the Dii are the eigenvalues of Φ.
Theorem 4. If the least squares matrix Φ is symmetric then Penalty Regularized Gra(t)dient Descent produces hypotheses Θ1:L that are commuting normal with Φ.
In addition, if Φ has a negative eigenvalue −λ and L is even, then `(Θ(t) ) ≥ λ2 /2for all t.

14

(t+1)(t)

Proof. For all t, Penalty
Regularized
Gradient Descent produces Θi= (1−κ)Θi +


(t)
(t)
(t)
(t)
>
>
κI − ηt (Θi+1:L ) Θ1:L − Φ (Θ1:i−1 ) . Thus, by induction, the Θi are matrix polynomials of Φ, and therefore they are all commuting normal. As in Lemmas 5 and 6, each(t)(t)
Θi is the same U > D̃(t) U and Θ1:L = U > (D̃(t) )L U . Since L is even, each (D̃(t) )Ljj ≥ 0,(t)
so `(Θ(t) ) = 12 ||Θ1:L − Φ||2F ≥ λ2 /2.
To analyze step-and-project algorithms, it is helpful to first characterize the Projectstep. (Lefkimmiatis et al. (2013) proved a similar lemma.)
Lemma 15. Let X be a symmetric matrix and let U > DU be its diagonalization.
For a > 0, let Y be the Frobenius norm projection of X onto Ba = {A :A is symmetric psd and ||A − I||2 ≤ a}. Then Y = U > D̃U where D̃ is obtained fromD by projecting all of its diagonal elements onto [1 − a, 1 + a].
Thus {X, Y } are symmetric commuting normal matrices.
Proof. First, if X ∈ Ba , then Y = X and we are done.
Assume X 6∈ Ba . Clearly U > D̃U ∈ Ba , so we just need to show that any memberof Ba is at least as far from X as U > D̃U is. Let Λ be the multiset of eigenvalues ofX (with repetitions) that are not in [1 − a, 1 + a], and for each λ ∈ Λ, let eλ be theadjustment to λ necessary to bring it to [1 − a, 1 + a]; i.e., so that λ + eλ is the projectionof λ onto [1 − a, 1 + a].
P
If uλ is the eigenvector associated with λ, we have U > D̃U − X = λ∈Λ eλ uλ u>
λ,
P
2
2
>
so that ||U D̃U − X||F = λ∈Λ eλ .
2
P Let 2Z be an arbitrary member of Ba . We would like to show that ||Z − X||F ≥λ∈Λ eλ . Since Z ∈ Ba , we have ||Z − I||2 ≤ a. ||Z − I||2 is the largest singular valueof Z −I so, for any unit length vector, in particular some uλ for λ ∈ Λ, |u>λ (Z −I)uλ | =>>|uλ Zuλ −1| ≤ a, which implies uλ Zuλ ∈ [1−a, 1+a]. Since U is unitary U > (X−Z)U
has the same eigenvalues as X − Z, and, since the Frobenius norm is a function of theeigenvalues, ||U > (X − Z)U ||F = ||X − Z||F . But since u>a] for all
λ Zuλ ∈ [1 − a, 1 +P>
2
λ ∈ Λ, just summing over the diagonal elements, we get ||U (X −Z)U ||F ≥ λ∈Λ e2λ ,completing the proof.
Theorem 5. If the least squares matrix Φ is symmetric then ψ-step-and-project algo(t)rithms produce hypotheses Θ1:L that are commuting normal with Φ.
In addition, if Φ has a negative eigenvalue −λ and either L is even or ψ(L, d) ≤ 1,then `(Θ(t) ) ≥ λ2 /2 for all t.
(t+1/2)

Proof. As in Lemmas 5 and 6, the Θi
are identical and mutually diagonalizablewith Φ. Lemma 15 shows that this is preserved by the projection step. Thus there is a
(t)
(t)
(t)
real diagonal D̃(t) such that each Θi = U > Di U , so Θ1:L = U > (D̃(t) )L U .
When L is even, each (D̃(t) )L )j,j ≥ 0. When ψ(d, L) ≤ 1 then the projection
ensures that the elements of D̃(t) are non-negative, and thus each (D̃(t) )L )j,j ≥ 0. In(t)either case, `(Θ(t) ) = 21 ||Θ1:L − Φ||2F ≥ λ2 /2.
One choice of Φ that satisfies the requirements of Theorems 4 and 5 is Φ =diag(−λ, 1, 1, ..., 1). For constant λ, the loss of Θ(0) = (I, I, ..., I) is a constant for15this target. Another choice is Φ = diag(−λ, −λ, 1, 1, ..., 1), which has a positive determinant.
The proofs in this section exploit the fact that the layers are initialized to multiplesof the identity; this greatly simplifies the iterates. Similar behavior has been identified
when gradient descent is used for matrix factorization (Jain et al., 2017).
After the publication of an earlier version of this paper (Bartlett et al., 2018b),
Shamir (2018) analyzed learning in one-dimensional deep linear networks with nearidentity initialization. That paper shows, when starting from a modest random perturbation of the identity and learning a Φ with negative eigenvalues, the number of iterations
needed to reach a good solution is exponential in the number of layers.
Here we give a Corollary of Theorems 4 and 5 that provides an alternative treatmentof near-identity initialization. A near-identity ψ-step-and-project algorithm has an additional parameter δ > 0; it initializes each layer to a member of an δ-ball centered I,
and otherwise satisfies the constraints on a ψ-step-and-project algorithm. Define a nearidentity penalty regularized gradient descent algorithm analogously. We now consider
learning an arbitrary (but fixed) deep network as described in Section 2.1.
Corollary 1. If the least squares matrix Φ is symmetric and its least eigenvalue is λ > 0,then
• for any t ∈ N , any  > 0 and any near-identity penalty regularized gradient(0)
descent algorithm, there is δ > 0 such that, if ||Θi − I||F ≤ δ for all i, then`(Θ(t) ) ≥ λ2 /2 − , and• for any t ∈ N , any  > 0 and any near-identity ψ-step-and-project algorithm A,(0)there is δ > 0 such that, if ||Θi − I||F ≤ δ for all i, then `(Θ(t) ) ≥ λ2 /2 − .
Proof. Let A be a near-identity penalty regularized gradient descent algorithm or anear-identity ψ-step-and-project algorithm, and let Θ(t) be A’s parameters after iteration t starting with the near-identity parameters Θ(0) . The updated parameters of A
are a continuous function of its pre-update parameters. Thus, for every t, `(Θ(t) ) isa continuous function of Θ(0) . Now consider starting A with the initial parametersΞ(0) = (I, I, . . . I), and let Ξ(t) be the parameters after t updates. By Theorem 4 or 5,`(Ξ(t) ) ≥ λ2 /2. From the continuity of the updates, for each t there is a δt > 0 such(0)
that, if ||Θi − I||2F < δt , then |`(Θ(t) ) − `(Ξ(t) )| ≤  completing the proof.

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 IIS1619362 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).

16

A

Proof of Lemma 1

We rely on the following facts (Horn, 1986; Harville, 1997).
Lemma 16. For compatible matrices (and, where m, n, p, q, r, s are mentioned, A ∈<m×n , B ∈ <p×q , X ∈ <r×s ):A ⊗ (B ⊗ E) = (A ⊗ B) ⊗ E,
AC ⊗ BD = (A ⊗ B)(C ⊗ D),(A ⊗ B)> = A> ⊗ B > ,vec(AXB) = (B > ⊗ A)vec(X),defTm,n vec(A) = vec(A> ),Tn,m Tm,n = Imn ,>Tm,n = Tn,m,

T1,n = Tn,1 = In ,DX (A(B(X))) = DB (A(B(X)))DX (B(X)),
DX (A(X)B(X)) = (B(X)> ⊗ Im )DX A(X) + (Iq ⊗ A(X))DX B(X),DX (A(X)T ) = Tn,m DX (A(X)),
DX (AXB) = B > ⊗ A,
DA (A ⊗ B) = (In ⊗ Tq,m ⊗ Ip )(Imn ⊗ vec(B))= (Inq ⊗ Tm,p )(In ⊗ vec(B) ⊗ Im ),DB (A ⊗ B) = (In ⊗ Tq,m ⊗ Ip )(vec(A) ⊗ Ipq )= (Tp,q ⊗ Imn )(Iq ⊗ vec(A) ⊗ Ip ).
Armed with Lemma 16, we now prove Lemma 1. We haveDΘi fΘ (x) = DΘi (Θi+1:L Θi Θ1:i−1 x) = (Θ1:i−1 x)> ⊗ Θi+1:L .
Again, from Lemma 16DΘi DΘj fΘ (x) = DΘi (Θ1:j−1 x)> ⊗ Θj+1:L= DΘ1:j−1 x (Θ1:j−1 x)> ⊗ Θj+1:L DΘi (Θ1:j−1 x)(by the chain rule, since i < j)
>  
>= DΘ1:j−1 x (Θ1:j−1 x) ⊗ Θ>
(Θ
x)
⊗
Θ
1:i−1
i+1:j−1 .
j+1:L(9)Define P = Θ1:j−1 x and Q = Θj+1:L , so that P ∈ <d×1 and Q ∈ <d×d . We have> 
DP P ⊗ Q >= Td2 ,d DP P ⊗ Q>
= Td2 ,d (I1 ⊗ Td,d ⊗ Id )(Id ⊗ vec(QT ))= Td2 ,d (Td,d ⊗ Id )(Id ⊗ vec(Q> )).

17

Substituting back into (9), we get>DΘi DΘj fΘ (x) = Td2 ,d (Td,d ⊗ Id )(Id ⊗ vec(Θ>
))
(Θ
x)
⊗
Θ
.
1:i−1
i+1:j−1
j+1:L
The product rule in Lemma 16 gives, for each i,DΘi ` (fΘ ) = E(DΘi (`(fΘ (X)))
1= E(DΘi ( (fΘ (X) − ΦX)> (fΘ (X) − ΦX)))
2= E(((Θ1:L − Φ)X)> DΘi fΘ (X))



>
>
= E ((Θ1:L − Φ)X) (Θ1:i−1 X) ⊗ Θi+1:L= E (I1 ⊗ ((Θ1:L − Φ)X)> ) (Θ1:i−1 X)> ⊗ Θi+1:L= E (Θ1:i−1 X)> ⊗ ((Θ1:L − Φ)X)> Θi+1:L>>= E X > Θ>
⊗
X
(Θ
−
Φ)
Θ
1:L
i+1:L
1:i−1

>
>
= E (X ⊗ X > ) Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L>= E ((X ⊗ X)vec(1))> Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L
> >= E vec(XX > )Θ1:i−1 ⊗ (Θ1:L − Φ)> Θi+1:L>= (vec(Id ))T Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L .
Hence,
(DΘi ` (fΘ ))> = Θ1:i−1 ⊗ Θ>
i+1:L (Θ1:L − Φ) (vec(Id ))>= vec Θ>i+1:L (Θ1:L − Φ)Id Θ1:i−1 .
Also, recalling that i < j, we have>DΘj DΘi ` (fΘ ) = DΘj (vec(Id ))T Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L>= (Id2 ⊗ (vec(Id ))T )DΘj Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L





>
= (Id2 ⊗ (vec(Id ))T ) (Id ⊗ Td,d ⊗ Id ) vec(Θ>1:i−1 ) ⊗ Id2 DΘj (Θ1:L − Φ) Θi+1:L .
Continuing with the subproblem,>DΘj (Θ1:L − Φ)> Θi+1:L = (Θ>i+1:L ⊗ Id )DΘj (Θ1:L − Φ)
+ (Id ⊗ (Θ1:L − Φ)> )DΘj (Θi+1:L )

>
= (Θ>
i+1:L ⊗ Id )DΘj Θ1:L
+ (Id ⊗ (Θ1:L − Φ)> )DΘj (Θi+1:L )

>
>
= (Θ>
⊗
I
)
Θ
⊗
Θ
d
j+1:L
i+1:L
1:j−1 DΘj (Θj )+ (Id ⊗ (Θ1:L − Φ)> ) Θ>
i+1:j−1 ⊗ Θj+1:L>>= (Θi+1:L ⊗ Id ) Θj+1:L ⊗ Θ1:j−1 Td,d

+ (Id ⊗ (Θ1:L − Φ)> ) Θ>
i+1:j−1 ⊗ Θj+1:L>= Θ>
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d>+ Θ>
i+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L .



18

Finally,>DΘi DΘi ` (fΘ ) = DΘi (vec(Id ))T Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L>= (Id2 ⊗ (vec(Id ))T )DΘi Θ>
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L= (Id2 ⊗ (vec(Id ))T ) (Id ⊗ Td,d ⊗ Id )>vec(Θ>
1:i−1 ) ⊗ Id2 DΘi (Θ1:L − Φ) Θi+1:L
and


>
DΘi (Θ1:L − Φ)> Θi+1:L = (Θ>i+1:L ⊗ Id )DΘi (Θ1:L − Φ)

>
= (Θ>
i+1:L ⊗ Id )DΘi Θ1:L

>
>
= (Θ>
i+1:L ⊗ Id ) Θi+1:L ⊗ Θ1:i−1 DΘi (Θi )

>
= (Θ>
i+1:L ⊗ Id ) Θi+1:L ⊗ Θ1:i−1 Td,d>= Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d .

B

Proof of Lemma 3

We have||∇2 ||2F = 2

X||DΘj DΘi `(fΘ )||2F +i<jX||DΘi DΘi `(fΘ )||2F .

(10)

i

Let’s start with the easier term. Choose Θ such that ||Θi − I||2 ≤ z for all i. We have||DΘi DΘi ` (fΘ ) ||F = (Id2 ⊗(vec(Id ))> ) (Id ⊗Td,d ⊗Id ) vec(Θ>1:i−1 )⊗Id2
>Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F≤ (Id2 ⊗ (vec(Id ))> ) (Id ⊗ Td,d ⊗ Id ) F >
× vec(Θ>Θi+1:L Θi+1:L ⊗Θ>
1:i−1 )⊗Id2
1:i−1 Td,d
= d3/2 vec(Θ>1:i−1 ) ⊗ Id2
>Θ>i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F≤ d3/2 vec(Θ>1:i−1 ) ⊗ Id2
F
>>× Θi+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F>>= d7/2 vec(Θ>
)
Θ
Θ
⊗Θ
i+1:L
1:i−1
i+1:L
1:i−1 Td,d FF>= d7/2 ||Θ1:i−1 ||F Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F>≤ d4 ||Θ1:i−1 ||2 Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F>≤ d4 (1 + z)i−1 Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F>= d4 (1 + z)i−1 Θ>
i+1:L Θi+1:L ⊗ Θ1:i−1
F= d4 (1 + z)i−1 Θ>
i+1:L Θi+1:L≤ d (1 + z)Θ>i+1:L Θi+1:L
52(L−1)
5

F

× Θ>
1:i−1

F

2

Θ>
1:i−1

2

i−1

≤ d (1 + z)

.

19

×

F

Similarly,||DΘj DΘi ` (fΘ ) ||F = (Id2 ⊗(vec(I))> ) (Id ⊗Td,d ⊗Id ) vec(Θ>1:i−1 )⊗Id2


>
Θ
⊗
Θ
Θ>
j+1:L
1:j−1 Td,d
i+1:L


>
>
+ Θi+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:LF>≤ d4 (1 + z)i−1 Θ>
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d>+ Θ>
i+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:LF>≤ d4 (1 + z)i−1Θ>
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d F
 
>
⊗
(Θ
−
Φ)
Θ
+ Θ>
1:L
j+1:L
i+1:j−1F≤ d4 (1 + z)i−1 d(1 + z)2L−1−i+>Θ>
i+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L
F= d4 (1 + z)i−1 d(1 + z)2L−1−i+ ||Θi+1:j−1 ||F × (Θ1:L − Φ)> Θj+1:L≤ d4 (1 + z)i−1 d(1 + z)2L−1−i + 2d(1 + z)F

2L−1−i= 3d5 (1 + z)2L−2 .

Putting these together with (10), we get ||∇2 ||2F ≤ L2 9d10 (1 + z)4L , so that||∇2 ||F ≤ 3Ld5 (1 + z)2L .

C

Proof of Lemma 7

Recall that a matrix M is unitary if its inverse is its conjugate-transpose (M −1 = M ∗ )and the polar decomposition of a matrix A consists of a unitary matrix R and a positive
semidefinite matrix P such that A = RP .
Lemma 17. (See, e.g., Horn and Johnson, 2013).
• A matrix is unitary if and only if all of its eigenvalues have magnitude 1.
• Every unitary matrix is normal and non-singular.
• A normal matrix with eigenvalues λ1 , ..., λd , has singular values |λ1 |, ..., |λd |.
Lemma 18. If matrix M is invertible and normal with singular values σ1 , ..., σd , then,
1/L
1/L
for any positive integer L, the singular values of M 1/L are σ1 , ..., σd .
Proof. Follows from Lemma 17 together with the fact that raising a non-singular matrix
to a power results in raising its eigenvalues to the same power.

20

Lemma 19. If matrix M is unitary, then M 1/L is unitary, and thus M i/L and (M ∗ )i/L
are unitary for any non-negative integer i.
Proof. Follows from Lemmas 17 and 18.
Lemma 20. If matrix U is unitary and M1 = U M2 (or M1 = M2 U ) then M1 and M2
have the same singular values.
Proof. Follows from M1∗ M1 = M2∗ M2 (or M1 M1∗ = M2 M2∗ ).
Recall that in a balanced factorization of A with polar decomposition A = RP ,each Ai = R1/L R(L−i)/L P 1/L (R∗ )(L−i)/L .
Q
Lemma 21. If σ1 , ..., σd are the singular values of A, and A = Li=1 Ai is a bal1/L
1/L
anced factorization of A, then σ1 , ..., σd are the singular values of Ai , for eachi ∈ {1, ..., L}.
Proof. Since R is unitary, the singular values of A and P are the same by Lemma 20.
Repeated use of Lemma 20 also shows that each Ai has the same singular values as
P 1/L . Lemma 18 completes the proof.
Lemma 22. If A1 , ..., AL is a balanced factorization of A, then
A=

L
Y

Ai .

i=1

Proof. We have:
A = RP= R1/L R(L−1)/L P 1/L R∗ (L−1)/L R(L−1)/L P (L−1)/L= A1 R(L−1)/L P (L−1)/L= A1 R1/L R(L−2)/L P 1/L R∗ (L−2)/L R(L−2)/L P (L−2)/L= A1 A2 R(L−2)/L P (L−2)/L
..
.
!
L−1
L
Y
Y
1/L 1/L=
Ai R P
=
Ai .
i−1

i=1

References
Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. (2014). Learning polynomials
with neural networks. In ICML.
Arora, S., Bhaskara, A., Ge, R., and Ma, T. (2014). Provable bounds for learning somedeep representations. In International Conference on Machine Learning, pages 584–
592.
21

Bartlett, P. L., Evans, S. N., and Long, P. M. (2018a). Representing smooth functions
as compositions of near-identity functions with implications for deep network optimization. arXiv preprint arXiv:1804.05012.
Bartlett, P. L., Helmbold, D. P., and Long, P. M. (2018b). Gradient descent with identity initialization efficiently learns positive definite linear transformations. In ICML,
volume 80 of JMLR Workshop and Conference Proceedings, pages 520–529.
Boyd, S. P. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University
Press, Cambridge, UK.
Brutzkus, A. and Globerson, A. (2017). Globally optimal gradient descent for a ConvNet with Gaussian inputs. In Precup, D. and Teh, Y. W., editors, Proceedings ofthe 34th International Conference on Machine Learning, volume 70 of Proceedingsof Machine Learning Research, pages 605–614, International Convention Centre,
Sydney, Australia. PMLR.
Brutzkus, A., Globerson, A., Malach, E., and Shalev-Shwartz, S. (2018). SGD learns
over-parameterized networks that provably generalize on linearly separable data.
ICLR.
Culver, W. J. (1966). On the existence and uniqueness of the real logarithm of a matrix.
Proceedings of the American Mathematical Society, 17(5):1146–1151.
Daniely, A. (2017). SGD learns the conjugate kernel class of the network. NIPS.
Ge, R., Jin, C., and Zheng, Y. (2017a). No spurious local minima in nonconvex low
rank problems: A unified geometric analysis. arXiv preprint arXiv:1704.00708.
Ge, R., Lee, J. D., and Ma, T. (2017b). Learning one-hidden-layer neural networks withlandscape design. arXiv preprint arXiv:1711.00501.
Ge, R., Lee, J. D., and Ma, T. (2018). Learning one-hidden-layer neural networks withlandscape design. ICLR.
Hardt, M. and Ma, T. (2017). Identity matters in deep learning. ICLR.
Harville, D. A. (1997). Matrix algebra from a statistician’s perspective, volume 1.
Springer.
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image
recognition. In CVPR, pages 770–778.
Horn, R. A. (1986). Topics in Matrix Analysis. Cambridge University Press, New York,NY, USA.
Horn, R. A. and Johnson, C. R. (2013). Matrix analysis. Cambridge University Press.
Second edition.

22

Jain, P., Jin, C., Kakade, S. M., and Netrapalli, P. (2017). Global convergence of nonconvex gradient descent for computing matrix squareroot. In AISTATS, pages 479–
488.
Janzamin, M., Sedghi, H., and Anandkumar, A. (2015). Beating the perils of nonconvexity: Guaranteed training of neural networks using tensor methods. arXiv
preprint arXiv:1506.08473.
Kawaguchi, K. (2016). Deep learning without poor local minima. In Advances in
Neural Information Processing Systems, pages 586–594.
Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B. (2016). Gradient descent
only converges to minimizers. In Feldman, V., Rakhlin, A., and Shamir, O., editors,
29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine
Learning Research, pages 1246–1257, Columbia University, New York, New York,USA. PMLR.
Lee, W. S., Bartlett, P. L., and Williamson, R. C. (1996). Efficient agnostic learningof neural networks with bounded fan-in. IEEE Transactions on Information Theory,42(6):2118–2132.
Lefkimmiatis, S., Ward, J. P., and Unser, M. (2013). Hessian Schatten-norm regularization for linear inverse problems. IEEE transactions on image processing,22(5):1873–1888.
Li, Y. and Yuan, Y. (2017). Convergence analysis of two-layer neural networks with relu
activation. In Advances in Neural Information Processing Systems, pages 597–607.
Livni, R., Shalev-Shwartz, S., and Shamir, O. (2014). On the computational efficiencyof training neural networks. In Advances in Neural Information Processing Systems,
pages 855–863.
Nguyen, Q. and Hein, M. (2017). The loss surface of deep and wide neural networks.
In ICML, pages 2603–2612.
Orhan, A. E. and Pitkow, X. (2018). Skip connections eliminate singularities. ICLR.
Safran, I. and Shamir, O. (2016). On the quality of the initial basin in overspecified
neural networks. In International Conference on Machine Learning, pages 774–782.
Saxe, A. M., McClelland, J. L., and Ganguli, S. (2013). Exact solutions to the nonlinear
dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120.
Shamir, O. (2018). Exponential convergence time of gradient descent for onedimensional deep linear neural networks. arXiv preprint arXiv:1809.08587.
Taghvaei, A., Kim, J. W., and Mehta, P. (2017). How regularization affects the criticalpoints in linear networks. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information
Processing Systems 30, pages 2502–2512. Curran Associates, Inc.
23

Zhang, Q., Panigrahy, R., and Sachdeva, S. (2018). Electron-proton dynamics in deeplearning. ITCS.
Zhang, Y., Lee, J., Wainwright, M., and Jordan, M. (2017). On the learnability of fullyconnected neural networks. In Proceedings of the 20th International Conference on
Artificial Intelligence and Statistics, pages 83–91.
Zhang, Y., Lee, J. D., and Jordan, M. I. (2016). l1-regularized neural networks are
improperly learnable in polynomial time. In International Conference on Machine
Learning, pages 993–1001.
Zhong, K., Song, Z., Jain, P., Bartlett, P. L., and Dhillon, I. S. (2017). Recovery guarantees for one-hidden-layer neural networks. In ICML, pages 4140–4149.

24