Year: 2018

Abstract:
Understanding the behavior of stochastic gradient descent (SGD) in the context of deep neural networks has raised lots of concerns recently. Along this line, we theoretically study a general form of gradient based optimization dynamics with unbiased noise, which unifies SGD and standard Langevin dynamics. Through investigating this general optimization dynamics, we analyze the behavior of SGD on escaping from minima and its regularization effects. A novel indicator is derived to characterize the efficiency of escaping from minima through measuring the alignment of noise covariance and the curvature of loss function. Based on this indicator, two conditions are established to show which type of noise structure is superior to isotropic noise in term of escaping efficiency. We further show that the anisotropic noise in SGD satisfies the two conditions, and thus helps to escape from sharp and poor minima effectively, towards more stable and flat minima that typically generalize well. We verify our understanding through comparing this anisotropic diffusion with full gradient descent plus isotropic diffusion (i.e. Langevin dynamics) and other types of position-dependent noise.

heading: 1 INTRODUCTION
text: As a successful learning algorithm, stochastic gradient descent (SGD) was originally adopted for dealing with the computational bottleneck of training neural networks with large-scale datasets (Bottou, 1991). Its empirical efficiency and effectiveness have attracted lots of attention. And thus, SGD and its variants have become standard workhorse for learning deep models. Besides the aspect of empirical efficiency, recently, researchers started to analyze the optimization behaviors of SGD and its impacts on generalization.
The optimization properties of SGD have been studied from various perspectives. The convergence behaviors of SGD for simple one hidden layer neural networks were investigated in (Li & Yuan, 2017; Brutzkus et al., 2017). In non-convex settings, the characterization of how SGD escapes from stationary points, including saddle points and local minima, was analyzed in (Daneshmand et al., 2018; Jin et al., 2017; Hu et al., 2017).
On the other hand, in the context of deep learning, researchers realized that the noise introduced by SGD impacts the generalization, thanks to the research on the phenomenon that training with a large batch could cause a significant drop of test accuracy (Keskar et al., 2017). Particularly, several works attempted to investigate how the magnitude of the noise influences the generalization during the process of SGD optimization, including the batch size and learning rate (Hoffer et al., 2017; Goyal et al., 2017; Chaudhari & Soatto, 2017; Jastrzębski et al., 2017). Another line of research interpreted SGD from a Bayesian perspective. In (Mandt et al., 2017; Chaudhari & Soatto, 2017), SGD was interpreted as performing variational inference, where certain entropic regularization involves to prevent overfitting. And the work (Smith & Le, 2018) tried to provide an understanding based on model evidence. These explanations are compatible with the flat/sharp minima argument (Hochreiter & Schmidhuber, 1997; Keskar et al., 2017), since Bayesian inference tends to targeting the region with large probability mass, corresponding to the flat minima.
However, when analyzing the optimization behavior and regularization effects of SGD, most of existing works only assume the noise covariance of SGD is constant or upper bounded by some
constant, and what role the noise structure of stochastic gradient plays in optimization and generalization was rarely discussed in literature.
In this work, we theoretically study a general form of gradient-based optimization dynamics with unbiased noise, which unifies SGD and standard Langevin dynamics. By investigating this general dynamics, we analyze how the noise structure of SGD influences the escaping behavior from minima and its regularization effects. Several novel theoretical results and empirical justifications are made.
1. We derive a key indicator to characterize the efficiency of escaping from minima through measuring the alignment of noise covariance and the curvature of loss function. Based on this indicator, two conditions are established to show which type of noise structure is superior to isotropic noise in term of escaping efficiency;
2. We further justify that SGD in the context of deep neural networks satisfies these two conditions, and thus provide a plausible explanation why SGD can escape from sharp minima more efficiently, converging to flat minima with a higher probability. Moreover, these flat minima typically generalize well according to various works (Hochreiter & Schmidhuber, 1997; Keskar et al., 2017; Neyshabur et al., 2017; Wu et al., 2017). We also show that Langevin dynamics with well tuned isotropic noise cannot beat SGD, which further confirms the importance of noise structure of SGD;
3. A large number of experiments are designed systematically to justify our understanding on the behavior of the anisotropic diffusion of SGD. We compare SGD with full gradient descent with different types of diffusion noise, including isotropic and positiondependent/independent noise. All these comparisons demonstrate the effectiveness of anisotropic diffusion for good generalization in training deep networks.
The remaining of the paper is organized as follows. In Section 2, we introduce the background of SGD and a general form of optimization dynamics of interest. We then theoretically study the behaviors of escaping from minima in Ornstein-Uhlenbeck process in Section 3, and establish two conditions for characterizing the noise structure that affects the escaping efficiency. In Section 4, we show that the noise of SGD in the context of deep learning meets the two conditions, and thus explains its superior efficiency of escaping from sharp minima over other dynamics with isotropic noise. Various experiments are conducted for verifying our understanding in Section 5, and we conclude the paper in Section 6.

