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_cc_2024_Conference
Published: 2024-05-04 11:02:16

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.

Main paper: 
 introduction: 
 Semi-Supervised Learning (SSL) is a popular paradigm which reduces reliance on large amounts of labeled data in many deep learning tasks [40, 35, 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 a desirable model that makes consistent and unambiguous predictions [53] . Besides, we also find that how to 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 is impractical in real-world scenarios where the label for each sample is unknown. Existing researchers also employ representativeness and diversity strategies to select appropriate samples for annotation. Representativeness [13] ensures that the selected subset distributes similarly with the entire dataset, and diversity [54] is designed to select informative samples by pushing away them in feature space. And focusing on only one aspect presents significant limitations (Figure 1a and b ). To address these issues, Xie et al. [57] and Wang et al. [50] employ a 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 a theoretical basis to substantiate their effectiveness.We observe that Active Learning (AL) primarily focuses on 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 of the labelling budget, making it difficult to work effectively with a very limited budget (e.g., 1% or even lower) [6] ; (2) They involve human annotators in iterative cycles of labelling and training, leading to 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 α-MMD. It aims to strike a balance between representativeness and diversity via a trade-off parameter α (Figure 1c ), for which we find an optimal interval adapt to different budgets. By using a 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 Kernel Hilbert Space (RKHS) assumptions, α-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 a theoretical assessment of 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 on the datasets CIFAR-10/100 [19] , SVHN [30] , STL-10 [9] and ImageNet [10] . Extensive experiments show that RDSS outperforms other sample selection methods widely used in SSL, AL or SSAL, especially with a constrained annotation budget. Besides, ablation experimental results demonstrate that RDSS outperforms methods using a 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 α-MMD. Under low-budget settings, we develop a 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 α 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 superiority over the fixed-ratio approach. 
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-labelling integrates 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 on large labelled datasets. There are 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 [18, 26] , and classification margin [47] to estimate uncertainty. Recent research regards uncertainty as training loss [17, 60] , influence on model performance [11, 24] or the prediction discrepancies between multiple classifiers [8] . 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 a statistical approach which selects a subset with size m as a surrogate for the full dataset with size n ≫ m. While model-based subsampling methods depend heavily on the model assumptions [1, 61] , improper choice of the model could lead to 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 to 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-mentioned methodologies either exclusively focus on representativeness or diversity, which are difficult to effectively apply to SSL. 
problem setup: 
 Let X be the unlabeled data space, Y be the label space, X n = {x i } i∈[n] ⊂ X be the full unlabeled dataset containing pairwise different data, andI m = {i 1 , i 2 , • • • , i m } ⊂ [n](m < n) be an index set contained in [n], our goal is to find an index set I * m = {i * 1 , i * 2 , • • • , i * m } ⊂ [n](m < n) such that the selected set of samples X I * m = {x i * 1 , x i * 2 , • • • , x i * m } is the most informative.After that, we can get access to the true labels of selected samples and use the set of labelled data S = {(x i , y i )} i∈I * m and the rest of the unlabeled data to train a deep learning model.Following the methodology of previous works, we use representativeness 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 a result, our goal can be formulated by solving the following problem:EQUATIONwhere Rep(X Im , X n ) and Div(X Im , X n ) 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, we 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] . 
