Uncertainty Herding: One Active Learning Method for All Label Budgets

(Minor) Figures in the main text are too small.

We appreciate this suggestion. We have reviewed all figures and increased the font size, especially in Figures 1 and 2, to ensure readability. If any figures remain difficult to read, please let us know and we will address it further.

Questions

The entropy-regularization: Is it just an engineering trick or a vital part of active learning? Would you mind conducting some further ablation studies, for example, combining entropy-regularization with other active learning algorithms (the MaxHerding and the margin-based uncertainty sampling)?

As discussed above, we have completely removed entropy regularization from our paper, since your questioning prompted us to recognize that it indeed was not a vital component.

The framework: This paper unifies other hybrid methods in the uncertainty coverage objective by choosing different uncertainty functions and kernels. Does this framework provide any (theoretical or empirical) insights into selecting the uncertainty functions or the kernels in practice?

We appreciate this question, and will add some more discussion of it to the final paper.

From our experiments, it appears that the specific choice of uncertainty function $U(\mathbf{x}; f\_\tau)$ (e.g., Entropy, Margin, or Confidence) or the precise form of a radial basis-type kernel function $k\_\sigma(\mathbf{x}, \mathbf{x}')$ (e.g., Gaussian, Student-t, or Laplace) is not crucial to make active learning algorithms robust to different budget regimes.

In particular, Figure 3 shows that, while Margin performs slightly better than Entropy and Confidence, the differences between these uncertainty functions (blue lines) are not substantial. A similar trend is observed for UHerding, where different uncertainty measures yield comparable performance (red lines).

For kernel choice, results from Figure 7 in MaxHerding (Bae et al., 2024) suggest that, among common kernels like Gaussian, Student-t, Laplace, and Cauchy, the impact on generalization performance is minimal in active learning tasks. As discussed by Bae et al. (2024), however, the top-hat function implicitly used by ProbCover does seem to be a poor choice; this is consistent with our analysis in Theorem 2, which requires a Lipschitz kernel to show good generalization, which the top-hat function is not (but the others are).

Our findings indicate that the relative weighting between uncertainty and kernel functions across budget regimes is far more impactful. Accordingly, we provide both theoretical and empirical methods for smoothly interpolating between low- and high-budget regimes, by adjusting parameters such as $\tau$ in $U(\mathbf{x}; f\_\tau)$ and $\sigma$ in $k\_\sigma(\mathbf{x}, \mathbf{x}')$, making active learning more adaptive across budget regimes.

While reformulating existing hybrid methods, particularly BADGE, as UHerding does offer performance improvements (see Figure 6a), parameter adaptation seems more important. Thus, the main insight is to rely more on good representations in low-budget regimes, and increasingly leverage uncertainty computed using a classifier as more data points become available. Given these considerations, selecting any reasonable uncertainty and kernel functions should suffice.

Thank you for your feedback and your work in reviewing our paper.

Weaknesses

(Major) …In that sense, the first two terms seem very natural, yet the third term is unnatural and not analyzed in the paper. On the one hand, the third term is important (and sometimes even critical) since the third term does boost the performance of the proposed algorithm. For example, in Appendix C, without entropy-regularization, the performance of Uncertainty Herding does not exceed uncertainty sampling in the high-budget regime…

We very much appreciate this comment, which made us think more deeply about the inclusion of entropy regularization. In developing the method, we added it as another way to try to assist calibration, but on reflection and further ablation studies, we think that the extra complexity is just not worth the fairly minor performance improvement it brings. We have decided to completely remove entropy regularization from our paper, and updated all the relevant text and figures with results that no longer include it. The changes are summarized as follows:

1. We re-ran all the proposed UHerding method without entropy regularization and updated the performance of UHerding in Figure 1-8 as well as Table 1.
2. We removed the paragraph explaining entropy regularization under “Handling the low-budget case: calibration” of Section 3.2.
3. We also removed an ablation study for entropy regularization previously listed under Appendix D.

All the changes are colored in blue in the revised manuscript. Without entropy regularization, the performance is sometimes worse, but sometimes better, compared to previous results with entropy regularization. In the cases where performance is worse, the gap is not large enough for any competitor to ever outperform UHerding, and for each competitor there remains some budget where UHerding wins substantially. It remains that UHerding significantly outperforms uncertainty-based methods in low- and mid-budget regimes whereas it outperforms representation-based methods in high-budget regimes.

For overall quantitative results, please refer to the updated Table 1, where UHerding is still the best (colored in green) compared to other methods on average throughout all budget regimes.

Again, we greatly appreciate this push to make our method more concise and straightforward.

(Moderate) The theory part does not contain much contribution and novelty.

Prior works on low-budget active learning, including MaxHerding (Bae et al., 2024) and ProbCover (Yehuda et al., 2022), provide lower bounds for $\hat{M}(\hat{S})$ in terms of $\hat{M}(S^\*)$, where $\hat{M}$ represents the approximate (empirical) value of the measure, e.g. GCoverage; $\hat{S}$ is the greedily selected set; and $S^\*$ is the set which optimizes $\hat{M}$ under a budget constraint. Our theoretical contribution seeks to go further. Specifically, we aim to assess the quality of greedy selection in terms of the true measure $M$, rather than its approximation $\hat{M}$.

To address this, we introduced Theorem 2 and Corollary 6, which establish a lower bound for $M(\hat{S})$ in terms of $M(S^*)$. As far as we are aware, this perspective – analyzing bounds with respect to the true measure $M$ – has not been addressed in previous active learning research.

These statements help justify the importance of a sufficiently large unlabeled set $\mathcal{U}$ relative to the acquisition budget $B$. Moreover, our analysis provides an explanation for the sensitivity of ProbCover to the radius parameter $\sigma$, as noted through the Lipschitz property of the function $k_\sigma$ (see line 208).

In terms of novelty: it is the case that our proof techniques are standard in learning theory, and we do not claim otherwise. Even so, we think the contribution is novel. Most low-budget active learning papers did not even attempt to address this problem; others, such as Bae et al. (2024), made simple claims based on a Hoeffding inequality that ignore the key point that the set $\\mathcal S$ is not independent of the points being used to estimate $\\hat M$.

If there are further specific aspects where our theoretical contributions could be clarified or strengthened, we would appreciate additional guidance. We are eager to improve our work and welcome any insights.

(Moderate) There seem to be no descriptions of how the temperature scaling changes the uncertainty function. For example, the $f\_\tau$ function in Definition 5 is used without definition.

We initially assumed that temperature scaling, as a widely recognized post-hoc calibration technique (Guo et al., 2017; Platt, 1999), might not need further explanation than the citation and its brief definition in line 248 of the original submission. However, we agree that additional clarification could be helpful, especially for readers who may be less familiar with model calibration. We have thus expanded the description slightly in lines 249-251.

Thank you for your feedback and your work in reviewing our paper.

Weaknesses

The proposed method seems to rely more on a combination of heuristics and lacks guiding principles. Some analysis is also presented only in the asymptotic regime. In particular, Proposition 4 requires $\sigma \rightarrow 0$.

We acknowledge that our method incorporates some heuristic elements, particularly for the choice of adaptive parameters. However, we would like to emphasize that these heuristics are grounded in theoretical analysis, as described in Propositions 3 and 4.

These propositions theoretically demonstrate how Uncertainty Coverage (UCoverage) can approximate Generalized Coverage (GCoverage) in low-budget regimes, and align with uncertainty measures in high-budget regimes. This analysis is based on the observations that representation-based methods work well in low-budget regimes, whereas uncertainty-based methods perform well in high-budget regimes. We believe this theoretical motivation is not only a core guiding principle for our UHerding method but also highly relevant for future research in active learning.

We would also like to highlight that the primary quantitative analysis, particularly Theorem 2 and Corollary 6, are finite-sample bounds that hold for any parameter values or dataset size.

A more intriguing question is that the paper does not provide a detailed recipe for choosing the design or detecting whether the budget is high or low.

We would like to clarify that the main goal of our paper is to avoid the need to decide whether the budget is high or low. We think this notion of discrete budget regimes, while useful, does not reflect the reality of active learning tasks (as discussed in Section 1). It seems like budget regimes are typically shaped by multiple continuous factors, including data distribution characteristics, the number of labeled data points, and model capacity, making it challenging to establish a single, clear boundary.

Even if we can find a reasonable boundary, it is more intuitive and natural to have continuous transition between different budget regimes, rather than abruptly shifting from low to high-budget at a certain point. As a result, we proposed a method that smoothly interpolates between low- and high-budget regimes. While we continue to refer to “low”, “mid”, and “high” budget regimes to give a general sense of different budget levels in our experimental analysis, the proposed UHerding method is not aware of these labels in any way.

We are unsure whether by "a detailed recipe for choosing the design" you meant the "design" of budget levels (just discussed), or something else. While our framework is flexible, we emphasize that we do suggest a default form of the kernel and a hyperparameter-free method to adapt the temperature and radius parameters, which is common to all of our experiments.

In terms of writing, although this paper builds on a line of literature, the exposition is far from self-contained; some notation and basic definitions are absent from Section 3.1.

We appreciate this concern. We have introduced the main notations and basic definitions in Section 2: Related Work and Background, which, to our understanding, is standard practice when a background section is included. Given the limited space, reintroducing these elements in Section 3 would reduce efficiency.

That said, we identified some instances, such as $\mathcal{X}$ and $k_\sigma$, where notations were not adequately clarified, and we have now added these definitions to enhance readability in the revised manuscript. If further clarification is needed in any place, please let us know; we would be very happy to improve the clarity of our paper.

Section 3.4 is poorly organized. Instead of simply citing lengthy theorems, it would provide more insights by including a coherent analysis and direct comparisons.

We appreciate this feedback as well. The propositions in Section 3.4 are intended to clarify the equivalence between UHerding and existing methods, such as weighted $k$-means and ALFA-Mix, under specific conditions. Given space constraints, while we originally wrote longer descriptions in this section, we believe that in the current form each proposition is concise (four or five lines of text, hardly "lengthy" in our opinion) but self-contained to ensure clarity.

For example, Proposition 7 shows that the weighted $k$-means algorithm with uncertainty $U'$ is equivalent to UHerding with uncertainty $U$ under a shared kernel, and we provide the necessary condition on $U$ in terms of $U’$ for this equivalence to hold. Similarly, Proposition 8 establishes that ALFA-Mix can be viewed as UHerding with the uncertainty measure $U$ defined in Eq. (3). By specifying the appropriate form of $U$ for each method, we illustrate how UHerding can generalize these approaches with appropriate adjustments to the uncertainty measure.

If there are specific parts that could be improved for clarity or coherence, we would greatly appreciate further suggestions and look forward to incorporating the reviewer’s constructive feedback.

Figures 3 and 4: The plots use the same markers for different methods.

Thank you to the reviewer for this helpful suggestion. After experimenting with different options to better differentiate the methods, we decided to use different markers to represent different active learning categories – random, uncertainty-based, representation-based, and hybrid methods – making it easier for readers to identify each approach at a glance. The changes are reflected to the revised manuscript for all the relevant figures, including Figure 3 and 4. If you have suggestions for further improvement of our visualizations, we would be very happy to hear them.

Thank you for your feedback and your work in reviewing our paper.

Weaknesses

In figure 5, there is a sudden increase in difference in accuracy from 7.2k to 8k budget. [...]

We appreciate your flagging of this point. We first want to clarify that the y-axis in both Figures 5 and 6 are $\Delta$ Acc relative to the performance of Random selection. These hikes happen when the performance of Random selection does not increase, whereas other methods improve. For example, the table shows the absolute performance of each method in Figure 5a with the budget size from 7.2k to 8k. Here, the performance of Random selection decreases by about 0.5% whereas that of the other methods improves by close to 1%, which results in such a hike that the reviewer pointed out. The degradation of performance with more number of labeled set as shown in the case of Random selection is in fact not uncommon in active learning. Although it is more common with warm-start than cold-start (Ash et al., 2020), it still does happen with cold-started active learning; for examples, please refer to Figure 16, 24-34 and more in the appendix of ALFA-Mix (Parvaneh et al., 2022).

Sometimes, instead, the performance of Random improves only very marginally, as shown in the subset of Figure 6a. Compared to the improvement of Random between 3k and 4k: 0.07%, the improvement of other methods are significantly higher – ActiveFT: 3.46%, MaxHerding: 2.16% and UHerding: 3.85%.

As suggested by the reviewer, we further investigated this phenomenon by conducting more experiments on Random selection, since it is caused by degradation / almost no improvement of Random selection. We ran Random selection with 10 seeds on CIFAR100 for Figure 5a and ImageNet for Figure 6a, and obtained the following results. On CIFAR100, the performance of Random selection no longer decreases from 7.2k to 8k and the hike is significantly flattened out, although it still exists — $\Delta$(Margin, Random): $1.37 \rightarrow 0.59$, and $\Delta$(MaxHerding, Random): $1.53 \rightarrow 0.75$. For ImageNet, the gap between 3k and 4k for Random selection increases somewhat ($0.07 \rightarrow 0.73$) but the gap with other methods e.g. $\Delta$(ActiveFT, Random) at 4k is still larger than 3k.

According to our observations, it seems like there is more than large variance of Random selection for these “hikes”. Given that it is persistent in other works as we mentioned earlier, it would be an interesting and important direction to investigate further.

Questions

Can the authors make the legend in figure 1(a) larger and more readable?

As suggested, we changed Figure 1(a) to be larger and readable along with similar changes to Figure 1(b) in the revised manuscript. Please let us know if there are any issues remaining with the modified figures.

Dear Reviewer x6W9,

Thank you once again for your thoughtful feedback, which has been valuable to improve our work. We have provided detailed responses to address all the points you raised. As the discussion phase is approaching its end, we would greatly value any additional thoughts or feedback you may have regarding our rebuttal. Your input would be very helpful as we work to improve the clarity and quality of our submission.

Thank you for your time and dedication to this review process.

Thank you for your feedback and your work in reviewing our paper.

Weaknesses

The method relies on having suitable pre-trained feature extractors and an accurate approximation of the data distribution, which might not always be feasible in real-world situations.

We appreciate this interesting point. In the modern deep learning era, it is very common to use pre-trained feature extractors, also known as foundation models; it is perhaps harder to find tasks where people do not utilize them. Foundation models are often very generalizable even for quite severe domain shift.

Even without the presence of a relevant foundation model, we want to emphasize that in pool-based active learning, we assume that we have a fairly large pool of unlabeled data points from which we select data points to annotate. In many domains, it is easy to find large amounts of unlabeled data. We can then train unsupervised/self-supervised feature extractors on the pool.

Even if there is not enough unlabeled data points or pre-trained feature extractors, we can still learn meaningful features from a limited number of unlabeled data points. In the response below to your final question, we show that only with a small fraction of data points, we can extract reasonably useful features to learn similarity between data points – essential information for kernel-based active learning methods such as MaxHerding and UHerding.

In summary, we argue that it is not hard to find pre-trained feature extractors in many domains in modern deep learning era. Even if they are not available, we can collect unlabeled data and train custom feature extractors using advanced self-supervised learning methods such as SimCLR and DINO. Even with a limited number of unlabeled data points, we can still extract meaningful features to estimate similarity between data points.

While it shows strong performance in supervised tasks, its effectiveness in transfer learning could benefit from additional validation against approaches tailored to specific domains.

We thank the reviewer for this thoughtful suggestion. First, we would like to emphasize that we have already included several methods that report results on transfer learning tasks, demonstrating their effectiveness relative to others at the time of their publication: ALFA-Mix, MaxHerding, and ActiveFT.

Among these, ActiveFT is perhaps most explicitly designed for transfer learning. However, we found that it performs significantly worse than UHerding, MaxHerding, and even ALFA-Mix after a few iterations. We believe this is because ActiveFT only considers single-iteration queries, which differs from the iterative querying approach typical in active learning. For this reason, we are uncertain that methods labeled as “tailored” for transfer learning necessarily provide the most meaningful comparisons.

However, we are eager to continue improving our work. If you have any specific suggestions for active learning methods optimized for transfer learning, we would be glad to explore and benchmark these against our method.

Questions

How sensitive is UHerding to changes in the adaptation parameters, particularly when applied to diverse datasets or models? Would a suboptimal parameter choice significantly affect performance?

We first would like to emphasize that we do not introduce any hyperparameters to tune; our procedure adapts the temperature $\\tau$ and radius $\\sigma$ itself. However, we understand the reviewer’s concern regarding the sensitivity of these choices. To validate the sensitive of the choice of adaptation parameters, we scaled up and down the selected temperature $\tau^\*$ and radius $\sigma^\*$ with scaling factor of $\pm 10, 20,$ and $40$%, and reported the results for one random seed in the table below. Please note that scale 1.00 corresponds to the “optimal” selection we proposed.

According to the results on temperature, it does not seem like the test performance (in accuracy) is sensitive to the choice of the temperature parameter. Even when scaling factor is $\pm 40$%, the performance degrades only for about $2$%. Even so, as the size of labeled points increases, it quickly catches up the performance; when it is in the high-budget regime (the labeled set size $\mathcal{L} \geq 1000$), the gap with the value selected by our method does not seem to be substantial.

Similarly, the test performance is also not very sensitive to the radius parameter $\sigma^*$. Although there is some degradation of performance, particularly in the mid-budget regime ($100 \leq \mathcal{L} \leq 1000$) for scale factor of $\pm 40$%, the gap is insignificant in other cases and regimes.

How well does UHerding perform in low-data or imbalanced data scenarios in practice, where pre-trained features may not fully capture distributional or distinguishable differences?

We first want to emphasize that all the low-budget active learning methods such as Typiclust, ProbCover and MaxHerding rely on a pre-trained feature extractors to measure the distance between data points properly. All the previous works utilize unlabeled data points to learn a good feature extractor using self-supervised learning techniques such as SimCLR or DINO.

Although training a good feature extractor using a limited number of unlabeled data points is out of scope of this work – this is one of the most fundamental problems in many machine learning tasks, including generative modeling like large language models (LLMs) and self-supervised learning tasks related to foundation models – as requested by the reviewer, we have conducted some experiments with a limited number of unlabeled data points, and provided a result in the table below. We trained a ResNet18 feature extractor using SimCLR on 0, 5k, 10k and 25k data points of CIFAR10 out of 50k data points that we initially used. (When training on 0 data points, we simply use the randomly initialized network.)

The results demonstrates that even when we use no unlabeled data points, the performance is comparable to Margin selection, which shows that even a randomly initialized feature extractor provides some useful information through the inductive bias of the network design (convolutions, Lipschitz activations, etc). With even a small number of additional unlabeled data points, e.g. 5k, the performance quickly improves and outperforms Margin selection in the low- and mid-budget regimes (labeled set size $\leq 1000$), and MaxHerding in the high-budget regime.

Dear Reviewer jSMZ,

Thank you for providing constructive feedback on our submission. We have carefully addressed all the concerns raised in your review during the rebuttal process. With the discussion phase ending in a few hours, we kindly request any further feedback you may have on our responses.

We look forward to your insights and appreciate your time and effort. Thank you.

Questions

There is a discussion about discrete and continuous budget regimes in the comparison with SelectAL. In particular, it is mentioned that this paper cover continuous budget regimes. What do these regimes mean?

First, we want to clarify that this use of "budget" refers to the total number of labeled data points. Here we used the terms discrete and continuous to describe the nature of budget regime distinctions. SelectAL assumes only two budget regimes – low and high – implying a single transition from low to high. However, we argue that budget regimes are not inherently discrete, and, in particular, not binary (i.e., limited to just low and high). Rather than assuming a single or discrete transition between budget regimes, it is more natural to view this transition as continuous; there is no sharp transition between low-budget and high-budget regimes. Rather, we think the utility of representation-based approaches mostly decreases relatively smoothly with budget, while that of uncertainty-based approaches does the opposite. We thus proposed a method smoothly interpolating between low-budget and high-budget behavior. While we still refer to low, mid, and high budget regimes to loosely indicate different budget levels, these are merely ways to split up our analysis, and not visible in any way to the UHerding method.

There isn't a formal definition of the kernel function $k$ outside Proposition 4. Do you need to assume that $k$ is in a particular form and has a "spread" parameter, $\sigma$?

Thanks for highlighting this. Every result in the paper works if $k\_\sigma(\\mathbf{x},\\mathbf{x}'; g)$ is of the form $\psi( (g(\mathbf{x}) - g(\mathbf{x}') ) / \sigma)$, for any feature mapping $g : \\mathcal{X} \\to \\mathbb{R}^d$, and $\psi : \\mathbb{R}^d \\to [0, 1]$ which is Lipschitz, has $\\psi(0) = 1$, and satisfies for any unit-norm direction $t \in \mathbb{R}^d$ that $\\lim\_{a \\to \\infty} \\psi(a t) = 0$.

