REVIEW 4 major objections 4 minor 16 references
Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities
T0 review · 4 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read This paper claims that gradient and curvature information can be grafted onto the Hit-&-Run proposal mechanism—while preserving its guarantee of feasible proposals—to make MCMC sampling of non-uniform densities on linearly constrained domai
desk verdict Real algorithmic contribution with a large benchmark, but the convergence proof has a fixable typo (largest vs smallest ratio) and the smMALA reduction claim is not mathematically right; worth refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the elliptical Hit-&-Run (EHR) proposal: it draws a uniform direction u on the sphere, maps it through the Cholesky factor of a covariance to obtain v=L^T u, truncates the step length at the first intersection with the polytope boundary, and produces a feasible proposal. Lemma 3.1 derives the EHR proposal density in closed form. Gradient information enters by shifting the proposal base point to x+ε̂∇logφ(x) (LHR), where ε̂ is a clipped step size chosen so the base point stays feasible; curvature enters by setting the covariance to ε²G(x)^{-1} (smHR), and smLHR does both. The fact that the proposal density is positive and continuous on the whole polytope is what carries
What would settle it
Take a 2D triangle, place x near one slanted side, and set the log-density gradient pointing toward the opposite vertex. Compute κ from Eq. (8) as the largest positive ratio (b_j - a_j^T x)/(a_j^T ∇logφ(x)) and check whether x+(κ/2)∇logφ(x) lies in the triangle. If it falls outside, the feasibility premise of Theorem 3.2 is violated for an explicit state, and the proof of convergence for the printed LHR algorithm would not apply.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that a Gaussian proposal can be decomposed into a direction and a magnitude, and Hit-&-Run already samples exactly this way; therefore gradient and curvature information can be injected into a feasible-direction proposal without giving up the feasibility guarantee. The Langevin Hit-&-Run (LHR) clips the gradient drift so the proposal base point remains inside the polytope and then runs Hit-&-Run from that point. The simplified manifold versions replace the spherical direction with an ellipsoidal direction derived from a metric tensor, giving the elliptical Hit-&-Run proposal; smLHR combines the clipped natural-gradient drift with that ellipsoidal di
Load-bearing premise
The convergence proof for LHR and smLHR assumes the clipped gradient step x+ε̂∇logφ(x) stays inside the polytope, which requires κ to be the distance to the nearest constraint in the gradient direction; as printed, Eq. (8) selects the largest positive ratio rather than the smallest, so the proposal base point can leave the feasible region.
Editorial extensions
If this is right
- If the central claim holds, constrained Bayesian inverse problems with expensive likelihood evaluations can be sampled with fewer wasted proposals, because every proposed state lies inside the feasible set.
- The curvature-aware samplers smHR and smLHR are the only methods tested that converge within budget on the 9-dimensional non-stationary metabolic-flux problem, suggesting that curvature information is necessary for strongly correlated, linearly constrained targets.
- The paper's δ-parametrization, which controls step size through the metric's regularization rather than an explicit scale, makes the second-order methods easier to tune, though the paper leaves the reason for its empirical success unexplained.
- When the target is close to uniform, the gain from gradient information shrinks and the plain feasible sampler remains competitive, so the methods do not lose much in the regime where boundary constraints dominate.
Reading between the lines
- If the clipping definition is corrected to measure the nearest constraint in the gradient direction, the feasibility proof becomes airtight; testing both definitions on a simple triangle would separate a proof fix from a substantive design choice.
- The same direction/magnitude decomposition could be applied to other proposal mechanisms, such as Hamiltonian trajectories, by replacing the Gaussian magnitude with the truncated step distribution, yielding feasible curvature-informed proposals beyond the Langevin family.
- Because the Hessian-based metric is local and automatic differentiation supplies it cheaply, these samplers could be combined with adaptive metric estimation to remove manual δ tuning, making them plug-in samplers for black-box constrained densities.
- The benchmark's scale axis suggests a practical selection rule: use a curvature-aware sampler when the high-probability region approaches a boundary, and a plain feasible sampler when the distribution is nearly uniform.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes three Hit-and-Run-style MCMC samplers for densities constrained to polytopes: LHR, smHR, and smLHR. LHR adds a clipped log-density gradient drift to the standard HR proposal; smHR uses an elliptical HR proposal with a curvature-based metric; smLHR combines both. The authors derive the elliptical HR proposal density, state a total-variation convergence theorem under positivity/continuity assumptions, and evaluate the methods on 2240 synthetic constrained problems and two 13C-MFA posterior sampling problems. They report that the new samplers often outperform RWMH, MALA, smMALA, Dikin walk, MAPLA, and HR, and they provide code.
Significance. If the results hold, the paper offers practically useful samplers for Bayesian inverse problems with polytope constraints. The benchmark is unusually broad, the real-world 13C-MFA examples are nontrivial, and the code is publicly available. The derivation of the elliptical HR density and the overall MH construction are sound. However, the theoretical convergence proof as written contains a concrete error in the clipping construction, and the empirical tuning protocol uses the ground-truth L1 error on the test problems. These are load-bearing issues for the central claims, though both appear fixable.
major comments (4)
- [§3.1, Eq. (8); Appendix A, Proof of Thm. 3.2] Eq. (8) defines a vector of ratios and then states 'we choose κ as the largest positive entry.' The largest positive ratio is not the first constraint hit along the drift direction; the feasible step is the smallest positive ratio. With the largest κ, the asserted inclusion x+κ∇logφ(x)∈P is false in general, so the proof's use of convexity to conclude x+ε̂∇logφ(x)∈P collapses. The surrounding text says 'closest constraint,' which suggests the intended definition is the smallest positive entry. This is a typo-level fix, but as printed the proof of Thm. 3.2 is invalid. Please correct Eq. (8) to use the minimum and ensure the code implements the minimum.
- [§5.1, Evaluation] The experimental protocol tunes the step size (and for manifold samplers the metric and δ) for each algorithm on each problem by grid search against the ground-truth L1 error computed from separate large MCMC simulations, and then reports the best L1 and minESS for that tuned setting. This is an information leak: the test metric is used as the selection criterion. The reported relative performances are therefore optimistic upper bounds and may not reflect what a user would obtain without access to ground truth. I recommend reporting results under a data-independent tuning rule (e.g., maximum acceptance rate, or a short pilot run) or showing sensitivity to the tuning criterion.
- [§3.2.1; §5.1] The text states that the smHR/smLHR metric is s.p.d. 'by construction in Eq. (14) and for δ large enough.' Eq. (14) takes the element-wise square root of the absolute values of H^T H and adds δI; this matrix is not guaranteed to be positive definite for arbitrary δ. The paper's fallback to the diagonal when Cholesky fails changes the proposal covariance discontinuously, and the convergence theorem's assumption that Σ is s.p.d. is then not ensured by the stated construction. Please state explicitly that the metric used in practice is the diagonal fallback or impose a condition on δ that guarantees positive definiteness.
- [§3.1, unconstrained limit] The paper motivates LHR/smLHR by the fact that HR with a χ_d step distribution becomes a Gaussian proposal as γmax→∞, and then claims that LHR simplifies to MALA in this limit. However, the experiments use a half-normal step distribution moment-matched to χ_d, not the χ_d itself. For the implemented samplers the unconstrained-limit proposal is not exactly Gaussian, so the 'recovers MALA' statement is only approximate for the benchmarked algorithms. Please clarify this distinction between the theoretical limit (χ_d) and the implementation (half-normal).
minor comments (4)
- [Eq. (8)] The same symbol κ is used for the vector of ratios and for the scalar clipping length. Use a different symbol for the vector to avoid confusion.
- [Appendix A] The proof header says 'Proof of Thm. 3.1' but the result is Lemma 3.1; similarly 'Thm. A.1' appears where 'Lemma A.1' is meant. Also Assumption A2 states p is positive on R_+, while Lemma A.1 says 'positive and continuous on R'; please align the domains.
- [Figure 5 and text] The captions of Fig. 5 and Fig. 6 refer to 'Eq.(14) Eq.(15)' but the text introduces only the squared Hessian metric (Eq. (13)) and the scaled squared Hessian metric (Eq. (14)). It seems Eq. (15) should be Eq. (13), or an equation number is missing.
- [§3.2.1, δ-parametrization] The δ-parametrization sets δ=λ^{-2} and fixes ε=1. In the convergence proof, the assumption 'for δ large enough' is stated, but in the λ-parametrization, λ large corresponds to δ small. Please make the dependence of the theoretical condition on λ explicit.
Circularity Check
No circularity: MH filter guarantees target invariance; performance tuning is standard hyperparameter selection; the clipping flaw in Eq. (8) is a correctness issue, not a circular one.
full rationale
The paper's central claims are not circular. The samplers are ordinary MH algorithms: the acceptance filter Eq. (2) enforces stationarity with respect to π, and the convergence proof (Thm. 3.2, Sec. A) invokes standard irreducibility/aperiodicity results rather than any assertion that already assumes the target. The Hessian/scaled-Hessian metrics (Eqs. 13–14) and the δ/λ step-size parametrization are tunable proposal ingredients, not quantities fitted to the benchmark and then reported as predictions; the grid search over step sizes is symmetric across algorithms. Self-citations (hopsy, CHRR, 13CFLUX) are used as ground-truth generation or likelihood/gradient engines, i.e., as external tools, not as load-bearing steps in the derivation. The one substantive concern is a correctness flaw, not circularity: Eq. (8) says 'we choose κ as the largest positive entry' from the ratio vector, while the feasible step along a ray is the smallest positive ratio; the proof of Thm. 3.2 states 'x+κ∇logφ(x)∈P', which can fail if κ is the largest. The surrounding text's 'closest constraint' suggests the intended quantity is the minimum, so the theorem is likely repairable, but as printed the proof's premise is false. This does not make the derivation an input into itself. Score 0.
Assumptions & free parameters
free parameters (4)
- step size ε =
grid-searched per problem (log-uniform)
- metric regularization δ (λ) =
grid-searched per problem
- clipping fraction 1/2 =
0.5
- half-normal step distribution =
moment-matched to χ_d
assumptions (5)
- domain assumption P is convex (A1)
- domain assumption Step distribution p is positive and continuous on R+ (A2)
- domain assumption Target π is finite and twice continuously differentiable on P (A3)
- domain assumption Metric G(x) is symmetric positive definite for every x∈P
- ad hoc to paper x + κ∇logφ(x) ∈ P for the chosen κ
invented entities (1)
-
scaled squared Hessian metric Gsc (Eq. 14)
Cite this review
Pith. "Pith review of Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities." pith.science (2026). https://pith.science/paper/KYQZEBIK
@misc{pith2026260214616,
author = {Pith},
title = {Pith review of: Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities},
year = {2026},
howpublished = {\url{https://pith.science/paper/KYQZEBIK}},
note = {Machine review of arXiv:2602.14616}
}
read the original abstract
Markov chain Monte Carlo (MCMC) sampling of densities restricted to linearly constrained domains is an important task arising in Bayesian treatment of inverse problems in the natural sciences. While efficient algorithms for uniform polytope sampling exist, much less work has dealt with more complex constrained densities. In particular, gradient information as used in unconstrained MCMC is not necessarily helpful in the constrained case, where the gradient may push the proposal's density out of the polytope. In this work, we propose a novel constrained sampling algorithm, which combines strengths of higher-order information, like the target's log-density's gradients and curvature, with the Hit-&-Run proposal, a simple mechanism which guarantees the generation of feasible proposals, fulfilling the linear constraints. Our extensive experiments demonstrate improved sampling efficiency on complex constrained densities over various constrained and unconstrained samplers.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[2]
Gabriel Gellner, Kevin McCann, and Alan Hastings
ISSN: 2640-3498. Gabriel Gellner, Kevin McCann, and Alan Hastings. Stable diverse food webs become more common when interactions are more biologically constrained.Proceedings of the National Academy of Sciences, 120(31):2017,
2017
-
[4]
ground truth
Recalling our earlier definitions, we have that γ=∥L −⊤(y−x)∥ 2, thus recovering Eq. (11). Next, we fill out the technical details of our sketched convergence argument from Sec. 3.3. Let P(x,y) :=α(y|x)q(y|x) + (1−r(x))δ x(y),withr(x) := Z P α(z|x)q(z|x) dz(19) be theMetropolis kernel, whereδ x(y)is the Dirac measure onx,α(y|x)is the MH filter (cf. Eq. (2...
2004
-
[5]
(23), which bounds the polytope within the[0,1] d box: cos(θ)·x i −sin(θ)·x j ≤0for any two differenti, j= 1,
PolytopesTheconeis constructed as a simplex with tilted sides and a scaled constraint in Eq. (23), which bounds the polytope within the[0,1] d box: cos(θ)·x i −sin(θ)·x j ≤0for any two differenti, j= 1, . . . , d,(22) dX i=1 xi ≤ cos(θ) sin(θ) + 1.(23) Thediamondis constructed as a [0,1] d whose sides are also tilted and scaled such that the resulting par...
2015
-
[6]
Gauss(µ= 0.5) Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32RWMH0.13 0.067 0.074 0.09 0.1160.414 0.279 0.272 0.164 0.2260.467 0.219 0.263 0.247 0.3180.118 0.047 0.077 0.101 0.1590.246 0.2 0.24 0.29 0.3680.297 0.211 0.247 0.29 0.3690.308 0.374 0.291 0.253 0.2590.471 0....
arXiv 2010
-
[8]
Gauss(µ= 0.5)10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.018 0.024 0.015 0.044 0.101 0.226 0.240.305 0.274 0.272 0.278 0.255 0.217 0.2960.29 0.257 0.249 0.278 0.344 0.366 0.3380.008 0.008 0.017 0.053 0.132 0.244 0.239MALA0.04 0.038 0.025 0.074 0.1...
-
[9]
SamplerTargetσ Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.103 0.147 0.221 0.283 0.366 0.38 0.3820.135 0.162 0.28 0.323 0.385 0.352 0.3420.317 0.407 0.332 0.187 0.248 0.29 0.3020.366 0.326 0.284 0.304 0.35 0...
-
[10]
Gauss(µ= 0.5) Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32RWMH0.208 0.162 0.181 0.226 0.2560.485 0.468 0.478 0.47 0.4770.513 0.464 0.499 0.616 0.6160.183 0.143 0.198 0.251 0.310.303 0.325 0.493 0.649 0.7250.389 0.395 0.512 0.685 0.760.528 0.613 0.522 0.566 0.5440.62...
arXiv 1940
-
[11]
Gauss(µ= 0.5) Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ RWMH0.01 0.057 0.102 0.2130.031 0.106 0.413 0.5350.033 0.248 0.435 0.4960.013 0.078 0.119 0.1920.198 0.343 0.287 0.2470.124 0.377 0.312 0.3180.185 0.334 0.272 0.3980.149 0.337 0.366 0...
arXiv 1920
Show all 16 references
-
[12]
Gauss(µ= 0.5)10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.034 0.035 0.033 0.097 0.212 0.490.5470.452 0.473 0.49 0.464 0.471 0.425 0.5550.453 0.437 0.447 0.486 0.6550.66...
-
[13]
SamplerTargetσ Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.174 0.268 0.446 0.541 0.648 0.6850.730.223 0.293 0.466 0.646 0.7240.749 0.7380.48 0.524 0.57 0.404 0.544 ...
-
[14]
Gauss(µ= 0.5) Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32 2 4 8 16 32RWMH0.039 0.046 0.111 0.221 0.3180.036 0.042 0.123 0.247 0.3350.045 0.048 0.076 0.162 0.250.04 0.043 0.041 0.045 0.0490.042 0.05...
-
[15]
Gauss(µ= 0.5) Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ 9◦ 19◦ 45◦ 90◦ RWMH0.401 0.095 0.047 0.0460.404 0.141 0.042 0.040.314 0.047 0.05 0.0540.044 0.039 0.044 0.0470.047 0.0...
-
[16]
Gauss(µ= 0.5)10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.116 0.144 0.188 0.171 0.15 0.135 0.1240.136 0.098 0.092 0.114 0.207 0.225 0.2250.077 0.084 0.113 0.131 0.137 0...
-
[17]
SamplerTargetσ Disc(µ= 0.5) Cigar(µ= 0.5) Bowtie Funnel10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 10−2 10−1.510−1 10−0.5 100 100.5 101 RWMH0.042 0.047 0.049 0.051 0.048 0.048 0.0490.045 0.047 0.048 0.051 0.052...
-
[2004]
Gareth O
ISBN 978-1-4419-1939-7 978-1-4757-4145-2. Gareth O. Roberts and Jeffrey S. Rosenthal. General state space Markov chains and MCMC algorithms.Probability Surveys, 1(none):20–71, January
1939
-
[2024]
10 Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities Apostolos Chalkis, Vissarion Fisikopoulos, Marios Papachristou, and Elias Tsigaridas
arXiv:2402.10797 [cs]. 10 Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities Apostolos Chalkis, Vissarion Fisikopoulos, Marios Papachristou, and Elias Tsigaridas. Truncated log-concave sampling with reflective hamiltonian monte carlo. 49(2):1–25,
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.