Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes

Insu Han, Mike Gartrell, Elvis Dohmatob, Amin Karbasi

Introduction

Determinantal Point Processes (DPPs) are elegant probabilistic models widely used in machine learning to select diverse subsets of items, making them highly valuable for recommendation systems, document summarization, and search. Standard DPPs rely on symmetric kernels that capture negative correlations (repulsion) between items. However, Nonsymmetric DPPs (NDPPs) extend this capability by modeling both positive and negative correlations, offering significantly better predictive power for real-world applications.

Despite their modeling advantages, NDPPs come with a massive computational tax. Traditionally, sampling a subset of size $k$ from a ground set of $n$ items (a $k$-NDPP) requires Markov chain Monte Carlo (MCMC) methods where each transition step takes $O(n^2)$ time. When $n$ reaches the millions—a common scenario in modern web applications—this quadratic scaling renders NDPPs completely infeasible.

This paper introduces a scalable MCMC algorithm designed to break this "quadratic wall," reducing the computational complexity of the MCMC transition step from $O(n^2)$ to $O(\log n)$ in the ground set size.

Methodology: Achieving Sublinear Sampling

The researchers achieve this drastic reduction in complexity through three primary technical innovations:

  1. Reformulating the "Up Operator": The core MCMC transition step involves swapping a pair of items. The authors observe that this step is mathematically equivalent to sampling a subset of size 2 from a conditional NDPP.
  2. Efficient Rejection Sampling: To sample this 2-NDPP, the authors employ rejection sampling. They construct a symmetric "proposal" distribution that consistently upper-bounds the nonsymmetric target. By utilizing the Youla decomposition, they build this proposal kernel in $O(d^3)$ time (where $d$ is the rank of the kernel). This is a substantial improvement over previous $O(nd^2)$ approaches.
  3. Tree-Based Acceleration: The algorithm leverages a binary tree structure to store item features. This allows the system to traverse the tree and sample from the proposal distribution in $O(\log n)$ time.

Crucially, the authors prove that the average number of rejections in their algorithm depends solely on the spectral properties of the kernel, remaining entirely independent of the dataset size ($n$) or the rank ($d$).

Experimental Validation

The authors evaluated their algorithm on five real-world datasets spanning recommendation and subset selection tasks:

  • UK Retail: Online gift transactions ($n = 3,941$)
  • Recipe: Ingredients from Food.com ($n = 7,993$)
  • Instacart: Grocery baskets ($n = 49,677$)
  • Million Song: User music playlists ($n = 371,410$)
  • Book: Goodreads book reviews ($n = 1,059,437$)

Key Results

  • Massive Speedups: On the massive Book dataset ($n \approx 1M$), selecting a subset size of $k=50$ using existing exact rejection-based methods was estimated to take millions of seconds. The proposed MCMC method completed the task in roughly 374 seconds.
  • Scalability: As the ground set size $n$ scaled from $10^2$ to $10^6$, the sampling time remained nearly constant (around 10 seconds for $k=10$), empirically validating the $O(\log n)$ logarithmic scaling.
  • Polynomial vs. Exponential: For unconstrained-size NDPPs, previous state-of-the-art methods suffered from runtimes exponential in the rank $d$. This new MCMC approach is polynomial in $d$, making it robust for high-rank kernels.

Key Insights

  • The Power of Low Rank: By assuming the NDPP kernel is low-rank ($d \ll n$), the computational heavy lifting is shifted from the massive ground set to a much smaller latent space.
  • Symmetry as a Bridge: A major breakthrough in this work is using a symmetric DPP as a proposal distribution for a nonsymmetric one. Because symmetric DPPs benefit from mature, fast-sampling libraries (like tree-based methods), this bridge allows the NDPP to inherit those efficiencies.
  • Sublinear is the New Standard: This research provides the first sublinear-time algorithm for $k$-NDPP sampling. Moving from $O(n^2)$ to $O(\log n)$ per step transforms the algorithm from theoretically interesting to practically deployable.

Limitations and Future Directions

While the per-step time is vastly improved, the algorithm does have limitations:

  • Mixing Time: The total number of steps required to converge to the true distribution (the mixing time) remains $O(k^2 \log(1/\epsilon))$. Empirical mixing times appear to increase linearly with $k$, leaving room for future optimization.
  • Preprocessing Cost: The algorithm requires a one-time preprocessing step of $O(nd^2)$ to build the binary tree. While linear in $n$, this could become a bottleneck for extremely large datasets or environments where item features change frequently.
  • Initialization: The mixing time is highly dependent on the starting subset. The authors suggest using greedy MAP inference for initialization, though they acknowledge this remains a heuristic approach.

Summary updated

Abstract

A determinantal point process (DPP) is an elegant model that assigns a probability to every subset of a collection of $n$ items. While conventionally a DPP is parameterized by a symmetric kernel ma...
BibTeX
@inproceedings{han2022scalable,
  author = {Insu Han and Mike Gartrell and Elvis Dohmatob and Amin Karbasi},
  title = {{Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=g1hwLSLz_K},
}
Figure