Convergence Guarantees for Modern Evolution Strategies

优化算法的主要作用是解决没有有效精确求解器的具有挑战性的问题。这种范式在黑盒优化领域尤为突出，在黑盒优化中，对问题结构只做了微弱和隐含的假设。数学优化涵盖了许多重要的问题类别。黑箱算法是一种基于最小假设的算法，它的目标是解决该领域之外的各种问题。在连续搜索空间中，一种非常成功的无梯度黑箱优化算法是进化策略（ES），它是进化算法的一个子类。这些随机零阶优化方法从分布中采样搜索点，然后根据观察到的目标值调整分布。对于搜索分布的灵活类，这种设计产生同样灵活的求解器。协方差矩阵自适应（CMA）进化策略（CMA-ES）是最先进的，它被广泛应用于工业设计和机器学习等领域。它在基准测试和竞赛中表现出很高的实用效率。从理论的角度来看，ES的一个主要缺点是缺乏收敛保证，这仅限于简单的ES和受限的函数类。随着新的证明技术的出现，这种情况最近得到了显着改善。最显著的突破是将漂移分析应用于ES。它产生了第一个结果，显示ES在相当大的一类问题上的收敛性，即强凸问题。在理解ES的主要局限性方面也取得了类似的进展，即，边缘情况下，他们无法收敛到局部最优。然而，现有的工程都没有涵盖CMA-ES。在分析中缺乏高度相关的CMA机制标志着理论与实践之间的重大脱节。填补这一研究空白是朝着全面理解CMA-ES在广泛类别问题上的收敛性迈出的重要一步。我们将提供第一个严格的收敛证明的ES与CMA。从凸二次函数上的相当简单的（1+1）-CMA-ES开始，我们将逐渐增加具有状态步长控制规则的非精英算法的复杂性，以及显着更大的问题类。我们的目标是证明线性收敛（在实践中观察到的行为），在正确的依赖问题的难度收敛速度，并在分析的依赖性的第一次击中时间的初始条件，不隐藏相关的影响背后（巨大的）常数。总的来说，这些步骤将标志着我们对最先进的搜索和优化算法的理解的一个重要里程碑。

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.