Centroid Approximation for Bootstrap
Authors: Mao Ye
qiang liu
Venue: ICLR 2022 Submitted (2022)
Keywords: bootstrap
centroid approximation
uncertainty

Abstract: Bootstrap is a principled and powerful frequentist statistical tool for uncertainty quantification. Unfortunately, standard bootstrap methods are computationally intensive due to the need of drawing a large i.i.d. bootstrap sample to approximate the ideal bootstrap distribution; this largely hinders their application in large-scale machine learning, especially deep learning problems. In this work, we propose an efficient method to explicitly \emph{optimize} a small set of high quality  ``centroid'' points to better approximate the ideal bootstrap distribution. We achieve this by minimizing a simple objective function that is asymptotically equivalent to the Wasserstein distance to the ideal bootstrap distribution. This allows us to provide an accurate estimation of uncertainty with a small number of bootstrap centroids,  outperforming the naive i.i.d. sampling approach. Empirically, we show that our method can boost the performance of bootstrap in a variety of applications.

Under review as a conference paper at ICLR 2022
CENTROID APPROXIMATION FOR BOOTSTRAP
Anonymous authors
Paper under double-blind review
ABSTRACT
Bootstrap is principled and powerful frequentist statistical tool for uncertainty quantification. Unfortunately, standard bootstrap methods are computationally intensive due to the need of drawing large i.i.d. bootstrap sample to approximate the ideal bootstrap distribution; this largely hinders their application in large-scale machine learning, especially deep learning problems. In this work, propose an efficient method to explicitly optimize small set of high quality "centroid" points to better approximate the ideal bootstrap distribution. We achieve this by minimizing a simple objective function that is asymptotically equivalent to the Wasserstein distance to the ideal bootstrap distribution. This allows us to provide an accurate estimation of uncertainty with a small number of bootstrap centroids, outperforming the naive i.i.d. sampling approach. Empirically, we show that our method can boost the performance of bootstrap in variety of applications.
INTRODUCTION
Bootstrap is a simple and principled frequentist uncertainty quantification tool and can be flexibly applied to obtain data uncertainty estimation with strong theoretical guarantees (Hall et al., 1988; Austern & Syrgkamis, 2020; Chatterjee et al., 2005; Cheng et al., 2010). In particular, when combined with the maximum likelihood estimator more general M-estimators, bootstrap provides general- purpose, plug-and-play non-parametric inference framework for general probabilistic models without case-by-case derivations; this makes it promising frequentist alternative to Bayesian inference.
However, the standard bootstrap inference is highly expensive in both computation and memory as typically requires drawing a large number! of i.i.d. bootstrap particles (samples) obtain accurate uncertainty estimation. In the context of this paper, as each bootstrap particle/sample/centoood is With a small
machine learning model, we might directly call a model as particl/ssmppl/ccnntre number of particles, bootstrap may perform poorly. As a consequence, when applied to deep learning. we need store large number of neural networks and feed the input into tremendous number of networks every time we make inference, which can be quite expensive and even unaffordable for deep learning problems with huge models?. For example, in autonomous driving applications, our device can only store limited number of models and we need to make decisions within short time, which makes the standard bootstrap with a large number of models no more feasible. Typical ensemble methods in deep learning, such Lakshminarayanan et al. (2017); Huang et al. (2017); Vyas et al. (2018); Maddox et al. (2019); Liu & Wang (2016), can only afford to use small number (e.g., less than 20) of models.
Therefore, to make bootstrap more accessible in modern machine learning, is essential to develop new approaches that break the key computation and memory barriers mentioned above. This paper aims to improve the bootstrap when the resource at inference is limited. We are motivated to consider the following problem:
How to improve the accuracy of bootstrap inference when the number of particles is limited?
We attack this challenge by presenting efficient centroid approximation for bootstrap. Our method replaces the i.i.d. bootstrap particles with set of carefully optimized centroid particles that are
For example, thousands of, as suggested by Statistics textbooks such as Wasserman (2013). While training cost is an extra burden, it is small compared with the cost of making prediction as we only need train the model once but make countless predictions deployment.

---

Under review as a conference paper at ICLR 2022
guaranteed to provide accurate and compact approximation to the ideal bootstrap distribution that only a smaller number of particles is needed to obtain good performance.
Our method is based on minimizing specially designed objective function that is asymptotically equivalent to the Wasserstein distance between the ideal bootstrap distribution and the particle distribution formed by the learned centroids. During the training, each centroid adjusts its location being aware of the locations of the others so that centroids are diversified and well distributed on the domain. Our method similar to doing K-means on the ideal bootstrap distribution, finding K representative centroids that well represent K separate parts of the target distribution 's domain in an optimal way. As centroids are optimized better approximate the distribution, our approach naturally improves over the vanilla bootstrap with i.i.d. particles. See Figure for illustration.
Empirically, we apply the centroid approximation method various applications. including confi- dence interval estimation (DiCiccio et al., 1996), bootstrap method for contextual bandit (Riquelm al., 2018), bootstrap deep Q-network (Osband et al., 2016) and bagging method (Breiman, 1996) for neural networks. We find that our method consistently improves over the standard bootstrap.
Notation We use ||-|| to represent the E norm for a vector and the operator norm for a matrix. We denote the integer set {1, 2, ..... N by [N]. Given any m, we define the probability simplex C. {[01...., Um] IR" U, O, vi [m] and Lie(m] 1s = 1]. For symmetric ma- trix M, we denote its minimal eigenvalue by Amin (M). For a positive-definite matrix M, M A A, then we denote A by M1/2, We de- note the Wasserstein distance between two distri- bution f1 and p2 by W2 P2]. We use and to denote the conventional big-O and small- notation and use Op to denote the stochastic
2002
Figure I: The solid lines represent the density of the target distribution. Left figure: Typical i.i.d. particles that are randomly distributed on the do- main. Right figure: The learned diversified cen- troids that are well distributed on the domain. The centroids partition the domain into several disjoint regions (separated by the dashed lines in the figure) and each centroid can be viewed as the 'K-means" center of the region it belongs to.
boundedness. We use to denote convergence in distribution.
BACKGROUND
Suppose we have a model fa parameterized by in a parameter space θ C Rd. Let |= C X' be training set with data points on X. Assume É(x, fe) is the negative ligliiill of data point with model fe. A standard approach to estimate is maximum likelihood estimator (MLE), which minimizes the negative log-likelihood function (loss) over the training set
arg min C()), DEE
((0) = Σ. ((xi, ((1x,,fo) fe)/n.
Here the MLE provides point estimation without any information on the data uncertainty. Bootstrap is simple and effective frequentist method to quantify the uncertainty. The bootstrap loss is randomly perturbed loss defined as
Lw = -i, w,l,,, fo)/n,
where [W1, ... Wn) ]T is of random weights of data points drawn from distribution A typical choice of is the multinomial distribution with uniform probability, which corresponds to resampling on the training set with replacement. Given w, one can calculate its associated bootstrap particle by minimizing the bootstrap loss:
0, = arg min (O). BEB
Let Pr be the distribution of &w when Bootstrap theory indicates that quantify the data uncertainty of & or any function g(0) using Pr. We call Pr the ideal bootstrap distribution and the main object we want to approximate.
2

---

Under review as a conference paper at ICLR 2022
Denote 89 the delta measure centered 0. Standard bootstrap method approximates Pr by the particle distribution (.) Σ}=1 ()/m formed by i.i.d. particles (0w, ),= which
can be obtained by drawing m i.i.d. weights {w from π and calculating each 0w, based on (1). However, for deep learning applications. discussed in the introduction, storing and making inference using a large number m of bootstrap particles can be quite expensive. On the other hand, m small, Pr tends be poor approximation of pr- In this paper, we aim to improve the approximation of the particle distribution when is small.
3 METHOD
Our idea is simple. Instead of using i.i.d. particles, in which the location of each particle is independent from that of the others, we try to actively optimize the location of each particle so that particles are diversified, better distributed and eventually providing a particle distribution with improved approximation accuracy. natural way to achieve this goal is to explicitly optimize set of points {0, | (called centroids) jointly such that the Wasserstein distance between Px and the induced particle distribution minimized:
{0}. 1ز = arg
min Om EB, [m].e..
W/
(2)
Here we consider a Wasserstein distance W2 equipped with a special data-dependent distance metric ||- Il that will be introduced later in (5). We note that here we also optimize the probability weights {uz m of the centroids. Finding the optimal centroids and probability weights can be decomposed into two steps: the centroid learning phase and the probability weights learning phase, based on the facts in (3,4).
W
Ej 60;, Pm Jz. (10)) where J= [=(10)))))==B--- minje[mm] 10, - d 116] (3)
Here (3) implies that, find the optimal particle distribution in (2), we start with the centroid learning phase where we only need to optimize the centroids. It can be achieved by minimizing Jxx (+0, (=1)) which is the averaged distance of bootstrap particles to their closest centroid. After we obtain the optimal centroids, the optimal probability weights can be learned by (4):
03 / /Ee [m] 02 where 0j w (j arg min
i l1:)
(4)
Here v is the proportion of bootstrap particles that are closest to the centroid j. We emphasize that the optimal solution two-stage learning is guaranteed to be the global minimizer of the loss in (2) (see Lemma 3.1 and 3.2 in Canas & Rosasco (2012)).
However, the key issue is that the losses in both (2. 3) can not be computed in practice, as they require us to access Pr (i.e., obtain & first in order to calculate the loss). To handle this issue, we seek an casy-to-compute surrogate loss. Our idea is based on the following observation. Assuming the size of training data large, which is usually the case in deep learning, we can expect that On will be centered around a small region². It implies that we should search the centroid in this small region. Notice that when 0 is close to d... based Taylor approximation, have
Lao (0) Luo (ōw) + VJ LuD (0w (0- )m)) + 1/2(0 0..) Co (0w)(( -0w)) Lox (0o) + 1/2 0m Ib: where |IVI : V V2 (On)
(5) Here (0) == E,l(x, f fo) denotes the population loss; 0g is the minimizer of (0). In (5), we use the facts" that V Lv (0w)) )= 0; and with large training set, the empirical distribution >i. day /n well approximates the whole data population, and hence the bootstrap resampling distribution, i.e. El,,0,02./ /n on the empirical distribution also well approximates the whole data population. This implies that Lw Ri fox (.) and V2 Re (-). As the loss are close to each other, their minimizers are also close 0w R 0g- Since Lo (0v) is some (unknown) constant independent with 0, we can replace the ||0, o. 1 in (3) by Lw (0,) as it only adds some constant into the loss.
"This can he formally characterized by central limit theorem as discussed in Section 4. We defer the detailed analysis to Section 4.
3

