# Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Functions

arXiv: https://arxiv.org/abs/2103.01578 · HTML: https://mlsanity.com/paper/2103.01578/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions](https://mlsanity.com/paper/2512.16200/) (2025)

## Abstract (arXiv)

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^*)T H (x - x^*)), where g:ℝ→ℝ is a strictly increasing function, H is a positive-definite symmetric matrix, and x^* ∈ ℝd 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·xi) )) for the case of H = diag(xi · 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.