PaperExp - "How SGD Selects the Global Minima in Over-parameterized Learning - A Dynamical Stability Perspective"
This blog explains this paper and the maths in it in detail, along with implementation and rigourous maths derivations.
Implementation
Currently only toy example is implemented: Repo link
Maths Prerequisite
What maths knowledge is required to understand this paper completely.
- Expectation
- Eigenvalue
- Multivariate Calculus
- Deep Learning
- Dynamical System
Quotes
- But now in the setting of over-parametrized learning, e.g. deep learning, when there is a large set of global minima, all of which have zero training error but the test error can be very different, this issue becomes highly relevant.
- In fact one might say that the task of optimization algorithms has become: Find the set of parameters with the smallest test error among all the ones with zero training error.
- At the moment, this is clearly an impossible task since we do not have much explicit information about the population risk. Therefore in this paper, we take a limited view and ask the question: Which global minima (of the empirical risk, of course) are accessible to a particular optimization algorithm with a particular set of hyper-parameters?
- Specifically, in deep learning one of the most puzzling issues is the recent observation that SGD tends to select the so-called flat minima,
- and flatter minima seem to generalize better
- The analysis leads to a sharpness-non-uniformity diagram that characterizes the kind of minima that are stable and hence accessible for SGD. We show that both the sharpness and the non-uniformity are important for the selection of the global minima, although we do observe in experiments that these two quantities are strongly correlated for deep neural network models.
Introduction
This blog explains this NeurIPS 2018 paper: “How SGD Selects the Global Minima in Over-parameterized Learning: A Dynamical Stability Perspective” by Lei Wu, Chao Ma and Weinan E.
Let me first state a fact which this paper uses to describe the problem it deals with:
- In deep learning, training error is being optimised but there are many global minimas** (minimas with lowest training error, i.e., zero training error).
- SGD finds flatter minima.
- Flat minima generalise better.
Problem statement: We need to minimise the population risk and not just empirical risk. So, a learning algorithm should choose that global minima of the empirical risk which has the lowest test error.
Since we do not have access to population risk, it is not clear how to solve the above problem.
But there is one particular observation on which this paper relies. By relying on this observation, it gives a way to attack the above difficult problem.
Therefore, this paper relies on the observation that SGD tends to find flat minima, and flat minima seem to generalise better.
How to use this observation to attack the above problem? It says that, for SGD, only some particular “set” of minimas are stable. SGD depends on hyperparameters like learning rate and batch size. So for different values of these hyperparameters, different kinds of minima should be stable. E.g., if, for a bigger learning rate, flatter minima are stable (if LR and flatness of the minima found by SGD are proportional), then we can find more flatter minima by increasing the learning rate. And more flat minimas may generalise even better than the minima which are less flat.
This observation motivates the authors to find an answer to the question: Which global minima are stable for different values of hyperparameters of an optimisation algorithm?
Stable global minima are those minimas which optimisers can converge to. To define the stability of a particular global minima x* mathematically, this paper considers the behaviour of SGD near x, so that the function “f” which is being minimised, can be approximated via Taylor expansion. f is expanded up to the second-order Taylor polynomial around x. This second-order Taylor polynomial is also called a quadratic approximation of f near x*. Because of this approximation, analysis of convergence becomes very easy because now we are dealing with the optimisation of a quadratic function instead of some highly complex function.
We need to first define stability. Authors uses “linear stability”. Linear stability is defined for a linear dynamical system.