Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a multipass streaming algorithm for rank-r SVD.  Given an input matrix X in R^{mxn} the algorithm identifies two matrices V* in R^{nxr} and H in R^{rxr}. V* has orthonormal columns that span the top r right singular vectors.  H rotates V* so that V*H = Vr, where Vr in R^{nxr} is the matrix of the top-r right singular vectors.  V* and H are computed by minibatch gradient descent, trained until convergence with custom loss functions.  V* is computed in the first stage and then H in the second stage. 

The algorithm is accurate and uses very little storage.
main_review: The main selling point of the algorithm is that the memory needed is only O(rn), as opposed to O(r(m+n)) for competing algorithms and the result is exact as opposed to approximate.  The way this reduction is achieved is by allowing multiple streaming passes over the rows of X, whereas the competing algorithms only allow 1 pass.  This would be useful when the dataset is so large that storing a copy of the data is prohibitive and that is a realistic setting in the modern data-science workflow.

Indeed, for the purpose of dimensionality reduction it might even be sensible to only to complete stage 1.  That's because many algorithms, e.g. linear/logistic regression, kernel methods with the Euclidean kernel, and many neural network architectures, will be agnostic to the rotation H.

One small theoretical disadvantage is that the number of passes required is not known.  The authors state at most 5 passes are necessary, but actually that number was determined empirically and your number of passes depends on the number of epochs to convergence in stage 1.

Table 1 states that Range-Net space complexity is r*(n+r), however Appendix E.3 states that the implementation dumps XV*, an intermediate mxr matrix, to disk.  Specificly E.3 states "The output data [of stage 1] is dumped onto the secondary memory assuming that storing a low rank approximation is still main memory intensive. For Stage 2, this low rank approximation in the secondary memory is streamed as input, and the extracted singular values and vectors are saved in main memory." so the authors' implementation actually requires r*(m+n) storage."

I think it is misleading that the implementation does not obey the claimed memory bound.  It is true that the algorithm can be implemented without dumping XV*, but it requires more compute and passes to recalculate XV* during stage 2 and still more to compute the actual singular values.  How this extra compute affect the time required for the approximation?

In terms of writing, I think that the paper is poorly organized.  The main drawback is that there is no clear and concise description of the algorithm.  Parts of the algorithm are described in Section 3 and Appendix E, but Section 3 also contains the statements of correctness interspersed with the description.  There are terms left undefined and dimensions of matrices are only identified haphazardly.

Other notes:
. Please formally define tail energy.
. Section 1.2.  "In the absence of ... different from SVD factors".  I didn't understand this sentence at all and Equation (1) does not include any decomposition.
. I found the description of the algorithm as a neural network confusing. The network is two layers that each consist of a single matrix multiplication,  it's two single matrix multiplications which are solved for independently.
. Figure 4 caption does not match the subfigure captions


