acceptodds
Withdrawn from ICLR 2027

A Safe and Reliable Active Learning Method

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Active learning (AL) aims to alleviate the annotation cost of deep supervised learning. Recently, coverage-aware AL methods obtain state-of-the-art performance across a wide range of budget settings. However, existing approaches often pay limited attention to the purity component of the coverage-purity framework. Explicitly optimizing purity in AL is challenging because of the inherent trade-off between coverage and purity, as well as the lack of an effective mechanism for incorporating purity into the AL process. To address these issues, we introduce the safe zone framework which identifies reliable, high-purity regions within the unlabeled pool and thereby preserves the purity of the total covered area. We further provide theoretical guarantees for the purity achieved by the resulting safe zone. Subsequently, we propose SafeHerding, an efficient purity-aware AL method that prioritizes high-purity samples to improve model performance. The safe zone framework provides the foundation for key components of SafeHerding, including coverage optimization and kernel herding paradigm. In addition, SafeHerding incorporates a novel skipping strategy to manage the intrinsic trade-off between coverage and purity. Experimental results across different learning settings demonstrate that SafeHerding consistently outperforms existing baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Active Learning, Kernel Herding

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tZwPOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the safe-zone framework for explicitly considering purity in coverage-based active learning. It consists of search region by leveraging labeled samples as centroids, and reduce the boundary itself when observing the different sample compared to centroid label of the region. It proposes two part: SafeHerding that combines with UHerding and agreement-based skipping controlled with the usage of safe-zone as training procedure.

Critical strengths

S1. Problem setting. It is meaningful that the paper considers the purity under the sample selection of existed coverage.

S2. Leverage the observed information without additional labeling cost. It is practical of reuse design in self-correction and configuration of search region with already acquired labeled sample.

S3. Experiment and ablation studies. The paper shows the evaluation results of various baselines including supervised learning, transfer learning, and various label budget. Furthermore, it provides the analyses of self-correction and agreement-based skipping.

Critical weaknesses

W1. The gap between assumption of Theorem 1 and self-correction rule. The algorithm selects the closest hyperplane, and move the boundary with centroid preservation condition. In contrast, the proof of Theorem 1 relies on the condition that selected hyperplane and updated threshold preserve the unknown pure region. Preserving centroid does not guarantee preserving the entire of pure region, and the closest hyperplane might not be equivalent to the proof-required hyperplane. Therefore, current proof cannot support the purity guarantee of self-correction rule.

W2. Finite convergence does not mean high purity. It is hard to conclude the high purity in final region by reducing the search region monotonically in the finite unlabeled pool. In particular, self-correction reacts only the sample verifying labels by querying, but in the finite label budget, samples, which are different label in the region, but not queried, can be remained in the region. To apply the conclusion of final region in Theorem 1, it should specify the condition that which sample can be observed.

W3. inconsistent result of initial round. To the best of my understanding, SafeHerding should be equivalently working with UHerding when ∣Lt∣<M|L_t| < M, but Figure 2-5 and 11-17 are not. Please explain why the number is different at the first round.

W4. Gap between author's intent and equation of local skipping. Authors described that the purpose is to alleviate the safe-zone constraint, but the kernal value of skipped area is 0 according to Eq. 13. As a result, candidate pool is reduced and the previous coverage credit can be diminished.

W5. Missing baseline. In my understanding, ProbCover is the most suitable baseline of this paper. The authors should be explain the justification why ProbCover is missing.

W6. Scalability. After self-correction, the cost should be O(∣U∣M2d)O(|U|M^2d), thereby the runtime should be increased (x1.9) in DomainNet while we can get the slight improvement (+0.2 percentage points). Is there any solution to solve the scalability in the proposed method?

Questions for authors

See the weakness.

6 comments

We sincerely thank Reviewer tZwP for the constructive comments and valuable feedback. We address the raised concerns and questions as follows:

Weakness 1:

SafeHerding assumes that a non-empty purity region exists around each centroid, and the role of the self-correction algorithm is to refine the separating hyperplanes so that the corresponding search region captures this pure neighborhood. We explicitly incorporate this assumption into Theorem 1 to align the theoretical analysis with the intended behavior of the method and to ensure a valid finite convergence guarantee.

Even without enforcing centroid preservation, the finite-convergence result of Theorem 1 would still hold. However, the algorithm could then converge either to a pure region that does not contain the original centroid but shares its label, or to a trivial region. The theorem further shows that any suitable hyperplane can, in principle, be updated to remove an erroneous sample while preserving finite convergence. In our implementation, we instead select the hyperplane closest to the erroneous sample in order to limit unnecessary removal of neighboring samples and prevent the search region from shrinking too aggressively. The more important issue is that finite convergence alone does not necessarily imply convergence to a high-purity region. This distinction was not sufficiently analyzed in the original manuscript, which understandably led Reviewer tZwP and other reviewers to question the purity guarantee of the method.

