PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric Valleys: Beyond Sharp and Flat Local Minima

Haowei He, Gao Huang, Yang Yuan

arXiv:1902.00744v2cs.LGstat.ML

TL;DR

The paper addresses whether sharpness and flatness adequately explain generalization in deep networks. It formalizes asymmetric valleys, proves that flat-side-biased solutions generalize better under mild assumptions, and shows that SGD averaging produces such bias. Experiments report prevalent asymmetric valleys and suggest batch normalization as a major cause.

  • Problem

    Existing explanations centered on sharp or flat minima are challenged by re-parameterization results, motivating a broader account of local geometry and generalization.

  • Method

    The paper defines asymmetric valleys, analyzes flat-side-biased solutions theoretically, and studies SGD trajectory averaging and empirical loss landscapes.

  • Results

    Flat-side-biased solutions generalize better than exact minimizers under mild assumptions, while SGD averaging implicitly produces this bias and experiments find asymmetric valleys prevalent.

  • Takeaways & Limitations

    Generalization depends not only on which minimum is reached but also on where the solution lies within an asymmetric valley.

  • Takeaways & Limitations

    The paper cannot rigorously verify that empirical SGD solutions are local minima and therefore treats such points as minima despite possible negative Hessian eigenvalues.

Abstract

from arXiv · show

Despite the non-convex nature of their loss functions, deep neural networks are known to generalize well when optimized with stochastic gradient descent (SGD). Recent work conjectures that SGD with proper configuration is able to find wide and flat local minima, which have been proposed to be associated with good generalization performance. In this paper, we observe that local minima of modern deep networks are more than being flat or sharp. Specifically, at a local minimum there exist many asymmetric directions such that the loss increases abruptly along one side, and slowly along the opposite side--we formally define such minima as asymmetric valleys. Under mild assumptions, we prove that for asymmetric valleys, a solution biased towards the flat side generalizes better than the exact minimizer. Further, we show that simply averaging the weights along the SGD trajectory gives rise to such biased solutions implicitly. This provides a theoretical explanation for the intriguing phenomenon observed by Izmailov et al. (2018). In addition, we empirically find that batch normalization (BN) appears to be a major cause for asymmetric valleys.

1. Introduction

The paper argues that sharpness and flatness alone do not capture modern neural-network minima, introducing asymmetric valleys and analyzing their generalization and optimization implications.

  • Motivation: Recent evidence challenges flatness as a complete characterization because re-parameterization can create arbitrarily sharp minima without changing generalization.Connected low-loss paths between minima further complicate explanations based solely on sharpness.
  • Asymmetric valleys: Asymmetric valleys contain directions where loss rises abruptly on one side but slowly on the other.The paper formally defines these asymmetric local minima and notes that solutions farther from the sharp side can appear wider and flatter.
  • Generalization: Under mild assumptions, a solution biased toward the flat side generalizes better than the exact training minimizer.This implies that location within a valley can matter more than which connected local minimum is selected.
  • SGD averaging: Averaging weights along the SGD trajectory naturally produces the desired flat-side bias.The paper provides a theoretical analysis connecting this mechanism to prior empirical observations.
  • Empirical findings: Experiments find asymmetric valleys prevalent in modern deep networks and identify batch normalization as a major apparent cause of asymmetric loss surfaces.Lower-generalization-error solutions also show bias toward the flat side.

2. Related Work

Prior work studied landscape connectivity, sharp and flat minima, and SGD’s optimization behavior; this paper extends that discussion with asymmetric directions and SGD’s flat-side implicit bias.

  • Neural network landscape: Neural-network studies report that essentially all local minima can be connected by simple paths and that ensembles of intermediate models can improve accuracy.These findings motivate analyzing landscape structure beyond isolated minima.
  • Sharp and flat minima: Sharp-minimum research linked large-batch SGD to poorer generalization, while other work pursued flat minima through entropy regularization.Later results showed large-batch training can achieve comparable performance with suitable learning rates or training durations.
  • Sharp and flat minima: The paper argues that sharp-versus-flat descriptions are oversimplified because one minimum may contain steep, flat, and asymmetric directions simultaneously.This reframes local geometry as multi-directional rather than governed by one scalar notion of width.
  • SGD optimization and generalization: SGD research has examined escaping saddle points and sharp minima, while this paper identifies an additional implicit bias toward flat sides.The paper places SGD averaging within a broader literature on implicit bias.

