The authors develop a regret analysis framework for using pretrained diffusion models in black-box optimization over structured inputs like molecules or crystals. Traditional Bayesian optimization regret bounds rely on maximum information gain and exact acquisition maximization, which don't apply when you're using a pretrained diffusion model as a structural prior and sampling candidates rather than exactly optimizing an acquisition function. They propose a certificate-based framework where the key quantity is "mass lift" — how much more probability the guided diffusion assigns to near-optimal designs compared to the pretrained generator.
Main takeaways:
- Existing Bayesian optimization regret analyses don't apply to guided-diffusion pipelines because they assume non-pretrained surrogates and exact acquisition maximization.
- The authors introduce a certificate-based expected simple-regret framework that avoids maximum-information-gain bounds and RKHS assumptions.
- The central quantity is "mass lift": the increase in probability mass assigned to near-optimal designs relative to the pretrained generator.
- This view explains how exponential-looking finite-budget convergence and polynomial acceleration can arise from the same mechanism.
- The paper provides practical diagnostics for estimating search exponents from finite candidate pools and a proposal-corrected resampling construction for certified sampling.