Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper aims to improve the quality of the parametric bootstrap when the number of particles is limited. It does so by constructing a small collection of "centroids" that well-approximate the ideal bootstrap distribution on parameter space in a certain Wasserstein distance. Practically, the centroids are constructed by gradient descent with respect to a loss function involving the negative log-likelihood. Theoretically, this paper shows that the surrogate loss converges to the Wasserstein distance under some assumptions. Empirically, this paper applies the centroid methodology to confidence interval construction, contextual bandits, the bootstrap deep q-network, and ensemble learning .
main_review: **Strengths:**

- This work seeks to improve on computational aspects of the bootstrap, a fundamental and popular statistical method

- The derivation of the centroid method involves interesting ideas from optimal transport and a natural choice of surrogate loss.

- The applications seem well-chosen and relevant to modern machine learning

**Concerns:**

- I could not understand how the centroid method is applied in the contextual bandit, bootstrap DQN, and ensemble learning experiments. In the "Contextual bandits" section below I have several questions and comments that I hope will clear up my confusion and suggest ways to improve the presentation.

- The training overhead should not be completely ignored since the main motivation of this paper is computational. It would strengthen the paper to make note of the training overhead for all experiments in addition to the note in Appendix C.6. 

- Although the topic of this paper is bootstrapping, there is no evaluation of uncertainty for the real-data experiments.

- The presentation of the algorithm in **Practical algorithm** is difficult to follow because the run-time analysis and algorithm description are all written together. One suggestion to improve readability is to move the Algorithm Box here, give a short description of the practical algorithm in words, and then justify its running time.

- The derivation and theory are essentially limited to concave log-likelihoods (otherwise, the Wasserstein distance here is not a proper distance), though the algorithm may be implemented for general losses

- Bootstrap DQN is limited to 2 and 5 models. This makes it hard to see trends.

**Contextual bandits**

- It seems that each model has a parameter (that of a neural net), and so the number of models is exactly the number of particles. Is that correct? This was not clear to me from the text.

- It seems that the centroid algorithm applied to the collection of parameters of the models. Is this correct? This should be explicitly stated.

- If the previous bullet is correct, what datapoints are input to the centroid algorithm. Is it only the datapoints in the memory buffer? Or a resampling according to $w$? What datapoints are used for the centroid degeneration-prevention step?

- Is the centroid method applied after every 50 contexts? Further, does one first learn the parameters of each model using SGD and then use these learned parameters as the initialization for the centroid method? 

- Once answered, these points can be included in the main text. More generally, for each experiment, a precise step-by-step explanation of how the centroid method is used would greatly improve readability.

**Further comments**

- The paper *Wasserstein measure coresets* of Claici, Genevay, and Solomon considers a similar methodology with a different loss function and different applications from this paper. In general, the constructions in the paper under review are reminiscent of the literature on coresets (cf *Introduction to Core-sets: an Updated Survey* by Feldman).

