Pith. sign in

REVIEW 1 major objections 3 minor 204 references

Dikin walks on polytopes now mix in d^2.25 iterations, improving the previous d^2.5 bound.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 03:16 UTC pith:YUXVEBRV

load-bearing objection The claimed d^{2.25} mixing bound relies on a factor-of-d error in Lemma 3.3; the proof as written recovers only the old d^{2.5}. the 1 major comments →

arxiv 2607.13943 v1 pith:YUXVEBRV submitted 2026-07-15 cs.DS cs.LGmath.OC

Beyond the d^(2.5)-mixing bound for Dikin walks on polytopes

Yunbum Kook This is my paper
classification cs.DS cs.LGmath.OC MSC 68W2060J2090C25
keywords average self-concordanceDikin walkLee-Sidford metricLewis weightspolytope samplingMarkov chain mixinginterior-point methodsWiener chaos
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper improves the warm-start mixing time of the Dikin walk for sampling from a polytope from O~(d^{2.5}) to O~(d^{2.25}) iterations, breaking a bound that had stood for about a decade and moving closer to the conjectured d^2. The engine is a sharper average self-concordance estimate for the Lee–Sidford metric: the unscaled metric now enjoys the required property at radius Θ~(d^{-1/8}) rather than the previously implicit d^{-1/4}, allowing the metric to be scaled by d^{1/4} instead of d^{1/2}. The improved estimate follows from a new higher-order calculus for Lewis weights, built from a moving orthonormal frame and a selective expansion of the few bottleneck terms, with the resulting Gaussian polynomials controlled by Wiener-chaos decompositions. A corollary improves the cold-start (no warm start) complexity from d^{23/8} to d^{41/16}.

Core claim

The paper's central claim is that the unscaled Lee–Sidford metric satisfies average self-concordance at radius Θ~(d^{-1/8}): for any base point in the polytope, a random Dikin proposal at that radius changes the squared local length by at most 2εr^2/d with probability at least 1−ε. Scaling a metric by L multiplies the symmetry parameter by L while converting a radius-r proposal into a radius-r/√L proposal for the unscaled metric, so this ASC radius translates into constant-radius ASC for the d^{1/4}-scaled metric with symmetry parameter O~(d^{5/4}). Plugging these into the standard Dikin-walk mixing lemma yields the d^{9/4} warm-start iteration bound. The path to the sharper ASC radius runs

What carries the argument

Average self-concordance (ASC) is the condition that a random Dikin proposal at radius r changes the squared local length, when measured at the proposal instead of the base point, by O(εr^2/d) with probability 1−ε; it is the property that keeps the Metropolis acceptance probability high. The paper proves ASC for the Lee–Sidford metric at radius d^{-1/8} by expanding the path function F(t) = h^T g0(x+th) h along a Gaussian direction h, but only through a recursively defined chain of bottleneck terms H_k(t) = q_t^T N_t^{(k−1)} v_t. The higher derivatives of the Lewis-weight matrix N_t are controlled via a moving orthonormal frame for the column space of a half of the metric, which removes irre

Load-bearing premise

The whole proof rests on the good-event estimates of Lemma 3.3: along a random proposal path of length η = r/√d, the coordinate-wise slack bounds stay O(1) and the first, second, and third derivatives of the Lewis-weight derivative matrix stay within O(d^{1/2}), O(d), and O(d^{3/2}) respectively, all on one event of probability 1−ε/20.

What would settle it