representative and diversity sample selection: 
 The Representative and Diverse Sample Selection (RDSS) framework consists of two steps: (1) Quantification. We quantify the representativeness and diversity of selected samples by a novel concept called α-MMD (6) , where λ is replaced by α as the trade-off hyperparameter; (2) Optimization. We optimize α-MMD by GKHR algorithm to obtain the optimally selected samples X I * m .In classical statistics and machine learning problems, the inner product of data points x, y ∈ X , defined by ⟨x, y⟩, is employed to as a similarity measure between x, y. However, the application of linear functions can be very restrictive in real-world problems. In contrast, kernel methods use kernel functions k(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 high-dimensional feature space [29] .Let k(•, •) be a kernel function on X × X , and we employ k(•, •) to measure the similarity between any two points and the average similarity, denoted byEQUATIONto measure the similarity between the selected samples. Obviously, S(X Im ) can evaluate the diversity of X Im since larger similarity implies smaller diversity.As a statistical discrepancy which measures the distance between distributions, the maximum mean discrepancy (MMD) is introduced here to quantify the representativeness of X Im to X n . Proposed by Gretton et al. [14] , 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 ∥ H ≤ 1, then the MMD between P and Q is defined byEQUATIONwhere X, X ′ ∼ P and Y, Y ′ ∼ Q are independent copies.We can next derive the empirical version for MMD that is able to measure the representativeness of X Im = {x i } i∈Im relative to X n = {x i } n i=1 by replacing P, Q with the empirical distribution constructed by X Im , X n in (3):EQUATION)Optimization objective. Set Rep(•, •) = -MMD 2 k (•, •) and Div(•) = -S k (•) in (1),where k is a proper kernel function, our optimization objective becomes minEQUATIONSet λ = 1-α αm , sincen i=1 n j=1 k (x i , x j) is a constant, the objective function in (5) can be rewritten byEQUATIONwhich defines a new concept called α-MMD, denoted by MMD k,α (X Im , X n ). This new concept distinguishes our method from those existing methods, which is essential for developing the sampling algorithms and theoretical analysis. Note that α-MMD degenerates to classical MMD when α = 1 and degenerates to average similarity when α = 0. As α 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 is generally a pseudo-metric on the space of all Borel probability distributions, implying that the MMD between two different distributions can be zero. Nevertheless, MMD becomes a proper metric when k is a characteristic kernel, i.e., P → X k(•, x)dP 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 k(•, •), i.e., its Gram matrix is always positive definite and symmetric, it uniquely determines an RKHS H 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.In the previous research [36, 27, 50, 38, 58] , sample selection is usually modelled by a nonconvex combinatorial optimization problem. In contrast, following the idea of [4] , we regardmin Im∈[n] MMD 2 k,α (X Im , X n )as a convex optimization problem by exploiting the convexity of α-MMD, and then solve it by a fast iterative minimization procedure derived from Frank-Wolfe algorithm (see Appendix A for derivation details):EQUATIONwheref Ip (x i ) = j∈Ip k (x i , x j ) -αp n l=1 k(x i , x l ).As an extension of kernel herding [7] , its corresponding algorithm (see Algorithm 2) is called Generalized Kernel Herding (GKH). Note that f Ip (x i ) is iteratively updated in Algorithm 2, which can save a lot of running time. However, GKH can select repeated samples that contradict the setting of sampling without replacement. To address this issue, we propose a modified iterating formula based on (7) :EQUATIONAlgorithm 1 Generalized Kernel Herding without Replacement Require: Data setX n = {x 1 , • • • , x n } ⊂ X ; the number of selected samples m < n; a positive definite, characteristic and radial kernel k(•, •) on X × X ; trade-off parameter α ≤ 1. Ensure: Selected samples X I * m = {x i * 1 , • • • , x i * m }. 1: For each x i ∈ X n calculate µ(x i ) := n j=1 k(x j , x i )/n. 2: Set β 1 = 1, S 0 = 0, I = ∅. 3: for p ∈ {1, • • • , m} do 4: i * p ∈ arg min i∈[n]\I * p S p-1 (x i ) -αµ(x i ) 5: For all i ∈ [n]\I * p , update S p (x i ) = (1 -β p )S p-1 (x i ) + β p k(x i * p , x i ) 6: I * p+1 ← I * p ∪ {i * p }, p ← p + 1, set β p = 1/p. 7:end for which admits no repetitiveness in the selected samples. Its corresponding algorithm (see Algorithm 1) 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 O(mn), 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 AnalysisQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: We disclose the implementation details of the main experiments for reproduction in Section 7.1 and Appendix D.5. We submit the code of our proposed method as supplemental material. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 a 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 is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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, confidence intervals, or statistical significance tests, at 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. Justification: We discuss the potential societal impacts of our work in Appendix F.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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., deployment 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 not 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 as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
