PaperlayerView exact revision on arXiv

Source-linked AI summary

A statistical test for Nested Sampling algorithms

Johannes Buchner

arXiv:1407.5459v3stat.CO

TL;DR

Nested sampling requires uniformly drawing points above successively higher likelihood thresholds, but constrained samplers can omit relevant prior volume and bias integration. This paper develops the Shrinkage Test to detect such shrinkage errors, applies it to existing and new algorithms, and finds that RADFRIENDS is robust but less efficient than MULTINEST.

  • Problem

    Nested sampling depends on constrained draws that preserve the expected prior-volume shrinkage, yet algorithms can exclude relevant volume and produce biased integration.

  • Method

    The paper develops the Shrinkage Test and applies it to constrained-sampling algorithms, including MULTINEST and RADFRIENDS.

  • Results

    MULTINEST fails the Shrinkage Test in the 7- and 20-dimensional cases, whereas RADFRIENDS passes it and solves the LogGamma problem and others correctly.

  • Takeaways & Limitations

    RADFRIENDS offers a simple, robust baseline that handles multimodal and peculiar shapes without tuning parameters or additional input information.

  • Takeaways & Limitations

    RADFRIENDS is one or two orders of magnitude less efficient than MULTINEST and is not useful above 10 dimensions except for fast test problems.

Abstract

from arXiv · show

Nested sampling is an iterative integration procedure that shrinks the prior volume towards higher likelihoods by removing a "live" point at a time. A replacement point is drawn uniformly from the prior above an ever-increasing likelihood threshold. Thus, the problem of drawing from a space above a certain likelihood value arises naturally in nested sampling, making algorithms that solve this problem a key ingredient to the nested sampling framework. If the drawn points are distributed uniformly, the removal of a point shrinks the volume in a well-understood way, and the integration of nested sampling is unbiased. In this work, I develop a statistical test to check whether this is the case. This "Shrinkage Test" is useful to verify nested sampling algorithms in a controlled environment. I apply the shrinkage test to a test-problem, and show that some existing algorithms fail to pass it due to over-optimisation. I then demonstrate that a simple algorithm can be constructed which is robust against this type of problem. This RADFRIENDS algorithm is, however, inefficient in comparison to MULTINEST.

1 Introduction to Nested Sampling

Nested sampling computes the prior-weighted likelihood integral by progressively shrinking prior volume above increasing likelihood thresholds. Its correctness depends on uniformly drawing constrained replacements, whose shrinkage follows a known statistical distribution.

  • The marginal likelihood is the prior-weighted integral of the likelihood over parameter space.
  • Nested sampling tracks prior volume above a likelihood threshold and sums layer contributions to approximate the integral.The method can handle high-dimensional, multimodal, and otherwise peculiar likelihood shapes.
  • Uniform constrained draws make the one-dimensional shrinkage factor follow S ∼ Beta(N, 1), with expectation ⟨S⟩ = (N + 1)^-1.Repeated replacement yields an average prior volume of approximately (N + 1)^-1 per step.
  • Each iteration removes the lowest-likelihood live point, adds its prior-volume contribution, and replaces it with a point above the threshold.
  • Constrained sampling is difficult for peculiar shapes, multimodality, tiny volumes, and higher dimensions, while slow likelihoods limit evaluations.

2 Constrained sampling

Constrained sampling methods use either local moves from live points or direct draws from estimated regions, but both face efficiency or coverage risks. The most severe failure excludes relevant prior volume, biasing likelihood draws and motivating the Shrinkage Test.

  • Constrained sampling draws from the prior above a likelihood threshold using local steps or region sampling.Both approaches exploit the existing live points inside the permitted sub-volume.
  • Local-step methods can sample only near the starting point when proposals are concentrated or too few steps are taken.Nearest-neighbour distances provide a possible check in geometrically simple problems, but become less useful in higher dimensions.
  • MULTINEST encloses live points in hyperellipses and draws directly inside the estimated regions.This region-sampling approach guarantees uniform draws within the constructed sampling region.
  • Region sampling can waste evaluations by including below-threshold space, especially as high-dimensional volumes grow rapidly.MULTINEST is reported to work inefficiently beyond approximately 20 dimensions.
  • The more severe error is excluding relevant volume, which can bias likelihood draws and cause incorrect integration.The paper introduces the Shrinkage Test to detect this problem in constructed test problems.

3 The Shrinkage Test

