# Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD

arXiv: https://arxiv.org/abs/2112.06007 · HTML: https://mlsanity.com/paper/2112.06007/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 11 Dec 2021.

## Builds on (most cited first, 11 of 11)

- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Monte Carlo with Determinantal Point Processes](https://mlsanity.com/paper/1605.00361/) (2016)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Active Mini-Batch Sampling using Repulsive Point Processes](https://mlsanity.com/paper/1804.02772/) (2018)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [A determinantal point process for column subset selection](https://mlsanity.com/paper/1812.09771/) (2018)
- [Determinantal Point Processes for Mini-Batch Diversification](https://mlsanity.com/paper/1705.00607/) (2017)
- [Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design](https://mlsanity.com/paper/1802.08318/) (2018)
- [Gaussian Determinantal Processes: a new model for directionality in data](https://mlsanity.com/paper/2111.09990/) (2021)
- [Learning from DPPs via Sampling: Beyond HKPV and symmetry](https://mlsanity.com/paper/2007.04287/) (2020)

## Built on by (most cited first, 12 of 12)

- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [Variance Matters: Improving Domain Adaptation via Stratified Sampling](https://mlsanity.com/paper/2512.05226/) (2025)
- [Learning with latent group sparsity via heat flow dynamics on networks](https://mlsanity.com/paper/2201.08326/) (2022)
- [Order Matters: Improving Domain Adaptation by Reordering Data](https://mlsanity.com/paper/2605.05084/) (2026)
- [Policy Gradient with Kernel Quadrature](https://mlsanity.com/paper/2310.14768/) (2023)
- [Bypassing orthogonalization in the quantum DPP sampler](https://mlsanity.com/paper/2503.05906/) (2025)
- [Learning under Latent Group Sparsity via Diffusion on Networks](https://mlsanity.com/paper/2507.15097/) (2025)
- [Fast determinantal sampling on general spaces and diffusion geometry](https://mlsanity.com/paper/2607.06644/) (2026)
- [Variance-reduced Domain Adaptation using Paired Sampling](https://mlsanity.com/paper/2607.20367/) (2026)
- [Online Variance Reduction for Domain Adaptation on Streaming Data](https://mlsanity.com/paper/2607.20374/) (2026)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)
- [Generalized Determinantal Point Processes for Attraction and Repulsion with Distinct Interaction Kernels](https://mlsanity.com/paper/2610.12894/) (2026)

## Abstract (arXiv)

Stochastic gradient descent (SGD) is a cornerstone of machine learning. When the number N of data items is large, SGD relies on constructing an unbiased estimator of the gradient of the empirical risk using a small subset of the original dataset, called a minibatch. Default minibatch construction involves uniformly sampling a subset of the desired size, but alternatives have been explored for variance reduction. In particular, experimental evidence suggests drawing minibatches from determinantal point processes (DPPs), distributions over minibatches that favour diversity among selected items. However, like in recent work on DPPs for coresets, providing a systematic and principled understanding of how and why DPPs help has been difficult. In this work, we contribute an orthogonal polynomial-based DPP paradigm for minibatch sampling in SGD. Our approach leverages the specific data distribution at hand, which endows it with greater sensitivity and power over existing data-agnostic methods. We substantiate our method via a detailed theoretical analysis of its convergence properties, interweaving between the discrete data set and the underlying continuous domain. In particular, we show how specific DPPs and a string of controlled approximations can lead to gradient estimators with a variance that decays faster with the batchsize than under uniform sampling. Coupled with existing finite-time guarantees for SGD on convex objectives, this entails that, DPP minibatches lead to a smaller bound on the mean square approximation error than uniform minibatches. Moreover, our estimators are amenable to a recent algorithm that directly samples linear statistics of DPPs (i.e., the gradient estimator) without sampling the underlying DPP (i.e., the minibatch), thereby reducing computational overhead. We provide detailed synthetic as well as real data experiments to substantiate our theoretical claims.