Projection Free Rank-Drop Steps

1 Introduction

The Frank-Wolfe algorithm has been widely used for many machine learning applications due to its projection-free property, particularly when linear minimization on the domain is easy but projection is difficult. A particularly interesting problem in machine learning is the nuclear norm constrained problem,

where ‖·‖NN is the nuclear norm, which is a typical convex relaxation for rank constrained optimization problems [Fazel et al., 2001]. Common applications of nuclear-norm constrained problems are matrix completions, multivariate regression, multi-task learning, and clustering with missing information. For (1), a projection operation onto the nuclear norm ball will require a full singular value decomposition (SVD), which can be too expensive to perform at each iteration, but is required by methods such as the projected gradient descent.

Without any projection, the FW iterate is guaranteed to be feasible. For (1), the linear subproblem used by FW only requires computing the singular vector pair corresponding to the largest singular value of the gradient at each iteration [Jaggi, 2013]. This is significantly cheaper than computing the full SVD when the dimension of the matrix is large. A challenge when using FW for (1) is that the nuclear norm ball is a convex hull of an infinite number of rank-one matrices, referred to as the atoms of the set of feasible points. Since an atom is added at each iteration, the solution is expressed as a convex combination of an arbitrarily large atomic set, which lacks the crucial low-rank property we desire from nuclear norm constrained problems.

While other methods exist for solving instances of (1), e.g., Active Subspace Selection [Hsieh and Olsen, 2014] or Redistributing Nonconvex Regularizers [Yao et al., 2016], implementations for these methods utilize specific properties of f(·). In [Yao et al., 2016], it appears that for each choice of f(·), a specialized solver must be written, and in [Hsieh and Olsen, 2014], knowledge of special structures using ∇f(·) and ∇2 f(·) is necessary to use the approach efficiently. In contrast, the FW can be readily used for a general f(·) without special modifications.

One of our main goals is to devise a new way to efficiently generate descent feasible steps which also decrease the rank of the current iterate when solving (1) without assuming a specific form for f(·). We propose a new nonconvex optimization formulation to determine the steepest descent rankdrop steps. By further considering the interior rank-drop step and exterior rank-drop step cases separately, we obtain formulations which lead to efficient feasible rank-drop step computation.

We establish theoretical properties of the proposed formulations. In addition we demonstrate computationally that the proposed rank-drop FW method can obtain much lower rank solutions than previous FW alternatives, greatly improving computational efficiency.

1.1 Notation

In this paper, σi(A) denotes the ith singular value of A, with σ1 ≥ ... ≥ σmin{m,n}. For a matrix A = [aij] ∈ Rm×n , ‖A‖NN := ∑i σi(A) denotes the nuclear norm and ‖A‖sp := σ1(A) denotes the spectral norm. Let B‖·‖(A, ϵ) := {X ∈ Rm×n : ‖A - X‖ ≤ ϵ} be the closed norm-ball with a specified norm. We use the term thin SVD to mean the SVD with strictly positive singular values, i.e., if A = UΣV ⊤ is a thin SVD and rank(A) = r, then U ∈ Rm×r ,Σ ∈ Rr×r , and V ∈ Rn×r . Finally, 〈A,B〉 := tr(A⊤B) denotes the usual trace inner product.

2 The Frank-Wolfe Algorithm and Away Step

We briefly review FW along with its common variants. Here FW is described for a general problem,

where S is a closed and bounded convex set.

The FW algorithm can be summarized in Algorithm 1. We denote the FW direction as dfw := sk - xk.

Algorithm 1 Frank-Wolfe (FW)

end for

There are many choices for the stepsize τ which ensure convergence. We will assume in this paper that the optimal step-size is used since the stepsize choice is not the focus of this work.

Away steps has been introduced in [Wolfe, 1970] and analyzed in [Gu´elat and Marcotte, 1986] to move away from "bad atoms" to accelerate convergence. The away step method maintains a set of active atoms, Ak, such that the current iterate xk is decomposed into an atomic decomposition, i.e., xk = ∑ai∈Ak αai ai, where the weight satisfy αai > 0 and ∑ai∈Ak αai ≤ 1.

The away step provides a direction that moves away from one of the active atoms which yields a better descent direction than the current FW direction. This direction solves the following optimization problem,