generalization bounds: 
 Recall the core-set approach in [36] , i.e., for any h ∈ H,R(h) ≤ R S (h) + |R(h) -R T (h)| + | R T (h) -R S (h)|,where T is the full labeled dataset and S ⊂ T is the core set, R(h) is the expected risk of h, R T (h), R S (h) are empirical risk of h on T, S. The first term R S (h) is unknown before we label the selected samples, and the second term |R(h) -R T (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), we only need to analyse the upper bound of the third term | R T (h) -R S (h)| called core-set loss, which requires several mild assumptions. Shalit, et al. [37] derived a MMDtype upper bound for | R T (h) -R S (h)| to estimate individual treatment effect, while our bound is generalized to a wider range of tasks.Let H 1 = {h|h : X → Y} be a hypothesis set in which we are going to select a predictor and suppose that the labelled data T = {(x i , y i )} n i=1 are i.i.d. sampled from a random vector (X, Y ) defined on X × Y. We firstly assume that H 1 is an RKHS, which is mild in machine learning theory [3, 5] . Assumption 5.1. H 1 is an RKHS associated with bounded positive definite kernel k 1 where the norm of any h ∈ H 1 is bounded by K h .We further make RKHS assumptions on the functional space of E(Y |X) and Var(Y |X) that are fundamental in the field of conditional distribution embedding [41, 43] . We next give a α-MMD-type upper bound for the core-set loss by the following theorem: Theorem 5.4. Take k = k 2 1 + k 1 k 2 + k 3 , then under assumptions 1-3, for any selected samples S ⊂ T , there exists a positive constant K c such that the following inequality holds:| R T (h) -R S (h)| ≤ K c (MMD k,α (X S , X T ) + (1 -α) √ K) 2 ,where 0 ≤ α ≤ 1, 0 ≤ max x∈X k(x, x) = K and X S , X T are projections of S, T on X .Therefore, minimizing α-MMD can optimize the generalization bound for R(h) and benefit the generalizability of the trained model (predictor).The concept of convergence does not apply to analyzing GKHR. With n fixed, GKHR iterates for at most n times and then returns X I * n = X n . Consequently, we analyze the performance of GKHR by its finite-sample-error bound. Previous to that, we make an assumption on the mean of f I * p over the full unlabeled dataset. Assumption 5.5. For any I * p returned by GKHR, 1 ≤ p ≤ m -1, there exists p + 1 elements {x j l } p+1 l=1 in X n such thatf I * p (x j1 ) ≤ • • • f I * p (x jp+1 ) ≤ n i=1 f I * p (x i ) n .When m is not relatively small, this assumption is rather unrealistic. Nevertheless, under our lowbudget 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 O(log m/m):Theorem 5.6. Let X I * m be the samples selected by GKHR, under assumption 4, it holds thatEQUATIONwhereB = 2K, 0 ≤ max x∈X k(x, x) = K, C 2 α = (1 -α) 2 K where K is defined in Lemma B.6. 
choice of kernel and hyperparameter tuning: 
 In this section, we make some suggestions for choosing the kernel and tuning the hyperparameter α.Choice of kernel. Recall Remark 1 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 of machine learning and statistics [3, 15] , we introduce Gaussian kernel as our choice, which is defined by k(x, y) = exp(-∥x -y∥ 2 2 )/σ 2 . The bandwidth parameter σ is set to be the median distance between samples in the aggregate dataset [15] , i.e., σ = Median({∥x -y∥ 2 |x, y ∈ X n }), since the median is robust and also compromises between extreme cases.Tuning trade-off hyperparameter α. According to Theorem 5.6 and Lemma B.3, by straightforward deduction we haveMMD k X I * m , X n ≤ C α + O log m m + (1 -α) √ Kto upper bound the MMD between the selected samples and the full dataset under a low-budget setting. We can just set α ∈ [1 -1 √ m , 1) so that the upper bound of the MMD would not be larger than the one of α-MMD in the perspective of the order of magnitude. 
experiments: 
 In this section, we first explain the implementation details of our method RDSS in Section 7.1. Next, we compare RDSS with other sampling methods by integrating them into two state-of-the-art (SOTA) SSL approaches (FlexMatch [63] and Freematch [53] ) on five datasets (CIFAR-10/100, SVHN, STL-10 and ImageNet-1k) 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 in Section 7.3. Lastly, we make quantitative analyses of the trade-off parameter α in Section 7.4.First, we leverage the pre-trained image feature extraction capabilities of CLIP [33] , a vision transformer 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 infinite-dimensional feature space. The value of σ 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 α = 1 -1 √ m , where m denotes the number of selected samples. Concretely, we set m = {40, 250, 4000} for CIFAR-10, m = {400, 2500, 10000} for CIFAR-100, m = {250, 1000} for SVHN, m = {40, 250} for STL-10 and m = {100000} for ImageNet. Next, the selected samples are used for two SSL approaches, which are trained and evaluated on the datasets using the codebase Unified SSL Benchmark (USB) [52] . The optimizer for all experiments is standard stochastic gradient descent (SGD) with a momentum of 0.9 [44] . The initial learning rate is 0.03 with a learning rate decay of 0.0005. We use ResNet-50 [16] 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 8*NVIDIA Tesla A100 (40 GB) and 2*Intel 6248R 24-Core Processor. We average our results over five independent runs.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 1 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 a 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 a priori.We also compare the second-best method USL with RDSS on ImageNet. Following the settings of FreeMatch [53] , we select 100k samples for annotation. FreeMatch, using RDSS and USL as sampling methods, achieves 58.24% and 56.86% accuracy, respectively, demonstrating a substantial enhancement in the performance of our method over the USL approach. Second, we compare RDSS with sampling methods used in SSAL when applied to the same SSL framework (i.e., FlexMatch or FreeMatch) on CIFAR-10. The sampling methods conclude Core-SetSSL [36] , MMA [42] , CBSSAL [12] , and TOD-Semi [17] . In detail, we tune recent SSAL approaches with their public implementations and run experiments under an extremely low-budget setting, i.e., 40 samples in a 20-random-and-20-selected setting. Table 3 illustrates that the performance of most SSAL approaches falls below that of random sampling methods under extremely low-budget settings. 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. Third, we 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.We analyze the effect of different α with Freematch on CIFAR-10/100. The results are presented in Table 4 , 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 α that achieve the best or the second best performance are within the interval we set, which is in line with our theoretical derivation in Section 6; (3) The experimental outcomes exhibit varying degrees of reduction compared to our approach when the representativeness or diversity term is removed.  
