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 variance and computational cost is critical. This paper introduces the $G^2T$ principle, a simple and universal rule for choosing the best gradient estimator in stochastic optimization: the optimal estimator is the one that minimizes the product of its expected squared norm ($G^2$) and its computational cost ($T$). By applying this rule adaptively, the authors demonstrate that an algorithm can automatically navigate the tradeoff between gradient noise and wall-clock speed, performing as well as the best estimator chosen with the benefit of hindsight.

The Challenge of Estimator Selection

In modern machine learning, particularly in Stochastic Gradient Variational Inference (SGVI), researchers often have a "menu" of different ways to estimate gradients. Some estimators, like the standard reparameterization estimator, are fast but noisy (high variance). Others use complex techniques like control variates (e.g., the Miller or STL estimators) to reduce noise at the expense of significantly higher computational cost.

Traditionally, choosing between these estimators is done through trial and error or researcher intuition. However, an estimator that works well for a neural network might be overkill for a simple regression, and an estimator that is helpful at the start of training might become inefficient as the model nears convergence. The paper addresses the lack of a formal, automated way to select the estimator that provides the fastest convergence per second of wall-clock time.

The $G^2T$ Principle

The authors derive their selection rule by analyzing standard convergence guarantees for Stochastic Gradient Descent (SGD). They observe that for various types of objectives (convex, strongly convex, or smooth non-convex), the convergence error bound after $K$ iterations is typically proportional to $(G^2/K)^p$ for some power $p$.

Since the number of iterations possible in a fixed time $T_{total}$ is $K \approx T_{total}/T$, the bound becomes proportional to $(G^2 T)^p$. Therefore, to get the best guarantee, one should minimize the product $G^2 T$. This leads to two proposed algorithms:

  1. Algorithm 1 (Finite Pool): For a small set of estimators, the algorithm periodically estimates $T$ (via profiling) and $G^2$ (via Monte Carlo samples at the current parameters) and switches to the estimator with the lowest product.
  2. Algorithm 2 (Infinite Pool/Control Variates): When estimators are formed by a weighted combination of control variates, the authors frame the selection as a Mixed Integer Quadratically Constrained Program (MIQCP). This allows them to use off-the-shelf solvers to find the best weights and the best subset of control variates simultaneously.

Experimental Insights

The authors evaluated their approach on several probabilistic modeling tasks, including Bayesian Logistic Regression (a1a dataset), a Hierarchical Poisson Model (Frisk dataset), and Bayesian Neural Networks (BNNs) using the Red-wine dataset.

Figure 4: Comparison of ELBO vs. Time across different models and fixed estimators. Note that no single estimator (STL, Miller, or Rep) is superior across all tasks.

As seen in Figure 4, there is no universal winner among fixed estimators. For BNN-A, the STL estimator converges fastest; for BNN-B, the plain reparameterization (Rep) estimator is superior; and for the Hierarchical Poisson model, the Miller estimator is the clear winner. This variability underscores the need for an adaptive selection rule.

Key Results

The most striking insight is that the $G^2T$ rule is "structural-blind." Whether the objective is strongly convex or non-convex, the same estimator (the one minimizing $G^2T$) is theoretically optimal for convergence. Furthermore, the experiments confirmed that the "best" estimator is a moving target. The variance of an estimator ($G^2$) changes as the parameters evolve.

Figure 6: Performance of the adaptive Algorithm 1 compared to fixed estimators on Logistic Regression. The adaptive method successfully tracks the performance of the best fixed estimators.

In all experiments, the "Auto" selection method achieved a final Evidence Lower Bound (ELBO) comparable to or better than the best fixed estimator chosen after seeing all results. As shown in Figure 6, Algorithm 1 effectively matches the performance of the top-performing fixed estimators by dynamically evaluating the $G^2T$ metric during training.

Limitations and Future Work

While the $G^2T$ principle provides a robust framework, it assumes that the learning rate (step-size) is chosen optimally for the given estimator. If the step-size is very small, the benefits of variance reduction are diminished. Additionally, the theory relies on a global bound for $G^2$, while the algorithm uses "local" estimates at the current parameters. Proving convergence guarantees using these local estimates remains an open theoretical question. Future work could explore how to simultaneously adapt the estimator and the step-size, as changing the estimator effectively changes the signal-to-noise ratio of the optimization process.

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...
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