Global Convergence of Non-Convex Gradient Descent for
Computing Matrix Squareroot

arXiv:1507.05854v2 [math.NA] 9 Mar 2017

Prateek Jain∗

Chi Jin†

Sham M. Kakade‡

Praneeth Netrapalli§

March 10, 2017

Abstract
While there has been a significant amount of work studying gradient descent techniques for non-convex
optimization problems over the last few years, all existing results establish either local convergence with
good rates or global convergence with highly suboptimal rates, for many problems of interest. In this paper,
we take the first step in getting the best of both worlds – establishing global convergence and obtaining
a good rate of convergence for the problem of computing squareroot of a positive definite (PD) matrix,
which is a widely studied problem in numerical linear algebra with applications in machine learning and
statistics among others.
Given a PD matrix M and a PD starting point U0 , we show that gradient descentwith appropriately
chosen step-size finds an -accurate squareroot of M in O α log( M − U0 2 F /) iterations, where
4

2
(U0 ), σmin (M)})3/2 . Our result is the first to establish global
α = (max{kU0 k22 , kMk2 } / min{σmin
convergence for this problem and that it is robust to errors in each iteration. A key contribution of our
work is the general proof technique which we believe should further excite research in understanding
deterministic and stochastic variants of simple non-convex gradient descent algorithms with good global
convergence rates for other problems in machine learning and numerical linear algebra.

1

Introduction

Given that a large number of problems and frameworks in machine learning are non-convex optimization
problems (examples include non-negative matrix factorization [Lee and Seung, 2001], sparse coding [Aharon
et al., 2006], matrix sensing [Recht et al., 2010], matrix completion [Koren et al., 2009], phase retrieval [Netrapalli et al., 2015] etc.), in the last few years, there has been an increased interest in designing efficient
non-convex optimization algorithms. Several recent works establish local convergence to the global optimum
for problems such as matrix sensing [Jain et al., 2013, Tu et al., 2015], matrix completion [Jain and Netrapalli,
2014, Sun and Luo, 2015], phase retrieval [Candes et al., 2015], sparse coding [Agarwal et al., 2013] and so on
(and hence, require careful initialization). However, despite strong empirical evidence, none of these results
have been able to establish global convergence. On the other hand some other recent works [Nesterov and
Polyak, 2006, Ge et al., 2015, Lee et al., 2016, Sun et al., 2015] establish the global convergence of gradient
descent methods to local minima for a large class of non-convex problems but the results they obtain are
quite suboptimal compared to the local convergence results mentioned above. In other words, results that
have very good rates are only local (and results that are global do not have very good rates).
Therefore, a natural and important question is if gradient descent actually has a good global convergence
rate when applied to specific and important functions that are of interest in machine learning. Apart from
theoretical implications, such a result is also important in practice since a) finding a good initialization might
∗ Microsoft

Research, India. Email:
of California, Berkeley.
‡ University of Washington. Email:
§ Microsoft Research, India. Email:
† University

prajain@microsoft.com
Email: chijin@cs.berkeley.edu
sham@cs.washington.edu
praneeth@microsoft.com

1

be difficult and b) local convergence results are inherently difficult to extend to stochastic algorithms due to
noise.
In this work, we answer the above question in affirmative for the problem of computing square root of
a positive definite (PD) matrix M: i.e., minU0 f (U) where f (U) = kM − U2 k2F . This problem in itself is
a fundamental one and arises in several contexts such as computation of the matrix sign function [Higham,
2008], computation of data whitening matrices, signal processing applications [Kaminski et al., 1971, Carlson,
1990, Van Der Merwe and Wan, 2001, Tippett et al., 2003] and so on.

1.1

Related work

Given the importance of computing the matrix squareroot, there has been a tremendous amount of work in
the numerical linear algebra community focused on this problem [Björck and Hammarling, 1983, Higham,
1986, 1987, 1997, Meini, 2004]. For a detailed list of references, see Chapter 6 in Higham’s book [Higham,
2008].
The basic component of most these algorithms is the Newton’s method to find the square root of a
positive number. Given a positive number m and a positive starting point u0 , Newton’s method gives rise
to the iteration


m
1
ut +
.
(1)
ut+1 ←
2
ut
√
It can be shown that the iterates converge to m at a quadratic rate (i.e., -accuracy in log log 1 iterations).
The extension of this approach to the matrix case is not straight forward due to non commutativity of
matrix multiplication. For instance, if M and Ut were matrices, it is not clear if umt should be replaced
by Ut −1 M or MUt −1 or something else. One approach to overcome this issue is to select U0 carefully
to ensure commutativity through all iterations [Higham, 1986, 1997, Meini, 2004], for example, U0 = M
or U0 = I. However, commutativity is a brittle property and small numerical errors in an iteration itself
can result in loss of commutativity. Although a lot of work since, has focused on designing stable iterations
that are inspired by Eq.(1) [Higham, 1986, 1997, Meini, 2004], and has succeeded in making it robust in
practice, no provable robustness guarantees are known in the presence of repeated errors. Similarly, another
recent approach by Sra [2015] uses geometric optimization to solve the matrix squareroot problem but their
analysis also does not address the stability or robustness to numerical or statistical errors (if we see a noisy
version of M) .
Another approach to solve the matrix square-root problem is to use the eigenvalue decomposition (EVD)
and then take square-root of the eigenvalues. To the best of our knowledge, state-of-the-art computation
complexity for computing the EVD of a matrix (in the
 real arithmetic model of computation) is due to Pan
et al. [1998], which is O nω log n + n log2 n log log 1 for matrices with distinct eigenvalues. Though the
result is close to optimal (in reducing the EVD to matrix multiplication), the algorithm and the analysis are
quite complicated. For instance robustness of these methods to errors is not well understood. As mentioned
above however, our focus is to understand if local search techniques like gradient descent (which are often
applied to several non-convex optimization procedures) indeed avoid saddle points and local minima, and
can guide the solution to global optimum.
As we mentioned earlier, Ge et al. [2015], Lee et al. [2016] give some recent results on global convergence
for general non-convex problems which can be applied to matrix squareroot problem. While Lee et al. [2016]
prove only asymptotic behavior of gradient
descent without any rate, applying the result of Ge et al. [2015]