- pg 3: Equation (3) is abrupt and not explained. It seems to rely on some important theorems from optimal transport (cf Lemmas 3.1 and 3.2 in Canas--Rosasco '12). More justification here is needed.

**Minor issues**

- In the Tables 1,2,3, please write the value of the best performing method in boldface for readability.

- pg 5, typo: estiblish

- pg 5, "... can be done using classic techniques in non-convex optimization..." This needs further elaboration or should be removed.

- pg 6: Theorems 1 and 2 are asymptotic in nature, and this should be mentioned again in the theorem statements

- pg 7, "Asymptotics when $m$ grows": The discussion below Proposition 7 of Weed--Bach '19 implies that for absolutely continuous measures, the iid particle measure approximately attains the rate $m^{-1/d}$, which is minimax optimal. Thus as $m \to \infty$, it is not possible to beat iid sampling. This is also supported by Figure 2. 

- pg 8, Figure 3: Interestingly, there is a period where centroid 2-head outperforms centroid 5-head. Why does this happen?

- pg 9, "However, those approaches are not applicable..." This is not true. The methods of Chen et al (and the coreset literature more broadly) work for a given dataset.

- pg 10: Please used published versions in the bibliography when possible, not just arxiv links. Also the phrase "et al" appears in the bibliography and should be removed.

- pg 13, Proof of Theorem 1: Please give a reference for the claim that the MLE is subGaussian. This should require some assumptions (note: it is not implied by asymptotic normality).

- pg 16, Algorithm 1: Why is there a loop over t' in inner-iters? I did not see any dependence on t'. 

- pg 16, Methods to construct confidence interval: the $\hat \rho_\pi$'s should be $\tilde \rho_\pi$'s


summary_of_the_review: I like the topic and motivation of this paper, and the derivation of the method is interesting. However, the most important part of this paper is the evaluation. This paper needs to explain better how the algorithm is applied in real-data scenarios. Until it can be clarified what precisely is happening in the experimental sections, it is difficult for me to judge effectiveness of this method. I am also concerned that there are no uncertainty estimates in the real-data experiments and only a few run-times are reported. It seems that careful revision is needed for this paper to be ready for publication, and that is the main reason for my score.  

========================================

**Update on review (11/29)**

The algorithm used in the real-data experiments seems to differ in a significant way from the centroid method derived in Section 3 (see my discussion with the authors). Further, these differences can only be ascertained by a careful read of the Appendix, which leads to a lack of clarity on what is being proposed. I think this paper needs a better explanation of how the methodology used in the real-data experiments matches with the initial derivation of the centroid method. I do think that both algorithms are quite interesting and that proper attention to both of them would improve this paper. 

I also think that more care should be taken to report the training times for all of the experiments. I understand that training time is not the main focus of the paper, but carefully reporting run-times/overheads would clarify to what extent the centroid method is practical. 

Overall, I think that improving the quality of bootstrap is a promising idea that should be further explored, and this paper takes an interesting route toward doing so. However, I feel that this work needs to be further developed to be ready for publication, so I have kept my initial scores the same.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a way to optimise the choice of Bootstrap samples so as to obtain efficient inference with smaller number of such samples. While traditional Bootstrap requires the need to use a large number of samples to approximate the target distribution, the authors propose a combination of k-means type algorithm is association with Bootstrapping to achieve the goal. In addition, they provide a theoretical justification for the method along with providing some experimental evaluation .
main_review: The major points can be summarised as follows:
1. While the concept and idea is nice, I think they are not entirely novel. k-means has often been used as a trick to summarise distributions with smaller samples. There are other methods such as Coresets (https://arxiv.org/abs/1906.03329) which also provide distributional approximations with smaller samples. How does this method compare to these prevailing methods?  This can be discussed in detail with either experimental or theoretical justifications. While the authors do a good job in terms of depicting the idea, these comparisons I find are a bit lacking. Suppose the data is derived from a mixture model. In this case, does this method capture the relevant modes (assuming the number of components is known). Do the obtained centroids provide a consistent estimation of the mixture component parameters? Can you provide an experiment to verify that? How much do the results depend on the starting seeds?

 2. Additionally, I cannot quite understand some of the intuition in the paper. For example, do the results (Theorem 2) hold for any distribution $\pi$ on $w$ or is this specific to the multinomial distribution? Does the approximation in Eq. 5 hold for any $w$. It is unclear to me what the intuition is behind such a logic? I do not understand why $\mathscr{L}_{\infty} \approx  \mathscr{L}_w$, or why the approximation for the corresponding estimators of $\theta$ hold. I think the paper tries to argue that different centroids of the Bootstrap samples capture different regions of the distribution, but I do not completely follow the theoretical justification that is provided.

3. The primary usage of Bayesian methodology is to provide uncertainty quantification for small data sizes. In that respect, I feel it is unfair to compare the current method to Bayesian approaches. 

4. How do the approximation of centroids vary ? For example if you have a mixture of a Cauchy and a Gaussian distribution, the modes of the distributions converge at different rates. As a result some more noisy data may not even reveal an interpretable centroid unless the datasize is sufficiently large. How do you plan to alleviate this issue?


summary_of_the_review: I think the paper is understandable and has a nice idea though not novel and needs a lot of clarification and revision before being accepted for publication
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Bootstrap is a versatile technique for uncertainty quantification and a viable alternative to Bayesian inference, but it can be expensive in terms of memory and computations. With a small number of particles/samples, bootstrap may perform poorly. As a consequence, bootstrap can be quite expensive and even unaffordable for deep learning problems with huge models. The paper proposes to address the question of improving the accuracy of bootstrap inference when the number of particles is limited. 

The approach is to minimize the Wasserstein distance between the ideal bootstrap distribution (denoted by $\rho_{\pi}$ in the paper) and a probability mass mass function supported on a small number of particles (called "centroids" in the paper). The exposition given around equations (3) and (4) plausible decomposes this problem into a coupled two-stage optimization problem. Unfortunately, $\rho_{\pi}$ is not observe, which is a major challenge to this conceptual development. The paper then relies on the fact that in standard problems when training data size is large, the bootstrap obtains properties similar (or identical) to the MLE or Bayes estimators, and the algorithmic steps are base don this framework.

main_review: Strengths: 

1) The problem is important and well-stated. The paper is clearly written.
2) The arguments justifying the algorithmic steps and the theory of Section~4 are plausible for the most commonly observed scenario in data sciences when hyperparameter dimension is fixed (and low). 

