Pith. sign in

REVIEW 2 major objections 4 minor 58 references

Faster logconcave sampling from a cold start in high dimension

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Cold-start sampling of logconcave densities in near-isotropic position runs in $\widetilde{O}(n^{2.75})$ queries, breaking a cubic barrier with relaxed R\'enyi warmness and an improved log-Sobolev bound.

desk verdict First sub-cubic cold-start sampling for near-isotropic inputs, with a real but patchable proof gap in the covariance-control lemma that does not touch the main n^2.75 claim. read the letter →

arxiv 2505.01937 v1 pith:KUKLP45Q submitted 2025-05-03 cs.DS cs.LGmath.FAmath.STstat.MLstat.TH

Yunbum Kook , Santosh S. Vempala This is my paper · ORCID
classification cs.DScs.LGmath.FAmath.STstat.MLstat.TH MSC 68W2068Q2560J2252A23
keywords logconcavesamplingcoldstartwarmGaussiancoolingRényidivergencelog-Sobolevinequalityproximalsamplerconvexbody
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sampling from an arbitrary logconcave density without a warm start has long faced a cubic barrier in the dimension: every known algorithm paid a warm-start generation penalty that left total query complexity at least cubic. This paper breaks that barrier for inputs in near-isotropic position, establishing that uniform sampling from a convex body given by a membership oracle costs $\widetilde{O}(n^{2.75})$ queries from a cold start, and that arbitrary logconcave densities given by an evaluation oracle admit the same exponent. The improvement comes from two ingredients: showing the proximal sampler only needs polylog-order R\'enyi warmness instead of the stringent infinity-R\'enyi warmness required since the first Ball-walk analyses in 1991, and proving a sharper log-Sobolev inequality for Gaussian-weighted logconcave measures with compact support. If correct, this removes the warm-start bottleneck that has persisted for three decades and makes sub-cubic sampling the new state of the art for well-rounded inputs.

What carries the argument

The argument is carried by three mechanisms. (1) A covariance-control lemma (Theorem 3.2): for a logconcave measure $\pi$ with first moment $R = E_\pi\|\cdot\|$ and largest covariance eigenvalue $\lambda$, the Gaussian-weighted measure $\pi\gamma_h$ satisfies $\|\mathrm{cov}(\pi\gamma_h)\| \lesssim \|\mathrm{cov}\,\pi\|$ once $h \gtrsim R\lambda^{1/2}\log^2 n\log^2(R^2/\lambda)$; the proof uses Lipschitz concentration under the Poincar\'e inequality, a thin-shell decomposition, and co-area/integration-by-parts estimates. (2) An interpolated log-Sobolev bound (Theorem 3.1 and Corollary 1.7): for logconcave $\pi$ supported in a set of diameter $D$, $C_{\mathrm{LSI}}(\pi) \lesssim \max\{D\lambda^{1/2}, D^2\wedge\lambda\log^2 n\}$, and consequently $C_{\mathrm{LSI}}(\pi\gamma_h) \lesssim D\lambda^{1/2}\,\mathrm{polylog}$ for all $h>0$, obtained by combining the known equivalence between Gaussian concentration and the log-Sobolev inequality for logconcave measures with two exponential-concentration bounds (one classical under the Poincar\'e inequality, one derived from stochastic localization). (3) R\'enyi-divergence annealing lemmas (Lemmas 4.4 and 4.5) that bound $R_q$ between consecutive annealing distributions and justify the accelerated variance schedule $\sigma^2 \leftarrow \sigma^2(1 + \sigma/(q^{1/2}R))$. The proximal sampler for uniform and truncated-Gaussian targets is the sampling workhorse whose required warmness drops from $R_\infty$ to $R_c$ with $c = \widetilde{O}(1)$.

What would settle it