Theorem 1 as submitted states the exact conditions it needs, which are weaker than those above (in particular, it doesn't need a parameter $\\sigma$). Proposition 4 was missing its assumption on $\psi$; we have added it in the revised version.

No results in our paper require $k$ to be a positive-definite kernel, nor do we need it to integrate to one (or even be integrable) as in kernel density estimation. For instance, the equivalence of MaxHerding to ProbCover shown by Bae et al. (2024) relied on using $k$ as a top-hat function, $k\_\sigma(\mathbf{x}, \mathbf{x}'; g) = \mathbb{1}(\\|g(\\mathbf{x}) - g(\\mathbf{x}')|| < \sigma)$, which is not positive-definite. (Neither is it Lipschitz, which is why our generalization theory does not apply and ProbCover estimation is so hard.) Although in practice the kernel we use is positive-definite, we can use non-kernel functions for UHerding without violating our theoretical results as long as they are in the form above. We added the definition in a footnote of the revised manuscript for clarity.

In equation (1), it would be helpful to clarify what $N$ is.

In (1), we use Monte Carlo (MC) approximation to estimate the expectation over the data distribution. Thus, $N$ is the number of Monte Carlo samples. In particular, both MaxHerding and us use the empirical data distribution for this MC approximation where the samples are from the unlabeled dataset. To clarify, we added “with $\mathbf{x}\_n \in \mathcal{U}$” to (1) in the revision.

