Gradient-Informed Quality Diversity for the Illumination of Discrete Spaces
Authors: Guillaume Richard
Raphael Boige
Jérémie DONA
Antoine Cully
Thomas PIERROT
Venue: Submitted to ICLR 2023 (2023)
Keywords: Quality Diversity
Latent Space
Protein

Abstract: Quality Diversity (QD) algorithms have been proposed to search for a large collection of both diverse and high-performing solutions instead of a single set of local optima. While early QD algorithms view the objective and descriptor functions as black-box functions, novel tools have been introduced to use gradient information to accelerate the search and improve overall performance of those algorithms over continuous input spaces. However a broad range of applications involve discrete spaces, such as drug discovery or image generation. Exploring those spaces is challenging as they are combinatorially large and gradients cannot be used in the same manner as in continuous spaces. We introduce MAP-Elites with a Gradient-Informed Discrete Emitter (ME-GIDE), which extends QD optimisation with differentiable functions over discrete search spaces. ME-GIDE leverages the gradient information of the objective and descriptor functions with respect to its discrete inputs to propose gradient-informed updates that guide the search towards a diverse set of high quality solutions. We evaluate our method on challenging benchmarks including protein design and discrete latent space illumination and find that our method outperforms state-of-the-art QD algorithms in all benchmarks.




Under review as a conference paper at ICLR 2023
GRADIENT-INFORMED QUALITY DIVERSITY FOR THE ILLUMINATION OF DISCRETE SPACES
Anonymous authors Paper under double-blind review
ABSTRACT
Quality Diversity (QD) algorithms have been proposed search for large collec- tion of both diverse and segh-performing solutions instead of single set of local optima. While early QD algorithms view the objective and descriptor functions as black-box functions, novel tools have been introduced to use gradient information to accelerate the search and improve overall performance of those algorithms over continuous input spaces. However broad range of applications involve discrete spaces, such as drug discovery or image generation. Exploring those spaces is challenging they combinatorially large and gradients cannot be used in the same manner as in continuous spaces. We introduce HAP-ELITES with a Gradient- Informed Discrete Emitter (ME-GIDE), which extends QD optimisation with dif- ferentiable functions over discrete search spaces. ME-GIDE leverages the gradient information of the objective and descriptor functions with respect to its discrete in- puts to propose gradient-informe set of high quality solutions. We evaluate our method on challenging benchmarks including protein design and discrete latent space illumination and find that our method outperforms state-of- oft-----t--tt- QD algorithms all benchmarks.
updates that guide the search towards a diverse
INTRODUCTION
Quality-Diversity (QD) Optimization algorithms Chatzilygeroudis et al. (202T): Cully & Demiris (017)) have changed the classical paradigm of optimization: inspired by natural evolution, the essence of QD methods is to provide large and diverse set of high segghpeeffrming solutions rather than only the best one. This core idea showed great outcomes in different fields such as roboties Cully et al. (2015) where it allows to learn to control robots using diverse and efficient policies or latent space exploration Footaine et al.] (202T) of generative models generate diverse set of high quality images video game levels. The main QD approaches are derivative-free optimizers, such as the MAP-ELITES algorithm Mouret Clune (2013), genetic algorithm that tries to find high quality solutions covering the space defined by variety of user-defined features of interest. However, subsequent methods Nilsson & Cully (202I); Fontaine & Nikolaidis (2021) have shown that when the objective functions (quality) the descriptor functions (diversity) differentiable, using gradients of those functions can improve convergence both in terms of speed and performance compared traditional QD algorithms. Those methods were applied to Reinforcement Learning problems such as robotics Pierrot et al. (2022) or latent space illumination Fontaine & Nikolaidis 202T of generative adversarial networks.
Those applications focused on optimization over continuous variables. However many real-world applications are best framed using discrete features. For instance, generative architecture such as discrete VAEs Van Den Oord et al. (2017); Rolfe (0016) have shown capability to generate high- quality images Razavi al. (2019) and have been the core of recent successful approaches for text-to-image generation Ramesh et al. (2021): Gafni et al. (2022). A further natural application using discrete variables is protein design Huang et al. (2016); proteins play a role in key functions in nature and protein design allows to create new drugs or biofuels. As proteins are sequences of 20 possible amino acids, designing them is a tremendously hard task as only a few of those possible sequences plausible in the real world. Deep learning for biological sequences provided significant advances in several essential tasks for biological sequence, such AlphaFold for structure prediction Jumper al. (2021a) or language models for amino acid likelihood prediction Rives et al.

---

Under review as a conference paper at ICLR 2023
Insert mutant in the repertoire
Compute and combine gradients
Gradient -nffrreed Discrete Emitter
Repertoire
V
V
Compute mutation probabilities
Sample mutant
Sample element
Figure I: MAP-ELITES with Gradients Informed Discrete Emitter (ME-GIDE). At each iteration, an element is sampled in the repertoire. Gradients are computed over continuous fitmess and descriptor functions with respect to their discrete inputs. Gradients are linearly combined to favour higher fitness and exploration of the descriptor space. Probabilities of mutation over the neighbours of the element are derived from this gradient information. Finally, a mutant is sampled according to those probabilities and inserted back in the repertoire.
2021 These successes motivate the use of these tools as objective functions for protein design Anishchenko et al. (2021a).
In practice, objective functions are often written differentiable functions of their inputs, enabling the use of gradient information of the continuous extension if the input are discrete Grathwohl et al. 2021 We second this research trend and address gradient informed quality-diversse optimization over discrete inputs when objective and descriptors functions are differentiable. We make several contributions: (i) we introduce HAP-ELITES with a Gradient-Infomen genetic algorithm where mutations are sampled thanks to gradient informed distribution. (ii) We propose way to select the hyperparameters this algorithm by weighting the importance we give to this gradient information. (iii) We demonstrate the ability of our method to better illuminate discrete spaces on proteins and the discrete latent space of a generative model.
Discrete Emitter (ME-GIDE),
PROBLEM DEFINITION
In this work, we consider the problem of Quality Diversity Optimization over discrete spaces. The QD problem assumes an objective function f X - TR, where X' called search space, and descriptors e X + R. or the descriptor space formed by the range c. We only consider discrete spaces of dimension m with K categories such that X' C f1...., K)m QD algorithms of the family of the MAP-ELITES algorithm, discretize the descriptor space S via a tessellation method. Let T the tessellation of S into M cells S. The goal of QD methods x; occupies a different cell S, in T and maximizes the objective function within that cell. The QD objective can thus be formalized follows:
single descriptor function X + Rdd We note S c(X²
find set of solutions x; E X' so that each solution
M f(x)), where Vi, c(x,) E S..
maX X
(1)
We consider here that both the objective and descriptor functions actually defined real values and restricted to the discrete inputs X. We also consider them to be first-order differentiable, hence for any input & E X, compute gradients [x)()) and V,c(()).
2

