Year: 2020

Abstract:
We present geometric Bayesian active learning by disagreements (GBALD), a framework that performs BALD on its geometric interpretation interacting with a deep learning model. There are two main components in GBALD: initial acquisitions based on core-set construction and model uncertainty estimation with those initial acquisitions. Our key innovation is to construct the core-set on an ellipsoid, not typical sphere, preventing its updates towards the boundary regions of the distributions. Main improvements over BALD are twofold: relieving sensitivity to uninformative prior and reducing redundant information of model uncertainty. To guarantee the improvements, our generalization analysis proves that, compared to typical Bayesian spherical interpretation, geodesic search with ellipsoid can derive a tighter lower error bound and achieve higher probability to obtain a nearly zero error. Experiments on acquisitions with several scenarios demonstrate that, yielding slight perturbations to noisy and repeated samples, GBALD further achieves significant accuracy improvements than BALD, BatchBALD and other baselines.

heading: 1 INTRODUCTION
text: Lack of training labels restricts the performance of deep neural networks (DNNs), though prices of GPU resources were falling fast. Recently, leveraging the abundance of unlabeled data has become a potential solution to relieve this bottleneck whereby expert knowledge is involved to annotate those unlabeled data. In such setting, the deep learning community introduced active learning (AL) (Gal et al., 2017) that, maximizing the model uncertainty (Ashukha et al., 2019; Lakshminarayanan et al., 2017) to acquire a set of highly informative or representative unlabeled data, and solicit experts’ annotations. During this AL process, the learning model tries to achieve a desired accuracy using minimal data labeling. Recent shift of model uncertainty in many fields, such as Bayesian neural networks (Blundell et al., 2015), Monte-Carlo (MC) dropout (Gal & Ghahramani, 2016), and Bayesian core-set construction (Sener & Savarese, 2018), shows that, new scenarios arise from deep Bayesian AL (Pinsler et al., 2019; Kirsch et al., 2019).
Bayesian AL (Golovin et al., 2010; Jedoui et al., 2019) presents an expressive probabilistic interpretation on model uncertainty (Gal & Ghahramani, 2016). Theoretically, for a simple regression model such as linear, logistic, and probit, AL can derive their closed-forms on updating one sparse subset that maximally reduces the uncertainty of the posteriors over the regression parameters (Pinsler et al., 2019). However, for a DNN model, optimizing massive training parameters is not easily tractable. It is thus that Bayesian approximation provides alternatives including importance sampling (Doucet et al., 2000) and Frank-Wolfe optimization (Vavasis, 1992). With importance sampling, a typical approach is to express the information gain in terms of the predictive entropy over the model, and it is called Bayesian active learning by disagreements (BALD) (Houlsby et al., 2011).
BALD has two interpretations: model uncertainty estimation and core-set construction. To estimate the model uncertainty, a greedy strategy is applied to select those data that maximize the parameter disagreements between the current training model and its subsequent updates as (Gal et al., 2017). However, naively interacting with BALD using uninformative prior (Strachan & Van Dijk, 2003)(Price & Manson, 2002), which can be created to reflect a balance among outcomes when no information is available, leads to unstable biased acquisitions (Gao et al., 2020), e.g. insufficient prior labels. Moreover, the similarity or consistency of those acquisitions to the previous acquired samples, brings redundant information to the model and decelerates its training.
Core-set construction (Campbell & Broderick, 2018) avoids the greedy interaction to the model by capturing characteristics of the data distributions. By modeling the complete data posterior over the
distributions of parameters, BALD can be deemed as a core-set construction process on a sphere (Kirsch et al., 2019), which seamlessly solicits a compact subset to approximate the input data distribution, and efficiently mitigates the sensitivity to uninformative prior and redundant information.
From the view of geometry, updates of core-set construction is usually optimized with sphere geodesic as (Nie et al., 2013; Wang et al., 2019). Once the core-set is obtained, deep AL immediately seeks annotations from experts and starts the training. However, data points located at the boundary regions of the distribution, usually win uniform distribution, cannot be highly-representative candidates for the core-set. Therefore, constructing the coreset on a sphere may not be the optimal choice for deep AL.
This paper presents a novel AL framework, namely Geometric BALD (GBALD), over the geometric interpretation of BALD that, interpreting BALD with core-set construction on an ellipsoid, initializes an effective representation to drive a DNN model. The goal is to seek for significant
accuracy improvements against an uninformative prior and redundant information. Figure 1 describes this two-stage framework. In the first stage, geometric core-set construction on an ellipsoid initializes effective acquisitions to start a DNN model regardless of the uninformative prior. Taking the core-set as the input features, the next stage ranks the batch acquisitions of model uncertainty according to their geometric representativeness, and then solicits some highly-representative examples from the batch. With the representation constraints, the ranked acquisitions reduce the probability of sampling nearby samples of the previous acquisitions, preventing redundant acquisitions. To guarantee the improvement, our generalization analysis shows that, the lower bound of generalization errors of AL with the ellipsoid is proven to be tighter than that of AL with the sphere. Achieving a nearly zero generalization error by AL with ellipsoid is also proven to have higher probability. Contributions of this paper can be summarized from Geometric, Algorithmic, and Theoretical perspectives.
• Geometrically, our key innovation is to construct the core-set on an ellipsoid, not typical sphere, preventing its updates towards the boundary regions of the distributions.
• In term of algorithm design, in our work, from a Bayesian perspective, we propose a two-stage framework that sequentially introduces the core-set representation and model uncertainty, strengthening their performance “independently”. Moreover, different to the typical BALD optimizations, we present geometric solvers to construct core-set and estimate model uncertainty, which result in a different view for Bayesian active learning.
• Theoretically, to guarantee those improvements, our generalization analysis proves that, compared to typical Bayesian spherical interpretation, geodesic search with ellipsoid can derive a tighter lower error bound and achieve higher probability to obtain a nearly zero error. See Appendix B.
The rest of this paper is organized as follows. In Section 2, we first review the related work. Secondly, we elaborate BALD and GBALD in Sections 3 and 4, respectively. Experimental results are presented in Section 5. Finally, we conclude this paper in Section 6.

heading: 2 RELATED WORK
text: Model uncertainty. In deep learning community, AL (Cohn et al., 1994) was introduced to improve the training of a DNN model by annotating unlabeled data, where the data which maximize the model uncertainty (Lakshminarayanan et al., 2017) are the primary acquisitions. For example, in ensemble deep learning (Ashukha et al., 2019), out-of-domain uncertainty estimation selects those data which do not follow the same distribution as the input training data; in-domain uncertainty draws the data from the original input distribution, producing reliable probability estimates. Gal &
Ghahramani (2016) use MC dropout to estimate predictive uncertainty for approximating a Bayesian convolutional neural network. Lakshminarayanan et al. (2017) estimate predictive uncertainty using a proper scoring rule as the training criteria to fed a DNN.
Bayesian AL. Taking a Bayesian perspective (Golovin et al., 2010), AL can be deemed as minimizing the Bayesian posterior risk with multiple label acquisitions over the input unlabeled data. A potential informative approach is to reduce the uncertainty about the parameters using Shannon’s entropy (Tang et al., 2002). This can be interpreted as seeking the acquisitions for which the Bayesian parameters under the posterior disagree about the outcome the most, so this acquisition algorithm is referred to as Bayesian active learning by disagreement (BALD) (Houlsby et al., 2011).
Deep AL. Recently, deep Bayesian AL attracted our eyes. Gal et al. (2017) proposed to cooperate BALD with a DNN to improve the training. The unlabeled data which maximize the model uncertainty provide positive feedback. However, it needs to repeatedly update the model until the acquisition budget is exhausted. To improve the acquisition efficiency, batch sampling with BALD is applied as (Kirsch et al., 2019; Pinsler et al., 2019). In BatchBALD, Kirsch et al. (2019) developed a tractable approximation to the mutual information of one batch of unlabeled data and current model parameters. However, those uncertainty evaluations of Bayesian AL whether in single or batch acquisitions all take greedy strategies, which lead to computationally infeasible, or excursive parameter estimations. For deep Bayesian AL, being short of interactions to DNN can not maximally drive their model performance as (Pinsler et al., 2019; Sener & Savarese, 2018), etc.

heading: 3 BALD
text: BALD has two different interpretations: model uncertainty estimation and core-set construction. We simply introduce them in this section.

heading: 3.1 MODEL UNCERTAINTY ESTIMATION
text: We consider a discriminative model p(y∣x, θ) parameterized by θ that maps x ∈ X into an output distribution over a set of y ∈ Y . Given an initial labeled (training) set D0 ∈ X × Y , the Bayesian inference over this parameterized model is to estimate the posterior p(θ∣D0), i.e. estimate θ by repeatedly updating D0. AL adopts this setting from a Bayesian view.
With AL, the learner can choose unlabeled data from Du = {xi}Nj=1 ∈ X , to observe the outputs of the current model, maximizing the uncertainty of the model parameters. Houlsby et al. (2011) proposed a greedy strategy termed BALD to update D0 by estimating a desired data x∗ that maximizes the decrease in expected posterior entropy:
x∗ = arg max x∈Du H[θ∣D0] −Ey∼p(y∣x,D0)[H[θ∣x, y,D0]], (1)
where the labeled and unlabeled sets are updated by D0 = D0 ∪ {x∗, y∗},Du = Du/x∗, and y∗ denotes the output of x∗. In deep AL, y∗ can be annotated as a label from experts and θ yields a DNN model.