In Algorithm 1, what is ECE in line 2? Should $U(x\_n)$ in line 5 be $U(x\_n; f\_{\tau^*})$?

ECE in Algorithm 1 stands for Expected Calibration Error (Naein et al., 2015) as described in Section 3.2. To be more clear and comprehensive, we have added a definition of ECE in a footnote of the revised manuscript.

Regarding line 5, we thank the reviewer for pointing it out; it is indeed clearer with $U(x\_n; f\_{\tau^*})$. We have also updated the relevant text in Section 3.2 to clearly define $f\_{\tau^*}$. Please let us know if it is still unclear.

Thank you for your feedback and your work in reviewing our paper.

Weaknesses

The theoretical results provide some insights but (...)

We agree that, ideally, we would be able to provide theory about how UHerding reduces generalization error of an arbitrary model. In one special case, we can: because UCoverage is a generalization of Generalized Coverage (GCoverage), when using a constant uncertainty function and training a 1-nearest-neighbor classifier, we can exploit the generalization guarantee of Bae et al. (2024) to show generalization for the full learning process. Their Theorem 1, generalizing previous work, showed a generalization error bound as (1 - GCoverage) + GPurity; they also show that MaxHerding achieves an estimated GCoverage nearly as good as is possible to obtain. Our Corollary 6 accounts for the gap between the true and estimated GCoverage; plugging the two results immediately leads to a true generalization error bound for running MaxHerding with a 1-NN classifier in terms of the best obtainable GCoverage and the GPurity.

