arXiv:1802.06093v2 [cs.LG] 24 Feb 2018

Gradient descent with identity initialization
efficiently learns
positive definite linear transformations
by deep residual networks
Peter L. Bartlett
UC Berkeley
bartlett@cs.berkeley.edu

David P. Helmbold
UC Santa Cruz
dph@soe.ucsc.edu

Philip M. Long
Google
plong@google.com

February 27, 2018
Abstract
We analyze algorithms for approximating a function f (x) = Φx mapping ℜd to ℜd using
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 optimum, in the case where the initial hypothesis Θ1 = ... = ΘL = I has loss bounded
by a small enough constant. 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 of
regularization 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 of f using a number of updates polynomial in L, the condition number
of Φ, and log(d/ǫ). In contrast, we show that if the target Φ is symmetric and has a negative
eigenvalue, then all members of a class of algorithms that perform gradient descent with identity
initialization, and optionally regularize toward the identity in each layer, fail to converge.
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 the invariant
u⊤ ΘL ΘL−1 ...Θ1 u > 0 for all u, and another that “balances” Θ1 ...ΘL so that they have the
same singular values.

1

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
1

• 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) = ΘL ΘL−1 ...Θ1 x, where, for
large L, each layer Θi is close to the identity, and
• for networks that compose near-identity transformations this way, if the loss is large, then
the gradient is steep.
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 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, as done by Hardt and Ma. We also assume that y = Φx; it is not
hard to see that this is equivalent to the case that y = Φx + ξ for noise ξ that is independent of
x and has zero mean. Finally, we focus on the case that the distribution on the input patterns is
isotropic. (The data may be transformed through a preprocessing step to approximately 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 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 loss of the identity is at most c0 , then
back-propagation initialized at the identity in each layer achieves loss at most ǫ 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 Φ
such that the identity has loss c1 with respect to Φ, but backpropagation with identity initialization
fails to learn Φ (Section 6).
We also show that if the target Φ is symmetric positive definite then gradient descent with identity
initialization achieves 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 Φ 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 loss is forever bounded below
by the square of this negative eigenvalue. This holds for step-and-project algorithms,
P and also
algorithms that initialize at 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 target Φ with
a positive determinant and a good condition number. Recall that such Φ 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 Φ that may not be symmetric, but satisfies
u⊤ Φu > γ for a γ > 0 that appears in the bounds. We say that such matrices have a margin γ.
Such Φ 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
2

what we call power projection, projecting its hypothesis ΘL ΘL−1 ...Θ1 onto the set of matrices
with a margin γ. 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 theoretically tractable
proxy for regularizers that promote a large margin 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 most closely related previous work is the paper by Hardt & Ma (2017) mentioned above. 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 U V . For an interesting survey on the rich
literature on these algorithms, please see Ge et al. (2017a). 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.
All three upper bound analyses use Hardt and Ma’s lemmas, together with a new upper bound on
the operator norm of the Hessian of a deep linear network. They otherwise have different outlines.
Roughly, 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 Lth root of a corresponding eigenvalue of Φ. As mentioned above, the
bound for matrices Φ with a positive margin is for an algorithm that achieves favorable conditioning
through regularization.

3

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.

2
2.1

Preliminaries
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 from P , the marginal on
X is isotropic, with EXX ⊤ = Id , and Y = ΦX for Φ ∈ ℜd×d . (As mentioned in the introduction,
this is equivalent to the case of zero-mean noise that is independent of X.)
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, ℓ(Θ) = 12 ||Θ1:L − Φ||2F with respect to target matrix Φ.
When Θ is produced by an iterative algorithm, will we also refer to loss of the tth iterate by ℓ(t).
Definition 1. For γ > 0, a matrix A ∈ ℜd×d has a margin γ if, for all unit length u, we have
u⊤ Au > γ.

2.2

Tools and background

We 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 Euclidian norm.
For a matrix A and a matrix-valued function B, define DA B(A) to be the matrix with
(DA B(A))i,j =

∂vec(B(A))i
,
∂vec(A)j

where 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 backprop,
is of course well known.) The proof is in the Appendix A.
4

Lemma 1. For i < j,
DΘi ℓ (fΘ ) = (vec(Id ))⊤
= vec(G)⊤ ,