Take a concrete non-Gaussian logconcave family — for instance the uniform distribution on a long thin box, or an affine image of the unit cube, in dimension $n$ — with known first moment $R$ and covariance norm $\lambda$, and numerically compute the operator norm of $\mathrm{cov}(\pi\gamma_h)$ at $h = C R\lambda^{1/2}\log^2n\log^2(R^2/\lambda)$ for a range of universal constants $C$. If the ratio $\|\mathrm{cov}(\pi\gamma_h)\|/\lambda$ exceeds any fixed universal constant at the stated threshold, Theorem 3.2 is false and the $n^{2.75}$ annealing schedule cannot be sustained.

Watch

Extended reading notes

Core claim

The paper's central claim is that the cubic barrier for cold-start sampling is not intrinsic. For a convex body $K$ given by a membership oracle with an enclosed unit ball and second-moment radius $R$, and uniform target $\pi$ with covariance operator norm $\lambda$, Theorem 1.8 asserts an algorithm that returns a sample $\varepsilon$-close in TV distance using $\widetilde{O}(n^2 R^{3/2}\lambda^{1/4}\,\mathrm{polylog}(1/\eta\varepsilon))$ membership queries in expectation; when $\pi$ is near-isotropic this is $\widetilde{O}(n^{2.75})$, the first sub-cubic cold-start bound. Theorem 1.10 extends the same $n^{2.75}$ exponent to arbitrary logconcave densities given an evaluation oracle, with complexity $\widetilde{O}(n^2\max\{n^{1/2}, R^{3/2}(\lambda^{1/4}\vee 1)\})$. The engine is a faster Gaussian-cooling schedule: because the proximal sampler now mixes from only polylog-order R\'enyi warmness, the annealing variance $\sigma^2$ can be multiplied by $1 + \sigma/(q^{1/2}R)$ rather than $1 + \sigma^2/R^2$, and once $\sigma^2$ exceeds $R\lambda^{1/2}$ polylog, the new log-Sobolev bound makes each phase cheaper still. Sampling a standard Gaussian truncated to an arbitrary convex body drops to $\widetilde{O}(n^{2.5})$ queries.

Load-bearing premise

The entire speedup depends on the claim that mixing a logconcave measure with a Gaussian of variance as small as $R\lambda^{1/2}$ polylog cannot enlarge its covariance beyond a constant factor of the original; if that geometric assertion fails, the fast annealing phase of the algorithm is not justified and the sub-cubic bound collapses.

Editorial extensions

