REVIEW 2 major objections 3 minor 1 cited by
On the query complexity of sampling from non-log-concave distributions
T0 review · 2 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read The paper proves matching upper and lower bounds showing the worst-case query complexity of sampling from $L$-log-smooth distributions with second moment at most $M$ is $(LM/(d\varepsilon))^{\Theta(d)}$.
desk verdict Strong lower bound with a matching upper bound that is formally proven only for centered potentials; the gap to the stated general theorem is real but probably fixable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The lower bound's load-bearing object is the plateau base distribution: a Gaussian with a flat ring of height $h_1 \approx \log(1/\varepsilon) + d \log R$ between radii $R/2$ and $R$, with $R = \sqrt{M/\varepsilon}$. Because the plateau raises the density where perturbations are placed, a perturbation of height $\gamma \approx d \log(3R/r)$ inside a ball of radius $r \approx \sqrt{d/L}$ adds about $\varepsilon$ of mass while keeping the Hessian at $O(L)$; a spherical-cap packing argument then yields $\left(\frac{LM}{d\varepsilon}\right)^{\Omega(d)}$ disjoint such balls on the sphere of radius $3R/4$. The upper bound's machinery is the truncated surrogate $\pi$: the target potential is cut at $h_1$, smoothly interpolated to $h_2 = h_1 + \frac d2 \log\frac{LM}{d\varepsilon}$, and replaced by a Gaussian outside radius $2R$; grid queries give $\hat f_* \in [f_*, f_*+d]$ and $\hat Z_\mu \in [e^{-d}Z_\mu/2, Z_\mu]$, enough to keep the density ratio $p_\pi/p_\gamma$ within $(LM/(d\varepsilon))^{O(d)}$ of a Gaussian and hence to control the Poincaré constant.
What would settle it
For a fixed parameter choice such as $d=10$, $L=M=10$, $\varepsilon=1/200$, evaluate the Hessian of the perturbed potential $f_v$ from Section 3.2 at points in the interpolation shell $r_1<\|x-v\|<r_2$; if its operator norm exceeds the universal constant times $L$, the hard-instance family is not $L$-log-smooth and the lower bound collapses. A complementary check is to run the upper-bound algorithm on the stitched-Gaussian family with $LM=\Theta(d)$ and constant $\varepsilon$: success in $\exp(o(d))$ queries would contradict the claimed $(LM/(d\varepsilon))^{\Omega(d)}$ lower bound.
Extended reading notes
Core claim
The central claim is that, for the class of distributions satisfying only $L$-log-smoothness and a second-moment bound $M$, the query complexity of $\varepsilon$-accurate sampling in total variation distance is $(LM/(d\varepsilon))^{\Theta(d)}$ under value and gradient oracle access. The lower bound holds for any $L,M$ with $LM \ge d \ge 5$ and $\varepsilon \in (0,1/200)$: the paper constructs a base distribution that is Gaussian except for a flat plateau ring, packs roughly $((R/r))^{d-1}$ disjoint balls on a sphere, and lowers the potential inside each ball by a carefully chosen amount so that each perturbed distribution is still $L$-log-smooth with second moment $O(M)$, while any two perturbed distributions are $4\varepsilon$ apart in total variation. The upper bound constructs a surrogate distribution $\pi$: outside a large ball it is Gaussian, inside a smaller ball the target potential is kept below a threshold, and the values of $\min f$ and the normalizing constant are estimated on a grid to within additive $d$ and multiplicative $e^{-d}$ respectively; the surrogate has a controlled Poincaré constant and is sampled with averaged Langevin dynamics. Together the two bounds characterize the worst-case exponent of the query complexity.
Load-bearing premise
The upper-bound algorithm and its proof assume the potential satisfies $\nabla f(0)=0$, using that origin to make the grid estimates of $f_*$ and $Z_\mu$ accurate; the paper says a stationary point can first be found by gradient descent, but it does not formalize the extra queries or the error propagation from an only approximately stationary point.
Editorial extensions
If this is right
- Any algorithm for this family must use exponentially many queries when $LM=\Theta(d)$, and at least $(1/\varepsilon)^{\Omega(d)}$ when $\varepsilon$ shrinks, ruling out samplers with polylogarithmic dependence on $1/\varepsilon$.
- When $LM=\omega(d)$, the lower bound becomes super-exponential in $d$, so the family contains distributions for which no sub-super-exponential sampling algorithm can exist under this oracle model.
- The upper bound shows that a very coarse estimate of $\min f$ and the normalizing constant—errors of size $d$ and factor $e^{-d}$—suffices to build a sampleable surrogate, which is why sampling does not require solving the optimization problem accurately.
- The OU-smoothness condition used by prior diffusion-based samplers is strictly stronger than $O(1)$-smoothness of the target: the stitched-Gaussian family is $O(1)$-log-smooth initially but develops Hessian of size $\Omega(e^{-2t}\|u\|^2)$ along the OU flow.
- For $LM=\Theta(d)$ and constant accuracy, the sampling upper bound is $(LM/d)^{O(d)}$, while the optimization lower bound is $(\alpha LM)^{d/2}$, so sampling can outperform optimization by a super-exponential factor.
Reading between the lines
- A natural extension of the lower-bound recipe is to weaker oracle models: if the same hard family can be recognized only through noisy or zeroth-order information, the $(LM/d\varepsilon)^{\Omega(d)}$ barrier should persist, although the paper does not analyze such oracles.
- The plateau construction suggests a general packing principle—place perturbations where the base density is highest so that small potential shifts move $\varepsilon$ mass—which could yield tight lower bounds for other structured non-log-concave families such as bounded mixtures.
- The paper's open conjecture that the exponent constant is $1/2$ implies that the gap between the current upper and lower bounds would be closed by replacing the truncation analysis with direct weak-Poincaré inequalities for the target distribution, an approach the paper explicitly leaves to future work.
- The smoothness analysis of the Ising-type mixture of Gaussians points toward a boundary question the paper does not resolve: for which spectra of the interaction matrix does polynomial-time sampling remain possible without extra assumptions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the worst-case query complexity of sampling from a d-dimensional distribution whose log-density is L-smooth and whose second moment is at most M. The lower-bound construction (Section 3) starts from a Gaussian-like base density with a flat annular plateau, then perturbs disjoint balls on that plateau; the authors prove that any algorithm must discover the perturbed ball, yielding an (LM/(dε))^{Ω(d)} query lower bound. The upper-bound algorithm (Section 4) constructs an auxiliary distribution π by truncating low-density regions of the target, approximating the minimum and normalizing constant on a grid, and then samples from π with a Langevin algorithm, giving (LM/(dε))^{O(d)} queries. The paper also compares the target-smoothness assumption with smoothness along the Ornstein-Uhlenbeck trajectory (stitched Gaussians and mixtures of Gaussians) and compares sampling with non-convex optimization, arguing that sampling can be super-exponentially easier than optimization.
Significance. If the matching upper and lower bounds hold for the full class, this is a significant contribution: it identifies the correct exponential dependence of query complexity on L, M, d, and ε for non-log-concave sampling, improves the earlier e^{Ω(d)} lower bound, and gives the first ε-dependence in this regime. The explicit stitched-Gaussian family clarifies that smoothness of the initial log-density does not imply smoothness along the OU trajectory, and the Ising-model connection is a nice addition. The proof structure is coherent, with detailed estimates for the lower-bound construction and for the Poincaré constant, smoothness, and warm start of the auxiliary distribution. However, the upper bound is formally proved only under the extra condition ∇f(0)=0, and the paper's claim that this is removable by a gradient-descent preprocessing step is not backed by a theorem; this gap affects the central matching-characterization claim for the full family.
major comments (2)
- Theorem 4 is stated only for potentials with ∇f(0)=0, and the text says the assumption is made 'for simplicity' and that one can first run gradient descent to find a stationary point and shift the origin. No theorem, query count, or error-propagation analysis for this reduction is provided. The gap is load-bearing: Lemma 26 uses ∇f(0)=0 to conclude ∇f_{≤2Rπ}(0)=0 and to bound gradients by L‖x‖ in B_{2R}; Lemma 32 uses ∥∇fμ(x)∥≤L‖x‖ when estimating f* and Zμ on the grid; and Corollary 28 together with Lemma 34 uses fπ(0)=min fπ and the warm-start bound KL(μ0∥π). If the new origin is only a δ-stationary point, each of these estimates changes: the grid errors in Lemma 32 acquire extra δ·√d·ℓ terms, the second moment about the shifted origin need not remain at most M, and the KL warm-start bound must be recomputed. A formal reduction with explicit δ and query cost is therefore necessary before Theorems 3 and 4 establish the claimed tight complexity for the full family D_{L,M}; alternatively, the abstract and Section 1 should state the upper bound only for the centered subclass.
- Theorem 8 claims that for every algorithm that succeeds on all of D_{L,M}, there is a hard distribution in D_{L,M}. However, the hard instances constructed in Section 3 are shown only to be O(L)-log-smooth with second moment O(M): Lemma 10 gives second moment O(M), Lemma 13 gives E_{μv}[‖X‖²]=O(M), and Lemma 14 gives O(L)-smoothness with unspecified universal constants. The proof then asserts, without a further argument, that the instances can be assumed to satisfy second moment at most M and smoothness L. This is a formal gap in the theorem statement. It is likely fixable by rescaling M (or by absorbing the universal constants into the Ω-exponent), but as written the lower bound is not literally against D_{L,M}.
minor comments (3)
- The definition r₂ = √(2r₁) is dimensionally inconsistent and incompatible with the mollifier construction, which requires r₂ ≥ r₁; the intended definition is presumably r₂ = √2·r₁. Please correct this throughout Section 3, since all subsequent radius ratios depend on it.
- The displayed Hessian computations in Lemma 10 (and similar long displayed equations in Lemma 22 and Section 5.2.1) contain unreadable inserted symbols in the provided version. These are likely transcription artifacts, but the arXiv version should be checked so that every displayed calculation is legible and complete.
- The statement of Theorem 5 says 'for arbitrary s=Ω(d)' but uses s both for the squared center distance and later for time scales; please define the parameter explicitly and avoid reusing s with the stationary-point notation from Section 1.1.
Circularity Check
No circularity: the lower and upper bounds are self-contained derivations from stated assumptions; self-citations are contextual and the ∇f(0)=0 caveat is a completeness gap, not a circular reduction.
full rationale
The paper's central claims are derived from first principles within the manuscript rather than from fitted parameters or load-bearing self-citations. The lower bound (Theorem 3 / Theorem 8) is an adversary construction: for any algorithm, the paper builds a base distribution and n perturbed distributions with the same L-smoothness and second-moment bound, proves pair-wise total-variation distance at least 4ε, and shows that any algorithm using fewer than the stated number of queries cannot identify which of two high-probability query zones was perturbed. The number of queries is bounded by the packing count from Lemma 16, which depends only on L, M, d, and ε; the perturbed distributions are constructed in Sections 3.1-3.3 with explicit smoothness and moment checks. Nothing in this chain is fitted to the algorithm's output or defined in terms of the target claim. The upper bound (Theorem 4) constructs an auxiliary distribution π with TV(π, μ) ≤ ε/2, bounded smoothness, bounded first moment, and a lower bound on its Poincaré constant, then invokes the external Langevin analysis of [BCE+22] and [CEL+24]. The estimation of f* and Zμ in Proposition 18 is obtained by grid queries, and the error bounds in Lemma 32 are proven directly from L-smoothness and ∇f(0)=0, not by assuming the conclusion. The self-citations [HRT24] and [HMHBE24] appear only in the introduction and comparison sections to contextualize the problem or to contrast with known bounds; they are not used as premises in the proof of either Theorem 3 or Theorem 4. The paper explicitly flags a limitation in Theorem 4: the proof assumes ∇f(0)=0 and says a gradient-descent preprocessing step can remove this assumption 'for simplicity,' but no theorem or query-count analysis is given for that reduction. This is a genuine completeness or correctness caveat in the claimed matching characterization over the full family D_{L,M}, but it is not circularity: the missing step would add an extra term to the query complexity and error propagation, not make the upper bound equal to its inputs by construction. Similarly, the statement that 'the optimal query complexity ... should be (LM/dε)^{Θ(d)}' is presented as a match between the proven upper and lower bounds and is explicitly interpreted as a characterization up to constants in the exponent; it is not a renamed version of a previously known empirical pattern.
Assumptions & free parameters
assumptions (4)
- domain assumption Oracle returns exact values of f and grad f at any queried point, with no noise.
- domain assumption Target distributions satisfy only L-log-smoothness and bounded second moment M (Assumptions 1 and 2).
- domain assumption External theorems used as black boxes: Langevin convergence under Poincare inequality (BCE+22), KL warm-start bound (CEL+24), optimization lower bound (MCJ+19), and OU Hessian identity (CLL23).
- standard math Standard measure-concentration and volume estimates: Stirling bounds, ball volumes, Gaussian tail bounds, Cauchy-Schwarz.
Cite this review
Pith. "Pith review of On the query complexity of sampling from non-log-concave distributions." pith.science (2026). https://pith.science/paper/QEFIBJQC
@misc{pith2026250206200,
author = {Pith},
title = {Pith review of: On the query complexity of sampling from non-log-concave distributions},
year = {2026},
howpublished = {\url{https://pith.science/paper/QEFIBJQC}},
note = {Machine review of arXiv:2502.06200}
}
abstract
We study the problem of sampling from a $d$-dimensional distribution with density $p(x)\propto e^{-f(x)}$, which does not necessarily satisfy good isoperimetric conditions. Specifically, we show that for any $L,M$ satisfying $LM\ge d\ge 5$, $\epsilon\in \left(0,\frac{1}{32}\right)$, and any algorithm with query accesses to the value of $f(x)$ and $\nabla f(x)$, there exists an $L$-log-smooth distribution with second moment at most $M$ such that the algorithm requires $\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$ queries to compute a sample whose distribution is within $\epsilon$ in total variation distance to the target distribution. We complement the lower bound with an algorithm requiring $\left(\frac{LM}{d\epsilon}\right)^{\mathcal{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=\mathtt{poly}(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 $\mathcal{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$.
Figures
Forward citations
Cited by 1 Pith paper
-
The Universal Warmup Path: Automatic Preconditioner Selection for HMC
A dimension-scheduled multi-chain controller automatically selects diagonal vs low-rank HMC preconditioners from warmup evidence and outperforms fixed Fisher and diagonal baselines on ESS per gradient.
Reference graph
Works this paper leans on
-
[1]
Faster high-accuracy log-concave sampling via algorithmic warm starts
Jason M Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. Journal of the ACM , 71(3):1--55, 2024
work page 2024
-
[2]
An introduction to MCMC for machine learning
Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael I Jordan. An introduction to MCMC for machine learning. Machine learning , 50:5--43, 2003
work page 2003
-
[3]
Nearly d-linear convergence bounds for diffusion models via stochastic localization
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear convergence bounds for diffusion models via stochastic localization. In International Conference on Learning Representations . OpenReview.net, 2024
work page 2024
-
[4]
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of non-log-concave sampling:first-order stationarity guarantees for Langevin Monte Carlo . In The Annual Conference on Learning Theory , volume 178, pages 2896--2923. PMLR, 2022
work page 2022
-
[5]
Herm Jan Brascamp and Elliott H Lieb. On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. Journal of Functional Analysis , 22(4):366--389, 1976
work page 1976
-
[6]
Convergence of Langevin MCMC in KL-divergence
Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence . In Algorithmic Learning Theory , volume 83, pages 186--211. PMLR , 2018
work page 2018
-
[7]
Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Underdamped Langevin MCMC : A non-asymptotic analysis. In The Annual Conference on Learning Theory , volume 75, pages 300--323. PMLR, 2018
work page 2018
-
[8]
The probability flow ODE is provably fast
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems , 2023
work page 2023
Show all 38 references
-
[9]
Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations . OpenReview.net, 2023
2023
-
[10]
Analysis of Langevin Monte Carlo from Poincar \'e to log-Sobolev
Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Matthew S Zhang. Analysis of Langevin Monte Carlo from Poincar \'e to log-Sobolev . Foundations of Computational Mathematics , pages 1--51, 2024
2024
-
[11]
On theoretical guarantees and a blessing of dimensionality for nonconvex sampling
Martin Chak. On theoretical guarantees and a blessing of dimensionality for nonconvex sampling. arXiv preprint arXiv:2411.07776 , 2024
2024 arXiv
-
[12]
Log-concave Sampling
Sinho Chewi. Log-concave Sampling . 2024. Book draft available at https://chewisinho.github.io
2024
-
[13]
Optimal dimension dependence of the Metropolis-adjusted Langevin algorithm
Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. Optimal dimension dependence of the Metropolis-adjusted Langevin algorithm. In The Annual Conference on Learning Theory , volume 134, pages 1260--1300. PMLR , 2021
2021
-
[14]
Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning , volume 202, pages 4735--4763. PMLR , 2023
2023
-
[15]
Simulation and Monte Carlo : With applications in finance and MCMC
John S Dagpunar. Simulation and Monte Carlo : With applications in finance and MCMC . John Wiley & Sons, 2007
2007
-
[16]
Log-concave sampling: Metropolis-Hastings algorithms are fast
Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis-Hastings algorithms are fast. Journal of Machine Learning Research , 20(183):1--42, 2019
2019
-
[17]
On sampling from Ising models with spectral constraints
Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. On sampling from Ising models with spectral constraints. 317:70:1--70:14, 2024
2024
-
[18]
Provable benefit of annealed Langevin Monte Carlo for non-log-concave sampling
Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed Langevin Monte Carlo for non-log-concave sampling. arXiv preprint arXiv:2407.16936 , 2024
2024 arXiv
-
[19]
Convergence rates for non-log-concave sampling and log-partition estimation
David Holzm \"u ller and Francis Bach. Convergence rates for non-log-concave sampling and log-partition estimation. arXiv preprint arXiv:2303.03237 , 2023
2023 arXiv
-
[20]
A separation in heavy-tailed sampling: Gaussian vs
Ye He, Alireza Mousavi-Hosseini, Krishnakumar Balasubramanian, and Murat A Erdogdu. A separation in heavy-tailed sampling: Gaussian vs. stable oracles for proximal samplers. Advances in Neural Information Processing Systems , 2024
2024
-
[21]
Weak Poincar 'e inequalities, simulated annealing, and sampling from spherical spin glasses
Brice Huang, Sidhanth Mohanty, Amit Rajaraman, and David X Wu. Weak Poincar 'e inequalities, simulated annealing, and sampling from spherical spin glasses. arXiv preprint arXiv:2411.09075 , 2024
2024 arXiv
-
[22]
Zeroth-order sampling methods for non-log-concave distributions: Alleviating metastability by denoising diffusion
Ye He, Kevin Rojas, and Molei Tao. Zeroth-order sampling methods for non-log-concave distributions: Alleviating metastability by denoising diffusion. Advances in Neural Information Processing Systems , 2024
2024
-
[23]
Faster sampling without isoperimetry via diffusion-based Monte Carlo
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, and Tong Zhang. Faster sampling without isoperimetry via diffusion-based Monte Carlo . In The Annual Conference on Learning Theory , volume 247, pages 2438--2493. PMLR , 2024
2024
-
[24]
Sampling approximately low-rank Ising models: MCMC meets variational methods
Frederic Koehler, Holden Lee, and Andrej Risteski. Sampling approximately low-rank Ising models: MCMC meets variational methods. In The Annual Conference on Learning Theory , volume 178, pages 4945--4988. PMLR , 2022
2022
-
[25]
Statistical mechanics: algorithms and computations , volume 13
Werner Krauth. Statistical mechanics: algorithms and computations , volume 13. OUP Oxford, 2006
2006
-
[26]
A guide to Monte Carlo simulations in statistical physics
David Landau and Kurt Binder. A guide to Monte Carlo simulations in statistical physics . Cambridge university press, 2021
2021
-
[27]
Concise formulas for the area and volume of a hyperspherical cap
Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics & Statistics , 4(1):66--70, 2010
2010
-
[28]
Convergence of score-based generative modeling for general data distributions
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory , volume 201, pages 946--985. PMLR , 2023
2023
-
[29]
Universal approximation using well-conditioned normalizing flows
Holden Lee, Chirag Pabbaraju, Anish Prasad Sevekari, and Andrej Risteski. Universal approximation using well-conditioned normalizing flows. Advances in Neural Information Processing Systems , 34:12700--12711, 2021
2021
-
[30]
Contraction and convergence rates for discretized kinetic Langevin dynamics
Benedict J Leimkuhler, Daniel Paulin, and Peter A Whalley. Contraction and convergence rates for discretized kinetic Langevin dynamics. SIAM Journal on Numerical Analysis , 62(3):1226--1258, 2024
2024
-
[31]
Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo
Holden Lee, Andrej Risteski, and Rong Ge. Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo . In Advances in Neural Information Processing Systems , volume 31. Curran Associates, Inc., 2018
2018
-
[32]
Sampling can be faster than optimization
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences , 116(42):20881--20885, 2019
2019
-
[33]
Towards a complete analysis of Langevin Monte Carlo : Beyond Poincar \'e inequality
Alireza Mousavi-Hosseini, Tyler K Farghly, Ye He, Krishna Balasubramanian, and Murat A Erdogdu. Towards a complete analysis of Langevin Monte Carlo : Beyond Poincar \'e inequality. In The Annual Conference on Learning Theory , volume 195, pages 1--35. PMLR , 2023
2023
-
[34]
Exponential convergence of Langevin distributions and their discrete approximations
Gareth O Roberts and Richard L Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli , 2(4):341 -- 363, 1996
1996
-
[35]
The randomized midpoint method for log-concave sampling
Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems , volume 32, pages 2098--2109, 2019
2019
-
[36]
Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. Advances in Neural Information Processing Systems , 32:8092--8104, 2019
2019
-
[37]
Proximal Langevin algorithm: Rapid convergence under isoperimetry
Andre Wibisono. Proximal Langevin algorithm: Rapid convergence under isoperimetry. arXiv preprint arXiv:1911.01469 , 2019
1911 arXiv
-
[38]
Improved discretization analysis for underdamped Langevin Monte Carlo
Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu. Improved discretization analysis for underdamped Langevin Monte Carlo . In The Annual Conference on Learning Theory , volume 195, pages 36--71. PMLR , 2023
2023
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.