PaperlayerView exact revision on arXiv

Source-linked AI summary

Importance Sampling: Intrinsic Dimension and Computational Cost

S. Agapiou, O. Papaspiliopoulos, D. Sanz-Alonso, A. M. Stuart

arXiv:1511.06196v3stat.CO

TL;DR

Importance sampling requires a principled account of how target–proposal mismatch determines the sample size needed for accurate approximation. The paper unifies computational-cost measures through general theory and analyzes Bayesian inverse problems and filtering, showing that intrinsic dimension and ρ organize performance and absolute-continuity behavior.

  • Problem

    The paper addresses confusion about what makes importance sampling hard in high dimensions and how computational cost should be measured relative to the target and proposal.

  • Method

    The paper develops a general importance-sampling framework and applies linear-Gaussian analysis to Bayesian inverse problems and filtering, including standard and optimal particle-filter proposals.

  • Results

    Intrinsic dimension, rather than state-space or nominal dimension, controls importance-sampling performance in the studied Bayesian linear models, while finite intrinsic dimension corresponds to finite ρ and absolute continuity in the analyzed settings.

  • Takeaways & Limitations

    The framework connects ρ, effective sample size, probability distances, intrinsic dimensions, and absolute continuity for analyzing importance-sampling cost in inverse problems and filtering.

  • Takeaways & Limitations

    Applications to Bayesian inverse problems and filtering are limited to linear problems with additive Gaussian noise.

Abstract

from arXiv · show

The basic idea of importance sampling is to use independent samples from a proposal measure in order to approximate expectations with respect to a target measure. It is key to understand how many samples are required in order to guarantee accurate approximations. Intuitively, some notion of distance between the target and the proposal should determine the computational cost of the method. A major challenge is to quantify this distance in terms of parameters or statistics that are pertinent for the practitioner. The subject has attracted substantial interest from within a variety of communities. The objective of this paper is to overview and unify the resulting literature by creating an overarching framework. A general theory is presented, with a focus on the use of importance sampling in Bayesian inverse problems and filtering.

1. INTRODUCTION

The paper unifies measures of importance-sampling cost and clarifies how intrinsic dimension, absolute continuity, and the parameter ρ govern performance in inverse problems and filtering.

  • 1.1 Our Purpose: The paper overviews and links measures of importance-sampling computational cost through mathematical reasoning, focusing on Bayesian inversion and filtering.These application settings are presented as important examples of scientific, technological, and societal problems.
  • 1.1 Our Purpose: The abstract theory relates ρ to effective sample size and distance metrics, while examining high-dimensional and singular-limit breakdowns of absolute continuity.The framework is then developed for inverse problems and filtering.
  • 1.1 Our Purpose: The paper addresses confusion about the curse of dimensionality by clarifying what “dimension” means in importance-sampling performance.It argues that statements about dimensionality are vacuous unless dimension is defined precisely.
  • 1.2 Organization of the Paper and Main Contributions: Intrinsic dimensions are linked to ρ and absolute continuity, and this connection is translated from linear inverse problems to particle filters with standard and optimal proposals.The paper presents these links as central to understanding computational cost.
  • 1.2 Organization of the Paper and Main Contributions: The paper’s theory provides a non-asymptotic bounded-test-function error result interpreted through ρ, effective sample size, probability metrics, and existing asymptotic results.The result is less useful for specific linear, bilinear, or quadratic test functions used for moments and covariances.
  • 1.3 Literature Review: Applications to inverse problems and filtering are restricted to linear problems with additive Gaussian noise, despite discussion of broader possible relevance.More precise analysis for nonlinear problems and non-Gaussian targets is identified as future work.

2. IMPORTANCE SAMPLING

The paper develops importance-sampling error theory around ρ, with convergence in the number of particles and links to practitioner metrics and probability distances.

  • 2. IMPORTANCE SAMPLING: The analysis relates ρ to effective sample size as commonly defined by practitioners and to various distances between probability measures.These links connect the key theoretical quantity to input and output measures of importance-sampling performance.
  • 2. IMPORTANCE SAMPLING: The paper examines how breakdown of absolute continuity affects growth of ρ as the dimension increases and in singular parameter limits.The two forms of breakdown are treated in separate subsections.

2.1 General Setting