Compute the operator norms of N'''(t) along the Dikin proposal path for a concrete polytope with explicit Lewis weights, for instance the d-dimensional simplex or the hypercube, at the claimed radius d^{−1/8}. If ∥N'''∥ exceeds d^{3/2}·poly(d^{1/8}) for a nontrivial fraction of directions, the terminal term H_4 contributes more than O(ε) and the ASC radius d^{−1/8} fails; equivalently, simulate the fluctuation |F(η)−F(0)| at r = d^{−1/8} and check it exceeds the ASC threshold 2εr^2/d with probability larger than ε.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Warm-start exponential sampling from any bounded full-dimensional polytope now runs in O~(d^{9/4}) Dikin-walk iterations, improving the previous O~(d^{5/2}) and shrinking the gap to the conjectured d^2.
  • Cold-start sampling via the annealing framework improves to O~(d^{41/16}) ≈ d^{2.56} iterations, the best known for this problem.
  • The sharper ASC radius for the unscaled Lee–Sidford metric is a stand-alone geometric fact: any future sampler whose analysis reduces to ASC will inherit this improvement.
  • The paper isolates the two estimates that remain to reach d^2—control of the j-th derivative of N_t pathwise and of the j-th base-point Gaussian polynomial for all j—and pushes both to j=3, making the remaining obstacle precise.
  • The higher-order Lewis-weight calculus (moving-frame derivatives up to third order and the Wiener-chaos tensor bounds) is reusable machinery for other barrier-based algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The recursion the paper exhibits suggests that if the pathwise estimate could be extended to ∥N_t^{(j)}∥ ≲ d^{j/2} and the base-point L2 estimate to ∥q^T N_x^{(j)} v_x∥_{L2} ≲ d^{(j+1)/2} for arbitrarily large j, the mixing time would approach d^{2+1/(j+1)}; reaching the exact d^2 likely needs a fundamentally different argument rather than longer expansions, since the j-terms grow with j.
  • The moving-frame calculus for Lewis weights may also benefit interior-point method analysis beyond sampling, where third- and higher-order barrier derivatives are typically avoided.
  • The cold-start exponent d^{41/16} emerges from a generic annealing schedule; a schedule tuned to the improved self-concordance constants could plausibly push it closer to d^{9/4}, the warm-start rate.
  • A natural test case for the sharper ASC radius is the d-dimensional simplex or hypercube, where the Lewis weights are explicit and the higher-order derivatives can be computed symbolically to verify the d^{-1/8} radius does not hide a larger constant.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 3 minor

Summary. The paper studies the Dikin walk for sampling from a bounded full-dimensional polytope with an exponential target distribution. It proves that, using the Lee–Sidford metric scaled by a factor L = Θ~(d^{1/4}), the Dikin walk mixes from a warm start in Θ~(d^{9/4} polylog m log(χ^2_0/ε)) iterations, improving the previous Θ~(d^{5/2}) bound and making progress toward the conjectured d^2 mixing time. The improvement rests on a sharper average self-concordance (ASC) estimate for the unscaled LS metric at radius r = Θ~(d^{-1/8}). The proof isolates a recursive bottleneck chain H_k, develops higher-order Lewis-weight calculus via a moving orthonormal frame, and controls the base-point Gaussian polynomials by Wiener-chaos decompositions and multiple stochastic integrals. A cold-start corollary gives d^{41/16} iterations.

Significance. If correct, this is the first improvement over the d^{2.5} bound of CDWY18 in nearly a decade, and a substantial step toward the d^2 conjecture. The technical machinery introduced—selective expansion of bottleneck terms, moving-frame higher-order calculus for Lewis weights, and MSI-based tensor-norm estimates for Gaussian polynomials—is likely to be useful for future analyses of Dikin-type walks. The proof is detailed and self-contained modulo the cited black boxes, and it is explicit about the remaining barriers to the d^2 conjecture. My independent checks of the exponent arithmetic, the scaling chain, and the main bottleneck estimates all pass.