The discussion at the end of Section 3.1 of Bae et al. (2024) gives a connection of their 1-NN bound to that of high-dimensional linear models, but requires very strong assumptions on the setting. Direct learning-theoretic analysis for non-constant U functions also seems difficult, although we agree that it would be very interesting.

There does not seem to be an empirical comparison with SelectAL and TCM.

We were eager to include the comparison with SelectAL (Hacohen et al., 2024). Unfortunately, as mentioned in Section 1 (and footnote 1), the authors of SelectAL have not released their code yet (though they indicated in private communication that they plan to do so). We attempted to reproduce their results, but were not successful.

The main issue we ran into (and could not solve) was repeatedly switching between predicted budget regimes. Although SelectAL assumes that there is one transition from low-budget to high-budget, the model we implemented based on their description alternates budget regimes multiple times. For example, although we expect the predictions on budget regimes look like (low, low, …, low, high, high, …, high) where once the model predicts “high”, it never predicts low again, the reproduced model yields sequences like (low, low, high, low, low, high, high, low, high) with intermittent “low” predictions after “high” has been predicted. This inconsistency poses a problem because applying uncertainty-based methods in low-budget regimes can significantly degrade performance, and similarly, using representation-based methods in high-budget regimes can have adverse effects. Our implementation of SelectAL therefore gave much worse accuracies than they reported, and we did not think reporting those numbers would be fair.

