High-dimensional Adaptive MCMC with Reduced Computational Complexity

We propose an adaptive MCMC method that learns a linear preconditioner which is dense in its off-diagonal elements but sparse in its parametrisation. Due to this sparsity, we achieve a per-iteration computational complexity of O(m2d) for a user-determined parameter m, compared with the O(d2) complexity of existing adaptive strategies that can capture correlation information from the target. Diagonal preconditioning has an O(d) per-iteration complexity, but is known to fail in the case that the target distribution is highly correlated, see citet[Section 3.5]hird2025a. Our preconditioner is constructed using eigeninformation from the target covariance which we infer using online principal components analysis on the MCMC chain. It is composed of a diagonal matrix and a product of carefully chosen reflection matrices. On various numerical tests we show that it outperforms diagonal preconditioning in terms of absolute performance, and that it outperforms traditional dense preconditioning and multiple diagonal plus low-rank alternatives in terms of time-normalised performance.