---

Under review as a conference paper at ICLR 2023
Algorithm/ 1: Gradient Informed Discrete Emitter (GIDE)
Given: batch of B elements 2n, from the repertoire.
for S n S do
// Compute the distribution
Compute d, using Equation 2
Compute the proposal distribution Pa using Equation
// Target entropy
Adjust T to obtain target entropy f = Hurga over the proposal distributions.
// Sample
Draw mutant s from each according to Pa.
end
Return z1, 21,...,. Z'B
3 MAP-ELITES WITH GRADIENT PROPOSAL EMITTER
MAP-Elites and Differentiable MAP-Elites MAP-ELITES is a QD method that discretizes the space of possible descriptors into repertoire (also called archive) via tessellation method. Its goal is to fill each cell of this repertoire with the highest performing individuals. To do so, MAP-ELITES the BD space and secondly initializes random solutions, evaluates
firstly initializes repertoire them and inserts them in the repertoire. Then successive iterations are performed: (i) select and copy solutions uniformly over the repertoire (ii) mutate the copies to create new solution candidates (ii) evaluate the candidates to determine their descriptor and objective value (iv) find the corresponding cells in the tessellation (v) the cell is empty, introduce the candidate and otherwise replace the solution already in the cell by the new candidate if it has a greater objective function value. When using real variables, the most popular choice is the Iso+LineDD Vassiliades Mouret (2018) that mixes two gaussian perturbations. When using discrete variables, mutations are generally defined as point mutation, ie select a random position and flip its value from the current one to a new one.
To incorporate gradients into MAP-ELITES algorithms, (Fontaine & Nikolaidis, 2021 introduced MAP-ELITES with a Gradient Arborescence (MEGA) novel way to use gradient information to guide the mutations. First, the authors propose novel objective function to encompass both quality and diversity: g(z) fx)) + Edd (x)( where w; (O, ag Vi E {o..... d.. In one version of their algorithm, OMG-MEGA, authors simply extend MAP-ELITES by mutating selected element of the repertoires x via x' x + |wo Vag((r) where w; are sampled at each iteration and for each element in the batch and 0g acts similarly to a learning rate. Indeed, maximizing will direct the mutations towards higher fitness and different directions of the descriptor space thanks to the randomness introduced by sampling the wi.
From Gradients to Gradient Informed Discrete Emitter As this approach has proven effective on several tasks, follow the previous formulation by trying maximize g- In this given iteration, for a given sampled æ E X' and given sampled coefficients Co....d, our mutation should ideally find a neighbour x' X' that maximizes g. Ideally, our operator should provide x' arg max max (w) 9(2) - g(x). where (z(x) the Hamming ball of size around our mutation.
However, for given variable E (1....,K'" K}m,, even for = the cardinality of this Hamming ball is mKK Hence finding the optimal x' requires mK 1 evaluations of g. Doing each step would be too expensive but since those differences are local, they can be approximated using gradient information. Following Grathwohl et al.) (202T) we use Taylor-series approximation of the local differences: noting (f,,6) the mutant from by flipping the position i from x; to k, we estimate those differences as
- (
Veg(z)a - xf (VVg(z)) = dd+
where x' differs from by a flip position 1 < iis m from I; to k {1,..,, K). The previous formulation works in the case where 7 = but similar approximations can be derived for larger window sizes at the expense of the approximation's qualitt
3

---

Under review as a conference paper at ICLR 2023
Using those approximations, could straightforwardly compute local maximum of by taking the argmax at each step. order to encourage exploration, we use those approximate local differ- ences to create proposal distribution over the neighbours of æ. Inspired by sampling techniques such Aatropolis-Hastingss define the probability p(x((.)))r) of mutating from to 2(1,k) as
plalik)))) (r) xe* 4
where 0 is a temperature parameter. The temperature parameter tempers whether the mutation will go towards the argmax (I' + 0) purely random mutation (I' + +oo). Finally, in order
to sample flips at position i from 2; to k we normalize those probabilities by computing softmax over every possible flip (mK possibilities):
culT
plz (1k)
x))
(4)
BulT
As every approximated difference dis can be computed in gradient evaluation V Vzg(z), those probabilities can be efficiently computed.
Formally our Gradient Informed Discrete Emitter (GIDE) receives a candidate æ, computes du using Equation 2 then computes mutation probabilities using Equation and finally samples mutated (((()) using these probabilities. We summarize this procedure in Algorithm 1
Using this emitter, we design our main algorithm: MAP-ELITES with a Gradient Informed Discrete Emitter (ME-GIDE). The procedure follows the one of MAP-ELITES: we firstly initialize repertoire of behaviour descriptors. Then at each iteration, the following operations are performed: (i) select batch of solutions uniformly the candidates and add them in the repertoire their fitness is higher than the existing solution in the cell. This procedure is described in Algorithm with additional step to control the strength of the gradient guidance defined in the following paragraph.
the repertoire (ii) sample mutants using
GIDE (iii) evaluate
Algorithm 2:
MAM-MAP-iee with Gradient Informed Discrete Emitter (ME-GIDE)
Given: the number of cells M and tesselation the batch size and the number of iterations N ;the descriptors function and multi-objective function a target entropy value Haarget the initial population of solution candidates {x+)
// Initialization
For each initial solution, find the cell corresponding descriptor and add initial solutions their cells.
// Main loop
for 5 Vheee S N do
// Select Sample uniformly solutions s, the repertoire with replacement
generation
// Compute the gradients
Randomly draw weights w(n) ~ ~N(0)) 7) Compute gradients Vz, (x.,) and V.,, c(x,) Normalize the gradients.
Compute combined updates V. ww! (0)) V., ((x) + Σ (m) (
V2, ((x))
// Gradi Info--Idd Discrete Emitter Use Algorithm D to sample mutants x/,
// Additicn in the archive
Add each mutant in its corresponding cell it improves the cell fitness, otherwise discard it.
end
4

---

Under review as a conference paper at ICLR 2023
Controlling the Gradient Guidance with Target Entropy The shape of the flip distribution Pi.k computed by GIDE strongly depends on the choice of the temperature parameter T. However, searching for optimal value of this unbound parameter can be tedious owing the fact that it lies in [0, + and has limited human-interpretabliiyy. Since this temperature parameter 7 controls the concentration of the probability mass over the directions with highest estimated- -improtedeemoo values de,,, mispecifying it would result in suffering either degenerated or uniform distribution. The former means being too greedy towards the most promising directions, which hinders exploration, while the latter means under-exploiting our estimate. We propose to tackle this exploration expllitatteliiiiiiionnn tradeoff by controlling the Shannon entropy of the flip-distribution (pt.)). When T - O, we approach the deterministic distribution over the highest estimate, i.e. with minimum entropy and when 7 - tc we approach the uniform distribution, i.e. with maximum entropy.
To avoid either degenerate cases, we set a target Hurget for the normalized entropy (p:.k) = (pp.a))
log[mm] [0, 1] of the flip distribution. We aim to find value T such that (p..)) Harget- The relationship between the normalized entropy and the temperature is non-trivial and depends on the gradients of g. Using Equation we can write the normalized entropy equation as a func- tion of the temperature T. we solve numerically for T by minimizing by gradient descent the penalty, In practice, to select an appropriate target Hurget we find it enough to test a few values in Hurget E {0.4, 0.6, 0.83. One can note that setting Hurget = 1 corresponds to completely random mutations.
4 EXPERIMENTS
4.1 SETTINGS
We conduct experiments different benchmarks to assess the performance of our new emitter. Namely, we experiment on three challenging applications: illuminating a family of proteins, gener- ating diverse images by working directly on the discretized pixel space and illuminating the discrete latent space of a generative model.
Design in the Ras Protein Family As proteins are involved in numerous biological phenomena, including every task of cellular life, designing them has been a longstanding issue for biologists. The simplest way to describe protein is through its primary structure: a natural protein is sequence of 20 basic chemical elements called amino-acids. Designing a protein is generally framed as finding the sequence of amino acids that maximizes score representing a property of a protein, such as its ability of binding to a virus or its stability. It is a tedious task as the search space grows expo- nentially with the length of the protein of interest, for instance designing a protein of 100 residues operates over space of 20 100 elements. In our experiment, we aim to redesign members of the "Rat sarcoma virus" (Ras) protein family (extracted from PFAM database (Mistry et al. 202T)), in- volved in cellular signal transduction and plays a role in cancer development Bos 1989) Following a common procedure members to maximize their stability. While many methods use biophysical simulations to estimate this stability Desmet et al. (1992). we follow recent trends Anishchenko et al. (2221b) and use a pre-trained neural network to approximate it.
computational protein design Huang et al. (2016), we aim to redesign its
Namely, for a given sequence, our objective function is defined as the log-likelihood provided by pre-trained protein language model: ESM2 et al. (2022); Rives et al. (2021). Indeed, it was shown that this quantity is correlated to the stability of a protein and can even be used to predict the effect of these mutations Hopf et al.] (2017); Riesselman al. (2018). We an unsupervised procedure to create descriptors similar to AURORA Grillotti & Cully[(2022) we sample 1,000,000 AURORA[Grillont
proteins from the Uniref50 database, compute their 640-dimens embeddings using ESM2 at the 20th layer and perform PCA on those embeddings to extract 5 components, Finally we use K -Means algorithm with K 30000 on these projected embeddings create the tesselation with 30, 000 cells. The descriptors of sequence is the corresponding projected embedding of this sequence and mapped its corresponding cell by finding the closest centroid. In practice, we use the 120, 000 elements of this family at initialization.
https:/
p/uni ref
5

---

Under review as a conference paper at ICLR 2023
Ras Protein Family
Binarized digits
Discrete LSI-1
Discrete LSI-2
QD score
00
02
64
26
02
04
06
08
Number of evalustions
Number of evaluations
Number of evalisaioon
Number of evaluations
ME-GIDE
ME-GIDE
ME-GIDE
ME-GIDE
ME
ME-GDP
ME
ME
Figure 2: (Top) QD-score evolution the different domains (median and interquartile range over seeds). ME-GIDE outperforms MAP-ELITES on every experiment and ME-GDP on every experiment except for Binarized Digits. Only the solution corresponding the best set of hyperparameters shown for MAP-ELITES and ME-GDP. (Middle) Final repertoire of ME-GIDE for one seed. A yellow color corresponds high fitness, whereas darker colours correspond to lower fitnesses. (Bottom) Repertoire of the best performing baseline.
Binarized Digits To further illustrate the interest of method, design experiment binary data consisting in generating diverse MNIST digits with QD methods. Given our fitness and descriptor functions,
aim find out how QD methods compare in generating diverse digits by directly searching over the image space. We define the fitness using an energy-based model trained on discrete MNIST data. Following Grathwohl
(20TT), we train a restricted Boltzmann machine (RBM) Hinton (2012) the binarized 28x28 images. To obtain descriptors we define diversity space by embedding the MNIST dataset into the hidden layer of the RBM and then by computing PCA over these embeddings. Thus, descriptors are defined as projections over the top-d components of this PCA with 20. We again finally use a K-Means algorithm with these projected embeddings to create the tesselation with 10, 000 cells. We display in Appendix how this descriptor space spans the different digits' classes. In our experiments, we initialize our images with randomly uniform distribution.
10000
Discrete Latent Space Illumination (LSI) Recent works/Fontaing al. (2021). Fontaine & Niko- laidis (022)) have proposed the latent space illumination of generative models (LSI) problem as a benchmark QD methods. It consists in searching the latent space of a large generative model for diverse and relevant latent codes. The diversity of the sampled images being a major concern for generative models, perfectly aligns with the QD methods design. For instance, |Fontaine & Niko- laidis) (2021) uses QD methods to illuminate the latent space of StyleGAN, they leverage CLIP Radford et al. (2021) prompts to create both a fitness function and a descriptor space and to gener- ate diverse images that satisfy some prompts. Since work is focused on discrete variables, we instead chose to illuminate the latent space a discrete VAE. Specifically, we choose to explore the latent space of vector-quantized auto-encoder (VQ-VAE). Similarly to previous work, CLIP to evaluate the quality of the VQ- VeE-deodde latents as well as their diversity. We have experimented two sets of prompts. The first aims to generate labrador dog images, the fitness is