conclusion: 
 In this work, we propose a model-free sampling method, RDSS, to select a subset from unlabeled data for annotation in SSL. The primary innovation of our approach lies in the introduction of α-MMD, designed to evaluate the representativeness and diversity of selected samples. Under a low-budget setting, we develop a 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 in the medical domain. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is 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 of the dataset/code/model 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: A.1 Derivation of Generalized Kernel Herding (GKH)Proof. The proof technique is borrowed from [32] . Let us firstly define a weighted modification of α-MMD. For any w ∈ R n such that w ⊤ 1 = 1, the weighted α-MMD is defined byMMD 2 k,α,Xn (w) = w ⊤ Kw -2αw ⊤ p + α 2 K, where K = [k(x i , x j )] 1≤i,j≤n , K = 1 ⊤ K1/n 2 , p = (e ⊤ 1 K1/n, • • • , e ⊤ n K1/n), {e i } n i=1 is the set of standard basis of R n . It is obvious that for any I p ⊂ [n], MMD 2 k,α,Xn (w p ) = MMD 2 k,α (X Ip , X n ), where (w p ) i = 1/p if i ∈ I p , and (w p ) i = 0 if not. Therefore, weighted α-MMD is indeed a generalization of α-MMD. LetK * = K -2αp1 ⊤ + α 2 K11 ⊤we obtain the quadratic form expression of weighted α-MMD by MMD 2 k,α,Xn (w) = w ⊤ K * w, where K * is strictly positive definite if the unlabeled data are pairwise different, w ̸ = w n and k is a characteristic kernel according to [32] .Recall our low-budget setting (so w ̸ = w n holds) and assumption for kernel, K * is indeed a strictly positive definite matrix. Thus MMD 2 k,α,Xn is a convex functional w.r.t. w, leading to the fact that min w ⊤ 1=1 MMD 2 k,α,Xn (w) can be solved by Frank-Wolfe algorithm. Then for 1 ≤ p < n, s p ∈ arg mins ⊤ 1=1 s ⊤ (Kw p -αp) = arg min ei,i∈[n]e ⊤ i (Kw p -αp).Let e i * p = s p , under uniform step size in Frank-Wolfe algorithm, we havew p+1 = p p + 1 w p + 1 p + 1 e i * p, w 0 = 0 as the update formula of Frank-Wolfe algorithm, which is equivalent toi * p ∈ arg min i∈[n] j∈Ip k(x i , x j ) -αp n l=1 k(x i , x l ).then we can immediately derive the iterating formula in (7) .Algorithm 2 Generalized Kernel Herding Require: Data set X n = {x 1 , • • • , x n } ⊂ X ; the number of selected samples m < n; a positive definite, characteristic and radial kernel k(•, •) on X × X ; trade-off parameter α ≤ 1. Ensure: selected samples [32] ). Let (t k ) k and (α k ) k be two real positive sequences and A be a strictly positive real. If t k satisfies t 1 ≤ A andX I * m = {x i * 1 , • • • , x i * m }. 1: For each x i ∈ X n calculate µ(x i ) := n j=1 k(x j , x i )/n. 2: Set β 1 = 1, S 0 = 0, I = ∅. 3: for p ∈ {1, • • • , m} do 4: i * p ∈ arg min i∈[n] S p-1 (x i ) -αµ(x i ) 5: For all i ∈ [n], update S p (x i ) = (1 -β p )S p-1 (x i ) + β p k(x i * p , x i ) 6: I * p+1 ← I * p ∪ {i * p }, p ← p + 1, set β p = 1/p. 7: end for B Technical Lemmas Lemma B.1 (Lemma 2t k+1 ≤ (1 -α k+1 ) t k + Aα 2 k+1 , k ≥ 1, with α k = 1/k for all k, then t k < A(2 + log k)/(k + 1) for all k > 1.Lemma B.2. The selected samples X I * m generated by GKH (Algorithm 2) satisfiesEQUATIONwhereB = 2K, 0 ≤ max x∈X k(x, x) ≤ K, M 2 α is defined by M 2 α := min w ⊤ 1=1,w≥0 MMD 2 k,α,Xn (w)Proof. Following the notations in Appendix A, let p α = αp, we could straightly follow the proof for finite-sample-size error bound of kernel 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, and0 ≤ max x∈X k(x, x) ≤ K. Let X m = {x i } m i=1 , Y n = {y j } m j=1 , x i , y j ∈ X . Then for any α ≤ 1, | MMD k,α (X m , Y n ) -MMD k (X m , Y n )| ≤ (1 -α) √ K Proof. |MMD k,α (X m , Y n ) -MMD k (X m , Y n )| = sup ∥f ∥ H ≤1   1 m m i=1 f (x i ) - α n n j=1 f (y j )   -sup ∥f ∥ H ≤1   1 m m i=1 f (x i ) - 1 n n j=1 f (y j )   ≤ sup ∥f ∥ H ≤1 1 -α n n i=1 f (y i ) = 1 -α n sup ∥f ∥ H ≤1 n i=1 f (y i ) = 1 -α n sup ∥f ∥ H ≤1 n j=1 ⟨f, k(•, y j )⟩ H ≤ 1 -α n sup ∥f ∥ H ≤1 n j=1 ⟨f, k(•, y j )⟩ H ≤ 1 -α n sup ∥f ∥ H ≤1 n j=1 ∥f ∥ H ∥k(•, y j )∥ H ≤ (1 -α) √ K.Lemma B.4 (Proposition 12.31 [48] ). Suppose that H 1 and H 2 are reproducing kernel Hilbert spaces of real-valued functions with domains X 1 and X 2 , and equipped with kernels k 1 and k 2 , respectively. Then the tensor product space H = H 1 ⊗ H 2 is an RKHS of real-valued functions with domain X 1 × X 2 , and with kernel functionk ((x 1 , x 2 ) , (x ′ 1 , x ′ 2 )) = k 1 (x 1 , x ′ 1 ) k 2 (x 2 , x ′ 2 ). Lemma B.5 (Theorem 5.7 [31] ). Let f ∈ H 1 and g ∈ H 2 , where H 1 , H 2 be two RKHS containing real-valued functions on X , which is associated with positive definite kernel k 1 , k 2 and canonical feature map ϕ 1 , ϕ 2 , then for any x ∈ X ,f (x) + g(x) = ⟨f, ϕ 1 (x)⟩ H1 + ⟨g, ϕ 2 (x)⟩ H2 = ⟨f + g, (ϕ 1 + ϕ 2 )(x)⟩ H1+H2 ,whereH 1 + H 2 = {f 1 + f 2 |f i ∈ H i } and ϕ 1 + ϕ 2 is the canonical feature map of H 1 + H 2 . Furthermore, ∥f + g∥ 2H1+H2 ≤ ∥f ∥ 2 H1 + ∥g∥ 2 H2 . Lemma B.6. For any unlabeled dataset X n ⊂ X and any subset X Im ,MMD 2 k,α (X n , X n ) = (1 -α) 2 K, MMD 2 k,α (X Im , X n ) ≤ (1 + α 2 )K, where K = n i=1 n j=1 k(x i , x j )/n 2 , K = max x∈X k(x, x).Lemma B.6 is directly derived from the definition of α-MMD.Proof for Theorem 5.4. The proof borrows the technique introduced in [37] for decomposing the expected risk of hypotheses.Firstly, let us denote thatH 4 = H 1 ⊗ H 1 + H 1 ⊗ H 2 + H 3 , with kernel k 4 = k 2 1 + k 1 k 2 + k 3 and canonical feature map ϕ 4 = ϕ 1 ⊗ ϕ 1 + ϕ 1 ⊗ ϕ 2 + ϕ 3 .Under the assumptions in Theorem 5.4, according to Theorem 4 in [41] , we have for any x ∈ X ,h(x) = ⟨h, ϕ 1 (x)⟩ H1 , E[Y |x] = ⟨E[Y |X], ϕ 2 (x)⟩ H2 , Var(Y |x) = ⟨Var(Y |X), ϕ 3 (x)⟩ H3 where ϕ 1 , ϕ 2 , ϕ 3 are canonical feature maps in H 1 , H 2 , H 3 . Denote that m = E[Y |X] and s = Var(Y |X). Now by definition, R(h) = E [ℓ(h(x), y)] = X Y ℓ(h(x), y)p(y|x)p(x)dxdy = X f (x)p(x)dx where f (x) = Y (y -h(x)) 2 p(y|x)dy = Var(Y |x) -2h(x)E[Y |x] + h 2 (x) = ⟨s, ϕ 3 (x)⟩ H3 -2 ⟨h, ϕ 1 (x)⟩ H1 ⟨m, ϕ 2 (x)⟩ H2 + ⟨h, ϕ 1 (x)⟩ H1 ⟨h, ϕ 1 (x)⟩ H1 = ⟨s, ϕ 3 (x)⟩ H3 -⟨2h ⊗ m, (ϕ 1 ⊗ ϕ 2 )(x)⟩ H1⊗H2 + ⟨h ⊗ h, (ϕ 1 ⊗ ϕ 1 )(x)⟩ H1⊗H1 = ⟨s -2h ⊗ m + h ⊗ h, ϕ 4 (x)⟩ H4where the fourth equality holds by Lemma B. = 1/(K 2 h + 2K h K m + K s ) we have ∥βf ∥ H4 = β∥f ∥ H4 ≤ 1. Then R T (h) -R S (h) = X f (x)dP T (x) - X f (x)dP S (x) =(K 2 h + 2K h K m + K s ) X βf (x)dP T (x) - X βf (x)dP S (x) ≤(K 2 h + 2K h K m + K s ) sup ∥f ∥ H 4 ≤1 X f (x)dP T (x) - X f (x)dP S (x) =(K 2 h + 2K h K m + K s ) MMD k4 (X S , X T) where P T denotes the empirical distribution constructed by X T , so does P S . Recall Lemma B.3, we have Theorem 5.4.Proof for Theorem 5.6. Following the notations in Appendix A, we further definew * = 1/n, C 2 α = MMD 2 k,α,Xn (w * ) = (1 -α) 2 K (11) w = arg min 1 ⊤ w=1 MMD 2 k,α,Xn (w) = α K -1 - K -1 11 ⊤ K -1 1 ⊤ K -1 1 p + K -1 1 1 ⊤ K -1 1 Let p α = αp, we have (p α -K w) ∝ 1. Define ∆ α (w) := MMD 2 k,α,Xn (w) -C 2 α = g(w) -g(w * )where g(w) = (w -w) ⊤ K (w -w). The related details for proving the equality are omitted, since they are completely given by the proof of alternative expression of MMD in Pronzato [32] . By the convexity of g(•), for j = arg min i∈[n]\I * p f I * p (x i ), g (w * ) ≥ g (w p ) + 2 (w * -w p ) ⊤ K (w p -w) ≥ g (w p ) + 2 min j∈[n]\I * p (e j -w p ) ⊤ K (w p -w)where the second inequality holds with the assumption in Theorem 5.6EQUATION)where w p+1 = pw p /(p + 1) + e j /(p + 1), and obviously B upper bounds (e j -w p )⊤ K (e j -w p ). Since α ≤ 1, it holds from Lemma B.6 that∆ α (w 1 ) ≤ MMD 2 k,α,Xn (w 1 ) ≤ (1 + α 2 )K ≤ B therefore by Lemma B.1, we have MMD 2 k,α (X I * m , X n ) = MMD 2 k,α,Xn (w p ) ≤ C 2 α + B 2 + log m m + 1Consider the fact that GKH is a convergent algorithm (Lemma B.2) and the finite-sample-size error bound (10) holds without any assumption on the data, we conduct some numerical experiments to empirically compare GKHR with GKH on datasets generated by four different distributions on R 2 .Firstly, we define four distributions on R 2 :1. Gaussian mixture model 1 which consists of four Gaussian distributions G 1 , G 2 , G 3 , G 4 with mixture weights [0.95, 0.01, 0.02, 0.02], 2. Gaussian mixture model 2 which consists of four Gaussian distributionsG 1 , G 2 , G 3 , G 4with mixture weights [0.3, 0.2, 0.15, 0.35], 3. Uniform distribution 1 which consists of a uniform distribution defined in a circle with radius 0.5, and a uniform distribution defined in a annulus with inner radius 4 and outer radius 6, 4. Uniform distribution 2 defined on [-10, 10] 2 .whereG 1 = N 1 2 , 2 0 0 5 , G 2 = N -3 -5 , 1 0 0 2 G 3 = N -5 4 , 8 0 0 6 , G 4 = N 15 10 , 4 0 0 9 (a) n=1000 (b) n=3000 (c) n=10000 (d) n=30000Figure 2 : The performance comparison between GKHR and GKH with different m, n over ten independent runs. The blue line is the mean value of D, the red dotted line over (under) the blue line is the mean value of D plus (minus) its standard deviation, and the pink area is the area between the upper and lower red dotted lines.To consistently evaluate the performance gap between GKHR and GKH at the same order of magnitude, we propose the following criterionD = D 1 -D 2 D 1 + D 2whereEQUATIONEQUATIONIm is the selected samples from GKHR and X(2) Im is the selected samples from GKH. Positive value of D implies that GKH outperforms GKHR, and negative values of D implies that GKHR outperforms GKH. Large absolute value of D shows large performance gap.The experiments are conducted as follows. We generate 1000,3000,10000,30000 random samples from the four distributions separately, then use GKHR and GKH for sample selection under the low-budget setting, i.e., m/n ≤ 0.2. The α 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 m grows, when m is relatively small, the performance of GKHR is similar to that of GKH. Therefore, under the low-budget setting, GKHR and GKH have similar performance on minimizing α-MMD over various type of distributions, which convinces us that GKHR could work well in the sample selection task.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,167 training and 100,000 test images. The training sets of the above datasets are considered as the unlabeled dataset for sample selection.To offer a more intuitive comparison between various sampling methods, we visualized samples chosen by stratified, random, k-Means, USL, ActiveFT and RDSS (ours). We generate 5000 samples from a 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.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 5 , where m represents the annotation budget, n 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 on an idle server without any workload. As illustrated by the results, the 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 . The choice of α depends on the number of full unlabeled data points, independent of the information on the shape of data distribution. This may lead to a loss of effectiveness of RDSS on those datasets with complicated distribution structures. However, it outperforms fixed-ratio approaches on the datasets under different budget settings.Positive societal impact. Our method ensures the representativeness 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 resourceconstrained 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 as medical care and finance. It is worth noting that most algorithms applied in these sensitive areas are subject to this risk.Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 in Appendix C.For the finite-sample-error bound in Section 5.2, the required assumption is Assumption 5.5, the proof is given by the Proof of Theorem 5.6 in Appendix C. Other technical lemmas and their proofs 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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? 

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

