Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era

Nicolas Durrande, Vincent Adam, Lucas Bordeaux, Stefanos Eleftheriadis, James Hensman

Abstract

Gaussian Markov models provide a computationally efficient alternative to standard Gaussian processes by utilizing sparse precision matrices. However, modern automatic differentiation frameworks lack the specialized operators needed to exploit this sparsity during gradient-based training. This paper introduces a suite of custom banded matrix operators for TensorFlow, enabling linear-time inference—including Variational Inference (VI) and Hamiltonian Monte Carlo (HMC)—for a wide range of probabilistic models such as state-space models and Gaussian Markov random fields.

Introduction

Gaussian Processes (GPs) are a cornerstone of Bayesian machine learning, prized for their ability to provide well-calibrated uncertainty estimates. However, they are notoriously difficult to scale, with computational costs growing cubically $\mathcal{O}(N^3)$ and memory requirements growing quadratically $\mathcal{O}(N^2)$ with the number of data points $N$.

Gaussian Markov models, which include State Space Models (SSMs) and Gaussian Markov Random Fields (GMRFs), offer a solution by representing the precision matrix (the inverse of the covariance matrix) as a sparse, "banded" matrix. In these models, inference can theoretically be performed in linear time $\mathcal{O}(N)$. Despite this advantage, modern machine learning practitioners often struggle to use these models because popular automatic differentiation (autodiff) frameworks like TensorFlow and PyTorch lack native, differentiable linear algebra operators for banded matrices. This forces researchers to either use inefficient dense representations or forgo modern gradient-based inference techniques.

Methods: Bridging the Autodiff Gap

The authors address this limitation by implementing a suite of low-level banded matrix operators as custom TensorFlow operations. Written in C++ with corresponding Python/C++ gradient definitions, the core toolkit includes:

  • Banded Cholesky decomposition
  • Banded triangular solve
  • Banded matrix multiplications
  • Sparse inverse subset: An implementation of Takahashi's algorithm to efficiently compute only the necessary diagonal and band elements of an inverse matrix.

Crucially, the authors derived and implemented the reverse-mode derivatives for all these operators. They demonstrate that the gradients of banded operations remain banded, meaning both the forward and backward passes maintain $\mathcal{O}(Nl^2)$ time complexity (where $l$ is the bandwidth). This ensures that the entire training pipeline remains efficient and never requires the instantiation of dense matrices.

Experimental Evaluation

The effectiveness of these operators was tested on two distinct datasets:

  1. Mauna Loa CO2 Dataset: This dataset contains over 3,000 observations of atmospheric CO2. The authors used it to benchmark a 1D GP regression model with a quasi-periodic kernel converted to a state-space representation.
  2. Porto Taxi Dataset: This dataset consists of GPS locations for taxi pick-ups mapped to a road network with over 11,000 nodes. It was used to test a GMRF with a non-conjugate Poisson likelihood to predict taxi demand across a city grid.

Key Results and Insights

Massive Speedups and Linear Scaling

The empirical results confirm the theoretical advantages of the banded operators. On the Mauna Loa dataset, the custom operators achieved a three-order-of-magnitude speedup compared to standard dense GP implementations in GPflow. As shown in the benchmarking results, the execution time scales strictly linearly with the number of data points, whereas traditional methods quickly become intractable.

Linear scaling of banded operators vs. cubic scaling of standard GPs.

Memory Efficiency and Real-world Viability

For the Porto taxi dataset, storing only the band of the precision matrix reduced the storage footprint by nearly two orders of magnitude. More importantly, the authors successfully trained this complex, non-conjugate spatial model using both VI and HMC. This demonstrates that the operators work seamlessly in end-to-end autodiff pipelines, allowing for the application of sophisticated inference methods to large-scale spatial problems.

Spatial demand prediction on the Porto Taxi dataset using GMRFs.

The Importance of Takahashi's Algorithm

A significant technical insight is the role of Takahashi's algorithm in enabling Variational Inference. VI requires computing the trace of the product of two matrices for the KL divergence term. For banded precision matrices, one only needs the elements of the inverse matrix that fall within the band. Takahashi's algorithm computes exactly this subset efficiently, making VI viable for these models for the first time in a standard autodiff framework.

Conclusion

By providing a differentiable toolkit for banded matrices, this work removes a major barrier to using Gaussian Markov models in modern machine learning. The authors have shown that with a small set of specialized operators, it is possible to unlock linear-time inference for a massive family of models. They hope this work will encourage major autodiff frameworks to adopt native support for sparse linear algebra, renewing the popularity of these efficient probabilistic models in the deep learning era.

Summary updated

Abstract

Banded matrices can be used as precision matrices in several models including linear state-space models, some Gaussian processes, and Gaussian Markov random fields. The aim of the paper is to make ...
BibTeX
@inproceedings{durrande2019banded,
  author = {Nicolas Durrande and Vincent Adam and Lucas Bordeaux and Stefanos Eleftheriadis and James Hensman},
  title = {{Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=BfQgfzMQ0bW},
}
Figure