gives us a runtime of O n10 /poly () 1 , which is highly suboptimal in terms of its dependence on n and .
Finally, we note that subsequent to this work, Jin et al. [2017] proved global convergence results with
almost sharp dimension dependence for a much wider class of functions. While Jin et al. [2017] explicitly
add perturbation to help escape saddle points, our framework does not require perturbation, and shows that
for this problem, gradient descent naturally stays away from saddle points.
1 For


optimization problem of dimension d, Ge et al. [2015] proves convergence in the number of iteration of O d4 , with

2
10
O (d) computation per iteration. In matrix squareroot problem d = n , which gives total O n
dependence.

2

Method

Runtime
O αnω log

Gradient descent (this paper)

1




Stochastic gradient descent [Ge
et al., 2015]


O n10 /poly ()

Newton variants [Higham, 2008]

O nω log log

EVD (algebraic [Pan et al., 1998])

O nω log n + n log2 n log log

EVD (power method [Golub and
Van Loan, 2012])

O n3 log

1


1




1




Global
convergence

Provable
robustness

X

X

X

X

×

×

Not iterative

×

Not iterative

×

Table 1: Comparison of our result to existing ones. Here ω is the matrix multiplication exponent and α is
our convergence rate parameter defined in Eq.(3). We show that our method enjoys global convergence and
is also provably robust to arbitrary bounded errors in each iteration. In contrast, Newton variants only have
local convergence and their robustness to errors in multiple iterations is not known. Robustness of methods
based on eigenvalue decomposition is also not well understood.

1.2

Our contribution

In this paper, we propose doing gradient descent on the following non-convex formulation:
M − U2

min

U∈Rn×n ;U0

2
F

.

(2)

We show that if the starting point U0 is chosen to be a positive definite matrix, our algorithm converges
to the global optimum of Eq.(2) at a geometric rate. In order to state our runtime, we make the following
notation:

4

α=

p



3

max kU0 k2 , kMk2

 ,
p
min σmin (U0 ) , σmin (M)

(3)

where σmin (U0 ) and kU0 k2 are the minimum singular value and operator norm respectively of the starting
point U0 , and σmin (M) and kMk2 are
 those of M.2 Our
 result says that gradient descent converges 
kM−U0 kF
close to the optimum of Eq.(2) in O α log
iterations. Each iteration involves doing only

three
and no inversions or leastsquares. So the total runtime of our algorithm is
 matrix multiplications

kMk
O nω α log  F , where ω < 2.373 is the matrix multiplication exponent[Williams, 2012]. As a byproduct
of our global convergence guarantee, we obtain the robustness of our algorithm to numerical errors for free.
In particular, we show that our algorithm is robust to errors in multiple steps in the
p sense that
 if each step
has an error of at most δ, then our algorithm achieves a limiting accuracy of O α kMk2 δ . Another nice
feature of our algorithm is that it is based purely on matrix multiplications, where as most existing methods
require matrix inversion or solving a system of linear equations. An unsatisfactory part of our result however
is the dependence on α ≥ κ3/2 , where κ is the condition number of M. We prove a lower bound of Ω (κ)
iterations for our method which tells us that the dependence on problem parameters in our result is not a
weakness in our analysis.
Outline: In Section 2, we will briefly set up the notation we will use in this paper. In Section 3, we will
present our algorithm, approach and main results. We will present the proof of our main result in Section 4
and conclude in Section 5. The proofs of remaining results can be found in the Appendix.
3

Algorithm 1 Gradient descent for matrix square root
Input: M, PD matrix U0 , η, T
Output: U
for t = 0, · · · , T − 1 do


Ut+1 = Ut − η Ut 2 − M Ut − ηUt Ut 2 − M
end for
Return UT .

2

Notation

Let us briefly introduce the notation we will use in this paper. We use boldface lower case letters (v, w, . . .)
to denote vectors and boldface upper case letters (M, X, . . .) to denote matrices. M denotes the input matrix
we wish to compute the squareroot of. σi (A) denotes the ith singular value of A. σmin (A) denotes the
kAk2
. κ without an argument
smallest singular value of A. κ (A) denotes the condition number of A i.e., σmin (A)
denotes κ (M). λi (A) denotes the ith largest eigenvalue of A and λmin (A) denotes the smallest eigenvalue
of A.

3

Our Results

In this section, we present our guarantees and the high-level approach for the analysis of Algorithm 1 which
is just gradient descent on the non-convex optimization problem:
M − U2

min

U∈Rn×n ;U0

2
F

.

(4)

We first present a warmup analysis, where we assume that all the iterates of Algorithm 1 commute with
M. Later, in Section 3.2 we present our approach to analyze Algorithm 1 for any general starting point U0 .
We provide formal guarantees in Section 3.3.

3.1

Warmup – Analysis with commutativity

In this section, we will give a short proof of convergence for Algorithm 1, when we ensure that all iterates
commute with M.
p
c
, and U0 is chosen to be kMk2 · I, then Ut
Lemma 3.1. There exists a constant c such that if η < kMk
2
in Algorithm 1 satisfies:
Ut 2 − M

2
F

≤ exp (−2ησmin (M) t) U0 2 − M

2
F

.

p
Proof. Since U0 = kMk2 I has the same eigenvectors as M, it can be seen by induction that Ut has the
same eigenvectors as M for every t. Every singular value σi (Ut+1 ) can be written as



2
σi (Ut+1 ) = 1 − 2η σi (Ut ) − σi (M) σi (Ut ) .

(5)

p
Firstly, this tells us that kUt k2 < 2 kMk2 for every t. Verifying this is easy using induction. The
statement holds for t = 0pby hypothesis.
p Assuming it holds for
p Ut , the induction step follows by considering
the two cases kUt k2 ≤ kMk2 and kMk2 < kUt k2 < 2 kMk2 separately and using the assumption
q
c
that η < kMk
. A similar induction argument also tells us that σi (Ut ) > σi (M)
2 . Eq.(5) can now be used
2

4

to yield the following convergence equation:
2

σi (Ut+1 ) − σi (M)

2
2
= σi (Ut ) − σi (M) · 1 − 4ησi (Ut )


