Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes two simple methods to learn the sketching matrix in low-rank matrix approximation. They serve as strong baselines to compare against other data-driven methods that learn the sketching matrix from training data.
The first method (one-shot), 1Shot1Vec / 1Shot2Vec, sets the sketching matrix using the singular vectors of blocks of the matrices in the training data.
The second method (few-shot), uses a different objective from the usual data-driven low-rank approximation that avoids costly calls to the SVD.
The paper empirically validates these two approaches, showing that they are fast and are competitive with more complex methods.
main_review: Strengths:
1. Both of the proposed methods are simple and fast. They avoid costly calls to the SVD. Moreover, the sketching matrix learned is interpretable, unlike the black-box nature of existing methods.
2. The modified objective of the few-shot method sheds light on the nature of low-rank approximation, pointing out more precisely what we need in a sketching matrix.

Weaknesses:
1. The motivation for the methods are not very strong. The paper motivates the method by arguing the existing methods requires auto-differentiation, GPUs, and long-training time. The first two conditions are now quite accessible in machine learning (or almost ubiquitous), so it's not clear to me when one would use the proposed methods instead of the existing methods.
2. The advantage compared to existing methods isn't very noticeable. The two proposed methods can be seen as better initialization for the sketching matrix before running SGD. However, as seen in Figure 1, after some iterations of SGD (around 3x the amount of time of the proposed methods), existing methods also find sketching matrices that are just as good. So it seems one would need to run SGD anyway, and I'm not sure how much benefits these few-shot algorithms would bring.

============== Post-rebuttal

Thank you for the response to my questions. That has helped me understand the method better.

I've increased my rating.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work is about the optimization of sparse sketching matrix in randomized low-rank matrix approximation. The data-driven low rank approximation algorithms are developed with better computational efficiency in the training phase. The experiments show the proposed algorithms are empirically advantageous over previous work with improved training time.
main_review: 1.The sparse sketching matrix considered in this work contains a single non-zero entry in each column. This is not a widely-used sketching strategy and would lead to relatively large error in the produced randomized LRA. Allowing 8 nonzero entries in each column is more practical which makes similar accuracy of approximation to that employing Gaussian random matrix, as suggested in J. A. Tropp and Martinsson’s recent work. 
The above sparse pattern (8 nonzeros in each column) in the sketching matrix should be considered in experiments. And, it seems the proposed method does not work in this scenario, while the method in [32] is able to handle it.

2. In Section 2.1, the idea of preserving as much of the Frobenius mass in 1Shot1Vec is not explained. By the way, do you assume that 2-norm of s_i is 1? Otherwise, it cannot infer that s_i should be the top left singular vector. This strategy and that randomly selecting singular vectors in 1Shot2Vec should be supported with more solid theoretic analysis and discussion.  

3. In the experiments, what’s the Error in Fig. 1? Is that the formula after line 292 on Page 7? The value of that formula depends on the norm of the data matrix and is not very good. A dimensionless value to measure the error is preferable.
Although some matrix data are tested in Section 3, the application scenarios of them are not explained. And, the size of test matrix is small. Why is computing the LRA of them important?

Some minor concerns.
1. Algorithm descriptions should be given in Section 2.
2. Eq. (2) is wrong?
3. Step 2 of Alg. 1, alternatively, QR factorization can be applied.
4. The references are not complete, and several recent work very relevant to randomized LRA are missed, e.g.
[1] Randomized numerical linear algebra: Foundations and algorithms
PG Martinsson, JA Tropp - Acta Numerica, 2020 - cambridge.org
[2] Fast randomized PCA for sparse data
X Feng, Y Xie, M Song, W Yu… - Asian conference on …, 2018 - proceedings.mlr.press

------
After reading the authors' response and the paper again, I'm willing to raise my review score. This work is good and can be accepted, providing that the presentation is improved to address the review concerns. 
limitations_and_societal_impact: Addressed
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Problem: Sketching based techniques (such as randomized algorithms, etc) is the go to approach for deriving a low rank approximation. Despite their power in terms of space and speed to deduce the solution, these algorithms induce large approximation errors, which regresses at the downstream tasks and need to be addressed
Solution: A data-driven approach for low rank approximation -- A low rank representation is learned by optimizing a frobenius loss function over the input training and approximation. There are some challenges with this approach. The proposed algorithm is less data hungry with a two step analytical approach.
Results: Significant gains in terms of accurate low rank approximations with less resource usage. 

main_review: Distinction from state-of-the-art:
Providing a low rank approximation is a handy technique, especially in the big data world. Given that, the proposed model clearly positions w.r.t the state-of-the-art methods such as IVY and addresses some of the limitations of the earlier method. 

Pros:
The paper is well written with a few to no grammatical errors, easy to follow and understand.

An effective analytical approximation which performs better even with small amounts of data.

Cons:
First of all, the abusive use of the word “latter” is really confusing, sometimes IVY is latter and other times it is the new method, please be consistent.

Since the proposed method is so fast, I wonder, what is the effect of multiple random initializations? If you repeat the experiment for multiple runs will the results still hold on an average? Even an average of these runs can help close the gap further, can you check?

I agree the method looks better over the state-of-the-art, however, can we add more value by exploring a different dimension in this space of research? That is, can the proposed approach be considered as a general enough for multiple inputs? Of course, the ranks are not the same for all the inputs. For example, what if you can synthesize the same rank benchmarks from different distributions and apply this method either individually or by mixing them? In the individual case, can the result of one benchmark be used as the initial point for a different benchmark (a form of transfer learning)? In the mixing case, can the solution be general enough?

Based on the response, willing to up the score.


### Post author response

Satisfied with the author response and increase the score to 7.
limitations_and_societal_impact: Providing a low rank approximation is a handy technique, especially in the big data world. Given that, the proposed model clearly positions w.r.t the state-of-the-art methods such as IVY and addresses some of the limitations of the earlier method.
review_title: null

Meta-review: The paper proposes a new data-driven approach for low rank approximation. Similar to previous works, it is based on the optimization of sparse sketching matrices, which leads to important reductions in computation and memory at test time. The proposed algorithm, significantly improves the computational efficiency in the training phase.

The authors provided a high quality rebuttal including new experiments and clarifying several points raised by the reviewers. All reviewers increased their scores by one and consequently all reviewers recommend accepting the paper. 

All reviewers consider that the work makes an interesting contribution to the field. The proposed algorithm is simpler than previous work, but is able to achieve similar performance while being computationally more efficient. The method is well motivated from an analytic perspective providing several insights on the problem. For instance, the sketching matrix learned is interpretable and can be set with meaningful values extracted from the dataset.

Overall the AC considers that the paper makes a solid contribution to the field and recommends its acceptance. The authors should incorporate the several clarifications provided to the reviewers (in particular those of Reviewer oFt2).

Decision: Accept (Poster)