Complexity of Non-Log-Concave Sampling in Fisher Information

• URL: http://arxiv.org/abs/2605.15859v1
• Date: Fri, 15 May 2026 11:20:26 GMT
• Title: Complexity of Non-Log-Concave Sampling in Fisher Information
• Abstract summary: We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution.<n>Our algorithm is based on the proximal sampler, which is an implicit discretization of the Langevin diffusion.
• Score: 18.448754225782743
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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ényi 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.

Related papers

• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  We show that high-accuracy guarantees for log-concave sampling are achievable using iteration gradients with subexponential tails.<n>Our framework also provides similar high accuracy guarantees under zeroth order (value) queries.
  arXiv  Detail & Related papers  (2026-02-15T23:19:07Z)
• Optimizing Input Data Collection for Ranking and Selection [2.3708672042234213]
  We design a sequential sampling algorithm that collects input and simulation data given a budget.<n>We show that MPB's posterior probability of optimality converges to one at an exponential rate as the sampling budget increases.<n>We extend OSAR by adopting the kernel ridge regression to improve the simulation output mean prediction.
  arXiv  Detail & Related papers  (2025-02-23T17:33:43Z)
• Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality [14.023607664569989]
  We study the mixing time guarantee for sampling in relative Fisher information via the Proximal Sampler algorithm.<n>We show that when the target probability distribution is strongly log-concave, the relative Fisher information converges exponentially fast along the Proximal Sampler.
  arXiv  Detail & Related papers  (2025-02-08T16:07:12Z)
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  We propose a novel parallel sampling method that improves adaptive complexity dependence on dimension $d$.<n>Our approach builds on parallel simulation techniques from scientific computing.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
  We provide theoretical guarantees for the convergence behaviour of diffusion-based generative models under strongly log-concave data.<n>Our class of functions used for score estimation is made of Lipschitz continuous functions avoiding any Lipschitzness assumption on the score function.<n>This approach yields the best known convergence rate for our sampling algorithm.
  arXiv  Detail & Related papers  (2023-11-22T18:40:45Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.