Density Descent for Diversity Optimization
David H. Lee Anishalakshmi V. Palaparthi Matthew C. Fontaine Bryon Tjanaka Stefanos Nikolaidis
Diversity optimization seeks to discover a set of solutions that elicit
diverse features. Prior work has proposed Novelty Search (NS), which, given a
current set of solutions, seeks to expand the set by finding points in areas of
low density in the feature space. However, to estimate density, NS relies on a
heuristic that considers the k-nearest neighbors of the search point in the
feature space, which yields a weaker stability guarantee. We propose Density
Descent Search (DDS), an algorithm that explores the feature space via gradient
descent on a continuous density estimate of the feature space that also
provides stronger stability guarantee. We experiment with DDS and two density
estimation methods: kernel density estimation (KDE) and continuous normalizing
flow (CNF). On several standard diversity optimization benchmarks, DDS
outperforms NS, the recently proposed MAP-Annealing algorithm, and other
state-of-the-art baselines. Additionally, we prove that DDS with KDE provides
stronger stability guarantees than NS, making it more suitable for adaptive
optimizers. Furthermore, we prove that NS is a special case of DDS that
descends a KDE of the feature space.