Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD
Authors: Rémi Bardenet
Subhroshekhar Ghosh
Meixia LIN
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: determinantal point processes
variance reduction
stochastic gradient descent
orthogonal polynomials

Abstract: 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), tractable 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 determinantal point process paradigm for performing 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, for a large enough batchsize and a fixed budget of item-level gradients to evaluate, 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.

Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD
Rémi Bardenet'
Université de Lille, CNRS, Centrale Lille
UMR 9189 CRIStAL, F-59000 Lille, France
remi www.eeetttuiii-lliiiiieieeeee
Subhroshekhar Ghosh"
National University of Singapore, Department of Mathematics 10 Lower Kent Ridge Road, 1 19076, Singapore subhrowork0gmail com
Meixia Lin't
National University of Singapore, Institute of Operations Research and Analytics 10 Lower Kent Ridge Road, 1 19076,, Singapore Hin_meixia@e nus edu
Abstract
Stochastic gradient descent (SGD) is a cornerstone of machine learning. When the number N of data items is large, SGD relies constructing unbiased estimator of the gradient of the empirical risk using a small subset of the original dataset, called minibatch. Default minibatch construction involves uniformly sampling subset of the desired size, but alternatives have been explored for variance reduction. In particular, experimental evidence suggests drawing minibatches from determi- nantal point processes (DPPs), tractable distributions over minibatches that favour diversity among selected items. However, like in recent work DPPs for coresets, providing systematic and principled understanding of how and why DPPs help has been difficult. this work, we contribute an orthogonal polynomial determinantal point process paradigm for performing minibatch sampling in SGD. Our approach leverages the specific data distribution hand, which endows with greater sensitivity and power over existing data-agnostic methods. We substantiate our method via detailed theoretical analysis of convergence properties, inter- weaving between the discrete data set and the underlying continuous domain. In particular, we show how specific DPPs and string controlled approximations can lead to gradient estimators with variance that decays faster with the batchsize than under uniform sampling. Coupled with existing finite-time guarantees for SGD convex objectives, this entails that, for large enough batchsize and fixed budget of item-level gradients to evaluate, DPP minibatches lead to smaller bound the mean square approximation eπrоr than uniform minibatches. Moreover, our estimators are amenable to 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 well real data experiments substantiate theoretical claims.
Alphabetical order Conresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Introduction
Consider minimizing an empirical loss
N Σ 0),, + X(0), ==1
min GEG
(I)
N
with some penalty θ + R+, Many learning tasks, such regression and classification,
are usually framed that way [1]. When N >> 1, computing the gradient of the objective in (I) becomes a bottleneck, even if individual gradients VgL(z,, 0) are cheap evaluate. For a fixed computational budget, it is thus tempting to replace vanilla gradient descent by more iterations but using an approximate gradient, obtained using only a few data points. Stochastic gradient descent (SGD; [2]) follows this template. In its simplest form, SGD builds an unbiased estimator at each iteration of gradient descent, independently from past iterations, using a minibatch of random samples from the data set. Theory [3] and practice suggest that the variance of the gradient estimators in SGD should be kept as small as possible. thus natural that variance reduction for SGD has been a rich area of research; see for instance the detailed references in [4, Section 2].
In a related vein, determinantal point processes (DPPs) are probability distributions over subsets of a (typically large or infinite) ground set that are known to yield samples made of collectively diverse items, while being tractable both in terms of sampling and inference. Originally introduced in electronic optics [5], they have been turned into generic statistical models for repulsion in spatial statistics [6] and machine learning [7, 8]. ML, DPPs have also been shown to be efficient sampling tools; see Section 2. Importantly for us, there is experimental evidence that minibatches in (1) drawn from DPPs and other repulsive point processes can yield gradient estimators with low variance for advanced learning tasks [4, 9]. though a conclusive theoretical result has remained elusive. In particular, it is hard to see the right candidate DPP when, unlike linear regression, the objective function does not necessarily have geometric interpretation.
Our contributions are as follows. We combine continuous DPPs based on orthogonal polynomials [10] and kernel density estimators built on the data to obtain two gradient estimators; see Section 3. We prove that their variance is Op-p-(1-1/d) where is the size of the minibatch, d is the dimension of data; Section 4. This provides theoretical backing to the claim that DPPs yield variance reduction [4] over, say, uniformly sampling without replacement. In passing, the combination of analytic tools -orthogonal polynomials-, and an essentially discrete subsampling task -minibatch sampling- sheds light on new ways to build discrete DPPs for subsampling. Finally, we demonstrate our theoretical results on simulated data in Section 5.
A cornerstone of our approach is to utilise orthogonal polynomials to construct our sampling paradigm, interweaving between the discrete set of data points and the continuum in which the orthogonal polynomials reside. A few words are in order regarding the motivation for our choice of techniques. Roughly speaking, would like to use a DPP that is tailored to the data distribution hand. Orthogonal Polynomial Ensembles (OPEs) provide a natural way of associating a DPP to a given measure (in this case, the probability distribution of the data points), along with substantive body of mathematical literature and tools that can be summoned as per necessity. This makes it a natural choice for our purposes.
Notation. Let data be denoted by D = (zi,..., nN). and assume that the z;'s are drawn i.i.d. from a distribution 7 on Rd Assume y is compactly supported, with support D c [-1, 11d bounded away from the border of [-1, 1]d. Assume also that 7 is continuous with respect to the Lebesgue measure, and that its density is bounded away from zero on its support. While our assumptions exclude learning problems with discrete labels, such as classification, we later give experimental support that our estimators yield variance reduction in that case too. We define the empirical measure âN := N-1, Σ 5z,, where dz, is the delta measure at the point 2; E Rd Clearly, AN 7 in P(RR);; under our operating assumption of compact support, this amounts to convergence in P(D).
For simplicity, we assume that no penalty is used in (1), but our results will extend straightforwardly We denote the gradient of the empirical loss by EN = Ex(0) == N-1 ΣN VoL(z, A). minibatch is a (random) subset A C [N] of size A = p < N such that the random variable
E = =x
Σ w; VoL(z, 0),

