A1451
Title: Sample complexity for covariance estimation via the unadjusted Langevin algorithm
Authors: Shogo Nakakita - The University of Osaka (Japan) [presenting]
Abstract: Estimating the covariance matrix of a Gibbs distribution with an unknown normalizing constant is a ubiquitous problem in statistics and machine learning. In particular, the high dimensionality of target distributions is frequently encountered, making the sample complexity and query complexity required to achieve a prescribed error tolerance with high probability an important concern of the community. The unadjusted Langevin algorithm (ULA) is studied, for which the sample complexity matches the query complexity, and its sample efficiency is analyzed. Furthermore, two settings are compared: (i) running a single long trajectory and estimating the covariance from the resulting dependent sequence, and (ii) implementing an embarrassingly parallel strategy that generates independent outputs and estimates the covariance from independent samples. It is shown that the sample complexity of the single-path approach is better than that of the parallel approach by a logarithmic factor.
