Asymmetric Valleys: Beyond Sharp and Flat Local Minima

Introduction

The loss landscape of neural networks has attracted great research interests in the deep learning community (Choromanska et al., 2015; Cooper, 2018; Keskar et al., 2017; Draxler et al., 2018; Ge et al., 2017; Sagun et al., 2017). It provides the basis of designing better optimization algorithms, and helps to answer the question of when and how a deep network can achieve good generalization performance. One hypothesis that draws attention recently is that the local minima of neural networks can be characterized by their flatness, and it is conjectured that sharp minima tend to generalize worse than the flat ones (Keskar et al., 2017). A plausible explanation is that a flat minimizer of the training loss can achieve lower generalization error if the test loss is shifted from the training loss due to random perturbations. Figure 1(a) gives an illustration for this argument.

Although being supported by plenty of empirical observations (Keskar et al., 2017; Izmailov et al., 2018; Li et al., 2018), the definition of flatness was recently challenged by (Dinh et al., 2017), who showed that one can construct arbitrarily sharp minima through weight re-parameterization without changing the generalization performance. In addition, recent evidence suggests that the minima of modern deep networks are connected with simple paths with low generalization error (Draxler et al., 2018; Garipov et al., 2018). Similarly, the minima found by large batch training and small batch training are shown to be connected without any “bumps” (Sagun et al., 2017). This raises several questions: (1) If all the minima are well connected, why do some algorithms keep finding sharp minima and others keep finding flat ones (Keskar et al., 2017)? (2) Does flatness really affect generalization?

For the second question, we argue that flatness does affect generalization. However, we do not simply follow the argument in (Keskar et al., 2017), which states that flat minima tend to generalize better because they are more stable. Instead, we prove that in asymmetric valleys, the solution biased towards the flat side of the valley gives better generalization under mild assumptions. This result has at least two interesting implications: (1) converging to which local minimum (if there are many) may not be critical for modern deep networks. However, it matters a lot where the solution locates; and (2) the solution with lowest a priori generalization error is not necessarily the minimizer of the training loss.

Given that a biased solution is preferred for asymmetric valleys, an immediate question is how we can find such solutions in practice. It turns out that simply averaging the weights along the SGD trajectory, naturally leads to the desired solutions with bias. We give a theoretical analysis to support this argument, see Figure 1(c) for an illustration. Note that our result is in line with the empirical observations recently made by Izmailov et al. (2018).

In addition, we provide empirical analysis to verify our theoretical results and support our claims. For example, we show that asymmetric valleys are indeed prevalent in modern deep networks, and solutions with lower generalization error has bias towards the flat side of the valley. We also find that batch normalization seems to be a major cause for shaping asymmetric loss surfaces.

Related Work

Neural network landscape. Analyzing the landscape of deep neural networks is an active and exciting area (Goodfellow & Vinyals, 2014; Li et al., 2018; Ge et al., 2017; Pennington & Bahri, 2017; Wu et al., 2017; Cooper, 2018; Sagun et al., 2017). For example, (Draxler et al., 2018; Garipov et al., 2018) observed that essentially all local minima are connected together with simple paths. (Huang et al., 2017) used cyclic learning rate and took the ensemble of intermediate models to get improved accuracy. There are also appealing visualizations for the neural network landscape (Li et al., 2018).

Sharp and flat minima. The discussion of sharp and flat local minima dates back to (Hochreiter & Schmidhuber, 1995), and recently regains its popularity. For example, Keskar et al. (2017) proposed that large batch SGD finds sharp minima, which leads to poor generalization. In (Chaudhari et al., 2016), an entropy regularized SGD was introduced to explicitly searching for flat minima. It was later pointed out that large batch SGD can yield comparable performance when the learning rate or the number of training iterations are properly set (Hoffer et al., 2017; Goyal et al., 2017; Smith et al., 2017; Masters & Luschi, 2018; Smith & Le, 2017; Jastrzebski et al., 2017). Moreover, (Dinh et al., 2017) showed that from a given flat minimum, one could construct another minimum with arbitrarily sharp directions but equally good performance. In this paper, we argue that the description of sharp or flat minima is an oversimplification. There may simultaneously exist steep directions, flat directions, and asymmetric directions for the same minimum.

