Year: 2019

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.

heading: 1 INTRODUCTION
text: 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; Sokolić 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.

heading: 2 RELATED WORK
text: 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, Sokolić 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; Sokolić 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.

heading: 3 OUTLINE AND NOTATIONS
text: In a typical K-way classification setting, each sample x ∈ X belongs to a single class denoted cx ∈ {0, 1, ...,K} according to the probability vector y ∈ Y , where Y is the k-dimensional probability simplex so that p(cx = i) = yi and ∑ i yi = 1. Denote a feed-forward DNN parametrized by w ∈ RW as fw : X → Y , which uses nonlinear activation functions and a softmax layer at the end. Denote the cross entropy loss as `(fw(x), y) = − ∑ i yi ln fw(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) = 1N ∑ (x,y)∼S `(fw(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[`(fw(x), y)]. Throughout this paper, we refer a local minimum of L(S, w) corresponding to a local minimizer w0 as just the local minimum w0. Given such w0, 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 γ(w0) that well captures local minima’s generalizability. • In Section 5.2 we provide a generalization bound related to γ(w0). • In Section 5.3 we propose an approximation γ̂(w0) for γ(w0), which is shown to be very
effective in Section 7.1 via extensive empirical evaluations. • In Section 6 we devise a practical regularizer from γ(w0) that consistently improves gen-
eralizability across different DNNs, as evaluated in Section 7.2.

heading: 3.1 OTHER NOTATIONS
text: Denote∇w as gradient, Jw[·] as Jacobian matrix,∇2w as Hessian, DKL(·‖·) 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 ith entry. We define `x(w) ∈ RK whose ith entry is− ln fw(x)i so that `(fw(x), y) = `x(w)T y. We define ȳ as argmax(y) and ỹ ∈ RK the one-hot vector whose ȳ-th entry is 1 and otherwise 0. Then we define L̃(S, w) ∈ RN as the “simplified” loss vector of S whose entries are `(fw(x), ỹ) for (x, y) ∈ S , i.e., we approximate the cross entropy loss `(fw(x), y) by `(fw(x), ỹ).

heading: 4 LOCAL MINIMUM AND FISHER INFORMATION
text: 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 w0 (in this case, also a global minimum) of the training loss with ∑ (x,y)∈S DKL(fw0(x)‖y) = 0.
Each sample (x, y) ∈ S has its label cx sampled by p(cx = i|x) = yi, denoted as (x, cx) ∼ S. The joint probability p(x, cx) modeled by the DNN is p(x, cx = i;w) = p(cx = i|x;w) p(x) = [fw(x)]i p(x) with p(x) = 1N . We can relate the training loss L(S, w) to the negative log-likelihood −``S(w) = − ∑ (x,y)∈S Ecx∼y ln p(x, cx;w) by:
L(S, w) = 1 N ∑ (x,y)∈S `x(w) T y = − 1 N ∑ (x,y)∈S E cx∼y ln p(cx|x;w) = − 1 N ``S(w) + ln 1 N
And so w0 also corresponds to a local maximum of the likelihood function. The observed Fisher information evaluated at w0 is defined as I(w0) = − 1N∇ 2 w``S(w0). We can further derive:
I(w0) = ∇2wL(S, w0) = E (x,cx)∼S [∇w ln p(cx|x;w0)∇w ln p(cx|x;w0)T ] (1)
The first equality is straightforward; the second has its proof in Appendix A. Since p(cx = i|x) = yi and ln p(cx = i|x;w0) = [`x(w0)]i, we can further simplify the Equation 1 to:
I(w0) = 1
N ∑ (x,y)∈S K∑ i=1 ( ∇w[`x(w0)]i )( ∇w[`x(w0)]i )T (2)
Remark: When we assume global optimality, we have ∇w`(fw0(x), y) = 0 as DKL(fw0(x)‖y) = 0; yet it does not indicate I(w0) ∈ RW×W 6= 0 in Equation 2.

heading: 5 LOCAL MINIMA CHARACTERIZATION
text: 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.

heading: 5.1 FISHER DETERMINANT AS GENERALIZATION METRIC
text: 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 w0 into account. Formally for a sufficiently small V , we define the model class M(w0) as the largest connected subset of {w ∈ RW : L(S, w) ≤ h} that contains w0, where the height h is defined as a real number such that the volume (namely the Lebesgue measure) ofM(w0) 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 γ(w0) indicates a better local minimum w0:
γ(w0) = ln|I(w0)| (3)
As a metric, γ(w0) requires |I(w0)| 6= 0. Therefore, we state the following Assumption 1. Assumption 1. The local minima w0 we care about in the comparison are well isolated and unique in their corresponding neighborhoodM(w0).
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 γ(w0) is a must. We present our approximation scheme and its intuition in Section 5.3.

heading: 5.1.1 CONNECTION TO FISHER INFORMATION APPROXIMATION (FIA) CRITERION
text: Our metric γ(w0) 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 w0. The model class’s FIA criterion is written as (lower FIA is better):
FIA = − ∑
(x,y)∈S E cx∼y ln p(x, cx;w0) +
W 2 ln N 2π + ln ∫ M(w0) √ |Iw| 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 Iw with the tractable observed one I(w0). Assuming the training loss is locally quadratic in M(w0), an assumption later formalized and validated as Assumption 2, since I(w0) = ∇2wL(S, w0) from Equation 1, we can modify the last term to be lnV + ln √ |I(w0)|.
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.

heading: 5.2 GENERALIZATION BOUND
text: Assumption 2. Given the training loss L(S, w), its local minimum w0 satisfying Assumption 1 and the associated neighborhoodM(w0) whose volume V is sufficiently small, as described in Section 3, 4 and 5.1, respectively, when confined toM(w0), we assume that L(S, w) is quadratic.
The Assumption 2 is quite reasonable as well. Grünwald & Grunwald (2007) suggests that, a loglikelihood function, under regularity conditions (1) existence of its 1st, 2nd & 3rd 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 w0 corresponds to a local maximum of ``S(w). Since L(S, w) is analytic and w0 is the only local minimum of L(S, w) inM(w0), 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(w0) 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 γ(w0). 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 w0 with L0 =∆ L(S, w0), the volume V of M(w0) 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)] ≤ L0 +A+ 2
√ 2L0 + 2A+ ln 2Nδ
N − 1 , A = WV
2 W π 1 W eγ(w0)/W
4πe
In short, Theorem 1 shows that a lower γ(w0) indicates a more generalizable local minimum w0.

heading: 5.3 APPROXIMATION
text: As stated in Section 4, in practice an approximation of γ(w0) as γ̂(w0) is necessary, as calculating γ(w0) 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 w0 of L(S ′, w) and so correspondingly a fullrank observed Fisher information matrix I ′(w0) so that ln|I ′(w0)| is well defined. In reality, we only have a training set S ⊂ S ′ with a singular I(w0). Notice that w0 is also a local minimum of L(S, w) since ∑ (x,y)∈S′ DKL(fw0(x)‖y) = 0 as assumed in Section 4. We then approximate eigenvalues of I ′(w0) by those of its sub-matrices and so to approximate ln|I ′(w0)|. First of all, we replace y by its one-hot version ỹ defined in Section 3.1 since they are very close. This drastically reduces the cost of gradient calculation. With L̃(S, w) ∈ RN and ȳ defined in Section 3.1, according to Equation 2, the observed Fisher information I ′(w0) ∈ RW×W is:
I ′(w0) ≈ 1
W ∑ (x,y)∈S′ ( ∇w[`x(w0)]ȳ )( ∇w[`x(w0)]ȳ )T = 1
W Jw[L̃(S ′, w)]TJw[L̃(S ′, w)] =
1
W Jw[L̃(S ′, w)] Jw[L̃(S ′, w)]T (4)
Let {λm}Wm=1 denote the eigenvalues of I ′(w0); then γ(w0) = ln ∏W m=1 λm = ∑W m=1 lnλm. Without calculating all W eigenvalues, we can perform a Monte-Carlo estimation of γ(w0) by
randomly samplingN ′ < N < W eigenvalues from {λm}Wm=1. We denote the samples as {λn}N ′ n=1 and we have WN ′ ∑N ′ n=1 lnλn ≈ ∑W m=1 lnλm. Suppose the estimation is run T times, we have limT→∞ 1 T ∑T t=1 W N ′ ∑N ′ n=1 lnλn = γ(w0).
In practice {λn}N ′ n=1 is inaccessible since we don’t have I ′(w0) in the first place. Instead, we sample St ⊂ S with |St|= N ′ for T times and define
ξt(w0) = ∆ Jw[L̃(St, w0)]Jw[L̃(St, w0)]T ∈ RN
′×N ′
Notice that ξt(w0) is a principal sub-matrix of WI ′(w0) by removing rows & columns for data in S \ St. 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 γ(w0) by γ̂(w0) with:
γ̂(w0) = ∆ 1
T T∑ t=1 ln |ξt(w0)|, γ(w0) ≈ W N ′ γ̂(w0) +W ln 1 W as T →∞ (5)
We leave Theorem 3 as well as the derivation of Equation 5 to Appendix C. In proposing γ̂(w0), 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).

heading: 6 LOCAL MINIMA REGULARIZATION
text: Besides pragmatism, devising a practical regularizer based on γ(w0) also “verifies” our theoretical understanding of DNN training, helping for future improvement of the learning algorithms. However, converting γ(w0) 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 γ(w0) which avoids eigenvalue computations, namely the trace norm of the observed Fisher information tr(I(w0)). These two terms have the relation:
1
W γ(w0) =
1
W ln|I(w0)| ≤ ln tr(I(w0))− lnW
Another major benefit of using the trace norm is that, unlike γ(w0), tr(I(w0)) still remains well defined even with a small training set |S|= N . From Equation 2 we have:
tr(I(w0)) = 1
N ∑ (x,y)∈S K∑ i=1 ‖∇w[`x(w0)]i‖22
The cost of computing tr(I(w0)) is linear in the number of its terms (in the double summation). We therefore simplify the calculation by replacing y with ỹ similar to Equation 4 so that
tr(I(w0)) ≈ 1
N ∑ (x,y)∈S ‖∇w`(fw0(x), ỹ)‖ 2 2 = 1 N N∑ i=1 ‖∇w[L̃(S, w0)]i‖22
where ỹ and L̃(·, ·) are defined in Section 3.1. As in gradient-based training we never exactly reach the local minimum w0, we choose to optimize tr(I(w)) during the entire training process. We have ∇w 1|B| ∑ i ‖∇w[L̃(B, w0)]i‖ 2 2 = 1 |B| ∑ i∇w‖∇w[L̃(B, w0)]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 {Bi}Mi=1. We define gi = ∆ 1 |Bi| ∑ (x,y)∈Bi `(fw0(x), ỹ) and compute ‖gi‖22 for gi ∈ {gi}Mi=1 instead of computing ‖[L̃(B, w0)]i‖22 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̃(Bi, w − αgi) ≈ L̃(Bi, w)− Jw[L̃(Bi, w)] αgi. Then
1
|Bi| |Bi|∑ j=1 [L̃(Bi, w)− L̃(Bi, w − αgi)]j ≈ 1 |Bi| |Bi|∑ j=1 [ Jw[L̃(Bi, w)] αgi ] j = α‖gi‖22
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 |Bi| |Bi|∑ j=1 [ L̃(Bi, w)− L̃(Bi, w − αgi) ] j
(6)
We omit any second order term when computing ∇wRα(w), simply by no back-prop through gi. 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 Learning (Single Update Step) 1: procedure UPDATE(w,B; α, β,M, τ ) . Last 4 are hyper-parameters 2: {Bi}Mi=1 ← B . Split the mini-batch B into M sub-batches 3: for i← 1 to M do 4: gi ← 1|Bi| ∑ (x,y)∈Bi `(fw0(x), ỹ) . Compute the gradient of the sub-batch
5: gi = copy(gi) . A copy prevents gradient flow 6: end for 7: ComputeRα(w) by Equation 6 . Use the copied version of gi 8: ∇wLreg ← ∇w[L(B, w) + βRα(w)] 9: Clip∇wLreg with threshold τ . clip_by_global_norm in TensorFlow 10: Gradient update with clipped∇wLreg . Update with any gradient-based optimizer 11: end procedure

heading: 7 EXPERIMENTS
text: We perform two sets of experiments to illustrate the effectiveness of our metric γ(w0). We demonstrate that: (1) the approximation γ̂(w0) captures the generalizability well across local minima; (2) our regularization technique based on γ(w0) 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.

heading: 7.1 EXPERIMENTS ON LOCAL MINIMA CHARACTERIZATION
text: We perform comprehensive evaluations to compare our metric γ̂(·) with several others on ResNet20 (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, Sokolić 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: 1N ∑ (x,y)∈S ‖Jx[fw(x)]‖ 2 2
• Frobenius norm: ‖∇2wL(S, w)‖ 2 F
• Spectral radius: ρ(∇2wL(S, w)) • Ours: γ̂(w) = 1T ∑T t=1 ln|ξ(St, w0)|, St ⊂ S
Both the Frobenius norm and the spectral radius based metric are related to ours, as from Equation 1 we have ‖∇2wL(S, w)‖ 2 F = ‖I(w)‖ 2 F and ρ(∇2wL(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 St ⊂ 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). 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.
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.

heading: 7.2 EXPERIMENTS ON LOCAL MINIMA REGULARIZATION
text: 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 DenseNetBC-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.

heading: 7.2.1 THE CHOICE OF THE OPTIMIZER
text: 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.

heading: 7.2.2 GENERALIZATION BOOST AS A RESULT OF BETTER LOCAL MINIMA
text: 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.

heading: 8 CONCLUSION AND FUTURE WORK
text: 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.

heading: A PROOF OF EQUATION 1
text: To prove the second equality in Equation 1, it suffices to prove the following equality:
−∇2w``S(w) = ∑
(x,y)∈S K∑ i=1 yi[∇w ln p(cx = i|x;w)∇w ln p(cx = i|x;w)T ]
For convenience, we change the notation of the local minimum from w0 to w and further denote p(cx = i|x;w) as pxw(i). Since−∇2w``S(w) = − ∑ (x,y)∈S ∑K i=1 yi ∇2w ln pxw(i), for each (x, y) ∈ S and i ∈ {1, 2, ...,K}, we have:
[∇2w ln pxw(i)]j,k = ∂2
∂wj∂wk ln pxw(i)
= ∂
∂wj
( ∂ ∂wk pxw(i)
pxw(i)
)
= pxw(i)
∂2
∂wj∂wk pxw(i) pxw(i) 2 − ∂ ∂wj pxw(i) pxw(i) ∂ ∂wk pxw(i) pxw(i)
=
∂2
∂wj∂wk pxw(i)
pxw(i) − ∂ ∂wj ln pxw(i) · ∂ ∂wk ln pxw(i)
Since w0 is a local minimum (also a global minimum) described in Section 4 as yi = pxw(i) for i = 1, 2, ...,K, when taking the double summation, the first term above becomes:
∑ (x,y)∈S K∑ i=1
∂2
∂wj∂wk pxw(i) =
∂2
∂wj∂wk ∑ (x,y)∈S K∑ i=1 pxw(i) = ∂2 ∂wj∂wk N = 0
Then it follows that:
[∇2w``S(w)]j,k = − ∑
(x,y)∈S K∑ i=1 yi[∇w ln pxw(i)∇w ln pxw(i)T ]j,k

heading: B PROOF OF THE GENERALIZATION BOUND IN SECTION 5.2
text: 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
√ 2DKL(Q||P) + ln 2Nδ
N − 1
As eγ(w0) = |I(w0)|, we can rewrite the generalization bound we want to prove in Section 5.2 as:
(7) E w ∼Q [L(D, w)] ≤ L0 +
W · V 2/Wπ1/W |I(w0)|1/W
4πe
+ 2
√ W · V 2/Wπ1/W |I(w0)|1/W + 4πeL0 + 2πe ln 2Nδ
2πe(N − 1)
As defined in Section 5.2, given the model classM(w0), whose volume is V , for the neural network fw, the uniform prior P attains the probability density function p(w) = 1V for any w ∈ M(w0) and the posterior Q has density q(w) ∝ e−|L(S,w)−L0|. Based on Assumption 2 and the observed Fisher information I(w0) derived in Section 4, especially the Equation 2, we have:
L(S, w) = L0 + 1
2 (w − w0)TI(w0)(w − w0) ∀w ∈M(w0)
Denote Σ = [I(w0)]−1 = [∇2wL(S, w0)]−1. Then Q is a truncated multivariate Gaussian distribution whose density function q is:
q(w;w0,Σ) =
√ (2π)−n|Σ|−1 exp{− 12 (w − w0)
TΣ−1(w − w0)}∫ M(w0) √ (2π)−n|Σ|−1 exp{− 12 (w − w0)TΣ−1(w − w0)} dw
= exp{− 12 (w − w0) TΣ−1(w − w0)}∫ M(w0) exp{− 1 2 (w − w0)TΣ−1(w − w0)} dw
(8)
Denote the denominator of Equation 8 as Z and define:
g(w;w0,Σ) = ∆ −1
2 (w − w0)TΣ−1(w − w0)} ≤ 0
Then q can also be written as:
q(w;w0,Σ) = exp{g(w;w0,Σ)}
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:
DKL(Q||P) = E w∼Q
ln q(w)
p(w)
= − E w∼Q
ln 1
V + E w∼Q ln q(w)
= lnV + E w∼Q
g(w;w0,Σ) + ln 1
Z
≤ lnV + E w∼Q 0− ln (∫ M(w0) exp{g(w;w0,Σ)} dw )
≤ lnV − ln (∫ M(w0) exp{− max w∈M(w0) L(S, w)} dw )
= lnV − ln ( V · exp{− max
w∈M(w0) L(S, w)} ) = lnV − lnV + h = h
where h is the height ofM(w0) defined in Section 5.1. For convenience, we shift down L(S, w) by L0 and denote the shifted training loss L0(w) =∆ L(S, w)− L0 so that L0(w0) = 0. Then
L0(w) = 1
2 (w − w0)TΣ−1(w − w0) ∀w ∈M(w0)
Furthermore, the following two sets are equivalent
{w ∈ RW : L(S, w) = h} = {w ∈ RW : L0(w) = h− L0}
both of which are the W -dimensional hyperellipsoid given by the equation L0(w) = h−L0, which can be converted to the standard form for hyperellipsoids as:
(w − w0)T Σ−1
2(h− L0) (w − w0) = 1
The volume enclosed by this hyperellipsoid is exactly the volume ofM(w0), i.e., V ; so we have πW/2
Γ(W2 + 1)
√ 2W (h− L0)W |Σ| = V
Solve for h, with the Stirling’s approximation for factorial Γ(n+ 1) ≈ √ 2πn (n e )n , we have
h = L0 + (V · Γ(W2 + 1))
2/W
2π|Σ|1/W ≈ L0 +
V 2/Wπ1/WW (W+1)/W |I(w0)|1/W
4πe
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(w0)|1/W + 4πeL0 + 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.

heading: C DERIVATION OF EQUATION 5
text: 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(w0), which is a N ′ ×N ′ sub-matrix of I ′(w0); then
γ̂(w0) = 1
T T∑ t=1 ln |ξt(w0)| = 1 T T∑ t=1 ln |W · 1 W ξt(w0)| = N ′ lnW + 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 nth smallest eigenvalues of 1W ξ
t(w0) and that of I ′(w0), respectively. For sufficiently largeN ′, we can use νn to approximate λn. Ignoring the eigenvalues of I ′(w0) larger than λN ′ is reasonable when estimating γ(w0), 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 γ(w0). A specific bound of the eigenvalues remains an open question, though. In short, we have ∑N ′ n=1 νn ≈ ∑N ′ n=1 λ ′ n and consequently:
W N ′ γ̂(w0) +W ln 1 W = W N ′ γ̂(w0)−W lnW
= W
N ′
( γ̂(w0)−N ′ lnW ) = 1
T T∑ t=1 W N ′ N ′∑ n=1 ln νn
≈ 1 T T∑ t=1 W N ′ N ′∑ n=1 lnλ′n
Finally we we have
lim T→∞
1
T T∑ t=1 W N ′ N ′∑ n=1 lnλ′n = γ(w0)

heading: D DETAILS OF CALCULATING THE METRICS IN SECTION 7.1
text: For the following metrics, we apply estimation by sampling a subset St from the full training set S for T times and averaging the results:
• Frobenius norm: ‖∇2wL(S, w)‖ 2 F
• Spectral radius: ρ(∇2wL(S, w)) • Ours: γ̂(w) = 1T ∑T t=1 ln|ξ(St, w0)|
For the Frobenius norm based metric, from Equation 2 we have:
‖∇2wL(S, w)‖ 2 F = ‖I(w)‖ 2 F =
1
N ∑ (x,y)∈S K∑ i=1 ∥∥∥(∇w[`x(w0)]i)(∇w[`x(w0)]i)T∥∥∥2 F
Similar to Equation 4, we approximate y by ỹ and so
‖∇2wL(S, w)‖ 2 F ≈
1
N ∑ (x,y)∈S ∥∥∥(∇w[`x(w0)]ȳ)(∇w[`x(w0)]ȳ)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 St ⊂ S and then sampling 100,000 entries of (∇w[`x(w0)]ȳ)(∇w[`x(w0)]ȳ)T . We perform the estimation 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/ √ NJw[L̃(S, w)]. We also perform estimation (with irrelevant
scaling constants dropped) by sampling St for T times, i.e., via 1T ∑ t ‖Jw[L̃(St, w)]‖ 2 2.
Furthermore, in all our experiments that involves samplings St, we set |St|= N ′ = T = 100.

heading: E ARCHITECTURE AND TRAINING DETAILS IN SECTION 7
text: 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.

Review summaries:
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.

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.