Differentiable Quality Diversity
Authors: Matthew Christopher Fontaine
Stefanos Nikolaidis
Venue: NeurIPS 2021 Oral (2021)
Keywords: quality diversity optimization
generative adversarial network
latent space exploration

Abstract: Quality diversity (QD) is a growing branch of stochastic optimization research that studies the problem of generating an archive of solutions that maximize a given objective function but are also diverse with respect to a set of specified measure functions. However, even when these functions are differentiable, QD algorithms treat them as "black boxes", ignoring gradient information. We present the differentiable quality diversity (DQD) problem, a special case of QD, where both the objective and measure functions are first order differentiable. We then present MAP-Elites via a Gradient Arborescence (MEGA), a DQD algorithm that leverages gradient information to efficiently explore the joint range of the objective and measure functions. Results in two QD benchmark domains and in searching the latent space of a StyleGAN show that MEGA significantly outperforms state-of-the-art QD algorithms, highlighting DQD's promise for efficient quality diversity optimization when gradient information is available. Source code is available at https://github.com/icaros-usc/dqd.

Differentiable Quality Diversity
Matthew C. Fontaine University of Southern California Los Angeles, CA mfontain @ edu
Stefanos Nikolaidis University of Southern California Los Angeles, CA nikolaid@usc.ed
Abstract
Quality diversity (QD) is growing branch of stochastic optimization research that studies the problem of generating an archive of solutions that maximize a given objective function but also diverse with respect measure functions. However, even when these functions are differentiable, QD algorithms treat them as "black boxes", ignoring gradient information. We present the differentiable quality diversity (DQD) problem, a special case of QD, where both the objective and measure functions are first order differentiable. We then present MAP-Elites via Gradient Arborescence (MEGA), DQD algorithm that leverages gradient information efficiently explore the joint range of the objective and measure functions. Results in two QD benchmark domains and in searching the latent space StyleGAN show that MEGA significantly outperforms state-of- the-art QD algorithms, highlighting DQD's promise for efficient quality diversity optimization when gradient information available. Source code is available https: /ttpt/ggggtto.../oo www.ttuu..o.mccooottoooooo com//caros-ssc///a
of specified
Introduction
We introduce the problem of differentiable quality diversity (DQD) and propose the MAP-Elites via Gradient Arborescence (MEGA) algorithm the first DQD algorithm.
Unlike single-objective optimization, quality diversity (QD) is the problem of finding range of high quality solutions that are diverse with respect to prespecified metrics. For example, consider the problem of generating realistic images that match as closely as possible a target text prompt "Elon Musk", but vary with respect to hair and eye color. We can formulate the problem of searching the latent space of generative adversarial network (GAN) (26) as a QD problem of discovering latent codes that generate images maximizing matching score for the prompt "Elon Musk", while achieving a diverse range measures hair and eye color, assessed by visual classification models [5T]. More generally, the QD objective is to maximize objective for each output combination of measure functions m,, A QD algorithm produces an archive of solutions, where the algorithm attempts to discover representative for each measure output combination, whose value is as large possible.
While our example problem can be formulated as a QD problem, all current QD algorithms treat the objective f and measure functions QD algorithms fail take advantage of the fact that both and m, are end-to-end differentiable neural networks. Our proposed differentiable quality diversity (DQD) algorithms leverage first-order derivative information to significantly improve the computational efficiency of solving a variety of QD problems where f and m, are differentiable.
black box. This means, in our example problem, current
To solve DQD, we introduce the concept of a gradient arborescence. Like gradient ascent, gradient arborescence makes greedy ascending steps based on the objective f. Unlike gradient ascent, gradient arborescence encourages exploration by branching via the measures m,, We adopt the term
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0 cV
v
0' Ascend to maximize Σ f(0.)
0 cVV
Sample c e~ c~N(H,
Branch via objective-measure gradients
Adapt (M, via CMA-ES
Update archive
Figure I: An overview of the Covariance Matrix Adaptation MAP-Elites via Gradient Arborescence (CMA-MEGA) algorithm. The algorithm leverages a gradient arborescence to branch in objective- measure space, while dynamically adapting the gradient steps to maximize QD objective (Eq.
arborescence from the minimum arborescence problem 8 in graph theory, a directed counterpart to the minimum spanning tree problem, to emphasize the directedness of the branching search.
Our work makes four main contributions. 1) We introduce and formalize the problem differentiable quality diversity (DQD). 2) We propose two DQD algorithms: Objective and Measure Gradient MAP-Elites via a Gradient Arborescence (OMG-MEGA), an algorithm based on MAP-Elites [3] which branches based the measures m, but ascends based on the objective function f: and Co- variance Matrix Adaptation MEGA (CMA-MEGA) which is based on the CMA-ME [9] algorithm. and which branches based the objective-measee objective (Fig. [ Both algorithms search directly in measure space and leverage the gradients of f and m, to form efficient parameter space steps in 0. 3) We show in three different QD domains (the linear projection, the arm repertoire, and the latent space illumination (LSI) domains), that DQD al- gorithms significantly outperform state-of-the-a QD algorithms that treat the objective and measure functions as a black box. 4) We demonstrate how searching the latent space of StyleGAN [36] in the I.SI domain with CMA-MEGA results in diverse range of high-quality images.
space but ascends based maximizing the QD
2 Problem Definition
Quality Diversity, The quality diversity (QD) problem assumes an objective ʃ R" + R in an n-dimensional continuous space IR" and k measures m, Rn R or, joint measure, m : IR" + _ Let S = m(R") be the measure space formed by the range of m. For each E S the QD objective is find a solution E= such that m(0) and f(0) is maximized.
However, we note that R is continuous, and an algorithm solving the quality diversity problem would require infinite memory to store solutions. Thus, QD algorithms the MAP-Elites 443 [3
family approximate the problem by discretizing S via tessellation method. Let T be the tessellation of S into M cells. We relax the QD objective to find a set of solutions 0,, E {1,..... M. such that each 0g occupies Each solution 02 has a position in the archive m (0,). corresponding to one out of cells, and an objective value f0t)..
unique cell in T. The occupants O, of all M cells form archive of solutions.
The objective of QD can rewritten as follows, where the goal is maximize the objective value for each cell in the archive:
max Σ f(O))
Differentiable Quality Diversity. We define the differentiable quality diversity (DQD) problem, as a QD problem where both the objective f and measures m, are first-order differentiable.
3 Preliminaries
We present several state-of-the-art derivative-free QD algorithms. Our proposed DQD algorithm MEGA builds upon ideas from these works, while introducing measure and objective gradients into the optimization process.

---

