arXiv:1607.07837v4 [math.OC] 17 Apr 2017

First Efficient Convergence for Streaming k-PCA:
a Global, Gap-Free, and Near-Optimal Rate∗
Zeyuan Allen-Zhu
zeyuan@csail.mit.edu
Institute for Advanced Study

Yuanzhi Li
yuanzhil@cs.princeton.edu
Princeton University

July 26, 2016†

Abstract
We study streaming principal component analysis (PCA), that is to find, in O(dk) space,
the top k eigenvectors of a d × d hidden matrix Σ with online vectors drawn from covariance
matrix Σ.
We provide global convergence for Oja’s algorithm which is popularly used in practice but
lacks theoretical understanding for k > 1. We also provide a modified variant Oja++ that runs
even faster than Oja’s. Our results match the information theoretic lower bound in terms of
dependency on error, on eigengap, on rank k, and on dimension d, up to poly-log factors. In
addition, our convergence rate can be made gap-free, that is proportional to the approximation
error and independent of the eigengap.
In contrast, for general rank k, before our work (1) it was open to design any algorithm with
efficient global convergence rate; and (2) it was open to design any algorithm with (even local)
gap-free convergence rate in O(dk) space.

1

Introduction

Principle component analysis (PCA) is the problem of finding the subspace of largest variance in
a dataset consisting of vectors, and is a fundamental tool used to analyze and visualize data in
machine learning, computer vision, statistics, and operations research. In the big-data scenario,
since it can be unrealistic to store the entire dataset, it is interesting and more challenging to study
the streaming model (a.k.a. the stochastic online model) of PCA.
Suppose the data vectors x ∈ Rd are drawn i.i.d. from an unknown distribution with covariance
matrix Σ = E[xx> ] ∈ Rd×d , and the vectors are presented to the algorithm in an online fashion.
Following [10, 12], we assume the Euclidean norm kxk2 ≤ 1 with probability 1 (therefore Tr(Σ) ≤ 1)
and we are interested in approximately computing the top k eigenvectors of Σ. We are interested
in algorithms with memory storage O(dk), the same as the memory needed to store any k vectors
in d dimensions. We call this the streaming k-PCA problem.
For streaming k-PCA, the popular and natural extension of Oja’s algorithm originally designed
for the k = 1 case works as follows. Beginning with a random Gaussian matrix Q0 ∈ Rd×k (each
∗
We thank Jieming Mao for discussing our lower bound Theorem 6, and thank Dan Garber and Elad Hazan for
useful conversations. Z. Allen-Zhu is partially supported by a Microsoft research award, no. 0518584, and an NSF
grant, no. CCF-1412958.
†
An earlier version of this paper appeared at https://arxiv.org/abs/1607.07837. This newer version contains
a stronger Theorem 2, a new lower bound Theorem 6, as well as the new Oja++ results Theorem 4 and Theorem 5.

1

entry i.i.d ∼ N (0, 1)), it repeatedly applies
rank-k Oja’s algorithm:

Qt ← (I + ηt xt x>
t )Qt−1 ,

Qt = QR(Qt )

(1.1)

where ηt > 0 is some learning rate that may depend on t, vector xt is the random vector in iteration
t, and QR(Qt ) is the Gram-Schmidt decomposition that orthonormalizes the columns of Qt .
Although Oja’s algorithm works reasonably well in practice, very limited theoretical results are
known for its convergence in the k > 1 case. Even worse, little is known for any algorithm that
solves streaming PCA in the k > 1. Specifically, there are three major challenges for this problem:
1. Provide an efficient convergence rate that only logarithmically depends on the dimension d.
2. Provide a gap-free convergence rate that is independent of the eigengap.
3. Provide a global convergence rate so the algorithm can start from a random initial point.
In the case of k > 1, to the best of our knowledge, only Shamir [18] successfully analyzed the
original Oja’s algorithm. His convergence result is only local and not gap-free.1
Other groups of researchers [3, 9, 12] studied a block variant of Oja’s, that is to sample multiple
vectors x in each round t, and then use their empirical covariance to replace the use of xt x>
t . This
algorithm is more stable and easier to analyze, but only leads to suboptimal convergence.
We discuss them more formally below (and see Table 1):
• Shamir [18] implicitly provided a local but efficient convergence result for Oja’s algorithm,2
which requires a very accurate starting matrix Q0 : his theorem relies on Q0 being correlated
with the top k eigenvectors by a correlation value at least k−1/2. If using random initialization,
this event happens with probability at most 2−Ω(d) .
• Hardt and Price [9] analyzed the block variant of Oja’s,3 and obtained a global convergence
that linearly scales with the dimension d. Their result also has a cubic dependency on the gap
between the k-th and (k + 1)-th eigenvalue which is not optimal. They raised an open question
regarding how to provide any convergence result that is gap-free.
• Balcan et al. [3] analyzed the block variant of Oja’s. Their results are also not efficient and
cubically scale with the eigengap. In the gap-free setting, their algorithm runs in space more
than O(kd), and also outputs more than k vectors.4 For such reason, we do not include their
gap-free result in Table 1, and shall discuss it more in Section 4.
• Li et al. [12] also analyzed the block variant of Oja’s. Their result also cubically scales with
the eigengap, and their global convergence is not efficient.
• In practice, researchers observed that it is advantageous to choose the learning rate ηt to be
high at the beginning, and then gradually decreasing (c.f. [22]). To the best of our knowledge,
there is no theoretical support behind this learning rate scheme for general k.
In sum, it remains open before our work to obtain (1) any gap-free convergence rate in space O(kd),
(2) any global convergence rate that is efficient, or (3) any global convergence rate that has the
optimal quadratic dependence on eigengap.
1

A local convergence rate means that the algorithm needs a warm start that is sufficiently close to the solution.
However, the complexity to reach such a warm start is not clear.
2
The original method of Shamir [18] is an offline one. One can translate his result into a streaming setting and
this requires a lot of extra work including the martingale techniques we introduce in this paper.
3
They are in fact only able to output 2k vectors, guaranteed to approximately include the top k eigenvectors.
4
They require space O((k + m)d) where k + m is the number of eigenvalues in the interval [λk − ρ, 1] for some
“virtual gap” parameter ρ. See our Theorem 2 for a definition. This may be as large as O(d2 ). Also, they output
k + m vectors which are only guaranteed to approximately “contain” the top k eigenvectors.

2

Shamir [17]
Sa et al. [16]

k=1
gapdependent

Li et al. [11]

a

Jain et al. [10]
Theorem 1 (Oja)

k=1
gap-free

Shamir [17]
(Remark 1.3)
Theorem 2 (Oja)
Hardt-Price [9]
Li et al. [12]

k≥1
gapdependent

b

d
gap2

·

1
ε

e
O

d
gap2

·

1
ε

e
O

dλ1
gap2

·

1
ε

e
O

λ1
gap2

·

1
ε

e
O

λ1
gap2

·

1
ε

e
O

d
ρ2

1
ε2

e
O

λ1∼(1+m)
ρ2

e
O

dλk
gap3

·

kλk
gap3

· kd +

·








1
ε



