Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
From MaRDI portal
Publication:6349366
DOI10.1137/20M1373815zbMATH Open1509.65044arXiv2009.08647MaRDI QIDQ6349366FDOQ6349366
Daiki Morinaga, Tobias Glasmachers, Anne Auger, Youhei Akimoto
Publication date: 18 September 2020
Abstract: 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
ew{ES family, namely the -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.
Numerical mathematical programming methods (65K05) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56)
This page was built for publication: Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349366)