Weakness 2:

The distinction between finite convergence and the purity guarantee has been addressed in our response to Reviewer u48Q (Weakness 1), with a detailed theoretical analysis included in the revised manuscript. We briefly summarize the key results below:

  • We establish the conditions governing both finite convergence and the purity guarantee of the self-correction algorithm in relation to the boundedness of the search region. For a bounded search region, Theorem 2 (Purity Guarantee in Bounded Search Region) shows that the algorithm can always update an appropriate hyperplane to remove an erroneous sample while preserving the centroid. Consequently, upon convergence, self-correction recovers a pure region around the centroid whenever such a region exists. In contrast, for an unbounded search region, certain erroneous samples may not be removable under the centroid-preservation constraint.

  • Under assumptions on the numbers of bounded and unbounded regions, the probability of selecting each region, and the conditional sample distribution within each region, we derive both the probability of selecting a non-correctable sample and the expected number of such samples in Theorem 3 (Probability of Selecting a Non-Correctable Sample). The primary factors affecting the likelihood of selecting non-correctable samples are the annotation budget B\mathcal{B}, which can be controlled in practice, and the number of unbounded regions M2M_2, which is determined by the geometry of the centroids and cannot be directly controlled.

In conclusion, the self-correction algorithm does not theoretically guarantee both finite convergence and high purity in all cases. When sufficient label information is available, it can reliably recover a high-purity region within a bounded search region. Extending this guarantee to unbounded regions remains an important direction for future work. In our experiments, however, we did not observe any non-correctable samples.

Weakness 3:

Theoretically, while ∣Lt∣<M|\mathcal{L}_t|<M and SafeHerding is still collecting centroids to construct the safe zones, its sampling behavior is equivalent to UHerding. Following the UHerding protocol, we use a continuous active learning process from the low- to high-budget regimes, rather than restarting from a cold start for each regime. Therefore, this equivalence is expected only during the first few rounds of the low-budget regime. As shown in Figures 2--5, SafeHerding and UHerding coincide for the first two rounds on CIFAR10 and for the first round on the remaining datasets; their behavior diverges once the safe-zone constraint becomes active.

Minor accuracy differences may still appear in these early rounds despite using the same random seeds. We attribute these fluctuations to nondeterministic CUDA operations, since our implementation did not enforce fully deterministic execution, e.g., we do not have this line in our code torch.use_deterministic_algorithms(True). Nevertheless, this numerical nondeterminism does not imply a fundamental difference in acquisition behavior. As further shown by the coverage and impurity analyses in Figures 4--10, systematic differences between SafeHerding and UHerding emerge only after the safe-zone constraint is introduced.

Weakness 4:

We agree with Reviewer tZwP that the local skipping mechanism does not immediately remove the entire safe-zone constraint; instead, it further restricts the search space of SafeHerding. This behavior is intentional: the safe-zone constraint progressively narrows the search regions to prioritize high-purity samples and is completely removed only when the global skipping condition is satisfied, after which SafeHerding resumes sampling from the entire space.

Although local skipping excludes certain regions from subsequent searches, samples previously selected from these regions remain in the labeled set Lt\mathcal{L}_t and continue to contribute to training the learner f^\hat{f}. Thus, information from the skipped regions is retained. Moreover, as shown in Proposition 3, a low empirical classification error of f^\hat{f} indicates that these regions are already sufficiently represented by the current labeled set, making further queries from them potentially redundant. Local skipping therefore redirects the sampling process toward regions that are less well-represented by Lt\mathcal{L}_t, improving the diversity and generalization of the labeled set. Once the labeled set sufficiently represents all search regions, global skipping removes the safe-zone constraint entirely, allowing SafeHerding to explore the full space and recover potentially informative samples that may have been excluded during self-correction.

Weakness 5:

We respectfully disagree that ProbCover is the most appropriate baseline for our study. ProbCover models coverage and purity through fixed-radius neighborhoods around samples, making its performance sensitive to the choice of radius. MaxHerding and UHerding address this limitation by adopting kernel herding, which provides a more flexible formulation of coverage and purity. Since SafeHerding is also built upon the kernel-herding framework, we consider MaxHerding and UHerding to be the most relevant baselines for comparison. Moreover, MaxHerding has already been shown to outperform ProbCover, and UHerding consequently omitted ProbCover from its baseline set. Following this prior work, we therefore focus our comparison on MaxHerding and UHerding.

Weakness 6:

