Kernel selection for kernel-based model is a difficult problem. Exact solutions are, in general, prohibitively expensive to solve for due to the NP-hard nature of these combinatorial tasks. In addition, gradient-based optimization techniques are inapplicable due to the non-differentiability of the objective function. As such, many state-of-the-art solutions for this problem resorts to heuristic search and gradient-free optimization.
These approaches, however, require imposing restrictive assumptions on the explorable space of candidate structures such as randomized candidate pool and/or upper-bounded structure dimension, thus depending heavily on the intuition of domain experts. This paper instead proposes DTERGENS, a novel generative search framework that constructs and optimizes a recursive structure generation routine for high-performance composite kernel expressions. DTERGENS does not require restricting the space of candidate kernels and is capable of exploring arbitrary-dimensional kernel structures by jointly optimizing a stopping criterion for the kernel structure generator. We demonstrate that our framework is able to explore a more diverse range of kernel structures and obtain better results than state-of-the-art approaches on many real-world predictive tasks.