A Rule for Gradient Estimator Selection, with an Application to Variational Inference

Tomas Geffner, Justin Domke

Abstract

Stochastic gradient descent (SGD) is the workhorse of modern machine learning. Sometimes, there are many different potential gradient estimators that can be used. When so, choosing the one with the best tradeoff between cost and variance is important. This paper analyzes the convergence rates of SGD as a function of time, rather than iterations. This results in a simple rule to select the estimator that leads to the best optimization convergence guarantee. This choice is the same for different variants of SGD, and with different assumptions about the objective (e.g. convexity or smoothness). Inspired by this principle, we propose a technique to automatically select an estimator when a finite pool of estimators is given. Then, we extend to infinite pools of estimators, where each one is indexed by control variate weights. This is enabled by a reduction to a mixed-integer quadratic program. Empirically, automatically choosing an estimator performs comparably to the best estimator chosen with hindsight.

Introduction

In modern machine learning, particularly within the domain of Stochastic Gradient Variational Inference (SGVI), practitioners are often faced with a "menu" of gradient estimators. These estimators present a fundamental tradeoff: some, like the standard reparameterization trick, are computationally efficient but high-variance; others incorporate control variates to reduce noise at the expense of significantly increased wall-clock time per iteration.

The central challenge lies in determining whether it is more effective to perform many noisy, fast updates or fewer, cleaner, slow updates. Historically, this selection has relied on researcher intuition or computationally expensive cross-validation. This work formalizes this cost-variance tradeoff, introducing a universal principle to navigate it in terms of actual wall-clock time.

The $G^2T$ Principle

The core theoretical contribution of this paper is the $G^2T$ principle. By analyzing the convergence rates of various Stochastic Gradient Descent (SGD) variants—including convex, strongly convex, and smooth objectives, as well as accelerated methods like Momentum and Nesterov—the authors demonstrate that the error bound consistently depends on the term $(G^2 T)^p$.

Here, $G^2$ represents the squared norm of the gradient estimator (a proxy for variance) and $T$ represents the computational time per iteration. Consequently, the "optimal" estimator is defined as the one that minimizes the product $G^2 \times T$. This rule is remarkably robust, holding true regardless of the specific mathematical properties of the model or the optimization algorithm employed.

Algorithmic Framework for Adaptive Selection

Since $G^2$ and $T$ are typically unknown a priori, the authors propose two algorithms to apply the $G^2T$ principle dynamically:

  1. Adaptive Selection (Algorithm 1): Designed for a finite pool of candidate estimators, this algorithm periodically pauses training to empirically estimate $G^2$ and $T$ for each candidate, subsequently switching to the estimator that minimizes their product.
  2. Control Variate Selection via MIQCP (Algorithm 2): For scenarios involving an infinite pool of estimators (e.g., weighted combinations of multiple control variates), the selection problem is reduced to a Mixed-Integer Quadratic Program (MIQCP). This allows the system to efficiently determine which control variates provide sufficient noise reduction to justify their computational cost and to calculate their optimal weights.

Experimental Evaluation

The proposed methods were evaluated across several probabilistic models, including Bayesian Logistic Regression (using a1a and Mushrooms datasets), a Hierarchical Poisson Model (Frisk dataset), and Bayesian Neural Networks (Red-wine dataset).

Performance of various fixed gradient estimators across different probabilistic models.

As shown in the figure above, the "best" fixed estimator is highly task-dependent. For instance, while the STL estimator performs best for BNN-A, the Reparameterization (Rep) trick is superior for BNN-B, and the Miller estimator excels in the Hierarchical Poisson task.

Key Results

The empirical results demonstrate that the "Auto" selection algorithm consistently performs as well as, or better than, the best fixed estimator chosen with the benefit of hindsight.

Comparison of the adaptive selection algorithm (Alg. 1) against fixed estimators on the Hierarchical Poisson model.

In the Hierarchical Poisson task (shown above), Algorithm 1 successfully identifies and tracks the performance of the Miller estimator, which is the optimal choice for this specific problem. Furthermore, in tasks like Bayesian Logistic Regression on the a1a dataset, the algorithm correctly identifies that certain complex control variates are too slow to be worth the noise reduction, opting instead for faster, simpler estimators.

Discussion and Limitations

While the $G^2T$ principle provides a powerful heuristic, it has certain limitations:

  • Step-size Dependence: The principle assumes the learning rate is optimized for the specific estimator. If the step size is excessively small, optimization becomes "iteration limited" rather than "variance limited," reducing the effectiveness of the $G^2T$ rule.
  • Local vs. Global Bounds: The theory assumes a global bound for $G^2$, but the implementation uses local estimates at the current parameter values. While empirically successful, the theoretical implications of this local approximation require further study.

Future research may explore the simultaneous adaptation of step sizes and estimators to further accelerate convergence.

Summary updated

Abstract

Stochastic gradient descent (SGD) is the workhorse of modern machine learning. Sometimes, there are many different potential gradient estimators that can be used. When so, choosing the one with the best tradeoff between cost and variance is important. This paper analyzes the convergence rates of SGD as a function of time, rather than iterations. This results in a simple rule to select the estimator that leads to the best optimization convergence guarantee. This choice is the same for different variants of SGD, and with different assumptions about the objective (e.g. convexity or smoothness). Inspired by this principle, we propose a technique to automatically select an estimator when a finite pool of estimators is given. Then, we extend to infinite pools of estimators, where each one is indexed by control variate weights. This is enabled by a reduction to a mixed-integer quadratic program. Empirically, automatically choosing an estimator performs comparably to the best estimator chosen with hindsight.
BibTeX
@inproceedings{geffner2020rule,
  author = {Tomas Geffner and Justin Domke},
  title = {{A Rule for Gradient Estimator Selection, with an Application to Variational Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=HudbHYq7Se5},
}
Figure