Source-linked AI summary
Beyond Effective Sample Size: Effective Number of Proposals for Adaptive Importance Sampling
Ali Mousavi, Victor Elvira
TL;DR
Population-based adaptive importance sampling lacks a proposal-level diagnostic for distinguishing balanced weights from genuinely diverse proposal contributions. This letter introduces ENP, which measures non-redundant proposal contributions and detects proposal collapse missed by ESS while supporting targeted rejuvenation.
Problem
Weight-based ESS diagnostics do not describe proposal-component arrangement or how many non-redundant proposals contribute to population-based AIS.
Method
ENP combines each proposal’s normalized weight with similarity-based, target-weighted redundancy among its generated samples.
Results
ENP detects proposal collapse and duplication missed by ESS, satisfies effective-number properties, and supports targeted rejuvenation with nearly full coverage, lowest MSE, and 1.15 average triggers.
Takeaways & Limitations
ENP provides a proposal-level signal for identifying empirical redundancy and guiding more targeted proposal rejuvenation in population-based AIS.
Abstract
from arXiv · showhide
Population-based adaptive importance sampling (AIS) methods use a set of proposal densities to approximate complex target distributions. Their performance is commonly assessed through effective sample size (ESS) and related weight-based diagnostics, which measure the concentration of normalized importance weights. However, a large ESS only indicates that the normalized sample weights are not strongly concentrated; it does not describe how the proposal components are arranged in the sampling space. In population-based AIS, several proposal components may generate samples in the same region of the target, so the sample weights can appear well balanced even though the effective number of distinct proposal components is small. This letter introduces the effective number of proposals (ENP), a similarity-aware proposal-level diagnostic for population-based AIS. ENP combines the total normalized weight assigned to each proposal with a redundancy measure computed from similarities among target-weighted samples, estimating the number of non-redundant empirical proposal contributions to the approximation. We establish basic effective-number properties and show that ENP detects proposal collapse and duplication missed by standard ESS. We also illustrate its use as a targeted feedback signal for proposal rejuvenation.
I. INTRODUCTION
Population-based AIS can exhibit proposal overlap or collapse even when ESS indicates balanced normalized weights. The letter introduces ENP, a similarity-aware proposal-level diagnostic that measures non-redundant proposal contributions and supports proposal rejuvenation.
- Motivation: Population-based AIS quality depends on both importance-weight distribution and proposal-population configuration, which ESS alone does not fully characterize.Different proposal arrangements can yield comparable ESS values, including populations with strongly overlapping components and lost diversity.
- Proposed diagnostic: ENP combines each proposal’s total normalized weight with similarity-based redundancy computed from its weighted samples.The diagnostic estimates the effective number of non-redundant proposal components contributing to the approximation.
- Theoretical properties: ENP is established through basic effective-number properties for non-redundant, collapsed, and duplicated proposal configurations.These configurations define the proposal-level cases used to assess ENP’s behavior.
- Practical use: ENP detects proposal redundancy missed by ESS and provides a useful signal for proposal rejuvenation.Its purpose is to reveal proposal collapse or excessive empirical redundancy not exposed by classical weight-based diagnostics.
II. BACKGROUND · A. Deterministic-Mixture Importance Sampling
The background introduces deterministic-mixture importance sampling, its proposal-and-sample notation, and the weight-based ESS diagnostics used for comparison. It defines the normalized and stacked importance-weight representations for the population samples.
- II. BACKGROUND: The background section introduces notation for deterministic-mixture importance sampling and the weight-based ESS diagnostics used for comparison.
- A. Deterministic-Mixture Importance Sampling: At each iteration, a population-based adaptive importance sampler maintains N proposal densities q1(x), . . . , qN(x).
- A. Deterministic-Mixture Importance Sampling: Each proposal qn(x) generates K samples xn,k ∼qn(x), producing a total sample size S = NK.
- A. Deterministic-Mixture Importance Sampling: Deterministic-mixture importance sampling is also known as balance-heuristic weighting in the MIS literature.
- A. Deterministic-Mixture Importance Sampling: The method specifies a mixture denominator and an unnormalized importance weight for each sample xn,k.
- A. Deterministic-Mixture Importance Sampling: The resulting normalized weights provide the sample-level weighting representation used in the method.
- A. Deterministic-Mixture Importance Sampling: Weights are also represented in stacked form as w = (w1, . . . , wS), with each index i corresponding to a proposal-sample pair (n, k).
B. Weight-Based ESS Diagnostics · III. EFFECTIVE NUMBER OF PROPOSALS
Weight-based ESS diagnostics characterize the concentration of normalized importance weights but omit sample locations, proposal labels, and inter-sample similarities. ENP extends effective-number assessment to quantify non-redundant proposal contributions and provide adaptation feedback.
- B. Weight-Based ESS Diagnostics: Classical empirical ESS is defined from normalized importance weights to assess the effective number of weighted samples.
- B. Weight-Based ESS Diagnostics: ESS is large when normalized weights are nearly uniform and small when a few samples dominate, making it useful for detecting weight degeneracy.
- B. Weight-Based ESS Diagnostics: Because ESS does not use sample locations, proposal labels, or sample similarities, it cannot explicitly characterize proposal overlap or geometric arrangement.
- B. Weight-Based ESS Diagnostics: Perplexity and inverse-maximum-weight ESS provide alternative effective-number interpretations based on the normalized weight vector.
- B. Weight-Based ESS Diagnostics: Within Rényi/Hill-type effective-number families, classical ESS, perplexity, and inverse-maximum-weight ESS correspond to different orders of a shared weight-based principle.
- III. EFFECTIVE NUMBER OF PROPOSALS: ENP quantifies how many non-redundant proposal components effectively contribute to the AIS approximation rather than only counting weighted samples.
- III. EFFECTIVE NUMBER OF PROPOSALS: ENP combines a similarity-aware proposal redundancy measure with a redundancy-corrected effective number.
- III. EFFECTIVE NUMBER OF PROPOSALS: By identifying redundant proposal populations, ENP can serve as a feedback signal for adaptation.
A. Similarity-Aware Proposal Redundancy
ENP measures empirical, target-weighted redundancy by comparing each proposal’s local neighborhood mass with the corresponding mass in the full sample population. Its proposal-level index is near one for distinct contributions and increases as samples overlap with other proposals.
- Similarity-aware redundancy: ENP compares whole-population weighted mass around each sample with mass generated by its own proposal to measure empirical, target-weighted redundancy.Similarities are computed among target-weighted samples rather than through analytical distances between proposal densities.
- Similarity-aware redundancy: A symmetric similarity matrix Z measures pairwise sample similarity, making neighborhood mass larger near many high-weight samples and smaller for relatively isolated samples.The matrix satisfies Zii = 1 and has entries in [0, 1].
- Similarity-aware redundancy: The samplewise redundancy ratio contrasts global neighborhood mass with the mass attributable only to proposal n.Rn,k ≈1 indicates a neighborhood mainly explained by proposal n, whereas Rn,k > 1 indicates overlap with samples from other proposals.
- Similarity-aware redundancy: The proposal redundancy index is a weighted power mean of samplewise ratios, with values close to one indicating mostly distinct contributions and larger values indicating stronger overlap.For q = 1 it becomes a weighted geometric mean, while q = 2 gives a weighted arithmetic mean.
B. Redundancy-Corrected ENP
The redundancy-corrected ENP family combines effective-number order with a redundancy-diversity adjustment that penalizes overlapping proposals. The letter focuses on its order-2 collision-type member, whose bounded redundancy keeps ENP within [1, N].
- Parameterization: The family uses order r for effective-number weighting and order q for the redundancy-diversity term ρ(q)_n.Larger r values emphasize dominant proposal weights, while the redundancy term penalizes overlap with the population.
- Order-2 ENP: The letter focuses on the order-2 member, which defines a collision-type ENP.This member belongs to the broader family of redundancy-corrected effective numbers of proposals.
- Order-2 ENP: The order-2 denominator represents a redundancy-corrected proposal collision probability.The term v2_n is the probability that two independent weighted draws select proposal n, while ρ̄(q)_n increases this contribution when proposal n overlaps with the rest.
C. Basic Properties
ENP satisfies effective-number properties: it lies between one and the nominal number of proposals and reflects both proposal-weight concentration and redundancy. Its order-2 form behaves as an effective number of non-redundant proposals, while the broader family offers additional flexibility.
- ENP lies between one and the nominal number of proposals.
- For non-redundant proposals, ENP reduces to the d ESS of the proposal-weight vector.
- Uniformly weighted non-redundant proposals yield an ENP approximately equal to their number, whereas a single proposal carrying all weight yields one.
- When equally weighted proposals generate highly overlapping samples, ENP detects their redundancy rather than counting every component.
- With M distinct regions duplicated L times among N = ML uniformly weighted proposals, duplicating existing components does not artificially increase ENP.
- The general ENP family provides flexibility, while the order-2 definition is simplest and most directly connected to classical ESS.
IV. NUMERICAL EXPERIMENTS
The numerical experiments use a standard two-dimensional five-modal Gaussian mixture target, with Gaussian proposals and similarity-based ENP evaluation. Across experiments, q = 2 and ENP(2,2) are reported.
- Experimental setup: Experiments use the standard two-dimensional five-modal Gaussian mixture target from AIS studies.Unless otherwise stated, proposals are Gaussian with isotropic covariance σ2.
- Similarity computation: Sample similarities are computed with a Gaussian kernel Zij.The supplied formulation defines Zij using pairwise sample distances and σ2.
- Reported diagnostic: All experiments use q = 2 and report ENP(2,2).These settings are stated as the common experimental configuration.
A. Controlled Diagnostic Experiment
The controlled experiment isolates ENP’s diagnostic behavior from adaptation by evaluating fixed proposal configurations under repeated sampling. It compares non-redundant, fully collapsed, and duplicated proposal arrangements.
- Experimental design: The experiment evaluates ENP in controlled proposal configurations, separating diagnostic behavior from the adaptation mechanism.Each scenario generates K = 500 samples from every proposal, with results averaged over 30 independent runs.
- Proposal configurations: Scenario A uses five non-redundant proposals, each centered at a different target mode.This configuration represents distinct proposal contributions across target modes.
- Proposal configurations: Scenario B uses five collapsed proposals, all centered at the same target mode.The configuration tests whether ENP responds to proposal concentration in one target region.
- Proposal configurations: Scenario C uses six proposals arranged as two distinct groups, with each group duplicated three times.This configuration tests duplication within two proposal groups.
B. Diagnostic-Triggered Proposal Rejuvenation
ENP is evaluated as a diagnostic-triggered adaptation signal for rejuvenating proposals from a collapsed initialization on a five-modal target. Compared with ESS-triggered rejuvenation, ENP-triggered rejuvenation provides more targeted adaptation, nearly full mode coverage, the lowest MSE, and only 1.15 triggers on average.
- B. Diagnostic-Triggered Proposal Rejuvenation: The experiment uses 50 Gaussian proposals, 20 samples per proposal, 40 adaptive DM-PMC iterations, and averages results over 20 independent runs.The target is a two-dimensional five-modal distribution, with σq = 2 and σZ = 2.5.
- B. Diagnostic-Triggered Proposal Rejuvenation: New proposal locations are drawn uniformly over [−20, 20]2 or from high-weight samples with inflated Gaussian perturbations.In the ENP-triggered variant, proposals with the largest redundancy-corrected contributions are selected for rejuvenation.
- B. Diagnostic-Triggered Proposal Rejuvenation: ENP-triggered rejuvenation achieves nearly full coverage, the lowest MSE, and only 1.15 triggers on average.ESS-triggered rejuvenation improves mode coverage but requires frequent intervention.
- B. Diagnostic-Triggered Proposal Rejuvenation: The results indicate that ENP responds directly to proposal redundancy and guides rejuvenation more efficiently than a purely weight-based trigger.This interpretation is based on ENP-triggered rejuvenation’s coverage, MSE, and intervention frequency.
V. CONCLUSION
The letter introduces ENP, a similarity-aware diagnostic for measuring proposal-level redundancy in population-based adaptive importance sampling. Unlike ESS, ENP estimates the number of non-redundant proposal components contributing to the approximation and satisfies natural effective-number properties.
- Contribution: ENP measures proposal-level redundancy in population-based adaptive importance sampling.It is presented as a similarity-aware diagnostic.
- Contribution: Unlike ESS, which measures the effective number of weighted samples, ENP estimates the number of non-redundant proposal components contributing to the approximation.The distinction is between sample-level weighting and proposal-level contributions.
- Properties: The proposed diagnostic satisfies natural effective-number properties.The passage also states that ENP behaves consistently under non-redundant, collapsed, and duplicated conditions.