Title: INFORMATION-THEORETIC LOCAL MINIMA CHARAC-TERIZATION AND REGULARIZATION

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.

1. INTRODUCTION:

Recently, there has been a surge in the interest of acquiring a theoretical understanding over deep neural network's behavior. Breakthroughs have been made in characterizing the optimization process, showing that learning algorithms such as 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 et al., 2018) . However, these numerically similar local minima typically exhibit very different behaviors in terms of generalizability. It 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; 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 or 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 et al., 2017; Hoffer et al., 2017; Neyshabur et 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 metrics, (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 answer 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 propose 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 effectiveness of the metric as a 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 on image classification datasets demonstrate that our approach gives consistent generalization boost for a range of DNN architectures.

2. RELATED WORK:

It 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 effectively improves generalization for large-batch training, a specific metric that indicates the generalizability 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-guided SGD that achieves faster convergence in training DNNs. However, the method does not consistently improve generalization, e.g., a decrease of performance on CIFAR-10 ( Krizhevsky & Hinton, 2009) . Another method that focused on modifying the optimization process is the Path-SGD proposed by Neyshabur et al. (2015a) . Specifically, the authors derived an approximate steepest descent algorithm that utilizes the path-wise norm regularization 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-parametrized 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 attraction 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 a "robustness" metric, Sokolić et al. (2017) derived a regularization technique that successfully 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 minima obtained by varying the coefficient of L2 regularization. It 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 a regularizer. A generalization bound is missing in MacKay (1992) as well.

In a broader context of the "what" question, properties that capture the generalization of neural networks 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 et 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 to 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 rate. Also an information-theoretic approach, Sun & Nielsen (2019) derived a novel formulation of the minimum description length in the context of deep learning by utilizing tools from singular semi-Riemannian geometry.

3. OUTLINE AND NOTATIONS:

In a typical K-way classification setting, each sample x ∈ X belongs to a single class denoted c x ∈ {0, 1, ..., K} according to the probability vector y ∈ Y, where Y is the k-dimensional probability simplex so that p(c x = i) = y i and i y i = 1. Denote a feed-forward DNN parametrized by w ∈ R W as f w : X → Y, which uses nonlinear activation functions and a softmax layer at the end. Denote the cross entropy loss as (f w (x), y) =i y i ln f w (x) i . De-note the training set as S, defined over X × Y with |S|= N . The training objective is given as L(S, w) = 1 N (x,y)∼S (f w (x), y). Assume S is sampled from some true data distribution denoted D, we can define expected loss L(D, w) = E(x,y)∼D[ (f w (x), y)]. Throughout this paper, we refer a local minimum of L(S, w) corresponding to a local minimizer w 0 as just the local minimum w 0 . Given such w 0 , our paper's outline as well as our main achievements are:

• In Section 4 we relates Fisher information to neural network training as a prerequisite.

• In Section 5.1 we propose a metric γ(w 0 ) that well captures local minima's generalizability.

• In Section 5.2 we provide a generalization bound related to γ(w 0 ).

• In Section 5.3 we propose an approximation γ(w 0 ) for γ(w 0 ), which is shown to be very effective in Section 7.1 via extensive empirical evaluations. We define x (w) ∈ R K whose i th entry is -ln f w (x) i so that (f w (x), y) = x (w) T y. We define ȳ as argmax(y) and ỹ ∈ R K the one-hot vector whose ȳ-th entry is 1 and otherwise 0. Then we define L(S, w) ∈ R N as the "simplified" loss vector of S whose entries are (f w (x), ỹ) for (x, y) ∈ S, i.e., we approximate the cross entropy loss (f w (x), y) by (f w (x), ỹ).

4. LOCAL MINIMUM AND FISHER INFORMATION:

First of all, if y is strictly one-hot, no 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, we assume the widely used label smoothing (Szegedy et al., 2016) is applied to train all models in our analysis. Label smoothing enables us to assume a local minimum w 0 (in this case, also a global minimum) of the training loss with (x,y)∈S D KL (f w0 (x) y) = 0.

