PaperlayerView exact revision on arXiv

Source-linked AI summary

Effective Sample Size for Importance Sampling based on discrepancy measures

L. Martino, V. Elvira, F. Louzada

arXiv:1602.03572v5stat.CO

TL;DR

ESS measures the efficiency of Monte Carlo methods, but the standard importance-sampling approximation is accurate only in specific cases and is tied to Euclidean discrepancy from uniform weights. The paper derives alternative ESS functions from other discrepancy measures, classifies them using five requirements, and compares promising functions through numerical simulations, identifying alternatives with interesting theoretical and practical features.

  • Problem

    The widely used importance-sampling ESS approximation is accurate only in specific cases, motivating alternative measures for assessing efficiency and resampling convenience.

  • Method

    The paper derives ESS functions from discrepancy measures between normalized-weight and uniform pmfs, defines five G-ESS requirements, classifies candidates, and compares them numerically.

  • Results

    Different G-ESS expressions present interesting theoretical and practical features and can be considered valid alternatives to the standard formula.

  • Takeaways & Limitations

    ESS selection can extend beyond the standard squared-weight formula to measures involving geometric means, entropy, perplexity, and Gini coefficients.

  • Takeaways & Limitations

    Importance sampling assumes the proposal density is positive wherever the target is nonzero and has heavier tails than the target density.

Abstract

from arXiv · show

The Effective Sample Size (ESS) is an important measure of efficiency of Monte Carlo methods such as Markov Chain Monte Carlo (MCMC) and Importance Sampling (IS) techniques. In the IS context, an approximation $\widehat{ESS}$ of the theoretical ESS definition is widely applied, involving the inverse of the sum of the squares of the normalized importance weights. This formula, $\widehat{ESS}$, has become an essential piece within Sequential Monte Carlo (SMC) methods, to assess the convenience of a resampling step. From another perspective, the expression $\widehat{ESS}$ is related to the Euclidean distance between the probability mass described by the normalized weights and the discrete uniform probability mass function (pmf). In this work, we derive other possible ESS functions based on different discrepancy measures between these two pmfs. Several examples are provided involving, for instance, the geometric mean of the weights, the discrete entropy (including theperplexity measure, already proposed in literature) and the Gini coefficient among others. We list five theoretical requirements which a generic ESS function should satisfy, allowing us to classify different ESS measures. We also compare the most promising ones by means of numerical simulations.

1 Introduction

The introduction motivates parsimonious resampling in SMC and examines ESS as a criterion for deciding when resampling is needed. It proposes generalized ESS functions based on discrepancy measures between normalized-weight and uniform pmfs, with theoretical classification and numerical comparison.

  • Motivation: SMC resampling avoids importance-weight degeneracy but reduces particle diversity, adds computational cost, and limits parallel implementation.These trade-offs motivate performing resampling only when required.
  • Effective Sample Size: ESS measures Monte Carlo efficiency by relating weighted-sample performance to the equivalent number of independent target-distributed samples.The theoretical definition compares the variance of an ideal estimator with that of an MCMC or IS estimator using the same sample count.
  • Existing ESS approximation: The standard IS approximation is the inverse sum of squared normalized importance weights, but it accurately estimates theoretical ESS only in specific cases.The approximation uses only the normalized weights and is widely applied in IS and SMC.
  • Discrepancy interpretation: The standard approximation is related to the Euclidean discrepancy between the normalized-weight pmf and the discrete uniform pmf.It is high when weights are close to uniform and small when mass is concentrated mainly in one weight.
  • Contributions: The paper introduces alternative ESS functions from different discrepancy measures, five requirements for generic G-ESS functions, and numerical comparisons of promising candidates.Examples involve the geometric mean, discrete entropy, perplexity, and Gini coefficient; four families of proper G-ESS functions are designed.

2 Effective Sample Size for Importance Sampling

