Linear Convergence of a Frank-Wolfe Type Algorithm over
Trace-Norm Balls

arXiv:1708.02105v3 [cs.LG] 9 Nov 2017

Zeyuan Allen-Zhu
Microsoft Research, Redmond
zeyuan@csail.mit.edu
Wei Hu
Princeton University
huwei@cs.princeton.edu

Elad Hazan
Princeton University
ehazan@cs.princeton.edu
Yuanzhi Li
Princeton University
yuanzhil@cs.princeton.edu

November 8, 2017
Abstract
We propose a rank-k variant of the classical Frank-Wolfe algorithm to solve convex optimization
over a trace-norm ball. Our algorithm replaces the top singular-vector computation (1-SVD) in
Frank-Wolfe with a top-k singular-vector computation (k-SVD), which can be done by repeatedly
applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version
of projected gradient descent. We show that our algorithm has a linear convergence rate when the
objective function is smooth and strongly convex, and the optimal solution has rank at most k. This
improves the convergence rate and the total time complexity of the Frank-Wolfe method and its
variants.

1

Introduction

Minimizing a convex matrix function over a trace-norm ball, which is: (recall that the trace norm kXk∗
of a matrix X equals the sum of its singular values)

minX∈Rm×n f (X) : kXk∗ ≤ θ ,
(1.1)

is an important optimization problem that serves as a convex surrogate to many low-rank machine learning
tasks, including matrix completion [2, 10, 16], multiclass classification [4], phase retrieval [3], polynomial
neural nets [12], and more. In this paper we assume without loss of generality that θ = 1.
One natural algorithm for Problem (1.1) is projected gradient descent (PGD). In each iteration, PGD
first moves X in the direction of the gradient, and then projects it onto the trace-norm ball. Unfortunately,
computing this projection requires the full singular value decomposition (SVD) of the matrix, which takes
O(mn min{m, n}) time in general. This prevents PGD from being efficiently applied to problems with
large m and n.
Alternatively, one can use projection-free algorithms. As first proposed by Frank and Wolfe [5], one
can select a search direction (which is usually the gradient direction) and perform a linear optimization
over the constraint set in this direction. In the case of Problem (1.1), performing linear optimization over
a trace-norm ball amounts to computing the top (left and right) singular vectors of a matrix, which can
be done much faster than full SVD. Therefore, projection-free algorithms become attractive for convex
minimization over trace-norm balls.
Unfortunately, despite its low per-iteration complexity, the Frank-Wolfe (FW) algorithm suffers from
slower convergence rate compared with PGD. When the objective f (X) is smooth, FW requires O(1/ε)
iterations to convergence to an ε-approximate minimizer, and
√ this 1/ε rate is tight even if the objective
is also strongly convex [6]. In contrast, PGD achieves 1/ ε rate if f (X) is smooth (under Nesterov’s
acceleration [14]), and log(1/ε) rate if f (X) is both smooth and strongly convex.
1

Recently, there were several results to revise the FW method to improve its convergence rate for
strongly-convex
functions. The log(1/ε) rate was obtained when the constraint set is a polyhedron [7, 11],
√
and the 1/ ε rate was obtained when the constraint set is strongly convex [8] or is a spectrahedron [6].
Among these results, the spectrahedron constraint (i.e., for all positive semidefinite matrices X with
Tr(X) = 1) studied by Garber [6] is almost identical to Problem (1.1), but slightly weaker.1 When stating
the result of Garber [6], we assume for simplicity that it also applies to Problem (1.1).
Our Question. In this paper, we propose to study the following general question:
Can we design a “rank-k variant” of Frank-Wolfe to improve the convergence rate?
(That is, in each iteration it computes the top k singular vectors – i.e., k-SVD – of some matrix.)
Our motivation to study the above question can be summarized as follows:
• Since FW computes a 1-SVD and PGD computes a full SVD in each iteration, is there a value
k  min{n, m} such that a rank-k variant of FW can achieve the convergence rate of PGD?

• Since computing k-SVD costs roughly the same (sequential) time as “computing 1-SVD for k times”
(see recent work [1, 13]),2 if using a rank-k variant of FW, can the number of iterations be reduced by
a factor more than k? If so, then we can improve the sequential running time of FW.
• k-SVD can be computed in a more distributed manner than 1-SVD. For instance, using block Krylov [13],
one can distribute the computation of k-SVD to k machines, each in charge of independent matrix-vector
multiplications. Therefore, it is beneficial to study a rank-k variant of FW in such settings.

1.1

Our Results

We propose blockFW, a rank-k variant of Frank-Wolfe. Given a convex function f (X) that is β-smooth, in
each iteration t, blockFW performs an update Xt+1 ← Xt + η(Vt − Xt ), where η > 0 is a constant step size
and Vt is a rank-k matrix computed from the k-SVD of (−∇f (Xt ) + βηXt ). If k = min{n, m}, blockFW
can be shown to coincide with PGD, so it can also be viewed as a rank-k restricted version of PGD.
Convergence. Suppose f (X) is also α-strongly convex and suppose the optimal solution X ∗ of
Problem (1.1) has rank k, then we show that blockFW achieves linear convergence: it finds an ε-approximate
β
minimizer within O( α
log 1ε ) iterations, or equivalently, in


kβ
1
log
computations of 1-SVD.
T =O
α
ε
We denote by T the number of 1-SVD computations throughout this paper. In contrast,
 
TFW = O βε
for Frank-Wolfe

n
o
√




β 1/2 β 1/2
β 1/4 β 3/4
1
TGar = O min βε ,
k ,
for Garber [6].
α
ε
α
ε
σmin (X ∗ )
Above, σmin (X ∗ ) is the minimum non-zero singular value of X ∗ . Note that σmin (X ∗ ) ≤

kX ∗ k∗
rank(X ∗ )

≤ k1 .

We note that TGar is always outperformed by min{T, TFW }: ignoring the log(1/ε) factor, we have




 √
β 1/4 β 3/4 1/4
β 1/4 β 3/4
≤ α
k
< α
k, and
• min βε , kβ
α
ε
ε
 β kβ




β 1/2 β 1/2 1/2
β 1/2 β 1/2
1
• min ε , α ≤ α
k
< α
ε
ε
σmin (X ∗ ) .

Remark. The low-rank assumption on X ∗ should be reasonable: as we mentioned, in most applications
of Problem (1.1), the ultimate reason for imposing a trace-norm constraint is to ensure that the optimal
1 The the best of our knowledge, given an algorithm that works for spectrahedron, to solve Problem (1.1), one has to
define a function g(Y ) over (n + m) × (n + m) matrices, by setting g(Y ) = f (2Y1:m,m+1:m+n ) [10]. After this transformation,
the function g(Y ) is no longer strongly convex, even if f (X) is strongly convex. In contrast, most algorithms for trace-norm
balls, including FW and our later proposed algorithm, work as well for spectrahedron after minor changes to the analysis.
2 Using block Krylov [13], Lanszos [1], or SVRG [1], at least when k is small, the time complexity of (approximately)
computing the top k singular vectors of a matrix is no more than k times the complexity of (approximately) computing the
top singular vector of the same matrix. We refer interested readers to [1] for details.

2

algorithm

# rank

# iterations

PGD [14]

min{m, n}

κ log(1/ε)

accelerated
PGD [14]

min{m, n}

FrankWolfe [9]

1

Garber [6]

1

blockFW

k

√

κ log(1/ε)
β
ε

κ
κ

1
4

1
2

√

β3
4
k , or
ε
β1
1
2
ε
σmin (X ∗ )

κ log(1/ε)

time complexity per iteration

O mn min{m, n}
O mn min{m, n}

Õ nnz(∇)



Õ nnz(∇) + (m + n)



× min



1/2

k∇k2

ε1/2

1/2

,

k∇k2

(σ1 (∇)−σ2

(∇))1/2





1/2
1/2
k∇k2
k∇k2
× min
,
1/2
1/2
ε
(σ1 (∇)−σ2 (∇))

k · Õ nnz(∇) + k(m + n)κ


(k∇k2 +α)1/2 κ(k∇k2 +α)1/2
× min
,
1/2
1/2
∗
ε