Each sample (x, y) ∈ S has its label c x sampled by p(c x = i|x) = y i , denoted as (x, c x ) ∼ S. The joint probability p(x, c x ) modeled by the DNN is p(x, c x = i; w) = p(c x = i|x; w) p(x) = [f w (x)] i p(x) with p(x) = 1 N . We can relate the training loss L(S, w) to the negative log-likelihood -S (w) = -(x,y)∈S E cx∼y ln p(x, c x ; w) by:

L(S, w) = 1 N (x,y)∈S x (w) T y = - 1 N (x,y)∈S E cx∼y ln p(c x |x; w) = - 1 N S (w) + ln 1 N

And so w 0 also corresponds to a local maximum of the likelihood function. The observed Fisher information evaluated at w 0 is defined as I(w 0 ) = -1 N ∇ 2 w S (w 0 ). We can further derive:

EQUATION

The first equality is straightforward; the second has its proof in Appendix A. Since p(c x = i|x) = y i and ln p(c x = i|x; w 0 ) = [ x (w 0 )] i , we can further simplify the Equation 1 to:

EQUATION

Remark: When we assume global optimality, we have ∇ w (f w0 (x), y) = 0 as D KL (f w0 (x) y) = 0; yet it does not indicate I(w 0 ) ∈ R W ×W = 0 in Equation 2.

5. LOCAL MINIMA CHARACTERIZATION:

In this section, we derive and propose our metric, provide a PAC-Bayes generalization bound, and lastly, propose and give intuitions of an effective approximation of our metric for modern DNNs.

5.1. FISHER DETERMINANT AS GENERALIZATION METRIC:

We would like a metric to compare different local minima. Similar to the various definitions of "flatness/sharpness", we take a small neighborhood of the target local minimum w 0 into account. Formally for a sufficiently small V , we define the model class M(w 0 ) as the largest connected subset of {w ∈ R W : L(S, w) ≤ h} that contains w 0 , where the height h is defined as a real number such that the volume (namely the Lebesgue measure) of M(w 0 ) is V . By the Intermediate Value Theorem, for any sufficiently small volume V there exists a corresponding height h.

We propose our metric γ(•), where lower γ(w 0 ) indicates a better local minimum w 0 :

EQUATION

As a metric, γ(w 0 ) requires |I(w 0 )| = 0. Therefore, we state the following Assumption 1. Assumption 1. The local minima w 0 we care about in the comparison are well isolated and unique in their corresponding neighborhood M(w 0 ).

The Assumption 1 is quite reasonable. For state-of-the-art network architectures used in practice, this is often the fact. To be precise, the Assumption 1 is violated when the Hessian matrix at a local minimum is 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 networks with scale-invariant activation functions, e.g. ReLU, referred as the rescaling issue. Namely, one can rescales the model parameters layer-wise so that the underlying function represented by 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 (Ioffe & 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 scaleinvariant. 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.

Note that normally we have a limited size of the dataset, and so an approximation of γ(w 0 ) is a 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 0 ) is closely related to the FIA criterion. From Information Theory, the MDL principle 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 a global minimum w 0 . The model class's FIA criterion is written as (lower FIA is better):

FIA = - (x,y)∈S E cx∼y ln p(x, c x ; w 0 ) + W 2 ln N 2π + ln M(w0) |I w | dw

On the right hand side, the first two terms are both constants. To see the connection to our metric, we replace the expected Fisher information I w with the tractable observed one I(w 0 ). Assuming the training loss is locally quadratic in M(w 0 ), an assumption later formalized and validated as Assumption 2, since I(w 0 ) = ∇ 2 w L(S, w 0 ) from Equation 1, we can modify the last term to be ln V + ln |I(w 0 )|.

Remark: Although in a 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/SHARPNESS METRICS:

As mentioned in Section 2, the "flatness" of a local minimum was firstly related to the generalization 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 a 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 is the first among these work that provides both the theoretical analysis including a generalization bound and the empirical verification of both an efficient metric and a practical regularizer for modern network architectures.

5.2. GENERALIZATION BOUND:

Assumption 2. Given the training loss L(S, w), its local minimum w 0 satisfying Assumption 1 and the associated neighborhood M(w 0 ) whose volume V is sufficiently small, as described in Section 3, 4 and 5.1, respectively, when confined to M(w 0 ), we assume that L(S, w) is quadratic.

