We consider two questions at the heart of machine learning; how can we predict if a minimum will generalize to the test set, and why does stochastic gradient descent find minima that generalize well? Our work responds to \citet{zhang2016understanding}, who showed deep neural networks can easily memorize randomly labeled training data, despite generalizing well on real labels of the same inputs. We show that the same phenomenon occurs in small linear models. These observations are explained by the Bayesian evidence, which penalizes sharp minima but is invariant to model parameterization. We also demonstrate that, when one holds the learning rate fixed, there is an optimum batch size which maximizes the test set accuracy. We propose that the noise introduced by small mini-batches drives the parameters towards minima whose evidence is large. Interpreting stochastic gradient descent as a stochastic differential equation, we identify the ``noise scale" $g = \epsilon (\frac{N}{B} - 1) \approx \epsilon N/B$, where $\epsilon$ is the learning rate, $N$ the training set size and $B$ the batch size. Consequently the optimum batch size is proportional to both the learning rate and the size of the training set, $B_{opt} \propto \epsilon N$. We verify these predictions empirically. This paper shows Bayesian principles can explain many recent observations in the deep learning literature, while also discovering practical new insights. BID27 trained deep convolutional networks on ImageNet and CIFAR10, achieving excellent accuracy on both training and test sets. They then took the same input images, but randomized the labels, and found that while their networks were now unable to generalize to the test set, they still memorized the training labels. They claimed these results contradict learning theory, although this claim is disputed BID18 BID7 . Nonetheless, their results beg the question; if our models can assign arbitrary labels to the training set, why do they work so well in practice? Meanwhile BID19 observed that if we hold the learning rate fixed and increase the batch size, the test accuracy usually falls. This striking result shows improving our estimate of the full-batch gradient can harm performance. BID11 observed a linear scaling rule between batch size and learning rate in a deep ResNet, while BID15 proposed a square root rule on theoretical grounds.Many authors have suggested "broad minima" whose curvature is small may generalize better than "sharp minima" whose curvature is large BID4 BID14 . Indeed, BID7 argued the results of BID27 can be understood using "nonvacuous" PAC-Bayes generalization bounds which penalize sharp minima, while BID19 showed stochastic gradient descent (SGD) finds wider minima as the batch size is reduced. However BID6 challenged this interpretation, by arguing that the curvature of a minimum can be arbitrarily increased by changing the model parameterization. In this work we show:• The results of BID27 are not unique to deep learning; we observe the same phenomenon in a small "over-parameterized" linear model. We demonstrate that this phenomenon is straightforwardly understood by evaluating the Bayesian evidence in favor of each model, which penalizes sharp minima but is invariant to the model parameterization.• SGD integrates a stochastic differential equation whose "noise scale" g ≈ N/B, where is the learning rate, N training set size and B batch size. Noise drives SGD away from sharp minima, and therefore there is an optimal batch size which maximizes the test set accuracy. This optimal batch size is proportional to the learning rate and training set size 1 .We describe Bayesian model comparison in section 2. In section 3 we replicate the observations of BID27 in a linear model, and show they are explained by the Bayesian evidence. In section 4 we show there is an optimum batch size which maximizes the test set accuracy, and in section 5 we derive scaling rules between the optimum batch size, learning rate, training set size and momentum coefficient. Throughout this work, "generalization gap" refers to the gap in test accuracy between small and large batch SGD training, not the gap in accuracy between training and test sets. Just like deep neural networks, linear models which generalize well on informative labels can memorize random labels of the same inputs. These observations are explained by the Bayesian evidence, which is composed of the cost function and an "Occam factor". The Occam factor penalizes sharp minima but it is invariant to changes in model parameterization. Mini-batch noise drives SGD away from sharp minima, and therefore there is an optimum batch size which maximizes the test accuracy. Interpreting SGD as the discretization of a stochastic differential equation, we predict this optimum batch size should scale linearly with both the learning rate and the training set size, B opt ∝ N . We derive an additional scaling rule, B opt ∝ 1/(1 − m), between the optimal batch size and the momentum coefficient. We verify these scaling rules empirically and discuss their implications.
Generalization is strongly correlated with the Bayesian evidence, and gradient noise drives SGD towards minima whose evidence is large.
{"src": "scitldr-AIC_train", "paper_id": "BJij4yg0Z"}