acceptodds
Under review as a conference paper at ICLR 2027

Online Class-specific Conformal Prediction with Diluted Bandit Feedback

Abstract

Conformal prediction is a distribution-free framework that constructs prediction sets with prescribed coverage guarantees by calibrating scoring thresholds. Standard online calibration of these thresholds relies on observing the ground truth after each prediction, yet many deployed systems reveal far less: the learner observes only whether the true label falls in the prediction set without knowing which element is the truth, a setting called . Such a binary signal conflates the contributions of every label in the prediction set, making class-specific credit assignment ambiguous when training a base model for scoring and calibrating the thresholds. To address this challenge, we propose an online algorithm for multi-class classification, Diluted-bandit Class-specific Conformal Prediction (), which displays a prediction set whose label inclusion probabilities are controlled by the learner. DCCP capitalizes on a designed estimator to recover an unbiased class-specific signal from the binary feedback alone. This signal trains the base model and calibrates the thresholds, dedicating the prediction set to covering the true label at a prescribed rate for each class. We provide a theoretical analysis for coverage and prediction set size, and evaluate both empirically relative to reference methods.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Conformal prediction, Classification, Online Learning, Bandit Feedback

Reviews

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

This article proposes the DCCP method for online multiclass prediction with 1-bit diluted feedback. The main idea is to combine randomized prediction sets with an augmented Horvitz–Thompson estimator to recover unbiased class-specific signals for model training and threshold calibration. Theoretical analyses of class-specific coverage are provided to guarantee validity of the proposed method. My major concern is that the current theory does not establish that the base model can learn effectively from diluted feedback. There are several other issues that remain to be resolved: (1) the motivating examples are insufficient and do not align with the proposed method; (2) the technical advance over prior work has not been convincingly illustrated or discussed; (3) the justification for the randomization and estimation choices require clarification.

Critical strengths

The basic idea is reasonable: randomization makes it possible to recover an identifiable class-specific covariance signal from set-level feedback. The strategy of substituting unbiased pseudo-labels into online threshold calibration is useful.

The theoretical analysis appears broadly reasonable.

Critical weaknesses
  1. The problem setting is narrow, and the motivating scenarios have not sufficiently established its practical importance. In customer support, resolving an issue is not equivalent to the true intent being included in the output set: resolution also depends on response quality, user behavior, and the possible presence of multiple intents. Similarly, in medicine, treatment may fail despite a correct diagnosis.

  2. The paper does not show that the base model learns effectively from such feedback. Size regret is a reasonable metric. However, Theorem 2 does not establish that the error bound can be controlled; it is unclear whether the model can learn a good score from diluted feedback.

  3. The relationship to prior work is insufficiently discussed. In particular, the connections to partial-label learning, weak supervision, noisy or corrupted feedback, and partial monitoring are not systematically examined. A clearer discussion is needed to clarify the paper's technical advance over existing work.

Questions for authors

Q1. Could the authors provide more insight underlying the unbiased estimator? The basic principle appears to apply to a broad class of score functions. Could the authors characterize this broader class and explain how it informs the appropriateness of the proposed design? In particular, Equations (2) and (3) are not supported by a principled derivation from an experimental-design perspective or by an optimality analysis. What information or utility criterion motivates the inclusion rule in Equation (2), and is the augmentation in Equation (3) variance-optimal? Without such a characterization, these choices appear ad hoc.

Q2. Could the authors provide more explanations on the motivating examples? The formulation concerns not only prediction set size but also the cost of actual interventions. In customer support, the system needs to randomly include some low-probability intents in its responses. In medicine, it needs to randomly include some low-scoring diagnoses in the treatment set. The paper measures this cost only through set size, without discussing incorrect actions, user experience, or clinical losses. How should these intervention costs be accounted for?

Q3. Is size regret alone sufficient to assess the value of diluted feedback, and does using such feedback improve learning efficiency compared with using no feedback? In particular, does it improve accuracy relative to a completely frozen initial model? Does jointly updating the model and thresholds produce smaller prediction sets than using feedback only to adjust the thresholds while keeping the score function fixed?

