This NeurIPS 2018 paper by Tomas Geffner and Justin Domke tackles one of the most persistent headaches in machine learning: noisy gradients. By providing a systematic "recipe" for creating control variates and a robust Bayesian method to combine them, the authors show that more is indeed merrier when it comes to variance reduction.
The Problem: Drunken Stumbles in Optimization
Variational Inference (VI) is a powerful tool for approximate probabilistic inference, but it relies heavily on stochastic optimization. To find the best approximation, we take steps in the direction of a "gradient." However, in complex models, we can only estimate this gradient.
If this estimate is "noisy" (has high variance), the optimization process becomes a drunken stumble—slow to converge and prone to crashing if the learning rate is too high. Control Variates (CVs) are a classic statistical trick to reduce this noise. While many CVs have been proposed in the past, they are usually treated as isolated "hacks." This paper asks: Is there a systematic way to find all possible CVs? And if we have dozens of them, how do we combine them without the math becoming a mess?
A Systematic Recipe and Bayesian Combination
The paper’s contribution is two-fold:
- The Systematic Recipe: The authors show that the gradient of the Evidence Lower Bound (ELBO) can be split into four distinct terms (Data, Prior, Variational, and Score). A control variate is simply the difference between two different ways of estimating the same term (e.g., comparing a "Score Function" estimator to a "Reparameterization" estimator). By mixing and matching these estimators or using Taylor approximations, one can generate a huge "ensemble" of valid CVs.
- Bayesian Regularization for Combination: To use multiple CVs, you need to assign each one a weight. Mathematically, there is an "optimal" weight, but calculating it requires knowing the exact covariance of your gradients—which is exactly what we don't have.
- The Innovation: Instead of just using a raw average from a small minibatch (which is itself noisy), they use a Bayesian risk minimization framework.
- The Result: This leads to a surprisingly simple "regularized" combination rule. It looks like standard linear regression but with a diagonal term added to the matrix inversion to prevent the weights from overreacting to noise in small minibatches.
Key Insights: The "More is Better" Principle
One might worry that adding too many CVs would make the weight estimation too noisy. However, the paper demonstrates that using all available CVs consistently outperforms using any single "best" CV.
By using exponential moving averages to track the performance of CVs across iterations, the algorithm "learns" how to weight the ensemble over time, making the overhead of using many CVs very manageable.
Key Results: Stability and Speed
The authors evaluated their approach using Bayesian binary logistic regression on three well-known datasets: Ionosphere, Australian, and Sonar. While these are smaller, classical datasets, they serve as a controlled environment to demonstrate how gradient variance behaves across different learning rates.
- Convergence Speed: In all tested datasets, the ensemble of 7 different CVs achieved the highest ELBO (best fit) in the fewest iterations.
- Variance Reduction: The "regularized" Bayesian rule successfully prevented the weights from exploding, a common failure mode when trying to combine multiple variance-reduction techniques.
- Higher Learning Rates: This is the "aha" moment for practitioners. Because the ensemble of CVs slashes the gradient noise so effectively, you can use much larger learning rates.
As shown in the performance plots across datasets, the ensemble method is much more robust to the choice of learning rate. While the standard "Base Gradient" only works within a narrow, small window of learning rates, the ensemble method remains stable and performs well even as the learning rate increases by an order of magnitude.
Limitations and Future Work
- Model Complexity: The experiments were limited to logistic regression. While the theory is general, the computational overhead of calculating many CVs for massive deep learning models remains an open question.
- Fixed Ensembles: The paper assumes the set of CVs is chosen beforehand. The authors suggest that a "smarter" future algorithm could dynamically decide which CVs are worth the extra computation at each step of the optimization.
- Implementation Overhead: While the combination rule is simple, implementing five or six different gradient estimators for a complex model requires significant engineering effort compared to a standard "black-box" approach.
Final Thought: This paper moves Variational Inference away from "bespoke" variance reduction and toward a more automated, ensemble-based approach. If you're struggling with "exploding gradients" in probabilistic models, Geffner and Domke suggest that the solution isn't to find the perfect control variate, but to use all of them at once—with a little Bayesian caution.
Summary updated