heading: 2 BACKGROUND
text: In general, supervised learning usually involves an optimization process of minimizing an empirical loss over training data, L(θ) := 1/N ∑N i=1 `(f(xi; θ), yi), where {(xi, yi)}Ni=1 denotes the training set with N i.i.d. samples, the prediction function f is often parameterized by θ ∈ RD, such as deep neural networks. And `(·, ·) is the loss function, such as mean squared error and cross entropy, typically corresponding to certain negative log likelihood. Due to the over parameterization and non-convexity of the loss function in deep networks, there exist multiple global minima, exhibiting diverse generalization performance. We call those solutions generalizing well good solutions or minima, and vice versa.
Gradient descent and its stochastic variants A typical approach to minimize the loss function is gradient descent (GD), the dynamics of which in each iteration t is, θt+1 = θt − ηtg0(θt), where g0(θt) = ∇θL(θt) denotes the full gradient and ηt denotes the learning rate. In non-convex optimization, a more useful kind of gradient based optimizers act like GD with an unbiased noise, including gradient Langevin dynamics (GLD), θt+1 = θt − ηtg0(θt) + σt t, t ∼ N (0, I), and stochastic gradient descent (SGD), during each iteration t of which, a minibatch of training samples with size m are randomly selected, with index set Bt ⊂ {1, 2, . . . , N}, and a stochastic gradient is evaluated based on the chosen minibatch, g̃(θt) = ∑ i∈Bt ∇θ`(f(xi; θt), yi)/m, which is an unbiased estimator of the full gradient g0(θt). Then, the parameters are updated with some learning rate ηt as θt+1 = θt − ηtg̃(θt). Denote g(θ) = ∇θ`((f(x; θ), y), the gradient for loss with a single data point (x, y), and assume that the size of minibatch is large enough for the central limit theorem to
hold, and thus g̃(θt) follows a Gaussian distribution (Mandt et al., 2017; Li et al., 2017), g̃(θt) ∼ N ( g0(θt), 1
m Σ(θt)
) , where Σ(θt) ≈ 1
N N∑ i=1 ( g(θt;xi)− g0(θt) ) ( g(θt;xi)− g0(θt) )T .
(1) Note that the covariance matrix Σ depends on the model architecture, dataset and the current parameter θt. Now we can rewrite the update of SGD as,
θt+1 = θt − ηtg0(θt) + ηt√ m t, t ∼ N
( 0,Σ(θt) ) . (2)
Inspired by GLD and SGD, we may consider a general kind of optimization dynamics, namely, gradient descent with unbiased noise,
θt+1 = θt − ηtg0(θt) + σt t, t ∼ N (0,Σt) . (3)
For small enough constant learning rate ηt = η, the above iteration in Eq. (3) can be treated as the numerical discretization of the following stochastic differential equation (Li et al., 2017; Jastrzębski et al., 2017; Chaudhari & Soatto, 2017),
dθt = −∇θL(θt) dt+ √ ησ2tΣt dWt. (4)
Considering √ ησ2tΣt as the coefficient of noise term, existing works (Hoffer et al., 2017; Jastrzębski et al., 2017) studied the influence of noise magnitude of SGD on generalization, i.e. ησ2t = η/m.
In this work, we focus on studying the benefits of anisotropic structure of Σt in SGD helping escape from minima by bridging the covariance matrix with the Hessian of the loss surface, and its implicit regularization effects on generalization, especially in deep learning context. For the purpose of eliminating the influence of the noise magnitude, we constrain it to be a constant when studying different structures of noise covariance. The noise magnitude could be evaluated as the expectation of the squared norm of the noise vector,
E[( √ ησt t) T ( √ ησt t)] = ησ 2 tE[ T ] = ησ2t TrE[ T ] = ησ2t Tr Σt. (5)
Thus, we introduce the following constraint,
given time t, ησ2t Tr (Σt) is constant. (6)
From the statistical physics point of view, Tr(ησ2tΣt) characterizes the kinetic energy (Gardiner), thus it is natural to force the energy to be unchanging, otherwise it is trivial that the higher the energy is, the less stable the system is.
For simplicity, we absorb ησ2t into Σt, denoting ησ 2 tΣt as Σt. If not pointed out, the subscript t of matrix Σt is omitted to emphasize that we are fixing t and discussing the varying structure of Σ.

heading: 3 THE BEHAVIORS OF ESCAPING FROM MINIMA IN ORNSTEIN-UHLENBECK PROCESS
text: For a general loss function L(θ) = EX`X(θ) (the expectation could be either population or empirical), where X denotes data example and θ denoted parameters to be optimized, under suitable smoothness assumptions, the SDE associated with the gradient variant optimizer as shown in Eq. (4) can be written as follows (Li et al., 2017; Jastrzębski et al., 2017; Chaudhari & Soatto, 2017; Hu et al., 2017), with little abuse of notation,
dθt = −∇θL(θt) dt+ Σ 1 2 t dWt. (7)
Let L0 = L(θ0) be one of the minimal values of L(θ), then for a fixed t small enough (such that Lt−L0 ≥ 0), Eθt [Lt−L0] characterizes the efficiency of θ escaping from the minimum θ0 of L(θ). It is natural to measure the escaping efficiency using E[Lt − L0] since it characterizes the increase of the potential, i.e., the increase of the loss L. And also note that Lt − L0 ≥ 0, for any δ > 0, the escaping probability P (Lt − L0 ≥ δ) can be controlled by the expectation E[Lt − L0] since by Markov’s inequality, we have P (Lt − L0 ≥ δ) ≤ E[Lt−L0]δ .
Proposition 1 (Escaping efficiency for general process). For the process (7), provided mild smoothness assumptions, the escaping efficiency from the minimum θ0 is,
E[Lt − L0] = − ∫ t
0
E [ ∇LT∇L ] + ∫ t 0 1 2 ETr(HtΣt) dt, (8)
where Ht denotes the Hessian of L(θt) at θt.
We provide the proof in Appendix, and the same for the other propositions.
The escaping efficiency for general processes is hard to analyze due to the intractableness of the integral in Eq. (8). However, we may consider the second-order approximation locally near the minima θ0, where L(θ) ≈ L0 + 12 (θ − θ0)
TH(θ − θ0). Without losing generality, we suppose θ0 = 0. Further, suppose that H is a positive definite matrix and the diffusion covariance Σt = Σ is constant for t. Then the SDE (7) becomes an Ornstein-Uhlenbeck process,
dθt = −Hθt dt+ Σ 1 2 dWt, θ0 = 0. (9)
Proposition 2 (Escaping efficiency of Ornstein-Uhlenbeck process). For Ornstein-Uhlenbeck process (9), with t small enough, the escaping efficiency from minimum θ0 = 0 is,
E[Lt − L0] = 1
4 Tr
(( I − e−2Ht ) Σ ) ≈ t
2 Tr (HΣ) . (10)
Inspired by Proposition 1 and Proposition 2, we propose Tr (HΣ) as an empirical indicator measuring the efficiency for a stochastic process escaping from minima. Now we turn to analysis which kind of noise covariance structure Σ will benefit escaping sharp minima, under the constraint Eq. (6).
Firstly, for the isotropic loss surface, i.e., H = λI , the escaping efficiency is E[Lt−L0] = λt2 Tr Σ, which is invariant under the constraint that Tr Σ is constant (Eq. (6)). Thus it is only nontrivial to study the impact of noise structure when the Hessian of loss surface is anisotropic.
Secondly, H and Σ being semi-positive definite, to achieve the maximum of Tr(HΣ) under constraint (6), Σ should be Σ∗ = (Tr Σ) · λ1u1uT1 , where λ1, u1 are the maximal eigenvalue and corresponding unit eigenvector of H . Note that the rank-1 matrix Σ∗ is highly anisotropic. More generally, the following Proposition 3 characterizes one kind of anisotropic noise significantly outperforming isotropic noise in order of number of parameters D, given H is ill-conditioned.
Proposition 3 (The benefits of anisotropic noise). With semi-positive definite H and Σ, assume
(1) H is ill-conditioned. Let λ1 ≥ λ2 ≥ . . . ,≥ λD ≥ 0 be the eigenvalues of H in descent order, and for some constant k D and d > 12 ,
λ1 > 0, λk+1, λk+2, . . . , λD < λ1D −d, (11)
(2) Σ is “aligned” with H . Let ui be the corresponding unit eigenvector of eigenvalue λi, for some projection coefficient a > 0,
uT1 Σu1 ≥ aλ1 Tr Σ
TrH , (12)
then we have the benefit of the anisotropic noise over the isotropic one in term of escaping efficiency, which can be characterized by the follow ratio,
Tr (HΣ) Tr(HΣ̄) = O
( aD(2d−1) ) , (13)
where Σ̄ = Tr ΣD I denotes the covariance of isotropic noise, to meet the constraint Eq. (6).
To give some geometric intuitions on the left hand side of Eq. (12), let the maximal eigenvalue and its corresponding unit eigenvector of Σ be γ1, v1, then the right hand side has a lower bound as uT1 Σu1 ≥ uT1 v1γ1vT1 u1 = γ1 〈u1, v1〉
2. Thus if the maximal eigenvalues of H and Σ are aligned in proportion, γ1/Tr Σ ≥ a1λ1/TrH , and the angle of their corresponding unit eigenvectors is close to zero, 〈u1, v1〉 ≥ a2, the second condition Eq. (12) in Proposition 3 holds for a = a1a2.
Typically, in the scenario of modern deep neural networks, due to the over-parameterization, Hessian and the gradient covariance are usually ill-conditioned and anistropic near minima, as shown by (Sagun et al., 2017) and (Chaudhari & Soatto, 2017). Thus the first condition in Eq. (11) usually holds for deep neural networks, and we further justify it by experiments in Section 5.3. Therefore, in the following section, we turn to focus on how the gradient covariance, i.e. the covariance of SGD noise meets the second condition of Proposition 3 in the context of deep neural networks.

heading: 4 THE ANISOTROPIC NOISE OF SGD IN DEEP NETWORKS
text: In this section, we mainly investigate the anisotropic structure of gradient covariance in SGD, and explore its connection with the Hessian of loss surface.
Around the true parameter According to the classic statistical theory (Pawitan, 2001, Chap. 8), for population loss L(θ) = EX`(θ), with ` being the negative log likelihood, when evaluating at the true parameter θ∗, there is the exact equivalence between the Hessian H of the population loss and Fisher information matrix F ,
F (θ∗) := EX [∇θ`(θ∗)∇θ`(θ∗)T ] = EX [∇2θ`(θ∗)] = ∇2θL(θ∗) =: H(θ∗). (14)
In practice, with the assumptions that the sample size N is large enough (i.e. indicating asymptotic behavior) and suitable smoothness conditions, when the current parameter θt is not far from the ground truth, Fisher is close to Hessian. Thus we can obtain the following approximate equality between gradient covariance and Hessian,
Σ(θt) = F (θt)−∇θLT (θt)∇θL(θt) ≈ F (θt) ≈ H(θt).
The first approximation is due to the dominance of noise over the mean of gradient in the later stage of SGD optimization, which has been shown in (Shwartz-Ziv & Tishby, 2017). A similar experiment as (Shwartz-Ziv & Tishby, 2017) has been conducted to demonstrate this observation, which is left in Appendix due to the limit of space.
In the following, we theoretically characterize the closeness between Σ and H in the context of one hidden layer neural networks; and show that the gradient covariance introduced by SGD indeed has more benefits than isotropic one in term of escaping from minima, provided some assumptions.
One hidden layer neural network with fixed output layer parameters For binary classification neural network with one hidden layer in classic setups (with softmax and cross-entropy loss), we have following results to globally bound Fisher and Hessian with each other. Proposition 4 (The relationship between Fisher and Hessian in one hidden layer neural network). Consider the binary classification problem with data {(xi, yi)}i∈I , y ∈ {0, 1}, and typical (either population or empirical) loss as L(θ) = E[φ ◦ f(x; θ)], where f denotes the output of neural network, and φ denotes the cross-entropy loss with softmax,
φ(f(x), y) = − ( y log ef(x)
1 + ef(x) + (1− y) log 1 1 + ef(x)
) , y ∈ {0, 1}.
If: (1) the neural network f is with one hidden layer and piece-wise linear activation. And the parameters of output layer are fixed during training; (2) the optimization happens on a set U such that, f(x; θ) ∈ (−C,C),∀θ ∈ U,∀x, i.e., the output of the classifier is bounded during optimization. Then, we have the following relationship between (either population or empirical) Fisher F and Hessian H almost everywhere:
e−CF (θ) H(θ) eCF (θ).