The computational complexity of the self-correction algorithm depends on the number of incorrectly assigned samples. For a search region βi\beta_i containing KiK_i such samples, computing their distances to the (M−1)(M-1) separating hyperplanes requires O(Ki(M−1)d)O(K_i(M-1)d) operations, while identifying the nearest hyperplane for each sample requires O(Ki(M−1))O(K_i(M-1)). Updating the hyperplane biases further costs O(M−1)O(M-1), and updating the skipped areas costs O(K~i)O(\tilde{K}_i) where K~i\tilde{K}_i is the number of skipped samples. Hence, the overall complexity for one region is O(KiMd+K~i)O(K_iMd + \tilde{K}_i). Considering all MM regions gives a worst-case complexity of O(KˉM2d+K~)O(\bar{K}M^2d + \tilde{K}), where Kˉ\bar{K} denotes the average number of incorrectly assigned samples per region, and K~\tilde{K} is the total number of skipped samples. Under the worst-case assumption that all queried samples are incorrectly assigned and approximately Kˉ=B/M\bar{K}=\mathcal{B}/M samples belong to each region, the total complexity becomes O(BMd+∣U∣)O(\mathcal{B}Md + |\mathcal{U}|), where U\mathcal{U} is the unlabeled set, B\mathcal{B} is the labeling budget, MM is the number of search regions, and dd is the feature dimension. This is consistent with the complexity analysis reported in our paper in term of MM.

Although the complexity is linear in MM under this assumption, SafeHerding can still incur substantial runtime when the number of regions is large; for example, on DomainNet SafeHerding uses 690 search regions. A major source of overhead is the iterative processing of individual regions and hyperplane updates required to remove incorrectly assigned samples. One possible optimization is to parallelize the hyperplane-bias updates, although this would require additional implementation effort. More broadly, developing efficient and reliable estimators of local purity could further reduce the computational cost of SafeHerding, which we consider an important direction for future work.

Reviewer_tZwPOpenReview ↗

Response to Authors

Thank you for the detailed response. The response confirms my concern rather than resolving it.

My remaining concerns are: (1) Theorems 2–3 address queried-but-non-correctable samples, but not unqueried impure samples remaining in the region (original W2). Under what observability condition does the final region become pure? (2) Does Theorem 2 hold specifically for the closest-hyperplane rule used in the implementation? (3) For W4, please clarify the effect of Eq. 13 on the coverage term in the herding objective, not only on learner training. (4) Given that CUDA nondeterminism causes visible differences in the first round, are the reported gains (e.g., +0.2pp on DomainNet) beyond seed variance?

Reviewer_SsH2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SafeHerding, a purity-aware active learning method that aims to balance coverage and purity during sample selection. The proposed safe zone framework partitions the feature space into regions based on labeled centroids and progressively refines these regions using a self-correction procedure that excludes queried samples whose ground-truth labels disagree with their region reference labels. Building on this framework, SafeHerding introduces safe coverage and an agreement-based skipping strategy to relax purity constraints when the model is considered sufficiently familiar with the corresponding regions.

The paper also provides a theoretical analysis of the convergence of the self-correction procedure and evaluates the proposed method on CIFAR-10, CIFAR-100, TinyImageNet, and DomainNet under supervised and transfer learning settings. The experimental results indicate that SafeHerding outperforms UHerding in many settings, although the improvements are not universal. Ablation studies and computational cost comparisons are also provided to investigate the contributions of the proposed components.

Critical strengths
  1. The paper explicitly addresses the trade-off between coverage and purity, which is an important limitation of coverage-aware active learning methods. The safe zone framework, self-correction procedure, and agreement-based skipping strategy form a coherent approach to this problem. In particular, the self-correction procedure uses labels obtained through the ordinary active learning process rather than requiring additional annotations for the entire unlabeled pool.

  2. The method is evaluated on multiple benchmark datasets under both supervised and transfer learning settings. The paper also examines coverage, impurity, component ablations, hyperparameter sensitivity, runtime, and memory consumption. The reported improvements over UHerding in several settings, including the low-budget CIFAR-10 experiment and the high-budget TinyImageNet experiment, provide encouraging evidence for the practical value of the proposed method.

Critical weaknesses

(1) Theorem 1 primarily establishes finite convergence of the self-correction procedure under the assumption that a non-empty pure region can be preserved throughout the refinement process. The algorithm permanently excludes incorrectly assigned samples only when they satisfy the update condition in Eq. (11). Incorrectly assigned samples that do not satisfy this condition may remain in the final region, and the paper does not derive a quantitative upper bound on their number or proportion.

