Graph Reparameterizations for Enabling 1000+ Monte Carlo Iterations in Bayesian Deep Neural Networks

Jurijs Nazarovs, Ronak R. Mehta, Vishnu Suresh Lokhande, Vikas Singh

Bayesian Deep Learning (BDL) provides a principled framework for uncertainty quantification, yet its practical application is often hindered by the computational burden of Monte Carlo (MC) sampling. This paper, presented at UAI 2021, introduces a graph reparameterization framework that decouples the size of the computation graph from the number of MC iterations. By enabling 1000+ iterations on standard hardware, the method achieves significant speedups and more stable uncertainty estimates.

The Monte Carlo Bottleneck in Deep Learning

In Bayesian Deep Learning, models learn a distribution over weights rather than point estimates. Training typically involves Variational Inference (VI) to minimize the KL divergence between an approximate posterior and a prior. For complex distributions, this objective is estimated via Monte Carlo (MC) sampling.

However, standard deep learning frameworks like PyTorch or TensorFlow implement MC sampling by replicating the computation graph for each sample. This linear scaling ($O(M)$) quickly exhausts GPU memory, forcing a compromise: researchers often use as few as 1 to 10 samples. Such low sample counts introduce high variance into gradients, leading to unstable training and unreliable uncertainty estimates.

Methodology: Graph Reparameterization

The authors propose a theoretical framework to make the computation graph size independent of the number of samples $M$. This is achieved by identifying "parameterization tuples" that allow functions of random variables to be decomposed into a form where the learnable parameters $\theta$ only appear once.

For specific probability families—notably Scaling families (e.g., Exponential, Gamma) and Location-Scale families (e.g., Normal, Laplace)—the summation over $M$ samples can be moved "inside" the graph.

Comparison of standard AutoGrad implementation (a) vs. the proposed graph-independent implementation (b).

As illustrated in the figure above, the standard implementation requires nodes for every individual sample $\xi_i$, whereas the proposed method collapses these into summary statistics, maintaining a constant graph size regardless of $M$. For functions that do not naturally fit this form, the authors utilize Taylor expansions to create polynomial approximations that satisfy these graph-independence requirements.

Key Results and Performance

The method was evaluated on CIFAR-10 and the ADNI medical imaging dataset using architectures including ResNet, DenseNet, and VGG.

Efficiency and Scalability

The primary benefit of graph reparameterization is the massive reduction in compute time and memory usage. The authors report up to a 14x reduction in compute time for complex networks. For models like DenseNet-121, the method used less than 25% of the GPU memory required by standard MC sampling for the same number of iterations.

Batch time comparison between standard General AutoGrad (GA) and the proposed method across various architectures.

The figure above demonstrates that the proposed method consistently outperforms standard AutoGrad (GA) across all tested architectures. Furthermore, while standard methods were capped at fewer than 100 iterations (and as low as 5 for VGG-16) due to memory limits, the proposed framework successfully ran 1,000+ MC iterations on a single GPU.

Improved Uncertainty Quantification

On the ADNI brain imaging task, the ability to use 100 iterations instead of 1 significantly improved "confident accuracy." Validation accuracy for high-confidence predictions rose from ~60% to 87.5%, while also significantly reducing the variance of the estimates. This suggests that high-sample MC estimates are crucial for reliable decision-making in sensitive domains like healthcare.

Conclusion

By rethinking the construction of computation graphs, this work removes a significant barrier to scaling Bayesian Neural Networks. While the current framework primarily addresses the KL divergence term, it provides a scalable path forward for high-fidelity Bayesian inference in large-scale deep learning. The authors provide a simple API to allow users to swap standard layers for these optimized Bayesian layers with minimal code changes.

Summary updated

Abstract

Uncertainty estimation in deep models is essential in many real-world applications and has benefited from developments over the last several years. Recent evidence suggests that existing solutions dependent on simple Gaussian formulations may not be sufficient. However, moving to other distributions necessitates Monte Carlo (MC) sampling to estimate quantities such as the KL divergence: it could be expensive and scales poorly as the dimensions of both the input data and the model grow. This is directly related to the structure of the computation graph, which can grow linearly as a function of the number of MC samples needed. Here, we construct a framework to describe these computation graphs, and identify probability families where the graph size can be independent or only weakly dependent on the number of MC samples. These families correspond directly to large classes of distributions. Empirically, we can run a much larger number of iterations for MC approximations for larger architectures used in computer vision with gains in performance measured in confident accuracy, stability of training, memory and training time.
BibTeX
@inproceedings{nazarovs2021graph,
  author = {Jurijs Nazarovs and Ronak R. Mehta and Vishnu Suresh Lokhande and Vikas Singh},
  title = {{Graph Reparameterizations for Enabling 1000+ Monte Carlo Iterations in Bayesian Deep Neural Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=jd9Tnm-9MRr},
}
Figure