REVIEW 2 major objections 4 minor 37 references
Revisiting the balance heuristic for estimating normalising constants
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The balance heuristic estimator is exactly an importance sampling estimator on an extended space whose target has the same normalising constant, and this representation yields an unbiased modified annealed estimator.
desk verdict The extended-space representation and modified AIS are the real contributions; the intractable-proposal estimator Ẑ_GF2 has an unproved bias claim that points the wrong way as K grows. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The object that carries the argument is an extended-space target. The key identity is the representation of $\hat Z_{\mathrm{BH}}$ as an importance weight for the joint proposal $\bar q^{\otimes N}(x_{1:N},l_{1:N})=\prod_{n=1}^N q_{l_n}(x_n)\alpha(l_n)$ when the target is $\eta_{\mathrm{BH}}$ of Eq. (8). This is what lets the paper view balance heuristic as a single point in a higher-dimensional space and bridge it to $\bar q^{\otimes N}$ by annealed intermediate distributions. The second load-bearing mechanism is the modified annealed importance sampling recursion of Algorithm 2, which keeps the labels $l_{1:N}$ fixed, runs independent annealed chains for each conditional $\eta_t(dx_n|n,l_{1:N})$, and multiplies the per-chain weights; Theorem 2 shows the resulting estimator is unbiased. In the intractable setting, the general target $\eta_{\mathrm{GF}}$ with surrogate functions $\psi_n$ and $\rho_n$ plays the same role, allowing the balance-heuristic weighting to be mimicked using only joint evaluations $\bar q(x,l)$.
What would settle it
Take the running example with a diffuse marginal proposal ($s=20$) and very large $K$ (for instance $K=3\times 10^6$) and compare the estimators; the paper's own Figures 5 and 6 show that $\hat Z_{\mathrm{GF1}}$ and $\hat Z_{\mathrm{GF2}}$ develop high variance or clear bias there, while the balance heuristic loses its cost advantage when $K_{\mathrm{eff}}$ approaches $K$. The claim would be settled by measuring variance per unit cost of $\hat Z_{\mathrm{BH}}$ against $\hat Z_{\mathrm{RB}}$ in a regime with $K_{\mathrm{eff}}\approx K$.
Extended reading notes
Core claim
The paper's central claim is that the balance heuristic estimator $$\hat Z_{\mathrm{BH}} = \sum_{n=1}^N \frac{\tilde\pi(X_n)}{\sum_{m=1}^N q_{L_m}(X_n)}, \qquad (X_n,L_n)\sim q_{L_n}\$\alpha$,$$ is exactly an importance sampling estimator with a single point on the space $\{1,\dots,N\}\times \mathcal{X}^N\times\{1,\dots,K\}^N$ under the extended target $$\eta_{\mathrm{BH}}(n,x_{1:N},l_{1:N}) = \frac{\pi(x_n)q_{l_n}(x_n)}{\sum_{m=1}^N q_{l_m}(x_n)}\,\$\alpha$(l_n)\prod_{m\neq n} q_{l_m}(x_m)\$\alpha$(l_m).$$ The normalising constant of $\eta_{\mathrm{BH}}$ is $Z$, by construction, even though $\pi$ cannot be recovered by marginalising any variable. Theorem 2 proves that the modified annealed importance sampling estimator of Algorithm 2 is unbiased for $Z$, and standard AIS theory gives that its variance is no larger than that of $\hat Z_{\mathrm{BH}}$. The paper then generalises the construction to $\eta_{\mathrm{GF}}(n,x_{1:N},l_{1:N})\propto \pi(x_n)\frac{\psi_n(x_n)}{\sum_{m=1}^N\psi_m(x_n)}\rho_n\prod_{m\neq n}\bar q(x_m,l_m)$, which contains balance heuristic ($\psi_n=q_{l_n}$, $\rho_n=\alpha(l_n)$) and the combined-estimator scheme ($\psi_n\equiv 1$, $\rho_n=\nu_{l_n}$) as special cases.
Load-bearing premise
The load-bearing premise is that the effective number of distinct proposals actually drawn, $K_{\mathrm{eff}}$, is much smaller than the pool size $K$; the paper states in Section 4 that $K_{\mathrm{eff}}\ll K$ is vital, and its own figures show deterioration when the marginal proposal is diffuse or $K$ is huge.
Editorial extensions
If this is right
- For any number of annealing steps $T\ge 1$, the modified annealed importance sampling estimator $\hat Z_{T,\mathrm{mAIS}}$ is unbiased for $Z$ and has variance at most that of the plain balance heuristic estimator (Theorem 2).
- Because the $N$ per-point chains in Algorithm 2 are conditionally independent given the labels, the estimator can be computed by $N$ parallel processes, each of cost $O(TN)$, replacing the serial $O(TN^2)$ weight computation of standard AIS.
- In the intractable-proposal setting, the estimators $\hat Z_{\mathrm{GF1}}$ and $\hat Z_{\mathrm{GF2}}$ require only evaluations of the joint density $\bar q(x,l)$, so they apply when the conditional $q_l(x)$ and label distribution $\alpha(l)$ are individually unavailable, as with order-induced labels.
- The computational cost of balance heuristic is $O(NK_{\mathrm{eff}})$, which is much less than $O(NK)$ when the effective number of sampled labels $K_{\mathrm{eff}}$ is small, so balance heuristic remains competitive against Rao-Blackwellized estimation for equal computational cost.
Reading between the lines
- If the extended-space representation is correct, the per-point weights of Algorithm 2 could be reused across independent draws of the labels, giving a Rao-Blackwellized version of the modified AIS estimator that the paper does not explore.
- The general framework suggests a constructive design rule: any approximation $\psi_n$ of the unavailable conditional $q_{l_n}$ that makes the denominator $\sum_m \psi_m(x)$ track $\sum_m q_{l_m}(x)$ should inherit the balance heuristic's variance reduction; a natural testable extension is to estimate $\psi_n$ adaptively from a pilot sample.
- A sequential Monte Carlo version of the modified AIS, which the paper flags as nontrivial because resampling can break unbiasedness, would turn balance heuristic into an online particle method; this is an open extension rather than a claim of the paper.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper revisits the balance heuristic for estimating normalising constants when the number of proposals K is much larger than the number of importance points N. It introduces an extended-space representation of the balance heuristic (Eq. 8), from which it derives a modified annealed importance sampling estimator (Algorithm 2) and proves its unbiasedness (Theorem 2). The paper then considers the intractable-proposal setting in which only the joint density \bar{q}(x,l) is available, and proposes a general framework (Eq. 14) that includes both the balance heuristic and linear combinations of unbiased estimators. Two specific estimators, \hat{Z}_{GF1} and \hat{Z}_{GF2}, are introduced and compared numerically on a Gaussian running example. The paper is explicitly candid about the bias of \hat{Z}_{comb} and about the regime restrictions implied by K_eff << K, but the treatment of \hat{Z}_{GF2} in the advertised K >> N regime is not supported by the analysis.
Significance. The extended-space representation of the balance heuristic is a genuinely useful conceptual contribution: it yields a clean derivation of the modified annealed importance sampling estimator, with an unbiasedness proof in Theorem 2, and it provides a common framework that contains both the balance heuristic and combinations of unbiased estimators. The proofs in Appendix 1 are substantially complete and appear correct for the balance-heuristic part. The paper is also commendably honest about the limitations of \hat{Z}_{comb}. However, the main new estimator for the intractable-proposal setting, \hat{Z}_{GF2}, is advertised for the regime K >> N with N fixed, while its bias is only argued to vanish as N → ∞; the numerical results in Figure 5 are consistent with a substantial bias in exactly that regime. In addition, the displayed formula for \hat{Z}_{GF1} is internally inconsistent with the general estimator definition, changing its expectation by a factor of N. The core contribution on the balance heuristic and annealed importance sampling is sound, but the Section 3 claims need substantial revision.
major comments (2)
- [Section 3.3, Eq. (14), Proposition 2, Figure 5] The claim that the bias of \hat{Z}_{GF2} 'vanishes as N → ∞ due to the consistency of ρ_n' addresses only the N-asymptotic, whereas the paper motivates GF2 precisely for K >> N with N fixed. From Eq. (14) and Proposition 2, the expectation of \hat{Z}_{GF2} is Z times \mathcal{Z} = E_{L,X∼π}[Σ_n q_{L_n}(X) ρ_n / (Σ_m q_{L_m}(X) α(L_m))]. For fixed N and K → ∞, most sampled labels are unique, giving ρ_n ≈ 1/(NK); when α is diffuse this yields ρ_n/α(L_n) ≈ 1/N and hence \mathcal{Z} ≈ 1/N, not 1. The empirical bias in Figure 5(c) (s = 20, K = 3 × 10^6, N = 500) is consistent with this concern. No finite-N bias bound, convergence rate, or K-asymptotic argument is supplied. Because K >> N is the advertised regime, this is a load-bearing gap: either the bias must be proved to vanish in the relevant asymptotic, or \hat{Z}_{GF2} must be repositioned as a heuristic whose bias is an explicit limitation.
- [Section 3.3, displayed formula for \hat{Z}_{GF1}] The general definition of \hat{Z}_{GF} in the paragraph immediately above gives \hat{Z}_{GF1} = Σ_n [\tilde{π}(X_n)/\bar{q}(X_n,L_n)] ρ_n, where ρ_n = (K^{-1} - 1 + N_{L_n})/N; this is (1/N) Σ_n [\tilde{π}(X_n)/\bar{q}(X_n,L_n)] (K^{-1} - 1 + N_{L_n}). The displayed equation for \hat{Z}_{GF1} instead contains an additional factor 1/N. With that displayed estimator, E[\hat{Z}_{GF1}] = Z/N rather than Z; with the general formula, Proposition 2 gives E[\hat{Z}_{GF1}] = Z. This inconsistency changes the unbiasedness of the estimator by a factor of N and must be corrected. The numerical experiments should also state explicitly which version was implemented.
minor comments (4)
- [Proposition 2 and Eq. (14)] The symbol Z is used both for the unknown normalising constant of π and for the integral of η_{GF}, which equals 1 for the balance heuristic and for GF1 but need not equal the target normalising constant. Renaming the latter, e.g. \mathcal{Z}(Ψ,ρ), would prevent a serious source of confusion.
- [Algorithm 1] The pseudocode contains a duplicated loop line 'for t ∈ [1,T − 1] do'; one of the duplicated lines should be removed.
- [Abstract and title] There is a typographical error in 'normalisi ng constants' in the title line of the arXiv text; it should read 'normalising constants'.
- [Figures 2 and 6] The boxplot labels such as AIS_M3, AIS_M2, AIS_M1, AIS_G, and GF_T1 are not all defined in the captions or text; a brief explanation of the naming convention would improve readability.
Circularity Check
No significant circularity: the extended-space targets are explicit identities and the new estimators are honestly labelled as biased where applicable.
full rationale
The paper's central move (Section 2.2, Eq. 8) is to multiply the balance heuristic estimator by the joint proposal density and divide by Z, so the extended target eta_BH has normalising constant Z by construction. This is an identity, not a circular derivation: Proposition 1 independently establishes E(Z_BH)=Z, and Theorem 2 proves unbiasedness of the modified annealed importance sampling estimator by the standard AIS telescoping argument, using the direct integral of the unnormalised extended density rather than assuming the conclusion. The general framework of Section 3.3 (Eq. 14, Proposition 2) is likewise an explicit integral identity for an arbitrary choice of psi and rho. The estimators Z_GF1 and Z_GF2 are presented as approximations for intractable proposals, with the paper transparently stating that Z_GF2 is biased by construction and that Z_comb's weights are estimated from the same sample, so its unbiasedness is not claimed. The only substantial caveats are correctness and robustness issues, not circularity: the bias of Z_GF2 is asserted to vanish only as N tends to infinity (Section 3.3), while the motivating regime is K >> N with N fixed, and Section 4 concedes that the methods rely on K_eff << K. These limitations are acknowledged in the manuscript and do not reduce the derivations to their inputs.
Assumptions & free parameters
assumptions (5)
- standard math Standard importance sampling unbiasedness (Proposition 1)
- standard math MCMC invariance of K_{t,n} implies that integrating the previous state with the transition kernel yields the target density, enabling the telescoping product in Theorem 2.
- domain assumption Proposal densities are bounded away from 0 and infinity on X in Theorem 1.
- domain assumption The joint proposal q̄(x,l) can be evaluated pointwise while q_l(x) and α(l) cannot be evaluated separately.
- ad hoc to paper For Ẑ_GF2, the consistency of ρ_n as N→∞ is asserted to imply vanishing bias.
Cite this review
Pith. "Pith review of Revisiting the balance heuristic for estimating normalising constants." pith.science (2026). https://pith.science/paper/W3EXVGA3
@misc{pith2026190806514,
author = {Pith},
title = {Pith review of: Revisiting the balance heuristic for estimating normalising constants},
year = {2026},
howpublished = {\url{https://pith.science/paper/W3EXVGA3}},
note = {Machine review of arXiv:1908.06514}
}
read the original abstract
Multiple importance sampling estimators are widely used for computing intractable constants due to its reliability and robustness. The celebrated balance heuristic estimator belongs to this class of methods and has proved very successful in computer graphics. The basic ingredients for computing the estimator are: a set of proposal distributions, indexed by some discrete label, and a predetermined number of draws from each of these proposals. However, if the number of available proposals is much larger than the number of permitted importance points, one needs to select, possibly at random, which of these distributions will be used. The focus of this work lies within the previous context, exploring some improvements and variations of the balance heuristic via a novel extended-space representation of the estimator, leading to straightforward annealing schemes for variance reduction purposes. In addition, we also look at the intractable scenario where the proposal density is only available as a joint function with the discrete label, as may be encountered in problems where an ordering is imposed. For this case, we look at combinations of correlated unbiased estimators which also fit into the extended-space representation and, in turn, will provide other interesting solutions.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
Andrieu, C. & Roberts, G. O. (2009). T he pseudo-marginal approach for efficient M onte C arlo computations. Ann. Statist. 37, 697--725
work page 2009
-
[2]
Beaumont, M. A. (2003). E stimation of P opulation G rowth or D ecline in G enetically M onitored P opulations. Genetics 164, 1139--1160
work page 2003
-
[3]
Online Variance Reduction with Mixtures
Borsos, Z. , Curi, S. , Levy, K. Y. & Krause, A. (2019). Online variance reduction with mixtures. arXiv preprint arXiv:1903.12416
work page Pith review arXiv 2019
-
[4]
Capp \'e , O. , Guillin, A. , Marin, J.-M. & Robert, C. P. (2004). Population monte carlo. Journal of Computational and Graphical Statistics 13, 907--929
work page 2004
-
[5]
Cornuet, J.-M. , Marin, J.-M. , Mira, A. & Robert, C. P. (2012). Adaptive multiple importance sampling. Scandinavian Journal of Statistics 39, 798--812
work page 2012
-
[6]
Del Moral, P. , Doucet, A. & Jasra, A. (2006). S equential M onte C arlo samplers. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 68, 411--436
work page 2006
-
[7]
Asymptotic optimality of adaptive importance sampling
Delyon, B. & Portier, F. (2018). Efficiency of adaptive importance sampling. arXiv preprint arXiv:1806.00989
work page Pith review arXiv 2018
-
[8]
Douc, R. , Guillin, A. , Marin, J.-M. , Robert, C. P. et al. (2007). Convergence of adaptive mixtures of importance sampling schemes. The Annals of Statistics 35, 420--448
work page 2007
Show all 37 references
-
[9]
, de Freitas, N
Doucet, A. , de Freitas, N. & Gordon, N. (2001). S equential M onte C arlo M ethods in P ractice . Information Science and Statistics. Springer New York
2001
-
[10]
, Martino, L
Elvira, V. , Martino, L. , Luengo, D. & Bugallo, M. F. (2015). Efficient multiple importance sampling estimators. IEEE Signal Processing Letters 22, 1757--1761
2015
-
[11]
, Martino, L
Elvira, V. , Martino, L. , Luengo, D. & Bugallo, M. F. (2017). Improving population monte carlo: Alternative weighting and resampling schemes. Signal Processing 131, 77--91
2017
-
[12]
, Martino, L
Elvira, V. , Martino, L. , Luengo, D. , Bugallo, M. F. et al. (2019). Generalized multiple importance sampling. Statistical Science 34, 129--155
2019
-
[13]
Everitt , R. G. , Culliford , R. , Medina-Aguayo , F. & Wilson , D. J. (2016). Sequential Monte Carlo with transformations . ArXiv e-prints
2016
-
[14]
, Samworth, R
Gramacy, R. , Samworth, R. & King, R. (2010). Importance tempering. Statistics and Computing 20, 1--7
2010
-
[15]
He, H. Y. & Owen, A. B. (2014). Optimal mixture weights in multiple importance sampling. arXiv preprint arXiv:1411.3954
2014 arXiv
-
[16]
Hesterberg, T. (1995). Weighted average importance sampling and defensive mixture distributions. Technometrics 37, 185--194
1995
-
[17]
Jarzynski, C. (1997). Nonequilibrium Equality for Free Energy Differences . Physical Review Letters 78, 2690
1997
-
[18]
& Singh, S
Jiang, L. & Singh, S. S. (2018). Tracking multiple moving objects in images using markov chain monte carlo. Statistics and Computing 28, 495--510
2018
-
[19]
, Singh, S
Jiang, L. , Singh, S. S. & Y ld r m, S. (2015). Bayesian tracking and parameter learning for non-linear multiple target tracking models. IEEE Transactions on Signal Processing 63, 5733--5745
2015
-
[20]
& Andrieu, C
Karagiannis, G. & Andrieu, C. (2013). Annealed Importance Sampling Reversible Jump Mcmc Algorithms . Journal of Computational and Graphical Statistics 22, 623--648
2013
-
[21]
Li, S. , Yi, W. , Hoseinnezhad, R. , Wang, B. & Kong, L. (2017). Multiobject tracking for generic observation model using labeled random finite sets. IEEE Transactions on Signal Processing 66, 368--383
2017
-
[22]
, Chen, R
Li, W. , Chen, R. & Tan, Z. (2016). Efficient sequential monte carlo with multiple proposals and control variates. Journal of the American Statistical Association 111, 298--313
2016
-
[23]
, Elvira, V
Martino, L. , Elvira, V. , Luengo, D. & Corander, J. (2015). An adaptive population importance sampler: Learning from uncertainty. IEEE Transactions on Signal Processing 63, 4422--4437
2015
-
[24]
, Elvira, V
Martino, L. , Elvira, V. , Luengo, D. & Corander, J. (2017). Layered adaptive importance sampling. Statistics and Computing 27, 599--623
2017
-
[25]
Neal, R. M. (2001). Annealed Importance Sampling . Statistics and computing 11, 125--139
2001
-
[26]
, Lindsten, F
Nemeth, C. , Lindsten, F. , Filippone, M. & Hensman, J. (2017). Pseudo-extended markov chain monte carlo. arXiv preprint arXiv:1708.05239
2017 arXiv
-
[27]
Nguyen, T. L. T. , Septier, F. , Peters, G. W. & Delignon, Y. (2015). Efficient sequential monte-carlo samplers for bayesian inference. IEEE Transactions on Signal Processing 64, 1305--1319
2015
-
[28]
& Zhou, Y
Owen, A. & Zhou, Y. (2000). Safe and Effective Importance Sampling . Journal of the American Statistical Association 95, 135--143
2000
-
[29]
Owen, A. B. & Zhou, Y. (2019). The square root rule for adaptive importance sampling. arXiv preprint arXiv:1901.02976
2019 arXiv
-
[30]
& Casella, G
Robert, C. & Casella, G. (2013). M onte C arlo S tatistical M ethods . Springer Texts in Statistics. Springer New York
2013
-
[31]
& Evangelou, E
Roy, V. & Evangelou, E. (2018). Selection of proposal distributions for generalized importance sampling estimators. arXiv preprint arXiv:1805.00829
2018 arXiv
-
[32]
& Elvira, V
Sbert, M. & Elvira, V. (2019). Generalizing the balance heuristic estimator in multiple importance sampling. arXiv preprint arXiv:1903.11908
2019 arXiv
-
[33]
& Havran, V
Sbert, M. & Havran, V. (2017). Adaptive multiple importance sampling for general functions. The Visual Computer 33, 845--855
2017
-
[34]
, Havran, V
Sbert, M. , Havran, V. & Szirmay-Kalos, L. (2016). Variance analysis of multi-sample and one-sample multiple importance sampling. In Computer Graphics Forum, vol. 35. Wiley Online Library
2016
-
[35]
, Havran, V
Sbert, M. , Havran, V. & Szirmay-Kalos, L. (2018). Multiple importance sampling revisited: breaking the bounds. EURASIP Journal on Advances in Signal Processing 2018, 15
2018
-
[36]
& Guibas, L
Veach, E. & Guibas, L. J. (1995). Optimally Combining Sampling Techniques for Monte Carlo Rendering . In Proceedings of the 22Nd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '95. New York, NY, USA: ACM
1995
-
[37]
& Roberts, G
Zanella, G. & Roberts, G. (2018). Scalable importance tempering and bayesian variable selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology)
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.