mlsanityData to 14 Oct 2026

Complexity of Non-Log-Concave Sampling in Fisher Information

arXiv 2605.15859 ↗First posted 15 May 2026cs.DS cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding an approximate stationary point in optimization. Our algorithm is based on the proximal sampler, which is an implicit discretization of the Langevin diffusion, and requires an implementation of the backward step known as the restricted Gaussian oracle (RGO). We show that by leveraging the recent results for log-concave sampling with high-accuracy guarantees in R'enyi divergence, we can obtain an approximate RGO implementation that -- when used with the proximal sampler -- yields a complexity guarantee in relative Fisher information that inherits the same dimension dependence as log-concave sampling, and improves upon prior work for non-log-concave sampling. We also show a converse reduction that any improvement in the dimension dependence in relative Fisher information for non-log-concave sampling will yield an improved dimension dependence for high-accuracy log-concave sampling.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 22 of its 26 references that are in the map. First posted on arXiv 15 May 2026.

Builds on

22 of 26 references.

References · 22

  1. 2017Stein Variational Gradient Descent as Gradient Flowcited by 152
  2. 2017Lower Bounds for Finding Stationary Points Icited by 126
  3. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 86
  4. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  5. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  6. 2024Optimal score estimation via empirical Bayes smoothingcited by 61
  7. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  8. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 45
  9. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  10. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 30
  11. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  12. 2022Regularized Stein Variational Gradient Flowcited by 19
10 more
  1. 2022Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Conditioncited by 16
  2. 2026High-accuracy sampling for diffusion models and log-concave distributionscited by 16
  3. 2024Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descentcited by 14
  4. 2022Fisher information lower bounds for samplingcited by 12
  5. 2023Query lower bounds for log-concave samplingcited by 12
  6. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 12
  7. 2022On the complexity of finding stationary points of smooth functions in one dimensioncited by 8
  8. 2025DDPM Score Matching and Distribution Learningcited by 7
  9. 2023Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributionscited by 5
  10. 2026Finite-Particle Rates for Regularized Stein Variational Gradient Descentcited by 5

Built on by

Not cited yet.