If this is right

  • Cold-start uniform sampling from a convex body in near-isotropic position costs $\widetilde{O}(n^{2.75})$ membership queries instead of the previous cubic bound from Gaussian cooling, with the same total-variation guarantee.
  • Sampling a standard Gaussian truncated to an arbitrary convex body costs $\widetilde{O}(n^{2.5})$ queries, improving the previous cubic bound by a factor of $n^{1/2}$.
  • Arbitrary logconcave densities given by an evaluation oracle inherit the same $n^{2.75}$ exponent for near-isotropic inputs, at cost $\widetilde{O}(n^2\max\{n^{1/2}, R^{3/2}(\lambda^{1/4}\vee 1)\})$.
  • The warmness requirement for the proximal sampler drops from infinity-R\'enyi divergence (essentially a pointwise density-ratio bound) to $q$-R\'enyi divergence with $q = \widetilde{O}(1)$, the first improvement in required warmness since 1991.
  • If the KLS conjecture holds, the log-Sobolev bound sharpens to $C_{\mathrm{LSI}}(\pi) \lesssim D\lambda^{1/2}$ without logarithmic factors, sharpening the same algorithmic bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The covariance-control lemma (Theorem 3.2) is the piece the whole speedup leans on; if Gaussian weighting can inflate covariance beyond $O(\lambda)$ at the stated threshold for some logconcave family, the accelerated phase would require a larger variance and the sub-cubic exponent would dissolve. Testing this lemma numerically on anisotropic logconcave families (slabs, affine images of cubes) woul
  • The same template — R\'enyi-warm annealing plus an interpolated log-Sobolev bound — should transfer to other samplers whose mixing is controlled by Poincar\'e or log-Sobolev constants, such as constrained Hamiltonian or Langevin methods, where warmness has likewise been a bottleneck; the paper does not explore this extension.
  • The $n^{2.75}$ exponent is unlikely to be final: the schedule's slope is set by the ratio $\sigma/R$ in the annealing multiplier, and any improvement in the covariance-control threshold (for instance replacing Poincar\'e-based concentration with thin-shell estimates) would lower the exponent further, with the $\widetilde{O}(n^2)$ warm-start mixing bound as the natural target.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops faster cold-start sampling algorithms for convex bodies and general logconcave distributions. Its main results are: (1) proximal samplers for uniform and truncated Gaussian distributions are shown to mix under an R_c-warm start with c = polylog(n), rather than the previous R∞-warmness; (2) a new log-Sobolev bound CLSI(π) ≲ D||cov π||^{1/2} polylog for compactly supported logconcave π, interpolating the known D and D² bounds; (3) a covariance-control lemma stating that Gaussian weighting of a logconcave measure does not inflate the covariance when the Gaussian variance is at least roughly R λ^{1/2} polylog; and (4) annealing algorithms based on these ingredients that achieve ~O(n² R^{3/2} λ^{1/4}) membership queries for uniform distributions and ~O(n² max{n^{1/2}, R^{3/2}(λ^{1/4}∨1)}) evaluation queries for general logconcave distributions, hence n^{2.75} in the near-isotropic case. Appendix A gives an alternative stochastic-localization proof of the LSI bound.

Significance. If the technical gaps are closed, this is a substantial advance: it is the first claimed sub-cubic sampling algorithm for near-isotropic inputs from a cold start, and the relaxation of warmness from R∞ to R_c for proximal samplers appears to be a genuinely new and useful contribution. The paper is well structured, the main mixing calculations in Sections 2 and 4 are coherent, and the Rényi-divergence versions of the annealing lemmas are of independent interest. The main risk is not an internal inconsistency in the sampling framework but a specific unproven edge case in the covariance-control theorem, on which the general-input complexity bound rests.

major comments (2)
  1. [§3.2, Theorem 3.2] The proof of Theorem 3.2 does not currently handle the regime where the normalized radius R is small. After scaling to unit covariance, the proof defines R := Eν||·||2 and asserts R ≥ 1. If this means Eν||Y||, the assertion is false: even a one-dimensional standard Gaussian has E|Z| ≈ 0.8, and a near-rank-one logconcave ν with ||cov ν|| = 1 behaves roughly like this. If R instead means sqrt(Eν||Y||²), then the theorem statement, which uses the first moment R = Eπ||·||, is not what is proved. The subsequent shell S = {||Y|| ∈ [R ± t]} requires t = c1 C_PI^{1/2} log R > 0, so for R < 1 the set is not well-defined and the denominator lower bound D ≳ exp(−R²/(2η)) ν(S) collapses. This is a proof gap rather than a demonstrated falsehood, but it is load-bearing because Corollary 3.3 and the annealing threshold in Theorems 4.2 and 5.1 rely on Theorem 3.2 for general inputs. Please revise the statement to use max(R, λ^{1/2}) (or another quantity satisfying the needed lower bound), or supply a separate argument for R < λ^{1/2}.
  2. [§1.2.3 and §4.2 (Lemma 4.8)] The treatment of approximate annealing states is incomplete. The triangle-inequality argument in §1.2.3 successfully controls the final TV error, but it does not establish that the actual distribution γ̂_{i−1} starting phase i is R_c-warm with respect to γ_i, which is what Theorem 2.2 requires to bound the query complexity of that phase. Boundedness of the clipped per-step cost ℓ^{-1}∧N and TV closeness would give an extra Nε term in the expected query count, so the argument is likely repairable, but it is not written. Please add the explicit accounting for the way approximate starts affect both the failure probability and the expected number of backward-step trials in each subsequent annealing phase.
minor comments (4)
  1. [§1.1 and §3.3] Result 2 references §A for the LSI bound for strongly logconcave distributions, but the main proof of Corollary 3.3 is in §3.3; §A contains an alternative stochastic-localization proof. Please correct the cross-reference.
  2. [Lemma 4.5] The lemma is stated for a distribution with support of diameter R, but the proof uses sup_νu ||X|| ≤ R. This requires the support to be contained in a ball of radius R, not merely to have diameter R. The annealing application uses K ∩ B_R(0), so the statement should say 'support contained in B_R(0)' to match the proof.
  3. [Definitions and theorem statements] There is minor notational drift between MemR(K), MemD(K), and Mem_{x0,R}(K) across Theorem 1.3, Theorem 1.4, Theorem 2.1, and Theorem 2.2. Please make the roles of D, R, and λ consistent in all statements.
  4. [§3.2, proof of Theorem 3.2] The expression 'R := Eν||·||2 (≥ 1)' is ambiguous: it should be clarified whether R is the first moment of the norm or the square root of the second moment, since the proof's shell argument depends on this distinction.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's complexity bounds are derived from stated lemmas and externally published results; self-citations are used as independent support rather than as assumed conclusions.

full rationale

The derivation chain is self-contained. The warm-start sampler bounds (Theorems 1.3, 1.4, 2.1, 2.2) follow from the proximal-sampler mixing lemmas of CCSW22 combined with the paper's own (p,q)-Holder decomposition of the rejection-sampling cost; the relaxed warmness condition R_c with c = ~O(1) is obtained by explicit inequalities, not by postulating the desired complexity. The improved LSI bound (Theorem 3.1) is derived from Milman's equivalence between Gaussian concentration and LSI, Bizeul's exponential concentration theorem, and Klartag's Poincare bound for isotropic logconcave measures; these are external results used as inputs, and the paper does not assume its own CLSI bound in their proofs. The covariance-control lemma (Theorem 3.2) is proved directly via Lipschitz concentration, co-area formula, integration by parts, and thin-shell estimates; it is an internal theorem whose statement does not contain the target query complexity or the annealing threshold. The final sub-cubic bound n^2 R^{3/2} lambda^{1/4} is then an arithmetic consequence of the annealing schedule (Lemma 4.5), the LSI/PSGauss iteration bounds, and the number of doubling phases; no fitted parameter is renamed as a prediction. The same structure holds for the logconcave extension (Theorem 1.10), where the per-phase bounds from Theorems 5.2 and 5.3 are combined with the Rényi annealing lemmas. The citations to the authors' prior work [KVZ24, KZ25, KV25, LV24] are load-bearing in the sense that the paper relies on published lemmas from those works, but those are externally accessible, stated results with their own proofs, not restatements of the present paper's conclusions; citing them does not make the derivation circular. A separate concern exists in the proof of Theorem 3.2, where the line 'R := E_nu||Y|| (>= 1)' in Section 3.2 is not true for every centered logconcave nu with unit covariance, since R can be below 1 (e.g., a 1D standard Gaussian has R ~ 0.8); this appears to be a proof gap for the R < 1 regime, and the thin-shell set S = {||Y|| in [R +/- t]} is ill-defined for negative t. That is a correctness or proof-completeness issue, not circularity, because the claimed covariance bound is not being assumed as an input. Accordingly, no circular step meets the quoted-reduction standard, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No parameters are fitted to data. The algorithm parameters q, h, N, and the step-size schedules are set explicitly from n, R, lambda, eta, and epsilon in Sections 2, 4, and 5. The central claims rest on standard geometric and functional-analysis theorems, listed above, plus the paper's own new lemmas. No new particles, forces, or ad hoc entities are introduced.