---

for suitable weights (wx)), provides good approximation for En.
2 Background and relevant literature
Stochastic gradient descent. Going back [2], SGD has been a major workhorse for machine learning; see e.g. [1, Chapter 14]. The basic version of the algorithm, applied to the empirical risk minimization (1), is to repeatedly update
0ct1 + 02 - (O.)),,, E N,
(3)
where 7/ is (typically decreasing) stepsize, and E is minibatch- estimator (2) of the gradient of the empirical risk function (1), possibly depending on past iterations. Most theoretical analyses assume that for any 0, (0) in the 1-th update (3) unbiased, conditionally on the history of the Markov chain (0,) so far. For simplicity, we henceforth make the assumption that Ex does not depend on the past of the chain. In particular, using such unbiased gradients, one can derive nonasymptoti bound [3] on the mean square distance of 8, to the minimizer of (1), for strongly convex and smooth loss functions like linear regression and logistic regression with &2 penalization. More precisely, for T oc t and 0 < a < 1, [3, Theorem 1] yields
0 - 0 s f(1) (E100- - 0. 0.112 -0.12+ T.
x²)
+
C t0
(4)
where C, L >
is the trace of the covariance matrix of the gradient estimator, evaluated at the optimizer 9. of (1). The initialization bias is thus forgotten subexponentially fast, while the asymptotically leading term is proportional to o² /ta_ Combined with practical insight that variance reduction for gradients is key, theoretical results like (4) have motivated methodological research on efficient gradient estimators [4, Section 2], i.e., constructing minibatches so minimize o². In particular, repulsive point processes such as determinantal point processes have been empirically demonstrated to yield variance reduction and overall better performance on MI. tasks [4, 9]. Our paper is stab at a theoretical analysis to support these experimental claims.
are problem-dependent constants, f(t) - O(e and 0² o2= (0.)
The Poissonian benchmark. The default approach to sample minibatch A C [N] is to sample p data points from D uniformly, with or without replacement, and take my = 1/p constant in (2). Both sampling with without replacement lead to unbiased gradient estimators. A similar third approach is Poissonian random sampling. This simply consists in starting from A = 0, and independently adding each element of D the minibatch with probability p/N. The Poisson estimator P is then (2), with constant weights again equal to 1/p. When p < N, which is the regime of SGD, the cardinality of A is tightly concentrated around p. and E, has the same fluctuations as the two default estimators, while being easier to analyze. In particular, BE [] = Ey and Var [ = Op(p-)(p)))))))) see Appendix $1 for details.
DPPs as (sub)sampling algorithms. As distributions over subsets of large ground set that favour diversity, DPPs are intuitively good candidates at subsampling tasks, and one of their primary applications in ML has been summary extractors [7]. Since then, DPPs or mixtures thereof have been used, e.g., to generate experimental designs for linear regression, leading to strong theoretical guarantees [11, 12, 13]; see also [14] for survey of DPPs in randomized numerical algebra, or [15] for feature selection in linear regression with DPPs.
When the objective function of the task has less structure than linear regression, it has been more difficult to prove that finite DPPs significantly improve over i.idd sampling. For coreset construction, for instance, [16] manages to prove that projection DPP necessarily improves over i...d sampling with the same marginals [16, Corollary 3.7]. but the authors stress the disappointing fact that current concentration results for strongly Rayleigh measures (such as DPPs) do not allow yet to prove that DPP coresets need significantly fewer points than their i.i.d. counterparts [16, Section 3.2). Even closer to motivation, DPPs for minibatch sampling have shown promising experimental performance [4], but reading between the lines of the proof of [4, Theorem 1], a bad choice of DPP can even yield larger variance than i.i.d. sampling!
For such unstructured problems (compared to, say, linear regression) as coreset extraction or loss- agnostic minibatch sampling, we propose to draw inspiration from work on continuous DPPs,
3

---

