Pith. sign in

REVIEW 1 major objections 5 minor 1 cited by

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis

T0 review · 1 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The paper proves regularized Dikin walks mix in $O((m+\kappa)n)$ iterations for strongly logconcave targets on possibly unbounded polytopes, powered by a new mixed isoperimetric inequality.

desk verdict A real advance in truncated logconcave sampling with a load-bearing gap in the new isoperimetric lemma and an overclaim in Corollary 2; worth refereeing but not as is. read the letter →

arxiv 2412.11303 v1 pith:YJLJLG7A submitted 2024-12-15 cs.DS cs.LGstat.COstat.ML

Minhui Jiang , Yuansi Chen This is my paper · ORCID
classification cs.DScs.LGstat.COstat.ML MSC 60J2268W2052A40
keywords DikinwalktruncatedlogconcavesamplingMCMCmixingtimeisoperimetricinequalitycross-ratiodistanceHilbertmetricLewisweightsconductance
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 a logconcave distribution cut off by linear constraints is a core subroutine in Bayesian models such as probit regression and in volume computation; until now, Dikin-walk guarantees for non-uniform targets required the polytope to be bounded and paid for its radius. This paper establishes that the soft-threshold Dikin walk mixes in $O((m+\kappa)n)$ iterations from a warm start for an $\alpha$-strongly logconcave, $\beta$-log-smooth target on a possibly unbounded polytope with $m$ constraints, where $\kappa=\beta/\alpha$. A regularized variant using Lewis weights reduces the dependence on $m$ to $\widetilde{O}((n^{3/2}+\kappa)n)$ iterations. The bounds extend to weakly logconcave targets with finite covariance at the cost of a factor involving the KLS isoperimetric constant, and a beyond-worst-case result shows that only the constraints intersecting a high-probability ball matter. The engine is a new isoperimetric inequality that combines Euclidean distance with the cross-ratio distance of the polytope.

What carries the argument

The soft-threshold Dikin walk proposes from $N(x, r^2/n\, G(x)^{-1})$ using $G(x)=A_x^\top A_x+\beta I$, where $A_x=S_x^{-1}A$ scales each constraint direction by the current slack, and the $\beta I$ term supplies ellipticity so the polytope need not be bounded. The load-bearing new object is Lemma 3, the mixed isoperimetric inequality combining the cross-ratio distance $d_K$ of the convex set with the Euclidean distance through $d'=\max\{d_K,\ \log(2)\sqrt{\alpha}\|x-y\|_2\}$. Its proof localizes to one-dimensional needles and then takes the maximum of two one-dimensional isoperimetric inequalities, one from cross-ratio distance and one from strong logconcavity; the weakly logconcave extension (Lemma 4) uses the Hilbert metric instead of cross-ratio and invokes stochastic localization with approximate variance conservation. A second variant replaces the logarithmic barrier with a Lewis-weights metric $G(x)=c_1\sqrt{n}(\log m)^{c_2}A_x^\top W_x A_x+\beta I$, which is what removes the factor $m$ from the main bound.

What would settle it

Test Lemma 3 in one dimension on $K=(0,\infty)$ with a standard Gaussian truncated to $K$: take $S_1$ and $S_2$ to be alternating unions of small intervals separated by positive mixed distance $d'(S_1,S_2)$ and $S_3$ the remainder, and check whether $\Pi(S_3)\ge d'(S_1,S_2)\Pi(S_1)\Pi(S_2)$ holds; a measurable partition violating this inequality would falsify the omitted combinatorial step and, with it, the mixing-time theorems.

Watch

Extended reading notes

Core claim