⊤
Θ⊤
1:i−1 ⊗ (Θ1:L −Φ) Θi+1:L



for the d × d matrix given by
def

⊤
G = Θ⊤
i+1:L (Θ1:L − Φ) Θ1:i−1 .

(1)



)
⊗
I
DΘj DΘi ℓ (fΘ ) = (Id2 ⊗ (vec(Id ))⊤ ) (Id ⊗ Td,d ⊗ Id ) vec(Θ⊤
2
d
1:i−1
⊤
((Θ⊤
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 Θi+1:L ⊗ Θ1:i−1 Td,d .

3

Targets near the identity

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

3.1

Procedure and upper bound

First, set Θ(0) = (I, I, ..., I), and then iteratively update


(t)
(t)
(t+1)
(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, if
(0)
1
, then the above gradient descent procedure achieves
ℓ(Θ1:L ) ≤ c1 , L ≥ c2 , and η ≤ p1 (L,d,||Φ||
2)


ℓ(0)
ℓ(fΘ(t) ) ≤ ǫ within t = p2 (1/η) ln ǫ
iterations.

3.2

Proof of Theorem 1

Hardt and Ma showed in the proof of their Theorem 2.2 that the gradient is steep if the loss is
large and the singular values of the layers are not too small.
Lemma 2 (Hardt & 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 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.
5

Lemma 3. Choose an arbitrary Θ with ||Θi ||2 ≤ 1 + z for all i, and target Φ with ||Φ||2 ≤ (1 + z)L .
Let ∇2 be the Hessian of ℓ(fΘ ) with respect to an arbitrary flattening of the parameters of Θ. We
have
||∇2 ||F ≤ 3Ld5 (1 + z)2L .
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 R(Θ) = maxi ||Θi − I||2 . From
the update, we have


(t)
(t)
(t+1)
(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) = 12 ||Θ1:L − Φ||2F , this implies
R(t + 1) ≤ R(t) + η(1 + R(t))L

p

2ℓ(t).

(2)

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

1
,
+ R(t + 1))2L , ||Φ||22 }

(3)

we have ℓ(t + 1) ≤ ℓ(t) − (η/2)||∇Θ(t) ||2 , which, using Lemma 2, gives

ℓ(t + 1) ≤ 1 − 2ηL(1 − R(t))2L ℓ(t).

(4)

η≤

3Ld5 (max{(1

(0)

Pick any c ≥ 1. Assume that L ≥ (4/3) ln c = c2 , ℓ(Θ1:L ) ≤
We claim that, for all t ≥ 0,


p
P
1. R(t) ≤ ηc 2ℓ(0) 0≤s<t exp − sηL
4
c



2. ℓ(t) ≤ exp − 2tηL
ℓ(0).
c4

The base case holds as R(0) = 0 and ℓ(0) = ℓ(0).

6

ln(c)2
8c10

= c1 and η ≤

1
.
3Ld5 max{c2 ,||Φ||22 }

Before starting the inductive step, notice that for any t ≥ 0,


X
p
sηL
exp − 4
ηc 2ℓ(0)
c
0≤s<t

p
≤ ηc 2ℓ(0) ×

1


1 − exp − ηL
4
c

p
2c4
(since
≤ ηc 2ℓ(0) ×
ηL
p
2c5 2ℓ(0)
≤
L
ln c
≤
≤ 3/4
L

ηL
c4

≤ 1)

where the last two inequalities follow from the constraints on ℓ(0) and L.
Using (2),
p
R(t + 1) ≤ R(t) + η(1 + R(t))L 2ℓ(t)


ln c L p
2ℓ(t)
≤ R(t) + η 1 +
L
p
≤ R(t) + ηc 2ℓ(t)


p
tηL
≤ R(t) + ηc 2ℓ(0) exp − 4
c


X
p
sηL
exp − 4 .
≤ ηc 2ℓ(0)
c
0≤s<t+1

Since R(t + 1) ≤

ln c
L ,

the choice of η satisfies (3), so

Now consider (1 − R(t))2L :


ℓ(t + 1) ≤ 1 − 2ηL(1 − R(t))2L ℓ(t).


ln (1 − R(t))2L = 2L ln(1 − R(t))
(1 − R(t))2L

≥ 2L(−2R(t))
ln c
≥ 2L(−2
)
L
≥ 1/c4 .

7

since R(t) ∈ [0, 3/4]
ln c
since 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/c2 completes the proof of the theorem.
4
c

4

Symmetric positive definite targets

In this section, we analyze the procedure of Section 3.1 when the target Φ is symmetric and positive
definite.
Theorem 2. There is an absolute positive constant c3 such that, if Φ is symmetric with margin
1
0 < γ < 1, and L ≥ c3 ln (||Φ||2 /γ), then for all η ≤ L(1+||Φ||
2 ) , gradient descent achieves ℓ(fΘ(t) ) ≤ ǫ
2
in poly(L, ||Φ||2 /γ, 1/η) log(d/ǫ) iterations.

4.1

Proof of Theorem 2

Let Φ be a symmetric real matrix with margin γ > 0, and let Θ(0) , Θ(1) , ... be the iterates of gradient
descent with a step size η > 0 that will be determined later by the analysis.
Definition 2. Symmetric matrices A ⊆ ℜd×d are commuting normal matrices if there is a single
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 & 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 set of singular values of A is the same as the set 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
(t)
(t)
Θ1 = ... = ΘL .

: i ∈ {1, ..., L}, t ∈ Z+ } are commuting normal. For all t,

8

Proof. The proof is by induction. The base case follows from the fact that Φ and I are commuting
normal.
For the induction step, the fact that
(s)

{Φ} ∪ {Θi

(s+1)

: i ∈ {1, ..., L}, s ≤ t} ∪ {Θi

: i ∈ {1, ..., L}, s ≤ t}
(t+1)

are commuting normal follows from Lemma 4. The update formula now reveals that Θ1
(t+1)
ΘL .

= ... =

Now we are ready to analyze the dynamics of the learning process. Let Φ = U ⊤ D L U be a diagonalization of Φ. Let Γ = max{1, ||Φ||2 }. We next describe a sense in 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
and
D̂ (t+1) = D̂ (t) − η(D̂ (t) )L−1 ((D̂ (t) )L − D L ).

= U ⊤ D̂ (t) U
(5)

(t)

Proof. Lemma 5 implies that there is a single real U such that Θi = U ⊤ D̂ (t) U for all i. Applying
(t)
(t)
(t)
Lemma 1, recalling that Θ1 = ... = ΘL , and applying the fact that Θi and Φ commute, we get


(t)
(t+1)
(t)
(t)
Θi
= Θi − η(Θi )L−1 (Θi )L − Φ .
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 ⊤ D L U


= U ⊤ D̂ (t) U − ηU ⊤ (D̂ (t) )L−1 (D̂ (t) )L − D L 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 for now on an
(t)
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
< 1 for all L ≥ c3 ln(Γ/γ).
constants c3 and c4 such that |1 − λ| ≤ c4 ln(Γ/γ)
L
We claim that, for all t, λ̂(t) lies between 1 and λ inclusive, so that |λ̂(t) − λ| ≤ c4 ln(Γ/γ)
. The
L
c4 ln(Γ/γ)
(t)
. Now let us work on the induction step.
base case holds because λ̂ = 1 and |1 − λ| ≤
L
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 |λ̂(t+1) − λ| ≤ |λ̂(t) − λ|. This would follow
from sign(λ̂(t+1) − λ̂(t) ) = sign(λ − λ̂(t) ) and |λ̂(t+1) − λ̂(t) | ≤ |λ − λ̂(t) |. (That is, the step is in
the correct direction, and the algorithm does not “overshoot”.) First, to see that the step is in
9

the right direction, note that λL ≥ (λ̂(t) )L if 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 to show that η(λ̂(t) )L−1 λL − (λ̂(t) )L ) ≤ |λ − λ̂(t) |, which, in turn would be implied by
PL−1 (t) i L−1−i
(λ̂ ) λ
), which follows
η ≤ (t) L−1 PL−11 (t) i L−1−i (since λL − (λ̂(t) )L = (λ − λ̂(t) ) i=0
(λ̂ )
( i=0 (λ̂ ) λ
)
1
from the inductive hypothesis and η ≤ LΓ
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 absolute constant c5 , there is a

1
dL ln Γ
constant c6 such that, after c6 ηLγ
steps, we have |λ̂(t) −λ| ≤
2 ln
γǫ
this implies, if c5 is small enough, that
(t) L

L 2

L

L 2

((λ̂ ) − λ ) = ((λ+r) −λ ) ≤ Γ

2



√
c5 γ√ ǫ
.
LΓ d

Writing r = λ̂(t) −λ,


2

2
2
ǫ
r L
2 2c5 rL
2 2c5 rL
−1 ≤ Γ
≤Γ
≤ .
1+
λ
λ
γ
d




(t)
dL ln Γ
1
steps, (Dkk − D̂kk )2 ≤ ǫ/d for all k, and therefore ℓ(Θ(t) ) ≤ ǫ,
ln
Thus, after O ηLγ
2
γǫ
completing the proof.

5

Asymmetric positive definite matrices

In this section, we consider Φ that may be asymmetric, but which are positive definite in the sense
that u⊤ Φu ≥ γ ≥ 0 for all unit length u. This 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 satisfies the above condition 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 a positive
semidefinite matrix P such that A = RP . The principal Lth root of a complex number whose
10

expression in polar coordinates is reθi is r 1/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 the principal Lth root of the corresponding
eigenvalue of A.
Definition 3. If A be 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.
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 ith 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; it is
proved in Appendix C.
Lemma 7. If σ1 , ..., σd are the singular values of A, and A1 , ..., AL is a balanced factorization of A,
Q
1/L
1/L
then the following hold: (a) A = L
are the singular
i=1 Ai ; (b) for each i ∈ {1, ..., L}, σ1 , ..., σd
values of Ai .

5.2

Procedure and upper bound

The following is the power projection algorithm. It has a (margin) parameter γ > 0, and uses
H = {A : ∀u s.t. ||u|| = 1, u⊤ Au ≥ γ}
(0)

as its “hypothesis space”. First, it initializes Θi
does the following.

= γ 1/L I for all i ∈ {1, ..., L}. Then, for each t, it

• Gradient Step. For each i ∈ {1, ..., L}, update:
(t+1/2)

Θi



(t)
(t)
(t)
(t)
= Θi − η(Θi+1:L )⊤ Θ1:L − Φ (Θ1:i−1 )⊤ .
(t+1/2)

• Power Project. Compute the projection Ψ(t+1/2) (w.r.t. the Frobenius norm) of Θ1:L
onto H.
(t+1)

• Factor. Let Θ1
(t+1)
Θ1:L .

(t+1)

, ..., ΘL

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

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.

11

5.3

Proof of Theorem 3
(t)

Lemma 8. For all t, Θ1:L ∈ H.
(t+1)

(0)

Proof. Θ1:L = γI ∈ H, and, for all t, Ψ(t+1/2) is obtained by projection onto H, and Θ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 a logarithm 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 of times.
(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 eigenvalue and
(t)
is invertible. By Lemma 9, Θ1:L has a real logarithm. Thus, its real Lth root can be constructed
(t)
via exp(log(Θ1:L )/L).
The preceding lemma implies that the algorithm is well-defined, since all of the required roots can
be calculated.
Lemma 11. H is convex.
Proof. Suppose A and B are in H and λ ∈ (0, 1). We have
u⊤ (λ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 uAv ⊤ = σ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.

12

n
o
(s)
1/L
(s)
Define U (t) = max maxs≤t maxi ||Θi ||2 , ||Φ||2
, B(t) = mins≤t mini σmin (Θi ), and recall that
(t)

ℓ(t) = ||Θ1:L − Φ||2F .

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

1

(7)

3Ld5 U (t)2L


we have ℓ(t + 1/2) ≤ 1 − ηLB(t)2L ℓ(t) (see Equation 4). Lemma 13 gives B(t) ≥ γ 1/L , so

(t+1/2)
onto a convex set H that
ℓ(t + 1/2) ≤ 1 − ηLγ 2 ℓ(t). Since Ψ(t+1/2) is the projection of Θ1:L
(t+1)

contains Φ, and Θ1:L

= Ψ(t+1/2) , (7) implies


ℓ(t + 1) ≤ ℓ(t + 1/2) ≤ 1 − ηLγ 2 ℓ(t).

(8)

Next, we prove an upper bound on U .
1/L
p
.
ℓ(t) + ||Φ||F
Lemma 14. For all t, U (t) ≤

(t)

(t)

Proof. Recall that ℓ(t) = ||Θ1:L − Φ||2F . By the triangle inequality, we have ||Θ1:L ||F ≤
p
p
(t)
(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.
(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, then (7) is satisfied, so that (8) gives ℓ(t+1) ≤
F

γ2
ℓ(t) and the power projection algorithm achieves ℓ(t + 1) ≤ ǫ after
1 − cd5 ||Φ||
2
F

O



d5 ||Φ||2F
log
γ2



ℓ(0)
ǫ



=O



d5 ||Φ||2F
log
γ2



||Φ||2F
ǫ



updates.

6

Failure

In this section, we show that positive definite targets 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 ψ mapping the number of 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+1/2)

Θi



(t)
(t)
(t)
(t)
= Θi − ηt (Θi+1:L )⊤ Θ1:L − Φ (Θ1:i−1 )⊤ .
13

t+1/2

• Project. Set each Θt+1
to the projection of Θi
i

onto {A : ||A − I||2 ≤ ψ(d, L)}.

We will also show that Penalty Regularized Gradient
Descent which uses gradient descent with any
κP
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 =

d
X

(D̂jj − Djj )2 ,

j=1

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


(t)
(t)
(t+1)
(t)
(t)
Θi
= (1 − κ)Θi + κI − ηt (Θi+1:L )⊤ Θ1:L − Φ (Θ1:i−1 )⊤ .
(t)

Thus, by induction, the Θi are matrix polynomials of Φ, and therefore they are all commuting
(t)
(t)
normal. As in Lemmas 5 and 6 each Θi is the same U ⊤ D̃ (t) U and Θ1:L = U ⊤ (D̃ (t) )L U . Since L
(t)
1
(t)
2
2
is even, each (D̃ (t) )L
jj ≥ 0, so ℓ(Θ ) = 2 ||Θ1:L − Φ||F ≥ λ /2.
To analyze step-and-project algorithms, it is helpful to first characterize the project step.
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 from D 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 member of Ba is at least
as far from X as U ⊤ D̃U is. Let Λ be the multiset of eigenvalues of X (with repetitions) that are
not in [1 − a, 1 + a], and for each λ ∈ Λ, let eλ be the adjustment to λ necessary to bring it to
[1 − a, 1 + a]; i.e., so that λ + eλ is the projection of λ onto [1 − a, 1 + a].
P
⊤
If uλ is the
eigenvector associated with λ, we have U ⊤ D̃U − X = λ∈Λ eλ uλ u⊤
λ , so that ||U D̃U −
P
2
2
X||F = λ∈Λ eλ .
P
Let Z be an arbitrary member of Ba . We would like to show that ||Z − X||2F ≥ λ∈Λ e2λ . Since
Z ∈ Ba , we have ||Z − I||2 ≤ a. ||Z − I||2 is the largest singular value of Z − I so, for any unit
14

⊤
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 the eigenvalues, ||U ⊤ (X − Z)U ||F = ||X − Z||F .
But since u⊤
λ Zuλ ∈ [1
P− a, 12 + a] for all λ ∈ Λ, just summing over the diagonal elements, we get
⊤
2
||U (X − Z)U ||F ≥ λ∈Λ eλ , completing the proof.

Theorem 5. If the target Φ is symmetric then ψ-step-and-project algorithms produce hypotheses
(t)
Θ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 diagonalizable with Φ.
Lemma 15 shows that this is preserved by the projection step. Thus there is a real diagonal D̃ (t)
(t)
(t)
(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
(t)
elements of D̃ (t) are non-negative, and thus each (D̃ (t) )L )j,j ≥ 0. In either case, ℓ(Θ(t) ) = 12 ||Θ1:L −
2
2
Φ||F ≥ λ /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 for this target. Another choice is
Φ = diag(−λ, −λ, 1, 1, ..., 1), which has a positive determinant.

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
Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. Learning polynomials with neural networks.
In ICML, 2014.
Arora, Sanjeev, Bhaskara, Aditya, Ge, Rong, and Ma, Tengyu. Provable bounds for learning some
deep representations. In International Conference on Machine Learning, pp. 584–592, 2014.
Boyd, S. P. and Vandenberghe, L. Convex Optimization. Cambridge University Press, Cambridge,
UK, 2004. URL http://www.stanford.edu/~boyd/cvxbook.html.
Brutzkus, A. and Globerson, A. Globally optimal gradient descent for a convnet with gaussian
inputs. In ICML, 2017.
15

Brutzkus, Alon, Globerson, Amir, Malach, Eran, and Shalev-Shwartz, Shai. SGD learns overparameterized networks that provably generalize on linearly separable data. ICLR, 2018.
Culver, Walter J. On the existence and uniqueness of the real logarithm of a matrix. Proceedings
of the American Mathematical Society, 17(5):1146–1151, 1966.
Daniely, A. SGD learns the conjugate kernel class of the network. NIPS, 2017.
Daniely, A., Frostig, R., and Singer, Y. Toward deeper understanding of neural networks: The
power of initialization and a dual view on expressivity. In NIPS, 2016.
Ge, R., Jin, C., and Zheng, Y. No spurious local minima in nonconvex low rank problems: A
unified geometric analysis. arXiv preprint arXiv:1704.00708, 2017a.
Ge, Rong, Lee, Jason D, and Ma, Tengyu. Learning one-hidden-layer neural networks with landscape design. arXiv preprint arXiv:1711.00501, 2017b.
Ge, Rong, Lee, Jason D, and Ma, Tengyu. Learning one-hidden-layer neural networks with landscape design. ICLR, 2018.
Hardt, M. and Ma, T. Identity matters in deep learning. ICLR, 2017.
Harville, D. A. Matrix algebra from a statistician’s perspective, volume 1. Springer, 1997.
He, Kaiming, Zhang, Xiangyu, Ren, Shaoqing, and Sun, Jian. Deep residual learning for image
recognition. In CVPR, pp. 770–778, 2016.
Horn, R. A. Topics in Matrix Analysis. Cambridge University Press, New York, NY, USA, 1986.
ISBN 0-521-30587-X.
Horn, Roger A and Johnson, Charles R. Matrix analysis. Cambridge University Press, 2013. Second
edition.
Janzamin, Majid, Sedghi, Hanie, and Anandkumar, Anima. Beating the perils of non-convexity:
Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473,
2015.
Kawaguchi, K. Deep learning without poor local minima. In Advances in Neural Information
Processing Systems, pp. 586–594, 2016.
Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B. Gradient descent only converges to
minimizers. In COLT, 2016.
Lee, Wee Sun, Bartlett, Peter L, and Williamson, Robert C. Efficient agnostic learning of neural
networks with bounded fan-in. IEEE Transactions on Information Theory, 42(6):2118–2132,
1996.
Li, Yuanzhi and Yuan, Yang. Convergence analysis of two-layer neural networks with relu activation.
In Advances in Neural Information Processing Systems, pp. 597–607, 2017.
Livni, Roi, Shalev-Shwartz, Shai, and Shamir, Ohad. On the computational efficiency of training
neural networks. In Advances in Neural Information Processing Systems, pp. 855–863, 2014.
16

Nguyen, Quynh and Hein, Matthias. The loss surface of deep and wide neural networks. In ICML,
pp. 2603–2612, 2017.
Orhan, A Emin and Pitkow, Xaq. Skip connections eliminate singularities. ICLR, 2018.
Safran, Itay and Shamir, Ohad. On the quality of the initial basin in overspecified neural networks.
In International Conference on Machine Learning, pp. 774–782, 2016.
Saxe, A. M., McClelland, J. L., and Ganguli, S. Exact solutions to the nonlinear dynamics of
learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Taghvaei, A., Kim, J. W., and Mehta, P. How regularization affects the critical points in linear
networks. In NIPS, 2017.
Zhang, Q., Panigrahy, R., and Sachdeva, S. Electron-proton dynamics in deep learning. ITCS,
2018.
Zhang, Yuchen, Lee, Jason D, and Jordan, Michael I. l1-regularized neural networks are improperly
learnable in polynomial time. In International Conference on Machine Learning, pp. 993–1001,
2016.
Zhang, Yuchen, Lee, Jason, Wainwright, Martin, and Jordan, Michael. On the learnability of fullyconnected neural networks. In Proceedings of the 20th International Conference on Artificial
Intelligence and Statistics, pp. 83–91, 2017.
Zhong, Kai, Song, Zhao, Jain, Prateek, Bartlett, Peter L., and Dhillon, Inderjit S. Recovery
guarantees for one-hidden-layer neural networks. In ICML, pp. 4140–4149, 2017.

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 ∈

17

ℜ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),
def

Tm,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),
T

DX (A(X) ) = 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 have
DΘ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)


⊤  
⊤
(Θ1:i−1 x)⊤ ⊗ Θi+1:j−1 .
= DΘ1:j−1 x
(Θ1:j−1 x) ⊗ Θj+1:L

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

18

(9)

Substituting back into (9), we get

DΘi DΘj fΘ (x)

= Td2 ,d (Td,d ⊗ Id )(Id ⊗

vec(Θ⊤
j+1:L ))



⊤



(Θ1:i−1 x) ⊗ Θi+1:j−1 .

The product rule in Lemma 16 gives, for each i,
DΘi ℓ (fΘ )

Hence,

= 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

 

⊤
⊤
⊗
X
(Θ
−
Φ)
Θ
= E 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:L
i+1:L
1:i−1


⊤
= (vec(Id ))T Θ⊤
1:i−1 ⊗ (Θ1:L − Φ) Θi+1:L .


(DΘi ℓ (fΘ ))⊤ = Θ1:i−1 ⊗ Θ⊤
(Θ
−
Φ)
(vec(Id ))
1:L
i+1:L


⊤
= vec Θ⊤
(Θ
−
Φ)I
Θ
1:L
d 1:i−1 .
i+1:L

Also, recalling that i < j, we have
DΘj DΘi ℓ (fΘ )



⊤
⊗
(Θ
−
Φ)
Θ
= DΘj (vec(Id ))T Θ⊤
1:L
i+1:L
1:i−1


⊤
⊗
(Θ
−
Φ)
Θ
= (Id2 ⊗ (vec(Id ))T )DΘj Θ⊤
1:L
i+1:L
1:i−1




⊤
(Θ
−
Φ)
Θ
)
⊗
I
= (Id2 ⊗ (vec(Id ))T ) (Id ⊗ Td,d ⊗ Id ) vec(Θ⊤
D
2
1:L
i+1:L .
Θj
d
1:i−1

19

Continuing with the subproblem,




⊤
(Θ
−
Φ)
⊗
I
)D
DΘj (Θ1:L − Φ)⊤ Θi+1:L = (Θ⊤
1:L
Θ
d
i+1:L
j

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


⊤
Θ
= (Θ⊤
⊗
I
)D
Θj
d
1:L
i+1:L

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


⊤
⊤
= (Θ⊤
i+1:L ⊗ Id ) Θj+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 − Φ)⊤ ) Θ⊤
⊗
Θ
j+1:L
i+1:j−1


⊤
= Θ⊤
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d


⊤
+ Θ⊤
⊗
(Θ
−
Φ)
Θ
1:L
j+1:L .
i+1:j−1

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:L
i+1:L
1:i−1
= (Id2 ⊗ (vec(Id ))T ) (Id ⊗ Td,d ⊗ Id )




⊤
(Θ
−
Φ)
Θ
vec(Θ⊤
)
⊗
I
D
2
1:L
i+1:L
Θ
d
1:i−1
i

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
)
Θ
⊗
Θ
i+1:L
d
i+1:L
1:i−1 DΘi (Θi )


⊤
= (Θ⊤
⊗
I
)
Θ
⊗
Θ
i+1:L
d
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<j

X
i

20

||DΘi DΘi ℓ(fΘ )||2F .

(10)

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(Θ⊤
)⊗I
2
d
1:i−1


⊤
Θ⊤
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d F
≤ (Id2 ⊗ (vec(Id ))⊤ ) (Id ⊗ Td,d ⊗ Id )
F



⊤
⊤
× vec(Θ1:i−1 )⊗Id2 Θi+1:L Θi+1:L ⊗Θ⊤
1:i−1 Td,d


= d3/2 vec(Θ⊤
1:i−1 ) ⊗ Id2


⊤
Θ⊤
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d
F


⊤
3/2
vec(Θ1:i−1 ) ⊗ Id2
≤d
F


⊤
⊤
× Θi+1:L Θi+1:L ⊗ Θ1:i−1 Td,d
F


⊤
⊤
7/2
Θi+1:L Θi+1:L ⊗Θ⊤
vec(Θ1:i−1 )
=d
1:i−1 Td,d

F
⊤
Θ⊤
= d7/2 ||Θ1:i−1 ||F
i+1:L Θi+1:L ⊗ Θ1:i−1 Td,d
F


4
⊤
⊤
≤ d ||Θ1:i−1 ||2 Θi+1:L Θi+1:L ⊗ Θ1:i−1 Td,d
F


⊤
⊤
4
i−1
Θi+1:L Θi+1:L ⊗ Θ1:i−1 Td,d
≤ d (1 + z)
F


⊤
⊤
4
i−1
Θi+1:L Θi+1:L ⊗ Θ1:i−1
= d (1 + z)
F

4

i−1

= d (1 + z)
5

i−1

≤ d (1 + z)
5

Θ⊤
i+1:L Θi+1:L

Θ⊤
i+1:L Θi+1:L

2(L−1)

≤ d (1 + z)

.

21

F
2

×

Θ⊤
1:i−1

×

Θ⊤
1:i−1

F
2

F

F

Similarly,


||DΘj DΘi ℓ (fΘ ) ||F = (Id2 ⊗(vec(I))⊤ ) (Id ⊗Td,d ⊗Id ) vec(Θ⊤
)⊗I
2
d
1:i−1


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


⊤
⊤
+ Θi+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L
F


⊤
≤ d4 (1 + z)i−1 Θ⊤
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d


⊤
+ Θ⊤
i+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L
F

 
⊤
Θ⊤
≤ d4 (1 + z)i−1
i+1:L Θj+1:L ⊗ Θ1:j−1 Td,d
F
 

⊤
⊤
+ Θi+1:j−1 ⊗ (Θ1:L − Φ) Θj+1:L
F

≤ d4 (1 + z)i−1 d(1 + z)2L−1−i


⊤
⊗
(Θ
−
Φ)
Θ
+ Θ⊤
1:L
j+1:L
i+1:j−1
4

i−1

= d (1 + z)



F

2L−1−i

d(1 + z)

+ ||Θi+1:j−1 ||F × (Θ1:L − Φ)⊤ Θj+1:L

F



≤ d4 (1 + z)i−1 d(1 + z)2L−1−i + 2d(1 + z)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 polar decomposition of a matrix A consists of a unitary matrix R and a positive
semidefinite matrix P such that A = RP .
Lemma 17 ((Horn & Johnson, 2013)). A is a unitary matrix if and only if all of the (complex)
eigenvalues z of A have magnitude 1.
Lemma 18 ((Horn & Johnson, 2013)). If A is unitary then A is normal.
Lemma 19 ((Horn & Johnson, 2013)). If A is normal with eigenvalues λ1 , ..., λd , the singular
values of A are |λ1 |, ..., |λd |.
Lemma 20. If A is unitary, then A1/L is unitary.
Proof. By induction on i, Ai/L is unitary for all i.

22

Lemma 21. If A is invertible and normal with singular values σ1 , ..., σd , then, for any positive
1/L
1/L
integer L, the singular values of A1/L are σ1 , ..., σd .
Proof. 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.
Lemma 22 ((Horn & Johnson, 2013)). If A = RP is the polar decomposition of A, then the
singular values of A are the same as the singular values of P .
Q
Lemma 23. If σ1 , ..., σd are the principal components of A, and A = L
i=1 Ai is a balanced factor1/L
1/L
ization of A, then then σ1 , ..., σd are the principal components of Ai , for each i ∈ {1, ..., L}.
Proof. The singular values of Ai = Ri Pi are the same as the singular values of Pi , which is similar
to P 1/L , whose singular values are the Lth roots of the singular values of P , which are the same as
the singular values of A.
Lemma 24. If A1 , ..., AL is a balanced factorization of A, then
A=

L
Y

Ai .

i=1

Proof. We have
A = RP
= R1/L R1−1/L P 1/L P 1−1/L
= R1/L R1−1/L P 1/L R−(1−1/L) R1−1/L P 1−1/L
= R1 P1 R1−1/L P 1−1/L
= A1 R1−1/L P 1−1/L
= A1 R1/L R1−2/L P 1/L P 1−2/L
and so on.

23

