Local Search Algorithms for Rank-Constrained Convex Optimization
Authors: Kyriakos Axiotis
Maxim Sviridenko
Venue: ICLR 2021 Poster (2021)
Keywords: low rank
rank-constrained convex optimization
matrix completion

Abstract: We propose greedy and local search algorithms for rank-constrained convex optimization, namely solving $\underset{\mathrm{rank}(A)\leq r^*}{\min}\, R(A)$ given a convex function $R:\mathbb{R}^{m\times n}\rightarrow \mathbb{R}$ and a parameter $r^*$. These algorithms consist of repeating two steps: (a) adding a new rank-1 matrix to $A$ and (b) enforcing the rank constraint on $A$. We refine and improve the theoretical analysis of Shalev-Shwartz et al. (2011), and show that if the rank-restricted condition number of $R$ is $\kappa$, a solution $A$ with rank $O(r^*\cdot \min\{\kappa \log \frac{R(\mathbf{0})-R(A^*)}{\epsilon}, \kappa^2\})$ and $R(A) \leq R(A^*) + \epsilon$ can be recovered, where $A^*$ is the optimal solution. This significantly generalizes associated results on sparse convex optimization, as well as rank-constrained convex optimization for smooth functions. We then introduce new practical variants of these algorithms that have superior runtime and recover better solutions in practice. We demonstrate the versatility of these methods on a wide range of applications involving matrix completion and robust principal component analysis.


