Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors in this paper study the problem of estimating the trace of a matrix that is changing dynamically over several iterations. Under the assumption that the diagonal entries of the matrix are not directly accessible, but multiplication with a vector $Av$ (or the quadratic form $v^{\top}Av$), the Hutchinston estimator is the baseline algorithm for comparison. The Hutchinston estimator takes the average of $\epsilon^{-2} \log 1/\delta,$ estimates $g_i^{\top} A g_i$ where $g_i$ is a random vector with iid gaussian variables, or Rademacher ($\pm 1$) variables, and is correct with probability $1-\delta.$

The model is that we have a sequence of matrices $A_1, \ldots, A_m$ each with $\|| A_i \|| \le 1$ and $\||A_{i+1} - A_{i} \|| \le \alpha,$ (where the matrix norm used is the Frobenius norm) and we wish to output estimates of $tr(A_1),\ldots,tr(A_m)$ such that each estimate is accurate to $\pm \epsilon.$ Using a Hutchinston estimator at each iteration will require $m \epsilon^{-2} \log m/\delta$  where all the answers are accurate with probability $1-\delta.$

The paper presents an algorithm that is able to maintain accurate estimates for such a dynamically changing $A$ using only $(m \alpha + 1 )\epsilon^{-2} \log m/\delta,$ which is essentially better by a factor of $\alpha.$ The authors also show a lower bound claiming to show that this method cannot be improved unless the original Hutchinston method is improved.

The algorithms extend their algorithm to the case where you have a stronger nuclear norm bound assumption, and present numerical simulations demonstrating their advantages.
main_review: I think this is a nice algorithm based on a clean and simple idea that could lead to direct gains in some settings, e.g. estimating the trace of the hessian while training a neural network. The key idea is to maintain a trace estimate of a moving (exponentially) weighted average of the matrices, and to estimate the trace of the difference at each step using the Hutchinston estimator.

A few comments:
1. A nicer baseline to compare against is a Hutchinston estimator that is restarted every $1/\alpha$ iterations.
2. The lower bound is weaker than the claim that "this method is the best possible". The lower bound only shows that using the case $\alpha \approx 1/m,$ this problem recovers the original estimation problem for hutchinston estimator. It does not rule out running time bounds such as $m + \sqrt{m \alpha} \epsilon^{-2} \log m/\delta.$
3. I think your algorithm can also work in the weaker model where we only have access to the quadratic forms. I think that's the usual model for the Hutchinston estimator too.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies dynamic setting of trace estimation problem; compute the trace of a sequence of matrices efficiently. The authors consider the differences of consecutive matrices are small and utilize the linearity of trace and Hutchinson estimator, which returns trace values with only matrix-vector multiplications. In addition, in order to reduce the variance of trace estimations, they adopt a damping strategy; it controls the scale of the input matrix to estimate and reduces its variance appropriately. They propose a closed form of the optimal damping factor. Experimental results show the superiority of the proposed algorithm with various problems of trace estimation under both synthetic and real-world datasets.
main_review: This work proposes an efficient method for the dynamic trace estimation problem by utilizing well-known Hutchinson trace estimation and variance reduction technique (aka control variate). The problem is quite fundamental so that it can be applied to various of practical tasks, e.g., triangle counting, Hessian spectral density estimation and so on. The idea of Hutchinson estimator and variance reduction is not new and widely used in many problems involving computational issues, but the authors analyze with concrete theoretical results. 

I think that dynamic trace estimation is somewhat related to greedy algorithm of the determinant maximization problem (aka MAP inference of Determinantal Point Processes). Indeed, [1] tried to dynamically estimate log-determinant (polynomial version of Hutchinson estimator) and analyzed the variance of two distinct Hutchinson estimations when randomness is shared (see Theorem 2 in [1]). More generally, it seems that the proposed method can combine with a polynomial to extend to more various essential problems.

[1] Han, Insu, et al. "Faster greedy MAP inference for determinantal point processes." ICML, 2017.

limitations_and_societal_impact: The paper is quite well-written and easy to understand. But, it would be good to highlight concrete applications that I provide in the experiment section. Also, I suggest providing some details of technical terms (e.g., Hanson-Wright inequality in line 127) for non-expert readers.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors proposed a method for estimating the trace for a sequence of matrices that only changes for a small amount at each step. The method originates from the well-known stochastic trace estimator, but bring it to a new practical setting (e.g. Hessian at learning iterations, evolving network, etc). By an interesting treatment of the iterative process (i.e. damping), the resulting algorithm could cut the computational cost by a factor of the size of the tolerable error. In addition, the authors included the recent development/improvement on the original Hutchinson estimator, to get better versions of their algorithm under more assumptions.
main_review: Please address this and correct me if I'm wrong, in the inequality between line 175 and 176, $(1-\alpha)^2\delta\epsilon^2+4\alpha/\ell\to\frac{3}{2}\delta\epsilon^2$ as $\alpha\to 0$. Thus the inequality doesn't seem to hold here.

Originality: I think the work is novel and this dynamic setting is probably never looked at before. The work builds on top of the well-known Hutchinson estimator, but the main contribution has great ideas that are totally independent from previous work. The paper also has good reference and sourced all the relevant work.

Quality: The paper is technically sound for the most part, but please respond about my question at the top. Nonetheless the experiment results are promising and shows the algorithm works well in practice.

Clarity: The paper is well-written and easy to follow. The list of reference is good. One thing bothers me a little is that the authors claimed in multiple places that $tr(\Delta_j)$ is easier to estimate and we can we can approximate $tr(\Delta_j)$ more accurately than $tr(A_j)$. While I get authors' point in the context of this problem, the statement on its own isn't very accurate because we usually look at relative error in this kind of estimations, and $tr(\Delta_j)$ isn't obviously easier in that sense.

Significance: I think the work is important and have many applications as suggested by authors' experiments. While I'm not sure about how much scalability problem we have in practice given the efficiency of the original estimator, the proposed work makes clear improvements. 

Other comment: While damping seems a great idea in general, the authors also mentioned that sometimes $\Delta_j$ can have special properties (e.g. low-rank, diagonally concentrated after reordering, etc). In this case, the damping would destroy those structures. 

limitations_and_societal_impact: There is no negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work considers the problem of dynamic trace estimation. Specifically, if there is a sequence of matrices $A_1, \dots, A_n$, and the norm of $A_i - A_{i-1}$ is small relative to the norm of $A_i$, we can estimate the trace of each matrix efficiently. The paper gives an efficient algorithm, the convergence analysis and conducts relavant experiments.

main_review: The paper is well-organized and I don't see any major flaws in the proofs. The idea of damped variance reduction is quite good. But I worry that setting of this paper is too specific and is not very important for other types of problems.
limitations_and_societal_impact: This method seems very specific to this problem. I don't know if it can be used in other time varying optimization problems, or would be useful for other machine learning tasks. The trace estimation problem has two special properties: The trace is linear, so we can easily divide it into subproblems; and the estimation error has a relative bound. If we have a time varying linear regression problem instead, it is hard to reasonably assume that the error can be bounded relatively rather than absolutely. Furthermore, although the problem is "dynamic", we are given the matrices $A_i$ and has the freedom to perform the measurement on the linear combinations of $A_i$ as we want. This is very different from most time series datasets where we can only observe data, not measure it.

I not satisfied with Section 3.2, the theoretical justification of this adaptive step is lacking. This can be a main focus of the paper.

One immediate application of this dynamic trace estimation I can think of, is in the stepsize for gradient descent (quasi-Newton method). At each step, we can use the trace of the inverse Hessian (divided by dimension) as the stepsize. Then the difference of two Hessians is diminishing as the iterates get closer to the optimizer. If the difference is vanishing, how can we choose the damping parameter? And I guess the answer to this can give us a very good quasi-Newton method. It is also related to the previous problem. We must choose the damping parameter adaptively.
review_title: null

Meta-review: This paper considers estimating the trace of a sequence of matrices $A_1, A_2, … A_t$ under the constraint that $||A_i - A_{i+1}||\_2$ is small. The proposed algorithm outperforms the baseline which repeatedly applies Hutchinson's stochastic trace estimator in terms of sample complexity. This paper receives unanimous support from the reviewers. Thus, I recommend acceptance. 
Decision: Accept (Poster)