heading: A B means that (B −A) is semi-positive definite.
text: There are a few remarks on Proposition 4. Firstly, as shown in (Brutzkus et al., 2017), the considered neural networks in Proposition 4 are non-convex and have multiple minima, and thus it is still nontrivial to consider the escaping from minima. Secondly, the Proposition 4 holds in both population and empirical sense, since the proof does not distinguish the two circumstances. Thirdly, the bound
between F and H holds "globally" in the set U where the output f is bounded, rather than merely around the true global minima as discussed previously.
By Proposition 4, the following relationship between gradient covariance and Hessian could be derived. Proposition 5 (The relationship between gradient covariance and Hessian in one hidden layer neural network). Assume the conditions in Proposition 4 hold, then for some small δ > 0 and for θ close enough to minima θ∗ (local or global),
uTΣu ≥ e−2(C+δ)λTr Σ TrH
(15)
holds for any positive eigenvalue λ and its corresponding unit eigenvector u of Hessian H .
As a direct corollary of Proposition 5, for such neural networks, the second condition Eq. (12) in Proposition 3 holds in a very loose sense.
Therefore, based on the discussion on population loss around the true parameters and one hidden layer neural network with fixed output layer parameters, given the ill-conditioning of H due to the over-parameterization of modern deep networks, according to Proposition 3, we can conclude the noise structure of SGD helps to escape from sharp minima much faster than the dynamics with isotropic noise, and converge to flatter solutions with a high probability. These flat minima typically generalize well (Hochreiter & Schmidhuber, 1997; Keskar et al., 2017; Neyshabur et al., 2017; Wu et al., 2017). Thus, we attribute such properties of SGD on its better generalization performance comparing to GD, GLD and other dynamics with isotropic noise (Hoffer et al., 2017; Goyal et al., 2017; Keskar et al., 2017).
In the following, we conduct a series of experiments systematically to verify our understanding on the behavior of escaping from minima and its regularization effects for different optimization dynamics.

