- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the query complexity of testing whether a low-rank matrix approximation is good using matrix-vector products. For a single approximation, the paper shows that queries are necessary and sufficient, even when queries are chosen adaptively. The paper also considers algorithms that gradually increase the approximation rank and repeatedly check whether the desired accuracy has been reached. The authors show that when the approximation sequence is constructed independently of the validation queries, matrix-vector products suffice to make all required decisions correctly with probability at least . More generally, for such sequences, they prove a tight query bound of . This improves the bound obtained by a naive union bound. Finally, the paper give numerical evaluation on synthetic data to support their theoretical results.
Critical strengths
- The technical contribution of this paper is solid. For a single matrix, the paper gives tight query bounds, which also hold for adaptive queries. For multiple approximation matrices, the authors improve the query bound from a dependence to and also prove a matching lower bound.
- The paper also gives an empirical study for their theory analysis, which is also interesting to me.
Critical weaknesses
- I feel like the presentation of this paper is hard to follow and can be improved significantly, especially in the abstract and introduction. For example, the "nested paths" and "W paths" are introduced without explaining what they mean, and the meanning of "exact dimension-uniform minimax query constant" is also unclear at a first look. I suggest the authors substantially revise the abstract and introduction to make the paper more accessible. In particular, they should clearly explain the different models considered in this paper and the corresponding result.
Questions for authors
See the above question.
3 comments
Thanks to the authors for the detailed response. I read the revised version and think the new abstract and introduction are much better now. I have raised my score to 3, and I think it would be great if the authors could further polish the presentation throughout the paper in the next version.
Dear Reviewer,
Thank you very much for your positive feedback, for re-evaluating our work, and for raising your score to 3. We are extremely glad that the revisions to our abstract and introduction met your expectations.
We highly appreciate your constructive suggestion to further polish the presentation. Thank you again for your invaluable guidance and support for our work.
Best regards,
The Authors
Improved Presentation and Clarification of Key Concepts
Thank you for this helpful suggestion. Revisions primarily addressing your comments are highlighted in blue. We have substantially rewritten the abstract, introduction, and Related Work, and checked and revised the presentation throughout the remaining sections.
The abstract and introduction now organize the paper around three questions: how to certify a single approximation, when validation can be reused across multiple candidates, and how certification affects stopping in iterative approximation. For each question, we introduce the setting before stating the corresponding result and its scope.
We have strengthened the explanations of the specific concepts raised in your review:
We also clarify the information model in Section 3.1, distinguishing additional validation queries in the upper bounds from all available operator observations in the lower bounds, and explicitly state the independence requirement for shared validation in Section 4.
Related Work has been rewritten to explain how the relevant ideas developed and where our contribution fits, rather than presenting separate summaries of individual papers. Across the remaining sections, we have supplemented previously abbreviated explanations, clarified assumptions and notation, and improved transitions between definitions, results, and their interpretation.
Thanks again for your time and valuable suggestion. We hope this revision can address your concern and make this paper more clear.