PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Quality Diversity

Matthew C. Fontaine, Stefanos Nikolaidis

arXiv:2106.03894v3cs.AI

TL;DR

Quality diversity seeks high-quality solutions across specified measures, but existing algorithms treat even differentiable objectives and measures as black boxes. The paper formalizes DQD and proposes MEGA algorithms that use gradients to explore objective–measure space; its reported results show significant benchmark gains, with a stated limitation in StyleGAN latent-space search.

  • Problem

    Existing QD algorithms treat objective and measure functions as black boxes, even when differentiable, despite the potential to use their gradients.

    Source: §1 · p. 1

  • Method

    The paper formalizes DQD and proposes MEGA variants that use objective and measure gradients to move through objective–measure space.

    Source: §1 · p. 2, §4 · p. 3

  • Results

    DQD algorithms significantly outperformed baselines in the sphere and Rastrigin domains, CMA-MEGA outperformed other algorithms in the arm domain, and CMA-MEGA without Adam performed poorly in LSI.

    Source: §1 · p. 2, §6.2 · pp. 7–8

  • Takeaways & Limitations

    The authors conclude that gradient arborescences can improve search efficiency when objective and measure functions are differentiable.

    Source: §9 · p. 10

    In LSI, small hyperparameter changes led CMA-MEGA and all QD baselines too far from the StyleGAN latent-space mean, producing artifacts and unrealistic images.

    Source: §9 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Quality diversity seeks high-quality solutions across prespecified measures, but existing QD algorithms ignore gradients even when the objective and measures are differentiable. The paper introduces differentiable quality diversity and MEGA, which uses gradient arborescences to branch through objective–measure space.

1 Introduction

  • QD seeks a range of high-quality solutions that vary across prespecified measures, such as image hair and eye color while matching a text prompt.The example formulates GAN latent-code search around a prompt-matching objective and hair- and eye-color measures.Source: §1 · p. 1
  • Current QD algorithms treat the objective and measure functions as black boxes, although both can be differentiable and provide first-order gradient information.The authors motivate DQD as a way to leverage those gradients to improve computational efficiency.Source: §1 · p. 1
  • A gradient arborescence takes greedy objective-ascending steps while branching via measure functions to encourage exploration.The term emphasizes the directed branching search.Source: §1 · pp. 1–2
  • The authors introduce and formalize differentiable quality diversity, propose OMG-MEGA and CMA-MEGA, and report that DQD algorithms outperform black-box QD methods across three domains.CMA-MEGA also produces diverse, high-quality images in StyleGAN latent-space illumination.Source: §1 · p. 2

2 Problem Definition

The paper defines QD over a continuous parameter space, seeking a solution with maximum objective value for each measure-space location. Since that space may be continuous, MAP-Elites-style methods discretize it into cells and keep one occupant per cell; DQD adds differentiability of the objective and measures.

Quality Diversity

  • For each measure-space location s, QD seeks a parameter vector θ with m(θ) = s that maximizes f(θ).The measure map sends parameters into the joint measure space.Source: §2 · p. 2
  • Because the measure space is continuous, MAP-Elites-family algorithms tessellate it into M cells and maintain one solution per cell.The archive objective is to maximize the objective value for each occupied cell.Source: §2 · p. 2

Differentiable Quality Diversity

  • Differentiable quality diversity (DQD) is QD in which both the objective and measure functions are first-order differentiable.This condition defines the problem setting addressed by the proposed algorithms.Source: §2 · p. 2

3 Preliminaries

The preliminaries contrast MAP-Elites’ archive-based perturbation search with CMA-ME’s adaptive Gaussian sampling and ranking-based updates. These provide the foundations for the paper’s gradient-based methods.

Related work

  • The paper positions MEGA as building on derivative-free QD methods while adding objective and measure gradients to optimization.The preliminaries describe these methods as the state-of-the-art derivative-free QD algorithms considered by the paper.Source: §3 · p. 2

MAP-Elites and MAP-Elites (line)

  • MAP-Elites tessellates measure space, samples archive occupants, and perturbs them with fixed-variance Gaussian noise; Iso+LineDD adds noisy interpolation between two occupants.Candidates enter the archive when they discover a cell or improve its occupant.Source: §3 · p. 3

CMA-ME

  • CMA-ME combines MAP-Elites archiving with CMA-ES adaptation, sampling candidates from a full-rank Gaussian distribution in parameter space.Candidates are ranked by improvement, with new-cell discoveries prioritized, and the distribution is updated from that ranking.Source: §3 · p. 3