where faster-than-ii.d. error decays have been proven in similar contexts. For instance, orthogonal polynomial theory motivated [10] to introduce particular DPP, called a multivariate orthogonal polynomial ensemble, and prove faster-than-i.i.d central limit theorem for Monte Carlo integration of smooth functions. While resorting to continuous tools to study a discrete problem such as minibatch sampling may be unexpected, we shall see that the assumption that the size of the dataset is large compared to the ambient dimension crucially allows to transfer variance reduction arguments.
3 DPPs, and two gradient estimators
Since we shall need both discrete and continuous DPPs, we assume that is either TR: or D, and follow [17] in introducing DPPs in abstract way that encompasses both cases. After that, propose two gradient estimators for SGD that build on a partieular family of continuous DPPs introduced in [10] for Monte Carlo integration, called multivariate orthogonal polynomial ensembles.
3.1 DPPs: The kernel machine of point processes
point process on X' distribution on finite subsets S of X: see [18] for general reference. Given reference measure μ X, a point process is said to be determinantal (DPP) if there exists a function K X' X the kernel of the DPP, such that, for every 1,
= -Jan f(1 M(a1...... v.) Det K(x,, m2) "
E E
du Rn (II,...,,..)
(5)
1,6=1
for every bounded Borel function f 2 - R. where the sum in the LHS of (5) ranges over all pairwise distinct n-uplets of the random finite subset S. A few remarks are in order. First, satisfying (5) for every is strong constraint K, so that not every kernel yields DPP, A set of sufficient conditions on K is given by the Macchi-Son Soschi--ossnikov theorem [5, 19). In words, if K(x,, y) = K(y, x), and if K further corresponds
integral operator
f + K(x, (()))d())))
I (x,,
that is trace-class with spectrum in [0, I]. then the corresponding DPP exists. Second, note in (5) that the kernel of a DPP encodes how the points the random configurations interact. strong point in favour of DPPs is that, unlike most interacting point processes, sampling and inference are tractable [17, 6]. Third, (5) yields simple formulas for the mean and variance of linear statistics of a DPP.
Proposition 1 (See e.g. [20, 21J). Let S ~ DPP(K, μ) and & X - R be a bounded Borel function,
E Σ
(o))) (a,,))1,
LSS
= /ʃ [x)x) - (v)) ( K(x, (((())))))))
Var
Σ ((x)
LES
+ / [0(0))1 ((x,z)) -
- / |K(x, ()). (d( dp(x).
(7)
Since the seminal paper [7], the case X' = D has been the most common in machine learning. Taking μ to be îN. any kernel is given by its restriction to D. usually given subset of size p of D, and & the indicator of yields P(A S) N -DetttK A. This is the usual way finite DPPs are introduced [7], except maybe for the factor P finite setting, careful implementation of the general DPP sampler of [17] yields m DPP samples of average cardinality Tr(K) in O(N + mTNT((K))) operations [22].
N x N matrix
K = Kl Equation (6) with n = p.
P, which comes from using fNN as the reference measure instead of N In this
We now go back to a general X' and fix E N. A canonical way to construct DPPs generating configurations of p points almost surely, i.e. orthonormal functions ou...., 0p-1 in L2 (H), and take for kernel
{a1...., ", the following. Consider p
p-1
K(x,g)
Σ (x))))(())
(8)
k=U

---

In this setting, the (permutation invariant) random variables 21,...,22 with joint distribution
P
Det K( XZ
I dy
p!
generate a DPP (x1,..., Fpp with kernel (x,, v), called projection DPP. For further information on determinantal point processes, we refer the reader [17, 7].
3.2 Multivariate orthogonal polynomial ensembles
This section paraphrases [10] in their definition of a particular projection DPP on X R4 called multivariate orthogonal polynomial ensemble (OPE). Fix some reference measure ((r))dz on [-1, 1]4 and assume that it puts positive mass some open subset of [-1, 1]d. Now choose ordering of the monomial functions (z1...., Fd) + 21 ... Fd Od. in this work we use the graded lexical order. Then apply the Gram-Schmidt algorithm (²(g(z) to these ordered monomials. This yields a sequence of orthonormal polynomial functions (Øx kek) the multivariate orthonormal polynomials w.r.t. q. Finally, plugging the first multivariate orthonormal polynomials Φu...., 0p-1 into the projection kernel (8), we obtain a projection DPP with kernel denoted K.") referred as the multivariate OPE associated with the measure ((r)dz.
3.3
Our first estimator: reweight, restrict, and saturate an OPE kernel
Let h >> 0 and
N Σ
2;
7(z)
(10)
Nha
be a banlwdbbandwidth kernel density estimator of the pdf of the data-generating distribution y [23, Section 4.2], particular, & is chosen so that f k(x)dr= = 1. Note that the approximation kernel
k is unrelated to any DPP kernel in this paper. Let now q(x) = 4i (21). ... qa(xa) be separable pdf on [-1, 1jd, where each g; is Nevai-class Let K!"" be the multivariate OPE kernel defined in Section 3.2, and form new kernel
((()) {xx
g(v)
K 9.5 (z. = V
K (z, V
7(y)
The form of K is reminiscent of importance sampling [24], which is no accident. Indeed, while the positive semidefinite matrix
K 9.5
K (21, 23) 9.5
(11)
ISiJEN
necessarily the kernel matrix of DPP on (f1....,N) N), fNN), see Section 3.1, we built be close to a projection of rank More precisely,
N
[ k(P) (2k, y) k 9.7 (v) =
((xx)
((2n)
7 (zt)
Σ n=1
(z,, 2.) (2n, (1,m,,,) z1)
k())
{(x))
N
((n))
(zz)
If N is large compared to p and d, that in particular 7 Re y, the term within brackets will be close to ʃ k(() (zx, =) (2, 2))g(=)dz = (p) (*k, 21), so that K k((p)
9.5 D is almost projection in (f(N
Let us actually consider the orthogonal projection matrix K with the same eigenvectors as K 9.5 2 but with the p largest eigenvalues replaced by 1, and the rest of the spectrum set O. By the Macchi-Soshnine theorem, K is the kernel matrix of DPP; see Section 3.1. We thus consider minibatch ~ DPP(K). Coming from a projection DPP, |A| p almost surely, and we define the gradient estimator
VoL(z,, K;
EAPPP
(12)
TEA
Seee [10, Section for details. It suffices that each qi is positive on 1-,
5

---

In Section 4, we shall prove that DAPDPP is unbiased, and examine under what assumptions its variance decreases faster than L/p.
On the computational cost of EA.DP The bottleneck is computing the p largest eigenvalues of matrix (11), along with the corresponding eigenvectors. This can be done once before running SGD, as a preprocessing step. Note that storing the kernel in diagonalized form only requires (NNp) storage. Each iteration of SGD then only requires sampling a rank-p projection DPP with diagonalized kernel, which takes (NNp²) elementary operations [22]. In practice, as the complexity of the model underlying 2, + VZ(2 8) increases, the cost of computing p individual gradients shall outweigh this (NNp²) overhead. For instance, learning the parameters of a structured model like conditional random field leads to arbitrarily costly individual gradients, as the underlying graph gets more dense [25]. Alternately, (12) can be sampled directly, without sampling the underlying DPP. Indeed the Laplace transform of (12) is a Fredholm determinant, and shown [26] that Nyström-type approximations of that determinant, followed by Laplace inversion, yield an accurate inverse CDF sampler.
Finally, we stress the unusual way in which our finite DPP kernel K is constructed, through reweighted continuous OPE kemel,, restricted to the actual dataset. This construction is interesting per se, as it is key leveraging analytic techniques from the continuous case in Section
3.4 Our second estimator: sample the OPE, but smooth the gradient
In Section 3.3, we smoothed the empirical distribution of the data and restricted continuous kernel to the dataset
make sure that the drawn minibatch would be subset of D. But one could actually
define another gradient estimator, directly from an OPE sample A = ={ [w1,.... wp} ~ (PP(K))) g)-
Note that in that case, the "generalized minibatch" A C [-1, 1] is not necessarily a subset of the dataset D. Defining kernel density estimator of the gradient,
VoL(2,0) Nha
VoL(z,,0) k
2 2i
we consider the estimator
V JoL(w,
EAs
Σ
MyEA ((w) K. (wy, w,)
On the computational cost of A.... Since each evaluation of this estimator is at least as costly as evaluating the actual gradient (x)),, its use is mostly theoretical: the analysis of the fluctuations of EA. is easier than that of EADDPT, while requiring the same key steps. Moreover, the computation of all pairwise distances A..s could be efficiently approximated, possibly using random projection arguments [27], so that the limited scope of E might be overcome in future work. Note also that, like E.DPP, inverse Laplace sampling [26] applies to A.s.
Analysis of determinantal sampling of SGD gradients
We first analyze the bias, and then the fluctuations, of the gradient estimators introduced in Section 3. By Proposition with 4 = VoL(-,0). comes
N
D / VoL(z, 0)
k(t) (2
(ddin())
VoL(z,,0)
= N
so that we immediatly get the following result.
Proposition 2. E(EA,Drr/2 [D] Ex-
Thus, EA,PP unbiased, like the classical Poissonian benchmark in Section 2. However, the
smoothed estimator EA,s from Section 3.4 is slightly biased. Note that while the results of [3], like (4), do not apply to biased estimators, SGD can be analyzed in the small-bias setting [28].
Proposition 3. Assume that in (10) has compact support and g is bounded on D. Then E(E,, = EN + Ophh/N)

---

Proof. Using the first part of Proposition again, it comes
vol(w,.0) 0)
B
ANDPP(K! 2
Σ
WEEA [K (wy, 20,)
VaL(w,
VoL(zi, 0)k (2T dw
K(P)
(2o, wu)
(p) ( w)
-
Nha
- Σ N
(
dw VoL(z., 0)
1 N
Σ VoL(zz 0) Oppph/NN), (13)
where, in the last step, have used the fact that h-d, (h- 2,)) is probability density. The Or(ph/N) error arises because we integrate that pdf D rather than Skpp(k). But since a compactly supported kernel, for points 2; that are within a distance O(h) from the boundary of D, we incur error of (1).). By Proposition 1, the expected number of such points 2; is J.. K. (w, w))(t)) dw,, where D2 is the h-neighbourhooo of the boundary of D. By a classical
asymptotic result of Totik, see [10, Theorem 4.8), w + K.P²) (w. w) is (pp) on Dy; whereas is bounded density, implying that Jr, ((w) ddw ((Vol O(h). Putting together all of these, we obtain the (phh/N) error term in (13).
The rest of this section devoted the more involved task of analyzing the fluctuations of DPP and EA.-- For the purposes of our analysis, we discuss certain desirable regularity behaviour for our kernels and loss functions in Section 4.1. Then, we tackle the main ideas behind the study of the fluctuations of our estimators in Section 4.2. Details can be found in Appendix S3.
4.1 Some regularity phenomena
Assume that ( K2 (2, is bounded the domain D uniformly in N (note that p
possibly depends on N). Furthermore, assume that z + (p-1. K(P) ()x=))())- 7(=) is I-Lipschitz, with Lipschitz constant Op(1) and bounded in 0.
Such properties are natural in the context of various known asymptotic phenomena, in particular asymptotic results on OPE kernels and the convergence of the KDE 7 to the distribution The detailed discussion deferred Appendix S2; we record here in passing that the above asymptotic phenomena imply that
VoL(z,0) ((() (z, (2)))((2)
d
7(2) VoL(2,0) - (2)) II /1 21p
(14)
Our desired regularity properties may therefore be understood in terms of closeness to this limit, which itself has similar regularity. At the price of these assumptions, we can use analytic tools to derive fluctuations for A. by working on the limit in (14). For the fluctuation analysis of the smoothed estimator EA,s: we similarly assume that (g(w)) K.(" (wo, - w. 0) is (p(1) and 1 1-Lipschitz with an (p(1) Lipschitz constant that is bounded in 0. These are once again motivated by the convergence of (g(ur) k<(p)( (w, -Vo 0) VoL(w, 0) Vi w p..
4.2 Reduced fluctuations for determinantal samplers
For succinctness of presentation, we focus on the theoretical analysis of the smoothed estimator EA,s: leaving the analysis of AAPPP to Appendix S3, while still capturing the main ideas of our approach.
Proposition 4. Under the assumptions in Section 4.1. Var(EA, [D] Op(p Op(p-(1+1/4) (1+1/4)).

---

Proof Sketch. Invoking (7) in the case of projection kemel,,
Var 11 //
VoL(2,0)
VoL(w, 0)
( w) w)){d(())d((()))
{(2)K( (7) (z,z)
( (P) (w, w)
2
VoL(2,0) 0)
VoL(w, 0)
q (2. ())d(()))
p² ((2) k (2,z)
g(2r) 1 Kg (w, w)
1 SMa- 17 / / || |2=- w12 | (z, w) 2 (d)())))(())
(15)
where we used the 1-Lipschitzianity of v.C.2)) with Ma - (p() the Lipschitz constant. (x)), (x,z2)
We control the integral in (15) by invoking the renowned
formula for the OPE kernel k.P) [29]. For clarity of presentation, we outline here the main ideas for d = 1; the details for general dimensions are available in Appendix S3. Broadly speaking, since K!() is an orthogonal projection of rank in Lg(g), we may observe that ff [K]") (z, ())<d(())dd((())) - p; so that without the || 2|12 term in (15), we would have Or(p-1) behaviour in total, which would be similar to the Poissonian estimator. However, it turns out that the leading order contribution to J || 2 |K(') (z, w) (z)(()) comes from near the diagonal 2 w, and this turns out to be neutralised in an extremely precise manner by the | w factor that vanishes on the diagonal.
This neutralisation is systematically captured by the Christoffel-Darbout formula [29]. which implies K(P) q (x, y) (r - y) A AAp (0,())),-1(0) - 0,, (1)))))-)
where A, = (1) and Φ 9--1 two orthonormal functions in L2(g). Substituting this into (15), a simple computation shows that ls | 212 | (z, ()) variance bound Var[EA,,|)] = Or(p~>), 2), which is the desired rate for d = 1. For general d, we use
(()). This leads to
the fact that 9 8 2 gs is product measure, and apply the Christoffel-Darborr formula for each Gs. leading to a variance bound of Var(Ex, = Op(p (p(p-(1+1/d) as desired.
The theoretical analysis of Var(EA.DPP/2) follows the broad contours of the argument for Var|EA.s| [] as above, with additional difficulties introduced by the spectral truncation from K {(2) to
9.9
K; see Section 3. This is addressed by an elaborate spectral approximation analysis in Appendix $3. In combination with the ideas expounded in the proof of Proposition 4, our analysis in Appendix $3 indicates a fluctuation bound of Var[E = Or(p -(1+1/)))
Experiments
In this section, we compare the empirical performance and the variance decay of our gradient estimator EAPPPP to the default EA,Poi. We do not to include EA,s. whose interest is mostly theoretical; see Section 4. Moreover, while we focus simulated data to illustrate our theoretical analysis, we provide experimental results on a real dataset in Appendix S4. Throughout this section, the pdf introduced in Section 3.2 is taken to be (ww) x II (1 + wbil)==(1 w & with ag. 33 [-1/2, 1/2] tuned to match the first two moments of the jth marginal of nN All DPPs are sampled using the Python package DPPy [30], which is under MIT licence.
Experimental setup. We consider the ERM setting (1) for linear regression Cin y). = (z5 0) y)² and logistic regression Cig y). 0) log[L + exp(-y(x, 0))] both with an additional &e penalty X(0) (An/2) [0 Here the features are x E [[-1, and the labels are, respectively. E [-1, and E {-1, 1}. Note that our proofs currently assume that the law y of = (a, y) is continuous w.r.t. Lebesgue, which in all rigour excludes logistic regression. However, we demonstrate below that if we draw a minibatch using our DPP but on features only, and then deterministically associate each label to the drawn features, we observe the same gains for logistic regression as for linear regression, where the DPP kernel takes into account both features and labels.
8

---

For each experiment, we generate N = 1000 data points 2; with either the uniform distribution or mixture of well-separated Gaussian distributions on |-1, -111]]=1. The variable y E E is generated as (Ii, Qmee) + Es, where Quve E Rd-1 1 is given, and IR' is white Gaussian noise vector. In the linear regression case, we scale by |l to make sure that yi E [-1,1]. In the logistic regression case, we replace each yt by its sign. The regularization parameter A is manually set to be 0.1 and the stepsize for the f-th iteration is set 1/t".9, so that (4) applies. In each experiment, performance metries are averaged over 1000 independent runs of each SGD variant.
Performance evaluation of sampling strategies in SGD. Figure summarizes the experimental results of Po and EPP with p and p = 10. The top row shows how the norm of the complete gradient || [8,)] decreases with the number of individual gradient evaluations x p. called here budget. The bottom row shows the decrease of ||0, - Note that using / p on all x-axes allows comparing different batchsizes. Error bars on the bottom row are +: one standard deviation of the mean. In all experiments, using DPP consistently improves the performance of Poisson minibatches of the same size, and the DPP with batchsize 5 sometimes even outperforms Poisson sampling with batchsize 10, showing that smaller but more diverse batches can be better way of spending fixed number of gradient evaluations. This is particularly true for mixture data (middle column), where forcing diversity with our DPP brings the biggest improvement. Maybe less intuitively, the gains for the logistic regression in d = 11 (last column) are also significant, while the case of discrete labels is not covered yet by our theoretical analysis, and the moderately large dimension makes the improvement in the decay rate of the variance minor. This indicates that there is variance reduction beyond the change of the rate.
10-1.
narm of gradient
idd_p5
1016 of gradient
1
lid_ kd_p5 iid_p10
gr gradieett
lid,
idd_p10
10-2
10-2
[d__p10
dpp_e5
dpp _pp_55
19 9x
dpp_p5
dpp_p10
10-2
Spp_p10
8 10-2
dpp. ipp_p10
10-2
7 10-2
10-3
6x
10-3
2000
4000
2000
4000
D
2000
4000
b budget
budget
budget
d
in: uniform
(b) L Lim. mixture
(c) d 11, L Lags uniform
iid_ps
0.05
iid _
0.6
ps
iid p10
0.06
dpp_p5
iid_p10
2 0.04
lid _o_
dpp_ps _pp_p
0.5-
dpp_p5
0.04
dpp_p10
0.03
dpp_pl0
|6c
dpp_p10
0.02
0.4
0.01
1000 2000 3000 4000
1000
3000 budget
4000
1000 2000 3000 4000
budget
budget
(d) d = 3, C = Cin. uniform
(e) d = 3, Lin, mixture
(f) d = 11, C Log. uniform
Figure I: Summary of the performance of two sampling strategies in SGD.
Variance decay. For a given dimension d, we want to infer the rate of decay of the variance σ² = (0=)3())) to confirm the Op(p (1+1/d)) rate discussed in Section 4. We take L = Lim as an example, with = 1000 i.i.d. samples D from the uniform distribution on [-1, For d = 1, we show in Figure 2 the sample variance of 1000 realizations of the variance of | (0.)ll² (white dots) and |[EA.PP((..) dots indicate standard 95% marginal confidence intervals, for indication only. The slope found by maximum likelihood in a linear regression in the log-log scale is indicated as legend. The experiment confirms that a² is smaller for the DPP, decays as p 11-1/d 1/d and that this decay starts at a batchsize p that increases with dimension.
(black dots), conditionally on D. Blue and red

---

MLEE slope 1.39
varaacce
10"2
variante
10-3
variance
10-3
10-3
-2000
10-1
MLE slopem-154
10
4 x 10
10
10
10
10
batch size
batch
batch
(a) d =1
(b) = 2
(c) d = 3
Figure 2: Summary of the variance decay results.
6
Discussion
In this work, we introduced an orthogonal polynomial-based DPP paradigm for sampling minibatches in SGD that entails variance reduction in the resulting gradient estimator. We substantiated our proposal by detailed theoretical analysis and numerical experiments. Our work raises natural questions and leaves avenues for improvement in several directions. These include the smoothed estimator EA.s. which calls for further investigation in order to be deployed procedure; improvement the dimension dependence of the fluctuation exponent when the gradients smooth enough, like [31, 32] did for [10]; sharpening of the regularity hypotheses for theoretical investigations to obtain a more streamlined analysis. While our estimators were motivated by continuous underlying data distribution, in situations like logistic regression, where the data is at least partially discrete. Extensions to account for discrete settings in a principled manner, via discrete OPEs otherwise, would be natural topic for future research. Another natural problem is to compare our approach with other, non-i.i.d., approaches for minibatch sampling. A case point is the method of importance sampling, where the independence across data points suggests that the variance should still be Op (1/p) as in uniform sampling. More generally, incorporating ingredients from other sampling paradigms to further enhance the variance reducing capacity of our approach would be of considerable interest. Finally, while our results already partly apply to more sophisticated gradient estimators like Polyak- Rupert averaged gradients [3, Section 4.2]. it would be interesting to introduce repulsiveness across consecutive SGD) iterations to further minimize the variance of averaged estimators. summary, we believe that the ideas put forward in the present work will motivate new perspective improved minibatch sampling for SGD, more generally on estimators based on linear statisties (e.g. in coreset sampling), and beyond.
computationally attractive
experiments suggest notably good performance
Acknowledgments and Disclosure of Funding
RB acknowledges support from ERC grant BLACKIACK (ERC-2019-STG-851166 and ANR AI chair BACCARAT (ANR-20-CHIAA-000)) S.G. was supported in part by the MOE grants R-146-000- 250-133 and R- R-146-000-312-114,
References
[1] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[2] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[3] É. Moulines and Bach. Non- Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 24, pages 451-459, 2011.
[4] C. Zhang, Kjellstrom, and Mandt. Determinantal point processes for mini-batch diversifi- cation. In Uncertainty in Artificial Intelligence (UAI), 2017.
10

---

[5] O. Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7:83-122, 122, 1975.
[6] Lavancier, Møller, and E. Rubak. Determinantal point process models and statistical inference. Journal of the Royal Statistical Society, Series B, 2014.
[7] A. Kulesza and B. Taskar. Determinantal Point Processes for Machine Learning, volume 5 of Foundations and Trends in Machine Learning. Now Publishers Inc., 2012.
[8] Subhroshekhar Ghosh and Philippe Rigollet. Gaussian determinantal processes: new model for directionality in data. Proceedings of the National Academy of Sciences, 117(24):13007 13213. 2020.
[9] C. Zhang, H. Kjellstrom, and S. Mandt. Active mini-batch sampling using repulsive point processes, In Proceedings of the AAAI conference on Artificial Intelligence, 2019.
[10] R. Bardenet and A. Hardy. Monte Carlo with determinantal point processes. Annals of Applied Probability, 2020.
[11] A. Nikolov, M. Singh, and U. T. Tantipongpipat. Proportional volume sampling and approxima- tion algorithms for a-optimal design. arXiv:1802.083/ 2018.
[12] M. Derezinski and M. K. Warmuth. Unbiased estimates for linear regression via volume sampling. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2017.
[13] A. Poinas and R. Bardenet. On proportional volume sampling for experimental design in general spaces. arXiv preprint arXiv:2011.0455 2020.
[14] M. Derezinski and M. W. Mahoney. Determinantal point processes in randomized numerical linear algebra. Notices of the American Mathematical Society, 68(1), 2021.
[15] A. Belhadji, R. Bardenet, and P. Chainais. A determinantal point process for column subset selection. Journal of Machine Learning Research (JMLR). 2020.
[16] N. Tremblay, S. Barthelmé, and P.-O. Amblard. Determinantal point processes for coresets. Journal of Machine Learning Research, 20(168):1-70, 2019.
[17] J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág. Determinantal processes and independence. Probability surveys, 2006.
[18] D. Daley and D. Vere-Jones An Introduction the Theory of Point Processes, volume 1. Springer, 2nd edition, 2003.
[19] A. Soshnikov.
Determinantal random point fields. Russian Mathematical Surveys, 55:923-975.
2000.
[20] A. Soshnikov. Gaussian limit for determinantal random point fields. Annals of Probability, 30(1):171-177, 2002.
[21] S. Ghosh. Determinantal processes and completeness of random exponentials: the critical case. Probability Theory and Related Fields, 163(3):643 665, 2015.
[22] J. A. Gillenwater. Approximate inference for determinantal point processes. PhD thesis, University of Pennsylvania, 2014.
[23] M. P. Wand and M. C. Jones. Kernel smoothing. CRC press, 1994.
[24] C. P. Robert and G. Casella. Monte Carlo statistical methods. Springer, 2004.
[25] S. V. N. Vishwanathan, training of conditional random fields with stochastic gradient methods. In Proceedings of the international conference on machine learning (ICML), pages 969-976, 2006.
Schraudolph, M. W. Schmidt, and P. Murphy, Accelerated
[26) R. Bardenet and Ghosh. Learning from DPPs via Sampling: Beyond HKPV and symmetry. arXiv preprint 2012:22007.04487,22222

---

[27] S. S. Vempala. The random projection method, volume 65. American Mathematical Society, 2005.
[28] A. Benveniste, M. Métivier, and Priouret. Adaptive algorithms and stochastic approximations. Springer Science & Business Media, 1990.
[29] B. Simon. The christoffel- kernel. In Perspectives in PDE, Harmonic Analysis and Applications, volume 79 of Proceedings of Symposia in Pure Mathematics, pages 295-335, 2008.
[30] G. Gautier, R. Bardenet, G. Polito, and M. Valko. DPPy: Sampling determinantal point processes with Python. Journal of Machine Learning Research; Open Source Software (JMLR MLOSS), 2019.
[31] A. Belhadji, R. Bardenet, and Chainais. Kernel quadrature with determinantal point processes. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[32] A. Belhadji, R. Bardenet, and P. Chainais. Kernel interpolation with continuous volume sampling. International Conference on Machine Learning (ICML), 2020.
12


Reviews:
[{"review_id": "ssPLZZ7f40C", "reviewer": "Reviewer_PADH", "summary": "The authors introduce the first complete theoretical analysis of minibatch sampling using determinantal point processes in the context of (batched) stochastic gradient descent.\n\nThe core of this analysis is built upon continuous DPP results (specifically, on orthogonal polynomial ensembles, or OPEs) in which it has been shown that DPPs achieve faster-than-iid error decay. Assuming knowledge of a KDE $\\tilde \\gamma$ for the distribution over data points, the authors introduce two batched estimators of the full gradient:\n1) A weighted sum of gradients at points sampled by a DPP with kernel $K$, where $K$ is build by restricting the eigenvalues of an OPE kernel reweighted by $\\tilde \\gamma$. This kernel (and associated DPP) can be computed and sampled from efficiently.\n2) An estimator of more theoretical nature, which can sample batches of points that do not arise in the actual data, and is as least as costly in practice as estimating the full gradient.\n\nThe authors then prove that the first estimator is unbiased, and obtain a bound on the bias of the second. They then also show that the variance of the resulting estimator decays at a rate $\\le p^{-(1 + \\frac1d)}$, where $p$ is an integer parameter controlling the number of polynomials used to build the OPE and $d$ is the dimensionality of the input data.\n\nFinally, the authors show on synthetic data that the resulting samplers improve the empirical convergence speed of SGD as a function of the number of required gradient evaluations, and confirm empirically the theoretical variance decay rate obtained earlier.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper is original, and combines a novel analysis with previous results on OPE DPPs and empirical analysis of DPP sampling. This paper provides the first complete analysis of the variance decay of gradient approximations using DPP batched sampling, a question which has been the focus of several works in the past (which are cited).\n\nQuality: This paper is of high quality, well positioned within the relevant literature, and introduces results of extreme relevance to the machine learning community.\n\nClarity: This paper is very clearly written, despite the complexity of the topic. The authors provide proof sketches that are sufficient to build an intuition for the proofs themselves, carefully tie in their work with previous results, and are upfront about the requirements and limitations of their methods. Their empirical analysis is also careful to include a comparison based on the number of gradient evaluations, an important distinction in this type of analysis.\n\nSignificance: This paper is of high significance. The question of using DPPs and other negatively dependent measures to improve convergence rates of batched SGD has been raised several times in previous work by the community, and this paper provides the first theoretical analysis of DPP sampling for minibatch SGD.\n\nI would've liked to see a comparison to importance sampling.\n\nQuestions & clarifications\n- Related work using DPPs and/or importance sampling to sample minibatches has also looked at building distributions over the data that are dependent on the gradients of the model at the current iteration. Do your results preclude this as a promising direction, are they independent, or could both approaches be combined in the future?\n\n- Section 2: you state the assumption that $\\Xi_A$ does not depend on the past of the Markov chain. Under this assumption, does this mean that individual gradients aren't affected by the past of the chain (in the sense that, in practice, the points that were sampled in a previous round of SGD change the model, and as such affect future gradients)?\n\n- I would recommend adding a complexity analysis of the use of the first estimator, including sampling costs (additional to the $\\mathcal O(Np^2)$ operations required to build the a rank-$p$ projection DPP. I also believe that readers will be interested in some empirical numbers of the runtime of SGD with the DPP batch sampler as a function of $p$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "o3z3jNpkiq", "reviewer": "Reviewer_KigW", "summary": "The authors introduce a sampling minibatches method in SGD based on determinantal point processes (DPPs) to reduce the estimation variance. Specifically, the authors proposed two gradient estimators using multivariate orthogonal polynomial ensembles, and provide theoretical results on the bias and the variance of the estimators. One of the two proposed estimators is tested on a synthetic dataset.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The studied problem of reducing SGD estimator variance is very interesting and important. As far as I understand, the proposed method based on DPPs is reasonable and the associated theoretical guarantees are novel. I have the following questions.\n\n1.\tIt will be better to present the variance result of the first estimator in the main text. Since this estimator is the one that can be used in practice (the experiment section only has results from this estimator). It is not clear to me whether this estimator has the same variance as the second one. \n2.\tThe experiment considers the budget in terms of the number of gradient evaluations. However the cost of each gradient evaluation is different for different methods. Could the authors compare in terms of the runtime? I wonder how much cost the proposed gradient estimator will add to each evaluation. \n3.\tAs the authors mentioned in the relevant literature, there are existing DPPs-based gradient estimators. How will the proposed estimator compare to other DPPs-based estimators empirically? The current experiment only includes Poisson minibatches as the baseline.\n\nIn conclusion, I think the proposed method is technically sound and could have a potential impact, but it needs some clarification on the theoretical result and improvement on the empirical results. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not contain this part.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SmXeLZNHUA3", "reviewer": "Reviewer_7px8", "summary": "This paper presents a framework for variance reduction in stochastic gradient descent (SGD) that involves detrimental point processes (DPPs) based on orthogonal polynomials.  This framework uses a class of continuous DPPs based on orthogonal polynomials, and kernel density estimators built from the data, to perform minibatch sampling in SGD.  Theoretical analysis of this approach proves a bound on the variance for two gradient estimators, leading to variance reduction compared to uniform minibatch sampling without replacement.  This approach is empirically validated using experiments performed on synthetic simulated data. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The minibatch sampling approach presented in this paper appears to be novel and technically sound, and the paper is reasonably well written.  The main theoretical result involving the bound on the gradient variance appears to be significant and will likely serve as a solid basis for future work in this area.  This does indeed seem to be one of the first theoretical results regarding the variance reduction that results from DPP-based minibatch sampling.  The sketch of the proof for Proposition 4 (the main theoretical contribution, regarding the variance bound) in Section 4.2 is reasonably clear.  However, this proof involves a fair amount of technical complexity and background, and I did not fully check the proof.\n\nA few aspects of this paper could be improved.  First, while the presentation of DPPs based on orthogonal polynomials, called multivariate orthogonal polynomial ensembles (OPEs), is reasonably clear, the motivation behind the choice of OPEs in this approach is not very clear.  It would be helpful for the authors to add a discussion regarding why OPEs are useful for variance reduction, and the intuition behind OPEs, to the beginning of the paper.  Second, experimental results on a real dataset are found only in the appendix.  It would be better to include these real-dataset results in the main paper, along with a discussion regarding the relative differences in the extent of variance reduction as compared to the simulated data.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have included a short, but adequate, discussion of the limitations of their work in Section 6 of the paper.  Since this work involves very general algorithmic and theoretical contributions, a discussion of potential negative societal impact does not appear to be applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "A9MBYwEDr3u", "reviewer": "Reviewer_mkKg", "summary": "This paper studies unbiased estimators of SGD minibatch via DPP with orthogonal polynomials. The estimator can be constructed by sampling DPP whose kernel consists of the orthogonal projection of some kernel proposition. Samples from the projection DPP are guaranteed fixed sizes (corresponds to the rank) and the variance of minibatch SGD can be achieved by O(p^{-(1 + 1/d)}) for batch size p and feature dimension d. This is smaller than the uniform batch sampling with O(p^{-1}) which leads us that DPP can play a role of variance reduction. Empirical results on both synthetic and real-world datasets show the superior performance of DPP sampling than uniform one in terms of the norm of gradients, distance to the optimal solution as well as the variance of gradient estimations.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "DPPs have been used for minibatch selection in SGD as a variance reduction. This work proposes a careful analysis of unbiased estimator of minibatch SGD based on DPP with an orthogonal polynomial. It is interesting that feature dimension d actually matters the variance of estimators rather than distribution of data points. However, if the data distribution is uniform then it seems that DPP sampling is equivalent to uniform sampling. In this case, it is still unclear that Proposition 4 still holds. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although DPPs can be good at reducing the variance of gradient estimators, their computations have always been critical issues and many works have tried to resolve them. More precisely, the proposed method can reduce the variance O(p^{-1/d}) time better than uniform sampling, but the time to sample mini-batches from a DPP is O(N*p^2) in general. Hence, in terms of computational time, DPP may have no advantage over uniform sampling.\n\nThese days, machine learning models have become more complex (likely to be deep architecture) and outperform linear models. However, the proposed method seems valid for linear models. Does it have a chance to extend more complex models, e.g., deep architectures?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a convincing theoretical analysis of a technique for minibatch sampling using determinantal point processes, showing that it can lead to variance decaying more rapidly compared with uniform sampling. The result formalizes and refines a commonly felt intuition, and is compelling, significant, and a great fit for NeurIPS. After author feedback, all reviewers favored acceptance.
Decision: Accept (Spotlight)