text:
\section{Introduction}
\label{s:introduction}
Consider minimizing an empirical loss
\begin{equation}
\label{e:ERM}
\min_{\theta\in\Theta} \ \frac{1}{N} \cdot \sum_{i=1}^N \mathcal{L}(\bm{z}_i,\theta) + \lambda(\theta),
\end{equation}
with some penalty $\lambda:\Theta\mapsto \mathbb{R}_+$.
Many learning tasks, such as regression and classification, are usually framed that way \cite{ShBe14}. When $N\gg 1$, computing the gradient of the objective in \eqref{e:ERM} becomes a bottleneck, even if individual gradients $\nabla_\theta \mathcal{L}(\bm{z}_i,\theta)$ are cheap to 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; \cite{RoMo51}) 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 \cite{BaMo11} and practice suggest that the variance of the gradient estimators in SGD should be kept as small as possible. It is thus natural that variance reduction for SGD has been a rich area of research; see for instance the detailed references in \cite[Section 2]{ZhKjMa17}.

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 \cite{Mac75}, they have been turned into generic statistical models for repulsion in spatial statistics \cite{LaMoRu14} and machine learning \cite{KuTa12,ghosh2020gaussian}. In ML, DPPs have also been shown to be efficient sampling tools; see Section~\ref{s:related_work}. Importantly for us, there is experimental evidence that minibatches in \eqref{e:ERM} drawn from DPPs and other repulsive point processes can yield gradient estimators with low variance for advanced learning tasks \cite{ZhKjMa17,ZhKjMa19}, 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 a geometric interpretation.

Our contributions are as follows. We combine continuous DPPs based on orthogonal polynomials \cite{BaHa20} and kernel density estimators built on the data to obtain two gradient estimators; see Section~\ref{s:estimator}. We prove that their variance is $\mathcal{O}_P (p^{-(1+1/d)})$, where $p$ is the size of the minibatch, $d$ is the dimension of data; see Section~\ref{s:theory}. This provides theoretical backing to the claim that DPPs yield variance reduction \cite{ZhKjMa17} 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~\ref{s:experiments}.

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, we would like to use a DPP that is tailored to the data distribution at 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 a substantive body of mathematical literature and tools that can be summoned as per necessity. This makes it a natural choice for our purposes.

\paragraph{Notation.} Let data be denoted by $\mathfrak{D}:=\{\bm{z}_1,\ldots,\bm{z}_N\}$, and assume that the $\bm{z}_i$'s are drawn i.i.d. from a distribution $\gamma$ on $\mathbb{R}^d$. Assume $\gamma$ is compactly supported, with support $\mathcal D\subset [-1,1]^d$ bounded away from the border of $[-1,1]^d$. Assume also that $\gamma$ 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 \textit{empirical measure}
$
\hat{\gamma}_N := N^{-1} \cdot \sum_{i=1}^N \delta_{\bm{z}_i},
$
where  $\delta_{\bm{z}_i}$ is the delta measure at the point $\bm{z}_i \in \mathbb{R}^d$. Clearly, $\hat{\gamma}_N \to \gamma$ in $\mathcal{P}(\mathbb{R}^d)$; under our operating assumption of compact support, this amounts to convergence in $\mathcal{P}(\mathcal D)$.

For simplicity, we assume that no penalty is used in \eqref{e:ERM}, but our results will extend straightforwardly. We denote the gradient of the empirical loss by
$\Xi_N = \Xi_N(\theta) :=  N^{-1} \cdot \sum_{i=1}^N \nabla_\theta \mathcal{L}(\bm{z}_i,\theta)$. A minibatch is a (random) subset $A \subset [N]$ of size $\vert A\vert=p\ll N$ such that the random variable
\begin{equation} \label{eq:linstat-loss}
\Xi_A = \Xi_A(\theta):= \sum_{i \in A} w_i \nabla_\theta \mathcal{L}(\bm{z}_i,\theta),
\end{equation}
for suitable weights $(w_i)$, provides a good approximation for $\Xi_N$.

\section{Background and relevant literature}
\label{s:related_work}
\paragraph{Stochastic gradient descent.}
Going back to \cite{RoMo51}, SGD has been a major workhorse for machine learning; see e.g. \cite[Chapter 14]{ShBe14}. The basic version of the algorithm, applied to the empirical risk minimization \eqref{e:ERM}, is to repeatedly update
\begin{equation}
\theta_{t+1} \leftarrow \theta_t - \eta_t\Xi_A(\theta_t), \quad t\in\mathbb{N},
\label{e:SGD_update}
\end{equation}
where $\eta_t$ is a (typically decreasing) stepsize, and $\Xi_A$ is a minibatch-based estimator \eqref{eq:linstat-loss} of the gradient of the empirical risk function \eqref{e:ERM}, possibly depending on past iterations. Most theoretical analyses assume that for any $\theta$, $\Xi_A(\theta)$ in the $t$-th update \eqref{e:SGD_update} is unbiased, conditionally on the history of the Markov chain $(\theta_t)$ so far. For simplicity, we henceforth make the assumption that $\Xi_A$ does not depend on the past of the chain. In particular, using such unbiased gradients, one can derive a nonasymptotic bound \cite{BaMo11} on the mean square distance of $\theta_t$ to the minimizer of \eqref{e:ERM}, for strongly convex and smooth loss functions like linear regression and logistic regression with $\ell_2$ penalization. More precisely, for $\eta_t \propto t^{-\alpha}$ and $0<\alpha<1$, \cite[Theorem 1]{BaMo11} yields
\begin{equation}
\label{e:bach_moulines}
\mathbb E \Vert \theta_t-\theta_\star\Vert^2 \leq f(t) \left(\mathbb E \Vert \theta_0-\theta_\star\Vert^2 + \frac{\sigma^2}{L}\right) + C \frac{\sigma^2}{t^\alpha},
\end{equation}
where $C, L>0$ are problem-dependent constants, $f(t) = \mathcal{O}(e^{-t^\alpha})$, and $\sigma^2 = \mathbb E [\Vert\Xi_A(\theta_\star)\Vert^2\vert\mathfrak{D}]$ is the trace of the covariance matrix of the gradient estimator, evaluated at the optimizer $\theta_\star$ of \eqref{e:ERM}.
The initialization bias is thus forgotten subexponentially fast, while the asymptotically leading term is proportional to $\sigma^2/t^{\alpha}$. Combined with practical insight that variance reduction for gradients is key, theoretical results like \eqref{e:bach_moulines} have motivated methodological research on efficient gradient estimators \cite[Section 2]{ZhKjMa17}, i.e., constructing minibatches so as to minimize $\sigma^2$. In particular, repulsive point processes such as determinantal point processes have been empirically demonstrated to yield variance reduction and overall better performance on ML tasks \cite{ZhKjMa17,ZhKjMa19}.
Our paper is a stab at a theoretical analysis to support these experimental claims.

\paragraph{The Poissonian benchmark.}
The default approach to sample a minibatch $A \subset [N]$ is to sample $p$ data points from $\mathfrak D$ uniformly, with or without replacement, and take $w_i=1/p$ constant in \eqref{eq:linstat-loss}.
Both sampling with or without replacement lead to unbiased gradient estimators.
A similar third approach is Poissonian random sampling. This simply consists in starting from $A=\emptyset$, and independently adding each element of $\mathfrak D$ to the minibatch $A$ with probability $p/N$. The Poisson estimator $\Xi_{A,\mathrm{Poi}}$ is then \eqref{eq:linstat-loss}, with constant weights again equal to $1/p$. When $p\ll N$, which is the regime of SGD, the cardinality of $A$ is tightly concentrated around $p$, and $\Xi_{A,\mathrm{Poi}}$ has the same fluctuations as the two default estimators, while being easier to analyze. In particular, $\mathbb{E}[\Xi_{A,\mathrm{Poi}} | \mathfrak{D}]=\Xi_N$ and $\mathrm{Var}[\Xi_{A,\mathrm{Poi}} | \mathfrak{D}]=\mathcal{O}_P(p^{-1})$; see Appendix~\ref{sec:S_Poisson} for details.