- 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]

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


References
- [1] Submodularity in machine learning and artificial intelligence
- [2] An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models
- [3] LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning
- [4] Deep Submodular Peripteral networks
- [5] GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning
questions: questions: Refer to the weaknesses.
limitations: limitations: Refer to the weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Please refer to the weakness.
limitations: limitations: Please refer to the weakness.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. Some details of the experiments are unclear, such as in Table 3.
questions: questions: 1. The definition and usage of variable X in the article are inconsistent. 
2. 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.
3. In Chapter 6, the determination of the kernel and parameters seems arbitrary. Could you provide some proofs, theories, or experiments to justify them?
4. The SOTA models selected by the author in the experiments are somewhat outdated. It is recommended to include some more updated methods.
5. 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.
6. In Table 2, what sampling method did the other comparison methods adopt?
7. What dataset does Table 3 represent? What is the data distribution?
8. The author should objectively evaluate their method, including its limitations.
limitations: limitations: as Weaknesses
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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

Specifically, 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].

Additionally, 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.

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

-------

[1] Mittal, Sudhanshu, et al. Parting with illusions about deep active learning. (2019).

[2] Hacohen, Guy et al. Active learning on a budget: Opposite strategies suit high and low budgets. (2022).

[3] Yehuda, Ofer, et al. "Active learning through a covering lens." (2022).

