2025/02/10 by Yuchen He, He, Yuchen, Chihao Zhang +1 · 3 citations
Computer Science · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2502.06200
openalex publication_date 2025/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of sampling from a d-dimensional distribution with density p(x)∝ e-f(x), which does not necessarily satisfy good isoperimetric conditions. Specifically, we show that for any L,M satisfying LM≥ d≥ 5, ε∈ (0,(1)/(32)), and any algorithm with query accesses to the value of f(x) and ∇ f(x), there exists an L-log-smooth distribution with second moment at most M such that the algorithm requires ((LM)/(dε))Ω(d) queries to compute a sample whose distribution is within ε in total variation distance to the target distribution. We complement the lower bound with an algorithm requiring ((LM)/(dε))O(d) queries, thereby characterizing the tight (up to the constant in the exponent) query complexity for sampling from the family of non-log-concave distributions. Our results are in sharp contrast with the recent work of Huang et al. (COLT'24), where an algorithm with quasi-polynomial query complexity was proposed for sampling from a non-log-concave distribution when M=\mathttpoly(d). Their algorithm works under the stronger condition that all distributions along the trajectory of the Ornstein-Uhlenbeck process, starting from the target distribution, are O(1)-log-smooth. We investigate this condition and prove that it is strictly stronger than requiring the target distribution to be \mathcal O(1)-log-smooth. Additionally, we study this condition in the context of mixtures of Gaussians. Finally, we place our results within the broader theme of ``sampling versus optimization'', as studied in Ma et al. (PNAS'19). We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension d.