  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.
