论文标题
全球线性融合进化策略对平滑凸出功能的平滑功能多
Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
论文作者
论文摘要
进化策略（ESS）是目标函数单调转换的零阶随机黑盒优化启发式启发式。他们进化了多元正态分布，从中产生了候选解决方案。在不同的变体中，如今，CMA-Es被认为是针对困难问题的最先进的零级优化器之一。尽管有足够的经验证据表明，具有长期控制机制的ESS线性收敛，但仅在有限的函数类别上建立了ESS线性收敛的理论保证。特别是，缺少有关凸功能的理论结果，其中经常分析零阶和一阶优化方法。在本文中，我们建立了几乎确定的线性收敛，并限制了一个\ new {es家族的预期打击时间，即$（1+1）_κ$ -ES，其中包括（1+1）-Es具有（概括性的）一五分之一的成功规则}和一个抽象的协方差矩阵适应条件，并具有界限的条件适应性。该分析具有正均均匀函数和二次界限功能的单调转换，后者特别包括具有Lipschitz连续梯度的强凸功能的单调转换。据作者所知，这是证明ES在如此广泛的功能上的线性收敛的第一部作品。
Evolution strategies (ESs) are zeroth-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 zeroth-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 zeroth-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 \new{ES family, namely the $(1+1)_κ$-ES, which includes 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.