To ensure convergence, the away direction daway := xk - vk is only taken if 〈∇f(xk), daway〉 ≤ 〈∇f(xk), dfw〉. Algorithm 2 summarizes the away step FW method (AFW) in [Lacoste-Julien and Jaggi, 2015].

2.1 In-Face Steps

In [Freund et al., 2015], In-Face Steps are proposed to generalize away-steps. Instead of generating descent directions by moving away from bad atoms, the in-face step selects the best descent direction along the minimal face containing the current iterate. By aiming to move along the minimal face to the boundary of the feasible region to reach a lower dimensional face, the algorithm explicitly maintains a low-rank structure without compromising convergence. For (1), as in [Freund et al., 2015], the minimal face F(Xk) of BNN(0, δ) containing a point Xk is given by the set,

where Xk has a thin r rank SVD, UΣV ⊤, M is a real positive semidefinite matrix with tr(M) = δ.

Algorithm 2 (Atomic) Away Steps Frank-Wolfe (AFW)

end for

In particular, for comparison, we consider the In-Face step from the Away-step Strategy described in [Freund et al., 2015], which uses the following direction,

3 Rank-Drop Steps

One significant issue with the FW method for nuclear norm constrained problems is that the rank of the intermediate solution often steadily increases [Freund et al., 2015], and frequently yielding a high rank solution upon termination. In Figure 1, we highlight this phenomenon. For very large problems, we cannot store the matrix Xk, and instead, only maintain the rank-one factors. Thus, computing the gradient at each iteration can be computationally prohibitive. For matrix completion, as an example, if Ω is the set of observed entries, then forming the gradient requires at least |Ω| · r inner product calculations. Since the number of observed entries, |Ω|, is typically very large, any increase in the rank of the solution greatly increases the computational time in each iteration.

To address this issue, we propose to search over the set of rank-one matrices which decrease the rank of the iterate by one. The proposed optimization formulation for determining such a rank-one matrix is motivated by the following theorem.

Theorem 3.1 ([Egerv´ary, 1960]). Let u ∈ Rm, v ∈ Rn , A ∈ Rm×n , and B = A - σ-1uv⊤. Then rank(B) = rank(A) - 1 if and only if there are vectors x ∈ Rn and y ∈ Rm such that u = Ax, v = A⊤y and σ = y⊤Ax ̸= 0.

3.1 The Rank-Drop Optimization Framework

Assume that rank(Xk) > 1. Our goal is to determine a rankdrop step which reduces the rank of Xk but has a comparable objective value. We restrict our attention to the rank-one matrices that can decrease the rank of a matrix; let R(A) denote, for a matrix A, the set of rank-drop steps, which are these rank-one matrices,

Since u and v must be in the column and row spans of A respectively, Lemma 3.2 shows that the set of rank-drop steps can be expressed in a more concise form.

Lemma 3.2. 1 Let A ∈ Rm×n with a thin SVDA = UΣV ⊤. Then we can rewrite the set of rank-drop steps as,

Let Zk ∈ R(Xk) and ˆ Zk = Zk/‖Zk‖NN . Then, similar to away steps, we consider iterates in the following form,

Our goal is to find a rank-drop step that results in a feasible iterate which best minimizes the objective. Since not all rankdrop steps lead to feasible iterates and testing for feasibility at each iteration is computationally expensive, we want to establish a verifiable sufficient condition for rank-drop steps that ensure feasibility. In Lemma 3.3, we first establish a lower bound on the nuclear norm of the rank-drop step.

Lemma 3.3. Let A ∈ Rm×n with rank r and let Z ∈ R(A) be an arbitrary rank-drop step. Then ‖Z‖NN ≥ σr(A).

To ensure feasibility of the iterate after a rank-drop step, we consider two distinct cases. Let κ(Xk) be half of the distance between Xk and the boundary of the nuclear norm ball,

We consider κ(Xk) ≥ σr(Xk), the interior case, and κ(Xk) < σr(Xk), the exterior case. For each case, we will motivate a rank-drop step formulation to guarantee feasibility of the next iterate and provide a method for its computation.