---

Under review as a conference paper at ICLR 2023
defined with the prompt "A labrador" while the descriptor functions are defined "A white puppy" and "A dog with long hair". The second set of prompt searches for truck images with fitness prompt "A truck" and descriptor prompts "A red truck", "A blue truck". The aim of this experiment is to find a large set of latent codes which once decoded yield diverse images with high scores accord- ing the CLIP evaluation. We refer the reader to the Appendix [C for the VQ-VAE model's details, and the training procedure. We want to stress that our goal is only to explore the latent space of the VQ-VAB the light of the CLIP score and descriptors functtins, do aim compete with image generation procedure nor with text-to-image approaches.
Experiment Setup In addition to our ME-GIDE al- gorithm, compare with two main baselines. The first baseline, MAP-ELITES stands for the original MAP- ELITES algorithm with completely random mutations each step. Searching via random mutations is the most popular solution when prior knowledge is assumed over the structure of solution. We also consider addi- tional variation operators such crossover. We also com- pare ME-GIDE to a natural baseline: gradient descent with projection (ME-GDP). Inspired by Fast SeqProp Linder & Seelig 2020), ME-GDP uses gradients following Objec- tive and Measure Gradient MAP-ELITES via Gradient Ar- borescence (OMG-MEGA) Fontaine & Nikolaidis (2021) and projects the mutants back to the discrete set. We im- plement every method based on Jax using the QDax open source library Lim et al. (2022).
(202))
Figure 3: Ras proteins designed by MF- GIDE, visualized using the prediction of AlphaFold. One can see diverse pat- terns in the secondary structure, while still retaining high estimated stability.
We run every experiment method. We use a repertoire with 30, 000 centroids for the protein experiment, 10, 000 centroids for the binarized digits experiments and 40, 000 centroids for the discrete LSI experiments. We stop the illumination after evaluat- ing le6 candidates on the protein and binarized digits experiment and 5e6 evaluations for the discrete LSI experiment. We provide more details about the settings in Appendix A
5 different seeds for each
4.2 RESULTS AND ANALYSIS
Figure 2 summarizes the results of our experiments, we display the median and the interquartile range over seeds for every benchmark. In the Ras and Discrete LSI experiments, ME-GIDE outper- forms other methods, since it converges in fewer iteration to higher performances. For clarity, only plot the results corresponding for the best set of hyperparameters for the basclines MAP-ELITES and ME-GDP. We the scores obtained over different seeds where the null hypothesis that the obtained scores have the same median. It shows that ME-GIDE constantly outperforms MAP-ELITES the QD score with p-values lower than 0.05 in every experiment and outperforms ME-GDP on every experiment except Binarized Digits.
Wilcoxon signed-rank test Wilcoxon| (1992) to compare the distribution of
Our target entropy procedure allows an easier choice of hyperparameters for ME-GIDE. Indeed, in our experiment, we only try for three values: 0.4, 0.6 and 0.8. While we display the best results for clarity on Figure 2 the conclusion are similar for values in the range [0.4, 0.8) as detailed in Appendix B
Interestingly, ME-GDP under-performs compared to purely random mutations for any set of hyper- parameters on both protein and VQ-VAE experiments. This means performing gradient descent
7