assumptions (6)
  • domain assumption Logconcave target distributions and the membership/evaluation oracle model with a unit inner ball and a finite second-moment radius R (Definitions 1.11 and 1.12).
    All theorems are stated in this oracle model, and the results do not apply to arbitrary densities or oracles without these guarantees.
  • standard math Klartag's bound C_PI(pi) <= C ||cov pi|| log n for every logconcave probability measure.
    Invoked throughout Sections 2 and 3, for example after Lemma 2.3 and in the proof of Theorem 3.1, as the current near-KLS isoperimetric bound.
  • standard math Bizeul's exponential concentration bound for logconcave measures (Theorem 3.8, cited to [Biz24]).
    Used in the proof of Theorem 3.1 to obtain C_LSI(pi) <= D lambda^{1/2} or lambda log^2 n; if this bound is incorrect, the main LSI corollary weakens.
  • standard math Milman's equivalence for logconcave measures: Gaussian concentration and LSI hold with comparable constants (Theorem 3.6).
    This is the bridge from concentration bounds to LSI constants in Section 3.1.
  • standard math Bakry-Emery and Brascamp-Lieb LSI and Poincare bounds for strongly logconcave measures, plus Holley-Stroock bounded perturbation.
    Used for C_LSI(pi gamma_h) <= h and in Lemma 4.5 for the Poincare constant of Gaussian-weighted distributions.
  • standard math Stochastic localization well-posedness, its quadratic variation estimates, and Freedman's inequality, as used in the Appendix A proof.
    The alternate proof of Theorem 3.1 relies on this machinery from Eldan, Klartag, Lehec, and Lee-Vempala.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster logconcave sampling from a cold start in high dimension." pith.science (2026). https://pith.science/paper/KUKLP45Q

@misc{pith2026250501937,
  author       = {Pith},
  title        = {Pith review of: Faster logconcave sampling from a cold start in high dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KUKLP45Q}},
  note         = {Machine review of arXiv:2505.01937}
}
abstract

We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular $q$-R\'enyi divergence for $q=\widetilde{\mathcal{O}}(1)$, whereas previous analyses required stringent $\infty$-R\'enyi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lov\'asz and Simonovits (1991). (2) We refine and generalize the log-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 52 canonical work pages

  1. [1]

    The central limit problem for convex bodies

    Milla Anttila, Keith Ball, and Irini Perissinaki. The central limit problem for convex bodies. Trans. Amer. Math. Soc. , 355(12):4723--4735, 2003

    work page 2003

  2. [2]

    Analysis and geometry of M arkov diffusion operators , volume 348

    Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of M arkov diffusion operators , volume 348. Springer, Cham, 2014

    work page 2014

  3. [3]

    On measures strongly log-concave on a subspace

    Pierre Bizeul. On measures strongly log-concave on a subspace. Ann. Inst. Henri Poincar\' e Probab. Stat. , 60(2):1090--1100, 2024

    work page 2024

  4. [4]

    The slicing conjecture via small ball estimates

    Pierre Bizeul. The slicing conjecture via small ball estimates. arXiv preprint arXiv:2501.06854 , 2025

    arXiv 2025

  5. [5]

    Bobkov and Alexander Koldobsky

    Sergey G. Bobkov and Alexander Koldobsky. On the central limit property of convex bodies. In Geometric Aspects of Functional Analysis , volume 1807 of Lecture Notes in Math. , pages 44--52. Springer, Berlin, 2003

    work page 2003

  6. [6]

    A note on the isoperimetric constant

    Peter Buser. A note on the isoperimetric constant. Ann. Sci. \' E cole Norm. Sup. (4) , 15(2):213--230, 1982

    work page 1982

  7. [7]

    Caffarelli

    Luis A. Caffarelli. Monotonicity properties of optimal transportation and the FKG and related inequalities. Comm. Math. Phys. , 214(3):547--563, 2000

    2000

  8. [8]

    Improved analysis for a proximal algorithm for sampling

    Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory , volume 178, pages 2984--3014. PMLR, 2022

    work page 2022