Importance sampling approximates a target measure using weighted independent samples from a proposal, producing a random particle measure whose required sample size determines computational cost.

  • 2.1 General Setting: Importance sampling estimates expectations under target measure µ using independent samples drawn from proposal measure π.The target and proposal are related through a density in the general setting.
  • 2.1 General Setting: The auto-normalized estimator uses normalized weights to integrate a test function with respect to a random probability measure µN.The measure is represented as a weighted sum of point masses at the sampled particles.
  • 2.1 General Setting: The particle approximation µN approximates target µ, and choosing N large enough for small error quantifies importance-sampling computational cost.The approximation depends on proposal π, although that dependence is suppressed in the notation.

2.2 A Non-asymptotic Bound on Particle Approximation Error

Theorem 2.1 gives non-asymptotic bias and MSE bounds for self-normalized importance sampling over bounded test functions, with computational difficulty governed by ρ and sample size N.

  • ρ is the second moment of the target density with respect to the proposal and satisfies ρ ≥ 1.
  • The bias and MSE bounds for bounded test functions are OTheir constants of proportionality are linear in ρ.
  • The theorem assumes that the target is absolutely continuous with respect to the proposal and that its density g is square-integrable under π.
  • For |φ| ≤ 1, the resulting bounds are useful only when the bias bound is below 2 and the MSE bound below 4.
  • Keeping ρ/N small is a practical heuristic for obtaining accurate importance sampling approximations.
  • The bounded-function result does not extend to unbounded test functions without stronger assumptions on the importance weights.For example, an estimator of μ(g^2) can have infinite variance when g has a third but not fourth moment under π.

2.3 Connections, Interpretations and Extensions

The paper connects ρ with effective sample size, divergence-based distance measures, and asymptotic results, then extends error analysis beyond bounded test functions while exposing limitations of ρ alone.

  • ρ determines the number of samples required to effectively approximate expectations and is linked to other importance-sampling monitoring and analysis quantities.
  • The effective sample size satisfies 1 ≤ ess ≤ N, attaining N for equal weights and 1 when one normalized weight equals 1.
  • For large N, ρ−1 quantifies the proportion of particles effectively characterizing the sample size, supporting ess as an effective sample size.
  • The required particle count scales exponentially with the Kullback-Leibler divergence and linearly with the χ2 divergence between proposal and target.
  • Under weaker moment assumptions, the asymptotic convergence rate is N −1/2, while broader non-asymptotic test-function classes require additional assumptions on the weights.
  • With suitable moments, importance sampling converges at rate N −1 for test functions satisfying πThe error constant is not readily interpretable solely through ρ and involves moments of g with exponent greater than two.

2.4 Behaviour of the Second Moment ρ

The second moment ρ can grow rapidly when target and proposal measures approach singularity, causing importance sampling costs to increase with dimension or a small parameter.

  • Importance sampling convergence scales as the square root of ρ/N, motivating analysis of ρ in high-dimensional and concentrated-likelihood regimes.
  • The infinite-dimensional target and proposal become mutually singular, so importance sampling is undefined at d = ∞ and performance is expected to degrade for large d.
  • In product models, ρ_d = (ρ_1)^d with ρ_1 > 1, so exponentially many particles may be required as state-space dimension d increases.
  • The collapse is attributed to loss of absolute continuity in the infinite-dimensional limit rather than to product structure itself.
  • When likelihood sensitivity diminishes across coordinates, increasing state-space dimension can have only a mild effect and well-behaved infinite-dimensional limits may occur.
  • In fixed dimension, small parameters can also produce mutual singularity and make ρ grow algebraically with the small parameter.
  • Under the stated smoothness and density assumptions, Theorem 2.1 indicates that the particle count should grow at least as fast as ǫ−1.

2.5 Discussion and Connection to Literature