[
·

1
ε

unknown

Shamir [18]
Balcan et al. [3]



e
O

e
O

b

b

Theorem 4 (Oja++ )
Theorem 6 (LB)

2

e
O

d(λ1∼k ) λk
gap3

λ1∼k
gap2

·

e
O

λ1∼k
gap2

·

e
O

Theorem 1 (Oja)

1
ε
1
ε





e
O

Theorem 5 (Oja++ )
Theorem 6 (LB)

λ1∼k+m
ρ2

·

[


1

[

ε

[


1

·ε
[
(when λ1∼k ≥ k/d) c

+k
Ω

1
ε

no

yes

kλk
gap2

·

1
ε




min{1, (λ1∼k +k·λ(k+1)∼(k+m) )}
·k
ρ2

e λ1∼k+m
+O
· 1ε
ρ2
e
O

Theorem 2 (Oja)

k≥1
gap-free

Is It
Local Convergence
“Efficient”?

e 12 · 1
O
[
no
[
gap
ε

e d2 · 1
O
[
no
[
gap
ε

e dλ12 · 1
[
no
O
[
gap
ε

e λ12 · 1
yes
O
gap
ε

e λ12 · 1
yes
O
gap
ε

Global Convergence

Paper



Ω

def

kλk
ρ2

·

1
ε



no
no
no
no
yes
yes

e
O
e
O

yes

·

1
ε2



dλk
gap3

·

1
ε

kλk
gap3

·

ε

O

1
gap2

·

e
O
e
O
e
O
e
O
e
O
e
O

(lower bound)

[

λ1∼(1+m)
ρ2

e
O

(lower bound)
yes

1
ρ2



·

1
ε




1

[
[


1

[

ε


1

2

d(λ1∼k ) λk
gap3

·ε
[
(when λ1∼k ≥ k/d)

λ1∼k 1
gap2 · ε

λ1∼k 1
gap2 · ε
λ1∼k+m
ρ2

·

1
ε

λ1∼k+m
ρ2

·

1
ε




Table 1: Comparison of known results. For gap = λk − λk+1 , every ε ∈ (0, 1) and ρ ∈ (0, 1):

2
“gap-dependent convergence” means kQ>
T ZkF ≤ ε where Z consists of the last d − k eigenvectors.
2
“gap-free convergence” means kQ>
T WkF ≤ ε where W consists of all eigenvectors with eigenvalues ≤ λk − ρ.
a global convergence is “efficient” if it only (poly-)logarithmically depend on the dimension d.
k is the target rank; in gap-free settings m be the largest index so that λk+m > λk − ρ.
def P
• we denote by λa∼b = bi=a λi in this table. Since kxk2 ≤ 1 for each sample vector, we have

•
•
•
•

gap ∈ [0, 1/k],

λi ∈ [0, 1/i],

kgap ≤ kλk ≤ λ1∼k ≤ λ1∼k+m ≤ 1 .

• we use [ to indicate the result is outperformed.
• some results in this table (both ours and prior work) depend on λ1∼k . In principle, this requires the algorithm
to know a constant approximation of λ1∼k upfront. In practice, however, since one always tunes the learning
rate η (for any algorithm in the table), we do not need additional knowledge on λ1∼k .
2

e dλ12 · 1 ) by under a stronger 4-th moment assumption. It slows down at least by a
The result of [11] is in fact O(
ε
gap
factor 1/λ1 if the 4-th moment assumption is removed.
b
2
These results give guarantees on spectral norm kQ>
T Wk2 , so we increased them by a factor k for a fair comparison.
c
If kxt k2 is always 1 then λ1∼k ≥ k/d always holds. Otherwise, even in the rare case of λ1∼k < k/d, their

e k2 λk3 and is still worse than ours.
complexity becomes O
d·gap
a

3

Over Sampling. Let us emphasize that it is often desirable to directly output a d × k matrix QT .
Some of the previous results, such as Hardt and Price [9], or the gap-free case of Balcan et al. [3],
are only capable of finding an over-sampled matrix d × k 0 for some k 0 > k, with the guarantee that
these k 0 columns approximately contain the top k eigenvectors of Σ. However, it is not clear how
to find “the best k vectors” out of this k 0 -dimensional subspace.
Special Case of k = 1. Jain [10] obtained the first convergence result that is both efficient and
global for streaming 1-PCA. Shamir [17] obtained the first gap-free result for streaming 1-PCA,
but his result is not efficient. Both these results are based on Oja’s algorithm, and it remains open
before our work to obtain a gap-free result that is also efficient even when k = 1.
Other Related Results. Mitliagkas et al. [13] obtained a streaming PCA result but in the
restricted spiked covariance model. Balsubramani et al. [4] analyzed a modified variant of Oja’s
algorithm and needed an extra O(d5 ) factor in the complexity.
The offline problem of PCA (and SVD) can be solved via iterative algorithms that are based on
variance-reduction techniques on top of stochastic gradient methods [2, 18] (see also [6, 7] for the
k = 1 case); these methods do multiple passes on the input data so are not relevant to the streaming
model. Offline PCA can also be solved via power method or block Krylov method [14], but since
each iteration of these methods relies on one full pass on the dataset, they are not suitable for
streaming setting either. Other offline problems and efficient algorithms relevant to PCA include
canonical correlation analysis and generalized eigenvector decomposition [1, 8, 21].
Offline PCA is significantly easier to solve because one can (although non-trivially) reduce a
general k-PCA problem to k times of 1-PCA using the techniques of [2]. However, this is not the
case in streaming PCA because one can lose a large polynomial factor in the sampling complexity.

1.1

Results on Oja’s Algorithm

We denote by λ1 ≥ · · · ≥ λd ≥ 0 the eigenvalues of Σ, and it satisfies λ1 + · · · + λd = Tr(Σ) ≤ 1.
We present convergence results on Oja’s algorithm that are global, efficient and gap-free.
Our first theorem works when there is a eigengap between λk and λk+1 :
def

Theorem 1 (Oja, gap-dependent). Letting gap = λk − λk+1 ∈ 0, k1
for every ε, p ∈ (0, 1) define learning rates


1
e
Θ






gap·T0 
kΛ
Λ
1
e
e
e
Θ
T0 = Θ
, T1 = Θ
, ηt =
gap·T1


gap2 p2
gap2
 Θ
1
e
gap·(t−T0 )



def

and Λ =

Pk

i=1 λi

1 ≤ t ≤ T0 ;
T0 < t ≤ T0 + T1 ;
t > T0 + T1 .


∈ 0, 1 ,
5

Let Z be the column orthonormal matrix consisting of all eigenvectors of Σ with values no more
than λk+1 . Then, the output QT ∈ Rd×k of Oja’s algorithm satisfies with probability at least 1 − p:

e T1
it satisfies kZ> QT k2 ≤ ε .
for every6 T = T0 + T1 + Θ
ε

e hides poly-log factors in
Above, Θ

1 1
p , gap

F

and d.

k
In other words, after a warm up phase of length T0 , we obtain a λ1 +···+λ
·
gap2
>
2
the quantity kZ QT kF . We make several observations (see also Table 1):

1
T

convergence rate for

• In the k = 1 case, Theorem 1 matches the best known result of Jain et al. [10].
5
6

The intermediate stage [T0 , T0 + T1 ] is in fact unnecessary, but we add this phase to simplify proofs.

e T1 /ε by making ηt poly-logarithmically dependent on T .
Theorem also applies to every T ≥ T0 + T1 + Ω

4

• In the k > 1 case, Theorem 1 gives the first efficient global convergence rate.

• In the k > 1 case, even in terms of local convergence rate, Theorem 1 is faster than the best
known result of Shamir [18] by a factor λ1 + · · · + λk ∈ (0, 1).

Remark 1.1. The quantity kZ> QT k2F captures the correlation between the resulting matrix QT ∈
Rd×k and the smallest d − k eigenvectors of Σ. It is a natural generalization of the sin-square
quantity widely used in the k = 1 case, because if k = 1 then kZ> QT k2F = sin2 (q, ν1 ) where q is
the only column of Q and ν1 is the leading eigenvector of Σ.
Some literatures instead adopt the spectral-norm guarantee (i.e., bounds on kZ> QT k22 ) as opposed to the Frobenius-norm one. The two guarantees are only up to a factor k away. We choose
to prove Frobenius-norm results because: (1) it makes the analysis significantly simpler, and (2) k
is usually small comparing to d, so if one can design an efficient (i.e., dimension free) convergence
rate for the Frobenius norm that also implies an efficient convergence rate for the spectral norm.
Remark 1.2. Our lower bound later (i.e. Theorem 6) implies, at least when λ1 and λk are within a
constant factor of each other, the local convergence rate in Theorem 1 is optimal up to log factors.
Gap-Free Streaming k-PCA. When the eigengap is small which is usually true in practice, it is
desirable to obtain gap-free convergence [14, 17]. We have the following theorem which answers the
open question of Hardt and Price [9] regarding gap-free convergence rate for streaming k-PCA.
Theorem 2 (Oja, gap-free). For every ρ, ε, p ∈ (0, 1), let λ1 , . . . , λm be all eigenvalues of Σ


def Pk
def Pk+m
that are > λk − ρ, let Λ1 =
i=1 λi ∈ 0, 1 , Λ2 =
j=k+1 λj ∈ 0, 1 , define learning rates


e 1
!
Θ
t ≤ T0 ;



kΛ2

ρ·T
0
k · min{1, Λ1 + p2 }

Λ1 + Λ2
1
e
e
e
Θ ρ·T1
t ∈ (T0 , T0 + T1 ];
T0 = Θ
, T1 = Θ
, ηt =


ρ2 · p2
ρ2
 Θ
1
e
t > T0 + T1 .
ρ·(t−T0 )
Let W be the column orthonormal matrix consisting of all eigenvectors of Σ with values no more
than λk − ρ. Then, the output QT ∈ Rd×k of Oja’s algorithm satisfies with prob. at least 1 − p:

e T1
for every7 T = T0 + T1 + Θ
it satisfies kW> QT k2 ≤ ε .
F

ε

e hides poly-log factors in 1 , 1 and d.
Above, Θ
p ρ

Note that the above theorem is a double approximation. The number of iterations depend both
on ρ and ε, where ε is an upper bound on the correlation between QT and all eigenvectors in W
(which depends on ρ). This is the first known gap-free result for the k > 1 case using O(kd) space.
One may also be interested in single-approximation guarantees, such as the rayleigh-quotient
guarantee. Note that a single-approximation guarantee by definition loses information about the
ε-ρ tradeoff; furthermore, (good) single-approximation guarantees are not easy to obtain.8
We show in this paper the following theorem regarding the rayleigh-quotient guarantee:
Theorem 3(Oja, rayleigh quotient, informal). There exist learning rate choices so that, for every
e 2k 2 , letting qi be the i-th column of the output matrix QT , then
T =Θ
ρ ·p


e
Pr ∀i ∈ [k], qi> Σqi ≥ λi − Θ(ρ)
≥1−p .

e hides poly-log factors in 1 , 1 and d.
Again, Θ
p ρ


e T0 /ε by making ηt poly-logarithmically dependent on T .
Theorem also applies to every T ≥ T0 + Ω
Pointed out by [10], a direct translation from double approximation to a rayleigh-quotient type of convergence
loses a factor on the approximation error. They raised it as an open question regarding how to design a direct proof
without sacrificing this loss. Our next theorem answers this open question (at least in the gap-free case).
7

8

5

Remark 1.3. Before our work, the only gap-free result with space O(kd) is Shamir [17] — but it is
not efficient and only for k = 1. His result is in Rayleigh quotient but not double-approximation.
If the initialization phase is ignored, Shamir’s local convergence rate matches our global one in
Theorem 3. However, if one translates his result into double approximation, the running time loses
a factor ε. This is why in Table 1 Shamir’s result is in terms of 1/ε2 as opposed to 1/ε.

1.2

Results on Our New Oja++ Algorithm

Oja’s algorithm has a slow initialization phase (which is also observed
 in practice [22]). For example,
λ1 +···+λk
1
e
in the gap-dependent case, Oja’s running time O
· k+ ε is dominated by its initialization
ρ2
when ε > 1/k. We propose in this paper a modified variant of Oja’s that initializes gradually.

Our Oja++ Algorithm. At iteration 0, instead putting all the dk random Gaussians into Q0
like Oja’s, our Oja++ only fills the first k/2 columns of Q0 with random Gaussians, and sets the
remaining columns be zeros. It applies the same iterative rule as Oja’s to go from Qt to Qt+1 , but
after every T0 iterations for some T0 ∈ N∗ , it replaces the zeros in the next k/4, k/8, . . . columns
with random Gaussians and continues.9 This gradual initialization ends when all the k columns
become nonzero, and the remaining algorithm of Oja++ works exactly the same as Oja’s.
We provide pseudocode of Oja++ in Algorithm 2 on page 58, and state below its main theorems:

def
1
++
Theorem 4 (Oja++ , gap-dependent, informal). Letting gap = λk − λk+1
 ∈ 0, k , our Oja
k
e λ1 +···+λ
outputs a column-orthonormal QT ∈ Rd×k with kZ> QT k2 ≤ ε in T = Θ
iterations.
2
F

gap ε

++ outputs a column-orthonormal
Theorem 5 (Oja++ , gap-free, informal). Given
 our Oja
 ρ ∈ (0, 1),
λ
+···+λ
e 1 2 k+m iterations.
QT ∈ Rd×k with kW> QT k2F ≤ ε in T = Θ
ρ ε

1.3

Result on Lower Bound

We have the following information-theoretical lower bound for any (possibly offline) algorithm:
Theorem 6 (lower bound, informal). For every integer k ≥ 1, integer m ≥ 0, every 0 < ρ < λ <
1/k, every (possibly randomized) algorithm A, we can construct a distribution µ over unit vectors
with λk+m+1 (Eµ [xx> ]) ≤ λ − ρ and λk (Eµ [xx> ]) ≥ λ. The output QT of A with samples x1 , ..., xT
i.i.d. drawn from µ satisfies




kλ
>
2
E
kW QT kF = Ω
.
x1 ,...,xT ,A
ρ2 · T
(W consists of the last d − (k + m) eigenvectors of Eµ [xx> ].)

Our Theorem 6 (with m = 0 and ρ = gap) implies that, in the gap-dependent setting, the global
convergence rate of Oja++ is optimal up to log factors, at least when λ1 = O(λk ). Our gap-free
result does not match this lower bound. We explain in Section 4 that if one increases the space
from O(kd) to O((k + m)d) in the gap-free case, our Oja++ can also match this lower bound.
9

Zeros columns will remain zero according to the usage of Gram-Schmidt in Oja’s algorithm.

6

2

Preliminaries

We denote by 1 ≥ λ1 ≥ · · · ≥ λd ≥ 0 the eigenvalues of the positive semidefinite (PSD) matrix Σ,
and ν1 , ν2 , . . . , νd the corresponding normalized eigenvectors. Since we assumed kxk2 ≤ 1 for each


def
data vector it satisfies λ1 + · · · + λd = Tr(Σ) ≤ 1. We define gap = λk − λk+1 ∈ 0, k1 . Slightly
abusing notations, we also use λk (M) to denote the k-th largest eigenvalue of an arbitrary M.
def
def
Unless otherwise noted, we denote by V = [ν1 , . . . , νk ] ∈ Rd×k and Z = [νk+1 , . . . , νd ] ∈
Rd×(d−k) . For a given parameter ρ > 0 in our gap-free results, we also define W = [νk+m+1 , . . . , νd ] ∈
Rd×(d−k−m) where m is the largest index so that λk+m > λk −ρ. We write Σ≤k = VDiag{λ1 , . . . , λk }V>
def
and Σ>k = ZDiag{λk+1 , . . . , λd }Z> so Σ = Σ≤k + Σ>k .
For a vector y, we sometimes denote by y[i] or y (i) the i-th coordinate of y. We may use different
notations in different lemmas in order to obtain the cleanest representations; when we do so, we
shall clearly point out inQthe statement of the lemmas.
def
We denote by Pt = ts=1 (I + ηs xs x>
s ) where xs is the s-th data sample and ηs is the learning
def
rate of iteration s. We denote by Q ∈ Rd×k (or Q0 ) the random initial matrix, and by Qt =
10 We use the
QR((I + ηt xt x>
t )Qt−1 ) = QR(Pt Q0 ) the output of Oja’s algorithm for every t ≥ 1.
notation Ft to denote the sigma-algebra generated by xt . We denote F≤t to be the sigma-algebra
generated by x1 , ..., xt , i.e. F≤t = ∨ts=1 Fs . In other words, whenever we condition on F≤t it means
we have fixed x1 , . . . , xt .
For a vector x we denote by kxk or kxk2 the Euclidean norm of x. We write A  B if A, B
are symmetric matrices and A − B is PSD. We denote by kAkS1 the Schatten-1 norm which is the
summation of the (nonnegative) singular values of A. It satisfies the following simple properties:
Proposition 2.1. For not necessarily symmetric matrices A, B ∈ Rd×d we have
(1): Tr(A) ≤ kAkS1

(2): Tr(AB) ≤ kABkS1 ≤ kAkS1 kBk2 .
1/2
(3): Tr(AB) ≤ kAkF kBkF = Tr(A> A)Tr(B> B)
.


Proof. (1) is because Tr(A) = 21 Tr(A + A> ) ≤ 12 kA + A> kS1 ≤ 12 kAkS1 + kA> kS1 = kAkS1 .
(2) is because of (1) and the matrix Holder’s inequality. P
(3) is owing to von Neumann’s trace
inequality (together with Cauchy’s) which says Tr(AB) ≤ i σA,i · σB,i ≤ kAkF kBkF . (Here, we
have noted by σA,i the i-th largest eigenvalue of A and similarly for B.


2.1

A Matrix View of Oja’s Algorithm

The following lemma tells us that, for analysis purpose only, we can push the QR orthogonalization
step in Oja’s algorithm to the end:
Lemma 2.2 (Oja’s algorithm). For every s ∈ [d], every X ∈ Rd×s , every t ≥ 1, every initialization
matrix Q ∈ Rd×k , it satisfies kX> Qt kF ≤ kX> Pt Q(V> Pt Q)−1 kF .

e t = Pt Q, we first observe that for every t ≥ 0, Qt = Q
e t Rt for
Proof of Lemma 2.2. Denoting by Q
k×k
some (upper triangular) invertible matrix Rt ∈ R
(if Rt is not invertible, then the right hand
side of the statement is +∞ so we already done). The claim is true for t = 0. Suppose it holds for
t by induction, then
>
Qt+1 = QR[(I + ηt+1 xt+1 x>
t+1 )Qt ] = (I + ηt+1 xt+1 xt+1 )Qt St

for some St ∈ Rk×k by the definition of Gram-Schmidt. This implies that
e t Rt St = Pt+1 QRt St = Q
e t+1 Rt St = Q
e t+1 Rt+1
Qt+1 = (I + ηt+1 xt+1 x> )Q
t+1

10

The second equality is a simple fact but anyways proved in Lemma 2.2 later.

7

e t Rt . As a result, since
if we define Rt+1 = Rt St . This completes the proof that Qt = Q
>
each Qt is column orthogonal for t ≥ 1, we have kQt Vk2 ≤ 1 and therefore kX> Qt kF ≤
kX> Qt (V> Qt )−1 kF kV> Qt k2 ≤ kX> Qt (V> Qt )−1 kF . Finally,
e t Rt (V> Q
e t Rt )−1 kF ≤ kX> Q
e t (V> Q
e t )−1 kF . 
kX> Qt kF ≤ kX> Qt (V> Qt )−1 kF = kX> Q

Observation. Due to Lemma 2.2, in order to prove our upper bound theorems, it suffices to upper
bound the quantity kX> Pt Q(V> Pt Q)−1 kF for X = W (gap-free) or X = Z (gap-dependent).

3

Overview of Our Proofs and Techniques

Oja’s Algorithm. To illustrate the idea, let us simply focus on the gap-dependent case. Denoting
def
in this section by st = kZ> Pt Q(V> Pt Q)−1 kF , owing to Lemma 2.2, we want to bound st in terms
of xt and st−1 . A simple calculation using the Sherman-Morrison formula gives
h η a 2 i
t t
>
−1
E[s2t ] ≤ (1 − ηt gap) E[s2t−1 ] + E
where at = kx>
(3.1)
t Pt−1 Q(V Pt−1 Q) k2
1 − η t at
At a first look, E[s2t ] is decaying by a multiplicative factor (1 − ηt gap) at every iteration; however,
this bound could be problematic when ηt at is close to 1 and thus we need to ensure ηt ≤ a1t with
high probability for every step.
>
−1
√One can naively bound at ≤ kPt−1 Q(V Pt−1 Q)
√ k2 ≤ st−1 + 1. However, since st−1 can be
Ω( d) even at t = 1, we must choose ηt ≤ O(1/ d) and the resulting convergence rate will be
not efficient (i.e., proportional to d). This is why most known global convergence results are not
efficient (see Table 1). On the other hand, if one ignores initialization and starts from a point t0
when st0 ≤ 1 is already satisfied, then we can prove a local convergence rate that is efficient (c.f.
[18]). Note that this local rate is still slower than ours by a factor λ1 + · · · + λk .
Our first contribution is the following crucial observation: for a random initial matrix Q, a1 =
>
−1
kx>
1 Q(V Q) k2 is actually quite small.
√ A simple fact on the singular value distribution of inverseWishart distribution √
implies a1 = O( k) with high probability. Thus, at least in the first iteration,
we can set η1 = Ω(1/ k) independent of the dimension d. Unfortunately, in subsequent iterations,
it is not clear whether at remains small or increases.
Our second contribution is to control at using the fact that at itself “forms another random
>
−1
process.” More precisely, denoting by at,s = kx>
t Ps Q(V Ps Q) k2 for 0 ≤ s ≤ t − 1, we wish
to bound at,s in terms of at,s−1 and show that it does
√ not increase by much. (If we could achieve
so, combining it with the initialization at,0 ≤ O( k), we would know that all at,s are small for
s ≤ t − 1.) Unfortunately, since xt is not an eigenvector of Σ, the recursion looks like
h
2 i
η a
E[a2t,s ] ≤ (1 − ηs λk ) E[a2t,s−1 ] + ηs λk E[b2t,s−1 ] + E 1−ηs ss,s−1
(3.2)
as,s−1
>
−1
where bt,s = kx>
t ΣPs Q(V Ps Q) k2 . Now three difficulties arise from formula (3.2):

• bt,s can be very different from at,s — in worse case, the ratio between them can be unbounded.

• the problematic term now becomes as,s−1 (rather than the original at = at,t−1 in (3.1)) which
t−1
is not present in the chain {at,s }s=1
.

• since bt,s differs from at,s by an additional factor Σ in the middle, to analyze bt,s , we need to
2
>
−1
further study kx>
t Σ Ps Q(V Ps Q) k2 and so on.
(i)

def

We solve these issues by carefully considering a multi-dimensional random process ct,s with ct,s =
i
>
−1
kx>
t Σ Ps Q(V Ps Q) k2 . Ignoring the last term, we can derive that
 (i) 2 
 (i) 2 
 (i+1) 2 
∀t, ∀s ≤ t − 1, E ct,s
/ (1 − ηs λk ) E ct,s−1
+ ηs λk E ct,s−1
.
(3.3)
8

Our third contribution is a new random process concentration bound to control the change in
this multi-dimensional chain (3.3). To achieve this, we adapt the prove of standard Chernoff bound
to multi dimensions (which is not the same as matrix concentration bound). After establishing
(0)
this non-trivial concentration result, all terms of at = ct,t−1 can be simultaneously bounded by a
constant. This ensures that the problematic term in (3.1) is well-controlled.
The overall plan looks promising; however, there are holes in the above thought experiment.
• In order to apply a random-process concentration bound (e.g., Azuma concentration), we need
the process to not depend on the future. However, the random vector ct,s is not F≤s measurable
but F≤s ∨ Ft measurable (i.e., it depends on xt for a future t > s).
• Furthermore, the expectation bounds such as (3.1), (3.2), (3.3) only hold if E[xt xt ] = Σ;
however, if we take away a failure event C —C may correspond to the event when at is large—
the conditional expectation E[xt xt | C] becomes Σ + ∆ where ∆ is some error matrix. This
can amplify the failure probability in next iteration.

Our fourth contribution is a “decoupling” framework to deal with the above issues (Appendix i.D).
At a high level, to deal with the first issue we fix xt and study {ct,s }s=0,1,...,t−1 conditioning on xt ;
in this way the process decouples and each ct,s becomes F≤s measurable. We can do so because
we can carefully ensure that the failure events only depend on xs for s ≤ t − 1 but not on xt . To
deal with the second issue, we convert the random process into an unconditional random process
(see (i.D.2)); this is a generalization of using stopping time on martingales. Using these tools, we
manage to show that the failure probability only grows linearly with respect to T and henceforth
(i)
bound the value of ct,s for all t, s and i.
we are able to show that Oja’s algorithm achieves convergence rate
Putting them together,

λ1 +...+λk 1
e
O
( ε + k) . The rate matches our lower bound asymptotically when λ1 and λk are
gap2
within a constant factor of each other, however, if we only care about crude approximation of the
eigenvectors (e.g. for constant ε), then the Oja’s algorithm is off by a factor k.
Remark 3.1. The ideas above are insufficient for our gap-free results. To prove Theorem 2 and 3, we
def
also need to bound quantities s0t = kW> Pt Q(V> Pt Q)−1 kF where W consists of all eigenvectors
of Σ with values no more than λk − ρ. This is so because the interesting quantity in a gap-free case
changes from st to s0t according to Lemma 2.2. Now, to bound s0t one has to bound ct,s ; however,
the ct,s process still depends on the original st as opposed to s0t . In sum, we unavoidably have to
bound st , s0t , and ct,s all together, making the proofs even more sophisticated.
Our Oja++ Algorithm. The factor k in Oja’s
√ algorithm comes from the fact that
√ the earlier
> Q)−1 k is at least Ω( k) at t = 1, so we must set η ≤ O(1/ k) and this
quantity a1 = kx>
Q(V
2
1
1
incurs a factor k in the running time. After warm start, at drops to O(1) and we can choose ηt ≤ 1.
A similar issue was also observed by Hardt and Price [9] and they solved it using “oversampling”. Namely, to put it into our setting, we can use a d × 2k random starting matrix Q0 and
run Oja’s to produce QT ∈ Rd×2k . In this way, the quantity a1 becomes O(1) even at the beginning
due to some property of the inverse-Wishart distribution. However, the output QT is now a 2k
dimensional space that is only guaranteed to “approximately contain” the top k eigenvectors. It is
not clear how to find this k-subspace (recall the algorithm does not see Σ).
Our key observation behind Oja++ is that a similar effect also occurs via “under-sampling”.
If we initialize Q0 randomly with dimension d × k/2, we can also obtain a speed-up factor of k.
Unlike Hardt and Price, this time the output QT0 is a k/2-dimensional subspace that approximately
lies entirely in the column span of V ∈ Rd×k .
9

After getting QT0 , one could hope to get the rest by running the same algorithm again, but
restricted to the orthogonal complement of QT0 . This approach would work if QT0 were exactly
the eigenvectors of Σ; however, due to approximation error, this approach would eventually lose a
factor 1/gap in the sample complexity which is even bigger than the factor k that we could gain.
Instead, our Oja++ algorithm is divided into log k epochs. At each epoch i = 1, 2, . . . , log k, we
attach k/2i new random columns to the working matrix Qt in Oja’s algorithm, and then run Oja’s
for a fixed number of iterations. Note that every time (except the last time) we attach new random
columns, we are in an “under-sampling” mode because if we add k/2i columns there must be k/2i
remaining dimensions. This ensures that the quantity at only increases by a constant so we have
at = O(1) throughout
execution
of Oja++ . Finally, there are only log k epochs so the total running


k 1
e λ1 +...+λ
e
time is still O
ε and this O notion hides a log k factor.
ρ2

Roadmap. Our proofs are highly technical so we carefully choose what to present in this main
body. In Section 5 we state properties of the initial matrix Q which corresponds to our first
contribution. In Section 6 we provide expected guarantees on st , s0t and at,s and they correspond
to our second contribution. The third (martingale lemmas) and fourth contributions (decoupling
lemma) are deferred to the appendix.
Most importantly, in Section 7 we present (although in weaker forms) two Main Lemmas to
deal with the convergence one for t ≤ T0 (before warm start) and one for t > T0 (after warm start).
These sections, when put together, directly imply two weaker variants of Theorem 1 and 2. We
state these weaker variants in Appendix i and include all the mathematical details there.
Appendix ii includes our Rayleigh quotient Theorem 3 and lower bound Theorem 6. Appendix
iii strengthens the main lemmas into their stronger forms, and prove Theorem 1 and 2 formally.
Our Oja++ results, namely Theorem 4 and 5, are also proved in Appendix iii.
In Figure 1 on page 14, we present a dependency graph of all of our main theorems and lemmas.
We hope that the readers could appreciate our organization of this paper.

4

Discussions, Extensions and Future Directions

In this paper we give global convergence analysis of the Oja’s algorithm, and a twisted version Oja++
which has better complexity. We also give an information-theoretic
bound
that
 showing
 lower
 any
kλk
>
2
algorithm, offline or online, must have final accuracy Ex1 ,...,xT ,A kW QT kF = Ω gap2 ·T . This
matches our gap-dependent result on Oja++ when λ1 + · · · + λk = O(kλk ); that is, when there is
an eigengap and when “the spectrum is flat.”
When the spectrum is not flat, our algorithm can be improved to have better accuracy. However,
this requires good prior knowledge of λ1 , · · · λk , and may not be realistic.

λ +···λ
In the gap-free case, Oja++ only achieves accuracy O 1 ρ2 ·Tk+m , which appears worse than


λ1 +···λk
k
the lower bound O ρkλ
if we allow more space, namely,
2 ·T . In fact, we can also achieve O
ρ2 ·T
space up to O((k + m)d) as opposed to O(kd). More generally, we have a space-accuracy tradeoff.
If we run Oja++ on k 0 initial random vectors, and thus using space O(dk 0 ) for k 0 ∈ [k, k + m],
we can randomly pick k columns from the output and have the following accuracy:
Theorem 4.1 (tradeoff). For every k 0 ∈ [k, k + m] with λk0 − λk+m ≥
0

ρ
log d ,

0

let Q ∈ Rd×k be a

random gaussian matrix and QT ∈ Rd×k be the output of Oja++ with random input Q. Then,
letting Q0T ∈ Rd×k be k random columns of QT (chosen uniformly at random), we have




k λ1 + · · · λk+m0
> 0 2
e
E kW QT kF = O
k0
ρ2 T
10

where m0 ≤ m is any index satisfying λk0 − λk+m0 ≥

ρ
log d .

Proof of Theorem 4.1. Observethat Oja++ guarantees (using ρ/ log d instead of ρ as the gap-free
k+m0
e λ1 +···λ
parameter) E[kW> QT k2F ] = O
. Then, k random columns of Q0T decreases the squared
ρ2 T



Frobenius norm by a factor of k 0 /k.

We also have the following crucial observation:
Corollary 4.2. There exists k 0 ∈ [k, k + m] such that λk0 − λk+m ≥

ρ
log d

and

k
(λ1 + · · · λk+m0 ) = O (λ1 + · · · λk ) .
k0

Proof of Corollary 4.2. The
is by counting.
Divide [λk − ρ, λk] into log d intervals of equal
 proof

ρ
ρ
span in descending order λk − log d , λk , λk − 2 log d , λk − logρ d , · · · , λk − ρ, λk − 1 − log1 d ρ , and
let Si ⊆ {k + 1, .P
. . , k + m} be the indices of λj is in the i-th interval above,P
for i = 1, 2, . . . , log d.
Define Λi = j∈Si λj and Λ0 = Λ = λ1 + · · · λk . Also define ki = k + 1≤j<i |Sj |. We then
P
have, for every k 0 = ki , we can choose m0 such that λ1 + · · · λk+m0 = Λ + ij=1 Λj . By Λ0 ≤ dΛlog d ,
we know that there must exist some i such that Λi ≤ 100Λi−1 . We compute



Pi
Pi−1 
k
k
k
Λ
≤
100
Λ
+
Λ
+
j
j=1
j=1 Λi = 100 ki (λ1 + · · · + λki ) ≤ 100Λ
ki
ki



so we have found such k 0 satisfying the statement.

++ to at most O((k + m)d), we can
In sum. In the gap-free case,
 if we increase the space of Oja
λ1 +···λk
achieve accuracy O ρ2 ·T , and thus match the lower bound when the spectrum is flat.11
It was also studied by Balcan et al. [3] that increasing the space could enhance the performance.
However, their algorithm always uses space Ω((k + m)d), and furthermore, in the Frobenius-norm
accuracy, their performance is always worse than Oja++ , not to say Oja++ only uses space O(kd).12
k
It is an important future direction to directly get O λ1ρ+···λ
without increasing the space.
2 ·T

Matrix Bernstein. Using matrix Bernstein and a gap-free variant of the Wedin theorem [2], one
can
QT be the top-k eigenvectors of the empirical covariance matrix
PT show>that, if we simply let >
e λ21 . If one directly translates this to a Frobenius
x
x
,
then
we
have
E[kW
QT k22 ] = O
t=1 t t
ρ T

λ1 k
>
2
e
norm bound, it gives E[kW QT kF ] = O ρ2 T and is worse than ours. However, our result, if
naively translated to spectral norm, also loses a factor k. It is a future direction to directly get a
spectral-norm guarantee for streaming PCA.

5

Random Initialization

We state our main lemma for initialization. Let Q ∈ Rd×k be a matrix with each entry i.i.d drawn
from N (0, 1), the standard gaussian.
Lemma 5.1 (initialization). For every p, q ∈ (0, 1), every T ∈ N∗ , every distribution on vector set
{xt }Tt=1 with kxt k2 ≤ 1, with probability at least 1 − p − 2q over the random choice of Q:

2
ln dp
and
 (Z> Q)(V> Q)−1 F ≤ 576dk
p2


1/2 
i−1
18
T
> (Σ/λ
> Q)−1
 Prx1 ,...,xT ∃i ∈ [T ], ∃t ∈ [T ], x>
2k
ln
≤q
ZZ
)
Q(V
≥
k+1
t
p
q
2

0

Of course, this requires the algorithm to know k which can be done by trying k0 = k + 2, k + 4, k + 8, etc.
2


12
e λ1∼k+m
e dk(λ1∼k+m3 ) λk , but ours is only O
.
For instance, when λ1∼k+m ≥ k+m , their global convergence is O
2
11

d

(k+m)ρ T

11

ρ T

(i)

The two statements of the above lemma correspond to s0 and ct,0 that we defined in Section 3. The
second statement is of the form “Pr[event] ≤ q” instead of “for every fixed xt , event holds with
probability ≤ q” because we cannot afford taking union bound on xt .

6

Expected Results

We now formalize inequalities (3.1), (3.2), (3.3) which characterize to the behavior of our target
random processes. Let X ∈ Rd×r be a generic matrix that shall later be chosen as either X = W
(corresponding to s0t ), X = Z (corresponding to st ), or X = [w] for some vector w (corresponding
(i)
to ct,s ). We introduce the following notions that shall be used extensively:
Lt = Pt Q(V> Pt Q)−1 ∈ Rd×k

r×k
R0t = X> xt x>
t Lt−1 ∈ R

St = X> Lt ∈ Rr×k

k×k
H0t = V> xt x>
t Lt−1 ∈ R

Lemma 6.1 (Appendix i.B). For every t ∈ [T ], suppose C≤t is an event on random x1 , . . . , xt and
1
>
>
−1
C≤t implies kx>
,
t Lt−1 k2 = kxt Pt−1 Q(V Pt−1 Q) k2 ≤ φt where ηt φt ≤
2

 >
and suppose Ext xt xt | F≤t−1 , C≤t = Σ + ∆. Then, we have:
(a) When X = Z,
h
i
2 2
E Tr(S>
S
)
|
F
,
C
≤ (1 − 2ηt gap + 14ηt2 φ2t )Tr(St−1 S>
t
≤t−1
≤t
t
t−1 ) + 10ηt φt

3/2

1/2 
>
+ 2ηt k∆k2 Tr(S>
+ 2Tr(S>
t−1 St−1 )
t−1 St−1 ) + Tr(St−1 St−1 )
(b) When X = W,
h
i
2 2
>
2 2
E Tr(S>
t St ) | F≤t−1 , C≤t ≤ (1 − 2ηt ρ + 14ηt φt )Tr(St−1 St−1 ) + 10ηt φt


1/2

1/2 
+ 2ηt k∆k2 Tr(S>
+ Tr(S>
1 + Tr(Z> Lt−1 L>
t−1 St−1 )
t−1 St−1 )
t−1 Z)

(c) When X = [w] ∈ Rd×1 where w is a vector with Euclidean norm at most 1,
h
i

ηt
2 2
>
2 2
kw> ΣLt−1 k22
E Tr(S>
t St ) | F≤t−1 , C≤t ≤ 1 − ηt λk + 14ηt φt Tr(St−1 St−1 ) + 10ηt φt +
λk


1/2

1/2 
>
>
>
+ 2ηt k∆k2 Tr(S>
S
)
+
Tr(S
S
)
1
+
Tr(Z
L
L
Z)
t−1 t−1
t−1 t−1
t−1 t−1

The above three expectation results will be used to provide upper bounds on the quantities we
(i)
care about (i.e., st , s0t , ct,s ). In the appendix, to enable proper use of martingale concentration,

>
>
we also bound their absolute changes |Tr(S>
t St ) − Tr(St−1 St−1 )| and variance E |Tr(St St ) −
>
2
13
Tr(St−1 St−1 )| in changes.

7

Main Lemmas

Our main lemmas in this section can be proved by combining (1) the expectation results in Section 6,
(2) the martingale concentrations in Appendix i.C, and (3) our decoupling lemma in Appendix i.D.
13

Recall that even in the simplest martingale concentration, one needs upper bounds on the absolute difference
between consecutive variables; furthermore, the concentration can be tightened if one also has an (expected) variance
upper bound between variables.

12

Our first lemma describes the behavior of quantities st = kZ> Pt Q(V> Pt Q)−1 kF and s0t =
kW> Pt Q(V> Pt Q)−1 kF before warm start. At a high level, it shows if the st sequence starts
from s20 ≤ ΞZ , under mild conditions, s2t never increases to more than 2ΞZ . Note that ΞZ = O(d)
according to Lemma 5.1. The other sequence (s0t )2 also never increases to more than 2ΞZ because
s0t ≤ st , but most importantly, (s0t )2 drops below 2 after t ≥ T0 . Therefore, at point t = T0 we need
to adjust the learning rate so the algorithm achieves best convergence rate, and this is the goal of
our Lemma Main 2. (We emphasize that although we are only interested in st and s0t , our proof of
the lemma also needs to bound the multi-dimensional ct,s sequence discussed in Section 3.)

Lemma Main 1 (before warm start). For every ρ ∈ (0, 1), q ∈ 0, 12 , ΞZ ≥ 2, Ξx ≥ 2, and fixed
matrix Q ∈ Rd×k , suppose it satisfies
• kZ> Q(V> Q)−1 k2F ≤ ΞZ , and
h
j−1
>
Q(V> Q)−1
• Prxt ∀j ∈ [T ], x>
t ZZ (Σ/λk+1 )

Suppose also the learning rates {ηs }s∈[T ] satisfy
(1):

3/2

∀s ∈ [T ], qΞZ ≤ ηs ≤

ρ
4000Ξ2x ln

(3):

24T
q2

2

i
≤ Ξx ≥ 1 − q 2 /2 for every t ∈ [T ].
(2):

PT

∃T0 ∈ [T ] such that

2 2
t=1 ηt Ξx

PT0

t=1 ηt

≤

1
100 ln

≥

ln(3ΞZ )
ρ

32T
q2

.

Then, for every t ∈ [T − 1], with probability at least 1 − 2qT (over the randomness of x1 , . . . , xt ):
• kZ> Pt Q(V> Pt Q)−1 k2F ≤ 2ΞZ , and

• if t ≥ T0 then kW> Pt Q(V> Pt Q)−1

2
F

≤ 2.

Our second lemma asks for a stronger assumption on the learning rates and shows that after
warm start (i.e., for t ≥ T0 ), the quantity (s0t )2 scales as 1/t.
√
Lemma Main 2 (after warm start). In the same setting as Lemma Main 1, if there exists δ ≤ 1/ 8
s.t.
T0
1
1
9 ln(8/q 2 )
, ∀s ∈ {T0 +1, . . . , T } : 2ηs ρ−56ηs2 Ξ2x ≥
and ηs ≤
≥
,
2
2
δ
s−1
20(s − 1)δΞx
ln T0
then, with probability at least 1 − 2qT (over the randomness of x1 , . . . , xT ):
• kZ> Pt Q(V> Pt Q)−1 k2F ≤ 2ΞZ for every t ∈ {T0 , . . . , T }, and
• kW> Pt Q(V> Pt Q)−1 k2F ≤

5T0 / ln2 (T0 )
t/ ln2 t

for every t ∈ {T0 , . . . , T }.

Parameter 7.1. There exist constants C1 , C2 , C3 > 0 such that for every q > 0 that is sufficiently
small (meaning q < 1/poly(T, ΞZ , Ξx , 1/ρ)), the following parameters satisfy both Lemma Main 1
and Lemma Main 2:
(
ln ΞZ
Ξ2x ln Tq ln2 ΞZ
t ≤ T0 ;
ρ
T0
T0 ·ρ
, and δ = C3 ·
=
C
·
,
η
=
C
·
.
1
t
2
1
2
2
t > T0 .
ρ
Ξx
ln (T0 )
t·ρ
Using such learning rates for our main lemmas, one can prove in one page (see Appendix i.F)
• a weaker version of Theorem 2 where (Λ1 , Λ2 ) are replaced by (1, 0), and
• a weaker version of Theorem 1 where Λ = λ1 + · · · + λk is replaced by 1.

13

Appendix Overview
Main Lemma Appendix ii.G
Lower Bound
Theorem 6

Rayleigh Quotient
Theorem 3

(before warm start)
Lemma Main 3

Appendix ii
upgrade

Appendix i
Expectation Lemma
Lemma 6.1 and Appendix i.B

upgra

Main Lemma Appendix i.E

de

Oja (GF, weak)
Theorem 2’

Decoupling Lemma
Appendix i.D

(after warm start)
Lemma Main 2

Oja (GD, weak)
Theorem 1’

Initialization Lemma
Lemma 5.1
Appendix i.A

rade

(before warm start)
Lemma Main 1

upg

Martingale Lemma
Appendix i.C

upgrade

u p grade

Appendix iii

Main Lemma Appendix iii.L
(before warm start)
Lemma Main 4

(after warm start)
Lemma Main 5

Expectation Lemma
Appendix iii.K

(under sampling)
Lemma Main 6

Oja (GF)
Theorem 2
Oja (GD)
Theorem 1

Initialization Lemma
Lemma iii.J.2
Appendix iii.J

Oja++ (GF)
Theorem 5
Oja++ (GD)
Theorem 4

Figure 1: Overall structure of this paper. GF and GD stand for gap-free and gap-dependent respectively.

We divide our appendix sections into three parts, Appendix i, ii, and iii.
• Appendix i (page 16) provides complete proof but for two weaker versions of our Theorem 1
and 2.
– Appendix i.A and i.B give missing proofs for Section 5 and 6;
– Appendix i.C and i.D provide details for our martingale and decoupling lemmas;
– Appendix i.E proves main lemmas in Section 7 and Appendix i.F puts everything together.
• Appendix ii (page 35) includes proofs for Theorem 6 and Theorem 3.
– Appendix ii.G extends our main lemmas to better serve for the rayleigh quotient setting;
14

– Appendix ii.H provides the final proof for our Rayleigh Quotient Theorem 3;
– Appendix ii.I includes a three-paged proof of our lower bound Theorem 6.
• Appendix iii (page 42) provide full proofs not only to the stronger Theorem 1 and Theorem 2
for Oja’s algorithm, but also to Theorem 4 and Theorem 5 for Oja++ .
–
–
–
–
–

Appendix
Appendix
Appendix
Appendix
Appendix

iii.J extends our initialization lemma in Appendix i.A to stronger settings;
iii.K extends our expectation lemmas in Appendix i.B to stronger settings;
iii.L extends our main lemmas in Appendix i.E to stronger settings;
iii.M provides the final proofs for our Theorem 1 and Theorem 2;
iii.N provides the final proofs for our Theorem 4 and Theorem 5.

We include the dependency graphs of all of our main sections, lemmas and theorems in Figure 1
for a quick reference.

15

Appendix (Part I)
In this Part I of the appendix, we provide complete proof but two weaker versions of our
Theorem 1 and 2. We state these weaker versions Theorem 1’ and 2’ here, and meanwhile:
• Appendix i.A and i.B give missing proofs for Section 5 and 6;

• Appendix i.C and i.D provide details for our martingale and decoupling lemmas;
• Appendix i.E proves main lemmas in Section 7; and

• Appendix i.F puts everything together and proves Theorem 1’ and 2’.

def
Theorem 1’ (gap-dependent streaming k-PCA). Letting gap = λk − λk+1 ∈ 0, k1 , for every
ε, p ∈ (0, 1) define learning rates
 



1
e

Θ gap·T0
1 ≤ t ≤ T0 ;
k
e


T0 = Θ
, ηt =
2
2
1
e
 Θ
gap · p
t > T0 .
gap·t
Let Z be the column orthonormal matrix consisting of all eigenvectors of Σ with values no more
than λk+1 . Then, the output QT ∈ Rd×k of Oja’s algorithm satisfies with prob. at least 1 − p:
 
T0
e
for every T = T0 + Θ
it satisfies kZ> QT k2F ≤ ε .
ε
e hides poly-log factors in 1 , 1 and d.
Above, Θ
p gap

Theorem 2’ (gap-free streaming k-PCA). For every ρ, ε, p ∈ (0, 1), define learning rates
 



1
e
 Θ
t ≤ T0 ;
k
0
e
 ρ·T
T0 = Θ
, ηt =
2
2
e 1
 Θ
ρ ·p
t > T0 .
ρ·t

Let W be the column orthonormal matrix consisting of all eigenvectors of Σ with values no more
than λk − ρ. Then, the output QT ∈ Rd×k of Oja’s algorithm satisfies with prob. at least 1 − p:
 
T0
e
for every T = T0 + Θ
it satisfies kW> QT k2F ≤ ε .
ε
e hides poly-log factors in 1 , 1 and d.
Above, Θ
p ρ

16

i.A

Random Initialization (for Section 5)

Recall that Q ∈ Rd×k is a matrix with each entry i.i.d drawn from N (0, 1), the standard gaussian.

i.A.1

Preparation Lemmas

Lemma i.A.1. For every x ∈ Rd that has Euclidean norm kxk2 ≤ 1, every PSD matrix A ∈ Rk×k ,
and every λ ≥ 1, we have


− λ
Pr x> ZZ> QAQ> ZZ> x ≥ Tr(A) + λ ≤ e 8Tr(A) .
Q

Proof of Lemma i.A.1. Let A = UΣA U> be the eigendecomposition of A, and we denote by
Qz = Z> QU ∈ R(d−k)×d . Since a random Gaussian matrix is rotation invariant, and since U is
unitary and Z is column orthonormal, we know that each entry of Qz draw i.i.d. from N (0, 1).
Next, since we have kZ> xk2 ≤ 1, it satisfies that y = x> ZZ> QU is a vector with each coordinate
i independently drawn from distribution N (0, σi ) for σi ≤ 1. This implies
x> ZZ> QAQ> ZZ> x = y > ΣA y =
P

)2

k
X
[ΣA ]i,i (yi )2 .

i=1
distribution14

is a subexponential
with parameter (σ 2 , b) where σ 2 , b ≤
Now,
i∈[k] [ΣA ]i,i (yi
Pk
4 i=1 [ΣA ]i,i . Using the subexponential concentration bound [20], we have for every λ ≥ 1,
" k
#
(
)
k
X
X
λ
2
Pr
[ΣA ]i,i (yi ) ≥
[ΣA ]i,i + λ ≤ exp − Pk
.
8 i=1 [ΣA ]i,i
i=1
i=1

After rearranging, we have

λ
− 8Tr(A)

Pr[x> ZZ> QAQ> ZZ> x ≥ Tr(A) + λ] ≤ e



.

The following lemma is on the singular value distribution of a random Gaussian matrix:
Lemma i.A.2 (Theorem 1.2 of [19]). Let Q ∈ Rk×k be a random matrix with each entry i.i.d.
drawn from N (0, 1), and σ1 ≤ σ2 ≤ · · · ≤ σk be its singular values. We have for every j ∈ [k] and
α ≥ 0:

 
j 2
αj
Pr σj ≤ √ ≤ (2e)1/2 α
.
k
Lemma i.A.3. Let Q be our initial matrix, then for every p ∈ (0, 1):
 h

√
−1 i π 2 ek
p
>
>
>
≥
≤
.
Pr Tr (V Q) (V Q)
Q
3p
1−p

Proof of Lemma i.A.3. Using Lemma i.A.2, we know that (using the famous equation
π2
6 )



Pr Tr

14



P∞

1
j=1 j 2

=



−1  π 2 ek 
2ek
−2
>
≥
(V Q) (V Q)
≤ Pr ∃j ∈ [k], σj (V Q) ≥ 2
3p
j p

√
√  X
k
j p
p
2
= Pr ∃j ∈ [k], σj (V> Q) ≤ √
≤
pj /2 ≤
.
1−p
2ek
j=1
>

>

>

Recall that a random variable X is (σ 2 , b)-subexponential if log E exp(λ(X − E X)) ≤ λ2 σ 2 /2 for all λ ∈ [0, 1/b].
The squared standard Gaussian variable is (4, 4)-subexponential.

17

i.A.2

Proof of Lemma 5.1
2

Proof of Lemma 5.1. Applying Lemma i.A.3 with the choice of probability = p4 , we know that



−1
36k
def
.
Pr Tr(A) ≥ 2 ≤ p where A = (V> Q)> (V> Q)
Q
p
n
o
Conditioning on event C = Tr(A) ≤ 36k
, and setting r = 36k
, we have for every fixed x1 , ..., xT
p2
p2
and fixed i ∈ [T ], it satisfies



T 1/2
i−1
>
>
−1
≥
18r
ln
Pr x>
ZZ
(Σ/λ
)
Q(V
Q)
C,
x
t
k+1
t
Q
q
2



¬
T 1/2
≤ Pr yt ZZ> Q(V> Q)−1 ≥ 18r ln
C, x1 , .., xt
q
2


® q2
­
T2
>
>
>
>
≤ Pr yt ZZ QAQ ZZ yt ≥ 9r ln 2 | C, x1 , .., xt ≤ 2 .
q
T

i−1
>
Above, ¬ uses the definition yt = x>
; ­ is from the definition of A; and ® is
t ZZ (Σ/λk+1 )
> Σ i−1
owing to Lemma i.A.1 together with the fact that kyt k2 ≤ kxt k2 · ZZ
≤ 1 and the fact
λk+1
2
def

that Z> Q is independent of V> Q.15 Next, define event

i−1
>
C2 = ∃i ∈ [T ], ∃t ∈ [T ], x>
Q(V> Q)−1
t ZZ (Σ/λk+1 )


T 1/2
≥ 18r ln
.
q
2
The above derivation, after taking union bound, implies that for every fixed x1 , ..., xT , it satisfies
PrQ [C2 | C, x1 , ..., xT ] ≤ q 2 . Therefore, denoting by 1C2 the indicator function of event C2 ,




1
Pr [C2 | Q] C
Pr Pr [C2 | Q] ≥ q C ≤ E
Q x1 ,...,xT
q Q x1 ,...,xT


1
= E
E [1C | Q] C
q Q x1 ,...,xT 2


1
=
E
E[1C | C, x1 , . . . , xT ]
q x1 ,...,xT Q 2


1
=
E
Pr[C2 | C, x1 , . . . , xT ]
≤ q .
q x1 ,...,xT Q
Above, the first inequality uses Markov’s bound. In an analogous manner, we define event
n

d 1/2 o
C3 = ∃j ∈ [d], j ≥ k + 1, kνj> Q(V> Q)−1 k2 ≥ 18r ln
p
where νj is the j-th eigenvector of Σ corresponding to eigenvalue λj . A completely analogous proof
as the lines above also shows PrQ [C3 | C] ≤ q. Finally, using union bound
h ^
i
h
i
Pr C3
Pr [C2 | Q] ≥ q ≤ Pr[C3 | C] + Pr
Pr [C2 | Q] ≥ q C + Pr[C] ≤ q + q + p ,
Q

x1 ,...,xT

Q

Q

x1 ,...,xT



Q

we conclude that with probability at least 1 − p − 2q over the random choice of Q, it satisfies
• Prx1 ,...,xT [C2 | Q] < q, and

• C3 holds (which implies kZ> Q(V> Q)−1 k2F < 18rd ln dp as desired).

15



In principle, we only proved Lemma i.A.1 when Q is a random matrix, independent of A. Here, A also depends
on Q but only on V> Q. Therefore, A is independent from Z> Q, so we can still safely apply Lemma i.A.1.

18

i.B

Expectation Lemmas (for Section 6)

Let X ∈ Rd×r be a generic matrix that shall later be chosen as either X = W, X = Z, or X = [w]
for some vector w. We recall the following notions from Section 6
Lt = Pt Q(V> Pt Q)−1 ∈ Rd×k

r×k
R0t = X> xt x>
t Lt−1 ∈ R

St = X> Lt ∈ Rr×k

k×k
H0t = V> xt x>
t Lt−1 ∈ R

Lemma i.B.1. For every Q ∈ Rd×k and every t ∈ [T ], suppose for φt ≥ 0, xt satisfies:
1
>
>
−1
kx>
.
t Lt−1 k2 = kxt Pt−1 Q(V Pt−1 Q) k2 ≤ φt and ηt φt ≤
2
Then the following holds:
>
>
0
>
0
(a) Tr(S>
t St ) ≤ Tr(St−1 St−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

2
0 2
2
0
0
+ (12ηt2 kH0t k22 + 2ηt2 kR0t k2 kH0t k2 )Tr(S>
t−1 St−1 ) + 8ηt kRt k2 + 2ηt kRt k2 kHt k2

>
2
2
0 2
>
2
2 kR0 k2 Tr(S> S
4 2
0 2
(b) |Tr(S>
t St )−Tr(St−1 St−1 )| ≤ 243ηt kHt k2 Tr(St−1 St−1 ) +12η
t 2
t−1 t−1 )+300ηt φt kRt k2
q t
>
>
2 2
>
(c) |Tr(S>
t St ) − Tr(St−1 St−1 )| ≤ 9ηt φt Tr(St−1 St−1 ) + 2ηt φt Tr(St−1 St−1 ) + 10ηt φt

Proof of Lemma i.B.1. We first notice that

X> Pt Q = X> Pt−1 Q + ηt X> xt x>
t Pt−1 Q

and

V> Pt Q = V> Pt−1 Q + ηt V> xt x>
t Pt−1 Q ,
where the second equality further implies (using the Sherman-Morrison formula) that
(V> Pt Q)−1 = (V> Pt−1 Q)−1 −

>
−1
ηt (V> Pt−1 Q)−1 V> xt x>
t Pt−1 Q(V Pt−1 Q)
>
−1 >
1 + η t x>
t Pt−1 Q(V Pt−1 Q) V xt

= (V> Pt−1 Q)−1 − (ηt − αt ηt2 )(V> Pt−1 Q)−1 H0t ,
def

and above we denote by αt =

ψt
1+ηt ψt

def

>
where ψt = x>
t Lt−1 V xt . Therefore, we can write

¬

St = X> Pt Q(V> Pt Q)−1
­

= St−1 − (ηt − αt ηt2 )St−1 H0t + ηt R0t − (ηt2 − αt ηt3 )R0t H0t
®

= St−1 − (ηt − αt ηt2 )St−1 H0t + (ηt − ψt ηt2 + αt ψt ηt3 )R0t

¯

=

St−1 − ηt St−1 Ht + ηt Rt .

Above, equality ¬ uses the definition of St and Lt ; equality ­ uses our derived equations for
X> Pt Q and (V> Pt Q)−1 ; equality ® uses R0t H0t = ψt R0t ; and in quality ¯ we have denoted by
Ht = (1 − αt ηt )H0t and Rt = (1 − ψt ηt + αt ψt ηt2 )R0t

to simplify the notations. Note that H0t , R0t are rank one matrices so kH0t kF = kH0t k2 and kR0t kF =

19

kR0t k2 . We now proceed and compute

>
>
>
Tr(S>
t St ) = Tr(St−1 St−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )
¬

>
2
>
2
>
+ηt2 Tr(H>
t St−1 St−1 Ht ) + ηt Tr(Rt Rt ) − 2ηt Tr(Rt St−1 Ht )

>
>
≤ Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )
>
2
>
+2ηt2 Tr(H>
t St−1 St−1 Ht ) + 2ηt Tr(Rt Rt )

­

>
>
≤ Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )
®

2
2 2
0 2
+2ηt2 (1 − αt ηt )2 kH0t k22 Tr(St−1 S>
t−1 ) + 2ηt (1 − ψt ηt + αt ψt ηt ) kRt k2

>
0
>
0
≤ Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

0
2
>
0
+2ηt2 |αt | Tr(S>
t−1 St−1 Ht ) + 2ηt (ηt |ψt | + ηt |αt ||ψt |) Tr(St−1 Rt )

¯

2
2 2 2
0 2
+2ηt2 (1 + 2φt ηt )2 kH0t k22 Tr(St−1 S>
t−1 ) + 2ηt (1 + φt ηt + 2φt ηt ) kRt k2

>
0
>
0
≤ Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

0
2
0
>
0
+4ηt2 kH0t k2 Tr(S>
t−1 St−1 Ht ) + 4ηt kHt k2 Tr(St−1 Rt )

°

2
0 2
+8ηt2 kH0t k22 Tr(St−1 S>
t−1 ) + 8ηt kRt k2

>
0
>
0
≤ Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

0
2
0 2
>
2
0 2
+4ηt2 kH0t k2 Tr(S>
t−1 Rt ) + 12ηt kHt k2 Tr(St−1 St−1 ) + 8ηt kRt k2 .

(i.B.1)

Above, ¬ is because 2Tr(A> B) ≤ Tr(A> A) + Tr(B> B) which is Young’s inequality in the matrix
case; ­ and ® are both because Ht = (1 − αt ηt )H0t and Rt = (1 − ψt ηt + αt ψt ηt2 )R0t ; ¯ follow from
the parameter properties |ψt | ≤ kH0t k2 ≤ φt , |αt | ≤ 2kH0t k2 ≤ 2φt , and 0 ≤ ηt φt ≤ 21 ; ° follows
0
>
0
from |Tr(S>
t−1 St−1 Ht )| ≤ Tr(St−1 St−1 )kHt k2 which uses Proposition 2.1.
Next, Proposition 2.1 tells us
q

kR0t k2 
0
0
0
>
> S
)|
≤
kR
k
kS
k
≤
kR
k
|Tr(S>
R
Tr(S
)
≤
Tr(S
S
)
+
1
, (i.B.2)
t−1 2
t−1 t
t S1
t 2
t−1 t−1
t−1 t−1
2
(the second inequality is because R0t is rank 1, and the spectral norm of a matrix is no greater than
its Frobenius norm.) we can further simplify the upper bound in (i.B.1) as
>
>
0
>
0
Tr(S>
t St ) ≤ Tr(St−1 St−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )


2
0 2
>
2
0 2
+2ηt2 kR0t k2 kH0t k2 Tr(S>
t−1 St−1 ) + 1 + 12ηt kHt k2 Tr(St−1 St−1 ) + 8ηt kRt k2
>
0
>
0
= Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

2
0 2
2
0
0
+(12ηt2 kH0t k22 + 2ηt2 kR0t k2 kH0t k2 )Tr(S>
t−1 St−1 ) + 8ηt kRt k2 + 2ηt kRt k2 kHt k2 .

This finishes the proof of Lemma i.B.1-(a).
A completely symmetric analysis of the above derivation also gives

>
>
0
>
0
Tr(S>
t St ) ≥ Tr(St−1 St−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

2
0 2
2
0
0
−(12ηt2 kH0t k22 + 2ηt2 kR0t k2 kH0t k2 )Tr(S>
t−1 St−1 ) − 8ηt kRt k2 − 2ηt kRt k2 kHt k2 ,

20

and thus combining the upper and lower bounds we have
>
>
0
>
0
|Tr(S>
t St ) − Tr(St−1 St−1 )| ≤ 2ηt |Tr(St−1 St−1 Ht )| + 2ηt |Tr(St−1 Rt )|

+(12ηt2 kH0t k22

+

2ηt2 kR0t k2 kH0t k2 )Tr(S>
t−1 St−1 )

+

8ηt2 kR0t k22

+

(i.B.3)

2ηt2 kR0t k2 kH0t k2

0
≤ (2ηt kH0t k2 + 12ηt2 kH0t k22 + 2ηt2 kR0t k2 kH0t k2 )Tr(S>
t−1 St−1 ) + 2ηt kRt k2

q
Tr(S>
(i.B.4)
)
t−1 St−1

q
2
0
Tr(S>
t−1 St−1 ) + 10ηt φt kRt k2 .

(i.B.5)

¬

+8ηt2 kR0t k22 + 2ηt2 kR0t k2 kH0t k2

­

0
≤ 9ηt kH0t k2 Tr(S>
t−1 St−1 ) + 2ηt kRt k2

Above, ¬ again uses Proposition 2.1 and (i.B.2); ­ uses ηt φt ≤ 1/2 and kH0t k2 , kR0t k2 ≤ φt .
Finally, if we take square on both sides of (i.B.5), we have (using again ηt kR0t k2 ≤ 12 ):

>
2
2
0 2
>
2
2
0 2
>
4 2
0 2
|Tr(S>
t St ) − Tr(St−1 St−1 )| ≤ 243ηt kHt k2 Tr(St−1 St−1 ) + 12ηt kRt k2 Tr(St−1 St−1 ) + 300ηt φt kRt k2

and this finishes the proof of Lemma i.B.1-(b). If we continue to use kH0t k2 , kR0t k2 ≤ φt to upper
bound the right hand side of (i.B.5), we finish the proof of Lemma i.B.1-(c).



Proof of Lemma 6.1 from Lemma i.B.1. According to the expectation we have E[H0t | F≤t−1 , C≤t ] =
V> (Σ + ∆)Lt−1 and E[R0t | F≤t−1 , C≤t ] = X> (Σ + ∆)Lt−1 . Now we consider the subcases separately:
(a) By Lemma i.B.1-(a),
h
i¬
2 2
>
2 2
E Tr(S>
t St ) | F≤t−1 , C≤t ≤ (1 + 14ηt φt )Tr(St−1 St−1 ) + 10ηt φt
h
i
0
>
0
+ E −2ηt Tr(S>
.
t−1 St−1 Ht ) + 2ηt Tr(St−1 Rt ) | F≤t−1 , C≤t

(i.B.6)

kR0t k2 , kH0t k2

≤ φt . Next, we compute the expectation
Above, ¬ uses
h
i
0
>
0
E −2ηt Tr(S>
S
H
)
+
2η
Tr(S
R
)
|
F
,
C
t
≤t−1 ≤t
t−1 t−1 t
t−1 t

>
>
>
= −2ηt Tr(S>
t−1 St−1 V (Σ + ∆)Lt−1 ) + 2ηt Tr(St−1 Z (Σ + ∆)Lt−1 )
­

>
>
>
>
≤ −2ηt gap · Tr(St−1 S>
t−1 ) − 2ηt Tr(St−1 St−1 V ∆Lt−1 ) + 2ηt Tr(St−1 Z ∆Lt−1 ) .(i.B.7)

>
>
>
>
>
Above, ­ is because Tr(S>
t−1 Z ΣLt−1 ) = Tr(St−1 Σ>k Z Lt−1 ) = Tr(St−1 Σ>k St−1 ) ≤ λk+1 Tr(St−1 St−1 ),
>
>
>
>
>
>
as well as Tr(St−1 St−1 V ΣLt−1 ) = Tr(St−1 St−1 Σ≤k V Lt−1 ) = Tr(St−1 St−1 Σ≤k ) ≥ λk Tr(St−1 St−1 ).

Using the decomposition I = VV> + ZZ> , kVk2 ≤ 1, kZk2 ≤ 1, and Proposition 2.1 multiple
times, we have
>
>
>
>
>
Tr(S>
t−1 St−1 V ∆Lt−1 ) = Tr(St−1 St−1 V ∆(VV + ZZ )Lt−1 )
>
>
>
≤ Tr(S>
t−1 St−1 V ∆V) + Tr(St−1 St−1 V ∆ZSt−1 )

¬

3/2 
>
≤ k∆k2 Tr(S>
t−1 St−1 ) + Tr(St−1 St−1 )

>
>
>
>
>
Tr(S>
t−1 Z ∆Lt−1 ) = Tr(St−1 Z ∆(VV + ZZ )Lt−1 )

>
>
>
≤ Tr(S>
t−1 Z ∆V) + Tr(St−1 Z ∆ZSt−1 )


>
1/2
≤ k∆k2 Tr(S>
S
)
+
Tr(S
S
)
.
t−1 t−1
t−1 t−1

3/2
>
>
Above, ¬ uses the fact that kSt−1 S>
t−1 St−1 kS1 ≤ kSt−1 St−1 kS1 kSt−1 k2 ≤ Tr(St−1 St−1 )

21

Plugging them into (i.B.7) gives
h
i
0
>
0
>
E −2ηt Tr(S>
S
H
)
+
2η
Tr(S
R
)
|
F
,
C
t
≤t−1 ≤t ≤ −2ηt gap · Tr(St−1 St−1 )
t−1 t−1 t
t−1 t

3/2

1/2 
>
>
+2ηt k∆k2 Tr(S>
S
)
+
2Tr(S
S
)
+
Tr(S
S
)
.
t−1 t−1
t−1 t−1
t−1 t−1

(i.B.8)

Putting this back to (i.B.6) finishes the proof of Corollary 6.1-(a).

(b) In this case (i.B.7) also holds but one needs to replace gap with ρ because of the definitional
difference between W and Z. We compute the following upper bounds similar to case (a):
>
>
>
>
>
Tr(S>
t−1 St−1 V ∆Lt−1 ) = Tr(St−1 St−1 V ∆(VV + ZZ )Lt−1 )
>
>
>
>
≤ Tr(S>
t−1 St−1 V ∆V) + Tr(St−1 St−1 V ∆ZZ Lt−1 )

¬

1/2 
>
>
≤ k∆k2 Tr(S>
t−1 St−1 ) 1 + Tr(Z Lt−1 Lt−1 Z)

>
>
>
>
>
Tr(S>
t−1 Z ∆Lt−1 ) = Tr(St−1 Z ∆(VV + ZZ )Lt−1 )

>
>
>
>
≤ Tr(S>
t−1 Z ∆V) + Tr(St−1 Z ∆ZZ Lt−1 )


­
>
>
1/2
1/2
(i.B.9)
1
+
Tr(Z
L
L
Z)
≤ k∆k2 Tr(S>
S
)
t−1 t−1
t−1 t−1

Above, ¬ is because (using Proposition 2.1)

1/2 
1/2
> >
· Tr(V> ∆ZZ> Lt−1 L>
t−1 ZZ ∆ V)

1/2
>
>
≤ k∆k2 Tr(S>
t−1 St−1 ) · Tr(Z Lt−1 Lt−1 Z)

>
>
>
2
Tr(S>
t−1 St−1 V ∆ZZ Lt−1 ) ≤ Tr (St−1 St−1 )

and ­ holds for a similar reason.

Putting these upper bounds into (i.B.7) finishes the proof of Corollary 6.1-(b).
(c) When X = [w], a slightly different derivation of (i.B.7) gives
h
i
2 2
>
2 2
E Tr(S>
t St ) | Ft−1 , C≤t ≤ (1 − 2ηt λk + 14ηt φt )Tr(St−1 St−1 ) + 10ηt φt

>
>
>
>
>
− 2ηt Tr(S>
t−1 St−1 V ∆Lt−1 ) + 2ηt Tr(St−1 w ∆Lt−1 ) + 2ηt Tr(St−1 w ΣLt−1 ) .
(i.B.10)

Note that the third and fourth terms can be upper bounded similarly using (i.B.9). As for the
fifth term, we have
1
λk
>
Tr(S>
Tr(w> ΣLt−1 L>
Tr(S>
t−1 w ΣLt−1 ) ≤
t−1 St−1 ) +
t−1 Σw)
2
2λk
Putting these together, we have:
h
i

ηt
2 2
>
2 2
E Tr(S>
S
)
|
F
,
C
kw> ΣLt−1 k22
≤t−1 ≤t ≤ 1 − ηt λk + 14ηt φt Tr(St−1 St−1 ) + 10ηt φt +
t t
λk


1/2

1/2 
>
>
>
+ 2ηt k∆k2 Tr(S>
S
)
+
Tr(S
S
)
1
+
Tr(Z
L
L
Z)

t−1
t−1
t−1
t−1
t−1
t−1

i.C

Martingale Concentrations

We prove in the appendix the following two martingale concentration lemmas. Both of them
are stated in their most general form for the purpose of this paper. The first lemma is for 1-d
martingales and the second is for multi-d martingales.
At a high level, Lemma i.C.1 will only be used to analyze the sequences st or s0t (see Section 3)
after warm start — that is, after t ≥ T0 . Our Lemma i.C.2 can be used to analyze ct,s as well as st
and s0t before warm start.
22

Lemma i.C.1 (1-d martingale). Let {zt }∞
t=t0 be a non-negative random process with starting time
1
∗
t0 ∈ N . Suppose there exists δ > 0, κ ≥ 2, and τt = δt
such that


E[zt+1 | F≤t ] ≤ (1 − δτt )zt + τt2 

E[(zt+1 − zt )2 | F≤t ] ≤ τt2 zt + κ2 τt4
∀t ≥ t0 :
(i.C.1)
√


|zt+1 − zt | ≤ κτt zt + κ2 τt2
2

If there exists φ ≥ 36 satisfying lnt20t ≥ 7.5κ2 (φ + 1) with zt0 ≤ φ2δln2 t0t0 , we have:
0
h
i exp{− φ −1 ln t }
0
(φ+1) ln2 t
36
Pr ∃t ≥ t0 , zt >
≤
.
φ
δ2 t
36

−1

Lemma i.C.2 (multi-dimensional martingale). Let {zt }Tt=0 be a random process where each zt ∈
T −1
RD
≥0 is F≤t -measurable. Suppose there exist nonnegative parameters {βt , δt , τt }t=0 satisfying κ ≥ 0
and κτt ≤ 1/6 such that, ∀i ∈ [D], ∀t ∈ {0, 1, . . . , T − 1},
(denoting by [zt ]i is the i-th coordinate of zt and [zt ]D+1 = 0)



2 )[z ] + δ [z ]
2 ,
E
[z
]
|
F
≤
(1
−
β
−
δ
+
τ
+
τ

t+1
i
≤t
t
t
t
i
t
t
i+1
t
t




E |[zt+1 ]i − [zt ]i |2 | F≤t ≤ τt2 [zt ]2i + [zt ]i +κ2 τt4 , and
(i.C.2)
p


[zt+1 ]i − [zt ]i ≤ κτt [zt ]i + [zt ]i + κ2 τt2 .


Then, we have: for every λ > 0, every p ∈ 1, mins∈[t] { 6κτ1s−1 } :

nP
o


t−1
2 τ 2 − pβ
Pr [zt ]1 ≥ λ ≤ λ−p maxj∈[t+1] {[z0 ]pj } exp
5p
s
s
s=0
nP
o
Pt−1
t−1
2 2
.
+ 1.4 s=0 exp
u=s+1 5p τu − pβu

The above two lemmas are stated in the most general way in order to be used towards all of
our three theorems each requiring different parameter choices of βt , δt , τt , κ. For instance, to prove
Theorem 2 it suffices to use κ = O(1).

i.C.1

Martingale Corollaries

We provide below four instantiations of these lemmas, each of them can be verified by plugging in
the specific parameters.
Corollary i.C.3 (1-d martingale). Consider the same setting as Lemma i.C.1. Suppose p ∈ (0, e12 ),


1
δ ≤ √18 , τt = δt
, κ ∈ 2, √12δ , lnt20t ≥ 9 ln(1/p)
, and zt0 ≤ 2 we have:
δ2
0
h
i
2
0 / ln t0 )
≤p .
Pr ∃t ≥ t0 , zt > 5(tt/
2
ln t
Corollary i.C.4 (multi-d martingale).
Consider the same setting as Lemma i.C.2. Suppose q ∈
Pt−1
−1 4t
1
2
(0, 1), mins∈[t] { 6κτ1s−1 } ≥ 4 ln 4t
and
s=0 τs ≤ 100 ln
q
q , then
h
i

Pr [zt ]1 ≥ 2 max 1, max {[z0 ]j } ≤ q .
j∈[t+1]

Corollary i.C.5 (multi-d martingale). Consider the same setting as Lemma i.C.2. Given q ∈
def
(0, 1), suppose there exists parameter γ ≥ 1 such that, denoting by l = 10γ ln 3t
q,


t−1
X
^
1
2
βs − lτs ≥ ln max {[z0 ]j }
and ∀s ∈ {0, 1, . . . , t − 1} : βs ≥ lτs2
κτs ≤
.
j∈[t+1]
12 ln 3t
q
s=0


Then, we have
Pr [zt ]1 ≥ 2/γ ≤ q .
23

i.C.2

Proofs for One-Dimensional Martingale

Proof of Lemma i.C.1. Define yt =

δ 2 tzt
ln t

− ln t, then we have:

δ 2 (t + 1) E[zt+1 | F≤t ]
− ln(t + 1)
ln(t + 1)
δ 2 (t + 1)(1 − δτt )zt δ 2 (t + 1)τt2
+
− ln(t + 1)
≤
ln(t + 1)
ln(t + 1)

¬ δ 2 tzt
δ 2 (t + 1) 1 − 1t
t+1
≤
zt + 2
− ln(t + 1) ≤
− ln t = yt ,
ln(t + 1)
t ln(t + 1)
ln t

t2
1
t+1
where ¬ is because for every t ≥ 4 it satisfies (t+1)(t−1)
ln(t+1) ≤ ln t and t2 ln(t+1) ≤ ln 1 + t .
At the same time, we have
­ δ2t
δ2
1
|yt+1 − yt | ≤
|zt+1 − zt | +
zt+1 + ,
(i.C.3)
ln t
ln t
t
t+1
where ­ is because for every t ≥ 3 it satisfies 0 ≤ ln(t+1)
− lnt t ≤ ln1 t and ln(t + 1) − ln(t) ≤ 1/t.
Taking square on both sides, we have
 2 2
 2 2
δ t
δ
3
2
2
2
|yt+1 − yt | ≤ 3
|zt+1 − zt | + 3
zt+1
+ 2 .
ln t
ln t
t
Taking expectation on both sides, we have
 2 2
(yt + ln t)2
3
δ t
2
(τt2 zt + κ2 τt4 ) + 3
+ 2
E[|yt+1 − yt | | F≤t ] ≤ 3
2
ln t
t
t
2
2
3(yt + ln t) 3(yt + ln t)
3(1 + κ )
<
+
+
t ln t
t2
t2
2
2
2
®
¯ 4(φt + 1)
3(φ + 1) 3(φ + 1) ln t 15κ
≤
+
+
≤
.
t
t2
4t2
t

Above, ® uses yt ≤ φ ln t and κ ≥ 2; ¯ uses lnt2 t ≥ lnt20t ≥ max 7.5κ2 , 6(φ + 1) and ln t ≥ 1.
0
Therefore, if yt ≤ φ ln t holds true for t = t0 , ..., T and t0 ≥ 8 (which implies lnt2 t ≥ lnt20t ), then
0
Z T
T
T
X
X
dt
4(φ + 1)
≤ 4(φ + 1)
≤ 4(φ + 1) ln(T ) .
E[|yt+1 − yt |2 | F≤t ] ≤
t
t=t0 −1 t
t=t
t=t
E[yt+1 | F≤t ] =

0

0

Now we can check about the absolute difference. We continue from (i.C.3) and derive that, if
yt ≤ φ ln t, then

√
δ2t
δ2
1
δ2t
δ2
1
|yt+1 − yt | ≤
|zt+1 − zt | +
zt+1 +
≤
κτt zt + κ2 τt2 +
zt+1 +
ln t
ln t
t
ln t!
ln t
t
!
r
r
°
yt + ln t
κ
(yt + ln t) 1
yt + ln t yt + ln t + κ
≤ κ
+
+
+
≤ κ
+
t ln t
t ln t
t
t
t ln t
t
!
r
r
±
²
(φ + 1) (φ + 1) ln t + κ
(φ + 1)
≤ κ
+
≤ 2κ
t
t
t

where ° uses ln t ≥ 2 and κ ≥ 2, ± uses yt ≤ φ ln t, and ² uses lnt2 t ≥ lnt20t ≥ 4 max{φ + 1, κ}.
0
From the above inequality, we have that if t0 ≥ 4κ2 (φ + 1) and yt ≤ φ ln t holds true for
t = t0 , ..., T − 1 then |yt+1 − yt | ≤ 1 for all t = t0 , . . . , T − 1.
2
Finally, since we have assumed φ > 36 and zt0 ≤ φ2δln2 t0t0 which implies yt0 ≤ φ ln2 t0 , we can apply

24

martingale concentration inequality (c.f. [5, Theorem 18]):
∞
X


Pr [∃t ≥ t0 , yt > φ ln t] ≤
Pr yT > φ ln T ; ∀t ∈ {t0 , ..., T − 1}, yt ≤ φ ln t
≤

T =t0 +1
∞
X

T =t0 +1
∞
X



Pr yT − yt0 > φ ln T /2; ∀t ∈ {t0 , ..., T − 1}, yt ≤ φ ln t

)
−(φ ln T /2)2
≤
exp
2 · 4(φ + 1) ln(T − 1) + 23 (φ ln T /2)
T =t0 +1


∞
X
φ2 /4
≤
exp − ln T
8(φ + 1) + φ/3
T =t0 +1



Z ∞
φ
exp{− 36
− 1 ln t0 }
φ
exp − ln T dT ≤
≤
.
φ
36
T =t0
36 − 1
def 4δ 2 t0
ln2 t0
φ ln2 t0
2δ 2 t0

Proof of Corollary i.C.3. Define φ =
√
1) (because κ ≤ 1/( 2δ)) and zt0 ≤

(

≥ 36 ln p1 ≥ 72. It is easy to verify that

t0
ln2 t0

≥ 7.5κ2 (φ+

= 2, so we can apply Lemma i.C.1:
n
o

φ
 



2 
exp
−
−
1
ln
t
0
36
φ
(φ + 1) ln t
≤
exp
−
Pr ∃t ≥ t0 , zt >
≤
−
1
ln
t
0 ≤p ,
φ
δ2t
36
−
1
36

φ
φ
− 1 ln t0 ≥ 36
. Therefore, we conclude that
where the last inequality uses ln t0 ≥ 2 and 36




2
5(t0 / ln t0 )
(φ + 1) ln2 t
Pr ∃t ≥ t0 , zt >
≤ Pr ∃t ≥ t0 , zt >
≤p .
δ2t
t/ ln2 t

i.C.3





Proofs for Multi-Dimensional Martingale


Proof of Corollary i.C.4. We apply Lemma i.C.2 with λ = 2 max 1, maxj∈[t+1] {[z0 ]j } ≥ 2. Using
the fact that βt ≥ 0, we have
(
)


t−1
X


Pr [zt ]1 ≥ λ = Pr [zt ]1 ≥ 2( max {[z0 ]j } + 1) ≤ (1 + 1.4t) exp − ln(2p ) + 5p2
τs2
.
j∈[t+1]

We can take p = 4 ln

4t
q

fore, denoting by α =

≤ mins∈[t] { 6κτ1s−1 }
Pt−1 2
s=0 τs , we have

s=0

which satisfies the assumption of Lemma i.C.2. There-

n
o


Pr [zt ]1 ≥ λ ≤ 4t exp − p ln 2 + 5p2 α ≤ q .

2
4t
Above, the last inequality is due to −p ln 2 + 5p2 α2 ≤ −2 ln 4t
+
5
4
ln
α ≤ − ln 4t
q
q
q which holds
for every α ≤

1
100

ln−1



4t
q.

Proof of Corollary i.C.5. We consider fixed p =
with (using the fact that γ ≥ 1)

l
5γ

βt0 = βt ,

= 2 ln 3t
q . Let yt = γ · zt , then yt satisfies (i.C.2)

δt0 = δt , (τt0 )2 = γτt2 , κ0 = κ .
def Pt−1
def P
2
We denote by b = s=0
βs = b and a = t−1
s=0 τs , and apply Lemma i.C.2 on yt with λ = 2. Using
2
2
0
the fact that βs ≥ lτs = 5zpτs we know pβt ≥ 5p2 (τt0 )2 . Therefore, for all s ∈ {0, 1, . . . , T − 1} we
25

have


Pr [[yt ]1 ≥ 2] ≤ exp −pb + 5p2 γa + p ln Ξ − p ln 2 + 1.4t exp {−p ln 2} ,

(i.C.4)

def

where we have denoted by Ξ = maxj∈[t+1] {[z0 ]j } for notational simplicity. Now, the choice p =
1
2 ln 3t
q satisfies the presumption of Lemma i.C.2 because we have assumed κτs ≤ 12 ln 3t Therefore,
q

we have

^
3t
q
⇐= b − la ≥ ln Ξ p ≥ 2 ln
2
q
q
3t
−p ln 2 ≤ ln
⇐= p ≥ 2 ln
.
3t
q
i
h



Plugging them into (i.C.4) gives Pr [zt ]1 ≥ γ2 = Pr [yt ]1 ≥ 2 ≤ 2q + 2q = q .
−pb + 5p2 γa + p ln Ξ − p ln 2 = p(−b + la + ln Ξ − ln 2) ≤ ln

Proof of Lemma i.C.2. Define vector st for every t ∈ {0, 1, . . . , T − 1} and i ∈ [D], it satisfies
def
]i
[st ]i = [z[zt+1
− 1. We have
t ]i


τ2
[zt ]i+1
+ t .
E [st ]i | F≤t ≤ −(δt + βt − τt2 ) + δt
[zt ]i
[zt ]i

In particular,



κ2 τt4
τ2
≤ (2 + (τt κ)2 )τt2 ≤ 3τt2 ,
E [st ]2i | F≤t ≤ τt2 + t +
[zt ]i
[zt ]2i
κτt
κ2 τt2
[st ]i ≤ κτt + p
+
≤ κτt (2 + κτt ) ≤ 3κτt .
[zt ]i
[zt ]i

if [zt ]i ≥ 1, then

(i.C.5)

(i.C.6)
(i.C.7)

We consider [zt+1 ]pi for some fixed value p ≥ 1 and derive that (using (i.C.7))
X

p  
p
1
[st ]qi
if (κτt )p ≤ and [zt ]i ≥ 1, then [zt+1 ]pi = [zt ]pi (1 + [st ]i )p = [zt ]pi
6
q
q=0

≤ [zt ]pi 1 + p[st ]i + p2 [st ]2i .

After taking expectation, we have if (κτt )p ≤
¬

E [[zt+1 ]pi | F≤t ] ≤
­

≤
=
®

≤
=
¯

≤

1
6

and [zt ]i ≥ 1, then

[zt ]pi 1 + p E [[st ]i | F≤t ] + 3p2 τt2


τt2 p
[zt ]i+1
p
2 2
2
[zt ]i 1 − p(δt + βt − τt ) + δt p
+
+ 3p τt
[zt ]i
[zt ]i

[zt ]pi 1 − p(δt + βt − τt2 ) + 3p2 τt2 + δt p[zt ]p−1
[zt ]i+1 + pτt2 [zt ]ip−1
i



p−1 p 1 p
p
2
2 2
2
[zt ]i + [zt ]i+1
[zt ]i 1 − p(δt + βt − τt ) + 3p τt + pτt + δt p
p
p

p
p
2
2 2
2
[zt ]i 1 − δt − pβt + pτt + 3p τt + pτt + δt [zt ]i+1

[zt ]pi 1 − δt − pβt + 5p2 τt2 + δt [zt ]pi+1 .

Above, ¬ uses (i.C.6); ­ uses (i.C.5); ® uses [zt ]i ≥ 1 and Young’s inequality ab ≤ ap /p + bq /q for
1/p + 1/q = 1; and ¯ uses p ≥ 1.
On the other hand, if (κτt )p ≤ 61 but [zt ]i < 1, we have the following simple bound (using
κτt ≤ 1/6):
p
[zt+1 ]i ≤ (1 + κτt )[zt ]i + κτt [zt ]i + κ2 τt2 ≤ (1 + κτt ) + (κτt ) + κ2 τt2 < 1.4 .
Therefore, as long as (κτt )p ≤ 16 we always have



E [zt+1 ]pi | F≤t ≤ [zt ]pi 1 − δt − pβt + 5p2 τt2 + δt [zt ]pi+1 + 1.4 =: (1 − αt )[zt ]pi + δt [zt ]pi+1 + 1.4 ,
26

def

and in the last inequality we have denoted by αt = δt + pβt − 5p2 τt2 . Telescoping this expectation,
and choosing i = 1, we have whenever p ∈ [1, mins∈[t] { 6κτ1s−1 }], it satisfies
!


t
t
t
Y
X
Y
p
p
E [[zt+1 ]1 ] ≤
(1 − αs + δs ) max {[z0 ]j } + 1.4
(1 − αu + δu )
≤
≤

j∈[t+2]

s=1
t
Y

(1 − pβs + 5p2 τs2 )

s=0

max

j∈[t+2]

{[z0 ]pj } exp

(



−p

s=0

u=s+1


t
X
p
max {[z0 ]j } + 1.4

j∈[t+2]
t
X
s=0

βs

!

s=0

+ 5p

2

t
X
s=0

τs2

)

t
Y

(1 − pβu + 5p2 τu2 )

u=s+1
t
X

+ 1.4

s=0

(

exp −p

u=s+1

Finally, using Markov’s inequality, we have for every λ > 0:

nP
o


t
2 τ 2 − pβ
Pr [zt+1 ]1 ≥ λ ≤ λ−p maxj∈[t+2] {[z0 ]pj } exp
5p
s
s
s=0
nP
o
Pt
t
2 2
+ 1.4 s=0 exp
.
u=s+1 5p τu − pβu

i.D

t
X

!

βu

!

+ 5p

2

u=s+1



Decoupling Lemmas

We prove the following general lemma. Let x1 , ..., xT ∈ Ω be random variables each i.i.d. drawn from
some distribution D. Let Ft be the sigma-algebra generated by xt , and denote by F≤t = ∨ts=1 Ft .16
Lemma i.D.1 (decoupling lemma). Consider a fixed value q ∈ [0, 1). For every t ∈ [T ] and
s ∈ {0, 1, ..., t − 1}, let yt,s ∈ RD be an Ft ∨ F≤s measurable random vector and let φt,s ∈ RD be a
fixed vector. Let D0 ∈ [D]. Define events (we denote by (i) the i-th coordinate)


h
i
(i)
(i)
0
0 def
Ct = (x1 , ..., xt−1 ) satisfies Pr ∃i ∈ [D ] : yt,t−1 > φt,t−1 Ft−1 ≤ q
xt
n
o
def
(i)
(i)
Ct00 = (x1 , ..., xt ) satisfies ∀i ∈ [D0 ] : yt,t−1 ≤ φt,t−1
def
def V
and denote by Ct = Ct0 ∧ Ct00 and C≤t = ts=1 Cs . Suppose the following three assumptions hold:

(A1) The random process {yt,s }t,s satisfy that for every i ∈ [D], t ∈ [T − 1], s ∈ {0, 1, . . . , t − 2}
 (i)


(i)
(a) E yt,s+1 | Ft , F≤s , C≤s ≤ fs yt,s , q ,
 (i)


(i)
(i)
(b) E |yt,s+1 − yt,s |2 | Ft , F≤s , C≤s ≤ hs yt,s , q , and

(i)
(i)
(i)
(c) yt,s+1 − yt,s ≤ gs yt,s whenever C≤s holds.

d
Above, for each i ∈ [D] and s ∈ {0, 1, . . . , T − 2}, we have fs , hs : Rd × [0, 1] → RD
≥0 , gs : R →
D
d
R≥0 are functions satisfying for every x ∈ R ,
(i)

(i)

(d) fs (x, p), hs (x, p) are monotone increasing in p, and
2
(i)
(i)
(i)
(i)
(i)
(e) x(i) − fs (x, 0) ≤ hs (x, 0) and x(i) − fs (x, 0) ≤ gs (x) whenever fs (x, 0) ≤ x(i) .

(A2) Each t ∈ [T ] satisfies Prxt [Et ] ≤ q 2 /2 where event
def 
(i)
(i)
Et = xt satisfies ∀i ∈ [D] : yt,0 ≤ φt,0
16

d

.

For the purpose of this paper, one can feel free view Ω as R , each xt as the t-th sample vector, and D as the
distribution with covariance matrix Σ.

27

t
X

τu2

)

.

(A3) For every t ∈ [T ], letting xt be any vector satisfying Et , consider any random process {zs }t−1
s=0
where each zs ∈ RD
≥0 is F≤s measurable with z0 = yt,0 as the starting vector. Suppose that
t−1
whenever {zs }s=0
satisfies


 (i)

(i)

E zs+1 | F≤s ≤ fs (zs , q) 
 


(i)
(i)
(i)
∀i ∈ [D], ∀s ∈ {0, 1, . . . , t − 2} :
(i.D.1)
E |zs+1 − zs |2 | F≤s ≤ hs (zs , q)




(i)
(i)
(i)
zs+1 − zs
≤ gs (zs )
(i)

(i)

then it holds Prx1 ,...,xt−1 [∃i ∈ [D0 ] : zt−1 > φt,t−1 ] ≤ q 2 /2.

Under the above two assumptions, we have for every t ∈ [T ], it satisfies Pr[Ct ] ≤ 2tq .
Proof of Lemma i.D.1. We prove the lemma by induction. For the base case, by applying assump
(i)
(i) 
tion (A2) we know that Prx1 ∃i ∈ [D0 ] : y1,0 > φ1,0 ≤ Pr[E1 ] ≤ q 2 /2 ≤ q so event C1 holds with
probability at least 1 − q. In other words, Pr[C≤1 ] = Pr[C1 ] ≤ q < 2q.
Suppose Pr[C≤t−1 ] ≤ 2(t − 1)q is true for some t ≥ 2, we will prove Pr[C≤t ] ≤ 2tq. Since it
satisfies Pr[C≤t ] ≤ Pr[C≤t−1 ] + Pr[Ct ], it suffices to prove that Pr[ Ct ] ≤ 2q.
Note also Pr[ Ct ] ≤ Pr[ Ct0 ] + Pr[ Ct00 | Ct0 ] but the second quantity Pr[ Ct00 | Ct0 ] is no more than
q according to our definition of Ct0 and Ct00 . Therefore, in the rest of the proof, it suffices to show
Pr[ Ct0 ] ≤ q.
We use yt,s (xt , x≤s ) to emphasize that yt,s is an Ft × F≤s measurable random vector. Let us
D
now fix xt to be a vector satisfying Et . Define {zs }t−1
s=0 to be a random process where each zs ∈ R
is F≤s measurable:
( (i)

yt,s n
xt , x≤s
 def
(i)
(i)
o if x≤s satisfies C≤s ;
 (i)
zs = zs x≤s =
(i.D.2)
(i)
min fs−1 zs−1 (x≤s−1 ), 0 , zs−1 (x≤s−1 )
if x≤s satisfies C≤s .
(i)

Then zs satisfies for every i ∈ [D], s ≤ {0, 1, . . . , t − 2},
 (i)

 (i)


 (i)


E zs+1 | F≤s = Pr[C≤s+1 | F≤s ] · E zs+1 | C≤s+1 , F≤s + Pr C≤s+1 | F≤s · E zs+1 | C≤s+1 , F≤s
¬
 (i)



≤ Pr[C≤s+1 | F≤s ] · E yt,s+1 | C≤s+1 , F≤s + Pr C≤s+1 | F≤s · fs(i) (zs , 0)
­




≤ Pr[C≤s+1 | F≤s ] · fs(i) yt,s , q + Pr C≤s+1 | F≤s · fs(i) zs , q
®




≤ Pr[C≤s+1 | F≤s ] · fs(i) yt,s , q + Pr C≤s+1 | F≤s · fs(i) yt,s , q
(i.D.3)
= fs(i) (zs , q)

(i.D.4)

Above, ¬ is because whenever C≤s+1 holds it satisfies
(i)
zs+1

(i)
fs (zs , 0);

(i)
zs+1

=

(i)
yt,s+1 ,

as well as whenever C≤s+1

holds it satisfies
≤
­ uses assumptions
 (A1a) and (A1d) as well as the fact that
we have fixed xt ; ® uses the fact that whenever Pr C≤s+1 | F≤s > 0 it must hold that C≤s is
satisfied, and therefore it satisfies yt,s = zs .
Similarly, we can also show for every i ∈ [D], s ≤ {0, 1, . . . , t − 2},
 (i)

E |zs+1 − zs(i) |2 | F≤s

 (i)

 (i)


= Pr[C≤s+1 | F≤s ] · E |zs+1 − zs(i) |2 | C≤s+1 , F≤s + Pr C≤s+1 | F≤s · E |zs+1 − zs(i) |2 | C≤s+1 , F≤s
¬
 (i)



(i)
≤ Pr[C≤s+1 | F≤s ] · E |yt,s+1 − yt,s |2 | C≤s+1 , F≤s + Pr C≤s+1 | F≤s · h(i)
s (zs , 0)
­

 (i)
≤ Pr[C≤s+1 | F≤s ] · h(i)
s yt,s , q) + Pr C≤s+1 | F≤s · hs (zs , q)
®

≤ h(i)
s (zs , q) .

(i.D.5)

28

(i)

(i)

(i)

Above, ¬ is because whenever C≤s+1 holds it satisfies zs+1 = yt,s+1 and zs
(i)

(i)

(i)

= yt,s , together
(i)

(i) 2

with whenever C≤s+1 holds it satisfies |zs+1 − ys |2 either equal zero or equal fs (zs , 0) − zs
(i)
fs (zs , 0)

,

(i)
zs

but in the latter case we must have
<
(owing to (i.D.2)) and therefore it holds
(i)
(i) 2
(i)
fs (zs , 0) − zs
≤ hs (zs , 0) using assumption (A1e). ­ uses assumptions
 (A1b) and (A1d) as
well as the fact that we have fixed xt . ® uses the fact that whenever Pr C≤s+1 | F≤s > 0 then
C≤s must hold, and therefore it satisfies yt,s = zs .
Finally, we also have
(i)

|zs+1 − zs(i) | ≤ gs(i) (zs(i) ) .

(i.D.6)

(i)
|zs+1

(i)
(i)
(i)
This is so because whenever C≤s+1 holds it satisfies
− zs | = |yt,s+1 − yt,s | so we can apply
(i)
(i)
assumption (A1c). Otherwise, C≤s+1 holds we either have |zs+1 − zs | = 0 (so (i.D.6) trivially

(i)
(i)
(i)
(i)
(i)
(i)
holds) or |zs+1 − zs | = fs zs , 0 − zs , but in the latter case we must have fs (zs , 0) < zs

(i)
(i)
(i)
(owing to (i.D.2)) so it must satisfy fs zs , 0 − zs ≤ gs (zs ) using assumption (A1e).

We are now ready to apply assumption (A3), which together with (i.D.4), (i.D.5), (i.D.6),
implies that (recalling we have fixed xt to be any vector satisfying Et )


(i)
(i)
Pr
∃i ∈ [D0 ] : zt−1 > φt,t−1 | Et ≤ q 2 /2 .
x1 ,...,xt−1

This implies, after translating back to the random process {yt,s }, we have



(i)
(i) 
(i)
(i)
Pr ∃i ∈ [D0 ] : yt,t−1 > φt,t−1 ≤ Pr ∃i ∈ [D0 ] : yt,t−1 > φt,t−1 | Et + Pr[Et ]
x1 ,...,xt
x1 ,...,xt


(i)
(i)
≤ Pr
∃i ∈ [D0 ] : zt−1 > φt,t−1 | Et + q 2 /2
x1 ,...,xt−1

≤ q 2 /2 + q 2 /2 = q 2 .

where the last inequality uses (A2). Finally, using Markov’s inequality,




 0
(i)
(i)
0
Ct
=
Pr
Pr ∃i ∈ [D ] : yt,t−1 > φt,t−1 | F≤t−1 > q
Pr
x1 ,...,xt−1 xt
x1 ,...,xt−1


1
(i)
(i)
0
≤
·
E
Pr[∃i ∈ [D ] : yt,t−1 > φt,t−1 | F≤t−1 ]
q x1 ,...,xt−1 xt
h
i
1
(i)
(i)
=
· Pr ∃i ∈ [D0 ] : yt,t−1 > φt,t−1 ≤ q .
q x1 ,...,xt

Therefore, we finish proving Pr[Ct0 ] ≤ q which implies Pr[C≤t ] ≤ 2tq as desired. This finishes the
proof of Lemma i.D.1.


i.E
i.E.1

Main Lemmas (for Section 7)
Before Warm Start

Proof of Lemma Main 1. For every t ∈ [T ] and s ∈ {0, 1, ..., t − 1}, consider random vectors yt,s ∈
RT +2 defined as:
(1)

def

(2)

def

yt,s = kZ> Ps Q(V> Ps Q)−1 k2F ,

yt,s = kW> Ps Q(V> Ps Q)−1 k2F ,

 x> ZZ> (Σ/λ )j P Q(V> P Q)−1
s
s
(3+j) def
k+1
t
yt,s
=
(3+j)
 (1 − η λ ) · y
,
s k

t,s−1

29

2
2

, for j ∈ {0, 1, . . . , t − s − 1};
for j ∈ {t − s, . . . , T − 1}.

(3+j)

(3+j)

(In fact, we are only interested in yt,s
for j ≤ t − s − 1, and can “almost” define yt,s
= +∞
whenever j ≥ t − s. However, we still decide to give such out-of-boundary variables meaningful
values in order to make all of our vectors yt,s (and functions f, g, h defined later) to be of the same
dimension T + 2. This allows us to greatly simplify our notations.)
We consider upper bounds

2ΞZ s < T0 ;
(3+j) def
(2) def
(1) def
, and φt,s = 2Ξ2x .
φt,s = 2ΞZ , φt,s =
2
otherwise.

For each t ∈ [T ], define event Ct0 and Ct00 in the same way as decoupling Lemma i.D.1 (with D0 = 3):


h
i
(i)
(i)
0 def
Ct = (x1 , ..., xt−1 ) satisfies Pr ∃i ∈ [3] : yt,t−1 > φt,t−1 Ft−1 ≤ q
xt
n
o
def
(i)
(i)
Ct00 = (x1 , ..., xt ) satisfies ∀i ∈ [3] : yt,t−1 ≤ φt,t−1
def V
def
and denote by Ct = Ct0 ∧ Ct00 and C≤t = ts=1 Cs .
As a result, if C≤s+1 holds, then we always have
2
>
−1 2
>
>
>
−1
>
>
>
−1
kx>
s+1 Ps Q(V Ps Q) k2 ≤ kxs+1 VV Ps Q(V Ps Q) k2 + kxs+1 ZZ Ps Q(V Ps Q) k2
√
(3)
≤ (1 + φs+1,s )2 = ( 2Ξx + 1)2 ≤ 4Ξ2x ,
where last inequality uses Ξx ≥ 2. This allows us to later apply Lemma i.B.1 and Lemma 6.1 with
φt = 2Ξx .

Verification of Assumption (A1) in Lemma i.D.1.
def
00
Suppose E[xs x>
s | C≤s , F≤s−1 ] = Σ + ∆, and we want to bound k∆k2 . Defining q1 = Pr[Cs |
00
0
0
Cs , C≤s−1 , F≤s−1 ], then we must have q1 ≤ q according to the definition of Cs and Cs . Using law of
total expectation:
0
>
>
00 0
E[xs x>
s | Cs , C≤s−1 , F≤s−1 ] = E[xs xs | C≤s , F≤s−1 ] · (1 − q1 ) + E[xs xs | Cs , Cs , C≤s−1 , F≤s−1 ] · q1 ,

>
0
>
and combining it with the fact that 0  xs x>
s  I and E[xs xs | Cs , C≤s−1 , F≤s−1 ] = E[xs xs ] = Σ,
17
we have
Σ  (Σ + ∆)(1 − q1 ) + q1 · I and Σ  (Σ + ∆)(1 − q1 ) .
q1
q
After rearranging, these two properties imply k∆k2 ≤ 1−q
.
≤ 1−q
1
Now, we can apply Lemma 6.1 and obtain for every t ∈ [T ], s ∈ {0, 1, . . . , t − 2}, and every
j ∈ {0, 1, . . . , T − 1}, it satisfies18
(1)

(1)

2
2
E[yt,s+1 | Ft , F≤s , C≤s+1 ] ≤ (1 + 56ηs+1
Ξ2x )yt,s + 40ηs+1
Ξ2x + 20ηs+1
(2)

(2)

(3+j)

(3+j)

3/2

qΞZ
1−q

,

2
2
E[yt,s+1 | Ft , F≤s , C≤s+1 ] ≤ (1 − 2ηs+1 ρ + 56ηs+1
Ξ2x )yt,s + 40ηs+1
Ξ2x + 20ηs+1
2
E[yt,s+1 | Ft , F≤s , C≤s+1 ] ≤ (1 − ηs+1 λk + 56ηs+1
Ξ2x )yt,s

(3+j+1)

+ ηs+1 λk yt,s

3/2

qΞZ
1−q

, and

2
+ 40ηs+1
Ξ2x + 20ηs+1

Moreover, for every i ∈ [T + 2], using Lemma i.B.1-(c) with φt = 2Ξx we have whenever C≤s+1
17
18

Here, we use notation A  B to indicate spectral dominance: that is, B − A is positive semidefinite.
We make a few comments regarding how to derive these upper bounds.
• Event C≤s+1 implies we can safely apply Lemma 6.1 with φt = 2Ξx .
• To obtain the third inequality, one needs to use the fact that when w = xt ZZ> the quantity ληkt kw> ΣLt−1 k22

ηt λ2
k+1
kw> Lt−1 k22 ≤ ηt λk kw> Lt−1 k22 .
λk
(3+j) def
(3+j)
which means yt,s
= (1 − ηs λk ) · yt,s−1 according

that appeared in Corollary 6.1-(c) can be upper bounded by
(3+j)

• Whenever j ≥ t − s we have yt,s
is “out of boundary”
to our definition. In this case it easily satisfies the third inequality.
(3+j+1)
• When j = T − 1, in the third inequality we should replace yt,s
with zero because it is out of bound.

30

3/2

qΞZ
1−q

.

holds it satisfies
(i)

(i)

(i)

yt,s+1 − yt,s ≤ 18ηs+1 Ξx · yt,s + 4ηs+1 Ξx ·

q
(i)
(i)
2
2
yt,s + 40ηs+1
Ξ2x ≤ 20ηs+1 Ξx · yt,s + 42ηs+1
Ξ2x .

Putting the above bounds together, one can verify that the random process {yt,s }t∈[T ],s≤t−1 satisfy
assumption (A1) of Lemma i.D.1 with19
2
2
Ξ2x )y (1) + 40ηs+1
Ξ2x + 20ηs+1
fs(1) (y, q) = (1 + 56ηs+1

3/2

qΞZ
1−q

,

2
2
Ξ2x + 20ηs+1
fs(2) (y, q) = (1 − 2ηs+1 ρ + 56ηs+1
Ξ2x )y (2) + 40ηs+1

3/2

qΞZ
1−q

,

2
2
Ξ2x )y (3+j) + ηs+1 λk y (3+j+1) + 40ηs+1
Ξ2x + 20ηs+1
fs(3+j) (y, q) = (1 − ηs+1 λk + 56ηs+1

3/2

qΞZ
1−q

,

2
gs(i) (y) = 20ηs+1 Ξx · y (i) + 42ηs+1
Ξ2x , and

2
(i)
h(i)
s (y, q) = gs (y)

Verification of Assumption (A2) of Lemma i.D.1.
(i)
For coordinates i = 1 and i = 2, our assumption kZ> Q(V> Q)−1 k2F ≤ ΞZ implies yt,0 ≤ ΞZ <
h
(i)
j−1
>
Q(V> Q)−1 2 ≤
φt,0 . For coordinates i ≥ 3, we have assumption Prxt ∀j ∈ [T ], x>
t ZZ (Σ/λk+1 )
i
def 
(i)
(i)
Ξx ≥ 1 − q 2 /2. Together, event Et (recall Et = xt satisfies ∀i ∈ [D] : yt,0 ≤ φt,0 ) holds for all
t ∈ [T ] with probability at least 1 − q 2 /2. In sum, assumption (A2) is satisfied in Lemma i.D.1.

Verification of Assumption (A3) of Lemma i.D.1.
For every t ∈ [T ], at a high level assumption (A3) is satisfied once we plug in the following three
sets of parameter choices to Corollary i.C.4 and Corollary i.C.5: for every s ∈ [T − 1], define
βs,1 = 0,

δs,1 = 0,

τs,1 = 20ηs+1 Ξx

βs,2 = 2ηs+1 ρ,

δs,2 = 0,

τs,2 = 20ηs+1 Ξx

βs,3 = 0,

δs,3 = ηs+1 λk

τs,3 = 20ηs+1 Ξx

More specifically, for every t ∈ [T ], let
Lemma i.D.1. Define q2 = q 2 /8.

{zs }t−1
s=0

be the arbitrary random vector satisfying (i.D.1) of

• For coordinate i = 1 of {zs }t−1
s=0 ,
– apply Corollary i.C.4 with {βs,1 , δs,1 , τs,1 }t−2
s=0 , q = q2 , D = 1, and κ = 1;
• For coordinate i = 2 of {zs }t−1
s=0 ,
– if t < T0 , apply Corollary i.C.4 with {βs,2 , δs,2 , τs,2 }t−2
s=0 , q = q2 , D = 1, and κ = 1;
t−2
– if t ≥ T0 , apply Corollary i.C.5 with {βs,2 , δs,2 , τs,2 }s=0 , q = q2 , D = 1, γ = 1, and κ = 1;
• For coordinates i = 3, 4, . . . , T + 2 of {zs }t−1
s=0 ,
– apply Corollary i.C.4 with {βs,3 , δs,3 , τs,3 }t−2
s=0 , q = q2 , D = T , and κ = 1.

19


(i)
(i)
The only part of (A1) that is non-trivial to verify is (A1e) for gs . Whenever fs x, 0 ≤ x(i) , it satisfies

if i = 1;
 0,

2ηs+1 ρ · x(2) , if i = 2; ≤ 2ηs+1 · x(i) ≤ gs(i) (x) ,
fs(i) x, 0 − x(i) ≤

ηs+1 λk · x(i) , if i ≥ 3.

where the second inequality uses ρ, λk ≤ 1 and the last inequality uses Ξx ≥ 2.

31

One needs to verify that the assumptions of Corollary i.C.4 and i.C.5 are satisfied as follows.
First of all, one can carefully check that our parameters β, δ, τ satisfy (i.C.2) with κ = 1 and this
needs our assumption q ≤ ηs+1
3/2 . Next, we can apply Corollary i.C.4 because our assumptions on ηs
ΞZ
PT −1 2
1
1
imply s=0 τs,i ≤ 100
ln−1 4T
q2 and τs,i ≤ 24 log(4T /q2 ) for i = 1, 2, 3. To verify the presumption of
Corollary i.C.5 with γ = 1, we notice that
• our assumption ηs ≤

ρ
4000·Ξ2x ln

3T
q2

2
implies βs,2 ≥ 10 ln 3T
q2 · τs,2 and κτs ≤

1
12 ln

3T
q2

for every s,

P 0 −1
P
3t 2
• our assumption Ts=0
βs,2 ≥ 1 + ln ΞZ implies t−1
s=0 βs − 10 ln q2 τs ≥ ln ΞZ + 1 − 1 = ln ΞZ
whenever t > T0 ,
Therefore, the conclusion of Corollary i.C.4 and Corollary i.C.5 imply that
(i)

(i)

Pr[∃i ∈ [3] : zt−1 > φt,t−1 ] ≤ 3q2 < q 2 /2

so assumption (A3) of Lemma i.D.1 holds.

Application of Lemma i.D.1. Applying Lemma i.D.1, we have Pr[CT ] ≤ 2qT which implies
our desired bounds and this finishes the proof of Lemma Main 1.


i.E.2

After Warm Start

Proof of Lemma Main 2. For every t ∈ [T ] and s ∈ {0, 1, ..., t − 1}, consider the same random
vectors yt,s ∈ RT +2 defined in the proof of Lemma Main 1:
(1)

def

(2)

def

yt,s = kZ> Ps Q(V> Ps Q)−1 k2F ,

yt,s = kW> Ps Q(V> Ps Q)−1 k2F ,

 x> ZZ> (Σ/λ )j P Q(V> P Q)−1
s
s
(3+j) def
k+1
t
yt,s
=
 (1 − η λ ) · y (3+j) ,
s k

2
2

, for j ∈ {0, 1, . . . , t − s − 1};

t,s−1

This time, we consider slightly different upper bounds

2ΞZ
if s < T0 ;


(1) def
(2) def
2
if s = T0 ; ,
φt,s = 2ΞZ , φt,s =

 5T0 / ln22(T0 ) if s > T0 .

for j ∈ {t − s, . . . , T − 1}.

(3+j)

and φt,s

def

= 2Ξ2x .

s/ ln s

We stress that the only difference between the above upper bounds and the ones we used in the
(2)
proof of Lemma Main 1 is the choice of φt,s for s > T0 . Instead of setting it to be constant 2 for
all such s, we make it decrease almost linearly with respect to index s.
Again, define event


h
i
(i)
(i)
0 def
Ct = (x1 , ..., xt−1 ) satisfies Pr ∃i ∈ [3] : yt,t−1 > φt,t−1 Ft−1 ≤ q
xt
n
o
def
(i)
(i)
Ct00 = (x1 , ..., xt ) satisfies ∀i ∈ [3] : yt,t−1 ≤ φt,t−1
def
def V
and denote by Ct = Ct0 ∧ Ct00 and C≤t = ts=1 Cs .
We next want to apply the decoupling Lemma i.D.1.
Verification of Assumption (A1) in Lemma i.D.1.
(i)
(i)
(i)
The same functions fs , gs , and hs used in the proof of Lemma Main 1 still apply here.
(i)
However, we want to make a minor change on gs whenever s ≥ T0 .

32

Applying Lemma i.B.1-(c) with φt = 2Ξx , we have whenever C≤s+1 holds for some s ≥ T0
(2)
(which implies yt,s ≤ 5),
q
q
(2)
(2)
(2)
(2)
(2)
2
2
|yt,s+1 − yt,s | ≤ 18ηs+1 Ξx yt,s + 4ηs+1 Ξx yt,s + 40ηs+1
Ξ2x ≤ 45ηs+1 Ξx yt,s + 40ηs+1
Ξ2x .
Therefore, we can choose

gs(2) (y)

q
2
= 45ηs+1 Ξx y (2) + 40ηs+1
Ξ2x

for all s ≥ T0 and this still satisfies assumption (A1) of Lemma i.D.1.20
Verification of Assumption (A2) of Lemma i.D.1.
This is the same as the proof of Lemma Main 1.
Verification of Assumption (A3) in Lemma i.D.1.
Again, for every t ∈ [T ], let {zs }t−1
s=0 be the arbitrary random vector satisfying (i.D.1) of
2
Lemma i.D.1. Choosing q2 = q /8 again, the same proof of Lemma Main 1 shows that
(i)

(i)

Pr[∃i ∈ {1, 3} : zt−1 > φt,t−1 ] ≤ 2q2 .
(2)

(2)

Therefore, it suffices to prove that Pr[zt−1 > φt,t−1 ] ≤ 2q2 .

(2)

We only need to focus on the case t ≥ T0 + 2, because otherwise if t ≤ T0 + 1 then gs is
(2)
not changed for all s ∈ {0, . . . , t − 2} so the same proof of Lemma Main 1 also shows Pr[zt−1 >
(2)

φt,t−1 ] ≤ q2 .
When t ≥ T0 + 2, we can first apply the same proof of Lemma Main 1 (for t = T0 + 1) to show
(2)
(2)
(2)
that Pr[zT0 > φT0 +1,T0 = 2] ≤ q2 . Next, conditioning on zT0 ≤ 2 which happens with probability
1
.
at least 1 − q2 , we want to apply Corollary i.C.3 with κ = 2 and τs = δs
More specifically, for every t ∈ {T0 + 2, . . . , T }, we have shown that the random sequence
(2)
{zs }t−1
s=T0 satisfies (i.D.1) with

(2)

2
2
fs(2) (y, q) = (1 − 2ηs+1 ρ + 56ηs+1
Ξ2x )y (2) + 40ηs+1
Ξ2x + 20ηs+1
q
(2)
2
gs (y) = 45ηs+1 Ξx y (2) + 40ηs+1
Ξ2x
2
(2)
h(2)
s (y, q) = gs (y)

Therefore, {zs }t−1
s=T0 also satisfies (i.C.1) with κ = 2 and τs =
our assumptions:

1
δτs

3/2

qΞZ
1−q

because the following holds from

1
2
≤ 2ηs+1 ρ − 56ηs+1
Ξ2x
s
3/2
1
2
qΞZ
2
2
τs2 = 2 2 ≥ 60ηs+1
Ξ2x ≥ 40ηs+1
Ξ2x + 20ηs+1 1−q
κτs =
≥ 40ηs+1 Ξx
δ s
δs
Now, we are ready to apply Corollary i.C.3 with q = q2 , t0 = T0 , and κ = 2. Because q2 ≤ e−2 ,
√
(2)
2)
zT0 ≤ 2, δ ≤ 1/ 8 and lnT2 0T ≥ 9 ln(1/q
, the conclusion of Corollary i.C.3 tells us
δ2
3/2

qΞZ ≤ ηs+1

δτs =

0

(2)

(2)

(2)

Pr[zt−1 > φt,t−1 | zT0 ≤ 2] ≤ q2 .

(2)

(2)

By union bound, we have Pr[zt−1 > φt,t−1 ] ≤ q2 + q2 = 2q2 as desired.
Finally, we conclude (for every t ≥ T0 + 2) that
(i)

(i)

Pr[∃i ∈ [3] : zt−1 > φt,t−1 ] ≤ 4q2 < q 2 /2



(i)
(2)
(2)
Similar to Footnote 19, we also need to verify (A1e) for gs . Whenever fs x, 0 ≤ x(2) , it satisfies fs x, 0 −
(2)
x(2) ≤ 2ηs+1 · x(2) ≤ gs (x) , where the first inequality uses ρ ≤ 1 and the second uses Ξx ≥ 2.
20

33

so assumption (A3) of Lemma i.D.1 holds.
Application of Lemma i.D.1. Applying Lemma i.D.1, we have Pr[CT ] ≤ 2qT which implies
our desired bounds and this finishes the proof of Lemma Main 2.


i.F

Proof of Theorem 1’ and 2’

Proof of Theorem
apply Lemma 5.1 with p0 = p6
 1 2’. pFirst for a sufficiently large constant C, we can
and q = min CT 2 d2 , 4T and obtain: with probability at least 1−p0 −q 2 ≥ 1−p/2 over the random
choice of Q, the following holds:

>
>
−1 2 ≤ 20736dk ln 6d , and

 (Z Q)(V" Q)
p
p2
F
#
q
i−1
>
>
>
−1

 Prx1 ,...,xT ∃i ∈ [T ], ∃t ∈ [T ], xt ZZ (Σ/λk+1 ) Q(V Q)

2

≥

216

k ln
p

2T
q

≤

q2
2

.

Denote by C1 the union of the above two events, and we have PrQ [C1 ] ≥ 1 − p/2.
Now, for every fixed Q, whenever C1 holds, we can let
q
216
2k ln 2T
p
20736dk 6d
ln , Ξx =
,
ΞZ =
2
p
p
p
so the initial conditions in Lemma Main 1 (and thus Lemma Main 2) is satisfied. Also, according
to Parameter 7.1, our parameter choices satisfy the assumptions in Lemma Main 2. Finally, the
conclusion of Lemma Main 2 immediately implies for every T ≥ T0

 

T0
p
>
>
−1 2
e
Pr ∀t = {T0 , . . . , T } : kW Pt Q(V Pt Q) kF ≤ O
C1 ≥ 1 − 2qT ≥ 1 − .
x1 ,...,xT
t
2
Union bounding this with event C1 , we have

 
T0
>
>
−1 2
e
Pr
∀t = {T0 , . . . , T } : kW Pt Q(V Pt Q) kF ≤ O
≥1−p .
Q,x1 ,...,xT
t

Combining this with Lemma 2.2 completes the proof.

Finally, Theorem 1’ is a direct corollary of Theorem 2’ by setting ρ ← gap.

34



Appendix (Part II)
Theorem a.
In this part II of the appendix, we provide our proofs for the lower bound Theorem 6, as well
as that for the Rayleigh quotient Theorem 3.
• Appendix ii.G extends our main lemmas to better serve for the rayleigh quotient setting;
• Appendix ii.H provides the final proof for our Rayleigh Quotient Theorem 3;
• Appendix ii.I includes a three-paged proof of our lower bound Theorem 6.

Below we address, at a high level, the main ideas needed behind our main lemma extension as
well as the proof of Theorem 3.
Additional Ideas Needed for Theorem 3. In order to prove Theorem 3 which is the rayleighquotient guarantee in gap-free streaming PCA, we want to strengthen Lemma Main 1 so that it
provides guarantee essentially of the form:
for every γ ≥ 1 :

Wγ> Pt Q(V> Pt Q)−1

2
F

≤ 2/γ ,

(ii.F.1)

where Wγ is the column orthonormal matrix consisting of all eigenvectors of Σ with eigenvalues
≤ λk − γ · ρ. For obvious reason Lemma Main 1 is a special case of (ii.F.1) when restricting only to
γ = 1. It is a simple exercise to show that (ii.F.1) implies our desired rayleigh-quotient guarantee
(via an Abel transformation and an integral computation, see Appendix ii.H).
Therefore, it suffices to prove (ii.F.1). If one were allowed to magically change learning rates and
apply Lemma Main 1 multiple times, then (ii.F.1) would be trivial to prove: just replace W with
Wγ and replacing ρ with γ · ρ and repeatedly apply Lemma Main 1. Unfortunately, the difficulty
arises because want to prove (ii.F.1) for all γ ≥ 1 but with a fixed set of learning rates ηt .
In Appendix ii.G, we showed that the same learning rates in Parameter 7.1, together with a
more general martingale concentration lemma (i.e., Corollary i.C.5 with γ ≥ 1), one can obtain
(ii.F.1) and we call it Lemma Main 3. This proof follows from the same structure as that of
Lemma Main 1 except for the change in how we apply Corollary i.C.5.
Finally, Theorem 3 follows from Lemma Main 3 for a one-paged reason, see Appendix ii.H.

35

ii.G

Improved Main Lemma

In this section we also sketch the proof to obtain Rayleigh quotient result. We will prove the
following lemma which is a strengthened version of Lemma Main 1.
Lemma Main 3 (before warm start). In the same setting as Lemma Main 1, suppose we redefine
W = Wγ to be the column orthonormal matrix consisting of eigenvectors of Σ with values ≤
λk − γ · ρ.
Then, for every γ ∈ [1, 1/ρ], with probability at least 1 − 2qT :
2
2
∀t ∈ {T0 , . . . , T }, Wγ> Pt Q(V> Pt Q)−1 F ≤
.
γ
Proof of Lemma Main 3. The proof is a non-trivial adaption of the proof of Lemma Main 1.
We redefine W = Wγ and consider random vectors yt,s ∈ RT +2 defined in the same way as the
proof of Lemma Main 1. This time, we consider upper bounds

2ΞZ s < T0 ;
(1) def
(2) def
(3+j) def
φt,s = 2ΞZ , φt,s =
, and φt,s = 2Ξ2x
2/γ s ≥ T0 .

so the only difference we make here is on coordinate i = 2 for s ≥ T0 . For each t ∈ [T ], we also
def
def V
consider events Ct0 , Ct00 , Ct = Ct0 ∧ Ct00 , and C≤t = ts=1 Cs defined in the same way as before.

Verification of Assumption (A1) in Lemma i.D.1.
We consider the same functions fs , gs , hs as defined in the proof of Lemma Main 1, except
that we replace ρ with γ · ρ because this time we have redefined W = Wγ so that it consists of
eigenvectors with values ≤ λk − γ · ρ. In other words, we redefine
2
2
fs(2) (y, q) = (1 − 2ηs+1 γρ + 56Ληs+1
Ξ2x )y (2) + 40ηs+1
ΛΞ2x + 20ηs+1

3/2

qΞZ
1−q

.

In the same way we can verify that these functions satisfy assumption (A1) of Lemma i.D.1.
Verification of Assumption (A2) of Lemma i.D.1.
This step is exactly the same as the proof of Lemma Main 1 so ignored here.
Verification of Assumption (A3) of Lemma i.D.1.
We consider the same parameters {βs , δs , τs }s as Lemma Main 1 except that at coordinate i = 2
we replace ρ with γ · ρ:
βs,2 = 2ηs+1 γρ,

δs,2 = 0,

τs,2 = 20Ληs+1 Ξx .

Now, for every t ∈ [T ], let {zs }t−1
s=0 be the arbitrary random vector satisfying (i.D.1) of Lemma i.D.1.
2
Letting q2 = q /8, we can handle coordinates i = 1 and i ≥ 3 in the same way as before. As for
t−1
coordinate i = 2 of {zs }s=0
,
• if t < T0 , apply Corollary i.C.4 with {βs,2 , δs,2 , τs,2 }t−2
s=0 , q = q2 , D = 1, and κ =

√1 ;
Λ

• if t ≥ T0 , apply Corollary i.C.5 with {βs,2 , δs,2 , τs,2 }t−2
s=0 , q = q2 , D = 1, γ = γ, and κ =

√1 ;
Λ

Note that the t < T0 case is exactly the same as before. When t ≥ T0 , we again apply Corollary i.C.5
but this time with value γ ≥ 1 rather than γ = 1. Since this is the only difference here, we only
need to verify the the presumptions of Corollary i.C.5:
• our assumption ηs ≤

ρ
4000Λ·Ξ2x ln

3T
q2

2
implies βs,2 ≥ 20γ ln 3T
q2 · τs,2 and κτs ≤

P 0 −1
P
3t 2
• our assumption Ts=0
βs,2 ≥ 1 + ln ΞZ implies t−1
s=0 βs,2 − 10γ ln q2 τs,2 ≥
whenever t > T0 .
36

1
12 ln
1
2

3T
q2

Pt−1

for every s,

s=0 βs,2

≥ ln ΞZ

Therefore, in the same way as the old proof in Lemma Main 1, we can conclude using Corollary i.C.4
and Corollary i.C.5 that
(i)

(i)

Pr[∃i ∈ [3] : zt−1 > φt,t−1 ] ≤ 3q2 < q 2 /2 .

This verifies assumption (A3) of Lemma i.D.1.

Application of Lemma i.D.1. Applying Lemma i.D.1, we have Pr[CT ] ≤ 2qT which implies
our desired bounds and this finishes the proof of Lemma Main 3.


ii.H

Proof of Theorem 3: Rayleigh Quotient

e
Theorem 3 (restated). In the same setting as Theorem 2’, we have for every T = Θ
letting qi be the i-th column of the output matrix QT , then
h
i
e
Pr ∀i ∈ [k], qi> Σqi ≥ λi − Θ(ρ)
≥1−p .

k
ρ2 ·p2



,

e hides poly-log factors in 1 , 1 and d.
Again, Θ
p ρ

Proof of Theorem 3. Since the statement of Theorem 3 uses the same learning rates21 as in Theorem 2’,
the same proof of Theorem 2’ ensures that the initialization assumptions in Lemma Main 3 are satisfied and thus we can apply Lemma Main 3.
We want to prove next the output matrix QT = [q1 , . . . , qk ] ∈ Rd×k satisfies
1
with probability at least 1 − (2kdT )q, ∀i ∈ [k] : qi> Σqi ≥ λi − 3ρ ln .
(ii.H.1)
ρ
For every i ∈ [k], let QiT ∈ Rd×i denote the first i-columns of QT . By the property of Oja’s
algorithm, the same QiT would have been the output if we started from an Rd×i random matrix
Q0 for streaming i-PCA. In other words, we can write QiT = [q1 , . . . , qi ].
Letting Wγi be the column orthonormal matrix consisting of all eigenvectors of Σ with eigenvalue
≤ λi − γ · ρ, we applying Lemma Main 3 (with k = i) and obtain:
w.p. at least 1 − 2qT :

k(Wγi )> QiT k2F ≤ k(Wγi )> PT Qi (V> PT Qi )−1 k2F ≤ 2/γ .

(Above, the first inequality uses Lemma 2.2.) This in particular implies k(Wγi )> qi k22 ≤
Let us define for each i ∈ [k],
nλ − λ
o
 1
def
def λi − λj
i
j
λi − λj ≥ ρ ⊆ R≥1 and γi,j =
.
Γi =
∈ 1,
ρ
ρ
ρ
By union bound,
w.p. at least 1 − 2qkdT , ∀i ∈ [k], ∀γ ∈ Γi :

k(Wγi )> qi k22 ≤ 2/γ .

2
γ

.

(ii.H.2)

We are now ready to bound Rayleigh quotient. For each i ∈ [k], let i0 be the index of the first
def P
(i.e., the largest) eigenvector with eigenvalue ≤ λi − ρ and define bi,j = ds=j hqi , νj i2 where νj is
the j-th largest eigenvector of Σ. It satisfies bi,1 = 1. By Abel’s formula,
qi> Σqi

=

d
X
j=1

21

2

λj hqi , νj i ≥ (λi − ρ) −

d
X

j=i0 +1

bi,j (λj−1 − λj ) .

More precisely, we can use the same Parameter 7.1 together with the same values of Ξx and ΞZ used in Section i.F.

37

Note that for every j ≥ i0 + 1, we have bi,j ≤ kWγi i,j qi k22 ≤
d
X

j=i0 +1

which implies

ii.I

bi,j (λj−1 − λj ) ≤

qi> Σqi

≥ λi − 3ρ ln

1
ρ

d
X

j=i0 +1

2
ρ(γi,j
γi,j

2
γi,j

according to (ii.H.2). Therefore,
Z 1
ρ 1
1
− γi,j−1 ) ≤ 2ρ
dz ≤ 2ρ ln ,
ρ
1 γ



so (ii.H.1) holds.

Proof of Theorem 6: Lower Bound

In this section we prove the following lower bound. Without loss of generality, we only focus on
the case when d = 2(k + m) and the case for d > 2(k + m) can be done by padding zeros. Denoting
by S(2(k+m))×k the set of all (column) orthonormal matrix in R(2(k+m))×k ,
Theorem 6 (lower bound, restated). For every k ∈ N∗ , every m ≥ 0 that is an integral
multiple of

1
λ
λ
∗
k, for every λ ∈ (0, 4(k+m) ], every δ ∈ (0, 2 ], every T ∈ N satisfying T ≥ Ω δ2 , every algorithm

A : (R2(k+m) )⊗T → S(2(k+m))×k , there exists a distribution µ over vectors in R2(k+m) such that




>
>
all x ∼ µ satisfies kxk2 ≤ 1, λk E [xx ] ≥ λ, λk+m+1 E [xx ] ≤ λ − δ .
x∼µ

x∼µ

def

Furthermore, let QT = A(x1 , . . . , xT ) be the output with respect to T i.i.d. random inputs
x1 , ..., xT from µ, we have


 >

kλ
2
,
E
kQT WkF = Ω 2
x1 ,...,xT ,A
δ T
where W consists of all the last d − (k + m) eigenvectors of Ex∼µ [xx> ].

We shall just prove this theorem for gap case, i.e. when m = 0. For the gap free case, the
theorem follows by first obtaining µ for the m = 0 case and for λ0 = λ · m+k
k , and then modifying it
(m/k) independent copies from µ, and then concatenate
into some µ0 as follows: first draw x(0)
,
.
.
.
,
x
√
k
them into x0 = (x(0) , . . . , x(m/k) ) · √m+k
and output this x0 instead.
Throughout this section, we use the phrase i-th eigenvalue to denote the i-th largest eigenvalue
of a matrix (tie breaking arbitrarily) and the i-th eigenvector to denote that corresponding to the
i-th eigenvector (with unit norm). We first state a lemma regarding 2 × 2 matrices:
√ √ 
 p
>
Lemma ii.I.1 (2×2 matrix). For every β ∈ 22 , 23 and ε ∈ (0, 2β 2 −1], choose a = β, 1 − β 2 , b =
p
>

β, − 1 − β 2 ∈ R2 and define


1
1
1
1
A = aa> + bb> , B =
+ ε aa> +
− ε bb> .
2
2
2
2
a
b
Then, letting ν1 and ν1 be the top eigenvectors of A and B respectively, letting λ1 , λ2 be the
eigenvalues of A, and λb1 , λb2 be the eigenvalues of B, we have
|hν1a , ν1b i|2 ≤ 1 −

ε2
16(λ1 − λ2 )2

and

λb1 > λ1 = β 2 > 1 − β 2 = λ2 > λb2 .



β2
0
Proof of Lemma ii.I.1. We can calculate that A =
and therefore λ1 = β 2 and
0 1 − β2
!
p
2
2
β
2εβ
1
−
β
2
p
λ2 = 1 − β . We can also compute B =
and the eigenvectors of B
2εβ 1 − β 2
1 − β2
p
are νib = √ 12 (1, si )> with eigenvalues λbi = β 2 + 2εβ 1 − β 2 si for i = 1, 2. Here, s1 ≥ s2 are the
si +1

38



2
2β
√−1
2εβ 1−β 2
have that λb1

two roots of equation s2 +



s − 1 = 0. Since exactly one of the roots is positive (denoted
p
= β 2 + 2εβ 1 − β 2 s1 > λ1 . This also implies λb2 < λ2 since

by s1 ), we immediately
λb1 + λb2 = Tr(B) = 1 = λ1 + λ2 .
2
We now turn to the eigenvectors. Denote by α = 2β√−1 2 and it satisfies α ≤ 2(λ1ε−λ2 ) because
2εβ 1−β
√ √ 
2
3
β ∈ 2 , 2 . Therefore,
√
−α + α2 + 4
2
1
1
ε
√
s1 =
=
≥√
≥q
≥√
.
2
4(λ1 −λ2 )2
8(λ
−
λ
)
α + α2 + 4
α2 + 4
1
2
+4
ε2

Above, the last inequality uses our assumption that ε ≤ 2β 2 − 1 = λ1 − λ2 . On the other hand,
s1 = α+√2α2 +4 ≤ 1. Therefore, we have:

1
s21
ε2
≤
1
−
≤
1
−
.

2
16(λ1 − λ2 )2
1 + s21
√ √ 
Corollary ii.I.2 (Corollary of Lemma ii.I.1). For every β ∈ 22 , 23 and every ε ∈ (0, gap] where
def
gap = 2β 2 − 1, choose a and b in R2 as defined as in Lemma ii.I.1. Define distributions over {a, b}:
1
1
1
µ1 : Pr[x = a] = Pr[x = b] =
and µ2 : Pr[x = a] = + ε, Pr[x = b] = − ε .
2
2
2
2
⊗T
2
Suppose we are given an arbitrary (possibly randomized) algorithm A : (R ) → R for T < O( ε12 ).
Then, if we pick i ∈ {1, 2} each with probability 1/2 and sample T i.i.d. vectors x1 , ..., xT from
distribution µi , it satisfies
kqk22 ε2
E[hq, ν2+ i2 ] ≥
,
512gap2
where q = A(x1 , ..., xT ) is the output of A, ν2+ is the second eigenvector of Eµi [xx> ], and the
expectation is taken over the randomness of i, x1 , ..., xT , and A.
|hν1a , ν1b i|2 =

Proof of Corollary ii.I.2. Without lose of generality, let us assume that kqk2 = 1. Let ν2a , ν2b be the
second eigenvectors of Eµ1 [xx> ] and Eµ2 [xx> ] respectively. Let ν1+ , ν2+ be the two eigenvectors of
Eµi [xx> ], and ν1− , ν2− be the two eigenvectors of Eµ3−i [xx> ].
ε2
Suppose by way of contradiction that E[hq, ν2+ i2 ] < 512gap
2 . Then, we shall construct a protocol
that can, given samples x1 , . . . , xT , with success probability at least 3/4 to tell if the distribution
µi is µ1 or µ2 . However, we cannot distinguish between a fair coin and a 21 ± ε biased coin with
probability ≥ 3/4 with fewer than O(1/ε2 ) samples. This will give a contradiction and finish the
ε2
proof that E[hq, ν2+ i2 ] ≥ 512gap
2.
We define the following protocol: on input samples x1 , ..., xT , run algorithm A and get output
ε2
q = A(x1 , . . . , xT ); then, declare distribution µ1 if hq, ν2a i2 < 128gap
2 , or distribution µ2 otherwise.
Using Markov’s inequality, with probability at least
2

3
4,

ε2
. In this
128gap2
+ − 2
ε2
hν1 , ν2 i ≥ 16gap2 . Using

it satisfies hq, ν2+ i2 <

ε
1
case, we have hq, ν1+ i2 ≥ 1 − 128gap
2 ≥ 2 . By Lemma ii.I.1, we also have
these two together we can derive that

hq, ν2− i2 = (hq, ν1+ ihν1+ , ν2− i + hq, ν2+ ihν2+ , ν2− i)2
1
ε2
ε2
ε2
≥
hq, ν1+ i2 hν1+ , ν2− i2 − hq, ν2+ i2 hν2+ , ν2− i2 ≥
−
≥
.
2
64gap2 128gap2
128gap2
This means, the protocol we just defined can declare the correct µi : indeed, among the two
ε2
vectors {ν2a , ν2b } = {ν2+ , ν2− }, the incorrect one (namely, ν2− ) will not satisfy hq, ν2− i2 < 128gap

2.
39

q
1+δ/λ
so 2β 2 − 1 = λδ . Let ε ∈ (0, λδ ] be defined such that
Proof of Theorem 6 . Choose β =
2

2λT /β 2 = Θ( ε12 ). (We can do so because T ≥ Ω δλ2 .) We let a and b be the two vectors defined
in Lemma ii.I.1 with parameters β, ε.
We also denote by A0 and A1 respectively the two 2 × 2 matrices from Lemma ii.I.1:
!
p
 2

2
2
β
2εβ
β
0
1
−
β
p
A0 =
and A1 =
.
0 1 − β2
1 − β2
2εβ 1 − β 2
Now, consider the following procedure to generate T random vectors x1 , . . . , xT ∈ R2k . At the
beginning, pick a vector z ∈ {0, 1}k uniformly at random from the 2k choices. Then, in each of the
T rounds,
1. Pick y ∈ [0, 1] uniformly at random.

2. If y > kλ/β 2 , output xt = 0; otherwise continue to the next step. (Note kλ/β 2 ∈ [0, 1].)
3. Pick i ∈ [k] uniformly at random.
4. If zi = 0, then pick

xt = 0⊕2(i−1) ⊕ a ⊕ 0⊕2(k−i) w.p. 1/2 and xt = 0⊕2(i−1) ⊕ b ⊕ 0⊕2(k−i) w.p. 1/2

If zi = 1, then pick

xt = 0⊕(i−1) ⊕ a ⊕ 0⊕(k−i) w.p. 1/2 + ε and xt = 0⊕(i−1) ⊕ b ⊕ 0⊕(k−i) w.p. 1/2 − ε
It is clear from the above definition that x1 , . . . , xT are generated i.i.d. from a distribution Dz which
is characterized by vector z. Since kak2 = kbk2 = 1, we also have kxt k2 ≤ 1. By the construction,
k 

M
λ
>
,
A
E [xx ] =
z
i
x∼Dz
β2
i=1

which implies, according to Lemma ii.I.1, for every possible z ∈ {0, 1}k




λ
λ
E [xx> ] ≥ 2 β 2 = λ and λk+1 E [xx> ] ≤ 2 (1 − β 2 ) ≤ λ − δ .
λk
x∼Dz
x∼Dz
β
β

Now, in the total number of T rounds, with probability ≥ 12 , there are less than 2T · kλ
rounds
β2
that xt 6= 0. Denote this event as E. If this happens, then at least 7/8 of i ∈ [k] are picked less than
16T · kλ
· 1 = 16 λT
times. Denote this set of indices as S1 ⊂ [k], and let QT = A(x1 , . . . , xT ) ∈ R2k×k
β2 k
β2
be the output of the algorithm on this random input sequence x1 , . . . , xT . (Recall that the algorithm
does not know the vector z ∈ {0, 1}k ). Let [QT ]i be the i-th row of QT , it holds:
1. ∀i ∈ [2k], k[QT ]i k22 ≤ 1.
P2k
2
2
2.
i=1 k[QT ]i k2 = kQT kF = k.

Therefore, at least 1/4 of j ∈ [k] satisfies k[QT ]2j−1 k22 + k[QT ]2j k22 ≥ 12 . We denote this set of j
def
as S2 ⊂ [k]. Let S = S1 ∩ S2 , then it holds that |S2 | ≥ k8 .
Now we apply Corollary ii.I.2 to each index i ∈ S under event E. We can apply Corollary ii.I.2
because 16λT /β 2 ≤ O( ε12 ) and the algorithm A has received only 16λT /β 2 nonzero samples under
event E. The conclusion of Corollary ii.I.2 implies: for every i ∈ S:

ε2
ε2
+ >
+
2
2
E[(νi,2
) QT Q>
≥
.
T νi,2 | E] ≥ k[QT ]2i−1 k2 + k[QT ]2i k2 ·
512(2β 2 − 1)2
1024(2β 2 − 1)2
+
Above, we have denoted by νi,2
= 0⊕2(i−1) ⊕ ν2+ ⊕ 0⊕2(k−i) where ν2+ is the second eigenvector
+
of Azi . It is clear that νi,2
QT = (ν2+ )> (q1 , ..., qk ) where each qj = ([QT ]2i−1,j , [QT ]2i,j )> ∈ R2 so
we can apply Corollary ii.I.2 on each of them. Thus, using Pr[E] ≥ 21 we conclude:

40

E

"

X
i∈S

+ >
k(νi,2
) QT k22

#

Θ(k)
ε2
1 k
=
=Θ
≥ · ·
2
2
2
2 8 1024(2β − 1)
λ(2β − 1)2 T /β 2



kλ
δ2T



.

Finally, let W be the column orthonormal matrix consisting of the (k + 1)-th till the 2k-th
+
eigenvectors of matrix Ex∼Dz [xx> ]. Since each νi,2
for i ∈ [k] is in one of the columns of W, the
above lower bound implies


h
i
kλ
>
2
E
,
kQT WkF ≥ Ω 2
z,x1 ,...,xT ,QT
δ T
where the expectation is over all possible choices z ∈ {0, 1}k , the random vectors x1 , . . . , xT generated from Dz , and the randomness of the algorithm. By an averaging argument, there exists some
z ∈ {0, 1}k such that


h
i
kλ
>
2
kQT WkF ≥ Ω 2
E
.

x1 ,...,xT ∼Dz ,QT
δ T

41

Appendix (Part III)
In this part III of the appendix, we make non-trivial modifications to Appendix I and derive
our final theorems. More specifically,
• Appendix iii.J extends our initialization lemma in Appendix i.A to stronger settings;

• Appendix iii.K extends our expectation lemmas in Appendix i.B to stronger settings;
• Appendix iii.L extends our main lemmas in Appendix i.E to stronger settings;
• Appendix iii.M provides the final proofs for our Theorem 1 and Theorem 2;
• Appendix iii.N provides the final proofs for our Theorem 4 and Theorem 5.
Theorem a.
Main Ideas Behind Main Lemmas.
Our New Main Lemmas in Appendix iii are extensions of Main Lemmas in Appendix i essentially
with two additional ingredients.
• Under Sampling

This we have already discussed in Section 3 of the main body.

• Variance Bound

Recall that our weaker theorems (such as Theorem 1’) do not have the factor Λ = λ1 +· · ·+λk ∈
[0, 1] show up in the complexity. This speed-up factor 1/Λ could be large and has been argued
as a very important factor in the total running time by [10]. To achieve this, we need tighter
martingale concentrations on our random variables and below we discuss the main intuition.

Recall that all martingale concentrations for a random process {zt }t require some upper bound
between consecutive variables |zt − zt+1 |. If this upper bound holds with probability 1, that
is, |zt − zt+1 |2 ≤ M , then an Azuma-type of concentration can be naturally
used. However,


Azuma concentration is not tight: if one knows a better bound on E |zt+1 − zt |2 | zt , the M
term can be replaced with this expected bound a tighter concentration bound can be implied.
See for instance the survey [5].
This same issue also shows up in streaming PCA. Our Lemma Main 1 and Main 2 have adopted
a probability-one absolute bound on |zt − zt+1 | because that gives the simplest proof. If one
replaces it with a tighter (but very sophisticated) expected bound, the concentration result can
be further improved and this improvement translates to a factor 1/Λ speed-up in the running
time on Oja’s algorithm in the gap-dependent case (and similarly in the gap-free case). We
present such expected bounds in Appendix iii.K.
Additional Ideas for Theorem 2.
While the extended main lemmas are sufficient to prove Theorem 1, they lead again to a
weaker version of Theorem 2 where Λ1 , Λ2 are replaced by (kΛ, kΛ2 ).22 The reason that the factor k shows up is because in gap-free case, there is no “local convergence” (i.e. convergence when
>
−1 2
kPt Q(V> Pt Q)−1 k2 = O(1)) as opposite to the gap-case. Therefore, the quantity kx>
t Pt Q(V Pt Q) k2
will stay at Ω(k) during the entire execution of Oja’s algorithm, and never decreased to O(1).
22
This new weaker version is still weaker than Theorem 2 but already stronger than Theorem 2’. We refrain from
stating it formally in this paper.

42

To overcome this issue, we consider an auxiliary “under-sampled” objective that has a “local
convergence” behavior. As illustrated by Figure 2 on page 57, we define W1 to consist of all
the eigenvectors of eigenvalue ≤ λ − ρ/2, and V1 = W1⊥ contains all eigenvectors of eigenvalue
> λ − ρ/2. Now, we define the auxiliary objective to be W1> Pt Q(V> Pt Q)−1 .
Unlike Z, this new matrix W1 has an eigengap ρ/2 as compared with V, and thus after certain
number of iterations, the quantity kW1> Pt Q(V> Pt Q)−1 k2F can drop to a constant, say ≤ 2.
Now, let us suddenly “shift” our objective to “ kW> Pt Q(V1> Pt Q)−1 k2F ”.23 The crucial
observation is that
>
−1
>
>
−1
>
>
−1
kx>
t Pt Q(V1 Pt Q) k2 ≤ 1 + kW1 Pt Q(V1 Pt Q) k2 ≤ 1 + kW1 Pt Q(V Pt Q) k2 ≤ 3 ,
√
and this is k times smaller than the previous bound
√
>
−1
kx>
t Pt Q(V Pt Q) k2 ≤ O( k) .

Therefore, we can now focus on this random process “ kW> Pt Q(V1> Pt Q)−1 k2F ”, and it converges
a factor Ω(k) faster than the old quantity kW> Pt Q(V> Pt Q)−1 k2F . Finally, Lemma 2.2 tells us
that bounding the former (with respect to V1 ) as opposed to the old quantity (with respect to V)
also implies the convergence of Oja’s algorithm, so we are done.
Additional Ideas for Oja++ Algorithm.
The analysis behind our Oja++ requires a more fine-grind argument regarding the alternation
between “under-sampling” and “objective shift”. As illustrated by Figure 4 on page 60, we consider
a logarithmic long sequence (V1 , W1 ), (V2 , W2 ), . . . and shift carefully and only when needed.
Since our main goal of Oja++ is to remove the factor O(k) in the running time, the spirit behind
these shiftings is the same as the “under-sampled” objective as we discussed above. However, in
this case we need to shift our objective once per epoch, so we need in total logarithmic many of
them.
Also, we need to establish a stronger initialization lemma. Recall that at the beginning of
each epoch of Oja++ , we insert random columns to the working matrix from the previous epoch.
Therefore, the initial matrix Q0 for every epoch (except the first epoch) is not completely fresh
e Q] where Q
e is a (fixed) column orthonormal matrix and
random, but consists of two parts Q0 = [Q,
Q is a fresh random gaussian matrix. We therefore need to re-design our initialization lemma for this
>
−1
> e
> e
−1
particular case, especially to bound the quantity kx>
t Q0 (V Q0 ) k2 = kxt [Q, Q](V [Q, Q]) k2 .
This will be our main focus in the next sub-section.

The matrix V1> Pt Q is not a square matrix anymore because of the shifting, so by inverse we actually mean the
>
−1/2 2
Moore-Penrose pseudo-inverse. kW> Pt Q(V1> Pt Q)−1 k2F is also equal to kW> Pt Q(Q> P>
kF .
t V1 V1 Pt Q)
23

43

iii.J

Final Initialization Lemmas

We state and prove the following lemma using random matrix theory:
Lemma iii.J.1. There exists constants C such that the following holds: Let Q in RN ×n , N ≥ n
be a random matrix with each entry i.i.d. N (0, 1), for every ε > 0,
√
√
1
Pr[λmin (Q> Q) ≤ ε2 ( N − n − 1)2 ] ≤ Cε log
ε
Proof of Lemma iii.J.1. Theorem 1.1 of [15] states that there exist constants C 0 , c > 0 such that
√
√
Pr[λmin (Q> Q) ≤ ε2 ( N − n − 1)2 ] ≤ (C 0 ε)N −n+1 + e−cN .
log

1

log

1

Therefore, if N > 2c ε then we are done. In the case when N ≤ 2c ε , we view Q as a submatrix
e where the entries of Q
e are also i.i.d. generated from N (0, 1).
of an N × N random matrix [Q, Q]
e and conclude that for every α ≤ 0,
In such a case, we can apply Lemma i.A.2 on [Q, Q]
h
2i
e > [Q, Q])
e ≤ α ≤ C 00 · α .
Pr λmin ([Q, Q]
N
>
>
e
e
e > [Q, Q]).
e
Since Q Q is a sub matrix of [Q, Q] [Q, Q], we know that λmin (Q> Q) ≥ λmin ([Q, Q]
Choosing α = εN , we conclude that
√
√
Pr[λmin (Q> Q) ≤ ε2 ( N − n − 1)2 ] ≤ Pr[λmin (Q> Q) ≤ ε2 N ] ≤ O(ε log(1/ε)) .

We prove the following the following initialization lemma that extends Lemma 5.1. Note that
e Q] where Q is a random matrix but Q
e is a fixed one. This
the matrix we are interested now is [Q,
will allow us to perform “under-sampling” and “objective shift” properly.
e ∈ Rd×α , Q ∈ Rd×β , V ∈ Rd×k be three matrices such that
Lemma iii.J.2 (initialization). Let Q
• α, β, k ∈ N where α ≥ 0, β ≥ 1, and α + β ≤ k ≤ d;
• each entry of Q is i.i.d. random from N (0, 1);
e and V are (column) orthonormal;
• Q

e = [] has zero column or Q
e > VV> Q
e  1 I holds.
• either Q
2

Denote by Z ∈ Rd×(d−k) the orthogonal complement of V.
Then, for every p, q ∈ (0, 1), every T ∈ N∗ , every set of random vectors {xt }Tt=1 with kxt k2 ≤ 1,
with probability at least 1 − p − q over the random choice of Q, the following holds:

−1/2 2
e Q] [Q,
e Q]> VV> [Q,
e Q]
• Z> [Q,
≤d·♣ ;
F



−1/2 2
e Q] [Q,
e Q]> VV> [Q,
e Q]
≥♣ ≤q ;
• Pr ∃i, t ∈ [T ], x> ZZ> (Σ/λk+1 )i−1 [Q,
t

x1 ,...,xT

•

where

νj> ZZ> Q(Q> VV> Q)−1/2

2

2

≤ ♣ for every j ∈ [d] .

β · log2 (1/p) · log(T d/q)
e
♣=C· 2 √
=Θ
√
p ( k − α − β − 1)2
def



β
√
√
2
p ( k − α − β − 1)2



.

def
e > VV> Q
e  1 I ∈ Rα×α and by B> def
e > VV> ∈ Rα×d .
Proof of Lemma iii.J.2. Let A2 = Q
= A−1 Q
2
We have


e > VV> Q]
e −1 Q> V V .
B> B = I and BB> = V> V> Q[Q

44

e > VV> Q]
e −1/2 is a column orthonormal matrix, we can always find C such that
Since V> Q[Q
VV> − BB> = CC>  0,

C> B = 0,

Therefore,


e Q]> VV> [Q,
e Q]
[Q,
=

C ∈ Rd×(k−α) .

!
e > VV> Q
e Q
e > VV> Q
Q
e Q> VV> Q
Q> VV> Q




A
I
B> Q
A
=
I
I
Q> B Q> (BB> + CC> )Q

Let us denote Qb = B> Q ∈ Rα×β , Qc = C> Q ∈ R(k−α)×β , σ = σmin (Q>
c Qc ), we then have:






I
Qb
A
A
>
> e
e
[Q, Q] VV [Q, Q]

I
I
Q>
Q>
b
b Qb + σI
Which implies that
 −1

  −1


−1
A
I + σ −1 Qb Q>
−σ −1 Qb
A
b
e Q]> VV> [Q,
e Q]
[Q,

I
I
−σ −1 Q>
σ −1 I
b


−σ −1 Qb
I + σ −1 Qb Q>
b
 2
−1
>
σ −1 I
−σ Qb


I 0
>
>
+ 2σ −1 [Q>
(iii.J.1)
= 2
b , −I] [Qb , −I] .
0 0

−1 

I
Qb
−σ −1 Qb
I + σ −1 Qb Q>
b
;
=
Above, the first spectral dominance uses
Q>
Q>
σ −1 I
−σ −1 Q>
b Qb + σI
b
b
the second spectral dominance uses A2  12 I
Now consider any fixed y ∈ Rd with kyk2 ≤ 1. We have

−1
e Q] [Q,
e Q]> VV> [Q,
e Q]
e Q]> y
y > [Q,
[Q,

−1/2

−1/2
e Q] [Q,
e Q]> VV> [Q,
e Q]
e Q] [Q,
e Q]> VV> [Q,
e Q]
= y > VV> [Q,
+ y > ZZ> [Q,

≤ 2 y>V

2
2

−1/2
e Q] [Q,
e Q]> VV> [Q,
e Q]
V> [Q,

2

>

>

>

2



2

−1/2
e Q] [Q,
e Q]> VV> [Q,
e Q]
+ 2 y > ZZ> [Q,

−1
e Q] [Q,
e Q] VV [Q,
e Q]
e Q]> ZZ> y .
≤ 2 + 2y ZZ [Q,
[Q,
>





2

(iii.J.2)

Above, the last inequality uses ky > Vk2 ≤ 1 and the fact that kA(A> A)−1/2 k2 ≤ 1 for every matrix
A that has full column rank. Next, using inequality (iii.J.1), we can bound

−1
1 > > e
e Q]> VV> [Q,
e Q]
e Q]> ZZ> y
y ZZ [Q, Q] [Q,
[Q,
2

e 2 + σ −1 ky > ZZ> QQ
e > − Q ]k2
≤ ky > ZZ> Qk
2
2
b
>
>
>
2
>
>
2
e
2kQb Q ZZ yk2 + 2kQ ZZ yk2
≤ 1+
.
(iii.J.3)
σ
Note that Qb = B> Q ∈ Rα×β , Qc = C> Q ∈ R(k−α)×β , and Z> Q ∈ R(d−k)×β are independent
of each other, because the entries of Q remain independent after rotation and the columns of
def
def
>
>
β
e> >
B, C, Z are pairwise orthogonal. Therefore, letting u1 = Q>
b Q ZZ y and u2 = Q ZZ y ∈ R ,
we have that
e > ZZ> yk2 );
• u1 ∈ Rβ is a random vector with entries i.i.d. in N (0, kBQ
2

• u2 ∈ Rβ is a random vector with entries i.i.d. in N (0, kZZ> yk22 );
45

2
2

• u1 , u2 and σ = σmin (Q>
c Qc ) are independent variables.

e > ZZ> yk2 ≤ 1 and kZZ> yk2 ≤ 1, it implies (using tail bound for chi-squared distriSince kBQ
2
bution) that
∀s ≥ 4 : Pr[ku1 k22 ≥ sβ], Pr[ku2 k22 ≥ sβ] ≤ (se1−s )β/2 ≤ e−s/6 .
def

Putting them into (iii.J.3) and then altogether to (iii.J.2), we claim that under event Cσ =
{σmin (Q> CC> Q) ≥ σ}, we have



−1
16βs
> e
>
> e
>
e
e
Pr y [Q, Q] [Q, Q] VV [Q, Q]
[Q, Q] y ≥ 6 +
(iii.J.4)
Cσ ≤ 2e−s/6 .
σ
Final Probability Arguments. Let us now take σ =

√
√
p2 ( k−α− β−1)2
c2 ·log2 (1/p)

for a large enough constant

c2 , we have Pr[Cσ ] ≥ 1 − p/2 according to Lemma iii.J.1. We also take s = Θ log(T d/q) , and it
satisfies


β · log2 (1/p) · log(T d/q)
16βs
√
=♣ .
=Θ
6+
√
σ
p2 ( k − α − β − 1)2
We now apply (iii.J.4) multiple times in two different manners
• We can apply (iii.J.4) with y = ν1 , ν2 , . . . , νd which are the eigenvector of Σ. By union bound,
we have Pr[C1 |Cσ ] ≥ 1 − q where C1 is the following event



−1/2 2




>
>
>
e Q] [Q,
e Q] VV [Q,
e Q]
 Z [Q,

≤ d · ♣ , and
def
C1 =
F

−1/2 2



e Q] [Q,
e Q]> VV> [Q,
e Q]
 ∀j ∈ [d] : νj ZZ> [Q,

≤♣ 
2

• Define 
event

−1/2
i−1 e
>
>
> e
e
ZZ
(Σ/λ
)
[
Q,
Q]
[
Q,
Q]
VV
[
Q,
Q]
C2 = ∃i ∈ [T ], ∃t ∈ [T ], x>
k+1
t
i−1
>
x>
t ZZ (Σ/λk+1 )

2


≥♣ .

(and we can do so
Then, we apply (iii.J.4) multiple times each with y =
because kyk2 ≤ 1). By union bound, we have for every fixed x1 , ..., xT , it satisfies PrQ [C2 |
Cσ , x1 , ..., xT ] ≤ q 2 . Denoting by 1C2 the indicator function of event C2 , then




1
Pr [C2 | Q] Cσ
Pr Pr [C2 | Q] ≥ q Cσ ≤ E
Q x1 ,...,xT
q Q x1 ,...,xT


1
E [1C | Q] Cσ
= E
q Q x1 ,...,xT 2


1
E
E[1C | Cσ , x1 , . . . , xT ]
=
q x1 ,...,xT Q 2


1
=
E
Pr[C2 | Cσ , x1 , . . . , xT ]
≤ q .
q x1 ,...,xT Q
Above, the first inequality uses Markov’s bound.


In sum, we just derived that PrQ [C1 |Cσ ] ≥ 1 − q and PrQ Prx1 ,...,xT [C2 | Q] ≥ q ≤ q. Applying
union bound again we have
h
i
Pr C1 ∧ Pr [C2 | Q] ≤ q ≥ 1 − p − 2q .
Q

x1 ,...,xT



This finishes the proof of Lemma iii.J.2.

46

iii.K

Final Expectation Lemmas

This section extends Appendix i.B to provide better bounds regarding the expected behaviors of
the random process we are interested. Recall that if X ∈ Rd×r is a generic matrix (either X = W,
X = Z, or X = [w] for some vector w), we have the following notions from Section 6.
Lt = Pt Q(V> Pt Q)−1 ∈ Rd×k

r×k
R0t = X> xt x>
t Lt−1 ∈ R

St = X> Lt ∈ Rr×k

k×k
H0t = V> xt x>
t Lt−1 ∈ R

Our next lemma is a stronger version of Lemma 6.1. It provide tighter expected bounds
byh introducing an additional factor
Γ, and introduce new bounds regarding the variance terms
i
2
>
>
E Tr(St St ) − Tr(St−1 St−1 ) .

Lemma iii.K.1. For every t ∈ [T ], For every t ∈ [T ], let C≤t be any event that depends on random
x1 , . . . , xt and implies
1
>
>
−1
∀j ∈ [d], kνj> Lt−1 k2 ≤ φt , kx>
,
t Lt−1 k2 = kxt Pt−1 Q(V Pt−1 Q) k2 ≤ φt where ηt φt ≤
2
and E[xt x>
t | F≤t−1 , C≤t ] = Σ + ∆. Let m be the largest integer such that λk+m > λk − ρ, and


k
k+m
X

X
def
def
Γ = min
λi + φ2t
λj + k∆k2 , 1
and χ = k + mφ2t


i=1

j=k+1

. We have:
(a) If X = [w] ∈ Rd×1 where w is a vector with Euclidean norm at most 1,
h
i

ηt
2 2
>
2 2
kw> ΣLt−1 k22
E Tr(S>
t St ) | F≤t−1 , C≤t ≤ 1−ηt λk +14Γηt φt Tr(St−1 St−1 )+10Γηt φt +
λk


1/2

1/2 
>
>
>
+ 2ηt k∆k2 Tr(S>
S
)
+
Tr(S
S
)
1
+
Tr(Z
L
L
Z)
t−1 t−1
t−1 t−1
t−1 t−1
(b) If X = [w] ∈ Rd×1 where w is a vector with Euclidean norm at most 1,
i
h
2
>
|
F
,
C
E Tr(S>
S
)
−
Tr(S
S
)
t−1 ≤t
t−1 t−1
t t

2
2 2
>
4 4
≤ 243Γηt2 φ2t Tr(S>
t−1 St−1 ) + 12Γηt φt Tr(St−1 St−1 ) + 300Γηt φt

(c) If X = W,
h
i
E Tr(S>
S
)
|
F
,
C
t−1 ≤t
t t


2
≤ 1 − 2ηt ρ + 12Γηt2 φ2t + ηt2 (6φt + 8)λk+1 Tr(St−1 S>
t−1 ) + 10Γηt (2φt + 8)


3/2
>
>
+ 2ηt k∆k2 ηt (4 + φt )χ + Tr(L>
+ (5 + 4ηt )Tr(L>
t−1 ZZ Lt−1 )
t−1 ZZ Lt−1 )

1/2 
>
>
+ Tr(Lt−1 ZZ Lt−1 )
.

(d) If X = W,

>
2
E[|Tr(S>
t St ) − Tr(St−1 St−1 )|2 | Ft−1 , C≤t ]

2
2
2
>
≤ 192Γηt2 φ2t Tr(St−1 S>
t−1 ) + 4ηt (4φt + 8) λk+1 Tr(St−1 St−1 )

+ 192Γηt4 φ2t + k∆k2 · 4ηt2 (4φt + 8)2 (χ + Tr(S>
t−1 St−1 )) .

47

Proof. The proof of the first two cases rely on the following tighter upper bounds when X = [w]:
n P




 o 2
k
2
E kH0t k22 | F≤t−1 , C≤t ≤ φ2t E kxt Vk22 | F≤t−1 , C≤t ≤ min
λ
+
k∆k
2 , 1 φt ≤ Γφt
i=1 i
o
n





Pk
2
2
E kR0t k22 | F≤t−1 , C≤t ≤ φ2t E kxt Xk22 | F≤t−1 , C≤t ≤ min
i=1 λi + k∆k2 , 1 φt ≤ Γφt

(iii.K.1)

φ2t

as opposed to
that we have used in the past.
The proof of the last two cases rely on different upper bounds for X = W. We introduce
def
some notations that shall be only used in this proof. Let Y = [νk+1 , . . . , νk+m ] ∈ Rd×m be the
matrix consisting of all the eigenvectors of Σ with eigenvalues λk+1 , . .P
. , λk+m . In this
Pnotation,
k
k+m
>
>
>
e
ZZ = YY + WW . We also denote by V = [V, Y]. Let Λ1 = j=1 λj , Λ2 = j=k+1
λj ,
Λ = Λ1 + Λ2 φ2t ≤ Γ.
We make three quick observations:

P
P
>
2
2
> e
e>

= kj=1 λj + k+m

j=k+1 λj kνj Lt k2 ≤ Λ1 + Λ2 φt = Λ ,
 Tr(Lt−1 VΣ≤k+m V Lt )P
k+m
2
2
e e>
(iii.K.2)
Tr(L>
t−1 VV Lt ) = k +
j=k+1 kνj Lt k2 ≤ k + mφt = χ , and



eV
e > + WW> )Lt ) ≤ χ + Tr(S> St−1 ) .
Tr(L> Lt ) = Tr(L> (V
t−1

t−1

t−1

Therefore, we have:

2
2
E[kH0t k22 | F≤t−1 , C≤t ] ≤ φ2t · E[kx>
t VkF | F≤t−1 , C≤t ] ≤ Γφt

2
>
>
E[kR0t k22 | F≤t−1 , C≤t ] ≤ E[kx>
t Lt−1 k2 | F≤t−1 , C≤t ] = Tr(Lt−1 ΣLt−1 ) + Tr(Lt−1 ∆Lt−1 )
e ≤k+m V
e > + WΣ>k+m W> )Lt−1 ) + k∆k2 Tr(L> Lt−1 )
≤ Tr(L> (VΣ
t−1

≤Λ+

=Λ+

t−1

>

λk+1 kW Lt−1 k2F + k∆k2 · (χ + Tr(S>
t−1 St−1 ))
>
λk+1 Tr(St−1 St−1 ) + k∆k2 · (χ + Tr(S>
t−1 St−1 ))

.

(iii.K.3)

We are now ready to prove our four cases individually.

(a) This follows from almost the same proof of Corollary 6.1-(c), except that one can replace the
use of (i.B.10) with the following (owing to (iii.K.1))
h
i
2 2
E Tr(S>
S
)
|
F
,
C
≤ (1 − 2ηt λk + 14Γηt2 φ2t )Tr(St−1 S>
≤t−1 ≤t
t t
t−1 ) + 10Γηt φt

>
>
>
>
>
−2ηt Tr(S>
t−1 St−1 V ∆Lt−1 ) + 2ηt Tr(St−1 w ∆Lt−1 ) + 2ηt Tr(St−1 w ΣLt−1 ) .

(b) This follows directly from Lemma i.B.1-(b) and (iii.K.1).
(c) The exact same first half of the proof of Lemma i.B.1 gives (i.B.1) which using kH0t k2 ≤ φt
gives
>
>
0
>
0
Tr(S>
t St ) ≤ Tr(St−1 St−1 ) − 2ηt Tr(St−1 St−1 Ht ) + 2ηt Tr(St−1 Rt )

0
2
0 2
>
2
0 2
+4ηt2 φt Tr(S>
t−1 Rt ) + 12ηt kHt k2 Tr(St−1 St−1 ) + 8ηt kRt k2 . (iii.K.4)

This time, we upper bound
0
>
>
>
>
>
> e e>
>
|Tr(S>
t−1 Rt )| = |Tr(St−1 W xt xt Lt−1 )| = |Tr(St−1 W xt xt (VV + WW )Lt−1 )|
eV
e > Lt−1 )|
(iii.K.5)
= |Tr(S> W> xt x> WSt−1 ) + Tr(S> W> xt x> V
t−1

t

t−1

¬

t

3
1 >e e>
>
>
2
≤
Tr(S>
t−1 W xt xt WSt−1 ) + kxt VV Lt−1 k2 .
2
2
Above, inequality ¬ is because 2Tr(A> B) ≤ Tr(A> A)+Tr(B> B) which is Young’s inequality

48

in the matrix case. We take expectation and get:


0
E |Tr(S>
t−1 Rt )| | Ft−1 , C≤t
3
1
>
> e e>
e e>
≤ Tr(S>
t−1 W (Σ + ∆)WSt−1 ) + Tr(Lt−1 VV (Σ + ∆)VV Lt−1 )
2
2


1
3
1
3
>
> e
>
>
> e e>
e
Tr(St−1 St−1 ) + Tr(Lt−1 VV Lt−1 )
≤ λk+1 Tr(St−1 St−1 ) + Tr(Lt−1 VΣ≤k+m V Lt ) + k∆k2 ·
2
2
2
2


¬ 3
1
3
χ
(iii.K.6)
Tr(S>
≤ λk+1 Tr(S>
t−1 St−1 ) + Λ + k∆k2 ·
t−1 St−1 ) +
2
2
2
2
Above, inequality ¬ has relied on our earlier observations (iii.K.2). At this point, plugging
(iii.K.6), (iii.K.3) into (iii.K.4) and using the assumption ηt φt ≤ 1/2, we have

2
E[Tr(S>
1 + 12Γηt2 φ2t + ηt2 (6φt + 8)λk+1 Tr(St−1 S>
t St ) | F≤t−1 , C≤t ] ≤
t−1 ) + ηt (2φt + 8)Λ


0
>
0
+ E − 2ηt Tr(S>
t−1 St−1 Ht ) + 2ηt Tr(St−1 Rt ) | F≤t−1 , C≤t


+2ηt k∆k2 · ηt (4 + φt )χ + ηt (4 + 3φt )Tr(S>
.
t−1 St−1 )
Finally, inequality (i.B.8) (from the proof of Corollary 6.1-(a)) gives an upper bound on the
0
>
0
expected value of −Tr(S>
t−1 St−1 Ht ) + Tr(St−1 Rt ). Putting it in gives us the desired bound.

(d) This time we compute a slightly different upper bound from (iii.K.5)

0
>
>
>
>
>
>
>
>
|Tr(S>
t−1 Rt )| = |Tr(St−1 W xt xt Lt−1 )| = |Tr(St−1 W xt xt (VV + ZZ )Lt−1 )|
>
>
>
>
>
>
= |Tr(S>
t−1 W xt xt V) + Tr(St−1 W xt xt ZZ Lt−1 )|
>
>
>
>
>
≤ |Tr(S>
t−1 W xt xt ZZ Lt−1 )| + kSt−1 W xt k2 .

Plugging this into (i.B.1), we obtain

>
>
0
>
0
2
0
>
0
|Tr(S>
t St ) − Tr(St−1 St−1 )| ≤ 2ηt |Tr(St−1 St−1 Ht )| + 2ηt |Tr(St−1 Rt )| + 4ηt kHt k2 Tr(St−1 Rt )
¬

2
0 2
+12ηt2 kH0t k22 Tr(St−1 S>
t−1 ) + 8ηt kRt k2 .

>
0
2
0 2
≤ 8ηt kH0t k2 Tr(St−1 S>
t−1 ) + 4ηt |Tr(St−1 Rt )| + 8ηt kRt k2

>
>
>
>
≤ 8ηt kH0t k2 Tr(St−1 S>
t−1 ) + 4ηt |Tr(St−1 W xt xt ZZ Lt−1 )|
­

>
2
0 2
+4ηt kS>
t−1 W xt k2 + 8ηt kRt k2

>
>
>
1/2
≤ 8ηt kH0t k2 Tr(St−1 S>
t−1 ) + ηt (4φt + 8)Tr(St−1 W xt xt WSt−1 )

+8ηt2 φt kR0t k2

Above, ¬ uses the fact that ηt kH0t k2 ≤ ηt φt ≤ 1/2, and ­ uses kR0t k2 ≤ φt as well as
>
>
>
>
kx>
t ZZ Lt−1 k2 ≤ kxt Lt−1 k2 + kxt VV Lt−1 k2 ≤ (φt + 1)

Taking square on both sides, we have

>
2
2
0 2
>
2
2
2
>
>
>
|Tr(S>
t St ) − Tr(St−1 St−1 )|2 ≤ 192ηt kHt k2 Tr(St−1 St−1 ) + 3ηt (4φt + 8) Tr(St−1 W xt xt WSt−1 )

+192ηt4 φ2t kR0t k22

49

Finally, taking expectation and using (iii.K.3), we have (noticing that ηt φt ≤ 1/2)
>
2
E[|Tr(S>
t St ) − Tr(St−1 St−1 )|2 | F≤t−1 , C≤t ]

2
2
2
>
>
≤ 192Γηt2 φ2t Tr(St−1 S>
t−1 ) + 3ηt (4φt + 8) Tr(St−1 W (Σ + ∆)WSt−1 )


>
+192ηt4 φ2t Λ + λk+1 Tr(S>
S
)
+
k∆k
·
(χ
+
Tr(S
S
))
.
t−1
2
t−1
t−1
t−1



2
2
2
>
≤ 192Γηt2 φ2t Tr(St−1 S>
)
+
3η
(4φ
+
8)
λ
+
k∆k
Tr(S
S
)
t
2
t−1
k+1
t−1
t
t−1


>
+192ηt4 φ2t Λ + λk+1 Tr(S>
t−1 St−1 ) + k∆k2 · (χ + Tr(St−1 St−1 )) .
2
2
2
>
≤ 192Γηt2 φ2t Tr(St−1 S>
t−1 ) + 4ηt (4φt + 8) λk+1 Tr(St−1 St−1 )

+192Γηt4 φ2t + k∆k2 · 4ηt2 (4φt + 8)2 (χ + Tr(S>
t−1 St−1 )) .

iii.L



Final Main Lemmas

In this section, we extend our main lemmas in Section 7 to their strong forms. Specifically,
• Lemma Main 4 is an extension of Lemma Main 1;
• Lemma Main 5 is an extension of Lemma Main 2;

• Lemma Main 6 is a new main lemma that takes into account “under-sampling”.
Recall that given parameter ρ ∈ (0, λk ),
• V is a matrix consisting of all the eigenvectors of Σ with eigenvalue ≥ λk ,

• Z is a matrix consisting of all the eigenvectors of Σ with eigenvalue < λk ,

• W is a matrix consisting of all the eigenvectors of Σ with eigenvalue ≤ λk − ρ.

When we apply these main lemmas in later sections, we may redefine the meaning of (V, Z, W) to
be with respect to some other λ that is not necessarily λk .

iii.L.1

Before Warm Start


Lemma Main 4 (before warm start). For every q ∈ 0, 12 , ΞZ ≥ 2, Ξx ≥ 2, and fixed matrix
Q ∈ Rd×k , suppose the initial matrix Q satisfies
• kZ> Q(V> Q)−1 k2F ≤ ΞZ ,
h
j−1
>
• Prxt ∀j ∈ [T ], x>
Q(V> Q)−1
t ZZ (Σ/λk+1 )

•
24

νj> ZZ> Q(V> Q)−1

2

≤ Ξx for every j ∈ [d].24

2

i
≤ Ξx ≥ 1 − q 2 /2 for every t ∈ [T ],

This assumption is redundant for j ∈ [k] because νj> Z = 0 for j ∈ [k].

50

Pk

Let m be the number of eigenvalues of Σ in (λk − ρ, λk+1 ]. Let Λ =
Suppose also the learning rates {ηs }s∈[T ] satisfy
(1):

∀s ∈ [T ],

3/2


2q(ΞZ + dΞ2x )
ρ
≤ ηs ≤ O
Λ
Λ · Ξ2x ln dT
q

(3):

(2):

T
X
t=1

i=1 λi

+ Ξ2x

Ληt2 Ξ2x ≤ O

∃T0 ∈ [T ] such that

T0
X
t=1

Pk+m

j=k+1 λj .

 1 
.
ln dT
q

 ln(Ξ ) 
Z
ηt ≥ Ω
ρ

(iii.L.1)

Then, for every t ∈ [T − 1], we have with probability at least 1 − 2qT (over the randomness of
x1 , . . . , xt ):
• if t ≥ T0 then kW> Pt Q(V> Pt Q)−1

2
F

≤ 2.

Proof of Lemma Main 4. The proof is a non-trivial adaption of the proof of Lemma Main 1.
This time we consider random vectors yt,s ∈ R2+d+T defined as:
(1)

def

(2)

def

(2+T +j)

def

yt,s = kZ> Ps Q(V> Ps Q)−1 k2F ,

yt,s = kW> Ps Q(V> Ps Q)−1 k2F ,
yt,s

(3+d+j)

yt,s

2

= νj> ZZ> Ps Q(V> Ps Q)−1 , for j ∈ [d] ,
2

 x> ZZ> (Σ/λ )j P Q(V> P Q)−1 2 , for j ∈ {0, 1, . . . , t − s − 1};
def
s
s
k+1
t
=
2
(3+d+j)
 (1 − η λ ) · y
,
for j ∈ {t − s, . . . , T − 1}.
s k
t,s−1

We again consider upper bounds

2ΞZ s < T0 ;
(1) def
(2) def
φt,s = 2ΞZ , φt,s =
,
2
otherwise.

(3)

(2+d+T )

and φt,s = · · · = φt,s

def

= 2Ξ2x .

For each t ∈ [T ], define event Ct0 and Ct00 in the same way as before:


h
i
(i)
(i)
0 def
Ct = (x1 , ..., xt−1 ) satisfies Pr ∃i ∈ [3 + d] : yt,t−1 > φt,t−1 Ft−1 ≤ q
xt
n
o
def
(i)
(i)
Ct00 = (x1 , ..., xt ) satisfies ∀i ∈ [3 + d] : yt,t−1 ≤ φt,t−1
def
def V
and denote by Ct = Ct0 ∧ Ct00 and C≤t = ts=1 Cs .

Verification of Assumption (A1) in Lemma i.D.1.
q1
q
Suppose E[xs x>
s | C≤s , F≤s−1 ] = Σ + ∆, then we have k∆k2 ≤ 1−q1 ≤ 1−q using the same proof
as before.
This time, we use Lemma iii.K.1 (instead of Lemma i.B.1) with φt = 2Ξx to obtain the following
tighter bounds for i ∈ [T + d + 2]:
 (i)


 (i)


(i)
E yt,s+1 | Ft , F≤s , C≤s ≤ fs(i) yt,s , q and E |yt,s+1 − yt,s |2 | Ft , F≤s , C≤s ≤ h(i)
s yt,s , q

51

where we define25




def
2
2
fs(i) (y, q) = 1 + O(Ληs+1
Ξ2x ) y (i) + O Ληs+1
Ξx + Err
for i = 1, 3, 4, . . . 2 + d



def
2
2
fs(i) (y, q) = 1 − 2ηs+1 ρ + O(Ληs+1
Ξ2x ) y (i) + O Ληs+1
Ξx + Err
for i = 2



def
2
2
fs(i) (y, q) = 1 − ηs+1 λk + O(Ληs+1
Ξ2x ) y (i) + ηs+1 λk y (i+1) + O Ληs+1
Ξ2x + Err
def






(i) 2

for i = 3 + d, . . . , 2 + d + T

2
2
2
4
h(i)
+ Ληs+1
Ξ2x y (i) + Ληs+1
Ξ2x + Err
for i = 1, 2, 3, . . . 2 + d
s (y, q) = O Ληs+1 Ξx y



def
2
2 (i) 2
2
4
h(i)
+ Ληs+1
Ξ2x y (i) + Ληs+1
Ξ4x
for i = 3 + d, . . . , 2 + d + T .
s (y, q) = O Ληs+1 Ξx y

def
3/2
q
Above, we denote by Err = ηs+1 Ξx ΞZ + dΞ2x · 1−q
the error term similar to the proof of
2q(Ξ

3/2

+dΞ2 )

x
Z
Lemma Main 1. Obviously if
≤ ηs is satisfied then the Err term can be absorbed into
Λ
the big-O notation.
For every i ∈ [2 + d + T ], we consider the same gs as defined in the proof of Lemma Main 1:

2
gs(i) (y) = 20ηs+1 Ξx · y (i) + 42ηs+1
Ξ2x
(i)

(i)

(i)

and it satisfies whenever C≤s+1 holds then |yt,s+1 − yt,s | ≤ gs (yt,s ) .
Putting the above bounds together, we finish verifying assumption (A1) of Lemma i.D.1.
Verification of Assumption (A2) of Lemma i.D.1.
This step is exactly the same as the proof of Lemma Main 1 so ignored here.
Verification of Assumption (A3) of Lemma i.D.1.
For every t ∈ [T ], at a high level assumption (A3) is satisfied once we plug in the following
√
def
three sets of parameter choices to Corollary i.C.4 and Corollary i.C.5: define κ = 1/ Λ > 1 and
for every s ∈ [T − 1],
√
βs,1 = 0,
δs,1 = 0,
τs,1 = O(ηs+1 Ξx · Λ)
√
βs,2 = 2ηs+1 ρ,
δs,2 = 0,
τs,2 = O(ηs+1 Ξx · Λ)
√
βs,3 = ηs+1 ρ,
δs,3 = ηs+1 λk
τs,3 = O(ηs+1 Ξx · Λ)
More specifically, for every t ∈ [T ], let {zs }t−1
s=0 be the arbitrary random vector satisfying (i.D.1) of
Lemma i.D.1. Define q2 = q 2 /(8 + 2d).
(i)

t−2
• For coordinate i = 1, 3, 4, . . . , 2 + d of {zs }t−1
s=0 , apply Corollary i.C.4 with {βs,1 , δs,1 , τs,1 }s=0 ,
q = q2 , D = 1, and κ;

• For coordinate i = 2 of {zs }t−1
s=0 ,
– if t < T0 , apply Corollary i.C.4 with {βs,2 , δs,2 , τs,2 }t−2
s=0 , q = q2 , D = 1, and κ;
t−2
– if t ≥ T0 , apply Corollary i.C.5 with {βs,2 , δs,2 , τs,2 }s=0 , q = q2 , D = 1, γ = 1, and κ;
• For coordinates i = 2 + d + 1, . . . , 2 + d + T of {zs }t−1
s=0 ,
– apply Corollary i.C.4 with {βs,3 , δs,3 , τs,3 }t−2
s=0 , q = q2 , D = T , and κ.

25
We refer readers to Footnote 18 in the proof of Lemma Main 1 on page 30 for a detailed discussion as well as a
careful treatment for out-of-bound indices. We remark here that to derive such bounds, one needs to use the fact that
when w = xZZ> for some unit norm vector x (such as x = xt for some t ∈ [T ] or x = νj for some j ∈ [d]), the quantity
ηt
kw> ΣLt−1 k22
λk

that appeared in Lemma iii.K.1-(a) can be upper bounded by

52

ηt λ2
k+1
kw> Lt−1 k22
λk

≤ ηt λk kw> Lt−1 k22 .

Note that we can apply Corollary i.C.4 because
for every i = 1, 2, 3, our assumptions on ηs
√
PT −1 2
−1 4T
1
Λ
imply s=0 τs,i ≤ 100 ln q2 and τs,i ≤ 24 log(4T /q2 ) .

We can apply Corollary i.C.5 with γ = 1 because our assumption ηs ≤ O Λ·Ξ2ρln dT implies
x
q
PT0 −1
Pt−1
2 for every s, and our assumption
βs,2 ≥ 10 ln 3(Tq+d)
·
τ
β
≥
1
+
ln
Ξ
implies
s,2
Z
s,2
s=0
s=0 βs −
2
3t 2
10 ln q2 τs ≥ ln ΞZ + 1 − 1 = ln ΞZ whenever t > T0 .
Therefore, the conclusion of Corollary i.C.4 and Corollary i.C.5 imply that
(i)

(i)

Pr[∃i ∈ [3 + d] : zt−1 > φt,t−1 ] ≤ (3 + d)q2 < q 2 /2

so assumption (A3) of Lemma i.D.1 holds.

Application of Lemma i.D.1. Applying Lemma i.D.1, we have Pr[CT ] ≤ 2qT which implies
our desired bounds and this finishes the proof of Lemma Main 4.


iii.L.2

After Warm Start

Lemma Main 5 √
(after warm start). In the same setting as Lemma Main 4, suppose in addition
there exists δ ≤ 1/ 8 such that
9 ln((8 + 2d)/q 2 )
T0
≥
,
δ2
ln2 T0

∀s ∈ {T0 +1, . . . , T } :

2ηs ρ−ηs2 Ξ2x ≥

Ω(1)
s−1

and

Then, with probability at least 1 − 2qT (over the randomness of x1 , . . . , xT ):
• kW> Pt Q(V> Pt Q)−1 k2F ≤

5T0 / ln2 (T0 )
t/ ln2 t

ηs ≤ √

O(1)
.
Λ(s − 1)δΞx

for every t ∈ {T0 , . . . , T }.

Proof of Lemma Main 5. For every t ∈ [T ] and s ∈ {0, 1, ..., t − 1}, consider the same random
vectors yt,s ∈ R2+d+T defined in the proof of Lemma Main 4. This time, we define upper bounds:

2ΞZ
if s < T0 ;


(1) def
(2) def
2
if s = T0 ; , and φ(3) = · · · = φ(2+d+T ) def
φt,s = 2ΞZ , φt,s =
= 2Ξ2x .
t,s
t,s
2

 5T0 / ln 2(T0 ) if s > T0 .
s/ ln s

def
def V
Also consider the same events Ct0 , Ct00 , Ct = Ct0 ∧ Ct00 and C≤t = ts=1 Cs defined in the proof of
Lemma Main 4. We again want to apply the decoupling Lemma i.D.1.

Verification of Assumption (A1) in Lemma i.D.1.
(i)
(i)
(i)
The same functions fs , gs , and hs used in the proof of Lemma Main 4 still apply here.
We make minor changes on the second coordinate (and this similar modification was also done in
Lemma Main 2): whenever s ≥ T0 , define
q


def
def
(2)
2
2
2 (2)
4
gs (y) = 45ηs+1 Ξx y (2) + 40ηs+1
Ξ2x and h(2)
+ Ληs+1
Ξ2x + Err .
s (y, q) = O Ληs+1 Ξx y
(2)

Note that we can make this change for gs owing to exactly the same reason as the proof of
(2)
Lemma Main 2. We can do so for hs because whenever C≤s+1 holds for some s ≥ T0 (which
(2)
(2)
implies yt,s ≤ 5), we have (y (2) )2 = O(y (2) ) so the formulation of hs can be simplified as above.
(i)

(i)

(i)

These choices of fs , gs , and hs satisfy assumption (A1) of Lemma i.D.1.

Verification of Assumption (A2) of Lemma i.D.1.
Same as before.
Verification of Assumption (A3) in Lemma i.D.1.

53

Same as the proof of Lemma Main 2, for every t ∈ [T ], let {zs }t−1
s=0 be the arbitrary random
2
vector satisfying (i.D.1) of Lemma i.D.1. Choosing q2 = q /(8 + 2d) again, the same argument
before indicates that it suffices to focus on t ≥ T0 + 2 and prove
(2)

(2)

(2)

Pr[zt−1 > φt,t−1 | zT0 ≤ 2] ≤ q2 .

(iii.L.2)

We want to apply Corollary i.C.3. Recall that for every t ∈ {T0 +2, . . . , T }, the random sequence
satisfies (i.D.1) with


def
2
2
fs(2) (y, q) = (1 − 2ηs+1 ρ + O(Ληs+1
Ξ2x ))y (2) + O Ληs+1
Ξx + Err ,


def
2
2 (2)
4
2
h(2)
(y,
q)
=
O
Λη
Ξ
y
+
Λη
Ξ
+
Err
,
s
s+1 x
s+1 x
q
def
2
gs(2) (y) = 45ηs+1 Ξx y (2) + 40ηs+1
Ξ2x
√
(2) t−1
1
Therefore, {zs }s=T
satisfies (i.C.1) with κ = 2/ Λ and τs = δs
because the following holds from
0
our assumptions:
1
3/2
2
Ξ2x )
qΞZ ≤ ηs+1
δτs = ≤ 2ηs+1 ρ − Ω(ηs+1
s
1
1
2
2
4
τs2 = 2 2 ≥ Ω(Ληs+1
Ξ2x ) κ2 τs4 =
≥ Ω(Ληs+1
Ξ2x )
κτs = √
≥ Ω(ηs+1 Ξx )
4
4
δ s
Λδ s
Λδs
√
Finally, we are ready to apply Corollary i.C.3 with q = q2 , t0 = T0 , and κ = 2/ Λ. Because
√
(2)
2)
q2 ≤ e−2 , zT0 ≤ 2, δ ≤ 1/ 8 and lnT2 0T ≥ 9 ln(1/q
, the conclusion of Corollary i.C.3 tells us
δ2

(2)
{zs }t−1
s=T0

(2)

(2)

(2)

0

Pr[zt−1 > φt,t−1 | zT0 ≤ 2] ≤ q2 , which is exactly (iii.L.2) so this finishes the verification of
assumption (A3).

Application of Lemma i.D.1. Applying Lemma i.D.1, we have Pr[CT ] ≤ 2qT which implies
our desired bounds and this finishes the proof of Lemma Main 5.

Parameter iii.L.1. There exists constants C1 , C2 , C3 > 0 such that for every q > 0 that is
sufficiently small (meaning q < 1/poly(T, ΞZ , Ξx , 1/gap)), the following parameters both satisfy
Lemma Main 4 and Lemma Main 5:
(
2
ln ΞZ
ΛΞ2x ln dT
t ≤ T0 ;
T0
ρ
q ln ΞZ
T0 ·ρ
= C1 ·
, ηt = C2 ·
, and δ = C3 · √
.
1
2
2
t
>
T
.
ρ
ln (T0 )
0
ΛΞx
t·ρ

iii.L.3

Under-Sampling Lemma

The previous two sections together (namely, Lemma Main 4 and Lemma Main 5 together), analyze
the behavior of a rank-k Oja’s algorithm with an eigen-partition (λk , λk − ρ), meaning V consists
of all eigenvectors with eigenvalues ≥ λk , Z consists of all the eigenvectors with eigenvalues < λk ,
and W consists of all the eigenvectors with eigenvalues ≤ λk − ρ.
In this section, we consider a more general scenario
Definition iii.L.2. Given λ ∈ [0, λk ] and ρ ∈ (0, λ), we say that V, Z, W form an (λ, λ − ρ) eigenpartition if V consists of all eigenvectors with eigenvalues ≥ λ, Z consist of all the eigenvectors
with eigenvalues < λ, and W consist of all the eigenvectors with eigenvalues ≤ λ − ρ.
The following lemma studies the behavior of a rank-k 0 Oja’s algorithm for an arbitrary k 0 ≤ r.

Lemma Main 6 (under sampling). Let V, Z, W be an (λ, λ − ρ) eigen-partition where the V ∈
Rd×r , Z ∈ Rd×(d−r) , W∈ Rd×(d−m−r) . We study rank k 0 Oja’s algorithm for some k 0 ≤ r.
0
For every q ∈ 0, 21 , ΞZ ≥ 2, Ξx ≥ 2, and fixed matrix Q ∈ Rd×k , suppose it satisfies
54

• kZ> Q(Q> VV> Q)−1/2 k2F ≤ ΞZ ,
h
j−1
>
Q(Q> VV> Q)−1/2
• Prxt ∀j ∈ [T ], x>
t ZZ (Σ/λr+1 )

•

νj> ZZ> Q(Q> VV> Q)−1/2

2

2

i

≤ Ξx ≥ 1−q 2 /2 for every t ∈ [T ],

≤ Ξx for every j ∈ [d].

Suppose also the learning rates {ηs }s∈[T ] satisfy the all conditions in Lemma Main 4 and Lemma Main 5
P
def P
with Λ replaced by Λ0 = ri=1 λi + Ξ2x r+m
j=r+1 λj .
0
d×k
Then, letting Qt ∈ R
be the output of the rank-k 0 Oja’s algorithm with respect to input Q,
with probability at least 1 − 2qT (over the randomness of x1 , . . . , xT ), it satisfies
• kW> Qt k2F ≤

5T0 / ln2 (T0 )
t/ ln2 t

for every t ∈ {T0 , . . . , T }.
0

Proof of Lemma Main 6. Since V> Q ∈ Rr×k for r ≥ k 0 , we can always find a (column) orthonor0
e = VS ∈ Rd×(r−k0 ) , we have
mal matrix S ∈ Rr×(r−k ) such that S> V> Q = 0. Letting Q
e > VV> Q
e = I, Q
e > VV> Q = 0, Z> Q
e = 0, Z> Σj−1 Q
e =0 .
Q
>
j−1 , or X> = ν ZZ> , we always have
Therefore, for every X> = Z> , X> = x>
j
t ZZ (Σ/λr+1 )


>
e
e −1 k2 = Tr X> [Q, Q]([Q,
e
e > VV> [Q, Q])
e −1 [Q, Q]
e >X
kX> [Q, Q](V
[Q, Q])
Q]
F


= Tr X> Q(Q> VV> Q)−1 Q> X

= kX> Q(Q> VV> Q)−1/2 k2F ≤ Ξ2X .

e ∈ Rd×r now satisfies
This implies this matrix [Q, Q]

> [Q, Q])
e
e −1 k2 ≤ ΞZ ,
• kZ> [Q, Q](V
F
h
j−1
>
> [Q, Q])
e
e −1
[Q, Q](V
• Prxt ∀j ∈ [T ], x>
t ZZ (Σ/λr+1 )

•

> [Q, Q])
e
e −1
νj> ZZ> [Q, Q](V

2

≤ Ξx for every j ∈ [d].

2

i
≤ Ξx ≥ 1 − q 2 /2 for all t ∈ [T ],

e and k = r and conclude
Therefore, we can apply Lemma Main 5 with initial matrix [Q, Q]
with probability 1 − 2qT :

>
e −1 k2 ≤
e
kW> Pt [Q, Q](V
Pt [Q, Q])
F

5T0 / ln2 (T0 )
.
t/ ln2 t

e ∈ Rd×r be the output of the rank-r Oja’s algorithm on input [Q, Q]
e
Now, let Qt = QR(Pt [Q, Q])
after t steps. Owing to Lemma 2.2, we have
5T0 / ln2 (T0 )
.
t/ ln2 t
However, recall that QR decomposition orthonormalizes a column vectors only with respect to its
previous columns. This implies, Qt , which is the output of the rank-k 0 Oja’s algorithm on input
Q, is exactly identical to the first k 0 columns of Qt . Therefore, we have
>
e
e −1 k2 ≤
kW> Qt k2F ≤ kW> Pt [Q, Q](V
Pt [Q, Q])
F

kW> Qt k2F ≤ kW> Qt k2F ≤

55

5T0 / ln2 (T0 )
.
t/ ln2 t



iii.M

Proof of Theorems 1 and 2 (for Oja)

We now prove the final Theorem of Oja’s algorithm in gap-free case:
Theorem 2 (restated). For every ρ, ε, p ∈ (0, 1), let k + m be the number of eigenvalues of Σ in
(λk − ρ, 1]. Let
o
nP
P
k
k Pk+m
Λ2 = k+m
Λ1 = min
i=1 λi .
i=1 λi + p2
j=k+1 λj , 1 ,

Define learning rates
e
T0 = Θ



kΛ1
ρ2 p2



e
T1 = Θ

,



Λ2
ρ2



,

 

1
e

t ≤ T0 ;
Θ


  ρ·T0 
1
e
ηt =
Θ
t ∈ (T0 , T0 + T1 ];
ρ·T1





1
e
 Θ
t > T0 + T1 .
ρ·(t−T0 )

Let W be the column orthonormal matrix consisting of all eigenvectors of Σ with values no more
than λk − ρ. Then, the output QT ∈ Rd×k of Oja’s algorithm satisfies with prob. at least 1 − p:
 
e T1
it satisfies kW> QT k2F ≤ ε .
for every T = T0 + T1 + Θ
ε
e hides poly-log factors in 1 , 1 and d.
Above, Θ
p ρ

Note that Theorem 1 is a direct corollary of Theorem 2 by setting ρ ← gap and noticing that
m = 0 so Λ1 = λ1 + · · · + λk and Λ2 = 0.
Proof of Theorem 2. First for a sufficiently large constant C, we can apply Lemma 5.1 with p0 = p8
and some sufficiently small q = poly(1/T, 1/d, p), with probability at least 1 − p0 − q 2 ≥ 1 − p/4
over the random choice of Q, the following holds:


2
d

, and
(Z> Q)(V> Q)−1 F ≤ O dk
2 ln p

p
#
"


 qk ln T 


2
q
i−1
>
≤ q2
Prx1 ,...,xT ∃i ∈ [T ], ∃t ∈ [T ], x>
Q(V> Q)−1 ≥ Ω
t ZZ (Σ/λk+1 )
p
2

q



T 

k ln q

 ν > ZZ> Q(V> Q)−1 ≤ O
for every j ∈ [d] .
j

2

p

Denote by C1 the union of the above three events, and we have PrQ [C1 ] ≥ 1 − p/4.
Let us introduce now some notations for this proof. As illustrated in Figure 2, besides the
definitions of V, W, Z, let W1 be the (column) orthogonal matrix consisting of all eigenvectors of
Σ with eigenvalue ≤ λk − ρ2 , and V1 be the (column) orthogonal matrix consisting of all eigenvectors
of Σ with eigenvalue > λk − ρ2 .
We now wish to apply our main lemma twice. Once with (V, Z, W) = (V, Z, W1 ), and once
with (V, Z, W) = (V1 , W1 , W).

Application One. For every fixed Q, whenever C1 holds, we can let
q
 dk d 
 k ln Tp 
ΞZ = Θ 2 ln
, Ξx = Θ
,
p
p
p
so the initial conditions in Lemma Main 4 is satisfied. Also, according to Parameter iii.L.1, our
parameter choices ηt for t ≤ T0 satisfy the assumptions in Lemma Main 4 with Λ replaced by Λ1 .
We can therefore apply Lemma Main 4 with
Q = Q,

(V, Z, W) = (V, Z, W1 ),

56

λk = λk ,

ρ = ρ/2,

ΞZ , Ξx

Application One
𝑉

𝑍

Application Two

𝑊

𝑉

𝑽

𝑍

𝑊

𝒁
𝑾𝟏
𝑾

𝑽𝟏
eigenvalues

𝜆𝑘

𝜆𝑘 − 𝜌/2

𝜆𝑘 − 𝜌

eigenvalues

Figure 2: Notations V1 , W1 for the proof of Theorem 2

and derive that
Pr

x1 ,...,xT0




kW1> PT0 Q(V> PT0 Q)−1 k2F ≥ 2 C1 ≤ 2qT0 ≤ p/4 .

Now, let C2 be the event where kW1> PT0 Q(V> PT0 Q)−1 k2F ≤ 2 holds, and by union bound
PrQ,x1 ,...,xT0 [C2 ] ≥ 1 − p/4 − p/4 = 1 − p/2.
Application Two. If C2 is true then

¬

>
−1/2 2
>
−1/2 2
kW1> PT0 Q(Q> P>
kF ≤ kW1> PT0 Q(Q> P>
kF
T0 V1 V1 PT0 Q)
T0 VV PT0 Q)
­

V1 V1>

= kW1> PT0 Q(V> PT0 Q)−1 k2F ≤ 2 .

VV>

(iii.M.1)

>
−1
(Q> P>
T0 V1 V1 PT0 Q)

Above, inequality ¬ is because

and this gives us

>
>
>
−1
>
(Q PT0 VV PT0 Q) ; equality ­ is because V PT0 Q is a square matrix and we therefore have

>
−1 = (V> P Q)−1 (V> P Q)−1 > .
(Q> P>
T0
T0
T0 VV PT0 Q)
Inequality (iii.M.1) also implies that, for every x ∈ Rd with kxk2 ≤ 1, it satisfies
√
>
>
−1/2
kx> W1 W1> PT0 Q0 (Q>
k2 ≤ 2 .
0 PT0 V1 V1 PT0 Q0 )

In sum, whenever C2 holds, we have that the initial conditions in Lemma Main 6 is satisfied.
Also, according to Parameter iii.L.1, our parameter choices ηt for t = T0 + 1, . . . , T —once shifted
left by T0 — satisfy the assumptions in Lemma Main 6 with Λ replaced by Λ2 . We can therefore
apply Lemma Main 6 with
Q = PT0 Q,

(V, Z, W) = (V1 , W1 , W),

and conclude that
h
Pr
∀T0 + T1 ≤ t ≤ T : kW> Qt k2F ≤

λ = λk − ρ/2,

ρ = ρ/2,

Ξx = ΞZ = 2

i
5T1 / ln2 (T1 )
C
≥ 1 − 2qT ≥ 1 − p/4 .
2
xT0 +1 ,...,xT
(t − T0 )/ ln2 (t − T0 )
In sum, we have with probability at least Pr[C2 ](1 − p/4) ≥ 1 − p over the random choices of Q,
e 1 /ε), it satisfies kW> Qt k2 ≤ ε.
and x1 , . . . , xT , for every t = T0 + T1 + Θ(T

F

57

iii.N

Proof of Theorem 4 and 5 (for Oja++ )


Algorithm 1 Oja {xt }Tt=1 , {ηt }Tt=1 , Q

Input: vectors {xt ∈ Rd }Tt=1 , learning rates {ηt ∈ R>0 }Tt=1 , an initial matrix Q ∈ Rd×k .
1: Q0 ← Q.
2: for t ← 1 to T do

3:
Qt ← QR (I + ηt xt x>
t )Qt−1
4: end for
5: return QT

Algorithm 2 Oja++ {xt }Tt=1 , {ηt }Tt=1 , {(T (i) , Q(i) )}si=1



Input: vectors {xt ∈ Rd }Tt=1 ; learning rates {ηt ∈ R>0 }Tt=1 ; initial matrices {Q(i) ∈ Rd×ri }si=1 ;
lengths T (1) , . . . , T (s) satisfying T (1) + · · · + T (s) = T .
Output: QT ∈ Rd×(r1 +···+rs ) .
1: Q0 ← []; t ← 0.
2: for i ← 1 to s do
3:
Qt ← [Qt , Q(i) ]
4:
for t0 ← 1 to T (i) do
5:
t ← t + 1;

6:
Qt ← QR (I + ηt xt x>
t )Qt−1
7:
end for
8: end for
9: return QT
We formally write the pseudocode of Oja++ in Algorithm 2. We also write down the pseudocode
of Oja because we shall use it in the analysis of this section. We emphasize here that Oja++ spends
the same per-iteration running time and space complexity as Oja.

58

We prove the following main theorem:
Theorem 5 (Oja++ , restated). For every ρ, ε, p ∈ (0, 1), let k + m be the number of eigenvalues
of Σ in (λk − ρ, 1]. Define

 

k
m
k+m
X
X
Λ2
1 X
Λ1
e
e
Λ1 =
, T1 = Θ
λi + 2
λj , Λ2 =
λi , s = dlog(k + 1)e, T0 = Θ
p
ρ2 p2
ρ2
i=1

i=1

j=k+1

and learning rates (where C

 

C · ρT1 0







1
 C·
 ρ(t−11iT
 0)
ηt =
1

C · ρT1







1
 C·
ρ(t−11sT0 )

e
is some fixed value that is only Θ(1)):

if t ∈ [11iT0 , 11iT0 + T0 ) for some i ∈ {0, 1, ..., s − 1};

if t ∈ [11iT0 + T0 , 11iT0 + 11T0 ) for some i ∈ {0, 1, ..., s − 1}26 ;
if t ∈ (11sT0 , 11sT0 + T1 );
if t > 11sT0 + T1 .
i−1 c−bk/2i c)

For each i ∈ [s], let Q(i) ∈ Rd×(bk/2
Then, the output


T
QT ← Oja++ xt t=1 , ηt

satisfies with probability at least 1 − p
for every

be a random matrix with entries i.i.d. N (0, 1).


T
s−1
, (T0 , Q(i) ) i=1
t=1

e
T = 11sT0 + T1 + Θ



e hides poly-log factors in 1 , 1 and d.
Above, Θ
p ρ

T1
ε





∪ (T − 11(s − 1)T0 , Q(s)
kW> QT k2F ≤ ε .

it satisfies

Note that Theorem 4 is a simple corollary of Theorem 5 by setting ρ ← gap and noticing that
m = 0 so Λ1 = λ1 + · · · + λk and Λ2 = 0.
𝑘/2 - 𝑘/22

𝑘 − 𝑘/2

𝑑

𝑄

1

𝑄

𝑘/22 - 𝑘/23

2

𝑄

3

𝑘

𝑑

𝑄

𝑇

1

1

𝑄

apply Oja’s for
= 11𝑇0 iterations

1

𝑄

𝑇

2

2

𝑄

apply Oja’s for
= 11𝑇0 iterations

2

𝑄

𝑇

3

3

…

𝑄

𝑘

𝑠

apply Oja’s for
= 11𝑇0 iterations

𝑄𝑇

𝑇

apply Oja’s for
= 𝑇 − 11𝑠𝑇0
iterations

s+1

Figure 3: Illustration of our Oja++ algorithm.

e (0) = [] being empty matrix and for every j ∈ [s] by
Proof of Theorem 5. Denote by Q




j
e (j) def
Q
= Oja++ x1 , . . . , x11jT0 , η1 , . . . , η11jT0 , (11T0 , Q(j) ) i=1
def

26
In fact, the intermediate learning rates for t ∈ {1, 2, . . . , 11sT0 } can all be set to the same value
them slightly decrease between epochs just for the sake of having a cleaner proof.

59

C
.
ρT0

We make

the output of Oja++ if we run the outer loop only for j iterations. By definition, it satisfies

 (j−1) (j) 

e
e (j) = Oja x11(j−1)T +b T0 , η11(j−1)T +b T0 , Q
,Q
,
∀j ∈ [s] : Q
0
0
b=1
b=1

e (j) as the output of the old Oja’s algorithm when initialized on the previous
so we can view each Q
(j−1)
e
output Q
appended with a new random matrix Q(j) . We illustrate this pictorially in Figure 3.
We also introduce some notations (see Figure 4 for an illustration). For each i ∈ [s], we define
Vi to be the (column) orthonormal matrix consisting of all eigenvectors of Σ with eigenvalue
i
> λk − s+1
ρ, and Wi to be the (column) orthonormal matrix consisting of all eigenvectors of Σ
i
with eigenvalue ≤ λk − s+1
ρ. Define V0 = V and W0 = Z. Let ki ≥ k be the column dimension
of Vi .
Application 1
𝑉
𝑍

Application 2

𝑊

𝑉

dim = 𝑘

𝑍

Application 𝑠 + 1
𝑉

𝑊

𝑽 = 𝑽0
𝑽1

𝒁 = 𝑾0
𝑾1

dim = 𝑘1

𝑽2

𝑽3

dim = 𝑑 − 𝑘1

𝑽𝑠

dim = 𝑑 − 𝑘2

𝑾3

dim = 𝑘3

dim = 𝑑 − 𝑘3

𝑾𝑠

dim = 𝑘s

𝑊

dim = 𝑑 − 𝑘

𝑾2

dim = 𝑘2

𝑍

dim = 𝑑 − 𝑘𝑠

𝑾
eigenvalues

𝜆𝑘

…

𝜆𝑘 − 𝜌

eigenvalues

Figure 4: Notations V0 , . . . , Vs , W0 , . . . , Ws for the proof of Theorem 5.

Below, we wish to apply our Lemma Main 6 a total of s + 1 times each corresponding to one
outer loop of Oja++ . Each time we shall use our new initialization lemma (i.e., Lemma iii.J.2) in
order to satisfy the preassumption of Lemma Main 6. The first s applications serve as a graduated
warm-start phase and the last application provides the final convergence rate.
def
e (j) k2 ≤ 1 }. In this first
Application 1 Through s. Define event Ci = {∀j ∈ N, j ≤ i : kWj> Q
F
2
step we prove Pr[Ci ] ≥ 1 − 2ip for all i = 0, 1, . . . , s by induction. The base case Pr[C0 ] = 1 is
e (0) is an empty matrix.
obvious because Q
Suppose Pr[Ci−1 ] ≥ 1 − 2(i − 1)p holds true for some i ∈ [s] and we wish to bound Pr[Ci ]. We
e (i−1) is an empty matrix)
first note that event Ci−1 implies (or if i = 1 then Q


e (i−1) > Vi−1 V> Q
e (i−1) = I − Q
e (i−1) > Wi−1 W> Q
e (i−1)  1 I .
Q
i−1
i−1
2
(i−1)
d×α
(i)
d×β
i−1
e
Next, we have Q
∈R
and Q ∈ R
where α = (k −bk/2 c) and β = bk/2i−1 c−bk/2i c.
Since ki−1 − α ≥ k − α ≥ 2β − 1, we have
β
β
β
p
√
≤ √
≤ √
<6 .
√
√
2
( 2β − 1 − β − 1)2
( k − α − β − 1)
( ki−1 − α − β − 1)2

Therefore, we can apply Lemma iii.J.2 on
e =Q
e (i−1) ,
Q

Q = Q(i) ,

(V, Z) = (Vi−1 , Wi−1 ).

and derive that, denoting by Q = [Q(i−1) , Q(i) ], then with probability 1 − p over the random choice
60

of Q(i) , the following event Bi holds (for some polynomially small q):

 

−1/2 2

d
> Q
> Q) Q> V
e

≤
O
and
V
(W

i−1 i−1
i−1
p2


F

"
#


 

−1/2 2
>
def
∃`∈[T ]
`−1
> Q
>
>
e 12
≥Ω
Pr
Q Q Vi−1 Vi−1
≤q
Bi =
∃t∈[T ] xt Wi−1 Wi−1 (Σ/λk+1 )
p
x
,...,x

1
T

2


2
 




 ν > W W> Q Q> V V> Q −1/2 ≤ O
e 1 for every j ∈ [d].

j

i−1

i−1

i−1

i−1

p2

2



















e (j) can be viewed as the output of the original Oja’s algorithm on
Whenever Bi holds, because Q

T0
, we can apply Lemma Main 6 with
input Q and applied with learning rates η11(i−1)T0 +b b=1


i−1
1
Q = Q, (V, Z, W) = (Vi−1 , Wi−1 , Wi ), (λ, ρ) = λk − s+1
ρ, s+1
ρ ,
2 ), O(1/p
2 ))
e
e
(ΞZ , Ξx ) = (O(d/p

T0
—once shifted left by 11(i − 1)T0 — are
We emphasize that these learning rates, η11(i−1)T0 +b b=1
exactly
  
e 1
 Θ
t ≤ T0
0
 ρT
ηt =
, T = 11T0 , Λ = Λ1
e 1
 Θ
t
>
T
0
ρt

so they satisfy the assumption of Lemma Main 6 according to Parameter iii.L.1. Finally, the conclusion of Lemma Main 6 tells us

1
> e (i) 2
Pr kWi Q kF ≥ Ci−1 ∩ Bi ≤ p ,
2
and by union bound, we have (recalling Pr[Bi ] ≥ 1 − p):


1
> e (i) 2
≥ Pr[Ci−1 ∩ Bi ] × (1 − p)
Pr[Ci ] = Pr Ci−1 ∧ kWi Q kF ≤
2
= (1 − p) Pr[Ci−1 ] Pr[Bi | Ci−1 ] ≥ (1 − p)(1 − 2(i − 1)p)(1 − p) ≥ 1 − 2ip .

This finishes the proof that Pr[Cs ] ≥ 1 − 2sp.

Application s + 1. We now focus on the last outer loop of Oja++ , which satisfies


 T
T
e (s) .
QT = Oja xt t=11sT0 +1 , ηt t=11sT0 +1 , Q

e (s) k2 ≤ 1 and thus (Q
e (s) )> Vs V> Q
e (s) 
Similar to the first s outer loops, under event Cs we have kWs> Q
s
F
2
√
1
> e (s) −1/2 k ≤
e (s) >
2 and therefore
2
2 I. This implies k((Q ) Vs Vs Q )
> e (s) e (s) >
> e (s) −1/2 2
e (s) k2 k((Q
e (s) )> Vs V> Q
e (s) )−1/2 k2 ≤ 2.
kW Q ((Q ) Vs V Q )
k ≤ kW> Q
s

s

F

s

F

s

2

Rd

Thus, for every x ∈
with kxk2 ≤ 1:
>
> e (s) e (s) >
e (s) )−1/2 k2 ≤ kW> Q
e (s) k2 k((Q
e (s) )> Vs V> Q
e (s) )−1/2 k2 ≤ 2 .
kx Ws Ws Q ((Q ) Vs Vs> Q
s
s

Now we can apply Lemma Main 6 again with parameters

(s)
e
Q = Q , (V, Z, W) = (Vs , Ws , W), (λ, ρ) = λk −


s
1
ρ,
ρ ,
s+1 s+1

ΞZ = Ξx = 2

 T
We emphasize that these learning rates, ηt t=11sT0 +1 —once shifted left by 11sT0 — are exactly
  
e 1
 Θ
t ≤ T1
1
 ρT
ηt =
, T = T − 11sT0 , Λ = Λ2
e 1
 Θ
t > T1
ρt
61

so they satisfy the assumption of Lemma Main 6 according to Parameter iii.L.1. We can conclude
from Lemma Main 6 that




T1
1
>
2
> e (s) 2
e
≤p .
Pr kW QT kF = Ω
kWs Q kF ≤
T − 11sT0
2
h
i
e (s) k2 ≥ 1 ≤ 2sp we complete the proof of Theorem 5 if we replace
Taking into account Pr kWs> Q
F
2



p with p/(2s + 1).

62

References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition. ArXiv e-prints, abs/1607.06017, July 2016.
[2] Zeyuan Allen-Zhu and Yuanzhi Li. LazySVD: Even Faster SVD Decomposition Yet Without
Agonizing Pain. In NIPS, 2016.
[3] Maria-Florina Balcan, Simon S Du, Yining Wang, and Adams Wei Yu. An improved gapdependency analysis of the noisy power method. In COLT, pages 284–309, 2016.
[4] Akshay Balsubramani, Sanjoy Dasgupta, and Yoav Freund. The fast convergence of incremental pca. In NIPS, pages 3174–3182, 2013.
[5] Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey.
Internet Mathematics, 3(1):79–127, 2006.
[6] Dan Garber and Elad Hazan. Fast and simple PCA via convex optimization. ArXiv e-prints,
September 2015.
[7] Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli,
and Aaron Sidford. Robust shift-and-invert preconditioning: Faster and more sample efficient
algorithms for eigenvector computation. In ICML, 2016.
[8] Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis. In ICML, 2016.
[9] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications.
In NIPS, pages 2861–2869, 2014.
[10] Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s
Algorithm. In COLT, 2016.
[11] Chris J. Li, Mengdi Wang, Han Liu, and Tong Zhang. Near-Optimal Stochastic Approximation
for Online Principal Component Estimation. ArXiv e-prints, abs/1603.05305, March 2016.
[12] Chun-Liang Li, Hsuan-Tien Lin, and Chi-Jen Lu. Rivalry of two families of algorithms for
memory-restricted streaming pca. In Proceedings of the 19th International Conference on
Artificial Intelligence and Statistics, pages 473–481, 2016.
[13] Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain. Memory limited, streaming
pca. In NIPS, pages 2886–2894, 2013.
[14] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and
faster approximate singular value decomposition. In NIPS, pages 1396–1404, 2015.
[15] Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix.
Communications on Pure and Applied Mathematics, 62(12):1707–1739, 2009.
[16] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic
gradient descent for some non-convex matrix problems. In ICML, pages 2332–2341, 2015.
63

[17] Ohad Shamir. Convergence of stochastic gradient descent for pca. In ICML, 2016.
[18] Ohad Shamir. Fast stochastic algorithms for svd and pca: Convergence properties and convexity. In ICML, 2016.
[19] Stanislaw J Szarek. Condition numbers of random matrices. Journal of Complexity, 7(2):131–
149, 1991.
[20] Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, chapter Chapter
2: Basic tail and concentration bounds. 2015.
[21] Weiran Wang, Jialei Wang, Dan Garber, and Nathan Srebro. Efficient Globally Convergent
Stochastic Optimization for Canonical Correlation Analysis. In NIPS, 2016.
[22] Bo Xie, Yingyu Liang, and Le Song. Scale up nonlinear component analysis with doubly
stochastic gradients. In NIPS, pages 2341–2349, 2015.

64

