A more efficient rank-one covariance matrix update for evolution strategies

TY - GEN

T1 - A more efficient rank-one covariance matrix update for evolution strategies

AU - Krause, Oswin

AU - Igel, Christian

N1 - Conference code: 13

PY - 2015/1/17

Y1 - 2015/1/17

N2 - Learning covariance matrices of Gaussian distributions is at the heart of most variable-metric randomized algorithms for continuous optimization. If the search space dimensionality is high, updating the covariance or its factorization is computationally expensive. Therefore, we adopt an algorithm from numerical mathematics for rank-one updates of Cholesky factors. Our methods results in a quadratic time covariance matrix update scheme with minimal memory requirements. The numerically stable algorithm leads to triangular Cholesky factors. Systems of linear equations where the linear transformation is defined by a triangular matrix can be solved in quadratic time. This can be exploited to avoid the additional iterative update of the inverse Cholesky factor required in some covariance matrix adaptation algorithms proposed in the literature. When used together with the (1+1)-CMA-ES and the multi-objective CMA-ES, the new method leads to a memory reduction by a factor of almost four and a faster covariance matrix update. The numerical stability and runtime improvements are demonstrated on a set of benchmark functions.

AB - Learning covariance matrices of Gaussian distributions is at the heart of most variable-metric randomized algorithms for continuous optimization. If the search space dimensionality is high, updating the covariance or its factorization is computationally expensive. Therefore, we adopt an algorithm from numerical mathematics for rank-one updates of Cholesky factors. Our methods results in a quadratic time covariance matrix update scheme with minimal memory requirements. The numerically stable algorithm leads to triangular Cholesky factors. Systems of linear equations where the linear transformation is defined by a triangular matrix can be solved in quadratic time. This can be exploited to avoid the additional iterative update of the inverse Cholesky factor required in some covariance matrix adaptation algorithms proposed in the literature. When used together with the (1+1)-CMA-ES and the multi-objective CMA-ES, the new method leads to a memory reduction by a factor of almost four and a faster covariance matrix update. The numerical stability and runtime improvements are demonstrated on a set of benchmark functions.

KW - cholesky factorization, cma-es, covariance matrix adaptation, rank-one update

U2 - 10.1145/2725494.2725496

DO - 10.1145/2725494.2725496

M3 - Article in proceedings

SN - 978-1-4503-3434-1

SP - 129

EP - 136

BT - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

PB - Association for Computing Machinery

T2 - ACM Conference on Foundations of Genetic Algorithms 2015

Y2 - 17 January 2015 through 20 January 2015

ER -