heading: 3.2 CORE-SET CONSTRUCTION
text: Let p(θ∣D0) be updated by its log posterior logp(θ∣D0, x∗), y∗ ∈ {yi}Ni=1, assume the outputs are conditional independent of the inputs, i.e. p(y∗∣x∗,D0) = ∫θ p(y
∗∣x∗, θ)p(θ∣D0)dθ, then we have the complete data log posterior following (Pinsler et al., 2019):
Ey∗[logp(θ∣D0, x∗, y∗)] = Ey∗[logp(θ∣D0) + logp(y∗∣x∗, θ) − logp(y∗∣x∗,D0)]
= logp(θ∣D0) +Ey∗[logp(y∗∣x∗, θ) +H[y∗∣x∗,D0]]
= logp(θ∣D0) + N
∑ i=1
⎛ ⎝ Eyi[logp(yi∣xi, θ) +H[yi∣xi,D0]] ⎞ ⎠ .
(2)
The key idea of core-set construction is to approximate the log posterior of Eq. (2) by a subset of D′u ⊆ Du such that: EYu[logp(θ∣D0,Du,Yu)] ≈ EY ′u[logp(θ∣D0,D ′ u,Y ′ u)], where Yu and Y ′ u denote the predictive labels of Du and D′u respectively by the Bayesian discriminative model, that is, p(Yu∣Du,D0) = ∫θ p(Yu∣Du, θ)p(θ∣D0)dθ, and p(Y ′ u∣D ′ u,D0) = ∫θ p(Y ′ u∣D ′ u, θ)p(θ∣D0)dθ. Here D′u can be indicated by a core-set (Pinsler et al., 2019) that highly represents Du. Optimization tricks such as Frank-Wolfe optimization (Vavasis, 1992) then can be adopted to solve this problem.
Motivations. Eqs. (1) and (2) provide the Bayesian rules of BALD over model uncertainty and core-set construction respectively, which further attract the attention of the deep learning community. However, the two interpretations of BALD are limited by: 1) redundant information and 2) uninformative prior, where one major reason which causes these two issues is the poor initialization on the prior, i.e. p(D0∣θ). For example, unbalanced label initialization on D0 usually leads to an uninformative prior, which further conducts the acquisitions of AL to select those unlabeled data from one or some fixed classes; highly-biased results with (Gao et al., 2020) redundant information are inevitable. Therefore, these two limitations affect each other.
4 GBALD
GBALD consists of two components: initial acquisitions based on core-set construction and model uncertainty estimation with those initial acquisitions.

