Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
复制标题
DOI：
10.1137/20m1373815
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Youhei Akimoto;A. Auger;T. Glasmachers;Daiki Morinaga
中科院分区：
文献类型：
--
作者：
Youhei Akimoto;A. Auger;T. Glasmachers;Daiki Morinaga
进化策略是一种零阶随机黑箱优化算法，对目标函数的单调变换具有不变性。它们演化出一个多元正态分布，并由此生成候选解。在不同的变体，CMA-ES是目前公认的最先进的零阶优化困难的问题之一。尽管有充分的经验证据表明，具有步长控制机制的ES线性收敛，但ES线性收敛的理论保证仅在有限的函数类上建立。特别是，凸函数的理论结果缺失，其中零阶和一阶优化方法经常被分析。在本文中，我们建立了几乎必然的线性收敛和一个界的预期命中时间的ES，即（1 + 1）-ES（广义）五分之一成功规则和一个抽象的协方差矩阵适应有界的条件数，在一个广泛的功能。该分析适用于正齐次函数和二次有界函数的单调变换，其中二次有界函数特别包括具有Lipschitz连续梯度的强凸函数的单调变换。据作者所知，这是第一个工作，证明了线性收敛的ES在这样一个广泛的功能。
Evolution strategies (ESs) are zero-order stochastic black-box optimization heuristics invariant to monotonic transformations of the objective function. They evolve a multivariate normal distribution, from which candidate solutions are generated. Among different variants, CMA-ES is nowadays recognized as one of the state-of-the-art zero-order optimizers for difficult problems. Albeit ample empirical evidence that ESs with a step-size control mechanism converge linearly, theoretical guarantees of linear convergence of ESs have been established only on limited classes of functions. In particular, theoretical results on convex functions are missing, where zero-order and also first order optimization methods are often analyzed. In this paper, we establish almost sure linear convergence and a bound on the expected hitting time of an ES, namely the (1 + 1)-ES with (generalized) one-fifth success rule and an abstract covariance matrix adaptation with bounded condition number, on a broad class of functions. The analysis holds for monotonic transformations of positively homogeneous functions and of quadratically bounded functions, the latter of which particularly includes monotonic transformation of strongly convex functions with Lipschitz continuous gradient. As far as the authors know, this is the first work that proves linear convergence of ES on such a broad class of functions.