Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a a new approach to solve the Robust PCA problem. They use matrix factorisation to formulate RPCA as a more scalable problem, then learn (or optimise) parameters during the algorithm's each iteration. They also add a recurrent layer at the end to allow for "unlimited" iterations. The methods is compared against classic RPCA solvers, but not against learned methods.
main_review: Overall the paper is well written and well motivated. The proposed method makes a huge improvement compared to the classical solvers.
My main criticism is that the authors don't compare against other learned methods arguing that they are specialised on problem types. However, for a practitioner it doesn't matter if the method is generic for their specific problem, they just need the best one. Hence, I'd encourage the authors to show performance results against specialised learned methods. Even if each specialised method is marginally better than this generic one on one problem, this methods is still a major contribution to the scientific community. However, I think it is important to understand how they compare for each setting.
limitations_and_societal_impact: I don't see any obvious limitations or societal impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the problem of robust PCA inspired  by a LISTA type approach. In particular, the authors consider  a hybrid model of feedforward, and recurrent NN architectures and "learn the parameters of (scaled) GD" that is used to solve RPCA. I am not extremely familiar with the literature, but essentially the hybrid model allows for a non-apriori (in terms of the architecture) number of iterations that the algorithm can run for. This seems particularly interesting to me. The authors show that under certain conditions of the parameters, the algorithm enjoys linear convergence. The authors also show synthetic data experiments and a use-case of background subtraction to validate their results. 
main_review: Overall, the paper is well written and the thought process is clearly explained. Here are some detailed comments: 

**Originality:** A key contribution of this paper seems to be a hybrid Neural Network architecture that exploits best-of-both-worlds of Feedforward NNs and Recurrent NNs. This allows for the iterative optimization algorithm (essentially a modified version of scaled Gradient Descent) for *infintely* many iterations. To my best knowledge, I am not aware of such a approach. Thus, it would be nice to see a slightly more detailed review of such a discussion (on this line of work).


**Quality:** The paper is well written and concepts are explained clearly. I think this is an interesting result, but I have the following main comments/questions:

**Experiments**

  - Firstly, the experiments are not very convincing. The reported run-time is definitely not a fair metric since the proposed method requires a massive NN that needs to be trained. The time taken for such training needs to be reported in ALL experiments. While I understand that training is a one-time cost incurred, this is also technically not true since if the data set changes (in test time, or said another way *if the network encounters an out of distribution sample*) then of course the network needs to be trained again. 

  - In the same vein as above, this makes the claim of the "constant factor" improvement in SVD not as impressive. Also to clarify, how do the authors attain this precise per iteration complexity (described in footnote 3)? There is no mention of this contribution anywhere later in the paper.
 
- The experiments only show a run time comparison with existing methods, what about the output of the background subtraction?  This definitely needs to be included to show it outperforms (or performs at par) with existing methods. 

**Theoretical Contributions**

- Firstly, the claim that the algorithm is better than state-of-the-art is misleading. There are key references (such as *Nearly Optimal Robust Matrix Completion*, Cherapanamjeri et al., '16 and references therein) that are missing. These provide better time complexity and outlier-tolerance (under the exact model considered in this paper). 

- Second, the claim that the result is better than [10] of the paper is also debatable. While I understand that tolerating a higher step-size is somewhat beneficial, a crtical point that has not been elaborated upon is that the $\zeta_k$'s require the knowledge of $X_{\ast}$ whereas [10] makes no such assumptions. 

- The fact that the threshold in soft-thresholding is reducing in every iteration is not a new idea.  This has in fact been the basis for *Non-Convex Robust PCA*, Netrapalli et al., '14, and follow up works


**Clarity:** The paper is well written and explained. 

**Significance:** The paper introduces some new ideas regarding a hybrid model of feedforward and recurrent NN architectures. This seems to allow more control in iterative optimization procedures that is instantiated on a RPCA problem.

-----------------------

Overall, I believe that the paper has some good ideas, but the authors need to tone the discussion down  wherever applicable. 
limitations_and_societal_impact: Please see above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of robust PCA. The authors first proposed an improved algorithm based on the previous work ScaledGD. Then they proposed to use "learning to optimize" to select the hyper parameters dynamically and adaptively. The numerical results showed that the proposed method is more effective than two baselines.
main_review: The paper is well-written and the motivation is clearly explained. The proposed LRPCA algorithm (Algorithm 1) is an improved version of the ScaledGD. They are different in the initialization and the update of the sparse matrix S. Theorem 1 can demonstrate the superiority of the proposed algorithm over the ScaledGD. On the other hand, the authors use RNN to determine the step size and thresholding parameter adaptively, which is new to me, though it is still in the traditional framework of "learning to optimize".

The paper has the following weakness.

1. Some statements are not convincing. For example, in lines 34-38, the authors claimed that "Another issue is that the existing approaches only learn the parameters for a finite number of iterations". But I think this is not an issue. Nobody wants to use infinite number of iterations. "Moreover, if the user desire a better accuracy later, one may have to restart the learning process to obtain parameters of the extra iterations". One can just store the iterative information and restart from any iterations.

2. In Theorem 1, the alpha should be no larger than a value scaled by 10^4. It is better to provide some examples of the values of \mu, r, \kappa to show that \alpha can be large relatively.

3. In Figure 3, it seems that the initialization plays a very important role in LRPCA. It is not clear that why the proposed method outperform the ScaledGD when alpha is larger.

4. In Figure 4, it is not clear why LRPCA has less time cost per iteration than the ScaledGD. The authors haven't provided the computational cost of training the RNN. I think the per-iteration cost of the proposed method should be higher than that of the ScaledGD because it involves the RNN.

5. In Table 1, the stop criterion may not be a good choice because the reconstruction error is sensitive the the sparsity of S. The authors may use the relative changes of the variables X and S instead.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper propose a new technique for robust PCA that can be realised as a trainable neural network. The technique provides similar theoretical guarantees to existing methods, yet scale better to larger problems. The paper is well-written and mostly easy to follow.
main_review: The paper considers robust PCA under the usual assumption of the data being an additive composition of a low-rank matrix and a sparse (outlier) matrix. This is solved with a  technique that is quite similar to ScaledGD [10], which provide a neat gradient update that is numerically well-behaved. As I see it, the main contribution of the paper is then an 'unfolding' of this method such that it can be realized as (trainable) feed-forward neural network. This allows for significant speed-ups compared to similar methods.

Positive:
-- the paper is well-written, and does a nice job of placing itself with respect to the existing literature.
-- the observation that an RNN version of the unfolded algorithm is unstable is (in many ways) unsurprising, but the straight-forward solution concatenating a feed-forward network with an RNN is neat. It's sufficiently simple that it trust it to work.
-- the theoretical guarantees are nice; it's good to see that nothing is lost when going to more scalable algorithms.
-- Theorem 1 seems quite useful as it justifies the simple soft-thresholding.

Less-positive:
-- While the paper does a nice positioning job relative to similar RPCA methods, other branches of the RPCA literature is ignored. E.g. statements such as "Nevertheless, all existing approaches call an expensive step of singular value thresholding (SVT)" (line 30-31) is only true with a highly narrow definition of RPCA. For example, methods based on Grassmann averages

  *) Scalable Robust Principal Component Analysis using Grassmann Averages
     Søren Hauberg, Aasa Feragen, Raffi Enficiaud and Michael J. Black.
     In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI).

  *) Intrinsic Grassmann Averages for Online Linear Robust and Nonlinear Subspace Learning
      Rudrasis Chakraborty, Liu Yang, Søren Hauberg and Baba C. Vemuri.
      In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI).

