Information-Theoretic Local Minima Characterization and Regularization
Authors: Zhiwei Jia
Hao Su
Venue:  (2020)
Keywords: local minima
generalization
regularization
deep learning theory

Abstract: 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.

Under review as a conference paper at ICLR 2020
INFORMATION- LOCAL MINIMA CHARAC- TERIZATION AND REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Recent advances in deep learning theory have evoked the study of generalizabil- ity 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 a practical regularizer. We provide theoretical analysis including a generalization bound and empirically demonstrate the success of our approach in both captur- ing and improving the generalizability of DNNs. Experiments are performed on CIFAR-I0 and CIFAR-100 for various network architectures.
INTRODUCTION
Recently, there has been surge in the interest of acquiring theoretical understanding over deep neural network's behavior. Breakthroughs have been made in characterizing the optimization pro- cess, showing that learning algorithms such stochastic gradient descent (SGD) tend to end up in one of the many local minima which have close-to-zero training loss (Choromanska et al., 2015; Dauphin et al., 2014; Kawaguchi, 2016; Nguyen Hein, 2018; Du al., 2018). However, these numerically similar local minima typically exhibit very different behaviors in terms of generaliz- ability. is, therefore. natural to ask two closely related questions: (a) What kind of local minima can generalize better? (b) How to find those better local minima?
To our knowledge, existing work focused only on one of the two questions. For the "what" question, various definitions of "flatness/sharpness" have been introduced and analyzed (Keskar et al., 2017; Neyshabur et al., 2018: 8; 2017; Wu et al., 2017; Liang et al., 2017). However, they suffer from one or more of the problems: (1) being mostly theoretical with no poor empirical evaluations on modern neural networks, (2) lack of theoretical analysis and understanding. (3) in practice not applicable to finding better local minima. Regarding the "how" question, existing approaches (Hochreiter & Schmidhuber, 1997; Sokolić et al., 2017; Chaudhari ct al., 2017; Hoffer et al., 2017; Neyshabur al., 2015a; Izmailov et al., 2018) share some of the common drawbacks: (1) derived only from intuitions but no specific metrics provided to characterize local minima, (2) no or weak analysis of such metries, (3) not applicable or no consistent generalization improvement for modern DNNs.
In this paper, we tackle both the "what" and the "how" questions in a unified manner. Our an- swer provides both the theory and applications for the generalization problems across different local minima. Based on the determinant of Fisher information estimated from the training set, we pro- pose a metric that solves all the aforementioned issues. The metric can well capture properties that characterize local minima of different generalization ability. We provide its theoretical analysis, primarily a generalization bound based on PAC-Bayes (McAllester, 1999b;a). For modern DNNs in practice, it is necessary to provide a tractable approximation of our metric. We propose an intuitive and efficient approximation to compare it across different local minima. Our empirical evaluations fully illustrate the effectiivnnes of the metric strong indicator of local minima's generalizability. Moreover, from the metric we further derive and design a practical regularization technique that guides the optimization process in finding better generalizable local minima. The experiments image classification datasets demonstrate that our approuch gives consistent generalization boost for range of DNN architectures.

---

Under review as a conference paper at ICLR 2020
2 RELATED WORK
has been empirically shown that larger batch sizes lead to worse generalization (Keskar et al,, 2017). Hoffer et al. (2017) analyzed how the training dynamics is affected by different batch sizes and presented a perturbed batch normalization technique for better generalization. While it effec- tively improves generalization for large-batch training. specifie metric that indicates the general- izability is missing. Similarly, Elsayed et al. (2018) employed a structured margin loss to improve performance of DNNs w.r.t. noise and adversarial attack yet no metric was proposed. Furthermore, this approach essentially provided no generalization gain in the normal training setup.
The local entropy of the loss landscape was proposed to measure "flatness" in Chaudhari et al. (2017), which also designed an entropy- SGD that achieves faster convergence in training DNNs. However, the method does not consistently improve generalization, e.g., a decrease of per- formance on CIFAR-10 (Krizhevsky & Hinton, 2009). Another method that focused on modifying the optimization process the Path-SGD proposed by Neyshabur et al. (2015a). Specifically, the authors derived an approximate steepest descent algorithm that utilizes the path-wise norm regular- ization to achieve better generalization. The authors only evaluated it on a two-layer neural network, very likely since the path norm is computationally expensive to optimize during training.
A flat minimum search algorithm was proposed by Hochreiter & Schmidhuber (1997) based on the "flatness" of local minima defined as the volume of local boxes. Yet since the boxes have their axes aligned to the axes of the model parameters, their volumes could be significant underestimations of "flatness" for over-oaranene vee-parametrrzed networks, due to the specific spectral density of Hessian of DNNs studied in Pennington& & Worah (2018); Sagun et al. (2018). The authors of Wu et al. (2017) also characterized the "flatness" by volumes. They considered the inverse volume of the basin of attrac- tion and proposed to use the Frobenius norm of Hessian at the local minimum as a metric. In our experiments, we show that their metric does not accurately capture the generalization ability of local minima under different scenarios. Moreover, they have not derived a regularizer from their metric.
Based on "robustness" metric, Sokolić et al. (2017) derived a regularization technique that suc- cessfully improves generalization on multiple image classification datasets. Nevertheless, we show that their metric fails to capture the generalizability across different local minima.
By using the Bayes factor, MacKay (1992) studied the generalization ability of different local min- ima obtained by varying the coefficient of 1.2 regularization. derived a formula involving the determinant of Hessian, similar to the one in ours. Whereas, this approach has restricted settings and, without proposing an efficient approximation, its metric is not applicable to modern DNNs, let alone serving as regularizer. A generalization bound is missing in MacKay (1992) well.
In a broader context of the "what" question, properties that capture the generalization of neural net- works have been extensively studied. Various complexity measures for DNNs have been proposed based on norm, margin, Lipschitz constant, compression and robustness (Bartlett & Mendelson, 2002; Neyshabur ct al., 2015b; Sokolić et al., 2017: Xu & Mannor, 2012; Bartlett et al., 2017: Zhou et al., 2019; Dziugaite & Roy, 2017; Arora et al., 2018; Jiang et al., 2019). While some of them aimed provide tight generalization bounds and some of them to provide better empirical results, none of the above approaches explored the "how" question at the same time.
Very recently, Karakida et al. (2019) and Sun & Nielsen (2019) studied the Fisher information of the neural network through the lens of its spectral density. In specific, Karakida et al. (2019) applied mean field theory to study the statistics of the spectrum and the appropriate size of the learning approach, Sun & Nielsen (2019) derived a novel formulation
rate. Also an iiformation-thhorre of the minimum description length in the context of deep learning by utilizing tools from singular Sami-Riemannian geometry.
3 OUTLINE AND NOTATIONS
In a typical K- K-way classification setting, each sample x E X belongs to a single class denoted
Cr {0, K} according to the probability vector y y, where y is the k-dimensional probability simplex so that p(c, = i) = yi and Σ; Vi = 1. Denote a feed-forward DNN parametrized by w E RW as f : X + y, which uses nonlinear activation functions and a softmax layer the end. Denote the cross entropy loss as (()o)))))) -. In (x) De-
2

