Analyzing Flexible Search Distributions in Black-Box Optimization with Normalizing Flow-based Estimation of Distribution Algorithms

Abstract

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.