---

Under review as a conference paper at ICLR 2023
similarly as in the continuous case is dangerous when ing discrete variables. We validate that the estimation of
Z
g(x((t))) - g(x) using du is sensible by computing the cor-
relation for some elements of each domain between those two quantities. For instance, for the discrete LSI experiment, we find an average correlation p 0.55, which means that even though the step between x.(ak) and r might be large, gradient information is indeed relevant. We give more details about this analysis in Appendix
1
3
4
5
We display some samples of the final repertoire obtained by ME-GIDE on Figure 3 To visualize the 3D structure of those proteins, we use AlphaFold2 [ Jumper et al. (2021b). One can that ME-GIDE manages extract proteins with various sec- ondary and tertiary structures and that those proteins have high confidence score according to AlphaFold. We also conduct further validation on the protein experiment. We subsample our repertoire by recomputing larger cells to obtain repertoire with 300 cells. Then, we insert the original repertoire into this smaller one to obtain the most fit solutions in each region. We firstly analyze the diversity in the sequence space, defined as the average edit distance between obtained solutions. We find that ME-GIDE reaches
Figure 4: Samples from ME-GIDE final repertoire on the Binarized Digits experiment. sample the 40, 000 elemnts in the reprtoire by clustering its centroids to 16 and display the element in each cell.
We down-
average distance of 106.9 whereas MAP-ELITES gets 97.2. We also use S4Pred Moffat S4PredMMfffat & Jones 202T) y to predict the secondary structure of each protein and use the average edit distance between secondary structures. ME-GIDE outperforms MAP-ELITES, obtaining aver- age distance of 44.2 against 34.9, and finds more diverse structures while also reaching an overall higher average fitness.
On Figure we first display some samples found by ME-GIDE on the binarized MNIST experiment. One can see that ME-GIDE is able to find diverse im- ages that resemble MNIST images and covers every digit. We also visualize on Figure 5 tor-performing images from the repertoire learned by ME-GIDE as well as natural images from the ImageNet dataset. Images found by ME-GIDE cannot be considered to match the prompt from human point of view al- though a small shape of a dog appears in the cen- ter of the image. It should still be noted that these images have higher CLIP scores than natural im- ages that humans would score as perfectly aligned with the score prompt. In sense, ME-GIDE man- ages to "fool" CLIP. Our work emulates the findings of Nguyen et al. (015a) where Evolutionary Algo- rithms manage to "fool" classifier. Our study high- lights the difficulty of directly sampling relevant la- tent codes in the latent space of discrete VAE, which is general bypassed by an additional auto-regressive model that learss to sample meaningful latent codes.
HE-GIDE samples
ImageNet images
Image
CLIP score
Image
CLIP scare
70.2 2
66.2
70.9
66.7
Figure 5: Samples found by ME-GIDE on the "Labrador" prompt against highest scor- ing images from ImageNet dataset. While the images found by ME-GIDE are not nat- ural images, they achieve a higher score to be a "labrador" according CLIP.
RELATED WORKS
Discrete optimization Parker & Rardin (2014) is longstanding branch of optimization where some of the variables or constraints are discrete. It is also named combinato- rial optimization as the set of feasible solutions is generally finite but evaluation every solution is irrealizable. A first class of algorithms search for exact solution: in particular, Integer Linear Prgoramming Schrijver (1998) has been the main subject of interest with exact methods such as cutting plan Gilmore & Gomory (1961) or branch and bound Land & Doig (210)). On the other hand, evolutionary algorithms have been very popular as they allow for more flexibility and can be stopped any iteration to get the best solution explored so far Dorigo et al. (199)). Most of those
Discrete Optimization
8