SGD optimization and generalization. As the de facto optimization tool for deep networks, SGD and its variants are extensively studied in the literature. For example, it is shown that they could escape saddle points or sharp local minima under reasonable assumptions (Ge et al., 2015; Jin et al., 2017, 2018a, 2018b; Xu et al., 2018; Allen-Zhu, 2018a, b; Allen-Zhu & Li, 2018; Kleinberg et al., 2018). For convex functions (Polyak & Juditsky, 1992) or strongly convex but non-smooth functions (Rakhlin et al., 2012), SGD averaging is shown to give better convergence rate. In addition, it can also achieve higher generalization performance for Lipschitz functions in theory (Shalev-Shwartz et al., 2009; Cesa-bianchi et al., 2002), or for deep networks in practice (Huang et al., 2017; Izmailov et al., 2018; therearemanyconsistentexplanations). Discussions on the generalization bound of neural networks can be found in (Bartlett et al., 2017; Neyshabur et al., 2018, 2017b; Kawaguchi et al., 2017; Neyshabur et al., 2017a; Arora et al., 2018; Zhou et al., 2019).

We show that SGD averaging has implicit bias on the flat sides of the minima. Previously, it was shown that SGD has other kinds of implicit bias as well (Soudry et al., 2017; Ji & Telgarsky, 2018; Gunasekar et al., 2018).

Asymmetric Valleys

In this section, we give a formal definition of asymmetric valley, and show that it is prevalent in the loss landscape of modern deep neural networks.

1 Definition of asymmetric valley

Before formally introducing asymmetric valleys, we first define asymmetric directions.

To put it simply, asymmetric direction is a direction $\boldsymbol{u}$ along which the loss function grows at different rates at the positive/negative direction. The constant $\zeta$ handles the small neighborhood around $\boldsymbol{w}$ with very small gradients. With this definition, we now formally define the asymmetric valley.

Notice that here we abuse the name “valley”, since $\boldsymbol{\hat{w}^{*}}$ is essentially a point at the center of a valley.

2 Find asymmetric directions empirically

Empirically, by taking random directions with value $(0,1)$ in each dimension, we could find an asymmetric direction for a given local minimum with decent probabilityBy contrast, a random direction with value in $(-1,1)$ is usually not asymmetric. . We perform experiments with three widely used deep networks, i.e., ResNet-110, ResNet-164 (He et al., 2016), DenseNet-100 (Huang et al., 2016), on the CIFAR-10 and CIFAR-100 image classification datasets. For each model on each dataset, we conduct 5 independent runs. The results show that we could always find asymmetric directions with certain specification $(r,p,c,\zeta)$ with $c>2$, which means all the local minimaNotice that empirically we could not verify whether the SGD solution $\boldsymbol{\hat{w}^{*}}$ is a local minimum. See the discussion in Section 6. being found are located in asymmetric valleys. Figure 2 shows an asymmetric direction for a local minimum in ResNet-110 trained on the CIFAR-10 dataset. We verified that it is a $(2.5,0.2,7.5,1.2)$-asymmetric direction. Asymmetric valleys widely exist in other models as well, see Appendix A.

Bias and Generalization

As we show in the previous section, most local minima in practice are asymmetric, i.e., they might be sharp on one direction, but flat on the opposite direction. Therefore, it is important to investigate the generalization ability of a solution $\boldsymbol{w}$ in this scenario. In this section, we prove that a biased solution on the flat side of an asymmetric valley yields lower generalization error than the empirical minimizer $\hat{\boldsymbol{w}}^{*}$ in that valley.

Before presenting our theorem, we first introduce two mild assumptions. We will show that they empirically hold on modern deep networks in Section 4.2.

The first assumption (Assumption 1) states that there exists a shift between the empirical loss and true population loss. This is a common assumption in the previous works, e.g., (Keskar et al., 2017), but was usually presented in an informal way. Here we define the “shift” in a formal way. Without loss of generality, we will compare the empirical loss $\hat{\mathsf{L}}$ with $\mathsf{L}^{\prime}\triangleq\mathsf{L}\!-\!\min_{\boldsymbol{w}}\mathsf{L}(\boldsymbol{w})\!+\!\min_{\boldsymbol{w}}\hat{\mathsf{L}}(\boldsymbol{w})$ to remove the “vertical difference” between $\hat{\mathsf{L}}$ and $\mathsf{L}$. Notice that $\min_{\boldsymbol{w}}\mathsf{L}(\boldsymbol{w})$ and $\min_{\boldsymbol{w}}\hat{\mathsf{L}}(\boldsymbol{w})$ are constants and do not affect our generalization guarantee.

