{"id":"d68ada8a-a823-46b7-be12-e5ab04673937","arxiv_id":"2412.20644","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Uncertainty Herding weights coverage by model uncertainty and adapts two parameters so it matches or beats specialized active learning methods at both low and high label budgets.","lead":"This paper introduces Uncertainty Herding, an active learning method that combines representative coverage with model uncertainty to work across both small and large label budgets. The authors show it rivals or beats existing specialized methods on image classification benchmarks, and prove a finite-sample guarantee for its greedy optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central practical claim rests on the §3.2 calibration and radius heuristics, which Corollary 6 does not cover; the paper's own ablation shows the method fails without them.","rationale":"The reader identified the same weakest assumption: the adaptive temperature and radius heuristics are not covered by the theory, and the method's practical claim depends entirely on them. I agree that this is the load-bearing concern. The objective is well-defined, the submodularity argument for fixed parameters is valid, and the experiments are broad, so there is no obvious internal contradiction. The issue is that the headline claim is comparative and practical ('only method that reliably works across budgets'), while the theoretical result only applies to a fixed-parameter version of the algorithm. The ablation in §4.4 makes this concrete by showing that removing either the temperature or radius adaptation degrades UHerding below MaxHerding or Margin. This does not warrant rejection, because the heuristics could still work well in practice and the proposed diagnostic could confirm them. It does warrant keeping the conditional verdict: the paper should add a sensitivity analysis of the calibration split and temperature grid, release code, and include the most direct competitor, SelectAL, before the strong 'only method' claim can be accepted.","tokens_in":18817,"tokens_out":7961,"duration_ms":87175,"concrete_test":"Re-run the CIFAR-10 low-budget protocol of §4.1 (budgets 20–100) selecting τ* by ECE on an independent validation set of 2,000 labeled points instead of on a random split of L_t, and record the variance of margin values over the unlabeled pool under the chosen τ*. If low-budget ∆Acc drops materially, or if the margin variance is not small, then the calibration heuristic—rather than the coverage objective—is carrying the claimed low-budget robustness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim is that UHerding is the only method that reliably works across label budgets, but the mechanism that is supposed to produce this robustness is the adaptive parameter selection in §3.2. Corollary 6 and Theorem 2 concern fixed τ and σ: they show that greedy maximization of the estimated uncertainty coverage is near-optimal for that fixed objective. Algorithm 1, however, changes τ* and σ* at every round, so the guarantee does not apply to the actual method. The link to the desired low- and high-budget behavior is supplied only by Propositions 3 and 4, and neither proposition is shown to follow from the heuristics. Proposition 3 requires U(x; f) → c, but the ECE-minimizing temperature on a random split of a tiny labeled set is not proven to produce near-constant uncertainty; at very low budgets the split also further shrinks the training set. Proposition 4 requires σ → 0, but setting σ* to the minimum pairwise distance in the labeled set is a heuristic that can be dominated by a single near-duplicate pair and has no proven relationship to the coverage transition. The paper's own ablation (§4.4, Fig. 8a) shows that with fixed parameters UHerding is worse than MaxHerding at low budgets and worse than Margin at high budgets, so the entire practical advantage is carried by these unproven heuristics. Moreover, in the high-budget regime the adaptive σ* → 0 makes the Lipschitz constant Lσ = sqrt(2/e)/σ in Theorem 2 diverge, so the finite-sample guarantee is vacuous exactly where the method is claimed to specialize to uncertainty selection. The empirical claim may still be true, but it is currently supported by heuristics rather than by the theory, and by experiments that do not include the most direct competitor, SelectAL.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a single active learning method, Uncertainty Herding (UHerding), intended to work well across low, middle, and high label budgets. The method greedily maximizes an 'uncertainty coverage' objective that weights generalized coverage by an uncertainty function, and it adaptively chooses a temperature τ* (by ECE minimization on a validation split) and a kernel length scale σ* (as the minimum pairwise feature distance in the labeled set). The authors prove a finite-sample uniform-convergence bound (Theorem 2) and a (1−1/e) greedy approximation guarantee (Corollary 6) for the coverage objective, and they give limit statements (Propositions 3 and 4) showing the objective reduces to generalized coverage when uncertainty is constant and to pure uncertainty selection when σ→0. Experiments on CIFAR-10/100, TinyImageNet, DomainNet, and ImageNet report that UHerding matches or beats existing methods across regimes, and ablations show that the adaptive parameters are essential to this performance. The paper also draws connections between UHerding and several hybrid methods such as weighted k-means, ALFA-Mix, and BADGE.","tokens_in":19169,"tokens_out":3554,"duration_ms":39775,"significance":"If the practical claim is fully supported, the paper would make a useful contribution to active learning: it proposes a single objective that interpolates between representation-based and uncertainty-based acquisition, provides a nontrivial finite-sample guarantee for the coverage objective itself, and demonstrates broad empirical improvement over many baselines. The theoretical part has genuine value: Theorem 2 gives a uniform bound over all size-B subsets, correcting a gap in earlier coverage bounds, and Corollary 6 correctly combines submodularity with that bound. The connections to weighted k-means, ALFA-Mix, and BADGE are also informative and may help practitioners understand those methods. However, the central practical claim depends on two adaptive heuristics in Section 3.2 that are not covered by the theory and are only weakly validated; the paper's own ablation shows that UHerding without these heuristics fails to beat MaxHerding at low budgets and Margin at high budgets. The empirical summary in Table 1 omits error bars and significance tests, which is a serious gap given the strength of the 'only method' claim.","major_comments":[{"comment":"The central approximation guarantee does not apply to the method as actually run. Corollary 6 assumes fixed τ and σ, whereas Algorithm 1 recomputes τ* and σ* at every round. The greedy marginal-gain step in lines 4–6 optimizes the objective for the current parameters, but the theorem's (1−1/e) and finite-sample error statements are for a single fixed objective. Moreover, the adaptive σ* is defined as the minimum pairwise distance in Lt, so as |Lt| grows σ* shrinks and the Lipschitz constant Lσ = sqrt(2/e)/σ in Theorem 2 diverges; the finite-sample bound therefore becomes vacuous in the high-budget regime where the method is claimed to behave like uncertainty sampling. The paper should either state the guarantee for the actual adaptive procedure, or clearly delineate that the theory covers only the fixed-parameter objective and provide alternative justification for the adaptive case.","section":"§3.2, Algorithm 1, Corollary 6"},{"comment":"The limiting propositions are essentially definitional, and the paper does not prove that the proposed heuristics realize the required conditions. Proposition 3 requires U(x;f) → c, but the ECE-minimizing temperature on a random split of the current labeled set is not shown to produce near-constant uncertainty, especially at very low budgets where the validation split further shrinks an already tiny training set. Proposition 4 requires σ→0, but the minimum pairwise labeled-set distance is a heuristic that can be controlled by a single near-duplicate pair and has no proven relationship to the coverage transition. The importance of these heuristics is demonstrated by the ablation in §4.4: with fixed parameters, UHerding is worse than MaxHerding at low budgets and worse than Margin at high budgets. Thus the entire practical claim rests on unproven mechanisms. The authors should either prove or rigorously empirically validate that the heuristics produce the claimed limiting behavior across the tested and new settings.","section":"§3.2, Propositions 3 and 4, §4.4/Fig. 8a"},{"comment":"The headline empirical claim that UHerding 'matches or beats state-of-the-art in essentially all cases' and is 'the only method' that works in both regimes is not supported by the reported statistics. Table 1 reports only mean improvement over Random, with no error bars, confidence intervals, or significance tests; many entries are close (e.g., CIFAR10 low-budget UHerding 5.5 vs. MaxHerding 5.0, and DomainNet high-budget UHerding 2.3 vs. MaxHerding 1.0), and the underlying runs number only 3–5. Some of these differences are plausibly within run-to-run noise. The paper should include variances, per-budget error bars, and preferably statistical comparisons or effect sizes for the key claims, and should also be explicit about which differences are robust across seeds.","section":"Table 1 and §4"},{"comment":"The transfer-learning comparisons are presented as supporting the main claim, but the reported setup varies across datasets (DeiT Small for CIFAR-100, DeiT Base for DomainNet, fixed DINO features for ImageNet) and the number of runs is not consistently stated. In particular, Table 1 aggregates three very different transfer-learning settings into a single 'High' column, which can hide regime-dependent failures. Please report the number of seeds for each transfer experiment, include error bars, and avoid aggregating across qualitatively different tasks without a clear justification.","section":"§4.3 and Figure 6/Table 1"}],"minor_comments":[{"comment":"The text reads 'centeroids' in the description of ActiveFT; this should be 'centroids'.","section":"§4, ActiveFT description"},{"comment":"The right panel's axes are labeled only 'Selected'; please clarify that the horizontal axis is the number of selected/labeled points and indicate which curve is τ and which is σ.","section":"Figure 1b"},{"comment":"Proposition 4 assumes g is injective on U, but the paper does not discuss whether the SimCLR or DINO feature extractors used in experiments are injective on the finite unlabeled pools; a short remark on this assumption would be helpful.","section":"§3.2, Proposition 4"},{"comment":"The statement that the authors' replication attempts of SelectAL gave 'extremely inconsistent' results is not verifiable; it would be useful to provide a brief description of the replication setup or to soften this claim.","section":"§1, footnote 1"},{"comment":"In line 3, the vector k is defined using σ* which is computed on the same line; for readability, separate the computation of σ* from the computation of k.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's core contribution is plausible and the fixed-parameter theory is clean, but the adaptive parameter mechanism is the load-bearing part of the practical claim and is not theoretically covered or sufficiently validated. Given the strong 'only method' assertion, the experimental reporting needs error bars and significance information. I would also encourage the editor to require code release as a condition of acceptance, since the method's success depends on implementation details of the heuristics and the paper currently has no public code."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on 2412.20644. The actual new thing is the uncertainty coverage objective and the greedy UHerding algorithm built around it. That is a sensible generalization of MaxHerding: weight coverage by uncertainty, with fixed temperature and radius. The paper proves Theorem 2, a uniform-convergence bound over all size-B sets, which corrects the flawed bound in Bae et al. 2024 and handles the S subset of U issue. Corollary 6 follows cleanly via submodularity. Propositions 7-9 are also useful: they show several existing hybrids become UHerding once you swap k-means for greedy kernel k-medoids, which is a nice unifying observation. The experiments are broad: CIFAR, TinyImageNet, DomainNet, ImageNet, supervised and transfer. On the face of it, the method does consistently beat the listed baselines.\n\nNow the soft spots, in proportion. First, the strongest claim—'only method that reliably works across budgets'—is not actually established. The theory covers fixed tau and sigma. The method in Algorithm 1 changes both at every round. The bridge from the heuristics to the intended limiting behavior is two propositions that are near-tautological: if U is constant you get GCoverage, if sigma goes to zero you get pure uncertainty. What the heuristics actually do is never proven to realize those limits. The ablation in Section 4.4 is honest: with fixed parameters UHerding is worse than MaxHerding at low budget and worse than Margin at high budget. So the entire practical advantage rests on the temperature-scaling and radius heuristics. At very low budgets, the ECE split also shrinks an already small training set. I don't think that is a fatal flaw—the empirical evidence is suggestive and the heuristics are plausible—but it does mean the paper oversells itself.\n\nSecond, a technical wrinkle worth noting: in the high-budget regime, the adaptive sigma* tends to the minimum pairwise distance in the labeled set, which typically shrinks; the Lipschitz constant L_sigma in Theorem 2 grows like 1/sigma, so the finite-sample guarantee becomes vacuous exactly where the method claims to become uncertainty selection. That is not a contradiction, but it should be acknowledged.\n\nThird, the aggregate Table 1 reports means without error bars, for 3-5 runs. Fine for a first look, not enough to support 'essentially all cases'. There is also no code release and no direct comparison to SelectAL, the most relevant competitor for budget adaptation. The paper mentions replication problems with SelectAL, which is fair, but a systematic comparison would strengthen the claim.\n\nWho is this for? People working in pool-based active learning, especially low-budget methods. The uncertainty coverage objective and the corrected bound are worth having. If I were the editor I would send it to review; the reviewer should ask for code, per-budget variances, SelectAL comparison, and an honest statement that the heuristics are not covered by the theorem.","headline":"A genuinely useful new objective and a correct finite-sample bound, but the paper's strongest claim about all budgets is carried by two heuristics the theory does not cover.","tokens_in":19715,"tokens_out":2185,"would_cite":true,"duration_ms":21865,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a single active learning method, Uncertainty Herding, that it claims reliably works well at both low and high label budgets, matching or beating state-of-the-art methods in almost every tested setting.","keywords":["active learning","uncertainty coverage","low-budget active learning","submodular optimization","temperature scaling","expected calibration error","transfer learning","greedy selection"],"falsifier":"On a dataset where the model is already well calibrated even with a tiny labeled set, compute the variance of $U(x;f_{\\tau^*})$ over the unlabeled pool at budgets 20, 40, and 80. If that variance stays clearly above zero at low budgets yet UHerding still matches MaxHerding, the low-budget behavior is not coming from the calibration heuristic; if the variance stays high and UHerding drops below MaxHerding, the heuristic is load-bearing. Either outcome settles the mechanism behind the paper's central claim.","tokens_in":18590,"feed_emoji":"🎯","tokens_out":11555,"duration_ms":101679,"temperature":0.7,"pith_summary":"Active learning methods built on uncertainty collapse when the label budget is tiny, while representative-selection methods stop improving once more labels arrive. The paper proposes a single objective, uncertainty coverage, that weights each point's coverage of the data by its model uncertainty, and a greedy algorithm, Uncertainty Herding, that maximizes it. Two automatic parameter heuristics—temperature scaling that flattens uncertainty when the model is poorly calibrated, and a coverage radius that shrinks to the closest labeled pair as the budget grows—let the same method behave like a representation-based selector at low budgets and an uncertainty selector at high budgets. The paper claims this is the only method it knows of that reliably beats both families across all budgets on several image benchmarks, and proves that greedy selection nearly maximizes the true coverage.","feed_headline":"One greedy rule wins at every active-learning budget","feed_subtitle":"A coverage objective slides from representative to uncertainty-driven picks as labels grow, beating all tested baselines","key_machinery":"The load-bearing object is the uncertainty coverage functional $\\mathrm{UC}_{k_\\sigma}(S)=\\mathbb{E}_x\\left[U(x;f)\\max_{x'\\in S}k_\\sigma(x,x';g)\\right]$, an expectation over data points of the product of an uncertainty score and the maximum kernel similarity to any selected point. Because it is nonnegative, monotone, and submodular in $S$, greedy batch selection inherits the classical $(1-1/e)$ approximation guarantee for the estimated objective. The interpolation between regimes is carried by two parameter-adaptation heuristics: choose the temperature $\\tau^*$ that minimizes expected calibration error on a random split of the labeled set so that a poorly trained model's uncertainty scores become nearly constant, and set the kernel lengthscale $\\sigma^*$ to the minimum pairwise distance between already-labeled points in feature space so that coverage becomes increasingly local and eventually reduces to selecting the most uncertain points.","core_discovery":"The paper's central discovery is that the apparent clash between low-budget and high-budget active learning is not a boundary between two regimes but a parameter regime of a single objective. Uncertainty coverage is defined as $\\mathrm{UC}_{k_\\sigma}(S)=\\mathbb{E}_x\\left[U(x;f)\\max_{x'\\in S}k_\\sigma(x,x';g)\\right]$, and its empirical estimate is maximized greedily. When the uncertainty function is nearly constant the objective reduces to generalized coverage, and when the kernel radius shrinks to zero it reduces to a sum of uncertainty scores. The paper selects the softmax temperature $\\tau^*$ by minimizing expected calibration error on a split of the current labeled set and sets the kernel lengthscale $\\sigma^*$ to the minimum pairwise distance between labeled points in feature space, so the same algorithm shifts from representation-driven to uncertainty-driven selection as labels accumulate. It proves that greedy optimization of the empirical estimate reaches at least $(1-1/e)$ of the optimal true coverage minus a finite-sample error, and reports that this one method matches or beats all baselines across budgets on image classification and transfer-learning benchmarks.","pith_inferences":["Beyond the paper, the two parameter heuristics are a general recipe: any uncertainty-weighted coverage objective with a kernel over fixed features could be slotted into the same self-adjusting scheme, so the interpolation idea is likely portable to other model classes such as regression or language models.","A direct test of the mechanism would measure the variance of $U(x;f_{\\tau^*})$ over the unlabeled pool at very small budgets; the paper's Proposition 3 predicts it should be near zero, and the method's low-budget wins would be expected to vanish where it is not.","The labeled-set split used for temperature selection consumes scarce labels at the lowest budgets; a natural extension is to estimate the temperature on a fixed validation set or on pseudo-labels so the fewest possible labels are diverted from training."],"forward_implications":["With a fixed uncertainty measure—margin, entropy, or confidence—UHerding performs about equally well, so practitioners can choose the uncertainty notion that is cheapest or most natural for their problem.","At small budgets the algorithm behaves like MaxHerding-style representative coverage, at large budgets like uncertainty sampling, and between those extremes it interpolates smoothly rather than requiring a discrete regime switch.","The same temperature and radius adaptation also improves existing hybrid methods such as BADGE when their clustering step is replaced with greedy kernel k-medoids.","The greedy selection inherits a $(1-1/e)$ approximation guarantee for the empirical uncertainty coverage and a corresponding near-optimality bound for the true coverage, so the method does not give up its theoretical grounding to gain robustness across budgets."],"supporting_citations":[{"why":"Defines generalized coverage and MaxHerding, the representation-based predecessor whose greedy formulation UHerding extends.","marker":"Bae et al. (2024)"},{"why":"Demonstrates that uncertainty-based methods can be worse than random in low budgets, motivating the low-budget regime and the Typiclust baseline.","marker":"Hacohen et al. (2022)"},{"why":"Introduces the covering-lens formulation and ProbCover, which the paper's uncertainty coverage generalizes.","marker":"Yehuda et al. (2022)"},{"why":"Proposes SelectAL for switching between low- and high-budget strategies, which the paper reproduces poorly and aims to replace with continuous interpolation.","marker":"Hacohen & Weinshall (2024)"},{"why":"Supplies temperature scaling, the post-hoc calibration method used to flatten uncertainty at low budgets.","marker":"Guo et al. (2017)"},{"why":"Defines expected calibration error, the criterion used to select the temperature in parameter adaptation.","marker":"Naeini et al. (2015)"},{"why":"Provides the submodular maximization approximation bound that Corollary 6 applies to greedy UHerding.","marker":"Nemhauser et al. (1978)"},{"why":"BADGE is the hybrid baseline and the variant shown to improve when the paper's parameter adaptation is added.","marker":"Ash et al. (2020)"},{"why":"ALFA-Mix is a hybrid baseline shown to be equivalent to UHerding under a particular uncertainty choice.","marker":"Parvaneh et al. (2022)"},{"why":"ActiveFT is the transfer-learning baseline that defines the fine-tuning evaluation setting.","marker":"Xie et al. (2023)"}],"fun_headline_variants":["Meet Uncertainty Herding: top active learning at any budget","One objective matches or beats all active learning baselines","Uncertainty Herding: one greedy rule for every label budget","No more budget tuning: one active learning rule for all"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method's versatility rests entirely on two parameter heuristics: the calibration-error-chosen temperature must flatten uncertainty scores into an almost-constant function when the labeled set is tiny, and the radius chosen as the closest labeled pair must keep shrinking as labels grow, since the paper's own ablations show that disabling either heuristic makes the method lose to both MaxHerding and Margin.","fun_headline_variants_meta":{"raw":{"variants":["Meet Uncertainty Herding: top active learning at any budget","One objective matches or beats all active learning baselines","Uncertainty Herding: one greedy rule for every label budget","No more budget tuning: one active learning rule for all"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000315,"raw_usage":{"total_tokens":1783,"prompt_tokens":941,"completion_tokens":842,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":774}},"tokens_in":557,"tokens_out":842,"duration_ms":8187,"temperature":1.0,"reasoning_tokens":774,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:14:46.902881+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a dataset where the model is already well calibrated even with a tiny labeled set, compute the variance of $U(x;f_{\\tau^*})$ over the unlabeled pool at budgets 20, 40, and 80. If that variance stays clearly above zero at low budgets yet UHerding still matches MaxHerding, the low-budget behavior is not coming from the calibration heuristic; if the variance stays high and UHerding drops below MaxHerding, the heuristic is load-bearing. Either outcome settles the mechanism behind the paper's central claim.","supporting_citations":[{"cited_title":"Generalized coverage for more robust low-budget active learning","cited_arxiv_id":null,"evidence_quote":"Defines generalized coverage and MaxHerding, the representation-based predecessor whose greedy formulation UHerding extends."},{"cited_title":"How to select which active learning strategy is best suited for your specific problem and budget","cited_arxiv_id":null,"evidence_quote":"Proposes SelectAL for switching between low- and high-budget strategies, which the paper reproduces poorly and aims to replace with continuous interpolation."},{"cited_title":"On calibration of modern neural networks","cited_arxiv_id":null,"evidence_quote":"Supplies temperature scaling, the post-hoc calibration method used to flatten uncertainty at low budgets."},{"cited_title":"Obtaining well calibrated probabilities using bayesian binning","cited_arxiv_id":null,"evidence_quote":"Defines expected calibration error, the criterion used to select the temperature in parameter adaptation."},{"cited_title":"Active learning by feature mixing","cited_arxiv_id":null,"evidence_quote":"ALFA-Mix is a hybrid baseline shown to be equivalent to UHerding under a particular uncertainty choice."},{"cited_title":"Active finetuning: Exploiting annotation budget in the pretraining-finetuning paradigm","cited_arxiv_id":null,"evidence_quote":"ActiveFT is the transfer-learning baseline that defines the fine-tuning evaluation setting."}],"review_version":1}