major comments (1)
  1. [§3.2 / Lemma 3.3] I explicitly checked the apparent inconsistency with (3.12) raised in the stress-test note. A termwise substitution of ||u'_i||^2 ≲ d w_i into Σ_i ||u'_i||^6 / w_i^2 would give d^4, but this ignores the global budget Σ_i ||u'_i||^2 = ||U'_t||_F^2 ≲ d. Writing x_i = ||u'_i||^2 / w_i, one has x_i ≲ d and Σ_i x_i w_i = ||U'_t||_F^2 ≲ d, so Σ_i ||u'_i||^6 / w_i^2 = Σ_i x_i^3 w_i ≲ d^2 Σ_i x_i w_i ≲ d^3. Hence the displayed bound ||Φ'''_t||_F^2 ≲ d^3 is consistent with (3.12), and consequently ||N'''_t|| ≲ d^{3/2} holds. The H4 bottleneck remains η^4 d^{5/2} = r^4 d^{1/2}, supporting the claimed r = Θ~(d^{-1/8}) ASC radius. The stress-test concern therefore does not land.
minor comments (3)
  1. [§3, Proposition 3.1] The statement 'choose R_ε = Θ~(d^{-1/8})' is imprecise with respect to ε: the displayed condition R_ε + R_ε^2 + R_ε^4 d^{1/2} ≤ ε/polylog(m/ε) requires a constant factor ε^{1/4} in R_ε (i.e. R_ε = Θ~(ε^{1/4} d^{-1/8})). Since Theorem 1.1 uses a fixed ASC accuracy, this does not affect the main result, but the proposition should be stated precisely.
  2. [§3.2–3.3] The notation B is overloaded: \widehat B_t = W_t^β A_t in Lemma 3.3, while B = W^{1/2}_x A_x in §3.3. These are different matrices and using the same letter in close proximity is confusing. Also P_t denotes both the original Lewis-weight projector and U_t U_t^T; a consistent renaming would improve readability.
  3. [Lemma 3.3 proof] The bound on Σ_i ||u'_i||^6 / w_i^2 is compressed into a single chain. Adding the two-line argument with x_i = ||u'_i||^2/w_i and the global budget ||U'_t||_F^2 ≲ d would remove a likely source of confusion and preempt the apparent d^4 issue.

Circularity Check

0 steps flagged

No circularity: the new ASC radius and mixing bound are derived from internal estimates, not from fitted or self-defined targets.

full rationale

The paper's central claim, Theorem 1.1, is a genuine derivation: Proposition 3.1 proves an average self-concordance radius r = Θ~(d^{-1/8}) for the unscaled Lee-Sidford metric using an explicit selective expansion (Equation 3.2), pathwise estimates (Lemmas 3.3-3.4), and Gaussian-polynomial concentration via Wiener chaos. The bottleneck contribution η^4 d^{5/2} = r^4 d^{1/2} is computed from those estimates and directly determines the allowed radius, rather than being imposed to match the desired d^{2.25} bound. The mixing-time conclusion then follows by the standard scaling observation (Proposition 2.3) and the prior published mixing framework [KV24, Theorem 1], which is cited as external machinery and not redefined in terms of the result. The paper does not fit any parameter to a subset of data and then rename it a prediction; it does not invoke a uniqueness theorem from its own prior work; and it does not smuggle an ansatz through a self-citation. The skeptical concern about the ∥N'''_t∥ bound (whether it should be d^2 rather than d^{3/2}) is a potential proof error or computational gap in Lemma 3.3, not a circularity: it challenges whether the claimed estimates are true, but does not show that the conclusion is equivalent to an input by construction or to a self-citation chain. The derivation remains self-contained given its explicit assumptions and prior cited lemmas.

Axiom & Free-Parameter Ledger

3 free parameters · 7 axioms · 0 invented entities

The paper's contribution is a proof, not a model: the only 'parameters' are existential scale constants (r, L, p) whose values are dictated by the analysis rather than fitted to data. All polytope and Lewis-weight geometry is inherited from prior work ([LS19], [LLV20]), and the mixing and annealing frameworks are imported from [KV24] as published facts. The genuinely new content is the ASC derivation chain (Lemma 3.3 and Section 3.3), which is where the load-bearing axioms concentrate. No new physical or mathematical entities are postulated; the bottleneck chain, moving frame, and chaos decompositions are bookkeeping devices.

free parameters (3)
  • Dikin radius r = Theta(1), any sufficiently small constant
    Theorem 1.1 takes r as a sufficiently small Theta(1) radius; existence follows from the scaling argument of Proposition 2.3. An existential constant, not fitted to data.
  • Metric scaling factor L = C d^{1/4} polylog(md)
    Chosen to convert the d^{-1/8} ASC radius of the unscaled metric into constant radius; it sets the symmetry parameter to d^{5/4} and hence the d^{9/4} mixing time. Determined by the proof, not fitted.
  • Lewis-weight exponent p = Theta(polylog m)
    Taken as Theta(polylog m) throughout; all polylog(m) factors are suppressed in the O-tilde notation. A design choice inherited from Lee-Sidford theory, not fitted.
axioms (7)
  • domain assumption Lewis-weight calculus of [LS19] (Lemmas 2.4-2.7): derivative formula W'_x,h = -Diag(W^{1/2} N W^{1/2} s), the closeness bound (Lemma 2.7), and the N-matrix bounds (Lemma 2.6)
    The foundational toolkit for Dikin-walk-with-Lewis-weights analysis; taken as prior literature, not re-proven.
  • domain assumption SSC, LTSC, and bar-nu = O~(d) symmetry of the standard LS metric, equivalently containment D_g(x,1) subset of K for radius-1 Dikin proposals
    Inherited from [LLV20, Lemmas 4.2 and 4.3]; used to keep the proposal path inside K (Lemma 3.3) and to apply the mixing theorem. Prior published result.
  • domain assumption Mixing framework of [KV24] (Lemma 2.2: SSC + LTSC + ASC + bar-nu-symmetric implies O(d bar-nu) warm-start mixing) and the annealing framework of [KV24, Theorem 2] for cold starts
    Used as black boxes. The author is a co-author of [KV24], so this is a self-citation, but the framework is an independently published theorem and the new ASC work is an input to it, not derived from it.
  • standard math Gaussian polynomial concentration (Lemma 3.2): P(|P(h)| >= t ||P||_{L2}) <= exp(- n t^{2/n} / 2e)
    Stated and used to convert L2 bounds on base-point Gaussian polynomials into high-probability bounds.
  • standard math Wiener chaos / multiple stochastic integral facts from [Nua06]: isometry (3.13), product formula (Lemma 3.7), chaos expansion (Theorem 3.8), and tensor-MSI lemmas 3.9-3.12
    The formal backbone of Sections 3.3.3-3.3.4 for computing L2 norms of quartic and quintic Gaussian polynomials; imported from the cited monograph.
  • standard math Existence of a smooth orthonormal frame with U^T U' = 0 via a matrix ODE (Lemma B.2) and its multi-parameter analogue (Lemma B.3)
    Underpins the moving-frame calculus and hence all higher-derivative bounds on N_t in Lemma 3.3. Elementary differential-geometric linear algebra, but it is the least battle-tested new ingredient and is acknowledged as LLM-assisted.
  • domain assumption Path containment: for good directions, the segment x + t h stays in int K for t in [0, eta]
    Guaranteed via bar-nu-symmetry (Dikin ellipsoid of radius 1 inside K) once r is small enough; used throughout Lemma 3.3 to differentiate Lewis weights along the path.

