Covariance Matrix Adaptation Evolution Strategy for Low Effective Dimensionality

Kento Uchida, Teppei Yamaguchi, Shinichi Shirakawa · 2024

Read Covariance Matrix Adaptation Evolution Strategy for Low Effective Dimensionality by Kento Uchida, Teppei Yamaguchi, Shinichi Shirakawa (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01156.txt.

Introduction

Kento Uchida, Teppei Yamaguchi, and Shinichi Shirakawa fix a blind spot in a leading optimizer when most dimensions barely matter. Their 2024 paper studies CMA-ES, a state-of-the-art evolution strategy for black-box problems. Many real problems have low effective dimensionality: the objective really depends on few rotated directions, padded with redundant ones.

The standard algorithm suffers twice, since its settings scale with the total dimension count and its step-size rules average over the dead dimensions too. Their variant rotates the space by the covariance eigenvectors, scores each direction by signal-to-noise ratios in its updates, and counts only effective dimensions. Step-size adaptation then measures norms on those directions alone. Benchmarks with planted redundancy showed the variant beating the original. The lesson: measure what matters, ignore the padding.

Catalog record

CREATORKento Uchida, Teppei Yamaguchi, Shinichi Shirakawa
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01156

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Covariance Matrix Adaptation Evolution Strategy for Low Effective Dimensionality Kento Uchida, Teppei Yamaguchi, Shinichi Shirakawa Abstract Despite the state-of-the-art performance of the covariance matrix adaptation evolution strategy (CMA-ES), high-dimensional black-box optimization problems are challenging tasks. Such problems often involve a property called low effective dimensionality (LED), in which the objective function is formulated with redundant dimensions relative to the intrinsic objective function and a rotation transformation of the search space. The CMA-ES suffers from LED for two reasons: the default hyperparameter setting is determined by the total number of dimensions, and the norm calculations in step-size adaptations are performed including elements on the redundant dimensions. In this paper, we incorporate countermeasures for LED into the CMA-ES and propose CMA-ES-LED. We tackle with the rotation transformation using the eigenvectors of the covariance matrix. We estimate the effectiveness of each dimension in the rotated search space using the element-wise signal-to-noise ratios of the mean vector update and the rank- μ \mu update, both of which updates can be explained as the natural gradient ascent. Then, we adapt the hyperparameter using the estimated number of effective dimensions. In addition, we refine the cumulative step-size adaptation and the two-point step-size adaptation to measure the norms only on the effective dimensions. The experimental results show the CMA-ES-LED outperforms the CMA-ES on benchmark functions with LED. Journal: Swarm and Evolutionary Computation 1 Introduction 1.1 Background and Related Works The black-box optimization problem is the minimization or maximization problem in which the gradient information of the objective function is not accessible. These problems have appeared in several real-world applications [ 1 ] . Among the search algorithm for the black-box optimization problem with continuous search space, the covariance matrix adaptation evolution strategy (CMA-ES) [ 2 ] has shown a promising search performance on several problems, containing functions that possess intractable properties such as ill-conditioned, multimodal, or non-separable landscapes. The CMA-ES employs a multivariate Gaussian distribution to generate the candidate solutions and iteratively updates the distribution parameter to generate better solutions. The update rule of the distribution parameters contains several hyperparameters. Because an improper hyperparameter setting deteriorates the search performance of CMA-ES, and because the problem-dependent hyperparameter tuning is a time-consuming task, their default settings are provided for the convenience of CMA-ES [ 3 ] . These default values are given by functions of the number of dimensions in the search space (i.e., the number of design variables to be optimized). Despite the state-of-the-art search performance of the CMA-ES, the high-dimensional black-box optimization problems are challenging tasks. A known intractable property of high-dimensional black-box optimization is low effective dimensionality (LED) [ 4 ] , in which the objective function value is determined by only some elements in the rotated search space and not influenced by the other elements. Problems with LED have often appeared in several real-world applications, such as the hyperparameter optimization of machine learning [ 5 ] , control of over-actuated systems [ 6 ] , and shape optimization [ 7 ] . Figure 1 shows the conceptual image of the function with LED considered in this paper. Such objective functions contain the intrinsic objective function with a lower number of dimensions, which is not accessible. As the default hyperparameters of the CMA-ES are determined by the total number of dimensions, including redundant dimensions, LED degrades the search performance of the CMA-ES. Ideally, using the default hyperparameters value obtained by the number of the intrinsic dimensions, several update rules of the CMA-ES on the function with LED behave the same as on the intrinsic objective functions. Another weakness of the CMA-ES is the update rules in the step-size adaptations, whose performance is usually influenced by LED. The popular step-size adaptations, including the cumulative step-size adaptation (CSA) [ 8 ] and the two-point step-size adaptation (TPA) [ 9 ] , evaluate the norm calculation by taking account of not only the effective dimensions but also the redundant dimensions. Due to these weaknesses, LED deteriorates the performance of the CMA-ES compared to the performance on the intrinsic objective function. Figure 1: The conceptual image of function with LED. We simply consider the case where the objective function contains a rotation matrix \boldsymbol{R}\in\mathbb{R}^{N\times N} and an intrinsic objective function \tilde{f}:\mathbb{R}^{N_{\mathrm{eff}}}\to\mathbb{R} . The objective function value at \boldsymbol{x} is given by f(\boldsymbol{x})=\tilde{f}(\psi(\boldsymbol{R}\boldsymbol{x})) , where \psi(\boldsymbol{y})=(\boldsymbol{y}_{1},\cdots,\boldsymbol{y}_{N_{\mathrm{eff}}})^{\mathrm{T}}\in\mathbb{R}^{N_{\mathrm{eff}}} . This figure shows an example with N=2 and N_{\mathrm{eff}}=1 . See Section 4 for detail. Since the LED property also deteriorates other black-box optimization methods, several improvement methods have been proposed. The simplest method is to project the search space into the subspace with fewer dimensions using a random embedding. The random embedding Bayesian optimization (REMBO) [ 10 ] and random embedding estimation of distribution algorithm (REMEDA) [ 11 ] incorporate such random embedding into Bayesian optimization and the estimation of distribution algorithm, respectively. However, random embedding contains several issues. As the number of dimensions on the intrinsic objective function is not accessible, the number of dimensions in the subspace should be chosen carefully. In addition, the random embedding may make the problem more difficult. Although several methods [ 12 , 13 , 14 ] using random embedding have been proposed later, those problems are not solved yet. On the other hand, the adaptive stochastic natural gradient method for LED (ASNG-LED) [ 15 ] considers the effectiveness of each dimension and estimates it using the element-wise signal-to-noise ratio (SNR) of the update direction of the distribution parameter. ASNG-LED incorporates this mechanism into an adaptation method of the learning rate [ 16 ] for the stochastic natural gradient. ASNG-LED successfully improves the search performance of ASNG on binary optimization problems with LED. Although the stochastic natural gradient recovers some of the update rules of the CMA-ES [ 17 ] , this approach cannot be incorporated directly because the rank-one update and the step-size adaptation are not recovered. Moreover, in continuous search space, because the projection between the search spaces of the objective function and the intrinsic objective function often involves a rotation transformation, the estimation of the rotation transformation is additionally required. 1.2 Our Contributions In this paper, we propose an estimation method of the effectiveness of each dimension and the rotation transformation, which reconstructs the landscape of the intrinsic objective function. Firstly, we estimate the rotation transformation using the eigenvectors of the covariance matrix in the CMA-ES. Then, we calculate the rotated update direction of the mean vector and the covariance matrix and estimate their element-wise SNRs. To achieve the effectiveness of each dimension from the element-wise SNRs, we introduce a monotonically increasing function with two tunable parameters. These parameters are adaptively updated based on the number of dimensions, the sample size, and the maximum element of element-wise SNRs, where any problem-dependent tuning by the user is unnecessary. Based on the estimated effectiveness of each dimension and the rotation transformation, we incorporate two countermeasures for LED into the CMA-ES and propose the CMA-ES-LED. The first is the hyperparameter adaptation using the default hyperparameter settings of the CMA-ES, in which we compute the hyperparameter values using the estimated number of effective dimensions instead of the total number of dimensions. The second is the refinement of the norm calculation in well-known step-size adaptations, the CSA and

Read the complete text