2024/10/22 by Yunbum Kook, Kook, Yunbum, Matthew S. Zhang +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Statistics Theory (math.ST) #Target Tracking and Data Fusion in Sensor Networks
paper · pdf · doi:10.48550/arxiv.2410.17147
openalex publication_date 2024/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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é 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.