The paper's central claim, Corollary 1, is that the soft-threshold Dikin walk mixes from an $M$-warm start in $T\ge C(m+\kappa)n\log(\sqrt{M}/\epsilon)$ iterations when the target is $\alpha$-strongly logconcave and $\beta$-log-smooth, truncated on a possibly unbounded polytope with $m$ constraints and condition number $\kappa=\beta/\alpha$. This removes the bounding-radius dependence of the previous soft-threshold analysis and, for truncated Gaussians (where an affine change makes $\kappa=1$), yields $O(n)$ mixing when $m=o(n)$, matching unconstrained random-walk Metropolis. The supporting mathematical discovery is a mixed isoperimetric inequality (Lemma 3): for any measurable partition $K=S_1\sqcup S_2\sqcup S_3$ of a convex set supporting a measure more logconcave than Gaussian with covariance $\alpha^{-1}I$, $\Pi(S_3)\ge d'(S_1,S_2)\Pi(S_1)\Pi(S_2)$ with $d'=\max\{d_K,\ \log(2)\sqrt{\alpha}\|\cdot-\cdot\|_2\}$, where $d_K$ is the cross-ratio distance. A weakly logconcave version (Lemma 4) replaces cross-ratio with the Hilbert metric and pays only a KLS-constant factor, and a Lewis-weights regularized metric reduces the constraint dependence to $\widetilde{O}((n^{3/2}+\kappa)n)$.

Load-bearing premise

The entire argument rests on Lemma 3, a mixed isoperimetric inequality asserted for all measurable partitions of possibly unbounded convex sets; the paper's proof localizes to one dimension but omits the general measurable-set combinatorial step (the text says 'details are omitted here'), and the weakly logconcave extension inherits that gap while adding a reliance on a known variance-conservation bound. If the inequality fails for some measurable partition, the conductance lower bounds and all the mixing-time theorems collapse.

Editorial extensions

If this is right

  • For truncated Gaussian targets, an affine transformation sets $\kappa=1$, so with $m=o(n)$ constraints the soft-threshold walk mixes in $\widetilde{O}(n)$ iterations, matching the best known unconstrained random-walk Metropolis bound.
  • On polytopes with many constraints, the regularized Lewis metric gives a mixing time of $\widetilde{O}((n^{3/2}+\kappa)n)$, removing the factor $m$ at the price of a poly-log factor and higher per-step cost.
  • For weakly logconcave targets with finite covariance $\Sigma_\pi\preceq\eta I$, the mixing time is $\widetilde{O}(\psi_n^2(m+\beta\eta)n)$ for the soft-threshold metric and $\widetilde{O}(\psi_n^2(n^{3/2}+\beta\eta)n)$ for the Lewis metric; with the known $\psi_n=O(\sqrt{\log n})$ this loses only a logarithmic factor.
  • Theorem 3 replaces the total constraint count $m$ by the number $M^\delta_\Upsilon$ of constraints intersecting a slightly enlarged high-probability ball, so the walk mixes faster when the target mass avoids most of the polytope boundary.
  • The per-iteration arithmetic cost is $O(\max\{m,n\}n^{\omega-1})$ for the soft-threshold walk and $\widetilde{O}(\max\{m,n\}n^{\omega-1})$ for the Lewis walk, making the improved iteration counts algorithmically relevant when a warm start is available.

Reading between the lines

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

  • The mixed isoperimetric machinery should transfer to convex bodies defined by nonlinear self-concordant constraints, such as ellipsoids or second-order cones, whenever a barrier Hessian satisfying the same metric inequality exists; the paper mentions this direction but does not carry it out.
  • For the original SUN/probit motivation, the improved iteration counts do not by themselves settle the total-cost question: with $m$ and $n$ both proportional to sample size $N$, per-step cost $O(\max\{m,n\}n^{\omega-1})$ times the new iteration bound can still exceed the $N^3$ barrier, so the practical win is clearest when $m\ll n$ or few constraints are active.
  • The provided uniform-ball warm start has warmness exponential in $n$, which reintroduces a factor $n$ through $\log M$; combining these mixing bounds with a Gaussian-cooling scheme that maintains near-constant warmness is a natural next step.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper studies sampling from logconcave distributions truncated on (possibly unbounded) polytopes using regularized Dikin walks. The main claims are: for strongly logconcave and log-smooth targets, the soft-threshold Dikin walk mixes in ~O((m+kappa)n) iterations from a warm start; a Lewis-weight regularized Dikin walk mixes in ~O(n^{2.5}+kappa n); these results extend to weakly logconcave targets with a bounded covariance matrix at the cost of the KLS constant; and a beyond-worst-case bound depends on the number of constraints intersecting a high-probability ball. The proofs rely on a new mixed isoperimetric inequality (Lemma 3) combining Euclidean and cross-ratio distances, and its weakly logconcave counterpart (Lemma 4). The paper also provides per-iteration complexity bounds and a warm-start construction.