[4] Mahmood, Rafid, et al. "Low budget active learning via wasserstein distance: An integer programming approach." (2021).

[5] Wen, Ziting, et al. "NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage." (2023).
questions: questions: Can you please elaborate on how the proposed method differs from the idea suggested in [2]?

How is the problem of selecting the labeled set of SSL different from the problem setting of active learning?
limitations: limitations: not relevant

Comments: title: Comparison with sampling methods used in low-budget AL scenarios
Thank you for your comments!
answer to the rebuttal
Thank you for your comments!
Thank you for the rebuttal!
comment: Thank you very much for taking the time to review our rebuttal. We acknowledge your concern regarding the comparison with other sampling methods used in low-budget AL scenarios [1-3]. While these methods can indeed achieve satisfactory performance in low-budget AL scenarios, they each have inherent limitations that prevent them from effectively adapting to SSL. Specifically, [1] and [3] involve a clustering step before sampling, which makes the sampling results heavily dependent on the quality of the clustering. Consequently, these methods require task-specific adjustments to the clustering algorithm, limiting their general applicability and making them unsuitable for our scenario. In contrast, [2] relies on multiple iterative rounds to enhance the model’s performance for more accurate selection of labelled samples. This iterative nature poses challenges when these methods are employed to determine labelled samples in a single pass, leading to suboptimal outcomes.