Furthermore, Appendix H.1 acknowledges that the retained pure region may shrink substantially during boundary updates. Although the paper argues that a non-empty pure region can be retained, this region may become trivial. Consequently, the existence of a non-empty pure subset and the finite termination of the refinement procedure do not, by themselves, guarantee that the resulting safe zone has high purity. The statement that the remaining incorrectly assigned samples are expected to be few is not supported by a corresponding formal bound or explicit assumptions.

Since the safe zone framework is the central theoretical contribution of the paper, this gap weakens the claimed theoretical justification for purity-aware sample selection. The authors should either establish a more informative purity guarantee under clearly stated assumptions or narrow the theoretical claims to match what is actually proved.

(2) The agreement score in Eq. (16) measures the fraction of samples whose predictions agree with their region's reference label. However, agreement with a reference label is not equivalent to actual region purity. Proposition 3 gives the bound, which implies that a high agreement score provides a strong error guarantee only when the region is sufficiently pure. Yet, the true purity πi\pi_i is unavailable during active learning and is not guaranteed by the preceding theoretical analysis.

This creates a potential weakness in the skipping strategy: a region may have a high agreement score even when it contains many samples from other classes, allowing the purity constraint to be relaxed prematurely. In addition, the global criterion based on the average agreement score across regions may be sensitive to the sizes and structures of the refined regions, particularly when some regions become trivial. The paper would benefit from a more direct analysis of whether the agreement score reliably identifies regions that no longer require purity-constrained selection.

The empirical evaluation also leaves some uncertainty about the robustness and practical trade-offs of the method. Although the paper reports three independent runs, the statistical significance of the reported improvements is not clearly established. The transfer learning results are mixed: SafeHerding trails UHerding by 1.15% in the high-budget CIFAR-100 setting. Moreover, Table 3 reports a runtime of 1736.6 seconds per active learning round on DomainNet for SafeHerding, compared with 902.8 seconds for UHerding. These results do not invalidate the method, but they make it important to establish whether the performance improvements are statistically reliable and justify the additional computational cost.

Questions for authors
  1. Can the authors provide a non-vacuous theoretical guarantee on the purity of the final safe zone?

In particular, can the authors bound the proportion of incorrectly assigned samples that remain after self-correction, under explicit assumptions on the feature-space geometry or the distribution of labels? How does the guarantee change when the retained pure region shrinks substantially or becomes trivial? A clearer distinction between finite convergence and guaranteed high purity would strengthen the theoretical contribution.

  1. How reliable is the agreement-based skipping criterion when the true region purity is unknown?

Can the authors provide a post-hoc analysis comparing the agreement score with the actual purity and classification error of regions at the time they are skipped? It would also be useful to examine whether the global skipping criterion is sensitive to region size and the occurrence of trivial regions, and whether alternative aggregation strategies improve its reliability.

  1. Are the reported performance gains statistically robust and worth the additional computational cost?

Can the authors provide clearer uncertainty estimates and statistical comparisons across independent runs, particularly for settings where the gains over UHerding are modest? Additional analysis of the performance-runtime trade-off on DomainNet would also help establish the practical advantages of SafeHerding.

2 comments

We sincerely thank Reviewer SsH2 for the constructive comments and valuable feedback. We address the raised concerns and questions as follows:

Weakness 1:

We understand the Reviewer’s concern regarding the purity guarantee, particularly because the centroid-preservation condition in the self-correction algorithm may not always remove all incorrectly assigned samples. To address this issue, we provide a theoretical analysis identifying the conditions under which self-correction can fully eliminate erroneous samples and converge, together with empirical results measuring the number of non-correctable samples observed in practice. We summarize the main findings below; for a more detailed discussion, please refer to our response to Reviewer u48Q (Weakness 1).

When the search region is bounded, the self-correction algorithm can fully remove incorrectly assigned samples and converges to an error-free high-purity region, as established in Theorem 2 (Purity Guarantee in Bounded Search Region). In contrast, unbounded search regions may contain non-correctable samples that cannot be eliminated while preserving the centroid. Under assumptions on the numbers of bounded and unbounded regions, the probability of selecting each region, and the conditional sample distribution within each region, we derive both the probability of selecting a non-correctable sample and the expected number of such samples in Theorem 3 (Probability of Selecting a Non-Correctable Sample). Empirically, we observed no non-correctable samples during the SafeHerding acquisition process.

Weakness 2