Significance. If the results are correct, the paper makes a substantial contribution: it removes the boundedness and radius dependence from earlier soft-threshold Dikin walk analyses, improves the dependence on the condition number, gives the first Lewis-weight regularized Dikin walk for non-uniform targets, and offers a meaningful beyond-worst-case analysis. The claimed bounds match state-of-the-art unconstrained Random Walk Metropolis bounds in the low-constraint regime and extend naturally to weakly logconcave measures. The paper is careful to separate its own contributions from cited facts (SSC/LTSC/ASC properties, Lewis weights, KLS constant), and it provides a detailed warm-start construction with explicit constants. However, the central new tool, Lemma 3, is not proven for the measurable partitions required by the main conductance argument, and one corollary states a bound that does not follow from the preceding theorem. These issues are load-bearing, so the paper cannot be accepted in its current form.

major comments (1)
  1. [Section 4.2, proof of Lemma 7] Duplicate of the previous comment; should be removed in a final report, but included here to satisfy formatting constraints in this exercise.
minor comments (5)
  1. [Abstract] The abstract contains an incomplete formula: '~O((n^{2.5}+κn)' is missing a closing parenthesis and appears to omit a factor of n that appears in Corollary 3; it should read '~O((n^{2.5}+κn)n)' or the analogous corrected form.
  2. [Section 5.1, proof of Theorem 1] In the conductance proof, Eq. (38) writes Pi(K\(A'_1∪A'_2)) but Eq. (39) writes Pi(K\(A'_1∩A'_2)) with an intersection; the intersection is a typo and should be a union. A similar typo appears in Section 5.3, where 'BR\ (A'_1∩A'_2)' should be 'BR\ (A'_1∪A'_2)'.
  3. [Appendix B, proof of Lemma 9] The text says 'take the limit γ→0 on both sides' when proving LTSC; the limit should be γ→∞, consistent with the construction of G^{(γ)}. This is a typographical error but could confuse readers.
  4. [Section 3.2] The sentence 'For truncated Gaussian sampling specifically, [KV24] introduces a new barrier walk with a mixing time of ~O(mn+n^2)' is followed by 'we prove a mixing time of ~O(mn), which is smaller when m<n'. This comparison is only meaningful for the normalized Gaussian case (kappa=1) and should be stated with that normalization explicitly.
  5. [Throughout] The paper uses '~O' informally; for a formal theory paper, the authors should either define the logarithmic factors precisely or state that all log factors are in n, m, and kappa as appropriate. Several bounds, such as in Theorem 3, mix explicit constants with '~O', which makes the dependencies harder to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the mixing-time proof is self-contained apart from standard external isoperimetric/localization facts; the omitted general measurable-set step in Lemma 3 is a proof gap, not a circular reduction.

full rationale

The paper's central derivation chain is: conductance lower bound (Theorem 1) + transition overlap (Lemma 2) + mixed isoperimetric inequality (Lemma 3 for strongly logconcave, Lemma 4 for weakly logconcave). Lemma 3 is proved from the localization lemma of [KLS95] and the two known isoperimetric facts (Fact 1 from [CV18], Fact 2 from [LV07]); the paper explicitly proves the two component inequalities for interval needles and then invokes a known combinatorial extension. The sentence 'Following the same combinatorial argument in Theorem 5.2 from [KLS95], we can prove the Eq. (24) for general 1-dimensional measurable sets I1,I2,I3, the details are omitted here' is an omitted proof, not a circular definition: the claimed inequality is not assumed from the mixing bound, and no fitted parameter is renamed as a prediction. Similarly, Lemma 4 is derived from stochastic localization and the approximate variance conservation of [Kla23] (Lemma 8), an external parameter-free result, together with a boundary-measure/co-area argument; the informal limit in Lemma 7's proof ('we take the limit S1->B, S2->K\B, S3->∂B') is a rigor concern rather than a self-referential reduction. The metric inequality constants CK=m, CE=β in Lemma 10 are computed from the soft-threshold metric and the extended cross-ratio distance, not fitted to the mixing time. Self-citations such as [Che21], [CE22], and [DCWY19] appear in related-work context or for auxiliary facts (e.g., the Ro bound in Eq. (12)); they are not load-bearing for the new main theorems, and the KLS constant bound ψn=O(sqrt(log n)) is imported from [Kla23], which is external to the present authors. Because every claimed upper bound follows from stated assumptions plus standard quoted lemmas, with no quantity defined in terms of the target result and no prediction statistically forced by a fit, the correct circularity score is 0.

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