\paragraph{DPPs as (sub)sampling algorithms.}
As distributions over subsets of a large ground set that favour diversity, DPPs are intuitively good candidates at subsampling tasks, and one of their primary applications in ML has been as summary extractors \cite{KuTa12}. Since then, DPPs or mixtures thereof have been used, e.g., to generate experimental designs for linear regression, leading to strong theoretical guarantees \cite{NiSiTa18,derezinski-17,PoBa20Sub}; see also \cite{DeMa21} for a survey of DPPs in randomized numerical algebra, or \cite{BeBach20b} 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.i.d. sampling.
For coreset construction, for instance, \cite{TrBaAm19} manages to prove that a projection DPP necessarily improves over i.i.d. sampling with the same marginals \cite[Corollary 3.7]{TrBaAm19}, 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 \cite[Section 3.2]{TrBaAm19}.
Even closer to our motivation, DPPs for minibatch sampling have shown promising experimental performance \cite{ZhKjMa17}, but reading between the lines of the proof of \cite[Theorem 1]{ZhKjMa17}, a bad choice of DPP can even yield a \emph{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, where faster-than-i.i.d. error decays have been proven in similar contexts. For instance, orthogonal polynomial theory motivated \cite{BaHa20} to introduce a particular DPP, called a multivariate orthogonal polynomial ensemble, and prove a 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.

\section{DPPs, and two gradient estimators}
\label{s:estimator}
Since we shall need both discrete and continuous DPPs, we assume that $\mathcal X$ is either $\mathbb{R}^d$ or $\mathfrak{D}$, and follow \cite{HKPV06} in introducing DPPs in an abstract way that encompasses both cases.
After that, we propose two gradient estimators for SGD that build on a particular family of continuous DPPs introduced in \cite{BaHa20} for Monte Carlo integration, called multivariate orthogonal polynomial ensembles.

\subsection{DPPs: The kernel machine of point processes}
\label{s:dpp}
A point process on $\mathcal X$ is a distribution on finite subsets $S$ of $\mathcal X$; see \cite{DaVe03a} for a general reference.
Given a reference measure $\mu$ on $X$, a point process
is said to be determinantal (DPP) if there exists a function $K:\mathcal X\times \mathcal X\rightarrow \mathbb R$, the \emph{kernel} of the DPP, such that, for every $n\geq 1$,
\begin{align}
\label{def k cor DPP}
\mathbb E\bigg[\sum_{ \neq } &f(  x_{i_1}, \ldots,  x_{i_n})\bigg] = \int_{(\mathcal{X})^n}f(x_1,\ldots,x_n) \cdot \mathrm{Det}\Big[K(x_i,x_\ell)\Big]_{i,\ell=1}^n \mathrm{d}\mu^{\otimes n}(x_1,\ldots,x_n)
\end{align}
for every bounded Borel function $f:\mathcal X^n\to\mathbb{R}$, where the sum in the LHS of \eqref{def k cor DPP} ranges over all pairwise distinct $n$-uplets of the random  finite subset $ S$. A few remarks are in order. First, satisfying \eqref{def k cor DPP} for every $n$ is a strong constraint on $K$, so that not every kernel yields a DPP.
A set of sufficient conditions on $K$ is given by the Macchi-Soshnikov theorem \cite{Mac75,Sos00}.
In words, if $K(x,y) = K(y,x)$, and if $K$ further corresponds to an integral operator
$$
f \mapsto \int K(x,y)f(y) \mathrm{d}\mu(y), \quad f\in L^2(\mathcal X,\mu),
$$
that is trace-class with spectrum in $[0,1]$, then the corresponding DPP exists.
Second, note in \eqref{def k cor DPP} that the kernel of a DPP encodes how the points in the random configurations interact.
A strong point in favour of DPPs is that, unlike most interacting point processes, sampling and inference are tractable \cite{HKPV06,LaMoRu14}.
Third, \eqref{def k cor DPP} yields simple formulas for the mean and variance of linear statistics of a DPP.

\begin{proposition}[See e.g. \cite{Sos02,Gho15}]
	Let $S\sim\text{DPP}(K,\mu)$ and $\Phi:\mathcal X\rightarrow \mathbb R$ be a bounded Borel function,
	\begin{align}
	\mathbb E \left[\sum_{x\in S} \Phi(x)\right] &= \int \Phi(x) K(x,x) \mathrm{d}\mu(x),\label{e:expectation_of_linear_statistics}
	\\
	\mathrm{Var}\l[ \sum_{x \in S} \Phi(x) \r]
	&=  \iint \l\| \Phi(x) - \Phi(y) \r\|_2^2 |K(x,y)|^2 \mathrm{d} \mu(x) \mathrm{d} \mu(y) \nonumber\\&\quad + \int \l\|\Phi(x)\r\|_2^2 \l( K(x,x) - \int |K(x,y)|^2 \mathrm{d} \mu(y) \r) \mathrm{d} \mu(x). \label{eq:varlinstat}
	\end{align}
	\label{p:linear_statistics}
\end{proposition}

Since the seminal paper \cite{KuTa12}, the case $\mathcal X= \mathfrak{D}$ has been the most common in machine learning.
Taking $\mu$ to be $\hat\gamma_N$, any kernel is given by its restriction to $\mathfrak{D}$, usually given as an $N\times N$ matrix $\mathbf K = K\vert_\mathfrak{D}$.
Equation~\eqref{e:expectation_of_linear_statistics} with $n=p$, $A$ a subset of size $p$ of $\mathfrak{D}$, and $\Phi$ the indicator of $A$ yields
$
\mathbb P (A\subset S) =  N^{-p} \mathrm{Det} \mathbf K_A.
$
This is the usual way finite DPPs are introduced \cite{KuTa12}, except maybe for the factor $N^{-p}$, which comes from using $\hat\gamma_N$ as the reference measure instead of $N\hat{\gamma}_N$.
In this finite setting, a careful implementation of the general DPP sampler of \cite{HKPV06} yields $m$ DPP samples of average cardinality $\text{Tr}(\mathbf K)$ in $\mathcal O(N^\omega + m N \text{Tr}(\mathbf K)^2)$ operations \cite{Gil14}.

We now go back to a general $\mathcal X$ and fix $p\in\mathbb{N}$.
A canonical way to construct DPPs generating
configurations of $p$ points almost surely, i.e. $S=\{x_1,\ldots,x_p\}$, is the following.
Consider $p$ orthonormal functions
$\phi_0,\ldots,\phi_{p-1}$ in $L^2(\mu)$, and take for kernel
\begin{equation}
\label{kernel DPP}
K(x,y)=\sum_{k=0}^{p-1}\phi_k(x)\phi_k(y).
\end{equation}
In this setting, the (permutation invariant) random variables $ x_1,\ldots, x_p$ with joint distribution
\begin{equation}
\label{density DPP proj}
\frac1{p!}\mathrm{Det}\Big[K(x_i,x_\ell)\Big]_{i,\ell=1}^p\prod_{i=1}^p\mathrm{d}\mu(x_i)
\end{equation}
generate a DPP $\{x_1,\dots,x_p\}$ with kernel $K(x,y)$, called a \emph{projection} DPP.
For further information on determinantal
point processes, we refer the reader to \cite{HKPV06,KuTa12}.

\subsection{Multivariate orthogonal polynomial ensembles}
\label{s:OPE}
This section paraphrases \cite{BaHa20} in their definition of a particular projection DPP on $\mathcal X = \mathbb{R}^d$, called a multivariate orthogonal polynomial ensemble (OPE).
Fix some reference measure $q(x)\mathrm{d} x$ on $[-1,1]^d$, and assume that it puts positive mass on some open subset of $[-1,1]^d$.
Now choose an ordering of the monomial functions $(x_1,\ldots,x_d)\mapsto x_1^{\alpha_1}\cdots x_d^{\alpha_d}$; in this work we use the graded lexical order.
Then apply the Gram-Schmidt algorithm in $L^2(q(x)\mathrm{d} x)$ to these ordered monomials.
This yields a sequence of
orthonormal polynomial functions $(\phi_k)_{k\in\mathbb{N}}$, the multivariate
orthonormal polynomials w.r.t. $q$.
Finally, plugging the first $p$ multivariate orthonormal polynomials $\phi_0,\dots,\phi_{p-1}$ into the projection kernel \eqref{kernel DPP}, we obtain a projection DPP with kernel denoted as $K_q^{(p)}$, referred to as the \emph{multivariate OPE} associated with the measure $q(x)\mathrm{d} x$.

\subsection{Our first estimator: reweight, restrict, and saturate an OPE kernel}
\label{s:first_estimator}
Let $h>0$ and
\begin{equation}
\label{e:kde}
\tilde \gamma(\bm{z}) = \frac{1}{Nh^d} \sum_{i=1}^N k\left(\frac{\bm{z}-\bm{z}_i}{h}\right)
\end{equation}
be a single-bandwidth kernel density estimator of the pdf of the data-generating distribution $\gamma$; see \cite[Section 4.2]{WaJo94}, In particular, $k$ is chosen so that $\int k(x)\mathrm{d} x=1$.
Note that the approximation kernel $k$ is unrelated to any DPP kernel in this paper.
Let now $q(x) = q_1(x_1)\dots q_d(x_d)$ be a separable pdf on $[-1,1]^d$, where each $q_i$ is Nevai-class\footnote{See \cite[Section 4]{BaHa20} for details. It suffices that each $q_i$ is positive on $[-1,1]^d$.}.
Let $K_q^{(p)}$ be the multivariate OPE kernel defined in Section~\ref{s:OPE}, and form a new kernel
$$
K_{q,\tilde\gamma}^{(p)}(x,y) :=   \sqrt{\frac{q(x)}{\tilde\gamma(x)}} K_q^{(p)}(x,y) \sqrt{\frac{q(y)}{\tilde\gamma(y)}}.
$$
The form of $K_{q,\tilde\gamma}^{(p)}$ is reminiscent of importance sampling \cite{RoCa04}, which is no accident.
Indeed, while the positive semidefinite matrix
\begin{equation}
\label{e:kernel_restriction}
K_{q,\tilde\gamma}^{(p)}\vert_{\mathfrak D} := \left( K_{q,\tilde\gamma}^{(p)}(\bm{z}_i,\bm{z}_j) \right)_{1\leq i,j\leq N}
\end{equation}
is not necessarily the kernel matrix of a DPP on $(\{1,\dots,N\}, \hat\gamma_N)$, see Section~\ref{s:dpp}, we built it to be close to a projection of rank $p$.
More precisely,
$$
\int K_{q,\tilde\gamma}^{(p)}(\bm{z}_k,y)K_{q,\tilde\gamma}^{(p)}(y,\bm{z}_\ell) \mathrm{d}\hat\gamma_N(y) = \sqrt{\frac{q(\bm{z}_k)}{\tilde\gamma(\bm{z}_k)}}  \left[\frac1N \sum_{n=1}^N K_q^{(p)}(\bm{z}_k,\bm{z}_n) K_q^{(p)}(\bm{z}_n,\bm{z}_\ell) \frac{q(\bm{z}_n)}{\tilde\gamma(\bm{z}_n)}\right]\sqrt{\frac{q(\bm{z}_\ell)}{\tilde\gamma(\bm{z}_\ell)}}.
$$
If $N$ is large compared to $p$ and $d$, so that in particular $\tilde\gamma\approx\gamma$, the term within brackets will be close to $\int K_q^{(p)}(\bm{z}_k,\bm{z})K_q^{(p)}(\bm{z},\bm{z}_\ell) q(\bm{z})\mathrm{d}\bm{z} = K_q^{(p)}(\bm{z}_k,\bm{z}_\ell)$, so that $K_{q,\tilde\gamma}^{(p)}\vert_{\mathfrak D}$ is almost a projection in $L^2(\hat\gamma_N)$.

Let us actually consider the orthogonal projection matrix $\widetilde\mathbf{K}$ with the same eigenvectors as $K_{q,\tilde\gamma}^{(p)}\vert_{\mathfrak D}$, but with the $p$ largest eigenvalues replaced by $1$, and the rest of the spectrum set to $0$.
By the Macchi-Soshnikov theorem, $\widetilde\mathbf{K}$ is the kernel matrix of a DPP; see Section~\ref{s:dpp}. We thus consider a minibatch
$A\sim \text{DPP}(\widetilde\mathbf{K})$.
Coming from a projection DPP, $\vert A\vert=p$ almost surely, and we define the gradient estimator
\begin{equation}
\Xi_{A,\text{DPP}} := \sum_{i\in A}  \frac{\nabla_\theta\mathcal{L}(\bm{z}_i,\theta)}{\widetilde\mathbf{K}_{ii}}.
\label{e:first_estimator}
\end{equation}
In Section~\ref{s:theory}, we shall prove that $\Xi_{A,\text{DPP}}$ is unbiased, and examine under what assumptions its variance decreases faster than $1/p$.

\paragraph{On the computational cost of $\Xi_{A, \text{DPP}}$.}
The bottleneck is computing the $p$ largest eigenvalues of matrix \eqref{e:kernel_restriction}, 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 $\mathcal O(N p)$ storage.
Each iteration of SGD then only requires sampling a rank-$p$ projection DPP with diagonalized kernel, which takes $\mathcal O(Np^2)$ elementary operations \cite{Gil14}.
In practice, as the complexity of the model underlying $\bm{z},\theta\mapsto \nabla \mathcal{L}(\bm{z},\theta)$ increases, the cost of computing $p$ individual gradients shall outweigh this $\mathcal O(Np^2)$ overhead.
For instance, learning the parameters of a structured model like a conditional random field leads to arbitrarily costly individual gradients, as the underlying graph gets more dense \cite{VSSM06}.
Alternately, \eqref{e:first_estimator} can be sampled directly, without sampling the underlying DPP.
Indeed the Laplace transform of \eqref{e:first_estimator} is a Fredholm determinant, and it is shown in
\cite{BaGh21Sub} that Nyström-type approximations of that determinant, followed by Laplace inversion, yield an accurate inverse CDF sampler.

\vspace{0.5cm}
Finally, we stress the unusual way in which our finite DPP kernel $\widetilde{\mathbf{K}}$ is constructed, through a reweighted continuous OPE kernel, restricted to the actual dataset.
This construction is interesting \emph{per se}, as it is key to leveraging analytic techniques from the continuous case in Section~\ref{s:theory}.

\subsection{Our second estimator: sample the OPE, but smooth the gradient}
\label{s:second_estimator}
In Section~\ref{s:first_estimator}, we smoothed the empirical distribution of the data and restricted a continuous kernel to the dataset $\mathfrak{D}$, to make sure that the drawn minibatch would be a subset of $\mathfrak D$.
But one could actually define another gradient estimator, directly from an OPE sample $A = \{\bm{w}_1,\dots, \bm{w}_p\} \sim \text{DPP}(K_q^{(p)}, q)$.
Note that in that case, the ``generalized minibatch" $A\subset [-1,1]^d$ is not necessarily a subset of the dataset $\mathfrak D$.
Defining a kernel density estimator of the gradient,
\[\widehat{\nabla_\theta \mathcal{L}}(\bm{z},\theta) := \frac{1}{Nh^d} \sum_{i=1}^N  \nabla_\theta \mathcal{L}(\bm{z}_i,\theta)  \cdot k \left(\frac{\bm{z}-\bm{z}_i}{h}\right),\]
we consider the estimator
\[  \Xi_{A,\mathrm{s}}=\sum_{w_j \in A}  \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{w}_j,\theta)}{q(\bm{w}_j)K_q^{(p)}(\bm{w}_j,\bm{w}_j)}. \]

