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 詳細情報について

  • CRID
    1390569845478486144
  • NII Article ID
    130008051559
  • DOI
    10.11517/pjsai.jsai2021.0_1h3gs1b03
  • ISSN
    27587347
  • Text Lang
    ja
  • Data Source
    • JaLC
    • CiNii Articles
  • Abstract License Flag
    Disallowed

Report a problem

Back to top