From the above definition, we know that the two functions match well after the shift $\boldsymbol{\delta}$ if $\xi_{\boldsymbol{\delta}}(\boldsymbol{w})$ is very small. For example, $\xi_{\boldsymbol{\delta}}(\boldsymbol{w})=0$ means $\mathsf{L}$ is locally identical to $\hat{\mathsf{L}}$ after the shift $\boldsymbol{\delta}$. Since $\hat{\mathsf{L}}$ is computed on a set of random samples from $\mathcal{D}$, the actual shift $\boldsymbol{\delta}$ between $\hat{\mathsf{L}}$ and $\mathsf{L}$ is a random variable, ideally with zero expectation.

Roughly, the above assumption says that the local landscape of the empirical loss and population loss match well after applying a shift vector $\boldsymbol{\delta}$, which has equal probability of being positive or negative in each dimension. Therefore, $\boldsymbol{\delta}$ has $2^{d}$ possible values for a given shift vector $\boldsymbol{\bar{\delta}}$, each with probability $2^{-d}$. The second assumption stated below can be seen as an extension of Definition 2.

Assumption 2 states that if $\boldsymbol{u}^{i}$ is an asymmetric direction at $\boldsymbol{\hat{w}}^{*}$, then the point $\boldsymbol{\hat{w}}^{*}\!+\!\boldsymbol{v}\!-\!\langle\boldsymbol{v},\boldsymbol{u}^{i}\rangle\boldsymbol{u}^{i}$ that deviates from $\boldsymbol{\hat{w}}^{*}$ along the perpendicular direction of $\boldsymbol{u}^{i}$, is also asymmetric along the direction of $\boldsymbol{u}^{i}$. In other words, the neighborhood around $\boldsymbol{\hat{w}^{*}}$ is an asymmetric valley.

Under the above assumptions, we are ready to state our theorem, which says the empirical minimizer is not necessarily the optimal solution, while a biased solution leads to better generalization. We defer the proof to Appendix B.

It is widely known that the empirical minimizer is usually different from the true optimum. However, in practice it is difficult to know how the training loss shifts from the population loss. Therefore, the best we could do is minimizing the empirical loss function (with some regularizers). On the contrary, Theorem 1 states that under the asymmetric case, we should pick a biased solution to minimize the expected population loss even the shift is unknown. Moreover, it is possible to distill our insight into practical algorithms, as we will discuss in Section 5.

2 Verification of assumptions

We show that a shift between $\mathsf{L}$ and $\hat{\mathsf{L}}$ is quite common in practice, by taking a ResNet-110 trained on CIFAR-10 as an example. Since we could not visualize a shift in a high dimensional space, we randomly sample an asymmetric direction $\boldsymbol{u}$ (more results are shown Appendix C) at the SGD solution $\boldsymbol{\hat{w}}^{*}$. The blue and red curves shown in Figure 3(a) are obtained by calculating $\hat{\mathsf{L}}(\boldsymbol{\hat{w}}^{*}+l\boldsymbol{u})$ and $\mathsf{L}^{\prime}(\boldsymbol{\hat{w}}^{*}+l\boldsymbol{u})$ for $l\in$, which correspond to the training and test loss, respectively.

We then try different shift values of $\boldsymbol{\delta}$ to “match” the two curves. As shown in Figure 3(a), after applying a horizontal shift $\boldsymbol{\delta}\!=\!0.4$ to the test loss, the two curves overlap almost perfectly. Quantitatively, we can use the shift gap defined in Definition 3 to evaluate how well the two curves match each other after shifting. It turns out that $\xi_{\boldsymbol{\delta}=0.4}\!=\!0.0335$, which is much lower than $\xi_{\boldsymbol{\delta}=0}\!=\!0.223$ before shifting ($\boldsymbol{\delta}$ has only one dimension here). In Figure 3(b), we plot $\xi_{\boldsymbol{\delta}}/\xi_{\boldsymbol{0}}$ as a function of $\boldsymbol{\delta}$. Clearly, there exists a $\boldsymbol{\delta}$ that minimizes this ratio, indicating a good match.

We conducted the same experiments for different directions, models and datasets, and similar observations were made. Please refer to Appendix C for more results.

Verification of Assumption 2.

Averaging Generates Good Bias

In the previous section, we show that when the loss landscape of a local minimum is asymmetric, a solution with bias towards the flat side of the valley has better generalization performance. One immediate question is that how can we obtain such a solution via practical algorithms? Below we show that it can be achieved by simply taking the average of SGD iterates during the course of training. We first analyze the one dimensional case in Section 5.1, and then extend the analysis to the high dimensional case in Section 5.2.