The discussion frames importance-sampling error through distances between target and proposal measures, especially ρ, and connects these quantities to sample requirements, effective sample size, and high-dimensional behavior. It also identifies limits of universal error analysis and reviews related particle-filter and high-dimensional results.

  • Error metrics: The random particle estimator is generally biased, so its quality is assessed using mean squared error over bounded test functions.Theorem 2.1 bounds this MSE and can be interpreted as bounding a distance between the target measure and its approximation.
  • Distance and cost: Increasing particle number linearly with Dχ2(µ∥π) or exponentially with DKL(µ∥π) is suggested by the links between ρ and these divergences.These divergence-based growth rates connect statistical distance to computational cost.
  • Distance and cost: Under concentrated log-weights, a sample size of approximately exp(...) is both necessary and sufficient to control the estimator’s L1 error.This complements the MSE analysis with a separate necessary-and-sufficient sample-size characterization.
  • Error metrics: Theorem 2.1’s bound is asymptotically sharp for large N, while its constant ρ is more tractable than covering-number-based alternatives.The central limit result in equation (2.3) supports sharpness of the upper bound.
  • Limitations: A universal error analysis based only on ρ is impossible for unbounded test functions because the relevant error constants can be more complex.The constants Ct in Theorem 2.3 arise from the Marcinkiewicz-Zygmund inequality.
  • High-dimensional and singular regimes: In high dimensions, if N does not grow exponentially with d, the maximum normalized weight can converge to 1 and the effective sample size to 1.This is the collapse of importance sampling; tempering and Kalman-based combinations are proposed, but their applicability remains under study.

3. IMPORTANCE SAMPLING AND INVERSE PROBLEMS

This section studies importance sampling for Bayesian inverse problems, using intrinsic dimension to connect posterior–prior distance, absolute continuity, and computational cost. Linear Gaussian models provide tractable insight while extending to potentially infinite-dimensional Hilbert spaces.

  • Framework: The inverse-problem analysis uses the posterior as target and the prior as proposal, with the distance between them determining importance-sampling cost.The main result identifies equivalent conditions involving intrinsic dimensions, absolute continuity, and finite ρ.
  • Framework: Linear Gaussian inverse problems are used because their parameters permit analytical study while accommodating function-space formulations and finite-dimensional approximations.The framework includes regression and deconvolution examples, as well as potentially infinite-dimensional Hilbert spaces.
  • Assumptions: The analysis assumes bounded operators and a countable, ordered spectrum for A, with infinite-dimensional formulae available under appropriate conditions.The operator A is defined through the model’s covariance and forward operators.
  • Intrinsic dimension: The operator A quantifies differences between posterior and prior precision and covariance operators through the traces of A and (I + A)^−1A.These traces motivate intrinsic-dimension measures and computational-cost analysis.
  • Intrinsic dimension: The effective dimension efd and τ measure intrinsic dimension, and efd is bounded above by the nominal dimension in the finite-dimensional setting.Their finiteness is linked to the rank and finite-dimensional structure of the forward problem.
  • Intrinsic dimension: In infinite-dimensional settings, efd and τ are finite or infinite together, and both are finite whenever the unknown or data lie in a finite-dimensional subspace.Lemma 3.7 establishes equivalence of trace-class conditions for A and (I + A)^−1A.

As a consequence

The supplied passage states that the next analysis studies how ρ and the intrinsic dimensions τ and efd depend on parameters such as observational noise and finite-dimensional approximation size.

  • Parameter dependence: The next subsection studies how ρ, τ, and efd vary with small observational noise and the dimension of finite-dimensional inverse-problem approximations.These parameter dependencies are examined after establishing the role of intrinsic dimension and absolute continuity.

3.3 Absolute Continuity

This section addresses when the posterior is absolutely continuous with respect to the prior in Hilbert-space inverse problems, because otherwise the density ratio and ρ may not exist. It establishes equivalent conditions linking this property to intrinsic dimension and prior-draw regularity.

  • Absolute continuity: In finite dimensions, posterior and prior Gaussian measures are mutually absolutely continuous, but this is not guaranteed in Hilbert spaces.When absolute continuity fails, the target–proposal density g and ρ are not defined.
  • Equivalent conditions: Theorem 3.8 makes finite efd, finite τ, prior-almost-sure membership of Γ^−1/2Ku in H, and posterior absolute continuity equivalent.The equivalence holds for νy-almost all observations under the stated assumption.
  • Equivalent conditions: The posterior’s absolute continuity also corresponds to positivity and finiteness of g together with a finite second moment of the target–proposal density.This follows from the exponential structure of g.
  • Regularity: The regularity requirement on Γ^−1/2Ku constrains possible reconstructions and is related to the inverse problem’s intrinsic dimension.It compares the regularity of prior-generated forward images with the regularity imposed by the noise.
  • Implications: When intrinsic dimension is finite, importance sampling may be possible, ρ is finite, and Theorem 2.1 can provide effective-sample-size bounds.The passage presents these properties as consequences of the equivalent conditions.

