# Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputs

arXiv: https://arxiv.org/abs/2605.10385 · HTML: https://mlsanity.com/paper/2605.10385/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 56 of its 80 references that are in the map.
- First posted on arXiv 11 May 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 56)

- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Diffusion Model Alignment Using Direct Preference Optimization](https://mlsanity.com/paper/2311.12908/) (2023)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Crystal Diffusion Variational Autoencoder for Periodic Material Generation](https://mlsanity.com/paper/2110.06197/) (2021)
- [VEEGAN: Reducing Mode Collapse in GANs using Implicit Variational Learning](https://mlsanity.com/paper/1705.07761/) (2017)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Protein Design with Guided Discrete Diffusion](https://mlsanity.com/paper/2305.20009/) (2023)
- [Crystal Structure Prediction by Joint Equivariant Diffusion](https://mlsanity.com/paper/2309.04475/) (2023)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgetting](https://mlsanity.com/paper/2206.00761/) (2022)
- [Local Latent Space Bayesian Optimization over Structured Inputs](https://mlsanity.com/paper/2201.11872/) (2022)
- [Diffusion Models for Black-Box Optimization](https://mlsanity.com/paper/2306.07180/) (2023)
- [Amortizing intractable inference in diffusion models for vision, language, and control](https://mlsanity.com/paper/2405.20971/) (2024)
- [πBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization](https://mlsanity.com/paper/2204.11051/) (2022)
- [Deep Neural Networks Learn Non-Smooth Functions Effectively](https://mlsanity.com/paper/1802.04474/) (2018)
- [Generalized Variational Inference: Three arguments for deriving new Posteriors](https://mlsanity.com/paper/1904.02063/) (2019)
- [BOSS: Bayesian Optimization over String Spaces](https://mlsanity.com/paper/2010.00979/) (2020)
- [High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning](https://mlsanity.com/paper/2106.03609/) (2021)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [GAUCHE: A Library for Gaussian Processes in Chemistry](https://mlsanity.com/paper/2212.04450/) (2022)
- [A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methods](https://mlsanity.com/paper/2305.15027/) (2023)
- [Looping in the Human Collaborative and Explainable Bayesian Optimization](https://mlsanity.com/paper/2310.17273/) (2023)

## Built on by (most cited first, 1 of 1)

- [Open-ended Scientific Discovery with Possibilistic Reasoning](https://mlsanity.com/paper/2610.11289/) (2026)

## Abstract (arXiv)

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.