For asymmetric functions, as long as the learning rate is not too small, SGD will oscillate between the flat side and the sharp side. Below we focus on one round of oscillation, and show that the average of the iterates in each round has a bias on the flat side. Consequently, by aggregating all rounds of oscillation, averaging SGD iterates leads to a bias as well.

For each individual round $i$, we assume that it starts from the iteration when SGD goes from sharp side to flat side (denoted as $w^{i}_{0}$), and ends at the iteration exactly before the iteration that SGD goes from sharp side to flat side again (denoted as $w^{i}_{T_{i}}$). Here $T_{i}$ denotes the number of iterations in the $i$-th rounds. The average iterate in the $i$-th round can be written as $\bar{w}\triangleq\frac{1}{T_{i}}\sum_{j=0}^{T_{i}}w^{i}_{j}$. For notational simplicity, we will omit the super script $i$ on $w^{i}_{j}$.

The following theorem shows that the expectation of the average has bias on the flat side. To get a formal lower bound on $\bar{w}$, we consider the asymmetric case where $\zeta=0$, and also assume lower bounds for the gradients on the function. Notice that we made little effort to optimize the constants or bounds on the parameters, and we defer the proof to Appendix E.

Assume that a local minimizer $w^{*}=0$ is a $(r,a_{+},c,0)$-asymmetric valley, where $b_{-}\leq\nabla\mathsf{L}(w)\leq a_{-}<0$ for $w<0$, and $0<b_{+}\leq\nabla\mathsf{L}(w)\leq a_{+}$ for $w\geq 0$. Assume $-a_{-}=ca_{+}$ for a large constant $c$, and $\frac{-(b_{-}-\nu)}{b_{+}}=c^{\prime}<\frac{e^{c/3}}{6}$. The SGD updating rule is $w_{t+1}=w_{t}-\eta(\nabla L(w)+\omega_{t})$ where $\omega_{t}$ is the noise and $|\omega_{t}|<\nu$, and assume $\nu\leq a_{+}$. Then we have

where $c_{0}$ is a constant that only depends on $\eta,a_{+},a_{-},b_{+},b_{-}$ and $\nu$.

Theorem 2 can be intuitively explained by Figure 5. If we run SGD on this one dimensional function, it will stay at the flat side for more iterations as the magnitude of the gradient on this side is much smaller. Therefore, the average of the locations is biased towards the flat side.

Of course, if the learning rate is sufficiently small, there will be no oscillations on the SGD trajectory, as shown in Figure 6. In this case, the bias on the sharp side tends to be closer to the center compared to the bias on the flat side, as the gradient on the sharp side is much larger than the gradient on the flat side, so SGD converges much faster. In other words, even if there is no oscillation and Theorem 2 does not apply, SGD averaging creates more bias on flat sides than sharp sides in expectation. Thus in all the scenarios, taking average of SGD iterates would be beneficial for asymmetric loss function.

In addition, for symmetric loss functions, averaging SGD iterates may also be helpful in terms of denoising (see Appendix D for concrete examples). Therefore, taking the average of the SGD trajectory may always improve generalization, regardless of whether the loss function is symmetric or not.

2 High dimensional case

For high dimensional functions, the analysis on averaging SGD iterates would be more complicated compared to that given in the previous subsection. However, if we only care about the bias on a specific direction $\boldsymbol{u}$, we could directly apply Theorem 2 with one additional assumption. Specifically, if the projections of the loss function onto $\boldsymbol{u}$ along the SGD trajectory satisfy the assumptions in Theorem 2, i.e., being asymmetric and the gradient on both sides have upper and lower bounds, then the claim of Theorem 2 directly applies. This is because only the gradient along the direction $\boldsymbol{u}$ will affect the SGD trajectory projected onto $\boldsymbol{u}$, and we could safely omit all other directions.

As shown in the Figure 7, after the first $40$ epochs, the projected loss surfaces becomes relatively stable. Therefore, we could directly apply Theorem 2 to the direction $\boldsymbol{u}$.

As we will see in Section 6.1, compared with SGD solutions, SGD averaging indeed creates bias along different asymmetric directions, as predicted by our theory.

Sharp and Flat Minima Illusion

In this section, we show that where the solution locates at a local minimum basin is very important, which is a refinement of judging the generalization performance by the sharpness/flatness of a local minimum. All of our observations support our theoretical analysis in the previous sections.