---

Under review as a conference paper at ICLR 2020
note the training set S. defined over X' x y with |s'= = N. The training objective is given as C(S, w) = E(aww (z). Assume is sampled from some true data distribution de- noted D, we can define expected loss L(D, w) = ((x.a))D(((f((()) v)]. Throughout this paper, we refer a local minimum of L(S, w) corresponding to a local minimizer wo as just the local minimum wg. Given such wig our paper's outline as well our main achievements are:
In Section 4 we relates Fisher information neural network training as prerequisite.
In Section 5.1 we propose metric ((w)) that well captures local minima's generalizability.
Section 5.2 we provide generalization bound related to ((w)).
In Section 5.3 we propose approximation (ww) for (wo)). which is shown to be very effective in Section 7.1 via extensive empirical evaluations.
In Section 6 we devise practical regularizer from (wa) that consistently improves gen- eralizability across different DNNs, as evaluated Section 7.2.
3.1 OTHER NOTATIONS
Denote V gradicnt, JwI:] Jacobian matrix, V Hessian, (-I-))l) as KL divergence, |1-112 as spectrum or Euclidean norm, ||-I|r as Frobenius norm, |-| as determinant, tr(-) as trace norm, p(-) spectral radius, (ws(w) as log-likelihood on S, and [+] for selecting the 2th entry.
We define (w) E R2 whose 7th entry is - In (x)); so that (x). y) = (uw) y. We define argmmax(y) and R the one-hot vector whose ý-th entry is and otherwise Then we define C(S, w) I as the "simplified" loss vector of S whose entries are (xf(w)), 7) for (x,y) E S, i... we approximate the cross entropy loss (f)( 3) by ((fw
LOCAL MINIMUM AND FISHER INFORMATION
First of all, if y is strictly one-hot, local minimum will even exist with 100% training accuracy, since the cross entropy loss will always be positive. To admit good local minima in the first place, assume the widely used label smoothing (Szegedy al., 2016) is applied train all models in our analysis. Label smoothing enables us to assume local minimum wo (in this case, also global minimum) of the training loss with E(swes ( (z)ll)) O.
Each sample (z, y) E S has its label ea sampled by p(c₂ = i|æ) = yi. denoted as (a, cz) ~ S. The joint probability p(r, cx) modeled by the DNN is p(z, Cz i; w) p(c₂ i|æ; w) p(x) [Nu((x)]; p(x) with p(x) = N. We can relate the training loss L(S, w) to the negative log- log-likeldhood -ll((w) Ensees Ee, Inp Czi w) by:
Σ (x(w) L(S,w) w) (x.y)ES
1
E Inp(c.|=;w) N (z.8) c-my
Σ
1 (ls(w) In 1 N
And wi also corresponds information evaluated at wp is defined as I(wo) = - (ls((w))) We can further derive:
local maximum of the likelihood function. The observed Fisher
E V In |z; V In p(c2/2; wo)= I(wo) = v L(S, wo) (a.c=)~~S
(1)
The first equality is straightforrard; the second has its proof in Appendix A. Since p(c, = i|xx) = yi and In p(c, = ilæ; wo) = [e, (wo)]i. we can further simplify the Equation to:
I I(w))
1
Σ Σ
E(Vuree (wollo( (V (Voll((wo))))
(2)
N
(2.0)ES
Remark: When we assume global optimality, we have V (1), = 0 as DJm (x)ll O; yet does not indicate I(ww) E RWxW * 0 in Equation 2.
=
5 LOCAL MINIMA CHARACTERIZATION
In this section, we derive and propose our metric, provide PAC- generalization bound, and lastly, propose and give intuitions of effective approximation of our metric for modern DNNs.
3

---

Under review as a conference paper at ICLR 2020
5.1 FISHER DETERMINANT AS GENERALIZATION METRIC
We would like a metric to compare different local minima. Similar to the various definitions of "flannes/Sharpness" we take small neighborhood of the target local minimum wo into account. Formally for a sufficiently small V. we define the model class M(wo) as the largest connected subset of {w E RW C(S, w) I h} that contains wo, where the height h is defined a real number such that the volume (namely the Lebesgue measure) of M(wo) is V. By the Intermediate Value Theorem, for any sufficiently small volume there exists a corresponding height
We propose our metric 7-),, where lower (wwo) indicates a better local minimum Wy:
7(wo) = In|I
(3)
As metric, 7ww) requires [I(w))] + O. Therefore, we state the following Assumption 1. Assumption 1. The local minima Wa we care about in the comparison are well isolated and unique in their corresponding neighborhood M(wo).
The Assumption 1 is quite reasonable. For state-of-the-an network architectures used in practice, this is often the fact. To be precise, the Assumption is violated when the Hessian matrix at a local minimum singular. Specifically, Orhan & Pitkow (2018) summarizes three sources of the singularity: (i) due to a dead neuron, (ii) due to identical neurons, and (iii) linear dependence of the neurons. As well demonstrated in Orhan & Pitkow (2018), network with skip connection, e.g- ResNet (He et al., 2016a), WRN (Zagoruyko & Komodakis, 2016), and DenseNet (Huang et al., 2017) used in our experiments, can effectively eliminate all the aforementioned singularity.
In Dinh et al. (2017), the authors pointed out another source of the singularity specifically for net- works with icale-invariint activation functions, e.g. ReLU, referred as the rescaling issue. Namely, one rescales the model parameters layer-wise the network remains unchanged in the region. In practice, this issue is not critical. Firstly, most modern deep ReLU networks, e.g. ResNet, WRN, and DenseNet, have normalization layers, e-g- BatchNorm (loffe & Szegedy, 2015), applied before the activations. BatchNorm shifts all the inputs to the ReLU function, equivalently shifting the ReLU horizontally which makes it no longer scale- invariant. Secondly, due to the ubiquitous use of Gaussian weights initialization scheme and weight decay, most local minima obtained by gradient learning have weights of a relatively small norm. Consequently, in practice, we will not compare two local minima essentially the same but have one as the rescaled version of the other with a much larger norm of the weights.
that the underlying function represented by
Note that normally we have a limited size of the dataset, and so an approximation of 7(wa) is must. We present our approximation scheme and its intuition in Section 5.3.
5.1.1 CONNECTION TO FISHER INFORMATION APPROXIMATION (FIA) CRITERION
Our metric ((w)) closely related the FIA criterion. From Information Theory, the MDL prin- ciple suggests that among different statistical models the best is the one that best compresses both the sampled data and the model (Rissanen, 1978). Accordingly, Rissanen (1996) derived the FIA criterion to compare statistical models, each of which is a class of model in the neighborhood of global minimum wp. The model class's FIA criterion is written as (lower FIA is better):
W
N
J
FIA Σ
E 1np(x, Czi wo) (21))S Sanry
2
In
2T
In
(M((N))
Vizl dw
On the right hand side, the first two terms are both constants. To see the connection to our metric, replace the expected Fisher information I,, with the tractable observed one I(wp). Assuming the training loss is locally quadratic in M(wo), an assumption later formalized and validated as Assumption 2, since I(wo) C(S, wo) from Equation 1, we can modify the last term to be In V + VIZ(wo))
Remark: Although in similar format, the FIA criterion and our metric are essentially different due to the appearance of observed Fisher information in place of the expected one, making our metric both tractable and much more applicable (no longer requires global optimality).
5.1.2 CONNECTION TO EXISTING FLATNESS/SHARPPH METRICS
4

---

Under review as a conference paper at ICLR 2020
As mentioned in Section 2, the "flatness" of local minimum was firstly related to the generaliza- tion ability of the neural network in Hochreiter & Schmidhuber (1997), where the concept and the method are both preliminary. The idea is recently popularized in the context of deep learning by series of paper such as Keskar et al. (2017); Chaudhari et al. (2017); Wu et al. (2017). Our approach roughly shares the same intuition with these existing works, namely, a "flat" local minimum admits less complexity and so generalizes better than a "sharp" one. To our best knowledge, our paper the first among these work that provides both the theoretical analysis including generalization bound and the empirical verification of both an efficient metric and practical regularizer for modern network architectures.
5.2 GENERALIZATION BOUND
Assumption 2. Given the training loss L(S,w) w). its local minimum we satisfying Assumption I and the associated neighborhood M(wa) whose volume V is sufficiently small, as described in Section 3, and 5. respectively, when confined to M(wn), we assume that L(S,w) w) is quadratic.
The Assumption quite reasonable as well. Grünwald & Grunwald (2007) suggests that, log- likelihood function, under regularity conditions (1) existence of its 1st 2 & 3rd derivatives and (2) uniqueness of its maximum in the region, behaves locally like a quadratic function around its maximum. In our case, C(S, w) corresponds to the log-likelihood function Els (lg(w) and so wo corre- sponds to a local maximum of &lg(w), (w). Since L(S, w) is analytic and Wy is the only local minimum of L(S, w) in M(mo). the training loss indeed can be considered locally quadratic.
Similar to Langford & Caruana (2002), Harvey et al. (2017) and Neyshabur et al. (2017), we apply the PAC-Bayes' Theorem (MeAllester, 2003) derive generalization bound for metric. Specif- ically, we pick a uniform prior P over w E .M(wo) according to the maximum entropy principle and after observing the training data S pick the posterior Q of density q(w) x e-14 ( Then Theorem bounds the expected L(D, w) using 7(wa). See its proof in Appendix B.
Theorem 1. Given |S|= N, D. L(S, w) and L(D, w) described in Section 3, a local minimum wo with Co A L(S, wo). the volume V of M(wo) sufficiently small, the Assumption 1 & 2 satisfied, and P, Q defined above, for any 5 E (0, 11, we have with probability at least 1 - 5 that:
2co + 2A In
2N 3 A
WV n ww/o//
[C(D, < Lo 2
-
4Te
In short, Theorem shows that a lower (ww)) indicates more generalizable local minimum wo.
5.3 APPROXIMATION
As stated in Section 4, in practice an approximation of (ww) as ?(wa) is necessary, as calculating (ww) involves computing the determinant of a W x W matrix. Let us first assume we have an imagined training set S' of size W, local minimum wy of L(S', w) and so correspondingly full- rank observed Fisher information matrix I'(wo) so that In|Z'(ww)) is well defined. In reality, we only have a training set S S' with a singular I(wg). Notice that wo also a local minimum of L(S, w) since ((ryes DKL (x)]ll) 0 as assumed in Section 4. We then approximate eigenvalues of I' (wma by those of its sub-matrices and so to approximate In In]T'(wo))
First of all, we replace y by its one-hot version ÿ defined in Section 3.1 since they are very close. This drastically reduces the cost of gradient calculation. With Ż(S w) E IRN and 7 defined in Section 3.1, according to Equation 2, the observed Fisher information I' ('(w)) E RxW is:
I'(wo)
Σ (B.))SS'
(vmle((w)))) (Vu(La(wo))s))
W
= Ju 1ō(S", (C((S""))"' J [C(S"" w)] = w Jul((S' w)] Ju Jw (C(S) w))² w
(4)
Let denote the eigenvalues of I' (wo): then 7(w)) = In Ih Am = > In Am Without calculating all W eigenvalues, we can perform Monte-Can Carlo estimation of ? by
5

