Behind State-Of-The-Art Adaptive Black-Box Optimization: A blend of Markov Chain Theory and Information Geometry
Seminar Probabilités & Statistique
2/02/2017 - 14:00 Anne AUGER (INRIA Saclay) Salle 106 - Batiment IMAG
Many real-world problems involve the resolution of challenging numerical optimization problems. Often the derivatives are not available---a scenario often referred to as black-box optimization--and the function combines difficulties like ill-conditionning, ruggedness of the function (a term that characterizes that the function can be discontinuous, noisy, or can have many local optima). In this context, the methods of choice are adaptive and stochastic. In the past fifteen years, an algorithm emerged to solve complex black-box problem, the so-called CMA-ES. It is now regarded as the state-of-the art algorithm for numerical black-box optimization standardly used in industry and implemented in scientific libraries. In this presentation, we will introduce the main aspects of the CMA-ES algorithm. Additionally, we will present on the one hand recent results connecting CMA-ES with information geometry and optimization on statistical manifolds. On the other hand, we will explain how the analysis of Markov chains underlying the algorithm can provide linear convergence proofs for variants of CMA-ES.