Convergence Analysis of the Hessian Estimation Evolution Strategy

The class of algorithms called Hessian Estimation Evolution Strategies (HE-ESs) update the covariance matrix of their sampling distribution by directly estimating the curvature of the objective function. The approach is practically efficient, as attested by respectable performance on the BBOB testbed, even on rather irregular functions. In this article, we formally prove two strong guarantees for the (1 + 4)-HE-ES, a minimal elitist member of the family: stability of the covariance matrix update, and as a consequence, linear convergence on all convex quadratic problems at a rate that is independent of the problem instance.

Automated summary

This article introduces the characteristics and performance of the class of algorithms called Hessian Estimation Evolution Strategies (HE-ESs), and provides two strong guarantees for the (1 + 4)-HE-ES algorithm: stability of covariance matrix update and linear convergence on all convex quadratic problems, regardless of the problem instance.