The reviewer’s concern regarding the reliability of the agreement score is consistent with that raised by Reviewer u48Q, and we agree that this point warrants further clarification. We provide a detailed analysis in our response to Reviewer u48Q (Weakness 2) and in Appendix F.8 of the revised manuscript. Figure 18 shows a negative Spearman correlation between prediction-based impurity and agreement across all reported rounds, indicating that regions with higher agreement generally tend to exhibit lower impurity. Importantly, the local agreement score is intended to reflect the learner’s understanding of a region rather than the actual purity or size of a search region. This behavior is illustrated in Table 1 above. For example, after refinement, Zone 0 has a size comparable to Zone 31, yet its agreement score is only 0.7070.707, with a classification accuracy of 53.302%53.302\%. In contrast, Zone 31 achieves an agreement score of 0.9570.957 and an accuracy of 85.976%85.976\%. Similarly, although Zone 2 exhibits high actual purity from the beginning, its initial agreement score remains low at approximately 0.2660.266, together with an accuracy of only 34.224%34.224\%, suggesting that the learner has not yet sufficiently learned the region. These observations support the interpretation that local agreement primarily captures the learner’s predictive understanding of a region rather than its purity or size. Since the global agreement score aggregates local agreement across regions, it likewise reflects the learner’s overall understanding of the search regions. Together, these results provide empirical support for the reliability of the agreement score as a criterion for the skipping mechanism.

We agree that SafeHerding does not consistently outperform existing methods in the transfer learning setting. On CIFAR-100, the results are mixed, while on DomainNet, SafeHerding provides no substantial improvement despite its additional computational cost. However, we do not position SafeHerding as a replacement for coverage-aware active learning methods, but rather as a complementary option that may be advantageous in certain settings. In particular, purity-aware selection can yield clear gains in supervised learning scenarios. We believe that the effectiveness of coverage- versus purity-aware selection may depend strongly on the structure of the feature space. This raises an important open question: what properties of the feature space determine whether coverage- or purity-aware selection is more effective? In some feature spaces, coverage optimization may be more effective, whereas in others, explicitly promoting purity may provide greater benefits. This issue may be particularly relevant in transfer learning, where distributional differences between source and target feature spaces can affect the suitability of a given acquisition strategy. Understanding this relationship is therefore an important direction for future research.

Question 1:

We provide a theoretical analysis of the expected number of non-correctable samples selected by SafeHerding in Theorem 3 (Probability of Selecting a Non-Correctable Sample). A detailed discussion of this result is included in our response to Reviewer u48Q (Weakness 1). If a non-empty pure region exists around the centroid within a bounded search region, the self-correction algorithm converges in a finite number of steps to a high-purity region. If no such pure region exists, the algorithm still converges finitely, but only to a trivial solution containing the centroid itself. For unbounded search regions, finite convergence may still occur, but some incorrectly assigned samples can remain, so the resulting region is not guaranteed to be pure. Improving self-correction for unbounded regions therefore represents an important direction for future work.

Question 2:

We provide a detailed analysis of the reliability of the agreement score in our response to Weakness 2 above. Overall, local agreement primarily reflects the learner’s predictive understanding of a search region rather than the region’s actual purity or size. Moreover, as discussed in our response to Reviewer u48Q (Question 4), the covariance between local agreement and region-size-based weights is very small, indicating only a weak relationship between agreement and region size. Since the global agreement score aggregates local agreement across regions, it therefore mainly captures the learner’s overall understanding of the search space and is not strongly influenced by region size or actual purity. These observations provide further support for the reliability of our agreement-based skipping mechanism.

Question 3:

We provide a computational complexity comparison between SafeHerding and other kernel-herding baselines in Appendix F.4. SafeHerding generally incurs a higher runtime, particularly for large MM, due to the additional cost of hyperplane refinement during self-correction. We acknowledge this computational overhead as a limitation of our method. However, estimating purity in active learning is inherently challenging because only a limited number of labels are available, and we are the first to attempt this problem. Our results show that incorporating purity-aware selection can yield substantial improvements, particularly in supervised learning, although the additional cost may not always translate into better performance, as observed in some transfer learning settings.

As mentioned in Weakness 2, we do not view purity-aware selection as a replacement for coverage-based methods such as MaxHerding and UHerding, but rather as a complementary strategy. Our findings raise an important open question: what properties of the feature space determine whether coverage- or purity-aware selection is more effective? In some feature spaces, coverage optimization may be preferable, whereas in others, explicitly promoting purity can provide substantial benefits. Understanding this relationship could enable adaptive selection between coverage- and purity-aware strategies and represents an important direction for future active learning research.

Reviewer_u48QOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

To address the limitations of existing coverage-aware active learning, this paper proposes SafeHerding, which constructs a high-purity safe zone and incorporates it into the uncertainty coverage objective. Initial search regions are constructed in the feature space using the first M labeled samples selected by the sampler S as fixed centroids. Then, when the label assigned to a region differs from the true label of a sample obtained via a query, the region is refined through a self-correction process that adjusts the hyperplane, thereby forming a high-purity safe zone. Furthermore, to prevent repeated sampling of data from areas where the model has already been well-trained, a skipping strategy is introduced: when the match rate between the model’s prediction and the region label reaches a threshold, the purity constraint is omitted. Local skipping excludes each β_i from the safe zone, while global skipping removes the purity constraint when the overall match rate exceeds the threshold. This helps mitigate the trade-off between purity and coverage.

