Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of review:

This 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.

Approach:

The 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.

- In the greedy approach, the rank-1 update is simply added to the iterate.
- 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.

Theoretical analysis:

For 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.

Validation:

The authors went on to validate their proposed approaches in matrix completion and robust PCA.

For 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.

Writing:

Overall, the writing is clear and easy to follow. I have several detailed comments below.

Questions:

It would help improve the reviewer's understanding if the author(s) address the following questions in their rebuttable.

--- Note: Properly addressing the questions below is required for the reviewer to better appreciate your results.

(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?

(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?

(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?

Detailed comments:

- 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?

- Typo, P2: "we will found useful" -> we will find useful
review_title: A greedy approach to solving rank-constrained convex optimization with theoretical guarantees

final_score: rating: 7: Good paper, accept
review_content: Paper is about the problem of minimizing a convex function R(A) subject to a rank constraint rank(A)<=r 

Paper 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:

O(r* kappa_{r+r*} R(0) / epsilon) where kappa is related to the function's condition number.  

The 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. 

Second 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 


O(r* kappa_{r+r*} log { [ R(0) - R(A*) ] / epsilon})

These analyses and the experimental results are encouraging and make the paper be a good contribution. 

I have a couple of questions regarding numerical experiments: 

1 - I could not figure out why in Figure 3, the orange plots (greedy_3iter) have a jump in test error around Rank ~ 7

2 - 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??

Minor: thanks for sharing the source for the paper. The python code really looks like MATLAB though :-( 
review_title: review of "Local Search Algorithms for Rank-Constrained Convex Optimization"

final_score: rating: 7: Good paper, accept
review_content: 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.

In 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.

One 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).

Overall, 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.


[Minor Comments]

_ "we will found useful" -> "we will find useful"

_ 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?
review_title: Review for Paper2635

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work deals with minimizing a convex loss under a rank constraint. Relatively tight bounds and numerical tests are presented. 

i) 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. 

ii) 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. 

iii) 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?

iv) The numerical tests demonstrate the efficiency of the proposed algorithms (and its fast implementation), but they are not supportive enough for the theoretical findings. 

v) 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.

vi) 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. 

The 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. 
review_title: A rather terse paper with a few high-level or intuitive justification

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)