JSAI2021

Presentation information

General Session

General Session » GS-1 Fundamental AI, theory

[1H3-GS-1b] 基礎・理論:モデル化

Tue. Jun 8, 2021 3:20 PM - 5:00 PM Room H (GS room 3)

座長:戸田 貴久 (電気通信大学)

4:00 PM - 4:20 PM

[1H3-GS-1b-03] Convergence Rate Bound of the (1+1)-Evolution Strategy on Convex Quadratic Function

〇Daiki Morinaga1,2, Kazuto Fukuchi1,2, Jun Sakuma1,2, Youhei Akimoto1,2 (1. University of Tsukuba, 2. RIKEN AIP)

Keywords:Continuous Black-Box Optimization, Evolutionary Computation, Convergence Analysis, Evolution Strategy, Convergence Rate

In this study, we provides a convergence rate of a continuous black-box optimization algorithm, the (1+1)- Evolution Strategy (ES), on a general convex quadratic function, where convergence rate is decrease rate of the distance to the optimal point in each iteration. We show an upper bound of the convergence rate is described with the ratio of the smallest eigenvalue of the Hessian matrix to the sum of all eigenvalues. As long as the authors know, this is the first study which suggests the convergence rate of the (1+1)-ES on a general convex quadratic function is affected not only by the condition number of the Hessian, but also the distribution of the eigenvalues. Furthermore, we show a lower bound of the convergence rate on the same function class is described with the inverse of the dimension of the search space, which agrees with previous studies on a part of convex quadratic function.

Authentication for paper PDF access

A password is required to view paper PDFs. If you are a registered participant, please log on the site from Participant Log In.
You could view the PDF with entering the PDF viewing password bellow.

Password