heading: 5 EXPERIMENTS
text: To better understanding the behavior of anisotropic noise different from isotropic ones, we introduce dynamics with different kinds of noise structure to empirical study with, as shown on Table 1.
Table 1: Compared dynamics defined in Eq. (3). For GLD dynamic, GLD diagonal, GLD Hessian and GLD 1st eigvec(H), σt are adjusted to make σt t share the same expected norm as that of SGD. For GLD leading, σt is same as in SGD. Note that GLD 1st eigvec(H) achieves the best escaping efficiency as our indicator suggested.
Noise t Remarks SGD t ∼ N
(
0,Σsgdt
)
Σsgdt is defined as in Eq. (1), and σt = ηt√ m
GLD constant t ∼ N (0, I) σt is a tunable constant GLD dynamic t ∼ N (0, I) σt is adjusted to make σt t share the same expected norm as that of SGD GLD diagonal t ∼ N ( 0, diag(Σt)
) The covariance diag(Σt) is the diagonal of the covariance of SGD noise.
GLD leading t ∼ N ( 0, Σ̃t )
Σ̃t = ∑k i=1 γiviv T i . γi, vi are the first k leading eigenvalues and corresponding eigenvalues of the covariance of SGD noise, respectively. (A low rank approximation of Σsgdt )
GLD Hessian t ∼ N ( 0, H̃t )
H̃t is a low rank approximation of the Hessian matrix of loss L(θ) by its the first k leading eigenvalues and corresponding eigenvalues.
GLD 1st eigven(H) t ∼ N ( 0, λ1u1u T 1 ) λ1, u1 are the maximal eigenvalue and its corresponding unit eigenvector of the Hessian matrix of lossL(θt).

