Research map / Probabilistic and scientific modeling / Bayesian optimization
Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization
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.
Studies normalizing constant estimation of RKHS (Matérn) black-box functions via Gaussian processes, showing the difficulty interpolates between Bayesian quadrature (small lambda) and Bayesian optimization (large lambda), with noisy and noiseless upper and lower bounds plus a two-batch MVS-LMC algorithm.
Problem
Estimating the normalizing constant integral of exp(-lambda f(x)) over a domain using only zeroth-order (noisy) queries to an RKHS-bounded black-box function, with relative error guarantees.
Approach
Frames normalizing constant estimation as a problem that interpolates between BQ (lambda to 0) and BO (lambda to infinity), derives matching-type lower bounds and a GP-based two-batch algorithm (maximum variance sampling then Langevin Monte Carlo residual correction) that works with multiplicative relative error.
Key results
- Noiseless lower bound Omega(T^{-nu/d-1+c}) for lambda=Theta(T^c), matching the BQ rate at c=0 and the BO rate Omega(T^{-nu/d}) at c=1 (nu>=d/2).
- Noisy setting with constant noise (sigma=Theta(1)): lower bound Omega(T^{-1/2}) at lambda=Theta(1), matching noisy BQ, and Omega(T^{-nu/(2nu+d)}) achievable with a suitable lambda scaling, matching noisy BO.
- Experiments show MVS and MVS-LMC outperform MC, PC and PC-MC, especially at low query budgets (a few hundred), with GP methods better than PC for small budgets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase λ toward infinity | normalizing constant estimation for RKHS functions · NC estimation | relative error difficulty | Hurt |
| use small λ and low observation noise | MVS and MVS-LMC · simple analytic functions | mean absolute relative error | Helped |
| use MVS-LMC instead of MC | MVS-LMC · simple analytic functions with larger λ and σ | mean absolute relative error: O(T^{-\frac{1}{2}}) | No clear effect |
| add the LMC second-batch component (ablation) | MVS · MLP and PSF | mean absolute relative error | Helped |
| add the LMC second-batch component (ablation) | MVS · some settings | mean absolute relative error | No clear effect |
| use both batches instead of the intermediate first-batch estimate (ablation) | MVS-LMC · noisy NC estimation when the stated conditions for both bounds hold | relative error upper bound: O(\frac{1}{\sqrt{T}}) factor | Helped |
Surprising findings
- For some noise and lambda regimes, NC estimation is strictly harder than BO, requiring more samples for large lambda.
- Under constant noise, the best upper bound from the proposed method does not match the noisy lower bound, leaving a gap.
Limitations
- Upper bounds have an extra Theta(sqrt(T)) gap relative to noiseless lower bounds due to L-infinity based analysis.
- Langevin sampling approximation error is not accounted for in the theory.
- Squared exponential kernel is not covered by the lower-bound techniques.
Experimental setup
Datasets: synthetic RKHS functions Ackley Alpine Product-Peak Zhou 8-dimensional MLP functions point spread function (Airy pattern)
Benchmarks: synthetic RKHS functions Ackley Alpine Product-Peak Zhou 8-dimensional MLP PSF
Metrics: mean absolute relative error lower and upper bound exponents
Baselines: Monte Carlo quadrature PC PC-MC
Builds on: Bayesian quadrature Bayesian optimization GP-UCB Langevin dynamics
Closest papers by meaning
- Bayesian Optimization on Function Spaces via Sparse RKHS Manifolds (NeurIPS 2026 · similarity 0.86)
- Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization (ICLR 2025 · similarity 0.85)
- Kernel-based guarantees for nonlinear parametric models in Bayesian optimization (NeurIPS 2026 · similarity 0.85)
- Stochastic Bayesian Optimization with Unknown Continuous Context Distribution via Kernel Density Estimation (AAAI 2024 · similarity 0.85)
- Vanilla Bayesian Optimization Performs Great in High Dimensions (ICML 2024 · similarity 0.85)
- Optimal kernel regression bounds under energy-bounded noise (NeurIPS 2025 · similarity 0.85)
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.