Total Variation Guarantees for Sampling with Stochastic Localization

• URL: http://arxiv.org/abs/2603.29555v1
• Date: Tue, 31 Mar 2026 10:34:42 GMT
• Title: Total Variation Guarantees for Sampling with Stochastic Localization
• Abstract summary: We present a rigorous convergence analysis of SLIPS, a sampling algorithm based on localization.<n>We establish the first guarantee for SLIPS in total variation distance.<n>We further provide theoretical insights into the empirically observed optimal choice of discretization points.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the success of score-based generative models, a number of diffusion-based algorithms have recently been proposed for the problem of sampling from a probability measure whose unnormalized density can be accessed. Among them, Grenioux et al. introduced SLIPS, a sampling algorithm based on Stochastic Localization. While SLIPS exhibits strong empirical performance, no rigorous convergence analysis has previously been provided. In this work, we close this gap by establishing the first guarantee for SLIPS in total variation distance. Under minimal assumptions on the target, our bound implies that the number of steps required to achieve an $\varepsilon$-guarantee scales linearly with the dimension, up to logarithmic factors. The analysis leverages techniques from the theory of score-based generative models and further provides theoretical insights into the empirically observed optimal choice of discretization points.

Related papers

• Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry [2.15242029196761]
  We study distributed optimization with gradients and finite-bit communication modeled by random (unbiased) quantization.<n>Under restricted secant inequality (RSI), a constant step-size yields a linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity.<n>Under PolyakLojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same quantized setting.
  arXiv  Detail & Related papers  (2026-06-09T18:18:41Z)
• Sublinear iterations can suffice even for DDPMs [20.394390032998036]
  We show that a "shifted composition rule" algorithm enjoys favorable discretization properties under appropriate assumptions.<n>This is the first sublinear complexity bound for pure DDPM sampling.<n>We also provide experimental validation of the advantages of our method, showing that it performs well in practice with pre-trained image synthesis models.
  arXiv  Detail & Related papers  (2025-11-06T22:15:19Z)
• Derivative-Free Sequential Quadratic Programming for Equality-Constrained Stochastic Optimization [3.2489082010225485]
  We consider solving nonlinear optimization problems with an objective and deterministic equality constraints.<n>We propose a Derivative-Free Sequential Quadratic Programming (DF-SSQP) method.<n>Under standard assumptions, we establish the global almost-sure convergence of the proposed DF-SSQP method.
  arXiv  Detail & Related papers  (2025-10-25T23:51:20Z)
• Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces [3.637162892228131]
  We develop a conformal prediction algorithm that offers finite-sample coverage guarantees and fast convergence rates of the oracle estimator.<n>In heteroscedastic settings, we forgo these non-asymptotic guarantees to gain statistical efficiency.<n>We demonstrate the practical utility of our approach in personalized--medicine applications involving random response objects.
  arXiv  Detail & Related papers  (2025-07-21T15:54:13Z)
• Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
  We study how to steer generation toward desired rewards without retraining the models.<n>Prior methods typically resample or filter within a single denoising trajectory, optimizing rewards step-by-step without trajectory-level refinement.<n>We introduce particle Gibbs sampling for diffusion language models (PG-DLM), a novel inference-time algorithm enabling trajectory-level refinement while preserving generation perplexity.
  arXiv  Detail & Related papers  (2025-07-11T08:00:47Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)

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.