The Assumption 2 is quite reasonable as well. Grünwald & Grunwald (2007) suggests that, a loglikelihood function, under regularity conditions (1) existence of its 1 st , 2 nd & 3 rd derivatives and (2) uniqueness of its maximum in the region, behaves locally like a quadratic function around its maximum. In our case, L(S, w) corresponds to the log-likelihood function S (w) and so w 0 corresponds to a local maximum of S (w). Since L(S, w) is analytic and w 0 is the only local minimum of L(S, w) in M(w 0 ), 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 (McAllester, 2003) to derive a generalization bound for our metric. Specifically, we pick a uniform prior P over w ∈ M(w 0 ) according to the maximum entropy principle and after observing the training data S pick the posterior Q of density q(w) ∝ e -|L(S,w0)-L(S,w)| . Then Theorem 1 bounds the expected L(D, w) using γ(w 0 ). 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 w 0 with L 0 = ∆ L(S, w 0 ), the volume V of M(w 0 ) sufficiently small, the Assumption 1 & 2 satisfied, and P, Q defined above, for any δ ∈ (0, 1], we have with probability at least 1 -δ that:

E w∼Q [L(D, w)] ≤ L 0 + A + 2 2L 0 + 2A + ln 2N δ N -1 , A = W V 2 W π 1 W e γ(w 0 )/W 4πe

In short, Theorem 1 shows that a lower γ(w 0 ) indicates a more generalizable local minimum w 0 .

5.3. APPROXIMATION:

As stated in Section 4, in practice an approximation of γ(w 0 ) as γ(w 0 ) is necessary, as calculating γ(w 0 ) involves computing the determinant of a W × W matrix. Let us first assume we have an imagined training set S of size W , a local minimum w 0 of L(S , w) and so correspondingly a fullrank observed Fisher information matrix I (w 0 ) so that ln|I (w 0 )| is well defined. In reality, we only have a training set S ⊂ S with a singular I(w 0 ). Notice that w 0 is also a local minimum of L(S, w) since (x,y)∈S D KL (f w0 (x) y) = 0 as assumed in Section 4. We then approximate eigenvalues of I (w 0 ) by those of its sub-matrices and so to approximate ln|I (w 0 )|.

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 L(S, w) ∈ R N and ȳ defined in Section 3.1, according to Equation 2, the observed Fisher information I (w 0 ) ∈ R W ×W is: In practice {λ n } N n=1 is inaccessible since we don't have I (w 0 ) in the first place. Instead, we sample S t ⊂ S with |S t |= N for T times and define

EQUATION

ξ t (w 0 ) = ∆ J w [ L(S t , w 0 )]J w [ L(S t , w 0 )] T ∈ R N ×N

Notice that ξ t (w 0 ) is a principal sub-matrix of W I (w 0 ) by removing rows & columns for data in S \ S t . According to Theorem 3, one can roughly estimate the size of eigenvalues of a matrix by those of its sub-matrices. Therefore we propose to estimate γ(w 0 ) by γ(w 0 ) with:

EQUATION

We leave Theorem 3 as well as the derivation of Equation 5to Appendix C. In proposing γ(w 0 ), we ignore the constants and irrelevant scaling factors because what matters is the relative size of γ(•) when comparing different local minima. Empirically we find that given relatively large number of sample trials T , our metric γ(•) can effectively capture the generalizability of a local minimum even for a small N (details in Section 7.1 and in Appendix D).

6. LOCAL MINIMA REGULARIZATION:

Besides pragmatism, devising a practical regularizer based on γ(w 0 ) also "verifies" our theoretical understanding of DNN training, helping for future improvement of the learning algorithms. However, converting γ(w 0 ) to a practical regularizer is non-trivial due to the computation burden of:

1. optimizing terms related to the gradient, which involves calculating the Hessian 2. computing the eigenvalues in each training step, which is even more expensive

We first solve the second issue and then the first one. To solve the second issue, we propose to optimize a surrogate term for γ(w 0 ) which avoids eigenvalue computations, namely the trace norm of the observed Fisher information tr(I(w 0 )). These two terms have the relation:

1 W γ(w 0 ) = 1 W ln|I(w 0 )| ≤ ln tr(I(w 0 )) -ln W

Another major benefit of using the trace norm is that, unlike γ(w 0 ), tr(I(w 0 )) still remains well defined even with a small training set |S|= N . From Equation 2we have:

tr(I(w 0 )) = 1 N (x,y)∈S K i=1 ∇ w [ x (w 0 )] i 2 2

The cost of computing tr(I(w 0 )) is linear in the number of its terms (in the double summation). We therefore simplify the calculation by replacing y with ỹ similar to Equation 4 so that

tr(I(w 0 )) ≈ 1 N (x,y)∈S ∇ w (f w0 (x), ỹ) 2 2 = 1 N N i=1 ∇ w [ L(S, w 0 )] i 2 2

where ỹ and L(•, •) are defined in Section 3.1. As in gradient-based training we never exactly reach the local minimum w 0 , we choose to optimize tr(I(w)) during the entire training process. We have ∇ w

1 |B| i ∇ w [ L(B, w 0 )] i 2 2 = 1 |B| i ∇ w ∇ w [ L(B, w 0 )] i 2 2

for each mini-batch B. Then we can further reduce the computation cost by batching. In specific, we randomly split B into M subbatches of equal size, namely {B i } M i=1 . We define

g i = ∆ 1 |Bi| (x,y)∈Bi (f w0 (x), ỹ) and compute g i 2 2 for g i ∈ {g i } M i=1 instead of computing [ L(B, w 0 )] i 2 2 for each data point in B.

We deal with the first computation burden by adopting first order approximation. For any w, with a sufficiently small α > 0 we have

L(B i , w -αg i ) ≈ L(B i , w) -J w [ L(B i , w)] αg i . Then 1 |B i | |Bi| j=1 [ L(B i , w) -L(B i , w -αg i )] j ≈ 1 |B i | |Bi| j=1 J w [ L(B i , w)] αg i j = α g i 2 2

Therefore, we propose to optimize the following regularized training objective for each update step:

L(B, w) + βR α (w), R α (w) = ∆ 1 M M i=1 1 |B i | |Bi| j=1 L(B i , w) -L(B i , w -αg i ) j (6)

We omit any second order term when computing ∇ w R α (w), simply by no back-prop through g i . On the other hand, we find that gradient clipping, especially at the beginning of the training, is necessary to make the generalization boost consistent. We have 4 hyper-parameters: α, β, the number of sub-batches M and the gradient clip threshold τ . Our approach is formalized as: 

Algorithm 1 Regularized Mini-batch

{B i } M i=1 ← B Split the mini-batch B into M sub-batches 3:

for i ← 1 to M do 4:

g i ← 1 |Bi| (x,y)∈Bi (f w0 (x), ỹ)

Compute the gradient of the sub-batch 5:

g i = copy(g i ) A copy prevents gradient flow 6:

end for 7:

Compute R α (w) by Equation 6Use the copied version of g i 8:

∇ w L reg ← ∇ w [L(B, w) + βR α (w)] 9:

Clip ∇ w L reg with threshold τ clip_by_global_norm in TensorFlow 10:

Gradient update with clipped ∇ w L reg Update with any gradient-based optimizer 11: end procedure

7. EXPERIMENTS:

We perform two sets of experiments to illustrate the effectiveness of our metric γ(w 0 ). We demonstrate that: (1) the approximation γ(w 0 ) captures the generalizability well across local minima; (2) our regularization technique based on γ(w 0 ) provides consistent generalization gain for DNNs.

Throughout our theoretical analysis, we 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 are 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 we used.

7.1. EXPERIMENTS ON LOCAL MINIMA CHARACTERIZATION:

We perform comprehensive evaluations to compare our metric γ(•) with several others on ResNet-20 (He et al., 2016a) for the CIFAR-10 dataset (architecture details in Appendix E). Our metric consistently outperforms others in indicating local minima's generalizability. Specifically, Sokolić et al. (2017) proposed a robustness-based metric used as a regularizer; Wu et al. (2017) proposed to use Frobenius norm of the Hessian as a metric; Keskar et al. (2017) proposed a metric closely 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".

