  Variational Bayes (VB) is a critical method in machine learning and
statistics, underpinning the recent success of Bayesian deep learning. The
natural gradient is an essential component of efficient VB estimation, but it
is prohibitively computationally expensive in high dimensions. We propose a
computationally efficient regression-based method for natural gradient
estimation, with convergence guarantees under standard assumptions. The method
enables the use of quantum matrix inversion to further speed up VB. We
demonstrate that the problem setup fulfills the conditions required for quantum
matrix inversion to deliver computational efficiency. The method works with a
broad range of statistical models and does not require special-purpose or
simplified variational distributions.
