Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the problem of minimizing a non-smooth matrix function  $f(X)$ over the spectrahedron $S_n$, i.e., positive semidefinite matrices with trace equal to 1. Such optimization problems often arise as the convex relaxation of various low-rank matrix recovery problems. In general solving these problems with projected subgradient descent requires a projection onto the spectraherdon at every iteration, which is expensive because of the need to compute a full SVD at every step.

Under the assumption that the non-smooth objective function $f(X)$ can be written as the pointwise maximum of a family of smooth functions,  the authors reformulate the original optimization problem as a saddle point problem which can be solved via the projected extragradient method. The key contribution is that under a “generalized strict complementarity” condition and when close to the ground truth, the projection onto $S_n$ can be replaced by a low-rank projection. Therefore, the overall algorithm can be significantly more efficient, because only a low-rank SVD is needed.
main_review: Pros:
1.	Prior work by Garber 2019 [16,17] consider only smooth functions, which has relatively limited practical applications for machine learning. This paper expands the scope by considering nonsmooth functions and gives examples like robust PCA and sparse PCA, which are of interest for the ML community. 
2.	Gives an interesting counterexample where previous guarantee for projected gradient descent does indeed fail for projected subgradient descent. This justifies the use of the extragradient method proposed in this paper.
3.	The saddle-point view has further applications in the context of two-player zero sum games, and other minimax type problems in ML.
4.	This paper also establishes an interesting tradeoff between the rank of the SVD and the radius of the neighborhood around the ground truth in which the extragradient method converges.

Cons:
1. The setting of this paper is fairly restrictive. The main result of this paper only applies to functions of the form $g(X) = h(X)+\max_y y^T(\mathcal{A}(x)-b)$, where $h(X)$ is a smooth convex function and $\mathcal{A}$ is a linear map.

2. The proof techniques seem incremental in view of the previous work of [16] and [17]. It is not clear how these techniques can be further extended to more general non-smooth functions.

3. The authors do not investigate how a good initial point might be found that satisfy the assumptions of their theoretical results. Also it seems difficult to verify a priori whether the strict complementarity condition actually holds for a given problem, without already having solved it.

4. Moreover, the numerical experiments in section 5 do not demonstrate the advantage of the extragradient method. They do not show the convergence rate of the method. It would be nice if we can see a more straightforward comparison between the convergence rates and computational costs of the extragradient method and projected subgradient descent.

Minor comments:
1. I suggest that the authors define the generalized strict complementarity condition and the standard complementarity condition more clearly in the introduction. Right now both terms are used in the introduction without a clear definition, which is a bit confusing. There are numerous places where strict complementarity is referred to, and it is not clear which one is being talked about.
2. I also feel that section 2 needs a bit more motivation. It is not clear from this section why the strict complementarity condition is important and what Lemma 3 and 4 are used for.


----- Update after rebuttal -----
I have read the response of the authors. As before, my main concern is that the proposed algorithm does not have strong guarantees of success. Therefore I choose to keep my original score. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers low-rank and nonsmooth optimization problems and proposes the extragradient method to solve it. 
main_review: Strengths:

The extragradient method is proved to converge with rate $O(1/t)$ and low computational cost. 

Weakness:

1. There seems no discussion on how restrictive the generalized strict complementarity condition (Assumption 1) in the paper. It would be much better if more explanations and intuitions about this condition are given.

2.  It's said that an advantage of the extragradient method over previous standard methods is low per iteration computational cost. How faster is this method than others quantitatively?
limitations_and_societal_impact: This is a theoretical paper, and I think there is no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops an algorithm for nonsmooth convex objectives with a trace norm ball constraint. It produces an algorithm using the extragradient method and shows the method enjoys lower iteration complexity due to strict complementarity.  
main_review: I think this is a good paper and it solves a class of nonsmooth problems that are interesting. I have a few questions that would like to hear the author's comment on them. 

1. Theoretically, the algorithm needs a warm start. Even though I think warm starting the matrix variable X is easy. It is not clear to me how to initialize the vector variable y. Can the author comment on why the y is initialized in the way in Section 5? Is there any rule being used for initializing y in section 5? 

2. Is there any particular reason to use the extragradient method?  Is it because simpler methods that use only one matrix variable and one vector variable, and one gradient update in each iteration, cannot have the same convergence guarantees as the extragradient method in general? 

3. Does the 1/t rate appears in the examples in section 5? Or do you observe an even faster convergence?
limitations_and_societal_impact: I did not see the author mentioned any limitation of the current work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper develops an extragradient method for low-rank and nonsmooth matrix optimization problems. Under certain conditions, the proposed method converges to an optimal solution with rate O(1/t). Numerical experiments are provided to support the theoretical results.
main_review: 1. I think authors should use more space to the assumptions imposed on the objective function and the optimal solution. The current version is not straightforward to see if the assumptions are stringent or easy to hold. For example, it would make paper more motived to show some applications in the introduction where the assumptions do hold.
2. It would be better to discuss the initialization condition in Theorem 1. Is this initialization requirement easy to meet?
3. In the numerical experiment, there is no comparison with the state-of-the-art algorithms. Therefore, it is unknown if the proposed algorithm improves over the prior work. As far as I know, there exist more efficient algorithms (converges faster than O(1/t)) to solve the applications in the numerical experiment.

As a result, I tend to vote for rejection.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: Thank you for your submission to NeurIPS. Overall, all reviewers found the work interesting and valuable, but could not agree on whether it was ready for publication. This was a difficult decision -- while the paper provides an interesting theoretical analysis, the reviewers found the setting to be quite restrictive, and the exposition of the assumptions to be unclear. One reviewer who reviewed the proof in detail expressed some concern in the amount of overlap with prior work. The reviewers also noted that the experimental results did not build a strong case for the proposed algorithm. 
Decision: Accept (Poster)