CHRRT: boosting coordinate hit-and-run with rounding by thinning

Abstract

Thinning is a sub-sampling technique to reduce the memory footprint of Markov chain Monte Carlo. Despite being commonly used, thinning is rarely considered efficient. For sampling convex polytopes uniformly, a highly relevant use-case in systems biology, we here demonstrate that thinning generally boosts computational and, thereby, sampling efficiencies of the widely used Coordinate Hit-and-Run with Rounding (CHRR) algorithm. We benchmark CHRR with thinning (CHRRT) with simplices and constrained-based metabolic networks with up to thousands of dimensions. With appropriate thinning, CHRRT offers a substantial increase in computational efficiency compared to unthinned CHRR, in our examples of up to three orders of magnitude, as measured by the effective sample size per time (ESS/t). Our experiments reveal that the performance gain of CHRRT by optimal thinning grows substantially with polytope (effective model) dimension. Based on our experiments, we provide practically useful advice for tuning thinning to efficient and effective use of compute resources. Besides allocating computational resources optimally to permit sampling convex polytopes uniformly to convergence in a fraction of time, exploiting thinning unlocks investigating hitherto intractable models under limited computational budgets. CHRRT thereby paves the way to keep pace with progressing model sizes within the existing constraint-based reconstruction and analysis (COBRA) tool set. Sampling and evaluation pipelines are available at https://jugit.fz-juelich.de/IBG-1/ModSim/fluxomics/chrrt.