---

Under review as a conference paper at ICLR 2020
randomly sampling N' < N < W eigenvalues from {Am 1 mm=1- We denote the samples {An } and we have W.
N' n= In An = Em In Am. Suppose the estimation is run T times, we have Ex=1 In X, = 7ww)).
DN
W 4om 1 Ei= N'
1. In practice (A,, n=1 is inaccessible since we don't 't have (wo) in the first place. Instead, we sample St C with S = N' for times and define
<'(wo) _ J,, Li(S", wo)] [C(S", wo)?" RN''''
Notice that (wrg) a principal sub-matrix of WT' (wn) by removing rows & columns for data in St. According Theorem one can roughly estimate the size of eigenvalues of matrix by those of its sub-matrices. Therefore we propose to estimate ((wa) by (wp)) with:
W N (wo)) W In
7(wb) A Σ In (mo)) 7(w))
W T
We leave Theorem 3 as well the derivation of Equation 5 Appendix C. In proposing (ww)), ignore the constants and irrelevant scaling factors because what matters is the relative size of 7-)) when comparing different local minima. Empirically we find that given relatively large number of sample trials T, our metric 7--) can effectively capture the generalizability of local minimum even for small N' (details in Section 7.1 and in Appendix D).
LOCAL MINIMA REGULARIZATION
Besides pragmatism, devising a practical regularizer based on ((w)) also "verifies" our theoretical understanding of DNN training, helping for future improvement of the learning algorithms. How- ever, converting (ww)) to practical regularizer is non-trivial due to the computation burden of:
optimizing terms related the gradient, which involves calculating the Hessian 2. computing the eigenvalues each training step, which even more expensive
We first solve the second issue and then the first one. To solve the second issue, propose to optimize surrogate term for ((w)) which avoids eigenvalue computations, namely the trace norm of the observed Fisher information tr([(w))). These two terms have the relation:
1 W (ww)
W In[I(w])] < Intr(I(wo)) In W
Another major benefit of using the trace norm is that, unlike (ww)), tr(Z(wo)) still remains well defined even with small training set |S N. From Equation 2 we have:
K
(r([ww))
Σ
(z.0)ES
The of computing (r(I())) is linear in the number of its terms (in the double summation). We therefore simplify the calculation by replacing y with ý similar to Equation so that
N Vn wo)
tr([[w))
=
1
IV (.) (Na))S
Σ
N
N
where ū and Z(--)) are defined in Section 3.1. As in gradient-based training we never exactly reach the local minimum wo. we choose to optimize tr(I(w)) during the entire training process. We have V E. V [C(B, wo)])112 = | E. V..iV.... V wo)]ill² for each mini-batch B. Then we further reduce the computation cost by batching. In specific, randomly split B into M sub- batches of equal size, namely { We define gi A |s. E(n,ye ((fmo (x), ū) and compute Ig: 1 for g: E M instead of computing [[[, : 112 for each data point in B.

---

Under review as a conference paper at ICLR 2020
We deal with the first computation burden by adopting first order approximation. For any w, with sufficiently small 0 we have L(B, ag.) = [[,, w) J [2 w)] ag.. Then
[an
1 1
[(B, w) [(B, w og:)lı
1
J Jm, w)] ag. a l
Therefore, we propose to optimize the following regularized training objective for each update step:
M
%1 [(B. (att))-L(BBBuu agi),
1
L(B, w) + 3Ro (w), (w)
(6)
M
We omit any second order term when computing Rec (w)), simply by no back-prop through gi- On the other hand, we find that gradient clipping, especially at the beginning the training, is necessary make the generalization boost consistent. We have 4 hyper-parameters: number sub-batches M and the gradient clip threshold т. Our approach is formalized as:
B, the
Algorithm Regularized Mini-batch Learning (Single Update Step)
1: procedure UPDATE(W, B; a, 3,
> Last are spper-parameters > Split the mini-batch B into M sub-batches
2:
{B. M
1= t B
3: for + 1 to M do
4:
9: | (zz,)ee, {(Sur (3),,)
Compute the gradient of the sub-batch b A copy prevents gradient flow
5:
9: cg.
6:
end for
7:
Compute R. (wr) by Equation 6
D. Use the copied version of g:
Vilhingg V [LB, w) + BR, (w)) 8:
9:
Clip V Crgg with threshold т Gradient update with clipped V wre
> chip_be syy_global__gg norm in TensorFlow Update with any gradient-basee optimizer
11:
end procedure
7 EXPERIMENTS
We perform two sets experiments to illustrate the effectiveness of our metric r(wo). We demon- strate that: (1) the approximation (ww)) captures the generalizability well across local minima; (2) our regularization technique based on (ww)) provides consistent generalization gain for DNNs.
Throughout theoretical analysis, assume that label smoothing (LS) is applied during model training in order to obtain well-defined local minima (first mentioned in Section 4). In all our empirical evaluations, we perform both the version with LS applied and without. Results very similar and so we stick to the version without LS since this is the same as the original training setup in papers of the various network architectures that used.
7.1 EXPERIMENTS ON LOCAL MINIMA CHARACTERIZATION
We perform comprehensive evaluations to compare our metric 7(-) with several others on ResNet- 20 (He et al., 2016a) for the CIFAR-10 10 dataset (architecture details in Appendix E). Our metric consistently outperforms others in indicating local minima's generalizability. Specifically, Sokolić ct al. (2017) proposed a robustness based metric used as a regularizer; Wu ct al. (2017) proposed to Frobenius norm of the Hessian related to the spectral radius of Hessian. In summary, we compare 4 metrics, all evaluated at a local minimum w given S. All four metrics go for "smaller values indicate better generalization".
metric; Keskar et al. (2017) proposed metric closely
Robustness: & E(E,)es (=)]1
Frobenius norm: V w)
Spectral radius: p 2VV C(S, w))
Ours: 7(w) ΣL= (S wa)l, St C

---

Under review as a conference paper at ICLR 2020
Both the Frobenius norm and the spectral radius based metric related to ours, from Equation have || L w)l = [[((w)]l and L(S, w)) p(I(w)). These two metrie, however, are too expensive to compute for the entire training set S; we instead calculate them by averaging the results for T' sampled St C S, similar to when we compute (ww). We leave details of how we exactly compute these metrics in our experiments to Appendix D.
We perform evaluations in three scenarios, similar Neyshabur et al. (2017); Keskar et al. (2017). We examine different local minima due to (I) confusion set of varying size in training, (2) different data augmentation schemes, and (3) different batch size. In specific,
In Scenario I, we randomly select subset of 10000 images as the training set and train the DNN with a confusion set consisting of CIFAR-10 samples with random labels. We vary the size of the confusion set so that the resulting local minima generalize differently to the test set while all remain close-to-zer terroo training losses. We consider confusion size of O, Ik, 2k, 3k, 4k and 5k. We calculate all metrics based on the sampled 10000 training images.
In Scenario II, we vary the level of data augmentation. We apply horizontal flipping, de- noted flip-only, random cropping from images with pixel padded each side plus flipping, denoted 1 1-crop-f, random cropping with 4 pixels padded each side plus flip- ping, denoted 4 c-rrop- and no data augmentation at all, denoted no no-aug. Under all schemes, the network achieves perfect training accuracy. All the metrics are computed on the un-augmented training set.
In Scenario III, we vary the batch size. Hoffer et al. (2017) suggests that large batch size leads to poor generalization. We consider the batch size to be 128, 256, 512 and 1024.
The default values for the 3 variables are confusion size 0, 4 4-crop-f and batch size 128. For each configuration in each scenario, we train 5 models and report results (average & standard deviations) of all metrics as well as the test errors (in percentage). For the confusion set experiments, we sample new training set and new confusion set every time. In all scenarios, epochs with an initial learning rate 0.1, divided by 10 whenever the training loss plateaus. Within each scenario, find the final training loss very small and very similar across different models and the training accuracy essentially equal to 1, indicating the convergence to local minima.
train the model for 200
The results in Figure 1, 2 and 3 for Scenario I, II and III, respectively. Our metric significantly outperforms others and is very effective in capturing the generalization properties, i.e., a lower value of our metric consistently indicates better generalizable local minimum.
7.2 EXPERIMENTS ON LOCAL MINIMA REGULARIZATION
We evaluate our regularizer on CIFAR- & CIFAR- 100 for four different network architectures including plain CÑN, ResNet-22, Wide ResNet (Zagoruyko & Komodakis, 2016) and DenseNet (Huang et al., 2017). We use WVN--2-2-B(3335 from the Wide ResNet paper and the DenseNet- BC-k=12 from the DensetNet paper. See Appendix E for further architecture details. We denote the four networks CNN, ResNet, WRN and DenseNet, respectively.
We manually set a = 0.0001 in all experiments and select the other three hyper-parameters in Algorithm 1 by validation via 45k/5k training data split for each of the network architecture on each dataset. In specific, we consider 3 E {10, 20, 30, 40, 50, 75, 100, 125]. M E (4, 8, 16) and {1, 5, 10, 15). We keep all the other training hyper- hyper-parameters. schemes as well as the setup identical to those in their original paper (details in Appendix E). The training details of the plain CNN are also in Appendix F. We train separate models for each network-dataset combination and report the test errors in percentage (mean + std.) in Table 1, where "+reg" indicates training with our regularizer applied. The results demonstrate that our method provides consistent generalization improvement to wide range of DNNs.
7.2.1 THE CHOICE OF THE OPTIMIZER
As described in Algorithm 1, our proposed regularizer is not tied to a specific optimizer. We perform experiments with SGD+Momentum because it is chosen to be used in ResNet, WRN, and DenseNet, helping all of them achieve current or previous state-of-the-an the-art results. Our regularizer aims to find better "flatter" minima improve generalization whereas adaptive optimization methods such as
8

---

Under review as a conference paper at ICLR 2020
Adam (Kingma & Ba, 2014) and AdaGrad (Duchi et al., 2011) try boost up convergence, yet usually at the cost of generalizability. Recent works (Wilson et al., 2017; Keskar & Socher, 2017) show that adaptive methods generalize worse than SGD+Moomnntum. In specific, very similar to setup, Keskar & Socher (2017) demonstrates that SGDD+Momentum consistently outperforms the others on ResNet and DenseNet for CIFAR-10 and CIFAR-100. Other approaches that also utilize local curvature to improve SGD, such as the Entropy-SGD (Chaudhari et al., 2017) mentioned in Section 2, have empirical results rather preliminary compared to ours.
7.2.2 GENERALIZATION BOOST AS A RESULT OF BETTER LOCAL MINIMA
Our regularizer essentially optimizes an upper bound of the proposed metric during training. We perform sanity check illustrate that the regularizer indeed induces better local minima charac- terized by our metric. For ResNet, Wide-ResNet and DenseNet trained on CIFAR-10, we compute the metric on local minima of similar training loss obtained with or without applying the regularizer. Table 2 shows that the resulting generalization boost aligns with what captured by our metric.
Error
Frobenius
Spectral
Ours
1750
2043
1250
1043
16
28
16
36 48 56
18 26 36 54
24
Figure 1: Scenario I: varied size of the confusion set. 5 models are trained for each size of the confusion set (x-axis). Solid lines are the average result; shaded areas represent the standard deviation (same for Figure 2 and 3). A larger confusion set leads to a higher test error, a trend well captured by our metric and the other two; the robustness based metric fails.
Test Error (%)
2500
Robustness
Frobenlus Norm
Spectral Radius
Ours
2000
2000
-100
1000
-1050
4aoppl
1-cop-
Ei-onty
4-cappl
T-ropd
Eip-otly
4.copp
1-ceppl Eipertty
4-cupd 1-csp- Sp-rrt
4-copp1
1-0opH
Sp-rrty
Figure 2: Scenario II: varied data augmentation schemes, Four different schemes are used. Our metric works well as an indicator of the test error while all the other metrics completely fail.
Test Error (%)
Robustness
Frobenius Norm
Spactral Radius
Ours
2000
60s3
-552
458
4063
10
1500
1000
D9120
ba256
Bs512
241024
20128
10256
2d512
ba0024
b8128
bx256
ba512
bel024
bs128
ba256
bid12
be1024
88128
ba256
ba512
be1004
Figure 3: Scenario III: varied batch size. Large batch size leads to poor generalization, captured by all the metries except for the robustness based one.
Table 1: Test error (%) for CIFAR-10 (1st row) and CIFAR- (2nd row). In general, model with more parameters admits more space for our regularizer. The representation power of ResNet-20 is too limited for CIFAR-100 (resulting in poor convergence);
ignore it in our experiments.
CNN
CNN+rg
WRN
WRN-reg
DenseNet
DenseNettreg
ResNet
ResNet-reg
8.52 = 0.08
7.46 + 0.13
5.44 + 0.04
4,80 + 0.10
4.61 + 0.08
4.31 + 0.08
8.50 + 0.31 7.91 = 0.25
31.12 4
29.19 0.21
25.52 0.15
23.65 + 0.14
22.54
0.28
9

---

Under review as a conference paper at ICLR 2020
Table 2: The proposed metric computed local minima obained with without applying the proposed regularizer. Each entry represents mean + std. among 5 runs. Smaller values are bolded.
ResNet
WRN
DenseNet
w/o reg.
999,3 22.3
-737.6 +
-850.3 23.5
with -11381 11.0
-804.8 + 18.7
-886.2 +: 20.5
CONCLUSION AND FUTURE WORK
In this paper, we show bridge between the field of deep learning theory and regularization meth- ods with respect to the generalizability of local minima. We propose a metric that captures the generalization properties of different local minima and provide its theoretical analysis including generalization bound. We further derive an efficient approximation of the metric and devise prac- tical and effective regularizer from it. Empirical results demonstrate our success in both capturing and improving the generalizability of DNNs. Our exploration promises direction for future work on regularization and optimization of DNNs.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference Machine Learning, pp- 254-263, 2018.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-488, 2002.
Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalizedd margin bounds for neural networks. Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradi- ent descent into wide valleys. International Conference on Learning Representations, 2017. URL /tttps://ppenreete wtwpearriiieeeeetoooottieeeeeeee
net forum?id-BlyfAEee
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pp. 192-204, 2015.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex op-
timization. In Advances neural information processing systems, pp. 2933-29434 2014.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1019-1028. JMLR. org, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. arXiv preprint 1rXiv:1811.03800 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ul):2121-2159, 201
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint 1rXiv:1703./1008 2017.
Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In Advances in Neural Information Processing Systems, pp. 842-852, 2018.
Peter D Grünwald and Abhijit Grunwald. The minimum description length principle. MIT press, 2007.
10

---

Under review as a conference paper at ICLR 2020
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piece- wise linear neural networks. In Conference on Learning Theory, pp. 1064-1068, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pp. 630-645. Springer, 2016b.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing 2017.
Systems, pp. 1731-1700
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wil- son. Averaging weights leads to wider optima and better generalization. arXiv preprint arXiv: 1803::800.000 054400 2018.
Yiding Jiang. Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. In International Conference on Learning Represen- fations, 2019. URL https::///// /owpnrvveeeeeeeeee/eeeeeee net/ wowrooodddoooeeee.e
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Universal statisties of fisher information in deep neural networks: Mean field approach. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1032-1041, 2019.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pp. 586-594, 2016.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from 2017.
adam sgd. arXiv preprint arXiv:
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-bate batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations, 2017. URL https: BtKLhts/s//pperrieeee /ppenrevie.. net/fore fort/f H Ygg.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
John Langford and Rich Caruana. (not) bounding the true error. In Advances in Neural Information Processing Systems, pp. 809-816, 2002.
Chen-Yu Yu Lee, Patrick W Gallagher, and Zhuowen Tu. Generalizing pooling functions in convo- lutional neural networks: Mixed, gated, and tree. In Artificial Intelligence and Statistics, pp- 464-472, 2016.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geome- try, and complexity of neural networks. arXiv preprint arXiv: 2017.
David JC MacKay, A practical bayesian framework for backpropagation networks. Neural compu- fation, 4(3):488 472, 1992.
11

---

Under review as a conference paper at ICLR 2020
David McAllester. Simplified pac-bayesian margin bounds. In Learning theory and Kernel ma- chines, pp. 203-215. Springer, 2003.
David A McAllester. Pac-bayesian model averaging. In COLT, volume 99, pp. 164-170. Citeseer, 1999a.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3):35-333,, 1999b.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized opti- mization in deep neural networks. Advances Neural Information Processing Systems, pp- 2422-2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- margin bounds for neural networks. International Conference on Learn- ing Representations, 2018. URL ht httpp: //perreiiee net/
WfbC2.
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In International Conference on Machine Learning, pp. 3727-3736, 2018.
Emin Orhan and Xaq Pitkow. Skip connections eliminate singularities. In International Confer- ence on Learning Representations, 2018. URL https: /otp:rss//pperevieww net forum? id=
HkwBEMWCZ.
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of a single- hidden-layer neural network. In Advances in Neural Information Processing Systems, pp. 5410- 5419, 2018.
Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465-471, 1978.
Jorma Rissanen. Fisher information and stochastic complexity. IEEE transactions on information theory, 42(1):40-45 1996.
Levent Sagun, Utku Evci, V. Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of net/
the hessian of over- wer-parametrized neural networks, 2018. URL forum? pewrrmmidirrie JTTTTbCD..
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16))4265-4280. 2017.
Ke Sun and Frank Nielsen. Lightlike neuromanifolds, occam's razor and deep learning. arXiv preprint arXiv: 2019.
Christian Szegedy. Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances Neural Information Processing Systems, pp. 4148-4 4158, 2017.
Lei Wu, Zhanxing Zhu, al. Towards understanding generalization of deep learning: Perspective of loss landscapes. In Proceedings of the 34th International Conference on Machine Learning- Volume 70. JMLR. org, 2017.
Huan Xu and Shie Mannor. Robustness and generalization. 2012.
Machine learning, 86(3):391-43
12

---

Under review as a conference paper at ICLR 2020
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Edwin R. Hancock Richard C. Wilson and William A. P. Smith (eds.), Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1-87.12. BMVA Press, September 2016. ISBN 1-901725-59-6. doi: 10.5244/C. 30.87. URL https: / /xx doi org/10 10. 5244 4 00.00.030....
Wenda Zhou, Victor Veitch, Morgane Austem, Ryan P. Adams, and Peter Orbanz. generalization bounds at the imagenet scale: PAC-bayesian compression approach. In Interna- tional Conference on Learning Representations, 2019. URL https::/ httpp::///ppeeevieeee net./ Forum?1d=BBJgqaake
A PROOF OF EQUATION
To prove the second equality in Equation 1, it suffices prove the following equality:
K
(llls() = Σ
v [V Σ
Inp(e = d|2; V. Inp(cz = =1/=; w)
(m.))ES
For convenience, we change the notation of the local minimum from wo to w and further denote p(ca i|æ; w)) as p (i). Since - valls(wr) = E(xy)es E V In p. (i), for each (Jr, y) E
S and E (1,2.... K), we have:
82
V (1)
In p (i)
Own P (i)
Ow,
P (t)
P (i) DrayOur P. (1)
o²
0
PT
Buny P (i)
Jwy
P (i)2
P (i)
Bw,BBr (i)
In p (i)
In p (1)
P (i)
Ow
Owk
Since we is local minimum (also global minimum) described in Section 4 as yi p% (i) for i == 1, 1,2, K, when taking the double summation, the first term above becomes:
K
82
0²
K
8²
Σ
dw, (1)
F
N = 0
Sw, (x.8)SS
Sw,ywk
(sSE)SS 1=1
1=
Then it follows that:
K
VVlls(w)]i
Σ
y V. (1) V. In)
(a,y)eS
B PROOF OF THE GENERALIZATION BOUND IN SECTION 5.2
First let us review the PAC-Bayes Theorem in McAllester (2003):
Theorem 2. For any data distribution DD and a loss function L(.,)) E [0, let L(D, w) and L(S, w) be the expected loss and training loss respectively for the model paramterized by w, with the training set |S|= N. For any prior distribution P with a model class as its support, any posterior distribution Q over C (not necessarily Bayesian posterior), and for any 5 (0. 1), have with probability at least 8 that:
2DkI In 2N
E LCD, w)] < E [C(S, w)] +2
N -
13

---

Under review as a conference paper at ICLR 2020
As ( [[(w)], we rewrite the generalization bound we want to prove in Section 5.2 as:
W V2/W x//W [I(wro))
E [C(D, w)] Lo ~
4
W.
V2/W 1/W II (Iw)) // 4TeCo 2 2N
+ +
2Te(N-1
As defined in Section 5.2, given the model class M(wo), whose volume is V, for the neural network fw. the uniform prior p attains the probability density function p(w) for any E M(wo) and the posterior Q has density q(w) e- C(S,w)-Col, Based Assumption and the observed Fisher information ((wp) derived in Section 4, especially the Equation 2, we have:
[(S, w) Lo + (w- w)) ) [w - w
Ve E MMww)
Denote Σ = [[[w]]]] VV wo)l Then @ is a truncated multivariate Gaussian distribu- tion whose density function q is:
exp - (w 2 (w wo)} [M((No) (2 1 | exp( 1 (w T I(w wp)} du
(2TT) (-))-12 -
q(w; wn, Σ)
expl - 1 (w wo) I
- (w-ww))
(8)
MM()o) expl 1/4 (w wp) " [ ( wo)} dw
Denote the denominator of Equation 8 as Z and define:
g(w: wo. Σ) 2 2 (w wo) " I (w wo)) S
Then & can also be written as:
q(u; Wo, Σ) exp[g(u; wo. 23}
Z.
In order to derive a generalization bound in the form of the PAC-Bayes Theorem, it suffices to prove an upper bound the KL divergence term:
E In ((w)
(KL(2(PP)
w~ p(w)
EE In
+ E
In (ww)
wm
In V +
E
glw; wa: E) + In Z
wm
In (Mmtno exp(g(u; wo. } dw
In V + E
0 -
2
In V
In
JM(mno expl- max wEM(wo)
L(S, w)} dw
In V In
V. Veexpf-
max wEM("))
L(S, w))
In InV vV+h
h
where h is the height of M(wo) defined in Section 5.1. For convenience, we shift down L(S,w) w) by Lo and denote the shifted training loss La(w) A L(S, w) Lo so that Lo(w)) = 0. Then
Co(w) ] (w wo) To - (w w
Vw E M(ww)
Furthermore, the following two sets are equivalent
(w R L(S, w) = h) (w E WRW Lo(w) -Lo}
14

---

Under review as a conference paper at ICLR 2020
both of which are the W dimenniiooal hyperellipsoid given by the equation Lu(w) h Lo. which can be converted to the standard form for hyperellipsoidss as:
Σ-
(w wo)
2(h Lo) (w wo)
The volume enclosed by this hyperellipsoid exactly the volume of M(wo), i.e,, V; so we have
W/2
(h 1o)
W
2
Solve for h, with the Stirling's 's approximation for factorial M(n + 1) R 22 (-) we have
h Co + (V
1 + 1))
LL /2/Wx///0 W(W+1)/W W/W//// [(w)))//WW
2
| 1/W
4
where r(-) denotes the Gamma function. Notice that for modern DNNs we have W > 1, and so
W w
W. Then the generalization bound in the form of the PAC-Bayes Theorem is given as:
W V2/W x 1//W I(wa) | 4TeLo + 2 In 2N
E [C(D, w)] $ E [C(S, w)] + 21 1--2
1
2Te(NN -
We can further bound the first term on the right hand side as:
((((,w)) < E max
L(S, w)]
w~
-~ wEM((
Putting all together, we can finally obtain Equation
C DERIVATION OF EQUATION
First, let us present the well-known theorem in linear algebra that relates the eigenvalues of matrix those of its sub-matrices.
Theorem 3. Given an n x real symmetric matrix A with eigenvalues A1 S ... S. An any k < n denote its principal sub-matrix B obtained from removing n - k rows and columns from A. Let 1/ S ... E Vi be the eigenvalues of B. Then for any 1 I r S k, we have X, I V, S Artn-k-
Let [un) 1N be the eigenvalues of w/ (wo),, which N' N' sub-matrix of I'(w)); then
1 T (wo)) = T Σ In (m (wo))
T T Σ ww W ["(w))l== I' W. + T 1=1 mm
T N
Σ
In
Theorem gives the relation between Vn and An, defined above and in Section 5.3 as the th smallest eigenvalues of 5' (wo) and that of (wo)), respectively. For sufficiently large N', we can use vn to approximate An Ignoring the eigenvalues of I'(wo) larger than Av reasonable when estimating (wo), since in general the majority of the eigenvalues of the Hessian for DNNs close to with only a few large "outliers" (Pennington & Worah, 2018; Sagun et al., 2018), and so the smallest eigenvalues are the dominant terms in ((w)). A specific bound of the eigenvalues remains open
question, though. In short, we have En Un R
N -==1 X₂ and consequently:
W N
1
W
(wo) + W In
N (wo) W In W
W
W
(7(w))
N''W
N
T
W
N
In Va
T
N
N'
W
In
X
N
Finally we we have
T
N'
lim
In X₂ (ww)
T
T
R=1
15

---

Under review as a conference paper at ICLR 2020
D DETAILS OF CALCULATING THE METRICS IN SECTION 7.1
For the following metrics, we apply estimation by sampling a subset S from the full training set S for T' times and averaging the results:
Frobenius norm: V w)ll
Spectral radius: PVV (S, w))
Ours: 7(w) = Σ In|E(S" wo)]
For the Frobenius norm based metric, from Equation 2 we have:
VV w)) ( -
Σ
N
(2.2)
Similar to Equation 4, we approximate y by and so
[V
w])
1 N
E
Σ
(a.j)es
expensive there W x W N entries in total. We therefore estimate the quantity by first sampling subset S C S and then sampling 100,000 entries of -V [2 (wo));)) [e (wo))l)) We perform the estimation T times and average the results, similar the approach when computing 9(w).
Summing over the entire Hessian matrix
Also by Equation 2 and the approximation in Equation 4, the spectral radius of Hessian is equivalent to the squared spectral norm of (.. æ=)] We also perform estimation (with irrelevant scaling constants dropped) by sampling St for T times, i.e., via + Ee [ w)ll(
Furthermore, in all our experiments that involves samplings St, we set |S N' T 100.
E ARCHITECTURE AND TRAINING DETAILS IN SECTION 7
Architecture details are below
The plain CNN is a 6-layer convolutional neural network similar to the baseline in Lee et al. (2016) yet without the "mipconv" layers (resulting in much fewer number of parameters). Specifically, the 6 layers has numbers of filters as {64, 64, 128, 128, 192, 192]. We use 3 3 kernel size and ReLU as the activation function. After the second and the fourth convolutional layer we insert 2 x 2 max pooling operation. After the last convolutional layer, we apply a global average pooling before the final softmax classifier.
layers
For ResNet-20 and WRN-28-2-B(3.3 we use the same architecture as in their original papers, with the only difference that we use pre-activation as in He et al. (2016b). This results in slightly stronger baselines than the models in their original papers.
For DenseNNetBBC-=111 paper.
the the architecture identical to the used in the original
The training details are
For the plain CNN, we initialize the weights according the scheme in He al. (2016a) and apply 12 regularization of coefficient 0.0001. We perform standard data augmenta- tion, the one denoted 4-crop-f in Section 7.1. We use stochastic gradient descent with Nesterov momentum set to 0.9 and a batch size of 128. We train 200 epochs in total with the learning rate initially set to 0.01 and then divided by 10 at epoch 100 and 150.
For ResNet-20, WRN-28-2-B(3.3 and DenseNet-BC-k=12. we the same hyper- parameters, training schemes, data augmentation schemes, optimization methods, etc., as those in their original papers, respectively.
16


Reviews:
[{"review_id": "rJgVQyi9FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper contributes to the deep learning generalization theory, mainly from the theoretical perspective with experimental verifications. The key proposition is given by the unnumbered simple equation in the middle of page 4 (please number it), where \\mathcal{I} is the Fisher information matrix. According to the authors, this simple metric, which is the log-determinant of the Fisher information matrix, can characterize the generalization of a DNN.\n\nRemarkably, this piece of work is well written in terms of English and formulations, and complete, with a rigorous theoretical analysis (section 5.1, 5.2), practical approximations (section 5.3) and empirical verifications (section 6).\n\nOn the theoretical side, this work builds upon Rissanen's formulation of the MDL principle, which has two parts (describing data given the model as well as the model complexity). Under rough approximations, the complexity term becomes the log-determinant of the Fisher information matrix evaluated at the local (global) optimum. This simple approximation is further proved to upper-bounds the generalization error as stated in theorem 1.\n\nTo make the criterion to be practically useful, the author used the Jensen inequality so that the metric simply depends on the trace of the Fisher information matrix.\n\nThe empirical study showed the usefulness of the proposed metric which can well approximate the testing error and a regularization term (based on the trace of the Fisher information matrix) that can improve generalization on real DNN experiments.\n\nThe reviewer has the following minor comments to further improve this contribution:\n\nsection 5.1, explain the abbreviation FIA\n\nRegarding the choice of the neighborhood \\mathcal{M}(w_0), what is the reason to define the model (neighbourhood of w_0) based on the loss? Why not simply take a coordinate neighborhood?\n\nAccording to your metric, the smaller the scale of the Fisher information matrix, the better the generalization. In section 5.1, there has to be some remarks on the intuition and related works on the flatness of the local minimum that is related to generalization.\n\nAs this contribution is related to the spectral properties of the Fisher information matrix, the reviewer points the authors to \"Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach. Karakida et al. 2018.\" and \"Lightlike Neuromanifolds, Occam's Razor and Deep Learning. Sun and Nielsen. 2019\", which deals with asymptotic cases and have similar MDL formulations expressed in terms of the spectrum of the Fisher information matrix.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJeaomh79S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a metric to characterize local minima of deep network loss landscapes based on the Fisher information matrix of the model parameterized by the deep network. The authors connect the Fisher information to the curvature of the loss landscape (the loss considered is the negative loss likelihood) and obtain generalization bounds through PAC Bayes analysis. They further propose regularizing the training of deep networks using the local curvature of the loss as a regularizer. In the final experimental section of the paper, the relationship between the empirical measures and generalization is shown on a variety of networks.\n\nThis is an interesting paper, but I have a few concerns.\n\n1. The information-theoretic measure that is proposed is essentially the (log) determinant of the hessian of the loss function.  If there are degenerate eigendirections (zero eigenvalues) then the proposed measure would not be able to distinguish between minima with different numbers of degenerate directions / same number of degenerate directions but different spectral norms of the hessians. If the authors contention is that there will be no zero eigenvalues, that suggests that local minima of deep networks are all strict, isolated minima, contrary to recent work on connected solutions (See Draxler et. al. 2018, Essentially No Barriers in Neural Network Energy Landscapes, ICML 2018).\n\n2. I would like to see how the authors believe their measure deals with rescalings layer parameters in deep networks, ie the issue brought up by Dinh et. al. in \"Sharp Minima can Generalize for Deep Networks\" ICML 2017. While I can see that the log determinant is invariant, it is not clear that the proposed approximation will be invariant to rescaling of deep network layer parameters. If the parameters corresponding to the eigenvalues sampled in the approximation are rescaled, I believe the proposed measure will not be invariant.\n\n3. The experiments regarding the local minima characterization are well constructed, though some details are missing such as how the authors decided that training had converged to a local minimum. As far as regularization based on the local curvature is concerned, I would like to see some more experiments that compare the proposed technique to adagrad/adam and other techniques that purport to condition the gradient based on local curvature. It would also be interesting to see whether the regularization indeed converges to flatter minima characterized by the proposed flatness measure. Since the claim is that the regularizer gets you flatter solutions, that information is important to decide whether the proposed technique is performing as advertised.\n\nI am willing to update my score based on responses to these concerns.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xq1PY2tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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,\n\n(A) the relation between this work and information theory\n\nIn 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.\n\nAs 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.\n\n(B) the different behavior of the proposed regularization (log det(I)) and its bound that is actually implemented (log tr(I))\n\nThis 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. \n\nThe 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 .\n(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)).\n(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.\n\nFollowing 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)).\n\nReviewer 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.\n\n\nOriginal Review\n============================================\n\nThis 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,\n\n1. 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. \n2. 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\".\n3. 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\". \n\n(Edit 11.8:\n* 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.\n* 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.)", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes using the Fisher information matrix to characterize local minima of deep network loss landscapes to indicate generalizability of a local minimum. While the reviewers agree that this paper contains interesting ideas and its presentation has been substantially improved during the discussion period, there are still issues that remain unanswered, in particular between the main objective/claims and the presented evidence. The paper will benefit from a revision and resubmission to another venue.
Decision: Reject