first tessellates the measure space S into evenly-spaced grid cells. The upper and lower bounds for m are given as input to constrain S to finite region. MAP-Flites first samples solutions from fixed distribution O ~ No0, 7), and populates an initial archive after computing f()) and m0).. Each iteration of MAP-Elites selects À cells uniformly at random from the archive and perturbs each occupant 0; with fixed- -xei-variance isotropic Gaussian noise: 0' = 0g + (0, f). Each new candidate solution O' is then evaluated and added to the archive if 0' discovers a new cell or improves existing cell. The algorithm continues to generate solutions for a specified number of iterations.
MAP-Elites and MAP-Elites (line). MAP-Elites [33 43
Later work introduced the Iso+LineDD operator [6]]. The Iso+LineDD operator samples two archive solutions 0₂ and 0y. then blends a Gaussian perturbation with a noisy interpolation given hyperparameters oi and d2: 0' = 0; + (0, I) + (0,(0, 1)(0, 02). MAP-Elites with an Iso+LineDDD operator as MAP-Elites (line).
In this paper we refer to
CMA-ME. Covariance Matrix Adaptation MAP-Elites (CMA-ME) 19 combines the archiving
mechanisms of MAP-Elites with the adaptation mechanisms of CMA-ES [30]. While MAP-Elites
creates new solutions by perturbing existing solutions with fixed-variance Gaussian noise, CMA-ME maintains a full-rank Gaussian distribution (u, Σ) in parameter space R". Each iteration of
CMA-ME samples À candidate solutions 0g ~ [ Σ), evaluates each solution, and updates the archive based on the following rule: if there a previous occupant Op the same cell, we compute A; f f(pp). otherwise if the cell is empty we compute A; f(O)). We then rank the sampled solutions by increasing improvement A, with an extra criteria that candidates discovering new cells are ranked higher than candidates that improve existing cells. We then update N(p,, Σ) with the standard CMA-ES update rules based on the improvement ranking. CMA-ME restarts when all X solutions fail to change the archive. On a restart we reset the Gaussian N(;;; 7), where 0g is an archive solution chosen uniformly at random, and all internal CMA-ES parameters. In the supplemental material, we derive, for the first time, natural gradient interpretation of CMA-ME's improvement ranking mechanism, based on previous theoretical work on CMA-ES
Algorithms
We present two variants of our proposed MEGA algorithm: OMG-MEGA and CMA-MEGA. We form each variant by adapting the concept of a gradient arborescence to the MAP-Elites and CMA-ME algorithms,, respectively. Finally, introduce two additional baseline algorithms, OG-MAP-Elie Elites and OG-MAP-Elite (line), which operate only on the gradients of the objective.
OMG-MEGA. We first derive the Objective and Measure Gradient MAP-Elites via Gradient Ar- borescence (OMG-MEGA) algorithm from MAP-Elites.
First, we observe how gradient information could benefit a QD algorithm. Note that the QD objective to explore the measure space, while maximizing the objective function f. We observe that maximizing a linear combination of measures: Σj= (O), where e a k-dimensional vector of coefficients, enables movement in a k-dimensional measure space. Adding the objective function If to the linear sum enables movement in an mbjactive-measure space. Maximizing g with a positive coefficient f results in steps that increasing f. while the direction of movement in the measure space is determined by the sign and magnitude of the coefficients cj.
.(0) (col
cm,
We can then derive direction function that perturbs a given solution 0 based on the gradient of linear combination 9: V (()) |cu V f() + Σ o mm We incorporate the direction function Vg to derive gradient- based MAP-Elites variation operator.
3

---

We observe that MAP-Elites samples cell 0₂ and perturbs the occupant with Gaussian noise: 0' 0g oN I). Instead, we sample coefficents e No ozd) and step:
0' =,++ ((())) + (
The value og acts as learning rate for the gradient step, because it controls the scale of the coefficients с (0, I. To balance the contribution of each function, we normalize all gradients. In the supplemental material, we further justify gradient normalization and provide empirical ablation study. Other than our new gradient-based operator, OMG-MEGA is identical to MAP-Elites.
CMA-MEGA. Next, derive the Covariance Matrix Adaptation MAP-Elites via Gradient Ar- borescence (CMA-MEGA) algorithm from CMA-ME. Fig. [
shows an overview the algorithm.
First, we note that we sample in OMG-MEGA from a fixed-variance Gaussian. However, it would be beneficial to select e based on how c, and the subsequent gradient step on 0, improve the QD objective defined in equation]
|
We frame the selection of с as optimization problem with the objective of maximizing the QD objective (Eq. []. We model a distribution of coefficients e as a k 1-dimensional Gaussian N (H,, E). Given a 0,
sample e [H,,, E), compute O' via Eq. 3 and adapt (p,, Σ) towards the direction of maximum increase of the QD objective (see Eq.
We follow evolution strategy approach to model and dynamically adapt the sampling distribution of coefficients N (H,, )). We sample a population
coefficients from e; ~ NN,,, 1)) and generate solutions Og. We then compute A; from CMA-ME's improvement ranking for each candidate solution 0 By updating (N,,, E) with CMA-ES update rules for the ranking A,, we dynamically maximize the QD objective.
adapt the distribution of coefficients
Algorithm D shows the pseudocode for CMA-MEGA. line 3 we evaluate the current solution and compute an objective value ʃ. vector of measure values m, and gradient vectors. As we dynamically adapt the coefficients c, we normalize the objective and measure gradients (line ( for stability. Because the measure space is tessellated, the measures place solution O into one of the M cells in the archive. We then add the solution to the archive (line 5). the solution discovers an empty cell in the archive, or if it improves existing cell, identically to MAP-Elites.
We then use the gradient information to compute a step that maximizes improvement of the archive. In lines 6 12 we sample population of X coefficients from multi-variate Gaussian retained by CMA-ES, and take a gradient step for each sample. We evaluate each sampled solution O', and compute the improvement A; (line 11.. As in CMA-ME, we specify A; as the difference in the objective value between the sampled solution 0, and the existing solution, one exists, or as absolute objective value of the sampled solution if 0g belongs to an empty cell.
In line 13 we rank the sampled gradients V. based on their respective improvements. As in CMA-ME, we prioritize exploration of the archive by ranking first by their objective values all samples that discover new cells, and subsequently all samples that improve existing cells by their difference in improvement. We then compute an ascending gradient step as a linear combination of gradients (line 14), following the recombination weights w; from CMA-ES [30] based on the computed improvement ranking. These weights correspond to the log-likelihood probabilities of the samples in the natural gradient interpretation of CMA-ES [..
In line 16 CMA-ES adapts the multi-variate Gaussian N(JA, E), as well as internal search parameters p, from the improvement ranking of the coefficients. In the supplemental material, we provide natural gradient interpretation of the improvement ranking rules of CMA-MEGA, where we show that the coefficient distribution of CMA-MEGA approximates natural gradient steps of maximizing modified QD objective.
CMA-MEGA (Adam). We add Adam based variant of CMA-MEGA, where replace line 15 with an Adam gradient optimization step [38].
OG-MAP-Elites. To show the importance of taking gradient steps in the measure space, opposed to only taking gradient steps objective space and directly perturbing the parameters, we derive two variants of MAP-Elice baseline that draw insights from the recently proposed Policy Gradient

---

Algorithm Covariance Matrix Adaptation MAP-Elites via Gradient Aborescence (CMA-MEGA)
CMA-MEGA (evaluate, 0g N, X. 1,77.0))
input :An evaluation function evaluate which computes the objective, the measures, gradients of the objective and measures, initial solution 0o desired number of iterations N, branching population size X, learning rate !,, and an initial step size for CMA-ES gg.
result: :
Generate N(A 1) solutions storing elites in archive A.
Initialize solution parameters 0 Oo. CMA-ES parameters μ Σ ogl, and p, where let p be the CMA-ES internal parameters.
for iler < to N do
f. V f, m, V m f evaluate(()
v - normalize( V Vm normalize( m)
update_ane aaeh_rrccceeeee f. for + to À do
c~ N(,, Σ)
V. t co + Σj=1 ms
+ 0 V:
f. m' evaluate (0') (0))
10
11
A t _pdate_archive
archive 0 m')
12
end
13
rank
V by A
14
W. V rankii]
15
θ 7
step
16
Adapt CMA-ES parameters Σ, p based on improvement ranking A if there no change in the archive then
18
Restart CMA-ES with μ = 0, E I.
Set O to a randomly selected existing cell Og from the archive
20
end
21 end
Assisted MAP-Elites (PGA-ME) algorithm 45 PGA-ME combines the Iso+LineDD operator 61 with a policy gradient operator only on the objective. Similarly, our proposed Sijlective-Grdieen MAP-Elites (OG-MAP-Elites, algorithm combines an objective gradient step with MAP-Elites style perturbation operator. Each iteration of OG-MAP- samples À solutions 0; from the archive. Each 0; is perturbed with Gaussian noise to form new candidate solution 0 = 0 + aN(0.. Z). OG-MAP-Elites evaluates the solution and updates the archive, exactly as in MAP-Elites. However, OG-MAP-Elites takes one additional step: for each O', the algorithm computes V ((()), forms new solution 0 0 + v (0() with an objective gradient step, and evaluates 0" Finally, we update the archive with all solutions O and 0% OG-MAP-Elites (line). Our second baseline, OG-MAP-Elites (line) replaces the Gaussian opera- tor with the Iso+LineDD operator [61]: 0' 0; + (0. a2A(0, () 0j). We consider OG-MAP- (line) a DQD variant of PGA-ME. However, PGA-ME was designed a rein- forcement learning (RL) algorithm, thus many of the advantages gained in RL settings are lost in OG-MAP-Elites (line). We provide detailed discussion and ablations in the supplemental material.
5
Domains
DQD requires differentiable objective and measures, thus we select benchmark domains from previous work in the QD literature where we can compute the gradients of the objective and measure functions.
Linear Projection. To show the importance of adaptation mechanisms in QD, the CMA-ME paper [19] introduced simple domain, where reaching the extremes of the measures challenging for non- adaptive QD algorithms. The domain forms each measure m; by a linear projection from IR" IR, while bounding the contribution of each component to the range [-5.12, 5.1].
We note that uniformly sampling from a hypercube in R results in a narrow distribution the linear projection in F [19 34). Increasing the number of parameters makes the problem of covering the
5

---

I.P (sphere)
LP (Rastrigin)
Arm Repertoire
LST
Algorithm
QD-score
Coverage
Q--score
Coverage
QD-score
Coverage
QD-score
Coverage
MAP-Elites
1.04
1.17%
1.18
1.72%
1.97
8.06%
13.88
23.15%
MAP-Elites (line)
12:21
14.32%
8.12
11.79%
33.51
35.79%
16.54
25.73%
CMA-ME
1.08
1.21%
1.21
1.76%
55,98
56.95%
18.96
26.18%
AG-MAP-Elite.
1.52
1.67%
0.83
1.26%
57.17
58.08%
N/A
N/A
OG-MAP-Elice (line)
15.01
17.41%
6.10
8.85%
59,66
60.28%
N/A
N/A
OMG-MEGA
71.58
92.09%
55.90
77.00%
44.12
44.13%
NIA
NIA
CMA-MEGA
75.29
100.00% %
62,54
100.00%
74.18
74.18%
5,36
8.61%
CMA-MEGA (Adam)
75.30
100.00 %
62.58
100.00 %
73.82
73.82%
21.82
30.73%
Table 1: Mean QD-score and coverage values after 10,000 iterations for each algorithm per domain.
measure space more challenging, because to reach an extremum m,(0) = 12.12n, all components must equal the extremum: [ 15.12.
We select this domain as a benchmark to highlight the need for adaptive gradient coefficients for CMA-MEGA as opposed to constant coefficients for OMG-MEGA, because reaching the edges of the measure space requires dynamically shrinking the gradient steps.
As QD domain, the domain must provide an objective. The CMA-ME study 19 introduces two variants of the linear projection domain with objective based the sphere and Rastrigin functions from the continuous black-box optimization set of benchmarks (29 31. We optimize an n = 1000
unbounded parameter space g" We provide more detail in the supplemental material.
Arm Repertoire. We select the robotic arm repertoire domain from previous work 13 61.. The
goal in this domain is to find an inverse kinematics (IK) solution for each reachable position of the end-effector of a planar robotic arm with revolute joints. The objective f of each solution is to minimize the variance of the joint angles, while the measure functions are the positions of the end effector in the x and y-axis, computed with the forward kinematics of the planar arm [4 We selected 1000-DOF robotic arm.
Latent Space Illumination Previous work 20 introduced the problem of exploring the latent space of generative model directly with QD algorithm. The authors named the problem latent space illumination (LSI). As the original LSI work evaluated non-differentiable objectives and measures, we create new benchmark for the differentiable LSI problem by generating images with StyleGAN (36) and leveraging CLIP [51 to create differentiable objective and measure functions. We adopt the StyleGAN+CLIP [48] pipeline, where StyleGAN- generated images passed CLIP, which in turn evaluates how well the generated image matches a given text prompt. We form the prompt "Elon Musk with short hair." as the objective and for the measures we form the prompts "A person with red hair." and "A man with blue eyes.". The goal of DQD becomes generating faces similar to Elon Musk with short hair, but varying with respect to hair and eye color.
Experiments
We conduct experiments to assess the performance of the MEGA variants. In addition to our OG-MAP-Elice baselines, which we propose in section 4 we compare the MEGA variants with the state-of-the-an QD algorithms presented in section 3 We implemented MEGA and OG-MAP-Elites variants in the Pyribs [59] QD library and compare against the existing Pyribs implementations of MAP-Elites, MAP-Elite (line), and CMA-ME.
6.1 Experiment Design
Independent Variables. We follow between-groups design, where the independent variables are the algorithm and the domain (linear projection, arm repertoire, and LSI). We did not run OMG-MEGA and OG-MAP-Elites in the LSI domain; while CMA-MEGA computes the f and m; gradients once per iteration (line in Algorithm D OMG-MEGA and OG-MAP compute the f and m, gradients for every sampled solution, making their execution cost- postiprohibetive for the LSI domain.
Dependent Variables. We measure both the diversity and the quality of the solutions returned by each algorithm. These are combined by the QD-score metric [49], which is defined as the sum of f values of all cells in the archive (Eq. I To make the QD-score invariant with respect to the

---

CMA-MEGA (Adam)
MAP-Fliee (line)
80
100
CMA-MEGA
QD- QD-Score
CMA MEGA
OMG-MEGA
OG-MAi--Riras (ime)
MAP Eiires
CMA-ME
MAP-Elites (line)
MAP-Elltes
0
5000
10000
Iterations
CMA-MEGA (Adam)
CMA-ME
80
100
QD-Score
5000
10000
Iterations
CMA-MEGA (Adam)
CMA-ME
25
100
QD-Score
5000
10000
Iterations
Figure 2: QD-Score plot with 95% confidence intervals and heatmaps of generated archives by CMA-MEGA (Adam) and the strongest derivative-fres competitor for the linear projection sphere (top), arm repertoire (middle), and latent space illumination (bottom) domains.
resolution of the archive, we normalize QD-score by the archive size (the total number of cells from the tessellation of the measure space). As an additional metric of diversity we compute the coverage as the number of occupied cells in the archive divided by the total number of cells. We run each algorithm for 20 trials in the linear projection and arm repertoire domains, and for 5 trials in the LSI domain, resulting in total of 445 trials.
6.2 Analysis
Table [ shows the metrics of all the algorithms, averaged over 20 trials for the benchmark domains and over 5 trials for the LSI domain. We conducted two-way ANOVA to examine the effect of algorithm and domain (linear projection (sphere), linear projection (Rastrigin), arm repertoire) on the QD-Score. There was statistically significant interaction between the search algorithm and domain (F(14, 456) = 7328.18, 18, p < 0.001). Simple main effects analysis with Bonferroni corrections showed that CMA-MEGA and OMG-MEGA performed significantly better than each of the baselines the sphere and Rastrigin domains, with CMA-MEGA significantly outperforming OMG-MEGA. CMA-MEGA also outperformed all the other algorithms in the arm repertoire domain.

---

6.0
5.45
A Aerson with red hair.
4.9
4.35
3.8
3.25
2.7 2.7
3.25
3.8
4,35
4.9
5.45
6.0
A man with blue eyes.
Figure 3: Result of latent space illumination for the objective prompt "Elon Musk with short hair." and for the measure prompts "A person with red hair." and "A man with blue eyes.". The axes values indicate the score returned by the CLIP model, where lower score indicates a better match.
We additionally conducted a one-way ANOVA to examine the effect of algorithm on the LSI domain. There was statistically significant difference between groups (4, 20) = 260.64, < 0.001). Post- hoc pairwise comparisons with Bonferroni corrections showed that CMA-MEGA (Adam) significantly outperformed all other algorithms,, while CMA-MEGA without the Adam implementation had the worst performance.
Both OMG-MEGA and CMA-MEGA variants perform well in the linear projection domain, where the objective and measure functions are additively separable, and the partial derivatives with respect to each parameter independently capture the steepest change of each function. We observe that OG-MAP-Elites performs poorly in this domain. Analysis shows that the algorithm finds a nearly perfect best solution for the sphere objective, but it interleaves following the gradient of the objective with exploring the archive as standard MAP-Elites, resulting smaller coverage of the archive.
In the arm domain, OMG-MEGA manages to reach the extremes of the measure space, but the algorithm fails to fill in nearby cells. The OG-MAP-Elites variants perform significantly better than OMG-MEGA, because the top-performing solutions in this domain tend to be concentrated in an "elite hypervolume" [1]; moving towards the gradient of the objective finds top- performinn cells, while applying isotropic perturbations to these cells fills in nearby regions in the archive. CMA-MEGA variants retain the best performance in this domain. Fig. shows a high-precision view of the CMA-MEGA (Adam) archive for the arm repertoire domain.
We did not observe a large difference between the CMA-MEGA (Adam) and our gradient descent implementation the first two benchmark domains, where the curvature of the search space well- conditioned. On the other hand, in the LSI domain CMA-MEGA without the Adam implementation performed poorly. We conjecture that this is caused by the conditioning of the mapping from the latent space of the StyleGAN the CLIP score.
Fig. shows the QD-score values for increasing number of iterations for each of the tested algorithms, with 95% confidence intervals. The figure also presents heatmaps of the CMA-MEGA (Adam) and the generated archive of the strongest QD competitor for each of the three domains. We provide generated archives of all algorithms in the supplemental material.
We visualize the top performing solutions in the L.SI domain by uniformly sampling solutions from the archive of CMA-MEGA (Adam) and showing the generated faces in Fig. 3 We observe that
8

---

as we move from the top right to the bottom left, the features matching the captions "a man with blue eyes" and "a person with red hair" become more prevalent. We note that these solutions were generated from single run of CMA-MEGA (Adam) for 10,000 iterations.
Overall, these results show that using the gradient information in quality diversity optimization results in significant benefits to search efficiency, but adapting the gradient coefficients with CMA-ES is critical in achieving top performance.
7 Related Work
Quality Diversity. The precursor to QD algorithms [50] originated with fiversity-driven algorithms as branch of evolutionary computation. Novelty search [39 which maintains an archive of diverse solutions, ensures diversity though provided metric function and was the first diversity-driver algorithm. Later, objectives were introduced as quality metric resulting in the first QD algorithms:
Novelty Search with Local Competition (NSLC) 40 and MAP-Elites 13 43 Since their inception,
many works have improved the archives [18 62 57], the variation operators 16
46), and the
selection mechanisms 212 [56] of both NSLC and MAP-Elites. While the original QD algorithms
were based on genetic algorithms, algorithms based on other derivative-free approaches such as
evolution strategies [19] 10, 46, [1] and Bayesian optimization (37) have recently emerged.
Being stochastic derivative- optimizers 77. QD algorithms are frequently applied to reinforcement learning (RL) problems [47] [2] [14] as derivative information must be estimated in RL. Naturally, approaches combining QD and RI. have started to emerge 45 9 Unlike DQD, these approaches estimate the gradient of the reward function, and in the case of QD-RL a novelty function, in action space and backpropagate this gradient through a neural network. Our proposed DQD problem differs by leveraging provided - rather than approximated gradients of the objective and measure functions.
Several works have proposed model-based QD algorithms. For example, the DDE-Elites algo- rithm 23 dynamically trains a variational autoencoder (VAE) on the MAP-Elites archive, then leverages the latent space of this VAE by interpolating between archive solutions latent space as a type of crossover operator. DDE-Elites learns a manifold of the archive data as a representation, regularized by the VAE's loss function, to solve downstream optimization tasks efficiently in this learned representation. The PoMS algorithm [52] builds upon DDE-Elited by learning an explicit manifold of the archive data via an autoencoder. To overcome distortions introduced by an explicit manifold mapping, the authors introduce a covariance perturbation operator based on the Jacobian of the decoder network. These works differ from DQD by dynamically constructing a learned representation of the search space instead of leveraging the objective and measure gradients directly,
Latent Space Exploration. Several works have proposed variety of methods for directly exploring the latent space of generative models. Methods on GANs include interpolation [60]. gradient descent (3). importance sampling (64). and latent space walks (33. Derivative-free optimization methods mostly consist of latent variable evolution (LVE) 4 24. the method of optimizing latent space with an evolutionary algorithm. LVE was later applied to generating Mario levels (63] with targeted gameplay characteristics. Later work (20 proposed latent space illumination (LSI), the problem of exploring the latent space of a generative model with QD algorithm. The method has only been applied to procedurally generating video game levels 20 58 55 17] and generating MNIST digits [65). Follow-up work explored LSI on VAEs [54. Our work improves LSI on domains where gradient information on the objective and measures is available with respect to model output.
Societal Impacts
By proposing gradient- based analogs to derivative-free QD methods, we hope to expand the potential the ideas of the growing QD community to a wider machine learning audience. We are excited about future mixing of ideas between QD, generative modeling, and other machine learning subfields.
applications of QD research and bring
In the same way that gradient descent is used to synthesize super-resolution images 42 our method can be used in the same context, which would raise ethical considerations due to potential biases present in the trained model [6. On the other hand, we hypothesize that thoughtful selection of the measure functions may help counterbalance this issue, since we can explicitly specify the measures

---

that ensure diversity over the collection of generated outputs. For example. a model may be capable of generating certain type of face, but the latent space may be organized in way which biases a gradient descent on the latent space away from a specific distribution of faces. If the kind of diversity required is differentiably measurable, then DQD could potentially help resolve which aspect of the generative model, i.e., the structure of the latent space or the representational capabilities of the model, is contributing to the bias.
Finally, we recognize the possibility of using this technology for malicious purposes, including generation of fake images ("DeepFakes"), and we highlight the utility of studies that help identify DeepFake models (28).
9 Limitations and Future Work
Quality diversity (QD) is a rapidly emerging field [7] with applications including procedural content generation (27), damage recovery in robotics [13 43) efficient aerodynamic shape design [22], and scenario generation in human-robot interaction [6 17. We have introduced differentiable quality diversity (DQD), special case of QD, where measure and objective functions are differentiable, and have shown how a gradient arborescence results in significant improvements in search efficiency.
As both MEGA variants are only first order differentiable optimizers, we expect them to have difficulty on highly ill-conditioned optimization problems. CMA-ES, as an approximate second order optimizer, retains a full-rank covariance matrix that approximates curvature information and known to outperform quasi-Newton methods on highly ill-conditioned problems [25]. CMA-ME likely inherits these properties by leveraging the CMA-E3 -ES adaptation mechanisms and we expect it to have an advantage on ill-conditioned objective and measure functions.
While we found CMA-MEGA to be fairly robust to hyperparameter changes in the first two benchmark domains (linear projection, arm repertoire), small changes of the hyperparameters in the LSI domain led CMA-MEGA, as well as all the QD baselines, to stray too far from the mean of the latent space, which resulted in many artifacts and unrealistic images. One way to address this limitation is to constrain the search region space, as done in previous work (42).
hypersphere of radius vd, where is the dimensionality of the latent
While CLIP achieves state-of-ther thrt--art performance in classifying images based visual concepts, the model does not measure abstract concepts. Ideally, we would like to specify "age" as a measure function and obtain quantitative estimates of age given an image of person. We believe that the proposed work on the LSI domain will encourage future research on this topic, which we would in turn be able to integrate with DQD implementations generate diverse, high quality content.
Many problems, currently modelled as optimization problems, may be fruitfully redefined as QD problems, including the training of deep neural networks. Our belief stems from recent works 53 41 which reformulated deep learning as a multi-objective optimization problem. However, QD algorithms struggle with high-variance variance stochastic objectives and measures with minibatch training in stochastic gradient descent [5]. These challenges need to be addressed before DQD training of deep neural networks becomes tractable.
which naturally conflicts
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers fNZE, 4FYu, Tlrp, and ghwT for their detailed feedback, thorough comments, and corrections throughout the review process that helped us improve the quality of the paper. We thank the area chair and senior area chair for their assessment, paper recommendation, and kind words about the paper. We thank Lisa B. Soros for her feedback on preliminary version of this work and Varun Bhatt for his assistance running additional experiments for the final version of the paper.
This work was partially supported by the National Science Foundation NRT (# 2024936) and the Alpha Foundation (# AFC820-68).
10

---

References
[1] Youhci Akimoto, Yuichi Nagata, Isao Ono, and Shigenobu Kobayashi. Bidirectional relation between ema evolution strategies and natural evolution strategies. In International Conference on Parallel Problem Solving from Nature, pages 154-163. Springer, 2010.
[2] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 314-315,
2019.
[3] Piotr Bojanowski, Armand Joulin, David Lopez-Paz, and Arthur Szlam. Optimizing the latent space of generative networks. arXiv preprint 170700077 2017.
2017.
[4] Philip Bontrager, Aditi Roy, Julian Togelius, Nasir Memon, and Arun Ross. Deepmasterprints: Generating masterprints for dictionary attacks via latent variable evolution. In 2018 JEEE 9th International Conference on Biometrics Theory, Applications and Systems (BTAS), pages 1-9. IEEE, 2018.
[5] Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436.
Springer, 2012.
[6] Joy Buolamwini and Timnit Gebru. Gender shades: Interscctional accuracy disparities in commercial gender classification. In Conference on faireess, accountability and transparency, pages 77-91. PMLR, 2018.
[7] Konstantinos Charrilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret. Quality- diversity optimization: novel branch of stochastic optimization. In Black Box Optimization,, Machine Learning, and No-Free Lunch Theorems, pages 109-135. Springer, 2021.
[8] Yoeng-Jin Chu. On the shortest arborescence of a directed graph. Scientia Sinica, 14:1396-14000 1400, 1965.
[9] Geoffrey Cideron, Thomas Pierrot, Nicolas Perrin, Karim Beguir, and Olivier Sigaud. Qd-rl: Efficient mixing of quality and diversity in reinforcement learning. arXiv preprint arXiv:2006.08500 2020.
[10] Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling map-elites to deep neuroevo- lution. In Proceedings of the 2020 Genetic and Evolutionary Compulation Conference, pages 67-75, 2020.
[11] Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population of novelty-seeking agents. arXiv preprint arXiv:1712.066660 2017.
[12] Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2):245-255 2017.
[13] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nature, 521(7553):5003, 2015.
[14] Adrien Ecoffet, Joost Huizinga. Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 59078477500
2021.
[15] Manon Flageat and Antoine Cully. Fast and stable map-elites in noisy domains using deep grids. In Artificial Life Conference Proceedings, pages 273-282. MIT Press, 2020.
[16] Matthew Fontaine and Stefanos Nikolaidis. A quality diversity approach to automatically generating human-robot interaction scenarios in shared autonomy. Robotics: Science and Systems, 2021. to appear.
[17] Matthew Fontaine, Sophie Hsu, Yulun Zhang, Bryon Tjanaka, and Stefanos Nikolaidis. On the importance of environments human-robot coordination. Robotics: Science and Systems (RSS), 2021.
[18] Matthew C Fontaine, Scott Lee, Lisa B Soros, Fernando de Mesentier Silva, Julian Togelius, and Amy K Hoover. Mapping hearthstone deck spaces through map-elites with sliding boundaries. In Proceedings of The Genetic and Evolutionary Computaaioon Conference, pages 161-169, 2019.
[19] Matthew C Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K Hoover. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the 2020 genetic and evolutionury computation conference, pages 94-102, 2020.
[20) Matthew C Fontaine, Ruilin Liu, Julian Togelius, Amy K Hoover, and Stefanos Nikolaidis. Illuminating mario scenes in the latent space of generative adversarial network. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
[21] Kevin Frans, LB Soros, and Olaf Witkowski. Clipdraw: Exploring text-to-drawing synthesis through language-image encoders. arXiv preprint arXiv:2106, 140,443,,,,4444,, 2021.
[22] Adam Gaier, Alexander Asteroth, and fean-Baptiste Mouret. Data-efficient design exploration through
surrogate-assisted illumination. Evolutionary computation, 26(3):381-410 2018
[23] Adam Gaier, Alexander Asteroth, and Jean- -aptistt Mouret. Automating representation discovery with map-elites, arXiv preprint arXiv:2003.04338 2020.

---

[24]
Federico A Galatolo, Mario GCA Cimino, and Gigliola Vaglini. Generating images from caption and vice versa via clip-guided generative latent space search. arXiv preprint wrXv:2102.01645,. 2021.
[25]
Tobias Glasmachers and Oswin Krause. The hessian estimation evolution strategy. In International Conference on Parallel Problem Solving from Nature, pages 597-609. Springer, 2020.
[26] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pages 2672-2680, 2014.
[27] Daniele Gravina, Ahmed Khalifa, Antonios Liapis. Julian Togelius, and Georgios N Yannakakis. Procedural content generation through quality diversity. In 2019 JEEE Conference on Games (CoG), pages 1-8. IEEE, 2019.
[28] David Güera and Edward Delp. Deepfake video detection using recurrent neural networks. 2018 15th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), pages 1-6. IEEE, 2018.
[29] N. Hansen, A. Auger, O. Mersmann, T. Tusar, and D. Brockhoff. Coco: A platform for comparing continuous optimizers in a black-box setting. 2016.
[30] Nikolaus Hansen. The ema evolution strategy: A tutorial. arXiv preprint arXiv:1604.00772 2016.
[31] Nikolaus Hansen, Anne Auger, Raymond Ros, Steffen Finck, and Petr Pošík. Comparing results of 31
algorithms from the black-box optimization benchmarking bbob-2009. pages 1689-1696, 07 2010. doi: 10. N0.1145/133066.11337777
[32]
Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. CMA-ES/pycma on Github. Zenodo, DO1:10.528 1101105528//eemod225555563 February 2019. URL https://cci.ozg/11 /2/.//2dd..rr/11000.28/////oo zenodo 2559634
[33] Ali Jahanian, Lucy Chai, and Phillip Isola. On the" steerability" of generative adversarial networks. arXiv preprint 197.:::999000777700 2019.
[34] Norman Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan. Continuous univariate distributions. volume 2, volume 289. John wiley & sons, 1995.
[35] Niels Justesen, Sebastian Risi, and Jean-Baptiste Mouret. Map-elites for noisy domains by adaptive sampling. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 121 121- 2019.
[36] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 4401-4410. 2019.
[37] Paul Kent and Juergen Branke. Bop-elites. bayesian optimisation algorithm for quality search. arXiv preprint arXiv:2005.044 04320, 2020.
[38] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[39] Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 19(2):189 1e111189222 2011.
[40] Joel Lchman and Kenneth O Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 211 211-218. 2011.
[41] Suyun Liu and Luis Nunes Vicente. The stochastic multi gradient algorithm for multi-objective multi-abjcttiveoopiiizzttoo and its application to supervised machine learning. Annals of Operations Research, pages 1-30, 2021.
optimization
[42] Sachit Menon, Alexandru Damian. Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Sele-super photo upsampling via latent space exploration of generative models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2437-2445, 2020.
[43] Jean- Baan-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504, 04404,449990000 2015.
[44] Richard M Murray, Zexiang Li, and S Shankar Sastry. A mathematical introduction robotic manipulation. CRC press, 2017.
[45] Olle Nilsson and Antoine Cully. Policy gradient assisted map-elites. Proceedings of the Genetic and Evolutionary Computation Conference, 2021.
[46] Jørgen Nordmoen, Eivind Samuelsen, Kai Olav Ellefsen, and Kyrre Glette. Dynamic mutation in map- elites for robotic repertoire generation. In Artificial Life Conference Proceedings, pages 598 -08-605,00 MIT Press.
2018.
12

---

[47] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski. and Stephen Roberts. Effective diversity in population-baset reinforcement learning, arXiv preprini 1rXiv:2002.00632. 2020.
[48] Victor Perez. Generating images from prompts using clip and stylegan, 2021. URL https://
Lowardsdatascionss com/ MIT License.
[49] Justin K Pugh, Lisa B Soros, Paul Szerlip, and Kenneth O Stanley. Confronting the challenge of quality diversity. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pages 967-974, 2015.
[50] Justin Pugh, Lisa Soros, and Kenneth O Stanley, Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3:40, 2016.
[51] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Proceedings of the 38th International Conference on Machine Learning ICMI, 2021, 2021.
[52] Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. Policy manifold search: Exploring the manifold neuroevolution. In Proceedings of the Genetic and Evolutionary Compu-
hypothesis for diversity- tation Conference, GECCO '21, page 901-909, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781 450383509. doi:
[53] Michael Ruchte and Josif Grabocka. Efficient multi-objective optimization for deep learning, arXiv preprint arXiv:2103. 13392, 2021.
[54] Anurag Sarkar and Seth Cooper. Generating and blending game levels via quality-diversity in the latent space of a variational autocneoder. arXiv preprint arXiv:2102. 12463, 2021.
[55] Jacob Schrum, Vanessa Volz, and Sebastian Risi. Cppu2gan: Combining compositional pattern producing networks and gans for large- scale pattern generation. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 139-147, 2020.
[56] Konstantinos Sfikas, Antonios Liapis, and Georgios N. Yannakakis. Monte carlo elites: Quality- diversity selection as a multi-armed bandit problem. In Proceedings of the Genetic and Evolution- ary Computation Conference. GECCO '21. page 180-188. New York, NY, USA, 2021. Associa-
tion for Computing Machinery. ISBN 9781450383509. doi: 10.1445749969..455921. URL
3459321
[57] Davy Smith, Laurissa Tokarchuk, and Geraint Wiggins. Rapid phenotypic landscape exploration through hierarchical spatial partitioning. International conference on parallel problem solving from nature. pages 1-900. Springer, 2016.
[58] Kirby Steckel and Jacob Schrum. Muuminatin the space of beatable lode runner levels produced by various generative adversarial networks. In Proceedings of the Genetic and Evolutionary Com- putation Conference Companion, GECCO '21, page 111-112, New York, NY, USA, 2021. Asso- ciation for Computing Machinery. ISBN 97814 9781450383516. 34594444
doi: 10. 10.114557449722.34544444 URL
https::/dci.
[59] Bryon Tjanaka, Matthew C. Fontaine, Yulun Zhang, Sam Sommerer, Nathan Dennler, and Stefanos Nikolaidis. pyribs: A hare-hones python library for quality diversity optimization. htttp:///ithu:t 2021.
com/ http//aaooossc/yyillie
[60] Paul Upchurch, Jacob Gardner, Geoff Pleiss, Robert Pless, Noah Snavely, Kavita Bala, and Kilian Weinberger. Deep feature interpolation for image content changes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7064-7073, 2017.
[61] Vassilis Vassiliades and Jean Baptiste Mouret. Discovering the elite hypervolume by leveraging interspecies correlation. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 456. 2018.
[62] Vassilis Vassiliades, Konstantinos Chatzilygeroudis, and Jean- -ean-Baptiste Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(4):623-630, 201 8. doi: 10.1
[63] Vanessa Volz, Jacob Schrum, Jialin Liu, Simon M Lucas, Adam Smith, and Sebastian Risi. Evolving mario levels in the latent space of deep convolutional generative adversarial network. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 221-228, 2018.
[64] Tom White. Sampling generative networks. arXiv preprint 1609v:1609.0444 2016.
[65] Yulun Zhang, Bryon Tjanaka, Matthew C. Fontaine, and Stefanos Nikolaidis. Illuminating the latent space of an mnist gan. pyribs.ory swwibb.org.22. 2021. hRLLhhtts:://ooo http://oocop....p...oo pyrriss........ wrw/ongg///ooo.... en/ stable/tutorials/
1si mnist. html MIT License.
13


Reviews:
[{"review_id": "nXPkVp3EaD", "reviewer": "Reviewer_fNzE", "summary": "The paper makes three primary contributions:\n\n(1) The paper proposes a new problem setup, called Differentiable Quality Diversity (DQD), where the goal is to optimize for a set of diverse solutions that maximize a target objective. Diversity is formalized by assuming the existence of **differentiable** measure functions, which intuitively specify an axis of variation and thus far away solutions along in the joint space of these measure functions are more diverse.\n\n(2) To solve the DQD, the paper extends the MAP-Elite algorithms from the related and previously studied non-differentiable variant, abbreviated as simply QD. The extensions incorporate gradient information in novel ways, interfacing first-order methods with evolutionary search style procedures. \n\n(3) Finally, the authors conduct empirical evaluation of the proposed algorithms which suggests that these combinations of gradient and evolutionary algorithms are indeed better than either approach alone on some toy benchmark tasks and a generative modeling task.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of my knowledge, both the problem setup and the proposed solutions are novel. The setup itself is a non-trivial important special case of the previously studied Quality Diversity problem, eg, the use case in generative modeling has potential implications beyond just diverse face generation in other scientific fields as well. The methods proposed in the work are sound, simple, and easy to implement. I also liked their descriptions, which was sufficiently clear in text and aptly formalized mathematically. \n\nQuestions/comments for clarification and improvement:\n\n- In CMA-MEGA, could the authors study the effect of the ranking strategy on downstream performance? in particular, it is not obvious to me that prioritizing all exploration candidates over  the delta improvements is a good defacto strategy. If the delta improvement is very large, then deprioritizing it to explore a new cell is not ideal. Similar to explore-exploit strategies in bayesopt, RL algorithms, an acquisition function style approach to scalarize the exploration score and the delta improvement score seems like a better strategy.\n\n- In general, for the QD problem, we expect a Pareto optimal frontier of (max or top-m) QD score vs. coverage. The results in Table 1 focus on a specific point on this frontier. Can we tailor the algorithms to target a specific frontier? (i.e., for x% coverage, what is the best QD score we can obtain? Or vice versa)\n\n- Empirical trends of model performance as a function of number of cells would be interesting to include for testing the scalability of the approaches and also for monitoring the divergence in performance from a baseline gradient-only approach (at the extreme, when number of cells is 1, we only care about the target based objective and the gradient based approach is expected to dominate).\n\n- Latent space illumination is a very important problem and a very convincing motivation for this work. But the empirical investigations seemed lacking. While the authors acknowledge that the results are not very robust to hyperparameters, a further investigation as to analyzing the causes of instability and tricks to alleviate them would make the work more extendable by other practitioners. The current set of results based on 1 elon musk prompt are too limited and potentially subject to cherrypicking.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the limitations are well described. I would encourage the authors to move the societal impact section from the appendix to the main text, especially given the rising concerns and useful applications of generative modeling. Also, they should include examples of LSI covering diverse demographics and not restrict to Elon Musk.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {"ethical_concerns": "The paper uses a generative modeling task as an application. Like any other application, the model could have biases but with human faces as the domain of interest, the societal and ethical concerns are even more barebones. The paper has acknowledged these concerns to a reasonable degree."}}, {"review_id": "gJxdHA1MPcs", "reviewer": "Reviewer_ghwT", "summary": "In the paper \"Differentiable Quality-Diversity\", the authors propose a new set of algorithms quality diversity algorithms for differentiable problems. Quality-Diversity is a new family of stochastic optimisation algorithms, often applied to black-box optimisation problems, where the goal is to generate a large collection of diverse and high-performing solutions. This paper provides novel approaches to leverage gradient information when the problems considered are first-order differentiable. The proposed methods (CMA-MEGA and OMG-MEGA) demonstrate excellent performance compared to state-of-the-art Quality-Diversity algorithms. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and clearly structured. It is pleasant to reach and easy to understand without unnecessary technical definitions and notations.  \nThe proposed methods make a lot of sense and are a smart way of using the gradient information when available. In particular, the combination of the measure and fitness value in a linear combination which then uses CMA-ES to automatically adjust the weights depending on the state of the archive is a nice way to formalise the problem. The use of the proposed methods in the domain of latent space illumination demonstrates promising results.  \n\nThe introduction and literature review about quality diversity is appropriate and is likely understandable by non-expert readers. \n\nHere are a couple of mostly minor points and inaccuracies: \n\n1)It might be important to stress that the proposed methods and associated performance improvements are limited to a specific scope of application (first-order differentiable) and that not all problems fall in this category. For instance, the paper says \"we focus on domains with differentiable objective and measures, where DQD is applicable.\". This is not an intentional choice but imposed by the method. \n\n2) \"MAP-Elites first samples solutions from a fixed distribution θ ∼ N (0, I )\". This is not always the case. Multiple papers (in particular from MAP-Elites' authors, including the reference implementation) use a uniform sampling (which require the search space to be bounded). This is a minor detail but can have a significant impact on certain tasks, like the linear projection considered in this paper (a 0 centred normal distribution is likely to make the problem easier). \n\n3) It is correct to say that PGA-ME combines a gaussian variation operator (the Iso+LineDD operator to be exact) with a policy gradient operator only on the objective. However, PGA-ME does not sum (or successively apply) the two operators on the same individual. Instead, it randomly applies one of those for each new offspring. The OG-ME variant introduced in this paper sums these two operators which is likely to create mutations that are too large to be effective.\n\n4) I did not find the definition of the weights wi used in line 14 of algorithm 1. \n\n5) I understand the desire to make some benchmarks more challenging, but I think that a 1000dof planar robot is a bit too much in my opinion (in particular when considering that this benchmark was initially based on a real 8dof robot). I hope that in the future the community will come up with realistic domains that will be challenging enough to demonstrate the benefits of such methods. \n\n6) The value of theta_0 used in the experiments cannot be found in the paper and supplementary material. \n\n7)Table 1 reports a surprising result: CMA-ME in the two LP domains seems to perform like MAP-Elites and worse than MAP-Elites (line), which goes against the main result of the original CMA-ME paper (which uses the same domains). The same thing is observed in the table provided in the supplementary material. However, I cannot find a discussion about this in the paper.\n\n8)In the sentence \"To make the QD-score invariant with respect to the resolution of the archive, we normalize QD-score by the archive size\", does \"archive size\" refer to the maximal archive size, or the number of solutions in the archive? I believe it is the former, but this could be clarified to avoid confusion.  \n\n9) In \"Naturally, approaches combining QD and RL have started to emerge [42, 9]. Unlike DQD, these approaches estimate the gradient of the reward function in action space and backpropagate this gradient through a neural network. Our proposed DQD problem differs by leveraging provided gradients for both the objective and measure functions.\", it is important to note that QD-RL [9] introduces a diversity gradient (via a diversity critic), and uses both the policy gradient (reward-based) and the diversity gradient. Therefore, it is inaccurate to say that DQD differs from other approaches because it uses gradient at both levels. Additionally, QD-RL is not limited to differentiable problems. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I cannot identify potential direct societal impacts of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YYfuRuVfy3", "reviewer": "Reviewer_T1rp", "summary": "The authors propose a quality diversity framework whether the objective and measure functions are differentiable. They propose two algorithms to this end by augment existing QD algorithms with gradient information and present experimental results on two benchmarks and a latent space illumination task. ", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Update: I've revised my score from 7 to 8, following the author response.**\n\n**Pros**  \n- The idea of DQD proposed by the paper is an intuitive and natural development combining ideas from QD with modern ML driven by first-order optimization. \n- The paper is extremely well-written, with a brief but useful explanation of the background, and the algorithms are carefully described in detail. \n- The DQD benchmark with StyleGAN-CLIP is quite intuitive and is bound to inspire some follow-up work.\n- The experimental evaluation is convincing, with the proposed algorithms demonstrating clear wins in high dimensional parameter spaces. \n- The experimental results are presented with a statistical significance analysis -- I commend the authors for this.\n\n**Cons/Questions**  \n- My first instinct upon looking at the problem would be to write down an optimization problem which trades-off the objective for diversity, e.g.,maintain a catalog $\\theta_1, \\cdots, \\theta_N$ and iteratively update $\\theta_j$ with an approximate solution to $\\max_\\theta f(\\theta) + \\lambda \\sum_{i \\neq j} \\Vert m(\\theta) - m(\\theta_i)\\Vert^2$ where $\\lambda$ is a trade-off parameter. How is the proposed approach better than this baseline? \n- MEGA takes one gradient step in Eq. (3). What are the pros and cons of taking multiple gradient steps? Would this help experimentally? \n- The proposed strategy to tune the learning rate in Appendix A does not seem scalable. Could the authors suggest some heuristics to choose the learning rate? How would a grid search work in this case? \n- How do you choose the noise variance $\\sigma_g^2$? What happens if it is too large or too small? \n- It would be helpful if the authors could show plots with QD score and coverage percentage versus the learning rate and $\\sigma_g^2$\n- (minor) $w_i$ is undefined in Algorithm 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "16OK-73iwAT", "reviewer": "Reviewer_4FYu", "summary": "This work introduces  DQD (differentiable quality diversity) problems: quality-diversity (QD) problems when both the objective function and the measures of diversity are differentiable. The running example for this is obtaining a variety of generated images corresponding to the objective \"looks like Elon Musk\" and diverse with respect to hair and eye color.\n\nThe authors then introduce 2 algorithm variants that can take advantage of differentiability to solve the DQD problem. \n- OMG-MEGA uses gradient arborescence to explore based on the diversity measures and optimize with respect to the objective. \n- CMA-MEGA branches based on both objective and diversity measures, but optimizes with respect to the objective. \nBoth proposed algorithms are variants on QD solutions (resp. MAP-Elites and and CMA-ME) that do not assume access to gradient information.\n\nAcross several experimental evaluations, the authors show that their proposed algorithms, and especially CMA-MEGA, outperform baselines that do not access gradient information, both in terms of maximizing the QD score and in terms of coverage of the search space.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This work builds upon prior solutions to building archives for the QD problem, taking advantage of use cases in which gradient information is available for both the QD objective and diversity metrics.\n\nQuality: This work reads as a complete paper, with a careful analysis of the pros and cons of the proposed methods (e.g., computational complexity constraints when applied to experimental design settings). Being unfamiliar with the relevant QD literature, I would have found this paper easier to parse were it to include a more in-depth discussion of several key steps of the proposed algorithm. In particular:\n- how important is normalizing the gradient in OMG-MEGA and CMA-MEGA? \n- can you formalize your claim \"$\\sigma_g$ acts as a learning rate for the gradient step\"?\n\nClarity: Without familiarity with the QD literature, the distinction between the CMA-MEGA and baseline CMA-ME algorithm is difficult to parse. Algorithm 1 could be augmented to include comments indicating deviations from the CMA-ME algorithm for increased clarity. \nI also found the running Elon Musk example somewhat counter-intuitive, and Figure 3 difficult to read (the eye color is not easily visible). I do not know if this is easily feasible, but choosing an example with more phenotype variation (dog breeds?) that is less reliant on small detail variations would have increased readability (in my opinion).\n\nSignificance:\nThe results seem significant to the QD community, as the introduced algorithms, and CMA-MEGA variants in particular, show vastly improved coverage of the search space compared to previous QD baselines.\n\nMinor comments and questions:\n- I believe the correct reference for MAP-Elites is [40] as well as [13] (last paragraph, page 1)\n- When you mention the QD objective (line 121), are you referring to $f(\\theta)$? \n- In Figure 3 of the appendix, it seems that adding the Adam variation can make a significant impact on the coverage. Do you have any intuition why this may be the case?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and negative societal impact have been discussed in detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Meta-review of Differentiable Quality Diversity

This paper proposes the first differentiable version of “Quality Diversity” optimization. QD, along with other multi-objective optimization methods, look at generating a large collection of diverse solutions, and are well-explored in the evolutionary computation community, while lesser known in the ML / RL community.

The 3 main contributions of this paper are well-summarized by reviewer fNzE:

1. The paper proposes a new problem setup, called Differentiable Quality Diversity (DQD), where the goal is to optimize for a set of diverse solutions that maximize a target objective. Diversity is formalized by assuming the existence of differentiable measure functions, which intuitively specify an axis of variation and thus far away solutions along in the joint space of these measure functions are more diverse.

2. To solve the DQD, the paper extends the MAP-Elite algorithms from the related and previously studied non-differentiable variant, abbreviated as simply QD. The extensions incorporate gradient information in novel ways, interfacing first-order methods with evolutionary search style procedures.

3. Finally, the authors conduct empirical evaluation of the proposed algorithms which suggests that these combinations of gradient and evolutionary algorithms are indeed better than either approach alone on some toy benchmark tasks and a generative modeling task.

Usually, the work in QD in the EC community focuses on artificial agents (like simulated robots), but here, the work really sheds light on how QD can be applied and effectively used in applications that the DL community is also interested in, like image generation. As Reviewer 4FYU pointed out: *the running example for this is obtaining a variety of generated images corresponding to the objective "looks like Elon Musk" and diverse with respect to hair and eye color*. Reviewer T1rp agrees, and mentions *The DQD benchmark with StyleGAN-CLIP is quite intuitive and is bound to inspire some follow-up work.*

All in all, the reviewers, including myself, agree that this paper is very well written, with good background explanation, well motivated, and presents experiments that are not only convincing, but will attract many folks in the NeurIPS community especially those in generative modelling to start using QD.

Given the feedback about the generally high quality of the paper and potential impact, I would like to recommend acceptance as Spotlight presentation.

Decision: Accept (Oral)