heading: 5.1 TWO-DIMENSIONAL TOY EXAMPLE
text: We design a 2-D toy example L(w1, w2) with two basins, a small one and a large one, corresponding to a sharp and flat minima, (1, 1) and (−1,−1), respectively, both of which are global minima.
Please refer to Appendix for the detailed constructions. We initialize the dynamics of interest with the sharp minimum (w1, w2) = (1, 1), and run them to study their behaviors escaping from this sharp minimum.
To explicitly control the noise magnitude, we only conduct experiments on GD, GLD const, GLD diag, GLD leading (with k = 2 = D in Table 1, or in other words, the exactly covariance of SGD noise), GLD Hessian (k = 2) and GLD 1st eigven(H). And we adjust σt in each dynamics to force their noise to share the same expected squared norm as defined in Eq. (6). Figure 1(a) shows the trajectories of the dynamics escaping from the sharp minimum (1, 1) towards the flat one (−1,−1), while Figure 1(b) presents the success rate of escaping for each dynamic during 100 repeated experiments.
As shown in Figure 1, GLD 1st eigvec(H) achieves the highest success rate, indicating the fastest escaping speed from the sharp minimum. The dynamics with anisotropic noise aligned with Hessian well, including GLD 1st eigvec(H), GLD Hessian and GLD leading, greatly outperform GD, GLD const with isotropic noise, and GLD diag with noise poorly aligned with Hessian. These experiments are consistent with our theoretical analysis on Ornstein-Uhlenbeck process shown Proposition 2 and 3, demonstrating the benefits of anisotropic noise for escaping from sharp minima.

heading: 5.2 ONE HIDDEN LAYER NEURAL NETWORK WITH FIXED OUTPUT LAYER PARAMETERS
text: We empirically show that in one hidden layer neural network with fixed output layer parameters, the anisotropic noise induced by SGD indeed helps escape from sharp minima more efficiently than isotropic noise. Three networks are trained to binary classify 1, 000 linearly separable two-dimensional points. The number of hidden nodes for each network varies in {20, 200, 2000}. We plot the empirical indicator Tr (HΣ) in Figure 2. We can easily observe that as the increase of the number of hidden nodes, the ratio Tr(HΣ)
Tr(HΣ̄) is enlarged significantly, which is
consistent with the Eq. (13) described in Proposition 3.