We have incorporated the above methods into FlexMatch and FreeMatch under four low-budget settings: CIFAR-10 with 40 labels, CIFAR-100 with 400 labels, SVHN with 250 labels, and STL-10 with 40 labels, and present the results in the table below. As observed, our method consistently outperforms across all settings, underscoring the superiority of our approach. Furthermore, in the theoretical section, we provide rigorous guarantees to demonstrate that our method is not only efficient but also generalizable.

| Dataset       | CIFAR-10 (40) | CIFAR-100 (400) | SVHN (250) | STL-10 (40) |
| ------------- | ---           | ---             | ---        | ---         |
| *Applied to FlexMatch* |      |                 |            |             |
| TypiClust     | 91.58         | 46.57           | 90.36      | 74.44       |
| Wasserstein   | 91.64         | 46.76           | 90.22      | 73.45       |
| NTKCPL        | 87.47         | 44.48           | 91.13      | 73.69       |
| RDSS (Ours)   | **94.69**     | **48.12**       | **91.70**  | **77.96**   |
| *Applied to FreeMatch* |      |                 |            |             |
| TypiClust     | 92.38         | 47.26           | 93.09      | 77.30       |
| Wasserstein   | 92.72         | 46.53           | 92.12      | 74.18       |
| NTKCPL        | 91.30         | 46.17           | 91.73      | 78.06       |
| RDSS (Ours)   | **95.05**     | **48.41**       | **94.54**  | **81.90**   |
|  |  |  |  |  |