\paragraph{On the computational cost of $\Xi_{A,\mathrm{s}}$.}
Since each evaluation of this estimator is at least as costly as evaluating the actual gradient $\Xi_N(\theta)$, its use is mostly theoretical: the analysis of the fluctuations of $\Xi_{A,\mathrm{s}}$ is easier than that of $\Xi_{A,\mathrm{DPP}}$, while requiring the same key steps.
Moreover, the computation of all pairwise distances in $\Xi_{A,\mathrm{s}}$ could be efficiently approximated, possibly using random projection arguments \cite{Vem05}, so that the limited scope of $\Xi_{A,\mathrm{s}}$ might be overcome in future work. Note also that, like $\Xi_{A,\mathrm{DPP}}$, inverse Laplace sampling \cite{BaGh21Sub} applies to $\Xi_{A,\mathrm{s}}$.

\section{Analysis of determinantal sampling of SGD gradients}
\label{s:theory}
We first analyze the bias, and then the fluctuations, of the gradient estimators introduced in Section~\ref{s:estimator}. By Proposition~\ref{p:linear_statistics} with $\Phi = \nabla_\theta \mathcal{L}(\cdot, \theta)$, it comes
\[ \mathbb{E}[\Xi_{A,\mathrm{DPP}} | \mathfrak{D}] =  \int_D \nabla_\theta  \mathcal{L}(\bm{z},\theta) \cancel{K_{q,\tilde\gamma}^{(p)}(\bm{z},\bm{z})^{-1}} \cdot \cancel{K_{q,\tilde\gamma}^{(p)}(\bm{z},\bm{z})}  \mathrm{d}  \hat{\gamma}_N(z) = \frac{1}{N}  \sum_{i=1}^N \nabla_\theta \mathcal{L}(\bm{z}_i,\theta),\]
so that we immediatly get the following result.
\begin{proposition}
	$ \mathbb{E}[\Xi_{A,\mathrm{DPP}} | \mathfrak{D}] = \Xi_N$.