---

Under review as a conference paper at ICLR 2023
algorithms either incorporate this knowledge by mutating only to feasible solutions or relax- ation and then project back to the feasible set Lin & Hajela 1992). For instance, for protein design, exact methods have been proposed for specific biophysical cost functions related to the potential energy Desmet et al. (1992) of the protein or its binding affinity Ojewole et al. (2018). However, due
to the limitations in flexibility of the previous methods, the most popular design tool, incorporated in the popular Rosetta library, is based on simulated annealing Huang et al. (201I). Several work
tried leverage recent breakthroughs of deep learning methods tailored to proteins in the protein
design, such as AlphaDesign Jendrusch et al. (2021) or TrDesign Norn et al. (202T). To the best of our knowledge, our work is the first propose QD as solution for protein design.
Quality Diversity Optimization Searching for novelty instead of quality Lehman & Stanley (011a) was the first work formulating diversity as an end in itself. was further refined by in- troducing notion of local quality with local competition Lehman & Stanley (201 MAP-ELITES Mouret & Clune (0135) refined the notion of diversity by introducing the notion of repertoire over set of deseriptors. Further improvement were made on the design the descriptor space such as using& a Voronoi tessellation Vassiliades et al. (2177) or use unsupervised descriptors Cully (2019); Grillotti & Cully (2022) as defining tailored descriptors
be tedious for some tasks. More effi- cient ways to illuminate this space have been proposed, such as more efficient mutation operators
Vassiliades & Mouret (2018) or covariance matrix adaptation Fontaine al. (2020). Closest this work is Differentiable QD Fontaine & Nikolaidis (202I) where gradients are used to directly update over the continuous variables.
Application specific methods were developed to apply QD algorihtms to noisy domains Flageat & (2020) or when multiple objectives are (Perrot al. (2022b). Reinforcement Learning
one of the most popular application of QD Arulkumaran et al. (2019) and some methods try to incorporate diversity directly in RI. algorithms Nilsson & Cully] (2021): Pierrot et al. (2022a). QD of the domains
experiment on. The earliest work was named Innovation Engines Nguyen et al. (2015b) where authors try to generate diverse images using a QD approach over ImageNet. Later Latent Space Illumination has been introduced to generate game levels (Schrum et al.] (2020) or images Fontaine Nikolaidis (202T). Our work is also applicable to LSI in the case of discrete latent space and is the first work of its kind to the best of authors' knowledge.
methods have already been applied to Latent Space Exploration,
6 CONCLUSION
We introduced ME-GIDE, a genetic algorithm that leverages gradient information over discrete vari- ables for Quality Diversity optimization and show it outperforms classical baselines. Our entropy- based guidance allows to ease the search for good hyperparameters which can be tedious for some applications. Our experiment on protein design is the first using QD methods the best of author's knowledge and this opens way for more applications in the future. Indeed, we believe that gener- ating not only fit but also diverse proteins can be useful as the fitness given by the model does not always translate to good properties in the lab.
Our goal was not propose a novel image generation technique but while the results of our LSI experiment are interpretable and ME-GIDE finds images with higher fitnesses than realistic images, further research can be done to better understand and exploit these results. Our method can be used to create adversarial examples for generative models using discrete latent spaces, that are becoming more and more popular. On the other hand, to generate more realistic images, we could constrain the search few latent codes and use recurrent architecture to generate more realistic prior, at the cost of potentially facing vanishing or exploding gradients. We leave these open questions for future works.
As our method involves computing gradients of the fitness and descriptor functions, we expect it to be intractable for functions involving large neural networks, such AlphaFold. Using a surrogate model to guide the search while keeping a large model for evaluation or validation to handle those cases could be good research direction.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ivan Anishchenko, Samuel J. Pellock, Tamuka M. Chidyausiku, Theresa A. Ramelot, Sergey Ovchinnikov, Jingzhou Hao, Khushboo Bafna, Christoffer Norn, Alex Kang, Asim K. Bera, Frank DiMaio, Lauren Carter, Cameron M. Chow, Gaetano T. Montelione, and David Baker. De novo protein design by deep network hallucination. Nature, 600(7888) Dec 2021a. ISSN 1476-4687. doi: 10. 01088//41586-021-4188888 241586-021-04111
URL
Ivan Anishchenko, Samuel Pellock, Tamuka M Chidyausiku, Theresa A Ramelot, Sergey Ovehin- nikov, Jingzhou Hao, Khushboo Bafna, Christoffer Norn, Alex Kang, Asim K Bera, et al. De novo protein design by deep network hallucination. Nature, 600(7889):547-552 2021b.
Kai Arulkumaran, Antoine Cully, and Julian Togelius, Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pp. 314-315, 2019.
Johannes I. Bos. Ras oncogenes in human cancer: a review. Cancer research, 49(17):4682-468 1989.
Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiss Mouret. Quality-diversity optimization: novel branch of stochastic optimization. In Black Box Opti- mization, Machine Learning, and No-Free Lunch Theorems, pp. 109-135. Springer, 2021.
Antoine Cully. Autonomous skill discovery with Proceedings of the Genetic and Evolutionary Computation Conference, pp. 81-89, 2019. and unsupervised descriptors. In
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular frame- work. IEEE Transactions on Evolutionary Computation, 22(2):245-259) 2017.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that adapt like animals. Nature, 521(7553):503-5007 2015.
Johan Desmet, Marc De Maeyer, Bart Hazes, and Ignace I Lasters. The dead-end elimination theorem and its use in protein side-chain positioning. Nature, 356(6369) 1992.
Marco Dorigo, Gianni Di Caro, and Luca Gambardella. Ant algorithms for discrete optimization. Artificial life, 5(2):137-172, 1999.
Manon Flageat and Antoine Cully. Fast and stable map-elites in noisy domains using deep grids. arXiv preprint arXiv:2006. 14253, 2020.
Matthew Fontaine and Stefanos Nikolaidis. Differentiable quality diversity. Advances in Neural Information Processing Systems, 34: 10000-10002,, 2021.
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 evolutionary computation conference, pp. 94 102, 2020.
Matthew C Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K Hoover, and Stefanos Nikolaidis. Illuiinating mario scenes in the latent space of generative adversarial network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 5922- 5930, 2021.
Oran Gafni, Adam Polyak, Oron Ashual, Shelly Sheynin, Devi Parikh, and Yaniv Taigman. Make-a-scene: Scene-based text-to-image generation with human priors. arXiv preprint 13311 2022.
Paul C Gilmore and Ralph E Gomory. A linear programming approach to the cutting-stock problem. Operations research, (6)):49 859, 1961.
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops i took a gradient: Scalable sampling for discrete distributions. In International Conference on Machine Learning, pp. 3831-3841. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Luca Grillotti and Antoine Cully. Unsupervised behaviour discovery with quality-diverss optimi- sation. IEEE Transactions on Evolutionary Computation, 2022.
Geoffrey E Hinton. A practical guide to training restricted boltzmann machines. In Neural networks: Tricks of the trade, pp. 599-619. Springer, 2012.
Thomas A Hopf, John B Ingraham, Frank Poelwijk, Charlotta PI Schärfe, Michael Springer, Chris Sander, and Debora S Marks. Mutation effects predicted from sequence co-variation. Nature biotechnology. 35(2):128-135, 2017.
Po-Ssu Huang. Yih-En Andrew Ban, Florian Richter, Ingemar Andre, Robert Vernon, William Schief, and David Baker. Rosettaremodel: generalized framework for flexible backbone protein design. PloS one, 6(8):e24109, 2011.
Po-Ssu Huang, Scott E Boyken, and David Baker. The coming of age of de novo protein design. Nature, 537(7620):320- 2012200--7,200 2016.
Michael Jendrusch, Jan O Korbel, and S Kashif Sadiq. Alphadesign: A de novo protein design framework based on alphafold. bioRxiv, 2021.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino Romera- Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Se- bastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Push- meet Kohli, and Demis Hassabis. Highly accurate protein structure prediction with alphafold. Nature, 596(7873)55335589, Aug a. ISSN 1476-4687, doi: 10. 1003///4118--02--00300 1038
URL http:http///ooo.ooo
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zídek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-588
2021b.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pp. 105-132. Springer, 2010.
Joel Lehman and Kenneth Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 199-2:1992223, 2011a.
Joel Lehman and Kenneth Stanley. Evolving diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp. 21 1-218, 20111 lb.
Bryan Lim, Maxime Allard, Luca Grillotti, and Antoine Cully. Accelerated quality-diversity for robotics through massive parallelism. arXiv preprint arXiv:2202.01258. 2022.
C-Y Lin and Prabhat Hajela. Genetic algorithms in optimization problems with discrete and integer design variables. Engineering optimization, 19(4):309-327, 1992.
Zeming Lin, Halil Akin, Roshan Rao, Brian Hie, Zhongkai Zhu, Wenting Lu, Allan dos San- Costa, Maryam Fazal-Zarandii, Tom Sercu, Sal Candido, and Alexander Rives. Language mod- els of protein sequences at the scale of evolution enable accurate structure prediction. bioRxiv, 2022. doi: 10. 2ttp://222222222220000000000 URL htw.tt:t///// /www www.:bbooxxiv..rr/cooeeeeee
eex.y/2022//1//112022.. 5009002
Johannes Linder and Georg Seelig. Fast differentiable dna and protein sequence optimization for molecular design. arXiv preprint arXiv:2005.1 /275, 2020.
Jaina Mistry, Sara Chuguransky, Lowri Williams, Matloob Qureshi, Gustavo A Salazar, Erik LL Sonnhammer, Silvio CE Tosatto, Lisanna Paladin, Shriya Raj, Lorna Richardson, et al. Pfam: The protein families database in 2021. Nucleic acids research, 49(D1):D4112-441, 2021.