heading: 4.1 GEOMETRIC INTERPRETATION OF CORE-SET
text: Modeling the complete data posterior over the parameter distribution can relieve the above two limitations of BALD. Typically, finding the acquisitions of AL is equivalent to approximating a core-set centered with spherical embeddings (Sener & Savarese, 2018). Let wi be the sampling weight of
xi, ∥wi∥0 ≤ N , the core-set construction is to optimize:
min w XXXXXXXXXXX N ∑ i=1 Eyi[logp(yi∣xi, θ) +H[yi∣xi,D0]]
´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ L
− N
∑ i=1 wiEyi[logp(yi∣xi, θ) +H[yi∣xi,D0]] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ L(w)
XXXXXXXXXXX
2
, (3)
where L and L(w) denote the full and expected (weighted) log-likelihoods, respectively (Campbell & Broderick, 2018; 2019). Specifically, ∑Ni=1H[yi∣xi,D0] = −∑yi p(yi∣xi,D0)log(p(yi∣xi,D0), where p(yi∣xi,D0) = ∫θ p(yi∣xi, θ)p(θ∣D0)dθ. Note ∥ ⋅ ∥ denotes the ` 2 norm.
The approximation of Eq. (3) implicitly requires that the complete data log posterior of Eq. (2) w.r.t. L must be close to an expected posterior w.r.t. L(w) such that approximating a sparse subset for the original inputs by sphere geodesic search is feasible (see Figure 2(a)). Generally, solving this optimization is intractable due to cardinality constraint (Pinsler et al., 2019). Campbell & Broderick (2019) proposed to relax the constraint in Frank–Wolfe optimization, in which mapping X is usually performed in a Hilbert space (HS) with a bounded inner product operation. In this solution, the sphere embedded in the HS replaces the cardinality constraint with a polynomial constraint. However, the initialization on D0 affects the iterative approximation to Du at the beginning of the geodesic search. Moreover, the posterior of p(θ∣D0) is uninformative, if the initialized D0 is empty or not correct. Therefore, the typical Bayesian core-set construction of BALD cannot ideally fit an uninformative prior. The another geometric interpretation of core-set construction, such as k-centers (Sener & Savarese, 2018), is not restricted to this setting. We thus follow the construction of k-centers to find the core-set.
k-centers. Sener & Savarese (2018) proposed a core-set representation approach for active deep learning based on k-centers. This approach can be adopted in core-set construction of BALD without the help of the discriminative model. Therefore, the uninformative prior has no further influence on the core-set. Typically, the k-centers approach uses a greedy strategy to search the data x̃ whose nearest distance to elements of D0 is the maximal:
x̃ = arg max xi∈Du min ci∈D0 ∥xi − ci∥, (4)
then D0 is updated by D0 ∪ {x̃, ỹ}, Du is updated by Du/x̃, where ỹ denotes the output of x̃. This max-min operation usually performs k times to construct the centers.
From the view of geometry, k-centers can be deemed as the core-set construction via spherical geodesic search (Bādoiu et al., 2002; Har-Peled & Mazumdar, 2004). Specifically, the max-min
optimization guidesD0 to be updated into one data, which draws the longest line segment from xi,∀i across the sphere center. The iterative update on x̃ is then along its unique diameter through the sphere center. However, this greedy optimization has large probability that yields the core-set to fall into boundary regions of the sphere, which cannot capture the characteristics of the distribution.

heading: 4.2 INITIAL ACQUISITIONS BASED ON CORE-SET CONSTRUCTION
text: We present a novel greedy search which rescales the geodesic of a sphere into an ellipsoid following Eq. (4), in which the iterative update on the geodesic search is rescaled (see Figure 2(b)). We follow the importance sampling strategy to begin the search.
Initial prior on geometry. Initializing p(D0∣θ) is performed with a group of internal spheres centered with Dj ,∀j, subjected to Dj ∈ D0, in which the geodesic between D0 and the unlabeled data is over those spheres. Since D0 is known, specification of θ plays the key role for initializing p(D0∣θ). Given a radius R0 for any observed internal sphere, p(yi∣xi, θ) is firstly defined by
p(yi∣xi, θ) = ⎧⎪⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎪⎩
1, ∃j, ∥xi −Dj∥ ≤ R0,
max ⎧⎪⎪ ⎨ ⎪⎪⎩ R0 ∥xi −Dj∥ ⎫⎪⎪ ⎬ ⎪⎪⎭ , ∀j, ∥xi −Di∥ > R0, (5)
thereby θ yields the parameter R0. When the data is enclosed with a ball, the probability of Eq. (5) is 1. The data near the ball, is given a probability of max{ R0∥xi−Dj∥} constrained by min∥xi −Dj∥,∀j, i.e. the probability is assigned by the nearest ball to xi, which is centered with Dj . From Eq. (3), the information entropy of yi ∼ {y1, y2, ..., yN} over xi ∼ {x1, x2, ..., xN} can be expressed as the integral regarding p(yi∣xi, θ):
N
∑ i=1
H(yi∣xi,D0) = − N
∑ i=1 ∫ θ p(yi∣xi, θ)p(θ∣D0)dθlog(∫ θ p(yi∣xi, θ)p(θ∣D0))dθ, (6)
which can be approximated by −∑Ni=1 p(yi∣xi, θ)log(p(yi∣xi, θ)) following the details of Eq. (3). In short, this indicates an approximation to the entropy over the entire outputs on Du that assumes the prior p(D0∣θ) w.r.t. p(yi∣xi, θ) is already known from Eq. (5).
Max-min optimization. Recalling the max-min optimization trick of k-centers in the core-set construction of (Sener & Savarese, 2018), the minimizer of Eq. (3) can be divided into two parts: minx∗ L and maxw L(w), where D0 is updated by acquiring x∗. However, updates of D0 decide the minimizer of L with regard to the internal spheres centered with Di,∀i. Therefore, minimizing L should be constrained by an unbiased full likelihood over X to alleviate the potential biases from the initialization of D0. Let L0 denote the unbiased full likelihood over X that particularly stipulates D0 as the k-means centers written as U of X which jointly draw the input distribution. We define L0 = ∣∑ N i=1Eyi[logp(yi∣xi, θ) +H[yi∣xi,U]]∣ to regulate L, that is
min x∗
∥L0 −L∥ 2, s.t. D0 = D0 ∪ {x ∗, y∗},Du = Du/x ∗. (7)
The other sub optimizer is maxw L(w). We present a greedy strategy following Eq. (1):
max 1≤i≤N min wi
N ∑ i=1 wiEyi[logp(yi∣xi, θ) +H[yi∣xi,D0]]
= N
∑ i=1 wilogp(yi∣xi, θ) −
N ∑ i=1 wip(yi∣xi, θ)logp(yi∣xi, θ),
(8)
which can be further written as: ∑Ni=1wilogp(yi∣xi, θ)(1 − logp(yi∣xi, θ)). Let wi = 1,∀i for unbiased estimation of the likelihood L(w), Eq. (8) can be simplified as
max xi∈Du min Dj∈D0 logp(yi∣xi, θ), (9) where p(yi∣xi, θ) follows Eq. (5). Combining Eqs. (7) and (9), the optimization of Eq. (3) is then transformed as
x∗ = arg max xj∈Du min Dj∈D0 ⎧⎪⎪ ⎨ ⎪⎪⎩ ∥L0 −L∥ 2 + logp(yj ∣xj , θ) ⎫⎪⎪ ⎬ ⎪⎪⎭ , (10)
where D0 is updated by acquiring x∗, i.e. D0 = D0 ∪ {x∗, y∗}.
Geodesic line. For a metric geometry M , a geodesic line is a curve γ which projects its interval I to M : I → M , maintaining everywhere locally a distance minimizer (Lou et al., 2020). Given a constant ν > 0 such that for any a, b ∈ I there exists a geodesic distance
d(γ(a), γ(b)) ∶= ∫ b a √ gγ(t)(γ′(t), γ′(t))dt, where γ′(t) denotes the geodesic curvature, and g denotes the metric tensor over M . Here, we define γ′(t) = 0, then gγ(t)(0,0) = 1 such that d(γ(a), γ(b)) can be generalized as a segment of a straight line: d(γ(a), γ(b)) = ∥a − b∥.
Ellipsoid geodesic distance. For any observation points p, q ∈M , if the spherical geodesic distance is defined as d(γ(p), γ(q)) = ∥p − q∥. The affine projection obtains its ellipsoid interpretation: d(γ(p), γ(q)) = ∥η(p − q)∥, where η denotes the affine factor subjected to 0 < η < 1.
Optimizing with ellipsoid geodesic search. The max-min optimization of Eq. (10) is performed on an ellipsoid geometry to prevent the updates of core-set towards the boundary regions, where ellipsoid geodesic line scales the original update on the sphere. Assume xi is the previous acquisition and x∗ is the next desired acquisition, the ellipsoid geodesic rescales the position of x∗ as x∗e = xi + η(x
∗ −xi). Then, we update this position of x∗e to its nearest neighbor xj in the unlabeled data pool, i.e. arg minxj∈Du ∥xj − x ∗ e∥, also can be written as
arg min xj∈Du
∥xj − [xi + η(x ∗ − xi)]∥. (11)
To study the advantage of ellipsoid geodesic search, Appendix B presents our generalization analysis.

heading: 4.3 MODEL UNCERTAINTY ESTIMATION WITH CORE-SET
text: GBALD starts the model uncertainty estimation with those initial core-set acquisitions, in which it introduces a ranking scheme to derive both informative and representative acquisitions.
Single acquisition. We follow (Gal et al., 2017) and use MC dropout to perform Bayesian inference on the model of the neural network. It then leads to ranking the informative acquisitions with batch sequences is with high efficiency. We first present the ranking criterion by rewriting Eq. (1) as batch returns:
{x∗1, x ∗ 2, ..., x ∗ b} = arg max
{x̂1,x̂2,...,x̂b}⊆Du H[θ∣D0] −Eŷ1∶b∼p(ŷ1∶b∣x̂1∶b,D0)[H[θ∣x̂1∶b, ŷ1∶b,D0]], (12)
where x̂1∶b = {x̂1, x̂2, ..., x̂b}, ŷ1∶b = {ŷ1, ŷ2, ..., ŷb}, ŷi denotes the output of x̂i. The informative acquisition x∗t is then selected from the ranked batch acquisitions x̂1∶b due to the highest representation for the unlabeled data:
x∗t = arg max x∗i ∈{x∗1,x∗2,...,x∗b} ⎧⎪⎪ ⎨ ⎪⎪⎩ max Dj∈D0 p(yi∣x ∗ i , θ) ∶= R0 ∥x∗i −Dj∥ ⎫⎪⎪ ⎬ ⎪⎪⎭ , (13)
where t denotes the index of the final acquisition, subjected to 1 ≤ t ≤ b. This also adopts the max-min optimization of k-centers in Eq. (4), i.e. x∗t = arg maxx∗i ∈{x∗1,x∗2,...,x∗b}minDj∈D0 ∥x ∗ i −Dj∥.
Batch acquisitions. The greedy strategy of Eq. (13) can be written as a batch acquisitions by setting its output as a batch set, i.e.
{x∗t1 , ..., x ∗ tb′
} = arg max x∗t1 ∶tb′ ⊆{x∗1,x∗2,...,x∗b} p(y∗t1∶tb′ ∣x ∗ t1∶tb′ , θ), (14)
where x∗t1∶tb′ = {x ∗ t1 , ..., x ∗ tb′ }, y∗t1∶tb′ = {y ∗ t1 , ..., y ∗ tb′ }, y∗ti denotes the output of x ∗ ti , 1 ≤ i ≤ b ′, and 1 ≤ b′ ≤ b. This setting can be used to accelerate the acquisitions of AL in a large dataset. Appendix A presents the two-stage GBALD algorithm.

heading: 5 EXPERIMENTS
text: In experiments, we start by showing how BALD degenerates its performance with uninformative prior and redundant information, and show that how our proposed GBALD relieves theses limitations.
Our experiments discuss three questions: 1) is GBALD using core-set of Eq. (11) competitive with uninformative prior? 2) can GBALD using ranking of Eq. (14) improve informative acquisitions of model uncertainty? and 3) can GBALD outperform state-of-the-art acquisition approaches? Following the experiment settings of (Gal et al., 2017; Kirsch et al., 2019), we use MC dropout to implement the Bayesian approximation of DNNs. Three benchmark datasets are selected: MNIST, SVHN and CIFAR10. More experiments are presented in Appendix C.

heading: 5.1 UNINFORMATIVE PRIORS
text: As discussed in the introduction, BALD is sensitive to an uninformative prior, i.e. p(D0∣θ). We thus initialize D0 from a fixed class of the tested dataset to observe its acquisition performance. Figure 3 presents the prediction accuracies of BALD with an acquisition budget of 130 over the training
set of MNIST, in which we randomly select 20 samples from the digit ‘0’ and ‘1’ to initialize D0, respectively. The classification model of AL follows a convolutional neural network with one block of [convolution, dropout, max-pooling, relu], with 32, 3x3 convolution filters, 5x5 max pooling, and 0.5 dropout rate. In the AL loops, we use 2,000 MC dropout samples from the unlabeled data pool to fit the training of the network following (Kirsch et al., 2019).
The results show BALD can slowly accelerate the training model due to biased initial acquisitions, which cannot uniformly cover all the label categories. Moreover, the uninformative prior guides BALD to unstable acquisition results. As the shown in Figure 3(b), BALD with Bathsize = 10 shows better performance than that of Batchsize =1; while BALD in Figure 3(a) keeps sta-
ble performance. This is because the initial labeled data does not cover all classes and BALD with Batchsize =1 may further be misled to select those samples from one or a few fixed classes at the first acquisitions. However, Batchsize >1 may result in a random acquisition process that possibly covers more diverse labels at its first acquisitions. Another excursive result of BALD is that the increasing batch size cannot degenerate its acquisition performance in Figure 3(b). Specifically, Batchsize =10 ≻ Batchsize =1 ≻ Batchsize =20,40 ≻ Batchsize =30, where ‘≻’ denotes ‘better’ performance; Batchsize = 20 achieves similar results of Batchsize =40. This undermines the acquisition policy of BALD: its performance would degenerate when the batch size increases, and sometimes worse than random sampling. This also is the reason why we utilize a core-set to start BALD in our framework.
Different to BALD, the core-set construction of GBALD using Eq. (11) provides a complete label matching against all classes. Therefore, it outperforms BALD with the batch sizes of 1, 10, 20, 30, and 40. As the shown learning curves in Figure 3, GBALD with a batch size of 1 and sequence size of 10 (i.e. breakpoints of acquired size are 10, 20, ..., 130) achieves significantly higher accuracies than BALD using different batch sizes since BALD misguides the network updating using poor prior.

heading: 5.2 IMPROVED INFORMATIVE ACQUISITIONS
text: Repeated or similar acquisitions delay the acceleration of the model training of BALD. Following the experiment settings of Section 5.1, we compare the best performance of BALD with a batch size of 1 and GBALD with different batch size parameters. Following Eq. (14), we set b = {3,5,7} and b′=1, respectively, that means, we output the highest representative data from a batch of highly-informative
acquisitions. Different settings on b and b′ are used to observe the parameter perturbations of GBALD.
Training by the same parameterized CNN model as Section 5.1, Figure 4 presents the acquisition performance of parameterized BALD and GBALD. As the learning curves shown, BALD cannot accelerate the model as fast as GBALD due to the repeated information over the acquisitions. For GBALD, it ranks the batch acquisitions of the highly-informative samples and selects the highest representative ones. By employing this special ranking strategy, GBALD can reduce the probability of sampling nearby data of the previous acquisitions. It is thus GBALD significantly outperforms BALD, even if we progressively increase the ranked batch size b.

heading: 5.3 ACTIVE ACQUISITIONS
text: GBALD using Eqs. (11) and (14) has been demonstrated to achieve successful improvements over BALD. We thus combine these two components into a uniform framework. Figure 5 reports the AL accuracies using different acquisition algorithms on the three image datasets. The selected baselines follow (Gal et al., 2017) including 1) maximizing the variation ratios (Var), 2) BALD, 3) maximizing the entropy (Entropy), 4) k-medoids, and one greedy 5) k-centers approach (Sener & Savarese, 2018). The network architecture is a three-layer MLP with three blocks of [convolution, dropout, max-pooling, relu], with 32, 64, and 128 3x3 convolution filters, 5x5 max pooling, and 0.5 dropout rate. In the AL loops, the MC dropout still randomly samples 2,000 data from the unlabeled data pool to approximate the training of the network architecture following (Kirsch et al., 2019). The initial labeled data of MNIST, SVHN and CIFAR-10 are 20, 1000, 1000 random samples from their full training sets. Details of baselines are presented in Appendix C.1.
The batch size of the compared baselines is 100, where GBALD ranks 300 acquisitions to select 100 data for the training, i.e. b = 300, b′ = 100. As the learning curves shown in Figure 5, 1) k-centers algorithm performs more poorly than other compared baselines because the representative optimization with sphere geodesic usually falls into the selection of boundary data; 2) Var, Entropy and BALD algorithms cannot accelerate the network model rapidly due to highly-skewed acquisitions towards few fixed classes at its first acquisitions (start states); 3) k-medoids approach does not interact with the neural network model while directly imports the clustering centers into its training set; 4) The accuracies of the acquisitions of GBALD achieve better performance at the beginning than the Var, Entropy and BALD approaches which fed the training set of the network model via acquisition loops. In short, the network is improved faster after drawing the distribution characteristics of the input dataset with sufficient labels. GBALD thus consists of the representative and informative acquisitions in its uniform framework. Advantages of these two acquisition paradigms are integrated and present higher accuracies than any single paradigm.
Table 1 reports the mean±std values of the test accuracies of the breakpoints of the learning curves in Figure 5, where breakpoints of MNIST are {0,10,20,30, ...,600}, breakpoints of SVHN are {0,100,200, ...,10000}, and breakpoints of CIFAR10 are {0,100,200, ...,20000}. We then calculate their average accuracies and std values over these acquisition
points. As the shown in Table 1, all std values around 0.1, yielding a norm value. Usually, an average
accuracy on a same acquisition size with different random seeds of DNNs, will result a small std value. Our mean accuracy spans across the whole learning curve.
The results show that 1) GBALD achieves the highest average accuracies; k-medoids is ranked the second amongst the compared baselines; 2) k-centers has ranked the worst accuracies amongst these approaches; 3) the others, which iteratively update the training model are ranked at the middle including BALD, Var and Entropy algorithms. Table 2 shows the acquisition numbers of achieving the accuracies of 70%, 80%, and 90% on the three datasets. The three numbers of each cell are the acquisition numbers over MNIST, SVHN, and CIFAR10, respectively. The results show that GBALD can use fewer acquisitions to achieve a desired accuracy than the other algorithms.

heading: 5.4 GBALD VS. BATCHBALD
text: Batch active deep learning was recently proposed to accelerate the training of a DNN model. In recent literature, BatchBALD (Kirsch et al., 2019) extended BALD with a batch acquisition setting to converge the network using fewer iteration loops. Different to BALD, BathBALD introduces diversity to avoid repeated or similar output acquisitions.
How to set the batch size of the acquisitions attracted our eyes before starting the experiments. It involves with whether our experiment settings are fair and reasonable. From a theoretical view, the larger the batch size, the worse the batch acquisitions will be. Experiments results of (Kirsch et al., 2019) also demonstrated this phenomenon. We thus set different batch sizes to run BatchBALD. Figure 6 reports the comparison results of BALD, BatchBALD, and our proposed GBALD following the experiment settings of Section 5.3. As the shown in this figure,
BatchBALD degenerates the test accuracies if we progressively increase the bath sizes, where BatchBALD with a batch size of 10 keeps similar learning curves as BALD. This means BatchBALD actually can accelerate BALD with a similar acquisition result if the batch size is not large. That means, if the batch size is between 2 to 10, BatchBALD will degenerate into BALD and maintains highly-consistent results.
Also because of this, BatchBALD has the same sensitivity to the uninformative prior. For our GBALD, the core-set solicits sufficient data which properly matches the input distribution (w.r.t. acquired data set size ≤ 100), providing powerful input features to start the DNN model (w.r.t.
acquired data set size > 100). Table 3 then presents the mean±std of breakpoints ({0,10,20, ...,600}) of active acquisitions on MNIST with batch settings. The statistical results show GBALD has much higher mean accuracy than BatchBALD with different bath sizes. Therefore, evaluating the model uncertainty of DNN using highly-representative core-set samples can improve the performance of the neural network.
6 CONCLUSION Table 3: Mean±std of BALD, BatchBALD, and GBALD of active acquisitions on MNIST with batch settings.
Algorithms Batch sizes Accuracies BALD 1 0.8654±0.0354
BatchBALD 10 0.8645±0.0365 BatchBALD 40 0.8273±0.0545 BatchBALD 100 0.7902±0.0951
GBALD 3 0.9106±0.1296 We have introduced a novel Bayesian AL framework, GBALD, from the geometric perspective, which seamlessly incorporates representative (core-set) and informative (model uncertainty estimation) acquisitions to accelerate the training of a DNN model. Our GBALD yields significant improvements over BALD, flexibly resolving the limitations of an uninformative prior and redundant information by optimizing the acquisition on an ellipsoid. Generalization analysis has asserted that training with ellipsoid has tighter lower error bound and higher probability to achieve a zero error than training with a typical sphere. Compared to the representative or informative acquisition algorithms, experiments show that our GBALD spends much fewer acquisitions to accelerate the accuracy. Moreover, it keeps slighter accuracy reduction than other baselines against repeated and noisy acquisitions.

heading: A. TWO-STAGE GBALD ALGORITHM
text: The two-stage GBALD algorithm is described as follows: 1) construct core-set on ellipsoid (Lines 3 to 13), and 2) estimate model uncertainty with a deep learning model (Lines 14 to 21). Core-set construction is derived from the max-min optimization of Eq. (10), then updated with ellipsoid geodesic w.r.t. Eq. (11), where θ yields a geometric probability model w.r.t. Eq. (5). Importing the core-set into D0 derives the deep learning model to return b informative acquisitions one time, where θ yields a deep learning model. Ranking those samples, we select b′ samples with the highest representations as the batch outputs. The iterations of batch acquisitions stop until its budget is exhaust. The final update on D0 is our acquisition set of AL.
Details of the hyperparameter settings are presented at Appendix C.6.
Algorithm 1: Two-stage GBALD Algorithm 1 Input: Data set X , core-set size NM, batch returns b, batch output b′, iteration budget A. 2 Initialization: α ← 0, core-setM← ∅. 3 Stage 1© begins: 4 Initialize θ to yield a geometric probability model w.r.t. Eq. (5). 5 Perform k-means to initialize U to D0. 6 Core-set construction begins by acquiring x∗i , 7 for i← 1,2, ...,NM do
8 x∗i ← arg maxxi∈Du minDi∈D0 ⎧⎪⎪ ⎨ ⎪⎪⎩ ∥L0 −L∥ 2 + logp(yi∣xi, θ) ⎫⎪⎪ ⎬ ⎪⎪⎭ , where
L0 ← ∣∑ N i=1Eyi[logp(yi∣xi, θ) +H[yi∣xi,U]]∣.
9 Ellipsoid geodesic line scales x∗i : x ∗ i ← arg minxj∈Du ∥xj − [xi + η(x ∗ − xi)]∥.
10 Update x∗i into core-setM:M← x ∗ i ∪M. 11 Update N ← N − 1. 12 end 13 Import core-set to update D0: D0 ←M ∪ U ′, where U ′ updates each element of U into their
nearest samples in X . 14 Stage 2© begins: 15 Initialize θ to yield a deep learning model. 16 while α < A do 17 Return b informative deep learning acquisitions in one budget:
{x∗1, x ∗ 2, ..., x ∗ b}← arg maxx∈Du H[θ∣D0] −Ey∼p(y∣x,D0)[H[θ∣x, y,D0]].
18 Rank b′ informative acquisitions with the highest geometric representativeness: {x∗t1 , ..., x ∗ tb′ }← arg maxx∗i ∈{x∗1,x∗2,...,x∗b} p(yi∣x ∗ i , θ). 19 Update {x∗t1 , ..., x ∗ tb′ } into D0: D0 ← D0 ∪ {x∗t1 , ..., x ∗ tb′
}. 20 α ← α + 1. 21 end 22 Output: final update on D0.

heading: B. GENERALIZATION ERRORS OF GEODESIC SEARCH WITH SPHERE AND ELLIPSOID
text: Optimizing with ellipsoid geodesic linearly rescales the spherical search on tighter geometric object. The inherent motivation is that the ellipsoid can prevent the updates of core-set towards the boundary regions of the sphere. This section presents generalization error analysis from geometry, which provides feasible error guarantees for geodesic search with ellipsoid, following the perceptron analysis. Proofs are presented in Appendix D.

heading: B.1 ERROR BOUNDS OF GEODESIC SEARCH WITH SPHERE
text: Given a perceptron function h ∶=w1x1 +w2x2 +w3, the classification task is over two classes A and B embedded in a three-dimensional geometry. Let SA and SB be the spheres that tightly cover A and B, respectively, where SA is with a center ca and radius Ra, and SB is with a center cb and radius Rb. Under this setting, generalization analysis is presented. Theorem 1. Given a linear perceptron function h = w1x1 +w2x2 +w3 that classifies A and B, and a sampling budget k, with representation sampling over SA and SB , the minimum distances to the boundaries of SA and SB of that representation data are defined as da and db, respectively. Let err(h, k) be the classification error rate with respect to h and k, π
ϕ = arcsinRa−da Ra , we then have an
inequality of error:
min ⎧⎪⎪ ⎨ ⎪⎪⎩ 4R3a − (2Ra + tk)(Ra − tk) 2 4R3a + 4R 3 b , 4R3b − (2Rb + t ′ k)(Rb − t ′ k) 2 4R3b + 4R 3 a ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h, k) < 1 k ,
where tk = R2a 3 + 3
√
− µk 2π +
√ µ2 k
4π2 − π3R3a 27π3 + 3
√
− µk 2π −
√ µ2 k
4π2 − π3R3a 27π3 , µk = ( 2k−43k − 1 ϕ cosπ ϕ )πR3a −
4πR3b 3k , t′k = R2b 3 + 3
√
− µ′ k
2π +
√ µ′2 k
4π2 − π3R3 b 27π3 + 3
√
− µ′ k
2π −
√ µ′2 k
4π2 − π3R3 b 27π3 , and µ′k = ( 2k−4 3k − 1 ϕ cosπ ϕ )πR3b −
4πR3a 3k .

heading: B.2 ERROR BOUNDS OF GEODESIC SEARCH WITH ELLIPSOID
text: Given class A and B are tightly covered by ellipsoid Ea and Eb in a three-dimensional geometry. Let Ra1 be the polar radius of Ea, {Ra2 ,Ra3} be the equatorial radii of Ea, Rb1 be the polar radius of Eb, and {Rb2 ,Rb3} be the equatorial radii of Eb, the generalization analysis is ready to present following these settings. Theorem 2. Given a linear perceptron function h = w1x1 +w2x2 +w3 that classifies A and B, and a sampling budget k, with representation sampling over Ea and Eb, the minimum distance to the boundaries of Ea and Eb of that representation data are defined as da and db, respectively. Let err(h, k) be the classification error rate with respect to h and k, π
ϕ = arcsinRa−da Ra , we then have an
inequality of error:
min ⎧⎪⎪ ⎨ ⎪⎪⎩ 4∏iRai − (2Ra1 + λk)(Ra1 − λk) 2 4∏iRai + 4∏iRbi , 4∏iRbi − (2Rb1 + λ ′ k)(Rb1 − λ ′ k) 2 4∏iRbi + 4∏iRai ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h, k) < 1 k ,
where i = 1,2,3, λk = R2a1 3 + 3
√
− σk 2π +
√ σ2 k
4π2 − π3R3a1 27π3 + 3
√
− σk 2π −
√ σ2 k
4π2 − π3R3a1 27π3 , σk = ( 2k−43k −
πRa1 2ϕ )π∏iRai − 4π∏iRbi 3k , λ′k = R2b1 3 + 3
√
− σk 2π +
√ σ′2 k
4π2 − π3R3 b1 27π3 + 3
√
− σk 2π −
√ σ2 k
4π2 − π3R3 b1 27π3 , and
σ′k = ( 2k−4 3k − πRb1 2ϕ )π∏iRbi − 4π∏iRai 3k .

heading: B.3 PROBABILITY BOUNDS OF ACHIEVING A ZERO GENERALIZATION ERROR
text: Let Pr[err(h, k) = 0]Sphere and Pr[err(h, k) = 0]Ellipsoid be the probabilities of achieving a zero generalization error of geodesic search with sphere and ellipsoid, respectively, we present their inequality relationship. Theorem 3. Based on γ-tube theory (Ben-David & Von Luxburg, 2008) of clustering stability, the probability of achieving a zero generalization error of geodesic search with ellipsoid can be defined as the volume ratio of Vol(Tube)
Vol(Sphere) . Then, we have:
Pr[err(h, k) = 0]Sphere = 1 − t3k R3a ,
where tk keeps consistent with Theorem 1. Theorem 4. Based on γ-tube theory (Ben-David & Von Luxburg, 2008) of clustering stability, the probability of achieving a zero generalization error of geodesic search with ellipsoid can be defined as the volume ratio of Vol(Tube)
Vol(Ellipsoid) . Then, we have:
Pr[err(h, k) = 0]Ellipsoid = 1 − λk1λk2λk3 Ra1Ra2Ra3 ,
where λki = R2ai 3 + 3
√
− σki 2π +
√ σ2 ki
4π2 − π3R3ai 27π3 + 3
√
− σki 2π −
√ σ2 ki
4π2 − π3R3ai 27π3 , and σki = ( 2k−4 3k −
πRai 2ϕ )πRa1Ra2Ra3 − 4πRb1Rb2Rb3 3k , i = 1,2,3.

heading: B.4 MAIN THEORETICAL RESULTS OF GEODESIC SEARCH WITH ELLIPSOID

heading: TIGHTER LOWER ERROR BOUND
text: Let lower[err(h, k)]Sphere and lower[err(h, k)]Ellipsoid be the lower bounds of the generalization errors of geodesic search with sphere and ellipsoid, respectively. With Ra1 < Ra, compare Theorem 1 and Theorem 2, we have the following proposition. Proposition 1. Given a linear perceptron function h = w1x1 +w2x2 +w3 that classifies A and B, and a sampling budget k. With representation sampling over Sa and Sb, let err(h, k) be the classification error rate with respect to h and k, the lower bounds of geodesic search with sphere and ellipsoid satisfy: lower[err(h, k)]Ellipsoid < lower[err(h, k)]Sphere.

heading: HIGHER PROBABILITY OF ACHIEVING A ZERO ERROR
text: Let Pr[err(h, k) = 0]Sphere and Pr[err(h, k) = 0]Ellipsoid be the probabilities of achieving a zero generalization error of geodesic search with sphere and ellipsoid, respectively. Their relationship is presented in Proposition 2. Proposition 2. Given a linear perceptron function h = w1x1 +w2x2 +w3 that classifies A and B, and a sampling budget k. With representation sampling over Ea and Eb, let err(h, k) be the classification error rate with respect to h and k, the probabilities of geodesic search with sphere and ellipsoid satisfy: Pr[err(h, k) = 0]Ellipsoid > Pr[err(h, k) = 0]Sphere.
With these theoretical results, geometric interpretation of geodesic search over ellipsoid is more effective than sphere due to tighter lower error bound and higher probability to achieve zero error. Theorems 6 and 7 of Appendix D then present a high-dimensional generalization for the above theoretical results in terms of the volume functions of sphere and ellipsoid.

heading: C. EXPERIMENTS

heading: C.1 BASELINES
text: To evaluate the performance of GBALD, several typical baselines from the latest deep AL literatures are selected.
• Bayesian active learning by disagreement (BALD) (Houlsby et al., 2011). It has been introduced in Section 3.
• Maximize Variation Ratio (Var) (Gal et al., 2017). The algorithm chooses the unlabeled data that maximizes its variation ratio of the probability:
x∗ = arg max x∈Du {1 −max y∈Y Pr(y∣, x,D0))}. (15)
• Maximize Entropy (Entropy) (Gal et al., 2017). The algorithm chooses the unlabeled data that maximizes the predictive entropy:
x∗ = arg max x∈Du { − ∑ y∈Y Pr(y∣x,D0))log(Pr(y∣x,D0))}. (16)
The parameter settings of Eq. (5) are R0 = 2.0e + 3 and η =0.9. Accuracy of each acquired dataset size of the experiments are averaged over 3 runs.

heading: C.2 ACTIVE ACQUISITIONS WITH REPEATED SAMPLES
text: Repeatedly collecting samples in the establishment of a database is very common. Those repeated samples may be continuously evaluated as the primary acquisitions of AL due to the lack of one or more kinds of class labels. Meanwhile, this situation may lead the evaluation of the model uncertainty to fall into repeated acquisitions. To respond this collecting situation, we compare the acquisition performance of BALD, Var, and GBALD using 5,000 and 10,000 repeated samples from the first 5,000 and 10,000 unlabeled data of SVHN, respectively. In addition, the unsupervised algorithms which do not interact with the network architecture, such as k-medoids and k-centers, have been shown that they cannot accelerate the training in terms of the experiment results of Section 5.3. Thus, we are no longer studying their performance. The network architecture still follows the settings of the MLP as Section 5.3.
The acquisition results over the repeated SVHN datasets are presented in Figure 7. The batch sizes of the compared baselines are 100, where GBALD ranks 300 acquisitions to select 100 data for the training, i.e. b = 300, b′ = 100. The mean±std values of these baselines of the breakpoints (i.e. {0,100,200, ...,10000}) are reported in Table 4. Results demonstrate that GBALD shows slighter perturbations on repeated samples than Var and BALD because it draws the core-set from the input distribution as the initial acquisition, leading small probability to sample from one or more fixed class. In GBALD, the informative acquisitions constrained with geometric representations further scatter the acquisitions spread in different classes. However, Var and BALD algorithms have no particular schemes against the repeated acquisitions. The maximizer on the model uncertainty may be repeatedly produced by those repeated samples. In additional, the unsupervised algorithms such as k-medoids and k-centers don not have these limitations, but cannot accelerate the training since there has no interactions with the network architecture.

heading: BALD,Batchsize=100, 0 Receptions
text: 0 2000 4000 6000 8000 10000
Acquired dataset size
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
A c c u
ra c y
Var,Batchsize=100, 0 Noises Var,Batchsize=100, 5000 Noises Var,Batchsize=100, 100000 Noises
(a) Var
0 2000 4000 6000 8000 10000
Acquired dataset size
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
A c c u ra
c y
BALD,Batchsize=100, 0 Noises BALD,Batchsize=100, 5000 Noises BALD,Batchsize=100, 100000 Noises
(b) BALD
0 2000 4000 6000 8000 10000
Acquired dataset size
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
A c c u ra
c y
GBALD,Batchsize=300, 0 Noises GBALD,Batchsize=300, 5000 Noises GBALD,Batchsize=300, 100000 Noises
(c) GBALD
Figure 8: Active noisy acquisitions on SVHN with 5,000 and 10,000 noisy labels.

heading: C.3 ACTIVE ACQUISITIONS WITH NOISY SAMPLES
text: Noisy labels (Golovin et al., 2010) (Han et al., 2018) are inevitable due to human errors in data annotation. Training on noisy labels, the neural network model will degenerate its inherent properties. To assess the perturbations of the above acquisition algorithms against noisy labels, we organize the following experiment scenarios: we select the first 5,000 and 10,000 samples respectively from the unlabeled data pool of the MNIST dataset and reset their labels by shifting {‘0’,‘1’,...,‘8’} to {‘1’,‘2’,...,‘9’}, respectively. The network architecture follows MLP of Section 5.3. The selected baselines are Var and BALD.
Figure 7 presents the acquisition results of those baseline with noisy labels. The batch sizes of the compared baselines are 100, where GBALD ranks 300 acquisitions to select 100 data for the training, i.e. b = 300, b′ = 100. Table 5 presents the mean±std values of the breakpoints (i.e. {0,100,200, ...,10000}) over learning curves of Figure 8. The results further show that GBALD has smaller noisy perturbations than other baselines. For Var and BALD, model uncertainty leads high probabilities to sample those noisy data due to their greatly updating on the model.

heading: C.5 ACCELERATION OF ACCURACY
text: Accelerations of accuracy i.e. the first-orders of breakpoints of the learning curve, describe the efficiency of the active acquisition loops. Different to the accuracy curves, the acceleration curve reflects how active acquisitions help the convergence of the interacting DNN model.
We thus firstly present the acceleration curves of different baselines on MNIST, SVHN, and CIFAR10 datasets following the experiments of Section 5.3. The acceleration curves of active acquisitions are drawn in Figure 9. Observing those acceleration curves of different algorithms clearly finds that, GBALD always keeps higher accelerations of accuracy than the other baselines against the three benchmark datasets. This revels the reason of why GBALD can derive more informative and representative data to maximally update the DNN model.
The acceleration curves of active acquisitions with repeated samples of Appendix C.2 are presented in Figure 10. As the shown in this figure, GBALD presents slighter perturbations to the number of repeated samples than that of Var and BALD due to its effective ranking scheme on optimizing model uncertainty of DNN. The acceleration curves of active noisy acquisitions of Section Appendix C.3 are drawn in Figure 11. Compared to Figure 7, it presents more intuitive descriptions for the noisy perturbations to different baselines. With horizontal comparisons to acceleration curves of Var and BALD, our proposed GBALD has smaller noisy perturbations due to 1) the powerful core-set which properly captures the input distribution, and 2) highly representative and informative acquisitions of model uncertainty.

heading: BALD,Batchsize=100, 0 Receptions

heading: C.6 HYPERPARAMETER SETTINGS
text: What is the proper time to start active acquisitions using Eq. (14) in GBALD framework? Does the ratio of core-set and model uncertainty acquisitions affect the performance of GBALD?
We discuss the key hyperparameter of GBALD here: core-set size NM. Table 6 presents the relationship of accuracies and the sizes of core-set, where the start accuracy denotes the test accuracy over the initial core-set, and the ultimate accuracy denotes the test accuracy over up to Q = 20,000 training data. Let b = 1000, b′ = 500 in GBALD,NM be the number of the core-set size, the iteration budget A of GBALD then can be defined as A = (Q −NM)/b′. For example, if the number of the initial core-set labels are set as NM = 1,000, we have A = (Q −NM)/b′ ≈ 38; ifNM = 2,000, then A = (Q −NM)/b ′ ≈ 36.
From Table 6, GBALD algorithm keep stable accuracies over the start, ultimate, and mean±std accuracies when there inputs more than 1,000 core-set labels. Therefore, drawing sufficient core-set labels using Eq. (10) to start the model uncertainty of Eq. (14) can maximize the performance of our GBALD framework.
Hyperparameter settings on batch returns b and bath outputs b′. Experiments of Sections 5.1 and 5.2 used different b and b′ to observe the parameter perturbations. No matter what the settings of b′ and b are, GBALD still outperforms BALD. For single acquisition of GBALD, we suggest b = 3 and b′ = 1. For bath acquisitions, the settings on b′ and b are user-defined according the time cost and hardware resources.
Hyperparameter setting on iteration budget A. Given the acquisition budget Q, let b′ be the number of the output returns at each loop,NM be the number of the core-set size, the iteration budget A of GBLAD then can be defined as A = (Q −NM)/b′.
Other hyperparameter settings. Eq. (5) has one parameter R0 which describes the geometry prior from probability. The default radius of the intern balls R0 is used to legalize the prior and has no further influences on Eq. (10). It is set as R0 = 2.0e + 3 for those three image datasets. Ellipsoid
geodesic is adjusted by η which controls how far of the updates of core-set to the boundaries of the distributions. It is set as η = 0.9 in this paper.
C.7 TWO-SIDED t-TEST
We present two-sided (two-tailed) t-test for the learning curves of Figure 5. Different to the mean± std of Table 1, t-test can enlarge the significant difference of those baselines. In typical t-test, the two groups of observations usually require a degree of freedom smaller than 30. However, the numbers of breakpoints of MNIST, SVHN, and CIFAR10 are 61, 101, and 201, respectively, thereby holding a degree of freedom of 60, 100, 200, respectively. It is thus we introduce t-test score to directly compare the significant difference of pairwise baselines.
t-test score between any pair group of breakpoints are defined as follows. Let B1 = {α1, α2, ..., αn} and B2 = {β1, β2, ..., βn}, there exists t-score of
t − score = √ n µ
σ ,
where µ = 1 n ∑ n i=1(αi − βi), and σ = √ 1 n−1 ∑ n i=1(αi − βi − µ) 2.
In two-sided t-test, B1 beats B2 on breakpoints αi and βi satisfying a condition of t − score > ν; B2 beats B1 on breakpoints αi and βi satisfying a condition of t − score < −ν, where ν denotes the hypothesized criterion with a given confidence risk. Following (Ash et al., 2019), we add a penalty of 1
e to each pair of breakpoints, which further enlarges their differences in the aggregated penalty matrix, where e denotes the number of B1 beats B2 on all breakpoints. All penalty values finally calculate their L1 expressions.
Figure 12 presents the penalty matrix over learning curves of Figure 5. Column-wise values at the bottom of each matrix show the overall performance of the compared baselines. As the shown results, GBALD has significant performances than that of the other baselines over the three datasets. Especially for SVHN, it has superior performance.

heading: D. PROOFS
text: We firstly present the generalization errors of k = 3 of AL with sphere as a case study. The assumption of the generalization analysis is described in Figure 13.
D.1 CASE STUDY OF GENERALIZATION ANALYSIS OF err(h,3) OF GEODESIC SEARCH WITH

heading: SPHERE
text: Theorem 5. Given a linear perceptron function h = w1x1 +w2x2 +w3 that classifies A and B, and a sampling budget k. With representation sampling over Sa and Sb, the minimum distance to the boundaries of SA and SB of that representation data are defined as da and db, respectively. Let err(h, k) be the classification error rate with respect to h and k, π
ϕ = arcsinRa−da Ra , we have an
inequality of error:
min ⎧⎪⎪ ⎨ ⎪⎪⎩ (2Ra + t)(Ra − t) 2 4R3a + 4R 3 b , (2Rb + t ′)(Rb − t ′)2 4R3b + 4R 3 a ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h,3) < 0.3334,
where t = R 2 a
3 +
3
√
− µ 2π +
√ µ2
4π2 − π3R3a 27π3 + 3
√
− µ 2π −
√ µ2
4π2 − π3R3a 27π3 , µ = ( 2 9 − 1 ϕ cosπ ϕ )πR3a − 4πR3b 9 ,
t′ = R2b 3 + 3
√
− µ′
2π +
√ µ′2
4π2 − π3R3 b 27π3 + 3
√
− µ′
2π −
√ µ′2
4π2 − π3R3 b 27π3 , and µ′ = ( 2 9 − 1 ϕ cosπ ϕ )πR3b − 4πR3a 9 .
Proof. Given the unseen acquisitions of {qa, qb, q∗}, where qa ∈ A, qb ∈ B, and q∗ ∈ A or q∗ ∈ B is uncertain. However, the position of q∗ largely decides h. Therefore, the proof studies the error bounds highly related to q∗ in terms of two cases: Ra ≥ Rb and Ra < Rb.
1) If Ra ≥ Rb, q∗ ∈ A. Estimating the position of q∗ starts from the analysis on qa. Given the volume function Vol(⋅) over the 3-D geometry, we know: Vol(A) = 4π
3 R3a and Vol(B) = 4π 3 R3b . Given k = 3
over Sa and Sb, we define the minimum distance of qa to the boundary of A as da. Let Sa be cut off by a cross section h′, where C be the cut and D be the spherical cap1 of the half-sphere (see Figure 12) that satisfy
Vol(C) = 2
3 πR3a −Vol(D) =
4π(R3a +R 3 b)
9 , (19)
and the volume of D is
Vol(D) = π( √ R2a − (Ra − da) 2) 2 (Ra − da) + ∫
2π √ R2a−(Ra−da)2
0
arcsinRa−da Ra
2π πR2a dx
= π(R2a − (Ra − da) 2 )(Ra − da) +
arcsinRa−da Ra
2π πR2a(2π
√ R2a − (Ra − da) 2)
= π(R2a − (Ra − da) 2 )(Ra − da) + πR 2 aarcsin Ra − da Ra √ R2a − (Ra − da) 2.
(20)
1https://en.wikipedia.org/wiki/Spherical_cap
Let π ϕ = arcsinRa−da Ra , Eq. (20) can be written as
Vol(D) = π(R2a − (Ra − da) 2 )(Ra − da) + πR3a ϕ cos π ϕ . (21)
Introducing Eq. (21) to Eq. (19), we have
( 2 3 − 1 ϕ cos π ϕ )πR3a − π(R 2 a − (Ra − da) 2 )(Ra − da) =
4π(R3a +R 3 b)
9 . (22)
Let t = Ra − da, Eq. (22) can be rewritten as
πt3 − πR2at + ( 2 9 − 1 ϕ cos π ϕ )πR3a − 4πR3b 9 = 0. (23)
To simplify Eq. (23), let µ = ( 2 9 − 1 ϕ cosπ ϕ )πR3a − 4πR3b 9
, Eq. (23) then can be written as πt3 − πR2at + µ = 0. (24)
The positive solution of t can be
t = R2a 3 + 3
¿ Á ÁÀ
− µ
2π +
√ µ2
4π2 − π3R3a 27π3 + 3
¿ Á ÁÀ
− µ
2π −
√ µ2
4π2 − π3R3a 27π3 . (25)
Based on Eq. (19), we know
Vol(D) = 2
3 πR3a −
4π(R3a +R 3 b)
9
= 2
9 πR3a −
4 9 πR3b > 0.
(26)
Thus, 3 √ 2Rb < Ra. We next prove q∗ ∈ A. Based on Eq. (26), we know
πR3b < 1
2 πR3a. (27)
Then, the following inequalities hold: 1)2πR3b < πR 3 a, 2) 2 3 πR3b < 1 3 πR3a, and 3) 2 3 πR3b + 1 3 πR3b < 1 3 πR3a + 1 3 πR3b . Finally, we have
πR3b < 1
3 (πR3a + πR 3 b). (28)
Therefore, Vol(B) < 1 3 (Vol(A) + Vol(B)). We thus know: 1) qa ∈ A and it is with a minimum distance da to the boundary of Sa, 2) qb ∈ B, and 3) q∗ ∈ A. Therefore, class B can be deemed as having a very high probability to achieve a nearly zero generalization error and the position of q∗ largely decides the upper bound of the generalization error of h.
In Sa that covers class A, the nearly optimal error region can be bounded as the spherical cap of Sa with a volume constraint of Vol(A) −Vol(C). We thence have an inequality of
Vol(A) −Vol(C) Vol(A) +Vol(B) < err(h,3) < 1 3 . (29)
We next calculate the volume of the spherical cap:
Vol(A) −Vol(C) = ∫ Ra−da
−Ra πx2d y
= π∫ Ra
Ra−da R2a − y 2d y
= 4
3 πR3a − πd 2 a(Ra − da 3 ).
(30)
Eq. (29) then is rewritten as 4 3 πR3a − π 3 (3Ra − da)d 2 a
4 3 πR3a + 4 3 πR3b
< err(h,3) < 0.3334, (31)
Then, we have the error bound of 4R3a − (3Ra − da)d 2 a
4R3a + 4R 3 b
< err(h,3) < 0.3334. (32)
Introducing da = Ra − t, Eq. (32) is written as 4R3a − (2Ra + t)(Ra − t) 2
4R3a + 4R 3 b
< err(h,3) < 0.3334. (33)
2) With another assumption of Ra < Rb, we follow the same proof skills of Ra ≥ Rb and know 4R3b−(3Rb−db)d 2 b
4R3 b +4R3a
< err(h,3) < 0.3334, i.e. where db = Rb−t′ and t′ = R2b 3 + 3
√
− µ′
2π +
√ µ′2
4π2 − π3R3 b 27π3 +
3
√
− µ′
2π −
√ µ′2
4π2 − π3R3 b 27π3 , and µ′ = ( 2 9 − 1 ϕ cosπ ϕ )πR3b − 4πR3a 9 .
We thus conclude that min ⎧⎪⎪ ⎨ ⎪⎪⎩ 4R3a−(2Ra+t)(Ra−t) 2 4R3a+4R3b , 4R3b−(2Rb+t ′)(Rb−t′)2 4R3 b +4R3a ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h,3) < 0.3334.

heading: D.2 PROOF OF THEOREM 1
text: We next present the generalization errors against an agnostic sampling budget k following the above proof technique.
Proof. The proof studies two cases: Ra ≥ Rb and Ra < Rb. 1) If Ra ≥ Rb, we estimate the optimal position of qa that satisfies qa ∈ A. Given the volume function Vol(⋅) over the 3-D geometry, we know: Vol(A) = 4π
3 R3a and Vol(B) = 4π 3 R3b . Assume qa be the nearest representative data to the
boundary of Sa, qb be the nearest representative data to the boundary of Sb, and q∗ be the nearest representative data to h either in Sa or Sb. Given the minimum distance of qa to the boundary of A as da. Let Sa be cut off by a cross section h′, where C be the cut and D be the spherical cap of the half-sphere that satisfy
Vol(C) = 2
3 πR3a −Vol(D) =
4π(R3a +R 3 b)
3k , (34)
and the volume of D is
Vol(D) = π( √ R2a − (Ra − da) 2) 2 (Ra − da) + ∫
2π √ R2a−(Ra−da)2
0
arcsinRa−da Ra
2π πR2a dx
= π(R2a − (Ra − da) 2 )(Ra − da) +
arcsinRa−da Ra
2π πR2a(2π
√ R2a − (Ra − da) 2)
= π(R2a − (Ra − da) 2 )(Ra − da) + πR 2 aarcsin Ra − da Ra √ R2a − (Ra − da) 2.
(35)
Let π ϕ = arcsinRa−da Ra , Eq. (36) can be written as
Vol(D) = π(R2a − (Ra − da) 2 )(Ra − da) + πR3a ϕ cos π ϕ . (36)
Introducing Eq. (36) to Eq. (34), we have
( 2 3 − 1 ϕ cos π ϕ )πR3a − π(R 2 a − (Ra − da) 2 )(Ra − da) =
4π(R3a +R 3 b)
3k . (37)
Let tk = Ra − da, we know
πt3 − πR2at + ( 2k − 4 3k − 1 ϕ cos π ϕ )πR3a − 4πR3b 3k = 0. (38)
To simplify Eq. (38), let µk = ( 2k−43k − 1 ϕ cosπ ϕ )πR3a − 4πR3b 3k
, Eq. (38) then can be written as πt3 − πR2at + µk = 0. (39)
The positive solution of tk can be
tk = R2a 3 + 3
¿ Á ÁÀ
− µk 2π + √ µ2k 4π2 − π3R3a 27π3 + 3
¿ Á ÁÀ
− µk 2π − √ µ2k 4π2 − π3R3a 27π3 . (40)
Based on Eq. (35), we know
Vol(D) = 2
3 πR3a −
4π(R3a +R 3 b)
3k
= 2k − 4
3k πR3a −
4
3k πR3b > 0.
(41)
Thus, 3 √
2 k−2Rb < Ra. We next prove q ∗ ∈ A. According to Eq. (41), we know
πR3b < k − 2
2 πR3a. (42)
Then, the following inequalities hold: 1) 2 k−2πR 3 b < πR 3 a, 2) 2 (k−2)kπR 3 b < 1 k πR3a, and 3) 2 (k−2)kπR 3 b+ k2−2k−2 (k−2)k πR 3 b < 1 k πR3a + k2−2k−2 (k−2)k πR 3 b . Finally, we have:
πR3b
< 1
k πR3a +
k2 − 2k − 2
(k − 2)k πR3b
= 1
k π(R3a +R 2 b) −
2
(k − 2)k πR3a
< 1
k π(R3a +R 3 b).
(43)
Therefore, Vol(B) < 1 k (Vol(A) + Vol(B)). We thus know: 1) qa ∈ A and it is with a minimum distance da to the boundary of Sa, 2) qb ∈ B, and 3) q∗ ∈ A. Therefore, class B can be deemed as having a very high probability to achieve a zero generalization error and the position of q∗ largely decides the upper bound of the generalization error of h.
In Sa that covers class A, the nearly optimal error region can be bounded as Vol(A) −Vol(C). We then have the inequality of
Vol(A) −Vol(C) Vol(A) +Vol(B) < err(h, k) < 1 k . (44)
Based on the volume equation of the spherical cap in Eq. (30), we have 4 3 πR3a − π 3 (3Ra − da)d 2 a
4 3 πR3a + 4 3 πR3b
< err(h, k) < 1
k . (45)
Then, we have the error bound of 4R3a − (3Ra − da)d 2 a
4R3a + 4R 3 b
< err(h, k) < 1
k . (46)
Introducing da = Ra − tk, Eq. (46) is written as 4R3a − (2Ra + t)(Ra − tk) 2
4R3a + 4R 3 b
< err(h, k) < 1
k . (47)
2) With another assumption of Ra < Rb, we follow the same proof skills of Ra ≥ Rb and know 4R3b−(3Rb−db)d 2 b
4R3 b +4R3a
< err(h, k) < 1 k , where db = Rb − t′k and t ′ k = R2b 3 + 3
√
− µ′ k
2π +
√ µ′2 k
4π2 − π3R3 b 27π3 +
3
√
− µ′ k
2π −
√ µ′2 k
4π2 − π3R3 b 27π3 , and µ′k = ( 2k−4 3k − 1 ϕ cosπ ϕ )πR3b − 4πR3a 3k .
We thus conclude that min ⎧⎪⎪ ⎨ ⎪⎪⎩ 4R3a−(2Ra+tk)(Ra−tk) 2 4R3a+4R3b , 4R3b(2Rb+t ′ k)(Rb−t ′ k) 2 4R3 b +4R3a ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h, k) < 1 k .

heading: D.3 PROOF OF THEOREM 2
text: Proof. Given class A and B are tightly covered by ellipsoid Ea and Eb in a three-dimensional geometry. Let Ra1 be the polar radius of Ea, {Ra2 ,Ra3} be the equatorial radii of Ea, Rb1 be polar radius of Eb, and {Rb2 ,Rb3} be the equatorial radii of Eb. Based on Eq. (10), we know Rai < Ra,Rbi < Rb,∀i, where Ra and Rb are the radii of the spheres over the class A and B, respectively. We follow the same proof technique of Theorem 1 to present the generalization errors of AL with ellipsoid.
The proof studies two cases: Ra1 ≥ Rb and Ra1 < Rb1 . 1) If Ra1 ≥ Rb1 , q ∗ ∈ A. Given the volume function Vol(⋅) over the 3-D geometry, we know: Vol(A) = 4π 3 Ra1Ra2Ra3 and Vol(B) = 4π 3 Rb1Rb2Rb3 . Given the minimum distance of qa to the boundary of A as da. Let Ea by cut off by a cross section h′, where C be the cut and D be the ellipsoid cap of the half-ellipsoid that satisfy
Vol(C) = 2
3 πR1aR 2 aR 3 a −Vol(D) =
4π(Ra1Ra2Ra3 +Rb1Rb2Rb3)
3k , (48)
and the volume of D is approximated as
Vol(D) ≈ π( √ R2a1 − (Ra1 − da) 2) 2 (Ra1 − da) + ∫ πRa2Ra3
0
arcsin Ra1−da Ra1
2π πR2a1 dx
= π(R2a1 − (Ra1 − da) 2 )(Ra1 − da) +
arcsin Ra1−da Ra
2π πR2a1(πRa2Ra3)
= π(R2a1 − (Ra1 − da) 2 )(Ra1 − da) +
1 2 πR2a1Ra2Ra3arcsin Ra1 − da Ra1 .
(49)
Let π ϕ = arcsin Ra1−da Ra1 , Eq. (49) can be written as
Vol(D) = π(R2a1 − (Ra1 − da) 2 )(Ra1 − da) +
π2 2ϕ R2a1Ra2Ra3 . (50)
Introducing Eq. (50) to Eq. (48), we have
( 2 3 − πRa1 2ϕ )πRa1Ra2Ra3 − π(R 2 a1 − (Ra1 − da) 2 )(Ra1 − da) = 4π(Ra1Ra2Ra3 +Rb1Rb2Rb3) 3k .
(51)
Let λk = Ra1 − da, we know
πλ3k − πR 2 aλk + (
2k − 4 3k − πRa1 2ϕ )πRa1Ra2Ra3 − 4πRb1Rb2Rb3 3k = 0. (52)
To simplify Eq. (52), let σk = ( 2k−43k − πRa1 2ϕ )πRa1Ra2Ra3 − 4πRb1Rb2Rb3 3k , Eq. (52) then can be written as πλ3k − πR 2 a1λk + σk = 0. (53)
The positive solution of λk can be
λk = R2a1 3 + 3
¿ Á ÁÀ
− σk 2π + √ σ2k 4π2 − π3R3a1 27π3 + 3
¿ Á ÁÀ
− σk 2π − √ σ2k 4π2 − π3R3a1 27π3 . (54)
The remaining proof process follows Eq. (40) to Eq. (46) of Theorem 1. We thus conclude that
min ⎧⎪⎪ ⎨ ⎪⎪⎩ 4∏iRai − (2Ra1 + λk)(Ra1 − λk) 2 4∏iRai + 4∏iRbi , 4∏iRbi − (2Rb1 + λ ′ k)(Rb1 − λ ′ k) 2 4∏iRbi + 4∏iRai ⎫⎪⎪ ⎬ ⎪⎪⎭ < err(h, k) < 1 k ,
(55)
where i = 1,2,3, λ′k = R2b1 3 + 3
√
− σk 2π +
√ σ′2 k
4π2 − π3R3 b1 27π3 + 3
√
− σk 2π −
√ σ2 k
4π2 − π3R3a1 27π3 , and σ′k = ( 2k−4 3k −
πRb1 2ϕ )πRb1Rb2Rb3 − 4πRa1Ra2Ra3 3k . In a simple way, Ra1Ra2Ra3 and Rb1Rb2Rb3 can be written as ∏iRai and∏iRbi , i=1,2,3, respectively.

heading: D.4 PROOF OF THEOREM 3
text: Proof. In clustering stability, γ-tube structure that surrounds the cluster boundary largely decides the performance of a learning algorithm. Definition of γ-tube is as follows.
Definition 1. γ-tube Tubeγ(f) is a set of points distributed in the boundary of the cluster. Tubeγ(f) ∶= {x ∈X ∣`(x,B(f)) ≤ γ}, (56)
where X is a noise-free cluster with n samples, B(f) ∶= {x ∈ X,f is discontinuous at x }, f is a clustering function, and `(⋅, ⋅) denotes the distance function.
Following this conclusion, representation data can achieve the optimal generalization error if they are spread over the tube structure. Let γ = da, the probability of achieving a nearly zero generalization error can be expressed as the volume ration of γ-tube and Sa:
Pr[err(h, k) = 0]Sphere = Vol(Tubeγ)
Vol(Sa)
=
4 3 πR3a − 4 3 (Ra − da) 3
4 3 πR3a
= 1 − t3k R3a ,
(57)
where tk keeps consistent with Eq. (40). With the initial sampling from the tube structure of class A, the subsequent acquisitions of AL would be updated from the tube structure of class B. If the initial sampling comes from the tube structure of B, the next acquisition must be updated from the tube structure of A. With the updated acquisitions spread over the tube structures of both classes, h is easy to achieve a nearly zero error. Then Theorem 3 is as stated.

heading: D.5 PROOF OF THEOREM 4
text: Proof. Following the proof technique of Theorem 3, volume of the tube is redefined as Vol(Tubeγ) = 4 3 πRa1Ra2Ra3 . Then, we know
Pr[err(h, k) = 0]Ellipsoid = Vol(Tubeγ)
Vol(Ea)
=
4 3 πRa1Ra2Ra3 − 4 3 (Ra1 − da)(Ra2 − da)(Ra3 − da) 4 3 πRa1Ra2Ra3
= 1 − λk1λk2λk3 Ra1Ra2Ra3 ,
(58)
where λki = R2ai 3 + 3
√
− σki 2π +
√ σ2 ki
4π2 − π3R3ai 27π3 + 3
√
− σki 2π −
√ σ2 ki
4π2 − π3R3ai 27π3 , and σki = ( 2k−4 3k −
πRai 2ϕ )πRa1Ra2Ra3 − 4πRb1Rb2Rb3 3k , i = 1,2,3.
Theorem 4 then is as stated.

heading: D.6 PROOF OF PROPOSITION 1
text: Proof. Let Cubea tightly covers Sa with a side length of 2Ra, and Cube ′ a tightly covers the cut C, following theorem 1, we know
err(h, k) > Vol(A) −Vol(C) Vol(A) > Cubea −Cube
′ a
Cubea . (59)
Then, we know
err(h, k) > πR3a − πR 2 ada
πR3a
= 1 − da Ra .
(60)
Meanwhile, let Cubee tightly covers Ea with a side length of 2Ra1 , Cubee ′ tightly covers C, following theorem 1, we know
err(h, k) > Vol(A) −Vol(C) Vol(A) > Cubee −Cube
′ e
Cubee . (61)
Then, we know
err(h, k) > πRa1Ra2Ra3 − πdaRa2Ra3
πRa1Ra2Ra3
= 1 − da Ra1 .
(62)
Since Ra1 < Ra, we know 1− da Ra > 1− da Ra1 . It is thus the lower bound of AL with ellipsoid is tighter than AL with sphere. Then, Proposition 1 holds.

heading: D.7 PROOF OF PROPOSITION 2
text: Proof. Following the proofs of Theorem 3:
Pr[err(h, k) = 0]Sphere = 1 − t3k R3a
= 1 − (Ra − da)
3
R3a
= 1 − ⎛
⎝ 1 − da Ra ⎞ ⎠
3
.
(63)
Following the proofs Theorem 4:
Pr[err(h, k) = 0]Ellipsoid = 1 − λk1λk2λk3
R3a1
= 1 − (Ra1 − da)(Ra2 − da)(Ra3 − da)
R3a1
> 1 − ⎛
⎝ 1 − da Ra1 ⎞ ⎠
3
.
(64)
Based on Proposition 1, 1 − da Ra > 1 − da Ra1 , therefore Pr[err(h, k) = 0]Sphere < Pr[err(h, k) = 0]Ellipsoid. Then, Proposition 2 is as stated.
D.8 LOWER DIMENSIONAL GENERALIZATION OF THE d-DIMENSIONAL GEOMETRY
With the above theoretical results, we next present a connection between 3-D geometry and ddimensional geometry. The major technique is to prove that the volume of the 3-D geometry is a lower dimensional generalization of the d-dimensional geometry. It then can make all proof process from Theorems 1 to 5 hold in d-dimensional geometry.
Theorem 6. Let Vold be the volume of a d-dimensional geometry, Vol3(Sa) is a low-dimensional generalization of Vold(Sa).
Proof. Given Sa over class A is defined with x21 + x 2 2 + x 2 3 = R 2 a. Let x 2 1 + x 2 2 = r 2 a be its 2-D generalization of Sa, assume that x2 be a variable parameter in this 2-D generalization formula, the “volume” (2-D volume is the area of the geometry object) of it can be expressed as
Vol2(Sa) = ∫ ra −ra 2 √ r2a − x 2 2dx2. (65)
Let ϑ be an angle variable that satisfies x2 = rasin(ϑ), we know dx2 = racos(ϑ)dϑ. Then, Eq. (65) is rewritten as
Vol2(Sa) = ∫ π/2
−π/2 2r2acos 2 (ϑ)dϑ
= ∫
π/2
0 4r2acos 2 (ϑ)dϑ.
(66)
For a 3-D geometry, for the variable x3, it is over a cross-section which is a 2-dimensional ball (circle), where the radius of the ball can be expressed as racos(ϑ), s.t. ϑ ∈ [0, π]. Particularly, let Vol3(Sa) be the volume of Sa with 3 dimensions, the volume of this 3-dimensional sphere then can be written as
Vol3(Sa) = ∫ π/2
0 2Vol2(racos(ϑ))ra(cos(ϑ))dϑ. (67)
With Eq. (67), volume of a d-dimensional geometry can be expressed as the integral over the (d-1)-dimensional cross-section of Sa
Volm(Sa) = ∫ π/2
0 2Volm-1(racos(ϑ))ra(cos(ϑ))dϑ, (68)
where Volm-1 denotes the volume of (m-1)-dimensional generalization geometry of Sa.
Based on Eq. (68), we know Vol3 can be written as
Vol3(Sa) = ∫ π/2
0 2Vol2(Racos(ϑ))ra(cos(ϑ
′ ))dϑ (69)
Introducing Eq. (66) into Eq. (69), we have
Vol3(Sa) = ∫ π/2
0 2Vol2(Racos(ϑ
′ ))ra(cos(ϑ ′ ))dϑ′
= ∫
π/2
0 ∫
π/2
0 8(racos(ϑ
′ ) 2cos2(ϑ′)ra(cos(ϑ))dϑ ′dϑ
= 4
3 πR2a s.t.Ra = ra.
(70)
Therefore, the generalization analysis results of the 3-D geometry still can hold in the high dimensional geometry. Then,
Theorem 7. Let Vold be the volume of a d-dimensional geometry, Vol3(Ea) is a low-dimensional generalization of Vold(Ea).
Proof. The integral of Eq. (67) also can be adopted into the volume of Vol3(Ea) by transforming the area i.e. Vol2(Sa) into Vol2(Ea). Then, Eq. (68) follows this transform.

Review summaries:
This paper is basically unreadable. The sentence structure / grammar is strange, and if that was the only issue it could be overlooked. The paper also does not describe or explain the motivation and interpretation of anything, but instead just lists equations. For example, eta is the parameter that projects a spherical geodesic onto an the ellipsoid one, and an ellipsoid geodesic prevents updates of the core-set towards the boundary regions where the characteristics of the distribution cannot be captured. However, what are these characteristics, and how can they motivate how to choose eta?