Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [55 references]  Display  Hide  Download

https://hal.inria.fr/hal-02941429
Contributor : Anne Auger <>
Submitted on : Thursday, October 15, 2020 - 9:43:16 AM
Last modification on : Friday, October 16, 2020 - 3:40:51 AM

File

siam.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02941429, version 2
  • ARXIV : 2009.08647

Collections

Citation

Youhei Akimoto, Anne Auger, Tobias Glasmachers, Daiki Morinaga. Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions. 2020. ⟨hal-02941429v2⟩

Share

Metrics

Record views

12

Files downloads

24