PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Learning of Determinantal Point Processes with Kernel-Structured Interactions

Takahiro Kawashima, Hideitsu Hino

arXiv:2610.12829v1stat.MLcs.LG

TL;DR

Scaling DPP learning requires kernel structure, but structures such as LR+D trade expressive power against computational cost. KS-DPPs combine nonlinear kernels and latent features with a surrogate-based scalable learning algorithm. On real-world datasets, they improve generalization performance and parameter efficiency.

  • Problem

    DPP learning without structural assumptions requires cubic computational complexity, while structural constraints such as LR+D trade expressive power against computational cost.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    KS-DPPs learn full-rank interactions from item-specific latent features and a nonlinear kernel, using a local surrogate and stochastic optimization for scalable learning.

    Source: §1 · pp. 1–2

  • Results

    Real-world dataset evaluations show that KS-DPPs improve the trade-off, achieving superior generalization performance with parameter efficiency.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    KS-DPPs offer a way to improve the trade-off between expressive power and computational cost while retaining full-rank interactions.

    Source: §1 · pp. 1–2

    Precise and efficient stochastic operations for KS-DPP evaluation, sampling, and mode exploration remain future work.

    Source: §5 · p. 8

Abstract

from arXiv · show

Determinantal point processes (DPPs) on a finite set are probability models that exhibit repulsion where inter-item similarities are encoded by a positive definite kernel matrix. Scaling DPP learning to large datasets typically requires imposing structural constraints on the kernel matrix, such as a low-rank-plus-diagonal form. However, structural assumptions introduce a severe trade-off between expressive power and computational scalability. Our study addresses this challenge by (a) modeling the full-rank interactions via a nonlinear kernel function and latent features, (b) designing a surrogate function for the maximum likelihood estimator, and (c) adopting stochastic optimization using random features of the nonlinear kernel. Numerical experiments on real-world datasets demonstrate that our method significantly improves this trade-off, achieving better generalization performance with remarkable parameter efficiency.

1 INTRODUCTION

DPP learning faces a trade-off: structural constraints improve scalability but can limit expressive power. The paper introduces KS-DPPs, whose nonlinear kernel supports full-rank interactions, and reports improved generalization with parameter efficiency on real-world datasets.

1 INTRODUCTION

  • DPPs model diversity, and their applications include recommendation, search, retrieval, stochastic optimization, and black-box optimization.The introduction also cites associations between diversity and downstream outcomes in Spotify consumption and LLM pre-training data.Source: §1 · p. 1
  • KS-DPPs use item-wise latent features and a nonlinear kernel to represent full-rank interactions with Nd learnable parameters.The introduction contrasts this with LR+D methods, whose off-diagonal interactions are restricted to a rank-r component.Source: §1 · pp. 1–2
  • A local quadratic surrogate and quality-weighted Nyström approximation support learning with linear per-iteration time and a theoretical approximation-bias bound.The method also uses stochastic optimization based on kernel random features.Source: §1 · p. 2
  • KS-DPPs improve the trade-off between generalization performance and computational cost with superior generalization and parameter efficiency on real-world datasets.The evaluations are reported in the introduction as empirical validation.Source: §1 · p. 2

Related Work

  • Earlier full-kernel DPP learning algorithms require cubic complexity, while KS-DPPs use nonlinear structure to retain full-rank interactions with low-dimensional latent features.The kernel function can be chosen to control inductive biases such as smoothness, stationarity, and periodicity.Source: Related Work · p. 2

2 KERNEL-STRUCTURED DPP

DPP learning on large ground sets is computationally costly without kernel structure, while LR+D structure constrains off-diagonal interactions. KS-DPPs instead use item-specific latent features and a nonlinear kernel to model full-rank interactions.

2.1 Determinantal Point Processes

  • The parameter-learning objective is a regularized log-likelihood over observed subsets of the finite ground set.The regularizer is weighted by a positive regularization parameter.Source: §2.1 · pp. 2–3
  • Without kernel structure, exact log-determinants and gradients require O(N^3) operations, while structural constraints such as LR+D trade expressive power against computational cost.An LR+D kernel is full rank, but its off-diagonal interactions are governed by a rank-r component.Source: §2.1 · pp. 2–3

2.2 Parameterization of KS-DPP

  • KS-DPPs parameterize item interactions with a positive definite nonlinear kernel over item-specific latent features and qualities.The latent features are learned jointly with item qualities rather than treated as observed inputs.Source: §2.2 · p. 3
  • Random Fourier features provide an example for shift-invariant kernels, and other valid choices include random binning, random Maclaurin, and random kernel features.The paper assumes regularity conditions on the kernel and its feature map.Source: §2.2 · p. 3
  • The nonlinear kernel induces full-rank interactions from (d−1)-dimensional latent geometry, using Nd learnable parameters.A small positive ε is included to prevent rank degeneracy.Source: §2.2 · p. 3