4 comments
AuthorsOpenReview ↗

Response to Reviewer BVPE – Part I

We appreciate the reviewer's questions for clarification. Please find our itemized response below.

Weakness 1 and Question 2 — “motivating scenarios … cost of actual interventions”.

“resolving an issue is not equivalent … true intent being included” (W1).

The examples motivate §3’s original model: each instance has one true label, and feedback reports whether the prediction set contains it.

That said, you are absolutely right that actual resolution or treatment outcomes also depend on other factors. Following your suggestion, we have clarified in §1’s opening paragraph that these examples motivate an abstraction and that interpreting the medical outcome as membership feedback is a modeling assumption.

“How should these intervention costs be accounted for?” (Q2).

Set size is one efficiency criterion: acting on a larger set of candidate labels can require more resources in subsequent interventions. Every included label contributes to this measure, including low-probability labels added by randomization. Your suggestion points to a useful direction for future work: explicitly optimizing a customized objective that incorporates set size and application-specific intervention costs.

Weakness 2 — “base model learns effectively … error bound can be controlled”.

“learn a good score from diluted feedback” (W2).

Proposition 2(i) establishes that Δ\Delta is unbiased for the one-hot label. With the log-probabilities fixed before the inclusion draws, the weighted loss in Equation (4) therefore equals full-label cross-entropy in expectation. Thus, the bit provides a model-training signal as well as a calibration signal. The frozen-model comparison under Question 3 tests whether updating the model improves its predictions.

“Theorem 2 does not establish … error bound can be controlled” (W2).

The theorem quantifies the effects of score discrepancy and threshold tracking. The original discussion following Theorem 2 in §4.4 explains this dependence; the paragraph after Proposition 3 in Appendix C qualifies the benchmark comparison. Controlling the discrepancy through model learning would require additional optimization and generalization analysis.

We agree that this scope should be more prominent and have brought the benchmark qualification into the discussion following Theorem 2 in §4.4.

Weakness 3 — “relationship to prior work is insufficiently discussed”.

“clarify the paper’s technical advance over existing work” (W3).

Batra & Manwani (2021) recover an unbiased learning signal from randomized fixed-size sets, but their method does not target a prescribed coverage level. DCCP must additionally calibrate each class’s coverage while learning from the prediction set’s own feedback. This calibration changes the sampling distribution, so the learning signal must remain valid throughout those changes. Our inclusion rule and unbiased estimator jointly support model training and class-specific threshold updates. We have clarified this distinction in §4.1’s Consequence paragraph.

“partial-label learning, weak supervision … partial monitoring” (W3).

To address your suggestion, we have expanded the final two paragraphs of §2.2 to discuss set-valued feedback, partial monitoring and weak supervision (e.g., Heuillet et al., 2024; Agrawal et al., 2025), alongside the existing corrupted-feedback discussion. We would be happy to include other relevant work if you have specific papers in mind.

AuthorsOpenReview ↗

Response to Reviewer BVPE – Part II

Question 1 — “more insight underlying the unbiased estimator”.

Thank you for asking us to clarify the generality and rationale of these choices.

“broad class of score functions” (Q1).

Although our experiments use RAPS (Angelopoulos et al., 2021; Appendix B.1), unbiasedness holds for any scores fixed before the inclusion draws, provided the inclusion probabilities are known and strictly between zero and one, with independent draws across classes (Proposition 2(i)). Score choice can still affect finite-sample coverage and prediction-set size. Inspired by your question, exploring score choices that improve these properties under diluted feedback could be a direction for future work.

“What information or utility criterion motivates the inclusion rule” (Q1).

We use the sigmoid in Equation (2) to randomize the conformal score–threshold rule while preserving its ordering: increasing a class's score raises its inclusion probability, and increasing its threshold lowers it. This monotone dependence on the threshold supports the convex calibration objective in Appendix A.2 (Equation (9)). The parameter hh controls how sharply inclusion responds to the score–threshold margin, as explained below Equation (2) and examined in §5.2 (Figure 2) through its effects on coverage and set size. We do not claim that the sigmoid optimizes an information or utility criterion.

