mlsanityData to 14 Oct 2026

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

arXiv 2605.10385 ↗First posted 11 May 2026stat.ML cs.LGcited by 1

On the map: Diffusion models → Diffusion foundations and sampling

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.

Key facts. Cited by 1 paper 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.

Builds on

56 of 80 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization24 Feb
  2. 2024Diffusion Models are Evolutionary Algorithms3 Oct
  3. 2024Amortizing intractable inference in diffusion models for vision, language, and control31 May
  4. 2024Diffusion Model for Data-Driven Black-Box Optimization20 Mar
  5. 2023Diffusion Models for Black-Box Optimization12 Jun
  6. 2023Diffusion Models are Minimax Optimal Distribution Estimators3 Mar

Other references · 50

  1. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  2. 2022Flow Matching for Generative Modelingcited by 5,702
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  5. 2023Diffusion Model Alignment Using Direct Preference Optimizationcited by 790
  6. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 765
  7. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 520
  8. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 374
  9. 2021Crystal Diffusion Variational Autoencoder for Periodic Material Generationcited by 270
  10. 2017VEEGAN: Reducing Mode Collapse in GANs using Implicit Variational Learningcited by 200
  11. 2019BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Searchcited by 179
  12. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
38 more
  1. 2023Protein Design with Guided Discrete Diffusioncited by 157
  2. 2023Crystal Structure Prediction by Joint Equivariant Diffusioncited by 148
  3. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 141
  4. 2024Fast Best-of-N Decoding via Speculative Rejectioncited by 112
  5. 2022On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgettingcited by 82
  6. 2022Local Latent Space Bayesian Optimization over Structured Inputscited by 79
  7. 2022πBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimizationcited by 70
  8. 2018Deep Neural Networks Learn Non-Smooth Functions Effectivelycited by 57
  9. 2019Generalized Variational Inference: Three arguments for deriving new Posteriorscited by 57
  10. 2020BOSS: Bayesian Optimization over String Spacescited by 54
  11. 2021High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learningcited by 54
  12. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 51
  13. 2022GAUCHE: A Library for Gaussian Processes in Chemistrycited by 41
  14. 2023A Rigorous Link between Deep Ensembles and (Variational) Bayesian Methodscited by 32
  15. 2023Looping in the Human Collaborative and Explainable Bayesian Optimizationcited by 27
  16. 2021BORE: Bayesian Optimization by Density-Ratio Estimationcited by 26
  17. 2020Incorporating Expert Prior in Bayesian Optimisation via Space Warpingcited by 23
  18. 2023A General Framework for User-Guided Bayesian Optimizationcited by 22
  19. 2025Guiding Generative Models to Uncover Diverse and Novel Crystals via Reinforcement Learningcited by 21
  20. 2022A General Recipe for Likelihood-free Bayesian Optimizationcited by 19
  21. 2023Advancing Bayesian Optimization via Learning Correlated Latent Spacecited by 18
  22. 2022Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization (ZoMBI)cited by 14
  23. 2025Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spacescited by 14
  24. 2024Time-Varying Gaussian Process Bandits with Unknown Priorcited by 11
  25. 2022Batch Bayesian optimisation via density-ratio estimation with guaranteescited by 9
  26. 2024Approximation-Aware Bayesian Optimizationcited by 8
  27. 2024Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimalcited by 7
  28. 2026Verifier-Constrained Flow Expansion for Discovery Beyond the Datacited by 7
  29. 2023Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approachcited by 6
  30. 2025Bayesian Optimization for Building Social-Influence-Free Consensuscited by 6
  31. 2025Direct Distributional Optimization for Provable Alignment of Diffusion Modelscited by 5
  32. 2026Verbalizing LLM's Higher-order Uncertainty via Imprecise Probabilitiescited by 5
  33. 2025Scalable Valuation of Human Feedback through Provably Robust Model Alignmentcited by 4
  34. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  35. 2025Generative Bayesian Optimization: Generative Models as Acquisition Functionscited by 3
  36. 2025Fixing the Pitfalls of Probabilistic Time-Series Forecasting Evaluation by Kernel Quadraturecited by 2
  37. 2025Natural Evolutionary Search meets Probabilistic Numericscited by 2
  38. 2026Open-Ended Task Discovery via Bayesian Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Open-ended Scientific Discovery with Possibilistic Reasoningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Robust Guided Diffusion for Offline Black-Box Optimization
  2. 2026Improving Bayesian Optimization via Training-Aware Conditional Diffusion Models
  3. 2024Diffusion-BBO: Diffusion-Based Inverse Modeling for Online Black-Box Optimization
  4. 2024Gradient Guidance for Diffusion Models: An Optimization Perspective
  5. 2026Support-Proximity Augmented Diffusion Estimation for Offline Black-Box Optimization
  6. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints
  7. 2025Censored Sampling for Topology Design: Guiding Diffusion with Human Preferences
  8. 2026D-IMPL: A Diffusion-based Solver for Parameterized BBOs