Jul 2026· Annual Conference on Genetic and Evolutionary Computation· pp. 179-187· 0 citations· 49 references
Computer Science
TL;DR
The results show that diffusion-based EDAs can outperform classical EDAs based on probabilistic graphical models and contemporary neural-network-based EDAs, particularly on problems with complex variable interactions.
Abstract
Diffusion models have demonstrated remarkable success in modeling high-dimensional probability distributions within machine learning. Their potential for modeling search distributions in combinatorial optimization, however, remains largely unexplored. This paper bridges this gap by integrating diffusion models into Estimation of Distribution Algorithms (EDAs). We propose two novel EDAs: a diffusion-by-denoising EDA (Diff-EDA) and a diffusion-by-deblending EDA (DbD-EDA), both adapted for discrete optimization. Key adaptations include the use of Gumbel-Softmax for discrete variables, fitness-guided sampling, and tailored loss functions. Through extensive experiments on benchmark additive functions and combinatorial problem instances (SAT, Ising, UBQP), we validate the effectiveness of the proposed algorithms. Our results show that diffusion-based EDAs can outperform classical EDAs based on probabilistic graphical models and contemporary neural-network-based EDAs, particularly on problems with complex variable interactions. This work establishes a new direction for EDAs, demonstrating that diffusion models can provide a powerful and flexible framework for learning and sampling from search distributions in evolutionary optimization.
This work establishes a minimax lower bound under the score-entropy loss, and proposes an MLE-based thresholding estimator that matches this lower bound up to constant and polylogarithmic factors that depend on neighboring density ratios.
The empirical success of diffusion models in generative modelling has motivated theoretical work, including quantitative error bounds and qualitative analyses that characterise the different phases of denoising. We bring these two areas together by studying the adaptivity of diffusion models to the structured geometry of multimodal high-dimensional data that consists of multiple clusters in $\mathbb{R}^D$, each with its own low-dimensional structure, and inter-cluster separation depending on $D$. We employ $K$-mixture Gaussian distributions as a canonical framework to capture this geometry and establish two theoretical results. First, we interpret denoising as a dynamical Bayesian classifier: the mixture score is a posterior-weighted average of cluster-wise scores, and we show that, with high probability, the posterior class probabilities concentrate on a single cluster once the signal-to-noise ratio reaches the scale $\Theta (\log (KD)/D)$. Second, by separately analysing the denoising process in its mixing and cluster-commitment phases, we prove that the KL error bound depends linearly on the maximum intrinsic dimension of a cluster, up to a logarithmic factor, even when $K$ grows polynomially with $D$. This improves on ambient-dimensional bounds and extends existing low-dimensional adaptivity analyses to multimodal distributions with heterogeneous, approximately low-rank covariances.
Diffusion models learn to reverse a predefined corruption process, but sampling still requires a costly time discretization and depends on the chosen noise schedule. We study these two issues for variance-preserving diffusions with matrix-valued schedules. Our analysis transfers reverse-time discretization errors to the forward corruption law and treats two numerical schemes within a common framework. The first freezes the score and yields, through a matrix-sensitive local comparison and forward information dissipation, an ambient-dimensional step complexity with leading factor $d/\varepsilon^2$ for KL accuracy $\varepsilon^2$. The second keeps the known Gaussian drift exact and freezes the posterior mean. For data of metric-entropy dimension $k$, a forward Markov identity, an anisotropic covering estimate, and Stieltjes integration by parts give the corresponding factor $k\log k/\varepsilon^2$. In both cases, the proof identifies a local error, accumulates it through the forward evolution, and inserts the result into a common KL decomposition. The local errors further provide directional criteria for matrix schedules and an asymptotically optimal square-root adaptive grid. A high-dimensional Gaussian-mixture experiment illustrates the resulting schedule and grid improvements.
Black-box optimization often requires search distributions that can adapt to complex geometric structures under limited evaluation budgets. We propose NF-EDA, a Normalizing Flow-based Estimation of Distribution Algorithm that replaces fixed Gaussian models with a learned, flexible search distribution. Beyond optimization performance, our goal is to better understand how increased distributional expressiveness affects search behavior. In contrast to classical Gaussian-based methods, NF-EDA can adapt to curved, asymmetric, and non-elliptical regions of the search space, enabling broader yet structured exploration during early stages of optimization. By tracking the evolution of the learned distribution over iterations, we analyze how NF-EDA reshapes its sampling behavior compared to predefined parametric approaches such as CMA-ES and Gaussian EDAs. Experimental results on selected COCO BBOB functions, including Rastrigin, Schwefel, Lunacek bi-Rastrigin, and Rosenbrock, show that NF-EDA achieves faster early progress and reduced variability across runs, particularly in higher-dimensional settings. An ablation against a Gaussian EDA with matching update rules further demonstrates that these effects arise from the learned flow transformation rather than from the surrounding EDA procedure alone. These findings highlight the importance of flexible search distributions for understanding and improving model-based black-box optimization.
Sara Karami, Christian Gagné· Proceedings of the Genetic a...· 0 citations
We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the underdamped Langevin diffusion, it yields an algorithm for sampling from a strongly log-concave and log-smooth distribution with condition number $\kappa$, in dimension $d$, to accuracy $\varepsilon$ in R\'enyi divergence, in $\widetilde O(\kappa^{2/3} d^{1/3}\,\mathrm{polylog}(1/\varepsilon))$ queries. Under a third derivative bound, the dimension dependence improves to $d^{1/5}$. This improves substantially over the prior state-of-the-art complexity of $\widetilde O(\kappa d^{1/2}\,\mathrm{polylog}(1/\varepsilon))$ for the Metropolis-adjusted Langevin algorithm, and over the $d^{1/4}$ dimension dependence of Metropolized Hamiltonian Monte Carlo under the same third derivative bound. We also present applications to the mirror Langevin diffusion, and for obtaining Fisher information bounds in the non-log-concave case.
Fan Chen, Sinho Chewi, Alexander Rakhlin et al.· 0 citations
We study high-dimensional numerical integration with respect to complex target measures using diffusion-based transport maps and randomized quasi-Monte Carlo (RQMC). Score-based diffusion models induce a deterministic probability flow ODE that transports a simple prior to the target, suggesting a principled way to transform low-discrepancy points on the unit cube into informative samples. We construct a cube-to-target map by composing a Gaussian base transformation (the component-wise inverse Gaussian CDF) with an Euler-discretized probability flow ODE. To retain unbiasedness under transport approximation, we formulate integration as importance sampling (IS) on the cube. Our main result provides verifiable conditions under which the resulting IS integrand satisfies the boundary growth condition, implying an $O(N^{-1+\epsilon})$ RMSE for scrambled nets. We then establish these conditions for diffusion probability-flow transport under mild bounded-derivative assumptions on the learned vector field, explicitly controlling the boundary singularities introduced by the inverse Gaussian CDF. Experiments range from a 2D mixture to 784D images and a 40,960D conditional vorticity-assimilation task; in the latter, blocked scrambled Sobol'sampling reduces the randomization standard deviation of nonlinear accuracy metrics at essentially unchanged online denoising cost. Together, these results give a theoretical and empirical foundation for combining diffusion generative modeling with high-precision RQMC integration.