[1] Active learning on a budget: Opposite strategies suit high and low budgets. ICML, 2022.   
[2] Low budget active learning via wasserstein distance: An integer programming approach. ICLR, 2022.  
[3] NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage. arXiv preprint, 2023.
Thanks for your explanation. I have no other problems. Good luck!
Thank you for your thorough review. We apologize for any confusion caused. The images presented in Figure 1 depict an actual sampling result from our method on the CIFAR-10 dataset, where we set the sample size to 40, rather than serving as a conceptual illustration. More detailed experimental settings can be found in the RDSS.py file within the supplementary materials we have uploaded.
I appreciate the author's rebuttal and the efforts made to address my concern. I have noticed the new visualization results. Additionally, I would like to ask whether the feature distribution and corresponding sample images in Fig 1 are the results of actual experiments or merely conceptual illustrations. If they are just conceptual illustrations, providing the distribution from actual experiments would be more convincing.
I appreciate the authors' detailed rebuttal and the efforts made to address the concerns raised.

However, my major concern regarding the comparison to other works in the field remains. While I acknowledge the distinction between active learning (AL) and semi-supervised learning (SSL), I still believe that when the labeled set in SSL is predetermined, it can be viewed as a specific instance of AL—where the initial budget is zero, and the labeled set chosen for SSL serves as the active set. Given the extensive body of work addressing these settings in AL, particularly in low-budget AL scenarios, I believe the paper should include a more thorough comparison to such works. This would better position the paper within the current literature and clarify how it advances the state of the art, if at all.

Some of these concerns have been alleviated by the authors' inclusion of an initial comparison to low-budget AL methods in the rebuttal. However, I still find the current framing of the paper somewhat misleading. A peer-reviewed revision would be necessary to incorporate the required changes effectively.

In light of the partial resolution of my concerns, I am adjusting my score to 4. Nevertheless, I remain inclined to recommend rejection of the current revision.
Thank you very much for taking the time to review our rebuttal. We are currently conducting comparative experiments similar to the work in [2] (same citations as above) and fine-tuning the CLIP model on the ImageNet dataset. Due to the time constraints and the large volume of data, we were unable to complete these experiments by the discussion phase. However, we will include these experimental results in the next version of the manuscript.
I thank the authors for rebuttal. GLISTER seems to be doing some bi-level optimization, so I am not sure how it is same as solving FL optimization, but what I was hoping for is something similar to done in say [2] (same citations as above). 


I also thank the authors for adding the results for fine-tuning CLIP model. Ideally I'd appreciate error bars, as well as going beyond CIFAR 10/100 since it is fine-tuning the CLIP model, one can get decent Imagenet performance too. (As in Labelbench) 


I will retain my score, and hoping the discussion and new results mentioned here in the next version of the manuscript.
Thank you very much for taking the time to review our rebuttal. We appreciate your acknowledgement and are glad to have addressed your concerns. Given the significance of our findings and the rigorous methodology we employed, we believe our work makes a valuable contribution to the SSL field. We would be grateful if you could kindly reconsider your evaluation in light of the clarifications and contributions highlighted in our rebuttal.
Thank you for your rebuttal. I have no quetions.