A divergence-based condition to ensure quantile improvement in black-box global optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912047616229376 |
|---|---|
| author | Guilmeau, Thomas Chouzenoux, Emilie Elvira, Víctor |
| author_facet | Guilmeau, Thomas Chouzenoux, Emilie Elvira, Víctor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01277 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A divergence-based condition to ensure quantile improvement in black-box global optimization Guilmeau, Thomas Chouzenoux, Emilie Elvira, Víctor Optimization and Control 90C26 (Primary) 90C59, 65K05 (Secondary) 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. |
| title | A divergence-based condition to ensure quantile improvement in black-box global optimization |
| topic | Optimization and Control 90C26 (Primary) 90C59, 65K05 (Secondary) |
| url | https://arxiv.org/abs/2402.01277 |