Critical strengths
  1. In an active learning environment with limited ground-truth labels, SafeHerding constructs approximate high-purity safe regions by utilizing hyperplane-based safe zone construction and self-correction. It explicitly incorporated purity into the existing coverage-aware sampling method.

  2. It is reasonable for self-correction to modify regions using newly acquired ground-truth labels. In particular, the algorithm is designed to select the hyperplane closest to the incorrectly assigned sample to minimize boundary displacement and to ensure that the centroid remains inside the region through a separate update condition.

  3. Once enough labeled samples have been collected, purity-constrained uncertainty coverage is applied, followed by a transition exploring a broader data space using skipping strategy. This strategy adaptively adjusts the coverage-purity trade-off.

Critical weaknesses
  1. Although Theorem 1 states that self-correction converges in a finite number of iterations under the assumption that a non-empty fixed pure region exists, there is no guarantee that the resulting region will be completely pure. The final region may contain incorrectly assigned samples N_i^((S) ); while the authors assume this number to be small, there is no quantitative bound for it. Therefore, Theorem 1 does not fully guarantee the purity of the resulting safe zone.

  2. The agreement score measures the consistency between the model’s predictions and the region reference labels. Although self-correction improves the purity of regions, it only corrects incorrectly assigned samples identified by labeling queries. As a result, regions with significant impurity may still exhibit high agreement, which could lead to premature skipping. Relying solely on high agreement to determine whether to relax the safe-zone constraint is insufficient.

  3. The number of search regions M affects the number of labeled samples required for initial safe-zone construction, region granularity, and computational costs. Although the authors provide sensitivity analyses, it remains unclear how to select M for new datasets with different class distributions and feature-space structures without tuning.

Questions for authors
  1. Corresponding to Weakness 1, could you provide a quantitative bound or empirical analysis for the noisy sample N in the refined safe regions?

  2. The initial centroids are taken from the initial labeled set and fixed; considering situations where a centroid that does not adequately represent the class is selected, does the composition of the centroids affect the construction of the safe zone and self-correction?

  3. Depending on the initial exploration steps for construction of the safe zone and the skipping strategy, the results may become similar to those of UHerding. It’s worth investigating whether there are sufficient intervals where purity-aware selection contributes to performance improvements. It would be helpful to have additional experiments that explicitly analyze the proportion of queries among all queries where the safe-zone constraint is activated.

  4. Since the global agreement score is computed as an unweighted average over regions, small regions with high agreement may disproportionately influence the global skipping decision. Have the authors considered a region-size-weighted agreement score?

6 comments

We sincerely thank Reviewer u48Q for the constructive comments and valuable feedback. We address the raised concerns and questions as follows:

Weakness 1:

We acknowledge that the theoretical and empirical analysis of the purity guarantees provided by the self-correction algorithm and the safe zone framework was not sufficiently developed in the original manuscript, which led to concerns from several reviewers regarding the effectiveness of SafeHerding. To address these concerns, we have added a more comprehensive analysis in Appendix H.1, including the conditions under which self-correction guarantees purity upon convergence, the probability of selecting non-correctable samples, and the expected number of such samples within a search region. Detailed proofs of the corresponding theorems are provided in the revised manuscript. Below, we briefly summarize the main results.

First, we show that the purity guarantee of the self-correction algorithm depends on whether the corresponding search region is bounded. We define this condition as follows.

Definition (Bounded and Unbounded Regions).
Let (βi)(\beta_i) denote the search region associated with centroid cic_i, characterized by the set of separating hyperplanes {(αi,j)}i≠j\{(\alpha_{i,j})\}_{i\neq j}. Without loss of generality, assume that the centroid cic_i lies on the negative side of every separating hyperplane.

The search region (βi)(\beta_i) is unbounded if and only if there exists a non-zero direction nˉ∈Rd×1\bar{n}\in\mathbb{R}^{d\times 1} such that

