Convergence rate of the (1+1)-evolution strategy with success-based step-size adaptation on convex quadratic functions

The (1+1)-evolution strategy (ES) with success-based step-size adaptation is analyzed on a general convex quadratic function and its monotone transformation, that is, f(x) = g((x - x*)TH(x - x*)), where g: R → R is a strictly increasing function, H is a positive-definite symmetric matrix, and x* ∈ Rd is the optimal solution of f. The convergence rate, that is, the decrease rate of the distance from a search point mt to the optimal solution x*, is proven to be in O(exp(-L/Tr(H))), where L is the smallest eigenvalue of H and Tr(H) is the trace of H. This result generalizes the known rate of O(exp(-1/d)) for the case of H = Id (Id is the identity matrix of dimension d) and O(exp(-1/(d · ξ))) for the case of H = diag(ξ · Id/2, Id/2). To the best of our knowledge, this is the first study in which the convergence rate of the (1+1)-ES is derived explicitly and rigorously on a general convex quadratic function, which depicts the impact of the distribution of the eigenvalues in the Hessian H on the optimization and not only the impact of the condition number of H.