Natural Evolutionary Search meets Probabilistic Numerics
This work addresses sample efficiency issues in black-box optimization for applications like hyperparameter tuning and robotics, representing an incremental improvement over existing NES methods.
The paper tackles the limited sample efficiency of Natural Evolution Strategies (NES) by introducing Probabilistic Natural Evolutionary Strategy Algorithms (ProbNES), which integrate Bayesian quadrature, and shows that ProbNES consistently outperforms non-probabilistic NES and global methods like Bayesian Optimization across various tasks.
Zeroth-order local optimisation algorithms are essential for solving real-valued black-box optimisation problems. Among these, Natural Evolution Strategies (NES) represent a prominent class, particularly well-suited for scenarios where prior distributions are available. By optimising the objective function in the space of search distributions, NES algorithms naturally integrate prior knowledge during initialisation, making them effective in settings such as semi-supervised learning and user-prior belief frameworks. However, due to their reliance on random sampling and Monte Carlo estimates, NES algorithms can suffer from limited sample efficiency. In this paper, we introduce a novel class of algorithms, termed Probabilistic Natural Evolutionary Strategy Algorithms (ProbNES), which enhance the NES framework with Bayesian quadrature. We show that ProbNES algorithms consistently outperforms their non-probabilistic counterparts as well as global sample efficient methods such as Bayesian Optimisation (BO) or $π$BO across a wide range of tasks, including benchmark test functions, data-driven optimisation tasks, user-informed hyperparameter tuning tasks and locomotion tasks.