Fisher information lower bounds for sampling

Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:375-410, 2023.

Abstract

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 Langevin Monte Carlo (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 ε2 from the target distribution requires poly(1/ε) queries, which is surprising as it rules out the existence of high-accuracy algorithms (e.g., algorithms using Metropolis{–}Hastings filters) in this context.

Cite this Paper


BibTeX
@InProceedings{pmlr-v201-chewi23b, title = {Fisher information lower bounds for sampling}, author = {Chewi, Sinho and Gerber, Patrik and Lee, Holden and Lu, Chen}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {375--410}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/chewi23b/chewi23b.pdf}, url = {https://proceedings.mlr.press/v201/chewi23b.html}, abstract = { 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 ($\mathsf{FI}$) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged Langevin Monte Carlo (LMC) is optimal for the regime of large $\mathsf{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 $\mathsf{FI}$, obtaining a $\mathsf{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.} }
Endnote
%0 Conference Paper %T Fisher information lower bounds for sampling %A Sinho Chewi %A Patrik Gerber %A Holden Lee %A Chen Lu %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-chewi23b %I PMLR %P 375--410 %U https://proceedings.mlr.press/v201/chewi23b.html %V 201 %X 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 ($\mathsf{FI}$) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged Langevin Monte Carlo (LMC) is optimal for the regime of large $\mathsf{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 $\mathsf{FI}$, obtaining a $\mathsf{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.
APA
Chewi, S., Gerber, P., Lee, H. & Lu, C.. (2023). Fisher information lower bounds for sampling. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:375-410 Available from https://proceedings.mlr.press/v201/chewi23b.html.

Related Material