Convergence Rate Bound of the (1+1)-Evolution Strategy on Convex Quadratic Function

DOI

Bibliographic Information

Other Title
  • (1+1)-Evolution Strategyの凸二次関数における収束速度の導出

Description

<p>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.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top