Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper gives improved bounds for estimating the trace of a matrix using matrix-vector products. It turns what was previous a multiplicative factor of log(1 / failure probability) into an additive one, and shows that this bound is tight up to a loglog factor. These methods are evaluated on a wide range of matrices, several of which are implicitly represented (via the Lanczos method), and a better success probability was observed.
main_review: I believe this is a solid result: trace estimators have been well studied, and the dependence on success probability is a nature parameter for analyzing algorithmic performances. The paper essentially closes off this dependence issue by showing that a additive log(1 / failure probability) is sufficient, and also necessary up to a loglog factor. They also empirically demonstrate this improvement by showing the failure probability of this method versus previous, and raises some interesting questions about better parallel performances of such estimators.

The importance of trace estimators across numerical/ML algorithms make this paper a clear accept. On the other hand, I feel the experiments demonstrate these gains are rather limited, and occur in performance only when parallelism is brought in. However, I believe they provide natural directions to extend some of the primitives developed here, and the evidences provided in the responses indicate that significantly more can be done on this front.
limitations_and_societal_impact: My impression is that failure probability are usually an artifact of the analysis. Outer loops that utilize these trace estimators are often ok with some randomized noise in the answer, and I feel empirical results (in either positive or negative directions) on this would be interesting.

Also, the performance gains of these methods shown in Fig 1 seems to be around 1.5x, which to me feels rather marginal. It might take more end-to-end experiments to demonstrate more pronounced gains of these methods. I'm very happy that the authors took time to provide additional empirical evaluations in their responses, and am now quite interested in running my own experiments on this topic.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper contains two main contributions. First, they provided an improved analysis on the NA-Hutch++ algorithm to bridge the gap between adaptive and non-adaptive algorithm. Secondly, they also provided a nearly matching lower-bound on the complexity of the problem, closing the gap.
main_review: I acknowledge that I am not an expert on this particular problem.Closing the complexity gap is usually a significant contribution to any problem, which indicates that improvement should be sought elsewhere. Therefore, I believe the authors have made significant contribution to the trace estimation problem where we only have access to a linear projection oracle. 

The paper is well-written. Even if I did not read the proof details, the authors have kindly provided intuitions and key idea behind the proof. 

My only concern is that the problem and the application itself might still not be close enough to make direct impact on real world applications, but the theoretical advances should interest the audience. 

update: thanks for the comment
limitations_and_societal_impact: Based on my limited knowledge, I believe that it is meaningful in some applications to break down the $1\pm\epsilon$-multiplicative bound into an upper bound and lower bound. I am wondering if some of the results can be refined for these error bound or whether they are nearly the same.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an improved analysis for Hutch++, a stochastic trace estimation method proposed recently. In particular, the paper presents a new analysis for the non-adaptive variant of the Hutch++ algorithm and show that even the non-adaptive algorithm achieves optimal dependency on the failure probability \delta (i.e., O(\sqrt{\log(1/\delta)}))for the number of samples/matvecs. The paper also presents an improved lower bound for the number of matrix-vector queries required in terms of \delta and error tolerance \epsilon. Some numerical results are also presented to illustrate the performance of the methods.
main_review: The paper presents a new analysis for the Hutch++ method that improves the non-adaptive query complexity of the algorithm. It also presents an improved lower bound for the number of matrix-vector queries required. These results are certainly interesting from theoretical analysis (TCS) perspective. The numerical results presented and the python implementation with parallel processing will be useful for practitioners. 

However, I have the following comments about the paper: 

1. Novelty is limited: The main concern about the paper is that the work is very incremental and novelty seems limited. The main algorithms of Hutch++ and much of the analysis have already appeared in reference [16]. The proof of the main theorem 3.1 largely depends on the results in [16] (Although, I have not gone over the proof that is in the supplement in details). The theoretical improvement is really just a \sqrt{\log} factor wrt. failure probability, and does not have any implications on the actual usage and implementation of the algorithm. The lower bound analysis wrt. \delta is novel, but it is not too far from the lower bounds presented in [16] (analysis approach also appears to be similar to [16]). 

Therefore, it is not very clear that the publication of this paper in an AI/ML conference is warranted. To my understanding, this paper is  more suitable for Theoretical Computer Science (TCS) or Numerical Linear Algebra (NLA) venue. 

2. Minor comment:
I suggest changing the title of the paper since it is almost identical to the Hutch++ paper. 

--------------------------
After Author response:

I thank the authors for their response to reviewers' comments and for clarifying things. 
One thing I should clarify, which was perhaps confusing, is the comment "much of the analysis has already appeared in [16]", where I was referring to the type of analysis presented, i.e., the multiplicative error bounds and lower bound analysis results that are also developed in [16]. The proof of Theorem 3.1 in this paper does follow the low rank approximation route (similar to [16] and uses the result on splitting the trace estimation), since the algorithm uses sketching to capture the top k singular values (and subspace). This is by design and the method was perhaps designed to leverage the sketching results. To my understanding, the algorithmic advancement was mainly this, using sketching to approximate the top singular values, and then using deflation and applying the stochastic trace estimator on the deflated matrix to capture the remaining part of the spectrum. This key idea has appeared in [16]. 
However, the novelty in this paper seems to be the new analysis of the sketched low rank approximation (I am not sure if there are changes to the algorithm itself, I request the authors to clarify). This analysis could be of independent interest, which I agree with the authors. Maybe authors can highlight this more and center some of the discussions around this point. Authors can add bullet points in 1.1 to highlight and discuss the key differences between [16] and this paper.

