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