Source-linked AI summary
Sequential Monte Carlo Sampling of Feasible Regions Represented by R-Functions
Sinan Yıldırım, Sergei Kucherenko
TL;DR
Sampling and estimating volumes becomes inefficient when feasible regions occupy only a small fraction of a bounding domain. The paper combines continuous signed R-functions with SMC intermediate targets to guide particles toward feasibility, then reports variance reductions over rejection sampling and region-only SMC, with CPU-adjusted gains depending on the setting.
Problem
Direct rejection sampling uses binary feasibility information and may require many samples when the feasible fraction of a bounding domain is small.
Source: §1 · p. 1Method
Results
Continuous constraint-violation information substantially improves the statistical efficiency of SMC-based feasible-region sampling, particularly for small feasible fractions.
Source: §6 · p. 17Takeaways & Limitations
The R-function-informed SMC concentrates particles in the feasible region earlier and yields lower-dispersion final volume estimates than region-only SMC in the reported comparisons.
Source: §6 · p. 16The study uses random-walk MH and α = 1; gradient-based moves and other operator parameter values are left for future investigation.
Source: §6 · p. 17
Abstract
from arXiv · showhide
Feasible-region sampling and volume estimation become increasingly inefficient when constraints define only a small fraction of a convenient bounding domain. We combine R-functions, which encode compound feasibility as a continuous signed field, with sequential Monte Carlo (SMC) samplers. The proposed construction exploits not only the sign of the R-function, which determines exact feasibility, but also its continuous negative values outside the feasible set, which provide graded information on constraint violation. Logistic intermediate distributions use this information to guide particles progressively towards feasibility, while the final target distribution remains uniform on the feasible region. Experiments on intersections and unions, including disconnected cases of hyperballs, show substantial variance reductions relative to direct rejection sampling, with the statistical advantage generally increasing as the feasible fraction decreases. For sufficiently small feasible regions, these advantages persist even after accounting for computational cost. To isolate the benefit of continuous R-function information, we also compare the proposed method with an SMC sampler with a region-only (RO) construction that uses the same sequential particle machinery but retains only binary feasible/infeasible information. We demonstrate that the R-function-informed SMC method concentrates particles in the feasible region earlier and produces lower-variance volume estimates than RO.
1 Introduction
Direct rejection sampling becomes inefficient when the feasible fraction of a bounding domain is small. The paper uses continuous signed R-function information in SMC intermediate targets to guide sampling while retaining a uniform final target on the feasible region.
1 Introduction
- When the feasible fraction is small, direct rejection sampling may require very many samples for adequate representation or accurate volume estimates.Rejection sampling uses only binary membership information, and its efficiency deteriorates in proportion to the feasible fraction.Source: §1 · p. 1
- Logistic intermediate targets use continuous R-function values to guide particles toward feasibility, while the final target remains uniform on the feasible region.The SMC normalising-constant ratio also provides an estimate of feasible volume.Source: §1 · p. 2
- R-function-informed SMC uses continuous signed constraint information to define intermediate targets for feasible-region sampling and volume estimation.The sign determines feasibility, while negative values outside the feasible region provide graded information about constraint violation.Source: §1 · pp. 1–2
- The method is evaluated on intersections and disconnected unions of hyperballs over increasing dimensions, with attention to small feasible fractions and particle evolution.The experiments assess accuracy and computational cost as well as particle evolution.Source: §1 · p. 2
2 R-Functions: Mathematical Background
R-functions combine constraint functions through R-conjunction and R-disjunction so that the sign of one continuous scalar function represents compound feasibility. In this work, negative values outside the feasible region supply graded violation information, but do not generally measure distance to its boundary.
2 R-Functions: Mathematical Background
- Constraint functions use the positive-inside convention: ϕ_i(x) ≥ 0 exactly when constraint i is satisfied.The constraint functions are continuous functions on X.Source: §2 · p. 2
- R-functions combine constraint primitives through R-conjunction and R-disjunction, reproducing logical operations through the sign of a single scalar function.The feasible region is represented by the nonnegative level set of the resulting function.Source: §2 · pp. 2–3
- The operators ∧ and ∨ encode conjunction and disjunction, and this work uses the symmetric operator family with α = 1.The passage introduces the symmetric families ∧α and ∨α for −1 < α ≤ 1.Source: §2 · p. 2
- The example region is defined by ϕ1 ≥ 0 or both ϕ2 ≥ 0 and ϕ3 ≥ 0, with the R-function formed using disjunction and conjunction operators.Its two disconnected lobes meet at the origin; the figure contrasts R-function values across the bounding region with the positive-only view.Source: §2 · p. 3
- Continuous negative R-function values outside the feasible set provide graded violation information, but generally are not geometric distances to the boundary.Their scale depends on the constraint primitives and R-function construction; the SMC method exploits this information.Source: §2 · p. 3
3 Rejection sampling and volume estimation
Rejection sampling estimates feasible volume by sampling uniformly from a known-volume bounding region and using feasibility information. Its efficiency is governed by the inverse feasible fraction, which can grow rapidly with dimension.
3 Rejection sampling and volume estimation
- The bounding region A contains the feasible region R, has known volume A, and the feasible volume V is unknown.The setup assumes A ≥ V > 0.Source: §3 · p. 3
- Figure 1 displays R-function values over the bounding region and, separately, the positive region with infeasible locations shown in white.The two views contrast the full signed field with a feasibility-only display.Source: Figure 1 · p. 4
- The standard rejection-sampling estimator is based on independent uniform samples from A, with feasibility determining which samples are retained.The supplied passage identifies this as indicator importance sampling.Source: §3 · p. 4
- Rejection sampling efficiency is governed by the inverse feasible fraction A/V, which can increase rapidly with dimension.When A/V is large, more samples are needed for a given relative accuracy, and a finite rare-event experiment may contain no feasible points.Source: §3 · p. 4
4 Sequential Monte Carlo Samplers
SMC bridges an easily sampled initial distribution to a uniform target on the feasible region, producing particles and an estimate of the normalising-constant ratio. The section describes R-function-informed intermediate targets and a region-only alternative that retains only binary feasibility information.
4 Sequential Monte Carlo Samplers
- SMC reweights, resamples, and moves particles with invariant MCMC kernels as it bridges to a uniform feasible-region target, returning particles and an unbiased normalising-constant ratio estimate.The unbiasedness result assumes a fixed target sequence, compatible supports, independent initial particles, conditionally unbiased resampling, and invariant mutation kernels.Source: §4 · pp. 4–5
4.1 R-function-informed SMC samplers
- Continuous negative R-function values grade constraint violation, guiding particles through logistic intermediate targets while preserving a uniform final target on the feasible region.These values do not generally represent geometric distance to the boundary; Figure 2 illustrates the logistic targets concentrating around feasibility as inverse temperature increases.Source: §4.1 · pp. 6–7, Figure 2 · p. 7
4.2 Region-only SMC samplers
- The region-only construction uses binary feasibility alone, progressively suppressing infeasible points while assigning equal weight to all feasible points.At its final setting, its target is uniform on the feasible region; unlike the R-function-informed construction, it does not distinguish infeasible points by their constraint-violation scores.Source: §4.2 · p. 7
5 Numerical experiments
The experiments benchmark R-function-informed SMC against rejection/importance sampling and region-only SMC on hyperball intersections and unions, then examine sampling accuracy and particle evolution.
5 Numerical experiments
- The experiments compare SMC, RO-lin, RO-geo, and IS on hyperball intersections and unions across dimensions, including disconnected union configurations.RO-geo is an oracle benchmark whose schedule requires knowing the feasible volume.Source: §5 · p. 8, §5.1 · p. 9, §5.2 · p. 10
- The study uses K = 16 stages, N = 10000 particles, one Gaussian random-walk MCMC rejuvenation move per stage, and 1000 independent runs per feasible region.The RO-geo schedule balances successive normalising-constant ratios but is an oracle because it requires knowing V.Source: §5 · pp. 8–9
- Variance gains compare estimator variances, while CPU-adjusted gains account for computation time; the nominal K = 16 cost reference is heuristic rather than an exact equivalence.The reported CPU-adjusted gain is the more direct computational-efficiency comparison.Source: §5 · p. 9, §5.1 · p. 9
5.1 Intersection of two hyperballs
- SMC’s variance advantage over IS grows with dimension and is stronger for smaller unequal-radius intersections, becoming CPU-adjusted advantageous at higher dimensions; both RO variants remain below a CPU-adjusted gain of 1.At lower dimensions, SMC’s variance gain does not fully offset the added cost of sequential stages.Source: §5.1 · p. 10, Figure 3 · p. 10
5.2 Union of two hyperballs
- SMC’s advantage over IS generally increases as the feasible fraction decreases in union experiments; RO-geo remains below a CPU-adjusted gain of 1, while RO-lin exceeds 1 in one rare configuration.The isolated RO-lin gain warrants caution when nearly all volume estimates are zero.Source: §5.2 · pp. 10, 12, Figure 4 · p. 11
5.3 Additional results
- Across the additional results, comparisons on intersections and unions show an advantage for R-function-informed SMC.Sampling accuracy and particle evolution are examined in the following analyses.Source: §5.3 · p. 12
5.3.1 Sampling accuracy
- In three rare d = 5 configurations, SMC has no zero-volume estimates across 1000 runs, while IS returns zero in 999, 999, and 1000 runs, respectively; both RO methods also return zero in most runs.Component occupancy estimates from SMC are more reliable than those from RO-lin and RO-geo; the RO methods complete far fewer runs for small radius pairs.Source: §5.3.1 · pp. 12, 14, Table 1 · p. 12, Figure 6 · p. 14
5.3.2 Effect of R-function information on particle evolution
- For the three-dimensional union with (r1, r2) = (1, 0.5), R-function-informed SMC concentrates particles in the feasible region earlier and produces less variable volume estimates than region-only alternatives.Figure 7 illustrates particle evolution for SMC and RO-lin in one run; Figure 8 summarizes 1000 independent replications.Source: Figure 7 · p. 15, §5.3.2 · p. 16, Figure 8 · p. 16
6 Conclusions
R-function-informed SMC reduces volume-estimate variance relative to rejection sampling, with stronger gains when feasible regions are smaller. Against region-only SMC, it concentrates particles in feasible regions earlier and yields lower-dispersion estimates, though schedule differences limit attribution; CPU-adjusted performance varies by setting.
6 Conclusions
- Variance reductions over direct rejection sampling are strongest as the feasible fraction decreases, while CPU-adjusted performance depends on the experimental setting.The R-function-informed approach produces accurate volume estimates across the examples considered.Source: §6 · pp. 16–17
- Compared with region-only SMC using linear and geometric schedules, the R-function-informed method concentrates particles earlier and produces lower-dispersion final volume estimates.Schedule differences prevent attributing the entire gain solely to graded R-function information.Source: §6 · p. 16
- The framework can be extended to constrained optimisation by including the objective function in intermediate distributions, but that extension is separate work.The objective f(x) is to be maximised.Source: §6 · p. 17
- The study used α = 1 for R-conjunction and R-disjunction operators; effects of α ∈ (−1, 1) remain to be investigated.The authors also identify gradient-based MCMC moves and differentiable intermediate distributions as possible improvements.Source: §6 · p. 17
A Analytic volumes of two balls
The appendix gives analytic volume expressions for two-ball intersections and unions, using spherical-cap volumes in partial-overlap cases. It also describes an incomplete-beta representation for cap volumes.
A Analytic volumes of two balls
- The appendix presents formulas for the volume of a ball and for the union and intersection volumes of two balls.The two-ball cases distinguish disjoint, containment, and partial overlap.Source: A Analytic volumes of two balls · p. 19
- In the partial-overlap case, the two-ball volume expressions use spherical-cap volumes with heights determined from the radii and center separation.The text identifies the cap heights as h_i = r_i − a_i.Source: A Analytic volumes of two balls · p. 19
- For cap heights up to the radius, a substitution expresses the cross-sectional integral using the regularised incomplete beta function; larger caps use complementary volume by symmetry.The beta-function representation is stated for 0 ≤ h ≤ r, with the complementary-volume case for r < h ≤ 2r.Source: A Analytic volumes of two balls · p. 19
B Bootstrap uncertainty for the reported gains
The appendix tables supplement point estimates with bootstrap intervals calculated from sample variances and unpaired run resampling.
B Bootstrap uncertainty for the reported gains
- The supplementary tables report percentile bootstrap intervals based on 5,000 sorted bootstrap values, using sample-variance and unpaired run-resampling procedures.The passage introduces the interval notation but does not provide its endpoints.Source: B Bootstrap uncertainty for the… · p. 19
B.1 Intersection experiments
Table 2 reports point estimates and pointwise 95% percentile bootstrap intervals for intersection variance gains.
B.1 Intersection experiments
- Table 2 covers intersection variance gains, reporting point estimates, pointwise 95% percentile bootstrap intervals, and the percentage of zero-variance bootstrap resamples.The caption does not state numerical results.Source: Table 2 · p. 19
B.2 Union experiments
The union experiments report variance-gain point estimates with pointwise 95% percentile bootstrap intervals. The table also defines z* as the percentage of zero-variance bootstrap resamples.
B.2 Union experiments
- Table 3 reports union variance-gain point estimates and pointwise 95% percentile bootstrap intervals.Source: Table 3 · p. 20
- The intervals are pointwise 95% percentile bootstrap intervals.Source: Table 3 · p. 20
- z* denotes the percentage of bootstrap resamples with zero variance.Source: Table 3 · p. 20