Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Update: I thank the authors for their response, and I will keep the score as is. It would be nice to have a simple empirical analysis in the final supplemental material.


The paper discusses the covariance of two FIM estimators, which is useful in deep learning where the exact FIM over the full dataset can be hard to compute. One is based on the variance of the score (type 1) and the other is based on the Hessian of the relative entropy (type 2). Comparing these covariances can depend on the exponential family used in the model, type 1 has a higher variance for Normal and Poisson whereas type 2 has a higher variance for Bernoulli. Convergence rate results are given which is $O(N^{-0.5))$ with constant determined by the variances. These results provide some theoretical justification as to which estimator of FIM to use when using it to perform natural gradient in deep learning. 
main_review: The paper is theoretical but is highly related to deep learning practice, especially when natural gradients are used. The paper compared two variants of FIM estimators, computed their covariances (Theorem 4, and Theorem 6), upper bounds (Corollaries 7 and 8), when these estimators are PSD (theorem 9, theorem 10), convergence rate (Lemma 11), and the structure of the deep learning network (Lemma 13).

I think the paper is clearly written, the results are solid, and the problem investigated is important to machine learning and natural gradient methods. The variance results clearly indicate what type of FIM estimator is preferred in NG in principle.

My only concern is that there are not any empirical results that corroborate with the theory. One very simple example is to take a very small neural network (just a two-layer one would suffice) on a small task, and evaluate their FIM with the same number of samples using the two FIM estimators. I also think it is interesting to see if these choices affect natural gradient optimization (although I do not think this is necessary to the paper).

Additional comment: can we gain insights regarding the spectrum of the estimated FIM, not just the smallest eigenvalue? This also seems to be related to stochastic optimization, because a small condition number for the true FIM does not necessarily indicate a small condition number of the estimated FIM?

limitations_and_societal_impact: Limitations are discussed.
Societal impact is N/A because the paper is theoretical.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: For two commonly used approximations to the Fisher Information Matrix, this paper derives bounds on the variance of these estimates. They give examples of how these bounds change for different types of exponential family neural network output distributions.
main_review: After looking at the author responses, I am raising my score to an 8 to reflect that I already believed the paper was good enough for acceptance, but is now stronger.

----------------------------

Overall this is a well-done theory paper. I believe that these bounds will be useful references for practitioners deriving optimization preconditioners or other methods to compute local loss surface information via the FIM, which in my opinion is an important ongoing area of research. Additionally, the possibility of negative eigenvalues is underappreciated in practice, and so section 3.3 is a nice consideration of this situation.

Correctness:
I briefly reviewed the proofs in the appendix, and while they appear correct I could have missed a detail due to the sometimes complicated algebra.

Writing:
The paper is well written, with arguments and theorems clearly set up and presented. Minor nits:
-line 52, exponentially -> exponential
-line 189 “neural network” -> “the neural network”

Prior work:
To my knowledge no such bounds have been previously derived, and thus this is a sufficiently novel paper.

Additionally, I’m not sure if there is such a relation (the forms look similar enough I wanted to ask), but is there any relationship between your equation (8) and the Generalized Gauss-Newton Matrix (see sec. 8 of https://arxiv.org/abs/1412.1193)? If so that would be a nice connection to make.

Additional feedback:
This is by no means a requirement, as theory-only papers are perfectly acceptable, but while the examples in Table/Figure 1 are useful and compelling, the paper would be further strengthened by small-scale feed-forward neural net experiments where you could analytically compute the FIM and the approximations presented in this paper.

At the end of section 2.3, you say “control the scale of neural network output h_L”. Could this be possible by using temperature scaling or adding a normalization layer to the top of the network (although the latter may introduce complexities in your assumptions about the NN structure h_i)? It could be nice to at least mention that in practice it is easily possible/common to control the scale of h_L.
limitations_and_societal_impact: I agree with the authors that I do not believe there are relevant societal impacts of this work that are useful to discuss at this time.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the Fisher information matrix (FIM) theoretically. Two equivalent expressions of FIM and their estimators are discussed (rediscovered) for deep neural network with exponential family output units. The closed-form variance (and simpler-form upper bounds) for the two estimators is proposed; the convergence rate of the positiveness definiteness are also analyzed. Finally, the variance is connected with the structure of the corresponding deep neural networks.
main_review: **Originality**

While the two estimators are not proposed originally, their variance has not been analyzed theoretically in machine learning, claimed by the authors. Besides, positive definiteness, convergence rates of the two estimators and the connection with the structure of the deep neural networks are also analyzed in details.

**Clarity**

This paper is clearly presented and readable. Although I am not familiar with this research area, I could keep up with the storyline without much effort.

**Significance**

The discussed estimators are very intuitive and make sense to me. In fact, I feel a little surprised about the "fact" that the two estimators have not been analyzed.

**Concerns**

In spite of some mentioned related work, more comparison of existing estimators with the two estimators should be proposed. It is confusing about the position in literature.

Moreover, since the two esitmators are quite simple, it is suggested to add some application cases (maybe toy cases) about them.
limitations_and_societal_impact: NA
review_title: null

Meta-review: The reviewers agreed that this is a solid theoretical paper that makes a real contribution. The paper is well-written relative to the complexity of what it's presenting.
Decision: Accept (Poster)