The Shrinkage Test compares observed prior-volume shrinkage with the distribution expected under uniform constrained sampling. It uses analytically tractable test problems and can quantify discrepancies visually or with a KS test.

  • Test rationale: The test checks whether each nested-sampling step removes the expected fraction of prior volume rather than shrinking too quickly.Accelerated shrinkage can result from inadvertently missing part of the sampling region.
  • Test construction: Test problems specify the constraint contour and its volume so observed volume ratios can be compared with the theoretical expectation N/(N + 1).Hyper-rectangular contours provide the simplest construction, exemplified by the hyper-pyramid likelihood.
  • Expected distribution: For the hyper-pyramid problem, the shrinkage border S has expected cumulative distribution p(< S) = 1 − (1 − S)^(d·N).The underlying volume ratio follows a beta distribution with shape parameters α = N and β = 1.
  • Evaluation: The test runs constrained sampling for many iterations, computes removed volume S, and compares its empirical distribution with the expected one.Discrepancies can be assessed visually or quantified with the Kolmogorov-Smirnov test.
  • Test scope: The framework supports hyper-cube, multi-scale, hyperelliptical, and multimodal contours across chosen dimensions.The example configuration uses s = 100 and σ_i = 1 in the hyper-cube case.

4 Application of the Shrinkage Test

The Shrinkage Test evaluates MULTINEST with 400 and 1000 live points across 2, 7, and 20 dimensions. It finds agreement in 2 dimensions but excessive shrinkage in 7 and 20 dimensions.

  • Experimental setup: MULTINEST was tested with 400 and 1000 live points, 30% sampling efficiency, and up to 100 modes.The analysis used version 3.4 without importance nested sampling.
  • Results: In 2 dimensions, MULTINEST’s observed and theoretical shrinkage distributions match.The comparison used the hyper-pyramid likelihood and 10,000 stored iterations per sequence.
  • Results: In 7 and 20 dimensions, shrinkage S is higher than expected, indicating that too much prior space is cut away.The discrepancy means MULTINEST under-estimates the volume and samples from a smaller region for this test problem.

5 Robustness against accelerated shrinking

The proposed rejection approach uses the existing uniformly distributed live points to define a neighborhood-based sampling region. Its construction is designed to avoid shrinking too quickly, while giving up efficiency in high dimensions.

  • Robustness principle: The method defines the sampling region as points within distance R of at least one live point.R is chosen conservatively so every live point could be sampled even when the point determining the maximum distance is omitted.

6 The RADFRIENDS algorithm

RADFRIENDS constructs a conservative neighborhood around live points using bootstrap-like distance estimation, then samples within that region while correcting for clustered coverage. Its geometry adapts to live-point configuration and supports multiple modes, but can require many live points between separated modes.

  • Region construction: RADFRIENDS estimates R with bootstrap-like resampling and uses it to define a region around the live points.The estimate leaves points out and ensures omitted points could still be sampled.
  • Sampling procedure: The algorithm’s draw_constrained procedure computes R and repeatedly generates candidates within the resulting constrained region.The algorithm is presented as a method for drawing a point above the likelihood threshold Lmin.
  • Sampling procedure: Two draw_near variants are equivalent in likelihood evaluations and generated-sample properties; the direct-neighborhood variant accepts candidates with probability 1/m.Here m is the number of live points within distance R, preventing preference for clustered regions.
  • Distance norms: The Euclidean and supremum norms define RadFriends and SupFriends variants, respectively.The norm determines the distance geometry used for the sampling region.
  • Emergent geometry: Increasing the number of live points narrows the sampling region, while separated or clustered points make it expand or tighten accordingly.The region adapts to irregular shapes and can represent multiple modes without assuming a fixed shape.
  • Efficiency boundary: For 20 well-separated modes, 800 live points are needed to safely avoid inefficient sampling between modes.This follows the stated example of 20 modes with 40 live points per mode.

7 Shrinkage test results

The Shrinkage Test compares empirical shrinkage distributions with the theoretical distribution to assess constrained-sampling correctness. It detects failures in MULTINEST and fixed-proposal MCMC, while RADFRIENDS and adaptive MCMC pass but may be less efficient.

  • Test setup: The Shrinkage Test evaluates algorithms by comparing empirical shrinkage with the theoretical distribution on a hyper-pyramid likelihood.The study uses 400 live points; KS-test p-values below 0.05 indicate results inconsistent with the expected distribution.
  • RADFRIENDS: RADFRIENDS can handle multiple modes by clustering points, provided separated regions are excluded during sampling.With 50 bootstrap iterations, the probability of leaving out all points in a sub-cluster is 0.5 for k = 10, 0.005 for k = 20, and 5×10^-7 for k = 40.
  • MCMC comparison: The fixed Gaussian MCMC proposal fails because it samples too close to existing live points, while adaptive MCMC passes the distance distribution test.Using only 10 or 20 adaptive-MCMC steps gives low p-values in 7 and 20 dimensions; at least 50 steps yields 2% efficiency.
  • Algorithm comparison: In 7 and 20 dimensions, MULTINEST shows shrinkage deviations, whereas rejection sampling and RADFRIENDS produce the correct distribution.The deviations indicate that MULTINEST does not reproduce the expected shrinkage law in these higher-dimensional cases.
  • Efficiency: MULTINEST uses one or up to two orders of magnitude fewer likelihood evaluations than RADFRIENDS/SUPFRIENDS.This efficiency advantage contrasts with the shrinkage deviations observed for MULTINEST in 7 and 20 dimensions.

8 Test problems

The paper evaluates RADFRIENDS and MULTINEST on two multimodal test problems: the 18-peak eggbox and a LogGamma–Gaussian problem with asymmetric heavy tails. Both algorithms solve the eggbox problem, while higher-dimensional LogGamma tests expose overestimation and efficiency differences.

  • Evaluation: The evaluation runs each algorithm 10 times and records the average integral value, estimator variance, and reported statistical uncertainty.The comparisons include RADFRIENDS, MULTINEST, and MULTINEST with Importance Nested Sampling.
  • Eggbox problem: The two-dimensional eggbox problem contains 18 distinct peaks and is designed to test extreme multi-modality.Its likelihood is defined on a unit square by ln L = (2 + cos(5π · x1) · cos(5π · x2))^5.
  • Eggbox problem: Both MULTINEST and RADFRIENDS integrate the eggbox problem successfully, while MULTINEST uses the fewest likelihood evaluations.RADFRIENDS can separate modes with more live points, which makes it more efficient in that setting.
  • LogGamma problem: The LogGamma problem combines well-separated peaks with asymmetric heavy-tailed distributions and is tested in d = 2 and d = 10 dimensions.Its true integral value is ln Ztrue = 0.
  • LogGamma problem: In two dimensions, all algorithms solve the LogGamma problem within the constraints, but Importance Nested Sampling in MULTINEST claims approximately fivefold higher accuracy than achieved.This overstatement had been noted previously.
  • LogGamma problem: In ten dimensions, MULTINEST overestimates the integral without Importance Nested Sampling, whereas RADFRIENDS and SUPFRIENDS compute the evidence correctly.Importance Nested Sampling mitigates MULTINEST’s overestimation; SUPFRIENDS requires one order of magnitude more evaluations than RADFRIENDS.

9 Conclusions

The paper introduces the Shrinkage Test to detect sampling errors in nested-sampling algorithms and presents RADFRIENDS as a robust alternative. RADFRIENDS passes the test and solves the evaluated problems correctly, but is substantially less efficient than MULTINEST and limited at higher dimensions.

  • Contributions: The Shrinkage Test detects algorithms that shrink prior volume faster than expected, potentially excluding relevant parameter space and producing incorrect integrals.It is limited to geometrically simple contours but can test high-dimensional, multimodal, and multiple-scale problems.
  • Results: MULTINEST fails the Shrinkage Test in the 7- and 20-dimensional cases, indicating that relevant prior volume is left out.This error may also contribute to incorrect integration of the LogGamma problem.
  • Results: RADFRIENDS passes the Shrinkage Test, solves the LogGamma problem and other tests correctly, and handles multimodal and peculiar shapes without tuning parameters or additional input information.The reported properties support its use as a robust constrained-sampling algorithm.
  • Results: All algorithms give correct results for the eggbox problem, while MULTINEST uses the fewest likelihood evaluations.RADFRIENDS becomes more efficient with more live points because its modes are better separated.
  • Limitations: RADFRIENDS is one or two orders of magnitude less efficient than MULTINEST by likelihood evaluations and is not useful above 10 dimensions.For low-dimensional problems, it can compete with MULTINEST.
  • Practical implications: The proposed algorithm is simple to implement and analytically understandable, making it a safe baseline for low-dimensional problems.The paper also suggests robustifying ellipsoidal methods by leaving out live points and expanding regions until they are included.

10 Future Work

Future work focuses on improving region-based constrained sampling, especially in high dimensions, and extending RADFRIENDS and its distance-measure choices. The paper also proposes machine-learning approaches for learning the boundary between retained and discarded points.

  • Open problems: Region-sampling constrained algorithms require further study, especially in the high-dimensional regime.These methods construct sampling regions from live points.
  • Possible methods: Support Vector Machines are suggested as a possible way to learn the boundary between live points and already discarded points.This is presented as a potential direction for improving region construction.
  • Algorithm extensions: Future work includes applying Importance Nested Sampling to RADFRIENDS and studying distance measures and alternative norms for higher-dimensional problems.The paper also calls for further improvements and study of RADFRIENDS.
Loading 1407.5459v3…