\qquad \forall j\neq i.$$ In this case, for any $x\in(\beta_i)$, the ray $$x(t)=x+t\bar{n}, \qquad \forall t\geq 0,$$ remains inside $(\beta_i)$, implying that the region extends infinitely along the direction $\bar{n}$. Accordingly, $(\beta_i)$ is **bounded** if and only if the only direction satisfying $$(\overrightarrow{n}_{i,j})^{T}\bar{n}\leq 0, \qquad \forall j\neq i,$$ is the zero vector $\bar{n}=0$. Within a bounded search region, any incorrectly assigned sample can always be excluded by updating an appropriate separating hyperplane while retaining the associated centroid. We formalize this property in the **Theorem 2 (Purity Guarantee in Bounded Search Region)** in the Appendix H.1. Due to OpenReview’s formatting limitations, we cannot provide the full details of **Theorems 2 and 3** here. Please refer to the revised manuscript for the complete statements. In the SafeHerding implementation, we prioritize updating the separating hyperplane that is closest to the misassigned sample while remaining farther from the centroid, thereby removing the sample without excluding the centroid. In unbounded search regions, however, there may exist incorrectly assigned samples that cannot be eliminated through such a hyperplane update while preserving the centroid. The characterization of these unbounded regions is closely connected to the geometry of Voronoi cells and the convex hull of the centroids. Let denote $\mathcal{C}$ denote the convex hull of the centroids $\lbrace c_i \rbrace^{M}_{i=1}$. A search region $(\beta_i)$ is unbounded if its corresponding centroid $c_i$ lies on the boundary of $\mathcal{C}$ [1]. Although the number of unbounded regions can be determined [2], doing so incurs substantial computational cost and lies outside the main scope of this work. Under assumptions regarding the numbers of bounded and unbounded regions, the probability of selecting each region, and the conditional sample distribution within each region, we can derive both the probability of selecting a non-correctable sample and the expected total number of such samples. These results are formalized in the **Theorem 3 (Probability of Selecting a Non-Correctable Sample)** in the Appendix H.1. In the AL setting, the probability $\gamma_j$ that a queried sample is selected from region $(\beta_j)$ depends on the underlying acquisition strategy. For instance, random sampling induces a uniform selection distribution across samples. In contrast, the conditional probabilities $p_{j,1}$, $p_{j,2}$, and $p_{j,3}$ cannot be directly estimated because the labels of the unlabeled samples are unknown. Consequently, the primary factors affecting the likelihood of selecting non-correctable samples are the annotation budget $\mathcal{B}$, which can be controlled in practice, and the number of unbounded regions $M_2$, which is determined by the geometry of the centroids and cannot be directly controlled. In practice, we conducted empirical evaluations and observed no non-correctable samples during the SafeHerding sampling process.

Weakness 2:

Table 1: Changes in agreement, prediction-based impurity, accuracy, and zone size across rounds for skipped and active zones on CIFAR-10.

ZoneRoundAgreementImpurityActual PurityAccuracy (%)Zone SizeSkip
3120.8680.0180.97084.431167✗
3170.9570.0170.98885.976164✓
220.2660.0470.90734.2241721✗
2140.9050.0400.97283.6991411✓
040.2410.0720.50921.2191640✗
0150.7070.0440.83553.302212✗
3950.2580.0690.88020.245326✗
39150.8230.0460.94972.662278✗

We acknowledge the reviewer’s concern that highly impure regions may still attain high agreement scores and thus be skipped prematurely. To investigate this issue, we have added an ablation study in Appendix F.8, with a detailed analysis provided in the revised manuscript. We briefly summarize the main findings below.

Figure 18 shows consistently negative Spearman correlations between impurity and agreement on CIFAR-10 across the rounds in which the safe-zone constraint is active. This indicates that lower impurity is generally associated with higher agreement, although the strength of the relationship varies across rounds. Table 1 further supports this observation at the region level. We select several representative zones from CIFAR-10 and analyze their behavior in detail. In particular, Zones 0 and 39 exhibit the highest impurity values observed in our experiments. At the earlier reported rounds, their impurity values range from 0.0690.069 to 0.0720.072, while their agreement scores remain low, between 0.2410.241 and 0.2580.258, and neither region is skipped. By round 15, their impurity decreases and accuracy improves as agreement increases, yet both regions remain active. These results suggest that, in the most impure cases observed, high impurity is not associated with spuriously high agreement, and the agreement-based criterion does not prematurely trigger skipping. Conversely, skipped regions typically exhibit high agreement together with low impurity, as illustrated by Zone 31. These results provide further evidence for the reliability of the agreement score and the effectiveness of the associated skipping mechanism.

Weakness 3:

