Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputs
This work addresses the lack of theoretical understanding in guided-diffusion BO for structured design problems, which is important for practitioners but remains incremental as it provides a theoretical framework rather than a new algorithm or breakthrough performance.
The paper provides the first regret analysis for guided-diffusion black-box optimization over structured inputs, introducing a certificate-based expected simple-regret framework that avoids standard assumptions. It shows how exponential convergence and polynomial acceleration arise from mass lift, and offers practical diagnostics and a certified sampler.
Guided-diffusion black-box optimization (BO) has shown strong empirical performance on structured design problems such as molecules and crystals, but its regret behavior remains poorly understood. Existing BO regret analyses typically rely on maximum information gain, non-pretrained surrogate models, or exact acquisition maximization -- assumptions that break down in modern diffusion -- BO pipelines, where pretrained diffusion models serve as powerful priors over valid structures and acquisition maximization is replaced by approximate sampling over astronomically large discrete spaces. We develop a first certificate-based expected simple-regret framework for guided-diffusion BO that avoids maximum-information-gain bounds, RKHS assumptions, and exact acquisition maximization. The central quantity in our analysis 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 all arise from the same mechanism. We also give practical diagnostics for estimating search exponents from finite candidate pools and a proposal-corrected resampling construction that provides a fully certified sampler instance.