Batch Size Matters: A Diffusion Approximation Framework on Nonconvex Stochastic Gradient Descent

Chris Junchi Li, Lei Li, Junyang Qian, Jian-Guo LiuarXiv 2017 · OpenReview

TL;DR

This paper provides a rigorous mathematical framework to understand Stochastic Gradient Descent (SGD) in nonconvex optimization by approximating it with diffusion processes. The authors show that this diffusion perspective explains why small batch sizes help escape sharp local minima and saddle points, while larger batch sizes are better for converging to flat minima, crucial for generalization.

What Problem Does This Paper Address?

Training deep neural networks often involves minimizing highly nonconvex loss functions. Stochastic Gradient Descent (SGD) is the workhorse for this, but its behavior, especially its ability to escape undesirable local minima and saddle points, is not fully understood. A key question is how to choose the batch size: small batches introduce more noise, potentially helping escape bad regions, while large batches offer more stable gradients but might get stuck. This paper aims to bridge this gap by providing a theoretical understanding of SGD's dynamics, particularly focusing on the role of batch size in navigating complex loss landscapes.

Methods

The core of the paper is a rigorous mathematical analysis that approximates the discrete-time SGD algorithm with a continuous-time diffusion process (specifically, a stochastic differential equation or SDE). This is achieved by using the weak form of the master equation for probability evolution. The authors then analyze the behavior of this diffusion process, particularly its "escaping times" from local minima and saddle points. They leverage tools from the theory of random perturbations of dynamical systems, including large deviation theory, to derive analytical results about these escaping times. The paper also introduces a specific SDE model for mini-batch SGD and analyzes its properties.

Datasets

The paper uses the MNIST dataset for numerical experiments to evaluate the performance of different batch sizes in training a fully-connected neural network.

Key Insights and Ideas

  • Diffusion as a Lens for SGD: Approximating SGD with diffusion processes provides a powerful analytical tool to understand its global dynamics, especially in nonconvex settings.
  • Batch Size and Noise: The variance of the noisy gradient in SGD scales inversely with batch size. Smaller batches mean higher variance (more noise), which is crucial for escaping difficult parts of the loss landscape.
  • Escaping Sharp Minima and Saddle Points: Small batch sizes, by introducing more noise, are theoretically shown to facilitate faster escaping from sharp local minima and unstable stationary points (saddle points). This aligns with empirical observations in deep learning.
  • Converging to Flat Minima: Conversely, larger batch sizes lead to less noise and more stable convergence, making them suitable for settling into flat local minima, which are generally associated with better generalization.
  • Dynamic Batch Sizing: The theory suggests a strategy of using small batch sizes early in training to escape sharp regions and then increasing the batch size later to converge to flat minima, akin to simulated annealing.

Key Results

  • Theoretical Guarantees: The paper provides rigorous proofs that the diffusion approximation captures the weak dynamics of SGD.
  • Escaping Time Analysis: For local minimizers, the expected escaping time is shown to be exponentially dependent on the inverse step size ($1/\eta$). For saddle points, the escaping time is almost linearly dependent on $1/\eta$.
  • Batch Size Effects: Numerical experiments on MNIST demonstrate that smaller batch sizes lead to greater diffusion (larger Euclidean distance of weights from initialization), and this is correlated with better generalization performance in some scenarios. The paper shows that large batch methods tend to converge to sharper minima, while small batch methods explore more broadly.
  • Conjecture on Noise: The authors propose and experimentally investigate adding artificial noise to large-batch SGD to mimic the diffusion behavior of small-batch SGD, showing it can improve performance.

Limitations and Future Work

  • Fixed Time Interval: The diffusion approximation is rigorously proven for a fixed time interval $[0, T]$. Its validity for arbitrarily long times is discussed but not fully proven in the main text.
  • Dimension-Free Error: The approximation error is characterized by a constant that may depend on the dimension, which is a limitation for very high-dimensional problems.
  • Momentum and Other Optimizers: The current analysis primarily focuses on basic SGD. Extending the framework to include momentum or adaptive methods would be a valuable future direction.
  • Exact Characterization of Escaping Local Minima: While the paper discusses escaping local minima, a more precise characterization of this phenomenon, especially compared to escaping saddle points, is left for future research.
  • Practical Implementation of Dynamic Batch Sizing: While the theory suggests dynamic batch sizing, practical strategies for implementing this effectively in deep learning remain an open area.

Summary updated

Abstract

We study the Stochastic Gradient Descent (SGD) method in nonconvex optimization problems from the point of view of approximating diffusion processes. We prove rigorously that the diffusion process can approximate the SGD algorithm weakly using the weak form of master equation for probability evolution. In the small step size regime and the presence of omnidirectional noise, our weak approximating diffusion process suggests the following dynamics for the SGD iteration starting from a local minimizer (resp.~saddle point): it escapes in a number of iterations exponentially (resp.~almost linearly) dependent on the inverse stepsize. The results are obtained using the theory for random perturbations of dynamical systems (theory of large deviations for local minimizers and theory of exiting for unstable stationary points). In addition, we discuss the effects of batch size for the deep neural networks, and we find that small batch size is helpful for SGD algorithms to escape unstable stationary points and sharp minimizers. Our theory indicates that one should increase the batch size at later stage for the SGD to be trapped in flat minimizers for better generalization.
BibTeX
@misc{li2017batch,
  author = {Chris Junchi Li and Lei Li and Junyang Qian and Jian-Guo Liu},
  title = {{Batch Size Matters: A Diffusion Approximation Framework on Nonconvex Stochastic Gradient Descent}},
  year = {2017},
  eprint = {1705.07562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.07562},
}
Figure