First we remark that rigorously testing whether a point is a local minimum, or even close to a local minimum, is extremely hard for deep models, see e.g. (Safran & Shamir, 2017). In fact, the Hessian of most empirical solutions still have plenty of small negative eigenvalues (Chaudhari et al., 2016), so technically they are saddle points. But we choose to ignore these technicalities, and treat all these points as “local minima”.

Recently, Izmailov et al. (2018) proposed the stochastic weight averaging (SWA) algorithm, which explicitly takes the average of SGD iterates to achieve better generalization. Inspired by their observation that “SWA leads to solutions corresponding to wider optima than SGD”, we provide a more refined explanation in this subsection. That is, averaging weights leads to “biased” solutions in an asymmetric valley, which correspond to better generalization.

Specifically, we run the SWA algorithm (with deceasing learning rate) with three popular deep networks, i.e., ResNet-110, ResNet-164 and DenseNet-100, on the CIFAR-10 and CIFAR-100 datasets, following the configurations in (Izmailov et al., 2018) (denoted as SWA). Then we run SGD with small learning rate from the SWA solutions to find a solution located in the same basin (denoted as SGD).

In Figure 8, We draw an interpolation between the solutions obtained by SWA and SGDIzmailov et al. (2018) have done a similar experiment.. One can observe that there is no “bump” between these two solutions, meaning they are located in the same basin. Clearly, the SWA solution is biased towards the flat side, which verifies our theoretical analysis in Section 5. Further, we notice that although the biased SWA solution has higher training loss than the empirical minimizer, it indeed yields lower test loss. This verifies our analysis in Section 4. Similar observations are made on other networks and other datasets, which we present in Appendix F.

To further support our claim, we list our result in Table 1, from which we can observe that SGD solutions always have higher training accuracy, but worse test accuracy, compared to SWA solutions. This supports our claim in Theorem 1, which states that a bias towards the flat sides of asymmetric valleys could help improve generalization, although it yields higher training error.

We further verify that averaging SGD solutions could create a bias towards the flat side in expectation for many other asymmetric directions, not just for the specific direction we discussed above.

We take a ResNet-110 trained on CIFAR-100 as an example. Denote $\boldsymbol{u}_{inter}$ as the unit vector pointing from the SGD solution to the SWA solution. We pick another unit random direction $\boldsymbol{u}_{rand}$. Then, we use the direction $\boldsymbol{u}_{inter}+\boldsymbol{u}_{rand}$ to verify our claim.

The results are shown in Figure 9, from which we can observe that SWA has a bias on the flat side compared with the SGD solution. We create $10$ different random vectors for each network and each dataset, and similar observations can be made (see more examples in Appendix G).

2 Illusion case 2: large batch SGD

Keskar et al. (2017) observed that training with small batch size using SGD algorithm generalizes better than training with large batch size. They argue that it is because large batch SGD tends to converge to sharp minima, while small batch SGD generally converges to flat minima. Here we show that it may not be the case in practice.

We use a PreResNet-164 trained on CIFAR-100 as an example. We first running SGD with a batch size of 128 for 200 epochs to find a solution (denoted as Large batch solution), and then contintue the training with batch size 32 for another 80 epoch to find a nearby solution (denoted as Small batch solution).

From the results shown in Figure 10, it is clear that the small batch solution has worse training accuracy but better test accuracy. Meanwhile, there is no ’bump’ between these solutions which suggests they are in the same basin. Therefore, small batch SGD generalizes better because it could find a better biased solution in the asymmetric valley, not because it finds a different wider or flatter minimum.

3 Illusion on the width of a minimum

We further point out that visualizing the “width” of a local minimum in a low-dimensional space may lead to illusive results. For example, one visualization technique (Izmailov et al., 2018) is showing how the loss changes along many random directions $\boldsymbol{v}_{i}$’s drawn from the $d$-dimensional Gaussian distribution.

We take the large batch and small batch solutions from the previous subsection as our example. Figure 11 visualizes the “width” of the two solutions using the method described above. From the figure, one may draw the conclusion that small batch training leads to a wider minimum compared to large batch training. However, as discussed in Subsection 6.2 these two solutions are actually from the same basin. In other words, the loss curvature near the two solutions looks different because they are located at different locations in an asymmetric valley, instead of being located at different local minima. Similar observation holds for SWA and SGD solutions, see Appendix H.

Batch Norm and Asymmetric Valleys

