VBALD - Variational Bayesian Approximation of Log Determinants
This addresses a bottleneck in various ML applications such as Gaussian processes and kernel learning, offering a more efficient solution, though it appears incremental as it builds on existing approximation methods.
The paper tackles the high computational cost of evaluating log determinants of positive definite matrices in machine learning by proposing a variational Bayesian approximation method with O(n^2) complexity, achieving state-of-the-art performance on synthetic and real-world datasets compared to existing approaches like Taylor, Chebyshev, and Lanczos.
Evaluating the log determinant of a positive definite matrix is ubiquitous in machine learning. Applications thereof range from Gaussian processes, minimum-volume ellipsoids, metric learning, kernel learning, Bayesian neural networks, Determinental Point Processes, Markov random fields to partition functions of discrete graphical models. In order to avoid the canonical, yet prohibitive, Cholesky $\mathcal{O}(n^{3})$ computational cost, we propose a novel approach, with complexity $\mathcal{O}(n^{2})$, based on a constrained variational Bayes algorithm. We compare our method to Taylor, Chebyshev and Lanczos approaches and show state of the art performance on both synthetic and real-world datasets.