# High-dimensional Adaptive MCMC with Reduced Computational Complexity

arXiv: https://arxiv.org/abs/2604.09286 · HTML: https://mlsanity.com/paper/2604.09286/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 10 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [The Barker proposal: combining robustness and efficiency in gradient-based MCMC](https://mlsanity.com/paper/1908.11812/) (2019)
- [Optimal Preconditioning and Fisher Adaptive Langevin Sampling](https://mlsanity.com/paper/2305.14442/) (2023)
- [Online Principal Component Analysis in High Dimension: Which Algorithm to Choose?](https://mlsanity.com/paper/1511.03688/) (2015)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Batch, match, and patch: low-rank approximations for score-based variational inference](https://mlsanity.com/paper/2410.22292/) (2024)
- [Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1803.02312/) (2018)
- [Tuning diagonal scale matrices for HMC](https://mlsanity.com/paper/2403.07495/) (2024)

## Abstract (arXiv)

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.