1 Due to space limitations, proofs will be omitted. The proofs will be added in an appendix at https://arxiv.org/abs/1704. 04285.

3.2 The Interior Rank-Drop Problem

Assume that κ(Xk) ≥ σr(Xk), where κ(Xk) is defined in (9). Theorem 3.4 below establishes an easily verifiable condition guaranteeing that Xk+1, after taking the rank-drop step, remains in the interior of the nuclear ball.

Theorem 3.4. Let Xk ∈ Rm×n with ‖Xk‖NN < δ, Zk ∈ R(A), and ˆ Zk = Zk/‖Zk‖NN . If ‖Zk‖ ≤ (δ-‖Xk‖NN )/2, then Xk+1 = Xk + τ(Xk - δ ˆ Zk) ∈ BNN(0, δ) for every τ ∈ [0, τ ∗ ], where τ ∗ = ‖Zk‖NN /(δ-‖Zk‖NN ). Moreover, if τ = τ ∗ , then rank(Xk+1) = rank(Xk) - 1.

Theorem 3.4 motivates the following formulation,

Problem (10) determines, in the interior case, the best rankdrop step for solving (1) based on the first order approximation to the objective. The constraint on Z guarantees that the next iterate is feasible if a rank-drop step is taken.

Theorem3.5. If rank(Xk) ≥ 1 with σr(Xk) ≤ κ(Xk), then the feasible region for (10) is non-empty.

Assume that a thin SVD for Xk, Xk = UΣV ⊤, is given. Using Lemma 3.2, the constraint in (10) can be made explicit,

To make (11) more amenable to computation, we remove the fraction using the normalization constraint s⊤Σ-1 t = κ(Xk)-1 and formulate the problem equivalently as follows,

Note that the constraints in (12) also ensure that s and t cannot be rescaled to obtain a different solution yielding an identical rank-drop step. The equivalence of (10) and (12) is formally established in Theorem 3.6.

Theorem 3.6. If Xk is a feasible point of (1) and κ(Xk) ≥ σr(Xk), then an optimal solution to (12) is an optimal solution to (11). Moreover, an optimal to (11) can always be rescaled into an optimal solution to (12).

3.3 The Exterior Rank-Drop Problem

Now consider the case κ(Xk) < σr(Xk). If κ(Xk) is relatively large and Xk is not nearly rank deficient, rank-drop is less important. If κ(Xk) is small, however, then Xk is close to the boundary of the nuclear ball. In this case, we are interested in rank-drop descent directions that move inside the nuclear norm ball. We establish the following theorems to facilitate formulating appropriate optimization problems for this case. Subsequently ∂g(X) denotes the subdifferential of g(X) at X.

Theorem 3.7. Let Xk ∈ BNN(0, δ) have the thin SVDXk = UΣV ⊤. Define Dk = Xk - δ ˆ Zk with Zk ∈ R(Xk) and ˆ Zk = Zk/‖Zk‖NN = Ust⊤V ⊤, for some s and t with ‖s‖ = ‖t‖ = 1. Then,

if and only if δs⊤t ≥ ‖Xk‖NN .

Following Theorem 3.7, Dk will be a descent direction for the nuclear norm at Xk if δs⊤t ≥ ‖Xk‖NN .

When Xk is on the boundary of the nuclear norm ball, Corollary 3.7.1 below states a simpler and useful characterization.

Corollary 3.7.1. Let Xk have the thin SVD Xk = UΣV ⊤ with ‖Xk‖NN = δ. Define Dk = Xk - δ ˆ Zk with Zk ∈ R(Xk) and ˆ Zk = Zk/‖Zk‖NN = Ust⊤V ⊤, for some s and t with ‖s‖2 = ‖t‖2 = 1. Then,

if and only if s = t.

When Xk is on the boundary of the nuclear ball, κ(Xk) = 0. Lemma 3.8 below shows that Xk is close to the boundary when either r is large or when σr(Xk) is small, assuming κ(Xk) < σr(Xk).

For the exterior case, κ(Xk) < σr(Xk), we are mostly interested in the situation when Xk is close to the boundary of the nuclear norm ball. Consequently, we motivate the next formulation assuming ‖Xk‖NN = δ as a good approximation.