3. Asymmetric Valleys

The paper formalizes asymmetric valleys as local minima with directions exhibiting unequal loss-growth rates and reports that such directions occur broadly in modern deep networks.

  • Setup: The analysis studies empirical-risk minimizers obtained from sampled training data rather than directly optimizing the unknown population loss.SGD is used to find the empirical minimizer.
  • Geometric setup: The paper uses a unit vector to represent a direction through a parameter point and describes the local valley geometry along that line.It notes that the term valley is used for a point at the center of the valley.
  • Definition: An asymmetric direction is characterized by small positive-side gradients and substantially larger negative-side gradients over a specified interval.The formal condition uses constants p, r, c, and ζ with c > 1.
  • Definition: The paper defines asymmetric valleys as local minima possessing at least one asymmetric direction.An asymmetric direction has different loss-growth rates along its positive and negative orientations.
  • Empirical prevalence: Experiments on ResNet-110, ResNet-164, and DenseNet-100 across CIFAR-10 and CIFAR-100 consistently find asymmetric directions with c > 2.Each model-dataset combination was evaluated in five independent runs.

4. Bias and Generalization

The paper models generalization through shifts between empirical and population loss and proves that, under mild assumptions, bias toward the flat side of an asymmetric valley can outperform the empirical minimizer. Experiments verify the assumptions and observe corresponding lower test loss.

  • Assumptions: The analysis assumes a shift between empirical and population loss and a locally asymmetric neighborhood around the empirical minimizer.The shift is formalized through a bounded shift gap, while local asymmetry requires orthogonal directions to remain asymmetric across nearby points.
  • Theoretical result: Under these assumptions, a solution biased toward the flat side of an asymmetric valley has lower generalization error than the empirical minimizer.The theorem applies when the bias coordinates satisfy the stated bounds relative to the asymmetry parameters and shift.
  • Implication: The empirical minimizer need not be the best solution under the modeled population-loss shift, although the shift is difficult to identify in practice.The paper therefore motivates selecting a biased solution rather than relying only on empirical-loss minimization.
  • Empirical verification: A ResNet-110 on CIFAR-10 shows that shifting the test-loss curve by δ=0.4 reduces the shift gap from 0.223 to 0.0335.The shifted test and training curves nearly overlap, and similar observations were reported across directions, models, and datasets.
  • Empirical verification: For neighboring points around a ResNet-110 solution, the projected loss curves have small variance and remain (4, 0.1, 5.22, 2)-asymmetric.The neighborhood was sampled using 100 local adjustments, supporting the locally asymmetric assumption.

5. Averaging Generates Good Bias

The paper shows that averaging SGD iterates produces the flat-side bias predicted to improve generalization in asymmetric valleys. This bias arises because SGD spends more time on the flat side, including in regimes without oscillation.

  • Overview: Averaging SGD iterates is proposed as a practical way to obtain solutions biased toward the flat side of an asymmetric valley.The analysis first considers one-dimensional dynamics and then extends the argument to higher-dimensional directions.
  • Oscillation case: With a learning rate that is not too small, SGD oscillates between the sharp and flat sides, while averaging each oscillation round biases the result toward the flat side.The mechanism is that smaller gradients on the flat side keep SGD there for more iterations.
  • Theoretical result: Theorem 2 states that, under asymmetric-gradient and bounded-noise assumptions, SGD averaging generates a positive expected bias.The formal bound uses an asymmetric valley, gradient bounds, a sufficiently large sharp-to-flat gradient ratio, and bounded update noise.
  • Small-learning-rate case: When the learning rate is sufficiently small and oscillations disappear, averaging still creates more flat-side bias in expectation because SGD converges faster on the sharp side.The paper consequently argues that trajectory averaging may help across both oscillatory and non-oscillatory regimes.
  • High-dimensional case: Projected-loss experiments find that the assumptions of the one-dimensional analysis become relatively stable after the first 40 epochs, and SGD averaging creates bias along different asymmetric directions.The projections are evaluated along random directions over SGD checkpoints and offsets.

