Certified two-sided EIG bounds beyond Gaussian surrogates for nonlinear, black-box sequential experimental design

Problem statement

Estimating the expected information gain (EIG) is the computational core of Bayesian optimal experimental design (BOED): every design decision is an argmax over EIG estimates, so the estimator's error budget is the experiment's error budget. Exact EIG evaluation requires a nested integral over the data marginal and the posterior, and the standard nested Monte Carlo estimator pays for that nesting with slow convergence and a cost multiplied by inner-loop bias control. The practical alternative substitutes a tractable surrogate for the intractable distribution, which yields two-sided bounds: approximating the posterior gives a lower bound in the Barber-Agakov family, and approximating the data marginal gives an upper bound. The unsolved problem is the gap between those bounds when the posterior is genuinely non-Gaussian. With Gaussian or Laplace surrogates the bounds are cheap, but their gap is uncontrolled exactly in the regime that black-box and PDE-constrained inverse problems produce: early sequential steps with little data, skewed or multimodal posteriors, and strongly nonlinear forward maps. Gruhlke, Hanu, Schillings and Wacker (arXiv:2504.13320) document this concretely in the gradient-free setting: at the first sequential step their joint samples are visibly non-Gaussian and the Gaussian lower bound degrades; a parametrized Laplace approximation repairs part of the gap at the cost of one optimization per observation sample; and every available tightness guarantee holds only in a limit, near-linearity ($\tau \to 0$), small noise or large data ($\varepsilon \to 0$), or infinite samples in a linear model ($J \to \infty$). Outside those limits nothing controls the gap, and an uncontrolled gap can silently reorder the candidate designs, which corrupts every observation the sequential procedure then chooses to acquire. There is also a known impossibility that shapes the problem: distribution-free, high-confidence lower bounds on mutual information require sample sizes exponential in the size of the bound (McAllester and Stratos, 2020). A resolution therefore cannot be distribution-free. It has to name and exploit the structure BOED actually has, a likelihood known in closed form up to normalization and a forward model that can be simulated at chosen designs, and stating the minimal structure that suffices for a certificate is part of the challenge. The challenge, stated as one sentence: construct EIG estimators, or bound pairs, for nonlinear and possibly multimodal posteriors that carry a certified, computable control of their error valid outside asymptotic limits, remain compatible with black-box forward models (no derivatives or adjoints of the forward map), and scale in parameter and design dimension without nested-Monte-Carlo cost blowup. A resolution would make sequential BOED trustworthy for the simulators where gradient-free methods are the only option, which is precisely where experimental data is most expensive and design decisions matter most.

Current state

Four families define the state of the art, and each one misses at least one of the three requirements (certificate, black-box compatibility, scale). 1. Nested Monte Carlo. Consistent and asymptotically exact, but the nesting makes it the benchmark rather than the tool: the surveys of Rainforth, Foster, Ivanova and Smith (2024) and Huan, Jagalur and Marzouk (2024) both treat its cost as the reason the field exists. Quasi-Monte Carlo variants reduce constants, not the structure. 2. Variational and amortized bounds. The Barber-Agakov lower bound (2003) and the bound taxonomy of Poole et al. (2019) are tight only when the variational family reaches the true posterior or marginal, and no computable certificate reports how far away the family is in a given problem. Amortized sequential methods in the line of Foster et al. (2019) additionally require differentiable models and a training phase, which the black-box setting rules out. 3. Gaussian and Laplace surrogates. These give cheap two-sided bounds, and their convergence is understood in restrictive regimes: Laplace-based EIG estimation goes back to Long, Scavino, Tempone and Wang (2013); Schillings, Sprungk and Wacker (2020) prove convergence of the Laplace approximation in the small-noise limit; Gruhlke et al. (arXiv:2504.13320) extend that analysis to KL divergence (their Theorem 3.3, rate $O(\varepsilon^{1/2})$) and prove $O(J^{-1})$ sample convergence for linear models (their Lemma 3.4). The same paper shows the failure mode outside those regimes, a visibly non-Gaussian first-step posterior where the Gaussian lower bound degrades, and names Gaussian mixtures as future work without any gap control attached. 4. Transport maps. Koval, Herzog and Scheichl (2024) and the subspace-accelerated sequential version of Cui, Koval, Herzog and Scheichl (2025) give expressive posterior and marginal approximations for design, but the resulting estimates carry no certified two-sided gap, and both papers state high-dimensional scalability as an open difficulty in their own text. Why the problem stays open: no existing method delivers computable, non-asymptotic, two-sided control of the EIG for nonlinear or multimodal posteriors at a forward-solve budget compatible with black-box models. The McAllester-Stratos impossibility (2020) explains why generic estimators cannot close this, so the missing piece is a certificate that provably spends the structure of the design problem, and no published work has stated the sufficient structure, let alone built the estimator on it.