“is the augmentation in Equation (3) variance-optimal?” (Q1).

Our augmentation uses a model-based control variate to reduce variance (Bang & Robins, 2005; Dudík et al., 2011), without claiming variance optimality. Appendix A.1 derives R^\widehat R as an estimate of the membership bit’s conditional mean; subtracting it preserves unbiasedness even when the estimate is inaccurate (Proposition 2(i)). Table 3 (Appendix B.2) demonstrates variance reduction, and Table 5 (Appendix B.3) shows CIFAR-100 accuracy of 57.0% with augmentation versus 25.0% without it.

Question 3 — “accuracy relative to a completely frozen initial model … smaller prediction sets”.

Thank you for suggesting this comparison. To assess learning beyond set size, we have added an experiment with the base model frozen at initialization and only the thresholds updated (see Table 6 in Appendix B.3). On the CIFAR-10 training stream, joint training raises accumulative top-1 accuracy from 10.7% to 78.0% and reduces set size from 8.91 to 2.56 labels while both arms maintain approximately 90% marginal coverage. Model updating therefore improves accuracy and reduces set size beyond threshold calibration alone. The original Table 5 (Appendix B.3) also shows accumulative top-1 accuracy increasing as model training proceeds on all three datasets.

References

  1. Batra, G., and Manwani, N. (2021). Multiclass Classification Using Dilute Bandit Feedback.
  2. Heuillet, M., Ahmad, O., and Durand, A. (2024). Randomized Confidence Bounds for Stochastic Partial Monitoring. ICML.
  3. Agrawal, V., Pukdee, R., Balcan, M.-F., and Ravikumar, P. (2025). Learning from Weak Labelers as Constraints. ICLR.
  4. Angelopoulos, A. N., Bates, S., Jordan, M. I., and Malik, J. (2021). Uncertainty Sets for Image Classifiers Using Conformal Prediction. ICLR.
  5. Bang, H., and Robins, J. M. (2005). Doubly Robust Estimation in Missing Data and Causal Inference Models. Biometrics.
  6. Dudík, M., Langford, J., and Li, L. (2011). Doubly Robust Policy Evaluation and Learning. ICML.

Dear reviewer,

We sincerely express our gratitude for your dedicated time in reviewing our paper, and providing constructive suggestions and questions to help improve its quality. We also thank you for the opportunity to clarify our work. As the deadline approaches, could you please let us know if our earlier response is unclear and if we may have another opportunity to clarify it? We really appreciate your time and help.

Warm regards,

Authors

Thank you very much for your clarifications, which have made the results more convincing. After considering all your responses, I have decided to maintain my original score.

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

The paper studies online multi-class conformal prediction under diluted bandit feedback. After each prediction, the learner sees only whether the true label was in the set. The proposed method, DCCP, works in three steps:

  1. It includes each class independently with a known probability, so the set is randomized.
  2. It builds an augmented Horvitz–Thompson estimator, which is an unbiased estimate of 𝟙{Y=k} from the single bit.
  3. It uses the above estimator both as soft labels for a cross-entropy update of the base model and in an ACI-style update of each class’s threshold.

On the theory side, the paper gives an impossibility result for deterministic sets (Prop. 1), unbiasedness of Horvitz-Thompson estimator and a variance bound for it, a high-probability class-specific coverage gap, a bound on set size relative to a calibrated benchmark. Experiments on CIFAR-10, CIFAR-100 (20 superclasses) and SVHN show worst-class coverage near 1−α, sets larger than the baselines.

Critical strengths
  1. The setting is well motivated. Learning a model and class-wise thresholds from the set-level bit alone is a real gap between BCCP (which needs a probe) and Gollapudi et al. / Ge et al. (fixed scores, marginal coverage only). Table 1 shows this gap clearly.

  2. The idea is simple and well explained. Randomizing class membership makes the bit equal ZYZ^Y, the draw of the true class. That turns class identification into a standard importance-weighting problem. Prop. 1 explains well why some form of randomization is needed.

  3. Thm. 1 does not depend on the base model. The martingale argument only uses fresh inclusion draws.

