Text

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

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. Despite 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 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.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.2 April-June 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1402-1429

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

LINEAR CONVERGENCE
STOCHASTIC ALGORITHMS
BLACK-BOX OPTIMIZATION
EVOLUTION STRATEGIES
RANDOMIZED DERIVATIVE FREE OPTIMIZATION

Info Detail Spesifik

https://doi.org/10.1137/20M1373815

Pernyataan Tanggungjawab

Youhei Akimoto, Anne Auger, Tobias Glasmachers, Daiki Morinaga

Versi lain/terkait

Lampiran Berkas

Komentar