Show all 58 references
  1. [9]

    A lower bound for the smallest eigenvalue of the L aplacian

    Jeff Cheeger. A lower bound for the smallest eigenvalue of the L aplacian. In Problems in analysis , pages 195--199. Princeton Univ. Press, Princeton, NJ, 1970

    1970

  2. [10]

    An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture

    Yuansi Chen. An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geom. Funct. Anal. , 31(1):34--61, 2021

    2021

  3. [11]

    Ben Cousins and Santosh S. Vempala. A cubic algorithm for computing G aussian volume. In S ymposium on D iscrete A lgorithms , pages 1215--1228. ACM, 2014

    2014

  4. [12]

    Ben Cousins and Santosh S. Vempala. Bypassing KLS : G aussian cooling and an O^*(n^3) volume algorithm. In S ymposium on T heory of C omputing , pages 539--548. ACM, 2015

    2015

  5. [13]

    Ben Cousins and Santosh S. Vempala. A practical volume algorithm. Mathematical Programming Computation , 8(2):133--160, Jun 2016

    2016

  6. [14]

    Ben Cousins and Santosh S. Vempala. Gaussian cooling and O^*(n^3) algorithms for volume and G aussian volume. SIAM J. Comput. , 47(3):1237--1273, 2018

    2018

  7. [15]

    A random polynomial-time algorithm for approximating the volume of convex bodies

    Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. , 38(1):1--17, 1991

    1991

  8. [16]

    Small ball probability estimates, _2 -behavior and the hyperplane conjecture

    Nikos Dafnis and Grigoris Paouris. Small ball probability estimates, _2 -behavior and the hyperplane conjecture. J. Funct. Anal. , 258(6):1933--1964, 2010

    1933

  9. [17]

    Thin shell implies spectral gap up to polylog via a stochastic localization scheme

    Ronen Eldan. Thin shell implies spectral gap up to polylog via a stochastic localization scheme. Geom. Funct. Anal. , 23(2):532--569, 2013

    2013

  10. [18]

    Log- S obolev inequalities and sampling from log-concave distributions

    Alan Frieze and Ravi Kannan. Log- S obolev inequalities and sampling from log-concave distributions. Ann. Appl. Probab. , 9(1):14--26, 1999

    1999

  11. [19]

    Improved dimension dependence of a proximal algorithm for sampling

    Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of a proximal algorithm for sampling. In Conference on Learning Theory , volume 195, pages 1473--1521. PMLR, 2023

    2023

  12. [20]

    Geometric algorithms and combinatorial optimization , volume 2 of Algorithms and Combinatorics

    Martin Gr\" o tschel, L\' a szl\' o Lov\' a sz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization , volume 2 of Algorithms and Combinatorics . Springer-Verlag, second edition, 1993

    1993

  13. [21]

    A note on B ourgain's slicing problem

    Qingyang Guan. A note on B ourgain's slicing problem. arXiv preprint arXiv:2412.09075 , 2024

    2024 arXiv

  14. [22]

    Hulda S Haraldsd\' o ttir, Ben Cousins, Ines Thiele, Ronan M T Fleming, and Santosh S. Vempala. CHRR : coordinate hit-and-run with rounding for uniform sampling of constraint-based models. Bioinformatics , 33(11):1741--1743, 01 2017

    2017

  15. [23]

    Logarithmic S obolev inequalities and stochastic I sing models

    Richard Holley and Daniel Stroock. Logarithmic S obolev inequalities and stochastic I sing models. J. Statist. Phys. , 46(5-6):1159--1194, 1987

    1987

  16. [24]

    On the geometry of differential privacy

    Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In S ymposium on T heory of C omputing , pages 705--714. ACM, 2010

    2010

  17. [25]

    He Jia, Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Reducing isotropy and volume to KLS : faster rounding and volume algorithms. arXiv preprint arXiv:2008.02146 , 2024

    2008 arXiv

  18. [26]

    Bourgain's slicing problem and KLS isoperimetry up to polylog

    Bo'az Klartag and Joseph Lehec. Bourgain's slicing problem and KLS isoperimetry up to polylog. Geom. Funct. Anal. , 32(5):1134--1159, 2022

    2022

  19. [27]

    Isoperimetric inequalities in high-dimensional convex sets

    Bo'az Klartag and Joseph Lehec. Isoperimetric inequalities in high-dimensional convex sets. To appear in Bull. Amer. Math. Soc. , 2024

    2024

  20. [28]

    Logarithmic bounds for isoperimetry and slices of convex sets

    Bo'az Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. Ars Inven. Anal. , pages Paper No. 4, 17, 2023

    2023

  21. [29]

    Blocking conductance and mixing in random walks

    Ravi Kannan, L\' a szl\' o Lov\' a sz, and Ravi Montenegro. Blocking conductance and mixing in random walks. Combinatorics, Probability and Computing , 15(4):541--570, 2006

    2006

  22. [30]

    Isoperimetric problems for convex bodies and a localization lemma

    Ravi Kannan, L\' a szl\' o Lov\' a sz, and Mikl\' o s Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom. , 13(3-4):541--559, 1995

    1995

  23. [31]

    Random walks and an O^*(n^5) volume algorithm for convex bodies

    Ravi Kannan, L\' a szl\' o Lov\' a sz, and Mikl\' o s Simonovits. Random walks and an O^*(n^5) volume algorithm for convex bodies. Random Structures Algorithms , 11(1):1--50, 1997

    1997

  24. [32]

    Yunbum Kook, Yin Tat Lee, Ruoqi Shen, and Santosh S. Vempala. Sampling with R iemannian H amiltonian M onte C arlo in a constrained space. In Advances in Neural Information Processing Systems , volume 35, pages 31684--31696, 2022

    2022

  25. [33]

    The strong data processing inequality under the heat flow

    Bo'az Klartag and Or Ordentlich. The strong data processing inequality under the heat flow. IEEE Transactions on Information Theory , 71(5):3317--3333, 2025

    2025

  26. [34]

    Adam Tauman Kalai and Santosh S. Vempala. Simulated annealing for convex optimization. Math. Oper. Res. , 31(2):253--266, 2006

    2006

  27. [35]

    Yunbum Kook and Santosh S. Vempala. Sampling and integration of logconcave functions by algorithmic diffusion. In S ymposium on T heory of C omputing . ACM, 2025

    2025

  28. [36]

    Vempala, and Matthew S

    Yunbum Kook, Santosh S. Vempala, and Matthew S. Zhang. In-and- O ut: algorithmic diffusion for sampling convex bodies. In Advances in Neural Information Processing Systems , volume 37, pages 108354--108388, 2024

    2024

  29. [37]

    Yunbum Kook and Matthew S. Zhang. R\' e nyi-infinity constrained sampling with d^3 membership queries. In Symposium on Discrete Algorithms , pages 5278--5306. SIAM, 2025

    2025

  30. [38]

    A simple analytic proof of an inequality by P

    Michel Ledoux. A simple analytic proof of an inequality by P . B user. Proc. Amer. Math. Soc. , 121(3):951--959, 1994

    1994

  31. [39]

    Spectral gap, logarithmic S obolev constant, and geometric bounds

    Michel Ledoux. Spectral gap, logarithmic S obolev constant, and geometric bounds. In Surveys in differential geometry. V ol. IX , volume 9 of Surv. Differ. Geom. , pages 219--240. Int. Press, Somerville, MA, 2004

    2004

  32. [40]

    Faster mixing via average conductance

    L\' a szl\' o Lov\' a sz and Ravi Kannan. Faster mixing via average conductance. In Symposium on Theory of Computing , pages 282--287. ACM, 1999

    1999

  33. [41]

    How to compute the volume? Jber

    L\' a szl\' o Lov\' a sz. How to compute the volume? Jber. d. Dt. Math.-Verein, Jubil \"a umstagung , pages 138--151, 1990

    1990

  34. [42]

    Hit-and-run mixes fast

    L\' a szl\' o Lov\' a sz. Hit-and-run mixes fast. Mathematical Programming , 86(3):443--461, 1999

    1999

  35. [43]

    The mixing rate of M arkov chains, an isoperimetric inequality, and computing the volume

    L\' a szl\' o Lov\' a sz and Mikl\' o s Simonovits. The mixing rate of M arkov chains, an isoperimetric inequality, and computing the volume. In S ymposium on F oundations of C omputer S cience , pages 346--354. IEEE, 1990

    1990

  36. [44]

    Random walks in a convex body and an improved volume algorithm

    L\' a szl\' o Lov\' a sz and Mikl\' o s Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms , 4(4):359--412, 1993

    1993

  37. [45]

    Structured logconcave sampling with a restricted G aussian oracle

    Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted G aussian oracle. In Conference on Learning Theory , volume 134, pages 2993--3050. PMLR, 2021

    2021

  38. [46]

    L\' a szl\' o Lov\' a sz and Santosh S. Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Symposium on Foundations of Computer Science , pages 57--68. IEEE, 2006

    2006

  39. [47]

    L\' a szl\' o Lov\' a sz and Santosh S. Vempala. Hit-and-run from a corner. SIAM Journal on Computing , 35(4):985--1005, 2006

    2006

  40. [48]

    L\' a szl\' o Lov\' a sz and Santosh S. Vempala. Simulated annealing in convex bodies and an O^*(n^4) volume algorithm. J. Comput. System Sci. , 72(2):392--417, 2006

    2006

  41. [49]

    L\' a szl\' o Lov\' a sz and Santosh S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms , 30(3):307--358, 2007

    2007

  42. [50]

    Yin Tat Lee and Santosh S. Vempala. Eldan's stochastic localization and the KLS conjecture: isoperimetry, concentration and mixing. Ann. of Math. (2) , 199(3):1043--1092, 2024

    2024

  43. [51]

    Isoperimetric and concentration inequalities: Equivalence under curvature lower bound

    Emanuel Milman. Isoperimetric and concentration inequalities: Equivalence under curvature lower bound. Duke Mathematical Journal , 154(2), August 2010

    2010

  44. [52]

    R\' e nyi differential privacy

    Ilya Mironov. R\' e nyi differential privacy. In Computer Security Foundations Symposium , pages 263--275. IEEE, 2017

    2017

  45. [53]

    Mechanism design via differential privacy

    Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Symposium on Foundations of Computer Science , pages 94--103. IEEE, 2007

    2007

  46. [54]

    Payne and Hans F

    Lawrence E. Payne and Hans F. Weinberger. An optimal P oincar\' e inequality for convex domains. Arch. Rational Mech. Anal. , 5:286--292 (1960), 1960

    1960

  47. [55]

    Robert L. Smith. Efficient M onte C arlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. , 32(6):1296--1308, 1984

    1984

  48. [56]

    A community-driven global reconstruction of human metabolism

    Ines Thiele et al. A community-driven global reconstruction of human metabolism. Nature Biotechnology , 31(5):419--425, mar 2013

    2013

  49. [57]

    R\' e nyi divergence and K ullback- L eibler divergence

    Tim van Erven and Peter Harremo \"e s. R\' e nyi divergence and K ullback- L eibler divergence. IEEE Trans. Inform. Theory , 60(7):3797--3820, 2014

    2014

  50. [58]

    Mixing time of the proximal sampler in relative F isher information via strong data processing inequality

    Andre Wibisono. Mixing time of the proximal sampler in relative F isher information via strong data processing inequality. arXiv preprint arXiv:2502.05623 , 2025

    2025 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.