Critical weaknesses

W1. The technical contribution is limited, and the relation to prior work is understated. Each piece is standard: inverse-propensity / Horvitz–Thompson estimation with a doubly-robust control variate; ACI-style threshold updates, made class-wise; weighting the cross-entropy by unbiased label estimates.

The analysis is also mostly standard: telescoping plus Azuma, and an OGD regret bound. The paper should say more precisely what is new compared with Batra & Manwani (2021). That work already trains a model from diluted feedback, and it also uses exploration with a randomized set and an unbiased estimator. Relative to it, the new pieces seem to be the class-wise calibration and the specific estimator augmentation. “Randomized conformal set” as contribution (i) should be positioned against that work.

W2. The paper also does not compare with Batra & Manwani (2021) combined with classwise ACI results. The paper builds on this idea, so this should necessarily be one of the baseline. The paper should also compare with full-supervision model. Table 5 should include the accuracy of the same ResNet-50 trained with full labels.

W3. Using the randomized sets in practice is a concern the paper doesn’t address. Every class appears with probability at least c (5% by default). In the paper’s own medical-diagnosis example, that means randomly adding wrong diagnoses to what a clinician sees. The same input can get different sets at different times. Empty sets are possible. The paper criticizes BCCP’s probe as unrealistic, but a fully randomized set is arguably just as hard to deploy. Please report: (a) how often sets are empty; (b) how much of the set size comes from the floor versus the margin-driven part.

W4. Experiments are limited to small label spaces only. CIFAR-100 is reduced to 20 superclasses. Scaling to many classes is the key open question, and the paper notes it in its conclusion, so results on CIFAR-100 with all 100 classes, or on ImageNet, are needed.

W5. The motivating applications aren’t tested. The paper motivates the setting with intent detection and diagnosis but evaluates only on image benchmarks.

Questions for authors
  1. What exactly is new relative to Batra & Manwani (2021) in the randomized set and the estimator? Is the difference only the class-wise calibration and R̂?

  2. Can Thm. 1 be tightened, via Freedman’s inequality or by restricting the noise to class-k instances, so that it depends on 1/√p_k or on the variance after augmentation?

  3. Does Thm. 1 hold for adversarial or adaptively chosen (X, Y) sequences? If so, please state this explicitly and test it.

  4. How do the results change with all 100 CIFAR-100 classes, and with ImageNet?

  5. What are the held-out test coverage and accuracy, rather than on the resampled training stream?

  6. How often are the sets empty, and what share of set size comes from the floor c?

  7. How does DCCP compare with an ε-exploration variant that uses a deterministic set on most rounds?

  8. How do you handle negative or large Δᵏ in the model update?

4 comments
AuthorsOpenReview ↗

Response to Reviewer ipFE – Part I

We appreciate the reviewer's concrete suggestions for strengthening our work.

Weakness 1 and Question 1 — “What exactly is new … in the randomized set and the estimator?”.

Batra & Manwani (2021) already learn from randomized sets with an unbiased estimator, but minimize mistakes without targeting a prescribed coverage level. DCCP designs the randomization, estimator, and calibration update together to learn under class-specific coverage targets.

“Randomized conformal set … positioned against that work” (W1/Q1).

Their set size is fixed in advance and hence cannot be adjusted during learning to achieve a prescribed coverage level. DCCP lets each class's score and threshold determine its inclusion probability (Equation (2)). Calibration can then correct under-coverage and adjust set size, but these adjustments also change the sampling distribution that generates the learning feedback.

“an unbiased estimator … the specific estimator augmentation” (W1/Q1).

Their estimator is derived for fixed-size sampling and has no variance-reduction term. DCCP's unbiased estimator (Equation (3)) is derived for class-specific inclusion probabilities that change with calibration. The signal therefore remains unbiased for both model training and threshold updates as calibration changes the prediction distribution. The model-based augmentation further reduces variance empirically without affecting unbiasedness.

