What is the Long-Run Distribution of Stochastic Gradient Descent?

Even though it's been around for more than 70 years, stochastic gradient descent (SGD) remains the go-to method for solving large-scale non-convex optimization problems and training deep learning models and networks. However, we know surprisingly little about the algorithm's long-run behavior—for example, which local minimizers are more likely to be observed in the long run (and by how much)? Using an approach based on the theory of large deviations and randomly perturbed dynamical systems, we show that the long-run distribution of SGD resembles the Boltzmann-Gibbs distribution of equilibrium thermodynamics with temperature equal to the method's step-size and energy levels determined by the problem's objective and the statistics of the noise entering the process. In particular, we show that, in the long run (i) the iterates of SGD spend an exponentially small amount of time away from the problem's critical region; (ii) any given critical point (or manifold thereof) is visited with probability that is exponentially proportional to its energy; (iii) minimizers are visited exponentially more often than non-minimizers; and (iv) SGD becomes exponentially concentrated around the problem's “ground state” (which does not always coincide with the minimum of the objective).