6. Sharp and Flat Minima Illusion

The section shows that apparent sharpness or flatness differences can arise from different locations within the same asymmetric valley rather than from different minima. Across SWA, batch-size, and width visualizations, solutions biased toward the flat side have better test performance despite higher training loss.

  • Where a solution locates within a local-minimum basin matters beyond judging the basin as sharp or flat.
  • 6.1. Illusion case 1: SWA algorithm: SWA and SGD solutions can lie in the same basin, yet SWA is biased toward the flat side and has lower test loss despite higher training loss.
  • 6.1. Illusion case 1: SWA algorithm: Table 1 reports that SGD solutions have higher training accuracy but worse test accuracy than SWA solutions, supporting the benefit of flat-side bias.
  • 6.2. Illusion case 2: large batch SGD: Small-batch SGD produces worse training accuracy but better test accuracy than large-batch SGD, while both solutions remain in the same basin.
  • 6.3. Illusion on the width of a minimum: Random-direction visualizations can make small-batch training appear to find a wider minimum, although the compared solutions are actually in the same asymmetric valley.
  • 6.3. Illusion on the width of a minimum: The paper cautions that apparent curvature differences reflect solution location within an asymmetric valley, not necessarily different local minima.

7. Batch Norm and Asymmetric Valleys

The paper presents empirical evidence that batch normalization contributes to asymmetric valleys and that averaging BN parameters is especially effective. Results are described as preliminary, with deeper non-BN networks difficult to train.

  • BN and asymmetric directions: BN-only directions are usually more asymmetric than non-BN directions, which are sharp on both sides.The BN direction is flat on one side and sharp on the other; similar results were obtained across networks and datasets.
  • BN and SGD averaging: SGD averaging only BN parameters is proposed as a targeted way to exploit asymmetric directions.The comparison follows from the claim that averaging in asymmetric directions can produce biased solutions with better generalization.
  • BN and SGD averaging: 1.41% of ResNet-110 parameters are BN parameters, and the experiment compares BN-only averaging with equally sized non-BN averaging.The BN-only condition is denoted SWA-BN, while the matched non-BN condition is denoted SWA-Non-BN.
  • BN and SGD averaging: Weight averaging improves both shallow ResNet-8 networks, but the BN-equipped network shows the larger test-accuracy improvement.The comparison starts averaging at epoch 126; deeper networks without BN were not effectively trainable, motivating shallow models.
  • Caveat: The authors characterize these empirical results as preliminary and leave understanding asymmetric-valley formation as future work.The section does not establish a complete account of how asymmetric valleys arise.

8. Conclusion

The conclusion argues that asymmetric-valley width explains generalization beyond ordinary sharpness or flatness. It states that flat-side-biased solutions generalize better and that SGD trajectory averaging naturally produces them.

  • Conclusion: Asymmetric-valley width is presented as especially important for explaining generalization.These valleys allow loss to increase at different rates along opposite directions.
  • Conclusion: A solution biased toward the flat side of an asymmetric valley generalizes better than the empirical minimizer.The conclusion attributes this result to the paper’s formal definition and analysis of asymmetric valleys.
  • Conclusion: Averaging points along the SGD trajectory naturally produces a solution biased toward the flat side.The conclusion reports this as a proved result supported by experiments with state-of-the-art deep models.
  • Conclusion: The paper aims to strengthen understanding of deep-network loss landscapes and inspire theories and algorithms for improving generalization.This is stated as the paper’s broader intended contribution.

B. Missing Proof for Theorem 1