As Reviewer u48Q correctly pointed out, although we provide a sensitivity analysis for different numbers of regions MM in the Appendix F.6, the current manuscript does not offer sufficient intuition or practical guidance for selecting an appropriate MM for a new dataset. We believe that the choice of MM should primarily balance two factors: the number of purity regions that can be captured and the associated computational cost. Assuming that samples in the feature space are surrounded by local purity regions, a larger MM allows the method to identify a greater number of such regions. Here, we emphasize the number rather than the size of the purity regions, as these regions may be relatively small in practice. However, increasing MM also introduces additional computational overhead, particularly during the self-correction procedure. Therefore, selecting MM involves a trade-off between capturing a larger number of potential purity regions and maintaining computational efficiency. As a practical guideline, we recommend setting MM larger than the number of classes so that each class has the opportunity to be represented by at least one region. In our experiments, we generally set MM to approximately twice the number of classes.

Question 1:

We have addressed this question in Weakness 1 above; please refer to that discussion for further details.

Question 2:

The objective of our safe zone framework is to identify local purity regions around the selected centroids. In principle, centroids may be located at arbitrary positions in the feature space; as long as a purity region exists around a centroid, our framework can identify and refine that region. We use centroids from the set Lt\mathcal{L}_t, obtained through uncertainty-coverage optimization, because these points tend to provide better coverage of their surrounding samples and are therefore more likely to be associated with larger purity regions. Nevertheless, the ability of our safe zone framework to identify a local purity region does not require the centroid to perfectly represent its class or neighboring samples. If a centroid is not sufficiently representative, the framework can still identify a purity region around it, provided such a region exists. The main impact of poorly representative centroids is instead on the performance of the learner model f^\hat{f}: if the selected samples do not adequately represent the underlying data distribution, the resulting model may produce less accurate predictions. Therefore, selecting reliable and representative centroids remains important for achieving strong overall learner performance.

Question 3:

Table 2: The proportion of safe queries in SafeHerding.

DatasetRound StartRound EndProportion (%)
CIFAR1031619.6
CIFAR100(s)22136.25
TinyImageNet21645.33
CIFAR100(t)21687.5
DomainNet-Real21193.2

To address the concern regarding the contribution of purity-aware selection, we report the proportion of queries for which the safe zone constraint is activated (i.e., safe queries) in Table 2. Overall, the transfer learning setting exhibits a substantially higher proportion of safe queries, which may partly result from its smaller number of active learning rounds compared with the supervised learning setting. In supervised learning, safe queries primarily occur during the low- and mid-budget regimes, while SafeHerding generally transitions to coverage-aware selection in the high-budget regime. Notably, the initial exploration required to construct the safe zones typically occupies only the first one or two rounds. The main behavioral difference between SafeHerding and UHerding therefore arises when the safe zone constraint is active, as reflected in their coverage and impurity results reported in Appendices F.1 and F.2. Although purity-aware selection accounts for a smaller proportion of queries than coverage-aware selection in the supervised learning setting, incorporating purity-aware selection still yields improvements in most cases, compared to total-coverage-aware methods such as UHerding and MaxHerding. This observation demonstrates the important contribution of safe queries to the overall performance of SafeHerding.

Question 4:

Table 3: Supervised learning results of SafeHerding with unweighted and weighted global agreements on CIFAR-10 and CIFAR-100. Results are reported at the last round of each budget regime.

MethodLow C10Low C100Middle C10Middle C100High C10High C100
Unweighted35.22±0.7135.22 \pm 0.7127.19±0.1627.19 \pm 0.1653.67±0.4153.67 \pm 0.4139.45±0.3539.45 \pm 0.3585.31±0.1285.31 \pm 0.1254.75±0.5054.75 \pm 0.50
Weighted35.32±0.6035.32 \pm 0.6026.98±0.2326.98 \pm 0.2353.55±0.3953.55 \pm 0.3939.22±0.4239.22 \pm 0.4285.37±0.1885.37 \pm 0.1854.69±0.4454.69 \pm 0.44

We thank Reviewer u48Q for the valuable suggestion of introducing a region-size-weighted formulation of global agreement. We implemented this variant and compared it with the unweighted formulation used in SafeHerding. The detailed results and analysis are provided in Appendix F.9 of the revised manuscript. Specifically, we define the region-size-weighted global agreement score as follows:

=\frac{\sum_{i=1}^{M}|(\beta_i)| \phi_i} {\sum_{i=1}^{M}|(\beta_i)|}$$ Figure 19 in Appendix F.9 compares the unweighted and region-size-weighted global agreement scores, along with the covariance between regional agreement and region weight across active learning rounds, on CIFAR-10 and CIFAR-100. The positive covariance between local agreement and region size explains this behavior: weighting regions by their size increases the global agreement score compared with the unweighted average. On CIFAR-10, the two agreement curves remain close throughout most rounds. Although the weighted score becomes slightly higher in the later rounds, both variants reach the skipping threshold at the same round. On CIFAR-100, the weighted score is more clearly elevated during the later rounds and crosses the threshold one round earlier.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.