\end{proposition}
Thus, $\Xi_{A,\mathrm{DPP}}$ is unbiased, like the classical Poissonian benchmark in Section~\ref{s:related_work}. However, the smoothed estimator $\Xi_{A,\mathrm{s}}$ from Section~\ref{s:second_estimator} is slightly biased.
Note that while the results of \cite{BaMo11}, like \eqref{e:bach_moulines}, do not apply to biased estimators, SGD can be analyzed in the small-bias setting \cite{BeMePr90}.

\begin{proposition}
	Assume that $k$ in \eqref{e:kde} has compact support and $q$ is bounded on $D$. Then $\mathbb{E}[\Xi_{A,\mathrm{s}} | \mathfrak{D}]=\Xi_N + \mathcal{O}_P(ph/N)$.
\end{proposition}

\begin{proof}
	Using the first part of Proposition~\ref{p:linear_statistics} again, it comes
	\begin{align*}
	& \mathbb{E}[\Xi_{A,\mathrm{s}} | \mathfrak{D}]
	=  \mathbb{E}_{A \sim \text{DPP}(K_q^{(p)},q)} \l[\sum_{w_j \in A}  \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{w}_j,\theta)}{q(\bm{w}_j)K_q^{(p)}(\bm{w}_j,\bm{w}_j)}\r] \\
	= & \int_D \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{w},\theta)}{\cancel{q(\bm{w})K_q^{(p)}(\bm{w},\bm{w})}} \cdot \cancel{K_q^{(p)}(\bm{w},\bm{w}) q(\bm{w})} \mathrm{d} \bm{w}
	= \int_D \l(  \frac{1}{Nh^d} \sum_{i=1}^N  \nabla_\theta \mathcal{L}(\bm{z}_i,\theta)  k \left(\frac{\bm{z}-\bm{z}_i}{h}\right)  \r) \mathrm{d} \bm{w}\\
	=&    \frac{1}{N} \sum_{i=1}^N   \l( \int_D \frac{1}{h^d} \cdot k \left(\frac{\bm{w}-\bm{z}_i}{h}\right) \mathrm{d} \bm{w} \r) \cdot  \nabla_\theta \mathcal{L}(\bm{z}_i,\theta)
	=  \frac{1}{N} \sum_{i=1}^N  \nabla_\theta \mathcal{L}(\bm{z}_i,\theta) + \mathcal{O}_P(ph/N) \addtocounter{equation}{1}\tag{\theequation}  \label{eq:smoothed_error} ,
	\end{align*}
	where, in the last step, we have used the fact that $h^{-d} \cdot k \left(h^{-1} (\bm{w}-\bm{z}_i)\right)$  is a probability density. The $\mathcal{O}_P(ph/N)$  error term arises because we integrate that pdf on $D$ rather than $\text{Supp}(k)$.
	But since $k$ is a compactly supported kernel, for  points $\bm{z}_i$ that are within a distance $\mathcal{O}(h)$ from the boundary of $D$, we incur an error of $\mathcal{O}_P(1)$. By Proposition~\ref{p:linear_statistics}, the expected number of such points $\bm{z}_i$ is $\int_{D_h}  K_q^{(p)}(\bm{w},\bm{w}) q(\bm{w}) \mathrm{d} \bm{w}$, where $D_h$ is the $h$-neighbourhood of the boundary of $D$. By a classical asymptotic result of Totik, see \cite[Theorem 4.8]{BaHa20}, $\bm{w}\mapstoK_q^{(p)}(\bm{w},\bm{w})$ is $\mathcal{O}(p)$ on $D_h$; whereas $q$ is a bounded density, implying that $\int_{D_h} q(\bm{w}) \mathrm{d} \bm{w} =\mathcal{O}(\text{Vol}(D_h))=\mathcal{O}(h)$. Putting together all of these, we obtain the $\mathcal{O}_P(ph/N)$ error term in \eqref{eq:smoothed_error}.
\end{proof}

The rest of this section is devoted to the more involved task of analyzing the fluctuations of $\Xi_{A,\mathrm{DPP}}$ and $\Xi_{A,\mathrm{s}}$. For the purposes of our analysis, we discuss certain desirable regularity behaviour for our kernels and loss functions in Section~\ref{sec:regularity}. Then, we tackle the main ideas behind the study of the fluctuations of our estimators in Section~\ref{s:fluctuations}. Details can be found in Appendix~\ref{sec:S_fluct}.

\subsection{Some regularity phenomena} \label{sec:regularity}
Assume that $(\frac{1}{p} \cdot K_q^{(p)}(\bm{z},\bm{z}))^{-1}\nabla_\theta  \mathcal{L}(\bm{z},\theta)$ is bounded on the domain $D$ uniformly in $N$ (note that $p$ possibly depends on $N$).
Furthermore, assume that $\bm{z}\mapsto (p^{-1} \cdot K_q^{(p)}(\bm{z},\bm{z})q(\bm{z}))^{-1}\nabla_\theta  \mathcal{L}(\bm{z},\theta) \cdot \tilde{\gamma}(\bm{z})$ is 1-Lipschitz, with Lipschitz constant $\mathcal{O}_P(1)$ and bounded in $\theta$.

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 $\tilde{\gamma}$ to the distribution $\gamma$. The detailed discussion is deferred to Appendix~\ref{sec:S_reg}; we record here in passing that the above asymptotic phenomena imply that
\begin{equation}
\label{e:limit}
\frac{\nabla_\theta  \mathcal{L}(\bm{z},\theta)}{\frac{1}{p} \cdot K_q^{(p)}(\bm{z},\bm{z})q(\bm{z})} \cdot \tilde{\gamma}(\bm{z})  \longrightarrow \nabla_\theta  \mathcal{L}(\bm{z},\theta) \cdot \gamma(\bm{z}) \prod_{j=1}^d\sqrt{1-\bm{z}[j]^2}.
\end{equation}
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 $\Xi_{A,\mathrm{DPP}}$ by working on the limit in \eqref{e:limit}.
For the fluctuation analysis of the smoothed estimator $\Xi_{A,\mathrm{s}}$, we similarly assume that $ (q(\bm{w})\cdot \frac{1}{p}K_q^{(p)}(\bm{w},\bm{w}))^{-1}\widehat{\nabla_\theta \mathcal{L}}(\bm{w},\theta)$ is  $\mathcal{O}_P(1)$ and 1-Lipschitz with an $\mathcal{O}_P(1)$ Lipschitz constant that is bounded in $\theta$. These are once again motivated by the convergence of $ (q(\bm{w})\cdot \frac{1}{p}K_q^{(p)}(\bm{w},\bm{w}))^{-1}\widehat{\nabla_\theta \mathcal{L}}(\bm{w},\theta)$  to $ \nabla_\theta \mathcal{L}(\bm{w},\theta) \prod_{j=1}^d \sqrt{1-\bm{w}[j]^2}$.

\subsection{Reduced fluctuations for determinantal samplers}
\label{s:fluctuations}
For succinctness of presentation, we focus on the theoretical analysis of the smoothed estimator $\Xi_{A,\mathrm{s}}$, leaving the analysis of $\Xi_{A,\mathrm{DPP}}$ to Appendix~\ref{sec:S_fluct}, while still capturing the main ideas of our approach.
\begin{proposition} \label{prop:var_est}
	Under the assumptions in Section~\ref{sec:regularity},  $\mathrm{Var}[\Xi_{A,\mathrm{s}}|\mathfrak{D}]=\mathcal{O}_P(p^{-\l(1+1/d\r)})$.
