{"id":"158ef708-03bc-45fc-a2cd-f16edecf6db9","arxiv_id":"2412.17899","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Gibbs sampling from log-smooth strongly log-concave targets mixes in O*(kappa^2 n^7.5 (max{1, sqrt(n^{-1} log(2M/gamma))})^2) steps from an M-warm start.","lead":"This paper proves an upper bound on how many coordinate-by-coordinate updates the Gibbs sampler needs to converge on smooth, bell-shaped probability distributions in high dimensions. The bound is polynomial in dimension and condition number, but a separate 2024 preprint already reported a faster convergence rate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1.2 Case 2 applies concentration bound (57) to cube union C2 outside K; Eq. (79)'s lower bound on Π(I) is unjustified and the conductance bound depends on it.","rationale":"The reader's weakest_assumption points at the cube-tiling/local-uniformity part of Lemma 1.2, which is indeed the most delicate part of the proof. My stress-test isolates a more specific failure inside that part: the use of the concentration bound (57) in Eq. (79) on a cube union that may not lie inside K. This is a genuine load-bearing gap because the Case 2 lower bound on Π(S3) depends on the lower bound on Π(I). However, the gap is likely repairable: one can apply (57) to C2 ∩ S1 instead of C2, since C2 ∩ S1 ⊆ K, and then use S1 ∩ K' ∩ C2 ⊆ I to recover a similar bound. I also checked other potential weak spots: the line-probability normalization in Lemma 3.2 is correct up to the implicit 1/n factor; the final Lemma 1.2 statement is stronger than what the proof literally shows (there is a −ε term rather than a denominator 5−ε), but the conductance proof can absorb this with slightly adjusted constants; and the constraint α ≤ 1/2 can be enforced by a uniform rescaling of coordinates, so it is not a substantive restriction. None of these issues makes the central claim look false, and the independent ALZ result does not bear on correctness. The reader's CONDITIONAL verdict remains appropriate: the theorem is plausible and probably correct, but the proof should be revised to justify or replace Eq. (79) and to align Lemma 1.2's statement with what is established.","tokens_in":18774,"tokens_out":30911,"duration_ms":288610,"concrete_test":"Symbolically re-derive Lemma 1.2 Case 2 replacing Eq. (79) with Π(I) ≥ Π(S1 ∩ C2 ∩ K') ≥ Π(C2 ∩ S1) − ε ≥ Π(S1)/2 − ε, and check that the chain through (80)–(83) still yields Π(S3) ≥ Ψ(Π(S1)/5 − ε). If any step fails, Lemma 1.2's proof has an unsupported lower bound; if it goes through, the gap is benign and the main theorem survives with a minor correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 1.2, Eq. (79) asserts Π(I) = Π(K' ∩ C2) > Π(C2) − ε by applying the bound Π(X ∩ K') ≥ Π(X) − ε from (57) with X = C2. But (57) is derived only for X ⊆ K, and C2 is a union of grid cubes that intersect S1; these cubes may cross ∂K, so C2 is not necessarily contained in K. Concentration Lemma 3.1 controls Π(R^n \\ K), not Π(C2 \\ K'), so the displayed inequality is unsupported. This lower bound on Π(I) feeds directly into the minimum in (82) and hence into the final isoperimetric coefficient Ψ in (83); without it, the Case 2 conductance argument in Theorem 1.1 is not justified. The gap appears repairable by instead applying (57) to C2 ∩ S1 (which is contained in K) and observing that S1 ∩ K' ∩ C2 ⊆ I, giving Π(I) ≥ Π(S1)/2 − ε, but this replacement is not what the paper writes and must be verified through the subsequent inequalities.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper establishes an upper bound on the mixing time of the Gibbs sampler (coordinate hit-and-run) for log-smooth, strongly log-concave target distributions on R^n. The main theorem (Theorem 1.1) states that, from an M-warm initial distribution and for any γ in (0,1/2), the total variation distance to the target is at most γ within O*(κ^2 n^{7.5} max{1, ((1/n) log(2M/γ))^{1/2}}^2) iterations. The proof combines the Lovász-Simonovits s-conductance mixing time bound with a new isoperimetric inequality (Lemma 1.2) for subsets of a high-probability Euclidean ball. The isoperimetric inequality is proved by a cube-tiling argument that exploits the approximate local uniformity of the density, building on the cube isoperimetry of Laddha and Vempala and the log-concave isoperimetric theorem of Lee and Vempala. The paper also discusses an improved bound for large n using Chen's isoperimetric estimate and an isotropic-position variant.","tokens_in":18951,"tokens_out":33063,"duration_ms":254452,"significance":"If correct, this is the first explicit polynomial mixing time bound for the Gibbs sampler on unbounded strongly log-concave targets with a clear n^7.5 dependence, complementing the uniform-distribution results of Laddha-Vempala and Narayanan-Srivastava. The proof strategy is coherent and builds on independently established results; it does not assume its own conclusion. The main technical contribution is the cube-based isoperimetric inequality for log-smooth log-concave measures, which is likely to be of independent interest. The paper is honest about the relation to the contemporaneous KL-contraction result of Ascolani, Lavenant, and Zanella. However, the proof as written contains a gap in the application of the concentration bound in Case 2 of Lemma 1.2 and an unstated normalization assumption about the smoothness constant; these need to be repaired before the result can be considered fully justified.","major_comments":[{"comment":"The inequality Π(I) = Π(K' ∩ C2) > Π(C2) − ε applies the concentration bound (57) with X = C2, but (57) is derived only for subsets of K. The set C2 is a union of grid cubes that intersect S1, and these cubes may cross the boundary of K, so C2 is not necessarily contained in K. Consequently the displayed inequality is unsupported. This lower bound on Π(I) is used in (82) to obtain min{Π(I), Π(K'\\I)} ≥ (1/5)Π(S1) − ε, which feeds directly into the final isoperimetric bound (83). A possible repair is to apply (57) to C2 ∩ S1 (which is contained in K) and use K' ∩ C2 ∩ S1 ⊆ I, giving Π(I) ≥ Π(C2 ∩ S1) − ε ≥ (1/2)Π(S1) − ε, and then re-verify the minimization leading to (82). The proof should be corrected along these lines or by another valid argument.","section":"Section 4.2.2, Eq. (79)"},{"comment":"The proof appears to rely on an unstated normalization of the smoothness constant. With the stated choice δ = (8c√κ L n^{1+σ} M)^{-1}, the Taylor bound (34) gives a first term proportional to r(ε)/(√L n^σ), not 1/(c n^σ) as claimed in (37); the displayed bound (38) is therefore only valid if L = 1 or a scaling reduction is made. Relatedly, the paper claims in (54) that L > max{1/(n log^2 n), μ} ensures α ≤ 1/2, but α = 1/(4√κ L√n log n M) and the stated lower bound on L does not imply L ≥ 1/(2√n log n) for n ≥ 10, so α can exceed 1/2 and even exceed 1. The proof should either state the standard reduction to L = 1 by scaling coordinates (which preserves the mixing time in number of steps and the warmness parameter) or carry the dependence on L through all subsequent inequalities. As written, the proof does not cover the full parameter range stated in Theorem 1.1.","section":"Section 4.2.2, Eqs. (53)-(54) and Section 4.1.1, Eq. (37)"}],"minor_comments":[{"comment":"The displayed equality P_y(ℓ_j ∩ A2) + P_z(ℓ_j ∩ A1) = Π(ℓ_j ∩ A2|y_{−j}) + Π(ℓ_j ∩ A1|z_{−j}) = Π(ℓ_j) = 1/n is not correct as written: P_x(A) includes the factor 1/n for the random coordinate choice, and Π(ℓ_j), the marginal probability of a single line, is zero rather than 1/n. The intended identity is P_y(ℓ_j ∩ A2) + P_z(ℓ_j ∩ A1) = (1/n)[Π(ℓ_j ∩ A2|y_{−j}) + Π(ℓ_j ∩ A1|y_{−j})] = 1/n, and the contradiction argument can be fixed by inserting the missing 1/n factors.","section":"Lemma 3.2, proof"},{"comment":"The constant 25102 in the display τ < 25102 n^2/Ψ^2 log(2M/γ) appears to be a typographical error; substituting φ_s > Ψ/(40n) into (29) yields a factor of 2·40² = 3200, not 25102.","section":"Eq. (30)"},{"comment":"The definition of δ is hard to parse because of the formatting of the superscript -1; the expression should be written explicitly as δ = (8c√κ L n^{1+σ} M)^{-1} with M = max{1, ((1/n) log(1/ε))^{1/2}}, to avoid ambiguity.","section":"Eq. (36) and surrounding text"},{"comment":"The proof defines K' as the α-shrinkage of K and then separately assigns R' = r(ε)√(n/μ); since R' = (1−α)R, these two statements determine α from R. The ordering of the choices (R, α, R') should be clarified, e.g., by choosing R' = r(ε)√(n/μ) first and then setting α = 1 − R'/R, which is consistent with the interval condition on R.","section":"Section 4.2.2, paragraph before Eq (55)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious contribution to the analysis of the Gibbs sampler, and the two gaps identified above appear repairable: the concentration-bound application in (79) admits a simple fix, and the scaling reduction to L=1 is standard and would resolve the α and L-dependence questions. I therefore recommend major revision rather than rejection. The paper is honest about the relationship to Ascolani et al. and does not overclaim. No issues of attribution or novelty are apparent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, you should know: the paper gives a polynomial mixing time bound for Gibbs sampling from log-smooth strongly log-concave distributions, using a new isoperimetric inequality. It is a genuine technical advance, but the headline mixing time is dominated by the concurrent linear-in-n result of Ascolani, Lavenant, and Zanella, which the authors themselves cite. So the practical value of the main theorem is modest; the isoperimetric lemma is the more interesting piece.\n\nThe paper does well in its structure and use of existing tools. Lemma 1.2, the cube tiling isoperimetric inequality for log-concave measures, is genuinely new as far as I can tell. The idea of using local uniformity of smooth f to transfer Laddha-Vempala's uniform cube isoperimetry to a non-uniform measure is clever and worth developing. The proof is self-contained, uses standard results (Lovász-Simonovits, Dwivedi et al., Lee-Vempala) appropriately, and I see no circularity or fitting.\n\nThe soft spots are localized but real. First, Theorem 1.1 states the bound as 'tau is no more than ...' which is backwards; it should be 'at least'. That is a typo but it will confuse readers. Second, in Lemma 3.2 the displayed equality has a missing factor of 1/n; the conclusion is right if you insert it, but as written it is wrong. Third, the stress-test concern about Eq. (79) is valid: the concentration bound (57) is applied to the cube union C2, which need not lie inside the ball K. The step Pi(I) > Pi(C2) - epsilon is unsupported as written. That said, the gap is easily repaired by applying (57) to C2 ∩ S1, which is inside K, giving the same lower bound Pi(I) ≥ (1/2)Pi(S1) - epsilon. So this is a minor revision, not a fatal flaw. I should also note the paper does not explicitly say the theorem is for the lazy chain, though the proof uses laziness; that is fine up to a constant factor but should be stated.\n\nOverall, the paper deserves a serious referee. The isoperimetric lemma is a real contribution, and the proof strategy may be useful even if the final n-dependence is not competitive. I would send it to peer review, with the expectation that the author tightens Eq. (79), fixes the typographical issues, and clarifies the lazy-chain framing. If those are addressed, it is publishable as a technical result.","headline":"A new isoperimetric proof of rapid mixing for Gibbs sampling, worth refereeing despite being dominated by a concurrent linear-in-n bound and having a few localized, repairable gaps.","tokens_in":19558,"tokens_out":8801,"would_cite":false,"duration_ms":69620,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J22","60D05","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that lazy Gibbs sampling on log-smooth log-concave targets is rapidly mixing, with an explicit $\\tilde{O}(\\kappa^2 n^{7.5})$ iteration bound from an $M$-warm start.","keywords":["Gibbs sampler","coordinate hit-and-run","log-concave sampling","mixing time","conductance","isoperimetric inequality","log-smooth","strongly log-concave"],"falsifier":"For a concrete strongly log-concave family such as an anisotropic Gaussian with a chosen condition number $\\kappa$, compute the maximum variation of $f$ over every axis-aligned cube of the side length $\\delta$ defined in Eq. (36) that intersects the mode-centered ball $K$; if for any $n$ this variation exceeds $\\log(6/5)$, the paper's Fact 4.1 fails on that configuration and the proof of Lemma 1.2 cannot proceed.","tokens_in":18500,"feed_emoji":"🎲","tokens_out":15105,"duration_ms":130217,"temperature":0.7,"pith_summary":"This paper proves a polynomial upper bound on how long the Gibbs sampler—the Markov chain that at each step picks one coordinate at random and resamples it from its conditional distribution—needs to run before it is close to a target distribution with density proportional to $e^{-f(x)}$, where $f$ is strongly convex with Lipschitz gradients. Starting from an $M$-warm initial distribution, the lazy sampler reaches total-variation error at most $\\gamma$ in at most $\\tilde{O}\\left(\\kappa^2 n^{7.5}\\left(\\max\\{1,\\sqrt{(1/n)\\log(2M/\\gamma)}\\}\\right)^2\\log(2M/\\gamma)\\right)$ iterations, with $\\kappa$ the ratio of the smoothness and strong-convexity constants of $f$. A curious reader should care because this shows that a simple, hyperparameter-free coordinate-resampling scheme mixes rapidly on a broad and practically common class of high-dimensional targets, complementing existing rapid-mixing results for the ball walk and hit-and-run. The paper's main technical contribution is an isoperimetric inequality for the target measure restricted to a mode-centered Euclidean ball, which controls the sampler's conductance and thereby the mixing time.","feed_headline":"Gibbs sampling proven rapid on log-concave targets","feed_subtitle":"Coordinate-by-coordinate resampling reaches a target error in O*(κ²n^7.5) steps, no step size to tune.","key_machinery":"The load-bearing mechanism is a cube-tiling isoperimetric argument. The proof embeds a mode-centered Euclidean ball in a grid of axis-aligned cubes of side $\\delta$, chosen so that a Taylor bound using the global smoothness constant $L$ guarantees $f$ varies by at most $\\log(6/5)$ across any cube; on such a cube the target density is nearly uniform. That near-uniformity lets the proof import a known isoperimetric inequality for the uniform distribution on a cube, apply it to each cube, and then correct for boundary cubes using a strongly log-concave isoperimetric inequality that bounds the measure of the internal boundary of the tiled set. The assembled inequality lower-bounds the conductance of the sampler, and the final iteration count follows from the conductance-to-mixing-time theorem.","core_discovery":"The central claim is Theorem 1.1: for a target density proportional to $e^{-f(x)}$ with $f$ $\\mu$-strongly convex and $L$-smooth, $\\kappa=L/\\mu$, and an $M$-warm start, the lazy Gibbs sampler satisfies $d_{\\mathrm{TV}}(\\pi_\\tau,\\pi)\\le\\gamma$ once $\\tau \\le C\\kappa^2 n^{7.5}\\log^2 n\\left(\\max\\{1,\\sqrt{(1/n)\\log(2M/\\gamma)}\\}\\right)^2\\log(2M/\\gamma)$ for a universal constant $C$. The engine behind this bound is Lemma 1.2, an axis-disjoint isoperimetric inequality: within a Euclidean ball centered at the mode and carrying at least $1-\\varepsilon$ of the target mass, any partition into two axis-disjoint sets $S_1,S_2$ and a remainder $S_3$ satisfies $\\Pi(S_3)\\ge\\Psi\\min\\{\\Pi(S_1)/(5-\\varepsilon),\\Pi(S_2)/(5-\\varepsilon)\\}$ with $\\Psi\\ge C/(\\kappa n^{2+3/4}\\log n\\max\\{1,\\sqrt{(1/n)\\log(1/\\varepsilon)}\\})$. Because the sampler cannot cross between axis-disjoint sets in one step, this inequality is exactly the kind of lower bound on escape probability that a conductance argument needs, and it yields the stated mixing time when combined with the standard s-conductance-to-mixing-time theorem.","pith_inferences":["The same local-near-uniformity trick would likely extend to blocked Gibbs samplers that resample groups of coordinates, since the argument only uses axis-disjointness and cube tiling; the paper does not pursue this extension.","The large gap between the $n^{7.5}$ exponent here and the linear-in-$n$ dependence reported for the contemporaneous entropy-contraction approach suggests the true worst-case mixing time of Gibbs sampling on this class is probably far below the bound proved here.","Because the bound depends only logarithmically on $M$ and $1/\\gamma$, the iteration budget degrades slowly when one asks for very accurate samples or starts far from the target; this practical feature is implicit in the bound but not highlighted.","A direct numerical study of the lazy Gibbs sampler on high-dimensional anisotropic Gaussians over a grid of $n$ and $\\kappa$ could estimate the empirical exponent of $n$ in the mixing time; if it is well below $7.5$, that would support the paper's suspicion that the bound is not tight."],"forward_implications":["For any log-smooth strongly log-concave target, lazy Gibbs sampling from a warm start is provably rapidly mixing, so the number of coordinate resamplings needed stays polynomial in the dimension and the condition number.","Because each iteration resamples a single coordinate from a known one-dimensional conditional, the bound converts directly into a polynomial total-work guarantee whenever those conditionals can be sampled efficiently.","The warm-start assumption is mild: the paper cites a procedure that computes a warm start for any log-concave target in $O(\\sqrt{n})$ iterations, so the overall algorithm remains polynomial even when initialized away from the target.","The axis-disjoint isoperimetric inequality applies to any log-smooth strongly log-concave measure and can be reused as a building block for other coordinate-constrained samplers, not only the specific chain analyzed here.","Under extra assumptions the dimension dependence improves: the paper notes that a sharper log-concave isoperimetric coefficient yields roughly $n^7$ for large $n$, and an isotropic-target variant gives an $n^{6.5}$ bound, so the proof framework supports refinements."],"supporting_citations":[{"why":"Supplies the cube isoperimetric lemma for the uniform distribution on an axis-aligned cube and the tiling strategy that the paper adapts to smooth log-concave densities.","marker":"[16]"},{"why":"Gives the concentration bound used to choose the mode-centered ball K so that it contains at least 1-epsilon of the target mass.","marker":"[25]"},{"why":"Provides the s-conductance inequality that converts the lower bound on conductance into the explicit iteration count in Theorem 1.1.","marker":"[21]"},{"why":"Supplies the strongly log-concave isoperimetric theorem used to lower-bound boundary measure in the bulk case of Lemma 1.2.","marker":"[27]"},{"why":"Establishes the inverse-square-root n-scaling of the cube isoperimetric coefficient, which sets the n-dependence of the final mixing-time exponent.","marker":"[26]"}],"fun_headline_variants":["Gibbs sampler mixes fast on log-smooth log-concave distributions","Coordinate-wise Gibbs sampling hits O*(κ²n^7.5) mixing time","No step size: Gibbs sampling has new mixing bound","Axis-disjoint isoperimetry yields Gibbs mixing time bound","Log-smooth log-concave: Gibbs sampler has explicit mixing time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each cube in the tiling is small enough that the target density is nearly uniform on it, a condition the proof checks only through a Taylor bound using the global smoothness constant; if the chosen cube size fails to keep the log-density variation within $\\log(6/5)$ on every cube that matters, the isoperimetric bound, and with it the mixing-time theorem, does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Gibbs sampler mixes fast on log-smooth log-concave distributions","Coordinate-wise Gibbs sampling hits O*(κ²n^7.5) mixing time","No step size: Gibbs sampling has new mixing bound","Axis-disjoint isoperimetry yields Gibbs mixing time bound","Log-smooth log-concave: Gibbs sampler has explicit mixing time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000924,"raw_usage":{"total_tokens":4005,"prompt_tokens":1031,"completion_tokens":2974,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":2882}},"tokens_in":647,"tokens_out":2974,"duration_ms":20472,"temperature":1.0,"reasoning_tokens":2882,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:10:34.075510+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a concrete strongly log-concave family such as an anisotropic Gaussian with a chosen condition number $\\kappa$, compute the maximum variation of $f$ over every axis-aligned cube of the side length $\\delta$ defined in Eq. (36) that intersects the mode-centered ball $K$; if for any $n$ this variation exceeds $\\log(6/5)$, the paper's Fact 4.1 fails on that configuration and the proof of Lemma 1.2 cannot proceed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the cube isoperimetric lemma for the uniform distribution on an axis-aligned cube and the tiling strategy that the paper adapts to smooth log-concave densities."},{"cited_title":"Wainwright, and Bin Yu","cited_arxiv_id":null,"evidence_quote":"Gives the concentration bound used to choose the mode-centered ball K so that it contains at least 1-epsilon of the target mass."},{"cited_title":"Lov´ asz and M","cited_arxiv_id":null,"evidence_quote":"Provides the s-conductance inequality that converts the lower bound on conductance into the explicit iteration count in Theorem 1.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the strongly log-concave isoperimetric theorem used to lower-bound boundary measure in the bulk case of Lemma 1.2."},{"cited_title":"On the $\\ell_0$ Isoperimetric Coefficient of Measurable Sets","cited_arxiv_id":"2312.00015","evidence_quote":"Establishes the inverse-square-root n-scaling of the cube isoperimetric coefficient, which sets the n-dependence of the final mixing-time exponent."}],"review_version":1}