Preview sections have focused on defining what are asymmetric valleys, and how to leverage them for better generalization. In this section, we take a step forward to answer where they originate, by showing empirical evidences that the Batch Normalization (BN) (Ioffe & Szegedy, 2015) adopted by modern neural networks seems to be a major cause for asymmetric valleys.

For a given SGD solution, if we take a random direction where only the BN parameters have non-zero entries, and compare it with a random direction where only the non-BN parameters have non-zero entries, we observe that those BN-related directions are usually more asymmetric. The result with ResNet-110 on CIFAR-10 is shown in Figure 12. As we can see, the Non-BN direction is sharp on both sides, but BN direction is flat on one side, and sharp on the other side. We also conducted trials with different networks and datasets, and obtained similar results (see Appendix I).

SGD averaging is more effective on BN parameters.

By Theorem 1 and 2, we know that SGD averaging could lead to biased solutions on asymmetric directions with better generalization. If BN indeed creates many asymmetric directions, can we improve the model performance by only averaging the weights of BN layers?

Note that BN parameters only constitute a small fraction of the total model parameters, e.g., 1.41% in a ResNet-110. In the follow experiment on ResNet-110 for CIFAR-10, we perform SGD averaging only on BN parameters, denoted as SWA-BN; and also averaging randomly selected non-BN parameters of the same amount (1.41% of the total parameters), denoted as SWA-Non-BN. The results are shown in Figure 13. It can be observed that averaging only BN parameters (blue curve) is more effective than averaging non-BN parameters (green curve), although there is still a gap comparing to averaging all the weights (yellow curve).

Moreover, we also conduct experiments with two 8-layer ResNets on CIFAR-10, one with BN layers and one without. We choose shallow networks here as deeper models without BN can not be effectively trained.

As shown in figure 14, we start weight averaging at the $126$-th epoch. Although in both networks, we observe an improvement in test accuracy after averaging, it is clear that the network with BN layers have larger improvement compared with the network without BN layers. This again indicates that SGD averaging is more effective on BN parameters.

The results presented above are still quite preliminary. Understanding how the asymmetric valleys are formed in deep networks might be a valuable future research direction.

Conclusion

The width of solutions has been used to explain generalization. In this paper, we elaborate on these arguments, and show that width along Asymmetric Valleys, where the loss may increase at different rates along two opposition directions, is especially important for explaining generalization. Based on a formal definition of asymmetric valley, we showed that a biased solution lying on the flat side of the valley generalizes better than the empirical minimizer. Further, it is proved that by averaging the points along the SGD trajectory naturally leads to such biased solution. We have conducted extensive experiments with state-of-the-art deep models to verify our theorems. We hope this paper will strengthen our understanding on the loss landscape of deep neural networks, and inspire new theories and algorithms that further improve generalization.

References

Appendix A Additional Figures for Section 3.2: Asymmetric Directions

See Figure 15, Figure 16, Figure 17, Figure 18, and Figure 19.

Appendix B Missing Proof for Theorem 1

Since $\boldsymbol{\delta}$ has $2^{d}$ possible value for a given $\bar{\boldsymbol{\delta}}$, we can use an integer $j\in\{0,\cdots,2^{d}-1\}$ to represent each value. When writing $j$ in binary, its $i$-th digit represents whether ${\boldsymbol{\delta}}_{i}=\boldsymbol{\bar{\delta}}_{i}$ (equal to $1$) or ${\boldsymbol{\delta}}_{i}=-\boldsymbol{\bar{\delta}}_{i}$ (equal to ). We use $j\wedge 2^{i}$ to represent the bitwise AND operator between $j$ and $2^{i}$, which equals if the $i$-th digit of $j$ is .

To prove our theorem, it suffices to show that for any $i\in[k]$,

If (1) is true, it suffices to take summation over $i$ on both sides, and we will get our conclusion. Therefore, below we will prove (1).

Where 1 holds by Assumption 1, and the fact that $\|\sum_{i_{0}=1}^{i-1}\boldsymbol{l}_{i_{0}}\boldsymbol{u}_{i_{0}}\|_{2}\leq\|\boldsymbol{l}\|_{2}=R$. For every $j$ s.t. $j\wedge 2^{i}=0$,

Since $\boldsymbol{l}_{i}\leq r-\boldsymbol{\bar{\delta}}_{i}$, we have $\boldsymbol{\bar{\delta}}_{i}+\boldsymbol{l}_{i}\leq r$. Therefore,

