# Covariance estimation using Markov chain Monte Carlo

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms](https://mlsanity.com/paper/2008.02146/) (2020)

## Built on by (most cited first, 2 of 2)

- [A Non-asymptotic Analysis for Learning and Applying a Preconditioner in MCMC](https://mlsanity.com/paper/2602.10714/) (2026)
- [On sample complexity for covariance estimation via the unadjusted Langevin algorithm](https://mlsanity.com/paper/2601.21717/) (2026)

## Abstract (arXiv)

We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when π satisfies a Poincar'e inequality and the chain possesses a spectral gap, we can achieve similar sample complexity using MCMC as compared to an estimator constructed using i.i.d. samples, with potentially much better query complexity. As an application of our methods, we show improvements for the query complexity in both constrained and unconstrained settings for concrete instances of MCMC. In particular, we provide guarantees regarding isotropic rounding procedures for sampling uniformly on convex bodies.