2025/12/14 by Martin Chak, Giacomo Zanella, Chak, Martin +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2512.12748
openalex publication_date 2025/12/14 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
Markov Chain Monte Carlo (MCMC), Laplace approximation (LA) and variational inference (VI) methods are popular approaches to Bayesian inference, each with trade-offs between computational cost and accuracy. However, a theoretical understanding of these differences is missing, particularly when both the sample size n and the dimension d are large. LA and Gaussian VI are justified by Bernstein-von Mises (BvM) theorems, and recent work has derived the characteristic condition n≫ d2 for their validity, improving over the condition n≫ d3. In this paper, we show for linear, logistic and Poisson regression that for n\gtrsim d, MCMC attains the same complexity scaling in n, d as first-order optimization algorithms, up to sub-polynomial factors. Thus MCMC is competitive with LA and Gaussian VI in complexity, under a scaling between n and d more general than BvM regimes. Our complexities apply to appropriately scaled priors that are not necessarily Gaussian-tailed, including Student-t and flat priors, with log-posteriors that are not necessarily globally concave or gradient-Lipschitz.