Recent advances in deep learning theory have evoked the study of generalizability across different local minima of deep neural networks (DNNs). While current work focused on either discovering properties of good local minima or developing regularization techniques to induce good local minima, no approach exists that can tackle both problems. We achieve these two goals successfully in a unified manner. Specifically, based on the Fisher information we propose a metric both strongly indicative of generalizability of local minima and effectively applied as a practical regularizer. We provide theoretical analysis including a generalization bound and empirically demonstrate the success of our approach in both capturing and improving the generalizability of DNNs. Experiments are performed on CIFAR-10 and CIFAR-100 for various network architectures.
Post-rebuttal update: I have just noticed the authors modified their summary post below and claimed "[my concerns] are all minor or resolved". This is not true. Here is my summary of unresolved concerns written after the discussion period.
This work has been substantially improved during the rebuttal process, and some of my concerns are addressed. But there are still major issues, as raised in my [last comment]( https://openreview.net/forum?id=BJlXgkHYvS&noteId=r1xAnokijS ), that remains unanswered. Specifically,
(A) the relation between this work and information theory
In the revision, the authors have make it very clear that the relation between FIA and their proposed regularized objective is very vague, relying on the crude approximation of expected Fisher information with observed Fisher information. Therefore the "information-theoretic" part in the title seems awkward and to some extent, misleading.
As Reviewer 1 has pointed out, it would have been better if the authors relate their theory and method to the observed FIM, instead of information theory, from the beginning. Since the observed FIM and the neural tangent kernel (NTK) share the same eigenspectrum, it would also be interesting to relate this work to the NTK.
(B) the different behavior of the proposed regularization (log det(I)) and its bound that is actually implemented (log tr(I))
This is the more important issue. My concern is that the observed FIM (or the NTK) is known to have fast decaying spectrum; (Karakida et al) has shown empirically that the decay can be exponential. Thus log det(I) would be dominated by the long tail (since after taking logarithm it is the sum (or average) of an arithmetic sequence), while log tr(I) would be dominated by the first largest few values. 
The authors claim that this is not an issue since they replaced the observed FIM with a subsampled, low-rank (<=10), version. It corresponds to consider a small submatrix of (the gram matrix of) the NTK. Denote this matrix as .
(a) This does not help with the problem, since we now have no chance of recovering the smaller eigenvalues that would have dominated log(det(I)), and it is impossible that the proposed regularizer has a similar behavior to log(det(I)).
(b) One could verify easily, using small feed-forward networks (or even simpler, computing a gram matrix using RBF kernels, since the FIM shares its eigenspectrum with NTK which is a p.d. kernel), that the new matrix  still has a fast-decaying eigenspectrum, so the behavior of  and \tilde{I} are still significantly different, even though this cannot be established by concentration bounds as the authors argue. While FFN and modern deep architectures can have different behaviors, I believe the above evidence suggests that a numerical experiment comparing the behavior of the two bounds is a must.
Following this argument we can see *another issue* of this work, namely the proposed generalization bound will be vacuous given the fast-decaying spectrum of the FIM, since it contains gamma=log(det(I)).
Reviewer 1 mentioned this work could enlighten future discussions on this subject. While I agree this paper presents interesting empirical observations (namely its final algorithm, which is vaguely connected to the proposed objective, leads to improved performance on CV tasks), I think this submission in its current form is a bit too misleading to serve this purpose well, and overall I believe it would be better to go through another round of revision.
Original Review
============================================
This paper presents a generalization bound based on Fisher information at a local optima, and proposes to optimize (an approximation to) it to get better generalization guarantees. There are issues in both parts, and I don't think it should be accepted. Specifically,
1. The definition of Fisher information is incorrect (for almost every parameter). The expectation should be taken w.r.t the model distribution p(c_x|x;w), instead of the data distribution S. 
2. Assumption (1) (loss locally quadratic) is not reasonable for DNNs, since local optimas will not be unique in their neighborhoods. See e.g. Section 12.2.2, "Information Geometry and Its Applications".
3. Regarding the approximation to the bound, approximating log det(I) with log trace(I) is not a good idea: adding a very small eigenvalue will lead to noticeable change in the former, but negligible change in the latter. This is particularly problematic for DNNs, since the spectrum of their Fisher information matrix varies in a wide range: see "Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach". 
(Edit 11.8:
* regarding point (1), there is a quantity called observed Fisher information in e.g. Grunwald (2007) that coincide with Eq (1) in the paper, but it is a function of the dataset instead of the model parameter, and can only used to study model parameters near the *global optima* (as it is applied in Grunwald (2007)); it cannot help with choosing between different local optimas as this work claims. Additionally, the FIA criterion, which is used in this paper to devleop the generalization bound, is defined using the standard form of Fisher information (i.e. taking expectation w.r.t model distribution), see Rissanen (1996). These facts lead me to believe this is a confusion on the authors' part.
* in point (2) I was referring to the authors' argument " Since L(S,w) is analytic and w_0 is the *only local minimum* of L(S,w) in M(w_0)", which is incorrect.)