This section develops the theoretical and practical ESS setting for importance sampling, where target samples are generally unavailable and proposal samples receive importance weights. ESS quantifies the equivalent number of direct target samples needed to match the weighted estimator’s efficiency.

  • Importance Sampling: Importance sampling targets a density known up to normalization by drawing samples from a proposal density and weighting them by the target-to-proposal ratio.Normalized weights are then used to form the importance-sampling estimator.
  • Importance Sampling: Direct sampling from the target is generally impossible, so the importance-sampling estimator is typically less efficient than the direct Monte Carlo estimator.The efficiency loss motivates measuring ESS through estimator variances.
  • Theoretical ESS: ESS is defined through the ratio of the ideal direct-sampling estimator’s variance to the variance of the MCMC or IS estimator.This theoretical definition depends on the integrand function used in the estimation.
  • Interpretation: ESS represents the number of independent samples drawn directly from the target needed to obtain an estimator with the same efficiency as the importance-sampling estimator.The interpretation compares direct target sampling with proposal sampling under importance weighting.
  • Assumptions: The proposal density is assumed positive wherever the target is nonzero and to have heavier tails than the target density.These assumptions define the support and tail relationship used for importance sampling.

N as a discrepancy measure

The commonly used ESS approximation P^(2)_N is tied to the Euclidean discrepancy between normalized importance weights and the uniform pmf, but its derivation relies on strong approximations and assumptions. This connection motivates alternative ESS functions based on other discrepancy measures.

  • The derivation of P^(2)_N contains several approximations and strong assumptions, and it can differ substantially from the theoretical ESS in many scenarios.
  • P^(2)_N is widely used for adaptive resampling in population Monte Carlo and particle-filtering schemes.
  • Monitoring P^(2)_N has been reported as sufficient to prevent particle-system collapse, despite its approximation limitations.
  • Adaptive resampling applies when the estimated ESS falls below the threshold ϵN, while avoiding resampling when the weights remain sufficiently uniform.Resampling addresses weight degeneracy but introduces diversity loss and computational cost.
  • P^(2)_N is equivalent to minimizing the Euclidean distance between the normalized-weight pmf and the discrete uniform pmf.
  • The discrepancy perspective supports deriving alternative ESS functions from non-Euclidean distances between the same two pmfs.The paper introduces a generic ESS framework with five conditions for evaluating such alternatives.

4 Generalized ESS functions

A generalized ESS function depends only on normalized weights in the unit simplex and is evaluated against five conditions. These conditions distinguish proper, degenerate, and stable G-ESS functions.

  • Definition: A G-ESS function maps the vector of normalized weights to a value in [1, N] on the unit simplex.The normalized weights satisfy ¯w1 + ¯w2 + ... + ¯wN = 1.
  • Five conditions: The first three G-ESS conditions are strictly necessary, while the final two are desirable but not required.
  • Five conditions: C1 requires invariance under any permutation of the normalized weights.
  • Five conditions: C2 requires the maximum value N at the uniform weight vector, while C3 requires the minimum value 1 at simplex vertices.
  • Five conditions: C4 requires unique extreme values, and C5 concerns stability when weights are repeated and scaled by 1/M.The repeated vector has dimension MN for M ≥ 1.
  • Classification: Functions satisfying C1–C4 are proper, those satisfying C1–C3 but not C4 are degenerate, and those satisfying all five conditions are stable.The paper also distinguishes type-1 and type-2 degeneracy according to nonunique maxima or minima.

5 G-ESS families and further examples

The paper constructs four parameterized G-ESS families satisfying the first three requirements, derives their coefficients, and examines special cases and classifications. It also presents additional examples, stable functions, and simulated distributions of ESS values.

  • G-ESS families: Four parameterized G-ESS families are introduced to satisfy the required conditions C1, C2, and C3.Their analytic forms use a parameter r ≥ 0.
  • G-ESS families: The family coefficients are obtained by solving linear systems designed to fulfill conditions C2 and C3, producing generally proper functions with some degenerate and stable exceptions.The resulting coefficients are summarized in Table 2.
  • Further examples: Special parameter values yield functions involving geometric means, discrete entropy, and the number of zero normalized weights.Table 3 collects these special cases and their classifications, including a proper and stable function not previously introduced.
  • Further examples: Perplexity and the Gini-based G-ESS are proper and stable, whereas the minimum-based functions T1,N and T2,N are degenerate type-2 measures.The Gini construction sorts normalized weights before defining the coefficient-based G-ESS function.
  • Distribution of the ESS values: For N = 2, the compared G-ESS functions exhibit different growth and density patterns, with some distributions concentrated near 1 and others unbalanced toward 2.Figure 1 compares D(∞)2, P(2)2, and T2,2 for N = 2.

6 Simulations