“ACI-style threshold updates, made class-wise” (W1).

Class-wise ACI uses the true label to identify which class’s coverage error to correct; that label is unavailable under diluted feedback. Equation (7) instead uses our unbiased class-specific estimator to update the thresholds. The original §3.3 and Appendix A.2 derive this rule as an unbiased gradient update for a convex objective expressing the class-specific coverage condition, with class-wise ACI recovered in the full-feedback, deterministic-set limit.

The estimator and calibration derivations were provided in Appendices A.1–A.2; we have now clarified the sampling distinction from Batra & Manwani in §4.1's Consequence paragraph.

Weakness 2 — “compare with Batra & Manwani (2021) … full-supervision model”.

“Batra & Manwani (2021) … classwise ACI” (W2).

Class-wise ACI cannot simply be attached to Batra–Manwani’s published method: their prediction rule fixes set size and provides no guarantee at a prescribed coverage level, while ACI changes set membership through calibrated thresholds. Making the calibrated set itself generate the feedback therefore requires proposing a compatible sampling rule and estimator, since their estimator and its unbiasedness proof are derived for fixed-size sampling.

“accuracy of the same ResNet-50 trained with full labels” (W2).

Thank you for suggesting this comparison. We have added results for the same ResNet-50 trained with full labels on all three datasets in Appendix B.4 (Table 8). Take CIFAR-10 as an example: DCCP reaches 79.9% accumulative top-1 accuracy on the held-out split using membership feedback, compared with 87.2% using full labels.

AuthorsOpenReview ↗

Response to Reviewer ipFE – Part II

Weakness 3 and Question 6 — “Using the randomized sets in practice …”.

“randomly adding wrong diagnoses … different sets at different times” (W3).

The medical example concerns covering possible causes before the true cause is known, as in empiric broad-spectrum therapy (Evans et al., 2021). A candidate that later proves incorrect is not automatically an inappropriate inclusion, and deterministic prediction sets also contain incorrect alternatives. DCCP selects these candidates using inclusion probabilities determined by scores and calibrated thresholds (Equation (2)), while randomization enables its estimator to recover class-specific supervision from the set-level outcome (Equation (3)). A deployment can retain the set drawn for each assessment, so repeated viewing does not trigger resampling. Fresh prediction events may still yield different sets, allowing the method to learn from their membership feedback.

“BCCP's probe as unrealistic … just as hard to deploy” (W3).

DCCP trades a separate label-specific feedback requirement for randomized candidate selection. When an application reports only whether the displayed set succeeded, BCCP (Wang & Qiao, 2024) requires a separate probe judgment that this outcome cannot generally supply. DCCP's randomization makes learning possible directly from the available set-level outcome. This is the practical advantage of its weaker feedback requirement: no additional label-specific judgment is needed.

“how often sets are empty” (W3/Q6).

Empty predictions serve as outlier flags in Guan & Tibshirani (2022). For DCCP’s classification task over the specified label set Y\mathcal Y, we choose to return at least one candidate label. If the random draw is empty, our implementation includes the class with the highest inclusion probability, so the displayed set is never empty. We have clarified this implementation rule in §3.1’s footnote.

“how much … comes from the floor versus the margin-driven part” (W3/Q6).

At the final stream step, classes whose inclusion probabilities are clipped to cc contribute approximately 18%, 7%, and 33% of expected set size on CIFAR-10, CIFAR-100 with 20 superclasses, and SVHN, respectively.

Weakness 4 and Question 4 — “scaling to many classes”.

Following your suggestion, we have added results for all 100 CIFAR-100 classes in Table 10 (see Appendix B.7).

With more training, accumulative worst-class coverage improves from 72.6% to 83.1%, though it has not yet reached the 90% target. Accuracy is also still improving, suggesting that more training steps are needed. As discussed in §6, learning faster and producing smaller sets with many classes remain directions for future work.

Weakness 5 — “The motivating applications aren't tested”.