Weakness:

1) I am surprised that the hyperparameter dimension plays no roll in either the assumptions or the results of Section4. This is not the case for several of the cited references, and requires some clarification. For example, when hyperparameter dimension grows, Assumption~2 may not be valid without proper control over $d$, or additional assumptions (like sparsity of $\theta$). If the authors are working in the fixed-$d$ case, that should be clarified.

2) The algorithm lacks clarity. In particular, I am confused about exactly how the \textit{spread} of $\rho_{\pi}$ and its tails and extremes are being captured. Considerable additional discussions and clarifications are needed about this. 

3) How is $m$ chosen? Is this optimized in any way? It seems that Algorithm~1 of page 16 can be very sensitive to the choice of $m$. The algorithm also requires (at least) $M$ iid draws from $\pi$, so what is $M$ and how is this chosen? 


4) The algorithm/theory seems to require that the randomly-weighted log-likelihood $L_w$ should have sufficient smoothness properties near each centroid. Since centroids can be anywhere in the support of the hyperparameter, this requires strong conditions on $L_w$. One important property that seems to be needed is a locally quadratic behavior, ie, equation (5) needs to hold at every centroid. This seems to be a very strong condition. This is different from the traditional bootstrap conditions, where similar properties are needed only near the true value of the hyperparameter. 


5) Bootstrap is computationally expensive but also embarrassingly parallel. So, while still challenging in applications where there is limited computational resource, the computational burden of bootstrap may be expected to  become less of an issue with time. 

6) 2 lines after equation (4): "We emphasize that the optimal solution to two-stage learning is guaranteed to be the global minimizer of the loss in (2)." Where are you getting this from? 

7) I would guess that different centroids "stabilize" at different rates, and some centroids are much easier to locate than others. The algorithm seems to treat all centroids equally. Some discussion would be helpful about this. 

summary_of_the_review: The bootstrap is an extremely versatile technique, and is applicable in many situations, for example, with dependent data, on extremes, cases where standard frequentist or Bayesian asymptotics may not hold, and so on. While the present papers approach does not cover many of these bases, it does address the most commonly observed scenario: where standard mathematical/calculus/probabilistic properties hold (like interchanges of limits and integrals etc) and the hyperparameter estimator has a limiting Gaussian distribution due to the Central Limit Theorem. This is the most important special case to tackle, and as an early attempt to address the computational aspects of bootstrap, I think this paper is showing quite a bit of promise.


Despite the long list of weaknesses mentioned above,  my initial feeling about this paper is quite positive. Bootstrap is a very strong alternative to Bayesian or ad hoc methods used in ML, and this paper may be a breakthrough to address the computational challenges of bootstrap. I am excited about this, but would appreciate considerable additional details and clarifications. 


Revised comments: I thank the authors for the updates on the paper and their detailed responses. While I am a strong enthusiast of the bootstrap and I like this paper, I still have several concerns. It would take a major revision to address these concerns, so I am leaving my rating unchanged. 

