The Adaptive Complexity of Minimizing Relative Fisher Information

Non-log-concave sampling from an unnormalized density is fundamental in machine learning and statistics. As datasets grow larger, computational efficiency becomes increasingly important, particularly in reducing adaptive complexity, namely the number of sequential rounds required for sampling algorithms. In this work, we initiate the study of the adaptive complexity of non-log-concave sampling within the framework of relative Fisher information introduced by Balasubramanian et al. in 2022. To obtain a relative Fisher information of at most ε 2 from the target distribution, we propose a novel algorithm that reduces the adaptive complexity from O(d 2 /ε 4 ) to O(d/ε 2 ) by leveraging parallelism. Furthermore, we show our algorithm is optimal for a specific regime of large ε. Our algorithm builds on a diagonally parallelized Picard iteration, while the lower bound is based on a reduction from the problem of finding stationary points.

1 Samplers with complexity poly(d, log(K0/ε)), assuming constant smoothness and condition number and K0 as initial KL divergence.