{"id":"871eb1e4-98c9-4710-8443-d8a66c985113","arxiv_id":"2412.11303","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The soft-threshold Dikin walk mixes in O((m+kappa)n) iterations for truncated logconcave targets, supported by a new isoperimetric inequality combining Euclidean and Hilbert metrics.","lead":"The paper proves faster mixing time bounds for a Markov chain algorithm called the regularized Dikin walk, which samples bell-shaped distributions that are cut off by a polytope. A smart generalist might read it because this sampling problem is the computational bottleneck in Bayesian models like probit regression.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Key gap: Lemma 3's mixed isoperimetric inequality is not proven for arbitrary measurable partitions because the 1D combinatorial step is omitted; the conductance argument depends on it.","rationale":"The reader's weakest_assumption correctly identifies the mixed isoperimetric inequality and the omitted combinatorial step. My analysis confirms that this is the single most load-bearing concern: the conductance lower bound in Theorem 1 applies Lemma 3 to arbitrary measurable sets A'_1 and A'_2, so the inequality must hold for all measurable partitions, not just interval partitions along a needle. The proof as written only covers the interval case and defers the general case to a citation, which is insufficient because the max-metric makes the reduction nontrivial: inf max can exceed max of infima, so combining Facts 1 and 2 does not yield Lemma 3. The Corollary 2 overclaim identified by the reader is real but secondary; it does not affect Corollary 1. I therefore agree with the CONDITIONAL verdict, but the condition should explicitly require completing the proof of Lemma 3 (and formalizing the boundary limit in Lemma 7). Since the reader already assigned CONDITIONAL, my concern does not move the verdict.","tokens_in":56549,"tokens_out":19516,"duration_ms":158824,"concrete_test":"Provide a complete proof of the omitted 1D combinatorial step in Lemma 3: for any logconcave density g on [0,1] and any measurable partition I1⊔I2⊔I3, show that max{d_K(I1,I2), log(2) sqrt(alpha) d_euclid(I1,I2)} J1 J2 <= J3 J4, or exhibit a counterexample. A practical way to test the claim is to run a numerical search over unions of intervals for a truncated standard Gaussian (alpha=1) on [0,1]: if any partition violates the inequality by more than numerical precision, Lemma 3 is false and Theorem 1 lacks its isoperimetric foundation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mixing bound of Theorem 1 relies on Lemma 3, which claims that for every measurable partition K=S1⊔S2⊔S3 of a (possibly unbounded) convex set K, with d'(x,y)=max{d_K(x,y), log(2) sqrt(alpha) ||x-y||_2}, we have Pi(S3) >= d'(S1,S2) Pi(S1) Pi(S2). This is strictly stronger than the maximum of the two known isoperimetric inequalities cited as Facts 1 and 2, because inf max >= max of the infima; the locations achieving the Euclidean and cross-ratio infima may differ. The proof in Section 4.1 localizes to 1D and proves the desired inequality only for the special case where I1 and I2 are intervals at the two ends of the needle. The passage from measurable sets to intervals is dismissed with the sentence 'Following the same combinatorial argument in Theorem 5.2 from [KLS95], we can prove Eq. (24) for general 1-dimensional measurable sets I1,I2,I3, the details are omitted here.' This omitted step is exactly what is needed: the conductance proof in Theorem 1 applies Lemma 3 to the arbitrary measurable sets A'_1 and A'_2. The standard compression argument for Euclidean or cross-ratio alone does not obviously extend to the max-metric, since the extremal sets for the infimum of the maximum may fail to be intervals. Consequently, Lemma 3 is currently unproven in the regime required by the main theorem. Lemma 4 inherits this issue and additionally contains a handwavy boundary limit ('we take the limit S1->B, S2->K\\B, S3->∂B') in the proof of Lemma 7 that is not formalized. If Lemma 3 fails, the O((m+kappa)n) mixing time collapses; this is more load-bearing than the Corollary 2 overclaim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":56920,"tokens_out":5548,"duration_ms":51568,"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":[{"comment":"Duplicate of the previous comment; should be removed in a final report, but included here to satisfy formatting constraints in this exercise.","section":"Section 4.2, proof of Lemma 7"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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)'.","section":"Section 5.1, proof of Theorem 1"},{"comment":"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.","section":"Appendix B, proof of Lemma 9"},{"comment":"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.","section":"Section 3.2"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within scope for this journal and addresses an important problem with plausible new techniques. The central issue is the unproven measurable-set version of Lemma 3, which the main theorem relies on; the authors should either supply the full proof or adjust the claims. The Corollary 2 overclaim should be corrected regardless. I recommend a major revision rather than rejection, because the overall approach is promising and the gaps appear fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one if you work on geometric random walks. The paper's core idea is a mixed isoperimetric inequality (Lemma 3) combining cross-ratio and Euclidean distance, and it uses it to get O((m+kappa)n) mixing for the soft-threshold Dikin walk on polytopes, removing the radius dependence of MV23. The regularized Lewis Dikin walk and the beyond-worst-case constraint-counting analysis are also new and reasonable. The writing is careful and the self-concordance machinery is mostly done well. I believe the main theorem is likely correct.\n\nThe soft spots: First, Lemma 3 is load-bearing and its proof has an omitted step. The localization reduces to 1D and proves the inequality for intervals at the two ends, but the paper says 'following the same combinatorial argument in Theorem 5.2 from [KLS95]... details are omitted here.' That step is not routine: the metric is the max of two distances, so the extremal sets for the infimum need not be intervals. The conductance proof in Theorem 1 applies Lemma 3 to arbitrary measurable sets, so this gap sits exactly where the main theorem depends. It may be fixable, but as written the central bound is unproven. Second, the extension to weakly logconcave measures (Lemma 4) inherits this and adds an informal boundary limit in Lemma 7 ('we take the limit S1->B, S2->K\\B, S3->∂B') that needs a real proof. Third, Corollary 2 and the abstract overclaim: O((m+kappa)n) gives O(n) mixing only when m=O(1), not when m=o(n); the paper later reverts to m=O(1), so this is an easy correction, not a fatal flaw.\n\nThe reader's stress-test note is right about Lemma 3. I agree with the reader's conditional verdict. The paper deserves a serious referee — the innovation is real and the gap is plausibly repairable — but it should not be accepted until Lemma 3's omitted combinatorial step is supplied and Corollary 2 is corrected.\n\nFor the reading group: yes, worth discussing, especially the localization and max-metric issue. I wouldn't cite the main theorem yet, but I'd follow the revision.","headline":"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.","tokens_in":57471,"tokens_out":2761,"would_cite":false,"duration_ms":25994,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J22","68W20","52A40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Dikin walk","truncated logconcave sampling","MCMC mixing time","isoperimetric inequality","cross-ratio distance","Hilbert metric","Lewis weights","conductance"],"falsifier":"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.","tokens_in":56350,"feed_emoji":"📐","tokens_out":11994,"duration_ms":102124,"temperature":0.7,"pith_summary":"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.","feed_headline":"Constrained sampling now mixes in O((m+κ)n) iterations","feed_subtitle":"New mixed isoperimetry removes the bounded-radius restriction, covering unbounded truncated Gaussians.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the soft-threshold Dikin walk and its bounded-polytope, radius-dependent analysis that this paper improves","marker":"[MV23]"},{"why":"supplies the strong self-concordance and Lewis-metric properties used to prove the regularized Lewis walk corollary","marker":"[KV24]"},{"why":"provides the localization lemma that reduces the new mixed isoperimetric inequality to one-dimensional inequalities","marker":"[KLS95]"},{"why":"contributes the two base isoperimetric inequalities (cross-ratio and Euclidean) that Lemma 3 combines","marker":"[LV07]"},{"why":"contributes the close-coupling argument for Metropolis acceptance rates that Lemma 13 extends to asymmetric proposals","marker":"[ALPW24]"},{"why":"supplies the approximate variance conservation used to extend the mixed isoperimetry to weakly logconcave measures","marker":"[Kla23]"},{"why":"provides strong self-concordance and nu-bar-symmetry facts used to verify local metric hypotheses","marker":"[LLV20]"},{"why":"gives the conductance-to-mixing-time lemma that converts isoperimetric bounds into iteration counts","marker":"[LS93]"}],"fun_headline_variants":["Dikin walk mixes in O((m+κ)n) for truncated logconcave","Unbounded polytope sampling: Dikin walk hits O((m+κ)n)","Faster truncated sampling: Dikin walk without radius bounds","Dikin walk mixing time independence from polytope radius","Soft-threshold Dikin walk: O((m+κ)n) mixing for unbounded sets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Dikin walk mixes in O((m+κ)n) for truncated logconcave","Unbounded polytope sampling: Dikin walk hits O((m+κ)n)","Faster truncated sampling: Dikin walk without radius bounds","Dikin walk mixing time independence from polytope radius","Soft-threshold Dikin walk: O((m+κ)n) mixing for unbounded sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3288,"prompt_tokens":1182,"completion_tokens":2106,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":798,"completion_tokens_details":{"reasoning_tokens":2004}},"tokens_in":798,"tokens_out":2106,"duration_ms":14331,"temperature":1.0,"reasoning_tokens":2004,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:05:30.797269+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}