summary_of_the_review: The algorithm is interesting and practical for is extremely small memory footprint, but organizational problems prevent a higher score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a streaming method to compute an approximate Singular Value Decomposition, without requiring to load the entire data matrix into the main memory. The first stage of the method identifies a basis optimizing for the constraint of orthonormality, as well as minimizing the error between the input and the reconstruction of the input based on the learnt basis. The second stage corresponds to a rotation step, which aligns the low-rank approximation extracted with the SVD factors.
main_review: - The extent to which the choice of the hyper-parameters of AdaMax (l_r and #steps per epoch) affects the result should be made more clear. Currently, the authors simply state those choices in the Appendix without justifying them. Also, the robustness of the underlying methodology w.r.t. the exact choice of optimization framework is also not clear (e.g., AdaMax or some other variant).

- There is very limited discussion motivating the target use cases; it'd be helpful if the authors could add more detail in terms of ensuring the usefulness of having those low-rank approximations computed is clear to the reader (e.g., Sandy Big Data use case).

- The authors could add more detail on why only SketchySVD was used as a baseline; also I believe the following work is a fundamental one in the area, so might worth citing that for the reader to get a more complete view of the topic [not my paper]:
Liberty, Edo. "Simple and deterministic matrix sketching." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 2013.

- Not clear if the Range-Net being "fully interpretable" is well-justified; I am not sure of the practical significance of this statement.

Additional Comments:
- The improvement in terms of memory requirements should be highlighted more in the description of the results (e.g., Section 4.3, where SketchySVD requires 24.91GB when only 4.19MB are required by RangeNet).

- Description of the exact methodology proposed (i.e., what are precisely the steps / optimization problems) should be highlighted more clearly in the main paper. Currently, a lot of the details are compressed as part of the Implementation Details subsection, and pushed into the Appendix which is not ideal.

- "It is well known that natural data matrices have a decaying spectrum wherein saving the data in memory in its original form is either redundant or not required from an application point of view." It'd be useful if the authors could provide with some concrete example use cases here.

- The "no loss in accuracy" statement in the last sentence of the first paragraph of the Introduction is quite unclear to me; any useful approximation through SVD for data matrices is by definition lossy.


summary_of_the_review: Strong results in terms of memory efficiency, which do justify consideration for acceptance in my view; however, the paper could improve in terms of clarity of exposing experiment setup details and choices of hyper-parameters, description of the main methodology, and having stronger application use cases.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper Range-Net is proposed for calculating the right singular vectors and singular values, which produces nrealy accurate results with less memory cost than existing SkectchSVD. However, no time analysis or real runtime is listed in this paper, which is an important shortcoming of this paper.
main_review: Strengths:
	RangeNet just costs O(nr+r^2) space to calculate truncated SVD, which is memory optimal. Besides, RangeNet produces the nearly accurate results with no more than 5 passes on matrix, which is pass efficient.

Weakness:
1. No time analysis of real runtime is listed in this paper. Once this algorithm costs much time to produce results, it is not feasible in real applications.
2. There is no dataset shown which can be handled by RangeNet but cannot be handled by classical algorithms for truncated SVD. Experiments on large dataset will make this work more solid.
3. It is not fair to compare RangeNet with SketchSVD, RangeNet just produces the right singular vectors while SketchSVD produces both left and right singular vectors. Besides, the experiments in paper just compare them on matrix with size m >> n.

Some recent work on randomized truncated SVD should be compared, like:

Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
W Yu, Y Gu, Y Li - SIAM Journal on Matrix Analysis and Applications, 2018 - SIAM

Fast randomized PCA for sparse data
X Feng, Y Xie, M Song, W Yu… - Asian conference on …, 2018 - proceedings.mlr.press
summary_of_the_review: Without runtime listed in this paper, although this algorithm is memory optimal, it is not good enough. Besides, using linear optimizer to solve the truncated SVD seems not a novel idea.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a neural network architecture for computing a rank-r approximation of a matrix. The first part consisted of learning the projection and the second part consisted of learning the rotation. An experimental comparison against the state-of-the-art Sketchy SVD algorithm is provided on three datasets. The authors claim that the proposed method is extremely memory efficient compared to previous approaches.
main_review: ##########################################################################

Summary: This paper offers an interesting approach to scaling rank r approximation of a matrix.

##########################################################################

Reasons for score: I am inclined to voting for a reject (borderline). The proposed algorithm is intuitive and simple - but I think the experimental sections could be augmented with more results. I am open to changing the rating, pending the authors' responses.

##########################################################################

Pros:
1. Proposes an interesting algorithm for solving a problem widely applicable in machine learning.


##########################################################################

Cons:
1. It seems the trained neural network is specifically tied to a particular dataset. Can a trained neural network be reused for another dataset of the same size? (e.g. time series data)

2. There are some lingering questions on experiments. Why does range-net require more memory than sketchy SVD on dimension reduction (Table 3)? How much is the deviation in the computed singular vectors from orthogonality?

3. How is the neural network trained? I did not see much description in the submission.
    

##########################################################################

Questions during rebuttal period:

Please provide clarifications for the points in the previous section. I also did not see an appendix in the submission which I wanted to glance at.

#########################################################################
summary_of_the_review: While the paper proposes an interesting algorithm, in the end I did feel much void in the experimental section. Perhaps adding more dimensions in terms of algorithm comparison (one more algorithm in addition to sketch SVD) / adding more datasets could help. In addition, the authors could clarify how trained neural network can be adapted to not just one dataset but a dataset that may be related (time series).
review_title: null

Meta-review: The reviewers were fairly consistent in agreeing that this is a reasonable paper with an interesting idea.  However, the use-case is fairly narrow, as the main benefit is less intermediate storage (and only significant for very rectangular matrices) but compared to alternatives it require many passes over the data (usually 5 or so). So it's a narrow use-case and many of the comparisons are not apples-to-apples since the accuracy, time, space-complexity and number of passes differ from algorithm to algorithm.

So while acknowledging the potential benefits of the method, there are downsides too, and thus a clear presentation is very essential. The reviewers mention that presentation (listing the algorithm, clear experiments) could be improved.

On my own reading, I noted that the choice of SketchySVD as the dominant baseline is misleading. SketchySVD is for streaming data (more restrictive than single-pass) so this is an unfair comparison. The appendix does a better job of including other baselines (block Lanczos), though it mischaracterizes them (it says "BlockLanczos requires persistence presence of the data matrix X in memory", but this is not true, the method could easily be implemented in a matrix-free fashion). Another method to compare with is the single-pass algorithm randSVD in Yu et al., who show how to implement one of the Halko et al. 2011 2-pass methods in just one-pass.  Other reviewers mention baseline algorithm issues too.  I do acknowledge the improved accuracy of your method over all these baselines for some matrices, in terms of the Frobenius norm (or tail error); however, I'm not sure the differences in spectral norm are are great, and see Remark 2.1 in Martinsson and Tropp '20 for arguments about why Frobenius norm guarantees are often not as desirable as spectral norm guarantees.

Another issue is related to the left vs right singular vectors. A reviewer noted: "It is not fair to compare RangeNet with SketchSVD, RangeNet just produces the right singular vectors while SketchSVD produces both left and right singular vectors." The authors respond "Range-Net computes both left and right singular vectors but does not consume main memory to store left singular vectors at run-time". However, if we allow another pass over the matrix to find the left singular vectors, this post-processing can be applied to *any* technique that approximates the singular values and right singular vectors, hence PCA methods are applicable, including deterministic methods like the "Frequent Directions" method (Ghashami et al. '16).  

In summary, this method is high-accuracy and low-memory, yet it also has downsides compared to other methods, and the paper could use some improvement.  I don't think the paper is ready at this time for acceptance, but given the advantages of the method, I encourage the authors to make changes and resubmit an improved version to ICLR next year or other similar venue.


References:

Yu, Gu, Li, Liu, Li, "Single-Pass PCA of Large High-Dimensional Data". IJCAI '17, https://doi.org/10.24963/ijcai.2017/468

Ghashami, Liberty, Phillips, Woodruff, "Frequent directions: Simple and deterministic matrix sketching". SIAM Journal on Computing. 2016;45(5):1762-92.

Martinsson, Tropp. "Randomized numerical linear algebra: Foundations and algorithms". Acta Numerica. 2020 May;29:403-572.
Decision: Reject