3.4 Large Nominal Dimension and Singular Parameter Limits

The section analyzes how intrinsic dimensions and singular parameter limits govern the computational cost of importance sampling in linear inverse problems. It shows that growth in ρ signals increasing particle requirements and, in relevant limits, loss of absolute continuity.

  • Intrinsic-dimension analysis: ρ can be lower bounded using intrinsic dimensions τ and efd together with the eigenvalue magnitudes of A.The paper studies clustered large eigenvalues and asymptotic simultaneously diagonalizable settings.
  • Intrinsic-dimension analysis: Exponentially many particles may be required as the number of large eigenvalues increases, while dependence on eigenvalue size is algebraic.This distinction follows from the asymptotic behavior of ρ and Theorem 2.1.
  • Spectral cascade: The model family varies prior and forward-map regularity, observational noise, and nominal dimension to study their effects on ρ.The nominal dimension is represented by the number of positive eigenvalues of A.
  • Spectral cascade: Table 1 relates scalings of τ and efd to ρ and thereby indicates how particle requirements change across parameter regimes.When ρ diverges, the posterior and prior approach mutual singularity.
  • Singular limits: Absolute continuity is lost as d →∞ when β ≤1, as β approaches 1 with d = ∞, and as γ →0.In the vanishing-noise limit, τ is always infinite.
  • Spectral cascade: ρ grows algebraically for finite nominal dimension under vanishing noise, exponentially with growing dimension or rougher priors, and factorially in infinite-dimensional small-noise limits.The exponential regimes occur for β < 1 as d →∞ or as β decreases to 1 with d = ∞.

3.5 Discussion and Connection to Literature

The discussion situates the linear inverse-problem analysis within related inverse-problem formulations and interprets effective dimensions through covariance, precision, and prior-information effects. It also identifies the scope of the main theorem and its limitation for specific test functions.

  • Related inverse problems: The analysis covers examples including Radon-transform inversion, temperature recovery, Laplace-transform inversion, and periodic deconvolution.These examples include both finite- and infinite-dimensional linear inverse problems.
  • Operator assumptions: The countable-eigenvalue assumption permits viewing A as an infinite diagonal matrix and includes compact operators and the non-compact case A = I.The assumption is therefore broader than compactness alone.
  • Operator assumptions: Equivalent formulations using S, S∗, or SS∗ preserve the relevant trace and nonzero-eigenvalue relationships under the stated operator conditions.For compact S, SS∗ and S∗S share the same nonzero eigenvalues.
  • Regularization interpretation: When SS∗ is compact, posterior means regularize data components associated with small eigenvalues; when it is unbounded, those high-frequency components remain nearly unaffected.The bounded case is described as the borderline determining the prior’s regularizing behavior.
  • Notions of dimension: The effective dimension efd is at most the nominal dimension and measures how the prior changes inference relative to maximum likelihood.The paper interprets efd as the effective dimension of the Bayesian linear model.

4. IMPORTANCE SAMPLING AND FILTERING