4 Algorithms

MEGA adapts gradient-arborescence search to MAP-Elites and CMA-ME. OMG-MEGA branches using measure gradients, while CMA-MEGA adapts coefficient sampling toward improvement in the QD objective.

4 Algorithms

  • MEGA has two variants: OMG-MEGA adapts MAP-Elites, while CMA-MEGA adapts CMA-ME; both use gradient-arborescence search.The paper also introduces objective-gradient MAP-Elites baselines that use objective gradients only.Source: §4 · pp. 3–4

OMG-MEGA

  • OMG-MEGA forms gradient steps from a coefficient-weighted combination of the objective and measure gradients, with coefficients controlling movement through objective–measure space.It samples coefficients from a fixed-variance Gaussian, normalizes gradients, and otherwise follows MAP-Elites.Source: §4 · pp. 3–4

CMA-MEGA

  • CMA-MEGA samples coefficients from an adaptive Gaussian and updates that distribution toward coefficients whose gradient steps improve the QD objective.The coefficient distribution is adapted using CMA-ES rules and CMA-ME’s improvement ranking.Source: §4 · p. 4
  • CMA-MEGA evaluates objective and measure values and gradients, archives new or improved cells, and generates a population of gradient-stepped candidate solutions.The algorithm uses CMA-ES distribution adaptation and restarts from a randomly selected archive solution if the archive does not change.Source: §4 · pp. 4–5
  • CMA-MEGA ranks sampled gradients by improvement, prioritizing new-cell discoveries, then combines them into an ascending step using CMA-ES recombination weights.CMA-ES also adapts its distribution and internal search parameters from the improvement ranking.Source: §4 · p. 4

CMA-MEGA (Adam)

  • An Adam variant of CMA-MEGA replaces its gradient optimization step with an Adam update.Source: §4 · p. 4

5 Domains

The domains test differentiable QD across linear projections, robotic-arm inverse kinematics, and StyleGAN latent-space illumination. Each provides differentiable objective and measure functions for evaluating DQD methods.

Domain Selection

  • DQD benchmark domains are selected from prior QD work where objective and measure gradients can be computed.Differentiability is a requirement of the DQD setting.Source: §5 · p. 5

Linear Projection

  • The linear-projection domain tests adaptive gradient coefficients because reaching measure-space edges requires dynamically shrinking gradient steps.Uniform sampling from a high-dimensional hypercube yields a narrow distribution of linear projections.Source: §5 · pp. 5–6
  • The linear-projection benchmark uses measures formed by linear projections of bounded parameters, with an n = 1000 parameter space and sphere or Rastrigin objectives.Reaching measure-space extremes becomes harder as n increases because every parameter must reach its own extreme.Source: §5 · pp. 5–6

Arm Repertoire

  • The 1000-DOF arm repertoire seeks an inverse-kinematics solution for each reachable end-effector position, minimizing joint-angle variance while measuring x- and y-position.The measures use the planar arm’s forward kinematics.Source: §5 · p. 6

Latent Space Illumination

  • StyleGAN latent-space illumination searches for faces matching an “Elon Musk with short hair” objective while varying red hair and blue eyes.StyleGAN generates images and CLIP evaluates their match to the text prompts.Source: §5 · p. 6

6 Experiments

The experiments compare MEGA variants with derivative-free QD algorithms across benchmark and StyleGAN domains. CMA-MEGA performs strongly across the reported domains, while its results depend on gradient adaptation and optimizer settings.

6.1 Experiment Design

  • The study compares algorithm and domain using normalized QD-score and coverage, with 20 trials per benchmark domain and five for LSI.OMG-MEGA and OG-MAP-Elites were omitted from LSI because computing gradients for every sampled solution made execution cost-prohibitive.Source: §6.1 · pp. 6–7, §6 · p. 6

6.2 Analysis

  • CMA-MEGA and OMG-MEGA significantly outperform every baseline on sphere and Rastrigin, with CMA-MEGA significantly ahead of OMG-MEGA; CMA-MEGA also leads in arm repertoire.Figure 2 plots QD-score over iterations with 95% confidence intervals and shows archive heatmaps for CMA-MEGA (Adam) and the strongest derivative-free competitor.Source: §6.2 · p. 7, Figure 2 · p. 7
  • CMA-MEGA (Adam) significantly outperforms all other algorithms in LSI, while CMA-MEGA without Adam performs worst.The one-way ANOVA found a significant algorithm effect, F(4, 20) = 260.64, p < 0.001.Source: §6.2 · p. 8, Figure 3 · p. 8
  • Gradient-based methods perform well on linearly separable objectives and measures, whereas OG-MAP-Elites finds a near-perfect sphere solution but achieves lower archive coverage.OG-MAP-Elites alternates objective-gradient following with archive exploration.Source: §6.2 · p. 8
  • In the arm domain, OMG-MEGA reaches measure-space extremes but misses nearby cells; CMA-MEGA variants retain the best performance.OG-MAP-Elites variants outperform OMG-MEGA there, as isotropic perturbations can fill regions near top-performing cells.Source: §6.2 · p. 8
  • CMA-MEGA (Adam) and gradient descent show little difference on the first two benchmarks, but non-Adam CMA-MEGA performs poorly in LSI.The authors conjecture this reflects conditioning of the StyleGAN latent-space to CLIP-score mapping.Source: §6.2 · p. 8
  • Overall, gradient information benefits QD search efficiency, but adapting gradient coefficients with CMA-ES is critical for top performance.The LSI archive examples come from a single CMA-MEGA (Adam) run of 10,000 iterations.Source: §6.2 · p. 9

7 Related Work

Related work spans evolutionary and other derivative-free QD methods, QD combined with reinforcement learning, learned archive representations, and latent-space exploration. DQD differs by directly using provided objective and measure gradients.

Quality Diversity

  • QD developed from novelty search and local competition into MAP-Elites, with later work improving archives, variation operators, and selection mechanisms.Derivative-free QD also includes evolution-strategy and Bayesian-optimization approaches.Source: §7 · p. 9
  • QD-RL estimates reward gradients in action space and backpropagates through a neural network, whereas DQD uses provided gradients of objective and measure functions.Some QD-RL approaches also estimate a novelty-function gradient.Source: §7 · p. 9
  • DDE-Elites and PoMS learn representations of archive data, unlike DQD, which directly leverages objective and measure gradients.PoMS uses a decoder-Jacobian-based covariance perturbation to address distortions from explicit manifold mapping.Source: §7 · p. 9

Latent Space Exploration

  • Prior latent-space exploration includes gradient descent, evolutionary methods, and QD-based latent space illumination; this work extends LSI to domains with available gradients.Earlier LSI applications included video-game levels and MNIST digits.Source: §7 · p. 9

8 Societal Impacts

The paper notes possible beneficial and harmful uses of gradient-based generation. It raises model-bias and malicious-use concerns while identifying potential roles for measure selection and DeepFake detection.

Societal Impacts

  • Applying the method to super-resolution image synthesis raises ethical concerns about biases in the trained model.The authors hypothesize that thoughtfully selected measures may help counterbalance bias by specifying diversity across outputs.Source: §8 · pp. 9–10
  • If required diversity is differentiably measurable, DQD could help distinguish bias associated with latent-space organization from limits in model representation.The authors frame this as a potential use, not a demonstrated result.Source: §8 · p. 10
  • The authors recognize malicious uses including DeepFake generation and point to studies that identify DeepFake models as useful.Source: §8 · p. 10

9 Limitations and Future Work

The authors present DQD as a route to more efficient search while identifying conditioning, latent-space, and stochastic-training limits. The appendices document hyperparameter choices, benchmark domains, and implementation.

9 Limitations and Future Work

  • DQD is presented as improving search efficiency, but both MEGA variants are first-order optimizers expected to struggle on highly ill-conditioned problems.CMA-MEGA may have an advantage there because it leverages CMA-ES adaptation mechanisms that approximate curvature information.Source: §9 · p. 10
  • Small hyperparameter changes in latent-space illumination sent CMA-MEGA and all QD baselines too far from the latent-space mean, producing artifacts and unrealistic images.Constraining the search to a hypersphere of radius d, the latent-space dimensionality, is proposed as one possible remedy.Source: §9 · p. 10
  • CLIP classifies visual concepts but does not measure abstract concepts, limiting its use for measures such as a person’s age.The authors identify age as a desired measure with quantitative estimates from images.Source: §9 · p. 10
  • High-variance stochastic objectives and measures conflict with minibatch training, and these challenges must be addressed before DQD training of deep neural networks becomes tractable.The authors suggest deep-network training may be fruitfully reformulated as a QD problem.Source: §9 · p. 10

A Hyperparameter Selection

  • Hyperparameters were manually tuned for the new algorithms, with LSI learning rates kept as large as possible while preserving perceptible differences in the first 10 iterations.Larger LSI learning rates moved the search away from the training distribution and produced unrealistic images; Adam settings followed the StyleGAN+CLIP implementation.Source: A Hyperparameter Selection · p. 14

B Domain Details.

  • In 1,000-dimensional sphere and Rastrigin projections, clipped measures make extremes difficult: OMG-MEGA often overshoots, while CMA-MEGA adapts its gradient steps.The measure contributions are clipped to [−5.12, 5.12], and the constant derivative over that range does not shrink OMG-MEGA’s gradient steps near measure-space extremes.Source: B Domain Details · p. 15
  • Arm-repertoire optima have equal joint angles and zero variance, with reachable end-effector space a radius-n circle; StyleGAN latent codes are 512-dimensional and repeated 18 times.The arm objective uses variance rather than standard deviation so it remains differentiable at zero.Source: B Domain Details · p. 15

C Implementation

  • Archives use 100 × 100 grids for linear-projection and arm domains and 200 × 200 for latent-space illumination; experiments ran 10,000 iterations using Pyribs.The appendix also reports parallel CPU/GPU execution and domain-specific trial runtimes.Source: C Implementation · pp. 16–17

D Improvement Ranking as a Natural Gradient Approximation

The section shows that CMA-ME’s improvement ranking is equivalent to ranking by a modified QD objective, yielding a natural-gradient interpretation. It extends this perspective to CMA-MEGA, which adapts gradient-step coefficients to increase that objective while assuming CMA-ES can handle changes in the optimization landscape.

D Improvement Ranking as a Natural Gradient Approximation

  • CMA-ME’s improvement ranking optimizes a modified QD objective, J2, via a natural-gradient approximation.The interpretation connects CMA-ME’s ranking to CMA-ES’s natural-gradient behavior.Source: D Improvement Ranking as a Natural… · pp. 17–18
  • CMA-ME ranks new-cell discoveries ahead of improvements to occupied cells, avoiding cases where an occupied-cell gain outranks a new-cell solution.The ranking first orders new-cell solutions by objective value, then occupied-cell improvements by their objective-value difference.Source: D Improvement Ranking as a Natural… · p. 17
  • CMA-ME’s improvement ranking is identical to ranking purely by J2.The paper shows that maximizing J2 produces the same ordering as CMA-ME’s improvement-ranking rules.Source: D Improvement Ranking as a Natural… · pp. 17–18
  • CMA-MEGA searches for gradient coefficients that maximize J2 at a fixed solution and archive, rather than updating solution parameters directly.Its CMA-ES sampling distribution adapts the gradient-step coefficients.Source: D Improvement Ranking as a Natural… · p. 18
  • Both CMA-ME and CMA-MEGA assume CMA-ES can handle optimization-landscape changes after archive updates; CMA-MEGA also changes the solution position.For CMA-MEGA, the optimization problem changes as the archive is updated and θ moves.Source: D Improvement Ranking as a Natural… · p. 18

E On the Importance of Normalizing Gradients

The ablation indicates that gradient normalization materially affects OMG-MEGA, with different gradient-scale imbalances shaping the observed behavior in the linear projection and arm repertoire domains. The section also compares sequential and independent gradient and perturbation operators, whose relative performance varies by domain.

E On the Importance of Normalizing Gradients

  • Gradient normalization greatly affects OMG-MEGA performance in the linear projection and arm domains.Table 2 reports the normalized-versus-unnormalized ablation.Source: E On the Importance of Normalizing… · p. 19
  • In the linear projection sphere domain, unnormalized OMG-MEGA fills cells near the optimum but struggles at lower objective values; normalization fills the archive evenly.The quadratic objective’s gradient grows with distance from the optimum and can dominate measure gradients under fixed-distribution coefficients.Source: E On the Importance of Normalizing… · p. 19
  • In the arm repertoire domain, objective gradients average 10^-2 versus 10^2 for measure gradients, so unnormalized OMG-MEGA largely ignores the objective gradient.The authors note that OG-MAP-Elites performs well there, indicating the objective gradient matters for filling the archive.Source: E On the Importance of Normalizing… · p. 20
  • The authors speculate that unnormalized gradients may destabilize CMA-MEGA by making gradient magnitudes conflict with its adaptive step-size control.They leave a thorough evaluation of normalization’s benefits for CMA-MEGA to future work.Source: E On the Importance of Normalizing… · p. 20
  • Normalizing measure gradients lets CMA-MEGA adapt its search distribution toward intermediate measure-space regions, not only the extremes.In QD, intermediate solutions are as important as solutions at the extremes.Source: E On the Importance of Normalizing… · p. 20

F On the Differences between OG-MAP-Elites (line) and PGA-MAP-Elites

  • Exact objective and measure gradients are assumed in DQD, and gradient computation can be more costly than solution evaluation.For neural networks, evaluation can use a forward pass, whereas gradient computation requires backpropagation.Source: F On the Differences between… · p. 20
  • Sequential operators reuse an evaluation and gradient for a gradient step, while independent operators spend a third of the evaluation budget computing gradients.The implementation comparison evaluates whether this operator design affects performance.Source: F On the Differences between… · pp. 20–21
  • Sequential operators outperform independent operators in both linear projection domains, while independent operators outperform them in arm repertoire.The authors conjecture that fewer perturbations hurt in harder-to-explore linear domains, while multiple sequential gradient steps can direct arm-repertoire search toward its elite hypervolume.Source: F On the Differences between… · p. 21

G On the Effect of the Archive Resolution on the Performance of CMA-ME

Archive resolution affects QD-algorithm performance: at 500 × 500, CMA-ME outperforms MAP-Elites variants, whereas coarse archives constrain movement through measure space and increase CMA-ME restarts. Additional experiments report CMA-MEGA outperforming the compared algorithms in two domains, while StyleGAN image comparisons and intermediate outputs reveal a limitation of CLIP-based selection.

G On the Effect of the Archive Resolution on the Performance of CMA-ME

  • At 500 × 500 resolution, CMA-ME outperforms MAP-Elites and MAP-Elites (line) on the linear projection domains.The additional experiments also report that coverage increases for MAP-Elites and CMA-ME at higher resolution, but decreases for MAP-Elites (line).Source: G On the Effect of the Archive… · pp. 21–22, Table 4 · p. 22
  • At 100 × 100 resolution, limited archive granularity hinders movement through measure space and CMA-ME restarts frequently, making it perform similarly to MAP-Elites.The restart rule triggers when none of the λ sampled solutions improves the archive.Source: G On the Effect of the Archive… · p. 22
  • At 500 × 500 resolution, CMA-ME restarts less often and its performance is consistent with the CMA-ME paper.The higher granularity leads sampled solutions to fall into different archive cells.Source: G On the Effect of the Archive… · p. 22

H.1 Generated Archives and Additional Metrics.

  • CMA-MEGA run for 10,000 iterations outperforms each compared algorithm in the linear projection and arm repertoire domains.The additional metrics include QD-score, coverage, and best solution.Source: §H.1 · p. 22
  • CMA-MEGA’s best generated images have quality comparable to images from the Adam baseline using the same prompt and hyperparameters.The comparison used five trials of 10,000 iterations and selected the best objective-scoring archive image per trial.Source: §H.1 · p. 23
  • Some intermediate CMA-MEGA images looked better than final collage images, which the authors interpret as overfitting to the CLIP loss.The cited intermediate images had lower CLIP-assessed quality than the collage images.Source: §H.1 · p. 23

H.2 Additional Experiments in the LSI Domain

Additional StyleGAN+CLIP runs retained CMA-MEGA (Adam)’s top quantitative performance across the experiments, while revealing qualitative artifacts and a limitation of the age proxy measure.

H.2 Additional Experiments in the LSI Domain

  • CMA-MEGA (Adam) retained top quantitative performance against each baseline across the Beyoncé, Jennifer Lopez, and Elon Musk experiments.Table 6 includes the additional Beyoncé and Jennifer Lopez runs alongside the original Elon Musk results.Source: §H.2 · p. 23, Table 6 · p. 28
  • For Beyoncé, only Fig. 14’s collage avoided significant artifacts; CLIP drove other runs far outside the latent Gaussian, overwriting high-quality archive images with low-quality ones.The authors flag that CLIP may perform differently for prompts identifying celebrities of different ethnic backgrounds.Source: §H.2 · pp. 23–24, Figure 14 · p. 28
  • Jennifer Lopez and Elon Musk archive collages were reported to be of similar quality.Figures 14 and 15 show the Beyoncé and Jennifer Lopez collages, respectively.Source: §H.2 · p. 23, Figure 15 · p. 29
  • Beyoncé’s “A small child” measure produced faces of different ages, while Jennifer Lopez’s proxy run missed younger faces later found using “A frowning person.”The authors hypothesize that this reflects using a proxy for age rather than a model that directly measures the abstract concept.Source: §H.2 · p. 24, Figure 16 · p. 29

Related papers

Loading 2106.03894v3…