heading: 5.3 PRACTICAL DATASETS
text: In this part, we conduct a series of experiments in real deep learning scenarios to demonstrate the behavior of SGD noise and its implicit regularization effects. We con-
struct a noisy training set based on FashionMNIST dataset1. Concretely, the training set consist of 1000 images with correct labels, and another 200 images with random labels. All the test data are with clean labels. A small LeNet-like network is utilized such that the spectrum decomposition over
1https://github.com/zalandoresearch/fashion-mnist
gradient covariance matrix and Hessian matrix are computationally feasible. The network consists of two convolutional layers and two fully-connected layers, with 11, 330 parameters in total.
We firstly run the standard gradient decent for 3000 iterations to arrive at the parameters θ∗GD near the global minima with near zero training loss and 100% training accuracy, which are typically sharp minima that generalize poorly (Neyshabur et al., 2017). And then all other compared methods are initialized with θ∗GD and run for optimization with the same learning rate ηt = 0.07 and same batch size m = 20 (if needed) for fair comparison2.
Verification of SGD noise satisfying the conditions in Proposition 3 To see whether the noise of SGD in real deep learning circumstance satisfies the two conditions in Proposition 3, we run SGD optimizer initialized from θ∗GD, i.e. the sharp minima found by GD. Figure 3(a) shows the first 400 eigenvalues of Hessian at θ∗GD, from which we see that the 140th eigenvalue has already decayed to about 1% of the first eigenvalue. Note that Hessian H ∈ RD×D, D = 11330, thus H around θ∗GD approximately meets the ill-conditioning requirement in Proposition 3. Figure 3(b) shows the projection coefficient estimated by â = u
T 1 Σu1 TrH λ1 Tr Σ
along the trajectory of SGD. The plot indicates that the projection coefficient is in a descent scale comparing toD2d−1, thus satisfying the second condition in Proposition 3. Therefore, Proposition 3 ensures that SGD would escape from minima θ∗GD faster than GLD in order ofO(D2d−1), as shown in Figure 3(c). An interesting observation is that in the later stage of SGD optimization, Tr(HΣ) becomes significantly (107 times) smaller than in the beginning stage, implying that SGD has already converged to minima being almost impossible to escape from. This phenomenon demonstrates the reasonability to employ Tr(HΣ) as an empirical indicator for escaping efficiency.
λ1 Tr Σ
, as shown in
Proposition 3. (c)Tr(HtΣt) versus Tr(HtΣ̄t) during SGD optimization initialized from θ∗GD , Σ̄t = Tr ΣtD I denotes the isotropic noise with same expected squared norm as SGD noise.
Behaviors of different dynamics escaping from minima and its generalization effects To compare the different dynamics on escaping behaviors and generalization performance, we run dynamics initialized from the sharp minima θ∗GD found by GD. The settings for each compared method are as follows. The hyperparameter σ2 for GLD const has already been tuned as optimal (σ = 0.001) by grid search. For GLD leading, we set k = 20 for comprising the computational cost and approximation accuracy. As for GLD Hessian, to reduce the expensive evaluation of such a huge Hessian in each iteration, we set k = 20 and update the Hessian every 10 iterations. We adjust σt in GLD dynamic, GLD Hessian and GLD 1st eigvec(H) to guarantee that they share the same expected squred noise norm defined in Eq. (6) as that of SGD. And we measure the expected sharpness of different minima as Eν∼N (0,δ2I) [ L(θ + ν) ] − L(θ), as defined in ((Neyshabur et al., 2017), Eq.(7)). The results are shown in Figure 4.
As shown in Figure 4, SGD, GLD 1st eigvec(H), GLD leading and GLD Hessian successfully escape from the sharp minima found by GD, while GLD, GLD dynamic and GLD diag are trapped in the minima. This demonstrates that the methods with anisotropic noise “aligned” with loss curvature can help to find flatter minima that generalize well.
We also provide experiments on standard CIFAR-10 with VGG11 in Appendix.
2In fact, in our experiment, we test the equally spacing learning rates in the range [0.01, 0.1], and the final results are consistent with each other.

heading: 6 CONCLUSION
text: We theoretically investigate a general optimization dynamics with unbiased noise, which unifies various existing optimization methods, including SGD. We provide some novel results on the behaviors of escaping from minima and its regularization effects. A novel indicator is derived for characterizing the escaping efficiency. Based on this indicator, two conditions are constructed for showing what type of noise structure is superior to isotropic noise in term of escaping. We then analyze the noise structure of SGD in deep learning and find that it indeed satisfies the two conditions, thus explaining the widely know observation that SGD can escape from sharp minima efficiently toward flat minina that generalize well. Various experimental evidence supports our arguments on the behavior of SGD and its effects on generalization. Our study also shows that isotropic noise helps little for escaping from sharp minima, due to the highly anisotropic nature of landscape. This indicates that it is not sufficient to analyze SGD by treating it as an isotropic diffusion over landscape (Zhang et al., 2017; Mou et al., 2017). A better understanding of this out-of-equilibrium behavior (Chaudhari & Soatto, 2017) is on demand.

heading: A PROOFS OF PROPOSITIONS IN MAIN PAPER

heading: A.1 PROOF OF PROPOSITION 1
text: Proof. The "mild smoothness assumptions" refers that Lt = L(θt) ∈ C2. Then the Ito’s lemma holds (Øksendal, 2003).
And by Ito’s lemma, the SDE of Lt is
dLt =
( −∇LT∇L+ 1
2 Tr
( Σ 1 2 t HtΣ 1 2 t )) dt+∇LTΣ 1 2 t dWt
= ( −∇LT∇L+ 1
2 Tr (HtΣt)
) dt+∇LTΣ 1 2 t dWt.
Taking expectation with respect to the distribution of θt,
dELt = E ( −∇LT∇L+ 1
2 Tr(HtΣt)
) dt, (16)
for the expectation of Brownian motion is zero. Thus the solution of EYt is,
ELt = L0 − ∫ t
0
E ( ∇LT∇L ) + ∫ t 0 1 2 ETr(HtΣt) dt.