In fact, there is no guarantee that SelectAL prevents the model from predicting “low” again after it starts predicting “high”. Although we asked some follow-up questions to one of the authors back in September, we have not yet heard back. After seeing your review, we have contacted the author again and will aim to include a comparison to SelectAL once we receive a response.

We would also like to clarify about TCM (Doucet et al., 2024). This method simply combines TypiClust (TC) and Margin (M), switching between them based on heuristics. The authors conducted extensive experiments to determine the ideal transition points, applying TypiClust for a fixed number of steps before switching to Margin based on the setting (e.g., in Tiny and Low settings, they perform three steps of TypiClust before switching; in Medium settings, they perform two steps, and so on). While their experiments provide valuable insights, we believe their heuristic approach will not generalize well to other settings without similar in-depth experimentation, which would not be possible without labels.

There are a few ambiguities that may lead to confusion. For example, the term "budget" is never clearly defined, except in Algorithm 1, where B is referred to as the budget.

Thank you for highlighting that our use of the term “budget” was unclear; we indeed used it both to refer to the size of the labeled set $| \mathcal{L} |$ and to the number of data points to query at each step $t$, $B_t$. We conducted a thorough editing pass to clarify this distinction. In the revised text (highlighted in blue color), we now consistently define the size of the labeled set $| \mathcal{L}_t |$ as the “budget” and use “query budget” to refer to $B_t$ at each step $t$. Please let us know if any parts of the revised paper remain unclear.

