Back to Search
Start Over
Convergence rate of the (1+1)-evolution strategy with success-based step-size adaptation on convex quadratic functions
- Source :
- GECCO
- Publication Year :
- 2021
- Publisher :
- ACM, 2021.
-
Abstract
- 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^*)^\mathrm{T} H (x - x^*))$, where $g:\mathbb{R}\to\mathbb{R}$ is a strictly increasing function, $H$ is a positive-definite symmetric matrix, and $x^* \in \mathbb{R}^d$ is the optimal solution of $f$. The convergence rate, that is, the decrease rate of the distance from a search point $m_t$ to the optimal solution $x^*$, is proven to be in $O(\exp( - L / \mathrm{Tr}(H) ))$, where $L$ is the smallest eigenvalue of $H$ and $\mathrm{Tr}(H)$ is the trace of $H$. This result generalizes the known rate of $O(\exp(- 1/d ))$ for the case of $H = I_{d}$ ($I_d$ is the identity matrix of dimension $d$) and $O(\exp(- 1/ (d\cdot\xi) ))$ for the case of $H = \mathrm{diag}(\xi \cdot I_{d/2}, I_{d/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$.<br />Comment: 17 pages
- Subjects :
- FOS: Computer and information sciences
Hessian matrix
Trace (linear algebra)
G.1.6
Computer Science - Neural and Evolutionary Computing
0102 computer and information sciences
02 engineering and technology
Quadratic function
Function (mathematics)
65K10 65K10
01 natural sciences
Combinatorics
symbols.namesake
Distribution (mathematics)
Rate of convergence
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
symbols
Symmetric matrix
020201 artificial intelligence & image processing
Neural and Evolutionary Computing (cs.NE)
Condition number
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the Genetic and Evolutionary Computation Conference
- Accession number :
- edsair.doi.dedup.....e21cb585634c36a67fd02794d5fbdea2