Fisher information lower bounds for sampling
This provides theoretical limitations for sampling algorithms in machine learning and statistics, particularly for non-log-concave distributions, with implications for practitioners relying on such methods.
The paper proves two computational lower bounds for sampling from non-log-concave distributions using Fisher information as a metric, showing that averaged LMC is optimal for large Fisher information regimes and that achieving small Fisher information requires polynomially many queries, which rules out high-accuracy algorithms like Metropolis-Hastings in this context.
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.