When selecting a subset of data from a large pool, we often face a trade-off between quality and redundancy. If we sample points purely based on individual merit, we risk selecting highly similar items that provide no new information.
Determinantal Point Processes (DPPs) offer an elegant mathematical solution to this problem. A DPP is a probabilistic model over subsets of items that naturally penalizes redundancy. The probability of selecting a specific subset $Y$ is proportional to the determinant of a kernel matrix $K$ restricted to the items in $Y$:
$$P(Y) \propto \det(K_Y)$$
Geometrically, this determinant represents the squared volume of the parallelotope spanned by the feature vectors of the items in $Y$. If two items are highly similar (i.e., nearly collinear), the volume collapses toward zero, making the subset highly unlikely to be sampled. This property makes DPPs incredibly powerful for tasks requiring diversity, such as selecting landmark points in manifold learning, choosing experimental designs, or managing experience replay buffers in reinforcement learning.
Despite their elegance, DPPs have historically suffered from a severe computational bottleneck. Standard exact sampling algorithms require computing the eigendecomposition of the full kernel matrix, an operation that scales cubically with the number of items ($O(n^3)$). For modern large-scale datasets, this cost is prohibitive.
To resolve this, a major research direction has emerged focused on scaling DPP sampling. By combining clever matrix decompositions, rejection sampling frameworks, and sequential thinning strategies, recent algorithms have successfully bypassed the cubic bottleneck, reducing the complexity of diverse subset selection to quadratic or even linear time.
Rejection Sampling via Leverage Scores
One of the most powerful ways to avoid evaluating a complex joint distribution is to use rejection sampling. The core idea is to find a simpler, cheaper "proposal" distribution that over-approximates the target distribution, draw candidates from it, and then selectively thin them out.
In the context of DPPs, an ideal proposal distribution can be constructed using statistical leverage scores. The leverage score of a data point measures its isolated importance or uniqueness relative to the rest of the dataset. Crucially, leverage scores can be computed or approximated much faster than a full determinantal distribution.
As shown by Simon Barthelmé et al. in A Faster Sampler for Discrete Determinantal Point Processes, using independent proposals calibrated by leverage scores allows for exact DPP sampling while shifting the computational bottleneck away from the sampling step entirely. Instead of performing a global matrix decomposition up front, the algorithm draws a candidate pool using the leverage scores and uses a rejection step to correct for the joint diversity requirements. This reduces the sampling complexity from $O(nm^2)$ to $O(nm + m^3 \log m)$, where $m$ is the target subset size.
Similarly, Michal Derezinski et al. leverage this insight in Leveraged volume sampling for linear regression. They introduce determinantal rejection sampling to efficiently draw subsets proportional to their volume, making the runtime largely independent of the total dataset size after an initial preprocessing step.
Bypassing Eigendecomposition via Sequential Thinning
An alternative to global proposal distributions is to build the diverse subset sequentially, point by point. However, standard sequential sampling requires updating conditional probabilities at every step, which traditionally demands repeated, expensive matrix inversions.
To circumvent this, Claire Launay et al. developed an exact algorithm in Exact sampling of determinantal point processes without eigendecomposition based on sequential thinning. The process unfolds in two stages:
- Dominating Process: The algorithm first samples a larger pool of candidates using a simple, independent Bernoulli point process. This process is designed to "dominate" the target DPP, meaning it acts as a loose envelope containing more points than needed but requiring negligible computation to generate.
- Sequential Thinning: The algorithm iterates through this candidate pool, deciding whether to keep or discard each point based on explicit formulas for DPP marginals and conditional probabilities.
The key algorithmic innovation that makes this fast is the use of rank-1 updates to a Cholesky decomposition to compute the conditional probabilities. Instead of recomputing the determinant of the kernel matrix from scratch when a point is considered, the algorithm updates an existing Cholesky factor. This avoids eigendecomposition entirely and reduces the cost of conditional updates to quadratic time.
[ Full Dataset ]
│
▼ (Fast Bernoulli Sampling)
[ Dominating Candidate Pool ]
│
▼ (Sequential Thinning via Rank-1 Cholesky Updates)
[ Final Diverse DPP Subset ]
This synergy of Cholesky updates and rejection sampling is highly versatile. For instance, Kaiyan Zhao et al. integrated this exact approach into deep reinforcement learning in Efficient Diversity-based Experience Replay for Deep Reinforcement Learning. By utilizing Cholesky-backed rejection sampling, their framework (EDER) filters out redundant trajectories from experience replay buffers in quadratic time, allowing agents to maintain diverse memories without bottlenecking the training loop.
Low-Rank and Regularized Decompositions
When datasets are high-dimensional, we can achieve further acceleration by exploiting the underlying structural properties of the kernel matrix. Many practical applications use a "regularized" variant of DPPs, which balances the diversity penalty with a prior or regularization term.
In Bayesian experimental design using regularized determinantal point processes, Michal Derezinski et al. demonstrate that a regularized DPP can be mathematically decomposed into two distinct components: a low-rank DPP component and a set of independent Bernoulli trials.
This structural insight provides a massive computational shortcut. Instead of evaluating the full-rank matrix, the sampling complexity scales linearly with the number of candidate items, depending only on the "effective dimension" of the data rather than the full feature dimension. This makes high-dimensional subset selection tractable for massive experimental design problems.
On a foundational level, this aligns with the theoretical framework implemented in libraries like DPPy, where Guillaume Gautier et al. note in DPPy: DPP Sampling with Python that any DPP can be decomposed into a mixture of simpler projection DPPs. By breaking a complex process down into these elementary projection components, sampling becomes a matter of selecting a component and drawing from a geometric projection, bypassing brute-force determinant calculations.
Applications and Downstream Impact
The ability to sample from DPPs efficiently has unlocked new capabilities across several machine learning domains:
- Unbiased Linear Regression: Standard mini-batching or random sampling in linear regression often introduces statistical bias relative to the true population optimum. In Correcting the bias in least squares regression with volume-rescaled sampling and Unbiased estimators for random design regression, Michal Derezinski et al. prove that augmenting an i.i.d. sample with points chosen via "volume-rescaled sampling" completely eliminates this bias. Thanks to low-precision determinantal rejection sampling and distortion-free intermediate sampling, this unbiased estimator can be computed with near-linear time complexity relative to the dataset size.
- Scalable Manifold Learning: Selecting representative "landmark" points on large graphs or non-Euclidean spaces is computationally heavy. Christian Wachinger et al. show in Sampling from Determinantal Point Processes for Scalable Manifold Learning that by restricting DPP updates to local neighborhoods, the complexity drops to $O(ndk)$, making rigorous diversity-based landmark selection practical for large-scale manifold visualization and classification.
- Monte Carlo Integration: In On two ways to use determinantal point processes for Monte Carlo integration, Guillaume Gautier et al. develop an efficient sampler for the multivariate Jacobi ensemble DPP. This allows researchers to deploy DPPs to optimize numerical integration at scales that were previously impossible, achieving perfect integration when the underlying integrand is sparse.
By shifting from naive $O(n^3)$ matrix operations to localized updates, low-rank decompositions, and leverage-score-driven rejection frameworks, these works have collectively transformed DPPs from a theoretical luxury into a scalable, practical toolkit for diversity-aware machine learning.
Key Foundational Work
Leveraged volume sampling for linear regression (2018) — contributed 2 concept elements to this direction.
Sampling from Determinantal Point Processes for Scalable Manifold Learning (2015) — contributed 1 concept elements to this direction.