The proof appendix analyzes how SGD averaging behaves in asymmetric and symmetric directions. It also reports numerical examples of asymmetric directions and shifts on asymmetric versus symmetric directions.

  • Proof representation: The appendix’s proof represents the 2^d sign choices of a perturbation using an integer j and binary digits.Each binary digit indicates whether a coordinate matches or opposes the reference perturbation.
  • Proof representation: The proof applies asymmetric-direction assumptions successively across directions to establish its claimed bounds.The argument constrains perturbations and their components relative to asymmetric directions.
  • Empirical illustrations: The appendix reports asymmetric-direction parameters for ResNet-164 and DenseNet-100 on CIFAR-100.The figures give separate parameter tuples for the two architectures.
  • Empirical illustrations: Shifts are reported for asymmetric directions in DenseNet-100 on CIFAR-100 and ResNet-164 on CIFAR-10.The listed comparisons contrast nonzero shifts with zero-shift references.
  • Symmetric comparison: The appendix contrasts this with a smaller shift on a symmetric direction and illustrates symmetric functions with flat or sharp sides.The symmetric-direction example is from ResNet-110 on CIFAR-100.
  • Symmetric comparison: For symmetric functions, SGD averaging may remain on one side when flat but oscillate around the center when sharp.The appendix uses these cases to explain how averaging can create different biases.

E. Missing Proof for Theorem 2

The proof appendix establishes probabilistic bounds on SGD’s residence times on flat and sharp sides of an asymmetric valley. It uses concentration arguments and combines the resulting cases into the theorem’s bound.

  • Concentration analysis: The proof introduces a concentration bound and uses Azuma’s inequality for the stochastic SGD analysis.The argument defines a supermartingale and bounds its per-iteration differences.
  • Side-transition bounds: The appendix defines pmin and pmax to bound the starting position and analyzes the first transition from the flat side to the sharp side.The sharp-side gradient and bounded noise determine the next-step lower bound.
  • Flat-side residence: With the stated probability bounds, SGD remains on the flat side for at least Tmin steps.The proof establishes this through an event sequence and a theorem controlling the flat-side residence time.
  • Sharp-side residence: The proof separately bounds the sharp-side residence time using Tmax and related inequalities.The appendix states that Tmax−1 bounds the total number of iterates on the flat side in the relevant round.
  • Assumptions: The proof requires conditions such as Tmin≥1 and assumptions on the constants and noise scale.The appendix notes that these conditions are needed to keep the theorem non-vacuous.
  • Combined bound: The combined theorem uses the flat-side and sharp-side cases to derive a probability bound for the SGD behavior.The stated failure event has probability at most (Tmin+Tmax)/τ.

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

Additional figures show asymmetric valleys and SGD–SWA interpolation behavior across ResNet and DenseNet models on CIFAR-10.

  • ResNet-110 on CIFAR-10 exhibits an asymmetric valley with (r, p, c, ζ) = (5, 0.005, 25, 3).The result corresponds to Figure 25.
  • ResNet-164 on CIFAR-10 exhibits an asymmetric valley with (r, p, c, ζ) = (2, 0.015, 6, 1).The result corresponds to Figure 26.
  • DenseNet-100 on CIFAR-10 exhibits an asymmetric valley with (r, p, c, ζ) = (6, 7.35e −05, 699, 3).The result corresponds to Figure 27.

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

Additional figures examine asymmetric directions, SGD averaging, SGD–SWA solutions, and batch-normalization versus non-batch-normalization directions across several network and dataset settings.

  • Examples of asymmetric directions for ResNet-110 on CIFAR-100 are shown in Figure 28.
  • Figures 28 and 29 compare SGD training loss, SWA training loss, the SGD solution, and the SWA solution.
  • Figure 30 shows examples of asymmetric directions for ResNet-110 on CIFAR-10.
  • Figure 31 presents random-ray comparisons between SGD and SWA solutions, with similar results observed by Izmailov et al. (2018).
  • Figures 32–34 compare batch-normalization and non-batch-normalization directions for ResNet-164, ResNet-110, and DenseNet-100.
Loading 1902.00744v2…