\end{proposition}
\begin{proof}[Proof Sketch]
	Invoking \eqref{eq:varlinstat} in the case of a projection kernel,
	\begin{align*}
	\mathrm{Var}& [\Xi_{A,\mathrm{s}}|\mathfrak{D}] = \iint \l\| \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{z},\theta)}{q(\bm{z})K_q^{(p)}(\bm{z},\bm{z})} - \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{w},\theta)}{q(\bm{w})K_q^{(p)}(\bm{w},\bm{w})} \r\|_2^2 |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w})  \\
	= & \frac{1}{p^2}\iint \l\| \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{z},\theta)}{q(\bm{z})\cdot \frac{1}{p} K_q^{(p)}(\bm{z},\bm{z})} - \frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{w},\theta)}{q(\bm{w})\cdot \frac{1}{p} K_q^{(p)}(\bm{w},\bm{w})} \r\|_2^2 |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w})  \\
	\lesssim &  \mathcal{M}_\theta \cdot \frac{1}{p^2} \int\int \l\| \bm{z} - \bm{w} \r\|_2^2 |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w}), \addtocounter{equation}{1}\tag{\theequation} \label{eq:break_1}
	\end{align*}
	where we used the 1-Lipschitzianity of $\frac{\widehat{\nabla_\theta \mathcal{L}}(\bm{z},\theta)}{q(\bm{z})K_q^{(p)}(\bm{z},\bm{z})}$, with $\mathcal{M}_\theta=\mathcal{O}_P(1)$ the Lipschitz constant.

	We control the integral in \eqref{eq:break_1} by invoking the renowned Christoffel-Darboux formula for the OPE kernel $K_q^{(p)}$ \cite{Sim08}. For clarity of presentation, we outline here the main ideas for $d=1$; the details for general dimensions are available in Appendix~\ref{sec:S_fluct}. Broadly speaking, since $K_q^{(p)}$ is an orthogonal projection of rank $p$ in $L_2(q)$, we may observe that $ \iint |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w})=p$; so that without the $\l\| z-w \r\|_2^2$ term in \eqref{eq:break_1}, we would have a $\mathcal{O}_P(p^{-1})$ behaviour in total, which would be similar to the Poissonian estimator. However, it turns out that the leading order contribution to $\int\int \l\| z-w \r\|_2^2 |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w})$ comes from near the diagonal $z=w$, and this turns out to be neutralised in an extremely precise manner by the $\l\| \bm{z} - \bm{w} \r\|_2^2$ factor that vanishes on the diagonal.

	This neutralisation is systematically captured by the Christoffel-Darboux formula \cite{Sim08}, which implies
	$$
	K_q^{(p)}(x,y) = (x-y)^{-1} A_p \cdot (\phi_q(x)\phi_{q-1}(y) -  \phi_q(y)\phi_{q-1}(x)),
	$$
	where $A_p=\mathcal{O}(1)$ and $\phi_q,\phi_{q-1}$ are two orthonormal functions in $L_2(q)$. Substituting this into \eqref{eq:break_1}, a simple computation shows that $ \iint \l\| z-w \r\|_2^2 |K_q^{(p)}(\bm{z},\bm{w})|^2 \mathrm{d} q(\bm{z}) \mathrm{d} q(\bm{w})=\mathcal{O}(1)$. This leads to a variance bound $\mathrm{Var}[\Xi_{A,\mathrm{s}}|\mathfrak{D}]=\mathcal{O}_P(p^{-2})$, which is the desired rate for $d=1$. For general $d$, we use the fact that $q=\bigotimes_{i=1}^d q_i$ is a product measure, and apply the Christoffel-Darboux formula for each $q_i$, leading to a variance bound of $\mathrm{Var}[\Xi_{A,\mathrm{s}}|\mathfrak{D}]=\mathcal{O}_P(p^{-\l(1+1/d\r)})$, as desired.
\end{proof}

The theoretical analysis of $\mathrm{Var}[\Xi_{A,\mathrm{DPP}}|\mathfrak{D}]$ follows the broad contours of the argument for $\mathrm{Var}[\Xi_{A,\mathrm{s}}|\mathfrak{D}]$ as above, with additional difficulties introduced by the spectral truncation from $K_{q,\tg}^{(p)}$ to $\widetilde\mathbf{K}$; see Section~\ref{s:estimator}.  This is addressed by an elaborate spectral approximation analysis in Appendix~\ref{sec:S_fluct}. In combination with the ideas expounded in the proof of Proposition \ref{prop:var_est}, our analysis in Appendix~\ref{sec:S_fluct}  indicates a fluctuation bound of $\mathrm{Var}[\Xi_{A}|\mathfrak{D}]=\mathcal{O}_P(p^{-\l(1+1/d\r)})$.

\section{Experiments}
\label{s:experiments}
In this section, we compare the empirical performance and the variance decay of our gradient estimator $\Xi_{A,\mathrm{DPP}}$ to the default $\Xi_{A,\mathrm{Poi}}$. We do not to include $\Xi_{A,\mathrm{s}}$, whose interest is mostly theoretical; see Section~\ref{s:theory}. Moreover, while we focus on simulated data to illustrate our theoretical analysis, we provide experimental results on a real dataset in Appendix~\ref{supp:s:real_dataset}.
Throughout this section, the pdf $q$ introduced in Section~\ref{s:OPE} is taken to be $q(\bm{w}) \propto \prod_{j=1}^d (1+\bm{w}[j])^{\alpha_j} (1-\bm{w}[j])^{\beta_j}$, with $\alpha_j,\beta_j\in[-1/2,1/2]$ tuned to match the first two moments of the $j$th marginal of $\hat\gamma_N$. All DPPs are sampled using the Python package {\verb DPPy } \cite{GBPV19}, which is under MIT licence.

