High-dimensional Adaptive MCMC with Reduced Computational Complexity

Authors	Max Hird & Samuel Livingstone
Year	2026
Field	AI / ML
arXiv	2604.09286
PDF	Download
Categories	stat.CO, stat.ML

Abstract

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(m^2d)$ for a user-determined parameter $m$, compared with the $O(d^2)$ 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.

---

Engineering Breakdown

Plain English

This paper proposes a new adaptive MCMC (Markov Chain Monte Carlo) method that learns a linear preconditioner to speed up sampling from high-dimensional distributions. The key innovation is achieving O(m²d) per-iteration complexity instead of O(d²) for existing adaptive methods, where m is a user-controlled parameter that trades off precision for speed. The method works by inferring correlation structure in the target distribution using online PCA on the MCMC chain itself, then constructing a preconditioner that is dense but sparse in its parametrization. This allows it to handle highly correlated target distributions better than simple diagonal preconditioning (O(d)) while remaining computationally tractable in high dimensions.

Core Technical Contribution

The core technical novelty is a hybrid preconditioner design that captures correlations through a low-rank structure while maintaining computational efficiency through sparse parametrization. Instead of storing and inverting a full O(d²) dense matrix like traditional adaptive MCMC, the authors decompose their preconditioner into a diagonal matrix plus a rank-m correction term, reducing both memory and per-iteration compute. The eigeninformation is estimated adaptively during MCMC sampling using online principal components analysis, eliminating the need for expensive upfront covariance estimation. This enables a principled trade-off between adaptation quality (controlled by m) and computational cost, which did not exist in prior adaptive MCMC literature.

How It Works

The algorithm operates by running MCMC while simultaneously learning the structure of the target distribution. At each iteration, the method: (1) proposes a new sample using a preconditioned proposal that incorporates learned correlation information; (2) accepts or rejects based on standard Metropolis-Hastings criteria; (3) updates an online PCA estimate of the top m eigenvectors and eigenvalues of the target covariance. The preconditioner is constructed as P = D + L, where D is a diagonal matrix (capturing marginal variances) and L is a low-rank term built from the m dominant eigenvectors weighted by their eigenvalues. This decomposition means computing P⁻¹v only requires O(md) operations instead of O(d²): first apply the diagonal inverse in O(d), then apply the Sherman-Morrison formula for the rank-m correction in O(m²d) time. The online PCA component uses sketching or streaming techniques to avoid storing the full covariance matrix, keeping memory requirements manageable even in very high dimensions.

Production Impact

For practitioners building Bayesian inference pipelines, this method directly solves the problem of sampling from high-dimensional correlated posteriors without astronomical compute costs. In production systems doing Bayesian neural network inference or hierarchical modeling, reducing per-iteration complexity from O(d²) to O(m²d) with d in the thousands means wall-clock speedups of 10-100x depending on m. The online learning of correlations means you don't need to burn compute on upfront covariance estimation — the sampler learns structure as it runs, improving both the initial burn-in phase and steady-state sampling efficiency. Trade-offs include: choosing m (small m= faster but lower quality adaptation; large m=better adaptation but slower), the overhead of online PCA maintenance, and the requirement that your sampling problem actually has low-rank correlation structure. In practice, you'd likely use this for posterior inference in hierarchical Bayesian models, variational inference initialization, or as a building block in federated or distributed inference systems where communication bandwidth is constrained.

Limitations and When Not to Use This

The method assumes the target covariance has significant low-rank structure (approximately rank-m), which may not hold for distributions with broad, diffuse correlations or many moderately important directions. The paper's abstract doesn't specify convergence guarantees for the online PCA component during adaptive MCMC, leaving open whether the simultaneous adaptation and sampling process has well-characterized asymptotic properties — this is a critical gap for production use. Computational savings only accrue when d is large enough that O(m²d) beats O(d²), meaning for moderate-dimensional problems (d<1000) the overhead of online PCA may eliminate benefits entirely. The method requires storing m eigenvectors and maintaining online statistics, which adds implementation complexity and potential numerical instability if not carefully implemented; the paper appears incomplete (abstract cuts off mid-sentence), so full algorithmic details and failure mode analysis are unavailable from this submission.

Research Context

This work extends the adaptive MCMC literature pioneered by work like AdaM and preconditioned samplers, addressing a longstanding limitation: adaptation methods that capture correlation structure (like Hessian-based preconditioning) hit O(d²) walls in high dimensions. The approach builds on online PCA and sketching techniques from the streaming algorithms and dimensionality reduction literature. This connects to broader trends in scalable Bayesian inference — similar low-rank + diagonal decompositions appear in natural gradient variational inference and stochastic optimization. The research opens a direction toward 'anytime' adaptive MCMC where you can dial computational budget up or down via the m parameter, and likely influences future work on adaptive sampling in distributed settings where communication cost also matters.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →