Diversity-Promoting Sampling with Determinantal Point Processes

This direction is split into other directions: cubic scaling bottleneck (determinantal point process scalability). Its last version stays readable and citable here.

Version 1 of 168 papers74 conceptsfrozen 2026-10-04

In many machine learning tasks, we don't just want the "best" items; we want the best diverse set of items. If you are summarizing a video, picking the five highest-scoring frames might just give you five nearly identical shots of the same scene. If you are pruning a neural network, removing the "weakest" neurons might leave you with a set of highly redundant survivors that fail to capture the full complexity of the data.

Determinantal Point Processes (DPPs) have emerged as the mathematical gold standard for solving this problem. They provide an elegant way to model "repulsion" between points, ensuring that selected subsets are both high-quality and non-redundant.

The Intuition: Diversity as Volume

The core idea behind a DPP is to define the probability of picking a specific subset of items based on the determinant of a similarity matrix.

Imagine each item in your dataset is a vector in a high-dimensional space. If you pick two items that are very similar, their vectors will point in roughly the same direction. If you pick items that are diverse, their vectors will be spread out. Mathematically, the determinant of a matrix formed by these vectors represents the squared volume of the parallelepiped they span.

As Jack Parker-Holder, Aldo Pacchiano, and Krzysztof Marcin Choromanski demonstrate in Effective Diversity in Population Based Reinforcement Learning, maximizing this volume forces a population of agents to explore different parts of a behavioral manifold, preventing the "crowding" effect where all agents converge on the same sub-optimal strategy.

The Scalability Wall

Despite their elegance, DPPs face a notorious "scalability wall." Standard operations—like calculating the likelihood of a set or sampling a new subset—require eigendecompositions or matrix inversions. These operations typically scale at $O(N^3)$, where $N$ is the number of items in the ground set.

As noted by Zelda Mariet and Suvrit Sra in Kronecker Determinantal Point Processes, this cubic complexity makes exact DPPs impractical for large-scale datasets like gene databases or massive product catalogs. Much of the recent research in this field focuses on breaking this $O(N^3)$ bottleneck.

Strategies for Scaling Diversity

To make diversity practical, researchers have developed several approximation and acceleration techniques:

  1. Low-Rank Approximations: In Nystrom Approximation for Large-Scale Determinantal Processes, Raja Hafiz Affandi and Alex Kulesza show that we can use Nyström methods to approximate the kernel matrix. This reduces the complexity from $O(N^3)$ to something closer to $O(Nk^2)$, where $k$ is the rank of the approximation.
  2. Coresets: Chengtao Li, Stefanie Jegelka, and Suvrit Sra introduced CoreDPP in Efficient Sampling for k-Determinantal Point Processes. This method uses "coresets" to prune the dataset down to a small, representative subset before sampling, making the sampling speed independent of the total number of items $N$.
  3. Fast MCMC Sampling: Instead of exact sampling, researchers use Markov Chain Monte Carlo (MCMC) methods. In Fast Sampling for Strongly Rayleigh Measures with Application to Determinantal Point Processes, the authors propose a "projection chain" that mixes in polynomial time, allowing for diverse selection even in high-dimensional spaces where traditional methods stall.

Applications Across the Spectrum

The ability to sample diverse subsets efficiently has transformed several subfields of AI:

By moving from independent sampling to determinant-based repulsive sampling, these methods ensure that every data point, neuron, or agent added to a system provides unique, non-redundant information.

Papers in this version

Showing 60 of 68 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_diversity_promoting_sampling_with_determ_f414507d,
  title = {Diversity-Promoting Sampling with Determinantal Point Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diversity-promoting-sampling-with-determinantal-point-processes/rdr_f414507de1a9430d832bd34c6ea9e61c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_diversity_promoting_sampling_with_determ_f414507d_v1,
  title = {Diversity-Promoting Sampling with Determinantal Point Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diversity-promoting-sampling-with-determinantal-point-processes/rdr_f414507de1a9430d832bd34c6ea9e61c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}