• Robustness: 1 N (x,y)∈S J x [f w (x)] 2 2 • Frobenius norm: ∇ 2 w L(S, w) 2 F • Spectral radius: ρ(∇ 2 w L(S, w)) • Ours: γ(w) = 1 T T t=1 ln|ξ(S t , w 0 )|, S t ⊂ S

Both the Frobenius norm and the spectral radius based metric are related to ours, as from Equation 1we have ∇ 2 w L(S, w)

2 F = I(w)

2 F and ρ(∇ 2 w L(S, w)) = ρ(I(w)). These two metric, however, are too expensive to compute for the entire training set S; we instead calculate them by averaging the results for T sampled S t ⊂ S, similar to when we compute γ(w). We leave details of how we exactly compute these metrics in our experiments to Appendix D. We perform evaluations in three scenarios, similar to Neyshabur et al. (2017); Keskar et al. (2017) . We examine different local minima due to (1) a 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 a 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-zero training losses. We consider confusion size of 0, 1k, 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, denoted flip-only, random cropping from images with 1 pixel padded each side plus flipping, denoted 1-crop-f, random cropping with 4 pixels padded each side plus flipping, denoted 4-crop-f and no data augmentation at all, denoted 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-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). The results are 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 a better generalizable local minimum.

7.2. EXPERIMENTS ON LOCAL MINIMA REGULARIZATION:

We evaluate our regularizer on CIFAR-10 & CIFAR-100 for four different network architectures including a plain CNN, ResNet-20, Wide ResNet (Zagoruyko & Komodakis, 2016) and DenseNet (Huang et al., 2017) . We use WRN-28-2-B(3,3) 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 as CNN, ResNet, WRN and DenseNet, respectively.

We manually set α = 0.0001 in all experiments and select the other three hyper-parameters in Algorithm 1 by validation via a 45k/5k training data split for each of the network architecture on each dataset. In specific, we consider β ∈ {10, 20, 30, 40, 50, 75, 100, 125}, M ∈ {4, 8, 16} and τ ∈ {1, 5, 10, 15}. We keep all the other training 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 E. We train 5 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 a 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-art results. Our regularizer aims to find better "flatter" minima to improve generalization whereas adaptive optimization methods such as Adam (Kingma & Ba, 2014) and AdaGrad (Duchi et al., 2011) try to 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+Momentum. In specific, very similar to our setup, Keskar & Socher (2017) demonstrates that SGD+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 a sanity check to illustrate that the regularizer indeed induces better local minima characterized 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. Table 1 : Test error (%) for CIFAR-10 (1st row) and CIFAR-100 (2nd row). In general, a 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); so we ignore it in our experiments. 

8. CONCLUSION AND FUTURE WORK:

In this paper, we show a bridge between the field of deep learning theory and regularization methods 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 a generalization bound. We further derive an efficient approximation of the metric and devise a practical and effective regularizer from it. Empirical results demonstrate our success in both capturing and improving the generalizability of DNNs. Our exploration promises a direction for future work on the regularization and optimization of DNNs. 

A PROOF OF EQUATION 1:

To prove the second equality in Equation 1, it suffices to prove the following equality:

-∇ 2 w S (w) = (x,y)∈S K i=1 y i [∇ w ln p(c x = i|x; w)∇ w ln p(c x = i|x; w) T ]

For convenience, we change the notation of the local minimum from w 0 to w and further denote p(c x = i|x; w) as p x w (i). Since -∇ 2 w S (w) = -(x,y)∈S K i=1 y i ∇ 2 w ln p x w (i), for each (x, y) ∈ S and i ∈ {1, 2, ..., K}, we have:

[∇ 2 w ln p x w (i)] j,k = ∂ 2 ∂w j ∂w k ln p x w (i) = ∂ ∂w j ∂ ∂w k p x w (i) p x w (i) = p x w (i) ∂ 2 ∂wj ∂w k p x w (i) p x w (i) 2 - ∂ ∂wj p x w (i) p x w (i) ∂ ∂w k p x w (i) p x w (i) = ∂ 2 ∂wj ∂w k p x w (i) p x w (i) - ∂ ∂w j ln p x w (i) • ∂ ∂w k ln p x w (i)

