PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Multidimensional Integration: VEGAS Enhanced

G. Peter Lepage

arXiv:2009.05112v4physics.comp-phhep-ph

TL;DR

High-dimensional integration needs adaptive methods because important structures can occupy tiny regions, while classic VEGAS is weaker on multiple peaks and diagonal structures. The paper introduces VEGAS+, combining adaptive importance sampling with adaptive stratified sampling, and reports stronger accuracy and efficiency across integration and Bayesian examples. It also identifies sample-size limits and cases where the VEGAS map is less useful.

  • Problem

    Classic VEGAS handles sharp peaks well but is less effective for integrands with multiple peaks or important diagonal structures.

  • Method

    VEGAS+ adds adaptive stratified sampling to classic VEGAS’s adaptive importance sampling and supports hybrid or preconditioned workflows using other integrators or external samples.

  • Results

    VEGAS+ was 2–19× more accurate than classic VEGAS, more than 100× more efficient when preconditioned in one example, and more than 10× as efficient as MCMC in two Bayesian analyses.

  • Takeaways & Limitations

    VEGAS+ is often effective for multiple peaks, diagonal structures, and small or moderate Bayesian problems, where the paper expects it to often outperform MCMC.

  • Takeaways & Limitations

    Adaptive stratified sampling requires at least Nst = 2 stratifications per direction, so its effect diminishes at higher dimensions; some integrands also make the VEGAS map of limited use.

Abstract

from arXiv · show

We describe a new algorithm, VEGAS+, for adaptive multidimensional Monte Carlo integration. The new algorithm adds a second adaptive strategy, adaptive stratified sampling, to the adaptive importance sampling that is the basis for its widely used predecessor VEGAS. Both VEGAS and VEGAS+ are effective for integrands with large peaks, but VEGAS+ can be much more effective for integrands with multiple peaks or other significant structures aligned with diagonals of the integration volume. We give examples where VEGAS+ is 2-19 times more accurate than VEGAS. We also show how to combine VEGAS+ with other integrators, such as the widely available MISER algorithm, to make new hybrid integrators. For a different kind of hybrid, we show how to use integrand samples, generated using MCMC or other methods, to optimize VEGAS+ before integrating. We give an example where preconditioned VEGAS+ is more than 100 times as efficient as VEGAS+ without preconditio ing. Finally, we give examples where VEGAS+ is more than 10 times as efficient as MCMC for Bayesian integrals with D = 3 and 21 parameters. We explain why VEGAS+ will often outperform MCMC for small and moderate sized problems.

1. Introduction

VEGAS is a widely used adaptive multidimensional Monte Carlo integrator, but it is less effective for multiple peaks and diagonal structures. VEGAS+ adds adaptive stratified sampling to address these cases and extends the workflow through hybrid and preconditioned approaches.

  • Motivation: Monte Carlo integration is well suited to high-dimensional problems because it requires few assumptions about the integrand and provides uncertainty estimates.Adaptive strategies are important when relevant structures occupy very small fractions of the integration volume.
  • Limitations of classic VEGAS: Classic VEGAS is effective for sharp peaks and non-separable integrands but performs less well on multiple peaks or diagonal structures.It remains substantially better than Simple Monte Carlo integration in those cases.
  • VEGAS+: VEGAS+ adds adaptive stratified sampling to classic VEGAS’s adaptive importance sampling, improving treatment of multiple peaks and diagonal structures given enough samples.The added strategy complements the original one rather than replacing it.
  • Illustrative result: 10 iterations of Nev = 10^7 samples each let VEGAS+ find a 20-dimensional sphere; 10 additional iterations estimate its volume to 0.05% accuracy.This example demonstrates the method’s ability to locate a structure occupying a tiny fraction of a high-dimensional volume.
  • Extensions and implementation: VEGAS+ can be combined with MISER or pre-optimized using MCMC-generated samples, while modern computers and parallel configuration support 10^8 or 10^9 evaluations.The paper also compares VEGAS+ with MCMC for Bayesian curve-fitting problems.

2. Adaptive Importance Sampling

Classic VEGAS remaps integration variables so uniform sampling concentrates near important regions, then iteratively refines that map. The approach reduces uncertainty for peaked and irregular integrands, but requires stabilization and sufficiently large sample counts.

  • Remapping the integration variable: VEGAS replaces the original integral with an equivalent y-space integral whose Jacobian is chosen to minimize Monte Carlo uncertainty.Uniform sampling in y-space is transformed into nonuniform sampling in x-space.
  • Monte Carlo estimates: The Monte Carlo estimate has the exact integral as its mean, while its standard deviation indicates the possible estimation error.The estimates become approximately Gaussian as the number of evaluations grows.
  • VEGAS map and importance sampling: VEGAS divides the x-axis into intervals whose widths define a map to uniform y-space intervals, concentrating samples where the integrand is largest.The Jacobian is a step function determined by interval widths, and smaller x-space intervals receive greater sampling density.
  • Iterative adaptation: The grid is refined iteratively by adjusting interval widths so the sampled averages d_i become more uniform across the integration region.The resulting Jacobian flattens peaks in y-space and reduces the standard deviation.
  • Stabilization: Early refinement can overreact because integrand information is poor, so VEGAS smooths and dampens updates to prevent destabilizing grid changes.Smoothing is especially important near large discontinuities, where samples can otherwise miss significant portions of a step.
  • Examples: With Nev = 10^4 evaluations, accuracy improves from 11% without a map to 0.3% at Ng = 100 and 0.1% around Ng = 700.For a harder D = 4 integral, uncertainty falls from 24% before adaptation to 0.34% after 10–20 iterations using Nev = 10^5 per iteration and α = 0.2.
  • Statistical limitations: Adequate Nev is integrand-dependent, and weighted iteration averages can retain a non-Gaussian bias that decreases like 1/Nev.For the cited second integral, the bias is about −0.05% at Nev = 10^5 and −0.03% at Nev = 2 × 10^5.

3. Adaptive Stratified Sampling

VEGAS+ enhances classic VEGAS by adaptively redistributing samples across hypercubes while retaining VEGAS’s adaptive importance-sampling map. This improves treatment of diagonal and multiple-peak structures, though high-dimensional gains depend on sufficient samples and stratification.

  • Adaptive sample allocation: Adaptive stratified sampling can reduce variance as the number of stratifications increases, potentially scaling as 1/N_st^D.Classic VEGAS uses equal sample allocation, whereas VEGAS+ allows hypercube-specific sample counts.
  • Adaptive sample allocation: VEGAS+ redistributes integrand samples across hypercubes after each iteration, optimizing sample allocation alongside the VEGAS map.The allocation uses hypercube-specific variance estimates and a damping parameter.
  • Diagonal and multiple-peak structures: 14–19× larger uncertainties occur for classic VEGAS than VEGAS+ at the same samples per iteration, and VEGAS+ remains reliable down to N_ev = 10^5.Classic VEGAS becomes unusable below N_ev = 3 × 10^6 because it can miss one or more peaks.
  • Diagonal and multiple-peak structures: VEGAS+ transfers samples from phantom peaks to real peaks, increasing the effective sample count for diagonal integrands.Classic VEGAS gives equal attention to real and phantom peaks, whereas VEGAS+ focuses mostly on the real peaks.
  • Limitations: Adaptive stratification has no effect below N_st = 2 per direction and activates only at N_ev ≥ 1.3 × 10^8 for D = 25.Consequently, the difference between VEGAS+ and classic VEGAS diminishes at sufficiently high dimensions.
  • High-dimensional behavior: Mixed stratification is significantly more accurate above D > 15 and remains useful through D = 50, while uniform stratification fails above D = 30.The mixed strategy helps the VEGAS map handle a sharp peak when adaptation has not fully converged.
  • High-dimensional behavior: In a two-peak diagonal example, mixed stratification preserves both peaks at higher dimensions, whereas uniform stratification loses them after changing from 2^13 hypercubes at D = 13 to one hypercube at D = 14.The partial stratification maintains 2^13 hypercubes for D > 13 and stabilizes map adaptation.
  • Limitations: The high-dimensional uncertainty growth in a diagonal example is driven by 2^D−2 phantom peaks; mixed stratification handles only 13 directions, leaving 2^D−15 phantoms.A single-peak example avoids phantom peaks and shows slowly growing uncertainty after the VEGAS map converges.

4. VEGAS+ Hybrids

VEGAS+ can be combined with MISER, MISER+, or preconditioning samples to address different integration structures. These hybrids improve accuracy in suitable settings, while VEGAS+ remains strongest overall in the reported tests.

  • Hybrid strategies: VEGAS+ generates an optimized map that can be paired with another adaptive integrator, replacing its own adaptive stratified sampling.The paper demonstrates this strategy with MISER and related hybrids.
  • MISER hybrids: 50–100×: MISER is less accurate than VEGAS+ for the axis-aligned four-dimensional integral.VEGAS+ combined with MISER+ is 7–38× more accurate than MISER+ alone.
  • MISER hybrids: 4–5×: MISER and MISER+ are more accurate for diagonal structures than for the preceding axis-aligned structure.For the diagonal case, VEGAS+ is 4–6× more accurate than MISER and 1.5–6× more accurate than MISER+.
  • Higher-dimensional tests: 500–1000× fewer integrand samples: VEGAS+ begins working reliably than MISER or MISER+ for the D = 8 axis-aligned integrand.At Nev = 10^6, VEGAS+ gives 0.03%-accurate estimates, while MISER and MISER+ are more than 500× less accurate for similar samples.
  • Preconditioned integrators: Preconditioning lets VEGAS+ find multiple narrow peaks reliably with Nev ≈ 10^4 to 10^5, compared with Nev ≈ 10^8 without preconditioning.By Nev = 10^6, preconditioned VEGAS+ gives 1%-accurate results.
  • Limitations: For the Hilbert-matrix Gaussian, neither TQs nor the VEGAS+TQs hybrid achieves errors below 50% with 12,000 samples when D ≥ 3.VEGAS+ gives errors below 1% for D = 3, showing a case where the VEGAS map is limited but standalone VEGAS+ remains effective.

5. Conclusions

The paper combines adaptive stratified sampling with VEGAS importance sampling and evaluates the resulting algorithm across hybrids, preconditioning, and Bayesian integration. VEGAS+ is broadly more accurate or efficient in the reported examples, while further exploration of hybrid options remains warranted.

  • Core contribution: VEGAS+ combines adaptive stratified sampling with classic VEGAS’s adaptive importance sampling.The added stratified strategy targets multiple peaks and diagonal structures.
  • Core contribution: 2–19×: VEGAS+ was more accurate than classic VEGAS across the paper’s examples.Its errors typically decreased faster than 1/√Nev as the number of integrand evaluations increased.
  • Hybrid integrators: VEGAS+ hybrids with other algorithms can be significantly more accurate than the original algorithms.The experiments specifically examine MISER and TQs combinations.
  • Preconditioning: More than 100× fewer integrand evaluations were needed by preconditioned VEGAS+ before reliable results appeared.The preconditioning samples can be generated separately, for example with MCMC.
  • Bayesian integration: More than 10×: VEGAS+ was more efficient than MCMC in Bayesian analyses with D = 3 and D = 21 parameters.The paper discusses why VEGAS+ is expected to often outperform MCMC for small and moderate-sized problems.

Appendix A. Sums and Feynman Diagrams

VEGAS+ is applied beyond ordinary integration to adaptive multidimensional summation and a finite-volume correction in lattice QCD. In the reported correction, it reaches lower uncertainty than classic VEGAS at the same sample count.

  • Adaptive summation: VEGAS+ can perform adaptive multidimensional summation as well as integration.The paper illustrates this capability through finite space-time volume corrections in lattice QCD simulations.
  • Lattice-QCD correction: The lattice-QCD correction is converted from a finite-volume sum into an ultraviolet-finite integral.The construction uses a box of side L = 5 fm and a change of variables involving k_μ = m_πz_μ/(1 − z_μ).
  • Numerical result: 0.5% errors: VEGAS+ achieves this uncertainty with Nev = 10^5 samples, compared with 1.0% for classic VEGAS.Using Nev = 10^3 gives 7.5% uncertainty, which the paper considers accurate enough for most practical applications.
  • Feynman-diagram application: The QED test integrates a tenth-order contribution to the muon’s magnetic moment over D = 9 Feynman parameters.The study considers light-by-light diagrams with vacuum-polarization insertions for muon and electron loop particles.

Appendix B. Bayesian Curve Fitting

The appendix applies VEGAS+ to Bayesian curve fitting, where narrow posterior peaks and correlated parameters make adaptive integration useful. It reports accurate parameter estimates, compares VEGAS+ with MCMC and classic VEGAS, and shows further gains from preconditioning and tailored stratification.

  • VEGAS+ evaluates Bayesian integrals by targeting narrow high peaks and can be faster than MCMC for small or medium-sized problems.
  • The example fits a straight line while modeling unreliable error estimates with a two-Gaussian probability density.
  • VEGAS+ with 28,000 integrand samples estimates three model parameters to 0.06–0.3% accuracy.
  • Ignoring correlations between VEGAS+ errors makes the parameter results 2.5–12× less accurate.
  • Using more than 5× as many integrand samples, MCMC produces parameter estimates that are 3–4× less accurate than VEGAS+.
  • For 21-variable integrals, VEGAS+ achieves better than 1% errors, while MCMC with 10× as many samples is 7–13× less accurate.
  • In the 21-dimensional example, default VEGAS+ stratification leaves it equivalent to classic VEGAS because available samples permit only one hypercube.
  • Preconditioning with approximate parameter means and covariances improves VEGAS+ results by factors of order 1.5–4 by aligning the error ellipse with integration axes.
Loading 2009.05112v4…