Resolution criteria

A paper resolves this Grand Challenge when it does all of the following. 1. Bound pair with a certificate. It exhibits estimators $L(p) \le \mathrm{EIG}(p) \le U(p)$, computable from finitely many forward-model evaluations with no derivatives or adjoints of the forward map, together with a proven non-asymptotic guarantee on $U(p) - L(p)$ for a stated class of nonlinear forward models. The class must not reduce to near-linear perturbations ($G = A(p)u + \tau F$ with small $\tau$), and the guarantee must not require a small-noise, large-data, or infinite-sample limit. 2. Multimodal demonstration. On at least one benchmark whose posterior is verifiably multimodal at some design, it reports a relative gap $U - L \le 0.1 \cdot \widehat{\mathrm{EIG}}_{\mathrm{ref}}$, where $\widehat{\mathrm{EIG}}_{\mathrm{ref}}$ is a double-loop nested Monte Carlo reference computed with at least $10^7$ total samples, and the reference value lies in $[L, U]$. 3. Scale and comparison. On a PDE-constrained or simulation-based problem with parameter dimension $d \ge 100$ and design dimension $\ge 10$, it reports cost in forward solves at matched budget against nested Monte Carlo and at least one transport-map or variational baseline, and the design ranking induced by its bounds reproduces the reference estimator's top choice on the benchmark's design set, or reports the regret of its top choice under the reference estimator and keeps it within a tolerance the paper states and justifies. 4. Sequential compatibility. It either operates in the sequential setting, reusing posterior samples across design steps, or states explicitly why the certificate cannot survive sequential reuse. A paper that meets criteria 1 and 2 but not the scale of criterion 3 is major progress to link on this thread, not a resolution.

Citations

1. R. Gruhlke, M. Hanu, C. Schillings, and P. Wacker, Gradient-free sequential Bayesian experimental design via interacting particle systems, arXiv:2504.13320, 2025.
2. A. Foster, M. Jankowiak, E. Bingham, P. Horsfall, Y. W. Teh, T. Rainforth, and N. Goodman, Variational Bayesian optimal experimental design, Advances in Neural Information Processing Systems 32, 2019.
3. B. Poole, S. Ozair, A. van den Oord, A. Alemi, and G. Tucker, On variational bounds of mutual information, Proceedings of the 36th International Conference on Machine Learning, PMLR 97, 2019.
4. T. Rainforth, A. Foster, D. R. Ivanova, and F. B. Smith, Modern Bayesian experimental design, Statistical Science, 39 (2024), pp. 100-114.
5. X. Huan, J. Jagalur, and Y. Marzouk, Optimal experimental design: Formulations and computations, Acta Numerica, 33 (2024), pp. 715-840.
6. C. Schillings, B. Sprungk, and P. Wacker, On the convergence of the Laplace approximation and noise-level-robustness of Laplace-based Monte Carlo methods for Bayesian inverse problems, Numerische Mathematik, 145 (2020), pp. 915-971.
7. K. Koval, R. Herzog, and R. Scheichl, Tractable optimal experimental design using transport maps, Inverse Problems, 40 (2024), 125002.
8. T. Cui, K. Koval, R. Herzog, and R. Scheichl, Subspace accelerated measure transport methods for fast and scalable sequential experimental design, with application to photoacoustic imaging, arXiv:2502.20086, 2025.
9. D. McAllester and K. Stratos, Formal limitations on the measurement of mutual information, Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, PMLR 108, 2020.
10. Q. Long, M. Scavino, R. Tempone, and S. Wang, Fast estimation of expected information gains for Bayesian experimental designs based on Laplace approximations, Computer Methods in Applied Mechanics and Engineering, 259 (2013), pp. 24-39.
11. D. Barber and F. V. Agakov, The IM algorithm: a variational approach to information maximization (published in the NIPS 16 proceedings as: Information maximization in noisy channels: a variational approach), Advances in Neural Information Processing Systems 16, 2003.

Linked papers

• Gradient-Free Sequential Bayesian Experimental Design via Interacting Particle Systemsrelated1 Sept 2026
• Certified Two-Sided Finite-Sample Bounds on Expected Information Gain from Mixture Surrogatesdeclared at submission7 Sept 2026