- 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 , 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 , 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
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 and continue to contribute to training the learner . Thus, information from the skipped regions is retained. Moreover, as shown in Proposition 3, a low empirical classification error of 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 , 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 containing such samples, computing their distances to the separating hyperplanes requires operations, while identifying the nearest hyperplane for each sample requires . Updating the hyperplane biases further costs , and updating the skipped areas costs where is the number of skipped samples. Hence, the overall complexity for one region is . Considering all regions gives a worst-case complexity of , where denotes the average number of incorrectly assigned samples per region, and is the total number of skipped samples. Under the worst-case assumption that all queried samples are incorrectly assigned and approximately samples belong to each region, the total complexity becomes , where is the unlabeled set, is the labeling budget, is the number of search regions, and is the feature dimension. This is consistent with the complexity analysis reported in our paper in term of .
Although the complexity is linear in 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.
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?
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, which can be controlled in practice, and the number of unbounded regions M2, 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 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.