You are right that intent detection and diagnosis are not tested directly. The image experiments test whether membership feedback alone supports model learning and class-specific calibration—the same learning problem those examples motivate. We have clarified this role in §1’s opening paragraph.

AuthorsOpenReview ↗

Response to Reviewer ipFE – Part III

Question 2 — “Can Thm. 1 be tightened …”.

Thanks for your suggestion. We have added a variance-adaptive coverage bound using Freedman's inequality in Appendix C (Theorem 3), with the proof in Appendix D.7. The result uses Proposition 2(ii)’s variance bound. Estimation noise also arises on other classes’ examples, so restricting to class-kk instances alone does not give the proposed dependence on pkp_k.

Question 3 — “adversarial or adaptively chosen (X,Y)(X, Y) sequences”.

Thank you for this suggestion. Theorem 1’s bound remains valid when examples are chosen adaptively from past observations and random draws, provided each example is fixed before its own inclusion draws. We have revised the proof in Appendix D.3 to make this explicit.

Following your suggestion, we have also added an adaptive CIFAR-10 experiment in Appendix B.6 (Table 9). At each step, the adversary selects from a candidate pool the examples whose true labels are estimated least likely to be covered by the current model and thresholds. At matched training steps, accumulative worst-class coverage is 89.4%, compared with 89.6% for the i.i.d. stream, while prediction sets are larger.

Question 5 — “held-out test coverage and accuracy”.

Thanks for this suggestion to make our work solid. We have added results for all three datasets on a held-out split never used for updates in Appendix B.4 (Table 7). Accuracy improves throughout training on all three datasets, showing that model improvements extend to unseen examples. Take CIFAR-10 as an example: accumulative top-1 accuracy reaches 79.9%, with marginal coverage of 90.4% and worst-class coverage of 88.4%.

Question 7 — “an ε\varepsilon-exploration variant … deterministic set on most rounds”.

The class-specific coverage target applies to the whole prediction sequence, including deterministic rounds. DCCP's update (Equation (7)) calibrates its randomized prediction rule; making most rounds deterministic without changing the update does not preserve Theorem 1's guarantee. The proposed alternative therefore requires a compatible estimator and an update that calibrates the combined policy.

Question 8 — “negative or large Δk\Delta^k in the model update”.

We retain negative Δk\Delta^k as signed weights in the model loss (Equation (4)); removing them would generally bias the learning signal. The inclusion-probability bounds ensure ∣Δk∣≤1/c|\Delta^k|\le 1/c, which is 20 at our default setting (Equation (12), Appendix D.2). We do not clip Δk\Delta^k in either update.

References

  1. Batra, G., and Manwani, N. (2021). Multiclass Classification Using Dilute Bandit Feedback.
  2. Wang, Z., and Qiao, X. (2024). Efficient Online Set-valued Classification with Bandit Feedback. ICML.
  3. Guan, L., and Tibshirani, R. (2022). Prediction and Outlier Detection in Classification Problems. Journal of the Royal Statistical Society: Series B.
  4. Evans, L., et al. (2021). Surviving Sepsis Campaign: International Guidelines for Management of Sepsis and Septic Shock 2021. Intensive Care Medicine.

Dear reviewer,

We sincerely express our gratitude for your dedicated time in reviewing our paper, and providing constructive suggestions and questions to help improve its quality. We also thank you for the opportunity to clarify our work. As the deadline approaches, could you please let us know if our earlier response is unclear and if we may have another opportunity to clarify it? We really appreciate your time and help.

Warm regards,

Authors

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

The paper proposes DCCP for online classification when feedback reveals only whether a prediction set contains the true label. Randomized label inclusion enables an unbiased class-specific estimator, which jointly trains the classifier and calibrates thresholds. The paper establishes cumulative class-specific coverage and a conditional set-size bound, supported by image-classification experiments.

