High-dimensional Adaptive MCMC with Reduced Computational Complexity

• URL: http://arxiv.org/abs/2604.09286v1
• Date: Fri, 10 Apr 2026 12:58:00 GMT
• Title: High-dimensional Adaptive MCMC with Reduced Computational Complexity
• Abstract summary: We propose an adaptive MCMC method that learns a linear preconditioner which is dense in its off-diagonal elements but sparse in its parametrisation.<n>We show that it outperforms diagonal preconditioning in terms of absolute performance.
• Score: 0.8594140167290097
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• On the Equivariant Learning of the $Q$-tensor Order Parameter [0.7734726150561086]
  We construct and evaluate group-equivariant neural networks for the prediction of the two-dimensional $Q$-tensor order parameter of nematic liquid crystals.<n>We find that the equivariant models consistently achieve lower errors and generalize more robustly to unseen defect configurations.
  arXiv  Detail & Related papers  (2026-05-26T20:54:38Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Covariance Matrix Adaptation Evolution Strategy without a matrix [0.0]
  We introduce a version of CMA-ES that uses no covariance matrix at all.<n>We prove that the probability distribution of individuals generated by the proposed method is identical to that of the standard CMA-ES.<n>The matrix-free CMA-ES converges faster than the matrix-based, and usually yields the results of a comparable or superior quality.
  arXiv  Detail & Related papers  (2025-12-31T20:35:58Z)
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models [68.31088463716269]
  We propose a structured sparse parametrization of transition matrices in state-space models (SSMs)<n>Our method, PD-SSM, parametrizes the transition matrix as the product of a column one-hot matrix ($P$) and a complex-valued diagonal matrix ($D$)<n>The model significantly outperforms a wide collection of modern SSM variants on various FSA state tracking tasks.
  arXiv  Detail & Related papers  (2025-09-26T12:46:30Z)
• Fast Linear Solvers via AI-Tuned Markov Chain Monte Carlo-based Matrix Inversion [8.596794810605124]
  We present an AI-driven framework recommending MCMC parameters for a given linear system.<n>A graph neural surrogate predicts preconditioning speed from $A$ and MCMC parameters.<n>On a previously unseen ill-conditioned system, the framework achieves better preconditioning with 50% of the search budget of conventional methods.
  arXiv  Detail & Related papers  (2025-09-22T22:14:13Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization [19.32160757444549]
  In practical instances of nonspecified matrix factorization, the rank of the true solutionrstar$ is often unknown, so the rankr$ of the model can be singular as $r>rstar$.<n>We propose an inexpensive suber for matrix sensing variant non matrix factorization that restores the convergence factor back to linear, even in agnosticized case.<n>Our numerical experiments find that PrecGD works equally well in restoring the convergence of other variants non matrix factorization.
  arXiv  Detail & Related papers  (2025-04-13T20:06:49Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Simplifying Momentum-based Positive-definite Submanifold Optimization with Applications to Deep Learning [24.97120654216651]
  We show how to solve difficult differential equations with momentum on a submanifold. We do so by proposing a generalized version of the Riemannian normal coordinates. We use our approach to simplify existing approaches for structured covariances and develop matrix-inverse-free $2textnd$orders for deep learning with low precision by using only matrix multiplications.
  arXiv  Detail & Related papers  (2023-02-20T03:31:11Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.