Where 2 holds by Assumption 1 and the fact that $\|\sum_{i_{0}=1}^{i}\boldsymbol{l}_{i_{0}}\boldsymbol{u}_{i_{0}}\|_{2}\leq\|\boldsymbol{l}\|_{2}=R$. That means,

Where the last inequality holds as $\boldsymbol{l}_{i}>\frac{4\xi}{(c_{i}-1)p_{i}}$.

Appendix C Additional Figures for Section 4.2: Shift Exists Empirically

Appendix D Additional Figures in Section 5: Averaging Works For Symmetric Case

If the function is symmetric, there are two possible cases, as we show in Figure 23 and Figure 24. On one hand, if the function is flat, SGD is likely to stay on one side of the function along the trajectory, and the average will have bias on that side. On the other hand, if the function is sharp, SGD is likely to oscillate between the two sides, and therefore the average of the iterates will concentrate around the center. In both cases, SGD averaging could help to create bias on flat sides or to denoise.

Appendix E Missing Proof for Theorem 2

To prove Theorem 2, we will need the following concentration bound.

Let $p_{\min}\triangleq-\eta(a_{-}+a_{+}+2\nu)$, $p_{\max}\triangleq-\eta(b_{-}-\nu)$. Since $-a_{-}=ca_{+}$, we know $p_{\min}>(c-1)\eta a_{+}-2\eta\nu$. First, we have the following bounds on the first step $w_{0}$.

For every $i\in[h]$, $w_{0}\in[p_{\min},p_{\max}]$.

Since $w_{0}$ is the first step that SGD jumps from the flat side to the sharp side, denote the previous location as $w_{-1}<0$. Since $w_{-1}$ is at the sharp side, we know that the gradient is $\nabla\mathsf{L}(w_{-1})\leq a_{-}$. Therefore, we have

Where $\omega_{-1}$ is the noise bounded by $\nu$.

At the time when SGD jump from the flat side to sharp side, denote the target position as $w^{\prime}_{-1}$. We know that $w^{\prime}_{-1}\in[-\eta(a_{+}+\nu),0]$. Since the gradient on the sharp side is at most $a_{-}$, we know the next step is lower bounded by $-\eta(a_{+}+2\nu+a_{-})=p_{\min}>0$. In other words, SGD stays at the sharp side for only $1$ iterations (this matches with our empirical observation, see e.g. Figure 5).

That means, the bound on $w^{\prime}_{-1}$ can be applied to $w_{-1}$ as well, because they are the same iterate. By applying the upper and lower bound on $\nabla\mathsf{L}(w_{-1})$, we get:

Below we first define $T_{\min}\triangleq\left(\frac{-\sqrt{2}\nu\log^{1/2}(2\tau)+\sqrt{2\nu^{2}\log(2\tau)-4a_{+}(a_{-}+a_{+}+2\nu)}}{2a_{+}}\right)^{2}$, where $\tau$ is a constant with value to be set later. $T_{\min}$ satisfies the following inequality.

$\forall t\leq T_{\min},p_{\min}-t\eta a_{+}-\sqrt{2t}\eta\nu\log^{1/2}(2\tau)\geq 0$.

Now, we have the following theorem that says with decent probability, the minimum number of iterates on the flat side in $i$-th round is at least $T_{\min}$.

If we start at $w_{0}\geq p_{\min}$, for every fixed $\tau>T_{\min}$, with probability at least $1-\frac{T_{\min}}{\tau}$, we have $\forall t\leq T_{\min},w_{t}>w_{0}-t\eta a_{+}-\sqrt{2t}\eta\nu\log^{1/2}(2\tau)\geq 0$.

Define filtration $\mathcal{F}_{t}=\sigma\{\omega_{0},\cdots,\omega_{t-1}\}$, where $\sigma\{\cdot\}$ denotes the sigma field. Define the event $\mathfrak{E}_{T}=\{\forall t\leq T,w_{t}>w_{0}-t\eta a_{+}-\sqrt{2t}\eta\nu\log^{1/2}(2\tau)\}$ and define $G_{t}=w_{0}-w_{t}-t\eta a_{+}+M$, where $M\triangleq(T_{\min}+1)(w_{0}+\nu+2\eta a_{+})$. Since we only consider the case $t\leq T_{\min}$, we have

Therefore, $G_{t}$ is always positive. By SGD updating rule, we have

We can also bound the absolute value of the difference in every iteration:

Similarly, we define $T_{\max}\triangleq\left(\frac{-\sqrt{2}\nu\log^{1/2}(2\tau)+\sqrt{2\nu^{2}\log(2\tau)-4(b_{-}-\nu)b_{+}}}{2b_{+}}\right)^{2}$, which satisfies the following inequality.

$p_{\max}-T_{\max}\eta b_{+}-\sqrt{2T_{\max}}\eta\nu\log^{1/2}(2\tau)<0$.

By the definition of $p_{\max}$, we want to show that

Which holds by the definition of $T_{\max}$. ∎

The Theorem below shows with decent probability, $T_{\max}-1$ is an upper bound on the total number of iterates on the flat side in the $i$-th round.

If $w_{0}\leq p_{\max}$, with probability at least $1-\frac{T_{\max}}{\tau}$, $w_{T_{\max}}<0$.

Define event $\mathfrak{E}^{\prime}_{T}=\{\forall t\leq T,w_{t}<w_{0}-t\eta b_{+}+\sqrt{2t}\eta\nu\log^{1/2}(2\tau)\}$, and $G_{t}^{\prime}=w_{t}+t\eta b_{+}>0$.

We can also bound the absolute value of the difference in every iteration:

Remark. To make sure Theorem 6 is not vacuous, we need to make sure that $T_{\min}\geq 1$. If we want to make $T_{\min}$, say, at least $2$, by Lemma 5, we have:

Notice that $p_{\min}>(c-1)\eta a_{+}-2\eta\nu$, so we could solve the above inequality and get

Since we assume that $c$ is a large constant and $a_{+}\geq\nu$, so $\tau$ can be fairly large in order to make sure $T_{\min}\geq 2$. We also know that $T_{\min}\leq\frac{-(a_{-}+a_{+}+2\nu)}{a_{+}}<c$.

On the other hand, by simple calculation, we know $T_{\max}\leq\frac{-(b_{-}-\nu)}{b_{+}}<c^{\prime}<\frac{e^{c/3}}{6}$. Therefore, we can always pick a $\tau$ such that $\frac{T_{\min}+T_{\max}}{\tau}\leq\frac{1}{2}$. So finally, we are ready to prove Theorem 2.

By Lemma 4 and Theorem 8, $T_{\max}$ is an upper bound on the length of the $i$-th round. By Theorem 6, we know that SGD will stay at flat side for at least $T_{\min}$ steps, and each step is lower bounded by $w_{t}>w_{0}-t\eta a_{+}-\sqrt{2t}\eta\nu\log^{1/2}(2\tau)$, therefore we know that with probability $1-\frac{T_{\min}+T_{\max}}{\tau}$:

The above inequality discussed the scenario when Theorem 6 and Theorem 8 hold. If they do not hold, which happens with probability at most $\frac{T_{\min}+T_{\max}}{\tau}$, we need to get lower bound for $\frac{1}{T_{i}}\sum_{j=0}^{T_{i}}w^{i}_{j}$. Notice that by Lemma 4, we know that SGD stays at the sharp side for at most $1$ iterate in each round, and also the iterates on the flat sides are always positive with $w_{0}\geq p_{\min}>\eta(a_{+}+\nu)$. Therefore, we have the following trivial bound:

Since we can pick $\tau$ s.t. $\frac{T_{\min}+T_{\max}}{\tau}\leq\frac{1}{2}$, we have

Appendix F Additional Figures in Section 6.1: No Bumps Between SGD and SWA Solutions

Asymmetric valley of ResNet-110 on CIFAR-10, $(r,p,c,\zeta)=(5,0.005,25,3)$. See Figure 25.

Asymmetric valley of ResNet-164 on CIFAR-10, $(r,p,c,\zeta)=(2,0.015,6,1)$. See Figure 26.

Asymmetric valley of DenseNet-100 on CIFAR-10, $(r,p,c,\zeta)=(6,7.35e-05,699,3)$. See Figure 27

Appendix G Additional Figures in Section 6.1: SGD Averaging Generates Good Bias

Examples for asymmetric directions of ResNet-110 on CIFAR-100 in Figure 28.

Examples for asymmetric directions of ResNet-164 on CIFAR-100 in Figure 29,

Examples for asymmetric directions of ResNet-110 on CIFAR-10 in Figure 30.

Appendix H Additional Figure for Section 6.3: Width of Minima

See Figure 31, similar results were observed by (Izmailov et al., 2018) as well.

Appendix I Additional Figures for Section 7: BN Parameters Are More Asymmetric