Critical strengths
  • A useful extension beyond BCCP: the displayed prediction set itself generates the learning feedback, eliminating the separate probe. The novelty is this integrated prediction-learning-calibration design, rather than diluted-feedback model learning alone, which already exists in Batra & Manwani (2021).
  • The estimator's unbiasedness argument is convincing under independent inclusion draws. The coverage proof appropriately separates threshold drift, estimator noise, and sampling noise; the bounded-score lemma addresses threshold confinement.
  • The algorithm and assumptions are clearly explained. The augmentation ablation provides persuasive evidence of practical variance reduction and smaller prediction sets.
Critical weaknesses

I did not identify a clear fatal error in the estimator or the main coverage proof, nor a major presentation problem. The two substantive reservations are:

  1. The size theorem does not establish end-to-end efficiency of the learned algorithm. Theorem 2 depends on the score discrepancy εt\varepsilon_t, but no bound connects its decay to the proposed model update. Moreover, the benchmark is an arbitrary calibrated predictor within the same randomized family, not necessarily a size-optimal predictor. Consequently, the result is a conditional tracking bound, not a demonstration that joint learning achieves vanishing size regret. This limits the theoretical support for a central contribution without invalidating the theorem as stated.

  2. The empirical evaluation does not sufficiently isolate the central model-learning contribution. Both ACI references use DCCP's learned scores, making them useful calibration controls but not independent learning comparisons. The experiments involve approximately 7.53 million resampled, augmented examples, an ImageNet-pretrained backbone, and accuracy measured on the online stream; no disjoint test evaluation is described. These results demonstrate learning on the resampled stream, but leave generalization to unseen examples and comparative feedback efficiency unresolved.

Questions for authors

Under what assumptions does the model update control εt\varepsilon_t in Theorem 2? Alternatively, should the result be interpreted strictly as conditional tracking rather than end-to-end size regret?

3 comments
AuthorsOpenReview ↗

Response to Reviewer QPrx

We appreciate the reviewers' suggestions and comments on our work.

Weakness 1 and Question 1 — “control εt\varepsilon_t … conditional tracking”. Theorem 2 quantifies how score discrepancy and threshold tracking affect set size relative to a calibrated benchmark. This dependence was explicit in the original §4.4, and Appendix C stated that the bound is “a comparison, not a guarantee on size.” Establishing decay of εt\varepsilon_t would require additional optimization and generalization analysis connecting the Δ\Delta-weighted cross-entropy update under one-bit feedback to the benchmark score discrepancy. We do not establish that decay or require the benchmark to be size-optimal, so conditional tracking is the intended interpretation.

That said, we agree that this scope should be more prominent, and we have added the benchmark qualification in the discussion following Theorem 2 in §4.4.

Weakness 2 — “isolate the central model-learning contribution”.

“not independent learning comparisons” (W2).

The two ACI references share DCCP's learned scores and therefore isolate calibration.

To isolate model updating, we have added a comparison with a frozen initial model whose thresholds alone are updated, evaluated on the training stream at five matched checkpoints (see Table 6 in Appendix B.3). On CIFAR-10, joint training reduces accumulative set size from 8.91 to 2.56 labels while both arms maintain approximately 90% marginal coverage. Model updating therefore reduces set size beyond threshold calibration alone.

“generalization to unseen examples” (W2).

Thanks for this suggestion to strengthen our work. We have added held-out results for accuracy, marginal and worst-class coverage, and set size to Table 7 in Appendix B.4. On this disjoint split, never used for updates, accuracy increases over training on all three datasets, showing that the model's improvement extends to unseen examples.

“comparative feedback efficiency unresolved” (W2).

Thank you for suggesting this comparison. We have also added a comparison with the same model trained with full labels in Table 8 (see Appendix B.4). On CIFAR-10, DCCP reaches 79.9% accumulative held-out accuracy, compared with 87.2% using full labels. This comparison quantifies the observed accuracy gap between diluted and full-label feedback.

Thanks for addressing my concerns! I will maintain my rating.

Thank you for your time reviewing our paper and for your constructive questions to improve it. We really appreciate it.

Comments on the paper

1 comment

Dear Reviewers,

Authors’ kindly responded to address your concerns. Please check rebuttals and share your opinions with authors. Thanks for your contributions!

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.