The simulations compare G-ESS functions with theoretical ESS definitions across sample sizes, proposal settings, and adaptive-resampling applications. Results indicate that the best approximation depends on sample size, proposal–target discrepancy, and whether variance or averaged ESS is considered.

  • 6.1 Analysis of the distribution of ESS values: 2000 independent weight vectors were sampled uniformly from the unit simplex, and proper stable G-ESS functions were evaluated to form ESS-rate histograms.The resulting empirical means and standard deviations were summarized for different N.
  • 6.1 Analysis of the distribution of ESS values: All G-ESS functions produced unimodal ESS-value distributions, with variances decreasing as N increased.These distributions can inform threshold selection in adaptive resampling.
  • 6.2 Approximation of the theoretical ESS definition: For N = 5 in setting S1, GiniN generally approximated ESSvar(x) most closely, while P (2)N also performed well; ESSvar(x) and ESSMSE(x) diverged as bias increased.At µp ≈ 0, the two theoretical curves were very close; larger bias produced substantial differences.
  • 6.2 Approximation of the theoretical ESS definition: For N = 1000, P (2)N most closely followed ESSvar(x) in S1, whereas GiniN was best for µp ∈[0, 0.5] and D(∞)N improved as µp increased.ESSvar(x) remained between the compared D(∞)N-based bounds in the reported simulations.
  • 6.2 Approximation of the theoretical ESS definition: In setting S2 with N = 5, GiniN and P (2)N were closest around the optimal σp, while D(∞)N was closest elsewhere; for N = 1000, P (2)N followed ESSvar(x) better overall and D(∞)N was closest at small σp.All G-ESS functions failed to reproduce ESSMSE(x) conveniently for N = 5 in this setting.
  • 6.2 Approximation of the theoretical ESS definition: When proposal and target differed substantially, D(∞)N performed best; GiniN worked well for closer shapes and small N, while P (2)N was a compromise in intermediate cases.For averaged ESS across integrands, D(∞)N was the closest approximation to A-ESS.

7 Conclusions

The paper proposes and evaluates alternative ESS approximations, selecting six functions that satisfy five theoretical requirements. Simulations identify context-dependent advantages among the most promising measures and suggest resampling thresholds.

  • The study proposes new ESS approximation classes, classifies them using five theoretical requirements, and selects six functions satisfying all necessary conditions.
  • D(∞)_N and Gini_N(w̄) offer benefits over the standard P^(2)_N formula, with their relative performance depending on proposal-target similarity and particle count.
  • When the proposal differs substantially from the target, D(∞)_N provides the best approximations; when it is close, Gini_N(w̄) also performs well.
  • For small N, Gini_N(w̄) seems to outperform P^(2)_N, while P^(2)_N can be a compromise in intermediate scenarios.
  • D(∞)_N behaves as a lower bound for theoretical ESS in simulations, and Table 5 suggests thresholds ε ≥ 1/2 for P^(2)_N and Gini_N(w̄), or ε ≥ 0.11 for D(∞)_N.
  • In stochastic-volatility particle filtering, D(∞)_N produced smaller MSE than P^(2)_N at equal resampling rates.

A Analysis of the theoretical derivation of P (2)

This analysis examines why the standard P^(2)_N approximation can diverge from theoretical ESS. Its derivation relies on approximations and assumptions that omit particle locations, ignore bias, and may fail under unnormalized targets or broader sampling schemes.

  • The derivation applies multiple approximations, including first and second delta methods, to obtain the standard P^(2)_N formula.
  • The variance-ratio definition ignores estimator bias, which can be significant for small N; the squared bias is typically order N^-2 versus variance order N^-1.
  • Because the derivation assumes i.i.d. samples from one proposal, applying P^(2)_N to multiple-proposal algorithms extends beyond its stated derivation.
  • The derivation assumes a normalized target, but without that assumption the approximation is no longer valid and the normalizing constant enters earlier expressions.
  • P^(2)_N depends only on normalized weights, not particle values, so it can misrepresent the effective sample size of weighted particles.
  • The theoretical ESS can be below 1 or above N under the general variance definition, whereas P^(2)_N ≤ N does not capture these possibilities completely.
  • When all particles coincide, P^(2)_N(w̄)=N even when the target is not a point mass, illustrating a concrete failure of weight-only assessment.

B The optimism of P (2)

