Research map / Probabilistic and scientific modeling / Variational and generative sampling
Nested Expectations with Kernel Quadrature
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes nested kernel quadrature (NKQ), a two-stage estimator that nests kernel quadrature estimators for inner and outer expectations, with a proven rate of Õ(Δ^{-d_X/s_X - d_Θ/s_Θ}) that beats NMC/NQMC/MLMC under smoothness.
Problem
Estimating nested expectations E_θ[f(E_X[g(X,θ)])], where standard nested Monte Carlo and multilevel Monte Carlo are consistent but need very many samples at both levels to converge.
Approach
Replace both inner and outer Monte Carlo averages with kernel quadrature estimators (inner weights on g at points sampled per θ_t, then outer KQ over θ_t applied to f of inner estimates), yielding a nested quadrature rule with faster rates when integrands are smooth; the stage II noise is shown to be subsumed by stage I error.
Key results
- On the synthetic problem, NKQ reaches cost Δ^-1 versus NMC's Δ^-3 in theory, with empirical rate for NKQ on the option pricing problem of 1.90 (iid) versus theoretical 2.
- On the option pricing problem, NMC's empirical rate was 2.97 versus theoretical 3, while QMC-based NMC under-performed at 2.74 versus theoretical 2.5.
- On EVPPI (d_X=17, d_Θ=2), NKQ consistently outperforms NMC and MLMC, and in Bayesian optimisation NKQ achieves the lowest NMSE under fixed wall-clock time on all three BoTorch tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use nested kernel quadrature instead of nested Monte Carlo | Nested expectation estimation · Synthetic nested expectation | cost exponent: \Delta^{-3} -> \Delta^{-1} | Helped |
| Use NKQ instead of NMC or MLMC | Financial risk management · Financial risk management | mean absolute error | Helped |
| Use NKQ instead of NMC or MLMC | Value of information for healthcare decision making · Health economics | mean absolute error | Helped |
| Use NKQ instead of NMC or MLMC | Bayesian optimization with look-ahead acquisition · Dropwave, Ackley, and Cosine8 | NMSE | Helped |
| Use QMC samples instead of i.i.d. samples | NKQ · Financial risk management | empirical rate r: 1.90 -> 1.91 | No clear effect |
| Use QMC points with NKQ | NKQ · Nested expectation estimation | performance | No clear effect |
| Use QMC instead of i.i.d. samples | NMC · Financial risk management | empirical rate r: 2.97 -> 2.74 | Hurt |
| Increase problem dimension | NKQ versus NMC · Higher-dimensional synthetic nested expectation | performance gap | Hurt |
| Replace NKQ with MLKQ | Nested expectation estimation · Nested expectations | convergence rate: \tilde{\mathcal{O}}(\Delta^{-1 - \frac{d_\mathcal{X}}{2s_\mathcal{X}} -\frac{d_\Theta}{2s_\Theta}}) | Hurt |
| Increase the NKQ regularization parameter substantially (ablation) | NKQ · Synthetic nested expectation | accuracy | Hurt |
| Select kernel lengthscale using the median heuristic (ablation) | NKQ · Synthetic nested expectation | performance | Helped |
| Use Matérn-3/2 instead of Matérn-1/2 kernels (ablation) | NKQ · Synthetic nested expectation | performance | Helped |
Surprising findings
- NKQ with Matérn-1/2 kernels still outperforms baselines in Bayesian optimisation and option pricing even where smoothness assumptions are violated.
- NQMC under-performed its theoretical rate on option pricing (empirical 2.74 vs theoretical 2.5), attributed to unbounded domains and non-uniform measures.
Limitations
- Theory requires strong smoothness assumptions (Sobolev kernels with s > d/2, f with s_Θ+1 bounded derivatives) that are violated in several experiments.
- Cost degrades with dimension (Õ(Δ^{-d_X/s_X - d_Θ/s_Θ})), so the advantage vanishes in high dimension, as the synthetic experiment shows.
- Worst-case cost O(TN^3 + T^3) from solving linear systems, and requires closed-form kernel mean embeddings.
Experimental setup
Datasets: synthetic nested expectation problem Black-Scholes butterfly option loss EVPPI health economics model BoTorch synthetic BO tasks (Dropwave, Ackley, Cosine8)
Benchmarks: synthetic nested expectation financial risk management option loss EVPPI health economics Bayesian optimisation with two-step look-ahead on BoTorch tasks
Metrics: absolute error vs cost empirical convergence rate NMSE vs wall clock time
Baselines: NMC NQMC MLMC Bayesian quadrature conditional (CBQ) MLKQ
Builds on: kernel quadrature nested Monte Carlo multilevel Monte Carlo nested quasi-Monte Carlo Bayesian quadrature
Closest papers by meaning
- Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need (ICML 2024 · similarity 0.83)
- Decision Making under the Exponential Family: Distributionally Robust Optimisation with Bayesian Ambiguity Sets (ICML 2025 · similarity 0.82)
- Quasi-Monte Carlo Features for Kernel Approximation (ICML 2024 · similarity 0.81)
- Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization (AAAI 2024 · similarity 0.81)
- Fearless Stochasticity in Expectation Propagation (NeurIPS 2024 · similarity 0.81)
- Stochastic Bayesian Optimization with Unknown Continuous Context Distribution via Kernel Density Estimation (AAAI 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.