Convergence Guarantees for Modern Evolution Strategies

• Applicant: Professor Dr. Tobias Glasmachers
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 442436089

The primary role of optimization heuristics is to address challenging problems for which no efficient exact solvers exist. This paradigm is particularly prominent in the field of black-box optimization, where only weak and implicit assumptions are made about the problem structure. Mathematical optimization covers many important problem classes. Black-box heuristics, designed with minimal assumptions in mind, aim to cover the wide range of problems outside that domain.An extremely successful class of algorithms for gradient-free black-box optimization in continuous search spaces are evolution strategies (ESs), a sub-class of evolutionary algorithms. These randomized zeroth-order optimization methods sample search points from a distribution and adapt the distribution afterwards based on the observed objective values. For flexible classes of search distributions this design yields equally flexible solvers. The state of the art is marked by the covariance matrix adaptation (CMA) evolution strategy, CMA-ES, which is applied in a wide range of domains, like industrial design and machine learning. It demonstrates high practical efficiency in benchmarks and competitions. From a theoretical perspective, a major downside of ESs is a lack of convergence guarantees, which are limited to simplistic ESs and restricted function classes.With new proof techniques available, this situation has recently improved significantly. The most notable breakthrough is the application of drift analysis to ESs. It yielded the first result showing the convergence of an ES on a rather large class of problems, namely strongly convex problems. Similar progress was achieved in understanding the principal limitations of ESs, i.e., edge cases where they fail to converge to a local optimum. However, none of the existing works covers CMA-ES. The lack of the highly relevant CMA mechanism in the analysis marks a major disconnect between theory and practice.Filling this research gap is a major step towards a complete understanding of the convergence of CMA-ES on wide classes of problems. We will provide the first rigorous convergence proof of an ES with CMA. Starting with the rather simple (1+1)-CMA-ES on convex quadratic functions we will gradually increase the complexity to non-elitist algorithms with stateful step size control rules, and to significantly larger problem classes. We aim at proofs of linear convergence (the behavior observed in practice), at the correct dependency of the convergence rate on problem difficulty, and at an analysis of the dependency of the first hitting times on initial conditions that does not hide relevant effects behind (huge) constants. Taken together, these steps will mark a major milestone of our understanding of state-of-the-art search and optimization heuristics.

• DFG Programme: Research Grants