When Xk is on the boundary of the nuclear norm ball, we consider all directions which move into the nuclear norm ball, hence feasible directions, as candidate solutions. From Corollary 3.7.1, this can be reduced to searching over directions Dk = Xk - δUss⊤V ⊤. Let W = U ⊤∇f(Xk)V . Note that 12 s⊤(W ⊤ +W)s = 〈∇f(Xk),Uss⊤V ⊤〉. Hence, in the exterior case, we solve the following optimization problem,

We note that (15) is a generalized eigenvalue problem, which can be further reduced to a standard eigenvalue problem since Σ-1 is a nonsingular diagonal matrix.

Theorem 3.9 below establishes that, using (15), the required step-size to decrease the rank of the current iterate also guarantees that the next iterate is feasible.

Theorem 3.9. Let s be an optimal solution to (15) and let Dk = Xk - δUss⊤V ⊤, where Xk = UΣV ⊤ is a thin SVD with ‖Xk‖NN ≤ δ. If τ ∗ = (δs⊤Σ-1 s - 1)-1 and Xk+1 = Xk + τ ∗Dk, then rank(Xk+1) = rank(Xk) - 1 and ‖Xk+1‖NN ≤ δ.

We observe that τ ∗ matches the upper bound on the stepsize for in-face steps when an away-step method is used and when ‖Xk‖ = δ.

Comparison with In-Face Steps

Lemma 3.10 and 3.11 below show that the rank-drop steps derived from (12) and (15) lie on the minimal face of BNN(0, δ) containing Xk, denoted as F(Xk).

Lemma 3.10. Suppose ‖Xk‖NN < δ and κ(Xk) ≥ σr(Xk), with thin SVD Xk = UΣV ⊤. Then Z = κ(Xk)Ust⊤V ⊤ ∈ F(Xk), where (s, t) is the solution to (12).

Lemma 3.11. Suppose κ(Xk) < σr(Xk), with thin SVD Xk = UΣV ⊤. Then Z = δUss⊤V ⊤ ∈ F(Xk), where s is the solution to (15).

We emphasize, however, that the rank-drop steps are constructed explicitly to decrease the rank of the current iterate. Specifically, we highlight the following differences between rank-drop steps and the in-face direction (5) suggested in [Freund et al., 2015]. Firstly, when the iterate is in the interior of the nuclear norm ball, the in-face steps often do not lead to rank-drop steps. Moreover, at each iteration when the iterate is in the interior, a binary search is required to determine the maximum feasible step length once the direction is computed. This requires several SVD updates, leading to very expensive intermediate iterates. Thus, it is critical for the iterates of the in-face method to reach the boundary of the nuclear norm ball quickly. Secondly, the parametrization suggested in [Freund et al., 2015] (i.e. γ1 = 0 and γ2 = ∞) for large datasets corresponds to only taking the maximum step length. On the boundary of the nuclear norm ball, this is equivalent to only accepting iterates with rank decreased. Since our proposed rank-drop is determined optimally to decrease the objective (up to the first order) among all rank-drop steps explicitly, we believe that this is a better optimization formulation when the iterate approaches the boundary.

Solving the Optimization Problem in the Interior Case

Now we discuss how to solve the Rank-Drop optimization problem (12) in the interior case. Let W := U ⊤∇f(Xk)V . The Lagrangian for (12) is,

Theorem 3.12. Suppose (s, t, λ, α, β) satisfies the KKT conditions of (12) with ‖t‖2 < 1. Then α = β = 0, λ is an eigenvalue of -ΣW, and Mλ := - 1 2 (W + λΣ-1 ) has zero as a singular value. Conversely, assume that (ˆ s, ˆ t) forms a singular vector pair of Mλ associated with the singular value zero and κ(Xk)ˆ s⊤Σ-1ˆ t > 1, then theKKT conditions of (12) are satisfied at (ˆ s, ˆ t/(κ(Xk)ˆ s⊤Σ-1ˆ t), λ, 0, 0).

