On sample complexity for covariance estimation via the unadjusted Langevin algorithm

Shogo Nakakita · 2026

Read On sample complexity for covariance estimation via the unadjusted Langevin algorithm by Shogo Nakakita (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21717.txt.

Introduction

Shogo Nakakita bounds the sample cost of estimating a covariance matrix with a popular sampling algorithm. The unadjusted Langevin algorithm draws samples by following a noisy downhill rule. For strongly log-concave, smooth distributions, its samples can estimate the covariance.

The author compares one long chain against many parallel chains. The single chain wins by a logarithmic factor in dimension and target precision. The gain comes from the burn-in phase cutting bias more effectively. Clear sample bounds help practitioners choose chain layouts with math, not folklore, when sampling feeds a covariance estimate.

Catalog record

CREATORShogo Nakakita
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21717

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On sample complexity for covariance estimation via the unadjusted Langevin algorithm Shogo Nakakita Abstract . We establish sample complexity guarantees for estimating the covariance matrix of strongly log-concave smooth distributions using the unadjusted Langevin algorithm (ULA). We quantitatively compare our complexity estimates on single-chain ULA with embarrassingly parallel ULA and derive that the sample complexity of the single-chain approach is smaller than that of embarrassingly parallel ULA by a logarithmic factor in the dimension and the reciprocal of the prescribed precision, with the difference arising from effective bias reduction through burn-in. The key technical contribution is a concentration bound for the sample covariance matrix around its expectation, derived via a log-Sobolev inequality for the joint distribution of ULA iterates. 1. Introduction Sampling from a Gibbs distribution \pi(\mathrm{d}x)\propto e^{-f(x)}\mathrm{d}x on \mathbb{R}^{d} is a fundamental problem in statistics, physics, and machine learning. Let f\in\mathcal{C}^{2}(\mathbb{R}^{d};\mathbb{R}) be an \alpha -convex and \beta -smooth potential function, i.e., \alpha I_{d}\preceq\nabla^{2}f(x)\preceq\beta I_{d} for all x\in\mathbb{R}^{d} . Markov Chain Monte Carlo (MCMC) is one of the successful strategies for this problem, and the unadjusted Langevin algorithm (ULA) is a popular MCMC method due to its simplicity and efficiency. Let us introduce the definition of ULA (with fixed step size). Given (i) an initial value X_{0} (a d -dimensional random vector, possibly X_{0}\sim\delta_{x} for some x\in\mathbb{R}^{d} ), (ii) step size \eta>0 , (iii) the number of burn-in steps m\geq 0 , and (iv) sample size n\geq 1 , the algorithm is defined for all i=1,\ldots,m+n as (1) X_{i}=X_{i-1}-\eta\nabla f(X_{i-1})+\sqrt{2\eta}Z_{i}, where \{Z_{i}\}_{i\in\mathbb{N}}\sim^{\textnormal{i.i.d.}}\mathcal{N}_{d}(0,I_{d}) independent of X_{0} . While its invariant distribution \pi_{\eta} (which exists for sufficiently small \eta ) differs from the target distribution \pi , it is known that \pi_{\eta} converges to \pi in some metrics or divergences as \eta\to 0 . ULA is derived by the Euler–Maruyama discretization of the Langevin dynamics (also known as the overdamped Langevin diffusion) defined as the solution of the following stochastic differential equation: \mathrm{d}Y_{t}=-\nabla f(Y_{t})\mathrm{d}t+\sqrt{2}\mathrm{d}B_{t},\ Y_{0}=X_{0}, where B_{t} is the standard d -dimensional Brownian motion. We can interpret that ULA approximates the continuous-time process Y_{t} at discrete time points t=i\eta for i=0,\ldots,m+n . The Langevin dynamics has \pi as its invariant distribution and has an explicit rate of convergence to \pi if \pi satisfies functional inequalities such as Poincaré inequalities and log-Sobolev inequalities ( Bakry et al., 2014 ) . Owing to this property, ULA is expected to approximate \pi well if \eta\ll 1 and m\eta\gg 1 . In fact, the community has unveiled the behaviour of the distribution of X_{n} for each n ( Dalalyan, 2017 ; Durmus and Moulines, 2017 ; Durmus and Moulines, 2019 ; Vempala and Wibisono, 2019 , e.g.,) and found favourable non-asymptotic convergence guarantees to the target distribution \pi in various metrics such as the 2-Wasserstein distance and Kullback–Leibler divergence in this decade. 1.1. Problem setting Our main interest lies in the sample complexity analysis for moment estimation via ULA. In statistical inference, we are often interested in moments of target distributions, such as means and covariance matrices, and the sample complexities required for their estimation. We expect that the sample mean \bar{X}_{n} and sample covariance matrix \hat{\Sigma}_{n} defined as (2) \bar{X}_{n}=\frac{1}{n}\sum_{i=m+1}^{m+n}X_{i},\quad\hat{\Sigma}_{n}=\frac{1}{n}\sum_{i=m+1}^{m+n}X_{i}X_{i}^{\top}-\bar{X}_{n}\bar{X}_{n}^{\top} of ULA should approximate the population mean \mathbb{E}_{\pi}[X]=\int x\pi(\mathrm{d}x) and population covariance \textnormal{Cov}(\pi)=\int xx^{\top}\pi(\mathrm{d}x)-\mathbb{E}_{\pi}[X]\mathbb{E}_{\pi}[X]^{\top} when \eta\ll 1 and n\eta\gg 1 . While this idea is asymptotically guaranteed by standard ergodic theorems under fixed d , it is not obvious when d is large. Specifically, it is unclear how large n should be to achieve a certain accuracy in high-dimensional settings due to the dependence among the ULA outputs and the resulting large variance. One may consider the embarrassingly parallel ULA to address dependence, which is the main comparison target of this paper. In this study, we refer to the embarrassingly parallel ULA as the procedure that collects the last iterates of N independent paths of ULA \{X_{m+1}^{k}\}_{k=1}^{N} defined as follows: for all k=1,\ldots,N and i=1,\ldots,m+1 (with m burn-in steps discarded in estimation), with d -dimensional random vectors X_{0}^{k} , (3) X_{i}^{k}=X_{i-1}^{k}-\eta\nabla f(X_{i-1}^{k})+\sqrt{2\eta}Z_{i}^{k}, where \{Z_{i}\}_{i,k}\sim^{\textnormal{i.i.d.}}\mathcal{N}_{d}(0,I_{d}) . While it requires burn-in for every path to remove bias , the variance of its sample moments is smaller than that of single-chain ULA with N=n . If the sample complexities of both methods coincide up to constant factors, embarrassingly parallel ULA is preferable in practice due to its wall-clock speedup via parallelization. Hence, one should raise the following question: Q . Does the bias removal of single-chain ULA by burn-in outweigh its large variance from dependence in comparison to embarrassingly parallel ULA in terms of sample complexity? If so, how large is the difference? To answer this question, we study sample complexity guarantees for covariance estimation of strongly log-concave smooth distributions via single-chain ULA and embarrassingly parallel ULA respectively. In particular, this study establishes a concentration bound for the sample covariance matrix of single-chain ULA, which is our main theoretical contribution. Some studies have investigated non-asymptotic guarantees for moment estimation via MCMC ( Durmus and Moulines, 2019 ; Kook and Zhang, 2024 ; Shen et al., 2025 ) , but this topic remains largely unexplored in the literature. Recently, Kook and Zhang, 2024 studied covariance matrix estimation with high-accuracy MCMC (that is, MCMC whose invariant distribution is exactly the target distribution; for example, random-walk Metropolis and Metropolis-adjusted Langevin algorithm) for \pi satisfying a Poincaré inequality. However, their comparison focuses on query complexities rather than sample complexities for covariance estimation. In contrast, this work examines sample complexity through a concentration analysis of the sample covariance matrix and establishes explicit bounds for both single-chain and parallel ULA approaches. We address the problem via a bias–variance decomposition and analysing the variance part; specifically, we show concentration bounds on sample moments of ULA around its expectation rather than the moments of \pi_{\eta} or \pi . By the triangular inequality with operator norm \|\cdot\| , we have (4) \left\|\hat{\Sigma}_{n}-\textnormal{Cov}(\pi)\right\|\leq\underbrace{\left\|\textnormal{Cov}(\pi_{\eta})-\textnormal{Cov}(\pi)\right\|}_{\text{bias by discretization}}+\underbrace{\left\|\mathbb{E}\left[\hat{\Sigma}_{n}\right]-\textnormal{Cov}(\pi_{\eta})\right\|}_{\text{bias by non-stationarity}}+\underbrace{\left\|\hat{\Sigma}_{n}-\mathbb{E}\left[\hat{\Sigma}_{n}\right]\right\|}_{\text{variance by sampling}}, where \textnormal{Cov}(\pi_{\eta}):=\int_{\mathbb{R}^{d}}xx^{\top}\pi_{\eta}(\mathrm{d}x)-\int_{\mathbb{R}^{d}}x\pi_{\eta}(\mathrm{d}x)(\int_{\mathbb{R}^{d}}x\pi_{\eta}(\mathrm{d}x))^{\top} . Since previous studies ( Durmus and Moulines, 2019 , e.g.,) show bounds on the 2-Wasserstein distances for the pair of \pi_{\eta} and \pi and that of the distribution of X_{i} and \pi_{\eta} , our focus is on evaluating the variance term. 1.2. Main contributions Our contributions can be summarized as follows. • Concentration for sample covariance matrices under dependence. Using the log-Sobolev inequality, we derive a concentration bound on the sample covariance matrix around its expectation in operator norm, whose rate of convergence is (1/\alpha)\sqrt{d/(\alpha\eta n)} (Theorem 1 ). This rate is reasonable since 1/\alpha is the largest eigenvalue of the covariance matrix under Gaussian settings, and \alpha\eta n can be regarded as the terminal time of the Langevin dynamics which ULA approximates and should serve as the effective sample size in an ordinary sense. • Sample complexity for covariance estimation. Combining the above variance bounds with existing non-asymptotic bias bounds for ULA, we obtain explicit sample complexity guarantees for estimating the covariance matrix of the target distribution \pi via a bias–variance decomposition. Under standard settings, the total sample complexity is shown to be of order \mathcal{O}(\beta^{2}d^{2}(d+\log(1/\delta))\alpha^{-6}\varepsilon^{-4}) to achieve \varepsilon -accuracy in operator norm with probability at least 1-\delta (Proposition 2 ). Notably, the estimation error does not deteriorate for large n beyond the required sample

Read the complete text