pith-pipeline@v1.3.0-alltime-deepseek · 36777 in / 27861 out tokens · 238883 ms · 2026-08-02T03:16:32.246334+00:00 · methodology

0 comments
read the original abstract

Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in $\mathbb{R}^{d}$ with $m$ linear inequalities mixes in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the correct mixing time should be $d^{2}$. We make progress toward this conjecture by improving the previous $d^{2.5}$-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in $d^{2.25}$ iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

204 extracted references · 56 canonical work pages

  1. [1]

    , title =

    Vempala, Santosh S. , title =

  2. [2]

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

    Kannan, Ravi and Narayanan, Hariharan , booktitle =. Random walks on polytopes and an affine interior point method for linear programming , year =

  3. [3]

    Path finding methods for linear programming: solving linear programs in

    Yin Tat Lee and Aaron Sidford , booktitle =. Path finding methods for linear programming: solving linear programs in

  4. [4]

    Self-concordant functions and polynomial time methods in convex programming

    Nesterov, Yurii and Nemirovskii, Arkadii , journal =. Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad , volume =

  5. [5]

    Iterative solution of problems of linear and quadratic programming , volume =

    Dikin, Iliya Iosiphovich , booktitle =. Iterative solution of problems of linear and quadratic programming , volume =

  6. [6]

    A polynomial-time algorithm, based on

    Renegar, James , journal =. A polynomial-time algorithm, based on

  7. [7]

    A new polynomial-time algorithm for linear programming , year =

    Karmarkar, Narendra , booktitle =. A new polynomial-time algorithm for linear programming , year =

  8. [8]

    and Johnson, Alan W

    Henderson, Darrall and Jacobson, Sheldon H. and Johnson, Alan W. , pages =. The theory and practice of simulated annealing , year =

  9. [9]

    Daniel and Vecchi, Mario P

    Kirkpatrick, Scott and Gelatt Jr, C. Daniel and Vecchi, Mario P. , journal =. Optimization by simulated annealing , volume =

  10. [10]

    Pierre-Antoine Absil and Robert Mahony and Rodolphe Sepulchre , publisher =

  11. [11]

    Malliavin calculus and normal approximations , year =

    Nualart, David , publisher =. Malliavin calculus and normal approximations , year =

  12. [12]

    Nualart, David , date-added =. The

  13. [14]

    High-Dimensional Probability: An Introduction with Applications in Data Science , url =

    Vershynin, Roman , date-added =. High-Dimensional Probability: An Introduction with Applications in Data Science , url =. 2018 , bdsk-url-1 =. doi:10.1017/9781108231596 , isbn =

    doi:10.1017/9781108231596 2018

  14. [15]

    Introductory Lectures on Convex Optimization , url =

    Nesterov, Yurii , date-added =. Introductory Lectures on Convex Optimization , url =. Applied Optimization , publisher =. 2004 , bdsk-url-1 =. doi:10.1007/978-1-4419-8853-9 , isbn =

    doi:10.1007/978-1-4419-8853-9 2004

  15. [16]

    Mirrored

    Hsieh, Ya-Ping and Kavis, Ali and Rolland, Paul and Cevher, Volkan , booktitle =. Mirrored. 2018 , bdsk-url-1 =

    2018

  16. [17]

    Functional Stochastic Localization , year =

    Anming Gu and Bobby Shi and Kevin Tian , date-added =. Functional Stochastic Localization , year =. arXiv preprint arXiv:2602.03999 , keywords =

    arXiv

  17. [18]

    Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified

    Gu, Yuzhou and Kuang, Nikki Lijing and Ma, Yi-An and Song, Zhao and Zhang, Lichen , booktitle =. Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified. 2024 , bdsk-url-1 =. doi:10.52202/079017-2212 , pages =

    work page doi:10.52202/079017-2212 2024

  18. [19]

    , booktitle =

    Mangoubi, Oren and Vishnoi, Nisheeth K. , booktitle =. Sampling from Structured Log-Concave Distributions via a Soft-Threshold. 2023 , bdsk-url-1 =

    2023

  19. [20]

    arXiv preprint arXiv:1910.08033 , title =

    Lee, Yin Tat and Sidford, Aaron , date-added =. arXiv preprint arXiv:1910.08033 , title =

    Pith/arXiv arXiv 1910

  20. [21]

    and Chewi, Sinho and Erdogdu, Murat A

    Kook, Yunbum and Zhang, Matthew S. and Chewi, Sinho and Erdogdu, Murat A. and Li, Mufan (Bill) , booktitle =. Sampling from the mean-field stationary distribution , url =. 2024 , bdsk-url-1 =

    2024

  21. [22]

    Tyrrell , date-added =

    Rockafellar, R. Tyrrell , date-added =. Monotone Operators and the Proximal Point Algorithm , url =. SIAM Journal on Control and Optimization , number =. 1976 , bdsk-url-1 =. doi:10.1137/0314056 , eprint =

    doi:10.1137/0314056 1976

  22. [23]

    Understanding

    Ahn, Kwangjun and Zhang, Zhiyu and Kook, Yunbum and Dai, Yan , booktitle =. Understanding. 2024 , bdsk-url-1 =

    2024

  23. [24]

    Affirmative resolution of

    Klartag, Bo'az and Lehec, Joseph , date-added =. Affirmative resolution of. Geometric and Functional Analysis , mrclass =. 2025 , bdsk-url-1 =. doi:10.1007/s00039-025-00718-w , fjournal =

    work page doi:10.1007/s00039-025-00718-w 2025

  24. [25]

    , date-added =

    Vaidya, Pravin M. , date-added =. A new algorithm for minimizing convex functions over convex sets , url =. Mathematical Programming , mrclass =. 1996 , bdsk-url-1 =. doi:10.1016/0025-5610(92)00021-S , fjournal =

    work page doi:10.1016/0025-5610(92)00021-s 1996

  25. [26]

    Isoperimetric inequalities in high-dimensional convex sets , url =

    Klartag, Bo'az and Lehec, Joseph , date-added =. Isoperimetric inequalities in high-dimensional convex sets , url =. Bulletin of the American Mathematical Society , mrclass =. 2025 , bdsk-url-1 =. doi:10.1090/bull/1869 , fjournal =

    work page doi:10.1090/bull/1869 2025

  26. [27]

    Regularized

    Jiang, Minhui and Chen, Yuansi , booktitle =. Regularized. 2025 , bdsk-url-1 =

    2025

  27. [28]

    Mixing time of the proximal sampler in relative

    Wibisono, Andre , booktitle =. Mixing time of the proximal sampler in relative. 2025 , bdsk-url-1 =

    2025

  28. [29]

    Tyrrell , date-added =

    Rockafellar, R. Tyrrell , date-added =. Convex analysis , year =

  29. [30]

    Lectures on Convex Optimization , url =

    Nesterov, Yurii , date-added =. Lectures on Convex Optimization , url =. Springer Optimization and Its Applications , publisher =. 2018 , bdsk-url-1 =. doi:10.1007/978-3-319-91578-4 , isbn =

    doi:10.1007/978-3-319-91578-4 2018

  30. [31]

    , date-added =

    Nesterov, Yurii and Todd, Michael J. , date-added =. On the. Foundations of Computational Mathematics , month = oct, number =. 2002 , bdsk-url-1 =. doi:10.1007/s102080010032 , issn =

    work page doi:10.1007/s102080010032 2002

  31. [32]

    Interior-point polynomial algorithms in convex programming , url =

    Nesterov, Yurii and Nemirovskii, Arkadii , date-added =. Interior-point polynomial algorithms in convex programming , url =. 1994 , bdsk-url-1 =. doi:10.1137/1.9781611970791 , isbn =

    doi:10.1137/1.9781611970791 1994

  32. [33]

    and Neudecker, Heinz , date-added =

    Magnus, Jan R. and Neudecker, Heinz , date-added =. The elimination matrix: some lemmas and applications , url =. SIAM Journal on Algebraic Discrete Methods , month = dec, number =. 1980 , bdsk-url-1 =. doi:10.1137/0601049 , issn =

    doi:10.1137/0601049 1980

  33. [34]

    Universal barrier is n -self-concordant , url =

    Lee, Yin Tat and Yue, Man--Chung , date-added =. Universal barrier is n -self-concordant , url =. Mathematics of Operations Research , month = aug, number =. 2021 , bdsk-url-1 =. doi:10.1287/moor.2020.1113 , fjournal =

    arXiv 2021

  34. [35]

    , date-added =

    Lee, Yin Tat and Vempala, Santosh S. , date-added =. Geodesic. SIAM Journal on Computing , month = apr, number =. 2022 , bdsk-url-1 =. doi:10.1137/17m1145999 , issn =

    work page doi:10.1137/17m1145999 2022

  35. [36]

    Powers of tensors and fast matrix multiplication , url =

    Le Gall, Fran. Powers of tensors and fast matrix multiplication , url =. International Symposium on Symbolic and Algebraic Computation , collection =. 2014 , bdsk-url-1 =. doi:10.1145/2608628.2608664 , month = jul, pages =

    arXiv 2014

  36. [37]

    Hyperbolic polynomials and interior point methods for convex programming , url =

    G. Hyperbolic polynomials and interior point methods for convex programming , url =. Mathematics of Operations Research , month = may, number =. 1997 , bdsk-url-1 =. doi:10.1287/moor.22.2.350 , fjournal =

    work page doi:10.1287/moor.22.2.350 1997

  37. [38]

    The entropic barrier is n -self-concordant , url =

    Chewi, Sinho , booktitle =. The entropic barrier is n -self-concordant , url =. 2023 , bdsk-url-1 =. doi:10.1007/978-3-031-26300-2_6 , isbn =

    work page doi:10.1007/978-3-031-26300-2_6 2023

  38. [39]

    The entropic barrier: a simple and optimal universal self-concordant barrier , url =

    Bubeck, S\'ebastien and Eldan, Ronen , booktitle =. The entropic barrier: a simple and optimal universal self-concordant barrier , url =. 2015 , bdsk-url-1 =

    2015

  39. [40]

    , date-added =

    Anstreicher, Kurt M. , date-added =. Volumetric path following algorithms for linear programming , url =. Mathematical Programming , month =. 1997 , bdsk-url-1 =. doi:10.1007/BF02614386 , issn =

    doi:10.1007/bf02614386 1997

  40. [41]

    Jia, He and Laddha, Aditi and Lee, Yin Tat and Vempala, Santosh , title =. J. ACM , month = apr, articleno =. 2026 , issue_date =. doi:10.1145/3795687 , abstract =

    work page doi:10.1145/3795687 2026

  41. [42]

    and Zhang, Matthew S

    Kook, Yunbum and Vempala, Santosh S. and Zhang, Matthew S. , date-added =. In-and-. Random Structures & Algorithms , number =. 2026 , bdsk-url-1 =. doi:https://doi.org/10.1002/rsa.70061 , eprint =

    work page doi:10.1002/rsa.70061 2026

  42. [43]

    , date-added =

    Kook, Yunbum and Vempala, Santosh S. , date-added =. The localization method for high-dimensional inequalities , year =. arXiv preprint arXiv:2512.10848 , keywords =

    arXiv

  43. [44]

    , booktitle =

    Kook, Yunbum and Vempala, Santosh S. , booktitle =. Faster logconcave sampling from a cold start in high dimension , year =. doi:10.1109/FOCS63196.2025.00052 , pages =

    arXiv 2025

  44. [45]

    Hit-and-run mixing via localization schemes , url =

    Chen, Yuansi and Eldan, Ronen , date-added =. Hit-and-run mixing via localization schemes , url =. Discrete & Computational Geometry , month =. 2025 , bdsk-url-1 =. doi:10.1007/s00454-025-00808-4 , issn =

    work page doi:10.1007/s00454-025-00808-4 2025

  45. [46]

    On the log-

    Bizeul, Pierre , date-added =. On the log-. Journal of Functional Analysis , month = may, number =. 2026 , bdsk-url-1 =. doi:10.1016/j.jfa.2026.111368 , issn =

    arXiv 2026

  46. [47]

    , booktitle =

    Laddha, Aditi and Lee, Yin Tat and Vempala, Santosh S. , booktitle =. Strong self-concordance and sampling , url =. 2020 , bdsk-url-1 =. doi:10.1145/3357713.3384272 , month = jun, pages =

    arXiv 2020

  47. [48]

    Localization schemes: a framework for proving mixing bounds for

    Chen, Yuansi and Eldan, Ronen , booktitle =. Localization schemes: a framework for proving mixing bounds for

  48. [49]

    Sampling from the

    El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark , booktitle =. Sampling from the

  49. [50]

    An information-theoretic view of stochastic localization , url =

    El Alaoui, Ahmed and Montanari, Andrea , date-added =. An information-theoretic view of stochastic localization , url =. IEEE Transactions on Information Theory , mrclass =. 2022 , bdsk-url-1 =. doi:10.1109/tit.2022.3180298 , fjournal =

    arXiv 2022

  50. [51]

    The isotropic constant in the theory of high-dimensional convex bodies , year =

    Giannopoulos, Apostolos and Pafis, Minas and Tziotziou, Natalia , date-added =. The isotropic constant in the theory of high-dimensional convex bodies , year =. To appear in Bull. Amer. Math. Soc. , keywords =

  51. [52]

    Geometry of isotropic convex bodies , url =

    Brazitikos, Silouanos and Giannopoulos, Apostolos and Valettas, Petros and Vritsiou, Beatrice-Helen , date-added =. Geometry of isotropic convex bodies , url =. 2014 , bdsk-url-1 =. doi:10.1090/surv/196 , isbn =

    doi:10.1090/surv/196 2014

  52. [53]

    Convex measures on locally convex spaces , url =

    Borell, Christer , date =. Convex measures on locally convex spaces , url =. Arkiv f. 1974 , bdsk-url-1 =. doi:10.1007/BF02384761 , id =

    work page doi:10.1007/bf02384761 1974

  53. [54]

    Klartag, Bo'az , date-added =. On. Lecture notes prepared for a winter school at the

  54. [55]

    , booktitle =

    Klartag, Bo'az and Milman, Vitali D. , booktitle =. The slicing problem by. 2022 , bdsk-url-1 =. doi:10.1007/978-3-031-05331-3\_9 , isbn =

    work page doi:10.1007/978-3-031-05331-3 2022

  55. [56]

    Fast Tensor Completion via Approximate

    Ghadiri, Mehrdad and Fahrbach, Matthew and Kook, Yunbum and Jadbabaie, Ali , booktitle =. Fast Tensor Completion via Approximate. 2025 , bdsk-url-1 =

    2025

  56. [57]

    A convex/log-concave correlation inequality for

    Harg\'e, Gilles , date-added =. A convex/log-concave correlation inequality for. Probability Theory and Related Fields , mrclass =. 2004 , bdsk-url-1 =. doi:10.1007/s00440-004-0365-8 , fjournal =

    doi:10.1007/s00440-004-0365-8 2004

  57. [58]

    Thin-shell bounds via parallel coupling , year =

    Klartag, Bo'az and Lehec, Joseph , date-added =. Thin-shell bounds via parallel coupling , year =. arXiv preprint arXiv:2507.15495 , keywords =

    arXiv

  58. [59]

    Stam, A. J. , date-added =. Some inequalities satisfied by the quantities of information of. Information and Control , mrclass =

  59. [60]

    arXiv preprint arXiv:2507.18021 , keywords =

    Zeroth-order Logconcave Sampling , url =. arXiv preprint arXiv:2507.18021 , keywords =. doi:10.48550/arXiv.2507.18021 , eprint =

    work page doi:10.48550/arxiv.2507.18021

  60. [61]

    , booktitle =

    Kook, Yunbum and Vempala, Santosh S. , booktitle =. Sampling and integration of logconcave functions by algorithmic diffusion , url =. 2025 , bdsk-url-1 =. doi:10.1145/3717823.3718202 , isbn =

    arXiv 2025

  61. [62]

    On a class of

    Yuan, Bo and Fan, Jiaojiao and Liang, Jiaming and Wibisono, Andre and Chen, Yongxin , booktitle =. On a class of. 2023 , bdsk-url-1 =

    2023

  62. [63]

    Optimal transport , url =

    Villani, C\'edric , date-added =. Optimal transport , url =. 2009 , bdsk-url-1 =. doi:10.1007/978-3-540-71050-9 , isbn =

    doi:10.1007/978-3-540-71050-9 2009

  63. [64]

    , booktitle =

    Vempala, Santosh S. , booktitle =. Geometric random walks: a survey , volume =

  64. [65]

    Liu, Yuan , date-added =. The. Electronic Journal of Probability , mrclass =. 2020 , bdsk-url-1 =. doi:10.1214/19-ejp403 , fjournal =

    work page doi:10.1214/19-ejp403 2020

  65. [66]

    Blocking conductance and mixing in random walks , url =

    Kannan, Ravi and Lov\'. Blocking conductance and mixing in random walks , url =. Combinatorics, Probability and Computing , mrclass =. 2006 , bdsk-url-1 =. doi:10.1017/S0963548306007504 , fjournal =

    work page doi:10.1017/s0963548306007504 2006

  66. [67]

    Analysis of

    Durmus, Alain and Majewski, Szymon and Miasojedow, B. Analysis of. Journal of Machine Learning Research , mrclass =

  67. [68]

    and Tsybakov, Alexandre B

    Dalalyan, Arnak S. and Tsybakov, Alexandre B. , date-added =. Sparse regression learning by aggregation and. Journal of Computer and System Sciences , mrclass =. 2012 , bdsk-url-1 =. doi:10.1016/j.jcss.2011.12.023 , fjournal =

    work page doi:10.1016/j.jcss.2011.12.023 2012

  68. [69]

    Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent , url =

    Dalalyan, Arnak , booktitle =. Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent , url =. 2017 , bdsk-url-1 =

    2017

  69. [70]

    Heat flow and a faster algorithm to compute the surface area of a convex body , url =

    Belkin, Mikhail and Narayanan, Hariharan and Niyogi, Partha , date-added =. Heat flow and a faster algorithm to compute the surface area of a convex body , url =. Random Structures & Algorithms , mrclass =. 2013 , bdsk-url-1 =. doi:10.1002/rsa.20513 , fjournal =

    doi:10.1002/rsa.20513 2013

  70. [71]

    Gradient flows in metric spaces and in the space of probability measures , year =

    Ambrosio, Luigi and Gigli, Nicola and Savar\'e, Giuseppe , date-added =. Gradient flows in metric spaces and in the space of probability measures , year =

  71. [72]

    A note on the spectral gap for log-concave probability measures on convex bodies , url =

    Bonnefont, Michel and Joulin, Ald\'eric , date-added =. A note on the spectral gap for log-concave probability measures on convex bodies , url =. International Mathematics Research Notices , mrclass =. 2024 , bdsk-url-1 =. doi:10.1093/imrn/rnae256 , fjournal =

    work page doi:10.1093/imrn/rnae256 2024

  72. [73]

    Klartag, Bo'az , date-added =. A. Probability Theory and Related Fields , mrclass =. 2009 , bdsk-url-1 =. doi:10.1007/s00440-008-0158-6 , fjournal =

    work page doi:10.1007/s00440-008-0158-6 2009

  73. [74]

    Probability in high dimension , volume =

    Van Handel, Ramon , date-added =. Probability in high dimension , volume =. Lecture Notes (Princeton University) , number =

  74. [75]

    Logarithmic

    Gross, Leonard , date-added =. Logarithmic. American Journal of Mathematics , mrclass =. 1975 , bdsk-url-1 =. doi:10.2307/2373688 , fjournal =

    doi:10.2307/2373688 1975

  75. [76]

    Polyrun: a

    Krzysztof Ciomek and Mi. Polyrun: a. SoftwareX , pages =. 2021 , bdsk-url-1 =. doi:https://doi.org/10.1016/j.softx.2021.100659 , issn =

    arXiv 2021

  76. [77]

    Andy Yu Zhu Yao and David Kane , date-added =. walkr:. 2017 , bdsk-url-1 =. doi:10.21105/joss.00061 , journal =

    work page doi:10.21105/joss.00061 2017

  77. [78]

    volesti: volume approximation and sampling for convex polytopes in

    Chalkis, Apostolos and Fisikopoulos, Vissarion , date-added =. volesti: volume approximation and sampling for convex polytopes in. The R Journal , pages =

  78. [79]

    arXiv preprint arXiv:2412.06629 , keywords =

    Sun, Benny and Chen, Yuansi , date-added =. arXiv preprint arXiv:2412.06629 , keywords =

    Pith/arXiv arXiv

  79. [80]

    , booktitle =

    Kook, Yunbum and Lee, Yin Tat and Shen, Ruoqi and Vempala, Santosh S. , booktitle =. Condition-number-independent convergence rate of. 2023 , bdsk-url-1 =

    2023

  80. [81]

    John's walk , url =

    Gustafson, Adam and Narayanan, Hariharan , date-added =. John's walk , url =. Advances in Applied Probability , mrclass =. 2023 , bdsk-url-1 =. doi:10.1017/apr.2022.34 , fjournal =

    work page doi:10.1017/apr.2022.34 2023

Showing first 80 references.