Fisher information lower bounds for sampling

Autor:	Chewi, Sinho, Gerber, Patrik, Lee, Holden, Lu, Chen
Rok vydání:	2022
Předmět:	Statistics - Machine Learning Computer Science - Machine Learning Mathematics - Statistics Theory
Druh dokumentu:	Working Paper
Popis:	We prove two lower bounds for the complexity of non-log-concave sampling within the framework of Balasubramanian et al. (2022), who introduced the use of Fisher information (FI) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged LMC is optimal for the regime of large FI by reducing the problem of finding stationary points in non-convex optimization to sampling. Our second lower bound shows that in the regime of small FI, obtaining a FI of at most $\varepsilon^2$ from the target distribution requires $\text{poly}(1/\varepsilon)$ queries, which is surprising as it rules out the existence of high-accuracy algorithms (e.g., algorithms using Metropolis-Hastings filters) in this context. Comment: 35 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2210.02482 Zobrazit plný text záznamu View this record from Arxiv