The paper recasts one-step particle filtering under standard and optimal proposals as related importance-sampling inverse problems. Their costs are characterized through intrinsic dimensions, ρ, and absolute-continuity conditions, revealing settings where the optimal proposal remains viable while the standard proposal collapses.

  • 4.1 General Setting: The filtering analysis embeds an inverse problem in both proposals, enabling direct transfer of importance-sampling cost results to particle filters.The framework computes each proposal's covariance, observation operator, and observational-noise covariance before applying the inverse-problem analysis.
  • 4.1 General Setting: One filtering step targets P_v1,v0|y1 and compares the standard proposal P_v1|v0P_v0 with the optimal proposal P_v1|v0,y1.Each proposal connects particle filtering to a different inverse problem on the product or state space.
  • 4.1.2 Optimal Proposal: The optimal proposal requires sampling from the conditioned dynamics P_v1|v0,y1, which remains Gaussian when the forward model is replaced by a nonlinear map f(v0).This sampling ability is a key assumption for implementing the proposal particle by particle.
  • 4.2–4.3 Cost and Absolute Continuity: The relative sizes of ρ_st and ρ_op determine the relative efficiency of filtering with the standard and optimal proposals.Finite second moments of the target-proposal densities are tied to the relevant absolute-continuity and intrinsic-dimension conditions.
  • 4.3 Absolute Continuity: τ_op = ∞ implies τ_st = ∞, so loss of absolute continuity for the optimal proposal entails loss for the standard proposal.The proposed comparison also identifies conditions under which both proposals collapse simultaneously, while deterministic dynamics remove the optimal proposal's advantage.
  • 4.4 Large Nominal Dimension and Singular Parameter Limits: τ_st = ∞ and τ_op < ∞ can occur, making filtering well-defined with the optimal proposal but not with the standard proposal.The example has τ_st = Tr(P + I) = ∞ and τ_op = Tr(P/2) < ∞; the situation is associated with observations providing more information about v1 than v0.
  • 4.4 Large Nominal Dimension and Singular Parameter Limits: As r → 0, the standard proposal degenerates algebraically, whereas the optimal proposal can remain insensitive when q is fixed; in large d, ρ may grow exponentially or remain finite for the optimal proposal.The large-dimensional example includes mutual singularity for both proposals, while another case has exponential ρ_st growth and finite limiting ρ_op.
  • 4.5 Discussion and Connection to Literature: In general nonlinear, non-Gaussian problems, the optimal proposal is usually not implementable because its weights or conditioned-dynamics samples cannot be evaluated or generated.Within the paper's Gaussian framework, however, the proposal is implementable and useful for analyzing data-informed alternatives.

5. CONCLUSIONS

The conclusions unify importance-sampling cost analysis around intrinsic dimension rather than nominal state or data dimension, focusing on Bayesian linear inverse problems and one-step filtering. They also identify practical extensions needed for broader algorithmic guidance.

  • 5. CONCLUSIONS: The framework unifies importance-sampling literature and develops non-asymptotic concentration inequalities for high- and infinite-dimensional inverse problems and filtering.The paper revisits importance sampling on general state spaces while connecting computational cost measures across settings.
  • 5. CONCLUSIONS: In Bayesian linear inverse problems, importance-sampling performance using the prior as proposal is controlled by intrinsic dimension rather than state-space or data dimension.The analysis balances tractability and practical relevance through linear models for regression and ill-posed statistical inversion.
  • 5. CONCLUSIONS: For one-step filtering, the paper introduces intrinsic-dimension notions and compares standard and optimal proposal schemes without analyzing interacting particles from resampling.This scope choice supports tractable comparison of sequential importance sampling while excluding multi-time resampling interactions.
  • 5. CONCLUSIONS: Future work includes concrete algorithmic recommendations and extensions to non-Gaussian priors, nonlinear observation operators, and unknown hyperparameters.These extensions are identified as practically relevant within the model structure studied.

6. SUPPLEMENTARY MATERIAL

The supplementary material develops the Hilbert-space Gaussian framework underlying infinite-dimensional importance-sampling analysis, including Gaussian construction, absolute continuity, and proof details for inverse problems and particle approximations.

  • Gaussian measures in Hilbert space: Section 3 uses Hilbert spaces to study infinite-dimensional limits of high-dimensional Bayesian inverse problems and importance-sampling complexity.The framework also assumes observation, prior, and forward-model operators are compatible so the observation model is well defined.
  • Gaussian measures in Hilbert space: A Gaussian draw can be represented through a Karhunen–Loève expansion in the covariance eigenbasis, with trace-class covariance ensuring membership in the Hilbert space almost surely.Eigenvalue decay determines the almost-sure regularity of the resulting draw.
  • Gaussian measures in Hilbert space: Cameron–Martin space consists of mean shifts producing equivalent Gaussian measures with fixed covariance, while typically having zero measure under the centered Gaussian distribution.This distinction is central because infinite-dimensional Gaussian measures can be mutually singular unless stringent conditions hold.
  • Gaussian measures in Hilbert space: The Karhunen–Loève construction extends to separable Hilbert spaces through independent standard normal coefficients and positive eigenvalue sequences satisfying an almost-sure summability condition.The construction implies λ_j tends to zero when draws belong to the space almost surely.
  • Proofs and particle approximations: The Hilbert-space extension of Proposition 3.5 requires the posterior precision formula and additional trace-commutativity justifications beyond the finite-dimensional case.These justifications use a different part of Lemma 6.5 in the infinite-dimensional setting.
Loading 1511.06196v3…