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:
- 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.
- 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