Can you elaborate on the computational complexity of Algorithm 1?

There are three different major sub-parts in Algorithm 1: 1) computation of adaptive parameters $\tau^\*$ and $\sigma^\*$, 2) computation of proximity measure $k\_\sigma(\mathbf{x}, \mathbf{x}’; g)$, and 3) computation of uncertainty measure $U(\mathbf{x}; f)$.

The time complexity of computing the proximity measure is equivalent to in MaxHerding, $\mathcal{O}( { | \mathcal{U} |}^2 \cdot d)$, where $d$ is the dimension of features from the feature extractor $g$. Computing uncertainty measures takes $\mathcal{O}( | \mathcal{U} | / b \cdot M) )$ time, where $M$ is the time complexity of one forward pass of a classifier $f$ on one data point, and $b$ is the size of a batch used in inference. In practice, $\mathcal{U}$ is large enough that the additional cost to computing uncertainty measures is orders of magnitude faster than computing the proximity, so the overhead over MaxHerding in this phase is negligible.

Thus, the additional computational overhead of UHerding in Algorithm 1 compared to MaxHerding is the computation of adaptive parameters. In particular, the computation of $\tau^\*$ is more demanding, due to re-training of a classifier $f$ on the split of the labeled set $\mathcal{L}\_t$. Re-training of $f$ in low-budget regimes is quite fast in practice; even in high-budget regimes, re-training of $f$ requires about 60-70% of computation of training $f$.

