Enhancing Semi-Supervised Learning via Representative and Diverse Sample Selection
Authors: Qian Shao
Jiangrui Kang
Qiyuan Chen
Zepeng Li
Hongxia Xu
Yiwen Cao
JIAJUAN LIANG
Jian Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Semi-supervised learning
Sample selection
Low-budget learning
Primary area: other
TL;DR: Proposed a representative and diversified sample selection method to select data for annotation from the unlabeled data to improve the performance of semi-supervised learning approaches.

Abstract: Semi-Supervised Learning (SSL) has become a preferred paradigm in many deep learning tasks, which reduces the need for human labor. Previous studies primarily focus on effectively utilising the labelled and unlabeled data to improve performance. However, we observe that how to select samples for labelling also significantly impacts performance, particularly under extremely low-budget settings. The sample selection task in SSL has been under-explored for a long time. To fill in this gap, we propose a Representative and Diverse Sample Selection approach (RDSS). By adopting a modified Frank-Wolfe algorithm to minimise a novel criterion $\alpha$-Maximum Mean Discrepancy ($\alpha$-MMD), RDSS samples a representative and diverse subset for annotation from the unlabeled data. We demonstrate that minimizing $\alpha$-MMD enhances the generalization ability of low-budget learning. Experimental results show that RDSS consistently improves the performance of several popular SSL frameworks and outperforms the state-of-the-art sample selection approaches used in Active Learning (AL) and Semi-Supervised Active Learning (SSAL), even with constrained annotation budgets. Our code is available at [RDSS](https://github.com/YanhuiAILab/RDSS).

Enhancing Semi-Supervised Learning via Representative and Diverse Sample Selection
Qian Shao 1,3-
L3> Jiangrui Kang"", Qiyuan Chen Zepeng Lit, Hongxia Xu! Yiwen Cao², Jiajuan Liang"t and Jian Wulf
Coollege of Computer Science & Technology and Liangzhu Laboratory, Zhejiang University BNU-HKBU United International College "WeDoctor Cloud
*The State Key Laboratory of Blockchain and Data Security, Zhejiang University {qianshao, qiyuanchen, lizepeng, einstein, wujian2000) @zju. edu. cn (kangjiangrui, yiwencao, jiajuanliang/Ouic edu. cn
Abstract
Semi-Supervised Learning (SSL) has become preferred paradigm in many deep learning tasks, which reduces the need for human labor. Previous studies pri- marily focus on effectively utilising the labelled and unlabeled data to improve performance. However, observe that how to select samples for labelling also sig- nificantly impacts performance, particularly under extremely low-budget settings. The sample selection task in SSL has been under-explored for long time. To fill in this gap, we propose a Representative and Diverse Sample Selection approach (RDSS). By adopting modified Frole-Wolfe algorithm to minimise novel crite- rion a--aaximum Mean Discrepancy (a-MMD), RDSS samples a representative and diverse subset for annotation from the unlabeled data. We demonstrate that minimizing a-MMD enhances the generalization ability of low-budget learning. Experimental results show that RDSS consistently improves the performance of several popular SSL frameworks and outperforms the state-of-the- sample se- lection approaches used in Active Learning (AL) and Semi- cumi-Supervised Active Learning (SSAL), even with constrained annotation budgets. Our code is available at RDDS
Introduction
Semi-Supervised Learning (SSL) is a popular paradigm which reduces reliance large amounts of labeled data many deep learning tasks [40 [59.. Previous SSL research mainly focuses on effectively utilising labelled and unlabeled data. Specifically, labelled data directly supervise model learning, while unlabeled data help learn desirable model that makes consistent and unambiguous predictions (53). Besides, also find that how select samples for annotation will greatly affect model performance, particularly under extremely low-budget settings (see Section 7.2).
The prevailing sample selection methods in SSL have many shortcomings. For example, random sampling may introduce imbalanced class distributions and inadequate coverage of the overall data distribution, resulting in poor performance. Stratified sampling randomly selects samples within each class, which impractical in real-world scenarios where the label for each sample is unknown. Existing researchers also employ representativeness. and diversity strategies select appropriate samples for annotation. Representativeness with the entire dataset, and diversity (54] is designed to select informative samples by pushing away
[3] ensures that the selected subset distributes similarly
"These authors contributed equally to this work. CCoresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

a) Representativeness only
b) Diversity only
c) a-MMD (ours)
Figure I: Visualization of selected samples from a dog dataset. The red and grey circles respectively symbolize the selected and unselected samples. a) The selected samples often contain an excessive number of highly similar instances, leading to redundancy; b) The selected samples contain too many edge points, unable to cover the entire dataset; e) The selected samples represent the entire dataset comprehensively and accurately.
them in feature space. And focusing on only one aspect presents significant limitations (Figure T and b). To address these issues, Xie et al. [57] and Wang al. (50) employ combination of the two strategies for sample selection. These methods set a fixed ratio for representativeness and diversity, restricting the ultimate performance through our empirical evidence (see Section 7.4). Fundamentally,
they lack theoretical basis to substantiate their effectiveness.
We observe that Active Learning (AL) primarily focuses selecting the right samples for annotation, and numerous studies transfer the sample selection methods of AL into SSL, giving rise to Semi- Supervised Active Learning (SSAL) [51]. However, most of these approaches exhibit several limitations: (1) They require randomly selected samples to begin with, which expends a portion the labelling budget, making it difficult to work effectively with very limited budget (e.g., 1%
lower) [6); (2) They involve human annotators in iterative cycles of labelling and training, leading substantial labelling overhead [57] (3) They are coupled with the model training so that samples for annotation need to be re-selected every time a model is trained [50]. In summary, selecting the appropriate samples for annotation is challenging in SSL.
To address these challenges, we propose a Representative and Diverse Sample Selection approach (RDSS) that requests annotations only once and operates independently of the downstream tasks. Specifically, inspired by the concept of Maximum Mean Discrepancy (MMD) 14, we design a novel criterion named a-MMD. It aims strike balance between representativeness and diversity via trade-off parameter a (Figure Tb), for which we find an optimal interval adapt to different budgets. By using modified Frank- Wolfe algorithm called Generalized Kernel Herding without Replacement (GKHR), we can get an efficient approximate solution to this minimization problem.
We prove that under certain Reproducing Kernll Hilbert Space (RKHS) assumptions, a-MMD effectively bounds the difference between training with a constrained versus an unlimited labelling budget. This implies that our proposed method could significantly enhance the generalization ability of learning with limited labels. We also give theoretical assessment GKHR with some supplementary numerical experiments, showing that GKHR performs well in learning with limited labels.
Furthermore, we evaluate our proposed RDSS across several popular SSL frameworks the datasets CIFAR-10/100 [1), SVHN (30), STL-10 ( and ImageNet [IO]. Extensive experiments show that RDSS outperforms other sample selection methods widely used in SSL, AL or SSAL, especially with constrained annotation budget. Besides, ablation experimental results demonstrate that RDSS outperforms methods using fixed ratio.
The main contributions of this article are as follows:
We propose RDSS, which selects representative and diverse samples for annotation to enhance SSL by minimizing a novel criterion a-MMD. Under low-budget settings, we develop fast and efficient algorithm, GKHR, for optimization.

---

We prove that our method benefits the generalizability of the trained model under certain assumptions and rigorously establish an optimal interval for the trade-off parameter a adapt to the different budgets.
We compare RDSS with sample selection strategies widely used in SSL, AL or SSAL, the results of which demonstrate superior sample efficiency compared to these strategies. In addition, we conduct ablation experiments to verify our method's s superiority over the fixed-ratio approach.
2 Related Work
Semi-Supervised Learning Semi-Supervised Learning (SSL)) effectively utilizes sparse labeled data and abundant unlabeled data for model training. Consistency Regularization [34] 20 45), Pseudo- Labeling [21 [56] and their hybrid strategies [40] 63 35 are commonly used in SSL. Consistency
Regularization ensures the model's output stays stable even when there's noise or small changes in the input, usually from the data augmentation [55]. Pseudo- integrates high-confie high-confidence data pseudo-labels directly into training, adhering to entropy minimization [23]. Moreover, an integrative approach that combines the aforementioned strategies can also achieve substantial results [53] [59]. Even though these approaches have been proven effective, they usually assume that labelled samples are randomly selected from each class (i.e., stratified sampling), which is not practical in real-world scenarios where the label for each sample is unknown.
Active Learning Active learning (AL) aims to optimize the learning process by selecting the appropriate samples for labelling, reducing reliance large labelled datasets. There two different criteria for sample selection: uncertainty and representativeness. Uncertainty sampling selects samples about which the current model is most uncertain. Earlier studies utilized posterior probability [22 49), entropy [8, (26). and classification margin [47] to estimate uncertainty. Recent research regards uncertainty training loss 17 60), influence on model performance 1 24
or the prediction discrepancies between multiple classifiers []. However, uncertainty sampling methods may exhibit performance disparities across different models. leading researchers to focus on representativeness sampling, which aims to align the distribution of selected subset with that of the entire dataset [36]] 39 27). Most AL approaches are difficult to perform well under extremely low-label settings. This may be because they usually require randomly selected samples to begin with and involve human annotators in iterative cycles of labelling and training, leading to substantial labelling overhead.
Model-Free Subsampling Subsampling is statistical approach which selects subset with size m as a surrogate for the full dataset with size n >> m. While model-based subsampling methods depend heavily the model assumptions [1] improper choice of the model could lead bad performance of estimation and prediction. In that case, model-free subsampling is preferred in data-driven modelling tasks, as it does not depend on the model assumptions. There are mainly two kinds of popular model-free subsampling methods. The one is induced by minimizing statistical discrepancies, which forces the distribution of subset to be similar that of full data, in other words, selects representative subsamples, such as Wasserstein distance 13] energy distance [28), uniform design (65), maximum mean discrepancy 7 and generalized empirical F-discrepancy (66). The other tends to select a diverse subset containing as many informative samples as possible [54]. The above- mentineet methodologies either exclusively focus on representativeness diversity, which are difficult to effectively apply to SSL.
3 Problem Setup
Let X' be the unlabeled data space, y be the label space, X, = (x:]ie(n) C X' be the full unlabeled dataset containing pairwise different data, and Imm = (i 12, ... (m) C [n] (m < n) be an index set contained in (n]]. our goal is to find index set I {17 "2. . C [n] < n)) such that the selected set of samples X = {xiç. X:j N,;, } is the most informative. After that, we can get access to the true labels of selected samples and use the set of labelled data {(x,, bezz and the rest of the unlabeled data to train a deep learning model.
3

---

Following the methodology of previous works, we use representativennss and diversity as criteria for evaluating the informativeness of selected samples. Representativeness ensures the selected samples distribute similarly to the full unlabeled dataset. Diversity is proposed to prevent an excessive concentration of selected samples in high-density areas of the full unlabeled dataset. Furthermore, the cluster assumption in SSL suggests that the data tend to form discrete clusters, in which boundary points are likely to be located in the low-density area. Therefore, under this assumption, selected samples with diversity contain more boundary points than the non-diversified ones, which is desired in training classifiers.
As result, our goal can be formulated by solving the following problem:
max Rep(XIm.. X,)) + (.., Im C(n)
where Rep(Xz, X and Div quantify the representativeness and diversity of selected samples respectively and À is a hyperparameter to balance the trade-off representativeness and diversity.
Besides, we propose another two fundamental settings which are beneficial to the implementation of the framework: (1) Low-budget learning. The budget for many of the real-world tasks which require sample selection procedures is relatively low compared to the size of unlabeled data. Therefore, set m/n 0.2 in default in the following context, including the analysis of the sampling algorithm and the experiments; (2) Sampling without Replacement. Compared with the setting of sampling with replacement, sampling without replacement offers several benefits which better match our tasks, including bias and variance reduction, precision increase and representativeness enhancement 25 46)
4 Representative and Diversity Sample Selection
The Representative and Diverse Sample Selection (RDSS) framework consists of two steps: (1) Quan- rification. We quantify the representativeness and diversity of selected samples by novel concept called a-MMD (6). where À is replaced by a as the trade-off hyperparameter; (2) Optimization. We optimize M-MMD by GKHR algorithm to obtain the optimally selected samples XT:
4.1 Quantification of Diversity and Representativeness
In classical statistics and machine learning problems, the inner product of data points x, E X, defined by (x, y), is employed to as a similarity measure between y. However, the application of linear functions can be very restrictive in real-world problems. In contrast, kernel methods use kernel functions 6(x. y). including Gaussian kernels (RBF), Laplacian kernels and polynomial kernels, as non-linear similarity measures between x, y. which are actually inner products of the projections of k(x, y) in some nigh-dimensional feature space (29].
Let k(:-) be kernel function on X' X, and we employ k(-,-) to measure the similarity between any two points and the average similarity, denoted by
S& X
Σ
Σ
k (x;,
m
VEI
JEIm
to measure the similarity between the selected samples. Obviously, S(XIm.. can evaluate the diversity of Xz.,. since larger similarity implies smaller diversity.
As statistical discrepancy which measures the distance between distributions, the maximum mean discrepancy (MMD) is introduced here to quantify the representativeness of X to X,,- Proposed by Gretton et al. [4], MMD is formally defined below:
Definition 4.1 (Maximum Mean Discrepancy). Let P.Q be two Borel probability measures on X.
Suppose f is sampled from the unit ball in a reproducing kernel Hilbert space (RKHS) H associated with its reproducing kernel k(, -), i.e., ||f 1| < 1, then the MMD between P and Q is defined by
( [dP | sao) = Ek + (X,Y" (((XY)), (3)
MMD (P,Q) ;= sup 11
where X' ~ P and Y, Y Q are independent copics.

---

We can next derive the empirical version for MMD that is able to measure the representativeness of XT. hem relative to X,, {x by replacing P. Q with the empirical distribution
constructed by XI.. X, in
3): x))+
MMD x
R a
+
Σ
Σ JETm
(x)
2 mn
1s x,).
n2
m
iE
JEZ
Optimization objective. Set - - -) and Div(.) = -Sp()) in where & is proper kernel function, our optimization objective becomes
min MMD (XT,, T.,. Xn) + XS I.n [(a]
Set x
1-a since am
1= ブド= (x,, x,) is a constant, the objective function in 55) can be rewritten
by
a(ax - 1) n (x,, Xy)
a MMD (X x,)
a Sk (XIm.)
m
n²
1=1 j=1
20
(x,, xy) +
k (x),
k Xy)
n2
m
(6)
VE Im jEIm
1=1 JEZ
2
Σ [(x)) - (xx)
sup gI
VEIm
which defines a new concept called a-MMD, denoted by MMD : This new concept distinguishes our method from those existing methods, which is essential for developing the sampling algorithms and theoretical analysis. Note that a-MMD degenerates to classical MMD when = and degenerates to average similarity when a = 0. As a decreases, À increases, thereby encouraging the diversity for sample selection.
Remark 1. In the following context, all the kernels are assumed to be characteristic and positive definite if not specified. The following illustrates the advantages of the two properties.
Characteristics kernels. The MMD generally a pseudo-metre on the space of Borel probability distributions, implying that the MMD between two different distributions can be zero. Nevertheless, MMD becomes proper metric when & is characteristic kernel, i.e., P + Jx lt(,x)dd for any Borel probability distribution P on X (29]. Therefore, MMD induced by characteristic kernels can be more appropriate for measuring representativeness.
Positive definite kernels. Aronszajn 2 showed that for every positive definite kernel Be(-..). i.e., its Gram matrix is always positive definite and symmetric, uniquely determines an RKHS and vice versa. This property is not only important for evaluating the property of MMD 43 but also required in optimizing MMD [32 by Frank- Wolfe algorithm.
4.2 Sampling Algorithm
In the previous research (36 27 50 38 58), sample selection is usually modelled by a non- convex combinatorial optimization problem. In contrast, following the idea of 4. we regard X..)
convex optimization problem by exploiting the convexity of a-MMD, and then solve it by a fast iterative minimization procedure derived from Frank-Wolfy algorithm (see Appendix A for derivation details):
minl,,,[e) MMD
E arg min fzz, (x;), T + I 1i =0
(7)
(E(x]
where (x:) l
(x,,,x)) op Ei= -=1 A(x,, x)). As extension of kernel herding 7 its
corresponding algorithm (see Algorithm is called Generalized Kernel Herding (GKH). Note that
fz, (x,) is iteratively updated in Algorithm which can save a lot of rumning time. However, GKH can select repeated samples that contradict the setting of sampling without replacement. To address this issue, we propose modified iterating formula based on
X5 E arg min JTş (x:), Ix I5+1 + IP [E[n](Z;
1i 0,
(8)
5

---

Algorithm Generalized Kernel Herding without Replacement
Require: Data set X,, (x1.-.. .x, C X; the number of selected samples m < n; positive definite, characteristic and radial kernel :);;)) -) on N' X; trade-off parameter a S 1.
Ensure: Selected samples XI= (xx;, "x. Xxz
1: For each E Xn calculate (xx;) := 1ز= k(x,, xi)/n.
2: Set 81 1, Sn I = 0.
] 3: for {1, ,1,...,, do
4: ip E arrarin ge/l/// Sp-1(x;) - o))((x,)
5: For all i E [n]] update Sp(x)) = (1 - ppp) (x:) + 3x,( xi)
6:
T + Ip U (pp. ptpppaa set Bp = 1/p.
7:
end for
which admits no repetitiveness in the selected samples. Its corresponding algorithm (see Algorithm D is thereby named as Generalized Kernel Herding without Replacement (GKHR), employed as the sampling algorithm for RDSS.
Computational complexity. Despite the time cost for calculating kernel functions, the computational complexity of GKHR is ((m)), since in each iteration, the steps in lines 4 and 5 of Algorithm 2 respectively require O(n) computations. Note that GKH has the same order of computational complexity as GKHR.
5
Theoretical Analysis
5.1 Generalization Bounds
Recall the core-set approach in 36 Le., for any h H.
R(h) < (h) + RRh) (h)) + [Rr((h) (h),,,,
where T is the full labeled dataset and S C T is the core set, R(h) is the expected risk of h, (h), (h) are empirical risk of h T.S. S. The first term R5(h) is unknown before we label the selected samples, and the second term (R(h) (r)h can be upper bounded by the so-called generalization bounds 3 64 which do not depend on the choice of core set. Therefore, to control the
upper bound of R(h), only need to analyse the upper bound of the third term (h) Rs(h) called core-set loss, which requires several mild assumptions. Shalit, et al. (37 derived a MMD- type upper bound for (h) Rs)h) to estimate individual treatment effect, while our bound is generalized to a wider range of tasks.
Let 741 = (h h: X - 3/ be hypothesis set in which we are going to select predictor and suppose that the labelled data T = {x;; y1)) 12=1 are i.i.d. sampled from random vector (X, Y) defined
X' x V. We firstly assume that Hi is an RKHS, which is mild in machine learning theory [3 [].
Assumption 5.1. H, is RKHS associated with bounded positive definite kernel ką where the norm of any h E H, is bounded by Kn.
We further make RKHS assumptions on the functional space of E (X) and Var(Y]X) that fundamental the field of conditional distribution embedding [1 43
Assumption 5.2. There is RKHS H2 associated with bounded positive definite kernel lo such that EEY X) E H2 and the norm of any E(Y[X) is bounded by K..
Assumption 5.3. There is RKHS H. associated with bounded positive definite kernel ka such that Var(Y|X) E H3 and the norm of any Var(Y (X) is bounded by K
We next give a-MMD-type upper bound for the core-set loss by the following theorem: Theorem 5.4. Take = ke + k2 + kis, then under assumptions 1-3, for any selected samples S C T. there exists a positive constant K, such that the following inequality holds:
(h) - (h)l S (MMMD Xx, + (1-10) (1-))
where 0 S a maxxex k(x, x) K and Xs projections of S, T on X.

---

Therefore, minimizing a-MMD can optimize the generalization bound for R(h) and benefit the generalizability of the trained model (predictor).
5.2 Finite-Sample-Error-BBooo for GKHR
The concept of convergence does not apply to analyzing GKHR. With n fixed, GKHR iterates for at most times and then returns Xz: Xn. Consequently, we analyze the performance of GKHR by its iiite-sample-ere bound. Previous to that, we make an assumption on the mean of fr; over the full unlabeled dataset.
Assumption 5.5. For any I returned by GKHR, 1 S S m 1, there exists p + 1 elements (x) [Kirt=1
(p+1 X, such that
2i=1 JIg (x.)
fzz (xji S ... fzz (ximt))
When m is not relatively small, this assumption is rather unrealistic. Nevertheless, under our low- budget setting, especially when m < n, the assumption becomes an extension of the principle that "the minimum is never larger than the mean", which still probably makes sense. We can then show that the decaying rate for optimization error of GKHR can be upper bounded by Olog m/m):
Theorem 5.6. Let XI; be the samples selected by GKHR, under assumption 4, it holds that
logm
MMD k.a (Xr. X,) S Ca + B +
where 2K, 0 maxxex k(x,x) K, C² = (1 R where K is defined in Lemma B.6
6 Choice of Kernel and Hyperparameter Tuning
In this section, we make suggestions for choosing the kernel and tuning the hyperparameter
Choice kernel. Recall Remark in Section 4.1 we only consider characteristic and positive definite kernels in RDSS. Since the Gaussian kernels are the most commonly used kernels in the field machine learning and statistics 15),, we introduce Gaussian kernel as our choice, which is defined by k(xx y) cxp(-lIx ||x y The bandwidth parameter is set to be the median distance between samples in the aggregate dataset [15), i.e., o = Median (f (f]]x y x, E X,,),
since the median is robust and also compromises between extreme cases.
Tuning trade-off hyperparameter a. According to Theorem an6 Lemma B33 by straightforward deduction we have
MMD (X2,,,,,, S C. +0 (v log m
+ (1 (1-a)VK
to upper bound the MMD between the selected samples and the full dataset under a low-budget setting, We can just set E [L 1) so that the upper bound of the MMD would not be larger than the one of a-MMD in the perspective of the order of magnitude.
7 Experiments
In this section, we first explain the implementation details of our method RDSS in Section we compare RDSS with other sampling methods by integrating them into two state-of- of-te-of-thh-art (SOTA) SSL approaches (FlexMatch [63] and Freematch [53] on five datasets (CIFAR-10// 10/100,00 SVHN,
7.1 Next,
STL-10 and ImageNet- Ik) in Section 7.2 The details of the datasets, the visualization results and the
computational complexity of different sampling methods are shown in Appendix D.2 D.3 and D.4
respectively. We also compare against various AL/SSAL approaches Section 7.3 Lastly. y, we make
quantitative analyses of the trade-off parameter in Section 7.4

---

7.1 Implementation Details of Our Method
First, we leverage the pre-trained image feature extraction capabilities of CLIP 33 a vision trans- former architecture, to extract features. Subsequently, the [CLS] token features produced by the model's final output are employed for sample selection. During the sample selection phase, the Gaussian kernel function is chosen as the kernel method to compute the similarity of samples in an infiniee-dimensione feature space. The value of a for the Gaussian kernel function is set as explained in Section 6 To ensure diversity in the sampled data, we introduce a penalty factor given by a = Vm where m denotes the number of selected samples. Concretely, we set
{250, 1000} for SVHN, m = {40, 250} for STL-10 and m = {100000) for ImageNet. Next, the selected samples used for two SSL approaches, which are trained and evaluated the datasets using the codebase Unified SSL Benchmark (USB) [52]. The optimizer for all experiments is standard stochastic gradient descent (SGD) with momentum of 0.9 44). The initial learning rate is 0.03 with learning rate decay of 0.0005. We use ResNet-50 [6] for the ImageNet experiment and Wide ResNet-28-2 [62] for other datasets. Finally, we evaluate the performance with the Top-1 classification accuracy metric on the test set. Experiments are run on N*NVIDAA Tesla A 100 (40 GB) and 2 Intel 6248R 24-Core Processor. We average our results over five independent runs.
m {40, 250, 4000} for CIFAR-10, m {400, 2500, 10000} for CIFAR-100 100,
7.2 Comparison with Other Sampling Methods
Main results We apply RDSS on Flexmatch and Freematch to compare with the following three baselines and two SOTA methods in SSL. under different annotation budget settings. The baselines conclude Stratified, Random and k-Means, while the two SOTA methods are USL (50) and ActiveFT [57]. The results are shown on Table T from which we have several observations: (1) Our proposed RDSS achieves the highest accuracy, outperforming other sampling methods, which underscores the effectiveness of our approach; (2) USL attains suboptimal results under most budget settings yet exhibits significant gap compared to RDSS, particularly under severely constrained ones. For instance, FreeMatch achieves a 4.95% rise on the STL-10 with a budget of 40; (3) In most experiments, RDSS either approaches or surpasses the performance of stratified sampling, especially on SVHN and STL-10. However, the stratified sampling method is practically infeasible given that the category labels of the data are not known priori.
Results on ImageNet We also compare the second-best method USL with RDSS on ImageNet. Following the settings of FreeMatch (53), select 100k samples for annotation. FreeMatch, using RDSS and USL. as sampling methods, achieves 58.2 24% and 56.86% accuracy. respectively, demonstrating substantial enhancement in the performance of our method over the USL approach.
Table 1: Comparison with other sampling methods. Due to stratified sampling limitations, the results marked in grey. Top and second-best performances are bolded and underlined, respectively, excluding stratified sampling. Metrics represent mean accuracy and standard deviation over five independent runs
Dosaset
CIFAR-IA 10
CIFAR 100
SVHN
STL 10
40 Applicd Plaxotacc
Budget
250
2000
400
2500
100RU
250
1000
40
250
[3]
Statilee
91.45=3.41
10:00:0::
05.6300.24
50.350441
67,35-0.45
50
95.66-00.49
75.33433344
02.2040..4
Random
$7.30
01
0.500
45.58.0..77
66.48-00.8
$7.67
90.20.10.79
$1,23-18.1
51
05.09:0.65
1.691112
65.99-0.57
53::0:4433
933331
$5.4310.30
9.664:1.05
USL
13
15.43.0.15
363910046
72.53:10.22
03.10.10.78
15.6510.00
90.7700366
AstiveFT
70.87=411
93.5511.3
05.31=0.75
25,0940.64
57.19-2.06
70-06-00775
80.92-1 87
02.53+0443
55.57+1422
87.28-1.19
(Ours)
94.09-0.22
05.21-0.47
05.71-0.10
48.12-0.36
67.27-0.55
70.21+0.29
91.70-0.39
05.70-0.35
77.96+0552
93.16-0.41
Apaliod in Moveearth (3]
Striifted
55 55.05520111 15
05:00123
00
$1.911055
61.09
73.0010.33
99.56 05
04.2310.5
91.3610.15
Random
93.412:.24
91981091
95 95.5620.17
47.00:1.25
72.00 72.0910.999 00.09:1008
91622 3M
94.402:125
76.0642.43
9.772-0377
& Means
$8.05:15.07
4130100.5
95.51100377
66.09_0.39
71 11.6910072
93.5011.00 06
91.6910.72
63 03.1214.92
39599087
USL 50
23.1-00.2
95. 19-00 18
05. 76.00.222
47.07+1.75
66.92-0.33
72 72.59:+0.15 36
93. 03.36-0.5
04
04:44:..44
76055-086
-1.5--0.58
AutivePT 5xx
78.13:2.87
94341031
05.3310.33
26.67.0..6
36.23.085
712611068
00601051
93.51
63.3112.9
86 0.360..330
RDSS (Ours)
95.05_.0.13
95.3010..39
95.96_00.8
48.1
67.40__0.23
73.1310.19
94.5410.46
95.83.00.37
81.90.1.772
02.22.00.00
7.3 Comparison with AL/SSAL Approaches
First, we compare RDSS against various traditional AI. approaches on CIFAR-10/100. AL. appraachs
conclude CoreSet (36). VAAL (39, LearnLoss [60 and MCDAL (8) For a fair comparison,
8

---

exclusively use samples selected by RDSS for supervised learning compared to other AL approaches, considering that AL relies solely on labelled samples for supervised learning. The implementation details are shown in Appendix D.5 The experimental results are presented in Table from which we observe that RDSS achieves the highest accuracy under almost all budget settings when relying solely on labelled data for supervised learning, with notable improvements on CIFAR-100.
Second, we compare RDSS with sampling methods used in SSAL when applied the same SSL framework (i.e., Flexhatch or FreeMatch) on CIFAR-10. The sampling methods conclude Core-
SetSSL [6) MMA 42). CBSSAL [2], and TOD-Semi [T7]. In detail, we tune recent SSAL approaches with their public implementations and run experiments under an extremely low-budger setting, Le., 40 samples in a 20-random-and- -nd-----ee--eeeeddd setting. Table Jillstsjil that the perfor- mance of most SSAL approaches falls below that of random sampling methods under extremely low-hudget setrings. This inefficiency stems from the dependency of sample selection on model performance within the SSAL framework, which struggles when the model is weak. Our model-free method, in contrast, selects samples before training, avoiding these pitfalls.
Table 2:
Comparison with AL approaches under Supervised Learning (SL) paradigm. The best per- formance is bold and the second best performance underlined.
Table 3: Comparison with SSAL approaches. The green (red) arrow represents the improve- ment (decrease) compared to the random sam- pling method.
Dataset
CIFAR-10
CIFAR-108 100
Method
FlexMatch
FreeMatch
Budget
7500
10000
7500
10000
Stratified
91.45
95.05
Random
87.30
93.41
CoreSet
85.46
87.56
47.17
53.06
VAAL
86.82
88.97
47.02
53.99
CoreSetSSI.
87.66 0.36
91.24 J. 2.17
LearnLoss
85.49
87.06
47.81
54.02
MMA
74.61 12.69
87.37
J. 6.04
MCDAL
87.24
89.40
49.34
54.14
CBSSAL
86.58 0.72
91.68
| 1.73
SL+RDSS (Ours)
87.18
89.77
50.13
56.04
TOD-Semi
86.21 1.09
90.77
$ 2.64
Whole Dataset
95.62
78.83
RDSS (Ours)
94.69 7.39
95.05
1.64
Third, directly compare RDSS with the above AL/SSAL approaches when applied to SSL, which may better reflect the paradigm differences. The experimental results and analysis are in the Appendix D.6
7.4 Trade-off Parameter
We analyze effect of different a with Freematch on CIFAR-10/100, The results are presented in Table from which we have several observations: (1) Our proposed RDSS achieves the highest accuracy under all budget conditions, surpassing those that employ a fixed value; (2) The a that achieve the best or the second best performance our theoretical derivation in Section 6 (3) The experimental outcomes exhibit varying degrees of reduction compared to approach when the representativeness or diversity term is removed.
within the interval we set, which is in line with
Table 4: Effect of different a. The grey results indicate that the is outside the interval set in Section 6 i.e., a < 1/ m/m while the black results indicate that the a is within the interval set, i.e., 1/ Vm < < 1. Among them, a 0 and indicate the removal of the representativeness and diversity terms, respectively. The best performance is bold, and the second- best performance underlined.
Dataset
CI
CIFAR- 100
Budget (m7)
40
250
4000
400
2500
10000
0
85.54.10.48
93.55.10.34
94.58.1..27
39.26:10.52
63.7740.26
71.9011.17
0.40
92.28-t0.24
93.68+t0133
94.95-t0.12
42.56++0.47
65.88+00.24
71.71+0.29
0.80
94.42.10.49
94.94.10.37
95.15.10.35
45.62-10.35
66.8740.20
72.45:10.23
0.90
94.33:1.228
95.03:10.21
95.20:10.42
48.12:t0.50
67.14:0.116
72.15+10.23
0.95
94.4410.64
95.0710.26
95.45:10.8
48.41100.59
67.1110.29
72.80:1..35
0.98
94.51+-0.39
95.02++0.15
95.31++0.44
48.33++0.54
67.40+10.23
72.68+0..2
94.53-10.42
95.0111.223
95.54110.25
48.18:10.36
67.20.10.29
13.05
///m (Ours)
95.05++0.13
95.50++..20
95.98+-0.28
48.41++0.59
67.40+H0.23
73.13++0119

---

8 Conclusion
In this work, we propose a model-free sampling method, RDSS, select subset from unlabeled data for annotation in SSL. The primary innovation of our approach lies in the introduction of a-MMD, designed to evaluate the representativeness and diversity of selected samples. Under a low-budget setting, we develop fast and efficient algorithm GKHR for this problem using the Frank- Wolfe algorithm. Both theoretical analyses and empirical experiments demonstrate the effectiveness of RDSS. In future research, we would like to apply our methodology to scenarios where labelling is cost-prohibitive, such as the medical domain.
Acknowledgements
This research was partially supported by National Natural Science Foundation of China under grant No. 82202984, Zhejiang Key R&D Program of China under grants No. 2023C03053 and No. 2024SSYS0026, and US National Science Foundation under grant No. 2316011. We thank Prof. Fred Hickernell and Mr. Yulong Wan for offering useful comments on this paper.
References
[1] M. Ai, J. Yu, Zhang, H. Wang. Optimal subsampling algorithms for big data regressions. Statistica Sinica, 31(2):749-77, 2021.
[2] N. Aronszajn. Theory reproducing kernels. Transactions of the American mathematical sociery, 68(3): 337 337-404, 1950.
[3] F. Bach. Learning theory from first principles. Draft of book, version of Sept, 6:2021, 2021.
[4] F. Bach, S. Lacoste-Julien, and G. Obozinski. On the equivalence between herding and conditional gradient algorithms. arXiv preprint /203.422235522 2012.
[5] A. Bictti and J. Mairal, Group invariance, stability to deformations, and complexity of deep convolutional representations. The Journal of Machine Learning Research, 20(1):876 924, 2019.
[6] Y.-C Chan,
and S. Oymak. On the marginal benefit of active learning: Does self-supervision eat its cake? In ICASSP 2021-2021 IEEE International Conference on Acoustics. Speech and Signal Processing (ICASSP), pages 3455-3458 IEEE, 2021.
[7] Y. Chen, M. Welling, and A. Smola. Super-samples from kernel herding, arXiv preprint arXiv:1203.33 1203.3472, 2012.
[8] W. Cho, D.-. Kim, Y. Jung, I. Kweon. Medal: Maximum classifier discrepancy for active learning. IEEE transactions on neural networks and learning systems, 2022.
[9] A. Coates, A. Ng. and H. Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 215 22-.223, JMLR Workshop and Conference Proceedings, 2011.
[10] J. Deng. W. Dong. Socher. L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee. 2009.
[11] A. Freytag, F.. Rodner, and J. Denzler. Selecting influential examples: Active learning with expected model output changes. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part IV 13, pages 562-577. Springer, 2014.
[12] Gao, Z. Zhang, G. Yu, S. Ô. Arik, L. S. Davis, and T. Pfister. Consisteney based semi- supervised active learning: Towards minimizing labeling cost. Computer Vision ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part X 16, pages 510-526. Springer, 2020.
[13] S. Graf and Luschgy. Foundations of quantization for probability distributions. Springer, 2007.
[14] A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola. A kemel method for the two-sample- problem. Advances neural information processing rystems, 19, 2006.
[15] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-775 2012.
10

---

[16] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and paltern recognition, pages 770-778, 2016.
[17] S. Huang, T. Wang, H. Xiong, Huan, and Dou. Semi-supervised active learning with temporal output discrepancy. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 3447-3456, 2021.
[18] A. J. Joshi, F. Porikli, and N. Papanikolopoulos. Multi-class active learning for image classification. In 2009 ieee conference computer vision ond pottern recognition, pages 2372-2379 IEEE, 2009.
[19] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[20] S. Laine and T. Aila. Temporal ensembling for semi-supervised learning. International Conference on Learning Representations, 2016.
[21] D.-H. Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896, Atlanta, 2013.
[22] D. D. Lewis Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pages 148-156. Elsevier, 1994.
[23] M. Li, R. Wu, H. Liu, J. Yu, X. Yang, B. Han, and T. Liu. Instant: Semi-supervised learning with instance-dependee thresholds. In seieth- Conference on Neural Information Processing Systems, 2023.
[24] Z. Liu, H. Ding, H. Zhong, W. Li, Dai, and C. He. Influence selection for active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9274-9283, 2021.
[25] S. L. Lohr. Sampling: design and analysis. Chapman and Hall/CRC, 2021.
[26] W. Luo, A. Schwing, and R. Urtasun. Latent structured active learning. Advances in Neural Information Processing Systems, 26, 2013.
[27] R. Mahmood, S. Fidler, and M. T. Law. Low budget active learning via wasserstein distance: An integer programming approach. arXiv preprint arXiv:2106.02968 2021.
[28] S. Mak and V. R. Joseph. Support points. The Annals of Statistics, 46(6A):2562-2553 2018.
[29] K. Muandet, K. Fukumizu, B. Sriperumbudur, B. Schölkopf, et al. Kernel mean embedding of distributions:
A review and beyond. Foundations and Trends@ in Machine Learning, (001-))111100 2017.
[30] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[31] V. I. Paulsen and M. Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge university press, 2016.
[32] L. Pronzato. Performance analysis of greedy algorithms for minimising a maximum mean discrepancy. arXiv preprint arXiv:2101.0753 075664 2021.
[33] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763, PMLR, 2021.
[34] M. Sajjadi, M. Javanmardi, and T. Tasdizen. Regularization with stochastic transformations and per- turbations for deep semi-supervised learning. Advances in neural information processing systems, 29, 2016.
[35] H. Schmutz, O. Humbert, and P.-A. Mattei. Don't fear the unlabelled: safe semi-supervised learning via debiasing. In The Eleventh International Conference on Learning Representations. 2022.
[36] O. Sener and Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
[37] U. Shalit, F. Johansson, and D. Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In International conference machine learning, pages 3076-3085. PMLR, 2017.

---

[38] Q. Shao, K. Zhang. B. Du. Z. Li. Y. Wu. Q. Chen, J. Wu, and J. Chen. Comprehensive subset selection for et volume compression improve pulmonary disease screening efficiency. In Artificial Intelligence and Data Science for Healthcare: Bridging Data-Centriae Al and People- Centric Healthcare, 2024.
[39] S. Sinha, S. Ebrahimi, and T. Darrell, Variational adversarial active learning. In Proceedings of the JEFF/CVF International Conference on Computer Vision, pages 5972-5981, 2019.
[40] K. Sohn, D. Berthelot, N. Carlini, Z. Zhang, H. Zhang. C. A. Raffel, E. D. Cubuk, A. Kurakin, and C.-L.
Li. Fixmatch: Simplifying semi supervised learning with consistency and confidence. Advances in neural information processing systems, 33:596 608, 2020.
[41] L. Song, J. Huang, A. Smola, and K. Fukumizu. Hilbert space embeddings of conditional distributions with applications dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 961-968, 2009.
[42] S. Song, D. Berthelot, and A. Rostamizadch. Combining mixmatch and active learning for better accuracy with fewer labels. arXiv preprint 192iv:/11..00594 2019.
[43] B. K. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schölkopf, and G. R. Lanckriet. On the empirical estimation of integral probability metrics. 2012.
[44] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In Internationna conference on machine learning, pages 1139-1147. PMLR, 2013.
[45] A. Tarvainen and H. Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi- supersuper deep learning results. Advances in neural information processing systems, 30, 2017.
[46] S. K. Thompson. Sampling, volume 755, John Wiley & Sons, 2012.
[47] S. Tong and Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 24N6v):45-66, 2001.
[48] M. J. Wainwright. Hiigh-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[49] K. Wang, D. Zhang, Y. Li, R. Zhang, and L. Lin. Cost-effective active learning for deep image classification. IEEE Transactions on Circuits and Systems for Video Technology, 27(12):591-2660 2016.
[50] X. Wang. L. Lian, and S. X. Yu. Unsupervised selective labeling for more effective semi- ceni-supervised learning. In European Conference on Computer Vision, pages 427-445. Springer. 2022.
[51] X. Wang, Z. Wu, L. Lian, and S. X. Yu. Debiased learning from naturally imbalanced pseudo-labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14647- 14657, 2022.
[52] Y. Wang, H. Chen, Y. Fan, W. Sun, R. Tao, W. Hou, R. Wang, L. Yang, Z. Zhou, L.-Z. Guo, et al. Usb: A unified supervisdd learning benchmark for classification. Advances in Neural Information Processing Systems, 35:3938 1188883961,228 2022.
[53] Y. Wang, H. Chen, Q. Heng, W. Hou, Y. Fan, Z. Wu, J. Wang, M. Savvides. T. Shinozaki, B. Raj, et al. Freematch: Self-adaptive thresholding for semi-supervised learning. arXiv preprint urXiv:2205.07246. 2022.
[54] X. Wu, Y. Huo, H. Ren, and 7ou. Optimal subsampling via predictive inference. Journal of the American Statistical A Association, (just-accepted))1-22 1-29, 2023.
[55] Q Xie, Z. Dai, E. Hovy, T. Luong, and Q. Le. Unsupervised data augmentation for consistency training. Advances in neural information processing systems, 33:6256 6268, 2020.
[56] Q. Xie, M.-T. Luong, E. Hovy, and Q. V. Le. Self-training with noisy student improves imagenet classification. In P Proceedings of the IEEE/CVF conference computer vision and pattern recognition. pages 10687-10698, 2020.
[57] Y. Xic, H. Lu, J. Yan, X. Yang, M. Tomizuka, and W. Zhan. Active finetuning: Exploiting annotation budget in the pretraining- mnerrainingffnctuuinng paradigm. In Proceedings of the IEFF/CVF Conference Computer Vision and Patiern Recognition, pages 23715-2372 2023.
[58] Y. Xu, D. Zhang, S. Zhang. S. Wu, Z. Feng, and G. Chen. Predictive and near-optimal sampling for view materialization in video databases. Proceedings of the ACM Management of Data, 2(1):122,, 2024.
12

---

[59] L. Yang. Z. Zhao, L. Qi. Y. Qiao. Y. Shi, and H. Zhao. Shrinking class space for enhanced certainty in semi-supervised learning. Proceedings the IEEE/CVF International Conference Computer Vision, pages 16187-16196, 2023.
[60] D. Yoo and L S. Kweon. Learning loss for active learning. In Proceedings the IEEE/CVF conference computer vision and pattern recognition, pages 93-102, 2019.
[61] J. Yu, H. Wang, M. Ai, and H. Zhang. Optimal distributed subsampling for maximum quasi-lieelihodd estimators with massive data. Journal of the American Statistical Association, 117(537):265 276, 2022.
[62] S. Zagoruyko and N. Komodakis. Wide residual networks. In Procedings of the British Machine Vision Conference 2016. British Machine Vision Association, 2016.
[63] B. Zhang, Y. Wang. W. Hou, H. Wu, J. Wang, M. Okumura, and T. Shinozaki. Flexmatch: Boosting sumi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 34:18408- 18419, 2021.
[64] Zhang and S. Chen, Concentration inequalities for statistical inference. Communications Mathematical Rexearch, 37(1):1-85, 2021.
[65] Zhang, Meng. Yu, Zhang, Zhong, and Ma. optimal transport approach for selecting representative subsample with application efficient kernel density estimation. Journal of Computational and Gruphicul Statistics, 32(1):329-333 2023.
[66] M. Zhang, Y. Zhou, Z. Zhou, and A. Zhang. Model-free subsampling method based on uniform designs. IEEE Transactions on Knowledge and Data Engineering, 2023.
13

---

A Algorithms
A.1 Derivation of Generalized Kernel Herding (GKH)
Proof. The proof technique is borrowed from [32]. Let us firstly define a weighted modification of
o-MMD. For any IR" such that w 1, the weighted o-MMDD is defined by
MMD M. X, (w)
Kw 2ow a²K,
where - [,,,,, x,) x,)]1 si.jssn K = 1 K1/n p = (e) K1/m ... e, K1/n), {e:).. is the set of standard basis of R. It obvious that for any Zp C [m].
MMD R, A.. (wp) MMD (XI, X,):
where (wp); = 1/p if i E Ip and (wp); = 0 if not. Therefore, weighted a-MMD is indeed a generalization of a-MMD. Let
= - 2ap1 + KKK
obtain the quadratic form expression of weighted a-MMD by MMD X. (w) w K, w, where K. is strictly positive definite if the unlabeled data are pairwise different, w o Wn and is characteristic kernel according to [32].
Recall our low-budget setting (so w o W, holds) and assumption for kernel, K, is indeed a strictly positive definite matrix. Thus MMD k.o.X,, is convex functional w.r.t. w, leading to the fact that
minw T1=1 1=1
MMD X., (w) can be solved by Frank-Wolfe algorithm. Then for p n.
Sp E arg min s (Kw, ap) arg min e, (Kw, -ap). e;+'((]]
1=1
Let e;; Sp, under uniform step size in Frank-Wold algorithm, we have
P +
1
p+1
p+1 c =
(p+1)
as the update formula of Frank- Wolfe algorithm, which equivalent to
i E arg min
Σ ((xx,x)) op Σ 1=1
k(x;, xt)-
DE [P)
JEZ,
then we can immediately derive the iterating formula in
A.2 Pseudo Codes
Algorithm 2 Generalized Kernel Herding
Require:
Data set X., (x...... xx definite, characteristic and radial kernel k(:,-) on N' x X; trade-off parameter a S 1.
X; the number selected samples m n: positive
Ensure: selected samples XI;, {x Xx
1: For each x; E X, calculate (ux;) = プラ= h(x,, x;)/n.
2: Set 31 = 1, S. = = 0. m) do 4: it E arg min (x;) - a)((x;)
3: for [1,-
5: For all i E [m). update Sx(x; = Sp) (x:) + (x, xi)
6:
I + IØ U (iz). p 1, set 3p = 1/pp.
7: end for
B Technical Lemmas
Lemma B.1 (Lemma' 2 B21). Let (tx), and (aw)s be two real positive sequences and A be a strictly positive real. If t satisfies
t A and tx+1 (1 ax+1) Aat 1, with ag 1/k for all k, then t2 < A(2 + log k)/ 1) for all k 1.
14

---

Lemma B.2. The selected samples XI; generated by GKH (Algorithm
satisfies
MMD R, (Xrg, X,) S M + B 2+ log m
(10)
+
where =2,, 0 S maxxex k(x,x) x) S K, Ma defined by
Ma = min MMD A. (w)
w11=1
Proof. Following the notations in Appendix A
let Pa ap, we could straightly follow the proof
for amite-sample-aee error bound of kermel herding with predefined step sizes given by [32 to derive
Lemma B.2 without any other technique. The detailed proof is omitted.
Lemma B.3. Let H be an RKHS over X' associated with positive definite kernel k. and 0
S
maxxex k(x, x) S K. Let Xm {x Y, {y,)T=1 Xt,J, E X. Then for any a S
MMM (Xmm Y. MMD Y. S a)vK
Proof.
MMD k.a (Xms Y.,) 4MMD((X.)) Yn
sup [I. x11
1 m1 7
(xx)
- Σ
n
((x)))
sup
m Σ (xi)
m
- n
1 1(5))))
11
I
5=1
5=1
1
-1-a* n
sup S1
f (yi)
sup 11
(wi)
1-
1 ---a (11-0)
sup
sup
(LA((-55)
n
S1
n
1=1
a
Σ [fll j=1
sup
1
Lemma B.4 (Proposition 12.31 48 ). Suppose that Hi and H2 are reproducing kernel Hilbert spaces of real-valued functions with domains Xi and X2, and equipped with kernels kn and k2, respectively. Then the tensor product space H. = H., @ Hy is an RKHS of real-valued functions with domain X1 X2, and with kernel function
le ((11, (x'1, = ki (II, K2 (x2,
Lemma B.5 (Theorem 5.7 BID. Let f E Hi and E H2, where Hi, H2 be two RKHS containing real-valued functions X, which is associated with positive definite kernel k2, k2 and canonical feature map Φ1, 22, then for any x E X,
f(x) + g()) (1))
+ (g, (2))))))) (f + (0: + o2)(2)) H1
where
Hi + H2 {ʃ1 + f2 H.} and Φi 02 is the canonical feature map of Hi H2. Furthermore,
Ilf + g H1 +2z - |1ffl + ll 2 Lemma B.6. For any unlabeled dataset X, C X and any subset X
MMD3.... X., = (1 (1-6h ()-a)2K- a) MMD? k.a (X.m.. X S (1+ K2),,
where K Eh E k(x, n/2, K maxxex k(x, x).
Lemma B.6 directly derived from the definition of a-MMD.
15

---

C Proof of Theorems
Proof for Theorem 5.4 The proof borrows the technique introduced in (37 for decomposing the expected risk of hypotheses.
Firstly, let denote that 74, 11 + @ H2 + H3. with kernel ha ki h1 R2 hy and canonical feature map Φ1 = Φ1 @ Φ1 + Φ1 ②
Ø2 + Ø3-
Under the assumptions in Theorem 5.4 according to Theorem 4 in 41 we have for any x E N.
1(x) (h, 01 (x)) B[y xx] ( X (2(x))
Var(Y (Var (Var(Y|X) (1|)) Ds (x))
where 11, 22, Øs canonical feature maps in H1, H2, Hz. Denote that E| and Var(Y|X). Now by definition,
R(h) (e(h(x), S e(h(x)) () 1 (xx)
where
f(x) / ( h(x)) (pp)))pppiill p(y)p(())) x)dy
Var(Y xx) 2h 2x(x)E((Y [x] + h² (xx
(8,03(x)) 2 (h, 01 (x)) ni (m, (2(x)) + (h, (x)) (h, 0z (x)) (8,05(x)) (2h 8 m. (01 & のz) dz) + (h @ h, (0r & oz)(x)) mx),
(s - 2h @ m + h @ h, (1())
where the fourth equality holds by Lemma B.4 and the last equality holds by Lemma B.5 then f E H4. and
||]
||s 2h + h 6 hllm
< || + 1|2h @ mi]H. H4. + /| @ hl]
S || + 2|]m/|/aall0 [//l + ||/ hl],,
|| + +2|mm||,,llM] |1 + ||/
S K Km KK,
where the second inequality holds by Lemma B.5
Therefore, let ==1/=KK] + Km + Ks) we
have ||3 &11 k. $
Then
(T( - Ris(h)
1 [(x)dPr(xx) -f f(x)dPs(x)
=(K3 + Km + KK)) 1/ 3f(x)dP((x) Bf(x)dPs(xx)
f(x)dPr(x) - / f(x))dPs(x)
<(K) + Km + Ko) sup
=(K + 2K, Km + K.) (Xs. X7)
where Pr denotes the empirical distribution constructed by Xx. does Ps. Recall Lemma B.3 we have Theorem 5.4
Proof for Theorem 5.6 Following the notations in Appendix A further define
1/n, C2 .MMD? k.a.X. (w.) 2
(1I)
K-1 K
K-111 K-111
K-1
arg min 2MD? ? k.a.X,, (w)
p 1K
1 w=1
16

---

Let Pa ap, we have (Pa - KW)) x 1. Define
Da(w) (w) MMD R.o.X. (w) - g(w) -(w.)
where g(w) = (w W) K (w w) The related details for proving the equality are omitted, since
they completely given by the proof of alternative expression of MMD in Pronzato 32 By the convexity of ((-), for = arg minie Izz. (x:),
(w.)) 2 / (wp) + (w. wp) K (w, w) 2 (wwp) +
min (ej wp) K (w, W) jE(n](z
where the second inequality holds with the assumption in Theorem 5.6
(w. - e₁) K (w, W) (w, -e,) (Kwp Pa)
Ei= fxz(xi) fz; (2)p=s)
Ei (x;(
fzz (x)(x))
therefore, we have for B 2K,
Aa (W(w1))
-9 (wp) 5 (W.) ww.)+ + p+1 (o, - [ppp W K(w, - (W) + (p+ 1)2 (e, wp) K K(e Wp) (12)
2
p ( w (w.)) + 1)² p p+1 Aw(p)
1)+ B
where Wp+1 = /p e, (p 1), and obviously B upper bounds (e,- - wp) (e; - -wp)
Since 1, it holds from Lemma B.6 that
Au (w1) s MMD 2 (w1) - (1+ B
therefore by Lemma B.1 have
2 log m
MMD Ko
(x X.) = MMD X, (wp) 5 CC2 +
m +
D Additional Experimental Details and Results
D.1 Supplementary Numerical Experiments GKHR
Consider the fact that GKH is a convergent algorithm (Lemma B.2 and the shiit--samll-sizze error bound (IO) holds without any assumption the data, conduct some numerical experiments to empirically compare GKHR with GKH on datasets generated by four different distributions on R2.
Firstly, we define four distributions on I
Gaussian mixture model which consists of four Gaussian distributions G2, G3, G4 with mixture weights [0.95, 0.01, 0.02, 0.02].
2. Gaussian mixture model 2 which consists of four Gaussian distributions Gi, G2, G3, G4 with mixture weights [0.3, 0.2, 0.15, 0.35).
3. Uniform distribution 1 which consists of uniform distribution defined in circle with radius 0.5, and uniform distribution defined in a annulus with inner radius and outer radius 6,
4. Uniform distribution 2 defined on [-10, 10
where
2
G2 = ([=)
[
G N
0 5
0
2
5
[8
0
[5
T
0
G3 =
4
0
6
G4 =
10
0
9
17

---

Gaussian Mistre Model
Gausslan Mixture Model
43
60
Uniform Distribution
Uniform 2istribttin
(6)
Gaussian Mixture Model
Gaussian Mixture Model
Unilomm
(b) n=3000
Gauasiinn Mieture Model
Gausstan Mixture Model
Unilom Distr
Uniform Distribtion 2
(c) 1010000
2149 Unitomm Distr
Unitorm Distribution
(d) 3-00000
Figure 2: The performance comparison between GKHR and GKH with different m, ten independent runs. The blue line is the mean value of D. the red dotted line over (under) the blue line the value of D plus (minus) its standard deviation, and the pink area is the between the upper and lower red dotted lines.
18

---

To consistently evaluate the performance gap between GKHR and GKH at the same order of magnitude, we propose the following criterion
D1 D2
D
D1 + D2
where D1 = MMD (x x), D2 = MMD
Ria (X (,), Im
(2)
x is the selected samples from
R,a
GKHR and (2) is the selected samples from GKH. Positive value of D implies that GKH outper- forms GKHR, and negative values of D implies that GKHR outperforms GKH. Large absolute value of D shows large performance gap.
The experiments are conducted follows. We generate 1000,3000, 1000,,00010000,300000 10000,3000 random samples from the four distributions separately, then use GKHR and GKH for sample selection under the low-budget setting, i.e., m/n S 0.2. The a is set by m/n. We report the results over ten independent runs in Figure 2 which shows that although the performance gap tends to grow as grows, when m relatively small, the performance of GKHR is similar that of GKH. Therefore, under the low-budget setting, GKHR and GKH have similar performance on minimizing a-MMD over various type of distributions, which convinces that GKHR could work well in the sample selection task.
D.2 Datasets
For experiments, we choose five common datasets: CIFAR-10/100, SVHN, STL-10 and ImageNet. CIFAR-10 and CIFAR- 100 contain 60,000 images with 10 and 100 categories, respectively, among which 50,000 images are for training, and 10,000 images are for testing; SVHN contains 73,257 images for training and 26,032 images for testing: STL-10 contains 5,000 images for training, 8,000 images for testing and 100,000 unlabeled images as extra training data. ImageNet spans 1,000 object classes and contains 1,281,165 training and 100,000 test images. The training sets of the above datasets are considered as the unlabeled dataset for sample selection.
D.3 Visualization of Selected Samples
To offer more intuitive comparison between various sampling methods, visualized samples chosen by stratified, random, k-Means, USL,, ActiveFT and RDSS (ours). We generate 5000 samples from Gaussian mixture model defined on R.2 with 10 components and uniform mixture weights. One hundred samples are selected from the entire dataset using different sampling methods. The visualisation results in Figure 3 indicate that our selected samples distribute more similarly with the entire dataset than other counterparts.
D.4 Computational Complexity and Running Time
We compute the time complexity of various sampling methods and recorded the time required to select 400 samples on the CIFAR- 100 dataset for each method. The results are presented in Table [ where represents the annotation budget, denotes the total number of samples, and T indicates the number of iterations. The sampling time was obtained by averaging the duration of three independent runs of the sampling code sampling efficiency of our method surpasses that of all other methods except for random and stratified sampling. This discrepancy is likely because the execution time of other algorithms is affected by the number of iterations T.
idle server without any workload. As illustrated by the results, the
Table 5: Efficiency comparison with other sampling methods.
Method
Time complexity
Time (s)
Random
(n) ((n)
~ 0
Stratified
k-means
O (mna)
579.97
USL
O OmnnT
257.68
ActiveFT
O OmnTT
224.35
RDSS (Ours)
(mm))
132.77
19

---

(a) Stratified
(b) Random
(c) K-Means
(d) USL
(e) ActiveFT
(1) RDSS (ours)
Figure 3: Visualization of selected samples using different sampling methods. Points of different
colours represent samples from different classes, while black points indicate the selected samples.
D.5 Implementation Details of Supervised Learning Experiments
We use ResNet-18 18 [66 as the classification model for all AL approaches and our method. Specifically, We train the models for 300 epochs using SGD optimizer (initial learning rate=0.1, weight decay=5e- momentum=0.9) with batch size 128. Finally, we evaluate the performance with the Top-1 classification accuracy metric the test
D.6 Direct Comparison with AL/SSAL
The comparative results with AL/SSAL approaches are shown in Figure 1 and Figure 5 respectively. The specific values corresponding to the comparative results in the above two figures are shown in Table
And the above results are from 8 and
Table 6: Comparative results with AL/SSAL approaches.
CIFAR-10
CIEAR-10P
Budget
250
500
1000
2000
4000
5000
7500
10000
400
2500
5000
7500
10000
Aciine Leurning (AL)
$7.56
37.36
53.06
VAAL
81.02
86.82
$8.97
38.46
47.02
53.99
LearnLoss 60
81.74
85.49
87.06
36. 12
47.8.
54.02
MCDAL
Somi Suporstedd Artile Aetive Learning (SSAL)
CoreSetSSL 36
90.94
92.34
93.30
94.02
63.14
66.29
68.65
CHSSAL
94.55
63.73
TOD-Semi
79.54
87.82
90.3
36.97
52.87
58.61
Semd Supertized Learning (SSL) with RDSS
Mexxaacch RDSS (Ours)
67.27
73.21
HooMMicchRRSS (Ours) 95.05 95.50
95.98
67.40
73.15
According to the results, we have several observations: (1) AL approaches often necessitate signifi- cantly larger labelling budgets, exceeding RDSS by 125 or more on CIFAR-10 10. This is primarily because AL paradigms are solely dependent on labelled samples not only for classification but also for feature learning. (2) SSAL and our methods leverage unlabeled samples, surpassing traditional AL approaches. However, this may not directly reflect the advantages of RDSS, as such performance enhancements could be inherently attributed to the SSL paradigm itself. Nonetheless, these experi- mental outcomes offer insightful implications: SSL may represent a more promising paradigm under scenarios with limited annotation budgets.
20

---

95.0
Accuracy
CoreSet
VAAL
87.5
LearnLoss
MCDAL
85.0
CoreSetSSL
CBSSAL
82.5
TOD-Semi
RIS (Ours)
80.0
RRSS (Ours)
2000
4000
6000
8000
10000
Budget
Figure 4: Comparison with AL/SSAL approaches on CIFAR-10.
70
CoreSet
Accuracy
VAAL
LearnLoss
MCDAL
CoreSetSSL
45
CBSSAL
TOD-Semi
FlexMatch+RDDS (Ours)
FRSSMatch+RDSS (Ours)
35
0
2000
4000
6000
8000
10000
Budget
Figure 5: Comparison with approaches CIFAR-100.
E
Limitation
The choice of depends the number of full unlabeled data points, independent of the information on the shape data distribution. This may lead to loss of effectiveness of RDSS on those datasets with complicated distribution structures. However, outperforms fixed-ratio approaches the datasets under different budget settings.
Potential Societal Impact
Positive societal impact. Our method ensures the representaaivennss and diversity of the selected samples and significantly improves the performance of SSL methods, especially under low-budget settings. This reduces the cost and time of data annotation and is particularly beneficial for resource- constrained research and development environments, such as medical image analysis.
Negative societal impact. When selecting representative data for analysis and annotation, the processing of sensitive data may be involved, increasing the risk of data leakage, especially in sensitive fields such medical care and finance. It is worth noting that most algorithms applied in these sensitive areas are subject to this risk.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We summarize our contributions in the last paragraph of Section [ The RDSS framework, including the quantification method and sample algorithm, illustrated in Section 4 Theoretical analysis on RDSS is presented in Section 5 Section 6 suggests the choice for kernel and tuning parameters. The comparison results with other methods are shown in Section
7.2 and Section 7.3
And we analyze the effect of different in
Section 7.4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
22

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For the generalization bound in Section 5.1 the required assumptions are
Assumption 5.1 5.2 and 5.3] the proof is given by the Proof of Theorem 5.4 Appendix C
For the finite-sample-erron bound in Section 5.2 the required assumption is Assumption 5.5
the proof given by the Proof of Theorem 5.6 in Appendix C Other technical lemmas and their proof' or references are presented in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
We disclose the implementation details of the main experiments for repro- duction in Section 7.1 and Appendix D.5. We submit the code of our proposed method as supplemental material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
23

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The data used for experiments are all publicly available datasets, as referenced in the penultimate paragraph of Section And we submit the code as supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cr
Seallic/giies/Codee /tte///Seeonsssssoooooiiiieeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ptaiss.cc/uublicguuudees Sow.eedeeeeoooeeeeeeeeeeeeeeeeee setpsubmissssioiiii swioiilicoyyycccooocooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify the implementation details of main experiments in Section 7.1 and Axpendix[D.5)
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Fach result of main experiments shows mean accuracy and standard deviation over five independent runs in Section
24

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We illustrate the compute resources utilized by the experimental implementa- tion in Section 7.1 and calculate the time of execution in Appendix D.4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp//whorrppp...c///bbl/teatt
Answer: [Yes]
Justification: We have read the NeurIPS Code of Ethics and ensure that the research conducted in the paper conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
25

---

Answer: [Yes]
Justification:
We discuss the potential societal impacts of our work in Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the original paper that produced the assets used in the paper and ensure that the use of these assets complies with the relevant licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
26

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We submit our code and the corresponding documentation as supplementary
materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
27

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "yWTB6PepJV", "reviewer": "Reviewer_Qb3b", "summary": "Choice of the labeled set in the semi supervised learning is critical for the final performance of the model. This problem can also be looked as AL with SSL, or single shot AL with SSL (in other words similar to experimental design). This works provides a way to select the seed set which is representative, as well as diverse. The problem is reduced to minimizing MMD and similarity score of the selected examples. The paper finally proposes a greedy algorithm, and compare the proposed method against various subset selection baselines, and AL.", "questions": "Refer to the weaknesses.", "limitations": "Refer to the weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the motivation of the problem and a neat theoretical derivation of the objective, and the provided theoretical analysis. Paper was also easy to follow and experiments are compelling.", "weaknesses": "- From a purely combinatorial point of view, I think that the final objective is supermodular in nature. Given the vast literature on submodular/supermodular functions, is it not possible to get an algorithm purely from that standpoint? If so, how different would it be from the proposed one? \n\n- Can one derive things such as leverage scores to detect the outlier-ness of a given point (or any other score)? If so, then couldn't one use something such as diversity - outlier score (or add a score that models likelihood) , with diversity such as Facility location function, and optimize the final objective using greedy? \n\n- In experiments I believe one of the strong baselines such as facility location function is missing. Facility Location has a rich history and have been used in several instances in Active Learning ([1, 2, 3, 4]). I believe authors can add a small discussion on FL and add that baseline. Furthermore, other diversity based approaches have also been considered in the past [5]\n\n- Now a days a lot of focus is also for doing finetuning of existing CLIP models [3]. I'd appreciate one experiment on fine-tuning the CLIP models using the proposed method. \n\n\nReferences\n- [1] Submodularity in machine learning and artificial intelligence\n- [2] An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models\n- [3] LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning\n- [4] Deep Submodular Peripteral networks\n- [5] GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments, which have definitely helped us enhance the paper and highlight its contributions in a better way.\n\n**W1. Given the vast literature on submodular/supermodular functions, is it not possible to get an algorithm purely from that standpoint? If so, how different would it be from the proposed one?**\n\n**Response:** Thank you for your question. In our opinion, it is possible to derive a sample selection algorithm from submodular/supermodular functions. This idea is inspiring to us, and we will try to explore its realizability. However, in our paper, if we apply submodular/supermodular functions to deal with the optimization problem, the problem can be purely combinatorial and may lose its advantage in low computational complexity, which is achieved by exploring the convexity of the weighed MMD function (see Appendix A.1).\n\n**W2. Can one derive things such as leverage scores to detect the outlier-ness of a given point (or any other score)? If so, then couldn't one use something such as diversity - outlier score (or add a score that models likelihood), with diversity such as Facility location function, and optimize the final objective using greedy?**\n\n**Response:** Thank you for your question. Multiple combinations of representativeness and diversity criteria are applicable to define sample selection optimization objectives by representativeness and diversity. However, to derive an effective methodology, one should also provide an efficient algorithm and some theoretical guarantees, which require a detailed study on the definition of the optimization objectives.\n\nFrom this perspective, your idea can be effective if your final objective can be modelled by a submodular framework. Intuitively, this can be achievable if we detaily study the properties of facility location function, diversity - outlier score and models likelihood. In our paper, we use kernel methods and RKHS to model the problem and derive GKHR as an efficient algorithm and generalization/finite-sample-error bound as the theoretical guarantee. The artful combination of representativeness (MMD) and diversity (kernel functions) criterions provide us a simple but effective approach to model the sample selection problem, so we don't have to use greedy algorithm to deal with it. Nevertheless, next time, we will try to start from your standpoint to study this problem if possible.\n\n**W3. Comparison with facility location function [1-4] and diversity based approaches [5] is missing.**\n\n**Response:** We follow your suggestions and compare two facility location-based methods from [2], namely the k-center and the conventional Facility Location (FL) method, as well as the GLISTER method [5]. Notably, the k-center method is equivalent to the Coreset method [6], which we have already benchmarked in our original manuscript (refer to line 309, Table 2).\n\nThe sampling process in GLISTER is tightly coupled with the downstream classification task, making it impossible to pre-determine all labelled samples, which renders it unsuitable for SSL. Therefore, we conduct comparisons under the AL framework, consistent with the experimental setup described in Appendix D.5 of the original manuscript. The results are presented in the table below, demonstrating that RDSS consistently outperforms the other methods, with particularly significant improvements observed on CIFAR-100 using 7,500 labels. We will incorporate these experimental results into a subsequent version of the manuscript.\n\n| Dataset       | CIFAR-10  |           | CIFAR-100 |           |\n| ------------- | ---       | ---       | ---       | ---       |\n| Budget        | 7500      | 10000     | 7500      | 10000     |\n| k-center      | 85.46     | 87.56     | 47.17     | 53.06     |\n| FL            | 86.03     | 89.21     | 47.87     | 55.45     |\n| GLISTER       | 86.64     | 89.33     | 48.74     | 55.39     |\n| RDSS (Ours)   | **87.18** | **89.77** | **50.13** | **56.04** |\n|  |  |  |  |  |\n\n\n**W4. I'd appreciate one experiment on fine-tuning the CLIP models [3] using the proposed method.**\n\n**Response:** This is a good point. We fine-tune the CLIP model via a selection-via-proxy approach [3]. We compare the RDSS with random and k-center sampling methods on CIFAR-10/100 with 10,000 labelled instances when applied to FlexMatch and FreeMatch. The results are shown in the table below, from which we find that RDSS achieves the highest accuracy, outperforming the other two sampling methods. We will incorporate these experimental results into a subsequent version of the manuscript.\n\n| Dataset       | CIFAR-10  | CIFAR-100 |\n| ------------- | ---       | ---       |\n| *Applied to FlexMatch* |        |     |\n| Random        | 96.46     | 83.37     |\n| k-center      | 96.51     | 85.48     |\n| RDSS (Ours)   | **97.83** | **86.75** |\n| *Applied to FreeMatch* |        |     |\n| Random        | 96.58     | 83.29     |\n| k-center      | 96.75     | 86.14     |\n| RDSS (Ours)   | **98.02** | **86.96** |\n|  |  |  |\n\nReferences:  \n[1] Submodularity in machine learning and artificial intelligence. arXiv preprint, 2022.  \n[2] An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models. arXiv preprint, 2024.  \n[3] LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning. Journal of Data-centric Machine Learning Research, 2024.  \n[4] Deep Submodular Peripteral networks. arXiv preprint, 2024.  \n[5] GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning. AAAI, 2021.  \n[6] Active learning for convolutional neural networks: A core-set approach. ICLR, 2018.", "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": "", "extra_scores": {}}, {"review_id": "bhUQhi7xof", "reviewer": "Reviewer_GzC9", "summary": "This paper proposes a new sample selection method, RDSS, for the SSL task. RDSS considers both the representativeness and diversity of the selected sample and achieves state-of-the-art performance. This is achieved by the proposed α-MMD criterion and an efficient optimization algorithm GKHR.", "questions": "Please refer to the weakness.", "limitations": "Please refer to the weakness.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. RDSS considers both representativeness and diversity of samples, which is a convincing strategy, and the experimental results also demonstrate the effectiveness of this motivation.\n2. Sufficient theoretical analysis and experimental comparisons are conducted to demonstrate the effectiveness of the proposed method.", "weaknesses": "I would like to see images of the actual selected samples and visualizations of the feature distribution to demonstrate that RDSS indeed balances the representativeness and diversity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your insightful comments, which have greatly contributed to improving the quality of our paper. We hope our responses can address all your concerns.\n\n**W1. I would like to see images of the actual selected samples and visualizations of the feature distribution to demonstrate that RDSS indeed balances the representativeness and diversity.**\n\n**Response:** We follow your suggestion and upload a PDF that contains the actual samples selected using different sampling methods in the \"global\" response. It can be observed that in the samples selected by our method, the variation in the number of samples across different categories is minimal. In contrast, certain methods fail to select representative samples for every category. For instance, $k$-means does not choose any samples from the *horse* category. Additionally, other methods tend to select an excessive number of similar samples within a single category, thereby neglecting diversity. For example, the ActiveFT approach selects too many samples from the *airplane* category.", "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": "", "extra_scores": {}}, {"review_id": "w14JM6MlJs", "reviewer": "Reviewer_sn3m", "summary": "This paper proposes a Representative and Diverse Sample Selection approach (RDSS) that utilizes a modified Frank-Wolfe algorithm to minimize a novel α-Maximum Mean Discrepancy (α-MMD) criterion, aiming to select a representative and diverse subset from unlabeled data for annotation. Experimental results demonstrate that RDSS consistently improves the performance of several popular semi-supervised learning frameworks and outperforms state-of-the-art sample selection methods used in Active Learning (AL) and Semi-Supervised Active Learning (SSAL), even under constrained annotation budgets.", "questions": "1. The definition and usage of variable X in the article are inconsistent. \n2. Is Y in the section starting from line 141 representing the point as X? If so, I suggest using notations like Xi, Xj for clarity.\n3. In Chapter 6, the determination of the kernel and parameters seems arbitrary. Could you provide some proofs, theories, or experiments to justify them?\n4. The SOTA models selected by the author in the experiments are somewhat outdated. It is recommended to include some more updated methods.\n5. In the experiment section, the author mentions the limitations of stratified sampling. What do these limitations refer to? Why was this method excluded? From the results, it seems that stratified sampling outperforms the proposed method in several settings.\n6. In Table 2, what sampling method did the other comparison methods adopt?\n7. What dataset does Table 3 represent? What is the data distribution?\n8. The author should objectively evaluate their method, including its limitations.", "limitations": "as Weaknesses", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper is in Well-written, logically organized, and smoothly expressed.\n2. The presented results demonstrate the effectiveness of the proposed approach.", "weaknesses": "1. The author conducted tests on two baseline methods(FlexMatch [58] and Freematch [50]), but neither of them represents the current state-of-the-art.\n2. Some details of the experiments are unclear, such as in Table 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your insightful comments. Since Weakness 1 and Question 4, as well as Weakness 2 and Question 7, address the same issue, we have consolidated them accordingly.\n\n**Q1. The definition and usage of variable X in the article are inconsistent.**\n\n**Response:** Thank you for your careful review of our work. In this article, $\\mathbf{X}$ is used for describing datasets, $\\mathcal{X}$ denotes the feature space, and X is denoted as random variables. Could you please point out the inconsistent part?\n\n**Q2. Is Y in the section starting from line 141 representing the point as X? If so, I suggest using notations like Xi, Xj for clarity.**\n\n**Response:** We understand your concern. From line 141, y and Y are used rigorously to explain kernel tricks and the definition of MMD, which are commonly used in statistics literature. Nevertheless, we will consider your suggestion for the modification.\n\n**Q3. In Chapter 6, the determination of the kernel and parameters seems arbitrary.**\n\n**Response:** Here is the determination of the kernel and parameters.  \n*Kernel:* Our determination of kernel is based on the kernel choice in the study of two-sample test by [1]. In fact, according to Remark 1 (line 170), you can see that any positive-definite and characteristic kernel is applicable to our method. Among all kernels, Gaussian kernels are the most popular in the study of machine learning, so we take them as our suggestion.\n\n*Bandwidth parameters:* The choice is also based on [1]. So far there is no theoretical guidance for us to determine the bandwidth parameters of Gaussian kernels in measuring similarity or representativeness. Some methods optimize this parameter in the learning process, but this idea is not applicable in RDSS.\n\n$\\alpha$: According to lines 246-250, we derived a finite-sample-error bound for MMD, which measures the representativeness, leading to our suggestion of the range of $\\alpha$. In the experiments, the choice of $\\alpha=1-1/\\sqrt{m}$ significantly outperforms other choices. \n\n**Q4 & W1. The SOTA models selected by the author in the experiments are somewhat outdated.**\n\n**Response:** Thank you for your suggestion. Since the sampling process and the SSL process are relatively independent, comparing the sampling methods across different SSL models may have a limited impact. However, we have still compared different methods under two additional SOTA SSL approaches, i.e., ReFixMatch [2] and SequenceMatch [3]. The experimental results in the table below show that RDSS achieves the highest accuracy.\n\n| Dataset              | CIFAR-10 |     |      | CIFAR-100  |      |      | SVHN |     | STL-10 |     |\n| -------------------- | ---      | --- | ---  | ---        | ---  | ---  | ---  | --- | ---    | --- |\n| Budget               | 40       | 250 | 4000 | 400        | 2500 | 10000| 250  | 1000| 40     | 250 |\n| *Applied to ReFixMatch* |        |     |      |            |      |      |      |     |        |     |\n| ActiveFT    | 75.62 | 93.56 | 95.64 | 26.86 | 56.97 | 71.65 | 96.17 | 96.97 | 62.53 | 87.53 |\n| USL         | 94.34 | 95.12 | 95.77 | 48.23 | 66.61 | 72.33 | 96.16 | 97.17 | 75.38 | 91.24 |\n| RDSS (Ours) | **95.18** | **95.54** | **96.22** | **49.32** | **67.46** | **73.15** | **96.75** | **97.52** | **78.78** | **92.25** |\n| *Applied to SequenceMatch* |        |     |      |            |      |      |      |     |        |     |\n| ActiveFT    | 78.91 | 95.02 | 95.11 | 31.94 | 55.49 | 70.38 | 93.65 | 94.20 | 69.44 | 89.44 |\n| USL         | 94.12 | 95.10 | 95.85 | 49.34 | 67.04 | 73.68 | 95.22 | 96.04 | 76.63 | 90.13 |\n| RDSS (Ours) | **95.33** | **95.26** | **96.17** | **50.76** | **69.96** | **74.83** | **96.86** | **97.91** | **81.41** | **92.86** |\n|  |  |  |  |  |  |  |  |  |  |  |\n\n**Q5. What are the limitations of stratified sampling. Why was this method excluded?**\n\n**Response:** Stratified sampling requires prior knowledge of sample categories, and then random sampling is performed within each category. However, in many real-world scenarios, we do not have prior knowledge of sample categories, making stratified sampling inapplicable. This is its limitation. We have a more comprehensive description in the manuscript (Line 25 and Line 81).\n\n**Q6. In Table 2, what sampling method did the other comparison methods adopt?**\n\n**Response:** We are sorry for overlooking this. The sampling methods employed by the AL approaches in Table 2 are as follows:  \n*CoreSet* uses a greedy algorithm known as $k$-Center-Greedy to select a subset from the unlabeled dataset;  \n*VAAL* consists of a VAE and an adversarial network. The VAE tries to trick the adversarial network into predicting that all data points are from the labelled pool, the adversarial network learns how to discriminate between dissimilarities in the latent space. The samples predicted as \"unlabeled\" by the adversarial network are selected for labelling;  \n*LearnLoss* designes a loss prediction module for a target network, which predicts target losses of unlabeled samples. The samples with the top-$K$ predicted losses are selected to be labelled;  \n*MCDAL* utilizes two auxiliary classification layers to select samples with the largest prediction discrepancy between them as those requiring labelling.\n\n**Q7 & W2. What dataset does Table 3 represent?**\n\n**Response:** Thank you for your reminder. The dataset used in Table 3 is CIFAR-10. We will refine these details in the next version of our manuscript.\n\n**Q8. The author should objectively evaluate their method, including its limitations.**\n\n**Response:** Thank you for your insightful suggestion. We have discussed the limitations of our method in Appendix E.\n\nReferences:  \n[1] A kernel two-sample test. The Journal of Machine Learning Research, 2012.  \n[2] Boosting Semi-Supervised Learning by bridging high and low-confidence predictions. ICCV, 2023.  \n[3] SequenceMatch: Revisiting the design of weak-strong augmentations for Semi-supervised learning. WACV, 2024.", "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": "", "extra_scores": {}}, {"review_id": "kVd9TqqRxl", "reviewer": "Reviewer_CxrG", "summary": "The paper suggests a new sampling method for the labeled set of semi-supervised learning. This sampling method, termed RDSS, selects a set of examples that is both representative of the data, and diverse. The paper shows that using such a sampling function improves both freematch and flexmatch, and compares it against other sampling methods, and methods from AL and SSAL.", "questions": "Can you please elaborate on how the proposed method differs from the idea suggested in [2]?\n\nHow is the problem of selecting the labeled set of SSL different from the problem setting of active learning?", "limitations": "not relevant", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The idea of the paper is good, and is well supported by theory. The experimental setup does convince me that the suggested method is better than random sampling when picking the labeled set of SSL. However, a better comparison to previous works is required, see the Weaknesses section.\n\nClarity: The paper is clearly written, the idea is well presented and intuitive, and the paper is easy to read and follow.", "weaknesses": "Some of the claims made by paper already appeared in previous art. Specifically, [1] showed that \"traditional\" AL methods do not pick bad labeled sets for SSL when compared to random sampling. [2] showed that when the labeled set is particularly small, instead of traditional AL techniques, one should focus on labeling examples that are more typical and diverse, showing that such a method can drastically improve both AL and sampling techniques for SSL. [3] presented sampling strategy, showing that picking examples that are representative and diverse examples for the labeled set of  SSL improves it by a big margin in low-budget scenarios.\n\nThe proposed manuscript does not reference or compare to any of these works. This affects both the novelty, significance and quality of the proposed method: the novelty is somewhat more limited, as many of the ideas overlap with existing works. The significance of this work is impacted, as while the problem at hand is important, it is unclear if the presented ideas pose significant advancement over the existing methods, and the quality is diminished, as a lot of comparisons are missing in the experimental setup.\n\nSpecifically, any low-budget strategy could be potentially applied to SSL as well, so those methods should be compared against as well. See for example [4], [5].\n\nAdditionally, the vice-versa argument should also hold -- if AL methods can be applied in this case, this method can be used as a method for picking labeled examples for active learning purposes and should be tested as such, as the literature in AL is much broader than the literature of picking the labeled set in SSL, which can provide a much wider context for the given work.\n\nIn addition, the framing of the paper is a bit unclear to me. I think the paper could benefit from explaining use cases in which one has the option to pick in advance the labeled set for SSL, which is not already covered by AL use cases.\n\n-------\n\n[1] Mittal, Sudhanshu, et al. Parting with illusions about deep active learning. (2019).\n\n[2] Hacohen, Guy et al. Active learning on a budget: Opposite strategies suit high and low budgets. (2022).\n\n[3] Yehuda, Ofer, et al. \"Active learning through a covering lens.\" (2022).\n\n[4] Mahmood, Rafid, et al. \"Low budget active learning via wasserstein distance: An integer programming approach.\" (2021).\n\n[5] Wen, Ziting, et al. \"NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage.\" (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review of our work. We hope our responses can address all your concerns.\n\n**W1. Some of the claims made by paper already appeared in previous art [1-3]. The proposed manuscript does not reference or compare to any of these works.**\n\n**Response:** Thank you for your comment. It is indeed correct that certain aspects of our methodology and initial hypotheses draw from established findings in the literature. The inclusion of these elements is essential for building upon a solid foundation of existing research. However, our work makes significant advancements beyond these foundational elements.\n\nSpecifically, even if our method is based on the perspective of representative and diverse sampling that previous studies have proposed, as we said to Reviewer Qb3b, multiple combinations of representativeness and diversity criteria are applicable to defining sample selection optimization objectives, but one should also provide an efficient algorithm and some theoretical guarantees derive an effective methodology that has better generalizability. In our paper, we artfully use kernel methods and the properties of RKHS to derive a simple but effective approach to model the sample selection problem that fulfils the aforementioned requirements for a generalizable method. In the experimental part, we have compared our method with more recent methods (e.g., USL [6] and ActiveFT [7]) and have achieved SOTA performance (refer to Table 1).\n\n**W2. Any low-budget strategy could be potentially applied to SSL as well, so those methods should be compared against as well. See for example [4,5].**\n\n**Response:** We follow your suggestions and compare our proposed RDSS with [4] and [5] by integrating them into FlexMatch and FreeMatch on CIFAR-10 with 40 labels. The experimental results show that RDSS outperforms the two methods.\n\n| Methods         | FlexMatch | FreeMatch |\n| --------------  | --------- | --------- |\n| Wasserstein [4] | 91.64     | 92.72     |\n| NTKCPL [5]      | 87.47     | 91.30     |\n| RDSS (Ours)     | **94.69** | **95.05** |\n|  |  |  |\n\n**W3. If AL methods can be applied in this case, this method can be used as a method for picking labeled examples for active learning purposes and should be tested as such.**\n\n**Response:** Thank you for your suggestions. In fact, we have already conducted comparisons with several SOTA AL methods, as demonstrated in Table 2 of the original manuscript. To ensure a more comprehensive evaluation, we have further supplemented our study with additional experiments comparing our approach against various AL methods. The results of these extended experiments can be found in our response to Reviewer Qb3b's Weakness 3.\n\n**W4. The framing of the paper is a bit unclear to me. I think the paper could benefit from explaining use cases in which one has the option to pick in advance the labeled set for SSL, which is not already covered by AL use cases.**\n\n**Response:** Thank you for your insightful feedback regarding the framing of the paper. We understand that the distinction between the use cases of SSL and AL may not have been sufficiently clear, and we appreciate the opportunity to clarify this aspect. In this work, we focus on scenarios where one can select a labelled set for SSL in advance, a situation that is distinct from traditional AL use cases. A particularly relevant example is in the context of medical trials. In such trials, labelling data (e.g., annotating medical images or patient records) often involves significant time and resources, typically requiring expert review. If the labelled data in later rounds of the trial must be determined based on the outcomes of previous rounds, as in a typical AL setup, the entire project timeline could be significantly extended due to the sequential nature of labelling and analysis. We will revise the manuscript to explicitly differentiate these use cases.\n\n**Q1. Can you please elaborate on how the proposed method differs from the idea suggested in [2]?**\n\n**Response:** Thank you for your question. Our standpoints are all from the idea of representative and diverse sampling, but each method has its own criterion for representativeness and diversity. This situation also happens when comparing our method to USL [6] and ActiveFT [7]. However, among all these works, our method exhibits not only a theoretical guarantee for generalization error but also a fast and effective optimization algorithm for practical sample selection tasks. Moreover, our method can be implemented in some research problems in the literature of statistical subsampling (e.g. [8]), which shows its potential in interdisciplinary scenarios or problems.\n\n**Q2. How is the problem of selecting the labeled set of SSL different from the problem setting of active learning?**\n\n**Response:** We understand that this is a critical issue. In SSL, the selection of the labelled set is typically predetermined or randomly sampled from an available pool of labelled data. In contrast, AL is an iterative process where the model actively queries an oracle (e.g., a human annotator) to label new samples that are expected to be the most informative for improving the model.\n\nReferences:  \n[1] Parting with illusions about deep active learning. arXiv preprint, 2019.  \n[2] Active learning on a budget: Opposite strategies suit high and low budgets. ICML, 2022.  \n[3] Active learning through a covering lens. NeurIPS, 2022.  \n[4] Low budget active learning via wasserstein distance: An integer programming approach. ICLR, 2022.  \n[5] NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage. arXiv preprint, 2023.  \n[6] Unsupervised selective labeling for more effective semi-supervised learning. ECCV, 2022.  \n[7] Active Finetuning: Exploiting Annotation Budget in the Pretraining-Finetuning Paradigm. CVPR, 2023.  \n[8] Optimal Subsampling via Predictive Inference. Journal of the American Statistical Association, 2023.", "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": "", "extra_scores": {}}]

Author rebuttal:
Here is a visualization of the sampling results for Reviewer GzC9.

Meta-review: This paper studies the sample selection problem for semi-supervised learning and proposes a novel RDSS method by adopting a modified Frank-Wolfe algorithm to minimize a novel criterion α-MMD. During the rebuttal, the authors provide detailed discussion and experimental results corresponding to the questions and weaknesses. The major concerns raised by the reviewers are well addressed. The remaining concern about the difference between the setting of this paper and low-budget AL is properly resolved with the follow-up response. Therefore, this paper meets the standards of NeurIPS and is ready for publication. Please revise this paper according to the reviewers' suggestions in the final version.
Decision: Accept (poster)