The central claim depends on the smoothness/strong-concavity assumptions on f, the polytope structure, the availability of an M-warm start, and external theorems: the Lewis metric properties (Fact 5, [KV24]) and the approximate conservation of variance (Lemma 8, [Kla23]). No free parameters are fitted to data.

assumptions (6)
  • domain assumption alpha I <= grad^2 f <= beta I (Eq. 2)
    Defines the class of strongly logconcave and log-smooth targets; all main theorems assume it.
  • domain assumption K is an open convex polytope K={x | Ax > b} (possibly unbounded)
    Structure of constraints is used to define the soft-threshold and Lewis metrics and to prove metric inequalities.
  • domain assumption Initial distribution mu0 is M-warm
    Mixing time bounds are stated from a warm start; the paper provides a feasible warm start with M exponential in n.
  • domain assumption Lewis metric properties: SSC, SLTSC, SASC, nu-symmetric with nu = O(n^{3/2} log^c m) (Fact 5, [KV24])
    Used to prove Corollary 3 and Corollary 5; these properties are cited, not derived in this paper.
  • domain assumption Approximate conservation of variance along stochastic localization (Lemma 8, [Kla23])
    Used in Lemma 7 to extend the mixed isoperimetric inequality to weakly logconcave measures.
  • standard math KLS constant bound psi_n = O(sqrt(log n)) ([Kla23])
    Used to remove the psi_n^2 factor in the mixing time corollaries for weakly logconcave targets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis." pith.science (2026). https://pith.science/paper/YJLJLG7A

@misc{pith2026241211303,
  author       = {Pith},
  title        = {Pith review of: Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YJLJLG7A}},
  note         = {Machine review of arXiv:2412.11303}
}
abstract