α

σmin (X )

Table 1: Comparison of first-order methods to minimize a β-smooth, α-strongly convex function over the unit-trace
β
norm ball in Rm×n . In the table, k is the rank of X ∗ , κ = α
is the condition number, ∇ = ∇f (Xt ) is the
gradient matrix, nnz(∇) is the complexity to multiply ∇ to a vector, σi (X) is the i-th largest singular
value of X, and σmin (X) is the minimum non-zero singular value of X.

solution is low-rank; otherwise the minimization problem may not be interesting to solve in the first place.
Also, the immediate prior work [6] also assumes X ∗ to have low rank.
k-SVD Complexity. For theoreticians who are concerned about the time complexity of k-SVD, we also
compare it with the 1-SVD complexity of FW and Garber. If one uses LazySVD [1]3 to compute k-SVD in
each iteration of blockFW, then the per-iteration k-SVD complexity can be bounded by



(k∇k2 + α)1/2 κ(k∇k2 + α)1/2
k · Õ nnz(∇) + k(m + n)κ × min
, 1/2
.
(1.2)
ε1/2
α σmin (X ∗ )

β
Above, κ = α
is the condition number of f , ∇ = ∇f (Xt ) is the gradient matrix of the current iteration t,
nnz(∇) is the complexity to multiply ∇ to a vector, σmin (X ∗ ) is the minimum non-zero singular value of
X ∗ , and Õ hides poly-logarithmic factors.

In contrast, if using Lanczos, the 1-SVD complexity for FW and Garber can be bounded as (see [6])
1/2
n k∇k1/2
o

k∇k2
2
Õ nnz(∇) × min
,
.
(1.3)
ε1/2 (σ1 (∇) − σ2 (∇))1/2
Above, σ1 (∇) and σ2 (∇) are the top two singular values of ∇, and the gap σ1 (∇) − σ2 (∇) can be as small
as zero.
We emphasize that our k-SVD complexity (1.2) can be upper bounded by a quantity that only depends
poly-logarithmically on 1/ε. In contrast, the worst-case 1-SVD complexity (1.3) of FW and Garber
depends on ε−1/2 because the gap σ1 − σ2 can be as small as zero. Therefore, if one takes this additional
ε dependency into consideration for the convergence rate, then blockFW has rate polylog(1/ε), but FW
and Garber have rates ε−3/2 and ε−1 respectively. The convergence rates and per-iteration running times
of different algorithms for solving Problem (1.1) are summarized in Table 1.
Practical Implementation. Besides our theoretical results above, we also provide practical suggestions
for implementing blockFW. Roughly speaking, one can automatically select a different “good” rank k for
each iteration. This can be done by iteratively finding the 1st, 2nd, 3rd, etc., top singular vectors of
the underlying matrix, and then stop this process whenever the objective decrease is not worth further
increasing the value k. We discuss the details in Section 6.

2

Preliminaries and Notation

For a positive integer n, we define [n] := {1, 2, . . . , n}. For a matrix A, we denote by kAkF , kAk2 and
kAk∗ respectively the Frobenius norm, the spectral norm, and the trace norm of A. We use h·, ·i to

3 In fact, LazySVD is a general framework that says, with a meaningful theoretical support, one can apply a reasonable
1-SVD algorithm k times in order to compute k-SVD. For simplicity, in this paper, whenever referring to LazySVD, we mean
to apply the Lanczos method k times.

3

denote the (Euclidean) inner products between vectors, or the (trace) inner products between matrices
(i.e., hA, Bi = Tr(AB > )). We denote by σi (A) the i-th largest singular value of a matrix A, and by
σmin (A) the minimum non-zero singular value of A. We use nnz(A) to denote the time complexity of
multiplying matrix A to a vector (which is at most the number of non-zero entries of A). We define the
(unit) trace-norm ball Bm,n in Rm×n as Bm,n := {X ∈ Rm×n : kXk∗ ≤ 1}.
Definition 2.1. For a differentiable convex function f : K → R over a convex set K ⊆ Rm×n , we say
• f is β-smooth if f (Y ) ≤ f (X) + h∇f (X), Y − Xi + β2 kX − Y k2F for all X, Y ∈ K;

• f is α-strongly convex if f (Y ) ≥ f (X) + h∇f (X), Y − Xi + α2 kX − Y k2F for all X, Y ∈ K.
For Problem (1.1), we assume f is differentiable, β-smooth, and α-strongly convex over Bm,n . We
β
denote by κ = α
the condition number of f , and by X ∗ the minimizer of f (X) over the trace-norm ball
Bm,n . The strong convexity of f (X) implies:

Fact 2.2. f (X) − f (X ∗ ) ≥

α
2 kX

− X ∗ k2F for all X ∈ K.

Proof. The minimality of X ∗ implies h∇f (X ∗ ), X − X ∗ i ≥ 0 for all X ∈ K. The fact follows then from
the α-strong convexity of f .

The Frank-Wolfe Algorithm. We now quickly review the Frank-Wolfe algorithm (see Algorithm 1)
and its relation to PGD.
Algorithm 1 Frank-Wolfe
Input: Step sizes {ηt }t≥1 (ηt ∈ [0, 1]), starting point X1 ∈ Bm,n
1: for t = 1, 2, . . . do
2:
Vt ← argminV ∈Bm,n h∇f (Xt ), V i
 by finding the top left/right singular vectors ut , vt of −∇f (Xt ), and taking Vt = ut vt> .
3:
Xt+1 ← Xt + ηt (Vt − Xt )
4: end for
Let ht = f (Xt ) − f (X ∗ ) be the approximation error of Xt . The convergence analysis of Algorithm 1
is based on the following relation:
¬
β
ht+1 = f (Xt + ηt (Vt − Xt )) − f (X ∗ ) ≤ ht + ηt h∇f (Xt ), Vt − Xt i + ηt2 kVt − Xt k2F
2
(2.1)
­
®
β
β
≤ ht + ηt h∇f (Xt ), X ∗ − Xt i + ηt2 kVt − Xt k2F ≤ (1 − ηt )ht + ηt2 kVt − Xt k2F .
2
2
Above, inequality ¬ uses the β-smoothness of f , inequality ­ is due to the choice of Vt in Line 2, and
inequality ® follows from the convexity of f . Based on (2.1), a suitable choice of the step size ηt = Θ(1/t)
gives the convergence rate O(β/ε) for the Frank-Wolfe algorithm.
If f is also α-strongly convex, a linear convergence rate can be achieved if we replace the linear
optimization step (Line 2) in Algorithm 1 with a constrained quadratic minimization:
β
Vt ← argminh∇f (Xt ), V − Xt i + ηt kV − Xt k2F .
(2.2)
2
V ∈Bm,n

In fact, if Vt is defined as above, we have the following relation similar to (2.1):
β
ht+1 ≤ ht + ηt h∇f (Xt ), Vt − Xt i + ηt2 kVt − Xt k2F
2
(2.3)
β
∗
≤ ht + ηt h∇f (Xt ), X − Xt i + ηt2 kX ∗ − Xt k2F ≤ (1 − ηt + κηt2 )ht ,
2
1
where the last inequality follows from Fact 2.2. Given (2.3), we can choose ηt = 2κ
to obtain a linear
convergence rate because ht+1 ≤ (1 − 1/4κ)ht . This is the main idea behind the projected gradient descent
(PGD) method. Unfortunately, optimizing Vt from (2.2) requires a projection operation onto Bm,n , and
this further requires a full singular value decomposition of the matrix ∇f (Xt ) − βηt Xt .
4

3

A Rank-k Variant of Frank-Wolfe

Our main idea comes from the following simple observation. Suppose we choose ηt = η =
iterations, and suppose rank(X ∗ ) ≤ k. Then we can add a low-rank constraint to Vt in (2.2):
Vt ←

argmin
V ∈Bm,n , rank(V )≤k

β
ηkV − Xt k2F .
2

h∇f (Xt ), V − Xt i +

1
2κ

for all

(3.1)

Under this new choice of Vt , it is obvious that the same inequalities in (2.3) remain to hold, and thus the
linear convergence rate of PGD can be preserved. Let us now discuss how to solve (3.1).

3.1

Solving the Low-Rank Quadratic Minimization (3.1)

Although (3.1) is non-convex, we prove that it can be solved efficiently. To achieve this, we first show that
Vt is in the span of the top k singular vectors of βηXt − ∇f (Xt ).
Pk
Lemma 3.1. The minimizer Vt of (3.1) can be written as Vt = i=1 ai ui vi> , where a1 , . . . , ak are
nonnegative scalars, and (ui , vi ) is the pair of the left and right singular vectors of At := βηXt − ∇f (Xt )
corresponding to its i-th largest singular value.
The proof of Lemma 3.1 is given in Appendix B. Now,
Pkowing to Lemma 3.1, we can perform k-SVD on
At to compute {(ui , vi )}i∈[k] , plug the expression Vt = i=1 ai ui vi> into the objective of (3.1), and then
Pk
Pk
search for the optimal values {ai }i∈[k] . The last step is equivalent to minimizing − i=1 σi ai + β2 η i=1 a2i
k
(where σi = u>
i At vi ) over the simplex ∆ := a ∈ R : a1 , . . . , ak ≥ 0, kak1 ≤ 1 , which is the same as
1
projecting the vector βη
(σ1 , . . . , σk ) onto the simplex ∆. It can be easily solved in O(k log k) time (see
for instance the applications in [15]).

3.2

Our Algorithm and Its Convergence

We summarize our algorithm in Algorithm 2 and call it blockFW.
Algorithm 2 blockFW
Input: Rank parameter k, starting point X1 = 0
1
1: η ← 2κ
.
2: for t = 1, 2, . . . do
3:
At ← βηXt − ∇f (Xt )
4:
(u1 , v1 , . . . , uk , vk ) ← k-SVD(At )
 (ui , vi ) is the i-th largest pair of left/right singular vectors of At
1
k
5:
a ← argmina∈Rk ,a≥0,kak1 ≤1 ka − βη
σk2
 where σ := (u>
i At vi )i=1
Pk
>
6:
Vt ← i=1 ai ui vi
7:
Xt+1 ← Xt + η(Vt − Xt )
8: end for
Since the state-of-the-art algorithms for k-SVD are iterative methods, which in theory can only give
approximate solutions, we now study the convergence of blockFW given approximate k-SVD solvers.
We introduce the following notion of an approximate solution to the low-rank quadratic minimization
problem (3.1).
Definition 3.2. Let gt (V ) = h∇f (Xt ), V − Xt i + β2 ηkV − Xt k2F be the objective function in (3.1), and let
gt∗ = gt (X ∗ ). Given parameters γ ≥ 0 and ε ≥ 0, a feasible solution V to (3.1) is called (γ, ε)-approximate
if it satisfies g(V ) ≤ (1 − γ)gt∗ + ε.
Note that the above multiplicative-additive definition makes sense because gt∗ ≤ 0:

Fact 3.3. If rank(X ∗ ) ≤ k, for our choice of step size η =
− h2t ≤ 0 according to (2.3).

1
2κ ,

we have gt∗ = gt (X ∗ ) ≤ −(1 − κη)ht =

The next theorem gives the linear convergence of blockFW under the above approximate solutions to
5

(3.1). Its proof is simple and uses a variant of (2.3) (see Appendix B).
Theorem 3.4. Suppose rank(X ∗ ) ≤ k and ε > 0. If each Vt computed in blockFW is a ( 12 , 8ε )-approximate
solution to (3.1), then for every t, the error ht = f (Xt ) − f (X ∗ ) satisfies

1 t−1
h1 + 2ε .
ht ≤ 1 − 8κ

As a consequence, it takes O(κ log

h1
ε )

iterations to achieve the target error ht ≤ ε.

Based on Theorem 3.4, the per-iteration running time of blockFW is dominated by the time necessary
to produce a ( 12 , 8ε )-approximate solution Vt to (3.1), which we study in Section 4.

4

Per-Iteration Running Time Analysis

In this section, we study the running time necessary to produce a ( 12 , ε)-approximate solution Vt to (3.1).
In particular, we wish to show a running time that depends only poly-logarithmically on 1/ε. The reason
is that, since we are concerning about the linear convergence rate (i.e., log(1/ε)) in this paper, it is not
meaningful to have a per-iteration complexity that scales polynomially with 1/ε.
Remark 4.1. To the best of our knowledge, the Frank-Wolfe method and Garber’s method [6] have their
worst-case per-iteration complexities scaling polynomially with 1/ε. In theory, this also slows down their
overall performance in terms of the dependency on 1/ε.

4.1

Step 1: The Necessary k-SVD Accuracy

We first show that if the k-SVD in Line 4 of blockFW is solved sufficiently accurate, then Vt obtained in
Line 6 will be a sufficiently good approximate solution to (3.1). For notational simplicity, in this section
we denote Gt := k∇f (Xt )k2 + α, and we let k ∗ = rank(X ∗ ) ≤ k.

Lemma 4.2. Suppose γ ∈ [0, 1] and ε ≥ 0. In each iteration t of blockFW, if the vectors u1 , v1 , . . . , uk , vk
Pk
∗
>
returned by k-SVD in Line 4 satisfy
u>
i At vi ≥ (1 − γ)σi (At ) − ε for all i ∈ [k ], then Vt =
i=1 ai ui vi


6Gt
obtained in Line 6 is
ht + 2 γ, ε -approximate to (3.1).
The proof of Lemma 4.2 is in Appendix C, and is based on our earlier characterization Lemma 3.1.

4.2

Step 2: The Time Complexity of k-SVD

We recall the following complexity statement for k-SVD:
Theorem 4.3 ([1]). The running time to compute the k-SVD of A ∈ Rm×n using LazySVD is4




2
(m+n)
k·nnz(A)+k2 (m+n)
√
√
Õ k·nnz(A)+k
or
Õ
.
γ
gap

>
In
 the former case,i we can have ui Avi ≥ (1 − γ)σi (A) for all i ∈ [k]; in the latter case, if gap ∈
σk∗ (A)−σk∗ +1 (A)
∗
0,
for some k ∗ ∈ [k], then we can guarantee u>
i Avi ≥ σi (A) − ε for all i ∈ [k ].
σk∗ (A)

The First Attempt. Recall that we need a ( 12 , ε)-approximate solution to (3.1). Using Lemma 4.2, it
suffices to obtain a (1 − γ)-multiplicative approximation to the k-SVD of At (i.e., u>
i At vi ≥ (1 − γ)σi (At )
1
for all i ∈ [k]), as long as γ ≤ 12Gt /h
.
Therefore,
we
can
directly
apply
the
first running time in
t +4
k·nnz(At )+k2 (m+n) 
√
Theorem 4.3: Õ
. However, when ht is very small, this running time can be unbounded.
γ
In that case, we observe that γ = Gεt (independent of ht ) also suffices: since kAt k2 = α2 Xt − ∇f (Xt ) 2 ≤
α
ε
>
>
2 + k∇f (Xt )k2 ≤ Gt , from ui At vi ≥ (1 − ε/Gt )σi (At ) we have ui At vi ≥ σi (At ) − Gt σi (At ) ≥ σi (At ) −
ε
Gt kAt k2 ≥ σi (At ) − ε; then according to Lemma 4.2 we can obtain (0, ε)-approximation to (3.1), which
is stronger than ( 12 , ε)-approximation. We summarize this running time (using γ = Gεt ) in Claim 4.5; the
running time depends polynomially on 1ε .

The Second Attempt. To make our linear convergence rate (i.e., the log(1/ε) rate) meaningful, we
4 The first is known as the gap-free result because it does not depend on the gap between any two singular values. The
second is known as the gap-dependent result, and it requires a k × k full SVD after the k approximate singular vectors are
computed one by one. The Õ notation hides poly-log factors in 1/ε, 1/γ, m, n, and 1/gap.

6

want the k-SVD running time to depend poly-logarithmically on 1/ε. Therefore, when ht is small, we wish
to instead apply the second running time in Theorem 4.3.
Recall that X ∗ has rank k ∗ so σk∗ (X ∗ ) − σk∗ +1 (X ∗ ) = σmin (X ∗ ). We can show that this implies
A := α2 X ∗ − ∇f (X ∗ ) also has a large gap σk∗ (A∗ ) − σk∗ +1 (A∗ ). (See Lemma C.1.) Now, according to
Fact 2.2, when ht is small, Xt and X ∗ are sufficiently close. This means At = α2 Xt − ∇f (Xt ) is also close
to A∗ , and thus has a large gap σk∗ (At ) − σk∗ +1 (At ). Then we can apply the second running time in
Theorem 4.3.
∗

4.2.1

Formal Running Time Statements

Fact 4.4. We can store Xt as a decomposition into at most rank(Xt ) ≤ kt rank-1 components.5 Therefore,
for At = α2 Xt − ∇f (Xt ), we have nnz(At ) ≤ nnz(∇f (Xt )) + (m + n)rank(Xt ) ≤ nnz(∇f (Xt )) + (m + n)kt.
If we always use the first running time in Theorem 4.3, then Fact 4.4 implies:
Claim 4.5. The k-SVD computation in the t-th iteration of blockFW can be implemented in Õ k ·
p

nnz(∇f (Xt )) + k 2 (m + n)t Gt /ε time.

Remark 4.6. As long
p as (m + n)kt ≤ nnz(∇f (Xt )), the k-SVD running time in Claim 4.5
p becomes
Õ k · nnz(∇f (Xt )) Gt /ε , which roughly equals k-times the 1-SVD running time Õ nnz(∇) k∇k2 /ε)
of FW and Garber [6]. Since in practice, it suffices to run blockFW and FW for a few hundred 1-SVD
computations, the relation (m + n)kt ≤ nnz(∇f (Xt )) is often satisfied.

If, as discussed above, we apply the first running time in Theorem 4.3 only for large ht , and apply the
second running time in Theorem 4.3 for small ht , then we obtain the following theorem whose proof is
given in Appendix C.
Theorem 4.7. The k-SVD comuputation
in the t-th iteration of blockFW can be implemented in

 √

κ Gt /α
2
Õ k · nnz(∇f (Xt )) + k (m + n)t σmin (X ∗ ) time.

Remark 4.8. Since according to Theorem 3.4 we only need to run blockFW for O(κ log(1/ε)) iterations,
we can plug t = O(κ log(1/ε)) into Claim 4.5 and Theorem 4.7, and obtain the running time presented in
(1.2). The per-iteration running time of blockFW depends poly-logarithmically on 1/ε. In contrast, the
per-iteration running times of Garber [6] and FW depend polynomially on 1/ε, making their total running
times even worse in terms of dependency on 1/ε.

5

Maintaining Low-Rank Iterates

One of the main reasons to impose trace-norm constraints is to produce low-rank solutions. However, the
rank of iterate Xt in our algorithm blockFW can be as large as kt, which is much larger than k, the rank
of the optimal solution X ∗ . In this section, we show that by adding a simple modification to blockFW, we
can make sure the rank of Xt is O(kκ log κ) in all iterations t, without hurting the convergence rate much.
We modify blockFW as follows. Whenever t − 1 is a multiple of S = d8κ(log κ + 1)e, we compute (note
that this is the same as setting η = 1 in (3.1))
β
Wt ←
argmin
h∇f (Xt ), W − Xt i + kW − Xt k2F ,
2
W ∈Bm,n , rank(W )≤k

and let the next iterate Xt+1 be Wt . In all other iterations the algorithm is unchanged. After this change,
the function value f (Xt+1 ) may be greater than f (Xt ), but can be bounded as follows:
Lemma 5.1. Suppose rank(X ∗ ) ≤ k. Then we have f (Wt ) − f (X ∗ ) ≤ κht .
Proof. We have the following relation similar to (2.3):
β
kWt − Xt k2F
2
β
≤ ht + h∇f (Xt ), X ∗ − Xt i + kX ∗ − Xt k2F
2

f (Wt ) − f (X ∗ ) ≤ ht + h∇f (Xt ), Wt − Xt i +

5

In Section 5, we show how to ensure that rank(Xt ) is always O(kκ log κ), a quantity independent of t.

7

≤ ht − ht +

β 2
· ht
2 α

= κht .



1 S
1 8κ(log κ+1)
h1 + 2ε ≤ e−(log κ+1) h1 + 2ε =
From Theorem 3.4 we know that hS+1 ≤ (1− 8κ
) h1 + 2ε ≤ (1− 8κ
)
1
κε
Therefore, after setting XS+2 = WS+1 , we still have hS+2 ≤ e h1 + 2 (according to Lemma 5.1).
Continuing this analysis (letting the κε here be the “new ε”), we know
 that this modified version of
blockFW converges to an ε-approximate minimizer in O κ log κ · log hε1 iterations.
Remark 5.2. Since in each iteration the rank of Xt is increased by at most k, if we do the modified step
every S = O(κ log κ) iterations, we have that throughout the algorithm, rank(Xt ) is never more than
O(kκ log κ). Furthermore we can always store Xt using O(kκ log κ) vectors, instead of storing all the
singular vectors obtained in previous iterations.
1
eκ h1 +ε/2.

6

Preliminary Empirical Evaluation

We conclude this paper with some preliminary experiments to test the performance of blockFW. We first
recall two machine learning tasks that fall into Problem (1.1).
Matrix Completion. Suppose there is an unknown matrix M ∈ Rm×n close to low-rank, and we
observe a subset Ω of its entries – that is, we observe Mi,j for every (i, j) ∈ Ω. (Think of Mi,j as user i’s
rating of movie j.) One can recover M by solving the following convex program:
 P
minX∈Rm×n 21 (i,j)∈Ω (Xi,j − Mi,j )2 | kXk∗ ≤ θ .
(6.1)

Although Problem (6.1) is not strongly convex, our experiments show the effectiveness of blockFW on this
problem.

Polynomial Neural Networks. Polynomial networks are neural networks with quadratic activation
function σ(a) = a2 . Livni et al. [12] showed that such networks can express any function computed by a
Turing machine, similar to networks with ReLU or sigmoid activations. Following [12], we consider the
class of 2-layer polynomial networks with inputs from Rd and k hidden neurons:
n
o
Pk
V
Pk = x 7→ j=1 aj (wj> x)2 ∀j ∈ [k], wj ∈ Rd , kwj k2 = 1 a ∈ Rk .
Pk
If we write A = i=1 aj wj wj> , we have the following equivalent formulation:

Pk = x 7→ x> Ax A ∈ Rd×d , rank(A) ≤ k .

Therefore, if replace the hard rank constraint with trace norm kAk∗ ≤ θ, the task of empirical risk
minimization (ERM) given training data {(x1 , y1 ), . . . , (xN , yN )} ⊂ Rd × R can be formulated as6
 PN
2
kAk∗ ≤ θ .
(6.2)
minA∈Rd×d 21 i=1 (x>
i Axi − yi )
P
N
2
Since f (A) = 12 i=1 (x>
i Axi − yi ) is convex in A, the above problem falls into Problem (1.1). Again,
this objective f (A) might not be strongly convex, but we still perform experiments on it.

6.1

Preliminary Evaluation 1: Matrix Completion on Synthetic Data

We consider the following synthetic experiment for matrix completion. We generate a random rank-10
matrix in dimension 1000 × 1000, plus some small noise. We include each entry into Ω with probability
1/2. We scale M to kM k∗ = 10000, so we set θ = 10000 in (6.1).

We compare blockFW with FW and Garber [6]. When implementing the three algorithms, we use
exact line search. For Garber’s algorithm, we tune its parameter ηt = ct with different constant values c,
and then exactly search for the optimum η̃t . When implementing blockFW, we use k = 10 and η = 0.2.
We use the Matlab built-in solver for 1-SVD and k-SVD.
In Figure 1(a), we compare the numbers of 1-SVD computations for the three algorithms. The plot
confirms that it suffices to apply a rank-k variant FW in order to achieve linear convergence.

6.2

Auto Selection of k

In practice, it is often unrealistic to know k in advance. Although one can simultaneously try k =
1, 2, 4, 8, . . . and output the best possible solution, this can be unpleasant to work with. We propose the
6 We

consider square loss for simplicity. It can be any loss function `(x>
i Axi , yi ) convex in its first argument.

8

8

FW
Garber
This paper

7
6

4

7

FW
Garber
This paper

6

2
1
0

5

Log(error)

3

4
3

2
1.5
1
0.5
0

2

-1
-2

3
2.5

4

Log(error)

Log(error)

5

FW
Garber
This paper

3.5

-0.5

1
0

20

40

60

# 1-SVD computations

80

100

0

50

100

150

# 1-SVD computations

(a) matrix completion on synthetic data (b) matrix completion
on MovieLens1M, θ = 10000

200

-1

0

100

200

300

400

500

# 1-SVD computations

(c) polynomial neural network
on Mnist, θ = 0.03

Figure 1: Partial experimental results. The full 6 plots for MovieLens and 3 plots for Mnist are included in
Figure 2 and Figure 3 in Appendix A.

following modification to blockFW which automatically chooses k.
In each iteration t, we first run 1-SVD and compute the objective decrease, denoted by d1 ≥ 0. Now,
given any approximate k-SVD decomposition of the matrix At = βηXt − ∇f (Xt ), we can compute its
(k + 1)-SVD using one additional 1-SVD computation according to the LazySVD framework [1]. We
compute the new objective decrease dk+1 . We stop this process and move to the next iteration t + 1
k+1
< dkk . In other words, we stop whenever it “appears” not worth further increasing k. We
whenever dk+1
count this iteration t as using k + 1 computations of 1-SVD.
All the experiments on real-life datasets are performed using this above auto-k process.

6.3

Preliminary Evaluation 2: Matrix Completion on MovieLens

We study the same experiment in Garber [6], the matrix completion Problem (6.1) on datasets MovieLens100K (m = 943, n = 1862 and |Ω| = 105 ) and MovieLens1M (m = 6040, n = 3952 and |Ω| ≈ 106 ).
In the second dataset, following [6], we further subsample Ω so it contains about half of the original entries.
For each dataset, we run FW, Garber, and blockFW with three different choices of θ.7 We present the six
plots side-by-side in Figure 2 in Appendix A.
We observe that when θ is large, there is no significant advantage for using blockFW. This is because
the rank of the optimal solution X ∗ is also high for large θ. In contrast, when θ is small (so X ∗ is of low
rank), as demonstrated for instance by Figure 1(b), it is indeed beneficial to apply blockFW.

6.4

Preliminary Evaluation 3: Polynomial Neural Network on Mnist

We use the 2-layer neural network Problem (6.2) to train a binary classifier on the Mnist dataset of
handwritten digits, where the goal is to distinguish images of digit “0” from images of other digits. The
training set contains N = 60000 examples each of dimension d = 28 × 28 = 784. We set yi = 1 if that
example belongs to digit “0” and yi = 0 otherwise. We divide the original grey levels by 256 so xi ∈ [0, 1]d .
We again try three different values of θ, and compare FW, Garber, and blockFW.8 We present the three
plots side-by-side in Figure 3 in Appendix A.
The performance of our algorithm is comparable to FW and Garber for large θ, but as demonstrated
for instance by Figure 1(c), when θ is small so rank(X ∗ ) is small, it is beneficial to use blockFW.

7

Conclusion

In this paper, we develop a rank-k variant of Frank-Wolfe for Problem (1.1) and show that: (1) it converges
in log(1/ε) rate for smooth and strongly convex functions, and (2) its per-iteration complexity scales with
7 We perform exact line search for all algorithms. For Garber [6], we tune the best η = c and exactly search for the
t
t
optimal η̃t . For blockFW, we let k be chosen automatically and choose η = 0.01 for all the six experiments.
8 We perform exact line search for all algorithms. For Garber [6], we tune the best η = c and exactly search for the
t
t
optimal η̃t . For blockFW, we let k be chosen automatically and choose η = 0.0005 for all the three experiments.

9

polylog(1/ε). Preliminary experiments suggest that the value k can also be automatically selected, and
our algorithm outperforms FW and Garber [6] when X ∗ is of relatively smaller rank.
We hope more rank-k variants of Frank-Wolfe can be developed in the future.
Acknowledgments
Elad Hazan is supported by NSF grant 1523815 and a Google research award.

References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. LazySVD: Even faster SVD decomposition yet without agonizing
pain. In NIPS, pages 974–982, 2016.
[2] Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111–119, 2012.
[3] Emmanuel J Candes, Yonina C Eldar, Thomas Strohmer, and Vladislav Voroninski. Phase retrieval
via matrix completion. SIAM review, 57(2):225–251, 2015.
[4] Miroslav Dudik, Zaid Harchaoui, and Jérôme Malick. Lifted coordinate descent for learning with
trace-norm regularization. In AISTATS, pages 327–336, 2012.
[5] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics
quarterly, 3(1-2):95–110, 1956.
[6] Dan Garber. Faster projection-free convex optimization over the spectrahedron. In NIPS, pages
874–882, 2016.
[7] Dan Garber and Elad Hazan. A linearly convergent conditional gradient algorithm with applications
to online and stochastic optimization. arXiv preprint arXiv:1301.4666, 2013.
[8] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In
ICML, pages 541–549, 2015.
[9] Elad Hazan. Sparse approximate solutions to semidefinite programs. In Latin American Symposium
on Theoretical Informatics, pages 306–316. Springer, 2008.
[10] Martin Jaggi and Marek Sulovský. A simple algorithm for nuclear norm regularized problems. In
ICML, pages 471–478, 2010.
[11] Simon Lacoste-Julien and Martin Jaggi. An affine invariant linear convergence analysis for frank-wolfe
algorithms. arXiv preprint arXiv:1312.7864, 2013.
[12] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural
networks. In NIPS, pages 855–863, 2014.
[13] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster
approximate singular value decomposition. In NIPS, pages 1396–1404, 2015.
[14] Yurii Nesterov. Introductory Lectures on Convex Programming Volume: A Basic course, volume I.
Kluwer Academic Publishers, 2004.
[15] Yurii Nesterov. Smooth minimization of non-smooth functions.
103(1):127–152, December 2005.

Mathematical Programming,

[16] Shai Shalev-Shwartz, Alon Gonen, and Ohad Shamir. Large-scale convex minimization with a
low-rank constraint. arXiv preprint arXiv:1106.1622, 2011.

10

Appendix
A

Additional Plots
6

6

FW
Garber
This paper

5.5
5

5.5

FW
Garber
This paper

5.5

4
3.5
3

Log(error)

5

Log(error)

4.5

Log(error)

6

FW
Garber
This paper

4.5

5

4.5

4

2.5

4

3.5
2
1.5

0

50

100

150

200

3

250

0

50

(a) MovieLens100K, θ = 3000
7

FW
Garber
This paper

200

250

3.5

300

0

50

100

150

200

# 1-SVD computations

(b) MovieLens100K, θ = 5000

(c) MovieLens100K, θ = 10000

7

7

FW
Garber
This paper

FW
Garber
This paper

6.5

6

4

Log(error)

6

5

5.5
5

5.5

5

3

4.5

2
1

150

6.5

Log(error)

Log(error)

6

100

# 1-SVD computations

# 1-SVD computations

4.5

4

0

50

100

150

3.5

200

# 1-SVD computations

0

50

100

150

200

250

4

300

0

50

# 1-SVD computations

(d) MovieLens1M, θ = 10000

100

150

200

250

300

# 1-SVD computations

(e) MovieLens1M, θ = 15000

(f) MovieLens1M, θ = 30000

Figure 2: Log objective error vs. the number of 1-SVD computations, for matrix completion.

4

4

FW
Garber
This paper

3.5
3

3.5

FW
Garber
This paper

3.5

FW
Garber
This paper

3

3

2
1.5
1

2.5

Log(error)

Log(error)

Log(error)

2.5

2
1.5

2.5

2

0.5

1
1.5

0

0.5

-0.5
-1

0

100

200

300

# 1-SVD computations

(a) Mnist, θ = 0.03

400

500

0

0

100

200

300

# 1-SVD computations

(b) Mnist, θ = 0.05

400

500

1

0

100

200

300

400

# 1-SVD computations

(c) Mnist, θ = 0.1

Figure 3: Log objective error vs. the number of 1-SVD computations, for polynomial neural network.

11

500

B

Missing Proofs for Section 3

The proof of Lemma 3.1 relies on the following folklore lemma.
Lemma B.1. Let A ∈ Rm×n and r = min{m, n}. Let g : Rr → R be a twice-differentiable convex
function. For any two sets of orthonormal vectors {u1 , . . . , ur } ⊂ Rm and {v1 , . . . , vr } ⊂ Rn , there exist
a permutation π over [r] and ξ1 , . . . , ξr ∈ {−1, 1} such that
>
>
g(u>
1 Av1 , u2 Av2 , . . . , ur Avr ) ≤ g(ξ1 σπ(1) (A), ξ2 σπ(2) (A), . . . , ξr σπ(r) (A)) .

We first prove Lemma 3.1 using Lemma B.1, and then give the proof of Lemma B.1.
Pk
Lemma 3.1 (restated). The minimizer Vt of (3.1) can be written as Vt = i=1 ai ui vi> , where a1 , . . . , ak
are nonnegative reals, and (ui , vi ) is the pair of the left and right singular vectors of At := βηXt − ∇f (Xt )
corresponding to its i-th largest singular value.
Proof. The quadratic objective in (3.1) can be written as h∇f (Xt ) − βηXt , V i + β2 ηkV k2F − h∇f (Xt ), Xt i +
β
2
2 ηkXt kF , where the last two terms do not depend on V . Hence, (3.1) is equivalent to
β
Vt ←
argmin
−hAt , V i + ηkV k2F .
(B.1)
2
V ∈Bm,n , rank(V )≤k

Pk
Since we have rank(V ) ≤ k, we can write its SVD as V = i=1 ai ui vi> , where {u1 , . . . , uk } ⊂ Rm and
{v1 , . . . , vk } ⊂ Rn are two sets of orthonormal vectors. To prove Lemma 3.1, it suffices to show for every
fixed set of singular values {ai }ki=1 where a1 ≥ · · · ≥ ak ≥ 0, the optimal choices of ui ’s and vi ’s must
coincide with the top k left and right singular vectors of At .
Pk
a1 , . . . , E
ak are fixed, kV k2F = i=1 a2i is also fixed, so (B.1) becomes maximizing hAt , V i =
D When
Pk
Pk
At , i=1 ai ui vi> = i=1 ai u>
i At vi . Now, applying Lemma B.1 (whose proof is provided later) with
Pk
Pk
Pk
A = At and g(x1 , . . . , xr ) = i=1 ai xi , we get i=1 ai u>
i At v i ≤
i=1 ai ξi σπ(i) (At ) for some permutation
π over [r] and some ξi ’s in {−1, 1}. Then by the non-negativity of singular values and the rearrangement
Pk
Pk
Pk
inequality we have i=1 ai ξi σπ(i) (At ) ≤ i=1 ai σπ(i) (At ) ≤ i=1 ai σi (At ).
Pk
Pk
In sum, we have shown hAt , V i = i=1 ai u>
i At v i ≤
i=1 ai σi (At ) for any ui ’s and vi ’s. It is easy to
see that the equality can be attained if u>
i At vi = σi (At ) for all i ∈ [k], or equivalently, if ui and vi are the
left and right singular vectors of At corresponding to its i-th largest singular value.

In order to prove Lemma B.1 (which we believe is a folklore result), we first prove its special case
where m = n.
Lemma B.2. Let A ∈ Rn×n and g : Rn → R be a twice-differentiable convex function. For any
two orthonormal bases {u1 , . . . , un } and {v1 , . . . , vn } of Rn , there exists a permutation π over [n] and
ξ1 , . . . , ξn ∈ {−1, 1} such that
>
>
g(u>
1 Av1 , u2 Av2 , . . . , un Avn ) ≤ g(ξ1 σπ(1) (A), ξ2 σπ(2) (A), . . . , ξn σπ(n) (A)) .

00
Proof. We denote by gi0 (x) the i-th partial derivative of g at x ∈ Rn , and by gi,j
(x) the (i, j)-th second-order
00
00
00
partial derivative. WLOG we assume that g is strictly convex, which implies that gi,i
(x)+gj,j
(x) > 2|gi,j
(x)|
holds for all i, j and x. In fact, if g is not strictly convex, we can add εkxk2 to g(x) to make it strictly
convex, which will add small perturbations to both sides of the desired inequality. Then we can let ε → 0
to make the perturbations arbitrarily small, and the desired inequality follows.
>
We now fix a pair of orthonormal bases {u1 , . . . , un } and {v1 , . . . , vn } that maximize g(u>
1 Av1 , u2 Av2 ,
>
n
. . . , un Avn ) over all orthonormal bases
 of R , and consider a pair of indices i 6= j. For ϕ ∈ R, define
 therocos ϕ − sin ϕ
u (ϕ)
tation matrix Rϕ =
. We apply the rotation Rϕ to vectors ui and uj , i.e., we let i
=
sin ϕ cos ϕ
uj (ϕ)
  



  

u
(cos ϕ)ui − (sin ϕ)uj
v (ϕ)
v
(cos ϕ)vi − (sin ϕ)vj
Rϕ i =
. Similarly define i
= Rϕ i =
. Note
uj
(sin ϕ)ui + (cos ϕ)uj
vj (ϕ)
vj
(sin ϕ)vi + (cos ϕ)vj
that if we replace ui and uj by ui (ϕ) and uj (ϕ), {u1 , . . . , ui (ϕ), . . . , uj (ϕ), . . . , un } is still an orthonormal
basis. Similarly, {v1 , . . . , vi (ϕ), . . . , vj (ϕ), . . . , vn } is also an orthonormal basis.
12

>
>
>
n
Let x(ϕ) = (u>
1 Av1 , . . . , ui (ϕ) Avi (ϕ), . . . , uj (ϕ) Avj (ϕ), . . . , un Avn ) ∈ R and consider the following function h defined on R:
>
>
>
h(ϕ) := g(x(ϕ)) = g(u>
1 Av1 , . . . , ui (ϕ) Avi (ϕ), . . . , uj (ϕ) Avj (ϕ), . . . , un Avn ) .

By the optimality of {ui } and {vi }, we know that h(ϕ) achieves its maximum at ϕ = 0. Since h is
twice-differentiable, this means h0 (0) = 0 and h00 (0) ≤ 0. We can directly calculate h0 (0) and h00 (0):


>
h0 (0) = gi0 − gj0 · u>
,
i Avj + uj Avi


 >
2
>
00
00
00
h00 (0) =2 gi0 − gj0 u>
ui Avj + u>
,
j Avj − ui Avi + gi,i + gj,j − 2gi,j
j Avi

where all the partial derivatives of g are at point x(0).

>
0
0
0
Assume that u>
i Avj + uj Avi 6= 0. Then from h (0) = 0 we know that gi − gj = 0, which implies 0 ≥
 >
2
00
00
00
00
00
00
>
> 0), a contradiction.
h (0) = 0 + gi,i + gj,j − 2gi,j ui Avj + uj Avi > 0 (recall that gi,i + gj,j − 2gi,j
>
>
Therefore we must have ui Avj + uj Avi = 0.
 
 
u
v
Next, we apply the rotation Rϕ on i and the rotation R−ϕ on i instead. Repeating the same
uj
vj
>
>
>
analysis as above, we can obtain u>
i Avj − uj Avi = 0. Combining this with ui Avj + uj Avi = 0, we
know that u>
6 j. Since {u1 , . . . , un } is an orthonormal basis and Avj is
i Avj = 0. This holds for all i =
orthogonal to ui for every i =
6 j, we must have Avj = λj uj (λj ∈ R) for all j. Hence ui ’s and vi ’s are (left
and right) singular vectors of A (up to sign flips), and ui and vi correspond to the same singular value.
This completes the proof of Lemma B.2.

00

Now we prove Lemma B.1.
Proof of Lemma B.1. The case where m = n is proved in Lemma B.2. Now
 WLOG we assume m < n.
A
e
We pad (n − m) × n zeros to the bottom of A to make it n × n: A =
, and we also pad each ui
0
 
u
with (n − m) zeros: u
ei = i ∈ Rn . We extend {e
u1 , . . . , u
em } and {v1 , . . . , vm } to two orthonormal bases
0
{e
u1 , . . . , u
en } and {v1 , . . . , vn } of Rn .
Consider a function h(x1 , . . . , xn ) := g(x1 , . . . , xm ) defined on Rn . Using Lemma B.2, we have
>
>
e
e
g(u>
u>
e>
u>
e>
1 Av1 , u2 Av2 , . . . , um Avm ) = g(e
1 Av1 , . . . , u
m Avm ) = h(e
1 Av1 , . . . , u
n Avn )
e . . . , ξn σπ(n) (A))
e = g(ξ1 σπ(1) (A),
e . . . , ξm σπ(m) (A))
e
≤ h(ξ1 σπ(1) (A),

(B.2)

e
for some permutation π over [n] and ξi ’s in {−1, 1}. Note
( that the n singular values of A include all the
e = σi (A), i ∈ [m]
m singular values of A and (n − m) zeros, i.e., σi (A)
. Thus the remaining
0,
i ∈ {m + 1, . . . , n}
thing to prove is that we can choose the permutation π such that (B.2) still holds and that π(1), . . . , π(m)
is a permutation of [m]. Suppose that π(1), . . . , π(m) is not a permutation of [m]. Then there exist i ∈ [m]
and j ∈ {m + 1, . . . , n} such that π(i) > m and π(j) ≤ m. Now, if we swap π(i) and π(j) to obtain a new
permutation π 0 over [n], by the convexity of g we have
e . . . , ξi σπ(i) (A),
e . . . , ξm σπ(m) (A))
e = g(ξ1 σπ(1) (A),
e . . . , 0, . . . , ξm σπ(m) (A))
e
g(ξ1 σπ(1) (A),


1
e . . . , σπ(j) (A),
e . . . , ξm σπ(m) (A))
e + g(ξ1 σπ(1) (A),
e . . . , −σπ(j) (A),
e . . . , ξm σπ(m) (A))
e
≤
g(ξ1 σπ(1) (A),
2
e . . . , ξi0 σπ(j) (A),
e . . . , ξm σπ(m) (A))
e
≤ 0 max g(ξ1 σπ(1) (A),
ξi ∈{−1,1}

=

max

ξi0 ∈{−1,1}

e . . . , ξi0 σπ0 (i) (A),
e . . . , ξm σπ0 (m) (A)).
e
g(ξ1 σπ0 (1) (A),

Repeatedly doing this procedure, we can eventually make σ(1), . . . , σ(m) a permutation of [m] without
decreasing the right hand side of (B.2). (The values of ξi ’s may change.) This completes the proof of
Lemma B.1.

13

Theorem 3.4 (restated). Suppose rank(X ∗ ) ≤ k and ε > 0. If each Vt computed in blockFW is a
( 12 , 8ε )-approximate solution to (3.1), then for every t, the error ht = f (Xt ) − f (X ∗ ) satisfies

1 t−1
h1 + 2ε .
ht ≤ 1 − 8κ
As a consequence, it takes O(κ log

h1
ε )

iterations to achieve the target error ht ≤ ε.

Proof. The proof only requires a simple modification to our previous analysis (2.3). Using that Vt is a
( 12 , 8ε )-approximate solution to (3.1) we have
β 2
η kVt − Xt k2F = ht + ηgt (Vt )
2


ε
1
∗
ht +
.
≤ ht + η(gt /2 + ε/8) ≤ ht + η(−ht /4 + ε/8) = 1 −
8κ
16κ
Repeatedly applying the above inequality for t = 1, 2, . . ., we get
"

t−1



t−2 #
1
ε
1
1
ht ≤ 1 −
h1 +
1+ 1−
+ ··· + 1 −
8κ
16κ
8κ
8κ
t−1

t−1

1
1
ε
ε
1
·
= 1−
h1 +
h1 + .
≤ 1−
8κ
16κ 1 − (1 − 1/(8κ))
8κ
2
ht+1 ≤ ht + ηh∇f (Xt ), Vt − Xt i +

C



Missing Proofs for Section 4

Recall that in Section 4 we let Gt = k∇f (Xt )k2 + α and k ∗ = rank(X ∗ ) ≤ k.

Lemma 4.2 (restated). Suppose γ ∈ [0, 1] and ε ≥ 0. In each iteration t of blockFW, if the vectors
∗
u1 , v1 , . . . , uk , vk returned by k-SVD in Line 4 satisfy u>
i At vi ≥ (1 − γ)σi (At ) − ε for all i ∈ [k ], then


Pk
6G
t
Vt = i=1 ai ui vi> obtained in Line 6 is
ht + 2 γ, ε -approximate to (3.1).

Proof. We rewrite the objective gt (V ) in (3.1) as gt (V ) = −h∇At , V i + β2 ηkV k2F − h∇f (Xt ), Xt i +
β
β
β
2
2
2
2 ηkXt kF = pt (V ) + st , where pt (V ) = −h∇At , V i + 2 ηkV kF and st = −h∇f (Xt ), Xt i + 2 ηkXt kF . Note
that st does not depend on V , and that we can upper bound st as
β
α
st ≤ k∇f (Xt )k2 kXt k∗ + ηkXt k2F ≤ k∇f (Xt )k2 · 1 + · 12 ≤ Gt ,
2
4
α
where we have used η = 2β
. Since the rank of X ∗ is k ∗ ≤ k, let us define a rank k ∗ version of the minimum
as
β
gt0 =
min
h∇f (Xt ), V − Xt i + ηkV − Xt k2F .
2
V ∈Bm,n , rank(V )≤k∗
0
∗
∗
We know that gt ≤ gt (X ) = gt . Moreover, According to Lemma 3.1 and the discussion thereafter, we
know that
( k∗
)
k∗
X
β X 2
0
gt = min −
σi (At )ai + η
a + st ,
(C.1)
a∈∆k∗
2 i=1 i
i=1
Pk∗
∗
where ∆k∗ = {a ∈ Rk : a1 , . . . , ak∗ ≥ 0, i=1 ai ≤ 1}. Denote by a∗ ∈ ∆k∗ the minimizer in (C.1), i.e.,
we have
k∗
k∗
X
β X ∗ 2
0
∗
gt = −
σi (At )ai + η
(a ) + st .
(C.2)
2 i=1 i
i=1

Now our algorithm uses approximate singular vectors ui ’s and vi ’s which satisfy σi = u>
i At v i ≥
(1 − γ)σi (At ) − ε for all i ∈ [k ∗ ]. Then the Vt produced by the algorithm should satisfy for ∆k = {a ∈
Pk
Rk : a1 , . . . , ak ≥ 0, i=1 ai ≤ 1}:
( k
)
k
X
β X 2
gt (Vt ) = min −
σi ai + η
a + st
a∈∆k
2 i=1 i
i=1
14

(

)
k∗
β X 2
≤ min −
σi ai + η
a + st
a∈∆k∗
2 i=1 i
i=1
( k∗
)
k∗
X
β X 2
a + st
≤ min −
((1 − γ)σi (At ) − ε)ai + η
a∈∆k∗
2 i=1 i
i=1
(
)
k∗
k∗
X
β X 2
≤ min −(1 − γ)
a + st + ε .
σi (At )ai + η
a∈∆k∗
2 i=1 i
i=1
∗

k
X

Since (1 − γ)a∗ ∈ ∆k∗ , we can choose a = (1 − γ)a∗ on the right hand side and obtain
∗

gt (Vt ) ≤ −(1 − γ)
= (1 −

≤ (1 −

∗

k
X

γ)a∗i

σi (At )(1 −
i=1
γ)2 (gt0 − st ) + st + ε
γ)2 (gt∗ − st ) + st + ε

k
β X
+ η
((1 − γ)a∗i )2 + st + ε
2 i=1

(C.3)

.

Above, the only equality is due to (C.2). Finally, from st ≤ Gt and gt∗ ≤ − h2t ≤ 0 (see Fact 3.3), we have
t ∗
st ≤ − 3G
ht gt . Then it follows from (C.3) that







3Gt
3Gt
3Gt
2
∗
2
gt (Vt ) ≤ (1 − γ) 1 +
−
gt + ε = 1 − (2γ − γ ) 1 +
gt∗ + ε
ht
ht
ht



3Gt
≤ 1 − 2γ 1 +
gt∗ + ε ,
ht



6Gt

By definition, we know that Vt is
ht + 2 γ, ε -approximate to (3.1).
The following lemma is used to prove Theorem 4.7.

Lemma C.1. The matrix A∗ :=

α ∗
2X

− ∇f (X ∗ ) satisfies σk∗ (A∗ ) − σk∗ +1 (A∗ ) ≥

α
∗
2 σmin (X ).

Proof. Since h∇f (X ∗ ), X − X ∗ i ≥ 0 for all X ∈ Bm,n , we have

h∇f (X ∗ ), X ∗ i = min h∇f (X ∗ ), Xi = −σ1 (∇f (X ∗ )) .

(C.4)

X∈Bm,n

Let the SVD of X ∗ be X ∗ =

Pk∗

i=1

σi (X ∗ )ui vi> . We first show that for all i ∈ [k ∗ ], we must have

h∇f (X ∗ ), ui vi> i = h∇f (X ∗ ), X ∗ i .

Assume (C.5) is false, then there exists i ∈ [k ] such that h∇f (X
∗

0

X =

X ∗ − 21 σi (X ∗ )ui vi>
.
1− 12 σi (X ∗ )

We have

h∇f (X ∗ ), X 0 i =
<

Since kX 0 k∗ =
proved (C.5).

kX ∗ k∗ − 12 σi (X ∗ )
1− 12 σi (X ∗ )

∗

), ui vi> i

(C.5)

> h∇f (X ), X i. Consider
∗

∗

h∇f (X ∗ ), X ∗ i − 12 σi (X ∗ )h∇f (X ∗ ), ui vi> i
1 − 12 σi (X ∗ )
h∇f (X ∗ ), X ∗ i − 12 σi (X ∗ )h∇f (X ∗ ), X ∗ i
1 − 21 σi (X ∗ )

= h∇f (X ∗ ), X ∗ i .

≤ 1, we have X 0 ∈ Bm,n and this contradicts (C.4). Thus, we have

From (C.4) and (C.5) we know that for each i ∈ [k ∗ ] we have h−∇f (X ∗ ), ui vi> i = σ1 (∇f (X ∗ )) =
σ1 (−∇f (X ∗ )). This implies that the largest k ∗ singular values of −∇f (X ∗ ) are all equal to the same
value, and all pairs (ui , vi ) for i ∈ [k ∗ ] are left and right singular vectors corresponding to this sinPk∗
gular value. Therefore we can write the SVD of −∇f (X ∗ ) as −∇f (X ∗ ) = σ1 (∇f (X ∗ )) i=1 ui vi> +
15

Pr

i=k∗ +1

σi (∇f (X ∗ ))ui vi> , where r = min{m, n}. It follows that
∗

k 
r

X
X
α
α
A = X ∗ − ∇f (X ∗ ) =
σi (X ∗ ) + σ1 (∇f (X ∗ )) ui vi> +
σi (∇f (X ∗ ))ui vi> ,
2
2
∗
i=1
∗

i=k +1

which is the SVD of A∗ . Therefore, we have
(
α
σi (X ∗ ) + σ1 (∇f (X ∗ )), i = 1, 2, . . . , k ∗ ,
∗
σi (A ) = 2
σi (∇f (X ∗ )),
i = k ∗ + 1, . . . , r .
which implies σk∗ (A∗ ) − σk∗ +1 (A∗ ) =

α
∗
∗
2 σk (X )

+ σ1 (∇f (X ∗ )) − σk∗ +1 (∇f (X ∗ )) ≥



α
∗
∗
2 σk (X ).

Theorem 4.7 (restated). The k-SVD comuputation
in the t-th iteration of blockFW can be implemented

 √

κ Gt /α
2
in Õ k · nnz(∇f (Xt )) + k (m + n)t σmin (X ∗ ) time.

Proof of Theorem 4.7. From Theorem 3.4 and Lemma 4.2, we only need to show that the stated running
ε
1
∗
time is enough for LazySVD to ensure u>
. We
i At vi ≥ (1 − γ)σi (At ) − 8 for all i ∈ [k ], where γ = 12Gt
ht

consider two cases.

α3 (σmin (X ∗ ))2
. From Fact 2.2
162β 2
α
Then, At = 2 Xt − ∇f (Xt ) and

• Case 1: ht ≤
σmin (X ∗ )
.
9κ

we know that kXt − X ∗ kF ≤

q

2
α ht

≤

q

2
α

·

+4

α3 (σmin (X ∗ ))2
162β 2

=

A =
− ∇f (X ) satisfy
α
(Xt − X ∗ ) − (∇f (Xt ) − ∇f (X ∗ ))
kAt − A∗ kF =
2
F
α
∗
∗
≤ kXt − X kF + k∇f (Xt ) − ∇f (X )kF
2
α
3β
≤ kXt − X ∗ kF + βkXt − X ∗ kF ≤
kXt − X ∗ kF
2
2
α
3β σmin (X ∗ )
·
= σmin (X ∗ ) .
≤
2
9κ
6
By Weyl’s inequality we know that |σi (At ) − σi (A∗ )| ≤ kAt − A∗ k2 ≤ kAt − A∗ kF ≤ α6 σmin (X ∗ ).
Since we have σk∗ (A∗ )− σk∗ +1 (A∗ ) ≥ α2 σmin (X ∗ )by Lemma C.1, we have σk∗ (At ) − σk∗ +1 (At ) ≥
σk∗ (A∗ ) − α6 σmin (X ∗ ) − σk∗ +1 (A∗ ) + α6 σmin (X ∗ ) = σk∗ (A∗ )−σk∗ +1 (A∗ )− α3 σmin (X ∗ ) ≥ α6 σmin (X ∗ ).


2
(m+n)
We can now apply the second running time of Theorem 4.3: Õ k·nnz(At√)+k
, where gap =
gap
σk∗ (At )−σk∗ +1 (At )
;
σk∗ (At )

Gt

=
Õ

∗

ασmin (X )
.
6Gt



α ∗
2X

∗

∗
in such running time LazySVD can guarantee u>
i At vi ≥ σi (At ) − ε for all i ∈ [k ].

Note that σk∗ (At ) ≤ kAt k2 ≤
∗
α
6 σmin (X )

∗

α
2 kXt k2

+ k∇f (Xt )k2 ≤ Gt . which implies gap =

σk∗ (At )−σk∗ +1 (At )
σk∗ (At )

Thus the running time is
s
!

k · nnz(At ) + k 2 (m + n)
G
t
= Õ (k · nnz(At ) + k 2 (m + n))
.
√
gap
ασmin (X ∗ )

≥

α3 (σmin (X ∗ ))2
. Lemma 4.2 implies that it suffices to ensure u>
i At vi ≥ (1 − γ)σi (At ) for
162β 2


3
(X ∗ ))2
α3 (σmin (X ∗ ))2
ht
1
∗
all i ∈ [k ], where γ = 12Gt
= Ω min{1, Gt } = Ω(min{1,
}) = Ω( α (σmin
) – the
β 2 Gt
β 2 Gt
+4
ht

last step here is because we have α3 (σmin (X ∗ ))2 ≤ β 2 · Gt · 12 = β 2 Gt .

• Case 2: ht >

We apply the first running time of Theorem 4.3:
s
!


k · nnz(At ) + k 2 (m + n)
β 2 Gt
2
Õ
= Õ (k · nnz(At ) + k (m + n))
√
γ
α3 (σmin (X ∗ ))2
!
p
κ
G
/α
t
= Õ (k · nnz(At ) + k 2 (m + n))
.
σmin (X ∗ )
16

Note that the running time for Case 2 is always no smaller than the running time for Case 1 (ignoring
logarithmic factors). Combining the two cases and plugging the bound of nnz(At ) from Fact 4.4, we have
the desired running time statement.


17

