2024/02/02 by Thomas Guilmeau, Guilmeau, Thomas, Émilie Chouzenoux +3
Computer Science · Decision Sciences · Mathematics · #65K05 (Secondary) #90C26 (Primary) 90C59 #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2402.01277
openalex publication_date 2024/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Black-box global optimization aims at minimizing an objective function whose analytical form is not known. To do so, many state-of-the-art methods rely on sampling-based strategies, where sampling distributions are built in an iterative fashion, so that their mass concentrate where the objective function is low. Despite empirical success, the theoretical study of these methods remains difficult. In this work, we introduce a new framework, based on divergence-decrease conditions, to study and design black-box global optimization algorithms. Our approach allows to establish and quantify the improvement of proposals at each iteration, in terms of expected value or quantile of the objective. We show that the information-geometric optimization approach fits within our framework, yielding a new approach for its analysis. We also establish proposal improvement results for two novel algorithms, one related with the cross-entropy approach with mixture models, and another one using heavy-tailed sampling proposal distributions.