---

Under review as a conference paper at ICLR 2022
Intuitively, expect that the centroid closest to fw is the one that gives the smallest loss ww- motivates us to learn the centroids via the modified centroid learning phase:
(0 = arg min Ew-s [miitee[m]] Lo (0,)] 0m. E6
(6)
Similarly, the optimal probability weights can be learned via the modified weight learning phase:
oj - -0 / üg where oj = Pwww (j E arg min
We note that here we slightly abuse the notation of 8 and uy in (3,4) and (6,7) for simplification. In the later context, 07 and 0z are used based on their definitions in (6,7).
Connection to K-means By viewing the target distribution as a set of particles that we want to cluster, in K-means clustering, each centroid (i.e., K-means center) represents one of the K disjoint groups² of particles, which is formed by assigning each particle in the whole set to the closest centroid among all the K centroids. K-means learns the optimal K centroids in the way that they can best approximate the whole set. The "closeness' for assigning the particles is measured by the distance between the two points. As pointed out by Canas & Rosasco (2012), K-means essentially searches the optimal particle distribution formed by the K centroids that minimizes its Wasserstein distance to the target distribution. Our centroid approximation idea follows the same fashion of clustering but our key innovation is to measure the 'closeness' by examining the bootstrap loss of the centroids so that we can still learn the optimal centroids without obtaining the i.idd bootstrap particles first. We also point out that, while share the same objective K-means, the optimization algorithms differ. The Expectation- wwwitattionMMMiiiiia Maximization type of algorithm used by K-means is not applicable to our scenario.
Comparing with Other Particle Improving Approach Intuitively, from high level abstracted perspective, we provide an approach to use K-means type of idea to improve the particle quality without accessing to the true target distribution. This is the key differentiator of this work to other approaches that improve the particle quality, as they all require to access the target distribution. For example Claici et al. (2018) requires that sampling from target distribution is cheap and easy. Chen et al. (2012; 201 8a): Campbell& & Beronov (2019) need to access the logarithm of the probability density function of the target distribution. In our problem, neither sampling from the target distribution is cheap nor the logarithm of the probability density function is available, making those approaches not more applicable.
3.1 TRAINING
The optimization of (6) can be solved by gradient descent. Suppose (t) is the j-th centroid at iteration We initialize (0) (0));-) by sampling from P. and iteration we update 6; by applying the gradient descent on the loss in (6), which yields
1) (t) (t) (i)(0
(8)
I (0)())) Volwws [ut E uw (0000)00000000
where we define the index of the closest centroid to particle O.. as tw (1) arg minje[m] C.v (0) (1)
and (t) P Pwwxx (j E ww (t)) denotes the probability that centroid is the one that gives the lowest bootstrap loss. The denominator vz (t) in s(0) (t)) is optional. However, notice that the magnitude of numerator in (t) decays with larger m, which might require an adjustment of the learning rate when m changes. This adjustment can be avoided by rescaling with o (t).
We note that (0)) is just i..d. bootstrap particles which is not optimal for approximation and our algorithm can be viewed as an approach for refining the m particles by solving (6). In practice, we find that can simply use random initialization (e.g., draw A from some Gaussian distribution) instead.
Centroid Degeneration Phenomenon Naively applying the updating rule (8) may cause a degenera- tion phenomenon: When a centroid happens to give considerably worse performance than others, which can be caused by the stochasticity of gradient or worse initialization, the performance of this centroid will remain considerably worse throughout the optimization. The reason is simple. As this
i.c. the regions separated by the dashed lines in the right plot of Figure
4

---

Under review as a conference paper at ICLR 2022
centroid (e.g. (t) gives considerably worse performance, the probability that it gives the lowest bootstrap loss, i.., v/ (t), is small. As consequence, the gradient that updates this centroid is only based on aggregating information from a small low-density region of π and hence can be unstable and further degrades this centroid. Note that this mechanism is self-reinforced since when this centroid cannot be effectively improved in the current iteration, it faces the same issue in the next one. As a result, this centroid is always significantly worse than the others.
We call this undesirable phenomenon centroid degemeration and we want to prevent this phenomenon because when it happens, have centroid that is not representative and contributes less to approximating Px- We solve this issue with a simple solution and here is the intuition. The reason that a centroid degenerates lies in that this centroid is far from the good region where gives good performance. And when this happens, we should push the centroid to move towards this good region, which can be achieved by using the common gradient over the whole training data. Specifically, we define a threshold 7 indicating centroid j is degenerated if vz (1) Y And when it happens, we update using the common gradient over the whole data:
07 + 1) < (7()) E, (o)(
In section 4, we give theoretical analysis on why this modification is important and able to solve the centroid degencration issue.
Practical Algorithm In practice, we estimate the gradient by replacing the expectation over w ~ I MM in (8) with averaging over M i.i.d. samples (wo, J h= drawn from
(0) EM [T] E uw (t) (0)
(10)
Σ Iíj E Vann (1)
We emphasize that here Vw, and Lu for all we be computed very cheaply, enabling to use very large M to reduce the error of gradient estimation. Specifically, at iteration i, for each j E [m]. first calculate
L (1) = fo;(s)) Soj (o) E R",
(11)
which is the vector encodes the loss of centroid at each data point. This procedure does not introduce any extra computational overhead compared with standard gradient descent. After that, the bootstrap
loss of centroid j can be computed cheaply by L (f) w L(0} (t)). Similarly, it is cheap to obtain Uwn. by
Uany (1) arg min w) (L) jE[m)
(12)
Taking the modified updating rule introduced to prevent the centroid degeneration phenomenon into account, we update 0j (t) by (] + + (t) ())(0((t), where
((0)) = ((0)(t)) voL(O)()) otherwise.
if i Uuws (t) = j}/M >
(13)
Notice that as as (() is pre-computed, calculating Lv.. (0) for many (e.g., M) different WA is almost free, since it only requires a simple matrix multiplication with ((nM) complexity. Similarly, calculating Man, (1) is also very cheap. In practical implementation, as Man, (1) do not change much within a few iterations, we can update Uww, (t) every a few iterations (c.g., every epoch). We can also replace the VoLws, (8) (t)) or VoL(O)(t) (t)) in (13) using mini-batch of data instead of the whole data, which leads to a stochastic gradient version of our algorithm. We refer readers to Algorithm 1 for the ideal updating and Algorithm 2 for the practical implementation in Appendix B for more details.
4 THEORY
Recall that, as discussed in (5), our approach relies on the intuition that bootstrap particles are nested in small region that we approximate the distance between the centroid and a bootstrap particle by the bootstrap loss of that centroid. The main goal of this section is to give a formal theoretical justification of this intuition.
5

---