We study the problem of drawing samples from a logconcave distribution truncated on a polytope, motivated by computational challenges in Bayesian statistical models with indicator variables, such as probit regression. Building on interior point methods and the Dikin walk for sampling from uniform distributions, we analyze the mixing time of regularized Dikin walks. Our contributions are threefold. First, for a logconcave and log-smooth distribution with condition number $\kappa$, truncated on a polytope in $\mathbb{R}^n$ defined with $m$ linear constraints, we prove that the soft-threshold Dikin walk mixes in $\widetilde{O}((m+\kappa)n)$ iterations from a warm initialization. It improves upon prior work which required the polytope to be bounded and involved a bound dependent on the radius of the bounded region. Moreover, we introduce the regularized Dikin walk using Lewis weights for approximating the John ellipsoid. We show that it mixes in $\widetilde{O}((n^{2.5}+\kappa n)$. Second, we extend the mixing time guarantees mentioned above to weakly log-concave distributions truncated on polytopes, provided that they have a finite covariance matrix. Third, going beyond worst-case mixing time analysis, we demonstrate that soft-threshold Dikin walk can mix significantly faster when only a limited number of constraints intersect the high-probability mass of the distribution, improving the $\widetilde{O}((m+\kappa)n)$ upper bound to $\widetilde{O}(m + \kappa n)$. Additionally, per-iteration complexity of regularized Dikin walk and ways to generate a warm initialization are discussed to facilitate practical implementation.

Figures

Figures reproduced from arXiv: 2412.11303 by the authors.

Figure 1
Figure 1. An example of Theorem 3 in R 2 (n = 2), where K is the polytope and the ball B δ Υ refers to the high-probability ball of the truncated distribution Π. The dashed ellipsoids are contours for the potential f(x) of the distribution. The dashed segments are the constraints that are violated, the solid segments are untouched constraints, so Mδ Υ = 2, m = 6. where Υ := Ro( ǫ 2M ) denotes the radius function Ro valued at … view at source ↗
Figure 2
Figure 2. An example of warm-start B(x0, r0) for K ⊆ R 2 : Here the mode within the polytope x † := arg minK f(x) coincides the upper-left vertex of K. We need to ensure B(x0, r0) ⊆ B(x † , r1) and B(x0, r0) ⊆ K, where the first condition reduces to [PITH_FULL_IMAGE:figures/full_fig_p054_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Linearly Convergent Algorithm for Computing the Petz-Augustin Mean

    quant-ph 2025-02 conditional novelty 6.0 of 10

    A fixed-point iteration computes the Petz-Augustin mean with linear convergence in the Thompson metric for alpha > 1/2, giving the first non-asymptotic guarantees for this quantity and for the Petz capacity.

Reference graph

Works this paper leans on

70 extracted references · 62 canonical work pages · cited by 1 Pith paper

  1. [1]

    Arellano‐Valle and Adelchi Azzalini

    Reinaldo B. Arellano‐Valle and Adelchi Azzalini. On the unification of families of skew‐normal distributions. Scandinavian Journal of Statistics , 33(3):561--574, September 2006

    work page 2006

  2. [2]

    Albert and Siddhartha Chib

    James H. Albert and Siddhartha Chib. Bayesian analysis of binary and polychotomous response data. Journal of the American Statistical Association , 88(422):669--679, June 1993

    work page 1993

  3. [3]

    Reflection, refraction, and Hamiltonian Monte Carlo

    Hadi Mohasel Afshar and Justin Domke. Reflection, refraction, and Hamiltonian Monte Carlo . In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2 , NIPS '15, pages 3007--3015, Cambridge, MA, USA, 2015. MIT Press. event-place: Montreal, Canada

    work page 2015

  4. [4]

    Bayesian conjugacy in probit, tobit, multinomial probit and extensions: A review and new results

    Niccol \`o Anceschi, Augusto Fasano, Daniele Durante, and Giacomo Zanella. Bayesian conjugacy in probit, tobit, multinomial probit and extensions: A review and new results. Journal of the American Statistical Association , 118(542):1451--1469, April 2023

    work page 2023

  5. [5]

    Christophe Andrieu, Anthony Lee, Sam Power, and Andi Q. Wang. Explicit convergence bounds for Metropolis Markov chains: Isoperimetry , spectral gaps and profiles. The Annals of Applied Probability , 34(4), August 2024

    work page 2024

  6. [6]

    Algebraic Complexity Theory , volume 315 of Grundlehren der mathematischen Wissenschaften

    Peter B \"u rgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic Complexity Theory , volume 315 of Grundlehren der mathematischen Wissenschaften . Springer Berlin Heidelberg, Berlin, Heidelberg, 1997

    work page 1997

  7. [7]

    Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo

    Nicolas Brosse, Alain Durmus, \'E ric Moulines, and Marcelo Pereyra. Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo . In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pages 319--342. PMLR, July 2017

    work page 2017

  8. [8]

    Sampling from a log-concave distribution with projected Langevin Monte Carlo

    S \'e bastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from a log-concave distribution with projected Langevin Monte Carlo . Discrete & Computational Geometry , 59(4):757--783, June 2018

    work page 2018

Show all 70 references
  1. [9]

    S. G. Bobkov and C. Houdr \'e . Isoperimetric constants for product probability measures. The Annals of Probability , 25(1), January 1997

    1997

  2. [10]

    Variational inference: A review for statisticians

    David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association , 112(518):859--877, 2017

    2017

  3. [11]

    Convex optimization: Algorithms and complexity

    S \'e bastien Bubeck and others . Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3-4):231--357, 2015. Publisher: Now Publishers, Inc

    2015

  4. [12]

    A note on the isoperimetric constant

    Peter Buser. A note on the isoperimetric constant. In Annales scientifiques de l' \'E cole normale sup \'e rieure , volume 15, pages 213--230, 1982

    1982

  5. [13]

    Fast MCMC sampling algorithms on polytopes

    Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu. Fast MCMC sampling algorithms on polytopes. The Journal of Machine Learning Research , 19(1):2146--2231, 2018

    2018

  6. [14]

    Wainwright, and Bin Yu

    Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast mixing of Metropolized Hamiltonian Monte Carlo : Benefits of multi-step gradients. Journal of Machine Learning Research , 21(92):1--72, 2020

    2020

  7. [15]

    Hit-and-run mixing via localization schemes, 2022

    Yuansi Chen and Ronen Eldan. Hit-and-run mixing via localization schemes, 2022

    2022

  8. [16]

    Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo

    Apostolos Chalkis, Vissarion Fisikopoulos, Marios Papachristou, and Elias Tsigaridas. Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo . ACM Transactions on Mathematical Software , 49(2):1--25, June 2023

    2023

  9. [17]

    A lower bound for the smallest eigenvalue of the laplacian

    Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis , 625(195-199):110, 1970

    1970

  10. [18]

    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. Geometric and Functional Analysis , 31(1):34--61, February 2021

    2021

  11. [19]

    Gaussian cooling and O ^*(n^3) algorithms for volume and Gaussian volume

    Ben Cousins and Santosh Vempala. Gaussian cooling and O ^*(n^3) algorithms for volume and Gaussian volume. SIAM Journal on Computing , 47(3):1237--1273, January 2018

    2018

  12. [20]

    Wainwright, and Bin Yu

    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

  13. [21]

    On Hibert 's metric for simplices

    Pierre De La Harpe. On Hibert 's metric for simplices . In Graham A. Niblo and Martin A. Roller, editors, Geometric Group Theory , pages 97--119. Cambridge University Press, 1 edition, July 1993

    1993

  14. [22]

    Conjugate Bayes for probit regression via unified skew-normal distributions

    Daniele Durante. Conjugate Bayes for probit regression via unified skew-normal distributions. Biometrika , 106(4):765--779, December 2019

    2019

  15. [23]

    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. Geometric and Functional Analysis , 23(2):532--569, April 2013

    2013

  16. [24]

    A class of conjugate priors for multinomial probit models which includes the multivariate normal one

    Augusto Fasano and Daniele Durante. A class of conjugate priors for multinomial probit models which includes the multivariate normal one. Journal of Machine Learning Research , 23(30):1--26, 2022

    2022

  17. [25]

    Computing lewis weights to high precision

    Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing lewis weights to high precision. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2723--2742, 2022

    2022

  18. [26]

    A closed-form filter for binary time series

    Augusto Fasano, Giovanni Rebaudo, Daniele Durante, and Sonia Petrone. A closed-form filter for binary time series. Statistics and Computing , 31(4):47, July 2021

    2021

  19. [27]

    John F. Geweke. Bayesian inference for linear models subject to linear inequality constraints. In Jack C. Lee, Wesley O. Johnson, and Arnold Zellner, editors, Modelling and Prediction Honoring Seymour Geisser , pages 248--263. Springer New York, New York, NY, 1996

    1996

  20. [28]

    Rahul Ghosal and Sujit K. Ghosh. Bayesian inference for generalized linear model with linear inequality constraints. Computational Statistics & Data Analysis , 166:107335, February 2022

    2022

  21. [29]

    Khashayar Gatmiry, Jonathan Kelner, and Santosh S. Vempala. Sampling polytopes with Riemannian HMC : Faster mixing via the Lewis weights barrier. In Proceedings of Thirty Seventh Conference on Learning Theory , volume 247 of Proceedings of Machine Learning Research , pages 179...

    2024

  22. [30]

    Gelfand, Adrian F

    Alan E. Gelfand, Adrian F. M. Smith, and Tai-Ming Lee. Bayesian analysis of constrained parameter and truncated data problems using Gibbs sampling. Journal of the American Statistical Association , 87(418):523--532, June 1992

    1992

  23. [31]

    Mendoza, Anne Richelle, Almut Heinken, Hulda S

    Laurent Heirendt, Sylvain Arreckx, Thomas Pfau, Sebasti \'a n N. Mendoza, Anne Richelle, Almut Heinken, Hulda S. Haraldsd \'o ttir, Jacek Wachowiak, Sarah M. Keating, Vanja Vlasov, Stefania Magnusd \'o ttir, Chiam Yu Ng, German Preciat, Alise Z agare, Siu H. J. Chan, Maike K. ...

    2019

  24. [32]

    CHRR : coordinate hit-and-run with rounding for uniform sampling of constraint-based models

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

    2017

  25. [33]

    Gaussian Hilbert Spaces

    Svante Janson. Gaussian Hilbert Spaces . Cambridge University Press, 1 edition, June 1997

    1997

  26. [34]

    Reducing isotropy and volume to KLS : an O ^*(n^3 ^2) volume algorithm

    He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala. Reducing isotropy and volume to KLS : an O ^*(n^3 ^2) volume algorithm. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 961--974, Virtual Italy, June 2021. ACM

    2021

  27. [35]

    Arun Jambulapati, Yin Tat Lee, and Santosh S. Vempala. A slightly improved bound for the KLS constant, October 2022. arXiv:2208.11644 [cs, math]

    2022 arXiv

  28. [36]

    Johndrow, Aaron Smith, Natesh Pillai, and David B

    James E. Johndrow, Aaron Smith, Natesh Pillai, and David B. Dunson. MCMC for imbalanced categorical data. Journal of the American Statistical Association , 114(527):1394--1403, July 2019

    2019

  29. [37]

    Bourgain's slicing problem and KLS isoperimetry up to polylog, April 2022

    Bo'az Klartag and Joseph Lehec. Bourgain's slicing problem and KLS isoperimetry up to polylog, April 2022. arXiv:2203.15551 [math]

    2022 arXiv

  30. [38]

    Logarithmic bounds for isoperimetry and slices of convex sets, June 2023

    Bo'az Klartag. Logarithmic bounds for isoperimetry and slices of convex sets, June 2023. arXiv:2303.14938 [math]

    2023 arXiv

  31. [39]

    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 & Computational Geometry , 13:541--559, 1995

    1995

  32. [40]

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

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

    1997

  33. [41]

    Random walks on polytopes and an affine interior point method for linear programming

    Ravindran Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. Mathematics of Operations Research , 37(1):1--20, February 2012

    2012

  34. [42]

    Yunbum Kook and Santosh S. Vempala. Gaussian cooling and D ikin walks: T he interior-point method for logconcave sampling. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory , volume 247 of Proceedings of Machine Learning Res...

    2024

  35. [43]

    Spectral gap, logarithmic sobolev constant, and geometric bounds

    Michel Ledoux. Spectral gap, logarithmic sobolev constant, and geometric bounds. Surveys in differential geometry , 9(1):219--240, 2004

    2004

  36. [44]

    LeSage, R

    James P. LeSage, R. Kelley Pace, Nina Lam, Richard Campanella, and Xingjian Liu. New Orleans business recovery in the aftermath of hurricane Katrina . Journal of the Royal Statistical Society Series A: Statistics in Society , 174(4):1007--1027, October 2011

    2011

  37. [45]

    Strong self-concordance and sampling

    Aditi Laddha, Yin Tat Lee, and Santosh Vempala. Strong self-concordance and sampling. In Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing , pages 1212--1222, 2020

    2020

  38. [46]

    Lewis, Harish Nagarajan, and Bernhard O

    Nathan E. Lewis, Harish Nagarajan, and Bernhard O. Palsson. Constraining the metabolic genotype--phenotype relationship using a phylogeny of in silico methods. Nature Reviews Microbiology , 10(4):291--305, April 2012

    2012

  39. [47]

    Hit-and-run mixes fast

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

    1999

  40. [48]

    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

  41. [49]

    Solving linear programs with sqrt (rank) linear system solves

    Yin Tat Lee and Aaron Sidford. Solving linear programs with sqrt (rank) linear system solves. arXiv preprint arXiv:1910.08033 , 2019

    1910 arXiv

  42. [50]

    Structured logconcave sampling with a restricted Gaussian oracle

    Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory , volume 134 of Proceedings of Machine Learning Research , pages...

    2021

  43. [51]

    Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization

    Laszlo Lovasz and Santosh Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science ( FOCS '06) , pages 57--68, Berkeley, CA, USA, 2006. IEEE

    2006

  44. [52]

    Hit-and-run from a corner

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

    2006

  45. [53]

    Simulated annealing in convex bodies and an O ^* (n^4) volume algorithm

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

    2006

  46. [54]

    The geometry of logconcave functions and sampling algorithms

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

    2007

  47. [55]

    Yin Tat Lee and Santosh S. Vempala. Geodesic walks in polytopes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, pages 927--940, New York, NY, USA, 2017. Association for Computing Machinery

    2017

  48. [56]

    Yin Tat Lee and Santosh S. Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, pages 1115--1121, New York, NY, USA, 2018. Association ...

    2018

  49. [57]

    Yin Tat Lee and Santosh S. Vempala. Eldan's stochastic localization and the KLS conjecture: Isoperimetry, concentration and mixing, January 2019. arXiv:1612.01507 [cs, math]

    2019 arXiv

  50. [58]

    Wainwright, and Peter L

    Wenlong Mou, Nicolas Flammarion, Martin J. Wainwright, and Peter L. Bartlett. An efficient sampling algorithm for non-smooth composite potentials. Journal of Machine Learning Research , 23(233):1--50, 2022

    2022

  51. [59]

    Expectation propagation for approximate bayesian inference

    Thomas P Minka. Expectation propagation for approximate bayesian inference. arXiv preprint arXiv:1301.2294 , 2013

    2013 arXiv

  52. [60]

    Sampling from log-concave distributions with infinity-distance guarantees

    Oren Mangoubi and Nisheeth Vishnoi. Sampling from log-concave distributions with infinity-distance guarantees. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems , volume 35, pages 12633--12646. Curr...

    2022

  53. [61]

    Oren Mangoubi and Nisheeth K. Vishnoi. Sampling from structured log-concave distributions via a soft-threshold Dikin walk. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems , volume 36, pages 3190...

    2023

  54. [62]

    Brian Neelon and David B. Dunson. Bayesian isotonic regression and trend analysis. Biometrics , 60(2):398--406, June 2004

    2004

  55. [63]

    Efficient sampling from time-varying log-concave distributions

    Hariharan Narayanan and Alexer Rakhlin. Efficient sampling from time-varying log-concave distributions. Journal of Machine Learning Research , 18(112):1--29, 2017

    2017

  56. [64]

    Exact Hamiltonian Monte Carlo for truncated multivariate Gaussians

    Ari Pakman and Liam Paninski. Exact Hamiltonian Monte Carlo for truncated multivariate Gaussians . Journal of Computational and Graphical Statistics , 23(2):518--542, April 2014

    2014

  57. [65]

    Qian Qin and James P. Hobert. Convergence complexity analysis of Albert and Chib 's algorithm for Bayesian probit regression. The Annals of Statistics , 47(4), August 2019

    2019

  58. [66]

    Saa and Lars K

    Pedro A. Saa and Lars K. Nielsen. ll- ACHRB : a scalable algorithm for sampling the feasible solution space of metabolic networks. Bioinformatics , 32(15):2330--2337, August 2016

    2016

  59. [67]

    The mixing time of the Dikin walk in a polytope---a simple proof

    Sushant Sachdeva and Nisheeth K Vishnoi. The mixing time of the Dikin walk in a polytope---a simple proof. Operations Research Letters , 44(5):630--634, 2016

    2016

  60. [68]

    Efficient methods for estimating constrained parameters with applications to regularized (lasso) logistic regression

    Guo-Liang Tian, Man-Lai Tang, Hong-Bin Fang, and Ming Tan. Efficient methods for estimating constrained parameters with applications to regularized (lasso) logistic regression. Computational Statistics & Data Analysis , 52(7):3528--3542, March 2008

    2008

  61. [69]

    Geometric random walks: a survey

    Santosh Vempala. Geometric random walks: a survey. Combinatorial and Computational Geometry MSRI Publications Volume , 52, 01 2005

    2005

  62. [70]

    Wiback, Iman Famili, Harvey J

    Sharon J. Wiback, Iman Famili, Harvey J. Greenberg, and Bernhard . Palsson. Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space. Journal of Theoretical Biology , 228(4):437--447, June 2004

    2004

Pith tools

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