Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.


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.

1.	It 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. 
2.	The 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. 
3.	As 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.

In 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. 

limitations_and_societal_impact: The paper does not contain this part.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 
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.

These 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?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduce the first complete theoretical analysis of minibatch sampling using determinantal point processes in the context of (batched) stochastic gradient descent.

The 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:
1) 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.
2) 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.

The 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.

Finally, 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.
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).

Quality: This paper is of high quality, well positioned within the relevant literature, and introduces results of extreme relevance to the machine learning community.

Clarity: 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.

Significance: 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.

I would've liked to see a comparison to importance sampling.

Questions & clarifications
- 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?

- 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)?

- 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$.

limitations_and_societal_impact: No negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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.

A 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.

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_title: null

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)