heading: A.2 PROOF OF PROPOSITION 2
text: Proof. Without losing generality, we assume that L0 = 0.
For multivariate Ornstein-Uhlenbeck process, when θ0 = 0 is an constant, θt follows a multivariate Gaussian distribution (Øksendal, 2003).
Consider change of variables θ → φ(θ, t) = eHtθt. Here, for symmetric matrix A,
eA := Udiag(eλ1 , . . . , eλn)U,
where λ1, . . . , λn and U are the eigenvalues and eigenvector matrix of A. Note that with this notation,
deHt
dt = HeHt.
Applying Ito’s lemma, we have
dφ(θt, t) = e HtΣ 1 2 dWt,
which we can integrate form 0 to t to get
θt = 0 + ∫ t 0 eH(s−t)Σ 1 2 dWs
The expectation of θt is zero. And by Ito’s isometry (Øksendal, 2003), the covariance of θt is,
EθtθTt = E ∫ t 0 eH(s−t)Σ 1 2 dWs (∫ t 0 eH(r−t)Σ 1 2 dWr )T = E
[∫ t 0 eH(s−t)Σ 1 2 Σ 1 2 eH(s−t) ds ]
= E [∫ t 0 eH(s−t)ΣeH(s−t) ds ]
= ∫ t 0 eH(s−t)ΣeH(s−t) ds. (for H and Σ are both constant.)
Thus,
EL(θt) = 1
2 ETr
( θTt Hθt ) = 1 2 Tr ( HEθtθTt
) = 1
2 ∫ t 0 Tr ( HeH(s−t)ΣeH(s−t) ) ds
= 1
2 ∫ t 0 Tr ( eH(s−t)HΣeH(s−t) ) ds (for H is symmetric.)
= 1
2 ∫ t 0 Tr ( e2H(s−t)HΣ ) ds
= 1
2 Tr
( 1
2 H−1
( I − e−2Ht ) HΣ ) = 1
4 Tr
(( I − e−2Ht ) Σ ) .
The last approximation is by Taylor’s expansion.

heading: A.3 PROOF OF PROPOSITION 3
text: Proof. Firstly, Tr(HΣ) has the decomposition as Tr(HΣ) = ∑D i=1 λiu T i Σui.
Secondly, compute Tr(HΣ),Tr(HΣ̄) respectively,
Tr(HΣ) ≥ uT1 Σu1 ≥ aλ1 Tr Σ
TrH ,
Tr(HΣ̄) = Tr Σ
D TrH,
and bound their quotient,
Tr(HΣ) Tr(HΣ̄) ≥ aλ1D (TrH) 2 ≥ aλ1D( kλ1 + (D − k)D−dλ1 )2 = O (aD2d−1) . (17) The proof is finished.