Overall, I agree with other reviewers that the theoretical results are strong. I am happy if the paper is accepted, since the theoretical results might be for interest for other RandNLA problems, including low rank approximation, spectral sums tr(f(A), etc.
But, I am still not convinced entirely that the results are of interest to broad AI readers and practitioners, since the main algorithmic advances have already appeared in [16], and the theoretical improvement of sqrt log factor wrt. to the success probability will likely have no practical consequence when the method is applied to the AI applications listed by the authors. Hence I am increasing the score to 6: Marginally above the acceptance threshold.
limitations_and_societal_impact: There does not seem to be a discussion on the limitations and potential negative societal impact of their work in the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of estimating the trace of an input PSD matrix with the perspective of improving the query complexity of matrix-vector products required to compute an eps-multiplicative approximation of the trace. There have been two types of randomized algorithms solving this problem: adaptive and non-adaptive.

The former uses samples that depend on previous ones and therefore, by definition, is sequential. The latter doesn't, and is therefore amenable to parallelization, clearly a useful/desirable feature to have. 

However, the prior lowest query complexity results for adaptive algorithms were lower than those for non-adaptive algorithms, by a factor of sqrt(log(1/delta)), where delta is the error probability. This paper focuses on non-adaptive algorithms for trace estimation of PSD matrices. Within the framework of this problem, it has two key contributions. 

1. The first is an improved analysis of a non-adaptive algorithm proposed in a previous paper. The analysis is an improvement in the sense that it is able to show that this non-adaptive algorithm in fact needs just as many queries as the best adaptive algorithm, thus shaving off a factor of sqrt(log(1/delta)) from the prior analysis. 

2. The second contribution is a proof that the new result obtained is in fact optimal, thereby completely resolving the question of non-adaptive query complexity of matrix-vector products for trace estimation of PSD matrices. 

In the process of 1., the paper also provides the following technical contribution: a proof that to estimate the k-rank approximation of a PSD matrix with probability 1-delta, it suffices to use O(k + log(1/delta)) queries, down from the previous best query complexity of O(k log (1/delta)). The paper explains how, to achieve k-rank approximation, one needs matrices that satisfy two properties: (1) a subspace embedding property, and (2) a property about orthogonal matrix products. While property (1) was satisfiable by the improved query complexity before, it wasn't known that (2) was. This paper shows, by carefully arguing about tail bounds of chi-squared distributed variables, that (2) is also in fact true for O(k + log(1/delta)) queries. 
main_review: REVIEW: This is a very strong paper. Both the main technical contributions (listed in the previous field) are strong in their own right: one, giving an improved analysis of an existing algorithm, and second, showing that this is the best possible query complexity for this problem, thereby effectively closing this specific problem. Further, the k-rank approximation using O(k + log(1/delta)) queries is also an improvement of a problem so fundamental, it's taught in week 4 of an introductory machine learning class. Clearly, this paper scores highly on significance and originality. 

The paper scores average on clarity: some parts of it are great! I particularly liked the succinct description of the main technical idea in lines 55-60 and of the technical contribution from lines 108 - 111. However,  ​I have some specific parts of the introduction I'd love to see re-written or explained better. 

1. The paper's opening paragraph (lines 20-26) gives a laundry list of applications that invoke trace estimation as a subroutine. However,  it's quite difficult to actually read five other papers to see *how* this routine actually shows up there. So, I feel the authors should "open up" at least one (maybe the most impactful) of these applications (in just a couple of sentences) and describe the exact use of trace estimation therein. Though I don't need convincing that trace estimation is important, I am curious to see exactly where it's applicable. 

2. Given that the paper measures efficiency in terms of number of queries to matrix-vector products, the authors should explain at the very outset (paragraph 2: lines 27-33) *what* is the exact connection between trace estimation and matrix-vector products.  

To  summarize, I enjoyed the technical contributions and think that the problem is well-motivated. However, I think explaining the fundamental assumptions and claimed applications of your work is critical  to making the paper accessible to people who may not have done research on this topic before. 

I currently rate this paper 7/10 (GOOD PAPER, ACCEPT). However, I will happily give this  paper a  CLEAR ACCEPT (SCORE 8) , CONDITIONED ON the authors addressing points 1 and 2 above. I look forward to reading the authors' response. 

limitations_and_societal_impact: None, as far as I can tell.
review_title: null

Meta-review: This paper considers the fundamental problem of estimating the trace of a PSD matrix from matrix vector product queries. Prior results had a gap between the adaptive and non-adaptive versions of the problem. In this paper, the authors propose a non-adaptive algorithm with nearly the same performance as the best adaptive algorithm. The paper also makes nice contributions in establishing lower bounds on the number of queries. The reviewers all felt that this paper should be published in NeuRIPS. 
Decision: Accept (Spotlight)