Early Stopping as Nonparametric Variational Inference

David Duvenaud, Dougal Maclaurin, Ryan P. AdamsAISTATS 2016 · OpenReview

Abstract

We show that unconverged stochastic gradient descent (SGD) can be interpreted as sampling from a nonparametric approximate posterior distribution. This distribution is implicitly defined by the transformation of an initial distribution by a sequence of optimization steps. By tracking the change in entropy of this distribution during optimization, we give a scalable, unbiased estimate of a variational lower bound on the log marginal likelihood. This bound can be used to optimize hyperparameters instead of cross-validation. This Bayesian interpretation of SGD also suggests new overfitting-resistant optimization procedures and gives a theoretical foundation for early stopping and ensembling. We investigate the properties of this marginal likelihood estimator on neural network models.

Introduction

In machine learning, practitioners often rely on heuristics like early stopping and ensembling to prevent overfitting. While effective, these methods lack a rigorous theoretical foundation. If the goal of optimization is to find the best parameters, why should stopping early yield better generalization? This paper addresses this gap by reinterpreting the entire optimization process as a form of variational inference. We argue that incomplete optimization is not merely a shortcut but a way of approximating a full Bayesian posterior distribution.

Methods: Tracking the Entropy of Optimization

The core methodology treats the optimization process as a sequence of transformations applied to an initial distribution, which acts as the prior.

  1. The Variational View: Instead of seeking a single Maximum A Posteriori (MAP) point, we view the distribution of parameters at any given step of optimization as a nonparametric approximation of the true posterior.
  2. Tracking Entropy: To calculate the Evidence Lower Bound (ELBO), one must track the entropy of the distribution. We demonstrate that the change in entropy at each SGD step is related to the log-determinant of the Jacobian of the update rule.
  3. Scalable Estimation: Computing determinants for high-dimensional models is typically $O(D^3)$. We introduce an $O(D)$ approximation using a second-order Taylor expansion and Hessian-vector products, which are efficiently computed via modern auto-differentiation.
  4. Entropy-Friendly SGD: We propose a modified SGD that "warps" the gradient to prevent the distribution from collapsing into low-entropy filaments too quickly, maintaining a more robust variational approximation.
Evolution of the parameter distribution during SGD optimization, moving from a broad prior to a narrow posterior.

Key Insights: Optimization as Inference

The most profound insight is that an optimizer acts as a sampler. Every step of SGD moves the model from a broad, high-entropy prior toward a narrow, low-entropy peak. The intermediate steps represent a "sweet spot" where the model has learned from the data but has not yet collapsed into an overfitted point.

Unlike standard Variational Inference, which often assumes a simple Gaussian posterior, this method allows for complex, nonparametric shapes defined by the optimization path itself. As shown in the comparison below, early stopping effectively captures the distribution while it still overlaps significantly with the true posterior.

The approximate posterior at various iterations compared to the true posterior (black outline). Early stopping captures the distribution before it collapses into a point.

Key Results

  • Validation-Free Stopping: On the Boston Housing dataset, the estimated marginal likelihood peaked at the exact iteration where test-set error was minimized. This allows for determining stopping points using only training data.
  • Model Selection: The estimator correctly penalizes overly complex models. In MNIST experiments, the marginal likelihood began to decrease as the number of hidden units increased beyond a certain point, even as training likelihood continued to improve.
  • Computational Efficiency: The proposed entropy estimator adds only a small constant factor to the cost of a standard SGD step, making it practical for large-scale deep learning models with millions of parameters.

Limitations and Future Work

While promising, the method currently uses a single optimization path, which can lead to high variance; ensembling multiple paths could provide more stable estimates. Additionally, extending this framework to momentum-based optimizers like Adam or RMSProp remains a challenge, as it requires tracking the entropy of auxiliary momentum variables. Future work will focus on taking gradients of this marginal likelihood estimate to automatically tune learning rates and architectures.

Summary updated

Abstract

We show that unconverged stochastic gradient descent can be interpreted as sampling from a nonparametric approximate posterior distribution. This distribution is implicitly defined by the transformation of an initial distribution by a sequence of optimization steps. By tracking the change in entropy of this distribution during optimization, we give a scalable, unbiased estimate of a variational lower bound on the log marginal likelihood. This bound can be used to optimize hyperparameters instead of cross-validation. This Bayesian interpretation of SGD also suggests new overfitting-resistant optimization procedures, and gives a theoretical foundation for early stopping and ensembling. We investigate the properties of this marginal likelihood estimator on neural network models.
BibTeX
@inproceedings{duvenaud2016early,
  author = {David Duvenaud and Dougal Maclaurin and Ryan P. Adams},
  title = {{Early Stopping as Nonparametric Variational Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=LHkLOoTR7a},
}
Figure