heading: A.4 PROOF OF PROPOSITION 4
text: Proof. Firstly compute the gradients and Hessian of φ,
∂φ ∂f =
ef
1 + ef − y =
{ ef
1+ef > 0 y = 0, − 1 1+ef < 0 y = 1.
∂2φ ∂f2 =
ef
(1 + ef )2 .
And note the Gauss-Newton decomposition for functions with the form of L = φ ◦ f ,
H = E(x,y) ∂ 2`((x,y);θ) ∂θ2
= E(x,y) ∂ 2φ ∂f2 ∂f ∂θ ∂fT ∂θ + E(x,y) ∂φ ∂f ∂2f ∂θ2 .
Since the output layer parameters for f is fixed and the activation functions are piece-wise linear, f(x; θ) is a piece-wise linear function on its parameters θ. Therefore ∂
2f ∂θ2 = 0, a.e., and H =
E(x,y) ∂ 2φ ∂f2 ∂f ∂θ ∂fT ∂θ .
It is easy to check that e−C ( ∂φ ∂f )2 ≤ ∂ 2φ ∂f2 ≤ e C ( ∂φ ∂f )2 . Thus,
H = E(x,y) ∂ 2φ ∂f2 ∂f ∂θ ∂fT ∂θ E(x,y)e C ( ∂φ ∂f )2 ∂f ∂θ ∂fT ∂θ = E(x,y)e C ( ∂φ ∂f ∂f ∂θ )( ∂φ ∂f ∂f ∂θ )T = eCF.
H = E(x,y) ∂ 2φ ∂f2 ∂f ∂x ∂fT ∂x E(x,y)e −C ( ∂φ ∂f )2 ∂f ∂x ∂fT ∂x = E(x,y)e −C ( ∂φ ∂f ∂f ∂θ )( ∂φ ∂f ∂f ∂θ )T = e−CF.

heading: A.5 PROOF OF PROPOSITION 5
text: Proof. For simplicity, we define g := ∇`, g0 := ∇L = E∇`. The gradient covariance and Fisher has the following relationship,
F = Eg · gT = E(g0 + )(g0 + )T = g0gT0 + E T = g0gT0 + Σ.
Applying Taylor’s expansion to g0(θ), g0(θ) = g0(θ ∗) +H(θ∗)(θ − θ∗) + o(θ − θ∗) = H(θ∗)(θ − θ∗) + o(θ − θ∗). Hence, ∥∥g0(θ)∥∥22 ≤‖H‖22‖θ − θ∗‖22 + o(‖θ − θ∗‖22) =‖H‖22‖θ − θ∗‖22 + o(‖θ − θ∗‖22) . Therefore, with the condition‖θ − θ∗‖2 ≤ √ δuTFu ‖H‖2
, we have∥∥g0(θ)∥∥22 ≤ δuTFu+ o (|δ|) . Thus,
uTΣu Tr Σ = uTFu− uT g0gT0 u TrF − Tr(g0gT0 ) ≥ uTFu−‖g0‖22 TrF −‖g0‖22 ≥ uTFu−‖g0‖22 TrF
= uTFu
TrF ( 1− ‖g0‖22 uTFu ) ≥ u TFu TrF ( 1− δ − o ( |δ| )) ≥ u TFu TrF e−2δ,
for δ small enough.
On the other hand, Proposition 4 indicates that e−CF H eCF , which means, ∀u, uT (eCF −H)u ≥ 0
and Tr(H − e−CF ) ≥ 0.
Thus u TFu TrF ≥ uT (e−CH)u Tr(eCH) .
Therefore, for λ, u being a positive eigenvalue and the corresponding unit eigenvector of H , we have
uTFu
TrF ≥ e−2C λ
TrH uTΣu
Tr Σ ≥ u
TFu
TrF e−2δ ≥ e−2(C+δ) λ TrH .

heading: B ADDITIONAL EXPERIMENTS

heading: B.1 DOMINANCE OF NOISE OVER GRADIENT
text: Figure 5 shows the comparison of gradient mean and the expected norm of noise during training using SGD. The dataset and model are same as the experiments of FashionMNIST in main paper, or as in Section C.2. From Figure 5, we see that in the later stage of SGD optimization, noise indeed dominates gradient.
These experiments are implemented by TensorFlow 1.5.0.

heading: B.2 THE FIRST 50 ITERATIONS OF FASHIONMNIST EXPERIMENTS IN MAIN PAPER
text: Figure 6 shows the first 50 iterations of FashionMNIST experiments in main paper. We observe that SGD, GLD 1st eigvec(H), GLD Hessian and GLD leading successfully escape from the sharp minima found by GD, while GLD diag, GLD dynamic, GLD const and GD do not.
These experiments are implemented by TensorFlow 1.5.0.

heading: B.3 ADDITIONAL EXPERIMENTS ON STANDARD CIFAR-10 AND VGG11
text: Dataset Standard CIFAR-10 dataset without data augmentation.
Model Standard VGG11 network without any regularizations including dropout, batch normalization, weight decay, etc. The total number of parameters of this network is 9, 750, 922.
Training details Learning rates ηt = 0.05 are fixed for all optimizers, which is tuned for the best generalization performance of GD. The batch size of SGD is m = 100. The noise std of GLD constant is σ = 10−3, which is tuned to best. Due to computational limitation, we only conduct experiments on GD, GLD const, GLD dynamic, GLD diag and SGD.
Estimation of Sharpness The sharpness are estimated by
1
M M∑ j=1 L(θ + νj)− L(θ), νj ∼ N (0, δ2I),
with M = 100 and δ = 0.01.
Experiments Similar experiments are conducted as in main paper for CIFAR-10 and VGG11, as shown in Figure 7. The observations and conclusions consist with main paper.
These experiments are implemented by PyTorch 0.3.0.

heading: C DETAILED SETUPS FOR EXPERIMENTS IN MAIN PAPER

heading: C.1 TWO-DIMENSIONAL TOY EXAMPLE
text: Loss Surface The loss surface L(w1, w2) is constructed by, s1 = w1 − 1− x1, s2 = w2 − 1− x2, `(w1, w2;x1, x2) = min{10(s1 cos θ − s2 sin θ)2
+ 100(s1 cos θ + s2 sin θ) 2, (w1 − x1 + 1)2 + (w2 − x2 + 1)2},
L(w1, w2) = 1
N N∑ k=1 `(w1, w2;x k 1 , x k 2),
where
θ = 1
4 π,
N = 100, xk ∼ N (0,Σ), Σ = (
cos θ sin θ − sin θ cos θ
) .
Note that Σ is the inverse of the Hessian of the quadric form generalizeing the sharp minima. And the 3-dimensional plot of the loss surface is shown in Figure 8.
Hyperparameters All learning rates are equal to 0.005. All dynamics concerned are tuned to share the same expected square norm, 0.01. The number of iteration during one run is 500.
These experiments are implemented by PyTorch 0.3.0.

heading: C.2 FASHIONMNIST WITH CORRUPTED LABELS
text: Dataset Our training set consists of 1200 examples randomly sampled from original FashionMNIST training set, and we further specify 200 of them with randomly wrong labels. The test set is same as the original FashionMNIST test set.
Model Network architecture: input⇒ conv1⇒ max_pool⇒ ReLU⇒ conv2⇒ max_pool
⇒ ReLU⇒ fc1⇒ ReLU⇒ fc2⇒ output. Both two convolutional layers use 5 × 5 kernels with 10 channels and no padding. The number of hidden units between fully connected layers are 50. The total number of parameters of this network are 11, 330.
w1 1.5 1.0 0.50.0 0.5 1.0 1.5
w2
1.5 1.0
0.5 0.0
0.5 1.0
1.5
loss 2 4 6 8 10 12
2 4 6 8 10 12

heading: Training details
text: Estimation of Sharpness The sharpness are estimated by
1
M M∑ j=1 L(θ + νj)− L(θ), νj ∼ N (0, δ2I),
with M = 1, 000 and δ = 0.01.
These experiments are implemented by TensorFlow 1.5.0.

Review summaries:
The authors studied the effect of the anisotropic noise of SGD on the algorithm’s ability to escape from local optima. To this end, the authors depart from the established approximation of SGD in the vicinity of an optimum as a continuous-time Ornstein-Uhlenbeck process. Furthermore, the authors argue that in certain deep learning models, the anisotropic noise indeed leads to a good escaping from local optima.