Since w 0 is a local minimum (also a global minimum) described in Section 4 as y i = p x w (i) for i = 1, 2, ..., K, when taking the double summation, the first term above becomes:

(x,y)∈S K i=1 ∂ 2 ∂w j ∂w k p x w (i) = ∂ 2 ∂w j ∂w k (x,y)∈S K i=1 p x w (i) = ∂ 2 ∂w j ∂w k N = 0

Then it follows that: As e γ(w0) = |I(w 0 )|, we can rewrite the generalization bound we want to prove in Section 5.2 as:

EQUATION

(7) E w ∼Q [L(D, w)] ≤ L 0 + W • V 2/W π 1/W |I(w 0 )| 1/W 4πe + 2 W • V 2/W π 1/W |I(w 0 )| 1/W + 4πeL 0 + 2πe ln 2N δ 2πe(N -1)

As defined in Section 5.2, given the model class M(w 0 ), whose volume is V , for the neural network f w , the uniform prior P attains the probability density function p(w) = 1 V for any w ∈ M(w 0 ) and the posterior Q has density q(w) ∝ e -|L(S,w)-L0| . Based on Assumption 2 and the observed Fisher information I(w 0 ) derived in Section 4, especially the Equation 2, we have:

L(S, w) = L 0 + 1 2 (w -w 0 ) T I(w 0 )(w -w 0 ) ∀w ∈ M(w 0 ) Denote Σ = [I(w 0 )] -1 = [∇ 2 w L(S, w 0 )] -1 .

Then Q is a truncated multivariate Gaussian distribution whose density function q is:

EQUATION

Denote the denominator of Equation 8 as Z and define:

g(w; w 0 , Σ) = ∆ - 1 2 (w -w 0 ) T Σ -1 (w -w 0 )} ≤ 0

Then q can also be written as: q(w; w 0 , Σ) = exp{g(w; w 0 , Σ)} Z In order to derive a generalization bound in the form of the PAC-Bayes Theorem, it suffices to prove an upper bound of the KL divergence term:

D KL (Q||P) = E w∼Q ln q(w) p(w) = -E w∼Q ln 1 V + E w∼Q ln q(w) = ln V + E w∼Q g(w; w 0 , Σ) + ln 1 Z ≤ ln V + E w∼Q 0 -ln M(w0) exp{g(w; w 0 , Σ)} dw ≤ ln V -ln M(w0) exp{-max w∈M(w0) L(S, w)} dw = ln V -ln V • exp{-max w∈M(w0) L(S, w)} = ln V -ln V + h = h

where h is the height of M(w 0 ) defined in Section 5.1. For convenience, we shift down L(S, w) by L 0 and denote the shifted training loss L 0 (w) = ∆ L(S, w) -L 0 so that L 0 (w 0 ) = 0. Then

L 0 (w) = 1 2 (w -w 0 ) T Σ -1 (w -w 0 ) ∀w ∈ M(w 0 )

Furthermore, the following two sets are equivalent

{w ∈ R W : L(S, w) = h} = {w ∈ R W : L 0 (w) = h -L 0 }

both of which are the W -dimensional hyperellipsoid given by the equation L 0 (w) = h -L 0 , which can be converted to the standard form for hyperellipsoids as:

(w -w 0 ) T Σ -1 2(h -L 0 ) (w -w 0 ) = 1

The volume enclosed by this hyperellipsoid is exactly the volume of M(w 0 ), i.e., V ; so we have

π W/2 Γ( W 2 + 1) 2 W (h -L 0 ) W |Σ| = V

Solve for h, with the Stirling's approximation for factorial Γ(n + 1) ≈ √ 2πn n e n , we have

EQUATION

where Γ(•) denotes the Gamma function. Notice that for modern DNNs we have W 1, and so W W +1 W ≈ W . Then the generalization bound in the form of the PAC-Bayes Theorem is given as:

E w∼Q [L(D, w)] ≤ E w∼Q [L(S, w)] + 2 W • V 2/W π 1/W |I(w 0 )| 1/W + 4πeL 0 + 2πe ln 2N δ 2πe(N -1)

We can further bound the first term on the right hand side as:

E w∼Q [L(S, w)] ≤ E w∼Q [ max w∈M(w0) L(S, w)] = h

Putting it all together, we can finally obtain Equation 7.

C DERIVATION OF EQUATION 5:

First, let us present the well-known theorem in linear algebra that relates the eigenvalues of a matrix to those of its sub-matrices. Theorem 3. Given an n×n real symmetric matrix A with eigenvalues λ 1 ≤ ... ≤ λ n , for any k < n denote its principal sub-matrix as B obtained from removing n -k rows and columns from A. Let ν 1 ≤ ... ≤ ν k be the eigenvalues of B. Then for any 1 ≤ r ≤ k, we have λ r ≤ ν r ≤ λ r+n-k .

Let {ν n } N n=1 be the eigenvalues of 1 W ξ t (w 0 ), which is a N × N sub-matrix of I (w 0 ); then

γ(w 0 ) = 1 T T t=1 ln |ξ t (w 0 )| = 1 T T t=1 ln |W • 1 W ξ t (w 0 )| = N ln W + 1 T T t=1 N n=1 ln ν n

Theorem 2 gives the relation between ν n and λ n , defined above and in Section 5.3 as the n th smallest eigenvalues of 1 W ξ t (w 0 ) and that of I (w 0 ), respectively. For sufficiently large N , we can use ν n to approximate λ n . Ignoring the eigenvalues of I (w 0 ) larger than λ N is reasonable when estimating γ(w 0 ), since in general the majority of the eigenvalues of the Hessian for DNNs are close to zero with only a few large "outliers" (Pennington & Worah, 2018; Sagun et al., 2018) , and so the smallest eigenvalues are the dominant terms in γ(w 0 ). A specific bound of the eigenvalues remains an open question, though. In short, we have For the following metrics, we apply estimation by sampling a subset S t from the full training set S for T times and averaging the results:

• Frobenius norm: ∇ 2 w L(S, w) T 2

F:

Summing over the entire Hessian matrix is too expensive as there are W × W × N entries in total.

We therefore estimate the quantity by first sampling a subset S t ⊂ S and then sampling 100,000 entries of (∇ w [ x (w 0 )] ȳ )(∇ w [ x (w 0 )] ȳ ) T . We perform the T times and average the results, similar to the approach when computing γ(w).

Also by Equation 2 and the approximation in Equation 4, the spectral radius of Hessian is equivalent to the squared spectral norm of 1/ √ N J w [ L(S, w)]. We also perform estimation (with irrelevant scaling constants dropped) by sampling S t for T times, i.e., via 1 T t J w [ L(S t , w)] 2 2 . Furthermore, in all our experiments that involves samplings S t , we set |S t |= N = T = 100.

E ARCHITECTURE AND TRAINING DETAILS IN SECTION 7:

Architecture details are as below

• The plain CNN is a 6-layer convolutional neural network similar to the baseline in Lee et al. (2016) yet without the "mlpconv" layers (resulting in a 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 a 2 × 2 max pooling operation. After the last convolutional layer, we apply a global average pooling before the final softmax classifier. • 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 DenseNet-BC-k=12 we use the the architecture identical to the one used in the original paper.

The training details are

• For the plain CNN, we initialize the weights according to the scheme in He et al. (2016a) and apply l2 regularization of a coefficient 0.0001. We perform standard data augmentation, 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 use the same hyperparameters, training schemes, data augmentation schemes, optimization methods, etc., as those in their original papers, respectively.

:



Figures and Tables:

4)Let {λ m } W m=1 denote the eigenvalues of I (w 0 ); then γ(w 0 ) = lnW m=1 λ m = W m=1 ln λ m .Without calculating all W eigenvalues, we can perform a Monte-Carlo estimation of γ(w 0 ) by randomly sampling N < N < W eigenvalues from {λ m } W m=1 . We denote the samples as {λ n } λ m . Suppose the estimation is run T times, we have lim T λ n = γ(w 0 ).