3 LEARNING KS-DPPS

The section develops a minorization-maximization learning procedure for KS-DPPs, combining local surrogates, random-feature stochastic gradients, and Nyström approximations. It also analyzes the approximation gap and the algorithm’s computational complexity.

3.1 Surrogate Objective

  • A local quadratic minorizer addresses the excessively loose global curvature-bound alternative, which can cause prohibitively slow convergence when ε is typically very small.The local bound is constructed within a trust region around the current iterate.Source: §3.1 · p. 4

3.2 Stochastic Gradient and Kernel Approximation

  • Random features provide unbiased estimates of the kernel and its gradient, while a quality-weighted Nyström approximation caches the frozen normalizer coefficient for inner steps.The approximation creates a non-touching minorizer whose bias remains theoretically controllable.Source: §3.2 · p. 4

3.3 Hybrid Linear Solves

  • For large observed subsets, the method uses a stochastic linear solver; for smaller subsets, it defaults to PCG, while finite Tsolve introduces approximation bias.The stochastic solver is used when |A| ≥ 10^3; otherwise, PCG is used, with typical complexity O(|A|^2).Source: §3.3 · p. 5

3.4 Gap Analysis

  • The surrogate improvement Gt must reach the anchor gap γt to ensure monotonic outer-iteration ascent, and the gap is theoretically controllable and bounded by the squared relative approximation difference.The gap also decays with Nyström rank, although the supplied passage does not give a complete rate.Source: §3.4 · p. 5

3.5 Computational Complexity

  • O(Nd + Bκd) is the overall complexity when Tin and Tsolve are fixed; exact trust-region tests and backtracking are omitted as incompatible with the target complexity.Using PCG replaces κ with κ^2 in the stated complexity.Source: §3.5 · p. 6

4 NUMERICAL EXPERIMENTS

Across MovieLens and Instacart, KS-DPP achieves strong generalization with few latent dimensions, while its computational cost scales more favorably with dimension than LR+D does with rank. The experiments also compare both structures with exact MM and measure how runtime changes with ground-set size.

4.1 Dataset and Configuration

  • The evaluation uses MovieLens and Instacart user histories, with uniformly subsampled training, validation, and test sets of 10,000, 500, and 1,000 observations.LR+D ranks span 4 to 1,024, KS-DPP dimensions span 4 to 32, and ground-set size is swept from 3,000 to the full catalogue.Source: §4.1 · p. 6

4.2 Main Results

  • On both datasets, KS-DPP with d = 8 matches or exceeds LR+D with r = 1,024 in generalization performance.KS-DPP with d = 4 underperforms configurations with d ≥8 on both datasets.Source: §4.2 · p. 6, Figure 1 · p. 7, Figure 2 · p. 7
  • KS-DPP is comparable in MovieLens convergence time to LR+D with r ∈[256, 512], and d = 32 converges faster than LR+D with r = 256 on Instacart.On Instacart, LR+D convergence times are non-monotonic; the authors suggest warm-starting may contribute to this pattern.Source: §4.2 · pp. 6–7

4.3 Comparison with Exact Method

  • For N ≥1,000, KS-DPP surpasses LR+D, although both methods perform slightly below exact MM overall.The comparison evaluates test mean log-likelihoods on MovieLens; LR+D with r = N still does not reach exact MM's final log-likelihoods.Source: §4.3 · p. 7

4.4 Measured Computational Cost

  • Per outer step, KS-DPP cost grows linearly with d, while LR+D per-step cost grows quadratically with r; below N = 30,000, observation-dependent overhead obscures linear scaling in N.KS-DPP's Nyström caching adds a large constant outer-step overhead that is amortized across inner optimization steps.Source: §4.4 · p. 8, Figure 3 · p. 8, Figure 4 · p. 8

5 CONCLUSION

The conclusion presents KS-DPP as a nonlinear-kernel DPP parameterization with latent features and a scalable learning procedure. Experiments on two real-world datasets show an improved trade-off between generalization and learning time, while efficient stochastic operations remain future work.

5 CONCLUSION

  • KS-DPP parameterizes the DPP kernel with (d −1)-dimensional latent features and a nonlinear kernel, capturing full-rank interactions with few parameters.Its learning procedure uses a local quadratic minorizer, a stochastic solver for large linear systems, and a quality-weighted Nyström approximation with a theoretical bias bound.Source: §5 · p. 8
  • On two real-world datasets, KS-DPP improves the trade-off between generalization performance and learning time, particularly as problem size and dataset complexity grow.Source: §5 · p. 8
  • Efficient stochastic operations for KS-DPPs—including evaluation, sampling, and mode exploration—remain future work.Source: §5 · p. 8