---

Under review as a conference paper at ICLR 2023
Lewis Moffat and David T Jones. Increasing the accuracy of single sequence prediction methods using a deep semi cemi-supervised learning framework. Bioinformatics, 37(21):3744 3751, 2021.
Jean-Bate Saan-Baptstte Mouret and Jeff Clune. Illuminating search spaces by mapping elites. 2015.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confi- dence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 427-436, 2015a.
Anh Mai Nguyen, Jason Yosinski, and Jeff Clune. Innovation engines: Automated creativity and im- proved stochastic optimization via deep learning. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 959-966, 2015b.
Olle Nilsson and Antoine Cully. Policy gradient assisted map-elites. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 866-875, 2021.
Christoffer Norn, Basile IM Wicky, David Juergens, Sirui Liu, David Kim, Doug Tischer, Brian Koepnick, Ivan Anishchenko, Foldit Players, David Baker, et al. Protein sequence design by conformational landscape optimization. Proceedings of the National Academy of Sciences, 118 (11):22017228118. 2021.
Adegoke A Ojewole, Jonathan D Jou, Vance G Fowler, and Bruce R Donald. Bbk (branch and bound over k*); A provable and efficient ensemble-based protein design algorithm to optimize stability and binding affinity over large sequence spaces. Journal of Computational Biology, 25 (7):726-739, 2018
Gary Parker and Ronald L Rardin. Discrete optimization. Elsevier, 2014.
Thomas Pierrot, Valentin Macé, Felix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Beguir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilber Diversity policy gradient for sample ef- ficient quality-diversity optimization. In ICLR Workshop on Agent Learning in Onen-Endedsess, 2022a.
Thomas Pierrot, Guillaume Richard, Karim Beguir, and Antoine Cully. Multi-objective quality diversity optimization. arXiv preprint arXiv:2202.03055 2022b.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748-8763. PMLR, 2021.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alee Radford, Mark Chen, and Ilya Sutskever. Zero-shot -inage generation. In International Conference Machine Learning, pp. 8821 8831. PMLR, 2021.
Ali Razavi, Aaron Van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with vQ-vae-2. Advances in neural information processing systems, 32, 2019.
Adam J Riesselman, John B Ingraham, and Debora S Marks. Deep generative models of genetic variation capture the effects of mutations. Nature methods, (5(10):81--82) 2018.
Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C Lawrence Zitnick, Jerry Ma, al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences. Proceedings of the National Academy of Sciences, 118(15)e2016233111 2021.
Jason Tyler Rolfe. Discrete variational autoencoders. arXiv preprint vrXiv:1609.022000 2016.
Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
Jacob Schrum, Vanessa Volz, and Sebastian Risi. Cppn2gan: Combining compositional pattern pro- ducing networks and gans for large-scale pattern generation. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 139-147, 2020.
12

