Matrices are exceptionally useful in various fields of study as they provide a convenient framework to organize and manipulate data in a structured manner. However, modern matrices can involve billions of elements, making their storage and processing quite demanding in terms of computational resources and memory usage. Although prohibitively large, such matrices are often approximately low rank. We propose an algorithm that exploits this structure to obtain a low rank decomposition of any matrix $\mathbf{A}$ as $\mathbf{A} \approx \mathbf{L}\mathbf{R}$, where $\mathbf{L}$ and $\mathbf{R}$ are the low rank factors. The total number of elements in $\mathbf{L}$ and $\mathbf{R}$ can be significantly less than that in $\mathbf{A}$. Furthermore, the entries of $\mathbf{L}$ and $\mathbf{R}$ are quantized to low precision formats $--$ compressing $\mathbf{A}$ by giving us a low rank and low precision factorization. Our algorithm first computes an approximate basis of the range space of $\mathbf{A}$ by randomly sketching its columns, followed by a quantization of the vectors constituting this basis. It then computes approximate projections of the columns of $\mathbf{A}$ onto this quantized basis. We derive upper bounds on the approximation error of our algorithm, and analyze the impact of target rank and quantization bit-budget. The tradeoff between compression ratio and approximation accuracy allows for flexibility in choosing these parameters based on specific application requirements. We empirically demonstrate the efficacy of our algorithm in image compression, nearest neighbor classification of image and text embeddings, and compressing the layers of LlaMa-$7$b. Our results illustrate that we can achieve compression ratios as aggressive as one bit per matrix coordinate, all while surpassing or maintaining the performance of traditional compression techniques.
Paper
Similar papers
Peer review
Summary
This work studies the problem of computing a low rank approximation when the low rank factors are under a bit budget constraint, that is, we must output factors L and R with bounded bits such that LR approximates a given input matrix A in the Frobenius norm. The authors show that by incorporating sketching into the quantization procedure, one can get improved bounds, due to the fact that a Gaussian sketch can “flatten” the entries of a vector, which is advantageous when rounding (Appendix D). Empirical results show that this algorithm indeed gives improved results over other naive implementations such as directly rounding SVD factors.
Strengths
The problem of efficiently quantizing low rank approximations is an extremely important problem given that both low rank approximations and low precision is gaining popularity for compressing massive neural networks (https://papers.nips.cc/paper/2020/file/13b919438259814cd5be8cb45877d577-Paper.pdf, https://arxiv.org/abs/2302.03764). This work offers an interesting new method which takes advantage of the “flattening” property of Gaussian sketches in order to obtain improved results for quantization in the context of low rank approximation. This idea is conceptually simple yet interesting. Empirical results are also convincing.
Weaknesses
The contribution is already quite nice, but there are several followup investigations that could strengthen this work much more: * Are there any lower bounds on the trade-off between the approximation accuracy and the bit budget? * There are structured sketching transforms such as the Subsampled Randomized Hadamard Transform (see Theorem 2.4 of http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/wNow3.pdf) which also have the “equalizing” or “flattening” type of behavior, yet can be applied in much faster time, and furthermore also save on the storage of the sketching matrix since it is an integer matrix. Can this be used to get faster implementations in theory/practice? * Can you report the running time of the experiments? * Can you comment on whether the bit bounds imply actual savings in the memory usage, or are the practical implementations of bit complexity too crude to capture these improvements?
Questions
* Should put A \approx LR in the abstract * Some of the references in the Related Works section for Low-rank approximation seem inappropriate for the context. Candes-Tao and Recht et al are not focused on faster algorithms for SVD, but rather a related but different problem of matrix completion. Gradient descent on the low rank factors is indeed one way to solve approximate SVD, which I agree Zhang et al captures, but there may be more appropriate references such as https://arxiv.org/abs/2106.14289 and references within. * Line 58: you should first establish that n >= d, or else the SVD time should be O(min{nd^2, dn^2}) * Typo (line 77): should be “instead of quantizing x directly” * Is the randomized rounding in Section 2.1 necessary? Can you get better results with naive rounding? * Line 177: what do you mean by “saturated” and “unsaturated”? Please define this term, it is unfamiliar to non-experts.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Discussion of limitations is limited. This work is mainly theoretical, and there are no potential negative societal impacts.
Summary
This paper introduces a novel low-rank matrix factorization algorithm that is using sketching matrix idea and quantization, such as they do: 1. Use Gaussian RV to generate sketch of the matrix and compute the approximate basis 2. Use Quantization with Q - to get Q(AS) 3. Use Q(AS) and Q' to get Q'(W) 4. Return Q(AS) and Q'(W) Authors provide theoretical and numerical analysis of their idea.
Strengths
- introduction section written very well & and very informative and to the point, such as introducing LPLR algorithm briefly, talking about Low-rank approximation and Randomized quantization. - the introduced algorithm clearly communicated and results are theoretically sound.
Weaknesses
- Abstract seem to be a bit wordy - it would be nice if there were formulations and numbers that grabs readers attention with resutls. - i like the way motivating the work - with memory constraints - but i am curious is there any application in real life for low rank decomposition that actually saves memory. some examples would be good - the paper doesn't exactly introduce a new direction - rather seems to be using existing ideas and put them together.
Questions
Table 1 & 2 is a bit puzzling me - it seems that Approximataion Error of Naive Uniform is smaller than LPLR and with cheaper computation cost. Do you think that you can clarify in the table itself - why LPLR is better ? because it seems to be confusing in the first glance.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
The are many sketching / matric factorization algorithms, i am puzzled why we only presented Naive Uniform and Direct SVD algorithms as comparison points.
Summary
The authors investigate combining low-rank matrix factorization and (uniform scalar) quantization. Through theoretical analysis and experiments they demonstrate that this can yield much higher accuracy than directly quantizing the input matrix. One natural choice is to compute the SVD of the matrix and quantize the two factors independently. It's shown that quantizing the left factor first and then computing a new right factor that best approximates the input when multiplied with the quantized left factor yields much better result. The choice of SVD is not critical and could be replaced by randomly mixing the columns of the input matrix, i.e. random sketching. In fact sketching has provable benefits as the entries of sketched matrices are bounded with very high probability. This bounded range improves quantization theoretically. The authors prove several theorems (their proofs are in the extensive appendix) and conduct detailed empirical evaluation.
Strengths
1) All the key ideas of the paper (low-rank approximation, sketching) are sound. 2) Detailed theoretical analysis with rigorous proofs. 3) Extensive experiments. 4) Compression of neural network weights and embeddings via low rank approximation and quantization are popular and impactful topics both to reduce memory usage and to speed up training and inference.
Weaknesses
1) Neither the ideas nor the analysis are particularly inventive in my opinion. It's self evident that optimizing the second factor after quantizing the first (LSVD) is superior to independent quantization (DSVD), in fact the process could be iterated further. While I appreciate the 30+ pages of proofs provided by the authors it seems as if they rely on chaining known results and techniques for sketching and random matrices combining with patient algebra. 2) Despite its seemingly weaker theoretical bounds LSVD is always one of the most accurate method in the experiments (see Tables 4-7). This is also clearly highlighted by the authors in the limitations section. 3) Quantization aware training (not considered in the paper) is highly likely to produce equivalent or better results.
Questions
1) Line 226 and Theorem 3.2: For (1+eps') relative Frobenius error approximation LPLR requires m=O(k/eps') >> k columns, which the text seems to overlook. Could you please discuss? 2) Table 3: Could you also add LSVD to this experiment too? DSVD's Frobenius error is always the same 0.496, and LPLR's error is the same the bottom of the table, when the bit budget is doubled, as in the top of the table. Could you discuss why? What was the rank (k) of DVSD, was it the same as m of LPLR? I.e. could you make Rank column header precise? 3) Matrix entries are typically rescaled to [0,1] before quantization as it's cheap to store their min/max (or some very low/high quantiles), even for each row (or column) of a matrix. How would such rescaling change your theoretical and empirical results? 4) Line 77: Sx -> x 5) Table 1, row of LPLR: delta is undefined 6) Lines 219-222: missing log2(), 4 times
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes, limitation section is adequate.
Summary
The paper studies compression of low-rank matrices by simultaneous low-rank factorization and quantization. It proposes a method that first quantizes the randomized rangefinder as the first low-rank factor and then quantize the minimizer of reconstruction error with respect to the remaining factor as the second. Randomized rangefinder uses random Gaussian matrix which possesses the equalization property to maintain low quantization error, compared to naïve quant. Experiments are provided to demonstrate the benefits of the proposed algorithm.
Strengths
1. provide a low rank factorization algorithm that come with quantization for further reducing memory footprint. 2. experiments demonstrate the advantage of the algorithm.
Weaknesses
1. experimental settings should be made clearer. the current description is a bit confusing.
Questions
1. what is the difference between LPLR and LPLR-SVD in experiments? 2. Accuracy seems to decrease with bits for some cases in experiments. Why?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
No limitations are addressed in the paper.
Summary
The paper proposed a memory efficient approach to approximate a matrix $A$ by: low-rank approximation $A=LR$ and quantization. The LPLR algorithm first applies a quantized random projection (RP) as the $L$, and then solve a minimization problem for the right loew-rank factor $R$, which is also quantized afterwards. Theoretical approximation error is obtained and compared with an alternative approach that quantized SVD low rank factors instead of RP. Experiments are conducted on image approximation and embedding classification, to show the effectiveness of the proposed method.
Strengths
1. The paper is well-organized and easy to follow. The theoretical analysis seems rigorous. 2. Experiments on multiple ML tasks and datasets are provided which make the results more grounded.
Weaknesses
In my understanding, the main idea of the paper is to waive the need to compute the SVD of A, by using random projection (RP) as a surrogate. I have the following concerns and suggestions: 1. At line 220, the authors wrote that the bits per entry for SVD-quant is $O(nd\sqrt k)$, but in Table 1 and Table 2, it is $O(k\sqrt{nd})$. Please double check and clarify. Also, the authors simply stated that LPLR is better than SVD-quant in terms of bits per query, which is not true with some n, d, m, k (comparing the results in the table). I suggest the authors to carefully compare the results and state the regimes when LPLR is better, and when it is worse. 2. In the main Theorem 3.2, $\kappa$ could be negative, right? Is $1-c_4\sigma_k/\sigma_{k-1}$ bounded? Or do we need to further assume an eigen gap for this result to hold? 3. I understand that the main usage of LPLR is for matrix (data) approximation, so the first experiments (Figure 1 and Table 3) make sense to me. However, for the second set of experiments on classification, why not directly using $Q(AS)$ (i.e., the quantized random projections)? This saves the storage for W (in other words, we may increase the sketch size m when using Q(AS) only). Some recent references on this include Random projections with asymmetric quantization, Li and Li NeurIPS 2019 Generalization error analysis of quantized compressive learning, Li and Li, NeurIPS 2019 Indeed, the research on QRP is highly related to this submission, since LPLR essentially does an optimization on W to recover the data from QRP. I suggest to add some discussion on this direction in the paper and some empirical comparisons. 4. Also, if LPLR is used for processing or storing the data for classification or search tasks, it might be inconvenient to handle new data points (e.g., in a streaming setting). Thus, it may not be suitable for such tasks. On the other hand, recently people are using low rank approximation in LLM fine-tuning frequently. Experiments related to fine-tuning language models could be a better application scenario for the proposed method. 5. Some references on similar results are missing. A similar result as in Appendix D that $S^TQ(AS)$ with uniform quantization has approximation error independent of $d$ has been established in [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning, Vargaftik et al., ICML 2022] (or maybe some even earlier paper) for rotation matrix $S$. This related result should be cited. Also, Eq. (2) is a standard result for uniform stochastic rounding. A reference should be added there. In all, I think the paper proposes a simple but intuitive method for low-rank low-precision matrix approximation from QRPs. The idea is clear, the analysis seems sufficient (despite the above and below questions).The experiments can be improved, but the current results on several tasks and datasets are convincing enough to show the effectiveness of LPLR in matrix approximation. For now, I would recommand borderline accept.
Questions
1. Proposition D.1 only bounds the error between $Q(Sx)$ and $Sx$. How does it imply $||S^TQ(Sx)-x||^2$ is also a constant? 2. What solver is used to solve Algorithm 1 line 4? This should be clarified. Is closed-form feasible?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
NA.
Summary
The paper studies the low-rank factorization of the matrix in the low-precision setting and proposes a new algorithm which is a combination of randomized low-rank approximation method and quantization. The paper formally analyzes the guarantee of the proposed algorithms and also give experiments on real world dataset which demonstrate the advantage of the proposed algorithm.
Strengths
1. The presentation of the paper is good. The writing of the paper is clear and easy to follow. 2. To get the formal guarantee, the authors do a careful analysis, which I think is non-trivial.
Weaknesses
1. Technical novelty: the main algorithm (Algorithm 1) seems to just be the standard way in randomized numerical linear algebra then plusing the quantization. Can you authors give more explanations about the technical novelty? (though the analysis I think is not standard) 2. Experiment: I have some questions about the setting and details of the experiments section. See the next question.
Questions
1. Theorem 3.2 shows the guarantee of the proposed algorithms. However, would the sketch size $m$ also have the requirement given the accuracy parameter $\epsilon$ and $k$? Also in experiment it may be a factor that affects the runtime and accuracy a lot, is there some place indicating the choice of $m$? 2. I am a little confused about the naive quantization baseline. Can this way make the matrix be low-rank? 3. As mentioned in the paper, the sketching-based method is popular in randomized low-rank approximation. I think in the experiment the baselines should also include it (with the naive way of quantization). 4. The paper discusses the runtime complexity. Hence, I think it would be better to include the runtime in the experiment section.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
See the above questions.
Summary
The paper introduces a low rank, quantized/low precision matrix factorization which decomposes an n x d matrix A in the form A= LR, where L (of size n x m) and R (of size m x d) are low rank factors. L and R are computed using a random projection matrix S in the form L = Q(AS) and R = Q'(W^*) where W^* is the matrix minimizing the squared Frobenius norm ||Q(AS)W− A||. Q and Q' are two independent quantizers with specified budgets. The authors contrast their method with an SVD based method for computing the quantized low rank approximation which instead sets L = Q(U_k S_k) and R = Q'(V_k), where U_k/V_k and S_k are the singular vectors/values respectively. The paper has a theorem deriving a bound on the Frobenious norm of the factorization eror. They apply the approximation on image data (for image compression) and embedding matrices (for an embedding classifation task).
Strengths
+ The paper is very well written and very clear in its presentation + Clear technical presentation incl. theorems, algorithms etc. + Novel idea, providing good review of relevant literature (different matrix sketching approaches, quantization etc.) + Thoughtful experiments to demonstrate real world application (using embedding compression)
Weaknesses
I don't see any weaknesses that need to be addressed at this moment.
Questions
* In Table 3, why are the SVD and Naive quant. Frobenious norm errors the same for different rank choice? Is it because the matrices are really low (<15) rank? * I think Table 3 may be expanded to a set of figures to better convey the message (with potentially more bit budgets).
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
This is an optimization paper and as such the limitations are not immediately obvious, though the eventual use of the model for downstream compression/computation speed up could be quite broad. The societal impact could also be positive given the matrix compression can lead to compute/energy savings. The paper doesn't have a dedicated discussion/section on any limitations.
Thanks for the reply
Thanks for the reply. I still have some follow-up questions: 1. I don't get why LPLR needs less computations. $Q(AS)$ has the same size as $L$, and $Q(S^Tx)$ has the same size as $Rx$, right? 2. Thanks for clarifying. Please add this analytic comparison to the paper and update the theorem statement. 3. Can we extend the method in the mentioned SIAM paper to LPLR to handle the streaming data setting? If so, I suggest adding some discussion and describing the general ideas. If not, it should be mentioned in the limitation section that LPLR should be used for fix/static data. 4. Prop. D.1: so the reconstruction error $||S^TQ(Sx)-x||^2$ is actually not $O(1)$ but is $d/m$ which increases with $d$?
Clarifications to follow-up questions
Dear Reviewer, Thank you once again for your thorough review, which really helped improve the clarity of our paper. Below, we have attended to your follow-up concerns: > Why LPLR needs less computations. We apologize for the confusion. Computing $Q(AS)Q(S^Tx)$ requires $nm$ multiplications (not $nmd$), which is the same as LPLR. You are correct -- we agree that the computation speedup of LPLR is not due to reduced number of multiplications. Nevertheless, in Li \& Li, the sketching matrix $S$ needs to be stored in full-precision (FP) for computing $S^Tx$ for any incoming $x$. Contrary to this, LPLR requires computation of $Q(W)x$, where $Q(W)$ consists of $md$ quantized values, which can leverage modern advancements in hardware primitives for speeding up low-precision computations (eg., half and mixed-precision compute). Thank you for bringing our attention to this. > Please add this analytic comparison to the paper and update the theorem statement. Thank you for acknowledging. We will make the necessary edits to the paper. > Can we extend the method in the mentioned SIAM paper to LPLR to handle the streaming data setting? If so, I suggest adding some discussion and describing the general ideas. An outline of how LPLR can be extended to the streaming setting is as follows: Suppose we have a matrix $A_n \in \mathbb{R}^{n \times d}$ with $n$ datapoints, for which we store the sketching matrix $S \in \mathbb{R}^{d \times m}$, the left factor $(L_n)$, and the right factor $(R_n)$. For an incoming datapoint $a_{n+1}$, we can simply update the left factor as: $L_{n+1} \gets [L_n; Q(a_{n+1}S)]$, where $;$ denotes the concatenation of an additional row. The second low-rank factor, which is $R_{n+1} = argmin_W\lVert L_{n+1}W - A_{n+1}\rVert_F$, can be computed from $R_n$ in a fashion similar to online least squares, which uses Woodbury matrix inversion lemma. Thank you once again for highlighting this setting. This is a very interesting observation and we will add a discussion regarding this to the main paper. > Prop. D.1: so the reconstruction error $\lVert S^\top Q(Sx) - x \rVert^2$ is actually not $O(1)$ but is $d/m$ which increases with $d$? Yes, the reconstruction error $\lVert S^TQ(Sx) - x\rVert^2$ scales as $d/m$. But it does not necessarily increase with $d$ if we choose the sketch size $m$ to be proportional to $d$, i.e., $m = O(d)$. In that case, $d/m$ will be $O(1)$. We are grateful for your careful scrutiny. We will add the above discussion to the paper, and mention that the reconstruction error $\lVert S^\top Q(Sx) - x \rVert^2$ does not grow with dimension as long as the sketch size $m$ is proportional to the dimension $d$.
Thanks for the quick response. 1. Thanks for clarification. Since QRP is just the left component in LPLR, comparing LPLR and QRP could better demonstrate the benefit brought by the extra optimization problem (3). Anyway, we can say that LPLR targets on a different task of data approximation, so not having such empirical results is OK to me. Please cite the QRP related papers and discuss their connections in the revision. 2. In the "online" procedure you described, you need the entire data matrix $A_{n+1}$ to do the optimization. However, the original data should have been discarded since the whole motivation about this work is that $A$ is too large to store. I'm not against this, since many of these type of optimization-based algorithms do not handle online data very well. My suggestion is to discuss this setting a bit to at least let the readers know the best application scenario of LPLR, because streaming data is indeed an important case in practice. 3. Thanks for confirming that the error is in fact not a constant but $d/m$. In the paper you mentioned $m\ll d$ to achieve good compression, so I think this error should be regarded as linear in $d$. I was particularly curious about this claim since prior work showed constant approximation error with $d\times d$ rotation matrix. This matrix is much "stronger" than low-rank random projection matrix. Now the $d/m$ error seems more intuitive and reasonable. There might also be a connection with their result when $m=d$, which could be interesting to the researchers. Anyway, please add the proof and revise the description of this result in the revision. In summary, thanks for answering my questions. Please update the paper according to our discussions. This revision would improve the quality of the paper. Based on this, I will raise my score to 6.
Acknowledgement of discussion
Dear Reviewer z4CA, Thank you for engaging in discussions and increasing your score. We commit to citing the QRP papers to provide a more comprehensive context for our nearest neighbor simulations. We agree with your suggestion regarding the extension of LPLR to an online setting. We believe that it is possible to design an approximate online version for which storing a sketch of the matrix $A$ suffices, i.e., $R_{n+1} = argmin_W\lVert L_{n+1}W - A_{n+1} \rVert_F$ can be obtained in terms of $R_n = argmin_W\lVert L_nW - A_n \rVert_F$, without having to store $A_n$ or $A_{n+1}$. This hinges on appropriately capturing the delta from $A_n$ to $A_{n+1}$. We refrain from delving into details since this is not what we study in our work. Nevertheless, we agree that this is an interesting future research direction and we will add a pertinent discussion in our paper. Regarding point 3, we will clarify the result to be explicit about the $d/m$ dependence. We agree that there may be a connection with their result, which is worthy of exploration in future work. We are grateful for your incisive review of our work, and will incorporate the outcome of this discourse into our revision.
Thank you for the responses!
The authors' responses are very helpful in understanding this work. As indicated in my original review, I regard this work highly, and the authors' responses help to increase my confidence in this assessment. I encourage the authors to mention the comment about the most time-consuming step in this procedure in the main text, I find this valuable. I would also appreciate if you mention that naive rounding does not make a difference in practice, I imagine this is much more convenient for practitioners.
Thank you
Dear Reviewer, Thank you once again for reading our work, and for providing a thoughtful and constructive feedback. We are happy that our responses have helped clarify your concerns. We will definitely include a mention of the most time-consuming step in the main text, along with emphasizing that naive rounding does not make a difference in practice. If you have any further comments or questions, please do not hesitate to reach out.
Thanks for the reply. I still have the follow-up question: 1. As mentioned by the authors, naive quantization does not make the matrix low-rank. However, if the bit-budget is the same, why the LPLR has a better error than naive quantization in Table 3. In that case, would naive quantization get the optimal error in this setting?
Response to follow-up question
Thank you for your question. To clarify your concern, allow us to revisit the relationship of LPLR with its antecedents for compressing models, namely Direct SVD (which reduces the total number of parameters by leveraging low-rankness) and Naive quant (which reduces the number of bits used to represent each parameter). The efficacy of LPLR relies on finding a harmonious equilibrium between these two key factors. In Table 3, we do not impose prior expectations on the performance of any particular algorithm. For instance, we don't possess any prior knowledge of the optimal target rank. However, given our analytical demonstration that there exists a regime (a combination of target rank and bit budget *per parameter*) where LPLR can surpass its baselines, we highlight this scenario (extreme model compression) in the *revised* Table 3, which corresponds to what is now Table 1 of the global response pdf. Naive Quant is indeed capable of outperforming LPLR/DSVD/LSVD (and does so) where significant model compression is not a requirement. This can be observed in rows $1$ to $4$ of the second sub-table in the global pdf. We hope this clarifies your query. In what follows, we further elaborate this. Let's consider compressing $A \in \mathbb{R}^{n \times d}$. If we choose our target rank (essentially, the sketch size) to be $k$, leading to an approximation of $A \approx LR$, where $L \in \mathbb{R}^{n \times k}$ and $R \in \mathbb{R}^{k \times d}$, the total parameter count in $L$ and $R$ becomes $k(n + d)$, instead of the original $nd$ parameters in $A$. If we employ naive quant., which directly quantizes each element of $A$ without capitalizing on any low-rank structure, the total number of bits utilized amounts to $ndB_{nq}$, where $B_{nq}$ denotes the number of bits assigned for quantizing each entry. On the other hand, in the case of LPLR/DSVD/LSVD, where $k(n + d)$ parameters are quantized, the overall bit consumption equals $k(n + d)B$, where $B$ represents, once again, the bit allocation per entry (potentially distinct from $B_{nq}$). In Table 3, a fair comparison is upheld by ensuring that each algorithm receives an equal allocation of resources—specifically, they utilize the same total number of bits. This similarity in resource allocation serves as the basis for evaluating their effectiveness in judiciously allocating the bits to maintain performance. In Table 3, the relevant columns, namely $B$ and $B_{\rm nq}$, correspond to LPLR/DSVD/LSVD and naive quantization, respectively. However, it is important to emphasize that we guarantee that the expression $$ \text{Total Bit Budget} = \text{Number of parameters} \times \text{Bit budget per parameter} = k(n+d)B = ndB_{nq}$$ remains consistent **across all algorithms**. For matrices that can be effectively approximated by low-rank methods, $\lVert A_k - A \rVert_F$ (where $A_k$ is the best rank-$k$ approximation) is small for some $k \ll {\rm min}(n,d)$. For such matrices, there's room to allow $B$ to exceed $B_{nq}$. This flexibility permits us to employ more bits per parameter while maintaining the same total bit count. The choice of hyperparameter $k$ plays a pivotal role in navigating the trade-off between the error stemming from low-rank approximation and the error resulting from quantization due to precision limitations. A smaller value of $k$ translates to a higher number of bits per parameter, leading to reduced quantization error. Conversely, a larger value of $k$ diminishes low-rank approximation error, but results in fewer bits per parameter, subsequently increasing the quantization error. **Matrices inherently characterized by low-rank traits allow for a substantially smaller $k$ value to be chosen, and within this context, LPLR exhibits superior performance compared to naive quantization.** If any concern still remains, please don't hesitate to ask for further clarification.
Further Clarifications
Dear Reviewer DCJv, Please let us know if your query about the comparative advantage of LPLR and naive has been addressed satisfactorily. We hope that our response has positively influenced your perception of our work. If you require further clarifications to potentially reconsider your score, we are enthusiastic about engaging in further discussion. We highly value the generous contribution of your time to review our paper.
Thanks for the detailed response. I think some parts of the response will make the main body of the paper more clear. I will raise my score to 5.
Thanks for your response.
Thank you for the detailed response. It addresses my concerns and questions and it's great that you caught and addressed the bug that caused the steady errors across parameters.
Thanks for the detailed reply and explanation. I'll revise my final review upwards accordingly. If you happen to read this comment in time: re: "references [16] and [74]" - these are quantization papers, could you double check? re: QAT: I meant learning factors $L$ and $R$ directly with gradient descent in the quantized bottleneck layer of the form $Q(L)\cdot Q(R)$ replacing $A$, where $Q$ denotes quantization as before.
Response
Dear reviewer, Thank you for your response. We are glad that you found our rebuttal convincing and are grateful for your willingness to revise your review upwards. To answer your remaining questions: 1. Sincere apologies for the confusion -- we meant references [16] and [74] of our supplementary material, which includes references from the main paper as well as the appendix. The specific papers we pointed out to are: P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. SIAM Journal on Computing, 36(1):158–183, 2006. R. Witten and E. Candès. Randomized algorithms for low-rank matrix factorizations: Sharp performance bounds. Algorithmica, 72(1):264–281, may 2015 2. QAT: Thank you for clarifying this. Yes, it is likely that QAT can decrease the approximation error further, but as we mention in our rebuttal, this comes at the cost of additional computation (which can potentially be prohibitive for compressing large data matrices).
Decision
Accept (poster)