Published as a conference paper at ICLR 2021
LOCAL SEARCH ALGORITHMS CONSTRAINED CONVEX OPTIMIZATION
FOR RANK-
Kyriakos Axiotis
Maxim Sviridenko
MIT
Yahoo! Research NYC svi vi @veri zoneedia..aaaaa.omommmmm... com
kaxioti Taxiotis@mit.cc
ABSTRACT
We propose greedy and local search algorithms for rank-constrained convex opti- mization, namely solving min R( () given convex function R [R=x ->
rank(A)gr*'
IR and a parameter r", These algorithms consist of repeating two steps: (a) adding new rank-1 matrix to A and (b) enforcing the rank constraint on A. We refine and improve the theoretical analysis of [Shalev-Shwartz et al. (20IT), and show that if the rank-restricted condition number of R is K, a solution A with rank Orr min (1 log (20)-R(AY x²)) x²)) }) and R(A) R(A") can be recovered,
where A is the optimal solution. This sigmificantly generalizes associated results on sparse convex optimization, as well as rank-constrained convex optimization for smooth functions. We then introduce new practical variants of these algorithms that have superior runtime and recover better solutions in practice. We demon- strate the versatility of these methods on wide range of applications involving matrix completion and robust principal component analysis.
INTRODUCTION
Given a real-valued convex function mxx E on real matrices and parameter y* e N, the rank-constrained convex optimization problem consists of finding matrix A E Rm** that minimizes R(A) among all matrices of rank at most r":
min R(A)
(ank(A)Sr*
Even though Rt is convex, the rank constraint makes this problem non-convex. Furthermore, it is known that this problem is NP-hard and even hard to approximate (Natarajan (1995): Foster et al. 2015
In this work, we propose efficient greedy and local search algorithms for this problem. Our contri- bution twofold:
1. We provide theoretical analyses that bound the rank and objective value of the solutions returned by the two algorithms in terms of the rank-restricted condition number, which is the natural generalization of the condition number for low-rank subspaces. The results significantly stronger than previous known bounds for this problem.
2. We experimentally demonstrate that, after careful performance adjustments, the proposed general-purpose greedy and local search algorithms have superior performance to other methods, even for some of those that are tailored to a particular problem. Thus, these algorithms can be considered a general tool for rank-constrained convex optimization and a viable alternative to methods that use convex relaxations or alternating minimization.
The restiiestrd condition number Similarly to the work in sparse convex optimization, restricted condition number quantity has been introduced reasonable assumption on R. If we let p² be the maximum smoothness bound and p, be the minimum strong convexity bound only along rank-r directions of R (these called rank-restricted smoothness and strong convexity spectively), the
condition number is defined as K, = eL_ If this quantity is bounded,

---

Published as a conference paper at ICLR 2021
one can efficiently find a solution A with R(A) & R((A)++++ + and rank == O -Krtr R(O) using a greedy algorithm (Shalev-Shwarz et al. (01I)). However, this is not an ideal bound since the rank scales linearly with π[o]_ which can be particularly high in practice. Inspired by the analogous literature on sparse convex optimization by Natarajan 1; (Shalev-Shwarzz al. (2010); (Zhang (2011); Jain et al. (2014) and more recently AAiiotis & Sviridenko (2020), one would hope to achieve
a logarithmic dependence or no dependence all on 200 In this paper we achieve this goal by providing an improved analysis showing that the greedy algorithm of ShaleevSSwarrt et al. (2011)
in fact returns a matrix of rank of O(r" Kr+r- log R(O) ). We also provide algorithm together with analysis guaranteeing rank of r O(r" - ). Apart from signifi- cantly improving upon previous work on rank-restricted convex optimization, these results directly generalize lot of work in sparse convex optimization, e.g. Natarajan (1995); (Shalev-Shwarter et al. 2010);
local search
Jain et al. (2014). Our algorithms and theorem statements can be found in Section
Runtime improvements Even though the rank bound guarantced by our theoretical analyses is adequate, the algorithm runtimes leave much to be desired. In particular, both the greedy algorithm of Shalev--Shaarre et al. (201T) and our local search algorithm have to solve an optimization problem in each iteration in order to find the best possible linear combination of features added far. Even for the case that R(A) = 2 Σ (M- - A) this requires solving a least squares problem on [S2] (iJ)
examples and x² variables. For practical implementations of these algorithms, we circumvent this issue by solving a related optimization problem that is usually much smaller. This instead requires solving n least squares problems with total number examples [S2], each on r variables. This not only reduces the size of the problem by a factor of but also allows for straightforward distributed implementation. Interestingly, our theoretical analyses still hold for these variants. We propose an additional heuristic that reduces the runtime even more drastically, which is only run few (less than 10) iterations of the algorithm used for solving the inner optimization problem. Experimental results show that this modification not only does not significantly worsen results, but for machine learning applications also acts as a regularization method that can dramatically improve generaliza- tion. These matters, as well as additional improvements for making the local search algorithm more practical, are addressed in Section 2.3
Roadmap In Section 2 we provide the descriptions and theoretical results for the algorithms used, along with several modifications boost performance. In Section we evaluate the proposed greedy and local search algorithms on optimization problems like robust PCA. Then, in Section we evaluate their generalization performance in machine learning problems like matrix completion.
2 ALGORITHMS & THEORETICAL GUARANTEES
In Sections 2.1 and 2.2 we state and provide theoretical performance guarantees for the basic greedy and local search algorithms respectively. Then in Section 2.3 we state the algorithmic adjustments that we propose in order to make the algorithms efficient in terms of runtime and generalization performance. A discussion regarding the tightness of the theoretical analysis is deferred to Ap- pendix A.4
When the dimension is clear from context, we will denote the all-ones vector by 1, and the vector that is 0 everywhere and 1 at position by 1, Given a matrix A, we denote by im(A) (A) its column span. One notion that we will find useful is that of singular value thresholding. More specifically,
given rank-k matrix A R with SVD
of such that σ1 2 2 Tke as well as an
integer parameter 2 1, we define HA(A) = Σ o to be the operator that truncates to the
highest singular values of A.
2.1 GREEDY
Algorithm (Greddy) was first introduced in Shalev-Shwarte et al. (201T) as the GECO algorithm. It works by iteratively adding rank-1 matrix to the current solution. This matrix is chosen as the
2

---

Published as a conference paper at ICLR 2021
rank-1 1 matrix that best approximates the gradient, i.e. the pair of singular vectors corresponding to the maximum singular value of the gradient. each iteration, an additional procedure run to optimize the combination of previously chosen singular vectors.
In Shalev-Shward et al. (20TT) guarantee on the rank of the solution returned by the algorithm is r" Ky-+r ROO The main bottleneck in order to improve on the R(O) factor is the fact that the analysis done terms of the squared nuclear norm of the optimal solution. As the worst-case discrepancy between the squared nuclear norm and the rank is R(0)/e, their bounds inherit this factor. Our analysis works directly with the rank, in the spirit of sparse optimization results (c.g. Shalev-Shward et al. (20IT); Jain et al. 2014);; Axiiotis & Sviridenko ). A challenge compared to these works is the need for a suitable notion of "intersection" between two sets of vectors. The main technical contribution of this work is to show that the orthogonal projection of one set of vectors into the span of the other such a notion, and, based on this, to define a decomposition of the optimal solution that is used in the analysis.
Algorithm Greedy
1: procedure GREEDY(r E N target rank)
2: function be minimized R: Rmmxn R
3: U E RR
> Initially rank is zero
4: V I
5: for & = O...r do
6:
ouv {- H1 (VR((UV)))
Max singular value and corresp. singular vectors u, > Append new vectors as columns
7:
U U+(
u)
8:
V +- (V 2)
9:
U,V <- OPTIMIZE(U,I)
return UVT
11:
procedure OPTIMIZE(U E Rax ER*))
12: X + arg min R(UXVT)
XERexr return UX,V
Theorem 2.1 (Algorithm (greedy) analysis). Let A be any fixed optimal solution of ( for some function R and rank bound r", and let 0 be error parameter. For any integer > 2r Ky4 log R(O) B(AA). if we let = GREEDY(r) be the solution returned by Algorithm 1 then R(A) < R(A") The number of iterations is
The proof of Theorem 2.1 can be found in Appendix A.2
2.2 LOCAL SEARCH
One drawback of Algorithm is that increases the rank in each iteration. Algorithm 2 is modifi- cation of Algorithm 1. in which the rank is truncated in each iteration. The advantage of Algorithm compared to Algorithm is that while Algorithm necessarily increases the rank in each iteration. More specifically, because of the greedy nature of Algorithm 1, some rank-1 components that have been added might become obsolcte have reduced benefit after number of iterations. Algorithm 2 is able to identify such candidates and remove them, thus allowing it to continue making progress.
able make progress without increasing the rank of A,
Theorem 2.2 (Algorithm 2 (local search) analysis). Let A be any fixed optimal solution of ( for some function R and rank bound r*, and let > be an ervor parameter. For any integer r 2 r" (1 8k?_..)) if we let A = SEARCH be the solution returned by Algorithm then R(A) < R(A") + e. The number of iterations is O Kr log [(O))
The proof of Theorem can can be found in Appendix A.3

---

Published as a conference paper at ICLR 2021
Algorithm 2 Local Search
1: procedure LOCAL SEARCH() E N target rank)
2: function be minimized R: Rmxx ->
3: U Omxr
D. Initialize with all-zero solution
4: V + Onxr
5:
for f = O... 1
b Run for L iterations Max singular value a and corresp. singular vectors u, Reduce rank of UV by one > Append new vectors as columns
6:
ouv f- ()
7:
U.V TRUNCATE(U.V)
8:
U +- (U u)
9:
V (V 2)
10:
U.V < OPTIMIZE(U,V)
11:
return UVT
12:
procedure TRUNCATE(U E ERR,, V ERR))
UEVT +- SVD(H+-(UVT)
Keep all but minimum singular value
14:
return UE,V
2.3
ALGORITHMIC ADICSTMENTS
Inner optimization problem search is:
The inner optimization problem that is used in both greedy and local
min R(UXVT)
X XEREX
It essentially finds the choice of matrices U and V" with columns in the column span of U and V respectively, that minimizes R(U'V'T). We, however, consider the following problem instead:
min R(UVT.. VER=xe
Note that the solution recovered from 33 will never have worse objective value than the one re-
covered from (2). and that nothing the analysis of the algorithms breaks. Importantly, (3) can
usually be solved much more efficiently than (2). As an example, consider the following objec- tive that appears in matrix completion: R(A)
Σ (M -) some C [m]] x [n]. (K.))E
let I. be an operator that zeroes out all positions in the matrix that not in Ω have VR(A) (A) [T - A). The optimality condition of (2) now is U "l -UXV V = 0 and least squares línear regression
that of U T UVT)= = O. The former corresponds problem with [S2] examples and 2² variables, while the latter can be decomposed into n independent
systems U
Σ 111 UV = U (M1,), where the variable is V which is the j-th
least squares linear regression problem with 1(i : (i.j) E [H examples and r variables. Note that the total number of examples in all systems is E1 (i (i, E [Q) = |62]. The choice of V here the variable to be optimized is jE(m)
column of V.
The j-th of these systems corresponds
arbitrary. In particular, as can be seen in Algorithm B in practice we alternate between optimizing U and V in each iteration. It is worthy of mention that the OPTIMIZE FAST procedure is basically the same as one step of the popular alternating minimization procedure for solving low-rank problems. As matter of fact, when our proposed algorithms are viewed from this lens, they can be seen as alternating minimization interleaved with rank-1 insertion and/or removal steps.
Singular value decomposition As modern methods for computing the top entries of singular value decomposition scale very well even for large sparse matrices (Martinsson et al. (): Szlam ctt al. (014)): Tulloch (2014)) the "insertion" step of greedy and local search, which the top entry of the SVD of the gradient is determined, is quite fast in practice. However, these methods are not suited for computing the smallest singular values and corresponding singular vectors, a step required for the local search algorithm that we propose. Therefore, in our practical implementations we opt to perfom the alternative step of directly removing one pair of vectors from the representation UV A simple approach is to go over all possible removals and pick the one that increases the
4

---

Published as a conference paper at ICLR 2021
Algorithm 3 Fast inner Optimization
1: procedure OPTIMIZE_ FUSSTI RRaxr V R E N iteration index of algorithm)
2:
if't mod = 0 then
X < arg min R(XVT)
XERmXr
4:
return X,
5: else
6: X c arg min R(UXT)
N return U,X
7:
objective by the least amount. variation of this approach has been used by Shalev-Shwarde et al. 2011. However, much faster approach is just pick the pair of vectors U1, V1, 1 that minimizes
U11 2 11 This is the approach that we use, as can be seen in Algorithm
Algorithm 4 Fast rank reduction
1: procedure TRUNCATE FASTTA IR
(Rxx))
2:
i arg min xE[r]
3: return (Um)),1..s1) Un41,141))) (V1I11,111)
b> Remove column
After the previous discussion, we are ready to state the fast versions of Algorithm Algorithm 2 that we use for our experiments. These are Algorithm 2.3 and Algorithm | Notice that initialize Algorithm 5 with the solution of Algorithm 2.3 and we run it until the value of R(-) stops decreasing rather than for fixed number of iterations.
Algorithm 2.3 (Fast Greedy). The Fast Greedy algorithm is defined identically as Algorithm with the only difference that it uses the OPTIMIZE FAST routine as opposed to the OPTIMIZE routine.
Alg Algorithm 5 Fast Local Search
1:
procedure
E N target rank) function to be minimized R: Rm*a +
2:
3: U, V solution returned by FAST GREEDY())
4: do
5:
Uprey, Vprev &- U,V ouv Hi (VRUUVT)) Max singular value and corresp. singular vectors u, Reduce rank of UV by one
6:
7:
U.V < TRUNCATTE.ASTTUU u)
8:
U (U
>> Append new vectors as columns
9:
V + (V v)
U, OPTIMIZE FAST(U,VVE)
11:
while R(UVT) < R(Upeey ViTev)
12:
return Uprer Vp ppev
3 OPTIMIZATION APPLICATIONS
An immediate application of the above algorithms is in the problem of low rank matrix recovery. Given any convex distance measure between matrices d Emxn Bmxx + R20. the goal is to find low-rank matrix A that matches target matrix M well as possible in terms of d: min d(M, This problem captures lot different applications, some which we go over rr)
in the following sections.
5

---

Published as a conference paper at ICLR 2021
3.1 LOW-RANK APPROXIMATION ON OBSERVED SET
A particular case of interest is when d( A) is the Frobenius norm of M - A, but only applied to entries belonging some set Ω2 In other words, d(M, A) - AM] We have compared our Fast Greedy and Fast Local Search algorithms with the SoftImpute algorithm of et al. (2010) as implemented by Rubinsteyn & Feldman (2016), on the same experiments as in Mazumder et al. (2010). We have solved the inner opumization problem required by our algorithms by the LSQR algorithm Paige & Saunders 19822.. More specifically, M UVT + 1 E R 11000100 where is some noise vector. We let every entry of U, V. be i..d. normal with mean 0 and the entries of S2 are chosen i.idd uniformly at random over the set [100] x [100]. The experiments have three parameters: The true rank r* (of TV the percentage of observed entries p [91/100, and the hignal-tonoiss ratio SNR. We measure the normalized MSE, i.e. [|[[ - 1) [12(M) I[? The results can be seen in Figure I where it is illustrated that Fast Local Search sometimes returns significantly more accurate and lower-rand solutions than Fast Greedy, and Fast Greedy generally returns significantly more accurate and lower-rank solutions than SoftImpute.
randem_crro _wworrrrrrrrrooo 113
andom_eror__1
groedy art local softimpute
groedy att
local atl
softimpute
13 5709
5700
0.5
0.2
0.2
22 15
20
20
12
15
24
20
nhC
(a) r" = 5. 0.2, SNR = 10
(b) r" = 6, p = 0.5. SNR
Figure 1: Objective value error vs rank in the problem of Section 3.1
3.2 ROBUST PRINCIPAL COMPONENT ANALYSIS (RPCA)
The robust PCA paradigm asks one to decompose given matrix M as L + 5, where L is a low- rank matrix and S is sparse matrix. This useful for applications with outliers where directly computing the principal components of M is significantly affected by them. For comprehensive survey on Robust PCA survey one can look at Bouwmans et al. (018). The following optimization problem encodes the above-stated requirements:
min S
JM Lilo
(4)
where ||X llo is the sparsity (i.e. number of non-zeros) of X. As neither the rank constraint or the to function are convex, Candès et al. (201T) replaced them by their usual convex relaxations, i.e. the nuclear norm || || and & norm respectively. However, we opt to only relax the bu function but not the rank constraint, leaving us with the problem:
min
JMM
Lll2
(5)
rank L))
Sm
In order to make the objective differentiable and thus more well-behaved, we further replace the & if | <
xx2/2 [|c]| |
norm by the Huber loss Hs(x)
thus getting:
min rank(E))rr*
HHo(M-
8²/2 otherwise'
D)j- This is problem which mization problem by applying 10 L-BFGS iterations.
directly apply algorithms. We solve the inner opti-
In Figure 2 one can PCA. The video is from the BMC 2012 dataset VVacvvant et al. (2012). In this problem, the low- rank part corresponds to the background and the sparse part to the foreground. We compare three
example of bireground-backgroww
separation from video using robust

---

Published as a conference paper at ICLR 2021
algorithms: Our Fast Greedy algorithm, standard PCA with component (the choice of 1 was picked to get the best outcome), and the standard Principal Component Pursuit (PCP) algorithm (Candès et al. (2011)), as implemented in Lin et al. (2010), where tuned the regularization parameter À to achieve the hest result. We find that Fast Greedy has the best performance out of the three algorithms in this sample task.
Foreground barbouuudbbbkgoouudd separation from video. From left to right: Fast Greedy with rank=3 and Huber loss with 20. Standard PCA with rank=1. Principal Component Pursuit (PCP) with À = 0.002. Both PCA and PCP have visible "shadows" in the foreground that appear as "smudges" in the background. These are less obvious still frame but more apparent in a video.
Figure 2:
4 MACHINE LEARNING APPLICATIONS
4.1 REGULARIZATION TECHNIQUES
In the previous section we showed that our proposed algorithms bring down different optimization objectives aggressively. However, in applications where the goal is to obtain a low generalization error, regularization needed. We considered two different kinds of regularization. The first method is to run the inner optimization algorithm for less iterations, usually 2-3. Usually this is straightfor- ward since an iterative method is used. For example, in the case R(A) = IIll optimization is least squares linear regression problem that solve using the LSQR algorithm. The second one is to add an & regularizer to the objective function. However, this option did not provide substantial performance boost in experiments, and have not implemented it.
M - A) the inner
4.2 MATRIX COMPLETION WITH RANDOM NOISE
In this section we evaluate our algorithms on the task of recovering low rank matrix UVT after observing II (UV + 1),, i.e. fraction of its entries with added noise. As in Section 3.1 we use the setting of Mazumder et al.) (2010) and compare with the SoftImpute method. The evaluation
metric the normalized MSE, defined as (UVT - (UVT-A)))(C Σ (UVT)))) where the
(EJ)E
(K.))
predicted matrix and TVT the true low rank matrix. few example plots can be seen Figure and table of results in Table We have implemented the Fast Greedy and Fast Local Search algorithms with inner optimization iterations. In the first few iterations there is a spike in the relative MSE of routine. We attribute this to the aggressive alternating
the algorithms that use the OPTIMIZE_FAS minimization steps of this procedure and conjecture that adding regularization term to the objective might smoothen the spike. However, the Fast Local Search algorithm still gives the best overall performance in terms of how well it approximates the true low rank matrix UVT and in particular with very small rank practcaayy the same the true underlying rank.