We would like to emphasize that the computational overhead of UHerding is substantially lower than that of SelectAL, which requires many re-training runs to select the budget regime and cross-validate. More importantly, we believe that the computational cost for adaptation is well-justified, given the significant performance gains UHerding offers over existing active learning methods across wide range of budget regimes.

The notation in Proposition 3 can be confusing -- what does $U(x;f) \rightarrow c$ exactly mean? Shouldn't $U(x;f)$ tend not to behave like constants as the model $f$ improves?

Proposition 3 says that if the uncertainty measure of all data points in the unlabeled set $\mathcal{U}$ approaches to a non-negative constant $c$, the estimated UCoverage approaches to the estimated GCoverage up to a constant. The simplest way to achieve this is to simply select an uncertainty function which is a constant; then UCoverage directly reduces to GCoverage.

In low-budget regimes where the classifier $f$ is generally not reliable, the uncertainty measure computed using $f$ is also not reliable. Hence, we would like the uncertainty measure to be nearly constant in low-budget regimes, thus reducing essentially to the coverage measure. Rather than hardcoding a constant, however, and requiring logic to decide when to stop, we achieve $U(\\mathbf{x}; f) \\rightarrow c$ in low-budget regimes with temperature scaling, as described in Section 3.2. This adaptively applies a high temperature in low-budget regimes (thus, $U(\mathbf{x}; f) \rightarrow c$), and a low temperature in high-budget regimes.