Under review as a conference paper at ICLR 2022
Before proceed, clarify several important setups for establishing and interpreting the theoretical result. As discussed in the introduction, we are mainly interested in the scenerio that the number of available particles/centrrids m is small while the number of training data n is large, which motivates us to establish theoretical result the region of small m and large n. This is significantly different from conventional asymptotic analysis in which aim to show the behavior when consider the setting that the parameter dimension is fixed and does not scale with n.
co. We
We are mainly interested in characterizing the approximation of the proposed loss in (6) to the ideal loss in (3), given any small and fixed number m of centroids when n - cc. This justifies why the proposed centroid approximation method can be viewed as minimizing the Wasserstein distance between the particle distribution P and the target bootstrap distribution pr.
For simplicity, we build our analysis assuming the ideal update rule (8,9) is used. We start with the following main assumptions.
Assumption (Smoothness and boundedness) Assume that the following quantities are upper bounded by some constant < Oc:
e(x fo) 0,0,00,00, Vid((r,
Vil(z, fe,) VZ6(I, fo,)l.
1. max sup kJikEld FE
2. sup sup 0.0
110 02
3. sup xEX
4. sup ||@]| Age
Assumption is a standard regularity condition on the boundness and smoothness of the problem.
Assumption (Asymptotic normality) Assume vn (0.-- -6) 0) S S A) and vn 00) d
N (0, - where A is positive-definite matrix with the largest eigenvalue bounded.
Assumption 2 is higher level assumption on the asymptotic normality of the estimators. Such result is classic and can be derived with some weak and technical regularity conditions. See examples in Chatterjee et al. (2005); Cheng et al. (2010).
Assumption (On the global minimizer) Suppose that Amin (V)Co((0)) >
Assumption 3 is also standard showing the locally strongly convexity of the loss around the truth 0g-
Assumption (On the learning rate) Suppose that max, E OO
Assumption 4 assumes that the learning rate of the algorithm is sufficiently small such that its induced discretization error is not the dominating term.
The key challenge of our analysis is to show that our dynamics is B(0,, -ttabbe (defined below in Definition 1) for some small r, saying that {0] (1) stay in a small region that is close to Oo for any
iteration f. Combined with the property that O.p are also close to Og. the centroids and the bootstrap particles are close to each other and thus our approximation in (5) holds for all / > O. In this way, optimizing the centroids by minimizing our loss almost equivalent to optimizing the centroids by minimizing the Wasserstein distance.
Given some 0 E θ and r 2 0, we say our dynamics is B(0, r--stable if 2 0 and Vj E [m]. (t) e B(O,r), where B(8,r) r) = {0' 1|0 01 I r, O' e ) the ball with radius centered at
Definition
The key intuition to establish such B(0g, -t-ble result is to characterize that our optimization dynamics implicitly self-controiled: when some centroid approaches the boundary of B(0,, r), the updating mechanism automatically start to push the centroid to move towards the center of the region. Thus, all the centroids are within B((g, r) at initialization, they will alway stay in this region.
Thanks to assumption 2, 3, when the dataset is large, the landscape of our loss is locally strongly convex around fg. When a centroid j is at the boundary of B(0o, r). has ug (t) < and thus the
TThis implied by the asymptotic normality in assumption 2.

---

Under review as a conference paper at ICLR 2022
m 20
50
Vn 100
WL 200
Bootstrap
0.029
0.010
0.031 1 0.011
0.021 1 0.010
0.0171000011
Normal
Centroid
0.027
0.010
0.001 1 0.009
0.012 1 0.010
0.016 1 0.010
Bootstrap
0.101 + 0.013
0.036 - 0.011
0.021 = 0.010
0,014
a 0.9
Percentile
Centroid
0.081 0.012
0.021 + 0.010
0.020 - 0.010
0.015 + 0.010
Bootstrap
0.106 0.013
0.045 + 0.011
0.025 + 0.010
0.023 + 0.010
Pivotal
Centroid
0.046 0.011
0.013 0.009
0.011 + 0.010
0.020 + 0.010
Table I: Centroid approximation for confidence interval. The numbers in the table represent |ax de) where å is the estimated coverage probability. The errors bar is the standard deviation.
updating direction is the gradient of loss L. By the convexity, such gradient will push the centroid move towards the center of (6g, r) where the empirical minimizer locates at. On the other hand, for centroid j with v5 (t) 2 7, its updating direction aggregates information from sufficient data point and thus behaves similarly to that of the common gradient, pushing centroid to move towards the center with the centroid is not close to the center.
Theorem Under Assumptions 1-4 and suppose that we initialize 07 j e [m]] by sampling from Pa, given any m < oc and > O, when n is sufficiently large, we have
max sup [10 0o 1ool=Op(V// =Op(V(logn)/nn)
jE JElm) 120
Here the probability is laken w.r.t. training data.
Theorem implies our dynamics is B(00, (o.,ra)a -ttable with r. = O(ylogn/n)) The condition that (0) Ps i.id. can be replaced by the condition that 07 (0) is sufficiently close to 9g We need such condition uniformly bound the distance between 07 (f) and Oo at any iteration including the first one. Theorem implies that the approximation stated in (5) holds with high probability and hence the proposed loss in (6) is 'almost as good as' the ideal loss in (3).
Theorem 2 Under the same assumptions Theorem 1, given any < and y >> 0, when is sufficiently large, we have
Ewnn min Lw (0) E- min (t0](t) 1/Bl/2 Op( (logn)/n3//)) jElm)
sup
jE[m]
Here the probability is taken w.r.t training data and B is some constant independent from 03 (1) for any 2 0 and j E [m].
Asymptotics when also grows Although our main interest is the asymptotics with small, fixed m and growing we discuss here on asymptotics when m also grows. As shown in Section 3 and introduction, method can be viewed as an 'approximated" K-means on the target distribution. From Theorem 5.2 in Canas & Rosasco (2012), the particle distribution formed by the optimal centroids learned by K-means gives improved O(m - 1/d) convergence to any general target distribution in terms of Wasserstein distance, where is data dimension. In comparison, the particle distribution of i..d. sample only gives O(m 0(m-1/(2444)) 1/(2444) from Theorem 5.1 in Canas & Rosasco (2012). This implies that our approach potentially also has such a rate improvement. Note that the results in Canas & Rosasco (2012) are for general target distribution without any involves. To rigorously establish the large m asymptotic result for our problem, we need to study the joint limit of n and m. This is indeed very non-trivial: as discussed in Weed al. (2019) (i.e. Proposition 14), when - cc, the target distribution P. becomes a sharp Gaussian and the convergence rate of i.i.d. bootstrap particles will gradually improve to 0(m 1/2) (in a way that depends on n). It implies that when n >> m - oc, our improvement may become only constant level. We find establishing such theory is out the scope of this conference paper and leave it as future work.
5 EXPERIMENT
As discussed in the introduction, our main goal is to improve the quality of the particle distribution when only limited number of particles/centrrids is allowed, that use less particles at
7

---

Under review as a conference paper at ICLR 2022
10
Boolstrap
3282.1 72.82
3307.9 69.2
3311.6 79.3
3397.4 51.4
Mushroom
Centroid
3702.7 1 89.76
3723.1 78.7
3799.6 1 84.2
3796.9 = 36.1
Bootstrap
15643 1 6.4
1869.2 0:99.22::5 5.2
1877.2 1177.21::1
1877.0
Statlog
Centroid
1893.6 1 6.0
1892.6 + 3.6
1891.3 3.5
1892.6 2.8
Bootstrap
2255.77 77 58.45
2265.42 + 58.17
2269.33 + 56.36
2281.35 = 56.65
Financial
Centroid
2313.29 + 56.45
2315.32 - 56.75
2323.88 + 56.73
2325.54 = 56.005
Table 2: Results on the contextual bandit experiment. The numbers in the table represent the averaged reward with its standard deviation.
deployment, which reduces the memory consumption and the computational cost for making predic- tion. Thus, our experiment design will be focusing on comparing the testing performance of vanilla bootstrap and our centroid based approach when the same and small number of particles/centroids is used. We apply our method to four applications: confidence interval construction, bootstrap method in contextual bandit, bootstrapped deep Q-network and bagging. Due to space limit, we refer to Appendix C.4 for the bagging experiment, Appendix C.5 for ablation study on the importance of modifying the gradient overcome the centroid degeneration phenomenon. Although we are less interested in the computational cost of training, as discussed in Section 3, our method actually only introduces a little training computation overhead, which another advantage of our method. We draw analysis this aspect in Appendix C.6.
5.1 BOOTSTRAP CONFIDENEE INTERVAL
0.20
Wasserstein Dist
Bootstrap
We start with a classic application of bootstrap: confidence interval estimation for linear model with parameter 0. Fix confidence level a, we consider three ways to construct (two-sided) bootstrap confidence interval of 0: the Normal interval, the percentile interval and the pivotal interval. And we test 20, 50, 100, 200. For all experiments, we repeat with 1000 indepen- dent random trials. We consider the standard bootstrap as baseline. Detailed experimental setup are included in Appendix C.I.
0.15
Centroid
0.10
0.05
20
50
100
200
Num particles
Figure 2: Wasserstein distance between the particle distribution and the true bootstrap distribution w.r.t. the number of particles.
Figure 2 shows the Wasserstein distance be- tween the target distribution Pr and the empirical distributions obtained by (a) i.i.d. sampling Pr. (b) the proposed centroid approximation P The centroid approximation significantly reduces the Wasserstein distance by large margin. We then compare the quality of obtained confidence intervals, which is measured by the difference between the estimated coverage probability and the true confidence level, i.e., lá al (the lower the better). Here we only consider confidence intervals of the first coordinate of 0: 0g. Table summarizes the result with a 0.9. We see that using more particles generally able to improve the constructed confidence intervals. We also compare with two variants of standard bootstrap: Bayesian bootstrap (Rubin, 1981) and residual bootstrap (Efron, 1992). And we consider varying a = 0.8,0.95. 0.95. These results are included in Appendix C.I.
5.2 CENTROID APPROXIMATION FOR BOOTSTRAP METHOD CONTEXTUAL BANDIT
Contextual bandit is classic task in sequential decision making, in which accurately quantifying the model uncertainty is important in order to achieve good exploration-explee exploitation trade-off. As shown in Riquelme al. (2018), tracking the model uncertainty using bootstrap strong method for contextual bandit. However, it is costly to maintain a large number of bootstrap models and thus the number of models is typically within 10 (Osband et al., 2016). We find that applying the proposed centroid approximation here can significantly improve the performance. Riquelme et al. (2018) uses m = 3 bootstrap models and we give a more comprehensive evaluation with m = 3, 4.5. 5, 10. We consider three datasets: Mushroom, Statlog and Financial. We set y 0.5/m. We randomly generate 20 different context sequences, apply all the methods and report the averaged cumulative reward and its standard deviation. Table summarizes the result and note that large part of variance
8

---

Under review as a conference paper at ICLR 2022
250
Moving avg roward
200
Moving avg reward
150
100
30
Bootstrap 2-bxad
20
Bootstrap 2-head
Cenrroid-2-head
10
Centroid-2-head
-50
Boststrap Sootstrap-S-haad
Bootstrap S-head
Centroid-S-bac
Costroid-S-head
-100
100
150
200
250
300
350
400
30
40
60
70
90
Episodes
Episodes
Figure Results for Bootstrap DQN with centroid approximation experiment. Left: LunarLander-v2:
Right: Catcher-vO,
can be explained by different context sequences. All results in Table 2 are statistically significant under significant level 5% using matched pair t-test. Table 2 shows that using more bootstrap models generally improves the accumulated reward. And when using the same number of models, the proposed centroid approximation method consistently improves over standard bootstrap method. We refer readers to appendix C.2 for more information on the background and experiment.
5.3 CENTROID A APPROXIMATION FOR BOOTSTRAP DQN
"Efficient exploration is a major challenge for reinforcement learning (RL). Common dithering strate- gies such e-greedy do not carry temporally-extendee exploration, which leads to exponentially larger data requirements" (Osband et al., 2016). To tackle this issue, Osband et al. (2016) proposes the Bootstrapped Deep Q-Network (DQN). We apply centroid approximation to improve Boot- strapped DQN. We consider m = 2, and similar to the experimental setting in contextual bandit, we set 7 f.5 We consider two benchmark environments: LunarLander-v2 and Catcher-vO from GYM (Brockman et al., 2016) and PyGame learning environment (Tasfi, 2016). We conduct the experiment with independent random trails and report the averaged result with its standard deviation. We refer readers to Appendix C.3 for more background and other experiment details. result. For Lunarl andeerv22, Bootstrap DQN with 2 and 5 heads give similar performance but both converge to a less optimal model compared with the centroid approximation method. Centroid approximation method with and heads performs similarly convergence but centroid approximation method with 5 heads is able to converge faster than 2-head model and thus has lower regret, For Catcher-vO, adding more heads to the model able to improve the performance for both methods. The proposed centroid approximation consistently improves over baselines.
Figure summarizes
RELATED WORK
Bootstrap is classical statistical inference method, which was developed by Efron (1992) and generalized by, i.e. Mammen (1993); Shao (2010); Efron (2012) (just to name a few). Bootstrap can be widely applied to various statistical inference problem, such confidence interval estimation (DiCiccio et al., 1996). model selection (Shao, 1996). high-dimensional inference (Chen et al., 2018b; El Karoui & Purdom, 2018: Nie Ročková, 2020), off off-policy evaluation (Hanna et al., 2017), distributed inference (Yu et al., 2020) and inference for ensemble model (Kim et al., 2020), etc.
Despite its wide applications and nice theoretical properties, there has been very few works on discussing and improving the approximation efficiency in the region of small bootstrap sample size, beyond the i.idd. sampling paradigm. While the m-out-of-n bootstrap (Bickel al., 2012) and the bag of little bootstrap ( (Kleiner et al., 2014) are designed to reduce the computational cost with the subsampling techniques the big data settings (large n)), they still require large bootstrap sample size and thus are still not scalable to large deep learning applications.
Bayesian Inference is different approach to quantify the model uncertainty. Different from frequentists' method, Bayesian assumes prior over the model and the uncertainty can be captured by the posterior. Bayesian inference have been largely popularized in machine learning, largely thanks to the recent development in scalable sampling method (Welling & Teh, 2011; Chen et al.. 2014; Seita et al., 2018; Wu et al., 2020), variational inference (Blei et al., 2017: Liu & Wang, 2016), and other approximation methods such Gal & Ghahramani (2016); Lee et al. (2018). In comparison,

---

Under review as a conference paper at ICLR 2022
bootstrap has been much less widely used in modern machine learning and deep learning. We believe this is largely attributed to the lack of similarly efficient computational methods in the small sample size region, which is the very problem that we aim to address with our centroid approximation method.
Uncertainty in Deep Learning In additional the applications considered in this paper, uncertainty in deep learning model can also be applied to problems including calibration (Guo et al., 2017) and out-of-distribution detection (Nguyen al., 2015). The definition of uncertainty of neural network is quite generalized (e.g., Gal & Ghahramani (2016); Ovadia et al. (2019); Maddox et al. (2019); Van Amersfoort al. (2020)) and can be quite different from the uncertainty that bootstrap inference want to quantify and can be approached with various methods including drop out (Gal & Ghahramani, 2016; Durasov al., 2020), label smoothing (Qin et al., 2020), designing new modules in the model (Kivaranovic et al., 2020), adversarial training (Lakshminnrayanan et al., 2017) and Bayesian modeling (Blundell et al., 2015), etc. This paper focuses on improving the bootstrap method and thus is orthogonal to those previous works. Pearce al. (2018); Salem et al. (2020) also try to refine ensemble models improve the quality of prediction interval. Compare with our method, their method can only be applied to prediction interval and does not have theoretical guarantee.
CONCLUSION
We propose centroid approximation method to learn improved particle distribution that better approximates the target bootstrap distribution, especially in the region with small particle size. Theoretically, when the size of training data is large, objective function is surrogate to the Wasserstein distance between the particle distribution and target distribution. Thus, compared with standard bootstrap, the proposed centroid approximation method actively optimizes the distance between particle distribution and target distribution. The proposed method is simple and can be flexibly used for applications of bootstrap with negligible extra computational cost.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Morgane Austern and Vasilis Syrgkanis. Asymptotics of the empirical bootstrap method beyond asymptotic normality. arXiv preprint arXiv:2011.11245 2020.
Peter J Bickel, Friedrich Götze, and Willem van Zwet. Resampling fewer than observations: gains, losses, and remedies for losses. In Selected works of Willem van Zwet, pp. 267-297. Springer, 2012.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 1126118):39--87,, 2017.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pp. 1613-1622. PMLR, 2015,
Leo Breiman. Bagging predictors. Machine learning, 24(2):123-140, 1996.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint wwxivv:600.015444 2016.
Trevor Camphell and Boyan Beronov. Sparse variational inference: Bayesian coresets from scratch. Advances in Neural Information Processing Systems, 32:1 1461-11472, 2019.
Guillermo Canas and Lorenzo Rosasco. Learning probability measures with respect to optimal transport metrics. In F. Pereira, C. J. C. Burges, I.. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Snigdhansu Chatterjee, Arup Bose, et al. Generalized bootstrap for estimating equations. The Annals of Statistics, 33(1):414-436, 2005.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient hamiltonian monte carlo. In International conference on machine learning, pp. 1683-1691. PMLR, 2014.
Wilson Ye Chen, Lester Mackey, Jackson Gorham, François- Xavier Briol, and Chris Oates. Stein points. In International Conference on Machine Learning, pp. 844-853. PMLR, 2018a.
Xiaohui Chen et al. Gaussian and bootstrap approximations for high-dimensional u-statistics and their applications. The Annals of Statistics, 46(2):642-678, 2018b.
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. arXiv preprint arXiv:1203.3477 2012.
Guang Cheng, Jianhua Z. Huang, et al. Bootstrap consistency for general semiparametric m-estimation. Annals of Statistics, 3885):2884-291 2010.
Sebastian Claici, Aude Genevay, and Justin Solomon. Wasserstein measure coresets. arXiv preprint 185.77280, 2018.
Thomas DiCiccio, Bradley Efron, et al. Bootstrap confidence intervals. Statistical science, 11(3): 189 299-228, 1996.
Nikita Durasov, Timur Bagautdinov, Pierre Baque, and Pascal Fua. Masksembles for uncertainty estimation. arXiv preprint arXiv:2012.08334 2020.
Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistics, pp. 569-593. Springer, 1992.
Bradley Efron. Bayesian inference and the parametric bootstrap. The annals of applied statistics, 6 (4):1971, 2012.
Noureddine El Karoui and Elizabeth Purdom. Can we trust the bootstrap in ?igh-dimensions? the case of linear models. The Journal of Machine Learning Research, 19(1):170-3 2018.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, PMLR, 2016.
11

---

Under review as a conference paper at ICLR 2022
Alex Graves. Practical variational inference for neural networks. In Advances in neural information processing systems, pp. 2348-2356. Citeseer, 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks, International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Peter Hall et al. Rate of convergence in bootstrap approximations. The Annals of Probability, 16(4): 1665-1684, 1988.
Josiah Hanna, Peter Stone, and Scott Nickum. Bootstrapping with models: Contidence intervals for off off-policy evaluation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
Botao Hao, Yasin Abbasi Yadkori, Zheng Wen, and Guang Cheng. Bootstrapping upper confidence bound. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Jiri Hron, Alexander G de G Matthews, and Zoubin Ghahramani. Variational gaussian dropout is not bayesian. arXiv preprint arXiv: 2017.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E Hopcroft, and Kilian Q Weinberger. Snapshot ensembles: Train get m for free. International Conference on Learning Representations, 2017.
Byol Kim, Chen Xu, and Rina Foygel Barber. Predictive inference is free with the jackknife+-after- bootstrap. Advances in Neural Information Processing Systems, 33, 2020.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-fre. prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 4346-4356. PMLR, 2020.
Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, and Michael Jordan. scalable bootstrap for massive data. Journal of the Royal Statistical Society: Series B: Statistical Methodology, pp. 795 816, 2014.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak. Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. International Conference on Learning Representations, 2018.
Qiang Liu and Dilin Wang. Stein variational gradient descent: general purpose bayesian inference algorithm. Advances in Neural Information Processing Systems, 29, 2016.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. Advances in Neural Information Processing Systems, 32:13153-1311 2019.
Enno Mammen. Bootstrap and wild bootstrap for high dimensional linear models. The annals of statistics, pp. 255-285, 1993.
Benedict C May, Nathan Korda, Anthony Lee, and David Leslie. Optimistic bayesian sampling in contextual-bandi problems. Journal of Machine Learning Research, 13:2069-211 2006, 2012.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks easily fooled: High confidence
predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 427-436. 2015.
Lizhen Nie and Veronika Ročková. Bayesian bootstrap spike-and-slat lasso. arXiv preprint 1..i:20011.142777 2020.
12

---

Under review as a conference paper at ICLR 2022
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29:4026 4034,, 2016.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in Neural Information Processing Systems, 32: 13991-14002, 2019.
Tim Pearce, Alexandra Brintrup, Mohamed Zaki, and Andy Neely. High-quality prediction intervals for deep learning: A distribution-free ensembled approach. In International Conference Machine Learning, pp. 4075 4084. PMLR, 2018.
Yao Qin, Xuezhi Wang, Alex Beutel, and Ed H Chi. Improving uncertainty estimates through the relationship with adversarial robustness. arXiv preprint arXiv:2006. 16375, 2020.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018.
Donald B Rubin. The bayesian bootstrap. The annals of statistics, pp. 130-134, 1981.
Tárik S Salem, Helge Langseth, and Heri Ramampiaro. Prediction intervals: Split normal mixture from quality-driven deep ensembles. In Conference on Uncertainty in Artificial Intelligence, pp. 1179-1187. PMLR, 2020.
Daniel Seita, Xinlei Pan, Haoyu Chen, and John Canny. An efficient minibatch acceptance test for metropolis-hastiee hastings. Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 5359-5363, 2018.
Jun Shao. Bootstrap model selection. Journal of the American statistical Association, 91(434): 655-665, 1996.
Xiaofeng Shao. The dependent wild bootstrap. Journal of the American Statistical Association, 105 (489):218 235, 2010.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 1929:1999-1158, 2014.
Norman Tasfi
Pygame learning environment.
httpps://githhbb.com/ttttt
PyGame SyGame-Learnn Etw.rnngnnErrroometttt..... 2016. 2016.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-299 1933.
Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using single deep deterministic neural network. International Conference on Machine Learning, pp- 9690-9700. PMLR, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Apoorv Vyas, Nataraj Jammalamadaka, Xia Zhu, Dipankar Das, Bharat Kaul, and Theodore L Willke. Out-of-distribution detection using an ensemble of self supervised leave-out classifiers. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 550-564, 2018.
Larry Wasserman. All of statistics: a concise course in statistical inference. Springer Science & Business Media, 2013.
Jonathan Weed, Francis Bach, et al. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):2620-22 2019.
13

---

Under review as a conference paper at ICLR 2022
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 681-688. Citeseer, 2011.
Tung-Yu Yu Wu, YX Rachel Wang, and Wing H Wong. Mini-batch metropolis-hasting with reversible sgid proposal. Journal of the American Statistical Association, pp. 1-9, 2020.
Jeremy Wyatt. Exploration and inference in learning from reinforcement. 1998.
Yang Yu, Shih-Kang Chao, and Guang Cheng. Simultancous inference for massive data: Distributed bootstrap. In International Conference on Machine Learning, pp. 10892-10901, PMLR, 2020.
14

---

Under review as a conference paper at ICLR 2022
A
PROOF
We also show Theorem 3, which gives a formal characterization of the Taylor approximation intuition introduced in (5).
Theorem Under Assumption and 2, when n. sufficiently large, we have
(w) = L. (0w) + (0- (0-00)) mm) V Vifco (0o) (o Ow +Op (118 wwl ( 1/2 110 Gmll
Here the stochastic boundedness is taken w.r.t. the training data and w.
In the proof, we may use e to represent some absolute constant, which may vary in different lines.
A.1 PROOF OF THEOREM 3
With the fact that V ((Ow) = 0 and under assumption 1, using Taylor expansion, we have
1 (o 0w)) V2 (o 0ms) O (11e 6. ")
(0) Lu (0w)
2
Notice that
0 0m
Vo - V3Cco (06) (o 0m))
0m
vi. Vo (0m) ViCxx (06)
0 0m
V/Lc - ViCw (8b)
+ 1[ =x
mm
(cl 0.. 0o
+ (o (8)
||.11 With assumption 2, we have 0 - 660| = =Op(n 1/2).
where we denote the Frobenius norm as
By applying centroid limit theorem and delta method to V3, (00) - V2,, Coo for every pair
j.j [d], we have (2C (8))l = On 112).. Thus we obtained the desired result.
A.2 PROOF OF THEOREM 1
Given any radius and > O, with sufficiently large n, we have
P 01 - 00| 2r) exp(-Xnr
for > = (A)mx((A) -1, Here the probability is the jointly probability of bootstrap weight and training data. Thus, given any r, under the assumption that 03 (0) is initialized via sampling O.. then we have
IP (Use(m) (0) - 0oll 2 r)) < Σ TP (10 0oll z r) S m (osp(-Anr]) +
jE(m
We proof by induction. Given any (0, {0,) define
REr = T T((w supp(m) arg min (0, and | 0o s srl. jE(m)
/ log
Suppose at iteration i, we have [10](t) - 0ol <
for some constant e and Ao which we
denote as the minimum eigenvalue of Vi (fo,). Now at iteration have two cases.
15

---

Under review as a conference paper at ICLR 2022
Case 1: Rx, 21 Suppose that at iteration for & such that E, Rk, 7 and [[)g(t) -Bull Yc. we have the following property:
[ 1) Poll2 (0t(()
C
Ex (o Bu
En RK,00000
2
(1) - Boll
(0%(t) 0o, ET oo (1)) Rx,oo) + || Vo (0f(1)) 211
E, Rk
Notice that
Bn (oLw
_ Ex V2 (0w) - -0w) Rx)
+ +o
(2) Ex
V2Cuo (0.)) (0((() 0o)
+ +0 (4))
3 Ex Vi (6)) (t) - Rk. +0 (q
Here (1) is obtained via applying Taylor expansion on VoLw (t)) at 0w-
(2) is by assumption
and 2. (3) is by assumption 1. We thus have
(t) 0u. B, VeLw (t) RR,col)
I (t) - 0u, E. VeLw (t) Rx 1) + (1) Boll E VoLw (()(t))) - Rk.
S (()(()) - Oo, ET Vo (0% RRx Rx. + egN exp(-Aru
S E. RR.o. (0E(1) 0o) V Lo (0)(() - 0o) + eun
+ (4
Notice that with sufficiently large n, with central limit theorem, we have
0o) < [(]((t) 0ol12 Ex (o) v2Cw (0o) Re. (0%(t) - 00) (3C=0(00001()) 0o)
E RR. (t) 0o) To)
-R,,RR..o (t) 0o) T (0) -0o) + On 11/2).
This gives that
(02(1) 00 Ex Cw (x,
S Es Rk.qu (1) 00) T Co (O 00) cgx exp( exp((Angg)) +0 00 1122
S - Au Re.. (t) loll + cgk (op(--ngg)) + +0 ( + 96n q/2-1/2)
Use the above estimation, we have
[1 1) 0o1l
ES Rk.qe (10)(1) - 0oll
< (10((1) - 0o. 2- -me E Rk.00
+200,9k (op(--nng)))) /EE R4,00 + + (e(( + 9k -1/2)) /Ea Rk + e.)
< [102(t) - 00.1 E, Rk
6t
Er (10)(1) - -Bo112 20qx (xx(--nng)) + O + + gen 1/2)
Notice that by choosing a > II(2A) and e, = O(n with sufficiently large n, when
log
ca
[[0((t) 0oll > Xg RR.qe
for some constant c, we have
110 + 1) 0oll (1) 6oll
Thus [[ 1) -oll <
6a
for some constant
R4,00
Ao7
16

---

Under review as a conference paper at ICLR 2022
Case 2: Rk,00 S
In this case, we have
1) (0%(() a (Vo((f22() Bu
(t) 0ol1 2c, (0%(t) Po. VeL(O)(t)) + voC(fo
Notice that
- (t) - fo: VeL(O)(0)) _ - (t) 0o. VZC(0)) (02(t) - 0o)) (01(0) 0.. voC(fe.)) + o() -bol1%)
(0 0b) T vi. (t) B.) + +(10 0oll)) Op(n 1/3) Bull
This gives that
[t 1) 0ull [1)((t) - (10](t) lull 10 +o(e) +00
With O(n and sufficiently large when
c02
(0)(t) - 0oll
Aoy
we have [ 0oll < (0%()) - 0n
Combine this two cases, we conclude that [10](t + 1) Bol
5
on
for any t, when
Ao7
[10](0) - 0oll
We thus conclude that, for any >
/1/(2A) and >> 0, when n
sufficiently large, with probability least mmpppp (-x
ca² logn
E, we have
log
sup |107() 001l 5 [E(m] t
Ao
A.3 PROOF FOR THEOREM 2
Notice that
VjLw (07(t) 0v) + +0 0w 13)
Lw (0) - Lw (0w)
2 (7(()) - 6m)
2 (07(1) - 8m)
VoLw (6o) (0)(t) kw) + +01 0m ||)
+ 0 00))) 0ul l 11 80(1)
[0](t) Aw
Li (8o) (8))l 07(0) dm 2
+ ()()) 0u0 1
+ 00100(00 0m 1 |w 0o()
Given w, we define uw arg mim]
(07(1) 0m
|| For any a: 1/(A) and 0, when
sufficiently large, with probability at least m exp
(-X en log x5
6, we have
(t) Buml
Expa
min jE(m)
2
|| -Bmul 1ull(,]
Eawas
2
L (o Lro (mw) c 10:0. 0mol" ( (000-oo) 00ll + Vi
- VgCoo + +1 - 0nn -mml))
> Eur
avllgg
Lo (Piw)) Euor Luw ((o))
> -Ew
A07733/2
=Ew>r
min Lw (e0( jE[ml]
Ewer
-c
( (aylogn
2//23/22
17

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Ideal algorithm for centroid approximation with full-batch gradient used and wn updated every iteration.
1: Initialize (0), [Ta]] by ii.d. sampling from Px or other distribution such as Gaussian.
2: for E iterations do
3: Vi E [m]] calculate L(Ø) (t)) defined in (11)
4: Sample (w,, (wr))/=> A=1= i.i.d. from n.
5: vh [M] and j E [m]] calculate w.w (0) = (t))
6: vh [M], calculate Uws defined in (12) for each h.
7: vj E [m], update 03 by (13).
8: end for
(-x car log n
Similarly, also have, with probability least 1 - m exp
Ewonn
jE[m)
min Lw (03(t)) -Ew~n (8w))
2 Ewwa
min [e[ml
(t) - 0 0ul1 -
\07m33/2
lavloogn
Notice that the above bound holds uniformly for all j E [m]] and any iteration f, which implies that
with probability at least 2m exp (-X car A07
2e, we have
aaVlogn Ag7n3/2
sup 2
E
W
Luo (0) B - Bwow min [10((t) Ow 0w11B1/2 sc JElm]
min
Je(m]
B ALGORITHM BOX
We provide pseudo algorithm for the ideal centroid approximation algorithm in Algorithm 1. In practical implementation, we do not need to update w9 every iteration and can also replace the full-batch gradient by stochastic gradient. Specifically, notice that g(fī) defined in (10) can be alternative represented
(t) Em En [T[ E Uwn, (f)) Wh,s Vollz,, Vol(xi
n ahs fa
EM [T]] E uws H]
(14)
where 4r is defined by
M ItjE E Unrn (1) Wh. h=
46
-i=1
(15)
[ Uann (4)
This allows us to use a stochastic gradient version of gradient
Isgd (0))
Σ
ths Vollei, So;),
(16)
B
EE(
where B is the set of mini-batch data. The detailed algorithm is summarized in Algorithm
C ADDITIONAL EXPERIMENT DETAILS
C.1 BOOTSTRAP CONFIDENCE INTERVAL
Given a model fe parameterized by and a training set with n data points i.idd sampled from population, goal is to construct confidence interval for 0. Let Ås be empirical distribution approximating Pr. which could be obtained by i.i.d. sampling, or by our centroid method. Denote by Q/a, (x] the a-quantile function of Ộ. with some E [0. 1]. We consider the following three ways to construct (two-sided) bootstrap confidence interval of with confidence level as the Normal interval, the percentile interval and the pivotal interval which defined below.
18

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Practical implementation of centroid approximation with less frequent updating of wn and stochastic gradient enabled.
1: Initialize (0), j [ma] by ii.d. sampling from Px or other distribution such as Gaussian.
2: for E iterations do
3:
// Update 4/, only every few iterations.
4: if mod freq == then
5:
Vj E [m]] calculate (()) defined in (11)
6:
Sample } i.idd from n.
7:
Yh E [M] and j E [m]], calculate Lun, (1) = / (().
8:
vh E M.. calculate Man, (t) defined in (12) for each h.
9:
else
10:
Murn (t) uur. (t-1)
11:
end if
12: Vj E [m]] update (t) by (13). (May use mini-batch gradient defined in (16)).
13:
end for
Methods to construct confidence interval are The Normal interval:
The methods we used to construct confidence interval
0 =((1 + a)) 0 [[1++00) a))2)s))))
where z(-) is the inverse cumulative distribution function of standard Normal distribution. And Soboot the standard deviation estimated from 7T.
The percentile intervals:
- |2(0--0//2,1,,
The pivotal interval:
[20- Q(11=))2 Q[( - - 22)
We consider the following simple linear regression:
(0 I. x (0 x, I), where the
features z E IRd and we set the true parameter to be 6g = [1, 11,11,, We consider n = 50 and the number particles m = 20, 50, 100, 200. We compare the coverage probability and the confidence level measure the quality:
Measuring the quality of confidence interval With large number N of independently generated training data (we use N = 1000), we are able to obtain the corresponding confidence intervals {CI()))) and and thus obtain the probability that the true parameter falls into the confidence intervals, which is the estimated coverage probability
à
=
Σ
Ifo E C(()))).
N
A good confidence interval should have à close to a. Thus we measure the performance by calculating the difference |a a].
As 6m is the least square estimator of the bootstrapped dataset, it has analytic solution and thus can be obtained via some matrix multiplications. 0*, is initialized using Onr and then updated for 2000 steps. For this experiment, we find that adding the threshold 7 does not gives further improvement for this experiment and thus we simply set = 0 and use M = 1. We approximate the true bootstrap distribution by sampling 10000 i.i.d. samples.
More experiment result Table 3 all the result we have varying a = 0.8, 0.95, m = 20, 50, 100, 200 and three different approaches for constructing confidence interval. As can see, centroid approximation gives the best performance in most cases compared with the other three baselines.
19

---

Under review as a conference paper at ICLR 2022
Num Particle
20
50
100
200
Bootstrap
0.033
0.013
0.028 0.013
0.026
0.031 0.003
Bayesian
0.084 0.014
0.076 = 0.014
0.082
0..014
0.004
Normal
Residual
0.033 0.013
0.037 = 0.013
0.019
0.013
Centroid
0.036 0.013
0.003 0.012
0.017 0.013
0.030+0000
Bootstrap
0.096 0.014
0.050 = -0,014
0.013
0.004
Bayesian
0.114 0.015
0.079 0.0014
0
0.071 0.014
a = 0.8
Percentile
Residual
0.079
0.014
0.032 0.013
0.017
0.013
0.010 0.013
Centroid
0.066 0.014
0.008 = 0.013
0.019 1 0.013
0.020 0.013
Bootstrap
0.101 0.015
0.053 = 0.014
0.045 10451000144
0.033 0.013
Bayesian
0.158 0.015
0.110 = 0.110
0.088 + 0.014
0.078 + 0.014
Pivotal
Residual
0.087 0.014
0.044 0.013
0.030 = 0.013
0.023 0.013
Centroid
0.026 0.013
0.030 0.012
0.018 0.013
0.030 0.013
Bootstrap
0.029 0.010
0.031 = 0.011
0.021 0.0TO
0.017 0.010
Bayesian
0.076 = 0.012
0.054 = 0.011
0.048 + 0.011
0.045 + 0.011
Normal
Residual
0.043 0.011
0.023 = 0.010
0.025 + 0.010
0.020 = 0.010
Centroid
0.027 0.010
0,001 0.009
0.012 0.010
0.016 - 0.010
Hootstrap
0.101 0.013
0.036 0.001
0.021 0.0TO
0.014 0.010
Bayesian
0.129 = 0.013
0.077 = 0.012
0.059 0.012
0.054 0.011
0.9
Percentile
Residual
0.098 = 0.013
0.030 = 0.011
0.033 1: 0.011
0.025 1 0.010
Centroid
0.081 0.012
0.021 = 0.010
0.020 + 0.010
0.015 + 0.010
Bootstrap
0.106 0.013
0.045 = 0.011
0.025 =
0.023 0.010
Bayesian
0.149 0.014
0.093 0.012
0.073 1 0.012
0.056 + 0.011
Pivotal
Residual
0.100 0.013
0.044 = 0.011
0.030 0.011
0.023 0.010
Centroid
0.046 0.011
0.013 = 0.009
0.011 0.010
0.020 = 0.010
Bootstrap
0.018 0.008
0.014 = 0.008
0.012 = 0.008
0,006 = 0.007
Bayesian
0.053 = 0.010
0.038 = 00,09
0.031 0.009
0.037 = 0.009
Normal
Residual
0.036 0.009
0.019 0.008
0.011 0.008
0.008 0.007
Centroid
0.018 = 0.008
0.005 = 0.006
0.009 0.007
0.005 0.007
Bootstrap
0.081 = 0.010
0.047 = 0.009
0.030 E 0.008
0.017 0.000
Baycsian
0.126 0.012
0.072 0.010
0.056 + 0.010
0.042 + 0.009
a
Percentile
Residual
0.100
0.011
0.040
0.009
0.037 1: 0.009
0.021 1 0.008
Centroid
0.077 0.010
0.029
0.008
0.020 0.008
0.016 1 0.008
Bootstrap
0.089 0.011
0.043
0.009
0.027 0.008
0.015 - 0.008
Bayesian
0.127 = 0.012
0.091 = 0.011
0.064 + 0.010
0.056 + 0.010
Pivotal
Residual
0.085 0.011
0.051 = 0.009
0.036 0.009
0.029 + 0.008
Centroid
0.046 0.009
0.002 0.007
0.014 + 0.008
0.009 + 0.007
Table 3: Complete result comparing centroid approximation with various bootstrap methods. The bold number shows the best approach.
20

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Algorithm for Centroid Approximation Applied to Contextual Bandit.
1: Obtain a randomly initialized 0j (0), j E [ml]
2: Initialize a common replay buffer R. = recording all the observed contexts.
3: For each model, initialize its own replay buffer R3 @ that is used for training.
4: for E number of total steps do
5: Obtain the t-th context 2z.
6: Sampling one model based on probability (1) to make action az and get reward r..
7: Update the common replay buffer by R. + R. (g,
8:
I/ Update wh and R2 and model every few iterations.
9:
if l. mod freq == O then
10:
Vj E [m/] calculate (t)) defined in (11) for all the contexts in Rg. // L(0 (1) e Rl
11:
Generate M sets of random weights {w), 1.M h==1 of contexts in Re from æ.
12:
Vh E [M] and j E [m.] calculate Lw. (0) (t)) )) = w L(f
13:
Vh E [M], calculate Uws (t) defined in (12) for each h.
14:
Vi R and [m]] calculate ga.j by (15)
15:
Vj E [m], update (t) based on (7).
16:
Vj E [m]] if oz( S y, construct R₃- = R. else, construct R3 by sample [R,l contexts
in Rg. The probability that context i is being sampled is 9 E RR] gt.--
17:
Vj E [m]]. train model using the data in R, for several iterations.
18:
end
19:
end for
C.2
CENTROID APPROXIMATION FOR BOOTSTRAP METHOD IN CONTEXTUAL BANDIT
C.2.1 MORE BACKGROUND
Contextual bandit is a classic task in sequential decision making problem in which at time t = I,..., a new context Ky arrives and observed by an algorithm. Based on its internal model, the algorithm selects actions a, and receives reward ra (22,, az) related to the context and action. During this process, the algorithm may update its internal model with the newly received data. At the end of this process, the cumulative reward of the algorithm is calculated by r = Σi= I'z and the goal for the algorithm is to improve the cumulative reward r. The exploration-exploiatioo dilemma is a fundamental aspect in sequential decision making problem such as contextual bandit: the algorithm needs to trade-off between the best expected action returned by the internal model at the moment (i.e., exploitation) with potentially sub-optimal exploratory actions. Thompson sampling (Thompson, 1933; Wyatt, 1998; May et al., 2012) is an elegant and effective approach to tackle the exploration- exploitation dilemma using the model uncertainty, which can be approached with various methods including Bayesian posterior (Graves, 2011; Welling & Teh, 2011), dropout uncertainty (Srivastava et al., 2014; Hron et al., 2017) and Bootstrap (Osband et al., 2016; Hao et al., 2019). The ability to accurately assess the uncertainty is key to improve the cumulative reward. Bootstrap method for contextual bandit maintains m bootstrap models trained with different bootstrapped training set. When conducting an action, the algorithm uniformly samples model and then selects the best action returned by the sampled model.
C.2.2 MORE EXPERIMENT SETUP DETAILS
We set all the experimental setting including data preprocessing, network architecture and training pipeline exactly the same the one used in Riquelme et al. (2018) and adopt its open source code repository.
Network architecture Following Riquelme et al. (2018), we consider fully connected feed forward network with two hidden layers with 50 hidden units and ReLU activations. The input and output dimensions depends on the dimension of context and number of possible actions.
Training For each dataset, we randomly generate 2000 contexts, and for each algorithm, we update the replay memory buffer for each model every 50 contexts, and each model is also updated every 50 contexts. For the standard bootstrap, when updating the replay buffer of each model, we sample 50 i.i.d. contexts with uniform probability from the latest 50 contexts (each model have different
21

---

Under review as a conference paper at ICLR 2022
realizations of the samples) and add the newly sampled contexts to each model's replay buffer. For the centroid approximation, we update the replay buffer of each model by applying resampling on all the observed contexts up to the current steps. The resampling probability of each context for each model is different and determined by the algorithm. We refer readers to Algorithm for the detailed procedures. Here we choose freq = 50 and M 100. When at model updating. each model is trained for 100 iterations with batch size 512 using the data from its replay buffer. Following Riquelme et al. (2018), we use RMSprop optimizer with learning rate 0.1 for optimizing. When making actions, we sample the prediction head according to (t) obtained using the examples between the last two model updates.
Notice that in the implementation, we only need to maintain one common replay buffer and the replay buffer for each model can be implemented by maintaining the number of each context. Thus when sampling batches of context, we simply need to sample the index of the context and refer to the common replay buffer to get the actual data.
C.3 CENTROID APPROXIMATION FOR BOOTSTRAP DQN
C.3.1 MORE BACKGROUND
Similar to the bootstrap method in contextual bandit problem, Bootstrap DQN explores using the model uncertainty, which can be assessed via maintaining several models trained with bootstrapped training set. Maintaining several independent models can be very expensive in RI. and to reduce the computational cost, Bootstrap DQN uses multi-head network with a shared base. Each head in the network corresponds to a bootstrap model and the common shared base is thus trained via the union of the bootstrap training set of each head. We train the Bootstrap DQN with standard updating rule for DQN and use Double-DQN (Van Hasselt et al., 2016) to reduce the overestimate issue. Notice that our centroid approximation method only changes the memory buffer for each head and thus introduces no conflict to other possible techniques that can be applied to Bootstrap DQN.
C.3.2 MORE EXPERIMENT SETUP DETAILS
Network Architecture Following Osband et al. (2016), we considered multi-head network structure with a shared base layer to save the memory. Specifically, we use a fully connected layer with 256 hidden neurons as the shared base and stack two fully connected layers each with 256 hidden neurons as head. Each head in the model can be viewed as one bootstrap particles and in computation, all the bootstrap particles use the same base layer.
Training and Evaluation For v, we train the model for 450 episodes with the first 50 episodes used to initialize the common memory buffer. The maximum number of steps within each episode is set to 1000 and we report the moving average reward with window width 100. For Catcher-vO, we train the model for 100 episodes with the first 10 episodes used to initialize the common memory buffer. We set the maximum number of steps within each episodes 2000 and report the moving average reward with window width 25.
For training the Bootstrap DQN, given the current state T₁, we sample one particle based on {uz Jm and use its policy network to make an action 0n and get the reward ra and next state T2+1- The Q-value of the state action pair Q( ax) is estimated by r. x ((7441). where Q(1441) is the predicted state value by the target network of the sampled particle and À is the discount factor set to be 0.99. At each step, the policy network of all particles are updated using one step gradient descent with Adam optimizer (3 = (0.9, 0.999) and learning rate 0.001) and mini-batch data (size 64) sampled from its replay buffer. We update target model, each particle's 's replay buffer and ois every 1000 steps for Lunarl Landr_ander-v2 and every 200 steps for Catcher-vO. The update scheme for replay buffers of each particles and v/s is the same as the one in contextual bandit experiment. As the model see significantly larger number of contexts than that in the contextual bandit experiment, to reduce the memory consumption, we set the max capacity of the common replay buffer to 50000 (the oldest data point will be pop out when the size reaches maximum and new data comes in). For training the shared base, following Osband et al. (2016), we adds up all the gradient comes from each head and normalizes it by the number of heads. Algorithm 4 summarizes the whole training pipeline.
[j=1
22

---

Under review as a conference paper at ICLR 2022
Algorithm 4 Algorithm for Centroid Approximation Applied to DQN.
1: Obtain a randomly initialized (0), j E [m/]. (For the j-th particle, both of its target and policy network use the same initialization..)
2: Initialize a common replay buffer R. = recording all the observed contexts.
3: For each head, initialize its own replay buffer R, = @ that is used for training.
4: for E number of total episodes do
5: while not at terminal state and the number of steps does exceed the threshold do
6: Obtain the (-th context Zt.-
Sample an head based on {eî} } make action at and get (2 ar) using the reward Fr and the prediction of the corresponding target network.
8:
Update the common replay buffer by R. + R. U ((z,, Q(z,,a)))
9:
Vj E [m]] update its policy network by one step gradient descent using the data from its
reply buffer.
10:
// Update wa and R2 and target network every few iterations.
l mod freq = then
12:
Vj [mm] calculate (())(t)) defined in (11) for all the contexts in Re-
Generate M of random weights {wi 1M h= of contexts in Re from w.
vh E [M]] and j E [m]], calculate Lw, (f) (t)) w (f))
Wh E [M]. calculate Wwr, (t) defined in (12) for each
16:
Vi E Rell and j [m]] calculate qi.j by (15)
Yj E im]. update 2z (t) based on (7).
Vj E [m], vz (4) S 7, construct R3 R.. else, construct R3 by sample Ra
Rg The probability that context is being sampled is 9t.z/ |Rcl qt.--
contexts
19:
Vj E [m], update the j-th target network by loading the weights of the j-th policy
network.
20:
end if 21: end while
22:
end for
76
92.5
74
Top-5
92.0
73
91.5
Centroid Bootstrap
Centroid
91.0
Bootstrap
71
5
8
9
10
5
8
10
Num particles
Num particles
Figure 4: Results on ensemble modeling with bootstrap using Vgg16 on CIFAR-100.
C.4 BOOTSTRAP ENSEMBLE MODEL
Ensemble of deep neural networks have been successfully used to boost predictive performance (Lakshminarayanan et al., 2017). In this experiment, we consider using an ensemble of deep neural network trained on different bootstrapped training set, which is also known popular strategy called bagging.
We consider image classification task on CIFAR-100 and use standard VGG-16 (Simonyan & Zisserman, 2014) with batch normalization. We apply a standard training pipeline. We train the bootstrap model for 160 epochs using SGD optimizer with 0.9 momentum and batchsize 128. The learning rate is initialized to be 0.1 and decayed by a factor of 10 at epoch 80 and 120. We start to apply the centroid approximation training). We generate the bootstrap training set for each centroid every epoch using the proposed centroid approximation method. We consider 3, 4,4, 5, 10 ensembles and use 7 0.5/m. We
epoch 120 (thus the centroid is initialized with 120 epochs'
23

---

Under review as a conference paper at ICLR 2022
#Particle
Y 0
y=
? == m
3
3480.0 120
3702.7 + 89.8
3467.7 + 115
3 126
3723.1 78.7
3600.0 69.3
5
3586.5 + 64.5
3799.6 6 84.2
3647.3 4 64.5
10
3785.0 59.1
3796.9 36.1
3 86.8
Table 4: Ablation study.
repeat the experiment for 3 random trials and report the averaged top1 and top5 accuracy with the standard deviation of the mean estimator. Algorithm
Figure summarizes the result. Overall, increasing m able to improve the predictive performance and with the same number of models, our centroid approximation consistently improves over standard bootstrap ensembles.
C.5 ABLATION STUDY
We study the effectiveness of using (8) modify the gradient of centroid with v)(() S 7. We consider the setting 0 (no modification) and m (always modify, equivalent to no bootstrap uncertainty) and applied the method on the mushroom dataset in the contextual bandit problem. Table 4 shows that (i) modifying the gradient of centroid with small oy (t) using do improve the overall result; (2) bootstrap uncertainty is important for exploration.
C.6 COMPUTATION OVERHEAD
Our main goal is not to decrease the training cost but improve the quality of bootstrap partical distribution so that we can use less models at deployment and hence reduce the memory cost and the computational cost for inference. Actually, discussed in Section 3, our method actually only introduces a little computation overhead while much improves the quality of the particles, which another advantage of our method. For example, in bandit problem on mushroom dataset, when m = 3, 10, vanilla bootstrap takes 33s, 101s while our approach takes 35s, 108s run. For the bagging, when m 3, 10, vanilla bootstrap takes 11200s, 34240s while ours take 12000s, 36200s. Results are based on the average of 3 runs. Our method only introduces about 7% computational overhead even with an naive implementation.
24


Reviews:
[{"review_id": "tXaH-3LIO_k", "reviewer": "Reviewer_5nLX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major points can be summarised as follows:\n1. 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?\n\n 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.\n\n3. 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. \n\n4. 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?\n\n", "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 .", "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", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rXrtGq8w6l", "reviewer": "Reviewer_oMBb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1) The problem is important and well-stated. The paper is clearly written.\n2) 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). \n\nWeakness:\n\n1) 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.\n\n2) 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. \n\n3) 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? \n\n\n4) 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. \n\n\n5) 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. \n\n6) 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? \n\n7) 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. \n", "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. \n\nThe 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.\n", "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.\n\n\nDespite 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. \n\n\nRevised 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. \n\n1) 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. \n\n2) The roles of m and M need to be studied more carefully. \n\n3) 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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fvivQo3MIRe", "reviewer": "Reviewer_y4AP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n\n- This work seeks to improve on computational aspects of the bootstrap, a fundamental and popular statistical method\n\n- The derivation of the centroid method involves interesting ideas from optimal transport and a natural choice of surrogate loss.\n\n- The applications seem well-chosen and relevant to modern machine learning\n\n**Concerns:**\n\n- 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.\n\n- 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. \n\n- Although the topic of this paper is bootstrapping, there is no evaluation of uncertainty for the real-data experiments.\n\n- 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.\n\n- 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\n\n- Bootstrap DQN is limited to 2 and 5 models. This makes it hard to see trends.\n\n**Contextual bandits**\n\n- 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.\n\n- It seems that the centroid algorithm applied to the collection of parameters of the models. Is this correct? This should be explicitly stated.\n\n- 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?\n\n- 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? \n\n- 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.\n\n**Further comments**\n\n- 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).\n\n- 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.\n\n**Minor issues**\n\n- In the Tables 1,2,3, please write the value of the best performing method in boldface for readability.\n\n- pg 5, typo: estiblish\n\n- pg 5, \"... can be done using classic techniques in non-convex optimization...\" This needs further elaboration or should be removed.\n\n- pg 6: Theorems 1 and 2 are asymptotic in nature, and this should be mentioned again in the theorem statements\n\n- 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. \n\n- pg 8, Figure 3: Interestingly, there is a period where centroid 2-head outperforms centroid 5-head. Why does this happen?\n\n- 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.\n\n- 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.\n\n- 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).\n\n- pg 16, Algorithm 1: Why is there a loop over t' in inner-iters? I did not see any dependence on t'. \n\n- pg 16, Methods to construct confidence interval: the $\\hat \\rho_\\pi$'s should be $\\tilde \\rho_\\pi$'s\n\n", "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 .", "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.  \n\n========================================\n\n**Update on review (11/29)**\n\nThe 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. \n\nI 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. \n\nOverall, 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5dVUIF7UUsi", "reviewer": "Reviewer_Uq9L", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "##########################################################################\n\nSummary:\nThis 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.\n \n\n##########################################################################\n\nReasons for score: \nFor 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.\n\n\n##########################################################################\n\nPros: \n\n \n1. The paper addresses an interesting computational problem applicable to many models in machine learning. The algorithm is simple to implement and to understand.\n\n2. Experiments cover interesting machine learning use cases, e.g. contextual bandit, reinforcement learning, confidence interval estimation.\n \n\n##########################################################################\n\nCons: \n\n \n1. It is unclear how much benefit the new methodology offers over the previous ones, e.g. in terms of model accuracy improvement.\nIt is presumed that the iterative nature of the algorithm incurs many model updates and model loss evaluations in the inner loop.\n\n2. 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).\n\n3. 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.\n \n4. 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.\n\n5. On a related above: how would the initialization of theta work for a tree based method?\n\n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease provide clarifications for the points in the previous section.\n\n \n\n#########################################################################\n\nSome typos: \n\n- page 19: bootstrap partical -> bootstrap particle\n", "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.", "summary_of_the_review": "It is overall an interesting paper providing an acceleration technique for bootstrap - but I would suggest the following:\n1. 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.\n\n2. Clarify experimental setting parameters (e.g. size of the dataset, size of theta, etc.). See above for details.\n\n3. Comment on comparison vs other previous bootstrap variants.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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