---

Published as a conference paper at ICLR 2021
randcm_erre ceremm_errrrrr
random_erm
1.0
greedy_ater local search sottimpute
groedy_ater local search sottimpute
000 005,000
100 005_omor
0.4
0.4
15
(a) k 5. p 0.2, SNR 10
(h) k 6, p 0.5, SNR
Figure 3: Test error vs rank in the matrix completion problem of Section 4.2 Bands of +11 standard shown. Note that Softlmpute starts to overfit for ranks larger than 12 in (a). The "jumps" at around rank 5-7 happen because of overshooting (taking too large a step) during the insertion the rank-1 I component in both Fast Greedy and Fast Local Search. More specifically, these implemen- tations only apply 3 iterations of the inner optimization step, which in some cases are too few to amend the overshooting. However, after few more iterations of the algorithm the overshooting issue is resolved (i.e. the algorithm has had enough iterations to scale down the rank-1 component that caused the overshooting).
Algorithm
random_error...
Hindom_error.I
random_erros
SoftImpute (Mazumder et al. (2010))
0.1759/10
0.2465/22 /28
0.2284/30
Fast Greedy (Algorithm 2.3)
0.0673/30
0.1948/ 13
0,1826/21
Fast Local Search (Algorithm 5
0.0613/14
0.1952 15
0.1811/15
Table 1: Lowest test error for any rank in the matrix completion problem of Section 4.2 and associ- ated rank returned by each algorithm. In the form error/rank.
4.3 RECOMMENDER SYSTEMS
In this section we compare our algorithms on the task of movie recommendation on the Moviclens datasets Harper & Konstan 20155). In order to evaluate the algorithms, perform random 80%- 20% train-test splits that are the same for all algorithms and measure the mean RMSE in the test set. If we let Ω S [m] [n] be the set of user-movie pairs in the training
assume that the true user-movie matrix is low rank, and thus pose (1) with R(A) = I (M A)l We make the following slight modification in order take into account the range of the ratings 1,5): We clip the entries of A between 1 and 5 when computing V R(A) in Algorithm 2.3 and Algorithm In other words, instead of 11 (A- .M) we compute the gradient as [cliciip(AA to replacing our objective by Huber loss, with the difference that we only do so in the steps that we mentioned and not the inner optimization step, mainly for runtime efficiency reasons.
5) .M.. This similar
The results can be seen in Table _ We do not compare with Fast Local Search, as we found that it only provides an advantage for small ranks (< 30), and otherwise matches Fast Greedy. For the inner optimization steps we have used the LSQR algorithm with 2 iterations in the 100K and 1M datasets, and with iterations the 10M dataset. Note that even though the SVD algorithm by Koren et al. (2009) as implemented by Hug (020) (with user/movie bias terms) is highly tuned algorithm for recommender systems that was one of the top solutions in the famous Netflix prize, it has comparable performance
perpose Algorithm 2.3
Finally, Table 3 demonstrates the speedup achieved by our algorithms over the basic greedy imple- mentation. It should be noted that the speedup compared to the basic greedy Shalev--Shaait et al. (201T) (Algorithm [ is larger as rank increases, since the fast algorithms scale linearly with rank, but the basic greedy scales quadratically.
8

---

Published as a conference paper at ICLR 2021
Algorithm
MovieLens 100K
MovieLens IM
MovieLens 10M
NMF (Lee & Seung (001))
0.9659
0.9166
0.8960
SoftImpute
1.0106
0.9599
0.957
Alternating Minimization
0.9355
0.8732
0.8410
SVD Koren et al. (2009))
0.9533
0,8743
0.8315
Fast Greedy (Algorithm 2.3)
0.9451
0.8714
0.8330
Mean RMSE and standard error among 5 random splits for 100K and 1M with standard errors < 0.01, and random splits for 10M with standard errors < 0.001. The rank of the prediction set 100 except for NMF where it 15 and Fast Greedy in the 10M dataset where it chosen Alternating Minimization is well known algorithm (e.g. [rebrr
Table 2:
to be 35 by cross-validation al. (2004)) that alternatively minimizes the left and right subspace, and also uses Frobenius norm regularization. For SoftImpute and Alternating Minimization we have found the best choice of parameters by performing a grid search over the rank and the multiplier of the regularization term. We have found the best choice of parameters by performing grid search over the rank and the multiplier of the regularization term. We ran 20 iterations of Alternating Minimization in each case.
Algorithm
Figure (a)
Movielens 100K
Movielens IM
SoftImpute
10.6
9.4
40.6
Altemating Minimization
18.9
252.0
1141.4
Greedy "Shaev-Shwaarz et al. (2011))
18.8
418.4
4087.3
Fast Greedy
10.2
43.4
244.2
Fast Local Search
10.8
46.1
263.0
Table 3: Runtimes (in seconds) of different algorithms for fitting rank=30 solution in various
experiments. Code written python and tested on an Intel Skylake CPU with 16 vCPUs.
important to note that our goal here is not to be competitive with the best known algorithms for matrix completion, but rather to propose general yet practically applicable method for rank- constrained convex optimization. For a recent survey on the best performing algorithms in the Movielens datasets see Rendle al. (2019). It should be noted that lot of these algorithms have significant performance boost compared to our methods because they use additional features (meta information about each user, movie, timestamp of rating, etc.) stronger models (user/movie biases, "implicit" ratings). A runtime comparison with these recent approches is an interesting avenue for future work. As a rule of thumb, however, Fast Greedy has roughly the same runtime as SVD (Kren et (2009) in each iteration, i.e. (( where Ω is the set of observable elements and r is the rank. some better performing approaches have been reported to be much slower than SVD (e.g. SVD++ is reported to be 50-100x slower than SVD in the Movielens 100K and 1M datasets (Hug (2020), this might also suggest a runtime advantage of our approach compared to some better performing methods.
CONCLUSIONS
We presented simple algorithms with strong theoretical guarantees for optimizing convex function under a rank constraint. Although the basic versions of these algorithms have appeared before, through series of careful runtime, optimization, and generalization performance improvements that we introduced, we have managed to reshape the performance of these algorithms in all fronts. Via our experimental validation on a host of practical problems such as low-rank matrix recovery with missing data, robust principal component analysis, and recommender systems, we have shown that the performance in terms of the solution quality matches or exceeds other widely used and even specialized solutions, thus making the argument that our Fast Greedy and Fast Local Search routines can be regarded as strong and practical general purpose tools for rank-constrained convex optimization. Interesting directions for further research include the exploration of different kinds of regularization and tuning for machine learning applications, as well as a competitive implementation and extensive runtime comparison of our algorithms.

---

Published as a conference paper at ICLR 2021
REFERENCES
Kyriakos Axiotis and Maxim Sviridenko. Sparse convex optimization via adaptively regularized hard thresholding. arXiv preprint Sttt::2006.155777 2020.
Thierry Bouwmans, Sajid Javed, Hongyang Zhang. Zhouchen Lin, and Ricardo Otazo. On the applications of robust pea in image and video processing. Proceedings of the IEFF, 106(8):1427- 1457, 2018.
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Steve Fisk. A note weyl's inequality. 1996.
Dean Foster, Howard Karloff, and Justin Thaler. Variable selection is hard. In Conference on Learning Theory, pp. 696-709, 2015.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis). 5(4):1-19, 2015.
Nicolas Hug. Surprise: A python library for recommender systems. Jourmal of Open Source Soft- ware, 5(52):2174, 2020. doi: 00.21005/0ss.021777. URL
joss. 02174
Prateek Jain, Ambuj Tewari, and Inderjit S Dhillon. Orthogonal matching pursuit with replacement. In Advances in neural information processing systems, pp. 1215-1223, 2011.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high- dimensional m-estimation. In Advances in Neural Information Processing Systems, pp. 685-693, 2014.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pp. 556-562, 2001.
Zhouchen Lin, Minming Chen, and Yi Ma. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint 100.5:100 2010.
Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert. A randomized algorithm for the de-
composition of matrices. Applied and Computational Harmonic Analysis, 30(1):47-68, 2011.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learn- ing large incomplete matrices. The Journal of Machine Learning Research, 11 11:2287-2322 2010.
Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on comput- ing, 24(2):227-2344 1995.
Christopher C Paige and Michael A Saunders. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software (TOMS), 811):43-71, 1982.
Yagyensh Chandra Pati, Ramin Rezaiffar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pp. 40-44. IEEE, 1993.
Steffen Rendle, Li Zhang, and Yehuda Koren, On the difficulty of evaluating baselines: study on recommender systems. arXiv preprint arXiv:1905.01395, 2019.
Alex Rubinsteyn and Sergey Feldman. fancyimpute: Version 0.0.16, May 2016. URL https
7/doi. http///1...2///eooe.... 51773
Shai Shalle-SSwwarz, Nathan Srebro, and Tong Zhang. Trading accuracy for sparsity in optimization problems with sparsity constraints, SIAM Journal Optimization, 2016):2807-2822, 2010.
10

---

Published as a conference paper at ICLR 2021
Shai Stalev-Shwartz. Alon Gonen, and Ohad Shamir. Large-scale convex minimization with a low- rank constraint. In Proceedings of the 28th International Conference on International Conference Machine Learning, pp. 529-336, 2011.
Nathan Srebro, Jason Rennie, and Tommi Jaakkola. Maximum-marginn matrix factorization. Ad- vances neural information processing systems, 17:1329-1336, 2004.
Arthur Szlam, Yuval Kluger, and Mark Tygert. An implementation of randomized algorithm for principal component analysis. arXiv preprint
2014.
Andrew Tulloch. Fast randomized svd. https::/reest
fb. fb.com/blog/2014/000
East pess-rrandmiied--sv 2014.
Antoine Vacavant, Thierry Chatcau, Alexis Wilhelm, and Laurent Lequièvre. A benchmark dataset for outdoor foreground/hacckroomn extraction. In Asian Conference on Computer Vision, pp- 291-300. Springer, 2012.
Tong Zhang. Sparse recovery with orthogonal matching pursuit under rip. IEEE Transactions on Information Theory, 57(9):6215-6221, 2011.
A APPENDIX
A.I PRELIMINARIES AND NOTATION
Given positive integer k; we denote [A:] 21, .k) Given matrix A, denote by || its Frobenius norm, i.e. the & norm of the entries of A (or equivalently of the singular values of A). The following lemma is simple corollary the definition of the Frobenius norm:
Lemma A.1. Given two matrices A E RRxx B 2 [1I + BBBB.)
RMxx,
have 1|A
B 1
S
Proof.
| B
EA
CA+BB) 2 (A2 2 BBJ 2(1 + +1111
Definition A.2 (Rank-restricted smoothness, strong convexity, condition number). Given a corver function R RRxx R. and integer parameter r, the rank-restricted smoothness of R rank v is the minimum constant p Z 0 such that for any two matrices A E mR B E Rmxn such that rank(A A B) < have
R(B) R(A)+ ( A)
B
A
Similarly, the rank-restricted strong convexity of R at rank is the maximum constant P7 2 0ucch that for any two matrices A E pm B E jumxn such that rank AA- - B) S r, we have
Pr B AlE
R(B) Z R(A) (VR(A), A)
Given that pt exist and are nonzero, the rank-restricted condition number of R at rank r is then defined as
PF
Ky
PF
Note that p.t is increasing and pT is decreasing in Therefore, even though our bounds are proven e
in terms of the constants and ei these quantities are always at most P. Pr and they directly imply the same bounds in terms of the constant Kr-
e Ky as long as 2 2,
Pr

---

Published as a conference paper at ICLR 2021
Definition A.3 (Spectral norm). Given matrix A E Rmx" we denote its spectral norm by ||A||2 The spectral norn is defined as
|
|| max =ER"
|
Definition AA (Singular value thresholding operator). Given matrix A E mx of rank k, singular value decomposition UEV such that Σ11 2 E2a 2 ... 2 Enke and an integer 15 r S k. we define (A) -U'V, here E' is a diagonal matrix with
Ee Sf
2/ 10
otherwise
In other words, H.).) is an operator that eliminates all but the top r highest singular values of matrix.
Lemma A.S (Weyl's inequality). For any matrix A and integer i 2 1, let (A(A) be the i-th largest singular value of A or 0 rank(A), (A). Then, for any two matrices A, B and integers i 2 1,J 1:
0+t5-1(A+ B) I (A(A) + o,(
A proof of the previous fact can be found e.g. in Fisk 1996).
Lemma A.6 (-)(-) optimization problem), Let A mx be rank-k matrix and E [k] be an integer parameter. Then M x (A) is an optimal solution to the following optimization
problem:
max ((A, rank(M)
1
(6)
Proof. Let USVT = E.UV, be a singular value decomposition of A. We note that (6) is equivalent to
min S)
IA- AMI = ((M)
Now, note that f(2 = 11A H,(A))
Dg On the other hand, by applying Weyl's
inequality (Lemmal A.5 for r
ktr
ktr
f(M) || AM
Σ
d XM)
Σ ()++)))))) Σ Σ
im++1
where the last equality follows from the fact that rank(A) k and rank(M) < Therefore,
M = (A) minimizes 7 and thus maximizes 6))
A.2 PROOF OF THROREM 2.1 (GREEDY)
We will start with the following simple lemma about the Frobenius norm of sum of matrices with orthogonal columns or rows:
Lemma A.7. Let E R V E R ,X R' Y Raxr such that the columns of U orthogonal to the columns of X or the columns of V are orthogonal the columns of Y. Then |UVT + XY
JUV |/ XXTT
Proof. If the columns of U are orthogonal to those of X, then U = 0 and if the columns of are orthogonal to those of Y. then TV 0. Therefore in any case (UVT (UV..XYT) Tr(VU ( Tr(U XY V) 0. implying
|UVT + XY | 2 + |XXT | + 2 XXT) |0V + XX
12

---

Published as a conference paper at ICLR 2021
Additionally, we have the following lemma regarding the optimality conditions of (2):
Lemma A.8. Let A = UXVT where U E RRxxr, X R and V E R such that X is the optimal solution to 2). Then for any u E im(U) and v E im(V) we have that (V R(A), ue )) O.
Proof. By the optimality condition 2 we have that
U VR(AV==
Now, for any u Un and
Vy we have
(V (VA))),w)) = u VR(A) - VR(A)Vy= 0
We now ready for the proof of Theorem 2.1
Proof. Let At-1 be the current solution UVT before iteration t 2 Let u E R and v E R" be left and right singular vectors of matrix V R(A),, i.e. unit vectors maximizing (VV((A) ) Let
B, = BB = A 1 + muv? ,7 .7ER)
By smoothness we have
R(Ar-1) R(A,) 2 max
(R(A--1)-R(B)
BEB,
max BEB,
-
B
A
2
Pi
(IVR(AA-1).u0)))
max "
n/ n|[ 172 pt
max
9
(VR(A-))
2p
where || l|2 is the spectral norm (i.e. maximum magnitude of singular value).
On the other hand, by strong convexity and noting that
rank(A" Ar-1) S rank rank(A") + (ank(A(-)) S +r,
R(A-) R(A,-1) (VR(A.-), A* A(-1) Prtr' ||A At-1l1
(8)
Let A-1 UV and A U.V*T. We let mm))
UY+ and I[](V)
V(VTV)+VT denote the orthogonal projections onto the images of U and respectively. We now write
A = UU- = (U + + = U +U +
where 1 = U* is a matrix where every column of U is replaced by its projection im(U) and 2 = -1² and similarly V1 = llim(v) V is matrix where every column of V is replaced by its projection im and 22 = - Vl. By setting U' (-U U') and V (V V1) can write
A A.-1 = U'VIT U u where im") = im) and im(V') = im(V). Also, note that
rank( ra & rank(V") rank(A") < r*
13

---

Published as a conference paper at ICLR 2021
and similarly rank(U?2v-T) S r". So now the right hand side of (8) can be reshaped as 11-1) (VR(A--1),A-- - + Prtr* ||A- 11-1
-VRRAL- + + ) + Aut + V + +
Now, note that since by definition the columns of U are in im(U) and the columns of V are in im(V), Lemma A.8 implies that (V (Vt U'
) = 0. Therefore the above is equal to
(VR(A-I),U'V2 + + Prtr* |U'V' + + + + 11
2
(VR(A-1), + 1)) U2
Prtr (1 11: + -| 12:)
2
VR(Ar-1), M) + Pptr" M ||
2
min Sr
Hr,- (VR(A,-1))1
2prtr'
[[)((A,)))1
Prtr*
where the first equality follows by noticing that the columns of V and V are orthogonal to those of 22 and the columns U' and U are orthogonal to those of U2, and applying Lemma The last equality is direct application of Lemma A.6 and the last inequality states that the largest squared singular value is not smaller than the average of the top r" squared singular values. Therefore we have concluded that
Prtr" (R(Ar-1) I((A))
V V
Plugging this back into the smoothness inequality, we get
R(A.-1) - -R(A)) 2 25* (R(A--1)- - - R(A"))
or equivalently
R(A.)- - R(A*)= < (1 (1- 2r (R(A,-1)- P((A)).
Therefore after L = *r* log I(Ao)-((A)) iterations we have
1 (R(Ad) R(A)))
((AT)-R((T))
2r
e _ (R(Ap) - R(AA))
Since Ao O, the result follows.
A.3 PROOF OF THEOREM
2.2 (LOCAL SEARCH)
Proof. Similarly to Section
A.3 we let A, be the current solution before iteration ビ- 1 > 0. be left and right singular vectors of matrix VR(A), i.e. unit vectors
Let u R and v E R maximizing (VR(A)) R2 A), we T) and let
B. B A,1 + uanrr minnxy T :7 TR),
14

---

Published as a conference paper at ICLR 2021
where mi T A HH is the rank-1 term corresponding to the minimum singular
value 41-1. By smoothness we have
R(A,-1) R(AA)
2 max {R(A(-1) R(B)) BEB,
(VR(A,-1)) 1). - Al-1) - P2 B A 11
max BEB,
2
Omiuxyy 1y
P2
Ominxy 11:
max
VEB
max DER
(VR(A,, 11.
- 1 - min
V7/ ( 1)112 - ~n² Sminp Pi
max
NER
VR(AA-1)1B
minP2
4p
where in the last inequality we used the fact that (VR(A(-1), = 0 following from Lemma A.8 as well as Lemma A.
On the other hand, by strong convexity,
R(A7) R(A,-1) 2 (VR(A-I),A) A1-1)+ Prtr' ||A" A1-111
Let A,1 TV and A =U- We write
A" = U-V = (U' + (V +V)T
+ + U
where U is a matrix where every column of U is replaced by its projection on im(U) and U2 U U1 and similarly V1 is matrix where every column of V* is replaced by its projection on im(V) and 122 =** V2. By setting U' = (-U U²) and V = (V (V)) we can write
A- = -UV' 2 +
where imm) UU) and im()) im(V). Also, note that rank(U4 S rank (V2) S rank(V**) rank Sr and similarly vank(U/²v-T) S So
So we now have
(VR(A)-1), Ac-1) + Prtr. |A- A1-1112
2
=VRR(A,)), + UU + +UZV.T)
Prtr
"U''" +U-V2T +UZV+TIP
2
(VR(AL-),U'V U2V + Prtr
11''ITT + V2T + +U }
2
(VR(A,-),,UVVTT + +UV + Prtr"
(I0'NVT 12++ + | + 2 T 11:
2
2 (VR(AL-)),U + U2V + Prtr (I 12 + 1122 T 112)
2
Prte II'''T
(VR(A.-)),)) Prtr |MI
+ Prtr- 11
22 2 min mank(M))Sr*
- Hp- (VR((AA-))))
Petrr
||
2pr+r-
2
2
[VR(A..)))E
Prtte
||U'V'
11
Pr+c
2
15

---

Published as a conference paper at ICLR 2021
where the second equality follows from the fact that [VR(A,1)) uu uE
for any im(U).
im(V) the third equality from the fact that im(U²) 1 im(U") U im and im() 1 iV') and by applying Lemma A.7 and the last inequality from the fact that the largest squared singular value not smaller than the average of the top rt squared singular values. Now, note that since
"ank(U-VVT)) r* < rank(UVV
11'' 11 = |1'VIT - UV
Σ O2(U'VI--UV)
=
Σ )
ir''41
2 (r - r" min(
= (r - r") m'm (Ac-1),
where we used the fact that rank(U?2 s r* together with Lemma concluded that
A.5
Therefore we have
V Prtr' (R(A,-1) R(A*)) + (p )0 r*)
min
7"
2r
Plugging this back into the smoothness inequality and setting R
get
Prtr
1 (R(A-11)
(r
R(A:-1)- -R((,)) 2
R(A*)) (R(A)))
oii (Ap-1)
4
8r
2 4
(R(AL11)
long as (1 8k or equivalently,
R(A,) R(A") = (1
4 (R(A)-1) - R(A"))
Therefore after L = 4r log R(Aa)-R(A") iterations we have
R(AA)-HHl <
(R(AA) - R(AA))
4r*
x (R( - R(AA))
Se
Since Ap 0 and R. S Krtr", the result follows.
A.4 TIGHTNESS OF THE ANALYSIS
It is important to note that the Kytr- factor that appears in the rank bounds of both Theorems 2.J and 2.2 is inherent in these algorithms and not an artifact of our analysis. In particular, such lower bounds based on the restricted condition number have been previously shown for the problem of sparse linear regression. More specifically, Foster et al. 2015) showed that there is a family of instances in which the analogues of Greedy and Local Search for sparse optimization require the sparsity to be 2((* for constant error e > O, where s" is the optimal sparsity and is the spar- sirt-rest condition number. These instances can be easily adjusted to give a rank lower bound of kr++)) for constant error e > 0, implying that the x dependence in Theorem 2.1 is tight for Greedy. Furthermore, specifically for Local Search, Axiotis & Sviridenko (2020) additionally
16

---

Published as a conference paper at ICLR 2021
showed that there is a family of instances in which the analogue of Local Search for sparse optimiza- tion requires a sparsity of Q0ss (x²)²). Adapting these instances to the setting of conk-constrained convex optimization is less trivial, but conjecture that it is possible, which would lead to a rank lower bound of 2(r"*)+4" ) for Local Search.
We present the following lemma, which essentially states that sparse optimization lower bounds for Orthogonal Matching Pursuit (OMP, Pati et al. (1993)) (resp. Orthogonal Matching Pursuit with Replacement (OMPR, Jain et al. ())1T)) in which the optimal sparse solution is also global optimum, immediately carry over (up to constants) to rank-constrained convex optimization lower bounds for Greedy (resp. Local Search).
Lemma A.9. Let f E R + R. and e R" be an -sparse vector that is also a global mininizer of f. Also, let J have restricted smoothness parameter B at sparsity level 8 + 8* for some & 2 s* and restricted strong convexity parameter sparsity level s". Then we can define the rank- constrained problem, with R Ruxx - R.
R(A) == f(diag(A)) + -.11 11 diagg()) 5
min
where diag(A) is a vector containing the diagonal of A. R has rank-restricted smoothness at rank + at most 23 and runk-restricted strong convexity rank s s" at least a. Suppose that run t iterations of OMP (resp. OMPR) starting from a solution x, to get solution x', and similarty run t iterations of Greedy (resp. Local Search) starting from solution A diag(z) (where diag(z) is diagonal matrix with x on the diagonal) to get solution A'. Then A' is diagonal and diag( (A') x'. In other words, in this scenario OMP and Greedy (resp. OMPR and Local Search) are equivalent.
Proof. Note that for any solution Å of we have R(A) 2 f(diag(A) 2 f(=)). with equality only if is diagonal. Furthermore, rank diag((")) )) < s", meaning that diag(x") is an optimal solution of (9.. Now, given any diagonal solution A of (9 such that A diag(z), we claim that one step of either Greedy or Local Search keeps it diagonal. This is because
2 (A - dAa)(A)) = diag(V (z)))))
VR(A) = ((siig(V[(()))))))))))))()))(()) +
Therefore the largest eigenvalue of V((A) has corresponding eigenvector 1, for some i, which implies that the rank-1 component which will be added is multiple of 1,1, For the same reason the rank-1 component removed by Local Search will be multiple of 1 for some j. Therefore running Greedy (resp. Local Search) on such an instance is identical to running OMP (resp. OMPR) on the diagonal.
Together with the lower bound instances of Foster et al. (2015) (in which the global minimum prop- crty true), it immediately implics a rank lower bound of [x(r"kx447) for getting a solution with constant eиror for rank-constrained convex optimization. On the other hand, the lower bound in- stances of Axiotis & Sviridenko 2020) give a quadratic lower bound in λ for OMPR. The above lemma cannot be directly applied since the sparse solutions not global minima, but we conjec- ture that a similar proof will give a rank lower bound of ((r"*r optimization with Local Search.
k for rank-constrained convex
A.5 ADDENDUM TO SECTION 4
17

---

Published as a conference paper at ICLR 2021
movielens 100k_ 2
1.8
greedy_3ite
local acal_search_ search_3iter
error
1.4
1.0
0.8
15
30
45
rank
Figure 4: One of the splits of the Movielens 100K dataset. We that for small ranks the Fast Local Search solution is better and more stable, but for larger ranks it does not provide any improvement over the Fast Greedy algorithm.
random error
randam error
gready local Leaar" sottippuoo
gruady lccal pearc"
sottmppte
02
02
22
15
20
22
24
mbC
13C
(a)
10, 0.5, SNR
(b) 10. = 0.3, SNR 3
Figure 5: Test emror vs rank in the matrix completion problem of Section 4.2 еттог are shown.
Bands +1 standard
18

---

Published as a conference paper at ICLR 2021
randem, erfor
random, error
gradyy_
gredd
0.0
0.8
0.4
0.4
(a) Train error vs rank
(b) Test error vs rank
Figure 6: Performance of greedy with fully solving the inner optimization problem (left) and ap- plying iterations of the LSQR algorithm (right) in the matrix completion problem of Section 4.2 = p 0.2, SNR 10. Bands of #1 standard error shown. This experiment shows why crucial to apply some kind of regularization to the Fast Greedy and Fast Local Search algorithms for machine learning applications.
19


Reviews:
[{"review_id": "y9ZQeh562sA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of review:\n\nThis paper considers solving rank-constrained convex optimization. This is a fairly general problem that contains several special cases such as matrix completion and robust PCA. This paper presents a local search approach along with an interesting theoretical analysis of their approach. Furthermore, this paper provided extensive simulations to validate their approach. Overall, the paper provided solid justification for their approach.\n\nApproach:\n\nThe proposed approaches, namely greedy and local search, iteratively add a rank-1 update to the current solution, where the rank-1 update comes from the maximum singular value and eigenvector of the current gradient. After performing the rank-1 update, an inner optimization problem is performed and operates in a low-rank (compared to the dimension of the input) space.\n\n- In the greedy approach, the rank-1 update is simply added to the iterate.\n- In the local search approach, the iterate goes through an additional truncation step, which reduces its rank by one before adding the rank-1 update.\n\nTheoretical analysis:\n\nFor both approaches, this paper proves that the iterative procedure converges with a solution within $\\epsilon$ to the optimum in $r^{\\star} \\kappa^2 \\log{O(1 / \\epsilon}$ iterations, where $r^{\\star}$ is the rank of the optimal solution of the minimization problem and $\\kappa$ is a certain rank-restricted condition number. This result is quite interesting because it provides an explicit upper bound on the rank of the converged iterates. The arguments in the analysis look sound to me.\n\nValidation:\n\nThe authors went on to validate their proposed approaches in matrix completion and robust PCA.\n\nFor matrix completion, the authors compared their approach to SoftImpute (Mazumder et al 2010), which is a well-known approach in this literature. They showed their approach outperforms SoftImpute in simulations. Then, the authors compared their approach to NMF and SVD on the MovieLens datasets and showed their approach achieves comparable test loss while speeding up the computation by several factors.\n\nWriting:\n\nOverall, the writing is clear and easy to follow. I have several detailed comments below.\n\nQuestions:\n\nIt would help improve the reviewer's understanding if the author(s) address the following questions in their rebuttable.\n\n--- Note: Properly addressing the questions below is required for the reviewer to better appreciate your results.\n\n(i) In Table 2 and 3, could you add a comparison to SoftImpute and Alternating Minimization with L2 Regularization (say you choose the rank via cross-validation)? How would your results compare to these approaches?\n\n(ii) Specific to the MovieLens benchmark, could you discuss how your approach compares to more recent approaches (as opposed to 2009, https://paperswithcode.com/sota/collaborative-filtering-on-movielens-10m)? Particularly the runtime improvements since these look like the key claims of this experiment. While these approaches may not apply to generic constrained convex optimization, it is still worth discussing?\n\n(iii) How large should I expect the rank-restricted condition number to be in Theorem 2.1 and 2.2? For example, how large are they in the setting of Figure 1 and 3?\n\nDetailed comments:\n\n- Section 2.1 and 2.2: these two theorems and the algorithms came out all of a sudden with no description. Could you add some explanation and describe some intuition?\n\n- Typo, P2: \"we will found useful\" -> we will find useful", "extra_scores": {}, "extra_text": {}}, {"review_id": "n2FulG0WjcY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work deals with minimizing a convex loss under a rank constraint. Relatively tight bounds and numerical tests are presented. \n\ni) Overall, this is a very terse paper at least to appreciate its analytical merits. A couple of theorems are presented in the main text without elaboration, which makes it hard to gain insights. For example, it is claimed that the analysis of Theorem 1 improves over [Shalev-Shwartz 2011], but it is not clear where the improvement comes from. Is it a new inequality or something else? In addition, in the local search of Algorithm 2, it is also difficult to grasp intuitively why it offers an improvement over Algorithm 1. \n\nii) In addition, some parameters which seem important in the analysis are not explained well. For example, in both Theorems 1 and 2 the phrase “let A* be the optimal solution,” implies that the solution to (1) is unique. But this has not been established. And for the rank-restricted condition number \\kappa_r, one wonders what will happen if \\rho_r^- = 0. In this case, it seems that \\kappa_r = \\infty, and the results in Theorems 1 and 2 no longer hold. \n\niii) It seems that in order for Theorem 1 to hold, r^* (which is the constraint on rank(A)), has to be smaller than 0.5min{m,n}? What if this condition is not met?\n\niv) The numerical tests demonstrate the efficiency of the proposed algorithms (and its fast implementation), but they are not supportive enough for the theoretical findings. \n\nv) Why does the test error of soft impute (the pink line) increase with rank in Fig.3 (a)? And no clear-enough description of implementation is provided so one has to check the code carefully.\n\nvi) In Section 4.1, it appears that the method running fewer iterations for the subproblem can be also theoretically supported by solving this subproblem to a certain accuracy. \n\nThe current form of this paper do not cross the acceptance threshold of this competitive conference. A major revision is due to better argue and justify the claims, but also provide enough implementation details. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "S5rJoGS9DXZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper is about the problem of minimizing a convex function R(A) subject to a rank constraint rank(A)<=r \n\nPaper builds on an algorithm (GECO, for Greedy Efficient Component Optimization) proposed by Shalev-Shwartz et al. (2011), which was already proven to find a solution to the problem in:\n\nO(r* kappa_{r+r*} R(0) / epsilon) where kappa is related to the function's condition number.  \n\nThe complexity of the solution of GECO is improved by the author of the present paper, by using techniques borrowed from sparse convex optimization, and they get a dependence in R(0) / epsilon that is logarithmic. This is their first contribution, in Theorem 2.1. \n\nSecond contribution is to use a series of approximations to the different steps involved in GECO. Using the proposed approximations, authors prove, in Theorem 2.2, that the complexity can further be reduced to \n\n\nO(r* kappa_{r+r*} log { [ R(0) - R(A*) ] / epsilon})\n\nThese analyses and the experimental results are encouraging and make the paper be a good contribution. \n\nI have a couple of questions regarding numerical experiments: \n\n1 - I could not figure out why in Figure 3, the orange plots (greedy_3iter) have a jump in test error around Rank ~ 7\n\n2 - Table 3 gives runtimes of the proposed algorithms versus the parent algorithm GECO. The proposed algorithm runs faster, OK, but does it have the same or lower reconstruction / test error? In fact, what is missing is test error of GECO in table 2. I fear that it is not reported because it was better than the proposed algorithm??\n\nMinor: thanks for sharing the source for the paper. The python code really looks like MATLAB though :-( ", "extra_scores": {}, "extra_text": {}}, {"review_id": "HfF12VldaL7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of rank-constrained convex optimization. Its primary contributions are an improved analysis with convergence rate logarithmic in R(0)/eps (rather than poly(R(0)/eps)), as well as some adjustments to the implementations of the greedy and local search methods which result in better empirical performance.\n\nIn terms of experimental performance, the authors consider several problem settings, including robust PCA, matrix completion with random noise, and recommender systems. Here, they show that their methods are generally competitive with, and sometimes even improve upon previous methods both in performance and in runtime.\n\nOne clarification: is the Greedy algorithm (Algorithm 1, with Optimize rather than Optimize_Fast) exactly the same as in Shalev-Shwartz et al. (2011)? If so, this could be made more clear, especially since the implication is that the benefit for this case appears to be just in terms of the improved analysis for a logarithmic dependence. Building on this, it would be nice to say just a bit more about how (at a high level) the analysis has changed to allow the exponential improvement, as well as how these changes compare to the analogous results of, e.g., Axiotis & Sviridenko (2020).\n\nOverall, I feel the paper provides a nice contribution, both theoretical and practical, to the problem of rank-constrained convex optimization that neatly builds upon previous work.\n\n\n[Minor Comments]\n\n_ \"we will found useful\" -> \"we will find useful\"\n\n_ The abstract claims that the theoretical analysis is \"tight\". By this do you mean tight in terms of what can be shown (or can hope to be shown) for greedy and/or local search methods, or do you mean tight in an oracle sense? Can either of these be shown?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Please clarify as early as the abstract that you refine the analysis of the algorithm proposed by Shalev-Shwartz et al (which is a great contribution given the importance of the problem).
Decision: Accept (Poster)