\paragraph{Experimental setup.}
We consider the ERM setting \eqref{e:ERM} for linear regression $\mathcal{L}_{\text{lin}}((x,y),\theta)=0.5(\langle x, \theta\rangle-y)^2$ and logistic regression $\mathcal{L}_\text{log}((x,y),\theta)=\log[1+\exp(-y\langle x,\theta\rangle )]$, both with an additional $\ell_2$ penalty $\lambda(\theta)=(\lambda_0/2)\|\theta\|_2^2$.
Here the features are $x\in[-1,1]^{d-1}$, and the labels are, respectively, $y\in[-1,1]$ and $y\in \{-1,1\}$.
Note that our proofs currently assume that the law $\gamma$ of $z=(x,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.

For each experiment, we generate $N=1000$ data points $x_i$ with either the uniform distribution or a mixture of $2$ well-separated Gaussian distributions on $[-1,1]^{d-1}$.
The variable $y_i\in\mathbb{R}$ is generated as $\langle  x_i,\theta_\text{true}\rangle+\varepsilon_i$, where $\theta_\text{true}\in \mathbb{R}^{d-1}$ is given, and $\varepsilon\in \mathbb{R}^{N}$ is a white Gaussian noise vector. In the linear regression case, we scale $y_i$ by $\|y\|_{\infty}$ to make sure that $y_i\in[-1,1]$. In the logistic regression case, we replace each $y_i$ by its sign. The regularization parameter $\lambda_0$ is manually set to be $0.1$ and the stepsize for the $t$-th iteration is set as $1/t^{0.9}$, so that \eqref{e:bach_moulines} applies.
In each experiment, performance metrics are averaged over $1000$ independent runs of each SGD variant.

\paragraph{Performance evaluation of sampling strategies in SGD.}
Figure \ref{fig:linear_uniform} summarizes the experimental results of $\Xi_{A,\mathrm{Poi}}$ and $\Xi_{A,\mathrm{DPP}}$, with $p=5$ and $p=10$.
The top row shows how the norm of the complete gradient $\Vert \Xi_N(\theta_t)\Vert $ decreases with the number of individual gradient evaluations $t\times p$, called here \emph{budget}.
The bottom row shows the decrease of $\Vert\theta_t-\theta_\star\Vert$. Note that using $t\times p$ on all $x$-axes allows comparing different batchsizes. Error bars on the bottom row are $\pm$ one standard deviation of the mean. In all experiments, using a 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 a better way of spending a 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.

\begin{figure}[hbt!]
	\subfigure[$d=3$, $\mathcal{L}=\mathcal{L}_\text{lin}$, uniform]{ \label{fig:d3_linear_u_grad}
		\includegraphics[width=0.31\linewidth]{loggrad_linear_d2_u.pdf}}
	\subfigure[$d=3$, $\mathcal{L}=\mathcal{L}_\text{lin}$, mixture]{ \label{fig:d3_linear_m2_grad}
		\includegraphics[width=0.33\linewidth]{loggrad_linear_d2_m2.pdf}}
	\subfigure[$d=11$, $\mathcal{L}=\mathcal{L}_\text{log}$, uniform]{ \label{fig:d11_logistic_u_grad}
		\includegraphics[width=0.33\linewidth]{loggrad_logistic_d10_u.pdf}}
	\subfigure[$d=3$, $\mathcal{L}=\mathcal{L}_\text{lin}$, uniform]{ \label{fig:d3_linear_u_err}
		\includegraphics[width=0.32\linewidth]{err_errorbar_linear_d2_u.pdf}}
	\subfigure[$d=3$, $\mathcal{L}=\mathcal{L}_\text{lin}$, mixture]{ \label{fig:d3_linear_m2_err}
		\includegraphics[width=0.32\linewidth]{err_errorbar_linear_d2_m2.pdf}}
	\subfigure[$d=11$, $\mathcal{L}=\mathcal{L}_\text{log}$, uniform]{ \label{fig:d11_logistic_u_err}
		\includegraphics[width=0.32\linewidth]{err_errorbar_logistic_d10_u.pdf}}
	\caption{Summary of the performance of two sampling strategies in SGD.}\label{fig:linear_uniform}
\end{figure}

\paragraph{Variance decay.}
For a given dimension $d$, we want to infer the rate of decay of the variance $\sigma^2 = \mathbb{E}[\Vert \Xi_A(\theta_\star) \Vert^2 \vert \mathfrak{D}]$, to confirm the $\mathcal{O}_P(p^{-(1+1/d)})$ rate discussed in Section~\ref{s:theory}. We take $\mathcal{L}=\mathcal{L}_{\text{lin}}$ as an example, with $N=1000$ i.i.d. samples $\mathfrak{D}$ from the uniform distribution on $[-1,1]^d$.
For $d=1,2,3$, we show in Figure~\ref{fig:slope_variance} the sample variance of $1000$ realizations of the variance of $\Vert \Xi_{A,\mathrm{Poi}}(\theta_\star) \Vert^2$ (white dots) and $\Vert \Xi_{A,\mathrm{DPP}}(\theta_\star) \Vert^2$ (black dots), conditionally on $\mathfrak{D}$. Blue and red 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 $\sigma^2$ is smaller for the DPP, decays as $p^{-1-1/d}$, and that this decay starts at a batchsize $p$ that increases with dimension.

\begin{figure}[hbt!]
	\subfigure[$d=1$]{ \label{fig:slope_d1}
		\includegraphics[width=0.32\linewidth]{slope_p1.pdf}}
	\subfigure[$d=2$]{ \label{fig:slope_d2}
		\includegraphics[width=0.32\linewidth]{slope_p2.pdf}}
	\subfigure[$d=3$]{ \label{fig:slope_d3}
		\includegraphics[width=0.32\linewidth]{slope_p3_v2.pdf}}
	\caption{Summary of the variance decay results.}\label{fig:slope_variance}
\end{figure}

\section{Discussion}
\label{s: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 $\Xi_{A,\mathrm{s}}$, which calls for further investigation in order to be deployed as a computationally attractive procedure; improvement in the dimension dependence of the fluctuation exponent when the gradients are smooth enough, like \cite{BeBaCh19,BeBaCh20} did for \cite{BaHa20}; sharpening of the regularity hypotheses for our theoretical investigations to obtain a more streamlined analysis. While our estimators were motivated by a continuous underlying data distribution, our experiments suggest notably good performance 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 or otherwise, would be a 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 in point is the method of importance sampling, where the independence across data points suggests that  the variance should still be $\mathcal{O}_P(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 \cite[Section 4.2]{BaMo11}, it would be interesting to introduce repulsiveness across consecutive SGD iterations to further minimize the variance of averaged estimators.
In summary, we believe that the ideas put forward in the present work will motivate a new perspective on improved minibatch sampling for SGD, more generally on estimators based on linear statistics (e.g. in coreset sampling), and beyond.

\section*{Acknowledgements}
  RB acknowledges support from ERC grant \textsc{Blackjack} (ERC-2019-STG-851866) and ANR AI chair \textsc{Baccarat} (ANR-20-CHIA-0002). S.G. was supported in part by the MOE grants R-146-000-250-133 and R-146-000-312-114.

redpajama_set_name: RedPajamaArXiv


Aaron plays some Desert Child on Steam.
Aaron plays some Horizon Chase Turbo for the Nintendo Switch.
Aaron plays some TrouserHeart for the Nintendo Switch.
Aaron plays some Toki for the Nintendo Switch.
Aaron plays some Crimson Keep for the Nintendo Switch.
Aaron plays some Miles & Kilo for the Nintendo Switch.
Aaron plays some Escape Doodland for the Switch.
Aaron plays some Guns, Gore and Cannoli 2 for the Switch.
Aaron plays some Rage in Peace on the Switch.
Aaron plays some Suicide Guy: Sleepin' Deeply on the Switch.
Aaron plays some Swap This! on the Switch.
Aaron plays some Zarvot on the Switch.
Aaron plays some Friday the 13th: Killer Puzzle on the Switch.
Aaron plays some SkyScrappers on the Nintendo Switch.
Aaron plays some Chiki-Chiki Boxy Racers on the Nintendo Switch.


text:
Home > Population Health > Community Health Needs Assessment > Health Indicators > Alcohol Use
Cost As a Barrier To Care
Housing Insecurity
Mental Health - Depression
Overall Good Health
Poor Mental Health Days
Primary Care Provider
Alcohol Use (Binge Drinking During the Past 30 Days)
Excessive alcohol use, such as binge drinking, can increase the risk of various health problems like liver diseases and cancer. Binge drinking can also lead to injuries from automobile accidents as well as injuries from interpersonal violence.1
Findings in Santa Barbara County
Binge drinking was defined as four or more drinks on one occasion for women and five or more drinks on one occasion for men consumed within the past 30 days. It is possible that this is under-reported because people might be reluctant to report high levels of drinking, which has a social stigma.
Table 8. Percentage of Adults Who Report Binge Drinking During the Past 30 Days and the Healthy People 2020 Target
2016 Santa Barbara
California*
Health People 2020
%(95% CI) % (95% CI)
16.7 (14.0-19.3) 15.6 (14.5–16.7)
11.4 (8.3-14.5) 11.1 (9.7–12.5)
Non-Hispanic White
24.4 (13.0-35.9) NA
*2014 Behavioral Risk Factor Surveillance System.
Figure 16. Percentages of Self-Reported Binge Drinking in Santa Barbara County, by Sex and Age
Figure 17. Percentage of Self-Reported Binge Drinking in Santa Barbara County, by Race/Ethnicity, Educational Attainment, and Income
The percentage of individuals who report binge drinking in the past 30 days in Santa Barbara County overall is substantially lower than the HP 2020 target, but twice as many men than women report binge drinking.
Binge drinking rates are similar for Hispanics and whites, but the highest percentage is among those of "other" ethnic groups, Asian-American and African-American. The age group most likely to binge drink is the 18–44 group, which includes college students, who might account for the higher prevalence of binge drinking.
The map below shows the percentage of survey respondents who report binge drinking during the past 30 days. The smaller map of Isla Vista with its overall percentage of binge drinking might underestimate rates, specifically among college students. The tract where the university is located has an estimated 13.3% binge drinking rate, and the tract next to it has an even higher rate, 20.1%.
However, two tracts in this cluster have no binge drinking reports, and another has a 7% reported incidence. In order to get a reliable estimate for this area, we had to combine the groups, which made an average incidence of binge drinking for these tracts of 12.6%.
Figure 18. Percentage of Santa Barbara County Adults Reporting Binge Drinking**, by County Subregion
Factors and Health Outcomes Associated with Binge Drinking
Figure 19 presents various individual, social, and environmental factors associated with binge drinking. It compares only Santa Barbara County residents who report binge drinking with all county residents and with Californians as a whole.
Figure 19. Health and Risk Factors of Santa Barbara County Adults Who Report Binge Drinking in the Past 30 Days (16.7%), Compared With All Santa Barbara County Adults and Californians* as a Whole
*Data for California are not available for all indicators
The figure shows that binge drinkers are more likely to also report current smoking than Santa Barbara County residents as a whole. In addition, they report food insecurity and cite not having health insurance at higher rates than others. Binge drinkers were less likely to report fair/poor health, diabetes/pre-diabetes, heart disease, or cancer. People who report binge drinking in the past 30 days may be more likely to be younger and thus suffering at lower rates from chronic diseases.
Key Opportunities for Population Health Improvement
What Businesses Can Do
Have written policies that promote an alcohol-free workplace.2
Inform and educate employees about alcohol and drug use as part of general employee wellness education.3
Provide a confidential Employee Assistance Program (EAP) for employees who want help with drinking.4
Encourage employees and their families to use the EAP and train supervisors to support employees who do so.5
2 http://www.samhsa.gov/sites/default/files/workplace-kit.pdf
4 http://calabria.dronet.org/comunicazioni/news/samhsa_work.pdf
What Healthcare Providers Can Do
Provide basic alcohol screening and brief intervention programs.6
Use the four-question CAGE from the National Institute on Alcohol Abuse and Alcoholism.7
Use the Alcohol Use Disorders Identification Test (AUDIT) instrument.8
6 http://www.countyhealthrankings.org/policies/alcohol-screening-brief-intervention
7 http://pubs.niaaa.nih.gov/publications/aa65/AA65.htm
What Individuals Can Do
Take the "Rethinking Drinking" self-test online.9
Get help at Alcoholics Anonymous.10
Use the EAP at work, if one is available.
9 https://www.rethinkingdrinking.niaaa.nih.gov/How-much-is-too-much/Is-your-drinking-pattern-risky/Whats-Your-Pattern.aspx
10 http://www.aa.org/
1 Miller, J. W., Naimi, T. S., Brewer, R. D., & Jones, S. E. (2007). Binge drinking and associated health risk behaviors among high school students. Pediatrics, 119(1), 76-85
Boffetta, P., & Hashibe, M. (2006). Alcohol and cancer. The lancet oncology, 7(2), 149-156.
Population Health Listening Tour
Learn about the challenges facing populations in Santa Barbara County and the implications that they have on public health.
Connect With Pop Health
We want to hear from you -- our community leaders! E-mail the Population Health team at: listenpophealth@sbch.org, or to be added to our mailing list please fill out this brief form.
Mailing List Form
Listening Tour Findings
View a brief summary of key findings from the Cottage Population Health Listening Tour.
View Listening Tour Key Findings
Listening Tour Survey
The results from this survey helped Cottage Health prioritize the health indicators highlighted in the Community Health Needs Assessment (CHNA) report.
View Listening Tour Survey Results

redpajama_set_name: RedPajamaCommonCrawl


text:
Just South of Home (Hardcover)
By Karen Strong
(40 MIDDLE GRADE FICT)
A Kirkus Reviews Best Middle Grade Book of 2019
"A stirring Southern middle grade book that burns brighter than fireworks on the Fourth." —Kirkus Reviews (starred review)
"A must for readers who appreciate a heartfelt mystery." —Booklist (starred review)
"An intricate mix of Southern mystery, history, and a ghost story that creeps but doesn't scare." —School Library Journal (starred review)
Cousins Sarah and Janie unearth a tragic event in their small Southern town's history in this witty middle grade novel that's perfect for fans of Stella by Starlight, The Ghosts of Tupelo Landing, and As Brave as You.
Twelve-year-old Sarah is finally in charge. At last, she can spend her summer months reading her favorite science books and bossing around her younger brother, Ellis, instead of being worked to the bone by their overly strict grandmother, Mrs. Greene. But when their cousin, Janie arrives for a visit, Sarah's plans are completely squashed.
Janie has a knack for getting into trouble and asks Sarah to take her to Creek Church: a landmark of their small town that she heard was haunted. It's also off-limits. Janie's sticky fingers lead Sarah, Ellis, and his best friend, Jasper, to uncover a deep-seated part of the town's past. With a bit of luck, this foursome will heal the place they call home and the people within it they call family.
Karen Strong was born and raised in rural Georgia. She spent most of her childhood wandering the woods, meadows, and gardens of her grandmother's land. She now lives in Atlanta. Just South of Home is her first novel. Learn more at Karen-Strong.com.
* "Strong's prose pours from her pen like iced sweet tea on an August afternoon—it's refreshing, steeped in tradition, and mixed with love. A stirring Southern middle-grade book that burns brighter than fireworks on the Fourth."
— Kirkus Reviews, STARRED REVIEW
* "Strong's prose presents a world so real readers will feel the warm Georgia breeze, or the haints' chilling breath down your neck….Readers will need a sweet tea to calm their nerves after this emotional adventure. First purchase for all collections."
— School Library Journal, STARRED REVIEW
* "Strong packs a lot of heart into this vivid debut about love, family, forgiveness, and the kinds of horrors few can scarcely conceive....Free-flowing dialogue, a rich story line, and warm characters nicely ground the more supernatural elements. This is a must for readers who appreciate a heartfelt mystery."
— Booklist, STARRED REVIEW
"Readers of Turnage's Three Times Lucky will appreciate this well-wrought, atmospheric mystery."
— BCCB
Publisher: Simon & Schuster Books for Young Readers
Publication Date: May 7th, 2019
Juvenile Fiction / Ghost Stories
Juvenile Fiction / People & Places / United States / African American
Kobo eBook (May 6th, 2019): $10.99


Wevikofds27.club is 1 month old (current registration since 25 February 2019).
wevikofds27.club is known by our system for 1 month. His IP address is 50.63.202.38 and there's at least 100 websites associated with this ip, it's a shared host.


text:
https://www.middletownpress.com/entertainment/article/Middletown-s-Buttonwood-Tree-presenting-pianist-11788445.php
Middletown's Buttonwood Tree presenting pianist Laszlo Gardony on Feb. 1
Published 7:34 pm EST, Wednesday, January 8, 2014
Photo by Richard Conde Laszlo Gardony is performing Feb. 1 at the Buttonwood Tree in Middletown.
MIDDLETOWN >> Laszlo Gardony returns to Buttonwood Tree on Saturday, Feb. 1 for a performance with his quartet, featuring Stan Strickland on reeds and vocals, John Lockwood on bass and Yoron Israel on drums.
Laszlo's new solo piano CD, titled Clarity has earned wide critical acclaim:
"Four stars. Each of the 10 electrifying improvisations, full of rhythmic daring and unfiltered emotional honesty, hits you square in the face and demands attention. Rather like that famous footage of Picasso at work in his studio, Gardony's stroke appears effortless." — Fred Grand, Jazz Journal UK
"Unusually intimate, as if we're overhearing a great pianist's most private musings from outside a practice-room door. The music is cathartic but celebratory more than somber, and Gardony's blending of his European roots with jazz give it a feel akin to Jarrett's solo work for ECM." — Bill Beuttler, JazzTimes
From www.laszlogardony.com: Gardony has brought his soulful improvisations and compositions to audiences in 24 countries. Winner of the Great American Jazz Piano Competition, Gardony has been called "one of contemporary music's truly original voices" by JazzTimes Magazine. Gardony has been praised for his "fluid pianism" by The New York Times and for his "uniformly high quality of compositions" by All About Jazz.
He has released ten albums showcasing a probing intellect with keen emotional sensitivity. He's led groups that included Dave Holland, Miroslav Vitous, Mick Goodrick, Yoron Israel, John Lockwood, Jamey Haddad and Stan Strickland among others. His most recent Sunnyside CD, Clarity - a soul-bearing solo album full of rhythmic variety, melodic discovery and an abundance of grace - was released on May 7, 2013 two decades after Gardony's acclaimed Sunnyside debut Changing Standards established him as one of jazz's foremost practitioners of the solo piano format. The album has earned wide acclaim:
More than a gifted improviser, Gardony is a cagey musical architect who understands that "shape is paramount. Without shape, regardless of what you create in your solo piano playing, it's not going to connect. On Clarity I created these 10 short stories building on each other and I naturally pause between them. The idea is to transcend the sense that here is a pianist and here is a listener. It's more of a joint journey."
In addition to his work as a leader, Gardony has recorded and toured extensively with Yoron Israel's High Standards Quartet and with Matt Glaser's Wayfaring Strangers. He has also performed with the David "Fathead" Newman Quintet, vocalist Shelley Neill's group, guitarist Garrison Fewell's quartet, the Eddie Gomez Quintet and the Marco Pignataro Jazzet. Randy Brecker, Dave Liebman and John Blake appeared as guest soloists with his group. He has been featured with the Boston Pops, the Utah Symphony and The Smithsonian Institute's "Beyond Category" Traveling Duke Ellington Exhibit. He was also commissioned to arrange his original compositions for The Danish Radio Big Band. A Boston resident for the past twenty five years, Gardony is a professor of piano at Berklee College of Music.
The Buttonwood Tree is located at 605 Main Street, Middletown. Showtime is 8 p.m, and tickets are $12. For more information go to www.buttonwood.org or call 860-347-4957.


text:
Home News & Articles Is It OK To Announce A New Owner In The Form Of A Question?
Is It OK To Announce A New Owner In The Form Of A Question?
Announcements of new partners or owners at law firms are mostly the same – sometimes pretentious, always formal and invariably dull. We've been guilty of the same thing in the past and if we weren't so unimaginative it would be distressing.
But we were given an opportunity to shake our lethargy when Kelly Bode became our newest co-owner on January 1. And since it's 2014, which is technically the future in nearly every science fiction novel written, it makes sense to try and upgrade the announcement for modern times.
But what do do? Posting a selfie already seems sort of old-fashioned. Putting an announcement on Facebook would appeal to the parents and grandparents but doesn't do much for Instagram or Snapchat fans. And to follow that point, we do want as many people as possible to know how proud we are to have Kelly join our group. She is, after all, the first owner that has spent her entire career at WMCZ. The poor woman deserves something special for enduring that.
So how about the tried and true method of creating a link-bait headline that will drive traffic to our website? Unfortunately we couldn't agree on one so we'll have to leave it to our readers to cut and paste a favourite:
5 Reasons Why Kelly Bode Should Have Never Become An Owner of WMCZ (And One Reason She Should)
This Is The Most Shocking Picture Of A New Law Firm Owner You Will See All Day
You Won't Believe What Kelly Bode's Nickname At WMCZ Was Before She Became An Owner
Does Kelly Bode Believe The Moon Landing Was A Hoax?
Use This One Simple Trick To Meet Kelly Bode
Watch This Kitten's Reaction When She Learns Kelly Bode Accepted An Ownership Offer At WMCZ
Congratulations and welcome, Kelly!


text:
Herzog & Co. adds Andie Beckerman to its ranks
Los Angeles-based entertainment outfit Herzog & Company has named Andie Beckerman as senior vice president of original programming and development. Beckerman will be tasked with overseeing all original programming development. She ...
By Selina Chignall
Los Angeles-based entertainment outfit Herzog & Company has named Andie Beckerman as senior vice president of original programming and development.
Beckerman will be tasked with overseeing all original programming development. She reports directly to company founder and CEO Mark Herzog.
The executive joins Herzog from USA Network and SyFy, where she previously served as VP of development. Beckerman also held multiple roles at AMC prior to joining the NBCUniversal Cable Entertainment Group-owned networks.
The Emmy Award-winning Herzog & Company's production stable currently include The Movies, a 12-hour docuseries produced with Tom Hanks' Playtone for CNN in Summer 2019. For ESPN, the production company is developing two docuseries for Fall 2019 in celebration of the 150th anniversary of college football, The American Game and The Greatest. Elsewhere, for History Channel comes the two-hour documentary Cola Wars, which examines the historic rivalry between Coke and Pepsi, and the true crime documentary special Dirty John: The Dirty Truth for Oxygen.
"Andie's depth of experience both in developing and seeing through successful productions will undoubtedly be a terrific contribution to Herzog's talented and inspired creative team," said Herzog in a statement.
Andie Beckerman, Herzog & Company, Mark Herzog
Syfy taps Andie Beckerman to lead unscripted development


text:
admin@larkbridge.co.uk
Re-Mortgaging
Mortgage Guide
Protection Guide
Equity Release Guide
Key Person Protection
Commercial Key Person Protection
Your employees are one of the most important resources for the future success of your business. Have you given thought to how your company would cope if a key member of staff were to die, be diagnosed with or suffer a critical illness?
The death or critical illness of a key person is likely to have a significant impact on your business. You could suffer a loss of profits, be unable to quickly recruit a suitable replacement and face significant disruption to your own business activities.
However, you can help protect the future survival of your business with Key Person Protection, which can help you financially cope with the loss of a key person.
About Larkbridge
Larkbridge Mortgages Ltd is an appointed representative of TenetLime Ltd which is authorised and regulated by the Financial Conduct Authority. TenetLime Ltd is entered on the Financial Services Register (http://fca.org.uk/register) under reference 311266. Larkbridge Mortgages Ltd is registered in England under registration number 08247201. Registered Office Address: The Stables, Flempton House, Bury Road, Flempton, Suffolk IP28 6EG. The information contained within this website is subject to the UK regulatory regime and is therefore primarily targeted at consumers based in the UK.
© Larkbridge Mortgages Ltd
For more information on our Privacy Policy please read here
Email communications are not secure and for this reason Larkbridge Mortgages Ltd cannot guarantee the security of email, its contents or that it remains virus free once sent. Email Us: admin@larkbridge.co.uk


Elvira del Pozo is an ABD who holds an Undergraduate Degree in Law and a Master´s degree in Sociology. She has gained 14 years of experience in a career which began as a Social Academic Researcher at Easter Michigan University (USA) and at Universitat de Valencia, continued as a Market Researcher at a local agency in Spain and is currently specialized in International Market Research Studies at a multinational corporation. In her academic years, Elvira conducted Doctoral studies while she was also working as a research assistant, which allowed her to collaborate in numerous research projects both in the US and Spain. She also gained some teaching experience in the US and publishing in National and International Journal Magazines. Currently, she has gained experience in project management and result analysis. She is an Executive Researcher at GfK, a Market Research Business. She works at the Animal and Crop Department and is responsible for coordinating both national and international studies, with a greater focus on the latter. This position includes managing client proposals, briefings and setting up and executing both quantitative and qualitative studies. The management of studies involves the following responsibilities: desk research analysis, processing and coordinating field work, managing data processing, write-up and presentation of final reports. Simultaneously, Elvira is also responsible for occasionally managing the work of students who collaborate as Market Assistants. She has lived in Switzerland for 2 years and the United States for 8 years.


Hamil-Swag: A Sticker Situation! – It's Hamiltime!
Hello this is historicalcutouts.com Thanks for featuring us =D. We have a large collection of historical figures, i myself have Tesla and Alan Turing by my desk.


Remarks: Edward Bement was a prominent New York banker. His philanthropic gifts established him as a generous New York art and social patron. He lived on Staten Island, where Bement Avenue commemorates his name.


: The load of a computer is an important metric and is useful in many applications, such as balanc ing load across heterogeneous computers. In this paper, a new metric for characterizing the load of a uniprocessor computer is studied. This metric is defined as a ratio of the average waiting time experienced by computing jobs to the average idle time of the processor. The definition of the new load metric is based on two important observations: 1) the average idle time between serving consecutive computing tasks shrinks as the load becomes heavier; 2) the average waiting time experienced by computing jobs increases as the load becomes heavier. The ability of the new load metric is examined by making this load metric serve as the criteria for bal ancing loads across multiple uniprocessor systems with different service capabilities. Compared to the ability of the traditional load metric—the average utilization, the evaluation results suggest that adoption of the new load metric serves to balance the load more evenly than the average utilization.


Based in the heart of Manchester, Nexus Solicitors provides clients with a personal service across business and private matters.
No matter is too big or small for us. Our team of experts really care about your welfare whether it's a business or personal cause.
Allowing you more time to focus on what really matters.
Helping you manage whatever personal issue you may face.
Backed by 18 years experience.
We're your friend as well as adviser.
Whether you have something specific you'd like to discuss or are unsure of how we can help you, fill out the form and we'll be in touch.
We offer a range of services for your business, whatever your requirement from banking and finance, commercial contracts, to dispute resolution and litigation.
We advise on a number of disciplines including initial funding and structuring, mergers and acquisitions, disposals, private equity and public company transactions.
We provide quality, cost effective and commercially pragmatic advice on agency, supply and distribution agreements, including those governed by the Commercial Agents Regulations. Our work in this area spans many sectors and disciplines.
Our lawyers advise in many corporate related actions, with particular expertise in shareholder and partnership actions, derivative actions, breaches of share and other warranties and similar disputes arising out of corporate or commercial transactions.
We offer a personal approach when taking care of issues you're facing. We handle anything from employment problems to property law.
Nexus solicitors represents clients in relation to every aspect of employment law without bias or discrimination.
Family and divorce issues can be a grueling process and you certainly shouldn't have to face it alone. We provide sensitive advice on both parts to ensure you make the best decision.
Tenancy Deposits – Are You Protected?
Looking for a professional, understanding and transparent representative?


Children should bring a packed lunch and drink from home each day.
On a fortnightly Fridays we offer a Sausage Sizzle for the children to buy if they wish. Funds from the sale of sausages are used to support the biennial school camp for year 6 and 7 students.
We also offer Sushi every second Thursday and alternative Thursday Teriyaki Chicken Bento.
This must be ordered in advance and we send out a reminder email that week. Check the school diary for availability.
A fortnightly school newsletter is emailed on Wednesdays, and published in the News & Events page of the web site.
Class teachers also send regular letters home (at the start of each term) to keep families informed of events that affect their children.
You can always check out the class blogs which are regularly updated and these are found HERE or by looking under the Class Blogs heading at the top of this page.
Please advise the school of any changes of address and/or telephone, cell phone or work numbers. It is vital that we can contact you in case of an emergency.
To make this as easy as possible, you are able to update your information HERE, or simply stop by the school office and let them know.