Covariance estimation using Markov chain Monte Carlo

Yunbum Kook, Matthew Shunshi Zhang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:60236-60259, 2026.

Abstract

We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when $$\pi$$ satisfies a Poincaré 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-kook26a, title = {Covariance estimation using {M}arkov chain {M}onte {C}arlo}, author = {Kook, Yunbum and Zhang, Matthew Shunshi}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {60236--60259}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/kook26a/kook26a.pdf}, url = {https://proceedings.mlr.press/v306/kook26a.html}, abstract = {We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when $$\pi$$ satisfies a Poincaré 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.} }
Endnote
%0 Conference Paper %T Covariance estimation using Markov chain Monte Carlo %A Yunbum Kook %A Matthew Shunshi Zhang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-kook26a %I PMLR %P 60236--60259 %U https://proceedings.mlr.press/v306/kook26a.html %V 306 %X We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when $$\pi$$ satisfies a Poincaré 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.
APA
Kook, Y. & Zhang, M.S.. (2026). Covariance estimation using Markov chain Monte Carlo. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:60236-60259 Available from https://proceedings.mlr.press/v306/kook26a.html.

Related Material