The paper analyzes the optimistic behavior of P^(2)_N in extreme weight configurations. Equal weights can occur despite proposal-target mismatch, while a single nonzero weight may still correspond to an ESS no greater than one.

  • P^(2)_N is analyzed using only normalized weights to characterize its behavior in two extreme cases.
  • Equal normalized weights imply P^(2)_N=N, but they can occur even when the proposal density differs from the target.
  • For independent or non-negatively correlated samples, equal weights support the bound ESS ≤ N, but do not establish that the proposal equals the target.
  • With one weight equal to one and all others zero, the best possible effective sample size is one when that particle is generated exactly from the target.
  • P^(2)_N assigns value one to every single-weight vector, making its treatment of both extreme cases optimistic.
  • Using only normalized weights appears reasonable despite these limitations, because the weight vector is the available information for this approach.

C G-ESS functions induced by non-Euclidean distances

The paper derives generalized ESS functions from non-Euclidean discrepancies between normalized weights and the uniform distribution. It develops L1-, L0-, and L∞-based constructions with distinct interpretations and properties.

  • The authors derive generalized ESS functions from non-Euclidean distances, extending the standard relationship between P^(2)_N and L2 distance.
  • Distance L1: The L1 distance yields Q_N(w̄), a proper and stable ESS function bounded between 1 and N.
  • Distance L1: Q_N(w̄) equals N for uniform weights and 1 for a one-hot vector, and maximizing it is equivalent to minimizing L1 distance from uniformity.
  • Norm L0: The L0 construction uses the Hamming distance from the all-zero vector and depends on the number of zero entries in the normalized-weight vector.
  • Norm L∞: The L∞ norm is determined by the largest normalized weight, motivating an ESS function based on the reciprocal of max[w̄_1,...,w̄_N].
  • Norm L∞: The paper notes that the L∞-based G-ESS function had also been considered in prior literature.

D Derivation of Generalized ESS families

The section constructs generalized ESS functions by transforming discrepancy-related functions so they satisfy prescribed ESS conditions. It then specializes this procedure to families of candidate functions.

  • General construction: A generalized ESS function can be constructed from a function f(w̄) satisfying the required conditions C1–C4, apart from some degenerate exception.The paper presents one simple construction procedure while noting that alternatives are possible.
  • Conditions: The underlying f(w̄) is required to be quasi-concave or quasi-convex, symmetric, and constrained at the uniform point and simplex vertices.The vertex condition assigns a common constant c across all vertices.
  • General construction: The construction uses a linear transformation g(w̄)=af(w̄)+b, with the sign of a chosen to make g quasi-concave.Positive a is used when f is quasi-concave, whereas negative a is used when f is quasi-convex.
  • General construction: The resulting G-ESS is defined through the transformed function, using either E_N(w̄)=1/(af(w̄)+b) or E_N(w̄)=af(w̄)+b.The transformation parameters are selected to satisfy the required normalization equations.
  • Specialized families: The procedure is applied to derive special cases of the families P^(r)_N and V^(r)_N.The text introduces these families as examples obtained using the general construction.

D.1 Special cases of P (r)

The paper analyzes limiting and selected parameter cases of several generalized ESS families. These cases connect the families to entropy-like, maximum-weight, and vertex-sensitive expressions.

  • P^(r)_N: For P^(r)_N, the r→0 case gives ESS N when there are no zero weights and adjusts according to the number N_Z of zeros otherwise.At a vertex, where N_Z=N−1, the value is 1.
  • P^(r)_N: The r=1 case of P^(r)_N is treated through a limit involving discrete entropy, with H(w̄*)=log_2 N at uniform weights.The derivation uses an indeterminate-form limit and L’Hôpital’s rule.
  • P^(r)_N: For P^(r)_N, the limit r→∞ gives ESS N for non-vertex weights and ESS 1 at a simplex vertex.The two cases are summarized explicitly for weights that are not vertices versus weights equal to a vertex.
  • D^(r)_N: For D^(r)_N, the r→∞ limit is N divided by the largest normalized weight, 1/max[w̄_1,...,w̄_N].This follows from convergence of the discrepancy to the L∞ distance.
  • V^(r)_N: For V^(r)_N, the r→∞ case yields ESS N away from vertices and ESS 1 at a vertex.The vertex result follows because the power sum equals 1 for a one-hot weight vector.
  • S^(r)_N: The S^(r)_N family includes an r=1/2 case with coefficients a_1/2=1 and b_1/2=0, and limiting cases involving the maximum normalized weight.The r→∞ coefficients are a_∞=−N and b_∞=N+1; Table 3 summarizes the special cases.
Loading 1602.03572v5…