In Bayesian machine learning, we rarely want just a single "best" answer. Instead, we seek a probability distribution over possible answers. For a neural network with $D$ parameters, this means maintaining a $D \times D$ covariance matrix to track how those parameters relate to one another.
The problem is scale. A modern neural network might have millions of parameters. A full covariance matrix would require trillions of entries—far exceeding the memory of any GPU—and inverting it would take ages. To survive, researchers have traditionally retreated to the Mean-Field Approximation, where we assume every parameter is independent. This makes the covariance matrix diagonal, reducing the cost to $O(D)$, but it throws away the very correlations that make deep learning work.
A growing body of research, spanning from variational inference to Kalman filtering, has converged on a powerful middle ground: the Diagonal Plus Low-Rank (D+LR) structure. By modeling uncertainty as a simple diagonal matrix plus a small number of "rank" components, we can capture the most important correlations without the quadratic cost.
The Intuition: Capturing the "Spikes" of Correlation
The D+LR approach assumes that while there are millions of potential interactions between parameters, only a few "directions" in the parameter space actually matter for uncertainty. Mathematically, we represent the covariance $\Sigma$ as:
$$\Sigma = \text{diag}(d) + VV^\top$$
where $d$ is a vector of length $D$ (the diagonal) and $V$ is a tall, skinny matrix of size $D \times K$. Here, $K$ is the "rank"—usually a small number like 10 or 20.
As Andrew Miller and Ryan P Adams describe in Variational Boosting, this structure allows us to trade extra computation for accuracy. The diagonal part handles the "independent noise" of each parameter, while the $VV^\top$ part captures the "spiked" correlations—the primary ways the parameters move together.
Why It Works: The Sherman-Morrison-Woodbury Identity
The "magic" that makes D+LR computationally feasible is a classic result in linear algebra: the Sherman-Morrison-Woodbury identity. This identity allows us to invert a D+LR matrix by only inverting a much smaller $K \times K$ matrix.
In Distributed Activity Detection, Jingreng Lei and colleagues use this trick to bypass high-dimensional matrix inversions entirely. Similarly, Aaron Mishkin and Mark Schmidt leverage this in SLANG to perform Natural Gradient Descent. Because Natural Gradient requires the inverse of the Fisher Information Matrix, the D+LR structure turns a $O(D^3)$ nightmare into a $O(DK^2)$ routine, making it nearly as fast as standard gradient descent.
From Optimization to Online Learning
The D+LR structure isn't just for static models; it's a cornerstone of efficient online learning. When data arrives in a stream, we need to update our beliefs instantly.
The LO-FI (Low-rank Extended Kalman Filter) algorithm, developed by Gerardo Duran-Martin and Kevin Patrick Murphy in Low-rank extended Kalman filtering, uses a D+LR precision matrix to track parameter uncertainty. This allows a neural network to adapt to distribution shifts in a single pass, capturing essential correlations that help it learn faster than methods that ignore parameter dependencies.
A similar logic applies to SWAG (SWA-Gaussian). In A Simple Baseline for Bayesian Uncertainty in Deep Learning, Wesley J. Maddox and Pavel Izmailov show that you can build a D+LR covariance simply by looking at the trajectory of Stochastic Gradient Descent. The "low-rank" part is formed by the differences between recent weight iterates, effectively capturing the geometry of the loss landscape "for free."
Balancing Expressivity and Cost
While D+LR is powerful, it involves a fundamental trade-off. In Statistical and Computational Trade-offs in Variational Inference, Kush Bhatia and Yixin Wang prove that while more complex models (higher $K$) eventually reach higher accuracy, they converge more slowly and can even be less accurate on small datasets due to the noise in estimating more parameters.
Researchers have found clever ways to navigate this:
- Layer-wise Rank: In Martingale Posterior Neural Networks, Gerardo Duran-Martin and Alvaro Cartea use high-rank approximations for the final decision layer (where uncertainty matters most) and low-rank approximations for hidden layers to save memory.
- Spatial Priors: For image tasks, Ben Glocker uses Stochastic Segmentation Networks to model spatial correlations. Here, the low-rank components act as "basis maps" that represent global structural variations in an image.
- Precision vs. Covariance: In Scalable GAM using sparse variational Gaussian processes, Vincent Adam and colleagues argue that for additive models, it is more efficient to parameterize the precision matrix (the inverse of covariance) as a low-rank update to the prior, capturing how multiple functions explain the same data.
The Future of "Honest" Models
The shift toward D+LR structures represents a move away from the "quick fixes" of the past. As Vasileios Baltatzis argues in Is MC Dropout Bayesian?, popular methods like Dropout often fail basic sanity checks. By contrast, D+LR provides a principled, structured way to handle high-dimensional uncertainty. Whether in 3D point cloud perception or scientific computing solvers, this "diagonal plus a little more" approach is proving to be the essential ingredient for making Bayesian deep learning practical.