does not suffer from such limitations. The first of the papers also demonstrated RPCA on terabytes of data (Star Wars IV, in HD resolution), which would indicate a significantly more scalable algorithm than the one presented here. I do not think that these (and similar) existing works diminish the contribution of the present paper, but the related work should be acknowledged.

--  Related: I found it rather confusing that the paper argues that SVD is not needed by the proposed algorithm, yet, line 4 of Algorithm 1 is a call to SVD. I acknowledge that this is just *one* call to SVD where as existing methods call SVD repeatedly, but for large data sets even a single call to SVD can be computationally (and memory-wise) prohibitive.

-- As I read the paper, the proposed method is very similar to ScaledGD. It isn't entirely clear to me if there are other benefits than a faster algorithm. Computational speed is important, so I think it is fine if a speed-up is the only benefit, but I could use a more explicit discussion of this in the paper.

-- The section "More numerical experiments" could to with a rewrite. The current text states which additional experiments can be found in the supplements, but it would be better if the text also provided a high-level summary of the findings.

Other:
-- I could not find any mention of licenses in Section 4 even if this is stated in the checklist.
-- The authors did not include code, but have promised to release upon acceptance. I find this satisfactory.
limitations_and_societal_impact: I was satisfied with this aspect of the paper.
review_title: null

Meta-review: The paper studies learned approaches to the problem of recovering a low-rank matrix from sparsely corrupted observations (here, RPCA). This problem has been intensely studied, and a number of methods have been proposed based on both convex and nonconvex optimization. The paper takes the perspective of *learned* optimization, in which one learns parameters of an optimization method from data, by interpreting iterations of the method as layers of a neural network. This has the advantage of adapting the method to (1) perform as well as possible for a given (small) number of iterations and (2) to perform as well as possible on data whose distribution mimics that of the training data. There are applications of learned optimization to RPCA. However, these approaches are based on the singular value decomposition, and so are not scalable to very large input matrices. 

The paper proposes a learned optimization method which combines soft-thresholding / proximal methods and a factorized low-rank model which is optimized using a scaled gradient descent (ScaledGD) which better copes with the ambiguity between factors. The paper uses learning to determine a sequence of step sizes and a sequence of thresholding parameters. The paper allows the learned method to be applied for arbitrary numbers of steps, by treating the layers as a recurrent neural net which can be iterated indefinitely. 

The main potential advantages compared to previous learned RPCA approaches are (1) avoiding the need to perform singular value decomposition, (2) the use of RNN’s enables the learned method to be applied for arbitrary numbers of iterations. 

The paper provides theoretical analysis showing that there exist parameters which enable linear convergence from an appropriate initialization (given by performing a single truncated SVD, as in many prior works). Experiments show significantly improved convergence speed compared to ScaledGD and alternating minimization. 

Initial reviews praised the clear motivation and presentation of the paper, as well as the idea of combining feedforward and recurrent networks to learn more flexible optimizers. At the same time, reviewers raised questions about the novelty of the paper’s proposals, the relationship to other notions of RPCA, and various aspects of the experiments. 

After responses from the authors, the reviewers converged to an evaluation of the paper as above the bar for acceptance, appreciating the paper’s empirical improvements, and the idea of combining feedforward and recurrent networks to handle arbitrary numbers of iterations. The paper would benefit from clarifications as to the novelty of the theoretical recovery results, and where technical innovations were required in the proofs.  
Decision: Accept (Poster)