Nonparametric Distributional Black-box Optimization via Diffusion Process

Yueming Lyu, Atsushi Nitanda, Ivor TsangDeLTa @ ICLR 2025 · OpenReview

TL;DR

This paper introduces a novel black-box optimization method called Diffusion-BO that uses diffusion models to learn and sample from complex, non-parametric distributions. This allows for more efficient exploration and avoids the limitations of traditional methods that rely on simple Gaussian distributions, especially for challenging optimization problems.

What Problem Does This Paper Address?

Black-box optimization is crucial for many real-world applications like material design and drug discovery, where the objective function is complex and its gradient is unknown. Existing methods, such as Evolution Strategies (ES), often rely on sampling from simple parametric distributions (like Gaussians) to propose new candidate solutions. However, this can limit their ability to model complex search spaces, leading to suboptimal exploration and potentially getting stuck in local optima. The paper aims to overcome this by enabling black-box optimization methods to learn and utilize more flexible, non-parametric distributions for sampling.

Methods

The core of the proposed method, Diffusion-BO, lies in two key components:

  1. Proximal Distributional Update: Instead of directly optimizing the objective function $f(x)$, the method optimizes an augmented problem that encourages the sampling distribution to concentrate around good solutions. This is achieved through an iterative update rule that incorporates the objective function and a KL divergence term, leading to a closed-form update for the target distribution. This update rule is derived from the idea of minimizing $f(x)$ by optimizing an augmented problem, which results in a distribution $p^{k+1}(x) \propto p^k(x)e^{-f(x)}$.
  2. Sampling via Diffusion Process: A major challenge with the derived non-parametric distribution is efficiently sampling from it, especially when the gradient of $f(x)$ is unavailable (as is the case in black-box optimization). The paper leverages diffusion models, specifically the Ornstein-Uhlenbeck process, to address this. By formulating the sampling process as a backward stochastic differential equation (SDE) derived from the diffusion process, the method can generate samples from the learned complex distribution without requiring gradient information. The paper details how to discretize this SDE for practical sampling.

Datasets

Not discussed in the paper. The paper evaluates its method on standard benchmark test functions.

Key Insights and Ideas

  • Bridging Diffusion Models and Black-Box Optimization: The paper ingeniously connects the powerful generative capabilities of diffusion models with the practical needs of black-box optimization. This allows for learning and sampling from arbitrary, complex distributions, a significant step beyond traditional parametric approaches.
  • Gradient-Free Sampling from Complex Distributions: By using the diffusion process's backward SDE, the method achieves gradient-free sampling from the learned non-parametric distribution. This is crucial for black-box scenarios where gradients are inaccessible.
  • Proximal Update for Distributional Learning: The proximal distributional update rule provides a principled way to iteratively refine the sampling distribution based on the black-box objective function, guiding the search towards better solutions.

Key Results

The paper evaluates Diffusion-BO on several challenging benchmark functions: Levy, Rastrigin, Nesterov (non-smooth), and Rosenbrock. The results, presented in Figure 1, show that Diffusion-BO can effectively decrease the objective value, achieving near-optimal results on functions like Levy and Rosenbrock. The method demonstrates its ability to handle complex optimization landscapes and achieve competitive performance compared to existing approaches.

Limitations and Future Work

The authors acknowledge that a formal convergence analysis of their method is left as future work. While the paper demonstrates strong empirical results, a deeper theoretical understanding of the convergence guarantees would be valuable. Future work could also explore applying this framework to more complex real-world problems and investigating different diffusion schemes for potentially improved sampling efficiency.

Summary updated

Abstract

Sampling-based black-box optimization, e.g., zeroth-order optimization and Evolution strategy, is important for the material design, molecular design and etc. However, existing sampling-based black-box optimization methods only employ simple parametric distribution, typically Gaussian distribution, as the sampling distribution to generate queries. This limits the capabilities of modeling complex distribution to generate good candidates and influence the query efficiency. In this work, we propose a novel nonparametric black-box optimization method that performs proximal distributional update for sampling. Particularly, we derive the closed-form update rule based on the diffusion process (e.g., Ornstein–Uhlenbeck process). Our sampling and updating method supports black-box target function $f(\cdot)$ without accessing the $\nabla f$, which is critical for our nonparametric distributional black-box optimization.
BibTeX
@inproceedings{lyu2025nonparametric,
  author = {Yueming Lyu and Atsushi Nitanda and Ivor Tsang},
  title = {{Nonparametric Distributional Black-box Optimization via Diffusion Process}},
  booktitle = {DeLTa @ ICLR},
  year = {2025},
  url = {https://openreview.net/forum?id=DOXsyHprRN},
}
Figure