For the confusion set experiments, we sample a new training set and a new confusion set every time. In all scenarios, we train the model for 200 epochs with an initial learning rate 0.1, divided by 10 whenever the training loss plateaus. Within each scenario, we 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.

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 ± 1 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.

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.

Figure 3: Scenario III: varied batch size. Large batch size leads to poor generalization, captured by all the metrics except for the robustness based one.

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 D and a loss function L(•, •) ∈ [0, 1], 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 C as its support, any posterior distribution Q over C (not necessarily Bayesian posterior), and for any δ ∈ (0, 1], we have with probability at least 1 -δ that: E w∼Q [L(D, w)] ≤ E w∼Q [L(S, w)] + 2 2D KL (Q||P) + ln 2N δ N -1

λ n = γ(w 0 ) D DETAILS OF CALCULATING THE METRICS IN SECTION 7.1

Spectral radius: ρ(∇ 2 w L(S, w))• Ours: γ(w) = 1 T T t=1 ln|ξ(S t , w 0 )|For the Frobenius norm based metric, from Equation 2 we have:[ x (w 0 )] i )(∇ w [ x (w 0 )] i ) T Similar to Equation4, we approximate y by ỹ and so∇ 2 w L(S, w) (∇ w [ x (w 0 )] ȳ )(∇ w [ x (w 0 )] ȳ )

J w [•] as Jacobian matrix, ∇ 2 w as Hessian, D KL (• •) as KL divergence, • 2 as spectrum or Euclidean norm, • F as Frobenius norm, |•| as determinant, tr(•) as trace norm, ρ(•) as spectral radius, S (w) as log-likelihood on S, and [•] i for selecting the i th entry.

Table content: <table><tr><td>• In Section 6 we devise a practical regularizer from γ(w 0 ) that consistently improves gen-</td></tr><tr><td>eralizability across different DNNs, as evaluated in Section 7.2.</td></tr><tr><td>3.1 OTHER NOTATIONS</td></tr><tr><td>Denote ∇ w as gradient,</td></tr></table>

Learning (Single Update Step)

Table content: <table/>

± 0.35 29.19 ± 0.21 25.52 ± 0.15 23.65 ± 0.14 22.54 ± 0.32 22.19 ± 0.28 --

Table content: <table><tr><td>CNN</td><td>CNN+reg</td><td>WRN</td><td>WRN+reg</td><td>DenseNet</td><td colspan="2">DenseNet+reg ResNet</td><td>ResNet+reg</td></tr><tr><td>8.52 ± 0.08</td><td>7.46 ± 0.13</td><td>5.44 ± 0.04</td><td>4.80 ± 0.10</td><td>4.61 ± 0.08</td><td>4.31 ± 0.08</td><td colspan="2">8.50 ± 0.31 7.91 ± 0.25</td></tr><tr><td>31.12</td><td/><td/><td/><td/><td/><td/></tr></table>

The proposed metric computed on local minima obained with or without applying the proposed regularizer. Each entry represents mean ± std. among 5 runs. Smaller values are bolded.

Table content: <table><tr><td>ResNet</td><td>WRN</td><td>DenseNet</td></tr><tr><td>w/o reg. -979.3 ± 22.3</td><td colspan="2">-737.6 ± 20.3 -850.3 ± 23.5</td></tr><tr><td colspan="3">with reg. -1138.1 ± 11.0 -804.8 ± 18.7 -886.2 ± 20.5</td></tr></table>

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://dx.doi.org/10.5244/C.30.87.

Table content: <table><tr><td>Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous</td></tr><tr><td>generalization bounds at the imagenet scale: a PAC-bayesian compression approach. In Interna-</td></tr><tr><td>tional Conference on Learning Representations, 2019. URL https://openreview.net/</td></tr><tr><td>forum?id=BJgqqsAct7.</td></tr></table>

Peer review (iclr2020):
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. Remarkably, 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). On 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. To 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. The 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. The reviewer has the following minor comments to further improve this contribution: section 5.1, explain the abbreviation FIA Regarding 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? According 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. As 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.