1) The bootstrap essentially is a technique for uncertaintly quantification, so it's main computational burden is during training: I am not convinced about the realism or practicality of the authors' premise that there is unlimited training resouce/time but limited time during inference. In any case, during inference, the bootstrap is just a bunch of forward model runs: for example in deep learning, it would be just evaluating what we get from the architecture for a given set of weights and biases. It certainly helps if the "set of weights and biases" is small, but I am struggling to find a realistic example where it is hard to simply run the code for a given architecutre with given weights and biases and test set features. 

2) The roles of m and M need to be studied more carefully. 

3) I am not convinced that the centroid method sufficiently addresses the issue of variability or stochasticity in the hyperparameter space. We need proper studies that the tails of the distribution are adequtely captured using the centroids method, which will take more work than what the paper currently contains.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an acceleration technique for bootstrap. Here a bootstrap particle corresponds to a machine learning model and for a large number of bootstrap particles, a huge computational cost is incurred. The authors propose using a k-means-like centroid approximation which optimizes a set of centroids (each of which corresponds to a machine learning model) minimizing a data-dependent Wasserstein distance.
main_review: ##########################################################################

Summary:
This paper offers an interesting approach to scaling bootstrapping which is applicable to many machine learning problems. While it is not a perfect method, I think a paper providing a thorough evaluation of this approach and the previous ones is worthy of publication, if done properly.
 

##########################################################################

Reasons for score: 
For the most part, the paper is written clearly but some of the crucial comparisons against previous approaches (see below) are missing. I am slightly leaning toward reject since the paper probably needs more work. While the algorithm is novel, it is unclear how much benefit it would offer above previous approaches. I am open to adjusting this score in the rebuttal stage, pending the authors' responses.


##########################################################################

Pros: 

 
1. The paper addresses an interesting computational problem applicable to many models in machine learning. The algorithm is simple to implement and to understand.

2. Experiments cover interesting machine learning use cases, e.g. contextual bandit, reinforcement learning, confidence interval estimation.
 

##########################################################################

Cons: 

 
1. It is unclear how much benefit the new methodology offers over the previous ones, e.g. in terms of model accuracy improvement.
It is presumed that the iterative nature of the algorithm incurs many model updates and model loss evaluations in the inner loop.

2. Comparison against previous approaches except for vanilla bootstrap are largely missing. It would be beneficial to comment on how this method compares against m-out-of-n bootstrap and bag-of-little bootstraps. The authors mention that both of these methods are inherently slower (page 9, Section 6). However, these methods are highly parallelizable algorithms and they are worthy of discussion (unlike the iterative algorithm proposed in this paper).

3. As stated in the appendix, the motivation of the paper is not to decrease the training cost but reduce the memory cost and the computational cost for inference. How much compression can be achieved in terms of memory? It seems the study on establishing the relationship between optimal m and n is for future work but it is a bit unclear from the experiments at least empirically.
 
4. How big is the dataset (n) in the experiments? Any comment on how the proposed method performs for ensemble tree methods, as the experiments discuss primarily neural networks? Please also comment on the dimensionality of theta in each experiment setting.

5. On a related above: how would the initialization of theta work for a tree based method?

##########################################################################

Questions during rebuttal period: 

 
Please provide clarifications for the points in the previous section.

 

#########################################################################

Some typos: 

- page 19: bootstrap partical -> bootstrap particle

summary_of_the_review: It is overall an interesting paper providing an acceleration technique for bootstrap - but I would suggest the following:
1. Provide a clarification in the beginning of this paper, rather than in the appendix, that this paper focuses on "model compression", hence inference time improvement and model size management, rather than reducing the training time.

2. Clarify experimental setting parameters (e.g. size of the dataset, size of theta, etc.). See above for details.

3. Comment on comparison vs other previous bootstrap variants.
review_title: null

Meta-review: The submission aims to improve the quality of the bootstrap when the number of samples is small.  It does so by gradient descent on the to approximate the ideal bootstrap in Wasserstein distance.  The submission combines a nice set of methodologies, and aims to address an interesting statistical problem in a principled way.  The reviewers were unanimous in their opinion that the submission falls below the threshold for acceptance to ICLR.  It was revealed in post rebuttal discussion with reviewer y4AP that they wish to retain a reject recommendation due to a lack of clarity in the methodology even after author comments.  The review details specific issues that can eventually be clarified in a revision for submission to another venue.
Decision: Reject