Technical Summary: Importance Sampling and Independent Metropolis–Hastings with an Unbounded Weight Function

1. Problem Statement

Monte Carlo methods, specifically Importance Sampling (IS) and Independent Metropolis–Hastings (IMH), rely on a proposal distribution $q$ to approximate a target distribution $\pi$. A critical component is the weight function $\omega(x) = \pi(x)/q(x)$. While theoretical analyses often assume $\omega$ is bounded, practical applications frequently involve unbounded weights.

The paper addresses two primary gaps in the literature regarding unbounded weights:

1. Bias Analysis: The non-asymptotic bias of Self-Normalized Importance Sampling (SNIS) and IMH estimators is often ignored in favor of asymptotic variance, yet it significantly impacts downstream tasks such as stochastic gradient optimization, nested expectations, and robust mean estimation.
2. Convergence Rates: Existing bounds for IMH with unbounded weights often lack explicit dependence on the number of particles $N$ (in the particle IMH variant) or rely on assumptions that are difficult to verify.

The authors investigate the bias of these estimators without assuming bounded weights, relying instead on the assumption that $\omega$ possesses finite moments of order $p > 1$ under $q$.

2. Methodology and Theoretical Framework

2.1. Moment Conditions

The core assumption (Assumption 2) is that the weight function has a finite $p$-th moment under the proposal: $q(\omega^p) < \infty$ for some $p > 1$. This is a weaker condition than the boundedness often assumed in geometric ergodicity analyses.

2.2. Coupling and Meeting Times

To analyze the convergence of IMH, the authors employ a common random numbers coupling (Algorithm 4). They demonstrate that this coupling is maximal (Theorem 3.1), meaning the probability of two chains meeting at time $t$ is exactly equal to $1 - |P^t(x, \cdot) - P^t(y, \cdot)|_{TV}$.

• The meeting time $\tau$ is shown to follow a geometric distribution conditioned on the rejection probabilities.
• The authors derive explicit polynomial bounds on the tail probabilities of $\tau$ (Proposition 4.3), linking them to the moments of the average weight $\hat{Z}_N$.

2.3. Bias Removal via Coupling

Building on the work of Glynn & Rhee (2014) and Middleton et al. (2019), the paper utilizes the coupling of lagged PIMH chains (Algorithm 5) to construct unbiased estimators (Coupling-UIS). The estimator is defined as a telescopic sum:
$$\hat{F}^u_N = \hat{F}_N(X^N_0) + \sum_{t=1}^{\tau-1} \{ \hat{F}_N(X^N_t) - \hat{F}_N(Y^N_{t-1}) \}$$
The paper introduces a Rao–Blackwellized version of this estimator (Algorithm 6) to improve efficiency.

3. Key Contributions and Results

3.1. Bias of Self-Normalized Importance Sampling (SNIS)

• Asymptotic Bias: Theorem 2.1 establishes that the asymptotic bias of the SNIS estimator is of order $O(N^{-1})$, specifically:
  $$\lim_{N \to \infty} N \times E[\hat{F}_N - \pi(f)] = -\int (f(x) - \pi(f)) \omega^2(x) q(dx)$$
  This result holds under conditions requiring finite inverse moments of $\omega$ and specific moment conditions on $f$.
• Moment Bounds: Theorem 2.2 and Proposition 2.1 provide bounds on the $s$-th moments of the error for unbounded test functions, extending previous results to cases where $p < 2$ (heavy-tailed weights).

3.2. Convergence Rates of IMH

• Polynomial Convergence: Theorem 4.1 and Corollary 4.1 provide explicit bounds on the total variation distance between the PIMH chain and the target $\bar{\pi}$.
  • For $p \ge 2$, the distance decays as $O(N^{-1/2} (1+t)^{-(p-1)})$.
  • For $1 < p < 2$, the decay is $O(N^{-(p-1)/p} (1+t)^{-(p-1)})$.
• Optimality: Example 3 provides a lower bound showing that the rate $t^{-(p-1)}$ is essentially optimal (up to logarithmic factors) without further assumptions, suggesting the moment condition is nearly necessary for polynomial convergence.
• Bias Comparison: Section 4.6 compares the bias of IMH and SNIS. For $p > 2$, the bias of IMH (after a burn-in period) decays as $O(N^{-(p-1)})$, which is faster than the $O(N^{-1})$ bias of SNIS. However, if $p \le 2$, SNIS may have a smaller bias.

3.3. Unbiased Estimators (Coupling-UIS)

• Finite Moments: Proposition 5.3 establishes conditions under which the unbiased Coupling-UIS estimator has finite moments. Specifically, if $p > 2$ and $r > 2$ (where $r$ is the moment of $f$), the estimator has finite variance.
• Asymptotic Efficiency: Proposition 5.5 and Theorem 5.6 show that the inefficiency (variance $\times$ cost) of the unbiased estimator is asymptotically equivalent to that of SNIS as $N \to \infty$, provided $p > 4$ (or slightly weaker conditions for specific test functions like $1/Z$).
• Improvement: The Rao–Blackwellized estimator (Algorithm 6) reduces the asymptotic inefficiency by a factor of two compared to the standard coupling approach, making it twice as efficient as $N \to \infty$.

3.4. Unbiased Estimation of Normalizing Constants

Section 5.6 and Proposition 5.7 specifically address the unbiased estimation of $1/Z$ (where $Z = q(\omega)$). By setting the test function $f = 1/\omega$, the authors derive conditions where the unbiased estimator has finite moments and achieves asymptotic equivalence to the natural SNIS estimator $1/\hat{Z}_N$, even when $p$ is not strictly greater than 4 (a condition required for general $f$).

4. Significance and Applications

The paper argues that while SNIS is asymptotically more efficient in terms of variance, IMH (and its unbiased variants) offers superior bias properties in specific regimes, making it a viable alternative for tasks where bias is detrimental.

The authors illustrate these findings through three applications:

1. Inverse Normalizing Constants: Comparing Coupling-UIS against MLMC-UIS and Taylor-UIS methods. Results show Coupling-UIS achieves the same asymptotic inefficiency as SNIS but with lower computational overhead than other unbiased methods.
2. Nested Expectations: In the context of Bayesian inference with missing data, the paper demonstrates that using unbiased estimators (Coupling-UIS) for the inner expectation allows for optimal budget allocation, recovering the canonical Monte Carlo convergence rate ($O(C^{-1})$) for the nested expectation, whereas biased estimators suffer from slower rates ($O(C^{-2/3})$ or $O(C^{-4/5})$).
3. Robust Mean Estimation: The paper applies Coupling-UIS to Median-of-Means (MoM) estimators. Since MoM requires unbiased inputs to guarantee sub-Gaussian concentration inequalities, the unbiased nature of Coupling-UIS allows for the direct application of MoM without the theoretical adjustments required for biased SNIS inputs.

5. Conclusion

The paper provides a rigorous theoretical foundation for the use of IMH and unbiased IS when weight functions are unbounded. It establishes that:

• IMH converges polynomially with rates determined by the moments of the weight function.
• Coupling-based debiasing techniques can remove the bias of IS entirely while maintaining asymptotic efficiency comparable to SNIS.
• These unbiased estimators are particularly valuable for downstream tasks like nested expectations and robust statistics where bias cannot be tolerated.

The work distinguishes itself by providing explicit dependencies on both the number of iterations $t$ and the number of particles $N$, and by offering a practical, Rao–Blackwellized algorithm (Algorithm 6) that is implementable under the same conditions as standard SNIS.