You are right that as the model $f$ improves, it is indeed preferable for $U(x;f)$ to be distinguishable and not behave like a constant. The $\\to$ in Proposition 3 is not an arrow that goes "with time" in Algorithm 1; it is the opposite, addressing what happens e.g. temperature scaling chooses a higher value.

Regarding Section 3.4, would you argue that the framework presented in this paper generalizes some existing methods?

The proposed uncertainty coverage indeed generalizes some existing hybrid methods such as weighted $k$-means (Zhdanov et al., 2019) and ALFA-Mix (Parvaneh et al., 2022), but up to some modifications specified in Section 3.4:

1. Replace $k$-means with greedy kernel $k$-medoids (or MaxHerding); see Appendix D to find a justification of this change
2. Apply a self-supervised feature extractor $g$ instead of a feature extractor from a classifier $f$
3. Replace their uncertainty measures with:
   1. Weighted $k$-means: $U(\\mathbf{x}; f) = U'(\\mathbf{x}; f) \\cdot \\mathbb{1}[U'(\\tilde{\\mathbf{x}}; f) \\geq \\nu]$ where $\\nu \\ge 0$ satisfies $\\sum\_{n=1}^N \\mathbb{1}[U'(\\mathbf{x}\_n; f) \\ge \\nu] = M$, a pre-defined number, and $U'(\\mathbf{x}; f)$ denotes the original uncertainty measure used in weighted $k$-means
   2. ALFA-Mix — $U(\\mathbf{x}; f) = \mathbb{1} [ \\exists\\, \text{ class } j \\text{ s.t. }\\; \\hat{y} (\\alpha\_j(\\mathbf{x}) \\, g(\\mathbf{x}) + (1-\\alpha\_j(\\mathbf{x})) \\, \\bar g\_j; f ) \\neq \\hat{y}(g(\\mathbf{x}); f) ]$; please refer to Proposition 8 for the definition of each term

By making these adjustments, weighted $k$-means and ALFA-Mix can be transformed into the structure of UHerding, but without parameter adaptation. However, parameter adaptation is a crucial component for improving the generalization performance; we believe this is why weighted $k$-means and ALFA-Mix perform significantly worse than UHerding, despite their similar formulations.

In Figure 3 (high-budget), why does the relative accuracy of UHerding drop as more labels are available?

As more labeled data points become available, performance eventually reaches a saturation point, converging to the accuracy of a model trained on the full dataset. For example, CIFAR10 has 50k training samples, so the performance of all active learning methods will eventually approach that of a model trained on all 50k samples as the budget increases. CIFAR10 is a relatively easy task, so performance saturates earlier – meaning that the accuracy of a model trained on 10k samples is not substantially different from one trained on the full 50k samples. As a result, models trained with Random selection will perform similarly to those trained with active learning methods in high-budget regimes, which explains the drop of relative accuracy (the improvement over Random) as the budget grows.

Thank you for your detailed responses. I am happy to maintain my positive rating.