---

Under review as a conference paper at ICLR 2023
Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Vassiñs Vassiliades and Jean-Baptiste Mouret. Discovering the elite hypervolume by leveraging in- terspecies correlation. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 149-156, 2018.
Vassilis Vassiliades, Konstantinos Chatzilygeroudis, and lean-Baptiste Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions Evolutionary Computation, 22(4):623-630) 2017.
Frank Wilcoxon. Individual comparisons by ranking methods. In Breakthroughs in statistics, pp- 196-202. Springer, 1992.
13


Reviews:
[{"review_id": "kjVUj9TqQf", "reviewer": "Reviewer_xfZC", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper presents an interesting extension of map-elite algorithm, ME-GIDE, to address the quality-diversity optimization with discrete inputs but differential objective and description functions. The authors evaluate their algorithm on several challenging benchmarks, including protein designs and image generation.", "summary_of_the_review": "I'm not an experts in this area, but I found interesting piece in this paper. However, this paper definitely needs some improvement either in writing or experiments.", "strength_and_weaknesses": "Strength:\n1) the algorithm seems to be a straightforward extension of an existing algorithm framework to make it work for a specific domain.\n2) the authors evaluate the algorithm on many interesting datasets and tasks, and show sizable improvements on these tasks\n\nWeakness:\n1) the paper needs to be re-organized in experiments. For example, a table with the performance of all baseline methods clearly listed will make the reviewers life much easier, than than going into your text to dig these results out ;)\n2) The baseline in experiments are very limited, it seems the author only picks one baseline for each experiment setup. Please correct me if I'm wrong. Please also clarify if there is only 1 baseline exists (which I don't think to be true)\n    a) protein: ME-GIDE V.S. ME-Elite\n    b) ImageNet: ME-GIDE V.S. ImageNet\n3) I also don't get the point of Fig.5. The image generated from ME-GIDE is not intuitive to human but with higher CLIP-score. I believe there are other metrics to be used in together with CLIP in image generation. How are other metrics like? Why ME-GIDE generates some non-sense images to human? I understood your point is using CLIP to measure the diversity. But this seems to me the ME-GIDE lacks a some protection mechanism to guarantee the correctness of optimization. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VjlMG-FrtZ", "reviewer": "Reviewer_MZFX", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper addresses the problem of quality diversity optimization. In short, this problem is to find a set of which maximize some function f(x) where each x in this set is the optimal value in some region of the space of possible x's. The space where these regions are define is typically lower dimensional than the space of x and is chosen by the user. \n\nThis problem has a number of successful solutions in continuous spaces. In discrete spaces, solutions exist but most rely on random search. This paper builds on recent developments in discrete MCMC sampling which notice that many discrete problems are often naturally embedded in continuous spaces and represented by continuous, differentiable function. In such settings the gradients of these functions are often useful for guiding discrete search. This paper applies this idea to quality diversity optimization in discrete spaces through a new local search proposal distribution. \n\nThis new proposal plugs in naturally to existing approaches and leads to improved performance over random search and an alternative gradient-based method. The authors demonstrate this on a diverse set of tasks ranging from protein design to image generation.", "summary_of_the_review": "This work applies recent successful advances from discrete sampling to quality diversity optimization in discrete spaces. The new method plugs in easily with existing approaches and performs well on a diverse set of challenging discrete problems. The method is not particularly novel but the results are compelling and the method is neat and simple. ", "strength_and_weaknesses": "Strengths:\n\nThe paper is clearly written and does a good job to introduce a the reader to the problem of quality diversity optimization (of which I am not an expert). The method is simple and well motivated for the problem at hand and is simple to implement and apply. The results are compelling (in particular the protein results). \n\nWeaknesses:\n\nWhile the presented empirical results are compelling, one is left to wonder when this method will fail. Recent works on discrete MCMC have presented some theory on when those methods will work well and when they won't. These arguments are typically made based on the Lipschitz constant of the model's log-likelihood function. I assume a similar argument could be applied here but I am not as familiar with the nuances of the quality diversity optimization problem to know that for sure. I feel the paper would be greatly strengthened with some (minor) theoretical justification on the settings where this approach is likely to work and when it is not. \n\nAs a non-expert in this exact domain, I left this paper wondering how much the choice of local regions effects the resulting solution. I feel the paper would be strengthened with some discussion of how this should be chosen to optimize performance. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FflvzBtYbmF", "reviewer": "Reviewer_i5mR", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "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": "", "summary_of_the_paper": "To address the quality diversity problem in discrete search spaces, the authors modify the existing algorithm MAP-ELITES to employ gradient information, yielding the ME-GIDE evolutionary algorithm.  They evaluate their method on protein data, MNIST, and ImageNet.\n", "summary_of_the_review": "The paper is far too vague in too many ways to merit publication. \n", "strength_and_weaknesses": "Strengths: \n- Extending gradient-based search to discrete spaces is an important problem.\n\nWeaknesses: \n- The paper is sorely lacking in many details (listed in the \"clarity\" section). \n- Several typos, including but not limited to:\n  - Abstract: Need a comma after \"However\".  Also at other instances of this word, including first line of the second paragraph of Section 1.\n  - Page 2: \"gradient informed\" -> \"gradient-informed\" \n  - Page 2: \"algorithm, discretize\" -> \"algorithm discretize\" \n  - Algorithm 1: \"Adjust T\" -> \"Adjust temperature parameter T\"\n  - Page 3: \"called archive\" -> \"called an archive\" \n  - Page 3 and elsewhere: Change all instances of \"firstly\" to \"first\", \"secondly\" to \"second\", etc.\n  - Page 3 and elsewhere: Add a comma or semicolon at the end of each item in an enumerated list, e.g., \"repertoire (ii)\" -> \"repertoire; (ii)\"\n  - Page 3: Capitalize \"gaussian\".\n  - Page 3: \"(Fontaine & Nikolaidis 2021)\" -> \"Fontaine & Nikolaidis (2021)\"\n  - Page 3: Place a comma after \"(MEGA)\"\n  - Page 3: The period after \"g(z)-g(x)\" should be a comma.\n  - Page 3: You use H for entropy and a Hamming ball.  Change one of these for clarity.\n  - Page 4: Put a comma after \"Formally\".\n  - Page 5: \"human-interpretability\" -> \"human interpretability\"\n  - Page 5: What is a \"degenerated\" distribution? \n  - Page 5 and elsewhere: Put a comma after \"i.e.\" and \"e.g.\"\n  - Page 5: Put \"T\" in math mode to italicize \n  - Page 5: \"amino-acids\" -> \"amino acids\" \n  - Page 5 and elsewhere: Use proper LaTeX quotes, i.e., two back quotes to open and two single quotes to close.  E.g., ``Rat sarcoma virus'' instead of \"Rat sarcoma virus\"\n  - Page 5: Add a space in \".Following\"\n  - Page 5 and elsewhere: Add a comma after \"Finally\"\n  - Page 6: Use math mode for MNIST sizes, i.e., \"28x28\" -> \"$28 \\times 28$\"\n  - Page 6: \"uses\" -> \"use\" after \"Fontaine & Nikolaidis (2021)\"\n  - Page 7: \"fewer iteration\" -> \"fewer iterations\"\n  - Page 7: \"conclusion are\" -> \"conclusions are\"\n  - Page 9: \"popular application\" -> \"popular applications\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4QrO6BkKGy", "reviewer": "Reviewer_uBn2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "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": "", "summary_of_the_paper": "This paper proposes ME-GIDE, an algorithm that aims to find a diverse set of solutions to a black-box function, which is referred as \"Quality Diversity (QD)\" in the paper. ME-GIDE extends existing MAP-ELITES algorithm, which is a genetic algorithm, to handle discrete inputs, by leveraging the gradient information of the function w.r.t the continuous inputs. The extension, known as Gradient Informed Discrete Emitter (GIDE), is straightforward: sampling neighboring solutions of the current discrete solution with the probability (Eqn. 4) that is proportional to the first-order function approximation by gradient at the current solution (Eqn. 2). The evaluation is done in protein folding domains. ", "summary_of_the_review": "Overall the paper requires substantial work and I vote for rejection. ", "strength_and_weaknesses": "Strength\n1. The paper is straightforward\n\nWeakness\n1. The core idea (sampling nearby solutions according to first-order local function approximation guided by gradient) has been used in numerous works and is not novel at all.\n2. The description of experiments is largely unclear, the significance of the results are unclear. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject