A covariance matrix adaptation evolution strategy in reproducing kernel Hilbert space

Viet-Hung Dang, Ngo Anh Vien, TaeChoong Chung

Abstract

Traditional black-box optimization algorithms like the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are often limited by a "feature bottleneck," requiring a predefined finite set of parameters. This paper introduces CMA-ES-RKHS, an extension that operates directly within infinite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). By reformulating the search distribution as a Gaussian Process and employing sparsification techniques like Kernel Matching Pursuit (KMP) and Kernel PCA (kPCA), the proposed method enables the optimization of complex, non-parametric functions without manual feature engineering. Experimental results on synthetic tasks and reinforcement learning benchmarks, such as the double pendulum swing-up, demonstrate that CMA-ES-RKHS outperforms standard parametric approaches in both flexibility and robustness.

Introduction

Black-box optimization is essential for solving complex problems where the objective function's gradient is unavailable or difficult to compute. CMA-ES has emerged as a state-of-the-art tool in this domain, iteratively updating a Gaussian distribution to find global minima. However, its reliance on a fixed parameterization—such as neural network weights or radial basis function (RBF) centers—presents a significant limitation. If the chosen features cannot represent the optimal solution, the optimizer is confined to a suboptimal subspace.

To overcome this, researchers have sought methods to optimize directly in function spaces. The primary challenge lies in the infinite-dimensional nature of such spaces, which renders standard matrix updates computationally intractable. This paper addresses this challenge by leveraging the mathematical framework of Reproducing Kernel Hilbert Spaces (RKHS) to extend CMA-ES into the functional domain.

Methodology

The core contribution of this work is the derivation of CMA-ES updates within an RKHS. The transition from finite-dimensional parameter spaces to infinite-dimensional function spaces involves several key components:

From Vectors to Functions

In standard CMA-ES, the search distribution is defined by a mean vector and a covariance matrix. In CMA-ES-RKHS, these are replaced by a mean function and a covariance operator. The search distribution is effectively extended to a Gaussian Process (GP), where each sample is an entire function rather than a discrete point in $\mathbb{R}^n$.

Analytic Updates in RKHS

The authors demonstrate that the fundamental update rules of CMA-ES—including recombination, step-size control, and covariance adaptation—can be handled analytically within the RKHS. This allows the algorithm to maintain the robust global search characteristics of CMA-ES while exploring a much richer class of functions.

Efficiency through Sparsification

To ensure computational feasibility and prevent the representation from growing indefinitely, the authors implement two sparsification techniques:

  1. Kernel Matching Pursuit (KMP): This technique is used to maintain a sparse representation of the mean function by selecting a subset of basis functions that best approximate the current state.
  2. Kernel PCA (kPCA): This is employed to sparsify the covariance operator and efficiently compute its inverse square root, which is necessary for the evolution strategy's updates.

Furthermore, the authors introduce the concept of "effective dimensionality," defined by the number of sparse kernel features ($n_1$). This metric is used to set internal hyperparameters, such as learning rates, providing a principled scaling mechanism for the algorithm.

Experimental Evaluation

The framework was tested against two primary benchmarks to evaluate its performance and flexibility.

Synthetic Functional Optimization

The algorithm was tasked with minimizing the distance to an unknown "ground truth" function (a mixture of Gaussians) in 1D and 2D spaces. CMA-ES-RKHS significantly outperformed "Adaptive CMA-ES," a baseline that attempts to optimize RBF centers manually. While the baseline struggled with the multi-modal nature of the target functions, CMA-ES-RKHS successfully captured the complex landscapes.

Reinforcement Learning Control

The method was applied to classic control tasks:

  • Inverted Pendulum: A standard balancing benchmark.
  • Double Pendulum Swing-up: A more rigorous test involving an under-actuated system requiring highly non-linear control policies.

In the double pendulum task, standard CMA-ES with fixed features failed to represent the necessary policy complexity. In contrast, CMA-ES-RKHS evolved sophisticated policies that achieved the highest cumulative rewards, demonstrating its superiority in handling complex, high-dimensional control problems.

Discussion and Conclusion

CMA-ES-RKHS represents a significant step forward in functional optimization. By moving beyond fixed parametric models, it allows for adaptive feature selection on the fly, effectively performing global search in a very rich function class. This makes it particularly robust for the complex landscapes encountered in robot learning and reinforcement learning.

Despite its successes, the method faces challenges. The computational cost of kernel-based methods remains higher than that of parametric alternatives. Future research will focus on improving scaling laws and conducting deeper theoretical studies into the convergence properties of evolution strategies in infinite-dimensional Hilbert spaces. Additionally, further investigation into hyperparameter sensitivity in the RKHS setting is warranted to refine the algorithm's practical application.

Summary updated

Abstract

The covariance matrix adaptation evolution strategy (CMA-ES) is an efficient derivative-free optimization algorithm. It optimizes a black-box objective function over a well-defined parameter space in which feature functions are often defined manually. Therefore, the performance of those techniques strongly depends on the quality of the chosen features or the underlying parametric function space. Hence, enabling CMA-ES to optimize on a more complex and general function class has long been desired. In this paper, we consider modeling the input spaces in black-box optimization non-parametrically in reproducing kernel Hilbert spaces (RKHS). This modeling leads to a functional optimisation problem whose domain is a RKHS function space that enables optimisation in a very rich function class. We propose CMA-ES-RKHS, a generalized CMA-ES framework that is able to carry out black-box functional optimisation in RKHS. A search distribution on non-parametric function spaces, represented as a Gaussian process, is adapted by updating both its mean function and covariance operator. Adaptive and sparse representation of the mean function and the covariance operator can be retained for efficient computation in the updates and evaluations of CMA-ES-RKHS by resorting to sparsification. We will also show how to apply our new black-box framework to search for an optimum policy in reinforcement learning in which policies are represented as functions in a RKHS. CMA-ES-RKHS is evaluated on two functional optimization problems and two bench-marking reinforcement learning domains.
BibTeX
@article{dang2019covariance,
  author = {Viet-Hung Dang and Ngo Anh Vien and TaeChoong Chung},
  title = {{A covariance matrix adaptation evolution strategy in reproducing kernel Hilbert space}},
  journal = {Genet. Program. Evolvable Mach.},
  year = {2019},
  doi = {10.1007/s10710-019-09357-1},
}
Figure