2
2
+4η 2 σi (Ut ) σi (Ut ) − σi (M)

2
2
≤ σi (Ut ) − σi (M) · 1 − 4ησi (Ut )

2
+8η 2 σi (Ut ) kMk2


2
2
σi (Ut ) − σi (M)
≤ 1 − 2ησi (Ut )
2

≤ exp (−ησmin (M)) σi (Ut ) − σi (M) ,
where we used the hypothesis on η in the last two steps. Using induction gives us
2

2

σi (Ut ) − M ≤ exp (−ησmin (M) t) σi (U0 ) − M .
This can now be used to prove the lemma:
Ut 2 − M

2
F

=

X

2

σi (Ut ) − σi (M)

2

i

≤ exp (−2ησmin (M) t)

X

2
2
σi (U0 ) − σi (M)

i

≤ exp (−2ησmin (M) t) U0 2 − M

2
F

.

Note that the above proof crucially used the fact that the eigenvectors of Ut and M are aligned, to reduce
the matrix iterations to iterations only over the singular values.

3.2

Approach

As we begin to investigate the global convergence properties of Eq.(4), the above argument breaks down
due to lack of alignment between the singular vectors of M and those of the iterates Ut . Let us now take a
step back and consider non-convex optimization in general. There are two broad reasons why local search
approaches fail for these problems. The first is the presence of local minima and the second is the presence
of saddle points. Each of these presents different challenges: with local minima, local search approaches
have no way of certifying whether the convergence point is a local minimum or global minimum; while with
saddle points, if the iterates get close to a saddle point, the local neighborhood looks essentially flat and
escaping the saddle point may take exponential time.
The starting point of our work is the realization that the non-convex formulation of the matrix squareroot
problem does not have any local minima. This can be argued using the continuity of the matrix squareroot
function, and this statement is indeed true for many matrix factorization problems. The only issue to be
contended with is the presence of saddle points. In order to overcome this issue, it suffices to show that the
iterates of the algorithm never get too close to a saddle point. More concretely, while optimizing a function
f with iterates Ut , it suffices to show that for every t, Ut always stay in some region D far from saddle
points so that for all U, U0 ∈ D:
k5f (U) − 5f (U0 )kF ≤ L kU − U0 kF
p
k5f (U)kF ≥ ` (f (U) − f∗ ),
5

(6)
(7)

where f∗ = minU f (U), and L and ` are some constants. If we flatten matrix U to be n2 -dimensional
vector, then Eq.(6) is the standard smoothness assumption in optimization, and Eq.(7) is known as gradient
dominated property [Polyak, 1963, Nesterov and Polyak, 2006]. If Eq.(6) and Eq.(7) hold, it follows from
standard analysis that gradient descent with a step size η < L1 achieves geometric convergence with
f (Ut ) − f∗ ≤ exp (−η`t/2) (f (U0 ) − f∗ ) .


Since the gradient in our setting is Ut 2 − M Ut + Ut Ut 2 − M , in order to establish Eq.(7), it suffices to
lower bound λmin (Ut ). Similarly, in order to establish Eq.(6), it suffices to upper bound kUt k2 . Of course,
we cannot hope to converge if we start from a saddle point. In particular Eq.(7) will not hold for any l > 0.
The core of our argument consists of Lemmas 4.3 and 4.2, which essentially establish Eq.(6) and Eq.(7)
respectively for the matrix squareroot problem Eq.(4), with the resulting parameters l and L dependent on
the starting point U0 . Lemmas 4.3 and 4.2 accomplish this by proving upper and lower bounds respectively
on kUt k2 and λmin (Ut ). The proofs of these lemmas use only elementary linear algebra and we believe such
results should be possible for many more matrix factorization problems.

3.3

Guarantees

In this section, we will present our main results establishing that gradient descent on (4) converges to the
matrix square root at a geometric rate and its robustness to errors in each iteration.
3.3.1

Noiseless setting

The following theorem establishes geometric convergence of Algorithm 1 from a full rank initial point.
Theorem 3.2. There exist universal numerical constants c and b
c such that if U0 is a PD matrix and
η < αβc 2 , then for every t ∈ [T − 1], we have Ut be a PD matrix with

cηβ 2 t M − U0 2 F ,
M − Ut 2 F ≤ exp −b
where α and β are defined as
3
p

max kU0 k2 , kMk2

 ,
α=
p
min σmin (U0 ) , σmin (M)


p
4
β = min σmin (U0 ) , σmin (M)


4

Remarks:
• This result implies global geometric convergence. Choosing η = αβc 2 , in order to obtain an accuracy of


kM−U0 2 kF
, the number of iterations required would be O α log
.

• Note that saddle points of (4) must be rank degenerate matrix (σmin (U) = 0) and starting Algorithm 1
from a point close to the rank degenerate surface takes a long time to get away from the saddle surface.
Hence, as U0 gets close to being rank degenerate, convergence rate guaranteed by Theorem 3.2 degrades
3
(as κ (U0 ) ). It is possible to obtain a smoother degradation with a finer analysis, but in the current
paper, we trade off optimal results for a simple analysis.
• The convergence rate guaranteed by Theorem 3.2 also depends on the relative scales of U0 and M (say
2
as measured by kU0 k2 / kMk2 ) and is best if it is close to 1.
• We believe that it is possible to extend our analysis to the case where M is low rank (PSD). In this
case, suppose rank(M) = k, and let U? be the k-dimensional subspace in which M resides. Then,
saddle points should satisfy σk (U> U? ) = 0.
6

A simple corollary of this result is when we choose U0 = λI, where kMk2 ≤ λ ≤ 2 kMk2 (such a λ can be
found in time O n2 Musco and Musco [2015]).
Corollary 3.3. Suppose we choose U0 = λI, where kMk2 ≤ λ ≤ 2 kMk2 . Then M − UT 2


3
kM−U0 2 kF
T ≥ O κ 2 log
.

3.3.2

F

≤  for

Noise Stability

Theorem 3.2 assumes that the gradient descent updates are performed with out any error. This is not
practical. For instance, any implementation of Algorithm 1 would incur rounding errors. Our next result
addresses this issue by showing that Algorithm 1 is stable in the presence of small, arbitrary errors in each
iteration. This will establish the stability of our algorithm in the presence of round-off errors for instance.
Formally, we consider in every gradient step, we incur an error 4t .
The following theorem shows that as long as the errors 4t are small enough, Algorithm 1 recovers the
true squareroot upto an accuracy of the error floor. The proof of the theorem follows fairly easily from that
of Theorem 3.2.
Theorem 3.4. There exist universal numerical constants c and b
c such that the following holds: Suppose U0
is a PD matrix and η < αβc 2 where α and β are defined as before:
3
p

max kU0 k2 , kMk2

 ,
α=
p
min σmin (U0 ) , σmin (M)


p
4
β = min σmin (U0 ) , σmin (M) .


4

Suppose further that k4t k2 <

1
300 ησmin

M − Ut 2

(M)β. Then, for every t ∈ [T − 1], we have Ut be a PD matrix with


≤ exp −b
cηβ 2 t M − U0 2 F
t−1
q
X
2
e−bcηβ (t−s−1) k4s kF .
+ 4 max(kU0 k2 , 3 kMk2 )
F

s=0

Remarks:
• Since the errors above are multiplied
they can be bounded to obtain a
p by a decreasing sequence,

limiting accuracy of O α(kU0 k2 + kMk2 )(sups k4s kF ) .
• If there is error in only the first iteration i.e., 4t = 0 for t 6= 0, then the initial error 40 is attenuated
with every iteration,

M − Ut 2 F ≤ exp −b
cηβ 2 t M − U0 2 F
2

+ 6 max(kU0 k2 , kMk2 )e−bcηβ

2

(t−1)

k40 kF .

That is, our dependence on k40 kF is exponentially decaying with respect to time t. On the contrary,
best known results only guarantees the error dependence on k40 kF will not increase significantly with
respect to time t [Higham, 2008].
3.3.3

Lower Bound

We also prove the following lower bound showing that gradient descent with a fixed step size requires Ω (κ)
iterations to achieve an error of O (σmin (M)).
7

Theorem 3.5. For any value of κ, we can find a matrix M such that,
p an inip for any step size η, there1exists
σmin (M),
tialization U0 that has the same eigenvectors as M, with kU0 k2 ≤ 3 kMk2 and σmin (U0 ) ≥ 10
such that we will have Ut 2 − M F ≥ 14 σmin (M) for all t ≤ κ.
This lemma shows that the convergence rate of gradient descent fundamentally depends on the condition
number κ, even if we start with a matrix that has the same eigenvectors and similar scale as √
M. In this case,
note that the lower bound of Theorem 3.5 is off from the upper bound of Theorem 3.2 by κ. Though we
do not elaborate in this paper, it is possible to formally show that a dependence of κ3/2 is the best bound
possible using our argument (i.e., one along the lines of Section 3.2).

4

Proof Sketch for Theorem 3.2

In this section, we will present the proof of Theorem 3.2. To make our strategy more concrete and transparent,
we will leave the full proofs of some technical lemmas in Appendix A.
At a high level, our framework consists of following three steps:
1. Show all bad stationary points lie in a measure zero set {U|φ(U) = 0} for some constructed potential
function φ(·). In this paper, for the matrix squareroot problem, we choose the potential function φ(·)
to be the smallest singular value function σmin (·).
2. Prove for any  > 0, if initial U0 ∈ D = {U| |φ(U)| > } and the stepsize is chosen appropriately,
then we have all iterates Ut ∈ D . That is, updates will always keep away from bad stationary points.
3. Inside regions D , show that the optimization function satisfies good properties such as smoothness
and gradient-dominance, which establishes convergence to a global minimum with good rate.
Since we can make  arbitrarily small and since {U|φ(U) = 0} is a measure zero set, this essentially establishes
convergence from a (Lebesgue) measure one set, proving global convergence.
We note that step 2 above implies that no stationary point found in the set {U|φ(U) = 0} is a local
minimum – it must either be a saddle point or a local maximum. This is because starting at any point
outside {U|φ(U) = 0} does not converge to {U|φ(U) = 0}. Therefore, our framework can be mostly used
for non-convex problems with saddle points but no spurious local minima.
Before we proceed with the full proof, we will first illustrate the three steps above for a simple, special
case where n = 2 and all relevant matrices are diagonal. Specifically, we choose target matrix M and
parameterize U as:




x 0
4 0
.
,
U=
M=
0 2
0 y
Here x and y are unknown parameters. Since we are concerned with U  0, we see that x, y ≥ 0. The reason
we restrict ourselves to diagonal matrices is so that the parameter space is two dimensional letting us give a
good visual representation of the parameter space. Figures 1 and 2 show the plots of function value contours
and negative gradient flow respectively as a function of x and y.
We will use Figures 1 and 2 to qualitatively establish the three steps in our framework.
√
√
1. From Figure 1, we note that (2, 2) is the global minimum. (2, 0), (0, 2) are saddle points, while
(0, 0) is local maximum. We notice all the stationary points which are not global minima lie on the
surface σmin (U) = 0, that is, the union of x-axis and y-axis.
2. By defining a boundary {U|σmin (U) > c, kUk2 < C} for some small c and large C (corresponding to
the red box in Figure 2), we see that negative gradient flow is pointed inside the box which means that
for any point in the box, performing gradient descent with a small enough stepsize will ensure that all
iterates lie inside the box (and hence keep away from saddle points).
8

3.0

3.0

2.5

2.5

2.0

2.0

1.5

1.5

1.0

1.0

0.5
0.5

0.0
0.0
0.0

0.5

1.0

1.5

2.0

2.5

0.0

3.0

0.5

1.0

1.5

2.0

2.5

3.0

Figure 2: Flow of Negative Gradient

Figure 1: Contour of Objective Functions

3. Inside the red box, Figure 2 shows that negative gradient flow points to the global optimum. Moreover,
we can indeed establish upper and lower bounds on the magnitude of gradients within the red box –
this corresponds to establishing smoothness and gradient dominance respectively.
Together, all the above observations along with standard results in optimization tell us that gradient
descent has geometric convergence for this problem.
We now present a formal proof of our result.

4.1

Location of Saddle Points

We first give a characterization of locations of all the stationary points which are not global minima.
Lemma 4.1. Within symmetric PSD cone {U|U  0}, all stationary points of f (U) = M − U2
are not global minima, must satisfy σmin (U) = 0.

2
F

which

Proof. For any stationary point U0 of f (U) which is not on the boundary {U|σmin (U) = 0}, by linear algebra
calculation, we have:
0 =k∇f (U0 )k2F = k(U02 − M)U0 + U0 (U02 − M)k2F
=h(U02 − M)U0 + U0 (U02 − M),
(U02 − M)U0 + U0 (U02 − M)i
=2Tr([(U02 − M)U0 ]2 ) + 2Tr((U02 − M)2 U02 )
2
≥4σmin
(U0 )kU02 − Mk2F
2
(U) > 0, which gives f (U0 ) =
Therefore, since U0 is not on the boundary of PSD cone, we have σmin
2
M − U02 F 6= 0, thus U0 is global minima.

As mentioned before, note that all the bad stationary points are contained in {U|σmin (U) = 0} which is
a (Lebesgue) measure zero set.
9

4.2

Stay Away from Saddle Surface

Since the gradient at stationary points is zero, gradient descent can never converge to a global minimum if
starting from suboptimal stationary points. Fortunately, in our case, gradient updates will keep away from
bad stationary points. As in next Lemma, we show that as long as we choose suitable small learning rate,
σmin (Ut ) will never be too small.
Lemma 4.2. Suppose η <



1/2
min σmin (U0 ),σmin (M)/10


,
c
3/2
max kU0 k32 ,(3kMk2 )

where c is a small enough constant. Then, for every

t ∈ [T − 1], we have Ut in Algorithm 1 be a PD matrix with
p
λmin (Ut ) ≥ min σmin (U0 ) ,

σmin (M)
10

!
.

It turns out that the gradient updates will not only keep σmin (U) from being too small, but also keep
kUk2 from being too large.
Lemma 4.3. Suppose η <

1
.
10 max(kU0 k22 ,3kMk2 )

For every t ∈ [T − 1], we have Ut in Algorithm 1 satisfying:



q
kUt k2 ≤ max kU0 k2 , 3 kMk2 .
Although kUk2 is not directly related to the surface with bad stationary points, the upper bound on
kUk2 is crucial for the smoothness of function f (·), which gives good convergence rate in Section 4.3.

4.3

Convergence in Saddle-Free Region

So far, we have been able to establish both upper bounds and lower bounds on singular values of all iterates
Ut given suitable small learning rate. Next, we show that when spectral norm of U is small, function f (U)
is smooth, and when σmin (U) is large, function f (U) is gradient dominated.
2

2

Lemma 4.4. Function f (U) = M − U2 F is 8 max{Γ, kMk2 }-smooth in region {U| kUk2 ≤ Γ}. That is,
2
for any U1 , U2 ∈ {U| kUk2 ≤ Γ}, we have:
k∇f (U1 ) − ∇f (U2 )kF ≤ 8 max{Γ, kMk2 }kU1 − U2 kF
2

2

Lemma 4.5. Function f (U) = M − U2 F is 4γ-gradient dominated in region {U|σmin (U) ≥ γ}. That
2
is, for any U ∈ {U|σmin (U) ≥ γ}, we have:
k∇f (U)k2F ≥ 4γf (U)
Lemma 4.4 and 4.5 are the formal versions of Eq.(6) and Eq.(7) in Section 3.2, which are essential in
establishing geometric convergence.
Putting all pieces together, we are now ready prove our main theorem:
Proof of Theorem 3.2. Recall the definitions in Theorem 3.2:
3
p

max
kU
k
,
kMk
4
0 2
2

 ,
α=
p
min σmin (U0 ) , σmin (M)


p
4
β = min σmin (U0 ) , σmin (M)


10

By choosing learning rate η < αβc 2 with small enough constant c. We can satisfy the precondition of
Lemma 4.2, and Lemma 4.3 at same time. Therefore, we know all iterates will fall in region:



q
U kUk2 ≤ max kU0 k2 , 3 kMk2 ,
!)
p
σmin (M)
λmin (U) ≥ min σmin (U0 ) ,
10
Then, apply Lemma 4.4 and Lemma 4.5, we know in this region, function f (U) =
smoothness parameter:
n
n
o
o
2
8 max max kU0 k2 , 3 kMk2 , kMk2 ≤ 24α2/3 β 2

U2 − M

2
F

has

and gradient dominance parameter:

4 min

2
(U0 ),
σmin

σmin (M)
100


≥

β2
25

That is, f (U) in the region is both 24α2/3 β 2 -smooth, and β 2 /25-gradient dominated.
Finally, by Taylor’s expansion of smooth function, we have:
f (Ut+1 ) ≤f (Ut ) + h∇f (Ut ), Ut+1 − Ut i
2

+ 12α2/3 β 2 kUt+1 − Ut kF
2

=f (Ut ) − (η − 12η 2 α2/3 β 2 ) k∇f (Ut )kF
η
2
≤f (Ut ) − k∇f (Ut )kF
2
β2
≤(1 − η )f (Ut )
50
The second last inequality is again by setting constant c in learning rate to be small enough, and the last
inequality is by the property of gradient dominated. This finishes the proof.

5

Conclusion

In this paper, we take a first step towards addressing the large gap between local convergence results with
good convergence rates and global convergence results with highly suboptimal convergence rates. We consider
the problem of computing the squareroot of a PD matrix, which is a widely studied problem in numerical
linear algebra, and show that non-convex gradient descent achieves global geometric convergence with a
good rate. In addition, our analysis also establishes the stability of this method to numerical errors. We
note that this is the first method to have provable robustness to numerical errors for this problem and our
result illustrates that global convergence results are also useful in practice since they might shed light on the
stability of optimization methods.
Our result shows that even in the presence of a large saddle point surface, gradient descent might be
able to avoid it and converge to the global optimum at a linear rate. We believe that our framework and
proof techniques should be applicable for several other nonconvex problems (especially those based on matrix
factorization) in machine learning and numerical linear algebra and would lead to the analysis of gradient
descent and stochastic gradient descent in a transparent way while also addressing key issues like robustness
to noise or numerical errors.
11

References
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, and Praneeth Netrapalli. Learning sparsely used
overcomplete dictionaries via alternating minimization. arXiv preprint, 2013.
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-SVD: An algorithm for designing overcomplete
dictionaries for sparse representation. Signal Processing, IEEE Transactions on, 54(11):4311–4322, 2006.
Åke Björck and Sven Hammarling. A Schur method for the square root of a matrix. Linear algebra and its
applications, 52:127–140, 1983.
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory
and algorithms. Information Theory, IEEE Transactions on, 61(4):1985–2007, 2015.
Neal Carlson. Federated square root filter for decentralized parallel processors. Aerospace and Electronic
Systems, IEEE Transactions on, 26(3):517–525, 1990.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle pointsonline stochastic gradient for
tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pages 797–842, 2015.
Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU Press, 2012.
Nicholas J Higham. Newtons method for the matrix square root. Mathematics of Computation, 46(174):
537–549, 1986.
Nicholas J Higham. Computing real square roots of a real matrix. Linear Algebra and its applications, 88:
405–430, 1987.
Nicholas J Higham. Stable iterations for the matrix square root. Numerical Algorithms, 15(2):227–242, 1997.
Nicholas J Higham. Functions of matrices: theory and computation. Society for Industrial and Applied
Mathematics (SIAM), 2008.
Prateek Jain and Praneeth Netrapalli. Fast exact matrix completion with finite samples. arXiv preprint,
2014.
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating
minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages
665–674. ACM, 2013.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points
efficiently. arXiv preprint arXiv:1703.00887, 2017.
Paul G Kaminski, Arthur E Bryson Jr, and Stanley F Schmidt. Discrete square root filtering: A survey of
current techniques. Automatic Control, IEEE Transactions on, 16(6):727–736, 1971.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems.
Computer, (8):30–37, 2009.
Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in
neural information processing systems, pages 556–562, 2001.
Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent converges to
minimizers. University of California, Berkeley, 1050:16, 2016.
Beatrice Meini. The matrix square root from a new functional perspective: theoretical results and computational issues. SIAM journal on matrix analysis and applications, 26(2):362–376, 2004.
12

Cameron Musco and Christopher Musco. Stronger approximate singular value decomposition via the block
lanczos and power methods. arXiv preprint, 2015.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance.
Mathematical Programming, 108(1):177–205, 2006.
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating minimization.
IEEE Transactions on Signal Processing, 63(18):4814–4826, 2015.
Victor Y Pan, Zhao Q Chen, and Ailong Zheng. The complexity of the algebraic eigenproblem. Mathematical
Sciences Research Institute, Berkeley, page 71, 1998.
BT Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and
Mathematical Physics, 3(4):864–878, 1963.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix
equations via nuclear norm minimization. SIAM review, 52(3):471–501, 2010.
Suvrit Sra. On the matrix square root via geometric optimization. arXiv preprint, 2015.
Ju Sun, Qing Qu, and John Wright.
arXiv:1510.06096, 2015.

When are nonconvex problems not scary?

arXiv preprint

Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via nonconvex factorization. In Foundations
of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 270–289. IEEE, 2015.
Michael K Tippett, Jeffrey L Anderson, Craig H Bishop, Thomas M Hamill, and Jeffrey S Whitaker. Ensemble square root filters*. Monthly Weather Review, 131(7):1485–1490, 2003.
Stephen Tu, Ross Boczar, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix
equations via procrustes flow. arXiv preprint arXiv:1507.03566, 2015.
Ronell Van Der Merwe and Eric Wan. The square-root unscented kalman filter for state and parameterestimation. In Acoustics, Speech, and Signal Processing, 2001. Proceedings.(ICASSP’01). 2001 IEEE
International Conference on, volume 6, pages 3461–3464. IEEE, 2001.
Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of
the forty-fourth annual ACM symposium on Theory of computing, pages 887–898. ACM, 2012.

13

A

Proofs of Lemmas in Section 4

In this section, we restate the Lemmas in Section 4 which were used to prove Theorem 3.2, and present their
proofs.
First, we prove lemmas which show a lower bound and a upper bound on the eigenvalues of the intermediate matrices Ut in Algorithm 1. This shows Ut always stay away from the surface where unwanted
stationary point locate.


√
c min σmin (U0 ), σmin (M)/10


, where c is a small
Lemma A.1 (Restatement of Lemma 4.2). Suppose η <
3/2
max kU0 k32 ,(3kMk2 )
enough constant. Then, for every t ∈ [T − 1], we have Ut be a PD matrix with
!
p
σmin (M)
.
λmin (Ut ) ≥ min σmin (U0 ) ,
10
Proof. We will prove the lemma by induction. The base case t = 0 holds trivially. Suppose the lemma holds
for some t. We will now prove that it holds for t + 1. We have


λmin (Ut+1 ) =λmin Ut − η Ut 2 − M Ut − ηUt Ut 2 − M




3
1
≥λmin
Ut − 2ηUt 3 + λmin
Ut + η(MUt + Ut M)
4
4







3
1
1
=λmin
Ut − 2ηUt 3 + λmin
I + ηM Ut
I + ηM − η 2 MUt M
(8)
4
2
2
When η ≤

1
,
100 max(kU0 k22 ,3kMk2 )

using Lemma 4.3 we can bound the first term as




3
3
σmin (Ut ) − 2ησmin (Ut ) .
(9)
4
Pn
To bound the second term,
any vector w ∈ Rn with kwk2 = 1, let w = i αi vi , where vi is the ith
Pn for
eigenvector of M, and i=1 αi2 = 1. Then:





1
1
I + ηM Ut
I + ηM − η 2 MUt M w
w>
2
2


2
1
2
I + ηM w − η 2 kUt k2 kMwk2
≥λmin (Ut )
2
2
2
n 
n
X
X
1
2
=λmin (Ut )
+ ηλi (M) αi2 − η 2 kUt k2
λi (M) αi2
2
i=1
i=1


n
X
1
2
2
+ ηλi (M) + η 2 λi (M) − η 2 κ (Ut ) λi (M)
=λmin (Ut )
αi2
4
i=1


n
X
1
(ζ1 )
2
2
2
2
2
= σmin (Ut )
αi
+ ησi (M) + η σi (M) − η κ (Ut ) σi (M)
4
i=1




n
X
(ζ2 )
1 1
1 1
≥ σmin (Ut )
αi2
+ ησi (M) ≥ σmin (Ut )
+ ησmin (M) ,
(10)
4 2
4 2
i=1
λmin

3
Ut − 2ηUt 3
4

=

where (ζ1 ) is due √
to the fact that
Ut is a PD matrix, so λmin (Ut ) = σmin (Ut ) ≥ 0, and (ζ2 ) is because since

η≤

min σmin (U0 ), σmin (M)/10


3/2
max kU0 k32 ,(3kMk2 )

≤

1
2κ(Ut )kMk2 ,

2

we have η 2 κ (Ut ) σi (M) ≤ 21 ησi (M).
14

Plugging Eq.(9) and Eq.(10) into Eq.(8), we have:
1
2
λmin (Ut+1 ) ≥ σmin (Ut ) (1 + ησmin (M) − 2ησmin (Ut ) )
2
When σmin (Ut ) ≤

p

σmin (M)/3, we obtain:
p
λmin (Ut+1 ) ≥ σmin (Ut ) ≥ max σmin (U0 ) ,

and when σmin (Ut ) ≥

σmin (M)
10

!
,

p
σmin (M)/3, we have:
2

λmin (Ut+1 ) ≥ σmin (Ut ) (1 − 2ησmin (Ut ) )
≥ σmin (Ut ) (1 −

2
2η kUt k2 )

9
≥
σmin (Ut ) ≥ min σmin (U0 ) ,
10

p

σmin (M)
10

!
.

This concludes the proof.
Lemma A.2 (Restatement of Lemma 4.3). Suppose η <

1
.
10 max(kU0 k22 ,3kMk2 )

For every t ∈ [T − 1], we

have:


q
kUt k2 ≤ max kU0 k2 , 3 kMk2 .
Proof. We will prove the lemma by induction. The base case t = 0 is trivially true. Supposing the statement
is true for Ut , we will prove it for Ut+1 .
Using the update equation of Algorithm 1, we have:


kUt+1 k2 = Ut − η Ut 2 − M Ut − ηUt Ut 2 − M

= I − 2ηUt 2 Ut + ηMUt + ηUt M 2

≤ I − 2ηUt 2 Ut 2 + 2η kMk2 kUt k2 .

2

(11)


The singular values of the matrix I − 2ηUt 2 Ut are exactly (1 − 2ησ 2 ) · σ where σ is a singular value
p
p
p
of Ut . For σ ≤ 2 kMk2 , we clearly have (1 − 2ησ 2 )σ ≤ 2 kMk2 . On the other hand, for σ > 2 kMk2 ,
we have (1 − 2ησ 2 )σ < (1 − 4η kMk2 )σ. Plugging this observation into Eq.(11), we obtain:

2 kMk2 , (1 − 4η kMk2 ) kUt k2 + 2η kMk2 kUt k2
q



q
1
2 kMk2 +
kUt k2 , kUt k2 ≤ max kU0 k2 , 3 kMk2 ,
≤ max
15

kUt+1 k2 ≤ max

q

where we used the inductive hypothesis in the last step. This proves the lemma.
Finally, we prove the smoothness and gradient dominance in above regions.
2

Lemma A.3 (Restatement of Lemma 4.4). For any U1 , U2 ∈ {U| kUk2 ≤ Γ}, we have function f (U) =
2
M − U2 F satisfying:
k∇f (U1 ) − ∇f (U2 )kF ≤ 8 max{Γ, kMk2 }kU1 − U2 kF
15

(12)

Proof. By expanding gradient ∇f (U), and reordering terms, we have:
k∇f (U1 ) − ∇f (U2 )kF
=k(2U1 3 − MU1 − U1 M) − (2U2 3 − MU2 − U2 M)kF
=k2(U1 3 − U2 3 ) − M(U1 − U2 ) − (U1 − U2 )MkF
≤2kMk2 kU1 − U2 kF + 2kU1 3 − U2 3 kF
=2kMk2 kU1 − U2 kF + 2kU1 2 (U1 − U2 ) + U1 (U1 − U2 )U2 + (U1 − U2 )U2 2 kF
≤2kMk2 kU1 − U2 kF + 6ΓkU1 − U2 kF
≤8 max{Γ, kMk2 }kU1 − U2 kF

2

Lemma A.4 (Restatement of Lemma 4.5). For any U ∈ {U|σmin (U) ≥ γ}, we have function f (U) =
2
M − U2 F satisfying:
k∇f (U)k2F ≥ 4γf (U)
(13)
Proof. By expanding gradient ∇f (U), we have:
k∇f (U)k2F = k(U2 − M)U + U(U2 − M)k2F
=h(U2 − M)U + U(U2 − M), (U2 − M)U + U(U2 − M)i
2
≥4σmin
(U)kU2 − Mk2F = 4γf (U)

B

Proof of Theorem 3.4

In this section, we will prove Theorem 3.4. We first state a useful lemma which is a stronger version of
Lemma 4.2
p
p
1
Lemma B.1. Suppose Ut is a PD matrix with kUt k2 ≤ max(kU0 k2 , 3 kMk2 ), and σmin (Ut ) ≥ min(σmin (U0 ) , 10
σmin (M
√
1
4
c min(σmin (U0 ), 10
σmin (M))
√
Suppose further that η <
, where c is a small enough constant and denote Ut+1 =
max(kU0 k2 , 3kMk2 )3/2


Ut − η Ut 2 − M Ut − ηUt Ut 2 − M . Then, Ut+1 is a PD matrix with:

λmin (Ut+1 ) ≥

1+

ησmin (M)
15


min(σmin (U0 ) ,

1p
σmin (M)).
10

Indeed, our proof of Lemma 4.2 already proves this stronger result. Now we are ready to prove Theorem
3.4.
Proof of Theorem 3.4. The proof of the theorem is a fairly straight forward modification of the proof of
Theorem 3.2. We will be terse since for most part we will use the arguments employed in the proofs of
Theorem 3.2 and Lemmas 4.3 and 4.2.
We have the following two claims, which are robust versions of Lemmas 4.3 and 4.2, bounding the spectral
norm and smallest eigenvalue of intermediate iterates. The proofs will be provided after the proof of the
theorem.
Claim B.2. For every t ∈ [T − 1], we have:
kUt k2 ≤ max(kU0 k2 ,
16

q

3 kMk2 ).

Claim B.3. For every t ∈ [T − 1], we have Ut be a PD matrix with
p
σmin (M)
).
σmin (Ut ) ≥ min(σmin (U0 ) ,
10
We prove the theorem by induction. The base case t = 0 holds trivially. Assuming the theorem is true


4
e t+1 =
for t, we will show it for t + 1. Denoting U
Ut − η Ut 2 − M Ut − ηUt Ut 2 − M , we have
M − Ut+1 2

F

e2 − U
e t+1 4t − 4t U
e t+1 − 4t 2
= M−U
t+1
e2
≤ M−U
t+1

F

e t+1
+2 U

2

k4t kF + 4t

F
2
F

.

(14)

Using Claims B.2 and B.3, Lemma 4.3 tells us that
e t+1
U

2

≤ max(kU0 k2 ,

q
3 kMk2 ),

and Theorem 3.2 tells us that
e2
M−U
t+1

F



2
≤ exp −b
cη min(σmin (U0 ) , σmin (M)) M − Ut 2

F

.

Plugging the above two conclusions into (14), tells us that
M − Ut+1 2 F
q


2
≤ exp −b
cη min(σmin (U0 ) , σmin (M)) M − Ut 2 F + 2 max(kU0 k2 , 3 kMk2 ) k4t kF
p
1
+ ησmin (M) min(σmin (U0 ) , σmin (M)) k4t kF
30

2
≤ exp −b
cη min(σmin (U0 ) , σmin (M)) M − U0 2 F
+ 4 max(kU0 k2 ,

q

3 kMk2 )

t
X



2
exp −b
cη min(σmin (U0 ) , σmin (M))(t − s) k4s kF ,

s=0

where we used the induction hypothesis in the last step.
We now prove Claim B.2.
Proof of Claim B.2. Just as in the proof of Lemma 4.3, we will use induction. Assuming the claim is true
for Ut , by update equation


Ut+1 = Ut − η Ut 2 − M Ut − ηUt Ut 2 − M + 4t
We can write out:

I − 2ηUt 2 Ut

+ η kMk2 kUt k2 + η kUt k2 kMk2 + k4t k2 .
(15)
p
Since η < 10 max(kU1 k2 ,kMk ) and kUt k2 ≤ max(kU0 k2 , 3 kMk2 ), note that the singular values of the
2
p
 0 2
matrix I − 2ηUt 2 Ut are exactly (1 − 2ησ 2 ) · σ where σ is a singular value of Ut . For σ ≤ 2 kMk2 ,
p
p
we clearly have (1 − 2ησ 2 )σ ≤ 2 kMk2 . On the other hand, for σ > 2 kMk2 , we have (1 − 2ησ 2 )σ <
(1 − 4η kMk2 )σ. Plugging this observation into (15), we obtain:
q

kUt+1 k2 ≤ max
2 kMk2 , (1 − 4η kMk2 ) kUt k2 + 2η kMk2 kUt k2 + k4t k2
q
≤ max(kU0 k2 , 3 kMk2 ),
kUt+1 k2 ≤

2

proving the claim.
17

We now prove Claim B.3.
Proof of Claim B.3. We will use
pinduction, with the proof following fairly easily using Lemma B.1. Suppose
1
σmin (M)). Denoting
σmin (Ut ) ≥ min(σmin (U0 ) , 10


4
e t+1 =
U
Ut − η Ut 2 − M Ut − ηUt Ut 2 − M ,
Lemma B.1 tells us that


 
p
e t+1 ≥ 1 + ησmin (M) min(σmin (U0 ) , 1 σmin (M)),
σmin U
15
10
which then implies the claim, since
σmin (Ut+1 ) ≥ σmin (Ut+1 ) − k4t k2 ≥ min(σmin (U0 ) ,

C

1p
σmin (M)).
10

Proof of Theorem 3.5

In this section, we will prove Theorem 3.5.
Proof. Consider two-dimensional case, where

kMk2
M=
0



0


σmin (M)

We will prove Theorem 3.5 by considering two cases of step size (where η ≥
separately.
Case 1

: For step size η ≥

1
4kMk2 .

Let β =

1
2ηkMk2

1
4kMk2 ,

or η <

1
4kMk2 )

+ 1, and consider following initialization U0 :

p
β kMk2
U0 = 
0
Since η ≥

1
4kMk2

0
p




σmin (M)

we know β ≤ 3, which satisfies our assumption about U0 and M. By calculation, we have:

U0 (U0 2 − M) + (U0 2 − M)U0 = 

q
3
2(β − 1) β kMk2
0


0

0

and since 2η(β − 1) kMk2 = 1, we have:
p
q
3
β
kMk
−
2η(β
−
1)
β kMk2
2
U1 = U0 − η[U0 (U0 2 − M) + (U0 2 − M)U0 ] = 
0
Then, by induction we can easily show for all t ≥ 1, Ut = U1 , thus Ut 2 − M
18

F

 
0
0
=
0
1

0
1




≥ kMk2 ≥ 41 σmin (M) .

Case 2

: For step size η ≤

1
4kMk2 ,

consider following initialization U0 :
p
kMk2
U0 = 
0



0
1
2


p
σmin (M)

According to the update rule in Algorithm 1, we can easily show by induction that: for any t ≥ 0, Ut is of
form:

p
kMk2
0

Ut = 
p
0
αt σmin (M)
where αt is a factor that depends on t, satisfying 0 ≤ αt ≤ 1 and:
αt+1 = αt [1 + ησmin (M) (1 − αt2 )],
Since η ≤

1
4kMk2 ,

α0 =

1
2

we know:
αt+1 ≤ αt [1 +

1
1
(1 − αt2 )] ≤ αt +
4κ
4κ

Therefore, for all t ≤ κ, we have αt ≤ 34 , and thus Ut 2 − M

19

F

≥ 41 σmin (M).

