Convergence Guarantees for Modern Evolution Strategies

优化启发式的主要作用是解决没有有效精确解的挑战性问题。这种范式在黑盒优化领域尤为突出，在黑盒优化中，只对问题结构做出微弱和隐含的假设。数学优化涵盖了许多重要的问题类。黑盒启发式在设计时考虑了最小的假设，旨在涵盖该领域之外的广泛问题。进化策略（evolution strategies, ESs）是一类非常成功的连续搜索空间无梯度黑盒优化算法，它是进化算法的一个子类。这些随机化的零阶优化方法从一个分布中寻找点，然后根据观察到的目标值对分布进行调整。对于灵活的搜索分布类，这种设计产生了同样灵活的求解器。协方差矩阵自适应（CMA）进化策略（CMA - es）在工业设计和机器学习等领域得到了广泛的应用。在基准测试和竞赛中显示出较高的实际效率。从理论的角度来看，ESs的主要缺点是缺乏收敛保证，这仅限于简化的ESs和受限制的函数类。随着新的证明技术的出现，这种情况最近得到了显著改善。其中最显著的突破是漂移分析在ESs中的应用。它产生了第一个结果，显示了ES在相当大的一类问题上的收敛性，即强凸问题。在理解ESs的主要限制方面也取得了类似的进展，即它们不能收敛到局部最优的边缘情况。但是，现有的工作都没有涉及CMA-ES。分析中缺乏高度相关的CMA机制标志着理论与实践的重大脱节。填补这一研究空白是朝着完全理解CMA-ES在广泛问题上的收敛迈出的重要一步。我们将提供具有CMA的ES的第一个严格收敛证明。从凸二次函数上相当简单的(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.