A GRADIENT ESTIMATOR AND IMPLEMENTATION DETAILS

The appendix describes random-feature gradient estimation for the surrogate and gives proof details for the anchor-gap bound. Its notation fixes the current parameter at each outer iteration.

A.1 Surrogate Gradient

  • For shift-invariant kernels, the random Fourier feature map is given as the cosine and sine of the projected input, and its feature dimension can be low.The surrogate gradient uses two independent random-feature draws for its quadratic terms.Source: §A.1 · p. 12

B MISSING PROOFS

B.1 Proof of Lemma 3.1

  • The proof of Lemma 3.1 defines the approximation gap using the log-determinant difference and a trace term, with the Nyström residual positive semidefinite.The proof attributes this ordering to the Nyström approximation being induced by an orthogonal projection.Source: §B.1 · p. 13

B.2 Proof of Theorem 3.2

The proof establishes that the expected anchor gap bound also holds for quality-weighted Nyström sampling without replacement. It relates the two sampling schemes through their approximations and residuals.

B.2 Proof of Theorem 3.2

  • The proof constructs a without-replacement sample by drawing an infinite sequence with replacement and retaining the first distinct indices; its conditional probabilities match a Gumbel top-r procedure.Source: §B.2 · p. 15
  • Quality-weighted Nyström sampling without replacement has the same expected anchor-gap bound as the result in Lemma B.1.Source: §B.2 · pp. 13, 15
  • Because the with-replacement sample's distinct indices are contained in the without-replacement set, its Nyström approximation is no larger and its residual is no smaller.The proof uses this residual ordering together with the quadratic anchor-gap bound to transfer the expected bound.Source: §B.2 · p. 15

C.1 Detailed Experimental Settings

This section details the datasets, computational setup, and approximation procedure used for the experiments.

C.1 Detailed Experimental Settings

  • MovieLens contains 87,585 movies, while Instacart contains 49,688 products; ground-set size N was swept across popularity-based subsets.The datasets span over 200,000 users for MovieLens and over 3,000,000 orders from over 200,000 users for Instacart.Source: §C.1 · p. 15
  • KS-DPP gradient estimation used 2 random features for observation-dependent terms and 4 for the normalizing-constant term.Source: §C.1 · p. 15
  • Held-out KS-DPP likelihoods used exact observation-dependent terms and a rank-512 quality-weighted Nyström approximation for fden.Its measured bias was below 1% of the exact value on synthetic data.Source: §C.1 · pp. 15–16
  • The experiments measured the expected anchor gap and the evaluation error of fden.Source: Figure C.1 · p. 16, Figure C.2 · p. 16

C.2 Rank Dependency of Quality-Weighted Nystr¨om Approximation

The appendix reports rank-dependent approximation behavior and an expanded MovieLens comparison with exact MM.

C.2 Rank Dependency of Quality-Weighted Nyström Approximation

  • The synthetic approximation study used Gaussian latent features, a Gaussian kernel, log-normal item qualities, and problem sizes from 3,000 to 30,000.For each problem size, the procedure was repeated 20 times.Source: §C.2 · p. 16
  • The expected anchor gap decays faster than the theoretical O(r^-1) rate in this synthetic setting, with decay largely unaffected by N.The bound depends on the sum of item qualities rather than N directly.Source: §C.2 · p. 16
  • Rank-512 quality-weighted Nyström approximation keeps the relative bias in fden below 1% across all tested N.This supports treating the approximation bias in the held-out KS-DPP evaluations as negligible.Source: §C.2 · p. 16

C.3 Full Result of Comparison with Exact MM

C.4 Measured Computational Cost for Instacart

Instacart measurements examine per-step computational costs as latent dimension, LR+D rank, and ground-set size vary.

C.4 Measured Computational Cost for Instacart

  • The Instacart measurements reused Section 4.4’s fitting functions: quadratic for LR+D and linear for KS-DPP.Source: §C.4 · p. 17
  • KS-DPP outer-step cost remains clearly linear in d, while LR+D cost appears nearly linear in r over the evaluated range.The authors suggest 36-thread parallel matrix calculations may have obscured LR+D’s theoretical O(r^2) behavior.Source: §C.4 · p. 17, Figure C.3 · p. 18
  • Across the evaluated N range, computational cost grows more mildly and flatly than a clear linear increase.Source: §C.4 · p. 17, Figure C.4 · p. 18
Loading 2610.12829v1…