Since problem (12) is nonconvex and generally difficult to solve, we only consider candidate KKT points characterized in Theorem 3.12. For each eigenvalue λ of -ΣWx, we fix α = β = 0 and choose (ˆ s, ˆ t) that corresponds to the singular vector pair of -0.5(W +λΣ-1 ) with the singular value zero. If (s, t) = (ˆ s, ˆ t/(κ(Xk)ˆ s⊤Σ-1ˆ t)) is feasible with respect to (12) and ‖t‖2 < 1, then by Theorem 3.12, (s, t, λ, 0, 0) satisfies the KKT conditions.

In the event that no feasible candidate is found, we solve (15) instead and obtain a feasible rank-drop step, guaranteed by Theorem 3.9. We remark that, although it is always possible to find feasible rank-drop steps using (15), in the interior case, it is still preferable to solve problem (12) since the assumption that s = t can be restrictive and unnecessary when far away from the boundary. Algorithm 3 presents the details of the rank-drop direction computation.

3.4 Step Selection Criteria

The criteria in [Freund et al., 2015] for away-steps require solving the regular FW linear subproblem at each iteration even when the FW step is not taken. In the rank-drop framework, we accept any rank-drop step that does not increase the objective. This allows the algorithm to maintain a lower rank SVD as well as allows the algorithm to skip computing a FW step unnecessarily. Additionally, for the rank-drop step, we observe that it is very rare that the algorithm chooses a rankdrop step two iterations in a row. Thus, we only generate the rank-drop direction when the previous iterate is a regular FW step, avoiding unnecessary rank-drop step computations.

4 Convergence Analysis

Following the proof for Theorem 4 in [Gu´elat and Marcotte, 1986], we show that the iterates, from Rank Drop FW in Algorithm 4, converge to the global optimum of (1).

Theorem 4.1. Let {Xk} be a sequence generated by Algorithm 4 and let f ∗ be the optimal value for problem (1). Assume ∇f(X) is Lipschitz continuous in the feasible region. Then f(Xk) - f ∗ ≤ 8δ2L 4+N k fw , where N k fw be the number of FW steps taken up to the iteration k.

5 Complexity Per Iteration

When computing the rank-drop steps, we note that the dimension of the subproblems is r, the rank of the current iterate. First, forming the matrix W := U ⊤∇f(Xk)V requires O(r2hmin{m, n}) operations, where h is the maximum number of nonzero elements in any row or column. In the interior case, we must compute an eigen-decomposition of an r×r matrix which takes O(r3 ) time. Then, each eigenvalue λ is used to form the matrix -0.5(W + λΣ-1 ) where the singular vector pair corresponding to the zero singular value is computed. The total time required for the interior case is O(r3 + r2hmin{m, n}). In the exterior case, O(r2 ) flops are required to compute the largest eigenvalue. Thus, the total complexity per iteration is O(r3 + r2hmin{m, n}).

6 Experimental Results

We validate the rank-drop steps on a matrix completion task using various datasets from MovieLens 2 . We first center and scale each data set to have mean 0 and standard deviation 1. We compare the proposed Rank-Drop Frank Wolfe (RDFW) against the aforementioned FW variants, FW [Frank and Wolfe, 1956], AFW [Lacoste-Julien and Jaggi, 2015], and IF(0,∞), [Freund et al., 2015], as well as a state-of-theart nuclear norm regularized solver in ActiveALT [Hsieh and Olsen, 2014].

2 http://grouplens.org/datasets/movielens/

Algorithm 3 Compute Rank-Drop Direction (rankDrop)

Input: thin SVDXk := UΣV ⊤ and ∇f(Xk). κ(Xk) ← δ-‖Xk‖NN 2 W ← U ⊤∇f (Xk)V if κ(Xk) ≥ σr(Xk) then (Interior Case) Λ ← eigs(-ΣW ) b ← -∞ for λi ∈ Λ do Mλ := - 12 (W +λiΣ-1 ) (s, t, σ) ← SVD(Mλ) (return the zero SV) if κ(Xk)s⊤Σ-1 t ≥ 1 and q (s, t κ(Xk)s⊤Σ-1 t ) > b then (s∗ , t∗ ) ← (s, t) b ← q (s, t κ(Xk)s⊤Σ-1 t ) end if end for α ← (s⊤Σ-1 t)-1 τ ∗ ← α δ-α end if if κ(Xk) < σr(Xk) or b = -∞ then (Exterior case or no candidates from the Interior Case) s∗ ← genEig(0.5(W + W ⊤), Σ-1 ) t∗ ← s∗ τ ∗ ← (δs⊤Σ-1 s - 1)-1 end if return (s∗ , t∗ , τ ∗ )

Algorithm 4 Rank-Drop Frank-Wolfe (RDFW)

Let X0 ∈ S, with initial SVD X0 = UΣV ⊤, and maximum iteration count T prevStep ← "RD" (Start with Frank-Wolfe step) for k = 0... do Compute ∇f (Xk) if prevStep == "RD" then GO TO (Frank-Wolfe) end if Compute Rank-Drop direction (see Algorithm 3): (sk, tk, τ ∗ ) ← rankDrop(U, Σ, V, ∇f (Xk)) ˜X := Xk + τ ∗ (Xk - δUskt⊤k V ⊤) if f( ˜X) ≤ f(Xk) then Xk+1 ← ˜X Zk ← -δUskt⊤k V ⊤ prevStep ← "RD" else (Frank-Wolfe) Zk ← arg minZ∈BNN (0,δ)〈Z, ∇f (Xk)〉 τ ∗ ← arg minτ∈[0,1] f (Xk + τ (Zk - Xk)) Xk+1 :=Xk + τ ∗ (Zk -Xk) prevStep ← "Frank-Wolfe" end if (U, Σ, V ) ← updateSVD(U, Σ, V, τ ∗Zk)

end for

Following [Yao et al., 2016], we randomly partition each dataset into 50% training, 25% validation, and 25% testing. The δ value in (1) is tuned with δ = µj · ‖Y ‖F , where ‖Y ‖F is the Frobenius norm of the training data matrix, and µj = 2 + 0.2j, j ∈ N. We increase j until the mean RMSE on the validation set does not improve by more than 10-3 . We terminate the algorithm when an upper bound on the relative optimality gap ensures (f(Xk) - f ∗ )/f ∗ < 10-2 or a maximum iteration count of 1000 is reached.

For ActiveALT, a regularized nuclear norm problem (not constrained) is solved where the regularization parameter λ is chosen by approximately solving for the Lagrange multiplier from the solution to the constrained problem. From the optimality conditions, we have U ⊤∇f(X∗ )V + λI = 0. Thus, λ is approximated by the mean of the diagonal values of U ⊤f(Xk)V , where Xk is the converged solution of RDFW. ActiveALT terminates when f(Xk-1) - f(Xk) < 10-4 , to match with the criterion suggested in [Yao et al., 2016] with a maximum iteration count of 150.

6.1 Computational Details

All simulations were run in MATLAB. For all FW variants, we maintain a thin SVD for the current iterate, where the SVD is updated at each iteration using a rank-one update as described in [Brand, 2006]. The rank is calculated by counting all singular values larger than 10-6 , in agreement with the definition of rank in [Freund et al., 2015].

7 Discussion

We observe that the proposed method, RDFW, shows large improvements over FW and its common variants in terms of the rank and computing time. While ActiveALT, the leading nuclear norm based matrix completion solver, is very competitive with RDFW, RDFW has the additional attractive property that it does not require knowledge of the structure of the Hessian, or even require f(·) to be twice differentiable, allowing for greater generality. Moreover, since the matrix completion objective is quadratic, this is the ideal situation for ActiveALT since the underlying solver in ActiveALT only requires one Newton step to converge, whereas with a nonquadratic objective, the computational burden can increase.

8 Conclusions

We have proposed a rank-drop optimization formulation to determine optimally descent rank-drop steps for the nuclearnorm constrained minimization. By considering the interior and exterior cases separately to ensure feasibility, we also devise subproblems that can be efficiently solved. The proposed formulation can be deployed in a projection free minimization method, e.g., FWmethod, to efficiently compute a low rank solution by maintaining low rank intermediate iterates, without compromising the strong convergence guarantees. While classic FWmethods tend to have very high rank solutions for nuclear-norm constrained problems, we have shown that the addition of rank-drop steps can drastically reduce the rank of the iterates, allowing for much faster algorithms to reach low rank solutions with less required space.

Acknowledgements

Authors acknowledge funding from the National Sciences and Engineering Research Council of Canada.