Source-linked AI summary
PolyChord: nested sampling for cosmology
W. J. Handley, M. P. Hobson, A. N. Lasenby
TL;DR
Growing cosmological datasets have increased demand for Bayesian inference, but existing methods struggle to compute evidences in high-dimensional spaces and exploit parameter-speed hierarchies. PolyChord addresses these challenges with nested sampling, slice sampling, clustering, and fast-slow parameter support; on a toy Gaussian problem, it scales more favorably with dimensionality than MultiNest, while retaining important low-dimensional limitations.
Problem
High-dimensional cosmological inference requires evidence calculations that standard MCMC methods cannot perform on a usable timescale, while MultiNest struggles with dimensionality and parameter-speed hierarchies.
Method
PolyChord combines nested sampling with slice sampling under hard likelihood constraints, covariance-based whitening, semi-independent mode evolution, parallelisation, and optional fast-slow parameter handling.
Results
PolyChord at worst scales as NL ∼O(D3), whereas MultiNest develops exponential scaling in higher dimensions on a D-dimensional Gaussian likelihood.
Takeaways & Limitations
PolyChord provides a nested-sampling approach for high-dimensional spaces with parameter-speed hierarchies and separate posterior modes.
Takeaways & Limitations
MultiNest performs better in low dimensions and navigates pronounced curving degeneracies more effectively, while PolyChord may require very long chains for such contours.
Abstract
from arXiv · showhide
PolyChord is a novel nested sampling algorithm tailored for high dimensional parameter spaces. In addition, it can fully exploit a hierarchy of parameter speeds such as is found in CosmoMC and CAMB. It utilises slice sampling at each iteration to sample within the hard likelihood constraint of nested sampling. It can identify and evolve separate modes of a posterior semi-independently and is parallelised using openMPI. PolyChord is available for download at: http://ccpforge.cse.rl.ac.uk/gf/project/polychord/
1 INTRODUCTION
Growing cosmological data has increased the use of Bayesian inference, but conventional methods struggle to compute evidences in high-dimensional settings. PolyChord is presented as an algorithm addressing high dimensionality and parameter-speed hierarchies.
- Bayesian inference combines parameter estimation with model comparison, the latter requiring high-dimensional likelihood integration over the prior.
- Metropolis-Hastings methods cannot compute cosmological evidences on a usable timescale, limiting Bayesian model comparison.
- Nested Sampling computes evidences and posteriors simultaneously and has been implemented in the widely adopted MultiNest algorithm.
- Modern cosmological likelihoods have many parameters with different calculation speeds, while MultiNest struggles with high dimensionality and cannot exploit that separation.
- PolyChord aims to sample high-dimensional spaces across a hierarchy of parameter speeds.
- The letter provides a brief algorithm overview and reports that PolyChord is already used in several cosmological applications.
2 W.J. Handley et. al
Nested Sampling estimates evidence by iteratively shrinking prior volume while replacing the lowest-likelihood live point. Dead points also provide posterior samples, and convergence can be assessed from the remaining live-point mass.
- Nested Sampling begins with live points drawn uniformly from the prior and repeatedly replaces the lowest-likelihood point under a stricter likelihood constraint.
- The enclosed prior fraction X_i is estimated as the lowest of n volumes drawn uniformly from [0, X_i−1].
- Evidence is calculated by quadrature from the likelihood and shrinking prior-volume sequence.
- Convergence is reached when the posterior mass remaining in the live points is a small fraction of the estimated evidence.
- The pool of dead points can be converted into posterior samples for parameter estimation.
4 SAMPLING WITHIN AN ISO-LIKELIHOOD CONTOUR
Sampling inside an iso-likelihood contour is the difficult step in nested sampling. Existing approaches have dimensionality, tuning, gradient, or degeneracy limitations, motivating slice sampling for PolyChord.
- The hard step is drawing from the prior subject to L > L_i, and algorithmic variants differ mainly in how they sample within this constraint.
- MultiNest uses live-point ellipsoids and rejection sampling, which has exponential scaling with dimensionality despite effectiveness for few parameters.
- Galilean Sampling uses reflection-based MCMC chains but requires parameter tuning and likelihood gradients.
- Diffusive nested sampling uses MCMC to explore mixed nested distributions and handles multimodal and degenerate posteriors, but has multiple tuning parameters.
- Slice sampling generates points uniformly within the one-dimensional likelihood slice after stepping out and contracting bounds when proposals fall outside it.
- Coordinate-wise slice sampling can struggle with degenerate distributions, which PolyChord aims to address.
5 THE PolyChord ALGORITHM
PolyChord combines slice sampling, whitening, and clustering to sample high-dimensional, degenerate, and multi-modal posteriors. Its clustering procedure evolves modes semi-independently, while whitening remains limited for strongly curved degeneracies.
- Slice sampling: PolyChord uses slice sampling informed by live-point geometry to handle degeneracies in high-dimensional likelihood contours.The algorithm whitens the contour using a covariance-based linear transformation before sampling along directions.
- Slice sampling: The whitening transformation uses the covariance matrix of live and inter-chain points, preserving uniform sampling under affine transformations.The Cholesky decomposition provides the transformation from the unit hypercube to the sampling space.
- Limitations: Whitening is dynamically adaptive and requires no tuning parameters, but it is ineffective for pronounced curving degeneracies.This is the stated scope boundary of the whitening procedure.
- Multi-modal posteriors: PolyChord recognizes clusters and evolves them semi-independently to address multi-modal posteriors that can be mishandled by global whitening.Far-separated modes can make the global covariance misleading, while insufficient live-point resolution can cause modes to die out or be missed.
- Multi-modal posteriors: Cluster recognition can use alternative algorithms, but checking too frequently risks substantial computational overhead.The paper states that checking every ∼O(nlive) iterations is sufficient in practice.
PolyChord 3
PolyChord identifies clusters with a k-nearest-neighbours procedure and controls spawning using estimated cluster volumes. This preserves global lowest-likelihood removal while treating modes as separate entities during evolution.
- Cluster recognition: Clusters are recognized by iterating k-nearest-neighbours connectivity until the cluster decomposition becomes stable.Sub-clusters are recursively processed when identified.
- Cluster evolution: The key innovation is to evolve identified clusters semi-independently rather than spawning solely according to their live-point counts.The method retains global information while treating clusters as separate entities.
- Cluster evolution: Cluster-specific whitening uses the covariance matrix of live points within each cluster when spawning from an existing live point.This addresses the misleading geometry produced by combining separated modes.
- Cluster evolution: Spawning is controlled by estimated cluster volume fractions because live-point counts can fluctuate and cause evidence biases or cluster death.The global lowest-likelihood point is still removed at each iteration.
- Cluster evolution: When spawning within a cluster, the new point is assigned according to its nearest cluster, and early cluster identification does not compromise evidence consistency.The paper explicitly states that premature identification is harmless for the evidence calculation.
- Parallel implementation: PolyChord uses an openMPI master-slave structure in which one master organizes live points and nprocs −1 slaves find new ones.The master sends a live point and Cholesky decomposition to a slave, which returns a new live point and inter-chain points.
4 W.J. Handley et. al
PolyChord’s slice-sampling workflow whitens the constrained region, samples along random directions, and repeats the process across dimensions. Its parallelization is nearly linear below the number of live points, while fast-slow parameter hierarchies are automatically exploited.
- Slice sampling: Whitening transforms degenerate contours to dimensions ∼O(1) in all directions before slice sampling begins.The transformation is defined by the inverse Cholesky decomposition of the live points’ covariance matrix.
- Slice sampling: Starting from a random live point, PolyChord performs one-dimensional slice sampling along random directions with w = 1 in sampling space.Repeating the procedure ∼O(ndims) times produces a decorrelated uniformly sampled point.
- Parallelization: PolyChord parallelizes nearly linearly when nprocs < nlive.The paper states that this condition is sufficient for most astronomical applications.
- Parallelization: The algorithm keeps slaves continuously active but discards returned points that are unusable for the current likelihood contour.Discard probability grows with the volume ratio between contours, limiting useful parallelism when too many slaves are used.
- Fast-slow parameters: The sampling-space transformation exploits fast-slow parameter hierarchies because the upper-triangular Cholesky transform mixes each parameter only with faster parameters.This makes the hierarchy easy to use in cosmological likelihood calculations.
6 PolyChord IN ACTION
On a Gaussian likelihood, PolyChord achieves accurate evidence estimates while scaling more favorably than MultiNest as dimensionality increases, although MultiNest remains stronger in low dimensions and on pronounced curving degeneracies.
- Gaussian likelihood: The evaluation sets nlive = 25D and defines convergence when posterior mass in live points is 10−2 of the total calculated evidence.These settings keep the evidence error constant with dimensionality.
- Gaussian likelihood: PolyChord produces consistent evidence and error estimates with an error ∼0.4 log units, while MultiNest estimates remain within this accuracy.The comparison uses importance nested sampling for MultiNest.
- Gaussian likelihood: PolyChord requires at worst NL ∼O(D3) likelihood evaluations, whereas MultiNest develops exponential scaling at higher dimensionalities.Figure 4 measures evaluations needed to reach convergence as a function of D.
- Gaussian likelihood: MultiNest wins in low dimensions and navigates pronounced curving degeneracies effectively, whereas PolyChord requires very long chains for such contours.This identifies a scope boundary for PolyChord’s scaling advantage.
- CosmoChord: PolyChord’s strength is exploiting fast-slow parameter hierarchies common in cosmological applications.The paper connects this capability to its CosmoChord implementation within CosmoMC.
PolyChord 5
The PolyChord implementation was made available for download and applied in multiple cosmological applications, including a 37-parameter reconstruction with four slow, 19 semi-slow, and 14 fast parameters.
- PolyChord 5: The CosmoChord implementation is available to download from the link at the end of the paper.
- PolyChord 5: CosmoChord has been effectively implemented in multiple cosmological applications in the latest Planck paper.The implementation applied PolyChord within a cosmological analysis.
- PolyChord 5: One application was a 37-parameter reconstruction comprising 4 slow, 19 semi-slow, and 14 fast parameters.This demonstrates use across a hierarchy of parameter speeds.
7 CONCLUSIONS
The paper introduces PolyChord as a nested sampling algorithm for high-dimensional parameter spaces, combining speed-hierarchy exploitation, constrained slice sampling, mode handling, and openMPI parallelisation.
- 7 CONCLUSIONS: PolyChord is a novel nested sampling algorithm tailored for high-dimensional parameter spaces.
- 7 CONCLUSIONS: It exploits parameter-speed hierarchies, uses slice sampling within hard likelihood constraints, evolves separate posterior modes semi-independently, and supports openMPI parallelisation.
DOWNLOAD LINK
PolyChord is available for download from the project link provided at the end of the paper.
- DOWNLOAD LINK: PolyChord is available for download from the project website.